floors.py
Checks: THERMAL: What each fate needs of the ground theorem.
Cited on: THERMAL.
To run it: save floors.py, with growth.py beside it; standard library only.
"""floors.py -- what each growth fate needs of the ground it grows on:
a bare order, a cancellative monoid with a weight, or unique
factorization.
QUESTION. thermal.py proves three fates of thermal growth over Z and
F_2[x]: transparency dies, dynamics reaches all of Z-hat, independence
grows the zeta measure. Each proof used a few properties of the
integers. Take the integers away one property at a time: on a finite
order, on a cancellative commutative monoid with a weight, on a free
one. Which fate survives on which ground, and which property is the
one a fate cannot do without?
THE OBJECT. FLOOR 0: a set of states strictly ordered, a demand naming
the admissible ascents from each state, no weight. The INTERVAL demand
on a region R admits every element of R above the state. FLOOR 1: a
countable cancellative commutative monoid M with a CHARACTER w,
w(ab) = w(a) w(b), 0 < w <= 1 off the identity, summable over M; the
thermal law picks m in A(x) with probability w(m) / Psi_x, Psi_x the sum of w over A(x). A demand is
UP-CLOSED when m in A(x) and m | m' give m' in A(x). FLOOR 2: M free
on countably many atoms. The worlds: Z (free on the primes, w = m^-beta),
F_2[x] (free on the irreducibles, w = 2^(-beta deg)), and NUM23, the
numerical monoid {x^n : n = 0 or n >= 2} with atoms x^2 and x^3,
cancellative and not free (x^2 x^2 x^2 = x^3 x^3); in NUM23, x^a
divides x^b iff b - a is 0 or at least 2.
THE ARGUMENT (written before the engine).
(1) DEATH NEEDS ONLY ORDER. A demand confining the walk to a finite
region R absorbs under every policy within the height of R,
since every move ascends strictly. For the interval demand the
graves are the reachable elements with no successor in R, each
reached by some policy, and the grave is unique iff the
reachable part of R has a maximum: a maximum dominates every
terminal, and without one two maximal elements are two graves.
On {1 < 2, 1 < 3} greedy dies at the cheaper of 2 and 3 and the
thermal law splits w(2) : w(3): the grave is the policy's. A
confined demand that is not an interval can run dry below a
maximum: R = divisors of 8, A(1) = {2}, A(2) empty. Transparency
over Z is the interval case with a maximum: the fibre above s is
the multiples of s dividing W(lambda(s)), so every trajectory
ends at that one wall.
(2) REACHING EVERYTHING NEEDS ONLY MULTIPLICATION. On floor 1 let A
be up-closed and nonempty. For any element a, m -> am maps A
into A cap aM injectively (cancellation) and multiplies weights
by w(a), so P(pick in aM) >= w(a) at every state. By Levy's
extension of Borel-Cantelli a divides infinitely many picks, so
it divides the state from some time on, almost surely, and M is
countable, so almost surely every element divides the state
eventually: the limit is the top. No atom and no factorization
is used.
(3) BEING ARITHMETIC RESTS ON UNIQUE FACTORIZATION. On floor 2
thermal.py's zeta measure transfers word for word (support,
entry-once, geometric depths), and the crystal's probability is
prod_g (1 - w(g)), which is 1/(sum of w over M) because the Euler
product equals the Dirichlet sum exactly when every element has
one factorization.
(4) FREENESS CANNOT BE DROPPED. In NUM23, call m independent of x^k when
no atom divides both. Every x^n with n >= 5 is divisible by both
atoms (n - 2 >= 3 and n - 3 >= 2 lie in the monoid), so every
independence walk from the identity dies within two moves; the
maximal two-move walks are 2 then 3, 3 then 2, 3 then 4 and 4 then
3, in exponents. The Euler product 1/((1 - t^2)(1 - t^3)) and the
Dirichlet sum 1 + t^2/(1 - t) first differ at t^6 (x^6 has two
factorizations), and at t = 1/4 they are 1024/945 and 13/12.
Up-closed demands reach the top of the same monoid by (2): two
fates part inside one world.
(5) CONSUMPTION. Independence avoids the support it has built, so a
move once taken is never admissible again: a consuming demand
owns no fixed standing move, and a standing family for it must
be made of recipes, as breadth's is in standing.py.
DESIGN. Standard library, exact rational arithmetic where it can be;
one process. growth.py supplies lambda and the wall.
C POSITIVE CONTROL, before any verdict. Over F_2[x] the Dirichlet
series sum_d 2^d u^d and the Euler product prod_d (1 - u^d)^(-N_d),
N_d the irreducible count by the necklace formula, agree
coefficient by coefficient to degree 24: the free world passes the
test NUM23 is to fail.
O floor 0. O1 every region: the divisor lattices of 60, 72, 210 and
360 from every seed, and 200 random subsets of the divisors of 360
containing 1 (fixed random seed), under the interval demand; the
graves counted, a record. O2 the specimen {1, 2, 3}: its graves,
greedy's end and the thermal split; the run-dry region printed.
O3 transparency from seeds 3, 5, 7: every maximal walk ends at
W(lambda(s)), 24, 240, 504.
M floor 1. M1 on NUM23 with t = 1/4, exactly: for the up-closed
demands A_c = {m : m does not divide x^c}, c = 0..12, and a in
{x^2, x^3, x^4, x^5, x^7}, mass(A_c cap aM) >= w(a) mass(A_c).
Each A_c is up-closed by transitivity of division, no check.
X the collapse. X1 both atoms divide x^n for 5 <= n <= 200. X2 every
maximal independence walk from the identity with moves of exponent
at most 60. X3 the two series to t^12 and at t = 1/4, exactly.
PREDICTIONS, fixed before the run.
C agreement at every degree to 24.
O O1 every walk no longer than the height, every end a no-successor
element, one grave iff a reachable maximum, with some regions of
several graves (the replaced record counted 30 of 240). O2 two
graves on {1, 2, 3}; the run-dry walk ends at 2. O3 every walk
ends at 24, 240, 504.
M M1 the inequality in every cell, equality whenever aA_c = A_c cap
aM. M2 no violation.
X X1 no exception. X2 no walk longer than 2; exactly four of length
2, (2, 3), (3, 2), (3, 4), (4, 3). X3 first difference at t^6, of
+1 on the Euler side; 13/12 and 1024/945.
A KILL is any failure in O, M1, X1, X2 or X3. The control reads the
series engine over F_2[x]; X3 sums NUM23's two series directly, so the
control does not test it, though X3 is read only once it passes.
[Ruled after a later reading: O1 and M2 held by construction, the
interval demand's walks being its chains and its graves the maximal
elements of a finite set, and A_c up-closed by transitivity; both
are cut, O1's grave count kept as a printed record, and the run-dry
walk, a demand written down, is printed, not checked.]
FINDINGS. 7/7 checks PASS and no kill.
C the irreducible counts 2, 1, 2, 3, 6, 9, 18, 30 to degree 8, and the
Euler product over F_2[x] equal to the Dirichlet series 2^d at every
degree to 24.
O 264 regions (the four divisor lattices from every seed and 200
random regions of 360's divisors), 101 with more than one grave.
{1, 2, 3} has the graves 2 and 3, greedy ending at 2 and the
thermal law at beta 2 sending 0.6923 of worlds to 2; the run-dry
walk ends at 2 below 8. Transparency from 3, 5 and 7 ends only at
24, 240 and 504.
M the mass inequality in all 65 cells of NUM23 at t = 1/4, strict in
every one.
X both atoms divide every x^n, 5 <= n <= 200. 60 maximal
independence walks with moves of exponent at most 60, the longest
of length 2, and those exactly (2, 3), (3, 2), (3, 4), (4, 3). The
series agree to t^5 and part at t^6 by one factorization; at
t = 1/4 the Dirichlet sum is 13/12 and the Euler product
1024/945.
Tiers: (1), (2), (4) are theorems, with the checks above in the
ranges printed; (3) is a theorem, its transfer being thermal.py's
argument read over any free monoid; (5) is a property.
RUN RECORD. python floors.py: 7/7 checks, 0.1 s, peak 8.3 MB under a
512 MB ceiling.
"""
import os
import random
import sys
import time
from fractions import Fraction
from functools import lru_cache
from math import comb
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import growth # noqa: E402
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)
def divisors(n):
ds = [1]
for p, e in growth.factor(n).items():
ds = [d * p ** i for d in ds for i in range(e + 1)]
return sorted(ds)
# ------------------------------------------------------ C the control
def necklace(d):
"""The number of monic irreducibles of degree d over F_2."""
tot = 0
for e in range(1, d + 1):
if d % e == 0:
mu, x = 1, d // e
for p in growth.PRIMES:
if p > x:
break
if x % p == 0:
x //= p
if x % p == 0:
mu = 0
break
mu = -mu
tot += mu * 2 ** e
return tot // d
def section_c():
section("C positive control: a free world's two series agree")
D = 24
series = [1] + [0] * D
for d in range(1, D + 1):
N = necklace(d)
factor = [0] * (D + 1)
for k in range(0, D // d + 1):
factor[d * k] = comb(N + k - 1, k)
series = [sum(series[i] * factor[n - i] for i in range(n + 1))
for n in range(D + 1)]
ok = series == [2 ** d for d in range(D + 1)]
print(f" irreducible counts to degree 8: "
f"{[necklace(d) for d in range(1, 9)]}")
check("C1 over F_2[x] the Euler product equals the Dirichlet series "
"to degree 24", ok)
return ok
# ------------------------------------------------------ O floor 0
def interval_graves(R, s):
"""Under the interval demand on R from s: the ends of every maximal
walk, by memoized search."""
R = sorted(R)
above = {r: [u for u in R if u != r and u % r == 0] for r in R}
@lru_cache(maxsize=None)
def ends(r):
if not above[r]:
return frozenset([r])
out = set()
for u in above[r]:
out |= ends(u)
return frozenset(out)
return ends(s)
def section_o():
section("O floor 0: death needs only order")
rng = random.Random(2)
regions = []
for n in (60, 72, 210, 360):
ds = divisors(n)
regions += [(ds, s) for s in ds]
d360 = divisors(360)
for _ in range(200):
R = [1] + [d for d in d360[1:] if rng.random() < 0.5]
regions.append((R, 1))
multi = sum(len(interval_graves(R, s)) > 1 for R, s in regions)
print(f" {len(regions)} regions, {multi} with more than one grave")
R = [1, 2, 3]
ends = interval_graves(R, 1)
g = 1
while [u for u in R if u != g and u % g == 0]:
g = min(u for u in R if u != g and u % g == 0)
beta = 2.0
split = 2 ** -beta / (2 ** -beta + 3 ** -beta)
R8, A = divisors(8), {1: [2], 2: []}
walk = [1]
while A.get(walk[-1]):
walk.append(A[walk[-1]][0])
print(f" {{1, 2, 3}}: graves {sorted(ends)}, greedy dies at {g}, the "
f"thermal law at beta 2 sends {split:.4f} of worlds to 2; the "
f"run-dry walk on {R8} ends at {walk[-1]} below {max(R8)}")
check("O2 two graves on {1, 2, 3}, greedy ending at the cheaper",
sorted(ends) == [2, 3] and g == 2)
ok = True
walls = []
for s in (3, 5, 7):
L = growth.lam_int(s)
@lru_cache(maxsize=None)
def tends(M):
moves = [m for m in range(2, 2000) if M * m <= 10 ** 6
and growth.lam_int(M * m) == L]
if not moves:
return frozenset([M])
out = set()
for m in moves:
out |= tends(M * m)
return frozenset(out)
e = tends(s)
walls.append(sorted(e))
ok &= e == frozenset([growth.wall(L)])
print(f" transparency graves from 3, 5, 7: {walls}")
check("O3 every transparency walk ends at the one wall W(lambda(s))",
ok and walls == [[24], [240], [504]])
# ------------------------------------------------------ M floor 1
T = Fraction(1, 4)
def in_num23(k):
return k == 0 or k >= 2
def divides23(a, b):
return b >= a and in_num23(b - a)
def mass(pred, start, B):
"""sum of t^n over n >= start with pred(n) for n <= B, every n > B
assumed to satisfy pred."""
tot = sum((T ** n for n in range(start, B + 1) if pred(n)), Fraction(0))
return tot + T ** (B + 1) / (1 - T)
def section_m():
section("M floor 1: reaching everything needs only multiplication")
bad = eq = n = 0
for c in range(0, 13):
def inA(k, c=c):
return k >= 2 and not divides23(k, c)
B = c + 20
mA = mass(inA, 2, B)
for j in (2, 3, 4, 5, 7):
mAa = mass(lambda k: inA(k) and divides23(j, k), 2, B + j)
n += 1
bad += mAa < T ** j * mA
eq += mAa == T ** j * mA
check("M1 mass(A_c cap aM) >= w(a) mass(A_c) in NUM23, exactly",
bad == 0, f"{n} cells, {eq} with equality")
# ------------------------------------------------------ X the collapse
def atoms(k):
return frozenset(a for a in (2, 3) if k >= a and in_num23(k - a))
def section_x(control):
section("X the coprimality collapse")
check("X1 both atoms divide x^n for 5 <= n <= 200",
all(atoms(n) == {2, 3} for n in range(5, 201)))
walks = []
def go(k, acc):
moves = [n for n in range(2, 61) if not (atoms(n) & atoms(k))]
if not moves:
walks.append(tuple(acc))
return
for n in moves:
go(k + n, acc + [n])
go(0, [])
longest = max(len(w) for w in walks)
two = sorted(w for w in walks if len(w) == 2)
print(f" {len(walks)} maximal walks, the longest {longest}; "
f"length 2: {two}")
check("X2 every independence walk from the identity dies within two "
"moves", longest == 2 and two == [(2, 3), (3, 2), (3, 4), (4, 3)])
dirich = [1 if in_num23(n) else 0 for n in range(13)]
euler = [sum(1 for a in range(7) for b in range(5) if 2 * a + 3 * b == n)
for n in range(13)]
first = next(n for n in range(13) if dirich[n] != euler[n])
t = T
ds = 1 + t * t / (1 - t)
ep = 1 / ((1 - t * t) * (1 - t ** 3))
print(f" Dirichlet {dirich}\n Euler {euler}")
print(f" first difference at t^{first}, Euler minus Dirichlet "
f"{euler[first] - dirich[first]}; at t = 1/4: {ds} against {ep}")
check("X3 the Euler product leaves the Dirichlet sum at t^6; 13/12 "
"against 1024/945", control and first == 6
and euler[6] - dirich[6] == 1 and ds == Fraction(13, 12)
and ep == Fraction(1024, 945))
def main():
t0 = time.time()
control = section_c()
section_o()
section_m()
section_x(control)
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()