Motzkin density for two forbidden differences in compact abelian groups

What Lean checks

The exact compact-group character formula, exhaustive relation-basis trichotomy, all-modulus cyclic formulas, gcd scaling, odd-cycle criterion, and stated example are checked. The literal fixed character window and rational interval unions attain the stated bounds. The exact floor-sum evaluator, Hermite independence number, attaining character, and explicit arithmetic-operation and integer-size bounds are checked and registered.

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

Let GG be a compact Hausdorff abelian group with Haar probability measure, and let a,ba,b be nonzero elements. The Motzkin density MG(a,b)M_G(a,b) is the supremum of the measures of Borel sets whose differences avoid aa and bb. If Ĝ\widehat G denotes the continuous homomorphisms from GG to 𝕋=ℝ/ℤ\mathbb T=\mathbb R/\mathbb Z, then

MG(a,b)=supχ∈Ĝmin(∥χ(a)∥,∥χ(b)∥).\boxed{M_G(a,b)=\sup_{\chi\in\widehat G}\min(\|\chi(a)\|,\|\chi(b)\|).}

Here ∥r∥\|r\| is the distance to the nearest integer. The theorem treats the complete two-difference case of Candela, Chamizo and Córdoba's Problem 1.1. Their Theorem 2.5 reduces the compact problem to a lattice quotient, and their Theorem 4.1 gives the density when the relation lattice has rank one. We give one proof covering all relation ranks, including finite noncyclic quotients. Problem 1.1 and earlier results

Prior work on the cyclic case. Candela, Catalá, Rué and Serra determined the density for two circle differences when at least one is irrational. They bounded the rational case via a finite circulant graph. In May 2026 Carotenuto, Nicoloso and Salvatore published an exact linear-time solution for connected four-regular circulants using odd-cycle transversals. The argument below independently recovers that independence number through a character and applies to general compact abelian groups. Circle problem, prior exact circulant solution

For example, let G=ℤ/NℤG=\mathbb Z/N\mathbb Z, let a,ba,b generate GG, and write |r|N=min(rmodN,(−r)modN)|r|_N=\min(r\bmod N,(-r)\bmod N). The theorem gives the independence number α=max0≤t<Nmin(|ta|N,|tb|N)\alpha=\max_{0\le t\lt N}\min(|ta|_N,|tb|_N). Each independent set of size ss implies the existence of a multiplier tt with both distances at least ss.

The lower bound

For a continuous character χ\chi, set h=min(∥χ(a)∥,∥χ(b)∥)h=\min(\|\chi(a)\|,\|\chi(b)\|). The preimage of [0,h)[0,h) in the circle avoids both differences. Its measure is hh because the image of GG is a closed subgroup of the circle and the pushforward of Haar probability is Haar probability on that subgroup. For full circle image this is interval length. For finite image of order mm, the fraction is again hh since mhmh is integral. This proves the lower bound also when h=0h=0.

The upper bound for finite groups

Let HH be any finite abelian group generated by a,ba,b, put N=|H|N=|H|, and let AA be an independent set in its Cayley graph for these jumps. Write x(z)x(z) for its indicator and ρ=|A|/N\rho=|A|/N. View the graph as the quotient of the square grid by

Λ={(u,v)∈ℤ2:ua+vb=0 in H}.\Lambda=\{(u,v)\in\mathbb Z^2:ua+vb=0\text{ in }H\}.

Put d1=ad_1=a and d2=bd_2=b. For the edge in direction ii at zz, define

ci(z)=1−x(z)−x(z+di).c_i(z)=1-x(z)-x(z+d_i).

Independence gives ci(z)∈{0,1}c_i(z)\in\{0,1\}. It marks the edges with two unoccupied ends. In each direction separately, there are N−2|A|N-2|A| marked edges. Around every unit square the number of marked sides is even, since modulo two each corner indicator occurs twice.

Assign signs to the marked edges. On the finite quotient grid, make one dual vertex per square and one dual edge across each marked side. Every dual degree is even. Orient the edges along an Euler tour in each nonempty component. For a marked edge of the original grid, put wi(z)=+1w_i(z)=+1 when the dual arrow passes from the face on the left of the positive grid edge to the face on its right, and −1-1 otherwise. On unmarked edges put wi(z)=0w_i(z)=0. Count grid edges and squares with their labels even if some endpoints are identified in the quotient. The signed sum of ww around a counterclockwise square equals the number of outgoing dual arrows minus incoming dual arrows at its face. Consequently

