Haralambis’s conjecture on three missing differences

What Lean checks

Exact equality of actual extremal density and real circle value for every positive triple, with no coprimality premise. An optimal periodic set has a pair-sum period. The proof includes finite balanced orientations, signed defects, odd periods, interval counting, and the explicit {2,5,9} example.

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

Let D={d1,d2,d3}D=\{d_1,d_2,d_3\} be three distinct positive integers. Write μ(D)\mu(D) for the supremum of the upper densities of sets of integers AA in which no two elements differ by a member of DD. Write ∥x∥\|x\| for distance to the nearest integer and set

κ(D)=maxt∈ℝ/ℤmini∥dit∥.\kappa(D)=\max_{t\in\mathbb R/\mathbb Z}\min_i\|d_i t\|.

Theorem. For every such DD, μ(D)=κ(D)\mu(D)=\kappa(D). An optimal periodic set exists with period equal to one of the three pair sums di+djd_i+d_j.

This is the three-element conjecture attributed to Haralambis (1977). Liu and Robinson state it as Conjecture 3 and determine the density for several infinite families. The character lower bound μ≥κ\mu\ge\kappa was already known. We prove the reverse inequality by comparing three short intervals in an arbitrary avoiding set. Haralambis’s paper · Liu and Robinson, Section 6

A finite interval inequality

Assume first that gcd(d1,d2,d3)=1\gcd(d_1,d_2,d_3)=1, and put L=d1+d2+d3L=d_1+d_2+d_3. Given any avoiding set in [0,L)[0,L), let PijP_{ij} count its members in [0,di+dj)[0,d_i+d_j). We prove

δ:=mini<jPijdi+dj≤κ(D).\delta:=\min_{i\lt j}\frac{P_{ij}}{d_i+d_j}\ \le\ \kappa(D). \tag{1}

We use the lattice height h(x)=d1x1+d2x2+d3x3h(x)=d_1x_1+d_2x_2+d_3x_3 and its kernel K⊂ℤ3K\subset\mathbb Z^3. In the unit cubic lattice, take the union BB of closed cubes with lower corners of negative height. Its boundary is a stepped plane. Indeed, BB is closed and is downward closed in the coordinatewise order. Every line in direction (1,1,1)(1,1,1) starts inside BB and ends outside it. Translating a point of BB a positive distance in the strictly negative diagonal direction puts it in the interior. Thus each such line meets the boundary exactly once. The boundary height along these lines is continuous because moving the base point by a vector of sup norm at most η\eta moves its diagonal parameter by at most η\eta, by coordinatewise comparison. Diagonal projection therefore identifies the boundary with a plane. Translations in KK act on that plane as a rank-two lattice, since diagonal projection restricts to a linear isomorphism on the real kernel of hh. The quotient surface is a torus.

The boundary vertices are the lattice points of heights 0,…,L−10,\ldots,L-1. At a vertex xx, the cubes with lowest and highest possible lower-corner heights have lower corners x−(1,1,1)x-(1,1,1) and xx, respectively. They lie on different sides exactly in that range. Similarly an edge in direction eie_i with lower endpoint of height uu belongs to the boundary exactly when 0≤u<L−di0\le u\lt L-d_i. A square in directions ei,eje_i,e_j with lower corner of height uu belongs to it exactly when 0≤u<dk0\le u\lt d_k, where kk is the remaining index. These facts follow by comparing the cubes incident on the edge or square. In the quotient, vertices of the same height coincide, and every integer height occurs by coprimality. We can therefore mark a vertex occupied precisely when its height belongs to the given avoiding set. Each edge has at most one occupied endpoint.

Sign the edges with two empty endpoints

Call an edge a defect if both endpoints are empty. Every square has an even number of defects. Indeed, each occupied corner removes its two incident sides from the four possible defects, and occupied corners are never adjacent. Form the dual graph on the squares, with a dual edge across each defect. Its degrees are even, so its edges can be oriented along Euler circuits with equal indegree and outdegree at every square.

