{"id":"erdos-discrepancy","name":"Erdős discrepancy: longest ±1 sequence of bounded discrepancy","family":"number-theory","description":"AlphaEvolve Problem 40: find the longest ±1 sequence whose homogeneous-progression sums a_d + a_2d + ... + a_kd all stay within ±C. Four instances (C = 2, 3; unrestricted and completely multiplicative), scored against the SAT-solver records of Konev and Lisitsa.","metric":"record_ratio","direction":"maximize","tolerance":0.1,"eval_timeout_seconds":240,"agent_timeout_seconds":1800,"mutable":["signs.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Erdős discrepancy: longest ±1 sequence of bounded discrepancy\n\n## Goal\n\nThe discrepancy of a sign pattern `a_1, ..., a_N` in {−1, +1} is the largest `|a_d + a_2d + ... + a_kd|`\nover all homogeneous progressions `d, 2d, ..., kd` with `kd ≤ N`. For a bound `C`, how long can a\nsequence be while keeping its discrepancy at most `C`? Tao proved (2015) that every infinite sequence\nhas unbounded discrepancy, so the answer is finite, and the exact values are a SAT-solver frontier:\n`C = 1` gives 11, `C = 2` gives 1160 (Konev–Lisitsa 2014), and for `C = 3` the longest known\nsequence has 130,000 terms with no proof that it is maximal.\n\nThis is AlphaEvolve Problem 40 (Section 6.23 of arXiv:2511.02864). Unaided, AlphaEvolve reached\nlength 200 for `C = 2`; with Tao's hint to try multiplicative sequences it reached 380, still far\nfrom 1160. Beat that.\n\n`signs.py` exposes\n\n    signs(C: int, completely_multiplicative: bool, time_budget: float, seed: int) -> list[int]\n\nreturning a list of Python ints, each `1` or `-1`; entry `i` of the list is `a_(i+1)` (the list is\n0-indexed, the sequence is 1-indexed). When `completely_multiplicative` is true the sequence must\nalso satisfy `a_(mn) = a_m * a_n` for all `m, n` (so `a_1 = 1`). Instances:\n\n| label | C | class | record length |\n|---|---|---|---|\n| `d2`  | 2 | any ±1 sequence            | 1160    |\n| `d3`  | 3 | any ±1 sequence            | 130000  |\n| `cm2` | 2 | completely multiplicative  | 246     |\n| `cm3` | 3 | completely multiplicative  | 127645  |\n\n## Metric\n\nThe eval does not require the whole returned list to be valid: it computes `L`, the length of the\nlongest *prefix* that has discrepancy at most `C` (and, for the `cm` instances, is completely\nmultiplicative), exactly, in `O(L log L)`. Only the first `2 × record` entries are examined, so a\nratio is capped at 2.0.\n\n    metric = mean over instances of  L(instance) / record(instance)\n\n1.0 means matching every record; anything above 1.0 on `d3` is a new lower bound for the\ndiscrepancy-3 length and gets flagged in `records_beaten`. `d2`, `cm2` and `cm3` are proven\nmaximal, so the best you can do there is 1.0. Entries that are not the ints `1` or `-1` fail the\nrun (`wrong_answer`); an empty list scores 0 for that instance.\n\n## Records\n\n| label | record | source | status |\n|---|---|---|---|\n| `d2`  | 1160   | Konev & Lisitsa, \"A SAT attack on the Erdős discrepancy conjecture\", arXiv:1402.2184 (2014); OEIS A237695 | proven maximal: no discrepancy-2 sequence of length 1161 exists |\n| `d3`  | 130000 | Konev & Lisitsa, \"Computer-aided proof of Erdős discrepancy properties\", Artificial Intelligence 224 (2015), arXiv:1405.3097, Table 1 and Section 5 (a 130,000-term sequence whose first 127,600 terms are completely multiplicative) | open; best known |\n| `cm2` | 246    | Polymath5 (2011), as recorded in Konev–Lisitsa 2015, Table 1 | proven maximal |\n| `cm3` | 127645 | Konev & Lisitsa 2015 (arXiv:1405.3097): SAT certificate that length 127,646 is unsatisfiable | proven maximal |\n\nFor reference, the maximal *multiplicative* (not completely) lengths are 344 for `C = 2` and\n127,645 for `C = 3` (same paper); they are not scored here.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over.\n- Deterministic given `seed`: use `random.Random(seed)`.\n- Keep memory sane: the eval only looks at the first `2 × record` entries anyway.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=d2,cm2` restricts the eval to a subset of labels (default `d2,d3,cm2,cm3`).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget (default 25; the full eval\n  takes about 90 s).\n- `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Depth-first search with backtracking on the partial sums for every `d` is the natural engine;\n  the baseline does exactly that, randomly. Everything better comes from ordering and pruning.\n- Multiplicative structure (Tao's hint): decide `a_p` for primes only and extend\n  multiplicatively; the search space collapses and the 246 / 127,645 records are of this kind.\n  Modified Dirichlet characters (e.g. `χ_3` with `a_3 = +1`) have discrepancy growing like `log N`\n  and are excellent seeds.\n- The 1160 record is *not* multiplicative, but Konev and Lisitsa found the 130,000 sequence by\n  forcing complete multiplicativity on a long prefix and letting the tail float free. A hybrid\n  (multiplicative skeleton, local repairs) is the obvious pure-Python analogue.\n- Symmetry: `a_2n = -a_n`-type constraints and sign flips of the whole sequence are cheap\n  reductions.\n\nWrite one honest line in `NOTES.md`: the idea, and which instance it helped.\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 erdos-discrepancy. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to signs()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per instance (default 25)\n  ZT_EVAL_INSTANCES              comma-separated instance labels (default \"d2,d3,cm2,cm3\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"25\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"d2,d3,cm2,cm3\").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\n# label -> (C, completely multiplicative?, best-known length). Sources and status in program.md:\n# d2 1160 and cm3 127645 are proven maximal (Konev-Lisitsa), cm2 246 is proven maximal (Polymath5),\n# d3 130000 is the longest known unrestricted discrepancy-3 sequence (Konev-Lisitsa 2015).\nRECORDS = {\n    \"d2\": (2, False, 1160),\n    \"d3\": (3, False, 130000),\n    \"cm2\": (2, True, 246),\n    \"cm3\": (3, True, 127645),\n}\nCAP_FACTOR = 2  # only the first CAP_FACTOR * record entries of a returned list are examined\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 valid_prefix(seq: list[int], c: int, cm: bool) -> int:\n    \"\"\"Length of the longest prefix with discrepancy <= c (and completely multiplicative if cm).\"\"\"\n    best = len(seq)\n    # discrepancy: for each d walk the multiples until the running sum leaves [-c, c]\n    d = 1\n    while d <= best:\n        s = 0\n        for pos in range(d, best + 1, d):\n            s += seq[pos - 1]\n            if s > c or s < -c:\n                best = pos - 1\n                break\n        d += 1\n    if cm and best >= 1:\n        if seq[0] != 1:\n            return 0\n        a = 2\n        while a * a <= best:\n            b = a\n            while a * b <= best:\n                if seq[a * b - 1] != seq[a - 1] * seq[b - 1]:\n                    best = a * b - 1\n                    break\n                b += 1\n            a += 1\n    return best\n\n\ndef validate(label: str, out, cap: int) -> list[int]:\n    if not isinstance(out, (list, tuple)):\n        fail(f\"signs({label}) must return a list of 1/-1 ints, got {type(out).__name__}\", \"wrong_answer\")\n    seq = []\n    for x in out[:cap]:\n        if type(x) is not int or x not in (1, -1):\n            fail(f\"signs({label}) returned a non-sign entry {x!r}\", \"wrong_answer\")\n        seq.append(x)\n    return seq\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"signs.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import signs as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import signs.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"signs\"):\n        fail(\"signs.py must define signs(C, completely_multiplicative, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"edp|{SEED}\").getrandbits(32)\n    per, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for instance {label!r} (known: {sorted(RECORDS)})\", \"error\")\n        c, cm, record = RECORDS[label]\n        t0 = time.perf_counter()\n        try:\n            out = cand.signs(c, cm, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"signs({label}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"signs({label}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        seq = validate(label, out, CAP_FACTOR * record)\n        length = valid_prefix(seq, c, cm)\n        per[label] = {\"C\": c, \"completely_multiplicative\": cm, \"length\": length, \"returned\": len(out),\n                      \"record\": record, \"ratio\": round(length / record, 6), \"seconds\": round(elapsed, 2)}\n        if length > record:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per.values()) / len(per)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"signs.py":"\"\"\"Baseline: randomised depth-first search with backtracking on the progression sums. Beat it.\n\nFor the completely multiplicative instances only primes are decision points; composites are forced.\n\"\"\"\n\nimport random\nimport time\n\n\ndef signs(C: int, completely_multiplicative: bool, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.9 * time_budget\n    limit = 2500 if C <= 2 else 12000  # far beyond what this search reaches\n\n    spf = list(range(limit + 1))  # smallest prime factor\n    for i in range(2, int(limit ** 0.5) + 1):\n        if spf[i] == i:\n            for j in range(i * i, limit + 1, i):\n                if spf[j] == j:\n                    spf[j] = i\n    divs = [[] for _ in range(limit + 1)]\n    for d in range(1, limit + 1):\n        for m in range(d, limit + 1, d):\n            divs[m].append(d)\n\n    best: list[int] = []\n    while time.perf_counter() < deadline and len(best) < limit:\n        seq, sums, stack = [], [0] * (limit + 1), []\n        backtracks = steps = 0\n        while backtracks < 4000:\n            steps += 1\n            if steps & 63 == 0 and time.perf_counter() > deadline:\n                break\n            n = len(seq) + 1\n            if n > limit:\n                break\n            if completely_multiplicative:\n                if n == 1:\n                    cands = [1]\n                elif spf[n] == n:\n                    cands = [1, -1]\n                else:\n                    p = spf[n]\n                    cands = [seq[p - 1] * seq[n // p - 1]]\n            else:\n                cands = [1, -1]\n            ok = [x for x in cands if all(-C <= sums[d] + x <= C for d in divs[n])]\n            if len(ok) == 2 and rng.random() < 0.5:\n                ok.reverse()\n            if ok:\n                x = ok.pop()\n                seq.append(x)\n                for d in divs[n]:\n                    sums[d] += x\n                stack.append(ok)\n                if len(seq) > len(best):\n                    best = seq[:]\n                continue\n            # dead end: unwind to the last position that still has an untried sign\n            backtracks += 1\n            while stack and not stack[-1]:\n                x = seq.pop()\n                for d in divs[len(seq) + 1]:\n                    sums[d] -= x\n                stack.pop()\n            if not stack:\n                break\n            alts = stack.pop()\n            x = seq.pop()\n            m = len(seq) + 1\n            for d in divs[m]:\n                sums[d] -= x\n            x = alts.pop()\n            seq.append(x)\n            for d in divs[m]:\n                sums[d] += x\n            stack.append(alts)\n    return best\n"}}