sprawl.py
Checks: GROWTH: The sprawl over F₂[x] theorem; observation; GROWTH: The sibling shadow theorem.
Cited on: GROWTH.
To run it: save sprawl.py, with growth.py beside it; standard library only.
"""sprawl.py -- the dynamics demand over F_2[x]: why it never locks, why it
opens at most one place of each degree, and the walk from the void in
closed form.
QUESTION. Over Z the greedy dynamics walk locks onto one prime
(growth.py); at a place of mixed characteristic a tick of lambda costs
a constant p^(ef), and in equal characteristic the tick price is
unbounded (module_law.py). What does the walk do over F_2[x], and what
does its support look like?
THE OBJECT. States are nonzero polynomials N over F_2 (all monic),
encoded as integers with bit i the coefficient of x^i, so 2 = x,
3 = x + 1, 7 = x^2 + x + 1, and the integer order is degree first,
then lexicographic from the top: the ENCODING ORDER, the canonical
reading of "the least m". lambda(N) is the exponent of
(F_2[x]/N)^x; at an irreducible g of degree d, lambda(g^a) =
(2^d - 1) 2^(ceil log2 a) (growth.py, checked there against the unit
group), and lambda(N) is the lcm over the prime powers of N. The walk
takes m >= 2 least in the encoding order with lambda(Nm) > lambda(N).
Write c = v_2(lambda) and lambda_odd for the odd part.
THE ARGUMENT (written before the engine).
(1) THE DOOR MENU. If m raises lambda, some prime power g^r of m
raises it alone; g^r divides m, so it has degree <= deg m and is
smaller in the encoding unless m = g^r. So every pick is a prime
power, and at g (degree d, a = v_g(N)) the least raising power
is: DEEPENING (a >= 1) r = 2^c + 1 - a, since the 2-part must
pass 2^c and (2^d - 1) already divides lambda, and a <= 2^c
because lambda carries 2^(ceil log2 a); OPENING AT EXPONENT 1 (a = 0,
(2^d - 1) not dividing lambda_odd) r = 1; CLOCKED OPENING (a = 0,
(2^d - 1) dividing lambda_odd) r = 2^c + 1. A deepening or a
clocked opening raises c by exactly one and leaves lambda_odd; an
opening at exponent 1 leaves c. Once c >= 1 the openings at
exponent 1 are the ghosts here, read as over a number ring with the
residue characteristic 2 in q's place: 2 divides lambda and
2^d - 1 does not, and the place lands at depth 1, where its door
is 2^c, so it seats no lock.
(2) THE SIBLING SHADOW. Once some place g of degree d is seated,
(2^d - 1) divides lambda, so every other place h of degree d is
clocked, its least move of degree d(2^c + 1), while g's own
deepening has degree d(2^c + 1 - a) with a >= 1: strictly less. So no
sibling of a seated place is ever picked, under any tie-break
among moves of one degree: the walk opens at most one place of
each degree, and none at a degree the seed already seats. Its
support holds at most one of the roughly 2^d/d places of each
degree d beyond the seed's, a set of density zero, so the fate
called BREADTH (every place seated) never occurs.
(3) THE SPRAWL. An opening at exponent 1 always exists: at the least d
with (2^d - 1) not dividing lambda_odd, which is at most
bit_length(lambda_odd) + 1. Suppose the openings stop. Then
lambda_odd is fixed, so that opening's degree is fixed, while
every move raises c by one. A column's depth is at most its seed
depth or 2^(c' - 1) + 1, c' the clock at its last pick, so once
2^(c - 1) passes every seed depth each deepening has degree >=
2^(c - 1) and each clocked opening more: the other moves outgrow
the opening at exponent 1, a contradiction. So openings at
exponent 1 recur forever under any tie-break, no place is ever the
whole tail, and a legal move always exists. Over F_q[x] the
argument should transfer on E(a) = p^(ceil log_p a)
(module_law.py); it is not run here.
(4) THE VOID IN CLOSED FORM. From N = 1 the walk opens x at exponent 2
(clocked, c = 0: the tie at degree 2 with x^2 + x + 1 goes to
x^2), then deepens x with x and x^2, reaching x^5, c = 3. After
that, by induction, x sits at 2^j + 1 with c = j + 1 and its least
move has degree 2^j, and the FRONTIER d, the least degree with
(2^d - 1) not dividing lambda_odd, has every degree 2..d-1 opened
at exponent 1, one place each. The frontier advances by exactly
one per opening at exponent 1: by Zsigmondy's theorem 2^n - 1 has
a prime factor dividing no 2^k - 1 with k < n, for every n >= 2
but 6, and at n = 6 the factor 9 of 63 divides none of 3, 7, 15,
31. While x's least move has degree 2^j the frontier lies in
[2^(j-1), 2^j], so the opening at exponent 1 is strictly cheaper
until the frontier reaches 2^j. Every other move is dominated by
x's least move: x + 1 is clocked at degree 2^c + 1 = 2^(j+1) + 1;
a clocked place of degree d' >= 2 costs d'(2^c + 1); a place
opened at exponent 1 deepens at degree d 2^c. So the walk is: x^2,
x, x^2, then for d = 2, 3, 4, ... the least irreducible of degree
d, preceded at every d = 2^j >= 4 by x^d, which wins that degree's
tie as the least monic of its degree. x + 1 never enters: the
sibling shadow at degree 1.
DESIGN. Standard library only; one process; the F_2[x] arithmetic and
lambda imported from growth.py. States are carried as factorizations,
never multiplied out, and irreducibility is Rabin's test.
C POSITIVE CONTROL, before any verdict: the menu of (1) against a
scan of every m in the encoding order, lambda(Nm) computed by
factoring N m, along each seed's walk (the void's included) for
at most 12 moves, ending at the first state where
deg N + deg(pick) > 18 or deg(pick) > 9.
S the census: the void and every monic of degree 1 to 5 (63 seeds),
60 moves each, under two tie-breaks at the least degree, the least
encoding and the greatest. Per trajectory: openings at exponent 1,
the count of other moves against c_final - c_seed, and the sibling
shadow (no opening at a degree already seated).
V the void, 60 moves, against the closed form of (4); the first
11 picks; x's depth; the frontier; x + 1 absent.
PREDICTIONS, fixed before the run (the census figures are those of the
script this one replaces).
C the menu equals the scan at every state checked.
S every trajectory under both tie-breaks: other moves = c_final -
c_seed <= 12, openings at exponent 1 >= 48 of 60, no opening at a
seated degree.
V the walk equals the closed form at all 60 moves; the first 11
picks are 4, 2, 4, 7, 11, 16, 19, 37, 67, 131, 256; x's depth
ends at 65; the frontier reaches 54; x + 1 never picked.
A KILL is any printed disagreement in C, in the sibling-shadow or
other-move counts of S, or in V: each refutes a step of the argument.
The bound on openings at exponent 1 in S is an observation.
FINDINGS. Every prediction landed: 11/11 checks PASS.
C Rabin's test agrees with factoring at every polynomial of degree
<= 10; the menu's pick is the least raising m of the encoding
scan at 318 states, 0 off.
S 63 seeds x 60 moves under the least-encoding tie-break: 3386
openings at exponent 1, 379 deepenings, 15 clocked openings; under
the greatest: 3400, 377 and 3. On both, every trajectory's count of
other moves equals c_final - c_seed, no opening lands at a degree
already seated, the fewest openings at exponent 1 is 53 of 60 and
the most other moves 7.
V the void's 60 picks equal the closed form of (4); the first 11 are
4, 2, 4, 7, 11, 16, 19, 37, 67, 131, 256; x ends at depth 65 (depth
moves at degrees 4, 8, 16, 32); the openings at exponent 1 are one
irreducible of each degree 2..54; x + 1 never enters.
Tiers: the door menu, the sibling shadow, the sprawl and the void's
closed form are theorems, each proved in the argument above and
verified in the ranges printed.
RUN RECORD. 11/11, 0.8 s wall, 8.4 MB peak commit under a memory guard. The
first run printed 10/11: the positive control found the menu off at 6 of
315 states, because it fixed the least degree before adding the clocked
openings and so dropped a clocked opening cheaper than the door-1
opening (seeds 19, 25 and 31, lambda = 15: the scan picks x^2 at degree
2, the menu took the opening at exponent 1 of degree 3). The fix
recomputes the least degree after the clocked openings; the S and V
lines printed the same figures before and after, since a trajectory's
count of other moves is c_final - c_seed along either path and the void
never meets the case.
"""
from growth import (lcm, v2, pdeg, pmul, pdivmod, ppow, pfactor,
lam_f2_pp)
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def section(title):
print()
print("=" * 72)
print(title)
print("=" * 72)
# ------------------------------------------------------ F_2[x], any degree
def pmod(a, m):
return pdivmod(a, m)[1]
def pgcd(a, b):
while b:
a, b = b, pmod(a, b)
return a
def prime_factors(n):
out, d = [], 2
while d * d <= n:
if n % d == 0:
out.append(d)
while n % d == 0:
n //= d
d += 1
if n > 1:
out.append(n)
return out
def is_irr(f):
"""Rabin's test: f of degree n is irreducible iff x^(2^n) = x mod f
and gcd(x^(2^(n/l)) - x, f) = 1 for every prime l | n."""
n = pdeg(f)
if n == 1:
return True
pw = [2]
for _ in range(n):
pw.append(pmod(pmul(pw[-1], pw[-1]), f))
if pw[n] != 2:
return False
return all(pgcd(pw[n // l] ^ 2, f) == 1 for l in prime_factors(n))
EXTREME = {}
def extreme_irr(d, greatest):
"""The least (or greatest) irreducible of degree d in the encoding."""
if (d, greatest) not in EXTREME:
f = (1 << (d + 1)) - 1 if greatest else 1 << d
while not is_irr(f):
f += -1 if greatest else 1
EXTREME[(d, greatest)] = f
return EXTREME[(d, greatest)]
ALL = {}
def irr_of_degree(d):
if d not in ALL:
ALL[d] = [f for f in range(1 << d, 1 << (d + 1)) if is_irr(f)]
return ALL[d]
# ------------------------------------------------------------- the walk
def lam(st):
L = 1
for g, a in st.items():
L = lcm(L, lam_f2_pp(pdeg(g), a))
return L
def menu(st, greatest=False):
"""Every least move of (1) at the least degree; returns the pick."""
L = lam(st)
c = v2(L)
odd = L >> c
cands = []
for g, a in st.items():
assert a <= 1 << c, "a column deeper than the clock allows"
cands.append((pdeg(g) * ((1 << c) + 1 - a), g, (1 << c) + 1 - a,
"deepen"))
d0 = 1
while odd % ((1 << d0) - 1) == 0:
d0 += 1
g0 = extreme_irr(d0, greatest)
assert g0 not in st, "a seated place of the exponent-1 degree"
cands.append((d0, g0, 1, "at 1"))
best = min(t[0] for t in cands)
d = 1
while d * ((1 << c) + 1) <= best:
if odd % ((1 << d) - 1) == 0:
for g in irr_of_degree(d):
if g not in st:
cands.append((d * ((1 << c) + 1), g, (1 << c) + 1,
"clocked"))
d += 1
best = min(t[0] for t in cands)
low = [t for t in cands if t[0] == best]
pick = (max if greatest else min)(low, key=lambda t: ppow(t[1], t[2]))
return pick
def walk(seed, T, greatest=False):
st = dict(seed)
log = []
for _ in range(T):
deg, g, r, kd = menu(st, greatest)
seated = {pdeg(h) for h in st}
log.append((g, r, deg, kd, v2(lam(st)), pdeg(g) in seated
and kd != "deepen"))
st[g] = st.get(g, 0) + r
return log, st
def state_poly(st):
N = 1
for g, a in st.items():
N = pmul(N, ppow(g, a))
return N
def lam_poly(f):
L = 1
for g, a in pfactor(f).items():
L = lcm(L, lam_f2_pp(pdeg(g), a))
return L
def brute_pick(N, stop):
"""The least m >= 2 in the encoding with lambda(Nm) > lambda(N)."""
L = lam_poly(N)
for m in range(2, stop + 1):
if lam_poly(pmul(N, m)) != L:
return m
return None
# ------------------------------------------------------------- sections
SEEDS = [{}] + [pfactor(f) for f in range(2, 64)]
def section_control():
section("C POSITIVE CONTROL: the menu against the encoding scan")
irr_ok = all(is_irr(f) == (len(pfactor(f)) == 1
and list(pfactor(f).values()) == [1])
for f in range(2, 1 << 11))
check("C0 Rabin's test agrees with factoring at every polynomial of "
"degree <= 10", irr_ok)
tested = bad = 0
for seed in SEEDS:
st = dict(seed)
for _ in range(12):
deg, g, r, kd = menu(st)
N = state_poly(st)
if pdeg(N) + deg > 18 or deg > 9:
break
move = ppow(g, r)
tested += 1
bad += brute_pick(N, move) != move
st[g] = st.get(g, 0) + r
check("C1 the menu's pick = the least raising m in the encoding, "
"deg N + deg m <= 18", bad == 0, f"{tested} states, {bad} off")
def section_s():
section("S THE SPRAWL and THE SIBLING SHADOW: 63 seeds x 60 moves")
for greatest in (False, True):
name = "greatest" if greatest else "least"
fresh_min, nonfresh_bad, shadow_bad, nonfresh_max = 60, 0, 0, 0
kinds = {}
for seed in SEEDS:
log, st = walk(seed, 60, greatest)
c0, c1 = v2(lam(seed)), v2(lam(st))
nf = sum(mv[3] != "at 1" for mv in log)
nonfresh_bad += nf != c1 - c0
nonfresh_max = max(nonfresh_max, nf)
fresh_min = min(fresh_min, 60 - nf)
shadow_bad += sum(mv[5] for mv in log)
for mv in log:
kinds[mv[3]] = kinds.get(mv[3], 0) + 1
print(f" tie-break {name}: kinds {kinds}; fewest openings at "
f"exponent 1 {fresh_min}; most other moves {nonfresh_max}")
check(f"S1 ({name}) other moves = c_final - c_seed on every "
f"trajectory", nonfresh_bad == 0, f"{nonfresh_bad} off")
check(f"S2 ({name}) no opening at a degree already seated (the "
f"menu's openings at exponent 1 avoid them by construction; "
f"the clocked ones are tested)",
shadow_bad == 0, f"{shadow_bad} openings")
check(f"S3 ({name}) at least 48 openings at exponent 1 of 60, at "
f"most 12 other moves", fresh_min >= 48 and nonfresh_max <= 12)
def closed_form(T):
out, d = [4, 2, 4], 2
while len(out) < T:
if d >= 4 and d & (d - 1) == 0:
out.append(1 << d)
out.append(extreme_irr(d, False))
d += 1
return out[:T]
def section_v():
section("V THE VOID: 60 moves against the closed form")
log, st = walk({}, 60)
picks = [ppow(g, r) for (g, r, deg, kd, c, sh) in log]
print(" first 11 picks:", picks[:11])
fresh_degs = [pdeg(g) for (g, r, deg, kd, c, sh) in log if kd == "at 1"]
print(f" x's depth {st.get(2)}; degrees opened at exponent 1 "
f"{fresh_degs[0]}.."
f"{fresh_degs[-1]}; x + 1 seated: {3 in st}")
check("V1 the walk equals the closed form at all 60 moves",
picks == closed_form(60))
check("V1 the first 11 picks are 4, 2, 4, 7, 11, 16, 19, 37, 67, 131, "
"256", picks[:11] == [4, 2, 4, 7, 11, 16, 19, 37, 67, 131, 256])
check("V1 x ends at depth 65, the degrees opened at exponent 1 run "
"2..54 one each, "
"x + 1 never enters", st.get(2) == 65
and fresh_degs == list(range(2, 55)) and 3 not in st)
def main():
section_control()
section_s()
section_v()
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()