Orient the torus. Assign each oriented surface edge ee a number f(e)f(e) as follows. A nondefect gets zero. A defect gets +1+1 or −1-1 according to the direction in which its oriented dual edge crosses it. Reversing ee negates f(e)f(e). The sum of ff around the boundary of every square is zero, since it counts signed dual crossings at a balanced vertex.

On the stepped plane the sum of the lifted ff along a path depends only on its endpoints. Every closed edge path in this simply connected square tiling is a sum of oriented square boundaries as an integer chain. For v∈Kv\in K, write H(v)H(v) for the sum along a path from a fixed vertex to its translate by vv. Path independence and translation invariance imply that this sum is the same for any starting vertex and that H:K→ℤH:K\to\mathbb Z is additive. For example, translating a path joining two starting vertices by vv gives the same edge sum, so those two contributions cancel on the closed path comparing the starting vertices.

Parity fixes the periods. On any edge from uu to u′u', we have f(e)≡1+1A(u)+1A(u′)(mod2)f(e)\equiv1+1_A(u)+1_A(u')\pmod2, with the indicators evaluated at the vertex heights. The indicator terms cancel on any closed quotient walk. A lift ending at displacement vv has length congruent to v1+v2+v3v_1+v_2+v_3 modulo two. Hence H(v)≡v1+v2+v3(mod2)H(v)\equiv v_1+v_2+v_3\pmod2 on KK. In particular there are three odd integers wiw_i such that H(v)=w⋅vH(v)=w\cdot v for all v∈Kv\in K. To see the integral extension explicitly, choose u∈ℤ3u\in\mathbb Z^3 with h(u)=1h(u)=1. The integer homomorphism v↦(H(v)−∑ivi)/2v\mapsto(H(v)-\sum_i v_i)/2 on KK extends to ℤ3\mathbb Z^3 by evaluating it at x−h(x)ux-h(x)u. Twice the coefficients of this extension, plus one in each coordinate, give ww.

Read the three interval counts on the same torus

Fix i<ji\lt j, put p=di+djp=d_i+d_j and g=gcd(di,dj)g=\gcd(d_i,d_j). On 0,…,p−10,\ldots,p-1 the permutation u↦u+di(modp)u\mapsto u+d_i\pmod p follows a positive eie_i edge when u<dju\lt d_j and a negative eje_j edge otherwise. All these edges belong to the surface. Its gg cycles have length p/gp/g. Each lifts to displacement (dj/g)ei−(di/g)ej(d_j/g)e_i-(d_i/g)e_j, since the cycle uses dj/gd_j/g positive steps and di/gd_i/g negative steps. Thus the sum of the signed edge values over all the cycles is djwi−diwjd_j w_i-d_i w_j.

The cycles contain exactly p−2Pijp-2P_{ij} defect edges in total. Each occupied vertex accounts for its two incident cycle edges, and no edge is counted by two occupied vertices. Since |f||f| is the defect indicator, we obtain simultaneously for all three pairs

|djwi−diwj|≤di+dj−2Pij≤(di+dj)(1−2δ).|d_jw_i-d_iw_j|\ \le\ d_i+d_j-2P_{ij} \ \le\ (d_i+d_j)(1-2\delta). \tag{2}

Set E=1−2δ≥0E=1-2\delta\ge0. Inequality (2) says precisely that the three closed real intervals

[wi−Edi,wi+Edi]\left[\frac{w_i-E}{d_i},\frac{w_i+E}{d_i}\right]

intersect pairwise. Thus they have a common point xx. Each dixd_i x is within EE of the odd integer wiw_i, so its distance from every even integer is at least 1−E=2δ1-E=2\delta. The single rotation t=x/2t=x/2 satisfies ∥dit∥≥δ\|d_i t\|\ge\delta for every ii. This proves (1).

From intervals to density and attainment

