Isosceles-free subsets of the n x n grid

# Isosceles-free subsets of the n x n grid ## Goal `solver.py` exposes `solve(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]`: a list of distinct grid points `(x, y)` with integer coordinates in `0..n-1` such that no three of them form an isosceles triangle. Maximise the number of points. Three distinct points `a, b, c` form a forbidden triangle when two of the three pairwise distances are equal, `|ab| = |bc|` for some labelling. Flat triangles count: a point midway between two others is `|ab| = |bc|` with `b` on the segment, so three points in arithmetic progression on any line are also forbidden. Equivalently: for every point `a` of your set, the distances from `a` to all the other points must be pairwise distinct. This is problem 59 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano, Tao, Wagner, "Mathematical exploration and discovery at scale", arXiv:2511.02864, section 6.39), a question asked independently by Wu, Ellenberg-Jain and possibly Erdos. Asymptotically only `n / sqrt(log n) <~ C(n) <~ exp(-c (log n)^(1/9)) n^2` is known; even `C(n) < n^1.99` is open. Computationally, SAT solvers settle `n <= 32`, the optimal sizes look linear (about `16n/9` was the guess in the PatternBoost paper), and the records for `n = 64` and `n = 100` were found by machine search after months of human attempts. AlphaEvolve found 112 points in the 64 x 64 grid (a size the PatternBoost authors had been chasing for months) and 164 in the 100 x 100 grid, and the authors "believe this is still not optimal". ## Instances and records Every instance is scored against the best-known size. `record_ratio` for an instance is `size / record`, so 1.0 is a match and above 1.0 is a new record. | n | best known | proven optimal | source | |---|---|---|---| | 16 | 28 | yes (SAT) | Charton, Ellenberg, Wagner, Williamson, "PatternBoost", arXiv:2411.00566, section 4.1, Figure 12; quoted as C(16) = 28 in arXiv:2511.02864 section 6.39 | | 32 | 56 | yes (SAT) | same, Figure 12; quoted as C(32) = 56 in arXiv:2511.02864 section 6.39 | | 64 | 112 | no | AlphaEvolve, arXiv:2511.02864 section 6.39 and repository problem 59 (notebook `sol_64`); previous best 110 (PatternBoost), 108 by classical search | | 100 | 164 | no | AlphaEvolve, arXiv:2511.02864 section 6.39 and repository problem 59 (notebook `sol_100`); previous best 160 (PatternBoost), 154 by classical search | The two small instances are calibration: they tell you whether your search finds known optima at all. The two large ones are open; the 100 x 100 record in particular is believed to be beatable. The repository lists problem 59 as a world record set by AlphaEvolve. ## Metric metric = mean over n in {16, 32, 64, 100} of size(n) / record(n) The eval re-derives everything from the point list you return: integer coordinates inside the grid, no repeated points, and the isosceles-free check on every apex. Any violation on any `n` is a failed run (`wrong_answer`), and a solver that raises or overruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed, so your method has to be robust to its starting point. ## Constraints - Standard library only. No numpy, no scipy, no numba. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 25 s per instance, so a full eval takes about 100 s; use the whole budget, nothing is gained by returning early. - Deterministic given `seed`: use `random.Random(seed)`. - Coordinates are `0..n-1` (the AlphaEvolve notebook convention; the papers use `1..n`). ## Iterating quickly - `ZT_EVAL_INSTANCES=64` (comma-separated `n` values from the table) runs a subset. - `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget. Example: `ZT_EVAL_INSTANCES=16,32 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py`. ## Ideas that are known to matter (check the journal before repeating one) - Keep an incremental structure: for each point the set of squared distances to the others. Adding a point `q` is legal iff no distance from `q` repeats and no existing point already has that distance. That makes add / remove / check `O(|S|)`, which is what every strong search relies on. - The records are close to four-fold symmetric (reflections in a horizontal and a vertical axis). The axes need not pass through the centre: for even `n` they may be offset by half a cell in one direction (e.g. `(31, 31.5)` instead of `(31.5, 31.5)` for `n = 64`). Search over symmetric generator orbits first, then break the symmetry with a few asymmetric moves. - Almost nothing sits near the middle of the grid. Excluding a large central block shrinks the candidate set considerably; how large a block is safe is not known. - Iterated local search (remove 8-30% of the points, greedily refill from the boundary inward, keep if not worse, accept equal-size moves to drift across plateaus) is the loop that reached 110 and 112 for `n = 64`. Run it for the whole budget. - The best small-`n` constructions look very different from one another, so restarts from several symmetric seeds beat one long run from a single one. Write one honest line in `NOTES.md`: the idea, and which `n` 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.