{"id":"autocorrelation-sidon-upper","name":"First autocorrelation inequality, upper bound for the Sidon constant","family":"analysis","description":"AlphaEvolve problem 2: a non-negative step function on [-1/4, 1/4] whose autoconvolution peak is as small as possible relative to its mass, giving an upper bound on the largest constant C with max f*f >= C (int f)^2. Scored exactly against the best-known bound 1.5029.","metric":"record_ratio","direction":"maximize","tolerance":0.02,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["construct.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":"# First autocorrelation inequality: push the Sidon constant's upper bound down\n\n## Problem\n\nLet `C` be the largest constant such that for every non-negative `f: R -> R`\n\n    max_{-1/2 <= t <= 1/2} (f * f)(t)  >=  C * ( int_{-1/4}^{1/4} f(x) dx )^2,\n\nwhere `(f * f)(t) = int f(t - x) f(x) dx`. The constant matters in additive combinatorics (the size\nof Sidon sets). It is known that `1.2748 <= C <= 1.5029`; every upper bound comes from exhibiting\na good `f`. This is problem 2 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano,\nTao, Wagner, \"Mathematical exploration and discovery at scale\", arXiv:2511.02864, Section 6.2),\nwhere AlphaEvolve lowered Matolcsi-Vinuesa's 1.50992 to 1.5053 and then 1.5032.\n\nFollowing Matolcsi-Vinuesa (2010), `f` is a step function with `n` steps of equal width on\n`[-1/4, 1/4]`, given by its heights `a_0, ..., a_{n-1} >= 0`. For such `f`\n\n    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),\n\nso the whole problem is: find non-negative heights whose discrete autoconvolution has the smallest\npeak relative to the squared sum. Smaller is better.\n\n## Solver interface\n\n`construct.py` exposes\n\n    construct(time_budget: float, seed: int) -> list[float]\n\nreturning the heights (ints or floats, non-negative, finite, not all zero), `1 <= n <= 20000`.\nLonger lists fail the run. Use `random.Random(seed)` for any randomness and respect\n`time_budget` (seconds).\n\n## Scoring\n\nThe eval never trusts a number you report. It rescales your heights so the largest is `2^60`,\nrounds each one DOWN to an integer (a relative change below `2^-60` per step, so the rounded list\nis itself a valid step function), squares the packed integer to get the exact autoconvolution, and\ncomputes `2 n max(b) / sum(a)^2` as an exact rational. That rational, rounded to a double, is\nyour `value`.\n\n    metric = record / value            (instance \"c1\"; there is only one instance)\n\n`records_beaten` lists the instance when `value < 1.50285`, i.e. below anything that rounds to\nthe published 1.5029.\n\n## Records\n\n| instance | best-known value | source | proven optimal? |\n|---|---|---|---|\n| `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 |\n\n## Iteration tips\n\n- `ZT_EVAL_PER_INSTANCE_SECONDS` (default 90) is the `time_budget` handed to `construct()`; set\n  it to 5 while iterating. `ZT_EVAL_INSTANCES` selects instances by label (only `c1` exists).\n  `ZT_EVAL_SEED` only changes `seed`; the held-out verification seed is different, so do not tune\n  to one seed.\n- Exact verification of 20 000 steps takes well under a second; the cap exists so the eval always\n  fits its timeout, not because long sequences are discouraged. AlphaEvolve's constructions have\n  600 to 5000 steps.\n- The Matolcsi-Vinuesa recipe: given the current `a`, solve the LP \"maximise `sum g` subject to\n  `g >= 0` and `(a * g)_k <= max(a * a)` for all `k`\" and move a little from `a` toward `g`. A\n  simplex on 2n constraints in the standard library is feasible for n in the hundreds; AlphaEvolve\n  added a cubic backtracking line search and momentum on top of that step, then annealed\n  perturbations to escape local optima.\n- The objective is scale-free and its sub-gradient is explicit: only the indices where `b` attains\n  its max matter. Coordinate descent that lowers the current peak(s) while raising the sum is\n  cheap with an incrementally updated `b` (see the baseline).\n- Grow `n` gradually: refine a good short sequence by splitting each step in two, then re-optimise.\n  Sparse, comb-like tails (many exact zeros) appear in the best known constructions.\n\nWrite one honest line in `NOTES.md`: the idea, and what value it reached.\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 autocorrelation-sidon-upper. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns the heights of a non-negative step function with n equal steps on [-1/4, 1/4].\nThe score is  2 n max_k b_k / (sum_i a_i)^2  where b = a * a (discrete autoconvolution), which\nis exactly max f*f / (int f)^2 for that step function (Matolcsi-Vinuesa 2010). Smaller is better;\nthe metric is record / score.\n\nEvery height is rescaled so the largest is 2^60 and rounded DOWN to an integer (a relative change\nof at most 2^-60 per step, which is itself a valid step function), then the autoconvolution and\nthe score are computed in exact integer / rational arithmetic. Nothing reported by the solver is\ntrusted.\n\nEnv:\n  ZT_EVAL_SEED                    seed handed to construct()\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget per instance (default 90)\n  ZT_EVAL_INSTANCES               comma-separated instance labels (default \"c1\"; that is the only one)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom fractions import Fraction\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"90\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"c1\").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\nN_MAX = 20000   # steps; exact verification of 20000 steps takes about half a second\nQ = 60          # heights are rounded down to multiples of max(a) / 2^Q\n\n# Best-known upper bound for the constant, per instance. \"c1\" is the single instance: the\n# constant C of  max_{|t|<=1/2} f*f(t) >= C (int_{-1/4}^{1/4} f)^2  over non-negative f.\n# History (AlphaEvolve repository of problems, problem 2): 1.50992 Matolcsi-Vinuesa 2009;\n# 1.5053 and 1.5032 AlphaEvolve (Georgiev, Gomez-Serrano, Tao, Wagner, arXiv:2511.02864, Section\n# 6.2; the 1.5032 construction has 1319 steps and evaluates to 1.5031635547 in this eval's exact\n# arithmetic); 1.5029 Yuksekgonul et al., Jan 2026 (quoted to four decimals on that page).\n# Not proven optimal: the best lower bound is 1.2748. Update when a hub-verified submission wins.\nRECORDS = {\"c1\": 1.5029}\n# The published record is rounded to 4 decimals, so only a value below anything that rounds to\n# 1.5029 is a certain improvement.\nBEAT_BELOW = {\"c1\": 1.50285}\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_integers(seq, label: str) -> list[int]:\n    \"\"\"Validate the heights and return them rescaled to max 2^Q and rounded down (exact).\"\"\"\n    if not isinstance(seq, (list, tuple)):\n        fail(f\"construct() must return a list of heights, got {type(seq).__name__}\", \"wrong_answer\")\n    n = len(seq)\n    if n == 0 or n > N_MAX:\n        fail(f\"[{label}] construct() returned {n} heights; need 1 <= n <= {N_MAX}\", \"wrong_answer\")\n    vals = []\n    for x in seq:\n        if isinstance(x, bool) or not isinstance(x, (int, float)):\n            fail(f\"[{label}] height {x!r} is not an int or float\", \"wrong_answer\")\n        if isinstance(x, float) and not math.isfinite(x):\n            fail(f\"[{label}] height {x!r} is not finite\", \"wrong_answer\")\n        if x < 0:\n            fail(f\"[{label}] height {x!r} is negative\", \"wrong_answer\")\n        vals.append(Fraction(x))\n    m = max(vals)\n    if m == 0:\n        fail(f\"[{label}] all heights are zero\", \"wrong_answer\")\n    top = Fraction(1 << Q)\n    return [int((x * top) // m) for x in vals]\n\n\ndef autoconvolve(q: list[int]) -> list[int]:\n    \"\"\"Exact self-convolution of non-negative integers: pack into one big integer and square.\"\"\"\n    n = len(q)\n    slot_bits = 2 * max(q).bit_length() + n.bit_length() + 1\n    width = (slot_bits + 7) // 8\n    big = int.from_bytes(b\"\".join(x.to_bytes(width, \"little\") for x in q), \"little\")\n    raw = (big * big).to_bytes(width * 2 * n, \"little\")\n    return [int.from_bytes(raw[k * width:(k + 1) * width], \"little\") for k in range(2 * n - 1)]\n\n\ndef score(q: list[int]) -> Fraction:\n    n = len(q)\n    s = sum(q)\n    return Fraction(2 * n * max(autoconvolve(q)), s * s)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"construct.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import construct as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import construct.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"construct\"):\n        fail(\"construct.py must define construct(time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"sidon|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for instance {label!r}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            seq = cand.construct(BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"[{label}] construct() raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"[{label}] construct() took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        q = to_integers(seq, label)\n        value = score(q)\n        v = float(value)\n        per_instance[label] = {\"value\": round(v, 12), \"record\": RECORDS[label], \"ratio\": round(RECORDS[label] / v, 8),\n                               \"n\": len(q), \"seconds\": round(elapsed, 2)}\n        if value < Fraction(str(BEAT_BELOW[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":{"construct.py":"\"\"\"Baseline: annealed hill climbing on 40 equal steps, restarted every second from a perturbed\nbest, with an incrementally updated autoconvolution. Reaches a peak ratio near 1.65 to 1.70\n(about 0.9 of the record 1.5029). Beat it.\"\"\"\n\nimport random\nimport time\n\nN = 40\nEPOCH = 1.0   # seconds per restart\n\n\ndef autoconvolve(a: list[float]) -> list[float]:\n    b = [0.0] * (2 * N - 1)\n    for i in range(N):\n        ai = a[i]\n        if ai:\n            for j in range(N):\n                b[i + j] += ai * a[j]\n    return b\n\n\ndef construct(time_budget: float, seed: int) -> list[float]:\n    rng = random.Random(seed)\n    t0 = time.perf_counter()\n    total = 0.9 * time_budget\n    best_a = [1.0] * N\n    best = 2 * N * max(autoconvolve(best_a)) / float(sum(best_a)) ** 2\n    first = True\n    while time.perf_counter() - t0 < total:\n        a = best_a[:] if first else [x * (1 + rng.uniform(-0.3, 0.3)) for x in best_a]\n        first = False\n        b = autoconvolve(a)                   # b = a * a, kept up to date below\n        s = float(sum(a))\n        cur = 2 * N * max(b) / (s * s)\n        epoch = min(EPOCH, total)\n        te = time.perf_counter()\n        while True:\n            frac = (time.perf_counter() - te) / epoch\n            if frac >= 1 or time.perf_counter() - t0 >= total:\n                break\n            step = 0.02 + 0.5 * (1 - frac)    # anneal the move size within the epoch\n            i = rng.randrange(N)\n            new = max(0.0, a[i] + rng.uniform(-step, step))\n            d = new - a[i]\n            if d == 0.0 or s + d <= 1e-9:\n                continue\n            # a -> a + d e_i changes b[i+j] by 2 d a_j for j != i and b[2i] by 2 d a_i + d^2\n            for j in range(N):\n                b[i + j] += 2 * d * a[j]\n            b[2 * i] += d * d\n            a[i] = new\n            s += d\n            v = 2 * N * max(b) / (s * s)\n            if v < cur:\n                cur = v\n                if v < best:\n                    best, best_a = v, a[:]\n            else:                             # undo\n                a[i] -= d\n                s -= d\n                for j in range(N):\n                    b[i + j] -= 2 * d * a[j]\n                b[2 * i] -= d * d\n    return best_a\n"}}