Erdős–Szekeres: point sets with no convex k-gon

# Erdős–Szekeres: point sets with no convex k-gon ## Goal The happy-ending problem. `ES(k)` is the least `N` such that every `N` points in the plane in general position (no three collinear) contain `k` points in convex position, a *convex k-gon*. Erdős and Szekeres proved in 1935 that `ES(k)` is finite and in 1961 built `2^(k-2)` points with no convex k-gon, so `ES(k) >= 2^(k-2) + 1`; they conjectured equality. That is proven for `k <= 6` and open for every `k >= 7` (the best upper bound, Suk 2017 / Holmsen–Mojarrad–Pach–Tardos 2020, is `2^(k + o(k))`). This pack asks for the other side of the conjecture: **build the largest point set you can with no convex k-gon**, for `k = 6, 7, 8, 9, 10`. `points.py` exposes build(k: int, time_budget: float, seed: int) -> list[tuple[number, number]] returning any number of points `(x, y)`. Integer coordinates are the natural choice (any size: Python ints); floats are accepted too and are converted *exactly* (a float is a binary fraction), never rounded. The eval refuses to verify more than `record + 16` points. ## Metric metric = mean over k in {6, 7, 8, 9, 10} of points(k) / record(k) Verification is exact integer arithmetic. The eval scales the returned coordinates to a common integer grid, checks general position with integer cross products over every triple, then runs the classical dynamic programme for the largest subset in convex position (for each point as the bottom-most vertex, sort the rest by angle and extend convex chains by left turns; `O(N^4)` worst case, about 0.6 s at `N = 128` and 10 s at `N = 256`). A set that has three collinear points or a convex k-gon on any `k` fails the whole run (`wrong_answer`) rather than scoring low. The per-instance counts and ratios are in the eval output (`per_instance`); any `k` above its record is listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to `build`. ## Records | k | best-known points | source | proven optimal | |---|-------------------|--------|----------------| | 6 | 16 | Erdős–Szekeres (1961) construction; `ES(6) = 17` proved by Szekeres & Peters (2006, computer search) | yes | | 7 | 32 | Erdős–Szekeres (1961) construction; `ES(7) = 33` conjectured | no | | 8 | 64 | same | no | | 9 | 128 | same | no | | 10 | 256 | same | no | AlphaEvolve problem 58, "Erdős–Szekeres Happy Ending problem" (Georgiev, Gómez-Serrano, Tao, Wagner, *Mathematical Exploration and Discovery at Scale*, arXiv:2511.02864, section 6.38), searched for `2^(k-2) + 1` points with no convex k-gon for `k = 7` and `k = 8`, i.e. for a counterexample to the conjecture. Its notebook reports 33- and 65-point sets with "0 convex k-gons", but that count came from a floating-point orientation test with a `1e-9` threshold on tightly clustered points; recounted with exact arithmetic (this pack's checker) each set contains exactly one convex k-gon. So the records stand at `2^(k-2)`, and the repository's status file lists problem 58 in no category. Beating any `k >= 7` row here would disprove the Erdős–Szekeres conjecture: treat a ratio above 1.0 as a bug until the hub's exact re-verification agrees. ## Constraints - Standard library only (`math`, `random`, `itertools`, `functools`, `collections`, `heapq`, `time`). The eval rejects other imports. - Respect `time_budget` (seconds, per call). - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_INSTANCES` is a comma-separated subset of `6,7,8,9,10`; the full set is the default. - `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `build` per instance (default 15). ``` ZT_EVAL_INSTANCES=6,7 ZT_EVAL_PER_INSTANCE_SECONDS=3 python eval.py ``` ## Ideas that are known to matter (check the journal before repeating one) - **The 1961 construction scores 1.0 on every k.** Build cup–cap blocks: `f(a, b)` is a set with no `a`-cap and no `b`-cup (caps and cups are chains with decreasing / increasing slopes when read left to right) of size `C(a+b-4, a-2)`; `f(2, b) = f(a, 2) =` one point, and `f(a, b)` is `f(a, b-1)` on the left together with `f(a-1, b)` placed far to the right and far *above* it, so that every right point lies above every line through two left points and every left point lies below every line through two right points. Then take `S_i = f(i+2, k-i)` for `i = 0..k-2` (sizes `C(k-2, i)`, total `2^(k-2)`) and place them left to right, each block far to the right and far *below* everything before it with the same two line conditions mirrored. Integer coordinates with big offsets make the placement exact (about 70 bits for `k = 9`). - Beyond the record you are looking for a counterexample to a 90-year-old conjecture. The record sets are rigid, so unstructured local search from them rarely helps; the notebook's near-misses (`2^(k-2) + 1` points with a single convex k-gon) are a more interesting neighbourhood: find such sets and try to break the one remaining polygon. - Exact incremental checking is cheap: keep the chain-length tables per pivot, or just rerun the DP with early exit, which is under a millisecond at `N <= 32`. - Random point sets are useless: 128 random points already contain convex 23-gons. 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.