fingerprint.py
Checks: FINGERPRINT: The fingerprint property; FINGERPRINT: The fingerprint theorem theorem; observation.
Cited on: FINGERPRINT.
To run it: save fingerprint.py; standard library only.
"""fingerprint.py -- one real number reads a residue tuple up to sign.
QUESTION. Let M = q_1 q_2 ... q_k be a product of powers of k DISTINCT
primes, and read n mod M through its k channels n mod q_j. The
FINGERPRINT of n is the real number
Theta_M(n) = sum over j of 2cos(2 pi n / q_j),
which depends on n only through its channels. Changing the sign of n in
one channel (n -> m with m = -n mod q_j and m = n mod every other
factor) leaves every term unchanged. Is that the ONLY way two residues
share a fingerprint -- does Theta_M(n) = Theta_M(m) force m = +-n in
every channel, independently -- for every M?
THE ARGUMENT (written before this script). Write c_j for the CLASS of n
at q_j, the least of n and -n mod q_j, so 0 <= c_j <= q_j/2 and the
channel's value is 2cos(2 pi c_j / q_j). Suppose two class tuples give
one sum.
(1) ISOLATION. The Galois group of Q(zeta_M) is the product of the
groups of the Q(zeta_{q_j}), the prime powers being coprime.
Average the vanishing difference over the subgroup fixing
zeta_{q_j}: channel j's difference delta_j is fixed and every
other channel's is replaced by a rational number. So each delta_j
is RATIONAL.
(2) ONE CHANNEL. The value 2cos(2 pi c / q) with q = p^e generates
the real subfield of Q(zeta_{p^a}), p^a = q / gcd(c, q), and those
fields grow strictly in degree with a once the value is
irrational. A rational difference of two irrational values puts
both in one layer, where every value of exact level p^a is a
Galois conjugate of every other and so has the same trace; the
difference then equals its own average, 0. A rational difference
of a rational and an irrational value is impossible. So a
NONZERO rational delta_j needs both values rational, and by
Niven's theorem the rational values of 2cos(2 pi r) with r
rational are 2, 1, 0, -1, -2. Hence the nonzero rational
differences at q are: +-4 at q = 2 (values 2, -2); +-2 and +-4
at q = 2^e, e >= 2 (values 2, 0, -2); +-3 at q = 3^e (values 2,
-1); none at q = p^e, p >= 5 (value 2 alone). Within one channel
2cos is strictly decreasing on the class range, so delta_j = 0
means equal classes.
(3) THE CLASH. At most one factor is a power of 2 and one a power of
3. A zero sum needs a difference in {0, +-2, +-4} at the 2-power
channel to cancel one in {0, +-3} at the 3-power channel, so both
are 0, and every channel's class agrees.
So Theta_M is injective on class tuples, for every M, and its fibres
are the orbits of the SIGN GROUP G_M = {g : g = +-1 mod every q_j},
acting by multiplication: m = g n. The distinct fingerprints number
prod_j (floor(q_j / 2) + 1).
Two readings of the same function. With 2cos t = 2 - 4 sin^2(t/2),
Theta_M(n) = 2k - |d(n)|^2 where |d(n)|^2 = sum_j 4 sin^2(pi n / q_j) is
the squared chord distance from 0 to n on the torus that draws each
channel as a circle of q_j points: the distance from the origin fixes
the point up to reflecting each circle. And Theta_M(m) is the
eigenvalue of the CHANNEL-STEP GRAPH -- the Cayley graph of Z/M whose
steps are +-1 in one channel, the product of the cycles C_{q_j} -- on
the character psi_m(x) = exp(2 pi i sum_j m_j x_j / q_j), labelled by
its CRT coordinates m_j = m mod q_j. So the theorem says each
eigenvalue's multiplicity is exactly the size of a sign orbit: each
eigenvalue is as simple as multiplication by the sign group allows. The additive character
x -> exp(2 pi i m x / M) is the character with coordinates m u_j, where
u_j is the inverse of M / q_j mod q_j, so its eigenvalue is
Theta_M(u * m), a TWIST that moves no label up to sign while every
u_j = +-1.
DESIGN. Sections, each a set of checks printing PASS or FAIL.
R step (2), exactly. For every prime power q <= 200: psi_q, the monic
integer polynomial of 2cos(2 pi / q), is built from the cyclotomic
polynomial (z^(-h) Phi_q(z) written in z^j + z^-j = D_j(z + 1/z),
h = phi(q)/2, D_0 = 2, D_1 = x, D_{j+1} = x D_j - D_{j-1}) and
certified irreducible by Rabin's test modulo a prime r whose class
generates (Z/q)* / {+-1}, which makes it the minimal polynomial.
The class value at c is then D_c reduced mod psi_q, and a pair
difference is rational iff its reduction is a constant
polynomial. Every pair c' < c <= q/2 is reduced in integer
arithmetic, no float in the verdict, and the set of rational
differences is compared with step (2)'s law. q = 2 has degree-1
Phi and rational values 2 and -2; its set {+-4} is written in by
hand, not computed.
POSITIVE CONTROL, read before the law's verdict: the detector must
fire at q = 3, 4, 8, 9, where rational differences exist (at 3 and
4 psi_q has degree 1, every reduction is constant, so only 8 and 9
test the split).
Z step (3): only the primes 2 and 3 carry nonzero difference sets
in R, so a zero sum across channels at distinct primes pairs one
2-power with one 3-power; no such pair with a nonzero entry sums
to zero. Z1 is R2's sets read by arithmetic, so it fails only
where R2 does. POSITIVE CONTROL, read first: two channels at ONE
prime (2 and 4; 3 and 9), which the hypothesis excludes, must show a
zero sum -- the theorem's distinct-primes hypothesis is load-bearing.
E the whole statement in floats, where enumeration reaches: every
class tuple's fingerprint for the squarefree rungs Z/p_k#,
k = 1..7, and the powered moduli 8*9*5*7*11, 16*27*5*7 and
4*9*25*49; the values are distinct iff the least gap between
them, sorted, is above 1e-9, and that gap is printed, with the
order of G_M counted over every g of Z/M. Then, by brute force
over every n in Z/M for M = 210, 2310, 360 and 900, the fibre of
Theta_M through each n against its sign orbit {g n : g in G_M}.
G the channel-step graph at M = 30, 210, 360: the adjacency applied
to every psi_m returns Theta_M(m) psi_m, read at every
max(1, M // 60)-th point (strides 1, 3 and 6: 30, 70 and 60
points); the multiplicity of each eigenvalue among the psi_m is its
orbit size, read off Theta_M itself, so it restates E's fibre law
and the graph enters through the eigen-relation alone; the additive
character's eigenvalue is Theta_M(u * m); the
u_j ladder over the rungs k = 1..10 and the first rung where some
u_j is not +-1; and off the primorials, Z/15, where u = 2 at 5.
C the chord identity over every n of Z/2310 and Z/360.
PREDICTIONS, fixed before the run.
R1 psi_q irreducible (a certificate found) at every prime power
q <= 200 with q >= 3; psi_q(2) = Phi_q(1), which is p at q = p^e.
R2 the rational-difference sets: {+-4} at 2; {+-2, +-4} at 4, 8, 16,
32, 64, 128; {+-3} at 3, 9, 27, 81; empty at every other prime
power <= 200. KILL: any printed set that differs.
R3 the detector fires at 3, 4, 8, 9 (at 3 and 4 it cannot fail).
Z1 no zero sum across distinct primes; Z2 the planted same-prime
pairs (2, 4) and (3, 9) each show one.
E1 distinct fingerprints = class count at every modulus in E: 2, 4,
12, 48, 288, 2016, 18144 for k = 1..7; 1800, 1512 and 4875 for the
powered moduli. Every fibre is its sign orbit; the largest orbit
is 2^(number of factors above 2), 64 at k = 7.
G1 the eigen-relation at float precision (deviation below 1e-9); the
multiplicities are the orbit sizes; the twist is invisible through
k = 3 and first visible at k = 4, where u = 3 at 5 and 4 at 7
(the inverses of 42 mod 5 and 30 mod 7).
C1 deviation below 1e-12.
One number was corrected before the first run: 4*9*25*49 has
3*5*13*25 = 4875 classes, first written as 7800.
FINDINGS. Every prediction landed: 29/29 checks PASS.
R1 59 certificates, one per prime power 3 <= q <= 200, each from the
least prime generating (Z/q)* / {+-1} and confirmed by Rabin's
test; psi_q(2) = p throughout.
R2 R3 the sets are exactly the law's at the 59 computed prime powers
and at q = 2, written in by hand: {+-4} at 2, {+-2, +-4} at every
larger power of 2, {+-3} at every power of 3, empty at 5, 25,
125, 7, 49, 11, 121, ..., 199. The detector
fires at 3, 4, 8 and 9, the last two the test.
Z1 no zero sum over the 28 pairs of a 2-power and a 3-power channel.
Z2 the same-prime pairs collide, (-4, 4) at (2, 4) and (-3, 3) at
(3, 9): two difference sets at one prime cancel (a clash on
Z/2 x Z/4, never in a Z/M), so the hypothesis is used.
E1 distinct fingerprints equal the class count at all ten moduli, the
least gap falling 4, 1, 0.38, 1.1e-2, 2.2e-5, 6.8e-6, 1.9e-7 over
the rungs k = 1..7 and 6.5e-6, 4.3e-6, 3.0e-7 over the powered
moduli. Every fibre is its sign orbit at 210, 2310, 360 and 900,
the largest 8, 16, 8, 8 = 2^(factors above 2); |G_M| counts 1, 2,
4, 8, 16, 32, 64 over the rungs.
G1 eigen-relation deviations at most 4.5e-14 on psi_m and 1.6e-12 on
the additive characters; multiplicities are the sign orbits at 30,
210 and 360; the twist first shows at k = 4, u = (1, 1, 3, 4)
(the ladder prints it signed, (1, 1, -2, -3));
at Z/15, u = (2, 2).
C1 deviation 3.6e-15.
Tiers: the fingerprint theorem is a theorem, proved above; R and Z
check steps (2) and (3) exactly at every prime power to 200, and E, G
and C are float cross-checks at small moduli, reported as such.
RUN RECORD. The first run failed one check: E1 at M = 2310 found 292
fibres against 288 sign orbits. The fibres had been grouped by rounding
each value to nine decimals, four values sat on a rounding edge, and
float noise from unreduced arguments split each in two. Grouping by
gaps after sorting, with n reduced mod q before the cosine, fixed it
(true gaps at that modulus are at least 2.2e-5); the chord side then
needed the same reduction. A later reading added E1's count of G_M
over every g of Z/M and G2, the twist off the primorials. The recorded
run: 29/29 PASS, 8.6 MB peak commit, 1.4 s.
Standard library only.
python fingerprint.py
"""
from itertools import product
from math import cos, pi, prod, sin
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def is_prime(n):
return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))
def prime_of(q):
return next(p for p in range(2, q + 1) if q % p == 0)
PRIME_POWERS = [q for q in range(2, 201)
if all(q % d for d in range(2, q) if d != prime_of(q)
and is_prime(d))]
# ------------------------------------------------ integer polynomials
# Little-endian coefficient lists over Z.
def pnorm(a):
a = list(a)
while a and a[-1] == 0:
a.pop()
return a
def padd(a, b, s=1):
n = max(len(a), len(b))
return pnorm([(a[i] if i < len(a) else 0)
+ s * (b[i] if i < len(b) else 0) for i in range(n)])
def pmul(a, b):
out = [0] * (len(a) + len(b) - 1)
for i, x in enumerate(a):
for j, y in enumerate(b):
out[i + j] += x * y
return pnorm(out)
def pmod(a, m, q=None):
"""a mod the monic m, over Z, or over F_q when q is given."""
a = pnorm(a if q is None else [c % q for c in a])
dm = len(m) - 1
while len(a) - 1 >= dm and a:
lead, shift = a[-1], len(a) - 1 - dm
for i, c in enumerate(m):
a[shift + i] -= lead * c
a = pnorm(a if q is None else [c % q for c in a])
return a
def peval(a, x):
v = 0
for c in reversed(a):
v = v * x + c
return v
def cyclotomic(q):
"""Phi_q for a prime power q = p^e: Phi_p(z^(p^(e-1)))."""
p = prime_of(q)
step = q // p
out = [0] * (q - step + 1)
for i in range(p):
out[i * step] = 1
return out
def dickson(h):
"""D_0..D_h with D_j(z + 1/z) = z^j + z^-j."""
D = [[2], [0, 1]]
while len(D) <= h:
D.append(padd(pmul([0, 1], D[-1]), D[-2], -1))
return D[:h + 1]
def psi(q):
"""The monic integer polynomial of 2cos(2 pi / q), q >= 3."""
phi = cyclotomic(q)
h = (len(phi) - 1) // 2
D = dickson(max(h, q // 2))
out = [phi[h]]
for j in range(1, h + 1):
out = padd(out, [phi[h + j] * c for c in D[j]])
return out, D
def rabin_irreducible(f, r):
"""f monic over Z; irreducible mod the prime r (Rabin's test)."""
m = len(f) - 1
fr = [c % r for c in f]
if m == 1:
return True
def mulmod(a, b):
return pmod(pmul(a, b) if a and b else [], fr, r)
def frob(times):
t = [0, 1]
for _ in range(times):
base, e, acc = t, r, [1]
while e:
if e & 1:
acc = mulmod(acc, base)
base = mulmod(base, base)
e >>= 1
t = acc
return t
if pnorm([c % r for c in padd(frob(m), [0, 1], -1)]):
return False
for ell in {d for d in range(2, m + 1) if m % d == 0 and is_prime(d)}:
a, b = [c % r for c in padd(frob(m // ell), [0, 1], -1)], fr
while b: # gcd over F_r
inv = pow(b[-1], r - 2, r)
b = [c * inv % r for c in b]
a, b = b, pmod(a, b, r)
if len(a) != 1:
return False
return True
# ------------------------------------------------------------------ R
LAW = {"2": [-4, 4], "2^e": [-4, -2, 2, 4], "3^e": [-3, 3], "p>=5": []}
def law(q):
p = prime_of(q)
if q == 2:
return LAW["2"]
return LAW["2^e"] if p == 2 else LAW["3^e"] if p == 3 else LAW["p>=5"]
def candidate(q):
"""The least prime r whose class generates (Z/q)* / {+-1}: psi_q is
irreducible mod r iff that order is phi(q)/2. Theory picks r and
Rabin's test certifies it, independently."""
h = (len(cyclotomic(q)) - 1) // 2
for r in range(2, 2000):
if is_prime(r) and q % r:
x, order = r % q, 1
while x not in (1, q - 1):
x, order = x * r % q, order + 1
if order == h:
return r
return None
def rational_differences(q):
"""Every rational value of v(c) - v(c'), 0 <= c' < c <= q/2, where
v(c) = 2cos(2 pi c / q); integer-exact."""
if q == 2:
return [-4, 4], None
f, D = psi(q)
red = [pmod(D[c], f) for c in range(q // 2 + 1)]
diffs = set()
for c in range(len(red)):
for cp in range(c):
d = padd(red[c], red[cp], -1)
if len(d) <= 1: # a constant reduction
v = d[0] if d else 0
diffs.update((v, -v))
return sorted(diffs), f
def section_r():
print("R rational differences at every prime power q <= 200, exact")
certs, psi2, sets = 0, True, {}
for q in PRIME_POWERS:
got, f = rational_differences(q)
sets[q] = got
if f is None:
continue
psi2 &= peval(f, 2) == prime_of(q)
cert = candidate(q)
certs += cert is not None and rabin_irreducible(f, cert)
check("R1 psi_q irreducible for every prime power 3 <= q <= 200",
certs == len(PRIME_POWERS) - 1, f"{certs} certificates")
check("R1 psi_q(2) = p at every q = p^e >= 3", psi2)
check("R3 the detector fires at 3, 4, 8 and 9 (8 and 9 the test)",
all(sets[q] for q in (3, 4, 8, 9)))
wrong = {q: s for q, s in sets.items() if s != law(q)}
for q in (2, 3, 4, 8, 9, 16, 27, 5, 25, 7, 49, 11, 121, 125, 199):
print(f" q = {q:3d} rational differences {sets[q] or 'none'}")
check("R2 every set equals step (2)'s law", not wrong,
f"differing at {wrong}" if wrong else
f"{len(sets)} prime powers")
return sets
# ------------------------------------------------------------------ Z
def zero_sums(channel_sets):
"""Choices, one difference per channel (0 allowed), summing to zero
with some entry nonzero."""
return [t for t in product(*[[0] + s for s in channel_sets])
if sum(t) == 0 and any(t)]
def section_z(sets):
print("Z the clash across channels")
by_prime = {}
for q, s in sets.items():
if s:
by_prime.setdefault(prime_of(q), []).append(q)
planted = [zero_sums([sets[2], sets[4]]), zero_sums([sets[3], sets[9]])]
check("Z2 the planted same-prime pairs (2, 4) and (3, 9) collide",
all(planted), f"e.g. {[z[:1] for z in planted]}")
twos, threes = by_prime.get(2, []), by_prime.get(3, [])
hits = [(a, b) for a in twos for b in threes
if zero_sums([sets[a], sets[b]])]
check("Z1 no zero sum over a 2-power and a 3-power channel",
not hits and set(by_prime) == {2, 3},
f"{len(twos) * len(threes)} pairs; only primes "
f"{sorted(by_prime)} have nonzero sets")
# ------------------------------------------------------------------ E
def classes(q):
return range(q // 2 + 1)
def fingerprint(n, factors):
return sum(2 * cos(2 * pi * (n % q) / q) for q in factors)
def fibres(values, tol=1e-9):
"""Group the keys of {key: real} into runs of values closer than tol,
after sorting: no rounding edge to straddle."""
order = sorted(values, key=values.get)
groups = [[order[0]]]
for a, b in zip(order, order[1:]):
if values[b] - values[a] < tol:
groups[-1].append(b)
else:
groups.append([b])
return [set(g) for g in groups]
def value_table(factors):
vals = [0.0]
for q in factors:
vals = [v + 2 * cos(2 * pi * c / q) for v in vals for c in classes(q)]
return vals
def sign_group(factors):
M = prod(factors)
return [g for g in range(M)
if all(g % q in (1 % q, q - 1) for q in factors)]
FIRST = [2, 3, 5, 7, 11, 13, 17]
POWERED = [(8, 9, 5, 7, 11), (16, 27, 5, 7), (4, 9, 25, 49)]
def section_e():
print("E the whole statement in floats")
for factors in [FIRST[:k] for k in range(1, 8)] + POWERED:
vals = sorted(value_table(factors)) # one per class tuple
gap = min((b - a for a, b in zip(vals, vals[1:])), default=1.0)
order = len(sign_group(factors))
above2 = sum(q > 2 for q in factors)
check(f"E1 M = {'*'.join(map(str, factors))}: distinct = classes",
gap > 1e-9 and order == 2 ** above2,
f"{len(vals)} classes, least gap {gap:.1e}, |G| = {order}")
for factors in [(2, 3, 5, 7), (2, 3, 5, 7, 11), (8, 9, 5), (4, 9, 25)]:
M, G = prod(factors), sign_group(factors)
buckets = fibres({n: fingerprint(n, factors) for n in range(M)})
ok = all(members == {g * n % M for g in G}
for members in buckets for n in members)
big = max(len(b) for b in buckets)
above2 = sum(q > 2 for q in factors)
check(f"E1 M = {M}: every fibre is its sign orbit", ok
and big == 2 ** above2 and len(G) == 2 ** above2,
f"{len(buckets)} fibres, largest {big}, |G| = {len(G)}")
# ------------------------------------------------------------------ G
def crt_units(factors):
M = prod(factors)
return [pow(M // q, -1, q) for q in factors]
def section_g():
print("G the channel-step graph")
for factors in [(2, 3, 5), (2, 3, 5, 7), (8, 9, 5)]:
M = prod(factors)
steps = []
for j, q in enumerate(factors):
e = next(x for x in range(M) if all(
x % r == (1 if i == j else 0) for i, r in enumerate(factors)))
steps += [e, M - e] if q > 2 else [e]
# at q = 2 a step of +1 and -1 is one edge; the graph's degree
# counts it twice so that each channel contributes 2cos
weight = [1 if q > 2 else 2 for q in factors for _ in
range(2 if q > 2 else 1)]
units = crt_units(factors)
dev, twist_dev = 0.0, 0.0
eig = {}
for m in range(M):
psi_m = [complex(cos(a), sin(a)) for a in
(2 * pi * sum((m % q) * (x % q) / q for q in factors)
for x in range(M))]
lam = fingerprint(m, factors)
for x in range(0, M, max(1, M // 60)):
applied = sum(w * psi_m[(x + s) % M]
for s, w in zip(steps, weight))
dev = max(dev, abs(applied - lam * psi_m[x]))
eig[m] = lam
chi = [complex(cos(2 * pi * m * x / M), sin(2 * pi * m * x / M))
for x in range(M)]
twisted = sum(2 * cos(2 * pi * m * u / q)
for u, q in zip(units, factors))
for x in range(0, M, max(1, M // 60)):
applied = sum(w * chi[(x + s) % M]
for s, w in zip(steps, weight))
twist_dev = max(twist_dev, abs(applied - twisted * chi[x]))
G = sign_group(factors)
eig = fibres(eig)
mult_ok = all(ms == {g * min(ms) % M for g in G} for ms in eig)
check(f"G1 M = {M}: A psi_m = Theta(m) psi_m and the additive "
f"character carries Theta(u*m)", dev < 1e-9 and twist_dev
< 1e-9, f"deviations {dev:.1e}, {twist_dev:.1e}")
check(f"G1 M = {M}: multiplicities are the sign orbits", mult_ok,
f"{len(eig)} eigenvalues")
first_visible = None
for k in range(1, 11):
q = FIRST[:k] + [19, 23, 29][:max(0, k - 7)]
u = crt_units(q)
signed = [x if x <= qq // 2 else x - qq for x, qq in zip(u, q)]
visible = any(abs(s) != 1 for s in signed)
print(f" k = {k:2d} u = {signed}")
if visible and first_visible is None:
first_visible = (k, u)
check("G1 the twist is first visible at k = 4, u = 3 at 5 and 4 at 7",
first_visible is not None and first_visible[0] == 4
and first_visible[1][2:] == [3, 4], f"{first_visible}")
u15 = crt_units([3, 5])
check("G2 off the primorials, at Z/15, u = 2 at 5", u15[1] == 2,
f"u = {u15}")
# ------------------------------------------------------------------ C
def section_c():
print("C the chord identity")
dev = 0.0
for factors in [(2, 3, 5, 7, 11), (8, 9, 5)]:
for n in range(prod(factors)):
chord2 = sum(4 * sin(pi * (n % q) / q) ** 2 for q in factors)
dev = max(dev, abs(fingerprint(n, factors)
- (2 * len(factors) - chord2)))
check("C1 Theta = 2k - |d|^2 on Z/2310 and Z/360", dev < 1e-12,
f"deviation {dev:.1e}")
def main():
sets = section_r()
section_z(sets)
section_e()
section_g()
section_c()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()