tower_rungs.py
Checks: TOWER: The first fourteen rungs property; TOWER: The transparency criterion criterion; TOWER: The fate rule rule; TOWER: The birthday formula theorem; observation; TOWER: The residue code's distance theorem; TOWER: The Hamming spectrum rule; TOWER: The unitary spectrum theorem; observation; TOWER: The escape law theorem; observation.
Cited on: TOWER.
To run it: save tower_rungs.py, with crt.py beside it; standard library only.
"""tower_rungs.py -- the primorial rungs one by one: the table, the
transparency criterion, the fate rule, the birthday formula, the
residue code's distance, the Hamming spectrum, the escape law and
the unitary spectrum.
QUESTION. The rung R_k = Z/p_k# is built from the first k primes, and
R_0 = Z/1. Rung k + 1 is rung k with one channel added and none removed.
What does that accumulation decide about which properties a rung has,
and when each property first appears or last holds?
DESIGN. Eight sections, each a set of checks that print PASS or FAIL.
T the table: N, phi and lambda for k = 1..14, computed with crt.py,
against the values written below; lambda read to k = 50.
C the transparency criterion: lambda(k) = lambda(k - 1) iff
(p_k - 1) | lambda(k - 1), lcm's definition and so not checked; the
transparent rungs among the first 14 checked against the list.
F the fate rule. A property of a rung that holds as soon as SOME
channel (or channel set) carries it can only be gained as channels
accumulate; one that needs EVERY channel to carry it can only be
lost. Each row of the chart but the code's (sieved, below) and the
code rate's (a formula in k) is computed per rung -- by brute force
over the ring's elements where the ring is small enough (k <= 6;
the zero-divisor row reads gcd(a, N) > 1 for each a, since a * N/g
= 0 with g = gcd(a, N), rather than searching every pair),
and by the row's criterion to k = 12. A criterion row is monotone
as written, so monotonicity is checked on the brute rows (k <= 6)
and on the code's row, read by the sieve below to k = 10. POSITIVE
CONTROL: the monotonicity checker
must flag a planted row that is neither ("k is even"). DESIGNED
TOWER CONTROL: on the rungs built from 2, 5, 13, 17, 29 (3 skipped,
every odd prime 1 mod 4) the square root of -1 must exist at every
rung, so the veto is the prime 3 and not the rule.
B the birthday formula: an element of multiplicative order m exists
in R_k iff m | lambda(k), so the first rung with one is the largest,
over the prime powers q^a exactly dividing m, of the rung of the
least prime = 1 mod q^a. Checked against a direct scan of lambda for
every m <= 200, and the achievable orders of R_k's units checked to
be exactly the divisors of lambda(k) by brute force, k <= 6.
D the residue code's distance: with r parity channels on rung k the
codewords are 0 .. p_{k-r}# - 1 (the range crt.py's code_range
gives, which D2 uses). Two
codewords agreeing on a channel set S differ by a multiple of the
product of S, so the distance is k minus the most channels any
difference d in 1 .. p_{k-r}# - 1 is divisible by. Computed
exhaustively by a multiples sieve over every d, k = 4..10 for
r = 2, 3 and k = 4..8 for r = 1 (one byte per d, so the range
p_{k-r}# is the footprint: p_9# = 223,092,870 is past it).
POSITIVE CONTROL: with the data put on the LARGEST
k - 3 primes instead, the sieve must find distance 2 (k = 5..8,
where 30 > p_k; at k = 10 that range would need a 215 MB sieve),
and with r = 1 (k = 3..7) or r = 2 (k = 4..8) on the largest, where
p_r# < p_k, distance 1.
THE SYNDROME'S SHAPE (crt.py code_syndrome): every codeword with
every single channel set to every wrong value, k = 4..7 and
r = 1..3 (r = 1 to k = 6), and the number of parity channels
whose check fails.
A wrong data channel i moves the integer the data channels read
by (p_{k-r}# / p_i) t with 0 < |t| < p_i; every parity prime is
coprime to that product and larger than p_i, so it divides no such
move, and every parity check fails. A wrong parity channel fails
only its own check.
POSITIVE CONTROL: with the data on the LARGEST k - 3 channels
(k = 5, 6), some single data error must pass a parity check; it
computes its syndrome inline, since code_syndrome puts the data on
the smallest moduli, so it controls the argument, not that function.
H the Hamming spectrum. The rung's Hamming graph joins two residues
that differ in exactly one channel: the Cartesian product of the
complete graphs K_p. K_p has eigenvalue p - 1 once (the constant
vector) and -1 on the p - 1 dimensions summing to zero, and a
Cartesian product's eigenvalues are sums, one term per factor. So
each subset S of the channels gives the eigenvalue
D - sigma(S), D = sum of (p - 1), sigma(S) = sum of S,
with multiplicity the product of p - 1 over S, and the distinct
eigenvalues are the distinct subset sums of the first k primes.
THE DEFICIT, proved before the run. Let T_k be the sum of the
first k primes and W_k the set of their subset sums. W_k is closed
under v -> T_k - v (take the complement). Claim: for k >= 4, W_k is
[0, T_k] minus {1, 4, 6} and their reflections. Checked directly
at k = 4 and k = 5. Step k -> k + 1 for k >= 5, with p = p_{k+1}:
W_{k+1} = W_k u (W_k + p). By induction W_k holds [7, T_k - 7], so
W_{k+1} holds [7, T_k - 7] u [p + 7, p + T_k - 7], which is all of
[7, T_{k+1} - 7] once p + 7 <= T_k - 6, that is p <= T_k - 13
(the STEP INEQUALITY). Below 7, W_{k+1} agrees with W_k, since
p >= 13; the top end follows by the reflection. The step
inequality holds at k = 5 (13 <= 15), and if it holds at k then
T_{k+1} - 2 p_{k+1} = T_k - p_{k+1} >= 13, so by Bertrand
p_{k+2} <= 2 p_{k+1} - 1 <= T_{k+1} - 14: it holds at every
k >= 5. So the rung's Hamming graph has exactly T_k - 5 distinct
eigenvalues at every k >= 4. At k = 4 the step inequality fails
(11 > 17 - 13), which is why k = 5 is a base case and not a step.
The checks: every eigenvector v_S (the product over S of the
vector 1 at 0, -1 at 1, 0 elsewhere, constant off S) satisfies
A v_S = (D - sigma(S)) v_S exactly, k = 3, 4, with the adjacency
read off the residue tuples and never off the formula; the whole
spectrum with its multiplicities at k = 3, 4 by closed walks: N
times the walks of length j from 0 back to 0 is the trace of A^j,
equal for every j <= N to the sum of multiplicity times
eigenvalue^j, and the power sums 0..N (the 0th the count N) fix
the N eigenvalues; the missing sums are computed by a bitset for
k = 3..60; the step inequality for k = 5..1999.
POSITIVE CONTROL: the set {2, 3, 5, 7, 11, 97}, whose last prime
breaks the step inequality, must show a missing sum in its middle.
E the escape law. A non-unit n of the rung has a NULL SET S, the
channels where n = 0; its CLASS is every residue with that null
set, prod of (p - 1) over the channels off S by CRT. A signed
generator step sends n to n + g or n - g, g one of the rung's
primes. Proved before the run: if g is in S no member escapes to
a unit (g | n + g). If g is off S, exactly
(g - 1) * prod over p off S, p != g, of (p - 2)
members land on a unit: off S the residues range over every tuple
of nonzero values once; a channel in S reads n + g = g, nonzero;
the channel g reads n + g = n, nonzero since g is off S, free
(g - 1 values); every other channel off S must avoid -g, p - 2 of
its p - 1 values. The step -g is the image under n -> -n. The
escape probability is one factor per channel,
prod over p off S, p != g, of (p - 2)/(p - 1).
Corollaries: the channel 2 contributes 2 - 2 = 0 whenever 2 is off
S and g is odd, so an odd non-unit escapes only by +-2 and an even
one never by +-2; the class {0} has no escape at all, and every
other class has one. From S = {q}, q odd, the +-2 probability is
the product over the odd channels but q; over all odd channels it
is A(k) = prod over 3 <= p <= p_k of (p - 2)/(p - 1), the chance
that z + 2 is a unit given z is. Since
(p - 2)/(p - 1) = (1 - 1/(p - 1)^2)(1 - 1/p),
A(k) is a partial product of the twin prime constant C2 times
prod over odd p of (1 - 1/p), which Mertens' theorem puts at
2 e^(-gamma) / ln p_k; so A(k) ln p_k / (2 C2 e^(-gamma)) -> 1.
The checks: every class and signed step, k = 3..7, counted from a
unit table and never from the formula; the corollaries; the stuck
non-units at k = 5 (a class-level law, not a per-element one);
the twin-unit count prod of (p - 2) at k = 7 by direct count,
which is the same escape count at S empty, the units, with g = 2,
the only check of that case; the ratio at k = 10, 100, 1000, 2000.
POSITIVE CONTROL: the formula with p - 1 in place of p - 2 must fail
somewhere.
U the unitary spectrum. The rung's UNITARY GRAPH joins two residues
whose difference is a unit, that is, that differ in EVERY channel:
the tensor product of the complete graphs K_p, whose eigenvalues
are products, one factor per channel, where H's were sums. The
same vectors v_S serve, with eigenvalue
e(S) = (-1)^|S| * prod over p off S of (p - 1),
multiplicity the product of p - 1 over S. Read as a character's
eigenvalue, with m = 0 exactly on the channels off S, e(S) is the
Ramanujan sum c_N(m), the sum of exp(2 pi i u m / N) over the units
u, and with g = gcd(m, N) it is mu(N/g) phi(g).
THE FIBRES, proved before the run. e(S) = e(S') iff |S| = |S'|
mod 2 and the products of p - 1 off S and off S' agree. The
channel 2 contributes p - 1 = 1, so moving 2 across S flips the
sign and keeps the size: the spectrum is +-U_k, where U_k is the
set of phi(d) over the squarefree d built from the odd primes to
p_k, and there are exactly 2 |U_k| distinct eigenvalues against
2^k sets S. Adding the next prime, p = p_k, gives U_k = U_(k-1) u
(p - 1) U_(k-1), so
|U_k| = 2 |U_(k-1)| - |U_(k-1) n (p - 1) U_(k-1)|,
and each value in that intersection is a COLLISION, a relation
phi(a) = (p - 1) phi(b) with a, b coprime and built from older
odd primes (common primes cancel, phi being multiplicative).
Where H's count is kept full by the primes' SIZE, this one is
thinned by the FACTORING of p - 1.
The checks: every v_S satisfies A v_S = e(S) v_S exactly, k = 3,
4, the adjacency read off gcd(n - n', N) = 1 and never off the
formula, and the multiplicities by closed walks as in H; c_N(m)
summed over the units in floats and rounded
equals mu(N/g) phi(g) at every m of Z/2310 and at every divisor
of 30030, with the rounding error printed; the distinct values
e(S) of all 2^k sets S number 2 |U_k|, k = 1..16 (read off the
formula the first checks test; the fibre criterion restates that
formula and is not checked); |U_k| by listing every subset
product, k = 2..20, with the collisions per rung and the least
relation of each printed (the recursion is an identity of sets).
POSITIVE CONTROL: the rule "distinct gcd, distinct eigenvalue",
which the fibre criterion denies, must fail at some k <= 16.
THE DOUBLING RUNG, added after the first print of U, which showed
rungs with no collision at all. Proved before its check: if p - 1
has a prime factor ell that divides no q - 1 over the older odd
primes q, that is, ell does not divide lambda(k - 1), then ell divides
every element of (p - 1) U_(k-1) and none of U_(k-1), so the
rung has no collision and |U_k| = 2 |U_(k-1)| exactly. The check
reads the collisions per rung by the recursion alone to k = 24,
against lambda kept as a running lcm, never against the rule. The
CONVERSE, no collision only at such a rung, is not proved; it is read off
the same column. It fails at k = 3, where 4 = 2^2 finds no partner
in U_2 = {1, 2}: the 2-adic valuation, not the prime, blocks it.
PREDICTIONS, fixed before the run.
T1 lambda for k = 1..10 is 1, 2, 4, 12, 60, 60, 240, 720, 7920, 55440
and stays 55440 through k = 14.
C1 the criterion holds at every k = 2..2000 (it is a property of lcm;
the check tests the implementation). Transparent rungs among the
first 14: k = 6 (13) and k = 11..14 (31, 37, 41, 43); k = 6 first.
F1 every row monotone in its direction; births and deaths: a field
dies at 2, the square root of -1 dies at 2, a cyclic unit group
dies at 3; zero divisors and idempotents beyond {0, 1} are born at
2, an element of order 4 at 3, of order 3 at 4, the distance-4
code at 4, a code rate above 1/2 at 7. The planted row is flagged.
The designed tower keeps its square root of -1 at all five rungs.
F2 the i pair: Z/30 has elements of order 4 and none squares to -1.
B1 formula = scan for every m <= 200; order 19 first at rung 43,
order 23 at rung 15, and the latest birthday for m <= 200 is
order 197's, at the prime 3547, rung 497. Unit orders = divisors of
lambda at every k <= 6.
D1 distance exactly r + 1 at every k in each r's range; the
control split has distance below 4 at every k = 5..8.
D2 a single wrong data channel fails all r parity checks and a single
wrong parity channel fails exactly its own, in every case.
The control finds a missed data error at k = 5 and at k = 6.
H1 every v_S is an eigenvector with eigenvalue D - sigma(S) at k = 3
and 4; the multiplicities sum to N; the least eigenvalue is -k,
with multiplicity phi(N) (92160 at k = 7).
H2 the missing subset sums are exactly {1, 4, 6, T - 6, T - 4, T - 1}
at every k = 4..60, so the distinct-eigenvalue count is T_k - 5
(53 at k = 7); at k = 3 the count is 7, not 10 - 5.
H3 the step inequality holds at every k = 5..2000 and fails at k = 4.
The control shows a missing sum strictly between 6 and its own
total less 6.
E1 the law is exact at every class and signed step, k = 3..7 (127
classes x 14 steps at k = 7); the control fails.
E2 odd class, odd step: 0 escapes; only the class {0} has no step
that escapes; at k = 5 some single non-units are stuck (every one
of their 2k neighbours a non-unit), 119 among them.
E3 22275 residues z of Z/510510 have z and z + 2 both units, and
A(7) = 22275/92160 = 0.2417.
E4 the ratio is within 2% of 1 at k = 1000 and k = 2000.
U1 every v_S is an eigenvector with eigenvalue e(S) at k = 3, 4;
the float Ramanujan sums round to mu(N/g) phi(g) everywhere, error
below 1e-6.
U2 no collision before p = 13: |U_k| = 2^(k-1) for k = 1..5, then
|U_6| = 26 (six relations, the least phi(21) = 12 * phi(1)), so
52 distinct eigenvalues at k = 6 against 64 sets. The brute
grouping agrees with 2 |U_k| and the criterion at every k <= 16;
the recursion agrees with the listing at every k <= 20.
U3 |U_k| / 2^(k-1) is nonincreasing (a property: |U_k| <=
2 |U_(k-1)|). Directional, a guess and not a derivation: it is
below 1/2 by k = 20. The observable is the printed ratio column.
U4 the control rule fails first at k = 6.
U5 (fixed after the first print of U, before its own run) every
rung whose p - 1 brings a new prime into lambda has no collision,
k = 2..24; the converse holds on k = 4..24 and fails at k = 3;
the doubling rungs to k = 24 are p = 3, 7, 11, 23, 29, 47, 53, 59
and 83.
FINDINGS. Every prediction landed; the audit in RUN RECORD replaced
the checks that held by construction, and the lines below are the
current run's (39/39).
T1 the table matches at k = 1..14; lambda is 55440 on k = 10..14 and
reads 1275120 at k = 15.
C1 1531 of the rungs 2..2000 are transparent; the transparent rungs
to 14 are 6, 11, 12, 13, 14, the primes 13, 31, 37, 41, 43.
F1 brute force agrees with every row's criterion at k <= 6; the brute
rows are monotone there and the code's sieved row to k = 10, each
row dying or born at the predicted rung; the planted row is
flagged; the designed tower keeps sqrt(-1) at all five
rungs. F2 the order-4 elements of Z/30 are 7, 13, 17, 23, and none
squares to 29.
B1 formula = scan at every m <= 200; order 19 at rung 43, order 23
at 15; the latest is order 197, prime 3547, rung 497; unit orders
are the divisors of lambda at k <= 6.
D1 distance 2, 3, 4 for r = 1, 2, 3 at every k checked; the control
split has distance 2 at k = 5..8; with the data on the largest
primes the distance is 1 at r = 1, k = 3..7 and r = 2, k = 4..8.
D2 every one of 223,922 single-channel errors has the predicted
syndrome: all r checks fail on a data error, one on a parity
error. The control misses 904 data errors at k = 5 and 20,684 at
k = 6 with the data on the largest primes.
H1 every v_S is an eigenvector with eigenvalue D - sigma(S) at k = 3
and 4, and the closed walks there give the whole spectrum with its
multiplicities; at k = 7 the formula gives 53 distinct
eigenvalues, the least -7 with multiplicity 92160.
H2 the missing sums are {1, 4, 6} and their reflections at every
k = 4..60 (k = 60: T = 7699, 7694 distinct). At k = 3 the missing
set is {1, 4, 6, 9}: the same union, the reflection of 4 being 6,
so the SET law holds from k = 3 and only the count T - 5 needs
k >= 4.
H3 the step inequality holds at k = 5..1999 and fails at k = 4; the
control misses 74 middle sums, the first 22.
E1 the law is exact at every class and signed step, k = 3..7 (127
classes x 14 steps at k = 7); the p - 1 control is wrong at 1428
class-steps.
E2 no odd step lifts an odd non-unit, and {0} is the one class with
no escape; at k = 5, 122 nonzero non-units are stuck, 119 among
them (117 = 3^2 13 and 121 = 11^2).
E3 22275 twin-unit residues at k = 7, A(7) = 0.241699.
E4 the ratio reads 0.9544, 0.9951, 0.9988, 0.9993 at k = 10, 100,
1000, 2000.
U1 every v_S is an eigenvector with eigenvalue e(S) at k = 3 and 4,
the closed walks giving the multiplicities there; the float
Ramanujan sums round to mu(N/g) phi(g) at every m of Z/2310 and
every divisor of 30030, worst error 5.6e-11.
U2 no collision to k = 5; |U_6| = 26, six collisions, the least
12 = 12 * 1; the distinct values of e(S) number 2 |U_k| to k = 16.
|U_k| by listing, for k = 6..20: 26, 50, 88, 176, 352, 576, 824,
1248, 2040, 4080, 8160, 16320, 21728, 34480, 53520.
U3 the share reads 0.1021 at k = 20: the directional guess (below
1/2) landed, first at k = 12 (0.4023; 0.5625 at k = 11).
U4 the control fails first at k = 6.
U5 every rung bringing a new prime into lambda has no collision,
k = 2..24; the rungs with none are p = 3, 5, 7, 11, 23, 29, 47, 53,
59, 83, and the converse fails only at k = 3; |U_24| = 326464,
share 0.0389.
Tiers: the table and the transparency criterion are properties; the
fate rule is a rule, proved, each row's fate read at its rungs by
brute force for k <= 6 and by the row's criterion to k = 12; the
birthday formula is a theorem, checked m <= 200; the code's distance
r + 1 is a theorem, checked exhaustively over the ranges above. The
deficit is a rule, proved for every k >= 4, its base cases k = 4, 5
computed. The escape law is a theorem, checked exhaustively at
k = 3..7; its limit is Mertens' theorem, read through one identity.
The unitary eigenvalues are Klotz and Sander's (Electron. J. Combin.
14 (2007) #R45); the fibre criterion, the recursion and the doubling
rung are theorems; the converse is an observation to k = 24, and the
share's fall one at k = 2..20, its value printed at k = 24.
RUN RECORD. The first run sieved r = 1 to k = 10 and peaked at 564 MB
commit (the 223 MB range at k = 10 and its slice copies), over the
512 MB line; r = 1 was cut to k = 8 and the increment moved to
bytes.translate. The recorded run: 16/16 PASS, 27 MB peak commit,
under a second. D2 was added later. Its first run covered r = 1 at
k = 7 as well (1,755,452 errors, all with the predicted shape, 4.8 s);
that row was dropped to keep the gate fast. The control was added
after that first D2 print had been read. The recorded run: 18/18 PASS,
27 MB peak commit, 0.8 s. H was added later, designed and proved
before its first run: 25/25 PASS, 27 MB peak commit, 1.0 s. E was
added after it the same way: 31/31 PASS, 29 MB peak commit, 2.0 s.
U was added after E, designed before its first run: 37/37 PASS, 29 MB
peak commit, 2.8 s. Its print showed rungs with no collision, and the
doubling rung was designed and predicted from it before its own run:
39/39 PASS, 74 MB peak commit, 2.8 s. An audit then cut the checks
that held by construction (C1's iff, the D1 witness pair, the fibre
criterion, the recursion's equality, U3's monotonicity, H1's k = 7
multiplicities, all now printed or proved) and added what tests the
graphs and the code: the spectra with their multiplicities by closed
walks at k = 3, 4, the distance-1 arms with the data on the largest
primes, distance exactly 2 in the control, monotonicity read on the
brute rows, the designed tower's criteria at k = 5, and each control
reported before its verdict: 38/38 PASS, 74 MB peak commit, 3.3 s,
under a memory guard. A second audit made the closed walks read the
power sums j = 0..N, since j < N leaves the last symmetric function
free, made each control (F1's planted row and designed tower, D1's
two, D2's, H3's, E1's, U4's) run before its verdict and stop the run
when it fails, and split U4's first failure at k = 6 into a verdict:
39/39 PASS, 2.6 s, 74 MB peak commit under a memory guard.
Standard library and crt.py.
python tower_rungs.py
"""
from fractions import Fraction
from math import cos, exp, gcd, lcm, log, pi, prod
from crt import (code_channels, code_range, code_syndrome, decode_from, encode,
first_primes, is_prime, multiplicative_order, primorial_ring)
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else ""))
def control(name, ok, detail=""):
"""A control: checked, and the run stops when it fails."""
check(name, ok, detail)
if not ok:
raise SystemExit(1)
PRIMES = first_primes(2000)
RUNG = {p: i + 1 for i, p in enumerate(PRIMES)} # prime -> its rung
LAM = [1] # LAM[k] = lambda(R_k)
for _p in PRIMES:
LAM.append(lcm(LAM[-1], _p - 1))
def primorial(k, primes=PRIMES):
return prod(primes[:k])
# ------------------------------------------------------------------ T
TABLE = { # k: (N, phi, lambda)
1: (2, 1, 1), 2: (6, 2, 2), 3: (30, 8, 4), 4: (210, 48, 12),
5: (2310, 480, 60), 6: (30030, 5760, 60), 7: (510510, 92160, 240),
8: (9699690, 1658880, 720), 9: (223092870, 36495360, 7920),
10: (6469693230, 1021870080, 55440),
11: (200560490130, 30656102400, 55440),
12: (7420738134810, 1103619686400, 55440),
13: (304250263527210, 44144787456000, 55440),
14: (13082761331670030, 1854081073152000, 55440),
}
def section_t():
print("T -- the first fourteen rungs")
print(f" {'k':>2} {'p_k':>4} {'N':>18} {'phi':>17} {'lambda':>7}")
ok = True
for k in range(1, 15):
R = primorial_ring(k)
print(f" {k:>2} {PRIMES[k - 1]:>4} {R.N:>18} {R.phi:>17} {R.lam:>7}")
ok &= (R.N, R.phi, R.lam) == TABLE[k] and R.lam == LAM[k]
check("T1 N, phi, lambda match the table, k = 1..14", ok)
print(" lambda, k = 1..50:", LAM[1:51])
# ------------------------------------------------------------------ C
def section_c():
print("C -- the transparency criterion")
# the iff is lcm's definition (a property): printed, not checked
n_trans = sum(LAM[k] == LAM[k - 1] for k in range(2, 2001))
print(f" transparent rungs among k = 2..2000: {n_trans}")
trans = [k for k in range(2, 15) if LAM[k] == LAM[k - 1]]
check("C1 transparent rungs k <= 14 are 6, 11, 12, 13, 14",
trans == [6, 11, 12, 13, 14],
"primes " + str([PRIMES[k - 1] for k in trans]))
# ------------------------------------------------------------------ F
def monotone(row, direction):
"""direction +1: never True then False; -1: never False then True."""
pairs = zip(row, row[1:])
if direction > 0:
return all(not (a and not b) for a, b in pairs)
return all(not (b and not a) for a, b in pairs)
def first(row, value):
"""1-based rung of the first entry equal to value, or None."""
return next((k for k, v in enumerate(row, 1) if v == value), None)
def brute(k, primes=PRIMES):
"""Element-by-element facts about the ring built from primes[:k]."""
N = primorial(k, primes)
units = [x for x in range(1, N) if gcd(x, N) == 1] if N > 1 else []
orders = {multiplicative_order(x, N) for x in units} if N > 2 else {1}
return {
"field": is_prime(N),
"sqrt(-1)": any(x * x % N == (N - 1) for x in range(N)),
"cyclic units": max(orders) == len(units) if units else True,
"zero divisors": any(gcd(a, N) > 1 for a in range(1, N)),
"idempotents beyond {0, 1}": sum(x * x % N == x for x in range(N)) > 2,
"order 4": 4 in orders,
"order 3": 3 in orders,
}
def criterion(k, primes=PRIMES):
"""The same rows by criterion, for any k."""
ps = primes[:k]
lam = lcm(*(p - 1 for p in ps)) if ps else 1
return {
"field": k == 1,
"sqrt(-1)": all(p == 2 or p % 4 == 1 for p in ps),
"cyclic units": lam == prod(p - 1 for p in ps),
"zero divisors": k >= 2,
"idempotents beyond {0, 1}": k >= 2,
"order 4": lam % 4 == 0,
"order 3": lam % 3 == 0,
}
def code_distance(k, r, data_primes=None):
"""Exhaustive minimum distance of the residue code on rung k with r
parity channels: k minus the most channels any difference d with
1 <= d < (data range) is divisible by, by a multiples sieve."""
ps = PRIMES[:k]
L = prod(data_primes) if data_primes else prod(ps[:k - r])
agree = bytearray(L)
for p in ps:
agree[p::p] = agree[p::p].translate(INCREMENT)
return k - max(agree[1:]) if L > 1 else None
INCREMENT = bytes(range(1, 256)) + bytes([255]) # saturates at 255
DIRECTION = {"field": -1, "sqrt(-1)": -1, "cyclic units": -1,
"zero divisors": 1, "idempotents beyond {0, 1}": 1,
"order 4": 1, "order 3": 1, "distance-4 code": 1,
"rate above 1/2": 1}
def section_f():
print("F -- the fate rule")
K = 12
bruted = [brute(k) for k in range(1, 7)]
crit = [criterion(k) for k in range(1, K + 1)]
agree = all(bruted[k - 1] == crit[k - 1] for k in range(1, 7))
check("F1 brute force equals the criteria, every row, k <= 6", agree)
rows = {name: [c[name] for c in crit] for name in crit[0]}
rows["distance-4 code"] = [k >= 4 and code_distance(k, 3) == 4
for k in range(1, 11)]
rows["rate above 1/2"] = [(k - 3) / k > 1 / 2 for k in range(1, K + 1)]
fates = {}
for name, row in rows.items():
d = DIRECTION[name]
fates[name] = ("born", first(row, True)) if d > 0 else ("dies", first(row, False))
print(f" {name:28} {fates[name][0]} at rung {fates[name][1]}")
# a criterion row is monotone as written (a prefix's all, an lcm's
# divisor); the rows that can fail are the brute ones and the sieve's
planted = [k % 2 == 0 for k in range(1, K + 1)]
control("F1 control: the planted row 'k is even' is flagged both ways",
not monotone(planted, 1) and not monotone(planted, -1))
ok = all(monotone([b[name] for b in bruted], DIRECTION[name])
for name in bruted[0])
ok &= monotone(rows["distance-4 code"], 1)
check("F1 the brute rows monotone in their direction, k <= 6, and the "
"code's sieved row, k <= 10", ok)
expected = {"field": 2, "sqrt(-1)": 2, "cyclic units": 3,
"zero divisors": 2, "idempotents beyond {0, 1}": 2,
"order 4": 3, "order 3": 4, "distance-4 code": 4,
"rate above 1/2": 7}
designed = (2, 5, 13, 17, 29)
dbrute = [brute(k, designed) for k in range(1, 6)]
ok = all(b["sqrt(-1)"] for b in dbrute)
ok &= all(dbrute[k - 1][n] == criterion(k, designed)[n]
for k in range(1, 6) for n in DIRECTION if n in crit[0])
control("F1 designed tower 2, 5, 13, 17, 29: sqrt(-1) at all five rungs, "
"brute force equal to the criteria there", ok)
check("F1 births and deaths at the predicted rungs",
all(fates[n][1] == r for n, r in expected.items()))
order4 = [x for x in range(30) if multiplicative_order(x, 30) == 4]
check("F2 the i pair: Z/30 has order-4 elements, none squares to -1",
order4 and all(x * x % 30 != 29 for x in order4), str(order4))
# ------------------------------------------------------------------ B
def prime_powers(m):
out, q = [], 2
while m > 1:
if m % q == 0:
qa = 1
while m % q == 0:
qa, m = qa * q, m // q
out.append(qa)
q += 1
return out
def least_prime_1_mod(n):
return next(p for p in PRIMES if p % n == 1)
def birthday_formula(m):
return max((RUNG[least_prime_1_mod(qa)] for qa in prime_powers(m)), default=0)
def birthday_scan(m):
return next(k for k, v in enumerate(LAM) if v % m == 0)
def section_b():
print("B -- the birthday formula")
ok = all(birthday_formula(m) == birthday_scan(m) for m in range(1, 201))
check("B1 formula = direct scan of lambda, every m <= 200", ok)
latest = max(range(1, 201), key=birthday_formula)
check("B1 order 19 at rung 43, order 23 at rung 15",
birthday_formula(19) == 43 and birthday_formula(23) == 15)
check("B1 latest birthday for m <= 200",
(latest, PRIMES[birthday_formula(latest) - 1], birthday_formula(latest))
== (197, 3547, 497),
f"order {latest}, prime {PRIMES[birthday_formula(latest) - 1]}, "
f"rung {birthday_formula(latest)}")
ok = True
for k in range(1, 7):
N = primorial(k)
orders = {multiplicative_order(x, N) for x in range(1, N) if gcd(x, N) == 1} \
if N > 2 else {1}
ok &= orders == {d for d in range(1, LAM[k] + 1) if LAM[k] % d == 0}
check("B1 unit orders = divisors of lambda, brute force, k <= 6", ok)
# ------------------------------------------------------------------ D
def section_d():
print("D -- the residue code's distance")
top = {1: 8, 2: 10, 3: 10}
dist = {r: {k: code_distance(k, r) for k in range(4, top[r] + 1)} for r in top}
for r in (1, 2, 3):
print(f" r = {r}: {dist[r]}")
ctrl = {k: code_distance(k, 3, PRIMES[3:k]) for k in range(5, 9)}
control("D1 control: data on the largest k - 3 primes, distance 2 at "
"k = 5..8, where 30 > p_k", all(d == 2 for d in ctrl.values()),
str(ctrl))
# the distance falls to 1 exactly when p_r# < p_k: r = 1 from k = 2,
# r = 2 from k = 4 (6 < 7), sieved at k = 3..7 and k = 4..8
low = {(r, k): code_distance(k, r, PRIMES[r:k])
for r, ks in ((1, range(3, 8)), (2, range(4, 9))) for k in ks}
control("D1 data on the largest primes, r = 1 at k = 3..7 and r = 2 at "
"k = 4..8: distance 1", all(d == 1 for d in low.values()),
str(sorted(set(low.values()))))
check("D1 distance exactly r + 1, k = 4..10 (r = 1: k = 4..8)",
all(d == r + 1 for r in dist for d in dist[r].values()))
missed = {}
for k in (5, 6): # control: data on the LARGEST primes
ring, r = primorial_ring(k), 3
data, parity = tuple(range(3, k)), (0, 1, 2)
span = prod(ring.moduli[i] for i in data)
missed[k] = 0
for n in range(span):
word = list(encode(n, ring))
for i in data:
for v in range(ring.moduli[i]):
if v != word[i]:
bad = word[:i] + [v] + word[i + 1:]
x = decode_from(bad, ring, data)
missed[k] += any((bad[j] - x) % ring.moduli[j] == 0
for j in parity)
control("D2 control: data on the largest primes, some data error "
"passes a parity check", all(missed.values()), str(missed))
shape, cases = True, 0
for k in range(4, 8):
ring = primorial_ring(k)
for r in ((1, 2, 3) if k < 7 else (2, 3)):
data, parity = code_channels(ring, r)
for n in range(code_range(ring, r)):
word = list(encode(n, ring))
for i, q in enumerate(ring.moduli):
for v in range(q):
if v == word[i]:
continue
bad = word[:i] + [v] + word[i + 1:]
fails = [j for j, s in zip(parity,
code_syndrome(bad, ring, r)) if s]
shape &= fails == (list(parity) if i in data
else [i])
cases += 1
check("D2 a wrong data channel fails every parity check, a wrong "
"parity channel only its own, k = 4..7, r = 1..3 (r = 1 to "
"k = 6)", shape,
f"{cases} single-channel errors")
# ------------------------------------------------------------------ H
def subset_sums(primes):
bits = 1
for p in primes:
bits |= bits << p
return {v for v in range(sum(primes) + 1) if bits >> v & 1}
def hamming_eigen_check(k):
"""A v_S = (D - sigma(S)) v_S for every S, adjacency off the tuples."""
from itertools import product
ps = PRIMES[:k]
D = sum(p - 1 for p in ps)
verts = list(product(*(range(p) for p in ps)))
ok = True
for mask in range(1 << k):
S = [i for i in range(k) if mask >> i & 1]
def v(t):
out = 1
for i in S:
out *= (1 if t[i] == 0 else -1 if t[i] == 1 else 0)
return out
lam = D - sum(ps[i] for i in S)
for t in verts:
av = sum(v(t[:i] + (u,) + t[i + 1:])
for i, p in enumerate(ps) for u in range(p) if u != t[i])
ok &= av == lam * v(t)
return ok
def formula_spectrum(k, value):
"""{eigenvalue: multiplicity} with value(S) per channel set S and
multiplicity the product of p - 1 over S."""
ps = PRIMES[:k]
mult = {}
for mask in range(1 << k):
S = [p for i, p in enumerate(ps) if mask >> i & 1]
lam = value(ps, S)
mult[lam] = mult.get(lam, 0) + prod(p - 1 for p in S)
return mult
def walk_spectrum_check(k, conn, mult):
"""The Cayley graph on Z/N with connection set conn: N times the
closed walks of length j at 0 is the trace of A^j, against the sum of
multiplicity times eigenvalue^j, for j <= N. Power sums 0..N (the
0th the count) fix a multiset of N values, so equality is the whole
spectrum."""
N = primorial(k)
v = [1] + [0] * (N - 1)
ok = True
for j in range(N + 1):
ok &= N * v[0] == sum(m * lam ** j for lam, m in mult.items())
v = [sum(v[(x - c) % N] for c in conn) for x in range(N)]
return ok
def hamming_value(ps, S):
return sum(p - 1 for p in ps) - sum(S)
def section_h():
print("H -- the Hamming spectrum")
check("H1 v_S has eigenvalue D - sigma(S), every S, k = 3, 4",
all(hamming_eigen_check(k) for k in (3, 4)))
ok = True
for k in (3, 4):
ps, N = PRIMES[:k], primorial(k)
conn = [c for c in range(1, N)
if sum(c % p != 0 for p in ps) == 1]
ok &= walk_spectrum_check(k, conn, formula_spectrum(k, hamming_value))
check("H1 the spectrum with its multiplicities, by closed walks, "
"k = 3, 4", ok)
mult = formula_spectrum(7, hamming_value)
print(f" k = 7 by the formula: {len(mult)} distinct, least "
f"{min(mult)} x {mult[min(mult)]}")
rows, ok = {}, True
for k in range(3, 61):
ps = PRIMES[:k]
T = sum(ps)
missing = sorted(set(range(T + 1)) - subset_sums(ps))
rows[k] = (T, T + 1 - len(missing), missing)
if k >= 4:
ok &= missing == [1, 4, 6, T - 6, T - 4, T - 1]
for k in (3, 4, 5, 7, 10, 60):
T, n, miss = rows[k]
print(f" k = {k:>2}: T = {T:>5}, distinct {n:>5}, missing {miss}")
check("H2 missing sums are {1, 4, 6} and reflections, k = 4..60",
ok and rows[7][1] == 53)
check("H2 k = 3 is outside: 7 distinct sums, not T - 5",
rows[3][1] == 7)
ctrl = [2, 3, 5, 7, 11, 97]
Tc = sum(ctrl)
gap = sorted(set(range(7, Tc - 6)) - subset_sums(ctrl))
control("H3 control {2, 3, 5, 7, 11, 97}: a middle sum is missing",
bool(gap), f"{len(gap)} middle sums missing, first {gap[:3]}")
step = [PRIMES[k] <= sum(PRIMES[:k]) - 13 for k in range(5, 2000)]
check("H3 step inequality p_{k+1} <= T_k - 13, k = 5..1999",
all(step))
check("H3 the step inequality fails at k = 4",
PRIMES[4] > sum(PRIMES[:4]) - 13)
# ------------------------------------------------------------------ E
def escape_predicted(ps, S, g):
if g in S:
return 0
return (g - 1) * prod(p - 2 for p in ps if p not in S and p != g)
def escape_counts(k):
"""{(S, step): members of class S that the step sends to a unit}."""
ps = PRIMES[:k]
N = prod(ps)
unit = bytearray(gcd(n, N) == 1 for n in range(N))
counts, sizes = {}, {}
for n in range(N):
if unit[n]:
continue
S = frozenset(p for p in ps if n % p == 0)
sizes[S] = sizes.get(S, 0) + 1
for g in ps:
for step in (g, -g):
key = (S, step)
counts[key] = counts.get(key, 0) + unit[(n + step) % N]
return ps, counts, sizes, unit
def section_e():
print("E -- the escape law")
ok, ctrl_fails, par, zero_only = True, 0, True, True
for k in range(3, 8):
ps, counts, sizes, unit = escape_counts(k)
for S, size in sizes.items():
ok &= size == prod(p - 1 for p in ps if p not in S)
for g in ps:
for step in (g, -g):
got = counts[(S, step)]
ok &= got == escape_predicted(ps, S, g)
ctrl = (0 if g in S else (g - 1) *
prod(p - 1 for p in ps if p not in S and p != g))
ctrl_fails += got != ctrl
if 2 not in S and g != 2:
par &= got == 0
any_escape = any(counts[(S, st)] for g in ps for st in (g, -g))
zero_only &= any_escape == (S != frozenset(ps))
print(f" k = {k}: {len(sizes)} classes x {2 * k} steps")
control("E1 control: p - 1 in place of p - 2 fails", ctrl_fails > 0,
f"{ctrl_fails} class-steps wrong")
check("E1 the escape law is exact, every class and signed step, "
"k = 3..7", ok)
check("E2 an odd step never lifts an odd non-unit; only {0} is "
"escape-free", par and zero_only)
ps, counts, sizes, unit = escape_counts(5)
N = prod(ps)
stuck = [n for n in range(N) if not unit[n] and n and
not any(unit[(n + st) % N] for g in ps for st in (g, -g))]
check("E2 k = 5: single non-units are stuck, 119 among them",
119 in stuck, f"{len(stuck)} stuck besides 0")
N7 = primorial(7)
unit7 = bytearray(gcd(n, N7) == 1 for n in range(N7))
twins = sum(unit7[n] and unit7[(n + 2) % N7] for n in range(N7))
A7 = Fraction(twins, 92160)
check("E3 k = 7: n, n + 2 both units for prod (p - 2) residues",
twins == prod(p - 2 for p in PRIMES[1:7]) == 22275,
f"{twins}, A(7) = {float(A7):.6f}")
C2 = 0.6601618158468696
ratios = {}
for k in (10, 100, 1000, 2000):
A = 1.0
for p in PRIMES[1:k]:
A *= (p - 2) / (p - 1)
ratios[k] = A * log(PRIMES[k - 1]) / (2 * C2 * exp(-0.5772156649015329))
print(" A(k) ln p_k / (2 C2 e^-gamma): "
+ ", ".join(f"k = {k}: {r:.4f}" for k, r in ratios.items()))
check("E4 the ratio is within 2% of 1 at k = 1000 and 2000",
all(abs(ratios[k] - 1) < 0.02 for k in (1000, 2000)))
# ------------------------------------------------------------------ U
def unitary_eigen_check(k):
"""A v_S = e(S) v_S for every S, adjacency off gcd(n - n', N) = 1."""
from itertools import product
ps = PRIMES[:k]
N = prod(ps)
verts = list(product(*(range(p) for p in ps)))
units = [u for u in range(N) if gcd(u, N) == 1]
tup = {n: tuple(n % p for p in ps) for n in range(N)}
index = {t: n for n, t in tup.items()}
ok = True
for mask in range(1 << k):
S = [i for i in range(k) if mask >> i & 1]
def v(t):
out = 1
for i in S:
out *= (1 if t[i] == 0 else -1 if t[i] == 1 else 0)
return out
e = (-1) ** len(S) * prod(p - 1 for i, p in enumerate(ps)
if i not in S)
vec = [v(t) for t in verts]
at = {index[t]: x for t, x in zip(verts, vec)}
for t, x in zip(verts, vec):
n = index[t]
ok &= sum(at[(n + u) % N] for u in units) == e * x
return ok
def mobius_phi(N, g):
"""mu(N/g) phi(g) for squarefree N and g | N."""
ps = [p for p in PRIMES if N % p == 0]
return prod(p - 1 if g % p == 0 else -1 for p in ps)
def ramanujan_float(N, m, units):
return sum(cos(2 * pi * u * m / N) for u in units)
def odd_values(k):
"""U_k by listing every subset product of p - 1, p odd, p <= p_k."""
vals = {1}
for p in PRIMES[1:k]:
vals |= {v * (p - 1) for v in vals}
return vals
def unitary_value(ps, S):
return (-1) ** len(S) * prod(p - 1 for p in ps if p not in S)
def section_u():
print("U -- the unitary spectrum")
check("U1 v_S has eigenvalue e(S), every S, k = 3, 4",
all(unitary_eigen_check(k) for k in (3, 4)))
ok = True
for k in (3, 4):
N = primorial(k)
conn = [u for u in range(N) if gcd(u, N) == 1]
ok &= walk_spectrum_check(k, conn, formula_spectrum(k, unitary_value))
check("U1 the spectrum with its multiplicities, by closed walks, "
"k = 3, 4", ok)
worst, ok = 0.0, True
for N, ms in ((2310, range(2310)),
(30030, [d for d in range(1, 30031) if 30030 % d == 0])):
units = [u for u in range(N) if gcd(u, N) == 1]
for m in ms:
x = ramanujan_float(N, m, units)
want = mobius_phi(N, gcd(m, N))
worst = max(worst, abs(x - want))
ok &= round(x) == want
check("U1 float Ramanujan sums = mu(N/g) phi(g), Z/2310 all m, "
"Z/30030 divisors", ok and worst < 1e-6, f"worst error {worst:.1e}")
# the fibre criterion restates the formula e(S), so it is not checked
# here; the count of distinct values against 2|U_k| is
ok_brute, first_fail = True, None
for k in range(1, 17):
ps = PRIMES[:k]
spec = {}
for mask in range(1 << k):
S = [p for i, p in enumerate(ps) if mask >> i & 1]
spec.setdefault(unitary_value(ps, S), []).append(mask)
ok_brute &= len(spec) == 2 * len(odd_values(k))
if first_fail is None and len(spec) < 1 << k:
first_fail = k
control("U4 control 'distinct gcd, distinct eigenvalue' fails at some "
"k <= 16", first_fail is not None,
f"first failure k = {first_fail}")
check("U4 the control fails first at k = 6", first_fail == 6)
check("U2 the distinct values of e(S) over all 2^k sets number "
"2|U_k|, k = 1..16", ok_brute)
# the recursion is |A u cA| = 2|A| - |A n cA|, an identity of sets:
# it prints the collisions; the listing's sizes are printed, and
# asserted at k = 5, 6
ratios = {}
prev = {1}
print(" k p |U_k| ratio collisions least relation")
for k in range(2, 21):
p = PRIMES[k - 1]
hit = prev & {v * (p - 1) for v in prev}
cur = odd_values(k)
ratios[k] = len(cur) / 2 ** (k - 1)
least = (f"{min(hit)} = {p - 1} * {min(hit) // (p - 1)}" if hit
else "-")
print(f" {k:>2} {p:>3} {len(cur):>7} {ratios[k]:>7.4f} "
f"{len(hit):>11} {least}")
prev = cur
check("U2 no collision to k = 5, |U_6| = 26",
len(odd_values(5)) == 16 and len(odd_values(6)) == 26)
print(f" U3 (directional): ratio at k = 20 is {ratios[20]:.4f}")
vals, lam, rows = {1}, 1, {} # U_1 and lambda(Z/2)
for k in range(2, 25):
p = PRIMES[k - 1]
hit = len(vals & {v * (p - 1) for v in vals})
new = any(lam % r for r in PRIMES[:k] if (p - 1) % r == 0)
rows[k] = (p, hit, new)
vals |= {v * (p - 1) for v in vals}
lam = lcm(lam, p - 1)
check("U5 a new prime in lambda means no collision, k = 2..24",
all(hit == 0 for p, hit, new in rows.values() if new))
quiet = [p for p, hit, new in rows.values() if hit == 0]
odd_ones = [k for k, (p, hit, new) in rows.items() if (hit == 0) != new]
print(f" no collision at p = {quiet}; converse fails at k = "
f"{odd_ones}; |U_24| = {len(vals)}, ratio "
f"{len(vals) / 2 ** 23:.4f}")
check("U5 converse holds on k = 2..24 but at k = 3",
odd_ones == [3])
def main():
for section in (section_t, section_c, section_f, section_b, section_d,
section_h, section_e, section_u):
section()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()