readout.py
Checks: LEARNER: Exact readout reads the subdominant criterion; LEARNER: The grown depth is the readable depth theorem.
Cited on: LEARNER.
To run it: save readout.py, with collision.py beside it; standard library only.
"""readout.py -- what a similarity lets a reader read exactly, and why the
prime a collision grower takes is the tower's agreement plus one.
QUESTION. A WORLD X is a finite set, a GRADING s a symmetric map from
pairs of X into a totally ordered set, and a LABEL a map on X. A reader
holding a query q of X and a STORE P, a set of other members of X, reads
q's label off a member of P with the greatest s(q, .), the MOST SIMILAR
member. At a threshold t the store is ADMISSIBLE when its most similar
member has s(q, .) >= t, and the readout is EXACT when every most
similar member carries q's label, so no tie-break is ever needed. A
label is READABLE at t when the readout is exact for every query and
every admissible store. Which labels are readable, and does the answer
depend on the world the grading lives on -- the tower's AGREEMENT (the
count of leading primes two inputs agree at), the count of primes at
which two residues agree, the distance on the line? And collision.py
grows a substrate of primes that takes, per difference d of two
differently labelled inputs, the least prime not dividing d: is that
prime the tower's agreement in another name, so that the grown depth is
the depth at which the labelled set's labels become readable?
THE ARGUMENT (written before the engine).
(A) THE COMPONENT CRITERION. Let G_t be the graph on X with an edge
x ~ y when s(x, y) >= t. A label is readable at t iff it is
constant on the components of G_t. If constant: a most similar
member of an admissible store has s >= t with q, so it is q's
neighbour, in q's component, and carries q's label, and so does
every tied one. If not constant: it differs across some edge
x ~ y; the query x with the store {y} is admissible and its one
member is wrong. Nothing about s is used but its
values' order: the criterion holds on every world.
(B) THE SUBDOMINANT. G_(t+1) has fewer edges than G_t, so its
components refine G_t's: the components nest across thresholds even where
the fixed-t neighbourhoods {y : s(x, y) >= t} do not. Define
u(x, y) as the largest t with x and y in one component of G_t,
equivalently the largest over paths from x to y of the least s
along an edge. Then u >= s, u satisfies the strong triangle
u(x, z) >= min(u(x, y), u(y, z)) (join the paths), and every
grading v >= s satisfying it has v >= u (along a best path,
v(x, y) >= the least v along an edge >= the least s = u(x, y)).
So u is the least ultrametric grading above s, and by (A) a
label is readable at t iff it is constant on the balls
{y : u(x, y) >= t}. The readout reads u, never s: a pair with
s(x, y) < t <= u(x, y) is merged whatever its label. This u is
the subdominant ultrametric of cluster analysis, the one single
linkage builds, in its dual form: the field states it as the
largest ultrametric below a dissimilarity. When s already
satisfies the strong triangle, u = s.
(C) THE LINE. On a finite set of integers with s(x, y) = -|x - y|,
the distance the tower deleted, (A) and (B) hold verbatim. The
points 0, 1, 2 at t = -1 are an OPEN TRIANGLE, 0 ~ 1 ~ 2 with
0 and 2 not adjacent, and a label splitting 0 from 2 is
unreadable: the query 1 with the store {0, 2} ties them at
distance 1. So the line's distance reads no finer than its
subdominant by this readout, and a reading finer than a
subdominant is bought by a different readout, never by a
different world.
(D) AGREEMENT. Order the pool primes p_1 < p_2 < ... < p_K and
let a(x, y) be the largest t with p_t# dividing x - y (p_0# = 1),
the number of leading pool primes dividing x - y. The balls
{y : a(x, y) >= t} are the classes mod p_t#, and a satisfies the
strong triangle since congruences compose, so a is its own
subdominant.
When a(x, y) < K, the least pool prime not dividing x - y is
p_(a(x, y) + 1): the LEAST NON-DIVISOR of collision.py is the
successor of the agreement, by definition.
(E) THE WELD. Take a labelled set X, its values below p_K#, and
a = the agreement. By (D), collision.py's grower takes the
primes p_(a(x, y) + 1) over differently labelled pairs, and its
DEPTH, the index of the largest prime taken (0 when none is), is
1 + the largest such a(x, y). By (A) and (D), the labelled set's label
is readable at t iff no differently labelled pair has
a(x, y) >= t, so the least threshold at which it is readable is
that same 1 + max. The grown depth IS the readable depth, and a
prime is taken iff some ball of X at its level holds two labels
that the next level splits.
THE WORLDS.
RANDOM GRADING: six points, s drawn uniformly from 0 .. 3 per pair
by random.Random(seed); twelve seeds.
TOWER: six integers drawn below 2310 = 2 * 3 * 5 * 7 * 11, s = a
along the pool 2, 3, 5, 7, 11; twelve seeds.
LINE: the integers 0, 1, 2, 4, 7, 8 with s = -|x - y|.
LABELLED SETS: seven integers drawn below 2310 with labels drawn from
two, three or four classes; 600 seeds.
PREDICTIONS (fixed before the engine ran).
P0 [controls, read first] (i) On Z/30 the pool 2, 3, 5 gives
a(0, 6) = 2, a(6, 16) = 1, a(0, 16) = 1, and the least
non-divisors 5 of 6 and 3 of 10. (ii) Over all 27,000 triples of
Z/30, a satisfies the strong triangle, and so no triple has
a(x, y) >= 1, a(y, z) >= 1, a(x, z) = 0 (printed beside it). (iii) The count of
the primes 2, 3, 5 at which two residues agree gives 0, 6, 16 the
values 2, 2, 1, an open triangle at t = 2, so the strong triangle
does fail in some world. (iv) The
brute readout calls the constant label readable at every
threshold and, on the line, the label splitting 0 from 2
unreadable at t = -1.
P1 [(A)] On every RANDOM GRADING, TOWER and the LINE world, for
every label map with at most three labels and every threshold
over the grading's values, brute readability over all queries
and all stores equals constancy on G_t's components: no
exception either way, and both answers occur.
P2 [(B)] u by components equals u by best paths on every world;
u satisfies the strong triangle and u >= s; over the two-label
maps, a map is constant on G_t's components under s iff it is
under u (P1 having equated readability with the former, by
brute readout over up to three labels); on TOWER, u = a.
On some RANDOM GRADING, u > s at a pair.
P3 [(C)] On the LINE, the open triangle 0 ~ 1 ~ 2 at t = -1 is printed and
the query 1 with the store {0, 2} finds both at distance 1, a tie
the store must break.
P4 [(D), (E)] Over all pairs of all LABELLED SETS, the least non-divisor
equals p_(a + 1); collision.py's grower's depth equals the least
threshold at which brute readout is exact; its grown set equals
{p_(a(x, y) + 1)} over differently labelled pairs.
KILLS (observables).
K0 any P0 control misses: nothing below is read.
K1 a label map where brute readability and component constancy
differ: (A) is wrong.
K2 a world where the two computations of u differ, or u breaks the
strong triangle: (B) is wrong.
K3 a labelled set where the grown depth and the readable depth differ, or
a pair where the least non-divisor is not p_(a + 1): (D) or (E)
is wrong.
FINDINGS (entered after the run; 17 of 17 checks pass, no kill).
F0 The controls pass: a(0, 6), a(6, 16), a(0, 16) = 2, 1, 1; the
least non-divisors of 6 and 10 are 5 and 3; a keeps the strong
triangle on all 27,000 triples of Z/30 with 0 open triangles; the count
of agreeing primes gives the open triangle 2, 2, 1; the brute readout
reads the constant label and refuses the line's split open triangle.
F1 Brute readability equals component constancy in every case:
43,740 on the random gradings (9,030 readable), 38,637 on the
tower worlds (11,745 readable), 6,561 on the line (783
readable).
F2 The two computations of u agree on all 25 worlds, u keeps the
strong triangle, lies above s, and its components at every
threshold carry the same two-label maps as s's;
u = a on every tower world, and u > s at some pair on all 12
random gradings.
F3 On the line s(0, 1) = s(1, 2) = -1, s(0, 2) = -2 and u(0, 2) =
-1: the open triangle is merged, and the query 1 ties 0 and 2.
F4 The least non-divisor is p_(a + 1) on all 12,600 pairs; on all
600 labelled sets the grown depth equals the least readable threshold,
depths 0 through 5 all occurring, and the grown set equals the
successors of the separated pairs' depths.
RUN RECORD. One run, 17 checks, 2.3 s, peak 13.6 MB. Exact integers
throughout.
"""
import os
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import random
import sys
from itertools import combinations, product
from math import prod
from collision import grow, first_primes
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(title)
POOL = first_primes(5)
TOP = prod(POOL)
# the gradings
def agreement(x, y, pool=POOL):
t, d = 0, x - y
for p in pool:
if d % p:
break
t += 1
return t
def least_non_divisor(d, pool=POOL):
for p in pool:
if d % p:
return p
return None
def count_agree(x, y, pool=POOL):
return sum(1 for p in pool if (x - y) % p == 0)
def grading_of(W, f):
return {(x, y): f(x, y) for x in W for y in W if x != y}
# the readout
def readable_brute(W, s, lab, t):
"""Every query, every store of other members, every most similar member."""
for q in W:
others = [x for x in W if x != q]
for r in range(1, len(others) + 1):
for P in combinations(others, r):
top = max(s[q, x] for x in P)
if top < t:
continue
if any(lab[x] != lab[q] for x in P if s[q, x] == top):
return False
return True
def components(W, s, t):
comp = {x: x for x in W}
def find(x):
while comp[x] != x:
comp[x] = comp[comp[x]]
x = comp[x]
return x
for x, y in combinations(W, 2):
if s[x, y] >= t:
comp[find(x)] = find(y)
return {x: find(x) for x in W}
def component_constant(W, s, lab, t):
c = components(W, s, t)
return all(lab[x] == lab[y] for x, y in combinations(W, 2)
if c[x] == c[y])
# the subdominant
def sub_components(W, s):
vals = sorted(set(s.values()))
u = {}
for x, y in s:
u[x, y] = max(t for t in vals if components(W, s, t)[x]
== components(W, s, t)[y])
return u
def sub_paths(W, s):
"""Widest paths: the largest least-edge value over paths."""
u = dict(s)
for k in W:
for i in W:
for j in W:
if len({i, j, k}) == 3:
u[i, j] = max(u[i, j], min(u[i, k], u[k, j]))
return u
def strong_triangle(W, s):
return all(s[x, z] >= min(s[x, y], s[y, z])
for x, y, z in product(W, repeat=3)
if len({x, y, z}) == 3)
def labellings(W, n_labels=3):
for lab in product(range(n_labels), repeat=len(W)):
yield dict(zip(W, lab))
def thresholds(s):
vals = sorted(set(s.values()))
return vals + [vals[-1] + 1]
# the worlds
def random_world(seed):
rng = random.Random(seed)
W = list(range(6))
s = {}
for x, y in combinations(W, 2):
s[x, y] = s[y, x] = rng.randrange(4)
return W, s
def tower_world(seed):
rng = random.Random(1000 + seed)
W = rng.sample(range(TOP), 6)
return W, grading_of(W, agreement)
def line_world():
W = [0, 1, 2, 4, 7, 8]
return W, grading_of(W, lambda x, y: -abs(x - y))
def worlds():
out = [("random", seed, *random_world(seed)) for seed in range(12)]
out += [("tower", seed, *tower_world(seed)) for seed in range(12)]
out.append(("line", 0, *line_world()))
return out
# the sections
def section_controls():
section("CONTROLS")
got = (agreement(0, 6, POOL[:3]), agreement(6, 16, POOL[:3]),
agreement(0, 16, POOL[:3]))
check("a(0, 6), a(6, 16), a(0, 16) = 2, 1, 1 on the pool 2, 3, 5",
got == (2, 1, 1), str(got))
got = (least_non_divisor(6, POOL[:3]),
least_non_divisor(10, POOL[:3]))
check("least non-divisors of 6 and 10 are 5 and 3", got == (5, 3),
str(got))
Z = list(range(30))
viol = opens = 0
for x, y, z in product(Z, repeat=3):
axy, ayz, axz = (agreement(x, y, POOL[:3]), agreement(y, z, POOL[:3]),
agreement(x, z, POOL[:3]))
viol += axz < min(axy, ayz)
opens += axy >= 1 and ayz >= 1 and axz == 0
check("a keeps the strong triangle on all 27,000 triples of Z/30",
viol == 0 and opens == 0,
f"{viol} violations, {opens} open triangles")
got = (count_agree(0, 6, POOL[:3]), count_agree(6, 16, POOL[:3]),
count_agree(0, 16, POOL[:3]))
check("the count of agreeing primes opens a triangle: 2, 2, 1",
got == (2, 2, 1), str(got))
W, s = line_world()
check("the constant label is readable at every threshold",
all(readable_brute(W, s, {x: 0 for x in W}, t)
for t in thresholds(s)))
lab = {x: 0 for x in W}
lab[2] = 1
check("on the line, splitting 0 from 2 is unreadable at t = -1",
not readable_brute(W, s, lab, -1))
def section_criterion(ws):
section("THE COMPONENT CRITERION")
for kind in ("random", "tower", "line"):
n = bad = yes = 0
for k, seed, W, s in ws:
if k != kind:
continue
for lab in labellings(W):
for t in thresholds(s):
b = readable_brute(W, s, lab, t)
c = component_constant(W, s, lab, t)
n += 1
bad += b != c
yes += b
check(f"{kind}: brute readability = component constancy",
bad == 0 and 0 < yes < n,
f"{n} cases, {bad} differ, {yes} readable")
def section_subdominant(ws):
section("THE SUBDOMINANT")
for k, seed, W, s in ws:
u1, u2 = sub_components(W, s), sub_paths(W, s)
ok = (u1 == u2 and strong_triangle(W, u1)
and all(u1[p] >= s[p] for p in s))
ok &= all(component_constant(W, s, lab, t)
== component_constant(W, u1, lab, t)
for lab in labellings(W, 2) for t in thresholds(s))
if not ok:
check(f"{k} {seed}: the subdominant", False)
return
check("u two ways agree, keep the strong triangle, lie above s, "
"and read the same labels, on every world", True,
f"{len(ws)} worlds")
towers = [(W, s) for k, _, W, s in ws if k == "tower"]
check("on every tower world u = a",
all(sub_paths(W, s) == s for W, s in towers))
gaps = sum(1 for k, _, W, s in ws if k == "random"
and any(sub_paths(W, s)[p] > s[p] for p in s))
check("some random grading has u > s at a pair", gaps > 0,
f"{gaps} of 12")
def section_line():
section("THE LINE")
W, s = line_world()
print(f" s(0, 1) = {s[0, 1]}, s(1, 2) = {s[1, 2]}, "
f"s(0, 2) = {s[0, 2]}")
u = sub_paths(W, s)
print(f" u(0, 2) = {u[0, 2]}")
check("0 ~ 1 ~ 2 is an open triangle at t = -1 and u merges 0 and 2",
s[0, 1] >= -1 and s[1, 2] >= -1 and s[0, 2] < -1
and u[0, 2] >= -1)
check("query 1, store {0, 2}: both most similar, at distance 1",
s[1, 0] == s[1, 2] == -1)
def streams(n, seed0=0):
for seed in range(seed0, seed0 + n):
rng = random.Random(seed)
W = rng.sample(range(TOP), 7)
c = 2 + seed % 3
yield W, {x: rng.randrange(c) for x in W}
def section_weld():
section("THE WELD")
pairs = bad_l = 0
bad_depth = bad_set = 0
depths = set()
for W, lab in streams(600):
for x, y in combinations(W, 2):
pairs += 1
a = agreement(x, y)
bad_l += least_non_divisor(x - y) != POOL[a]
sep = [(x, y) for x, y in combinations(W, 2) if lab[x] != lab[y]]
D = {abs(x - y) for x, y in sep}
g = grow(D, POOL)
gdepth = POOL.index(max(g)) + 1 if g else 0
s = grading_of(W, agreement)
rdepth = min(t for t in range(len(POOL) + 2)
if readable_brute(W, s, lab, t))
depths.add(gdepth)
bad_depth += gdepth != rdepth
bad_set += sorted(g) != sorted({POOL[agreement(x, y)]
for x, y in sep})
check("the least non-divisor of x - y is p_(a + 1) on every pair",
bad_l == 0, f"{pairs} pairs, {bad_l} differ")
check("the grown depth = the least readable threshold",
bad_depth == 0, f"600 labelled sets, {bad_depth} differ, "
f"depths seen {sorted(depths)}")
check("the grown set = the successors of the separated depths",
bad_set == 0, f"{bad_set} differ")
def main():
section_controls()
ws = worlds()
section_criterion(ws)
section_subdominant(ws)
section_line()
section_weld()
print()
n, ok = len(CHECKS), sum(CHECKS)
print(f"{ok} of {n} checks pass")
return 0 if ok == n else 1
if __name__ == "__main__":
sys.exit(main())