Packing sets with two nonmixed gap lengths

What Lean checks

The exact three-case packing and real circle formula for every positive gap pair and arbitrary positive gap counts, including gcd normalization, literal tile semantics, periodic attainment, and the stated example.

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

Let a,b,k,ma,b,k,m be positive integers with gcd(a,b)=1\gcd(a,b)=1. Consider the tile

S={0,a,…,ka,ka+b,…,ka+mb}S=\{0,a,\ldots,ka,ka+b,\ldots,ka+mb\}

and its set of positive differences

M={ia+jb:0≤i≤k,0≤j≤m,i+j>0}.M=\{ia+jb:0\le i\le k,\ 0\le j\le m,\ i+j>0\}.

A set of centers A⊆ℤA\subseteq\mathbb Z packs translates of SS precisely when no two centers differ by an element of MM. Write μ(M)\mu(M) for the supremum of their upper densities. Write κ(M)=maxt∈ℝ/ℤminw∈M∥wt∥\kappa(M)=\max_{t\in\mathbb R/\mathbb Z}\min_{w\in M}\|wt\|, where the norm denotes distance to the nearest integer.

Theorem. Put s=k+m+1s=k+m+1 and write a−b=sd+ra-b=sd+r, with 0≤r<s0\le r\lt s. Then