w1(z)+w2(z+a)−w1(z+b)−w2(z)=0.w_1(z)+w_2(z+a)-w_1(z+b)-w_2(z)=0. \tag{1}

Integrate and average. Lift ww to the square grid and reverse its sign when traversing an edge backwards. Equation (1) makes its sum along a path depend only on the two endpoints. Interchanging adjacent coordinate steps preserves the sum, as does cancelling a step with its reverse. There is therefore an integer function h0h_0 on ℤ2\mathbb Z^2 with these increments.

For λ=(u,v)∈Λ\lambda=(u,v)\in\Lambda, the difference h0(p+λ)−h0(p)h_0(p+\lambda)-h_0(p) is constant in pp, since its increments in both directions are zero by periodicity. Denote it by L(λ)L(\lambda). Let mi=N−1∑zwi(z)m_i=N^{-1}\sum_z w_i(z). Average a fixed path from pp to p+λp+\lambda over the NN starting cosets. Each positive step in direction ii contributes mim_i, and each negative step contributes −mi-m_i. Thus

L(λ)=um1+vm2.L(\lambda)=u m_1+v m_2.

On every edge, wi≡ci≡1+x(z)+x(z+di)(mod2)w_i\equiv c_i\equiv1+x(z)+x(z+d_i)\pmod2. In the path sum the internal indicators cancel, and the endpoint indicators agree because λ∈Λ\lambda\in\Lambda. It follows that L(λ)≡u+v(mod2)L(\lambda)\equiv u+v\pmod2. Therefore the map

(u,v)↦u(1−m1)/2+v(1−m2)/2(mod1)(u,v)\longmapsto u(1-m_1)/2+v(1-m_2)/2 \pmod1

vanishes on Λ\Lambda. It defines a character ψ\psi on H=ℤ2/ΛH=\mathbb Z^2/\Lambda. Finally, |mi|≤N−1∑zci(z)=1−2ρ|m_i|\le N^{-1}\sum_z c_i(z)=1-2\rho, so both (1−mi)/2(1-m_i)/2 belong to [ρ,1−ρ][\rho,1-\rho]. Evaluating ψ\psi at a,ba,b yields min(∥ψ(a)∥,∥ψ(b)∥)≥ρ\min(\|\psi(a)\|,\|\psi(b)\|)\ge\rho. In the cyclic case ψ(z)=tz/N(mod1)\psi(z)=tz/N\pmod1 for some integer tt. This proves the asserted finite formula.

Passing to a compact abelian group

Let H=⟨a,b⟩H=\langle a,b\rangle now denote the abstract subgroup generated by the differences in GG. The restrictions of the continuous characters of GG are dense in the character group of discrete HH, evaluated on a,ba,b. To see this, identify each pair of values with a point of 𝕋2\mathbb T^2. An integer pair (u,v)(u,v) annihilates all continuous-character evaluations if and only if every continuous character vanishes at ua+vbua+vb, which is equivalent to ua+vb=0ua+vb=0 by separation of points. The closed subgroup theorem for the torus (equivalently, Pontryagin biduality) says that the closure of these evaluations is the annihilator of this integer relation lattice. That annihilator is precisely the pairs arising from homomorphisms H→𝕋H\to\mathbb T. Thus each character on a finite quotient of HH gives a lower bound on the displayed supremum through its two evaluations. The torus annihilator argument, Lemma 6.1

Suppose a Borel avoiding set in GG has measure ρ\rho. If HH is finite, some translate of HH contains an occupied fraction at least ρ\rho, by averaging translations over GG. Apply the finite result to that independent set.

