Cinna Davis and GPT-6.2 Astra · November 2026 · Unrefereed computer-assisted proof
For a finite set of positive integers , let be the supremum of the upper densities of subsets of in which no two elements differ by a member of . This is the independence ratio of the distance graph generated by , also called the Motzkin density. We prove Conjecture 38 and disprove Conjecture 39 of the 2014 arXiv preprint by James Carraher, David Galvin, Stephen Hartke, A. J. Radcliffe and Derrick Stolee. The author-hosted manuscript numbers them 36 and 37. These results concern two particular families in the three-missing-differences problem. arXiv version, pp. 34–35, author-hosted version
A complete classification gives the corrected gap-seven formula and all omitted small values for both families.
Statements
Theorem 1. For , , the following table gives . An entry denotes the number .
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Entry |
Theorem 2. . The residue- branch of Conjecture 39 predicts , larger by . The authors' supplementary table already gives as a lower bound, in red in row 49, column 7. The upper certificate below proves equality. Original data and color key, pp. 1–2
Two elementary reductions
If upper density exceeds a rational bound, take a sufficiently long interval whose occupied fraction exceeds it even after appending zeros. Repeating the padded word gives a periodic independent set that exceeds the same bound. Thus upper bounds can be proved using periodic words.
If a periodic sequence of integers has negative period sum, it has a cyclic shift whose every nonempty prefix has negative sum. Start just after the last occurrence of the largest prefix sum among indices from zero through one less than the period. Until wrapping, all later prefix sums lie strictly below that maximum. After wrapping, a whole negative period has been added. Negating the sequence gives the positive version.
The constructions for Theorem 1
If , choose all integers whose residue belongs to . This avoids whenever the residues of are in for . When divides , its density is .
For residues in the table, set and . This is integral. The residues for and are , and . The required inequality is equivalent to . It holds at the smallest admissible in each of those five classes, respectively , and hence thereafter.
For residue , use , and . Here is even and with odd, so . The identity gives , and . Also .
For residue , use , . All three forbidden differences are modulo 7. The upper bound follows from the first seven-cycle in the next section by averaging its translates.
Two cycle counts
Write for the indicators of a periodic independent set. Each of the following vertex lists forms a seven-cycle, using five edges of length 1 and one edge of each of the other two lengths:
- .
- .
Each cycle contains at most three occupied vertices. Define its two nonnegative integer deficits by
At density , the average of is . In each table entry with , put . A density exceeding the proposed bound makes the average strictly less than . Apply the negative-prefix reduction to . After shifting, a necessary condition is
It remains to rule out a finite word satisfying (1) for every admissible . The reduction to finitely many values of below applies to these words directly.
The strip of bits
Write as in the table, with or . Read rows at once. Row begins at . A state records five consecutive bits from each row. Each row word has no adjacent ones and adjacent rows have disjoint words. A transition appends one column. Horizontal neighbors, vertical neighbors and a lower-row bit five columns before an upper-row bit cannot both be one. These tests enforce differences . A row-pair transition starting at column has cost , computed from the old five-bit words and the two new bits.
Process columns. The final five bits of each row except the last must equal the initial five bits of the next row. Finally process extra transitions in the last pair of rows. Their lower appended bits must reproduce the first appended bits of the original last row. This accounts for all costs, in row order. The seam requirements express that the rows are successive pieces of one integer-indexed word. Every periodic independent set exceeding the proposed density therefore gives a path satisfying (1). The finite verification tests this path condition.
For a single pair of rows there are 99 states. Consider only transitions of zero cost. Exactly seven states have both an incoming walk of length three and an outgoing walk of length three in this graph. Between these seven states the zero transitions form one directed seven-cycle. The verifier establishes these finite facts by generating every state and transition, propagating reachability for three steps in both directions, then following successors. Consequently any run of 13 zero-cost steps contains seven successive steps that return to their initial state. In fact the states from times 3 through 10 are all in the seven-state set. For three rows the same argument works at the same times in both adjacent pairs if their costs are both zero. The complete three-row state then repeats.
Shortening a hypothetical path
Suppose a path exists for . Set , which has the same residue modulo 7, and . We shall remove seven columns in each of disjoint segments, using identical cuts in all rows. Give segment , , the transition indices from inclusive to exclusive. Set aside the first and last 13 transitions of every segment. Each remaining interior has length at least
because . The total cost over the row pairs in the first columns is at most by (1) at and nonnegativity. In any segment interior, at most columns can have positive cost in any pair. If all zero runs had length at most 12, the interior would have length at most . Hence it contains 13 consecutive zero columns, and the preceding state calculation permits deletion of a closed seven-step subwalk. Do this once in every segment. The endpoint states, the seam equalities and the remembered first appended bits survive. All removed costs are zero. The final transitions also survive.
For completeness the shrinking of the strict prefix bounds matters. For a nonnegative integer cost sequence, (1) is equivalent to the cumulative cost being at most at each integer time , . Indeed, for any use and monotonicity. Write , . Then
Its column within row is within positions to the right of . No cut touches this protected region. When the point is in the final extension, which is also protected. Exactly positions in row order have been removed before this time. Its new time is , with the same cumulative cost. Thus the shortened path satisfies all the required inequalities for .
Iterating would produce a path for an admissible . A step from above 1600 lands at or above 1531, so it cannot land on an excluded small parameter. This proves the reduction for arbitrarily large .
Finite decisions
The C++ checker exhausts all 1,365 values in that require a strip test. For each starting state it records the current state, the remembered upper bits and, for three rows, the cost accumulated in the first pair. Among identical keys it retains the least cost in the last pair. A larger last cost can only make a later upper bound harder to meet.
For three rows it tries every integer bound from 0 to on the total cost in the first pair. It applies (1) to the first pair and to the last pair with added to that pair's running cost. A genuine path is represented when is its actual first-pair total. Conversely, a path accepted with a greater also satisfies the actual inequalities. At the end it tests the seam equalities and the final steps. No path is accepted in the required cases. Increasing by one gives accepted paths in the small positive controls. This proves the upper bounds in Theorem 1. Finite verifier
The counterexample to Conjecture 39
For , use and . The residues for are , and . This realizes the lower bound in the authors' table.
For the upper bound, a larger periodic density would give a translated word of length 116 in which every nonempty prefix had density strictly above . The Python verifier tests for this word directly. After occupied sites have been chosen, the next site, indexed from zero, can be no later than , since the preceding prefix must still qualify. Site zero must be occupied. The search tries each possible next site, deleting its conflicts and all skipped sites. It also partitions the still available sites into cliques, taking the least unassigned site to start each clique. At a clique start, at most one site from each preceding clique can augment the current prefix count. Failure to reach that start with this upper bound permits pruning. The same clique count bounds the total attainable size. Reaching 51 sites suffices since zeros can then be appended to length 116.
The exhaustive decision rejects length 116 at threshold . It accepts both a length-58 control at that threshold and length 116 at threshold . Thus the lower bound is exact. Independent counterexample verifier
Reproduction and literature
Run from the repository root with a C++20 compiler and Python 3.
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.pyThe numbered statements above use the arXiv version. The journal article is shorter. In particular its Conjectures 26 and 29 are different predictions, addressed by Liu and Robinson. A search of the original and author-hosted versions, the supplementary computations and subsequent missing-differences literature located no earlier resolution of these two statements. Priority remains provisional. Journal article, Liu and Robinson