Flat Littlewood polynomials, extremes of |p| on the unit circle

# Flat Littlewood polynomials: keep |p| close to sqrt(n+1) on the whole circle ## Problem For `n >= 1` let `U_n` be the polynomials `p(z) = c_0 + c_1 z + ... + c_n z^n` with every `c_k in {+1, -1}`. Parseval gives `mean |p|^2 = n + 1` on the unit circle, so `|p| / sqrt(n+1)` is the natural normalisation and a perfectly flat polynomial would have it identically 1. Littlewood asked (1966) whether such "ultraflat" polynomials exist in `U_n`; the extensive computations of Odlyzko (2018) say almost certainly not, with the extreme values converging to about `M = 1.27`, `m = 0.64`, `W = 0.79`. Define, over `|z| = 1`, M(p) = max |p(z)| / sqrt(n+1), m(p) = min |p(z)| / sqrt(n+1), W(p) = M(p) - m(p), and the degree-`n` optima `C+(n) = min_p M(p)`, `C-(n) = max_p m(p)`, `Cw(n) = min_p W(p)`. The Golay-Rudin-Shapiro polynomials give `C+(2^k - 1) <= sqrt 2`; nothing else is known rigorously in the limit. This is problem 28 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano, Tao, Wagner, arXiv:2511.02864, Section 6.13); AlphaEvolve's constructions there (degrees 9 to 88) do not reach the exhaustive-search optima, so this pack scores against Odlyzko's values. ## Instances | label | degree `n` | quantity | direction | |---|---|---|---| | `M10` | 10 | `M` | minimise | | `m12` | 12 | `m` | maximise | | `W12` | 12 | `W` | minimise | | `W24` | 24 | `W` | minimise | | `M102` | 102 | `M` | minimise | ## Solver interface `flat.py` exposes flat(n: int, kind: str, time_budget: float, seed: int) -> list[int] with `kind in {"M", "m", "W"}`, returning exactly `n + 1` coefficients, each `+1` or `-1` (ints; `1.0`/`-1.0` are accepted). Use `random.Random(seed)` and respect `time_budget` (seconds). ## Scoring The eval never trusts a number you report. On the circle `|p(e^{it})|^2 = T(t) = (n+1) + 2 sum_{k>=1} r_k cos(kt)` with integer autocorrelations `r_k`, and `|T''| <= 2 sum k^2 |r_k|` exactly, so a branch-and-bound over `t` (sample, bound each interval by its endpoint values plus `B2 d^2 / 8`, discard, bisect) encloses `max T` and `min T` to a relative width of `1e-9`; an explicit floating-point slack is added to every bound. Your `value` is the pessimistic end of the enclosure: an upper bound on `M` or `W`, a lower bound on `m`. It is therefore a certificate for the polynomial you returned (and it costs well under 0.1 s even at degree 102). metric = mean over instances of record / value (M, W) or value / record (m) `records_beaten` lists instances whose certified value is strictly better than anything that rounds to the published record (see the thresholds in `eval.py`). ## Records | instance | best-known value | source | proven optimal? | |---|---|---|---| | `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 | | `m12` | 0.8375248131 (0.8375) | Odlyzko 2018: the Barker polynomial of degree 12 "has the largest m(F) (= 0.8375)", exhaustive search | yes | | `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 | | `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 | | `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 | The AlphaEvolve notebook's constructions certify to `M = 1.1464386` at degree 10 and `m = 0.8375248` at degree 12 (the Barker polynomials), and to `M` around 1.39 to 1.41 for degrees 78 to 88, well above Odlyzko's skew-symmetric values near 1.27. ## Iteration tips - `ZT_EVAL_PER_INSTANCE_SECONDS` (default 20; the full run is about 100 s) is the `time_budget` per instance; `ZT_EVAL_INSTANCES=M102` runs one instance. `ZT_EVAL_SEED` only changes `seed`. - Degrees 10 and 12 are exhaustively searchable in seconds (`2^11` and `2^13` sign patterns, up to the symmetries `p(z) -> z^n p(1/z), -p(z), p(-z)`), degree 24 with pruning; the point of those instances is a fast, exact check that your search machinery is right. `M102` is the open one. - Skew-symmetric polynomials (`c_{n-k} = (-1)^k c_k`, even `n`) contain the optimum in most known cases and halve the search space; Odlyzko's `M*_102` came from that class. - Inside your search use a sampled proxy (`|p|` on `~16(n+1)` points; Bernstein's inequality bounds the error) and update it incrementally per flip, as the baseline does; run the certified computation only on candidates. Simulated annealing over flips and pair flips, restarted often, is the standard route; a flat polynomial has small `r_k` for every lag, so high Golay merit factor is a useful surrogate but not the same thing. Write one honest line in `NOTES.md`: the idea, and which instance 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.