Distance graphs with three missing differences

What Lean checks

The actual extremal densities and circle maxima for {1,k,k+5} and {1,k,k+7} are classified for every positive k, including every small exception. Explicit periodic optima, the exact Conjecture 39 discrepancy, and infinitely many strict counterexamples are proved.

Collection · Catalogue · Verification · Lean status

Result

Carraher et al., arXiv Conjecture 38 proved for all admissible parameters. Conjecture 39 fails for every k=50,59,68,…. The corrected formula gives all densities for gaps five and seven.

Proof and sources

Read the proof for the original problem, assumptions, argument, and cited sources. These notes are unrefereed.

Verification

Run from the repository root:

c++ -std=c++20 -O3 results/distance-graph-densities/verify.cpp -o /tmp/verify-distance-graphs
/tmp/verify-distance-graphs
python3 results/distance-graph-densities/counterexample.py

See the verification guide for dependencies and the distinction between computational checks and formal proofs.

Formalization

Complete Lean formalization. The ThreeDistanceGraph modules prove the density and circle formulas for every positive k, all exceptional small cases, explicit optimal periodic constructions, and the infinite family of strict counterexamples to Conjecture 39. See the checked proof and the status report.

Supporting files