{"id":"flat-littlewood-polynomials","name":"Flat Littlewood polynomials, extremes of |p| on the unit circle","family":"analysis","description":"AlphaEvolve problem 28: polynomials with +/-1 coefficients whose modulus on the unit circle is as flat as possible: minimise the max (C+), maximise the min (C-), or minimise the annulus width max - min (Cw), each divided by sqrt(n+1). Extremes are certified by branch and bound; scored against Odlyzko's exhaustive-search optima for n = 10, 12, 24 and his skew-symmetric best for n = 102.","metric":"record_ratio","direction":"maximize","tolerance":0.02,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["flat.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":false,"status":"active","captain":null,"parent_problem":null,"program_md":"# Flat Littlewood polynomials: keep |p| close to sqrt(n+1) on the whole circle\n\n## Problem\n\nFor `n >= 1` let `U_n` be the polynomials `p(z) = c_0 + c_1 z + ... + c_n z^n` with every\n`c_k in {+1, -1}`. Parseval gives `mean |p|^2 = n + 1` on the unit circle, so `|p| / sqrt(n+1)`\nis the natural normalisation and a perfectly flat polynomial would have it identically 1.\nLittlewood asked (1966) whether such \"ultraflat\" polynomials exist in `U_n`; the extensive\ncomputations of Odlyzko (2018) say almost certainly not, with the extreme values converging to\nabout `M = 1.27`, `m = 0.64`, `W = 0.79`. Define, over `|z| = 1`,\n\n    M(p) = max |p(z)| / sqrt(n+1),    m(p) = min |p(z)| / sqrt(n+1),    W(p) = M(p) - m(p),\n\nand the degree-`n` optima `C+(n) = min_p M(p)`, `C-(n) = max_p m(p)`, `Cw(n) = min_p W(p)`. The\nGolay-Rudin-Shapiro polynomials give `C+(2^k - 1) <= sqrt 2`; nothing else is known rigorously in\nthe limit. This is problem 28 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano,\nTao, Wagner, arXiv:2511.02864, Section 6.13); AlphaEvolve's constructions there (degrees 9 to 88)\ndo not reach the exhaustive-search optima, so this pack scores against Odlyzko's values.\n\n## Instances\n\n| label | degree `n` | quantity | direction |\n|---|---|---|---|\n| `M10` | 10 | `M` | minimise |\n| `m12` | 12 | `m` | maximise |\n| `W12` | 12 | `W` | minimise |\n| `W24` | 24 | `W` | minimise |\n| `M102` | 102 | `M` | minimise |\n\n## Solver interface\n\n`flat.py` exposes\n\n    flat(n: int, kind: str, time_budget: float, seed: int) -> list[int]\n\nwith `kind in {\"M\", \"m\", \"W\"}`, returning exactly `n + 1` coefficients, each `+1` or `-1`\n(ints; `1.0`/`-1.0` are accepted). Use `random.Random(seed)` and respect `time_budget` (seconds).\n\n## Scoring\n\nThe eval never trusts a number you report. On the circle `|p(e^{it})|^2 = T(t) = (n+1) +\n2 sum_{k>=1} r_k cos(kt)` with integer autocorrelations `r_k`, and `|T''| <= 2 sum k^2 |r_k|`\nexactly, so a branch-and-bound over `t` (sample, bound each interval by its endpoint values plus\n`B2 d^2 / 8`, discard, bisect) encloses `max T` and `min T` to a relative width of `1e-9`; an\nexplicit floating-point slack is added to every bound. Your `value` is the pessimistic end of the\nenclosure: an upper bound on `M` or `W`, a lower bound on `m`. It is therefore a certificate for\nthe polynomial you returned (and it costs well under 0.1 s even at degree 102).\n\n    metric = mean over instances of  record / value   (M, W)   or   value / record   (m)\n\n`records_beaten` lists instances whose certified value is strictly better than anything that\nrounds to the published record (see the thresholds in `eval.py`).\n\n## Records\n\n| instance | best-known value | source | proven optimal? |\n|---|---|---|---|\n| `M10` | 1.1464386126 (Odlyzko prints 1.1464) | Odlyzko 2018: \"the Barker polynomial of degree 10 has the smallest M(F) (= 1.1464) of all polynomials that have been tested\", the tests being exhaustive for all degrees <= 52; value certified by this eval on that polynomial | yes |\n| `m12` | 0.8375248131 (0.8375) | Odlyzko 2018: the Barker polynomial of degree 12 \"has the largest m(F) (= 0.8375)\", exhaustive search | yes |\n| `W12` | 0.5492256775 | same polynomial; Odlyzko prints 0.5493, which is 1.3868 - 0.8375 from rounded parts; the certified difference is 0.549226 | yes |\n| `W24` | 0.8343546947 (Odlyzko prints 0.8344) | Odlyzko 2018: \"W_24 = 0.8344\", the case where the best general polynomial beats every skew-symmetric one (0.9528) by the widest margin; exhaustive search. The polynomial `1 1 1 1 1 1 1 1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1` certifies to `M = 1.4`, `m = 0.5656453`, `W = 0.8343546947`, consistent with that figure, so the true optimum is within 5e-6 of the value used | yes |\n| `M102` | 1.2633 | Odlyzko 2018: `M*_102 = 1.2633`, the best skew-symmetric polynomial of degree 102 (optimal among skew-symmetric ones; the general search stops at degree 52) | no |\n\nThe AlphaEvolve notebook's constructions certify to `M = 1.1464386` at degree 10 and\n`m = 0.8375248` at degree 12 (the Barker polynomials), and to `M` around 1.39 to 1.41 for degrees\n78 to 88, well above Odlyzko's skew-symmetric values near 1.27.\n\n## Iteration tips\n\n- `ZT_EVAL_PER_INSTANCE_SECONDS` (default 20; the full run is about 100 s) is the `time_budget`\n  per instance; `ZT_EVAL_INSTANCES=M102` runs one instance. `ZT_EVAL_SEED` only changes `seed`.\n- Degrees 10 and 12 are exhaustively searchable in seconds (`2^11` and `2^13` sign patterns, up\n  to the symmetries `p(z) -> z^n p(1/z), -p(z), p(-z)`), degree 24 with pruning; the point of those\n  instances is a fast, exact check that your search machinery is right. `M102` is the open one.\n- Skew-symmetric polynomials (`c_{n-k} = (-1)^k c_k`, even `n`) contain the optimum in most known\n  cases and halve the search space; Odlyzko's `M*_102` came from that class.\n- Inside your search use a sampled proxy (`|p|` on `~16(n+1)` points; Bernstein's inequality\n  bounds the error) and update it incrementally per flip, as the baseline does; run the certified\n  computation only on candidates. Simulated annealing over flips and pair flips, restarted often,\n  is the standard route; a flat polynomial has small `r_k` for every lag, so high Golay merit\n  factor is a useful surrogate but not the same thing.\n\nWrite one honest line in `NOTES.md`: the idea, and which instance 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 flat-littlewood-polynomials. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns n+1 coefficients c_0..c_n in {+1, -1} of p(z) = sum c_k z^k. On |z| = 1,\n|p(e^{i t})|^2 = T(t) = (n+1) + 2 sum_{k>=1} r_k cos(k t) with integer autocorrelations\nr_k = sum_j c_j c_{j+k}. Every instance asks for one of\n\n    M = max |p| / sqrt(n+1)   (minimise),  m = min |p| / sqrt(n+1)   (maximise),  W = M - m   (minimise).\n\nThe extremes of T are certified by branch and bound: |T''| <= B2 = 2 sum k^2 |r_k| exactly, so on\nan interval of length d the function lies within B2 d^2 / 8 of the larger (smaller) endpoint\nvalue; intervals that cannot contain the extreme are discarded and the rest are bisected until\nthe enclosure is tighter than 1e-9 relative (or than the floating-point slack, whichever is\nlarger). Floating-point evaluation error is covered by an explicit slack added to every bound. The reported value is the pessimistic end of the enclosure\n(an upper bound on M and W, a lower bound on m), so it is a valid certificate for the solver's\npolynomial. Nothing reported by the solver is trusted.\n\nEnv:\n  ZT_EVAL_SEED                    seed handed to flat()\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget per instance (default 20)\n  ZT_EVAL_INSTANCES               comma-separated instance labels (default \"M10,m12,W12,W24,M102\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"20\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"M10,m12,W12,W24,M102\").split(\",\") if s.strip()]\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\nTOL = 1e-9   # relative width of the certified enclosure of the extreme of T = |p|^2\n\n# Instance label -> (degree n, quantity). Records are Odlyzko, \"Search for ultraflat polynomials\n# with plus and minus one coefficients\" (Connections in Discrete Mathematics, CUP 2018;\n# preprint on the author's page), which exhaustively searched all +/-1 polynomials of degree\n# <= 52 and skew-symmetric ones of even degree <= 104. This is AlphaEvolve problem 28 (Georgiev,\n# Gomez-Serrano, Tao, Wagner, arXiv:2511.02864, Section 6.13), where AlphaEvolve did not reach\n# the known records.\n#   M10  : M_10 = 1.1464, the Barker polynomial of degree 10, proven optimal. Exact certified\n#          value of that polynomial: 1.1464386126.\n#   m12  : m_12 = 0.8375, the Barker polynomial of degree 12, proven optimal. Exact: 0.8375248131.\n#   W12  : W_12, the Barker polynomial of degree 12, proven optimal. Odlyzko prints 0.5493\n#          (= 1.3868 - 0.8375 from rounded parts); the certified value is 0.5492256775.\n#   W24  : W_24 = 0.8344, proven optimal (quoted to four decimals; Odlyzko gives no polynomial).\n#          The polynomial 1 1 1 1 1 1 1 1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 (found by\n#          this pack's baseline) certifies to M = 1.4, m = 0.5656453056, W = 0.8343546947, which\n#          rounds to Odlyzko's figure, so W_24 lies in [0.83435, 0.8343546947]; that certified\n#          value is the record.\n#   M102 : M*_102 = 1.2633, the best skew-symmetric polynomial of degree 102 (not proven optimal\n#          over all +/-1 polynomials; quoted to four decimals).\nINSTANCES_SPEC = {\"M10\": (10, \"M\"), \"m12\": (12, \"m\"), \"W12\": (12, \"W\"), \"W24\": (24, \"W\"), \"M102\": (102, \"M\")}\nRECORDS = {\"M10\": 1.1464386126, \"m12\": 0.8375248131, \"W12\": 0.5492256775, \"W24\": 0.8343546947, \"M102\": 1.2633}\n# A four-decimal record is only certainly beaten by a value outside anything that rounds to it.\nBEAT = {\"M10\": 1.1464386126 - 1e-9, \"m12\": 0.8375248131 + 1e-9, \"W12\": 0.5492256775 - 1e-9,\n        \"W24\": 0.8343546947 - 1e-9, \"M102\": 1.26325}\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 pack.py: {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_signs(seq, n: int, label: str) -> list[int]:\n    if not isinstance(seq, (list, tuple)):\n        fail(f\"[{label}] flat() must return a list of coefficients, got {type(seq).__name__}\", \"wrong_answer\")\n    if len(seq) != n + 1:\n        fail(f\"[{label}] flat() returned {len(seq)} coefficients; degree {n} needs {n + 1}\", \"wrong_answer\")\n    out = []\n    for x in seq:\n        if isinstance(x, bool) or not isinstance(x, (int, float)) or x not in (1, -1):\n            fail(f\"[{label}] coefficient {x!r} is not +1 or -1\", \"wrong_answer\")\n        out.append(int(x))\n    return out\n\n\ndef certify(c: list[int]) -> tuple[float, float, float, float]:\n    \"\"\"Certified enclosures [lo, hi] of max T and of min T, T = |p|^2 on the unit circle.\"\"\"\n    N = len(c)\n    r = [sum(c[j] * c[j + k] for j in range(N - k)) for k in range(N)]\n    b2 = 2 * sum(k * k * abs(r[k]) for k in range(1, N))               # |T''| <= b2, exact integer\n    err = 2.0 ** -48 * (N + 1) * (N + 2 * sum(abs(x) for x in r))       # float slack on every T value\n    ks = range(1, N)\n\n    def T(t: float) -> float:\n        return N + 2 * sum(r[k] * math.cos(k * t) for k in ks)\n\n    grid = max(64, 8 * N)\n    h = 2 * math.pi / grid\n    nodes = [(i * h, T(i * h)) for i in range(grid + 1)]\n    base = [(nodes[i][0], nodes[i][1], nodes[i + 1][0], nodes[i + 1][1]) for i in range(grid)]\n\n    def search(sign: int) -> tuple[float, float]:\n        \"\"\"sign=+1 encloses max T, sign=-1 encloses min T (by maximising -T).\"\"\"\n        work = [(a, sign * av, b, sign * bv) for a, av, b, bv in base]\n        lo = max(max(av, bv) for _, av, _, bv in work) - err\n        for _level in range(64):\n            d = work[0][2] - work[0][0]\n            slack = b2 * d * d / 8 * 1.000001 + err\n            hi = max(max(av, bv) for _, av, _, bv in work) + slack\n            # the enclosure can never be narrower than the float slack on both ends\n            if hi - lo <= max(TOL * max(1.0, abs(lo)), 4 * err):\n                return lo, hi\n            keep = [iv for iv in work if max(iv[1], iv[3]) + slack > lo]\n            work = []\n            for a, av, b, bv in keep:\n                mid = 0.5 * (a + b)\n                mv = sign * T(mid)\n                lo = max(lo, mv - err)\n                work.append((a, av, mid, mv))\n                work.append((mid, mv, b, bv))\n        return lo, hi                                   # depth cap: still a valid, just wider, enclosure\n\n    max_lo, max_hi = search(+1)\n    neg_lo, neg_hi = search(-1)\n    return max_lo, max_hi, -neg_hi, -neg_lo          # max in [max_lo, max_hi], min in [min_lo, min_hi]\n\n\ndef evaluate(c: list[int], kind: str) -> float:\n    \"\"\"Pessimistic end of the certified enclosure of the requested quantity, divided by sqrt(n+1).\"\"\"\n    N = len(c)\n    max_lo, max_hi, min_lo, min_hi = certify(c)\n    s = math.sqrt(N)\n    big = math.sqrt(max(max_hi, 0.0)) / s        # certified upper bound on M\n    small = math.sqrt(max(min_lo, 0.0)) / s      # certified lower bound on m\n    return {\"M\": big, \"m\": small, \"W\": big - small}[kind]\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"flat.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import flat as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import flat.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"flat\"):\n        fail(\"flat.py must define flat(n, kind, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"flat|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for label in INSTANCES:\n        if label not in INSTANCES_SPEC:\n            fail(f\"no record for instance {label!r}\", \"error\")\n        n, kind = INSTANCES_SPEC[label]\n        t0 = time.perf_counter()\n        try:\n            seq = cand.flat(n, kind, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"[{label}] flat() raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"[{label}] flat() took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        c = to_signs(seq, n, label)\n        v = evaluate(c, kind)\n        rec = RECORDS[label]\n        ratio = v / rec if kind == \"m\" else rec / v\n        per_instance[label] = {\"n\": n, \"kind\": kind, \"value\": round(v, 10), \"record\": rec, \"ratio\": round(ratio, 8),\n                               \"seconds\": round(elapsed, 2)}\n        if (v > BEAT[label]) if kind == \"m\" else (v < BEAT[label]):\n            beaten.append(label)\n    metric = sum(r[\"ratio\"] for r in per_instance.values()) / len(per_instance)\n    print(json.dumps({\"metric\": round(metric, 8), \"per_instance\": per_instance, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"flat.py":"\"\"\"Baseline: restarted single-flip hill climbing on a sampled proxy of |p| (16(n+1) points on the\ncircle, updated incrementally per flip). Finds the proven optima at degrees 10, 12 and 24 within\nseconds and reaches M about 1.52 at degree 102 (0.83 of the record 1.2633). Beat it there.\"\"\"\n\nimport math\nimport random\nimport time\n\n\ndef flat(n: int, kind: str, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    t0 = time.perf_counter()\n    N = n + 1\n    K = 16 * N\n    Z = [[complex(math.cos(2 * math.pi * i * k / K), math.sin(2 * math.pi * i * k / K)) for i in range(K)]\n         for k in range(N)]                                                             # z_i^k\n\n    def proxy(P):\n        mags = [abs(v) for v in P]\n        if kind == \"M\":\n            return max(mags)\n        if kind == \"m\":\n            return -min(mags)\n        return max(mags) - min(mags)\n\n    best_c, best_v = None, math.inf\n    while best_c is None or time.perf_counter() - t0 < 0.9 * time_budget:\n        c = [rng.choice((1, -1)) for _ in range(N)]\n        P = [sum(c[k] * Z[k][i] for k in range(N)) for i in range(K)]\n        cur = proxy(P)\n        improved = True\n        while improved and time.perf_counter() - t0 < 0.9 * time_budget:\n            improved = False\n            for j in rng.sample(range(N), N):\n                Zj = Z[j]\n                d = -2 * c[j]\n                Q = [P[i] + d * Zj[i] for i in range(K)]\n                v = proxy(Q)\n                if v < cur:\n                    cur, P, c[j] = v, Q, -c[j]\n                    improved = True\n        if cur < best_v:\n            best_v, best_c = cur, c[:]\n    return best_c\n"}}