Second autocorrelation inequality, how flat can f*f be

# Second autocorrelation inequality: make f*f look like an indicator ## Problem Let `C` be the smallest constant such that for every non-negative `f: R -> R` ||f * f||_2^2 <= C * ||f * f||_1 * ||f * f||_inf. Equality would need `f * f` to be an indicator function, which no autoconvolution is, so the trivial bound `C <= 1` is not attained; every lower bound comes from exhibiting an `f` whose autoconvolution is nearly flat on its support. This is problem 3 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano, Tao, Wagner, "Mathematical exploration and discovery at scale", arXiv:2511.02864, Section 6.2, Problem 6.3): Matolcsi-Vinuesa had 0.88922, AlphaEvolve reached 0.8962 in May 2025, Boyer-Li 0.901564, and AlphaEvolve's final 50,000-step construction gives 0.961. `f` is a step function with `n` steps of equal width on `[-1/4, 1/4]` with heights `a_0, ..., a_{n-1} >= 0`. Then `f * f` is piecewise linear on `[-1/2, 1/2]` with node values proportional to `y = (0, b_0, ..., b_{2n-2}, 0)`, `b = a * a`, and ||f*f||_2^2 / (||f*f||_1 ||f*f||_inf) = sum_k (y_k^2 + y_k y_{k+1} + y_{k+1}^2) / (3 sum(b) max(b)). Larger is better. A constant `f` (triangle `f*f`) scores exactly 2/3. ## 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 <= 60000`. 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 evaluates the formula above as an exact rational. That rational, rounded to a double, is your `value`. metric = value / record (instance "c2"; there is only one instance) `records_beaten` lists the instance when `value > record + 1e-9`. ## Records | instance | best-known value | source | proven optimal? | |---|---|---|---| | `c2` | 0.9610210777840241 (lower bound on `C`) | AlphaEvolve, arXiv:2511.02864 Section 6.2 ("C >= 0.961 using a step function consisting of 50,000 parts"); the value is that construction from the repository notebook evaluated by this eval's exact arithmetic. Earlier: 0.901564 Boyer-Li (arXiv:2506.16750), 0.8962 AlphaEvolve May 2025, 0.88922 Matolcsi-Vinuesa 2009 | no, the only upper bound is the trivial 1 | Note: the AlphaEvolve problem page and its status file still list 0.8962 (May 2025) as the AlphaEvolve figure and mark Boyer-Li as the record; the paper and the notebook give the later 0.961 construction, which is what is verified here. ## 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 `c2` exists). `ZT_EVAL_SEED` only changes `seed`; the held-out verification seed is different, so do not tune to one seed. - Exact verification of 60 000 steps takes about two seconds; the cap keeps the eval inside its timeout. The record construction uses 50 000 steps, but it is 82 % zeros: 9 074 non-zero heights in a few dense runs, with `f*f` above 0.9 of its peak on a third of its support. - The objective is scale-free, smooth away from ties in `max(b)`, and cheap to update incrementally: changing one height changes `b` on a window (see the baseline). Gradient ascent on the ratio with the `max` replaced by a soft-max, then a final exact evaluation, is the standard route. - Think about the shape: you want `f*f` to rise steeply, stay flat, and fall steeply. Sums of narrow spikes with non-overlapping pairwise sums score exactly 2/3, so density matters; the best constructions are dense combs with slowly varying envelopes. - Grow `n` gradually: refine a good short sequence by splitting each step in two, then re-optimise. 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.