{"id":"erdos-szekeres-kgon-free","name":"Erdős–Szekeres: point sets with no convex k-gon","family":"discrete-geometry","description":"The happy-ending problem: place as many points in general position as you can with no k of them in convex position, for k = 6..10. Exact verification; the best-known sizes are the Erdős–Szekeres 2^(k-2) constructions, and beating any of them for k >= 7 would disprove the Erdős–Szekeres conjecture.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":240,"agent_timeout_seconds":1800,"mutable":["points.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Erdős–Szekeres: point sets with no convex k-gon\n\n## Goal\n\nThe happy-ending problem. `ES(k)` is the least `N` such that every `N` points in the plane in\ngeneral position (no three collinear) contain `k` points in convex position, a *convex k-gon*.\nErdős and Szekeres proved in 1935 that `ES(k)` is finite and in 1961 built `2^(k-2)` points with\nno convex k-gon, so `ES(k) >= 2^(k-2) + 1`; they conjectured equality. That is proven for\n`k <= 6` and open for every `k >= 7` (the best upper bound, Suk 2017 / Holmsen–Mojarrad–Pach–Tardos\n2020, is `2^(k + o(k))`).\n\nThis pack asks for the other side of the conjecture: **build the largest point set you can with\nno convex k-gon**, for `k = 6, 7, 8, 9, 10`.\n\n`points.py` exposes\n\n    build(k: int, time_budget: float, seed: int) -> list[tuple[number, number]]\n\nreturning any number of points `(x, y)`. Integer coordinates are the natural choice (any size:\nPython ints); floats are accepted too and are converted *exactly* (a float is a binary fraction),\nnever rounded. The eval refuses to verify more than `record + 16` points.\n\n## Metric\n\n    metric = mean over k in {6, 7, 8, 9, 10} of  points(k) / record(k)\n\nVerification is exact integer arithmetic. The eval scales the returned coordinates to a common\ninteger grid, checks general position with integer cross products over every triple, then runs\nthe classical dynamic programme for the largest subset in convex position (for each point as the\nbottom-most vertex, sort the rest by angle and extend convex chains by left turns; `O(N^4)` worst\ncase, about 0.6 s at `N = 128` and 10 s at `N = 256`). A set that has three collinear points or a\nconvex k-gon on any `k` fails the whole run (`wrong_answer`) rather than scoring low. The\nper-instance counts and ratios are in the eval output (`per_instance`); any `k` above its record is\nlisted under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to `build`.\n\n## Records\n\n| k | best-known points | source | proven optimal |\n|---|-------------------|--------|----------------|\n| 6 | 16 | Erdős–Szekeres (1961) construction; `ES(6) = 17` proved by Szekeres & Peters (2006, computer search) | yes |\n| 7 | 32 | Erdős–Szekeres (1961) construction; `ES(7) = 33` conjectured | no |\n| 8 | 64 | same | no |\n| 9 | 128 | same | no |\n| 10 | 256 | same | no |\n\nAlphaEvolve problem 58, \"Erdős–Szekeres Happy Ending problem\" (Georgiev, Gómez-Serrano, Tao,\nWagner, *Mathematical Exploration and Discovery at Scale*, arXiv:2511.02864, section 6.38),\nsearched for `2^(k-2) + 1` points with no convex k-gon for `k = 7` and `k = 8`, i.e. for a\ncounterexample to the conjecture. Its notebook reports 33- and 65-point sets with \"0 convex\nk-gons\", but that count came from a floating-point orientation test with a `1e-9` threshold on\ntightly clustered points; recounted with exact arithmetic (this pack's checker) each set contains\nexactly one convex k-gon. So the records stand at `2^(k-2)`, and the repository's status file lists\nproblem 58 in no category. Beating any `k >= 7` row here would disprove the Erdős–Szekeres\nconjecture: treat a ratio above 1.0 as a bug until the hub's exact re-verification agrees.\n\n## Constraints\n\n- Standard library only (`math`, `random`, `itertools`, `functools`, `collections`, `heapq`,\n  `time`). The eval rejects other imports.\n- Respect `time_budget` (seconds, per call).\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES` is a comma-separated subset of `6,7,8,9,10`; the full set is the default.\n- `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `build` per instance (default 15).\n\n```\nZT_EVAL_INSTANCES=6,7 ZT_EVAL_PER_INSTANCE_SECONDS=3 python eval.py\n```\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- **The 1961 construction scores 1.0 on every k.** Build cup–cap blocks: `f(a, b)` is a set with no\n  `a`-cap and no `b`-cup (caps and cups are chains with decreasing / increasing slopes when read\n  left to right) of size `C(a+b-4, a-2)`; `f(2, b) = f(a, 2) =` one point, and `f(a, b)` is\n  `f(a, b-1)` on the left together with `f(a-1, b)` placed far to the right and far *above* it, so\n  that every right point lies above every line through two left points and every left point lies\n  below every line through two right points. Then take `S_i = f(i+2, k-i)` for `i = 0..k-2`\n  (sizes `C(k-2, i)`, total `2^(k-2)`) and place them left to right, each block far to the right and\n  far *below* everything before it with the same two line conditions mirrored. Integer coordinates\n  with big offsets make the placement exact (about 70 bits for `k = 9`).\n- Beyond the record you are looking for a counterexample to a 90-year-old conjecture. The record\n  sets are rigid, so unstructured local search from them rarely helps; the notebook's near-misses\n  (`2^(k-2) + 1` points with a single convex k-gon) are a more interesting neighbourhood: find such\n  sets and try to break the one remaining polygon.\n- Exact incremental checking is cheap: keep the chain-length tables per pivot, or just rerun the\n  DP with early exit, which is under a millisecond at `N <= 32`.\n- Random point sets are useless: 128 random points already contain convex 23-gons.\n\nWrite one honest line in `NOTES.md`: the idea, and which `k` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for erdos-szekeres-kgon-free. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact: the coordinates the solver returns (ints, or floats, which are exact\nbinary rationals) are scaled to a common integer grid, and every orientation test is an integer\ncross product. The set must be in general position (no three collinear) and must contain no k\npoints in convex position; the eval finds the largest subset in convex position itself with the\nusual bottom-vertex / angular-sweep dynamic programme over convex chains. Environment:\n  ZT_EVAL_SEED                    seed handed to build() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated k values (default \"6,7,8,9,10\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to build() per instance (default 15)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport functools\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom fractions import Fraction\nfrom pathlib import Path\n\n# Best-known number of points in general position with no convex k-gon: the Erdos-Szekeres\n# (1961) construction gives 2^(k-2) for every k. It is optimal for k = 6 (Szekeres & Peters 2006:\n# every 17 points contain a convex hexagon) and conjectured optimal for all k (the Erdos-Szekeres\n# conjecture ES(k) = 2^(k-2) + 1); k >= 7 is open. AlphaEvolve problem 58 searched for 33- and\n# 65-point counterexamples; exact recounting of its constructions finds one convex k-gon in each.\nRECORDS = {\"6\": 16, \"7\": 32, \"8\": 64, \"9\": 128, \"10\": 256}\nPROVEN = {\"6\"}\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"6,7,8,9,10\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"15\"))\nEXTRA = 16   # verify at most record + EXTRA points (the DP is O(N^4); this keeps a k=10 run short)\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in {path.name}: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef to_integer_points(raw, k: int) -> list[tuple[int, int]]:\n    \"\"\"Exact conversion: every coordinate becomes a Fraction, then all are scaled by the common\n    denominator. Floats convert exactly (they are dyadic rationals), so nothing is rounded.\"\"\"\n    if not isinstance(raw, (list, tuple)) or not raw:\n        fail(f\"build({k}) must return a non-empty list of (x, y) points\", \"wrong_answer\")\n    if len(raw) > RECORDS[str(k)] + EXTRA:\n        fail(f\"build({k}) returned {len(raw)} points, more than record + {EXTRA}; refusing to verify\", \"wrong_answer\")\n    pts = []\n    for i, p in enumerate(raw):\n        try:\n            if len(p) != 2:\n                raise TypeError\n            x, y = p[0], p[1]\n        except Exception:\n            fail(f\"build({k}): point {i} is not an (x, y) pair: {p!r}\", \"wrong_answer\")\n        for c in (x, y):\n            if isinstance(c, bool) or not isinstance(c, (int, float, Fraction)):\n                fail(f\"build({k}): point {i} has a non-numeric coordinate {c!r}\", \"wrong_answer\")\n            if isinstance(c, float) and not math.isfinite(c):\n                fail(f\"build({k}): point {i} has a non-finite coordinate\", \"wrong_answer\")\n        pts.append((Fraction(x), Fraction(y)))\n    den = 1\n    for x, y in pts:\n        den = math.lcm(den, x.denominator, y.denominator)\n    ip = [(int(x * den), int(y * den)) for x, y in pts]\n    if len(set(ip)) != len(ip):\n        fail(f\"build({k}) returned duplicate points\", \"wrong_answer\")\n    return ip\n\n\ndef collinear_triple(P: list[tuple[int, int]]):\n    n = len(P)\n    for i in range(n):\n        ax, ay = P[i]\n        for j in range(i + 1, n):\n            dx, dy = P[j][0] - ax, P[j][1] - ay\n            for l in range(j + 1, n):\n                if dx * (P[l][1] - ay) - dy * (P[l][0] - ax) == 0:\n                    return P[i], P[j], P[l]\n    return None\n\n\ndef largest_convex_polygon(pts: list[tuple[int, int]], stop_at: int) -> int:\n    \"\"\"Exact size of the largest subset in convex position, returning early once >= stop_at.\n\n    For each point as the bottom-most vertex, the others are sorted by angle (an exact cross-product\n    order because no three points are collinear) and L[b][a] is the longest convex chain\n    pivot -> ... -> a -> b made of left turns; a chain closes into a convex polygon when the turn at\n    b back to the pivot is a left turn as well. Every convex polygon is found from its lowest vertex.\n    \"\"\"\n    P = sorted(pts, key=lambda p: (p[1], p[0]))\n    n = len(P)\n    best_overall = min(3, n)\n\n    def cmp(a, b):\n        c = a[0] * b[1] - a[1] * b[0]\n        return -1 if c > 0 else (1 if c < 0 else 0)\n\n    for i in range(n):\n        px, py = P[i]\n        Q = [(x - px, y - py) for (x, y) in P[i + 1:]]\n        M = len(Q)\n        if M < 2 or M + 1 < stop_at:\n            continue\n        Q.sort(key=functools.cmp_to_key(cmp))\n        L = [[0] * M for _ in range(M)]\n        for b in range(M):\n            bx, by = Q[b]\n            Lb = L[b]\n            for a in range(b):\n                ax, ay = Q[a]\n                dx, dy = bx - ax, by - ay\n                La = L[a]\n                best = 3\n                for c in range(a):\n                    lc = La[c]\n                    if lc + 1 > best and (ax - Q[c][0]) * dy - (ay - Q[c][1]) * dx > 0:\n                        best = lc + 1\n                Lb[a] = best\n                if best > best_overall and dy * bx - dx * by > 0:\n                    best_overall = best\n                    if best_overall >= stop_at:\n                        return best_overall\n    return best_overall\n\n\ndef verify(k: int, raw) -> int:\n    \"\"\"Exact check. Returns the number of points.\"\"\"\n    P = to_integer_points(raw, k)\n    bad = collinear_triple(P)\n    if bad is not None:\n        fail(f\"build({k}): three collinear points (scaled integer coordinates): {bad}\", \"wrong_answer\")\n    if len(P) >= k and largest_convex_polygon(P, k) >= k:\n        fail(f\"build({k}): the set contains {k} points in convex position\", \"wrong_answer\")\n    return len(P)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"points.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import points as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import points.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"build\"):\n        fail(\"points.py must define build(k, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"eskgon|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for k={label}\", \"error\")\n        k = int(label)\n        t0 = time.perf_counter()\n        try:\n            raw = cand.build(k, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"build({k}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"build({k}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        n_pts = verify(k, raw)\n        rec = RECORDS[label]\n        per_instance[label] = {\"points\": n_pts, \"record\": rec, \"proven_optimal\": label in PROVEN,\n                               \"ratio\": round(n_pts / rec, 6), \"seconds\": round(elapsed, 2)}\n        if n_pts > rec:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per_instance.values()) / len(per_instance)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per_instance, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"points.py":"\"\"\"Baseline: random greedy. Draws random integer points and keeps each one that leaves the set in\ngeneral position and free of convex k-gons. Lands well short of the 2^(k-2) records; the\nErdos-Szekeres cup/cap construction described in program.md reaches all of them.\"\"\"\n\nimport functools\nimport random\nimport time\n\n\ndef largest_convex_polygon(pts, stop_at):\n    \"\"\"Exact: size of the largest subset in convex position (early exit at stop_at).\"\"\"\n    P = sorted(pts, key=lambda p: (p[1], p[0]))\n    n = len(P)\n    best_overall = min(3, n)\n\n    def cmp(a, b):\n        c = a[0] * b[1] - a[1] * b[0]\n        return -1 if c > 0 else (1 if c < 0 else 0)\n\n    for i in range(n):\n        px, py = P[i]\n        Q = [(x - px, y - py) for (x, y) in P[i + 1:]]\n        M = len(Q)\n        if M < 2 or M + 1 < stop_at:\n            continue\n        Q.sort(key=functools.cmp_to_key(cmp))\n        L = [[0] * M for _ in range(M)]\n        for b in range(M):\n            bx, by = Q[b]\n            for a in range(b):\n                ax, ay = Q[a]\n                dx, dy = bx - ax, by - ay\n                La = L[a]\n                best = 3\n                for c in range(a):\n                    lc = La[c]\n                    if lc + 1 > best and (ax - Q[c][0]) * dy - (ay - Q[c][1]) * dx > 0:\n                        best = lc + 1\n                L[b][a] = best\n                if best > best_overall and dy * bx - dx * by > 0:\n                    best_overall = best\n                    if best_overall >= stop_at:\n                        return best_overall\n    return best_overall\n\n\ndef keeps_general_position(pts, q):\n    qx, qy = q\n    for i in range(len(pts)):\n        ax, ay = pts[i]\n        dx, dy = qx - ax, qy - ay\n        for j in range(i + 1, len(pts)):\n            if dx * (pts[j][1] - ay) - dy * (pts[j][0] - ax) == 0:\n                return False\n    return True\n\n\ndef build(k: int, time_budget: float, seed: int) -> list[tuple[int, int]]:\n    rnd = random.Random(seed)\n    t0 = time.perf_counter()\n    pts: list[tuple[int, int]] = []\n    for _ in range(300):\n        if time.perf_counter() - t0 > 0.8 * time_budget:\n            break\n        q = (rnd.randrange(1000), rnd.randrange(1000))\n        if q in pts or not keeps_general_position(pts, q):\n            continue\n        cand = pts + [q]\n        if len(cand) >= k and largest_convex_polygon(cand, k) >= k:\n            continue\n        pts = cand\n    return pts\n"}}