Cinna Davis and GPT-6.2 Astra · November 2026 · Unrefereed proof
Let be a compact Hausdorff abelian group with Haar probability measure, and let be nonzero elements. The Motzkin density is the supremum of the measures of Borel sets whose differences avoid and . If denotes the continuous homomorphisms from to , then
Here 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 , let generate , and write . The theorem gives the independence number . Each independent set of size implies the existence of a multiplier with both distances at least .
The lower bound
For a continuous character , set . The preimage of in the circle avoids both differences. Its measure is because the image of 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 , the fraction is again since is integral. This proves the lower bound also when .
The upper bound for finite groups
Let be any finite abelian group generated by , put , and let be an independent set in its Cayley graph for these jumps. Write for its indicator and . View the graph as the quotient of the square grid by
Put and . For the edge in direction at , define
Independence gives . It marks the edges with two unoccupied ends. In each direction separately, there are 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 when the dual arrow passes from the face on the left of the positive grid edge to the face on its right, and otherwise. On unmarked edges put . Count grid edges and squares with their labels even if some endpoints are identified in the quotient. The signed sum of around a counterclockwise square equals the number of outgoing dual arrows minus incoming dual arrows at its face. Consequently
Integrate and average. Lift 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 on with these increments.
For , the difference is constant in , since its increments in both directions are zero by periodicity. Denote it by . Let . Average a fixed path from to over the starting cosets. Each positive step in direction contributes , and each negative step contributes . Thus
On every edge, . In the path sum the internal indicators cancel, and the endpoint indicators agree because . It follows that . Therefore the map
vanishes on . It defines a character on . Finally, , so both belong to . Evaluating at yields . In the cyclic case for some integer . This proves the asserted finite formula.
Passing to a compact abelian group
Let now denote the abstract subgroup generated by the differences in . The restrictions of the continuous characters of are dense in the character group of discrete , evaluated on . To see this, identify each pair of values with a point of . An integer pair annihilates all continuous-character evaluations if and only if every continuous character vanishes at , which is equivalent to 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 . Thus each character on a finite quotient of 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 has measure . If is finite, some translate of contains an occupied fraction at least , by averaging translations over . Apply the finite result to that independent set.
Otherwise write , where is finite and . Set . Averaging over gives a translate of containing at least occupied sites. Let bound the magnitudes of all free coordinates of both jumps. Delete sites within layers of any box face, losing at most a fraction for . The remaining occupied sites project injectively to 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 , the images of the two jumps are nonzero. They generate .
The finite result gives a character of with both distances at least . Pull it back to and use density of restrictions to bound the supremum over by the same quantity from below. Let . This proves the upper bound for every Borel avoiding set.
Computing the value from the relations
Let in the original compact group. The supremum in the theorem equals the maximum of on the annihilator of in . This yields the following explicit evaluation.
- If , the value is , attained on the annihilator at .
- If has rank one, put . The value is , recovering Candela, Chamizo and Córdoba's rank-one theorem. When is even use . When it is odd, choose equal to with the signs of respectively, choosing either sign for a zero coordinate. Then is integral. Conversely, if both distances are at least , write , modulo one with . Since is integral and odd, is an odd integer. Thus .
- In rank two, take a lattice basis with , . The value is the largest of the numbers for and . These are all the characters because the two defining congruences are and 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 . The exact independence number and an attaining character can be computed in arithmetic operations on -bit integers. The input is the three integers describing the quotient. An explicit list of all vertices of a maximum independent set can of course have size proportional to .
For a proposed integer size , the first character residue must lie in . This restricts to an integer interval . At fixed , the possible second residues modulo are exactly those congruent to . Thus the number of feasible residue pairs is
A positive count is equivalent to feasibility. Binary search finds the greatest feasible . A second binary search on the endpoint finds the first feasible row, giving its two character residues. For a connected cyclic input , use , , and (take if ). The relations hold and their determinant is , so they give the required basis.
For the complexity claim, let . Removing the integer quotients of by adds explicit arithmetic progressions, leaving . Put , . When the remaining sum is zero. Otherwise and counting the terms at each positive height gives
At each recursion the modulus drops from to , and the next reduction replaces by its remainder modulo . This is the Euclidean algorithm. Each binary-search comparison therefore uses arithmetic operations. Exact evaluator
Two consequences
The circle problem. Write two nonzero rational circle differences as with their least common denominator . For every , a measurable avoiding set occupies at most of the points . Integration gives an upper bound of on its normalized measure. Taking the union of over a maximum independent set attains it. Thus the displayed formula divided by 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 , put . Every independent set meets each translated shortest odd cycle in at most vertices, giving . A connected cyclic graph attains this upper bound exactly when there are with
Indeed, the pairs modulo lie in the kernel of . This homomorphism is onto by , so the kernel has size . The pairs are distinct for the same gcd reason, and hence fill the kernel. The criterion follows from the theorem. For example, at , , , the predicted upper bound from the 7-cycle is 10, but no pair in satisfies the congruence. The maximum is 9, attained at . 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 , multiply the answer for by .
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