peel.py
Checks: FORGET: The quarantine theorem theorem.
Cited on: FORGET.
To run it: save peel.py, with ithmove.py, quarantine.py beside it; standard library only.
"""peel.py -- does a set flat for the i-th move keep a flat piece through
every maximal first move, in a world avoiding position 1?
QUESTION. The peel lemma (by hand): in a world avoiding position 1, a
set F of routes of one age to one endpoint, flat for the i-th move
(i >= 2) over the classes C it meets, has F^(f0), its routes starting
f0, flat for the i-th move and meeting every class of C, for every
first move f0 whose prime set no other first move of F strictly
contains. Proof: every first move is a unitary divisor of the endpoint;
x_q -> oo for a prime q of f0 keeps the routes whose first move holds q
(no later menu holds x_q) and sends every other route's 1/D to 0 (the
menu before q's move holds its monomial); repeat over f0's primes.
Peeling i - 1 times reaches a set sharing its first i - 1 moves, which
the quarantine theorem bars from flatness where position i is avoided:
so in a world avoiding positions 1..i no set meeting two i-th moves is
flat for the i-th move. Does every flat set the engine reaches peel, and
is none flat where 1..i are avoided?
THE ARGUMENT (by hand, the hypothesis the run reads).
(L) PEEL LEMMA. Psi_0, the start's menu, is common and dropped; x_q
= q^-beta are independent, so flat is an identity of rational
functions at every positive point. Avoiding position 1, every
menu after a first move f is prime to f: f is a unitary divisor
of the endpoint N, its primes in no later move, distinct first
moves with distinct prime sets. Fix a prime q of f0. A route with
q | f has no x_q in its D; a route without takes q at a position
k >= 2, and the menu after k - 1 moves holds that move's
monomial with coefficient 1, so its 1/D -> 0 as x_q -> oo, the
other x fixed, all coefficients being nonnegative. The limit of
S_c = S_c' is L_c = L_c', the sums over the routes of class c
with q | f, an identity in the other x. Over f0's primes in turn
what survives is the routes whose first move holds every prime of
f0: by maximality and unitarity F^(f0). It is nonempty, so its
equal class sums are positive: it meets every class of C.
(T) THEOREM. Avoiding 1..i, no F meeting two i-th moves is flat for
the i-th move at every beta. Induct on i: i = 1 is the quarantine
theorem; at i >= 2 peel f0, divide out Psi_(f0), common to
F^(f0), and read the shifted routes in the world after f0, which
avoids 1..i-1, flat for the (i-1)-th move over C: read from
state 1 with menu'(r) = menu(f0, r), the avoidance being a fact
about the moves alone.
(S) SHARP over position sets: for k < i the world W_(k, i-1) (q's to
k - 1, {b, c} at k, fresh r's to i - 1, {b, c} at i) avoids
every position but k and ties two routes whose i-th moves differ;
for k = i, W_i. So the i-th move is quarantined over every set in
every world avoiding T iff 1..i lie in T. The smallest case,
(abc, 3) in a coprime world at the last move: x_p -> oo for p of
a met class forces every first move prime to every met class, so
every route starts with the third prime and each class is one
route (all three classes met leaves no first move at all): no
such set is flat.
DESIGN. Reads (world, age, i), i >= 2, with positions 1..i-1 avoided
on every route. Sets: every whole dated fiber, and every subset of two
routes or more of a fiber of at most 8 routes, meeting two i-th moves.
Flatness by a modular reader (class sums of 1/D at 4 random points of
independent x_q modulo 2^61 - 1, a candidate re-read at 16 points
modulo 2^89 - 1, a point where a D vanishes redrawn). PEEL(F, i): for
every maximal first move f0, F^(f0) meets every class of F and is
flat; recurse on F^(f0) shifted one move, down to i = 1. A set is
NONTRIVIAL when it has two first moves or more at the top peel (a
deeper peel's two first moves are not counted).
CP (commuting phase, state menus, 3000 worlds): at a state holding
fewer than two of A = {7, 11, 13}, a random nonempty set of the A
primes prime to it; else a random nonempty subset of {2, 3, 4};
ages 3, 4, 5. Routes (7, 11, ...) and (11, 7, ...) meet one menu at
77, so flat unions over two first moves arise.
RP1, RP2 (route menus, 2000 worlds each): random menus of 1 or 2 on
U5 (the 5-smooth numbers 2..12) avoiding positions 1..I (I = 1, 2),
free after; ages 3, 4.
CONTROLS. K1 the built world menu() = {7, 11}, menu(7) = {11},
menu(11) = {7}, menu(7, 11) = menu(11, 7) = {2, 3}, {2, 3} after three
moves: (462, 4) flat for move 3, nontrivial, PEEL passes; it avoids 1
and 2, not 3. K2 the plant: the seed-{2, 3} world (menu() = {2, 3},
menu(2) = menu(3) = {5}, menu(2, 5) = menu(3, 5) = {2, 3}) at (30, 3),
i = 3, PEEL must FAIL (it avoids 2 and 3, not 1). K3 the reader equals
the exact reader (quarantine.first_move_robust on the routes shifted to
start at i) on every read set of at most 4 routes, flat and not flat
both met.
CHANGES AFTER THE FREEZE (before the engine): CP reads
i = 2..age (to 5) where the frozen design read 2..4, the reads past 4
admitted only where 1..i-1 are avoided; the arm sizes (3000, 2000,
2000 worlds) were set in the engine.
PREDICTIONS (frozen before the engine). P1 K1, K2, K3 hold. P2 KILL: 0
PEEL failures over every flat set read. P3 the kill's reach:
nontrivial flat sets above 0 in CP. P4 0 flat sets meeting two i-th
moves where every position 1..i is avoided, over reads above 0.
KILLS. P2 above 0: the lemma is false, read the specimen. P3 at 0:
nothing is verdicted.
FINDINGS.
P1 held: K1's (462, 4) at 7,11,2,3; 7,11,3,2; 11,7,2,3; 11,7,3,2 is
flat over two first moves and peels; K2's plant fails PEEL (2,5,3
and 3,5,2, each piece one class, so it shows only that PEEL can
fail, not that it reads flatness); the reader equals the exact
reader on 242717 of 242717 sets of at most 4 routes, 7738 flat.
P2 the kill missed: 0 of 7829 flat sets fail PEEL (CP 7643, RP1 99,
RP2 87).
P3 held: 1753 nontrivial flat sets at the top peel, all in CP and
all at i = 3; the random route arms reach none there (deeper
peels uncounted). In CP a whole-fiber flat union over 7 and 11
factors as (1/Psi_7) A + (1/Psi_11) B over a common suffix, a
narrow corner of the lemma.
P4 held: 0 of 151073 sets flat for the i-th move with 1..i avoided
(CP 149091, RP1 973, RP2 1009).
The lemma and the theorem it gives rest on the hand proof; the run
reads that no flat set the engine reached contradicts them.
RUN RECORD. python peel.py: 6 of 6 checks, 237.7 s, peak commit 10.6
MB.
"""
import itertools
import os
import random
import sys
import time
from collections import defaultdict
from math import gcd
import quarantine as Q
from ithmove import Reader, avoids, P1, P2
CHECKS = []
U5 = (2, 3, 4, 5, 6, 8, 9, 10, 12)
A = (7, 11, 13)
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f": {detail}" if detail
else ""))
def primes(n):
out, q = set(), 2
while q * q <= n:
while n % q == 0:
out.add(q)
n //= q
q += 1
if n > 1:
out.add(n)
return frozenset(out)
class Flat:
"""The two-stage modular reader, redrawn where a D vanishes."""
def __init__(self, seed):
self.rng = random.Random(seed)
self.r1 = Reader(self.rng, P1, 4)
self.r2 = Reader(self.rng, P2, 16)
def __call__(self, items, i):
f = self.r1.flat(items, i)
while f is None:
self.r1 = Reader(self.rng, P1, 4)
f = self.r1.flat(items, i)
if not f:
return False
f = self.r2.flat(items, i)
while f is None:
self.r2 = Reader(self.rng, P2, 16)
f = self.r2.flat(items, i)
return f
def classes(items, i):
return {r[i - 1] for r, _ in items}
def peel(items, i, flat):
"""Whether every maximal first move keeps a flat piece meeting every
class, recursively down to i = 1."""
if i == 1:
return True
cls = classes(items, i)
firsts = {r[0] for r, _ in items}
for f0 in firsts:
if any(primes(f0) < primes(g) for g in firsts):
continue
piece = [(r, ms) for r, ms in items if r[0] == f0]
if classes(piece, i) != cls or not flat(piece, i):
return False
if not peel([(r[1:], ms[1:]) for r, ms in piece], i - 1, flat):
return False
return True
def sets_of(items, i):
yield items
if len(items) <= 8:
for s in range(2, len(items)):
for sub in itertools.combinations(items, s):
yield list(sub)
def cp_world(rng):
cache = {}
def menu(prefix, n):
if n not in cache:
held = [a for a in A if n % a == 0]
pool = ([a for a in A if n % a] if len(held) < 2
else [2, 3, 4])
k = rng.randint(1, len(pool))
cache[n] = tuple(sorted(rng.sample(pool, k)))
return cache[n]
return menu
def read(name, worlds, ages, flat, t, spec):
for menu in worlds:
t["worlds"] += 1
for age in ages:
av = {k for k in range(1, age + 1) if avoids(menu, age, k)}
fib = Q.fibers(menu, age)
for i in range(2, age + 1):
if not set(range(1, i)) <= av:
continue
full = i in av
for n, items in fib.items():
if len(items) < 2:
continue
for F in sets_of(items, i):
if len(classes(F, i)) < 2:
continue
t["read"] += 1
f = flat(F, i)
if len(F) <= 4:
e = Q.first_move_robust(
[(r[i - 1:], ms) for r, ms in F])
t["K3 read"] += 1
t["K3 agree"] += e == f
t["K3 flat"] += e
if full:
t["full read"] += 1
t["full flat"] += f
if f:
spec.append((name, "FULL", i, age, n, F))
if not f:
continue
t["flat"] += 1
nontriv = len({r[0] for r, _ in F}) >= 2
t["nontrivial flat"] += nontriv
t[f"nontrivial flat i={i}"] += nontriv
if not peel(F, i, flat):
t["peel fail"] += 1
spec.append((name, "PEEL", i, age, n, F))
return t
def main():
t0 = time.time()
scale = float(os.environ.get("PEEL_SCALE", "1"))
flat = Flat(11)
print("CONTROLS")
k1 = Q.by_prefix({(): (7, 11), (7,): (11,), (11,): (7,),
(7, 11): (2, 3), (11, 7): (2, 3),
(7, 11, 2): (2, 3), (7, 11, 3): (2, 3),
(11, 7, 2): (2, 3), (11, 7, 3): (2, 3)})
it = Q.fibers(k1, 4)[462]
check("K1 the built world: (462, 4) flat for move 3 over two first "
"moves, PEEL passes; avoids 1, 2, not 3",
flat(it, 3) and len({r[0] for r, _ in it}) == 2
and peel(it, 3, flat) and avoids(k1, 4, 1) and avoids(k1, 4, 2)
and not avoids(k1, 4, 3), f"{sorted(r for r, _ in it)}")
k2 = Q.by_prefix({(): (2, 3), (2,): (5,), (3,): (5,), (2, 5): (2, 3),
(3, 5): (2, 3)})
it = Q.fibers(k2, 3)[30]
check("K2 the plant: the seed-{2, 3} world's (30, 3) is flat for move "
"3 and PEEL fails; avoids 2, 3, not 1",
flat(it, 3) and not peel(it, 3, flat) and not avoids(k2, 3, 1)
and avoids(k2, 3, 2) and avoids(k2, 3, 3),
f"{sorted(r for r, _ in it)}")
rng = random.Random(7)
spec = []
out = {}
arms = [("CP", (cp_world(rng) for _ in range(int(3000 * scale))),
(3, 4, 5))]
for name, T in (("RP1", (1,)), ("RP2", (1, 2))):
arms.append((name, (Q.random_world(
rng, U5, lambda m, n, p, T=T: all(
gcd(m, p[k - 1]) == 1 for k in T if k <= len(p)),
"prefix", (1, 2)) for _ in range(int(2000 * scale))), (3, 4)))
for name, worlds, ages in arms:
out[name] = dict(read(name, worlds, ages, flat, defaultdict(int),
spec))
print(f" {name} ({time.time() - t0:.0f} s): {out[name]}")
tot = defaultdict(int)
for d in out.values():
for k, v in d.items():
tot[k] += v
check("K3 the reader equals the exact reader on read sets of at most "
"4 routes, both verdicts met",
tot["K3 read"] > 0 and tot["K3 agree"] == tot["K3 read"]
and 0 < tot["K3 flat"] < tot["K3 read"],
f"{tot['K3 agree']} of {tot['K3 read']}, {tot['K3 flat']} flat")
for s in spec[:6]:
print(f" SPECIMEN {s[:5]}: {[r for r, _ in s[5]]}")
check("P2 KILL: no flat set fails PEEL", tot["peel fail"] == 0,
f"{tot['peel fail']} of {tot['flat']} flat sets")
check("P3 reach: nontrivial flat sets in CP",
out["CP"].get("nontrivial flat", 0) > 0,
f"CP {out['CP'].get('nontrivial flat', 0)}, all "
f"{tot['nontrivial flat']}")
check("P4 no set flat for the i-th move with 1..i avoided",
tot["full read"] > 0 and tot["full flat"] == 0,
f"{tot['full flat']} of {tot['full read']}")
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
sys.exit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()