At each position in any avoiding set on the line, apply (1) to the next LL sites. At least one block starting there, of length di+djd_i+d_j, has density at most κ(D)\kappa(D). Take that block and repeat at its right endpoint. In any interval of length NN the complete blocks contain at most κ(D)\kappa(D) times their total length in occupied sites, and the final unused piece has length less than LL. This gives the uniform bound |A∩I|≤κ(D)N+L|A\cap I|\le\kappa(D)N+L, and hence the upper density bound. For a common divisor g>1g>1, partition into classes modulo gg and apply the primitive result for D/gD/g in each class. Their sum gives the same asymptotic upper bound. Also κ(D)=κ(D/g)\kappa(D)=\kappa(D/g) since multiplication by gg maps the circle onto itself.

For completeness, the maximum defining κ\kappa occurs at some t=j/pt=j/p with p=di+djp=d_i+d_j for a pair i<ji\lt j. The maximized function is the lower envelope of three triangular waves. Its positive maximum, if strictly below 1/21/2, must have active linear pieces of opposite slopes. Otherwise a small displacement in one direction increases every active wave. At such a crossing ditd_i t and djtd_j t have opposite signed distances of equal magnitude from integers, so (di+dj)t(d_i+d_j)t is integral. If the maximum is 1/21/2, every wave equals 1/21/2 there and the same integrality holds. The maximum is positive because sufficiently small positive tt makes every wave positive.

Reduce this maximizing fraction to t=u/qt=u/q and put H=qκ(D)H=q\kappa(D). It is an integer. Take the centers nn with unmodqun\bmod q in {0,…,H−1}\{0,\ldots,H-1\}. These residues give density H/qH/q, since uu is a unit modulo qq. A difference between two centers has circular residue distance less than HH after multiplication by uu, whereas each forbidden difference has distance at least HH. This attains κ(D)\kappa(D), and qq divides the pair sum pp. Thus pp is a period of the construction.

For example, for D={2,5,9}D=\{2,5,9\} the finite maximum over the three pair sums is 3/73/7, attained at t=2/7t=2/7. The residues 0,1,40,1,4 modulo 77 attain this density. The upper bound applies to every avoiding set.

An algebraic check on the period argument

One can also obtain the odd vector without using the topology of the stepped plane. Write Fi(t)F_i(t) for the signed value on the positive ii-edge at height tt. The square equations are

Fi(t)+Fj(t+di)=Fj(t)+Fi(t+dj)F_i(t)+F_j(t+d_i)=F_j(t)+F_i(t+d_j)

whenever the four heights are inside the window. Extend the occupancy indicator to be zero outside. We claim the edge values extend integrally to all integer heights, preserving both the square equations and the parity Fi(t)≡1+1A(t)+1A(t+di)(mod2)F_i(t)\equiv1+1_A(t)+1_A(t+d_i)\pmod 2. Outside the original window their magnitudes may grow.

To add the next height T≥LT\ge L, the only new unknowns are ui=Fi(T−di)u_i=F_i(T-d_i) on the three incoming edges. Each square with upper height TT prescribes the difference of two of the uiu_i. These three differences sum to zero around the cube with lower height T−LT-L, because the three opposite squares are already closed. More explicitly, the alternating sum of all six square boundaries of a cube cancels every edge. Thus one can choose u1u_1 freely and solve for u2,u3u_2,u_3 in integers. Choose u1u_1 of the prescribed parity. The other parities follow because the prescribed edge parities themselves sum to zero around every square. Continue upwards, then perform the reflected construction downwards with outgoing edges at each new lowest height.

Pull the extended values back to the whole cubic lattice by height. Their sum on any closed lattice walk vanishes, since steps in different coordinate directions may be interchanged across elementary squares and opposite steps cancel. Integrating therefore gives a potential. Translating by KK preserves all edge values, so potential differences under these translations are an integer homomorphism on KK. Its parity is the coordinate sum by the prescribed edge parities. The same integral extension on KK as above yields odd wiw_i. All pair cycles used in (2) remain inside the original window, where the absolute values still count defects.

Verification and priority

The verifier constructs the dual orientations, checks every square sum and reconstructs an odd period vector and common rotation from the signed pair cycles. It uses only standard Python and can be run with python3 results/haralambis-three-differences/verify.py. The general proof uses no computational assumption. A literature search located the conjecture, earlier special cases and the known character bound. We found no earlier resolution for arbitrary triples. Priority remains provisional.