First autocorrelation inequality, upper bound for the Sidon constant

# First autocorrelation inequality: push the Sidon constant's upper bound down ## Problem Let `C` be the largest constant such that for every non-negative `f: R -> R` max_{-1/2 <= t <= 1/2} (f * f)(t) >= C * ( int_{-1/4}^{1/4} f(x) dx )^2, where `(f * f)(t) = int f(t - x) f(x) dx`. The constant matters in additive combinatorics (the size of Sidon sets). It is known that `1.2748 <= C <= 1.5029`; every upper bound comes from exhibiting a good `f`. This is problem 2 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano, Tao, Wagner, "Mathematical exploration and discovery at scale", arXiv:2511.02864, Section 6.2), where AlphaEvolve lowered Matolcsi-Vinuesa's 1.50992 to 1.5053 and then 1.5032. Following Matolcsi-Vinuesa (2010), `f` is a step function with `n` steps of equal width on `[-1/4, 1/4]`, given by its heights `a_0, ..., a_{n-1} >= 0`. For such `f` max f*f / (int f)^2 = 2 n * max_k b_k / (sum_i a_i)^2, b = a * a (b_k = sum_{i+j=k} a_i a_j), so the whole problem is: find non-negative heights whose discrete autoconvolution has the smallest peak relative to the squared sum. Smaller is better. ## Solver interface `construct.py` exposes construct(time_budget: float, seed: int) -> list[float] returning the heights (ints or floats, non-negative, finite, not all zero), `1 <= n <= 20000`. Longer lists fail the run. Use `random.Random(seed)` for any randomness and respect `time_budget` (seconds). ## Scoring The eval never trusts a number you report. It rescales your heights so the largest is `2^60`, rounds each one DOWN to an integer (a relative change below `2^-60` per step, so the rounded list is itself a valid step function), squares the packed integer to get the exact autoconvolution, and computes `2 n max(b) / sum(a)^2` as an exact rational. That rational, rounded to a double, is your `value`. metric = record / value (instance "c1"; there is only one instance) `records_beaten` lists the instance when `value < 1.50285`, i.e. below anything that rounds to the published 1.5029. ## Records | instance | best-known value | source | proven optimal? | |---|---|---|---| | `c1` | 1.5029 (upper bound on `C`) | Yuksekgonul et al., Jan 2026, as listed on the AlphaEvolve problem 2 page; previous: 1.5032 AlphaEvolve (arXiv:2511.02864 Section 6.2, 1319-step construction in the repository notebook, exact value 1.5031635547 in this eval), 1.5053 AlphaEvolve May 2025, 1.50992 Matolcsi-Vinuesa 2009 | no, the best lower bound is 1.2748 | ## Iteration tips - `ZT_EVAL_PER_INSTANCE_SECONDS` (default 90) is the `time_budget` handed to `construct()`; set it to 5 while iterating. `ZT_EVAL_INSTANCES` selects instances by label (only `c1` exists). `ZT_EVAL_SEED` only changes `seed`; the held-out verification seed is different, so do not tune to one seed. - Exact verification of 20 000 steps takes well under a second; the cap exists so the eval always fits its timeout, not because long sequences are discouraged. AlphaEvolve's constructions have 600 to 5000 steps. - The Matolcsi-Vinuesa recipe: given the current `a`, solve the LP "maximise `sum g` subject to `g >= 0` and `(a * g)_k <= max(a * a)` for all `k`" and move a little from `a` toward `g`. A simplex on 2n constraints in the standard library is feasible for n in the hundreds; AlphaEvolve added a cubic backtracking line search and momentum on top of that step, then annealed perturbations to escape local optima. - The objective is scale-free and its sub-gradient is explicit: only the indices where `b` attains its max matter. Coordinate descent that lowers the current peak(s) while raising the sum is cheap with an incrementally updated `b` (see the baseline). - Grow `n` gradually: refine a good short sequence by splitting each step in two, then re-optimise. Sparse, comb-like tails (many exact zeros) appear in the best known constructions. Write one honest line in `NOTES.md`: the idea, and what value it reached. 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.