boij-soderberg-engine

A hand-written C++ engine for experiments in Boij–Söderberg theory. It enumerates candidate degree sequences, computes their pure Betti tables, and searches for sequences that violate two Betti-number lower-bound conjectures — the Buchsbaum–Eisenbud–Horrocks ("BEH") rank bound and an "LLBC" total-rank bound.

It was built in 2024 for the research behind a co-authored paper, Arithmetic in the Boij–Söderberg Cone (Boocher, Huang, Wolf, arXiv:2512.24320), where its exhaustive searches surfaced the counterexample candidates the paper then classifies. The repository is CLI-first and research-oriented, not a general-purpose library.

Provenance

The ~1,200-line mathematical core — src/seq_funcs.cc, src/test_funcs.cc, src/binom.cc and their headers (gen_deg_seqs, pure_betti, test_BEH, test_LLBC, calc_L) — is hand-written, no AI, and is cross-validated case-by-case against Macaulay2's own BoijSoederberg package (pureBetti). The repository was later reorganized and given its test and benchmark harness with the help of an AI coding agent.

What This Repo Does

• generate candidate degree sequences in fixed codimension,
• compute pure Betti sequences from those degree sequences,
• calculate L values and related pi_i/B_i data,
• test conjectural lower bounds (BEH and LLBC),
• collect potential counterexamples ("bad ones"),
• parse and deduplicate large batch outputs.

Historical outputs and research artifacts are kept in-repo for reproducibility. Longer operational notes, detailed CLI usage, and batch workflow material live in docs/cli_reference.md and docs/batch_workflows.md.

Performance vs. Macaulay2

On a task-matched benchmark (same machine, same candidate families, same BEH/LLBC checks, program CPU time), the engine runs roughly 70–115× faster than an equivalent Macaulay2 implementation, and at large problem sizes Macaulay2 becomes impractically slow — 17 minutes for a 20.7M search versus 11 seconds, and it had not finished a 15.9M search after 25 minutes. Because it must materialize the entire candidate list, it also eventually runs out of memory once that list outgrows RAM (as it did on the lighter hardware the 2024 research ran on).

codim	sequences (n)	C++	Macaulay2	speedup
5	1,221,759	0.88 s	100.6 s	114×
6	906,192	0.81 s	93.1 s	115×
7	1,184,040	1.79 s	156.4 s	87×
3	20,708,500	11.0 s	1,021 s (~17 min)	93×
6	15,890,700	20.6 s	>25 min (unfinished)	—

Full data across codimensions 3–7: data/processed/benchmarks/benchmark_results.csv. The "bad one" counts are identical across the C++ engine, Macaulay2's built-in pureBetti, and a Macaulay2 transcription of the same algorithm, so this is a same-task comparison, not same-answer-different-work.

In the 2024 research campaign the engine swept on the order of tens of billions of degree sequences (codimension 3 out to degree 7,100), collecting counterexamples — a scale Macaulay2 cannot reach.

Build

Requirements:

• g++ (or a compatible C++ compiler)
• make

Build the default toolset from the repository root:

make

This builds the main binaries in build/bin/, including:

• boij_soderberg_calculator
• bad_one_generator
• parse_huge_output
• remove_duplicates
• tell_which_violations
• test_program
• find_big_ones

Build extra research tools individually:

make L_finder quick_run find_172 foo

If your compiler defaults are older, build with C++17 explicitly:

make CXXFLAGS="-O2 -Wall -Wextra -std=c++17"

Clean generated build output:

make clean

Quick Start

Run the interactive calculator:

./build/bin/boij_soderberg_calculator

Sample input:

0 3 5 8

For a file-based workflow:

touch /tmp/bad_ones_demo.txt
./build/bin/bad_one_generator /tmp/bad_ones_demo.txt 3 30 1

touch /tmp/parsed_demo.txt
./build/bin/parse_huge_output data/samples/burntest.txt /tmp/parsed_demo.txt

touch /tmp/unique_demo.txt
./build/bin/remove_duplicates /tmp/parsed_demo.txt /tmp/unique_demo.txt

./build/bin/tell_which_violations /tmp/unique_demo.txt

Main Tools / Algorithms

Main executables:

• boij_soderberg_calculator: interactive entry point for entering a degree sequence and seeing its pure Betti resolution, L value, pi_i, B_i, and BEH/LLBC status.
• bad_one_generator: generates degree sequences in a search window and writes out those that fail one or both checks (full pure_betti + test_BEH + test_LLBC path).
• parse_huge_output: extracts brace-form degree sequences from noisy merged outputs.
• remove_duplicates: removes constant-multiple duplicates from a sequence list.
• tell_which_violations: reports which B_i values fail BEH and whether LLBC fails.

Core algorithms and concepts:

• Degree sequence: represented as {0,d1,d2,...,dc} with strictly increasing entries.
• Codimension c: inferred as sequence_length - 1.
• Pure Betti sequence: computed by pure_betti(...) in src/seq_funcs.cc via a reformulation of the Herzog–Kühl equations.
• BEH check: test_BEH(...) compares each Betti entry against its binomial lower bound.
• LLBC check: test_LLBC(...) compares the total Betti sum against its lower bound.
• L value: computed from the reduced pi_i denominators, used to scale a pure Betti table to integers.
• pi_i values: rational factors associated to a degree sequence before clearing denominators.
• Bad ones: degree sequences whose pure Betti data fail BEH, LLBC, or both.
• Rinsing/deduplication: gcd_rinse(...) is a quick filter and rinse_seqs(...) removes constant-multiple duplicates more thoroughly.

Detailed executable usage and development-facing tools are documented in docs/cli_reference.md.

Data Format

Preferred sequence format:

{0,1,2,3}

Parsing expectations:

• Degree sequences are modeled as strictly increasing sequences beginning with 0.
• parse_huge_output scans for {...} patterns and extracts comma-separated integers.
• Compact brace format with no spaces is the safest form for downstream tools such as remove_duplicates.

Additional parsing notes, batch scripts, and benchmark commands are documented in docs/batch_workflows.md.

Repository Layout

• apps/ — executable entry points and one-off research drivers.
• src/ — shared implementation for sequence generation, Betti computations, checks, and utilities.
• include/ — headers for the shared C++ code.
• scripts/ — shell helpers for demos, benchmarks, and batch processing.
• data/ — stored inputs and outputs (raw/, processed/, samples/, archive/).
• docs/ — CLI reference and batch-workflow notes.
• research/ — archived experiments, historical code snapshots, and Macaulay2 material.
• build/ — generated build artifacts (make).