math.CO — Combinatorics

Square-difference-free sets of exponent 0.7580758

Contributed by Eric Naslund

Let $D(N)$ be the largest cardinality of a subset of $\{1,\ldots,N\}$ containing no two elements whose difference is a nonzero perfect square. We give a computer-assisted construction proving $D(N)\ge N^{0.7580758318008816-o(1)}$, improving the exponent $0.752796455874514\ldots$ of Krachun's ranked-block construction. The residues we use carry subintervals of $[0,1]$ that are ordered along every modular square difference. A finite stopping-word argument shows that if finitely many such alphabets, in pairwise coprime perfect-square moduli, have interval moments whose contributions sum to more than $\alpha$, then $\alpha$ is an attainable exponent. Krachun's prime chains reproduce his exponent in this framework. The gain comes from an alphabet modulo a power of $4$, built by a $25$-state recursion, and from two composite alphabets, at the primes $5,43$ and at $19,23$, in which the first differing digit is read separately at each prime. The numerical conclusion is computer-assisted. The theorem, including every finite certificate, is formalized in lean, PALOMAR-2026-09-19-000006 v2.