μ(M)=κ(M)={1/sr=0,(b+kd)/(ka+(m+1)b)1≤r≤m,(a−m(d+1))/((k+1)a+mb)m<r<s.\mu(M)=\kappa(M)= \begin{cases} 1/s & r=0, \\ (b+kd)/(ka+(m+1)b) & 1\le r\le m, \\ (a-m(d+1))/((k+1)a+mb) & m\lt r\lt s. \end{cases}

This proves the tightness conjecture following Theorem 2 of Natalchenko and Sagdeev and answers their question about κ(M)\kappa(M) in Section 4. They proved the packing lower bound in full generality, proved optimality when k=1k=1 or m=1m=1, and identified the two candidate interval lengths for an upper bound. We use their two intervals. The new step is an integer inequality relating their occupancy counts. Original article · Authors' formulation and proof

For example, S={0,5,10,13,16}S=\{0,5,10,13,16\} has two gaps of length five followed by two of length three. Three centers at 0,1,20,1,2 modulo 1919 give a packing. The theorem shows that every packing, periodic or otherwise, has upper density at most 3/193/19.

The two interval counts

Exchanging (a,k)(a,k) with (b,m)(b,m) preserves MM. For r>0r>0 this sends (d,r)(d,r) to (−d−1,s−r)(-d-1,s-r) and interchanges the two formulas. Thus we can assume a>ba>b for the upper bound when r>0r>0. Put

D=ka+mb,n1=D+b,n2=D+a.D=ka+mb,\quad n_1=D+b,\quad n_2=D+a.

Suppose 0∈A0\in A and AA avoids MM. Let J=|A∩[0,n1)|J=|A\cap[0,n_1)| and C=|A∩[0,n2)|C=|A\cap[0,n_2)|.

Counting lemma. There exists an integer zz such that

J≤b+kz,C≤a−mz.J\le b+kz,\qquad C\le a-mz. \tag{1}

Lift each site t∈A∩[0,n2)t\in A\cap[0,n_2) to an integer pair (x,y)(x,y) with ax−by=tax-by=t. Such lifts exist by coprimality. They differ by multiples of T=(b,a)T=(b,a). Give a lift the weight mx+kymx+ky. Translation by TT adds DD to its weight, so choose the unique lift of each site with weight in [0,D)[0,D). The lift of 00 is (0,0)(0,0). Include TT as a final endpoint of weight DD and height zero. Here height means ax−byax-by.

We check how two lifts can differ. For distinct lifted sites, and also for the two endpoints lifting 00, take the difference (u,v)(u,v) in the direction of nondecreasing weight, so mu+kv≥0mu+kv\ge0. The following are the only possibilities.

Type Bounds on the displacement
Both coordinates positive u≥1,v≥1u\ge1,\ v\ge1
XX, with v≤0v\le0 u≥k+1,v≥1−mu\ge k+1,\ v\ge1-m
YY, with u≤0u\le0 v≥m+1,u≥−kv\ge m+1,\ u\ge-k

Indeed, if v≤0v\le0 then u>0u>0 for a nonzero displacement of nonnegative weight. If u≤ku\le k, the weight condition forces −v≤m-v\le m, so the positive height difference ua+(−v)bua+(-v)b belongs to MM. This contradicts avoidance. Thus u≥k+1u\ge k+1. If also v≤−mv\le-m, the height would increase by at least (k+1)a+mb=n2(k+1)a+mb=n_2, impossible inside [0,n2)[0,n_2). This gives row XX. If u≤0u\le0, the same weight argument shows that v≤mv\le m would put (−u)a+vb(-u)a+vb in MM. Hence v≥m+1v\ge m+1. Then u≤−k−1u\le-k-1 would give a height decrease of at least (k+1)a+(m+1)b>n2(k+1)a+(m+1)b>n_2. This proves row YY. The two copies of 00 have displacement TT in the positive direction, which lies in the first row.

All three rows have strictly positive weight. In particular, distinct chosen lifts have distinct weights. Sort the lifts by weight, from (0,0)(0,0) to TT. There are exactly CC steps. Write NX,NYN_X,N_Y for the numbers of steps of the indicated types and set z=NY−NXz=N_Y-N_X. Summing the second coordinates in the table gives

a=∑v≥C+mz.a=\sum v\ \ge\ C+mz.

For the first coordinates, a YY step ordinarily contributes at least 1−k1-k. The one exception is u=−ku=-k. Such a step drops in height by at least ka+(m+1)b=n1ka+(m+1)b=n_1. Its starting site therefore lies in [n1,n2)[n_1,n_2). Each starting site occurs once, so at most C−JC-J steps have this exception. Summing gives

b=∑u≥C+kNX−kNY−(C−J)=J−kz.b=\sum u\ \ge\ C+kN_X-kN_Y-(C-J)=J-kz.

This proves (1).

The upper bound

Let δ\delta be the claimed density. Each center starts an interval of length n1n_1 or n2n_2 in which the fraction of centers is at most δ\delta. To see this, translate the center to zero and apply (1).

  • If 1≤r≤m1\le r\le m and z≤dz\le d, then J≤b+kd=δn1J\le b+kd=\delta n_1. If z≥d+1z\ge d+1, then C≤a−m(d+1)≤b+(k+1)d<δn2C\le a-m(d+1)\le b+(k+1)d<\delta n_2. The last inequality follows from (b+kd)n2−(b+(k+1)d)n1=br(b+kd)n_2-(b+(k+1)d)n_1=br.
  • If m<r<sm\lt r\lt s and z≥d+1z\ge d+1, then C≤a−m(d+1)=δn2C\le a-m(d+1)=\delta n_2. If z≤dz\le d, then J≤b+kd≤a−(m+1)(d+1)<δn1J\le b+kd\le a-(m+1)(d+1)<\delta n_1. Here (a−m(d+1))n1−(a−(m+1)(d+1))n2=a(s−r)(a-m(d+1))n_1-(a-(m+1)(d+1))n_2=a(s-r).

Starting at the left endpoint of any integer interval, take such a block if the first site is a center, and take a single empty site otherwise. Continue until the next block would overrun the interval. Each complete block has density at most δ\delta, and the remaining length is less than n2n_2. Dividing by the interval length and taking a limit gives μ(M)≤δ\mu(M)\le\delta for arbitrary packings. If r=0r=0, simple counting gives the same bound 1/s1/s, since each disjoint tile contains ss sites and has bounded diameter.

Attainment by a character

For rational t=p/qt=p/q in lowest terms, the residues pxmodqp x\bmod q permute the classes modulo qq. If minw∈M∥wt∥=H/q\min_{w\in M}\|wt\|=H/q, centers whose residues pxmodqp x\bmod q lie in [0,H)[0,H) have density H/qH/q and avoid every difference in MM. Continuity in tt and density of rationals give μ(M)≥κ(M)\mu(M)\ge\kappa(M).

For r=0r=0, both a,ba,b are the same unit modulo ss by coprimality. Taking t=p/st=p/s with pa≡1(mods)pa\equiv1\pmod s sends the differences to the nonzero classes (i+j)/s(i+j)/s on the circle, attaining 1/s1/s.

For r>0r>0, exchange the two steps if necessary so that 1≤r≤m1\le r\le m. We now allow either order of a,ba,b. Write h=b+kdh=b+kd and n=ka+(m+1)bn=ka+(m+1)b. We have h>0h>0 for d≥0d\ge0, and for d<0d<0 this follows from h=a−(m+1)d−rh=a-(m+1)d-r. Directly,

n=sh+kr,ah−b(h+r)=dn.n=sh+kr,\qquad ah-b(h+r)=dn.

Choose integers U,VU,V with Ua+Vb=1Ua+Vb=1 and put p=U(h+r)+Vhp=U(h+r)+Vh. The second identity gives ap≡h+rap\equiv h+r and bp≡h(modn)bp\equiv h\pmod n. Thus each forbidden difference ia+jbia+jb, multiplied by pp, has representative (i+j)h+ir(i+j)h+ir in [h,n−h][h,n-h]. The largest occurs at (i,j)=(k,m)(i,j)=(k,m) since (k+m)h+kr=n−h(k+m)h+kr=n-h. The difference bb attains hh, so t=p/nt=p/n gives κ(M)≥h/n\kappa(M)\ge h/n. The upper bound already proved gives equality throughout. The step exchange gives the last branch of the theorem as well.

The proof covers noncoprime steps after dividing by their greatest common divisor. Indeed each residue class modulo that divisor carries a copy of the reduced packing problem, and repeating a reduced packing in every class attains the same density. For the character value, multiplication by the divisor maps the circle onto itself.

Reproducibility

The argument above is independent of computation. The verifier enumerates finite anchored packings directly from forbidden differences and checks (1) and the two interval bounds. It also checks character attainment and the density of the associated periodic packing in a larger parameter range. Run python3 results/nonmixed-gap-packing/verify.py from the repository root. A literature search located the original 2025 statement and no earlier general resolution. Priority remains provisional.