Furstenberg–Sárközy: modular sets avoiding k-th power differences

# Furstenberg–Sárközy: modular sets avoiding k-th power differences ## Goal The Furstenberg–Sárközy theorem says a subset of `{1, ..., N}` with no two elements differing by a perfect square has size `o(N)`. The best lower bounds come from a modular construction (Ruzsa 1984): take a squarefree modulus `m` and a set `A ⊆ Z/mZ` in which no two distinct elements differ by a nonzero `k`-th power residue mod `m`; writing integers in base `m` with digits from `A` lifts this to a subset of `{1, ..., N}` of size about `N^q` with `q = log|A| / log m` (Ruzsa's exponent for squares is then `½(1 + q)`). Ruzsa used `m = 65`, `|A| = 7`; Lewko (2015) found `m = 205`, `|A| = 12`, which is the current record for squares. For cubes the known construction is 14 elements in `Z/91Z`. This is AlphaEvolve Problem 31 (Section 6.16 of arXiv:2511.02864; the notebook header numbers it 32). AlphaEvolve reproduced both records and found nothing better. The open question this pack poses is: **is there a squarefree `m` with a larger `log|A| / log m`?** `modset.py` exposes modular_set(k: int, time_budget: float, seed: int) -> tuple[int, list[int]] returning `(m, A)`: `m` a squarefree Python int with `2 ≤ m ≤ 1_000_000`, and `A` a list of distinct Python ints in `[0, m)`. Instances are `k2` (squares) and `k3` (cubes). ## Metric The eval recomputes the nonzero `k`-th power residues `{y^k mod m : 1 ≤ y < m}`, checks `m` is squarefree, and checks every ordered pair `a ≠ b` in `A` has `(a − b) mod m` outside that set. Then q = log|A| / log m (0 if |A| < 2) metric = mean over k of q / q_record | label | k | record | q_record | source | status | |---|---|---|---|---|---| | `k2` | 2 | `m = 205`, `|A| = 12` | 0.466824 | M. Lewko, "An improved lower bound related to the Furstenberg–Sárközy theorem", Electron. J. Combin. 22(1) (2015) P1.32; Ruzsa 1984 had `m = 65`, `|A| = 7` (q = 0.466155); AlphaEvolve Problem 31 reproduces it | 12 is the exact maximum for `m = 205` (exhaustive branch-and-bound while building this pack); whether any other `m` beats the exponent is open | | `k3` | 3 | `m = 91`, `|A| = 14` | 0.585045 | AlphaEvolve Problem 31 (arXiv:2511.02864, Section 6.16) states it as the known lower bound and reproduces it | 14 is the exact maximum for `m = 91` (exhaustive search); other `m` open | Two warnings. The explicit sets printed in the AlphaEvolve notebook (`furstenberg_sarkozy.ipynb`) do **not** verify: they contain forbidden differences. The sizes are right; find your own sets (e.g. for `m = 205`: `{0, 2, 8, 14, 77, 79, 85, 96, 103, 109, 111, 181}`). And the scale is compressed: exponents of sensible constructions all sit between 0.40 and 0.47, so a ratio of 0.998 is Ruzsa's construction and 1.0015 would be a new theorem. `tolerance` in `problem.toml` is set accordingly; make your solver deterministic in its outcome, not just its seed. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. - `m ≤ 1_000_000` (the eval enumerates residues in `O(m)`). ## Iterating - `ZT_EVAL_INSTANCES=k2` restricts the eval to one power (default `k2,k3`). - `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget (default 40; the full eval can take up to about 80 s; the baseline stops early). - `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed. ## Ideas that are known to matter (check the journal before repeating one) - For a fixed `m` this is a maximum independent set in a circulant graph (vertices `Z/mZ`, edges at `±` residue differences); it is translation-invariant, so fix `0 ∈ A`. Bitset branch-and-bound solves `m = 205` exactly in seconds in pure Python. - Products of small primes (`65 = 5·13`, `205 = 5·41`, `91 = 7·13`) win because the residue set is a product set (CRT) and stays small: fewer forbidden differences per modulus. Enumerate `m` by the *fraction* of residues that are `k`-th powers first, then search only the promising ones. - Ruzsa's exponent for squares only uses `q`; for higher powers the lifting differs, but the modular problem scored here is the same. - Lewko searched `m` by computer; the frontier is wherever pure Python plus cleverness runs out. Write one honest line in `NOTES.md`: the idea, and which `k` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.