Otherwise write H≅F×ℤdH\cong F\times\mathbb Z^d, where FF is finite and 1≤d≤21\le d\le2. Set Bn=F×{0,…,n−1}dB_n=F\times\{0,\ldots,n-1\}^d. Averaging over GG gives a translate of BnB_n containing at least ρ|Bn|\rho|B_n| occupied sites. Let LL bound the magnitudes of all free coordinates of both jumps. Delete sites within LL layers of any box face, losing at most a fraction 2dL/n2dL/n for n>2Ln>2L. The remaining occupied sites project injectively to Hn=F×(ℤ/nℤ)dH_n=F\times(\mathbb Z/n\mathbb Z)^d and remain independent there. Starting in the interior and taking a jump stays in the box, where equality of projected sites implies equality of representatives. For sufficiently large nn, the images of the two jumps are nonzero. They generate HnH_n.

The finite result gives a character of HnH_n with both distances at least ρ−2dL/n\rho-2dL/n. Pull it back to HH and use density of restrictions to bound the supremum over Ĝ\widehat G by the same quantity from below. Let n→∞n\to\infty. This proves the upper bound for every Borel avoiding set.

Computing the value from the relations

Let Λ={(u,v):ua+vb=0}\Lambda=\{(u,v):ua+vb=0\} in the original compact group. The supremum in the theorem equals the maximum of min(∥x∥,∥y∥)\min(\|x\|,\|y\|) on the annihilator of Λ\Lambda in 𝕋2\mathbb T^2. This yields the following explicit evaluation.

  • If Λ=0\Lambda=0, the value is 1/21/2, attained on the annihilator at (1/2,1/2)(1/2,1/2).
  • If Λ=⟨(u,v)⟩\Lambda=\langle(u,v)\rangle has rank one, put k=|u|+|v|k=|u|+|v|. The value is ⌊k/2⌋/k\lfloor k/2\rfloor/k, recovering Candela, Chamizo and Córdoba's rank-one theorem. When kk is even use (1/2,1/2)(1/2,1/2). When it is odd, choose x,yx,y equal to ⌊k/2⌋/k\lfloor k/2\rfloor/k with the signs of u,vu,v respectively, choosing either sign for a zero coordinate. Then ux+vyux+vy is integral. Conversely, if both distances are at least hh, write x=(1+e)/2x=(1+e)/2, y=(1+f)/2y=(1+f)/2 modulo one with |e|,|f|≤1−2h|e|,|f|\le1-2h. Since ux+vyux+vy is integral and u+vu+v odd, ue+vfue+vf is an odd integer. Thus 1≤k(1−2h)1\le k(1-2h).
  • In rank two, take a lattice basis (m,0),(s,k)(m,0),(s,k) with m,k>0m,k>0, 0≤s<m0\le s\lt m. The value is the largest of the mkmk numbers min(∥i/m∥,∥j/k−si/(mk)∥)\min(\|i/m\|,\|j/k-si/(mk)\|) for 0≤i<m0\le i\lt m and 0≤j<k0\le j\lt k. These are all the characters because the two defining congruences are mx=0mx=0 and sx+ky=0sx+ky=0 modulo one. This covers finite subgroups with two nontrivial invariant factors as well as cyclic ones.

Evaluation without enumerating the finite quotient

In rank two put N=mkN=mk. The exact independence number and an attaining character can be computed in O(log2N)O(\log^2 N) arithmetic operations on O(logN)O(\log N)-bit integers. The input is the three integers m,k,sm,k,s describing the quotient. An explicit list of all vertices of a maximum independent set can of course have size proportional to NN.

For a proposed integer size 1≤h≤N/21\le h\le N/2, the first character residue kiki must lie in [h,N−h][h,N-h]. This restricts ii to an integer interval [I,J]⊆[0,m−1][I,J]\subseteq[0,m-1]. At fixed ii, the possible second residues modulo NN are exactly those congruent to −si(modm)-si\pmod m. Thus the number of feasible residue pairs is

∑i=IJ(⌊N−h+sim⌋−⌊h−1+sim⌋).\sum_{i=I}^{J}\left( \left\lfloor\frac{N-h+si}{m}\right\rfloor- \left\lfloor\frac{h-1+si}{m}\right\rfloor \right).

A positive count is equivalent to feasibility. Binary search finds the greatest feasible hh. A second binary search on the endpoint JJ finds the first feasible row, giving its two character residues. For a connected cyclic input (N,a,b)(N,a,b), use k=gcd(N,a)k=\gcd(N,a), m=N/km=N/k, and s≡−b(a/k)−1(modm)s\equiv-b(a/k)^{-1}\pmod m (take s=0s=0 if m=1m=1). The relations (m,0),(s,k)(m,0),(s,k) hold and their determinant is NN, so they give the required basis.

