Erdős squares in a square, maximum total side length

# Erdős squares in a square, maximum total side length ## Goal `pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float, float]]`: `n` squares `(cx, cy, theta, s)` inside the unit square `[0, 1] x [0, 1]`, where `(cx, cy)` is the centre, `theta` the rotation in **radians** (0 means axis-aligned; any real value is accepted) and `s >= 0` the side length. Interiors must be pairwise disjoint (touching is fine). Maximise `sum(s)`. Let `f(n)` be the maximum. Erdős asked in 1932 whether `f(k^2 + 1) = k`, i.e. whether one extra square buys nothing over the trivial `k x k` grid. Erdős–Soifer (1995) and Campbell–Staton (2005) independently gave the construction `f(k^2 + 2c + 1) >= k + c/k` for `-k < c < k` and conjectured it is optimal; Praton (2005, arXiv:math/0504341) showed that conjecture is equivalent to the original one. Baek, Koizumi and Ueoro (2024, arXiv:2411.07274) proved it when all squares are axis-parallel, so any improvement must use rotated squares. This is problem 55 of the AlphaEvolve repository of problems (arXiv:2511.02864, section 6.35); AlphaEvolve matched the known constructions for exactly the seven `n` used here and found nothing better. Beat any row of the table below and you have disproved a 90-year-old conjecture. ## Metric metric = mean over n in {10, 12, 14, 17, 26, 37, 50} of sum_s(n) / best_known(n) The eval validates every square before it sums anything: finite numbers, `s >= 0`, all four corners inside the unit square (tolerance `EPS = 1e-9` per coordinate), and no pair of squares overlapping by more than `EPS`, tested with the separating axis theorem on the four edge normals, the same geometry as the AlphaEvolve verifier. The tolerance runs the way this repository's other packing evals run it: touching is fine and penetration up to `EPS` is forgiven (the AlphaEvolve notebook instead demanded a strict `1e-9` gap). A square with `s <= EPS` is a point: it must lie in the unit square and cannot overlap anything. A wrong answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so your method must be robust to its starting point. ## Records `n = k^2 + 2c + 1`, best known `k + c/k`. None is proven optimal in general (only `f(2) = 1`, `f(5) = 2` and `f(k^2) = k` are theorems, and the whole table is proven for axis-parallel packings). | n | k, c | best known | source | |---|---|---|---| | 10 | 3, 0 | 3 | Erdős–Soifer (1995) construction; AlphaEvolve problem 55 matched it | | 12 | 3, 1 | 10/3 = 3.3333... | Campbell–Staton (2005) construction; AlphaEvolve matched it | | 14 | 3, 2 | 11/3 = 3.6666... | Campbell–Staton (2005) construction; AlphaEvolve matched it | | 17 | 4, 0 | 4 | Erdős–Soifer construction; AlphaEvolve matched it | | 26 | 5, 0 | 5 | Erdős–Soifer construction; AlphaEvolve matched it | | 37 | 6, 0 | 6 | Erdős–Soifer construction; AlphaEvolve matched it | | 50 | 7, 0 | 7 | Erdős–Soifer construction; AlphaEvolve matched it | The known constructions are axis-parallel. Start from the `k x k` grid of squares of side `1/k` (sum `k`). For `c >= 1`, replace a `c x c` block of it by a `(c + 1) x (c + 1)` grid of squares of side `c / (k (c + 1))`: the count rises by `2c + 1` and the sum by `c/k`. For `c = 0` the record is the plain grid plus one zero-side square, which the eval accepts; Erdős' question is precisely whether that extra square can ever be given positive size without losing more elsewhere. (For `c < 0`, merge a `|c| x |c|` block into `(|c| - 1)^2` squares of side `|c| / (k (|c| - 1))`.) ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval kills a call at `1.25 * time_budget + 3 s`. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_NS=10,17 python eval.py` runs a subset of the instances. - `ZT_EVAL_PER_N_SECONDS=2 python eval.py` shortens the per-`n` budget (default 15 s, so the full seven-instance eval takes about 105 s of solver time). ## Ideas that are known to matter (check the journal before repeating one) - Reproducing `k + c/k` is a construction, not a search; write it down and spend the budget on perturbations that rotate a few squares. - Any improvement must be non-axis-parallel (Baek–Koizumi–Ueoro). Look at where rotated squares could wedge into the slack a `1/k` grid leaves once one cell is subdivided. - Penalty-method gradient descent on `-sum(s) + w * (overlap + outside)` over `(cx, cy, theta, s)` with `w` ramped, then a final feasibility projection that shrinks offending squares slightly. - Combinatorial skeleton search: which squares touch which and at what angle, then continuous optimisation of the rest. 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.