Cinna Davis and GPT-6.2 Astra · November 2026 · Unrefereed proof
Let be coprime integers and . Write for the supremum of the upper densities of sets of centers whose translates of are disjoint. Write for the infimum of the lower densities of sets of centers whose translates cover .
Theorem. If have opposite parity then . If they are both odd, put and . Then
This proves both statements of Natalchenko and Sagdeev's Conjecture 1. Its packing part is the Liu–Zhu conjecture of 2004. Indeed, disjoint translates are equivalent to a center set avoiding the four differences . Liu and Zhu had already constructed a packing attaining the proposed value, proved the opposite-parity case and treated the packing case . Natalchenko and Sagdeev explicitly identified the general packing assertion as open and proposed its covering counterpart. Liu and Zhu, Section 4, Natalchenko and Sagdeev, Conjecture 1
A local obstruction for odd steps
We prove a stronger statement. Every interval of consecutive integers in a packing contains an uncovered site. No family of translates can cover each of consecutive integers exactly once. In particular every such interval in a covering contains a site covered at least twice.
Let indicate a center at , and define
Here counts covers of . Suppose, for a contradiction, that on . In the packing argument take and assume everywhere. In the other argument take , allowing arbitrary multiplicities outside this interval.
Two elementary implications will be used. If and , then . In fact a tile starting at covers both sites and gives . A tile starting at covers both sites and gives , since the two sites already have their unique cover. Exchanging gives the second implication. If and , then . Also, at any site with , having means that the unique tile starts at .
Find a residue class. The equations on the interval show that the values on are bits. They agree there with a sequence on all of such that . To construct it, extend the values at by this rule. Since is odd, . At least one of the successive steps of length from to therefore changes the bit. A change persists when is shifted by in either direction, since both bits are complemented. Fix a residue class modulo on which the change holds.
Two forced zeros. Choose its representative in for packing and in for the -site argument. Put . For and , the sites are in and belongs to the chosen residue class. Hence . In the packing case both sites have multiplicity at most one by hypothesis. In the -site case both belong to the exactly covered interval. The first implication gives .
Force two intersecting tiles. Starting at , take steps of length . All arrival sites are in , so at each arrival. Since is odd and , we obtain . Similarly . The sites all belong to . For packing, gives , , and . For the other case, even gives .
The second implication and force . Hence by exact coverage at , and by the choice of residue class. Both flags are now one at each of and . Thus there must be centers at both sites. Their tiles both cover . This contradicts disjointness in the packing case. In the other case it contradicts exact coverage at inside the interval. Translation gives the obstruction on every interval of the stated length.
Density bounds
In a packing, summing multiplicities over full disjoint intervals of length gives average multiplicity at most , up to a boundary error tending to zero. For a covering, each interval of length contributes total multiplicity at least . The multiplicity is the sum of four fixed translates of the center indicator. On a long interval its average differs from four times the center density there by a quantity tending uniformly to zero. Taking the upper or lower density gives the two desired inequalities. This argument applies to arbitrary center sets.
Constructions attaining the bounds
For the odd packing case, is coprime to and . Multiplication by turns modulo into . Write as a rectangle of width and height , with consecutive integers across each row. Both dimensions are even. Partitioning it into squares packs precisely translates, leaving one residue uncovered. Multiplication by and periodic repetition give the required integer packing.
For covering, is also coprime to , and . The image of under multiplication by is a translate of . Tile the rectangle of width and height before reducing its entries modulo . Its starting positions remain distinct, since they are all between and . Exactly one residue is covered twice and all others once. Undoing the coordinate change and repeating gives the asserted covering. These examples also show that the two local obstruction lengths are sharp.
Finally, for opposite parities let be the even step, the odd step, and the largest power of two dividing . Modulo take the even residues in as centers. Adding or covers each even residue exactly once. Translating these covered even residues by covers each odd residue exactly once. The resulting tiling attains both counting bounds.
Verification and scope
The proof uses no computational assumptions. The finite verifier independently searches local exact covers for small odd steps and checks the sharp periodic constructions across a larger range. Run python3 results/symmetric-four-point-density/verify.py from the repository root.
The statement concerns symmetric four-point sets of the form above. Natalchenko and Sagdeev's other conjecture on arbitrary lengths of two nonmixed gaps is a different question. A search of the original paper, the 2025 formulation and subsequent literature found no earlier general resolution of the packing and covering statements. Priority remains provisional.