Erdős discrepancy: longest ±1 sequence of bounded discrepancy

# Erdős discrepancy: longest ±1 sequence of bounded discrepancy ## Goal The discrepancy of a sign pattern `a_1, ..., a_N` in {−1, +1} is the largest `|a_d + a_2d + ... + a_kd|` over all homogeneous progressions `d, 2d, ..., kd` with `kd ≤ N`. For a bound `C`, how long can a sequence be while keeping its discrepancy at most `C`? Tao proved (2015) that every infinite sequence has unbounded discrepancy, so the answer is finite, and the exact values are a SAT-solver frontier: `C = 1` gives 11, `C = 2` gives 1160 (Konev–Lisitsa 2014), and for `C = 3` the longest known sequence has 130,000 terms with no proof that it is maximal. This is AlphaEvolve Problem 40 (Section 6.23 of arXiv:2511.02864). Unaided, AlphaEvolve reached length 200 for `C = 2`; with Tao's hint to try multiplicative sequences it reached 380, still far from 1160. Beat that. `signs.py` exposes signs(C: int, completely_multiplicative: bool, time_budget: float, seed: int) -> list[int] returning a list of Python ints, each `1` or `-1`; entry `i` of the list is `a_(i+1)` (the list is 0-indexed, the sequence is 1-indexed). When `completely_multiplicative` is true the sequence must also satisfy `a_(mn) = a_m * a_n` for all `m, n` (so `a_1 = 1`). Instances: | label | C | class | record length | |---|---|---|---| | `d2` | 2 | any ±1 sequence | 1160 | | `d3` | 3 | any ±1 sequence | 130000 | | `cm2` | 2 | completely multiplicative | 246 | | `cm3` | 3 | completely multiplicative | 127645 | ## Metric The eval does not require the whole returned list to be valid: it computes `L`, the length of the longest *prefix* that has discrepancy at most `C` (and, for the `cm` instances, is completely multiplicative), exactly, in `O(L log L)`. Only the first `2 × record` entries are examined, so a ratio is capped at 2.0. metric = mean over instances of L(instance) / record(instance) 1.0 means matching every record; anything above 1.0 on `d3` is a new lower bound for the discrepancy-3 length and gets flagged in `records_beaten`. `d2`, `cm2` and `cm3` are proven maximal, so the best you can do there is 1.0. Entries that are not the ints `1` or `-1` fail the run (`wrong_answer`); an empty list scores 0 for that instance. ## Records | label | record | source | status | |---|---|---|---| | `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 | | `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 | | `cm2` | 246 | Polymath5 (2011), as recorded in Konev–Lisitsa 2015, Table 1 | proven maximal | | `cm3` | 127645 | Konev & Lisitsa 2015 (arXiv:1405.3097): SAT certificate that length 127,646 is unsatisfiable | proven maximal | For reference, the maximal *multiplicative* (not completely) lengths are 344 for `C = 2` and 127,645 for `C = 3` (same paper); they are not scored here. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. - Keep memory sane: the eval only looks at the first `2 × record` entries anyway. ## Iterating - `ZT_EVAL_INSTANCES=d2,cm2` restricts the eval to a subset of labels (default `d2,d3,cm2,cm3`). - `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget (default 25; the full eval takes about 90 s). - `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed. ## Ideas that are known to matter (check the journal before repeating one) - Depth-first search with backtracking on the partial sums for every `d` is the natural engine; the baseline does exactly that, randomly. Everything better comes from ordering and pruning. - Multiplicative structure (Tao's hint): decide `a_p` for primes only and extend multiplicatively; the search space collapses and the 246 / 127,645 records are of this kind. Modified Dirichlet characters (e.g. `χ_3` with `a_3 = +1`) have discrepancy growing like `log N` and are excellent seeds. - The 1160 record is *not* multiplicative, but Konev and Lisitsa found the 130,000 sequence by forcing complete multiplicativity on a long prefix and letting the tail float free. A hybrid (multiplicative skeleton, local repairs) is the obvious pure-Python analogue. - Symmetry: `a_2n = -a_n`-type constraints and sign flips of the whole sequence are cheap reductions. Write one honest line in `NOTES.md`: the idea, and which instance it helped. 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.