Exact packing and covering densities for symmetric four-point sets

What Lean checks

Exact real packing and covering densities for every literal translated symmetric four-point integer set, including common-divisor normalization. Both periodic constructions and the two sharp local interval lengths are proved.

Cinna Davis and GPT-6.2 Astra · November 2026 · Unrefereed proof

Let 0<a<b0\lt a\lt b be coprime integers and S={0,a,b,a+b}S=\{0,a,b,a+b\}. Write dp(S)d_p(S) for the supremum of the upper densities of sets of centers whose translates of SS are disjoint. Write dc(S)d_c(S) for the infimum of the lower densities of sets of centers whose translates cover ℤ\mathbb Z.

Theorem. If a,ba,b have opposite parity then dp(S)=dc(S)=1/4d_p(S)=d_c(S)=1/4. If they are both odd, put P=ab+b−aP=ab+b-a and Q=ab+b+aQ=ab+b+a. Then

dp(S)=P−14P,dc(S)=Q+14Q.\boxed{d_p(S)=\frac{P-1}{4P},\qquad d_c(S)=\frac{Q+1}{4Q}.}

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 a,b,b−a,a+ba,b,b-a,a+b. Liu and Zhu had already constructed a packing attaining the proposed value, proved the opposite-parity case and treated the packing case a=1a=1. 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 PP consecutive integers in a packing contains an uncovered site. No family of translates can cover each of QQ consecutive integers exactly once. In particular every such interval in a covering contains a site covered at least twice.

Let xtx_t indicate a center at tt, and define

yt=xt+xt−a,zt=xt+xt−b,mt=yt+yt−b=zt+zt−a.y_t=x_t+x_{t-a},\qquad z_t=x_t+x_{t-b},\qquad m_t=y_t+y_{t-b}=z_t+z_{t-a}.

Here mtm_t counts covers of tt. Suppose, for a contradiction, that mt=1m_t=1 on [0,L−1][0,L-1]. In the packing argument take L=PL=P and assume mt≤1m_t\le1 everywhere. In the other argument take L=QL=Q, allowing arbitrary multiplicities outside this interval.

Two elementary implications will be used. If yt>0y_t>0 and mt,mt+b≤1m_t,m_{t+b}\le1, then zt=zt+bz_t=z_{t+b}. In fact a tile starting at tt covers both sites and gives zt=zt+b=1z_t=z_{t+b}=1. A tile starting at t−at-a covers both sites and gives zt=zt+b=0z_t=z_{t+b}=0, since the two sites already have their unique cover. Exchanging a,ba,b gives the second implication. If zt>0z_t>0 and mt,mt+a≤1m_t,m_{t+a}\le1, then yt=yt+ay_t=y_{t+a}. Also, at any site with mt=1m_t=1, having yt=zt=1y_t=z_t=1 means that the unique tile starts at tt.

Find a residue class. The equations zt+zt−a=1z_t+z_{t-a}=1 on the interval show that the zz values on [−a,L−1][-a,L-1] are bits. They agree there with a sequence ZZ on all of ℤ\mathbb Z such that Zj+a=1−ZjZ_{j+a}=1-Z_j. To construct it, extend the values at −a,…,−1-a,\ldots,-1 by this rule. Since bb is odd, Zj+ab=1−ZjZ_{j+ab}=1-Z_j. At least one of the aa successive steps of length bb from jj to j+abj+ab therefore changes the bit. A change Zs≠Zs+bZ_s\ne Z_{s+b} persists when ss is shifted by aa in either direction, since both bits are complemented. Fix a residue class modulo aa on which the change holds.

Two forced zeros. Choose its representative j0j_0 in [−a,−1][-a,-1] for packing and in [0,a−1][0,a-1] for the QQ-site argument. Put i=j0+(b−1)ai=j_0+(b-1)a. For j=j0j=j_0 and j=ij=i, the sites j,j+bj,j+b are in [−a,L−1][-a,L-1] and jj belongs to the chosen residue class. Hence zj≠zj+bz_j\ne z_{j+b}. In the packing case both sites have multiplicity at most one by hypothesis. In the QQ-site case both belong to the exactly covered interval. The first implication gives yj0=yi=0y_{j_0}=y_i=0.

Force two intersecting tiles. Starting at j0j_0, take aa steps of length bb. All arrival sites are in [0,L−1][0,L-1], so yt=1−yt−by_t=1-y_{t-b} at each arrival. Since aa is odd and j0+ab=i+aj_0+ab=i+a, we obtain yi+a=1y_{i+a}=1. Similarly yi+b=1−yi=1y_{i+b}=1-y_i=1. The sites i,i+a,i+bi,i+a,i+b all belong to [0,L−1][0,L-1]. For packing, −a≤j0≤−1-a\le j_0\le-1 gives i≥0i\ge0, i+a≤ab−1i+a\le ab-1, and i+b≤P−1i+b\le P-1. For the other case, 0≤j0≤a−10\le j_0\le a-1 even gives i+a+b≤Q−1i+a+b\le Q-1.

The second implication and yi≠yi+ay_i\ne y_{i+a} force zi=0z_i=0. Hence zi+a=1z_{i+a}=1 by exact coverage at i+ai+a, and zi+b=1z_{i+b}=1 by the choice of residue class. Both flags are now one at each of i+ai+a and i+bi+b. Thus there must be centers at both sites. Their tiles both cover i+a+bi+a+b. This contradicts disjointness in the packing case. In the other case it contradicts exact coverage at i+a+bi+a+b 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 PP gives average multiplicity at most (P−1)/P(P-1)/P, up to a boundary error tending to zero. For a covering, each interval of length QQ contributes total multiplicity at least Q+1Q+1. 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, P=(a+1)(b−1)+1P=(a+1)(b-1)+1 is coprime to bb and b(a+1)≡a(modP)b(a+1)\equiv a\pmod P. Multiplication by b−1b^{-1} turns SS modulo PP into {0,1,a+1,a+2}\{0,1,a+1,a+2\}. Write 0,…,P−20,\ldots,P-2 as a rectangle of width a+1a+1 and height b−1b-1, with consecutive integers across each row. Both dimensions are even. Partitioning it into 2×22\times2 squares packs precisely (P−1)/4(P-1)/4 translates, leaving one residue uncovered. Multiplication by bb and periodic repetition give the required integer packing.

For covering, Q=(a+1)(b+1)−1Q=(a+1)(b+1)-1 is also coprime to bb, and b(a+1)≡−a(modQ)b(a+1)\equiv-a\pmod Q. The image of SS under multiplication by b−1b^{-1} is a translate of {0,1,a+1,a+2}\{0,1,a+1,a+2\}. Tile the rectangle of width a+1a+1 and height b+1b+1 before reducing its entries 0,…,Q0,\ldots,Q modulo QQ. Its (Q+1)/4(Q+1)/4 starting positions remain distinct, since they are all between 00 and Q−1Q-1. 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 ee be the even step, oo the odd step, and 2t2^t the largest power of two dividing ee. Modulo 2t+12^{t+1} take the even residues in [0,2t)[0,2^t) as centers. Adding 00 or ee covers each even residue exactly once. Translating these covered even residues by oo 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.