size.py
Checks: COORDINATES: The bearers theorem; SIZE: The locality criterion criterion; SIZE: The size wall theorem; SIZE: The hiding lemma theorem; SIZE: The half-coverage law theorem; SIZE: The conjunctive split theorem; SIZE: The least key theorem; SIZE: The additive labelling law theorem; SIZE: The F₂[x] control theorem.
Cited on: COORDINATES, SIZE.
To run it: save size.py; standard library only.
"""
size.py -- what a residue window cannot read about size, and what the
cheapest exact read of size costs.
USE. In Python, from the folder holding size.py. The
least key reads floor(x/m_k) and x mod m_k off a residue word alone,
and compare orders two words by it:
>>> from size import least_key, compare
>>> ms = (2, 3, 5, 7, 11, 13, 17) # Z/510510
>>> a = tuple(1000 % m for m in ms)
>>> b = tuple(999 % m for m in ms)
>>> least_key(a, ms) # 1000 = 17 * 58 + 14
(58, 14)
>>> compare(a, b, ms)
1
QUESTION. A residue window reads an integer x in [0, M) through its
residues x mod p at the places p of M. Which maps can such a window
compute channel by channel, why is size (sign, comparison, overflow)
not among them, how completely is size hidden from a proper window,
and what is the least a reader must add to compare two residue words
exactly? Which of these answers are about windows, and which are about
the archimedean place the integers happen to have?
THE ARGUMENT (written before this script).
(1) THE LOCALITY CRITERION. Call F : R -> R on a finite ring
R = K_1 x ... x K_k (a product of finite fields: a squarefree
Z/M, or F_2[x]/f with f squarefree) CHANNEL-LOCAL when the i-th
component of F(x) depends only on the i-th component of x. Then
F is channel-local iff it is a polynomial function. A polynomial
is evaluated componentwise; conversely each component map
K_i -> K_i is a Lagrange polynomial of degree < |K_i|, and the
coefficients glue degree by degree by the CRT. The same proof
runs in several variables. The equivalence needs the fields:
over Z/8 the channel-local maps (value mod 2 fixed by argument mod 2)
number 2^2 * 4^8 = 262,144, and the polynomial maps are Kempner's
8 * 8 * 4 * 4 = 1,024.
(2) THE SIZE WALL. Read x as its least residue. For every prime
p | M with p < M, sign(x) = [x >= M/2] is not channel-local at p:
0 and b = p * ceil(M/(2p)) agree mod p, and M/2 <= b <= M - 1
because p <= M/2. The same pair walls comparison [x < y] (at
(0, 0) against (0, b)) and overflow [x + y >= M] (at (0, 0)
against (b, b)). A channel-local bijection T has a channel-local
inverse, so sign o T is channel-local at no prime p | M below M
either: no channel-local change of coordinates, linear or not,
exposes size.
(3) THE HIDING LEMMA. In any cyclic Z/M, knowing x mod W for a proper
divisor W of M leaves x on the ladder r + jW, j < c = M/W.
Exactly c/2 of the ladder sits at or above M/2 when c is even; when
c is odd it is (c - 1)/2 or (c + 1)/2 as r < W/2 or not. So the
sign bit's bias in every fiber is exactly 0 or exactly half an
element, 0 iff c is even. Cyclic orientation is hidden totally:
translate a triple's base point to 0, where orientation is integer
comparison on (0, M); each ladder holds an element <= W and one
>= (c - 1)W, so the extreme completions give both orientations,
unless both ladders are {W} at c = 2 (no distinct triple).
(4) THE HALF-COVERAGE LAW. Read x in [1, X] through x mod Q, for any
Q <= X. The fiber of x has one lift iff x - Q < 1 and x + Q > X,
so exactly max(0, 2Q - X) elements are determined. Every fiber's
least lift is <= Q and its greatest is > X - Q, so two fibers can
be ordered with certainty only if X - Q + 1 <= a < b <= Q for
some lifts, which needs 2Q - X >= 2; conversely at 2Q - X >= 2
the elements X - Q + 1 and X - Q + 2 are both determined. At a
divisor Q | X, Q < X, the best guess of [a < b] from the residues
(order the residues) is right on exactly X(X + Q - 2)/2 of the
X(X - 1) ordered pairs of distinct elements, half of them at
Q = 1: order leaks at every Q >= 2 while certainty waits for
half.
(5) THE RELATIONAL FORM. A relation R on Z/M is CONJUNCTIVE when it
equals the conjunction of its projections to the channels.
Equality is; divisibility is (x | y iff y_p = 0 wherever x_p = 0,
channel by channel); the order x <= y is not, and fails
maximally: every projection is all of F_p x F_p (take
x < p <= y <= 2p - 1, in range when M >= 2p), so the conjunction is
everything. Conjunctive iff R is a rectangle (rank 1) at every
split of one channel against the rest: a set equal to the
product of its projection and its co-projection for every
coordinate is the product of all its projections (replace one
coordinate at a time).
(6) THE EXACT COMPARATOR. Pairwise coprime moduli m_1 < ... < m_k,
M their product, S = sum M/m_i, D(x) = sum floor(x/m_i) on
[0, M). (i) gcd(M, S) = 1: modulo a prime of m_i every term but
M/m_i carries m_i. (ii) M * D(x) = S * x - sum (M/m_i) x_i, so
D(x) = -M^(-1) sum (M/m_i) x_i mod S, and 0 <= D <= S - k: one dot
product of the residues mod S reads D exactly. (iii)
D(x + 1) - D(x) counts the moduli dividing x + 1. So inside a run
where D is constant no modulus divides a later element, every
residue x mod m_j climbs by one without wrapping, and the run has
at most m_1 elements. Hence key_j(x) = (D(x), x mod m_j) is strictly
increasing on [0, M) for EVERY j: an exact comparator, with sign
one compare against key_j(ceil(M/2)) and the overflow of x + y the
compare key_j(z) < key_j(x), z = x + y mod M. D alone ties exactly
the pairs inside one run; the adjacent ties are the x with no
modulus dividing x + 1, M prod (1 - 1/m_i) of them, phi(M) when
every modulus is prime.
(7) THE COST LAW. The comparator's dot product is reduced mod S and
reconstruction's mod M, and S / M = sum 1/m_i. So it is narrower
iff sum 1/m_i < 1, and S = M never happens, by (i). The primorial
rungs fail from k = 3 on (1/2 + 1/3 + 1/5 = 31/30), k = 2 passes
(5/6). The Fermat numbers are pairwise coprime with
sum 1/F_n < 0.5961, so every set of them passes. A strictly
monotone characteristic on [0, M) takes M values, so a
characteristic comparator computing below log2 M bits must be a
non-injective form plus a tie-break (pigeonhole).
(8) THE F_2[x] CONTROL. Over the ring F_2[x]/f, f squarefree with
two or more factors, read a as its representative of degree
< deg f. The criterion (1) holds verbatim. The top degree bit
[deg a = deg f - 1] is channel-local at no channel f_i (0 against
f_i * x^(deg f - 1 - deg f_i)), so the information core of the
wall is unchanged. What goes is three things the Z side has: (a)
every fiber of a proper window g | f is a coset r + g * P, P the
polynomials of degree < deg f - deg g, and exactly half of it has top
bit 1, so the bias is 0 at EVERY proper window (over Z it is half
an element whenever M/W is odd); (b) the degree of a product is
the sum of the degrees, no carry; (c) the partial-fraction read is exact or flags itself.
With a/f = sum b_i / f_i (b_i = a * (f/f_i)^(-1) mod f_i), sum of
proper fractions being proper, the t leading Laurent coefficients
add without carries: sum_i (b_i x^t div f_i) = (a x^t) div f. That
quotient is either nonzero, and its degree gives deg a exactly, or
zero, which says deg a < deg f - t. Over Z the t-bit truncation of
y/M = frac(sum y_i w_i / m_i), y_i = y mod m_i, w_i = (M/m_i)^(-1)
mod m_i, can wrap below 0 and read a small y as a large one, with
no flag. (Settled
later, on an audit: this control does not say which difference
between Z and F_2[x] owns (a) to (c). The two differ in the
archimedean place and in the characteristic. Carries belong to
characteristic 0, the 2-adic integers carrying too. (a) was first
read as the fiber size 2^e being even; the F_3[x] arm below,
added later, reads it again. Measured against the ring's
own share, a fiber's degree profile above deg g is the same for
every r at every q, since deg(r + g*P) = deg g + deg P for P != 0:
the ultrametric inequality of the place degree reads. PREDICTION,
fixed before that arm ran: at f = x(x + 1)(x^2 + 1)(x^2 + x + 2)
over F_3, every fiber of all 15 proper windows has one profile.)
(9) THE LEAST COMPARATOR (added after the first run, on reading
Babenko, Piestrak, Chervyakov and Deryabin, Electronics 10 (2021)
1041, in full). A key (G(x), x mod m_j) injective on [0, M) needs
G to take at least M/m_j values, since the M/m_j elements of one
residue class mod m_j must get distinct G: the pigeonhole floor,
for ANY G. G = floor(x/m_j) attains it, and it is one dot product
of the residues mod M/m_j: floor(x/m_j) = (B - x_j) * m_j^(-1) mod
M/m_j, B the CRT value of the other residues mod M/m_j. The key
is then x itself in mixed radix, strictly increasing, and the
largest modulus m_k gives the least range. The paper works with
core functions, weighted sums of the quotients
floor(x/m_i); it calls this one the minimum-range
monotonic core function and shows the diagonal D is the core
function with every weight equal to 1. Since
S = sum M/m_i > M/m_1 >= M/m_k, the diagonal is never the least:
the cost law (7) compares D with the wrong rival. The least key's
first coordinate is a reconstruction of x modulo every modulus
but the largest.
PREDICTION (fixed before the second run): at the four sets of D,
floor(x/m_k) by the dot product equals the direct quotient at
every x in [0, M), and M/m_k < S at each.
THE KEY AS A TOOL. least_key(residues, ms) takes one residue
word, pairwise coprime moduli in any order, and returns
(floor(x/m_k), x mod m_k) from the residues alone;
compare(a, b, ms) returns -1, 0 or 1 as the integers the two
words name compare. Nothing else is read: the quotient is the dot
product above, the CRT coefficients rebuilt per call (the calls
are shown under USE at the head of this docstring).
PREDICTION (fixed before the third run): at each of the four sets
of D, on 2000 seeded pairs and every pair of the corners 0, 1,
m_k - 1, m_k, M - 2, M - 1, compare agrees with integer
comparison and least_key's two coordinates rebuild x as
m_k * q + r; the words also pass in reversed modulus order.
(10) THE ADDITIVE LABELLING (added later, on the question of a small
size labelling). A LABELLING is a map mu : [0, N) -> L,
|L| = s < N; it is ADD-UPDATABLE when some A : L x L -> L has
mu(x + y) = A(mu(x), mu(y)) whenever x + y < N. Then mu(x + 1) =
g(mu(x)) with g = A(., mu(1)), so mu is the orbit of mu(0) under
one self-map of an s-set: injective on a prefix [0, x0) and
periodic with period d from x0 on, x0 + d <= s. Conversely each
such pair is the congruence of (N, +) with index x0 and period d,
a monoid congruence, so it is add-updatable; for N > s the pairs
give distinct labellings, and up to relabelling there are exactly
s(s + 1)/2 of them, one for each x0 >= 0, d >= 1 with x0 + d <= s.
The congruence respects multiplication too (x = y mod d, both
>= x0, gives xz = yz mod d with both >= x0, or both 0), so every
add-updatable labelling is mul-updatable for free. Labels (a, b)
are ORDER-INFORMATIVE when every value labelled a lies below
every value labelled b. Every label first appears below x0 + d,
so an informative b has least value at most s - 1; and for
values u < v both at or above s, v's label already labels a value
below x0 + d <= s <= u, so no such pair is ordered by its labels,
at every N > s.
PREDICTION (fixed before section A ran): a depth-first search over
every labelling, labels in first-occurrence order and A filled in
as the search goes, no shape assumed, finds exactly s(s + 1)/2
add-updatable labellings at every N in {8, 10, 12, 14} and s in
{2, 3, 4, 5}; each is a rho with x0 + d <= s and is
mul-updatable; the largest least value of an informative b is
s - 1; and where N >= 2s no pair of values at or above s has an
informative pair of labels.
PREDICTIONS (fixed before the run). Every check prints PASS. Counts:
Z/6 has 108 channel-local maps, all polynomial; Z/4 64 of 64; Z/8
1,024 polynomial of 262,144 channel-local; F_2[x]/(x(x+1)) 16 = 16;
F_2[x]/(x(x^2+x+1)) 1,024 = 1,024; F_2[x]/x^2 64 of 64; F_2[x]/x^3
1,024 of 262,144. The run over {97, 101, 103} reaches 97 elements.
At Z/510510 the D-only ties number phi = 92,160. A Z witness of the
silent wrap exists at t = 16 bits among x <= 1000 at Z/510510.
DESIGN. Sections of checks printing PASS or FAIL, a control first
where a check could pass vacuously.
L the locality criterion: exhaustive at Z/6; span counts at Z/4,
Z/8 and four F_2[x] quotients, against channel-local totals that
are the channels' map counts multiplied by hand; the Lagrange +
CRT lift in one and two variables at Z/30 on seeded random maps.
W the size wall: the witness b, 0 mod p, in [M/2, M) by its own
arithmetic (argued, the pairs to M <= 300 counted); sign o T for
seeded channel-local bijections T of Z/30.
H the hiding lemma: every fiber of every proper window of every
Z/M, M <= 240 (the high count c/2 at even c, (c - 1)/2 plus
[r >= W/2] at odd c); orientation at every M <= 60 and every
proper W, both orientations in every class but the antipodal one.
C the half-coverage law: singles at X <= 240, counted from each
residue class's lifts, pairs at X <= 120, the accuracy count at
every divisor budget X <= 120.
R the relational form at Z/210 (equality, divisibility, order) and
the rectangle criterion at Z/30 on the same three relations;
after the audit, betweenness as a
ternary relation at Z/6 and Z/30 in place of its base-0
identity.
D the comparator: gcd(M, S) = 1 on seeded random coprime sets; the
dot-product formula for D at 2000 seeded x at Z/510510,
{3, 5, 17, 257}, {97, 101, 103} and the composite set
{15, 77, 221}, the longest run of constant D printed (the
strictness of every key_j and the run's length m_1 are (6)(iii)'s
argument, holding by D's definition, and are not checked); the
D-only ties; sign and overflow at Z/210 exhaustively.
K the cost law: the rung sums (S/M is the same sum, printed at
k = 2, 3, 7), the Fermat sum, two designed sets.
Q the least comparator (added after the first run): the dot
product for floor(x/m_k) at every x of the four sets of D, and
M/m_k < S; the tool (added later): least_key and
compare on residue words at seeded pairs and corners. Its two
controls run first, with A's, and stop the run if one fails:
words read against the wrong modulus order must mis-compare, and
one modulus keys a word by its residue.
A the additive labelling (added with (10)): the search over every
labelling at the sixteen cells, the rho, the free multiplication,
the height and the blind tail.
F the F_2[x] control at f = x(x+1)(x^2+x+1)(x^3+x+1)(x^3+x^2+1),
degree 10: the factors' irreducibility (the degree wall is (8)'s
argument), the zero bias at all 31 proper
windows, deg(ab), the exact-or-flagged read at every a and every
t from 1 to 10; and the Z wrap witness at Z/510510.
RUN RECORD. First run: 46 of 46 PASS, every prediction met. Z/6 108
channel-local, 108 polynomial of 46,656; Z/8 1,024 of 262,144;
F_2[x]/x^3 1,024 of 262,144; the two squarefree F_2[x] quotients 16 = 16
and 1,024 = 1,024. The runs of D reach 2, 3, 97 and 15 at the four sets,
each its m_1. Z/510510's D-only ties are 92,160 = phi. The orientation sweep
met 15,475 base-0 classes, and the 29 without a distinct triple are the
antipodal ones, one per even M from 4 to 60. The Z wrap's first witness is
x = 1: its 16-bit truncated sum lands past one half. Second run, after
the source read that added (9): 50 of 50 PASS. The least range M/m_k
against the diagonal's S: 30,030 against 716,167 at Z/510510, 255 against
39,062 at {3, 5, 17, 257}, 9,797 against 30,191 at {97, 101, 103}, and
1,155 against 21,487 at {15, 77, 221}. Wall 2.8 s, peak 79 MB. After
the audit, 51 of 51: betweenness as a ternary relation, 60 triples
with a closure of 192 at Z/6 and 12,180 with 27,000 at Z/30. Then 52
of 52: the F_3[x] arm finds one degree profile per window at
all 15 proper windows, as predicted. With (10), 54 of 54: the search
finds x mod 3 and rejects [x >= 3] at N = 8, and returns 136 labellings
over the sixteen cells, s(s + 1)/2 at each, every one a rho with
x0 + d <= s, mul-updatable and blind at and above s where N >= 2s, the
largest least value of an informative label s - 1 at every cell. Wall
2.8 s, peak 81 MB. (A later proof read found N >= 2s idle: the
blindness holds at every N > s, and the check now covers the one
cell it skipped, (8, 5); still 54 of 54.) With the tool, 59 of 59:
the one-modulus control, and compare and least_key right at 2,036
pairs per set, each in both modulus orders, as predicted; the usage
lines, run by hand, give (58, 14) and 1. Wall 2.9 s. After a code
read, 51 of 51: checks that held by construction were cut (every key_j's
strictness and the longest run of D, now argued and printed; S < M iff
the rung sum < 1, now printed; the size wall's witness b and the degree
wall's), the controls run first and stop the run on a failure, the
wrong-order words mis-comparing at 404 of 900 pairs of Z/30; the bias is
now read with its sign, the singles from the residue classes' lifts,
betweenness's closure holding all 60 and 12,180 triples of the other
orientation, and the five factors irreducible. Wall 2.6 s, peak 75 MB.
With a check of the tie count at composite moduli, 52 of 52: at
{15, 77, 221} D ties 234,080 adjacent pairs, M prod (1 - 1/m_i),
against phi(M) = 92,160, where (6) had said the ties were the x with
x + 1 prime to M. Wall 2.5 s, peak 75 MB.
Run: python size.py (a few seconds, under 100 MB)
"""
import random
from fractions import Fraction
from itertools import product
from math import gcd, prod
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
tail = f" ({detail})" if detail else ""
print(f" {'PASS' if ok else 'FAIL'} {name}{tail}")
def primes_of(n):
out, d = [], 2
while d * d <= n:
if n % d == 0:
out.append(d)
while n % d == 0:
n //= d
d += 1
if n > 1:
out.append(n)
return out
def phi(n):
r = n
for p in primes_of(n):
r = r // p * (p - 1)
return r
# ---------------------------------------------------------------- rings
# A finite commutative ring as elements 0..q-1 with add and mul tables
# built from a rule; F_2[x] elements are ints read as bit polynomials.
def clmul(a, b):
r = 0
while b:
if b & 1:
r ^= a
a <<= 1
b >>= 1
return r
def pdeg(a):
return a.bit_length() - 1
def pmod(a, f):
df = pdeg(f)
while a and pdeg(a) >= df:
a ^= f << (pdeg(a) - df)
return a
def pdivmod(a, f):
q, df = 0, pdeg(f)
while a and pdeg(a) >= df:
s = pdeg(a) - df
q ^= 1 << s
a ^= f << s
return q, a
def pinv(a, f):
"""Inverse of a modulo f in F_2[x] (a prime to f)."""
r0, r1, s0, s1 = f, pmod(a, f), 0, 1
while r1:
q, r = pdivmod(r0, r1)
r0, r1 = r1, r
s0, s1 = s1, s0 ^ clmul(q, s1)
assert r0 == 1
return pmod(s0, f)
class Ring:
def __init__(self, name, q, add, mul):
self.name, self.q = name, q
self.els = range(q)
self.add = [[add(a, b) for b in self.els] for a in self.els]
self.mul = [[mul(a, b) for b in self.els] for a in self.els]
def zmod(n):
return Ring(f"Z/{n}", n, lambda a, b: (a + b) % n,
lambda a, b: a * b % n)
def f2quot(f, label):
return Ring(label, 1 << pdeg(f), lambda a, b: a ^ b,
lambda a, b: pmod(clmul(a, b), f))
def poly_function_span(R):
"""All polynomial functions R -> R, as tuples: the R-span of the
power functions x^j, taken until the powers repeat."""
powers, seen = [], set()
cur = tuple(1 for _ in R.els)
while cur not in seen:
seen.add(cur)
powers.append(cur)
cur = tuple(R.mul[cur[a]][a] for a in R.els)
span = {tuple(0 for _ in R.els)}
for g in powers:
mults = {tuple(R.mul[c][v] for v in g) for c in R.els}
span = {tuple(R.add[s[a]][m[a]] for a in R.els)
for s in span for m in mults}
return span
# ------------------------------------------------------------ section L
CHANNEL_MAPS = {
"Z/4": [lambda a: a % 2],
"Z/8": [lambda a: a % 2],
"F2[x]/(x(x+1))": [lambda a: pmod(a, 0b10), lambda a: pmod(a, 0b11)],
"F2[x]/(x(x^2+x+1))": [lambda a: pmod(a, 0b10),
lambda a: pmod(a, 0b111)],
"F2[x]/x^2": [lambda a: pmod(a, 0b10)],
"F2[x]/x^3": [lambda a: pmod(a, 0b10)],
}
def lagrange_crt_lift(M, table):
"""Given a channel-local map on squarefree Z/M (as a table of
values), build one polynomial with coefficients mod M by Lagrange
on each channel and CRT glue per degree; return its coefficients."""
ps = primes_of(M)
deg = max(ps)
coeffs_by_p = {}
for p in ps:
g = [table[x] % p for x in range(p)] # the channel map
c = [0] * p
for a in range(p):
if g[a] == 0:
continue
# basis polynomial prod_{b != a} (x - b)/(a - b) over F_p
basis = [1]
den = 1
for b in range(p):
if b == a:
continue
basis = [((basis[i - 1] if i > 0 else 0)
- b * (basis[i] if i < len(basis) else 0)) % p
for i in range(len(basis) + 1)]
den = den * (a - b) % p
s = g[a] * pow(den, -1, p) % p
for i, v in enumerate(basis):
c[i] = (c[i] + s * v) % p
coeffs_by_p[p] = c
out = []
for j in range(deg):
# CRT: the coefficient mod M agreeing with each channel's
val = 0
for p in ps:
cj = coeffs_by_p[p][j] if j < p else 0
e = (M // p) * pow(M // p, -1, p)
val = (val + cj * e) % M
out.append(val)
return out
def lift2(M, table2):
"""Two-variable version: the channel map of (x, y) is a Lagrange
polynomial in x and y over F_p; glue per bidegree by the CRT."""
ps = primes_of(M)
deg = max(ps)
coef = {}
for p in ps:
c = [[0] * p for _ in range(p)]
inv = {}
for a in range(p):
basis, den = [1], 1
for b in range(p):
if b == a:
continue
basis = [((basis[i - 1] if i > 0 else 0)
- b * (basis[i] if i < len(basis) else 0)) % p
for i in range(len(basis) + 1)]
den = den * (a - b) % p
inv[a] = [v * pow(den, -1, p) % p for v in basis]
for a in range(p):
for b in range(p):
g = table2[(a, b)] % p
if g == 0:
continue
for i, u in enumerate(inv[a]):
for j, v in enumerate(inv[b]):
c[i][j] = (c[i][j] + g * u * v) % p
coef[p] = c
out = [[0] * deg for _ in range(deg)]
for i in range(deg):
for j in range(deg):
val = 0
for p in ps:
cij = coef[p][i][j] if i < p and j < p else 0
e = (M // p) * pow(M // p, -1, p)
val = (val + cij * e) % M
out[i][j] = val
return out
def section_l():
print("L the locality criterion")
# exhaustive at Z/6: all 6^6 maps
local = poly = 0
inside = True
span = poly_function_span(zmod(6))
for F in product(range(6), repeat=6):
is_local = all(F[a] % p == F[a % p] % p
for p in (2, 3) for a in range(6))
local += is_local
poly += F in span
inside &= is_local or F not in span
check("Z/6: channel-local maps = polynomial maps, exhaustive",
inside and local == poly == 108,
f"{local} channel-local, {poly} polynomial of 46656")
# counts elsewhere: channel-local by construction, polynomial by span
cases = [
(zmod(4), 2 ** 2 * 2 ** 4, 64),
(zmod(8), 2 ** 2 * 4 ** 8, 1024),
(f2quot(0b110, "F2[x]/(x(x+1))"), 2 ** 2 * 2 ** 2, 16),
(f2quot(clmul(0b10, 0b111), "F2[x]/(x(x^2+x+1))"),
2 ** 2 * 4 ** 4, 1024),
(f2quot(0b100, "F2[x]/x^2"), 2 ** 2 * 2 ** 4, 64),
(f2quot(0b1000, "F2[x]/x^3"), 2 ** 2 * 4 ** 8, 1024),
]
for R, n_local, n_poly in cases:
span = poly_function_span(R)
# the channel of the value: the residue mod the one prime (Z/4,
# Z/8, F_2[x]/x^k) or mod each factor; checked on the span
chans = CHANNEL_MAPS[R.name]
inside = all(all(ch(F[a]) == ch(F[b]) for ch in chans
for a in R.els for b in R.els if ch(a) == ch(b))
for F in span)
check(f"{R.name}: {len(span)} polynomial of {n_local} channel-local"
f" (counted by hand), each channel-local",
len(span) == n_poly and inside)
# constructive lift at Z/30, one and two variables
rng = random.Random(30)
ok = True
for _ in range(100):
chan = {p: [rng.randrange(p) for _ in range(p)] for p in (2, 3, 5)}
table = []
for x in range(30):
v = sum(chan[p][x % p] * (30 // p) * pow(30 // p, -1, p)
for p in (2, 3, 5)) % 30
table.append(v)
c = lagrange_crt_lift(30, table)
ok &= all(sum(cj * pow(x, j, 30) for j, cj in enumerate(c)) % 30
== table[x] for x in range(30))
check("Z/30: 100 seeded channel-local maps lift to one polynomial", ok)
ok = True
for _ in range(20):
chan = {p: {(a, b): rng.randrange(p) for a in range(p)
for b in range(p)} for p in (2, 3, 5)}
table2 = {}
for x in range(30):
for y in range(30):
table2[(x, y)] = sum(
chan[p][(x % p, y % p)] * (30 // p)
* pow(30 // p, -1, p) for p in (2, 3, 5)) % 30
c = lift2(30, table2)
ok &= all(sum(c[i][j] * pow(x, i, 30) * pow(y, j, 30)
for i in range(5) for j in range(5)) % 30
== table2[(x, y)] for x in range(30) for y in range(30))
check("Z/30: 20 seeded two-variable channel-local maps lift", ok)
# ------------------------------------------------------------ section W
def section_w():
print("W the size wall")
count = 0
for M in range(4, 301):
for p in primes_of(M):
if p == M:
continue
count += 1
# the witness b = p ceil(M/(2p)) lies in [M/2, M) for every p < M by
# its own arithmetic (the proof's step), so it is not checked
print(f" the witness b at {count} (M, p) pairs, M <= 300: argued")
rng = random.Random(7)
ok = True
for _ in range(30):
perms = {p: rng.sample(range(p), p) for p in (2, 3, 5)}
T = [sum(perms[p][x % p] * (30 // p) * pow(30 // p, -1, p)
for p in (2, 3, 5)) % 30 for x in range(30)]
assert sorted(T) == list(range(30))
sT = [int(2 * T[x] >= 30) for x in range(30)]
ok &= all(any(sT[a] != sT[b] for a in range(30) for b in range(30)
if a % p == b % p) for p in (2, 3, 5))
check("sign o T channel-local at no channel, 30 seeded bijections T", ok)
# ------------------------------------------------------------ section H
def section_h():
print("H the hiding lemma")
ok, windows = True, 0
for M in range(2, 241):
for W in range(1, M):
if M % W:
continue
c = M // W
for r in range(W):
high = sum(1 for j in range(c) if 2 * (r + j * W) >= M)
want = c // 2 if c % 2 == 0 else (c - 1) // 2 + (2 * r >= W)
ok &= high == want
windows += 1
check("sign bias exactly 0 (M/W even) or 1/2 (M/W odd, + iff "
"r >= W/2), every fiber", ok, f"{windows} windows, M <= 240")
ok, classes, empty = True, 0, 0
for M in range(3, 61):
for W in range(1, M):
if M % W:
continue
c = M // W
for bb in range(W):
for gg in range(W):
Y = [bb + j * W for j in range(c)]
Z = [gg + j * W for j in range(c)]
seen = set()
for y in Y:
for z in Z:
if y != 0 and z != 0 and y != z:
seen.add(y < z)
classes += 1
if not seen:
empty += 1
ok &= c == 2 and bb == 0 and gg == 0
else:
ok &= seen == {True, False}
check("orientation: both in every class with a distinct triple", ok,
f"{classes} base-0 classes, M <= 60, {empty} without one")
# ------------------------------------------------------------ section C
def section_c():
print("C the half-coverage law")
ok, n = True, 0
for X in range(1, 241):
for Q in range(1, X + 1):
# a residue class with one lift in [1, X] determines it
det = sum(1 for r in range(Q) if len(range(r or Q, X + 1, Q)) == 1)
ok &= det == max(0, 2 * Q - X)
n += 1
check("determined singles = max(0, 2Q - X)", ok, f"{n} budgets")
ok, n = True, 0
for X in range(1, 121):
for Q in range(1, X + 1):
spans = {}
for m in range(1, X + 1):
lo, hi = spans.get(m % Q, (m, m))
spans[m % Q] = (min(lo, m), max(hi, m))
sp = list(spans.values())
has = any(a[1] < b[0] or b[1] < a[0]
for i, a in enumerate(sp) for b in sp[i + 1:])
ok &= has == (2 * Q - X >= 2)
n += 1
check("some pair is ordered with certainty iff 2Q - X >= 2", ok,
f"{n} budgets")
ok, n = True, 0
for X in range(2, 121):
for Q in range(1, X):
if X % Q:
continue
fib = [[m for m in range(1, X + 1) if m % Q == r]
for r in range(Q)]
right = 0
for fa in fib:
for fb in fib:
lt = sum(1 for a in fa for b in fb if a < b)
gt = sum(1 for a in fa for b in fb if a > b)
right += max(lt, gt) # the better order of the
# two classes: residues ordered, 0 read as Q
ok &= 2 * right == X * (X + Q - 2)
n += 1
check("best residue guess right on X(X + Q - 2)/2 pairs", ok,
f"{n} divisor budgets, X <= 120")
# ------------------------------------------------------------ section R
def conj_closure(M, rel):
ps = primes_of(M)
proj = {p: {(x % p, y % p) for (x, y) in rel} for p in ps}
return {(x, y) for x in range(M) for y in range(M)
if all((x % p, y % p) in proj[p] for p in ps)}, proj
def rectangle_everywhere(M, rel):
ps = primes_of(M)
for p in ps:
rows = {(x % p, y % p) for (x, y) in rel}
cols = {(x % (M // p), y % (M // p)) for (x, y) in rel}
rebuilt = {(x, y) for x in range(M) for y in range(M)
if (x % p, y % p) in rows
and (x % (M // p), y % (M // p)) in cols}
if rebuilt != rel:
return False
return True
def section_r():
print("R the relational form")
M = 210
eq = {(x, x) for x in range(M)}
div = {(x, x * z % M) for x in range(M) for z in range(M)}
le = {(x, y) for x in range(M) for y in range(M) if x <= y}
for name, rel, want in (("equality", eq, True),
("divisibility", div, True),
("order", le, False)):
closure, proj = conj_closure(M, rel)
check(f"Z/210 {name} conjunctive: {closure == rel}",
(closure == rel) == want)
closure, proj = conj_closure(M, le)
check("order fails maximally: every projection is all of F_p x F_p",
all(len(proj[p]) == p * p for p in primes_of(M))
and len(closure) == M * M)
for M in (6, 30):
btw = {(a, b, c) for a in range(M) for b in range(M)
for c in range(M)
if len({a, b, c}) == 3 and (b - a) % M < (c - a) % M}
proj = {p: {(a % p, b % p, c % p) for (a, b, c) in btw}
for p in primes_of(M)}
closure = {(a, b, c) for a in range(M) for b in range(M)
for c in range(M)
if all((a % p, b % p, c % p) in proj[p] for p in proj)}
apart = [t for t in closure - btw if len(set(t)) == 3]
check(f"Z/{M}: cyclic betweenness, ternary, is not conjunctive",
(0, 1, 1) in closure and len(apart) == len(btw),
f"{len(btw)} triples, closure {len(closure)}, (0, 1, 1) in "
f"it, and {len(apart)} distinct triples of the other "
f"orientation")
M = 30
rels = {"equality": {(x, x) for x in range(M)},
"divisibility": {(x, x * z % M) for x in range(M)
for z in range(M)},
"order": {(x, y) for x in range(M) for y in range(M) if x <= y}}
ok = all(rectangle_everywhere(M, r) == (conj_closure(M, r)[0] == r)
for r in rels.values())
check("Z/30: conjunctive iff a rectangle at every one-channel split",
ok)
# ------------------------------------------------------------ section D
def comparator(ms):
M = prod(ms)
S = sum(M // m for m in ms)
return M, S
def D_direct(x, ms):
return sum(x // m for m in ms)
def D_dot(x, ms, M, S):
Minv = pow(M, -1, S)
return (-Minv * sum((M // m) * (x % m) for m in ms)) % S
def D_table(ms, M):
return [sum(x // m for m in ms) for x in range(M)]
def runs(Dv):
"""The runs of constant D, as (start, length)."""
out, start = [], 0
for x in range(1, len(Dv) + 1):
if x == len(Dv) or Dv[x] != Dv[x - 1]:
out.append((start, x - start))
start = x
return out
def section_d():
print("D the exact comparator")
rng = random.Random(510510)
ok = True
for _ in range(300):
ms, size = [], rng.randrange(2, 7)
while len(ms) < size:
m = rng.randrange(2, 400)
if all(gcd(m, o) == 1 for o in ms):
ms.append(m)
M, S = comparator(ms)
ok &= gcd(M, S) == 1
check("gcd(M, S) = 1 on 300 seeded pairwise coprime sets", ok)
sets = [(2, 3, 5, 7, 11, 13, 17), (3, 5, 17, 257), (97, 101, 103),
(15, 77, 221)]
for ms in sets:
M, S = comparator(ms)
rng2 = random.Random(M)
xs = [rng2.randrange(M) for _ in range(2000)]
ok_dot = all(D_dot(x, ms, M, S) == D_direct(x, ms) for x in xs)
longest = max(length for _, length in runs(D_table(ms, M)))
check(f"{set(ms)}: D by one dot product mod S (2000 seeded x)",
ok_dot, f"M = {M}, longest run of constant D {longest} "
f"(m_1 by D's definition)")
M = 510510
ms = sets[0]
Dv = D_table(ms, M)
ties = sum(1 for x in range(1, M) if Dv[x] == Dv[x - 1])
check("Z/510510: D alone ties exactly phi(M) adjacent pairs",
ties == phi(M), f"{ties} ties, phi = {phi(M)}")
ms = sets[3]
M = 15 * 77 * 221
Dv = D_table(ms, M)
ties = sum(1 for x in range(1, M) if Dv[x] == Dv[x - 1])
want = M
for m in ms:
want = want // m * (m - 1)
check("{15, 77, 221}: D ties exactly M prod (1 - 1/m_i) adjacent "
"pairs", ties == want, f"{ties} ties, phi = {phi(M)}")
ms, M = (2, 3, 5, 7), 210
Dv = [D_direct(x, ms) for x in range(M)]
K = [(Dv[x], x % 2) for x in range(M)]
half = -(-M // 2)
ok = all((K[x] >= K[half]) == (2 * x >= M) for x in range(M))
ok &= all((K[(x + y) % M] < K[x]) == (x + y >= M)
for x in range(M) for y in range(M))
check("Z/210: sign and overflow each one key compare, exhaustive", ok)
# ------------------------------------------------------------ section K
def rung_primes(k):
out, n = [], 2
while len(out) < k:
if all(n % p for p in out):
out.append(n)
n += 1
return out
def section_k():
print("K the cost law")
sums = [sum(Fraction(1, p) for p in rung_primes(k)) for k in range(1, 11)]
check("rungs: sum 1/p < 1 exactly at k = 1, 2",
[s < 1 for s in sums] == [True, True] + [False] * 8,
f"k = 3 gives {sums[2]}")
for k in (2, 3, 7):
M, S = comparator(rung_primes(k))
print(f" rung k = {k}: S/M = sum 1/p = {float(S / M):.4f}")
fermat = [2 ** (2 ** n) + 1 for n in range(8)]
ok = all(gcd(a, b) == 1 for i, a in enumerate(fermat)
for b in fermat[i + 1:])
total = sum(Fraction(1, F) for F in fermat)
tail = Fraction(2, 2 ** (2 ** 8)) # sum over n >= 8 of 1/F_n
check("Fermat numbers pairwise coprime, sum 1/F_n < 0.5961",
ok and total + tail < Fraction(5961, 10000),
f"sum to F_7 = {float(total):.7f}")
for bits in (16, 32):
ps, n = [], 2 ** bits - 1
while len(ps) < 8:
n -= 2
if is_probable_prime(n):
ps.append(n)
M, S = comparator(ps)
check(f"8 primes below 2^{bits}: S narrower than M",
S < M, f"log2 M = {M.bit_length()}, log2 S = "
f"{S.bit_length()}")
def is_probable_prime(n):
if n < 2:
return False
for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
if n % p == 0:
return n == p
d, s = n - 1, 0
while d % 2 == 0:
d //= 2
s += 1
for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
x = pow(a, d, n)
if x in (1, n - 1):
continue
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
break
else:
return False
return True
# ------------------------------------------------------------ section Q
def quotient_dot(ms, j):
"""floor(x/m_j) for every x in [0, M), each read off the residues
by one dot product modulo M/m_j."""
M = prod(ms)
mj, R = ms[j], M // ms[j]
others = [m for i, m in enumerate(ms) if i != j]
crt = [(R // m) * pow(R // m, -1, m) for m in others]
inv = pow(mj, -1, R) if R > 1 else 0
out = []
for x in range(M):
y = sum((x % m) * c for m, c in zip(others, crt))
out.append((y - x % mj) * inv % R)
return out
def least_key(residues, ms):
"""(floor(x/m_k), x mod m_k) for the x in [0, M) with the given
residues mod the pairwise coprime ms, m_k the largest modulus: the
least exact key, read off the residues alone."""
if len(residues) != len(ms):
raise ValueError("one residue per modulus")
k = max(range(len(ms)), key=lambda i: ms[i])
mk, R = ms[k], prod(ms) // ms[k]
rk = residues[k] % mk
if R == 1:
return 0, rk
y = sum((r % m) * (R // m) * pow(R // m, -1, m)
for i, (r, m) in enumerate(zip(residues, ms)) if i != k)
return (y - rk) * pow(mk, -1, R) % R, rk
def compare(a, b, ms):
"""-1, 0 or 1 as the integers named by residue words a and b
compare, each read through its least key."""
ka, kb = least_key(a, ms), least_key(b, ms)
return (ka > kb) - (ka < kb)
def section_q():
print("Q the least comparator")
for ms in ((2, 3, 5, 7, 11, 13, 17), (3, 5, 17, 257), (97, 101, 103),
(15, 77, 221)):
M, S = comparator(ms)
k = len(ms) - 1
q = quotient_dot(ms, k)
ok = all(q[x] == x // ms[k] for x in range(M))
check(f"{set(ms)}: floor(x/m_k) by one dot product mod M/m_k",
ok and M // ms[k] < S,
f"range M/m_k = {M // ms[k]} against S = {S}")
for ms in ((2, 3, 5, 7, 11, 13, 17), (3, 5, 17, 257), (97, 101, 103),
(15, 77, 221)):
M, mk = prod(ms), max(ms)
rng = random.Random(M + 1)
corners = [0, 1, mk - 1, mk, M - 2, M - 1]
pairs = [(rng.randrange(M), rng.randrange(M)) for _ in range(2000)]
pairs += [(x, y) for x in corners for y in corners]
rev = ms[::-1]
ok, n = True, 0
for x, y in pairs:
for order in (ms, rev):
a = tuple(x % m for m in order)
b = tuple(y % m for m in order)
q, r = least_key(a, order)
ok &= compare(a, b, order) == (x > y) - (x < y)
ok &= mk * q + r == x
n += 1
check(f"{set(ms)}: compare and least_key on residue words",
ok, f"{n // 2} pairs, each in both modulus orders")
# ------------------------------------------------------------ section F
def section_f():
print("F the F_2[x] control")
factors = [0b10, 0b11, 0b111, 0b1011, 0b1101] # x, x+1, x^2+x+1, ...
f = 1
for g in factors:
f = clmul(f, g)
n = pdeg(f)
# degree at most 3: irreducible iff no root, at 0 or at 1
irred = all(pdeg(g) == 1 or (g & 1 and bin(g).count("1") % 2)
for g in factors)
check("f has degree 10 and five distinct irreducible factors",
n == 10 and len(set(factors)) == 5 and irred)
ok, windows = True, 0
for mask in range(31): # proper divisors g | f
g = 1
for i, h in enumerate(factors):
if mask >> i & 1:
g = clmul(g, h)
free = n - pdeg(g)
for r in range(1 << pdeg(g)):
top = sum(1 for P in range(1 << free)
if pdeg(r ^ clmul(g, P)) == n - 1)
ok &= 2 * top == 1 << free
windows += 1
check("top bit exactly balanced in every fiber of every proper window",
ok, f"{windows} windows; over Z the bias is 1/2 at odd M/W")
ok = all(pdeg(clmul(a, b)) == pdeg(a) + pdeg(b)
for a in range(1, 256) for b in range(1, 256))
check("deg(ab) = deg a + deg b for every nonzero a, b < 256", ok)
us = [pinv(pmod(pdivmod(f, g)[0], g), g) for g in factors]
ok, flagged = True, {}
for a in range(1 << n):
bs = [pmod(clmul(a, u), g) for u, g in zip(us, factors)]
whole = 0
for b, g, in zip(bs, factors):
whole ^= clmul(b, pdivmod(f, g)[0])
ok &= pmod(whole, f) == a
for t in range(1, n + 1):
lead = 0
for b, g in zip(bs, factors):
lead ^= pdivmod(b << t, g)[0]
ok &= lead == pdivmod(a << t, f)[0]
if lead:
ok &= pdeg(lead) - t + n == pdeg(a)
else:
ok &= a == 0 or pdeg(a) < n - t
flagged[t] = flagged.get(t, 0) + 1
check("partial fractions: t leading coefficients exact or zero",
ok and all(flagged[t] == 2 ** (n - t) for t in range(1, n + 1)),
f"flagged {[flagged[t] for t in range(1, n + 1)]}")
ms = (2, 3, 5, 7, 11, 13, 17)
M = prod(ms)
t = 16
w = {m: pow(M // m, -1, m) for m in ms}
witness = None
for x in range(1, 1001):
est = sum(((x % m) * w[m] % m) * (1 << t) // m for m in ms)
est %= 1 << t
if 2 * est >= 1 << t: # read as x >= M/2
witness = x
break
check("Z at Z/510510: a 16-bit truncation reads a small x as large",
witness is not None, f"first witness x = {witness}")
# F_3[x]: polynomials as coefficient tuples, low degree first
def trim3(a):
a = [c % 3 for c in a]
while a and a[-1] == 0:
a.pop()
return tuple(a)
def add3(a, b):
n = max(len(a), len(b))
return trim3([(a[i] if i < len(a) else 0)
+ (b[i] if i < len(b) else 0) for i in range(n)])
def mul3(a, b):
if not a or not b:
return ()
r = [0] * (len(a) + len(b) - 1)
for i, u in enumerate(a):
for j, v in enumerate(b):
r[i + j] += u * v
return trim3(r)
def below3(d):
return [trim3(c) for c in product(range(3), repeat=d)]
facs3 = [(0, 1), (1, 1), (1, 0, 1), (2, 1, 1)]
f3 = (1,)
for h in facs3:
f3 = mul3(f3, h)
n3 = len(f3) - 1
ok, windows = True, 0
for mask in range(2 ** len(facs3) - 1):
g = (1,)
for i, h in enumerate(facs3):
if mask >> i & 1:
g = mul3(g, h)
dg = len(g) - 1
profiles = set()
for r in below3(dg):
prof = [0] * (n3 + 1)
for P in below3(n3 - dg):
d = len(add3(r, mul3(g, P))) - 1
if d >= dg:
prof[d] += 1
profiles.add(tuple(prof))
ok &= len(profiles) == 1
windows += 1
check("F_3[x]: every fiber of a proper window has one degree profile",
ok, f"{windows} windows at degree {n3}")
def labellings(N, s):
"""Every add-updatable labelling on [0, N) with at most s labels,
labels in first-occurrence order; A is filled in as the search
goes, keyed by the unordered pair of labels."""
out, mu, A = [], [0], {(0, 0): 0}
def rec(n, used):
if n == N:
out.append(tuple(mu))
return
for c in range(min(used + 1, s)):
new, ok = {}, True
for x in range(n // 2 + 1):
y = n - x
a, b = mu[x], (c if y == n else mu[y])
key = (min(a, b), max(a, b))
have = A.get(key, new.get(key))
if have is None:
new[key] = c
elif have != c:
ok = False
break
if ok:
A.update(new)
mu.append(c)
rec(n + 1, max(used, c + 1))
mu.pop()
for key in new:
del A[key]
rec(1, 1)
return out
def rho(mu):
first = {}
for x, a in enumerate(mu):
if a in first:
return first[a], x - first[a]
first[a] = x
return len(mu), None
def section_controls():
print("controls")
fam = set(labellings(8, 3))
check("control: the search finds x mod 3 and rejects [x >= 3]",
tuple(x % 3 for x in range(8)) in fam and
tuple(int(x >= 3) for x in range(8)) not in fam)
ms = (2, 3, 5)
wrong = sum(compare(tuple(x % m for m in ms[::-1]),
tuple(y % m for m in ms[::-1]), ms)
!= (x > y) - (x < y) for x in range(30) for y in range(30))
check("control: words read against the wrong modulus order "
"mis-compare", wrong > 0, f"{wrong} of 900 pairs at Z/30")
check("control: one modulus keys every word by its residue",
compare((0,), (0,), (7,)) == 0 and least_key((3,), (7,)) == (0, 3))
def section_a():
print("A the additive labelling")
bad = total = 0
worst = {}
for N in (8, 10, 12, 14):
for s in (2, 3, 4, 5):
fam = labellings(N, s)
total += len(fam)
bad += len(fam) != s * (s + 1) // 2
for mu in fam:
x0, d = rho(mu)
shape = d is not None and x0 + d <= s and all(
mu[x] == mu[x + d] for x in range(x0, N - d))
B, mul = {}, True
for x in range(N):
for y in range(x, N):
if x * y < N:
key = (min(mu[x], mu[y]), max(mu[x], mu[y]))
if B.setdefault(key, mu[x * y]) != mu[x * y]:
mul = False
vals = {}
for x, a in enumerate(mu):
vals.setdefault(a, []).append(x)
inf = [(a, b) for a in vals for b in vals
if max(vals[a]) < min(vals[b])]
h = max((min(vals[b]) for a, b in inf), default=0)
worst[(N, s)] = max(worst.get((N, s), 0), h)
blind = all(
not (max(vals[mu[u]]) < min(vals[mu[v]]))
for u in range(s, N) for v in range(u + 1, N))
bad += not (shape and mul and blind)
bad += worst[(N, s)] != s - 1
check("every add-updatable labelling is a rho, mul-updatable, and "
"blind at and above s; s(s+1)/2 of them per cell", bad == 0,
f"{total} labellings over 16 cells, largest least value of an "
f"informative label s - 1 at every cell, {bad} faults")
def main():
section_controls()
if not all(CHECKS):
print("\nCONTROL FAILED: nothing below is read.")
raise SystemExit(1)
section_a()
section_l()
section_w()
section_h()
section_c()
section_r()
section_d()
section_k()
section_q()
section_f()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()