← All papers
First page of A Proof of Fraenkel's Conjecture

A Proof of Fraenkel's Conjecture

Hu Tan, Ying Zhang

math.NT Sep 1, 2026 · v2
Lean code accompanying the finite-case verifications of the proof is released in a public GitHub repository.
Fraenkel's conjecture asserts that a partition of the integers into at least three Beatty sequences with distinct moduli has the binary densities $1,2,4,\ldots,2^{m-1}$, normalized by $2^m-1$. We prove the conjecture through a dimension-free intermediate statement: every such partition contains a component of density at least 1/3. After reducing the partition to primitive common-period data, Fourier cancellation produces a finite inverse-sine system. We prove that no such system can exist when every density is below 1/3. The proof combines a divisor-concentration identity with uniform analytic estimates and three exact finite verifications, all carried out with integer or rational arithmetic. The component supplied by the density bound has mean spacing at most three. Deleting it preserves balance, and every surviving periodic balanced set is again a rational Beatty set. Induction determines the surviving binary scales, while a two-sequence disjointness criterion forces the deleted density to be the next binary scale. This yields the asserted density pattern.An eventual Beatty representation of balanced binary indicators extends the classification to one-sided balanced sequences on at least three letters with distinct positive densities, proving the balanced-sequence conjecture of Altman, Gaujal, and Hordijk.

Fraenkel's conjecture states that a partition of the integers into m ≥ 3 Beatty sequences with pairwise distinct moduli must have moduli (2^m−1)/2^j for 0 ≤ j < m. It was previously known only for m ≤ 7.

The proof first establishes a dimension-free 'one-third theorem': every such partition has a component of density at least 1/3. Data are reduced to a primitive common period, and Graham–O'Bryant Fourier cancellation yields a finite inverse-sine row system. A divisor-concentration slack identity and analytic kernel estimates bound the problem size, and exact integer/rational finite verifications exclude the remaining cases. Tijdeman-style balanced-word deletion and induction then recover the binary density pattern.

The paper gives a full proof of Fraenkel's conjecture for all m ≥ 3. It also proves the balanced-sequence conjecture of Altman, Gaujal, and Hordijk for one-sided balanced sequences on at least three letters with distinct densities. Finite-verification code and accompanying Lean code are publicly released.