{"id":"autocorrelation-indicator-lower","name":"Second autocorrelation inequality, how flat can f*f be","family":"analysis","description":"AlphaEvolve problem 3: a non-negative step function on [-1/4, 1/4] whose autoconvolution is as close to an indicator as possible, measured by ||f*f||_2^2 / (||f*f||_1 ||f*f||_inf). Scored exactly against AlphaEvolve's 50,000-step construction (0.96102).","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":"# Second autocorrelation inequality: make f*f look like an indicator\n\n## Problem\n\nLet `C` be the smallest constant such that for every non-negative `f: R -> R`\n\n    ||f * f||_2^2  <=  C * ||f * f||_1 * ||f * f||_inf.\n\nEquality would need `f * f` to be an indicator function, which no autoconvolution is, so the\ntrivial bound `C <= 1` is not attained; every lower bound comes from exhibiting an `f` whose\nautoconvolution is nearly flat on its support. This is problem 3 of the AlphaEvolve repository of\nproblems (Georgiev, Gomez-Serrano, Tao, Wagner, \"Mathematical exploration and discovery at scale\",\narXiv:2511.02864, Section 6.2, Problem 6.3): Matolcsi-Vinuesa had 0.88922, AlphaEvolve reached\n0.8962 in May 2025, Boyer-Li 0.901564, and AlphaEvolve's final 50,000-step construction gives\n0.961.\n\n`f` is a step function with `n` steps of equal width on `[-1/4, 1/4]` with heights\n`a_0, ..., a_{n-1} >= 0`. Then `f * f` is piecewise linear on `[-1/2, 1/2]` with node values\nproportional to `y = (0, b_0, ..., b_{2n-2}, 0)`, `b = a * a`, and\n\n    ||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)).\n\nLarger is better. A constant `f` (triangle `f*f`) scores exactly 2/3.\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 <= 60000`.\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\nevaluates the formula above as an exact rational. That rational, rounded to a double, is your\n`value`.\n\n    metric = value / record            (instance \"c2\"; there is only one instance)\n\n`records_beaten` lists the instance when `value > record + 1e-9`.\n\n## Records\n\n| instance | best-known value | source | proven optimal? |\n|---|---|---|---|\n| `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 |\n\nNote: the AlphaEvolve problem page and its status file still list 0.8962 (May 2025) as the\nAlphaEvolve figure and mark Boyer-Li as the record; the paper and the notebook give the later\n0.961 construction, which is what is verified here.\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 `c2` 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 60 000 steps takes about two seconds; the cap keeps the eval inside its\n  timeout. The record construction uses 50 000 steps, but it is 82 % zeros: 9 074 non-zero heights\n  in a few dense runs, with `f*f` above 0.9 of its peak on a third of its support.\n- The objective is scale-free, smooth away from ties in `max(b)`, and cheap to update\n  incrementally: changing one height changes `b` on a window (see the baseline). Gradient ascent on\n  the ratio with the `max` replaced by a soft-max, then a final exact evaluation, is the standard\n  route.\n- Think about the shape: you want `f*f` to rise steeply, stay flat, and fall steeply. Sums of\n  narrow spikes with non-overlapping pairwise sums score exactly 2/3, so density matters; the best\n  constructions are dense combs with slowly varying envelopes.\n- Grow `n` gradually: refine a good short sequence by splitting each step in two, then re-optimise.\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-indicator-lower. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns the heights a_0..a_{n-1} of a non-negative step function f with n equal steps on\n[-1/4, 1/4]. Then f*f is piecewise linear on [-1/2, 1/2] with node values (0, b_0, ..., b_{2n-2}, 0)\nup to a common factor, where b = a * a, so\n\n    ||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)),\n    y = (0, b, 0).\n\nLarger is better (the trivial upper bound is 1); the metric is score / record.\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 \"c2\"; 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\", \"c2\").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 = 60000   # steps; exact verification of 60000 steps takes about two seconds\nQ = 60          # heights are rounded down to multiples of max(a) / 2^Q\n\n# Best-known lower bound for the constant, per instance. \"c2\" is the single instance: the\n# constant C of  ||f*f||_2^2 <= C ||f*f||_1 ||f*f||_inf  over non-negative f.\n# History (AlphaEvolve repository of problems, problem 3): 0.88922 Matolcsi-Vinuesa 2009; 0.8962\n# AlphaEvolve May 2025; 0.901564 Boyer-Li (arXiv:2506.16750); 0.961 AlphaEvolve with a 50,000-step\n# function (Georgiev, Gomez-Serrano, Tao, Wagner, arXiv:2511.02864, Section 6.2, Problem 6.3).\n# The value below is that 50,000-step construction evaluated by this file's exact arithmetic.\n# Not proven optimal: the only known upper bound is the trivial 1.\nRECORDS = {\"c2\": 0.9610210777840241}\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    b = autoconvolve(q)\n    y = [0] + b + [0]\n    num = sum(y[k] * y[k] + y[k] * y[k + 1] + y[k + 1] * y[k + 1] for k in range(len(y) - 1))\n    return Fraction(num, 3 * sum(b) * max(b))\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\"indicator|{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(v / RECORDS[label], 8),\n                               \"n\": len(q), \"seconds\": round(elapsed, 2)}\n        if value > Fraction(RECORDS[label]) + Fraction(1, 10 ** 9):\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. A constant f scores 2/3; this reaches about\n0.80 (roughly 0.83 of the record). 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 ratio(b: list[float]) -> float:\n    num = 0.0\n    prev = 0.0\n    for v in b:\n        num += prev * prev + prev * v + v * v\n        prev = v\n    num += prev * prev\n    return num / (3 * sum(b) * max(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 = ratio(autoconvolve(best_a))\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        cur = ratio(b)\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 sum(a) + 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            v = ratio(b)\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                for j in range(N):\n                    b[i + j] -= 2 * d * a[j]\n                b[2 * i] -= d * d\n    return best_a\n"}}