image.py
Checks: IMAGE: The colour count theorem; IMAGE: A quadratic ring's ideal image is 2^t rule; IMAGE: The lock's rider erases a choice rule; IMAGE: A curve's image is the continuum rule; IMAGE: The gap rule; IMAGE: Greed's point rule.
Cited on: IMAGE.
To run it: save image.py, with element.py, element_ring.py, limit.py, module_law.py beside it; standard library only.
"""image.py -- the set of limits a greedy growth walk reaches when its
ties are all followed: a union of orbits of the colour-preserving
permutations, a finite count over an imaginary quadratic ring where
the walk locks, the continuum over a curve over F_2 with a rational
place besides the one removed (the ideal world at limit.py's corner),
and the lock's rider as what erases a choice rather than what adds
one.
QUESTION. limit.py and element.py follow ONE greedy walk to its limit.
Wherever two least moves cost the same, a tie-break picks one, and a
different pick can reach a different limit. The GREEDY IMAGE of a seed s
is the set of limits of every branch from s, every tie followed. How big
is it, what decides its size, and which of a ring's features reach it?
Three worlds are on the table: Z, where the least move is unique; the
imaginary quadratic rings Z[sqrt(-5)] and the maximal order of
Q(sqrt(-23)), where walks lock; and the rings of five curves over F_2 and
F_2[x], where walks sprawl. And one question carried in from the
element world: at Q(sqrt(-23)) the lock (2) = P2 P2' carries its rider,
both places over 2 running away with a gap the seed chose. Does that
rider move the count?
THE OBJECTS. A place's COLOUR is what the dynamics reads of it: over a
curve its degree in the ideal world and its (degree, class) in the
element world (element.py); over a number ring its norm and local kind
in the ideal world, and those with its class in the element world
(element_ring.py). sigma(omega) counts the places of colour omega. A
LIMIT gives every place an exponent in {0, 1, 2, ...} or infinity; a
lock sends its vehicle's support to infinity and freezes the rest. The SHAPE of a state
or a limit forgets which place of a colour carries which exponent: per
colour, the multiset of exponents. G is the group of permutations of the
places preserving colour; G_s its subgroup fixing the seed s, which is G
for the void. The RIDER REACH is the union of the supports of the
minimal riders MINREP(c) over the classes c.
THE ARGUMENT (written before the engine).
(1) THE COLOUR COUNT. Everything a menu reads is a function of the
colours and the exponents: lambda of a state is an lcm of place
contributions read off (degree, exponent), or (norm, kind,
exponent) over a number ring; a door is the least r with
lambda_P(a + r) not dividing L; a price is d r, or N^r, plus the
rider m(-r c); a rider is a least divisor of its class, and a
permutation keeping degree or norm and class sends it to a least
divisor of the same class, so with every least vehicle on the menu
the menu is carried to the menu (on the curves and the two
quadratic rings run here each class has one least divisor,
element.py; over Q(sqrt(-15)) the class of the places over 2 has
two). So
for pi in G, menu(pi s) = pi menu(s), the branch tree from pi s is
the image of the tree from s, and the limit map commutes with pi.
Im(s) is therefore a union of G_s-orbits, and the orbit of a
limit X has size
|G_s X| = prod over refined colours c' of
sigma(c')! / prod_k n(c', k)!,
a colour refined by the seed's exponent, n(c', k) the places of c'
at exponent k in X. So
|Im(s)| = sum over the limit SHAPES reached of that product:
the walk is run only to find the shapes, and the supply prices
every orbit. The product over a trajectory's openings of the tie
multiplicity is the case of one shape with every opened colour
carrying one item at exponent 1. A count of TRAJECTORIES is not a
count of limits: the limit forgets the order of seating and the
finite exponents at the places it sends to infinity.
(2) WHY THE COLOURING IS EXACTLY RIGHT. element.py proves no coarser
colouring than (degree, class) prices every menu, and (1) proves
that colouring enough to count. So a multinomial over DEGREES
alone overcounts the element world's image wherever a class is
read, and a price reading anything finer than a colour breaks (1).
(3) OVER Z the doors at distinct primes are powers of distinct
primes and never tie (growth.py), so every branch is the one walk
and the image is a point.
(4) AN IMAGINARY QUADRATIC RING, IDEAL WORLD. A door costs N(P)^r, a
power of P's rational prime, so equal costs lie over one rational
prime, which carries two places only when it splits: every tie is
a conjugate pair, one colour of sigma = 2. Conjugates share a
ladder: with K the least depth whose lambda does not divide L,
once P is seated at depth a >= 1 the unseated conjugate P' has
door K against P's K - a, so P' is strictly dearer at every later
state and is never seated (STARVATION). On
every seed run the walk locks onto one place within 60 moves,
read as 20 repeated tie-free moves (growth.py leaves the lock
open in general), so there a trajectory makes finitely
many ties t, the same t on every branch by (1), and the
two members of each tie stand at the limit at different exponents,
one of them 0. So the image is ONE orbit, of size exactly 2^t.
Over a field of degree n every tie lies over one rational prime,
which carries at most n places, so a tie there is at most n wide.
(5) THE SAME RINGS, ELEMENT WORLD. At Z[sqrt(-5)], h = 2, every class
is its own inverse, so conjugates share a colour and (4)'s single
orbit of 2^t should stand; its lock (2) is the ramified place over
2 squared and carries no rider. At Q(sqrt(-23)), h = 3, conjugates
carry inverse classes, so a tie is between two colours of
sigma = 1: every multinomial is 1 and the image is a count of
SHAPES. There the lock (2) = P2 P2' sends both places over 2 to
infinity, so two branches that differ only in which of the two
stands deeper are two states and ONE limit: the lock's rider
ERASES a choice, it does not add one. Predicted: every erasure is
two branches differing only on the lock vehicle's support, and
only a lock whose vehicle carries a rider can erase; the inert
(5) lock and the ramified (2) lock of Z[sqrt(-5)] erase nothing.
(6) A CURVE OVER F_2, IDEAL WORLD, at limit.py's corner, the curve
holding a rational place besides the one removed. The limit of
every branch is infinity at one runaway C of degree 1 or 2 and one
place at exponent 1 at each opened degree, every supplied degree
above 1 opening (limit.py). So the limit shapes are two, C of
degree 1 and, where the void menu ties, C of degree 2, and
|Im| = sigma(1) prod_(d >= 2) sigma(d)
+ sigma(2) prod_(d >= 3) sigma(d),
each product over the supplied degrees (sigma(d) > 0), the second
term present iff sigma(2) > 0. Each product has
infinitely many factors >= 2, so each shape's orbit is already the
continuum, and its points are choice functions on the degrees.
(7) THE SAME CURVES, ELEMENT WORLD. Past the transient an opening at
degree d takes a principal core and pays no rider (element.py),
so it chooses one of the sigma(d, 0) principal places of degree
d. A declined one is never seated later: as a core it is clocked
at d (T + 1) against its seated sibling's d T, both of class 0
and so riderless; as a rider it is impossible, a rider place being
alone in its colour while (d, 0) holds two or more. So every
opened colour outside the rider reach carries one place at
exponent 1 (or the runaway) and the rest at 0 in every limit, and
contributes sigma(d, 0) to its orbit. Openings never stop, the
recurrent price doubling while an opening costs its degree. The
image is the continuum wherever sigma(d, 0) >= 2 at all but
finitely many degrees, so that the infinitely many opened degrees
meet it infinitely often, which element.py reads at every supplied degree
above the principal-free ones to degree 400. The rider reach is
finite, so the places a rider can bring back after they were
declined are finitely many.
(8) THE GAP. Over the three families, under the scopes below, the
image is a point, a finite number, or the continuum, and never
countably infinite: over Z by
(3), over the quadratic rings wherever the walk locks, as on every
seed run, because the lock ends the ties, over
the curves (at limit.py's corner, a rational place besides the
one removed)
because one shape's orbit is already the continuum.
Erasure needs a lock, a lock ends the openings, and a rider can
re-seat only the finitely many places of its reach (finitely many
classes, finitely many least divisors each), so neither
way of losing a choice can happen at endlessly many openings.
TRANSPLANTS, marked. From an earlier record of the same two number
rings: at Z[sqrt(-5)]'s norm-40 ideal belt t = 0, 1, 2 at 35, 15, 2
seeds of 52, and t = 0, 1 at 65, 14 of 79 at Q(sqrt(-23)); in the
element world two erasures at Q(sqrt(-23)), at the seeds (2) and (2)^2.
From the same record over the curves: the first ten openings' product
at about 1.8e11 over F_2[x].
PREDICTIONS, frozen before the engine, each naming what the run PRINTS.
IP1 THE COLOUR COUNT, BRUTE. Printed per ring and world (the ideal world
over F_2[x], h2 and g2; the element world over h2, h3 and g2),
from the void and depth by depth: labelled states reached by an
engine over the actual places with lambda read exactly, grouped by
shape, against the shapes the walker reading colours alone
(limit.py's corner, element.py's element world) reaches, with each
group's size against its product of multinomials. KILL: one shape in one
set and not the other, or one group off its product.
IP2 THE COLOURING IS EXACTLY RIGHT. Printed: the same labelled states
grouped by DEGREE alone in the element world, the degree
multinomial against the group sizes. KILL of (2): no group off at
h3 or g2. And a price reading one place's label in the ideal world
over F_2[x]: the groups against the multinomials. KILL of the
control: no group off.
IP3 THE CURVE CORNER. Printed per ring: the runaway degrees over every
branch of limit.py's corner walk, against the two shapes of (6),
and log10 of each shape's product over its first ten openings.
KILL: a runaway degree outside {1, 2}, or 2 at a ring with
sigma(2) = 0, or 1 missing.
IP4 THE CURVES' ELEMENT IMAGE. Printed per ring over element.py's
branches (every tie followed over the first moves, each walked to
300): the rider reach's size, the openings past the transient and
the least sigma(d, 0) any of them chose from, the opened colours
inside the rider reach, and at every branch's end whether every
opened colour outside the reach holds exactly one seated place.
KILL: an opening past the transient at a colour with
sigma(d, 0) < 2, or an opened colour outside the reach holding a
second seated place.
IP5 THE QUADRATIC IDEAL IMAGE. Printed per ring over the void and
every ideal of norm <= 40: branches followed to their lock, ties
per branch, distinct limits and 2^t, each shape's limits asserted
equal to its orbit; with starvation asserted at every visited
state. KILL: a seed with two branch tie counts, distinct limits
off 2^t or off the orbit sum, or one unseated conjugate as cheap
as its seated partner.
IP6 THE QUADRATIC ELEMENT IMAGE. Printed per ring over the void and
every principal ideal of norm <= 40: branches, distinct lock-time
states, distinct limits, each shape against its orbit, and for
every erasure (two lock-time states, one limit) the places where
the two differ and the lock vehicle's support. KILL: distinct
limits off the orbit sum; an erasure differing off the lock
support; an erasure at a lock whose vehicle carries no rider (read
as a lock support of two or more places, no rider standing on its
own core's place at these two rings); or, against (5), no erasure
at Q(sqrt(-23)). At Q(sqrt(-23)) every colour holds one place, so
the orbit-sum kill cannot fire there, as (5) predicts.
CONTROLS, run first but IP2's, which section_o runs after IP1's
counts: element_ring.py's control walks; the limit map
made to count a planted pair of states differing off a lock's support
as two limits and a pair differing only on it as one; IP2's
label-reading price; the menus of the number-ring walker read against
the ring's own least raising elements at every visited element state.
FINDINGS (entered after the run, from its printed output).
F1 THE COLOUR COUNT (IP1 hit). The labelled engine, over every place of
degree <= 9 with lambda read as an integer, reaches exactly the
shapes of the walker reading colours alone at every depth, and
every shape's
group holds exactly its product of multinomials: F_2[x], h2 and g2
in the ideal world to depths 9, 9 and 8 (6480, 12096 and 4608
labelled states at the last), h2, h3 and g2 in the element world
to depth 11 (5440, 11664 and 4208). The depth-8 counts 396, 672 and
4608 over two shapes each are an earlier record's, reproduced.
F2 THE COLOURING IS EXACTLY RIGHT (IP2 hit). Grouped by degree alone,
the element world's states sit off the degree multinomial at every
depth of all three rings, from depth 1 on: g2's last depths read
21, 68, 69 and 70 groups off. The label-reading price breaks the
colour count at every depth of F_2[x], so the brute sees a price that
reads more than a colour.
F3 THE CURVE CORNER (IP3 hit). The runaway degrees over every branch
are {1, 2} at the five rings with a degree-2 place and {1} at h5,
which has none. log10 of the degree-1 shape's orbit over its first
ten openings reads 11.56 at F_2[x] (the earlier record's 1.8e11
leaves out the runaway's own factor sigma(1) = 2), 11.57 to 16.97
over the curves; the degree-2 shape reads 13.78 to 16.63.
F4 THE CURVES' ELEMENT IMAGE (IP4 MISSED AS FROZEN, the argument
standing). The kill fired at F_2[x]: its one principal place of
degree 2 is opened past the transient, a choice from one place. The
kill asked every opening to choose from two or more, which (7)
never needs: it needs infinitely many. Every other opening past
the transient chooses from at least 2, at all six rings over 2 to
120 branches and 574 to 34,188 openings, and at every branch's end
every opened colour outside the rider reach holds one seated
place. The rider reach is 0, 1, 2, 3, 4 and 6 places: the h - 1
rational points of nonzero class over the elliptic curves, and
four rational points and two places of degree 2 at g2, one of
which, (2, 13), the walk also opens.
F5 THE QUADRATIC IDEAL IMAGE (IP5 hit). Z[sqrt(-5)], 52 seeds: t = 0,
1, 2 at 35, 15, 2, with 1, 2, 4 limits; Q(sqrt(-23)), 79 seeds:
t = 0, 1 at 65, 14. Every seed's branches share one t, its limits
number 2^t and form ONE shape, and starvation held at 4028
checks.
F6 THE QUADRATIC ELEMENT IMAGE (IP6 hit). Z[sqrt(-5)], 26 seeds:
t = 0 at 16 and t = 1 at 10, each t = 1 seed two limits in ONE
shape, the conjugates sharing a colour. Q(sqrt(-23)), 27 seeds:
t = 0 at 21; t = 1 at 6, four of them two limits over TWO shapes,
the conjugates two colours, and two of them two lock-time states
and ONE limit. Those two are the seeds (2) and (2)^2, exactly the
earlier record's, and at each the two states differ at the two
places over 2 and nowhere else, the lock vehicle being (2) =
P2 P2', a core and its rider. So the lock's rider erases the one
choice it can reach and adds none. 1599 element menus equal the
ring's own least raising elements; no two branches merged before
their locks.
The slate called (1) the orbit law; it is the COLOUR COUNT here, the
first name being the element world's for the runaway's class orbit.
RUN RECORD. One process, CPython, no numpy: 393,974 checks, 12.4 s,
peak 67 MB under a memory guard. A code read aligned two asserts with
their prints (the degree grouping off at every depth of h2, h3 and g2;
a lone principal place at F_2[x]'s degree 2 alone): 393,975 checks,
11.9 s, 63 MB.
"""
import os
import sys
import time
from collections import Counter
from math import factorial, log10
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import element as EL
import element_ring as ER
import limit as LM
import module_law as ML
CHECKS = [0]
def check(cond, msg):
CHECKS[0] += 1
if not cond:
raise AssertionError(msg)
DCAP = 9 # the labelled universe: every place of degree <= DCAP
LABEL_CAP = 30000 # labelled states per depth before the brute stops
LOCK_R = 20 # a lock: LOCK_R consecutive tie-free moves, one vehicle
MAXN = 60 # moves a number-ring branch has to lock in
SEED_N = 40 # number-ring seeds up to this norm
INF = float("inf")
def multinomial(sigma, counts):
"""sigma! / (prod counts! (sigma - sum counts)!)"""
rest = sigma - sum(counts)
check(rest >= 0, "more items than the colour holds")
out = factorial(sigma) // factorial(rest)
for k in counts:
out //= factorial(k)
return out
# ---------------------------------------------------------------------------
# the labelled engine over a curve: actual places, lambda read exactly
class Places:
"""Every affine place of degree <= DCAP of one ring, labelled, with
its colour; the element world's riders mapped onto the one place
of their colour."""
def __init__(self, W):
self.W = W
pl = W.R.places(DCAP)
self.deg = [p[0] for p in pl]
self.cls = [p[1] for p in pl]
self.n = len(pl)
cnt = Counter(zip(self.deg, self.cls))
for (d, c), k in cnt.items():
check(k == W.n[d][c], f"{W.name}: the count against the"
f" matrix at ({d}, {c})")
self.sig_dc = cnt
self.sig_d = Counter(self.deg)
self.where = {}
for i in range(self.n):
self.where.setdefault((self.deg[i], self.cls[i]), []).append(i)
def lam_int(d, a):
return (2 ** d - 1) * EL.pow2ceil(a) if a else 1
def lam_state(P, st):
L = 1
for i, a in enumerate(st):
if a:
x = lam_int(P.deg[i], a)
L = L // gcd(L, x) * x
return L
def gcd(a, b):
while b:
a, b = b, a % b
return a
def door(P, st, L, i):
r = 1
while L % lam_int(P.deg[i], st[i] + r) == 0:
r += 1
return r
def labelled_menu(P, st, element, bias=None):
"""The least moves of the labelled engine as successor states. The
ideal world moves one place to its door at d r; the element world
moves the core to its door and adds MINREP(-r c) on the places of
its colours. bias makes one place dearer by a hair, a price that
reads a label. None when the least cost exceeds DCAP, where a place
outside the universe could tie."""
L = lam_state(P, st)
W = P.W
best, out = None, set()
for i in range(P.n):
d = P.deg[i]
if best is not None and d > best[0]:
continue
r = door(P, st, L, i)
cost = d * r + (W.m[W.R.neg[W.R.mul(P.cls[i], r)]] if element
else 0)
key = (cost, i == bias)
if best is not None and key > best:
continue
s = list(st)
s[i] += r
if element:
for (rd, rc), k in W.rider((d, P.cls[i]), r):
(j,) = P.where[(rd, rc)]
s[j] += k
s = tuple(s)
check(lam_state(P, s) != L, "a least move that does not raise")
if best is None or key < best:
best, out = key, set()
out.add(s)
if best[0] > DCAP:
return None
return out
def labelled_shape(P, st, element, by_degree=False):
T = EL.pow2ceil(max(st))
c = Counter()
for i, a in enumerate(st):
if a:
col = P.deg[i] if (by_degree or not element) else \
(P.deg[i], P.cls[i])
c[(col, a)] += 1
return (T, tuple(sorted(c.items())))
def orbit_size(P, shape, element, by_degree=False):
per = {}
for (col, a), k in shape[1]:
per.setdefault(col, []).append(k)
out = 1
for col, ks in per.items():
sig = P.sig_d[col] if (by_degree or not element) else P.sig_dc[col]
out *= multinomial(sig, ks)
return out
def free_ideal(W, n):
"""limit.py's corner over the ring's supply: shape keys depth by
depth, every tie followed."""
S = LM.Sched("corner", LM.ladder_b(2), LM.price_power(1))
sup = {d: W.supplied[d] for d in range(1, EL.DMAX + 1)}
front = {LM.State().key(): LM.State()}
out = []
for _ in range(n):
nxt = {}
for st in front.values():
for t, _m in LM.menu(S, st, sup)[1]:
s2 = LM.apply(S, st, t)
nxt.setdefault(s2.key(), s2)
front = nxt
out.append({(s.T, tuple(sorted(Counter(
{de: k for de, k in s.seat.items() if k}).items())))
for s in front.values()})
return out
def free_element(W, n):
front = {EL.State().key(): EL.State()}
out = []
for _ in range(n):
nxt = {}
for st in front.values():
for t in EL.menu(W, st)[1]:
s2, _rec = EL.apply(W, st, t)
nxt.setdefault(s2.key(), s2)
front = nxt
keys = set()
for s in front.values():
c = Counter()
for cell, v in s.seat.items():
for e, k in v.items():
if k:
c[(cell, e)] += k
keys.add((s.T, tuple(sorted(c.items()))))
out.append(keys)
return out
def brute(P, element, bias=None, nmax=12):
"""The labelled states depth by depth, grouped by shape: per depth
(shapes, groups off their product, groups off the DEGREE multinomial,
labelled states). Stops before a depth holding more than LABEL_CAP
states, counting as it builds so the frontier never outgrows it, or
reaching a menu the universe cannot price."""
front = {tuple([0] * P.n)}
rows = []
for depth in range(1, nmax + 1):
nxt, over = set(), False
for st in front:
m = labelled_menu(P, st, element, bias)
if m is None or len(nxt | m) > LABEL_CAP:
over = True
break
nxt |= m
if over:
break
front = nxt
groups = Counter(labelled_shape(P, s, element) for s in front)
off = sum(k != orbit_size(P, sh, element)
for sh, k in groups.items())
offd = 0
if element:
gd = Counter(labelled_shape(P, s, element, True) for s in front)
offd = sum(k != orbit_size(P, sh, element, True)
for sh, k in gd.items())
rows.append((depth, set(groups), off, offd, len(front)))
return rows
def section_o(worlds):
"""IP1 and IP2."""
print("IP1 THE COLOUR COUNT, BRUTE")
for W in worlds:
P = Places(W)
for element in (False, True):
if (W.name, element) not in ORBIT_CASES:
continue
t0 = time.time()
rows = brute(P, element)
free = (free_element if element else free_ideal)(W, len(rows))
for (depth, shapes, off, offd, n), fk in zip(rows, free):
check(shapes == fk, f"{W.name}: the shapes at depth"
f" {depth} part from the identity-free walker's")
check(off == 0, f"{W.name}: {off} groups off their orbit"
f" at depth {depth}")
world = "element" if element else "ideal"
print(f" {W.name:6s} {world:7s} {P.n} places of degree <="
f" {DCAP}; depths 1..{rows[-1][0]}: labelled states"
f" {[r[4] for r in rows]}, shapes"
f" {[len(r[1]) for r in rows]}; every shape the"
f" walker's and every group its product"
f" ({time.time() - t0:.1f} s)")
if element:
DEG_OFF[W.name] = [r[3] for r in rows]
print(f" {'':6s} {'':7s} grouped by degree alone, groups"
f" off the degree multinomial per depth"
f" {DEG_OFF[W.name]}")
print("IP2 A PRICE THAT READS A LABEL (control)")
W = worlds[0]
P = Places(W)
x = P.where[(1, 0)][0]
rows = brute(P, False, bias=x)
off = [r[2] for r in rows]
check(sum(off) > 0, "control: a label-reading price keeps every orbit")
print(f" {W.name}: one degree-1 place priced a hair dearer on ties:"
f" groups off their product per depth {off}")
ORBIT_CASES = {("F2[x]", False), ("h2", False), ("g2", False),
("h2", True), ("h3", True), ("g2", True)}
DEG_OFF = {}
# ---------------------------------------------------------------------------
# the curves' images
def first_openings(W, start, k=10):
return [d for d in range(start, EL.DMAX + 1) if W.supplied[d]][:k]
def section_c(worlds):
"""IP3: the corner's two shapes and their orbits."""
print("IP3 THE CURVE CORNER")
S = LM.Sched("corner", LM.ladder_b(2), LM.price_power(1))
for W in worlds:
sup = {d: W.supplied[d] for d in range(1, EL.DMAX + 1)}
out, census = LM.branches(S, sup, 10, 290)
run = Counter(LM.shape(st)[0] for st, lg in out)
want = {1} | ({2} if sup[2] else set())
check(set(run) == want, f"{W.name}: runaway degrees {set(run)}")
one = log10(sup[1]) + sum(log10(sup[d])
for d in first_openings(W, 2))
two = (log10(sup[2]) + sum(log10(sup[d])
for d in first_openings(W, 3))
if sup[2] else None)
print(f" {W.name:6s} sigma(1..6) {[sup[d] for d in range(1, 7)]};"
f" runaway degrees over {len(out)} branches"
f" {dict(sorted(run.items()))}; log10 of each shape's orbit"
f" over its first ten openings: C of degree 1 {one:.2f}"
+ (f", C of degree 2 {two:.2f}" if two is not None else
", no degree-2 shape"))
def section_e(worlds):
"""IP4: the element image over the curves."""
print("IP4 THE CURVES' ELEMENT IMAGE")
for W in worlds:
t0 = time.time()
reach = {cell for x in range(W.h) for cell, k in W.rep[x]}
for cell in reach:
check(W.n[cell[0]][cell[1]] == 1, "a rider colour holding two")
out, _ = EL.branches(W)
least, inside, past, prod, ones = None, set(), 0, None, set()
for st, log in out:
trans = max([i for i, x in enumerate(log)
if x["open"] and x["rider"]] + [-1])
opened = []
for i, x in enumerate(log):
if not x["open"]:
continue
cell = x["t"][0]
if cell in reach:
inside.add(cell)
if i > trans:
past += 1
check(cell[1] == 0, f"{W.name}: an opening past"
f" the transient not principal")
s = W.n[cell[0]][0]
if s < 2:
ones.add(cell[0])
else:
least = s if least is None else min(least, s)
opened.append(s)
for cell in {x["t"][0] for x in log if x["open"]} - reach:
check(st.nseat[cell] == 1, f"{W.name}: a declined"
f" sibling of {cell} seated")
if prod is None:
prod = sum(log10(s) for s in opened[:10])
check(ones == ({2} if W.name == "F2[x]" else set()),
f"{W.name}: a lone principal place chosen at degrees"
f" {sorted(ones)}")
print(f" {W.name:6s} rider reach {len(reach)} place(s)"
f" {sorted(reach)}; {len(out)} branches, {past} openings"
f" past the transient; degrees opened from a single"
f" principal place {sorted(ones)}, every other opening"
f" choosing from at least {least}; opened colours inside"
f" the reach"
f" {sorted(inside)}; every opened colour outside it one"
f" seated place at every branch's end; log10 of the first"
f" ten such choices {prod:.2f} ({time.time() - t0:.1f} s)")
# ---------------------------------------------------------------------------
# the number rings
def colour(F, C, pl, element):
kind = "split" if pl[2] >= 0 else pl[2]
base = (pl[0], pl[1], kind)
return base + (C.cls[pl],) if element else base
TALLY = Counter()
class RingWorld:
def __init__(self, F, element):
self.F, self.element = F, element
self.C = ER.Classes(F)
self.S = ER.Supply(self.C)
self.name = F.name + (" element" if element else " ideal")
def menu(self, st, L):
F = self.F
if self.element:
b1, v1 = ER.abstract_menu(self.S, st, L)
b2, v2 = ER.ring_menu(F, st, L)
check(b1 == b2 and v1 == set(v2), f"{self.name}: the menu"
f" against the ring's least raising elements")
TALLY["ring menus"] += 1
return sorted(v1, key=lambda v: sorted(v))
cost, ties = ML.menu(F, st, L)
self.starve(st, L)
return [frozenset({pl: r}.items()) for pl, r in ties]
def starve(self, st, L):
F = self.F
for p in {pl[1] for pl in st if pl[2] >= 0 and st[pl]}:
P, Q = F.over(p)
if bool(st.get(P, 0)) != bool(st.get(Q, 0)):
s, u = (P, Q) if st.get(P, 0) else (Q, P)
cs = s[0] ** ML.door(F, s, st[s], L)
cu = u[0] ** ML.door(F, u, 0, L)
check(cu > cs, f"{self.name}: starvation at {s}, {u}")
TALLY["starvation"] += 1
def skey(st):
return tuple(sorted((p, a) for p, a in st.items() if a))
def run_seed(RW, seed):
"""Every branch from seed followed to its lock: per lock-time state,
(state, lock vehicle, ties on the branch)."""
F = RW.F
front = {skey(seed): (dict(seed), F.lam_state(seed), (), 0)}
finals = {}
for _ in range(MAXN):
nxt = {}
for k, (st, L, hist, t) in front.items():
if (len(hist) == LOCK_R and len(set(hist)) == 1
and not hist[0][1]):
finals[k] = (st, hist[0][0], t)
continue
vs = RW.menu(st, L)
tie = len(vs) > 1
for v in vs:
s2 = dict(st)
for pl, a in v:
s2[pl] = s2.get(pl, 0) + a
L2 = F.lam_state(s2)
check(L2 != L, "a move that does not raise lambda")
h2 = (hist + ((v, tie),))[-LOCK_R:]
k2 = skey(s2)
if k2 in nxt:
TALLY["merges"] += 1
nxt.setdefault(k2, (s2, L2, h2, t + tie))
front = nxt
if not front:
break
check(not front, f"{RW.name}: a branch from {seed} unlocked after"
f" {MAXN} moves")
return finals
def limit_of(st, vehicle):
lim = {p: a for p, a in st.items() if a}
for pl, a in vehicle:
lim[pl] = INF
return tuple(sorted(lim.items()))
def orbit_sum(RW, seed, limits):
"""The colour count at a seed: distinct limits grouped by shape, each
group against its product of multinomials over the colours refined
by the seed. A split colour holds its two conjugates; every other
colour one place."""
F, C = RW.F, RW.C
def col(pl):
return (colour(F, C, pl, RW.element), seed.get(pl, 0))
groups = Counter()
for lim in limits:
d = dict(lim)
cols = {}
for pl in d:
c = col(pl)
mates = [q for q in (F.conj(pl), pl) if col(q) == c]
cols[c] = sorted(set(mates))
shape = tuple(sorted(
((c, tuple(sorted(d.get(q, 0) for q in m)))
for c, m in cols.items()), key=repr))
groups[shape] += 1
total = 0
for shape, k in groups.items():
size = 1
for c, ex in shape:
size *= multinomial(len(ex), list(Counter(ex).values()))
check(k == size, f"{RW.name}: a shape at seed {seed} holding {k}"
f" limits against its orbit {size}")
total += size
return total, len(groups)
def section_r(F, element):
"""IP5 or IP6 at one ring."""
RW = RingWorld(F, element)
t0 = time.time()
seeds = ER.seeds(F) if element else \
[{}] + [ideal for n, ideal in F.ideals(SEED_N)]
rows = Counter()
erase = []
for sd in seeds:
finals = run_seed(RW, sd)
ts = {t for st, v, t in finals.values()}
byl = {}
for st, v, t in finals.values():
byl.setdefault(limit_of(st, v), []).append((st, v))
_, nshape = orbit_sum(RW, sd, byl)
if not element:
check(len(ts) == 1, f"{RW.name}: branch tie counts {ts}")
check(nshape == 1, f"{RW.name}: {nshape} shapes at {sd}")
check(len(byl) == 2 ** min(ts), f"{RW.name}: {len(byl)}"
f" limits against 2^{min(ts)} at {sd}")
for lim, grp in byl.items():
if len(grp) > 1:
s1, v1 = grp[0]
diff = {p for s2, _ in grp[1:] for p in set(s1) | set(s2)
if s1.get(p, 0) != s2.get(p, 0)}
supp = {pl for pl, a in v1}
check(all(v2 == v1 for _, v2 in grp),
"an erasure across two lock vehicles")
check(diff <= supp, f"{RW.name}: an erasure off the lock"
f" support at {sd}")
check(len(supp) >= 2, f"{RW.name}: an erasure at a lock"
f" carrying no rider")
erase.append((sd, sorted(diff), sorted(v1), len(grp)))
rows[(min(ts), max(ts), len(finals), len(byl), nshape)] += 1
print(f" {RW.name}: {len(seeds)} seeds ({time.time() - t0:.1f} s)")
print(f" (least ties, most ties, lock-time states, limits, shapes):"
f" seeds {sorted(rows.items())}")
for sd, diff, v, n in erase:
print(f" erasure at seed {sd}: {n} states differing at"
f" {diff}, one limit, the lock vehicle {v}")
return erase
def section_q():
print("IP5, IP6 THE QUADRATIC RINGS")
TALLY.clear()
er = {}
for F in (ML.K5, ML.K23):
section_r(F, False)
for F in (ML.K5, ML.K23):
er[F.name] = section_r(F, True)
print(f" starvation checks {TALLY['starvation']}; ring menus read"
f" {TALLY['ring menus']}; branch merges {TALLY['merges']}")
check(er[ML.K23.name], "no erasure at Q(sqrt(-23))")
check(not er[ML.K5.name], "an erasure at Z[sqrt(-5)]")
def section_control():
print("CONTROLS")
ER.section_control()
A, B, C = (2, 2, 0), (2, 2, 1), (3, 3, 1)
v = frozenset({A: 1, B: 1}.items())
s1, s2, s3 = {A: 5, B: 3, C: 1}, {A: 3, B: 5, C: 1}, {A: 5, B: 3, C: 2}
check(limit_of(s1, v) == limit_of(s2, v), "control: on the support")
check(limit_of(s1, v) != limit_of(s3, v), "control: off the support")
print(" the limit map: two states differing on a lock's support read"
" one limit, differing off it two")
def main():
t0 = time.time()
section_control()
rings = [EL.Ring(*x) for x in EL.RINGS]
worlds = [EL.World(R) for R in rings]
section_o(worlds)
for name in ("h2", "h3", "g2"):
check(DEG_OFF.get(name) and all(v > 0 for v in DEG_OFF[name]),
f"{name}: the degree multinomial fits the element world at"
" some depth")
section_c(worlds)
section_e(worlds)
section_q()
print(f"{CHECKS[0]} checks, {time.time() - t0:.1f} s")
if __name__ == "__main__":
main()