For the complexity claim, let F(n,M,A,B)=∑i=0n−1⌊(Ai+B)/M⌋F(n,M,A,B)=\sum_{i=0}^{n-1}\lfloor(Ai+B)/M\rfloor. Removing the integer quotients of A,BA,B by MM adds explicit arithmetic progressions, leaving 0≤A,B<M0\le A,B\lt M. Put An+B=qM+rAn+B=qM+r, 0≤r<M0\le r\lt M. When q=0q=0 the remaining sum is zero. Otherwise A>0A>0 and counting the terms at each positive height jj gives

F(n,M,A,B)=∑j=1q(n−⌈Mj−BA⌉)=F(q,A,M,r).F(n,M,A,B)=\sum_{j=1}^q\left(n-\left\lceil\frac{Mj-B}{A}\right\rceil\right) =F(q,A,M,r).

At each recursion the modulus drops from MM to AA, and the next reduction replaces MM by its remainder modulo AA. This is the Euclidean algorithm. Each binary-search comparison therefore uses O(logN)O(\log N) arithmetic operations. Exact evaluator

Two consequences

The circle problem. Write two nonzero rational circle differences as a/N,b/Na/N,b/N with their least common denominator NN. For every y∈[0,1/N)y\in[0,1/N), a measurable avoiding set occupies at most α\alpha of the points y+j/Ny+j/N. Integration gives an upper bound of α/N\alpha/N on its normalized measure. Taking the union of [j/N,(j+1)/N)[j/N,(j+1)/N) over a maximum independent set attains it. Thus the displayed formula divided by NN is the exact Motzkin density. Together with the authors' Theorem 1.2 for pairs containing an irrational difference, this gives the density for every pair on the circle. Equivalently, the character lower bound of Candela, Chamizo and Córdoba is exact for two circle differences. Candela et al., Theorem 1.2, Candela, Chamizo and Córdoba, Theorem 6.2 and Section 6

When the odd-girth bound is sharp. If the graph has odd girth kk, put U=⌊N(k−1)/(2k)⌋U=\lfloor N(k-1)/(2k)\rfloor. Every independent set meets each translated shortest odd cycle in at most (k−1)/2(k-1)/2 vertices, giving α≤U\alpha\le U. A connected cyclic graph attains this upper bound exactly when there are r,s∈[U,N−U]∩ℤr,s\in[U,N-U]\cap\mathbb Z with

br≡as(modN).br\equiv as\pmod N.

Indeed, the pairs (ta,tb)(ta,tb) modulo NN lie in the kernel of (r,s)↦br−as(r,s)\mapsto br-as. This homomorphism is onto by gcd(a,b,N)=1\gcd(a,b,N)=1, so the kernel has size NN. The NN pairs (ta,tb)(ta,tb) are distinct for the same gcd reason, and hence fill the kernel. The criterion follows from the theorem. For example, at N=24N=24, a=3a=3, b=4b=4, the predicted upper bound from the 7-cycle is 10, but no pair in [10,14]2[10,14]^2 satisfies the congruence. The maximum is 9, attained at t=3t=3. This is Example 4.4 of the original paper. Original example

For a cyclic group in which the jumps generate a proper subgroup, the graph is a disjoint union of isomorphic connected components. With g=gcd(N,a,b)g=\gcd(N,a,b), multiply the answer for (N/g,a/g,b/g)(N/g,a/g,b/g) by gg.

Checks and scope

The accompanying Python program compares the formula with a direct maximum-independent-set calculation on cyclic and noncyclic groups. It also constructs the signed dual orientation for individual independent sets, checks (1) at every square, and recovers a character from the resulting averages. Run python3 results/two-difference-motzkin/verify.py from the repository root. Executable checks

The integer-line problem for three arbitrary forbidden differences is Haralambis's separate conjecture. The sign assignment above uses the fact that a grid edge has two incident squares. A search under Motzkin densities, two-jump circulants, toroidal quadrangulations and star-extremal circulants located the prior results cited above. We found no earlier statement of the character identity for all compact abelian groups with two differences. Priority for that general formulation remains provisional. Liu and Robinson on the integer-line problem