numwall.py
Checks: GROWTH: The wall over a number ring theorem; rule.
Cited on: GROWTH.
To run it: save numwall.py; standard library only.
"""numwall.py -- the wall over a number ring against w_L(K).
QUESTION. Over Z the wall at L (the largest M with lambda(M) | L) is
Adams' number W(L), and it is also the largest m with Gal(Q(mu_m)/Q)
of exponent dividing L, because Gal(Q(mu_m)/Q) is (Z/m)^x: a fact of
Z, re-derived for K here, not assumed. Over the ring of integers O_K
of a number field the wall W_K is an ideal, read off (O_K/M)^x, while
w_L(K), the largest m with Gal(K(mu_m)/K) of exponent dividing L (the
name is Serre's; the integer is defined here, its Chebotarev form D7
resting on Chebotarev's density theorem), is an integer read off K's cyclotomic extensions. What
does one read of the other?
THE OBJECTS (K Galois over Q, so the places over p are conjugate).
W_K = prod_p rad(p)^(a_p), a_p the largest a with
lambda(P^a) = (N(P) - 1) E_P(a) dividing L (the module law), P
any place over p; c the positive generator of W_K cap Z, so
v_l(c) = ceil(a_l / e_l).
w = w_L(K), as defined above.
n = n_L(K), the NORM WALL: the largest m with N_(K/Q)((O_K/m)^x) of
exponent dividing L; equivalently the gcd over y in O_K of
N(y)^s (N(y)^L - 1) at large s. The wall is Adams' gcd ideal
over y in O_K of y^s (y^L - 1): n is the same gcd taken after
the norm.
THE ARGUMENT (written before the engine).
D1 c | W(L): Z/c embeds in O_K/W_K, so (Z/c)^x has exponent | L.
D2 W(L) | w: Gal(K(mu_m)/K) embeds in Gal(Q(mu_m)/Q) = (Z/m)^x.
D3 w | n: the principal ideal (y), y prime to m, has Artin symbol
|N(y)| on Q(mu_m), so H_el(m) = N((O_K/m)^x) lies in
Gal(K(mu_m)/K), which also holds -1 when K has a real place.
D4 the Artin map takes the ideals prime to m onto Gal(K(mu_m)/K) and
the principal ones onto H+ = {|N(y)|}, inside <H_el, -1>, so
Gal / H+ is Gal(K(mu_m) cap H / K), H the Hilbert class field.
K(mu_oo) cap H lies in Q^ab cap H, which is unramified over K;
an abelian field over Q is generated over Q by its inertia
groups (Q has no unramified extension), so one
unramified over K and inside K(mu_oo) is K itself when every
inertia group of K is already that of the bigger field: at
K = Q(mu_m) always, at a quadratic K of prime discriminant since
then one inertia group of order 2 generates. There Gal = H+, so
n = w at even L. For quadratic K, K(mu_m) cap H lies in the genus
field, so Gal / H+ is a quotient of its group, of exponent 2:
g^2 lies in H+ for every g, so n | w_(2L) at even L, and a prime
of n / w is
one l whose K(mu_(l^k)) meets the genus field beyond K, which
needs l | D.
D5 at l unramified in K the local norm maps O_P^x onto Z_l^x, so the
l-part of n is W(L)'s. D6 v_l(w) > v_l(W(L)) needs
K cap Q(mu_(l^oo)) != Q, so l ramified in K.
D7 the Chebotarev form: v_l(w) = min over places v not over l of
v_l(N(v)^L - 1): Frobenius at v acts on mu_(l^k) as N(v), and
every element of Gal(K(mu_(l^k))/K) is a Frobenius.
DESIGN. Standard library only; one process.
Fields: Q (m = 1, the control); Q(sqrt d) at every squarefree d,
2 <= |d| <= 50, and d = -1; Q(mu_m) at m = 3, 4, 5, 7, 8, 9, 12.
L: every even L <= 60. Q(mu_3) and Q(mu_4) repeat d = -3, -1 as C4's
control, so the 69 fields are 67 distinct.
The local ring at P is a TOWER W_f[x]/(g): W_f = Z_p[y]/(h), h
irreducible mod p of degree f, g Eisenstein over Z_p of degree e
(g = x - p at e = 1): Q_p(sqrt d) by x^2 - d or (x + 1)^2 - d, and
Q_p(mu_m) by Phi_(p^k)(x + 1) over W_f, f the order of p mod m'.
E(a) is the largest order in U_1/U_a of the generators 1 + y^j x^i.
w by its definition, per prime l (the exponent of Gal(K(mu_M)/K) is
the lcm over l^k || M of the exponents at l^k, since K(mu_M) is the
compositum): Gal(K(mu_(l^k))/K) is the image in (Z/l^k)^x of the
a mod lcm(f_K, l^k) with a mod f_K in H_K, K the fixed field of
H_K in Q(mu_(f_K)). Only l <= nL + 1 can enter (the image mod l
has index at most n in a cyclic group of order l - 1).
n by the norm Adams gcd over a box of y in O_K = Z[t]/(F), s = 64,
read at two boxes.
C CONTROLS, read before any verdict:
C1 the tower's (N(P) - 1) E(a) is the exponent of the whole unit
group of O_P/P^a at every local ring a wall can meet
(N(P) <= 61) and every a with N(P)^a <= 20,000; and E(1..9)
at Z_2, Q_2(sqrt -2), Q_2(i),
Q_2(sqrt -5) as module_law.py printed them.
C2 K = Q: W = (W(L)) and c = w = n = W(L), W(L) by its closed
form 2^(v_2(L) + 2) prod (p^(v_p(L) + 1) : p odd, p - 1 | L).
C3 the Adams gcd ideal over a box of y in O_K has index N(W_K);
it lies in W_K by definition, so equal index is equality; at
every L for degree <= 2, at L = 2, 4, 6, 12, 24, 60 above.
C4 Q(mu_3), Q(mu_4) agree with d = -3, -1 on N(W), c, w, n.
C5 w by definition equals w by D7 (places v with N(v) <= 4000).
C6 the hand values at L = 2: Q(i) W = P2^2, c 2, w 24, n 24;
Q(sqrt -3) W = P3, c 3, w = n = 24; Q(sqrt 5) W = (1), c 1,
w = n = 120; Q(sqrt -15) W = P2^3 P2'^3 P3, c 24, w 24, n 120.
C7 n read at two boxes agrees.
C8 at every place P alone over its p (N(P) <= 61), a_P read a
second way: v_P(x) = v_p(N(x)) / f, the norm taken in
Z[t]/(F) mod p^(41 f), and a_P the least v_P(g^L - 1) over a
generator t of (O/P)^x and the 1 + t^j pi^b (j < f, b >= 1,
pi of valuation 1, both found by search), which generate
(O/P^a)^x since each U_b/U_(b+1) is the residue field under
addition; b runs while b < the running least.
PREDICTIONS AND KILLS, frozen before the engine.
T1 c | W(L) | w | n at every (K, L).
T2 n = w at every cyclotomic field and every quadratic field of
prime discriminant.
T3 quadratic K: n | w_(2L), every prime of n / w divides D.
T5 v_l(n) = v_l(W(L)) at every l unramified in K.
T6 v_l(w) > v_l(W(L)) only at l ramified in K.
A KILL is any printed violation of T1-T6; a control miss fails the
instrument. OBSERVED, no prediction: where c = W(L), where
w = W(L), where n != w.
FINDINGS (from the printed run, 14/14 checks PASS).
C every control held: C1 at 1089 (ring, a) over 145 local rings,
0 off, and E(1..9) at the four rings at 2 as module_law.py
printed; C2 at every even L <= 60; C3 at 1950 (field, L), 0 off;
C4; C5 at 2070 (field, L), 0 off; C6 (Q(i): W = P2^2, norm 4,
c 2, w 24, n 24; Q(sqrt -3): W = P3, c 3, w = n = 24;
Q(sqrt 5): W = (1), c 1, w = n = 120; Q(sqrt -15): W =
P2^3 P2'^3 P3, norm 192, c 24, w 24, n 120); C7 at 2070; C8 at
6900 (field, place, L), 0 off, the eight depths past C1 among
them: 18, 22, 18 over 2 of Q(mu_8) at L = 16, 32, 48; 12, 12, 18
over 3 of Q(mu_9) at 18, 36, 54; 8 over 7 of Q(mu_7) at 42; 8
over 2 of Q(mu_12) at 48. A tower with E lowered at depth 7, in a
scratch copy, fails C8 at 104 (field, place, L).
T every prediction held: T1 at 2070 (field, L), T2 at 750, T3, T5
and T6 with 0 off.
O c = W(L) at 115 of 2070, w = W(L) at 1915, W_K = (1) at 72, and
n != w at 439, over 26 quadratic fields, every one of composite
discriminant. The 178 odd (field, L, l) in n / w are l^(1 + v_l(L)),
at the L with (l - 1)/2 | L and (l - 1) not | L: l = 5 over
d = -35, -30, -15, -10, -5, 10, 15, 30, 35; 13 over d = -39, -26,
-13, 26, 39; 17 over d = -34, -17, 34; 29, 37, 41 over -29, -37,
-41. 2 exactly divides n / w at every L over d = -46, -38, -30,
-22, -14, -6, 10, 26, 34, 42. Read at L = 2, 12, 60: Q(mu_7) has
W_K = (1), c = 1 at L = 2 and the place over 7, c = 7, at 12 and
60, while w = 168, 65520, 6814407600; Q(sqrt 17)'s wall is the
same ideal at L = 12 and 60.
WHY the odd gaps (a proof): at odd l | D with K not
Q(sqrt l*), K cap Q(mu_(l^oo)) = Q, so Gal(K(mu_(l^k))/K) is all of
the cyclic (Z/l^k)^x, exponent (l - 1) l^(k - 1); the norm of a
local unit a + b sqrt(l u) is a^2 - l u b^2 = a^2 mod l, and 1 + l Z_l
is all squares, so the norm image is the squares, exponent
(l - 1)/2 l^(k - 1). Hence v_l(n / w) = 1 + v_l(L) exactly when
(l - 1)/2 | L and l - 1 does not, which at even L needs l = 1 mod 4.
The relation: no ideal map from W_K to w. They are Adams' gcd over
O_K taken before the norm (W_K) and after it (n, which is w up to
the genus field), and they meet at Adams' number, c | W(L) | w | n.
Residue degree takes from the wall (a place enters only when
N(P) - 1 | L), ramification adds to w (only at l | D).
RUN RECORD. 124.4 s, peak commit 29.3 MB; with the gap tally,
123.2 s, 31.0 MB, every earlier print unchanged; its label read
(field, L, l), 124.6 s, 29.4 MB; with C8, 124.4 s, 31.1 MB, C8 itself
under a second. An earlier run
built towers for places no wall meets (an irreducible of degree 6 mod
61 by trial) and recomputed (Z/l^k)^x per field at T3; both stopped by
the clock, redesigned, not rerun as they were.
"""
import sys
import time
from itertools import product
from math import gcd, isqrt
CHECKS, NAMES = [], []
LS = list(range(2, 61, 2))
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
NAMES.append(name)
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def section(title):
print()
print("=" * 72)
print(title)
print("=" * 72)
# ------------------------------------------------------------ arithmetic
def lcm(a, b):
return a // gcd(a, b) * b
def vp(n, p):
if n == 0:
return 10 ** 9
v = 0
while n % p == 0:
n //= p
v += 1
return v
def primes_up_to(n):
s = bytearray([1]) * (n + 1)
s[0] = s[1] = 0
for i in range(2, isqrt(n) + 1):
if s[i]:
s[i * i::i] = bytearray(len(s[i * i::i]))
return [i for i in range(n + 1) if s[i]]
PR = primes_up_to(5000)
def factor(n):
out = {}
for p in PR:
if p * p > n:
break
while n % p == 0:
out[p] = out.get(p, 0) + 1
n //= p
if n > 1:
out[n] = out.get(n, 0) + 1
return out
def mult_order(a, m):
if m == 1:
return 1
k, x = 1, a % m
while x != 1:
x = x * a % m
k += 1
return k
def adams_closed(L):
"""W(L) at even L by its closed form."""
w = 2 ** (vp(L, 2) + 2)
for p in PR[1:]:
if p - 1 > L:
break
if L % (p - 1) == 0:
w *= p ** (vp(L, p) + 1)
return w
def kronecker(D, a):
"""(D / a) for a > 0."""
r = 1
while a % 2 == 0:
a //= 2
if D % 2 == 0:
return 0
r *= 1 if D % 8 in (1, 7) else -1
# Jacobi (D / a), a odd
x, y = D % a, a
while x:
while x % 2 == 0:
x //= 2
if y % 8 in (3, 5):
r = -r
x, y = y, x
if x % 4 == 3 and y % 4 == 3:
r = -r
x %= y
return r if y == 1 else 0
def poly_mod_p_irreducible(h, p):
"""h monic, coefficients low to high, irreducible over F_p (by trial
division by every monic polynomial of degree <= deg h / 2)."""
n = len(h) - 1
for d in range(1, n // 2 + 1):
for tail in product(range(p), repeat=d):
q = list(tail) + [1]
r = [c % p for c in h]
while len(r) - 1 >= d:
c = r[-1]
if c:
for i in range(d + 1):
r[len(r) - 1 - d + i] = (r[len(r) - 1 - d + i]
- c * q[i]) % p
r.pop()
if not any(r):
return False
return True
def irreducible(p, f):
if f == 1:
return [0, 1]
for tail in product(range(p), repeat=f):
h = list(tail) + [1]
if poly_mod_p_irreducible(h, p):
return h
raise ValueError
def cyclotomic(m):
"""Phi_m, coefficients low to high."""
num = [-1] + [0] * (m - 1) + [1]
for d in range(1, m):
if m % d == 0:
q = cyclotomic(d)
out = [0] * (len(num) - len(q) + 1)
r = num[:]
for i in range(len(out) - 1, -1, -1):
c = r[i + len(q) - 1]
out[i] = c
for j, qj in enumerate(q):
r[i + j] -= c * qj
num = out
return num
def shift1(g):
"""g(x + 1)."""
out = [0] * len(g)
for i, c in enumerate(g):
b = 1
for j in range(i + 1):
out[j] += c * b
b = b * (i - j) // (j + 1)
return out
# ------------------------------------------------------- the local tower
class Tower:
"""O_P = W_f[x]/(g), W_f = Z_p[y]/(h), carried mod p^N; an element
is e lists of f integers, z[i][j] the coefficient of x^i y^j."""
def __init__(self, p, h, g):
self.p, self.h, self.g = p, h, g
self.f, self.e = len(h) - 1, len(g) - 1
self.q = p ** self.f
self.Ecache = {}
def wmul(self, u, w, mod):
f, h = self.f, self.h
prod_ = [0] * (2 * f - 1)
for i, a in enumerate(u):
if a:
for j, b in enumerate(w):
prod_[i + j] += a * b
for d in range(2 * f - 2, f - 1, -1):
c = prod_[d]
if c:
prod_[d] = 0
for k in range(f):
prod_[d - f + k] -= c * h[k]
return [c % mod for c in prod_[:f]]
def mul(self, u, w, mod):
e, f, g = self.e, self.f, self.g
prod_ = [[0] * f for _ in range(2 * e - 1)]
for i, a in enumerate(u):
if any(a):
for j, b in enumerate(w):
if any(b):
c = self.wmul(a, b, mod)
prod_[i + j] = [(s + t) % mod
for s, t in zip(prod_[i + j], c)]
for d in range(2 * e - 2, e - 1, -1):
c = prod_[d]
if any(c):
prod_[d] = [0] * f
for k in range(e):
prod_[d - e + k] = [(s - g[k] * t) % mod for s, t in
zip(prod_[d - e + k], c)]
return prod_[:e]
def power(self, u, k, mod):
r = self.one()
while k:
if k & 1:
r = self.mul(r, u, mod)
u = self.mul(u, u, mod)
k >>= 1
return r
def one(self):
z = [[0] * self.f for _ in range(self.e)]
z[0][0] = 1
return z
def val(self, z, N):
best, mod = self.e * N, self.p ** N
for i, c in enumerate(z):
for cij in c:
cij %= mod
if cij:
best = min(best, self.e * vp(cij, self.p) + i)
return best
def minus_one(self, z, mod):
w = [c[:] for c in z]
w[0][0] = (w[0][0] - 1) % mod
return w
def prec(self, a):
return a // self.e + 2
def xpow(self, i, mod):
x = [[0] * self.f for _ in range(self.e)]
if self.e == 1:
x[0][0] = self.p
else:
x[1][0] = 1
return self.power(x, i, mod)
def ypow(self, j):
z = [[0] * self.f for _ in range(self.e)]
z[0][j] = 1
return z
def E(self, a):
"""The exponent of U_1/U_a from the generators 1 + y^j x^i."""
if a in self.Ecache:
return self.Ecache[a]
N = self.prec(a)
mod, best = self.p ** N, 0
for i in range(1, a):
xi = self.xpow(i, mod)
for j in range(self.f):
z = self.mul(self.ypow(j), xi, mod)
z[0][0] = (z[0][0] + 1) % mod
m = 0
while self.val(self.minus_one(z, mod), N) < a:
z = self.power(z, self.p, mod)
m += 1
best = max(best, m)
self.Ecache[a] = self.p ** best
return self.Ecache[a]
def lam(self, a):
return 1 if a == 0 else (self.q - 1) * self.E(a)
def depth(self, L):
"""a_P: the largest a with lambda(P^a) | L."""
if L % (self.q - 1):
return 0
a = 1
while L % self.lam(a + 1) == 0:
a += 1
return a
def whole_exponent_is(self, a, lam):
"""True iff lam is the exponent of (O_P/P^a)^x, every unit read."""
N = self.prec(a)
mod = self.p ** N
xs = [self.xpow(i, mod) for i in range(a)]
digits = [list(t) for t in product(range(self.p), repeat=self.f)]
units = []
for combo in product(range(len(digits)), repeat=a):
if combo[0] == 0:
continue
z = [[0] * self.f for _ in range(self.e)]
for i, k in enumerate(combo):
if k:
d = [[0] * self.f for _ in range(self.e)]
d[0] = digits[k][:]
t = self.mul(d, xs[i], mod)
z = [[(s + u) % mod for s, u in zip(r1, r2)]
for r1, r2 in zip(z, t)]
units.append(z)
def is_one(z):
return self.val(self.minus_one(z, mod), N) >= a
if not all(is_one(self.power(u, lam, mod)) for u in units):
return False
for l in factor(lam):
if all(is_one(self.power(u, lam // l, mod)) for u in units):
return False
return True
# ------------------------------------------------------------ the fields
class Field:
"""A Galois field K: O_K = Z[t]/(F), K the fixed field of H_K in
Q(mu_fK), and its local towers."""
def __init__(self, name, F, fK, HK, ram, local, ef, cyc):
self.name, self.F, self.fK, self.HK = name, F, fK, HK
self.n = len(F) - 1
self.ram, self.local, self.ef, self.cyc = ram, local, ef, cyc
self.towers = {}
def tower(self, p):
if p not in self.towers:
e, f, h, g = self.local(p)
self.towers[p] = (Tower(p, h, g), e, f, self.n // (e * f))
return self.towers[p]
def residue(self, p):
e, f = self.ef(p)
return e, f, self.n // (e * f)
def quad(d):
D = d if d % 4 == 1 else 4 * d
F = [-(d - 1) // 4, -1, 1] if d % 4 == 1 else [-d, 0, 1]
fK = abs(D)
HK = {a for a in range(1, fK + 1) if gcd(a, fK) == 1
and kronecker(D, a) == 1}
ram = set(factor(abs(D)))
def local(p):
k = kronecker(D, p)
if k == 1:
return 1, 1, [0, 1], [-p, 1]
if k == -1:
return 1, 2, irreducible(p, 2), [-p, 1]
if p == 2 and d % 4 == 3:
return 2, 1, [0, 1], [1 - d, 2, 1]
return 2, 1, [0, 1], [-d, 0, 1]
def ef(p):
k = kronecker(D, p)
return (1, 1) if k == 1 else (1, 2) if k == -1 else (2, 1)
name = "Q(i)" if d == -1 else f"Q(sqrt{d})"
K = Field(name, F, fK, HK, ram, local, ef, False)
K.D = D
return K
def cyc(m):
F = cyclotomic(m) if m > 1 else [-1, 1]
ram = set(factor(m)) if m > 1 else set()
def local(p):
k, m1 = 0, m
while m1 % p == 0:
m1 //= p
k += 1
f = mult_order(p, m1)
h = irreducible(p, f)
g = shift1(cyclotomic(p ** k)) if k else [-p, 1]
return (len(g) - 1), f, h, g
def ef(p):
k, m1 = 0, m
while m1 % p == 0:
m1 //= p
k += 1
return (p ** k - p ** (k - 1) if k else 1), mult_order(p, m1)
name = "Q" if m == 1 else f"Q(mu_{m})"
return Field(name, F, max(m, 1), {1 % max(m, 1)} if m > 1 else {0},
ram, local, ef, True)
def fields():
ds = [-1] + [d for d in range(-50, 51)
if abs(d) >= 2 and all(d % (p * p) for p in (2, 3, 5, 7))]
return ([cyc(1)] + [quad(d) for d in ds]
+ [cyc(m) for m in (3, 4, 5, 7, 8, 9, 12)])
# ----------------------------------------------------- the three objects
def wall(K, L):
"""{p: a_p} over the p with N(P) - 1 | L."""
out = {}
for p in PR:
if p - 1 > L:
break
e, f, g = K.residue(p)
if L % (p ** f - 1):
continue
T = K.tower(p)[0]
a = T.depth(L)
if a:
out[p] = a
return out
def wall_norm(K, W):
N = 1
for p, a in W.items():
e, f, g = K.residue(p)
N *= p ** (f * g * a)
return N
def contraction(K, W):
c = 1
for p, a in W.items():
e, f, g = K.residue(p)
c *= p ** (-(-a // e))
return c
GAL = {}
def gal_exp(K, l, k):
"""The exponent of Gal(K(mu_(l^k))/K) in (Z/l^k)^x."""
M = l ** k
fK, s, f0 = K.fK, 0, K.fK
while f0 % l == 0:
f0 //= l
s += 1
key = (K.name, l, k) if s else (l, k)
if key in GAL:
return GAL[key]
if s == 0:
# a mod l^k and a mod fK are independent (CRT): the image is all
# of (Z/l^k)^x as soon as H_K is nonempty
img = [a for a in range(1, M) if a % l]
else:
big = l ** max(s, k)
mod = big * f0
img = set()
units_f0 = [b for b in range(f0) if gcd(b, f0) == 1] or [0]
# CRT: x = a mod big, b mod f0
inv = pow(f0, -1, big) if big > 1 else 0
for a in range(big):
if a % l == 0:
continue
for b in units_f0:
x = (b + f0 * ((a - b) * inv % big)) % mod
if (x % fK) in K.HK:
img.add(a % M)
break
img = sorted(img)
ex = 1
for a in img:
ex = lcm(ex, mult_order(a, M))
GAL[key] = ex
return ex
def w_def(K, L):
w = 1
for l in PR:
if l > K.n * L + 1:
break
k = 0
while L % gal_exp(K, l, k + 1) == 0:
k += 1
w *= l ** k
return w
NV = {}
def place_norms(K, bound):
if (K.name, bound) not in NV:
out = []
for p in PR:
if p > bound:
break
e, f, g = K.residue(p)
if p ** f <= bound:
out.append((p, p ** f))
NV[(K.name, bound)] = out
return NV[(K.name, bound)]
def w_cheb(K, L, bound=4000):
w = 1
for l in PR:
if l > K.n * L + 1:
break
m = None
for p, Nv in place_norms(K, bound):
if p != l:
v = vp(pow(Nv, L, l ** 40) - 1, l)
m = v if m is None else min(m, v)
if m == 0:
break
w *= l ** m
return w
def det(M):
"""Bareiss, exact integers."""
M = [r[:] for r in M]
n, sign, prev = len(M), 1, 1
for k in range(n - 1):
if M[k][k] == 0:
for i in range(k + 1, n):
if M[i][k]:
M[k], M[i] = M[i], M[k]
sign = -sign
break
else:
return 0
for i in range(k + 1, n):
for j in range(k + 1, n):
M[i][j] = (M[i][j] * M[k][k] - M[i][k] * M[k][j]) // prev
prev = M[k][k]
return sign * M[n - 1][n - 1]
def pmul(u, w, F, mod=None):
n = len(F) - 1
prod_ = [0] * (2 * n - 1)
for i, a in enumerate(u):
if a:
for j, b in enumerate(w):
prod_[i + j] += a * b
for d in range(2 * n - 2, n - 1, -1):
c = prod_[d]
if c:
prod_[d] = 0
for k in range(n):
prod_[d - n + k] -= c * F[k]
r = prod_[:n]
return [c % mod for c in r] if mod else r
def ppow(u, k, F, mod):
r = [1] + [0] * (len(F) - 2)
while k:
if k & 1:
r = pmul(r, u, F, mod)
u = pmul(u, u, F, mod)
k >>= 1
return r
def norm(y, F):
n = len(F) - 1
rows, v = [], y[:]
for _ in range(n):
rows.append(v)
v = pmul(v, [0, 1] + [0] * (n - 2), F) if n > 1 else v
return det(rows) if n > 1 else y[0] * 1
def box(n, B):
return [list(t) for t in product(range(-B, B + 1), repeat=n)
if any(t)]
NORMS = {}
def norms(K, B):
key = (K.name, B)
if key not in NORMS:
NORMS[key] = sorted({norm(y, K.F) for y in box(K.n, B)})
return NORMS[key]
def norm_wall(K, L, B, s=64):
g = 0
for N in norms(K, B):
if g == 0:
g = abs(N ** s * (N ** L - 1))
else:
g = gcd(g, pow(N, s, g) * (pow(N, L, g) - 1) % g)
return g
def adams_index(K, L, B, s=64):
"""The index in O_K of the ideal generated by W(L) and the
y^s (y^L - 1), y over the box."""
n, D = K.n, adams_closed(L)
basis = [[D if j == i else 0 for j in range(n)] for i in range(n)]
def insert(v):
v = [c % D for c in v]
for i in range(n):
if v[i] == 0:
continue
b = basis[i]
g, s1, s2 = xgcd(b[i], v[i])
nb = [(s1 * x + s2 * y) for x, y in zip(b, v)]
v = [(b[i] // g) * y - (v[i] // g) * x for x, y in zip(b, v)]
nb[i] = g
basis[i] = [nb[j] % D if j > i else nb[j] for j in range(n)]
v = [c % D for c in v]
tpow = [[int(j == i) for j in range(n)] for i in range(n)]
for y in box(n, B):
z = ppow(y, L, K.F, D)
z[0] -= 1
z = pmul(ppow(y, s, K.F, D), z, K.F, D)
if not any(z):
continue
for tj in tpow:
insert(pmul(z, tj, K.F, D))
idx = 1
for i in range(n):
idx *= basis[i][i]
return idx
def xgcd(a, b):
x0, x1, y0, y1 = 1, 0, 0, 1
while b:
q = a // b
a, b = b, a - q * b
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
if a < 0:
a, x0, y0 = -a, -x0, -y0
return a, x0, y0
CAP = 40
GENS = {}
def v_place(K, x, p, f, mod):
"""v_P(x) at the one place P over p, read off the norm, capped."""
N = norm([c % mod for c in x], K.F) % mod
v = CAP * f if N == 0 else vp(N, p)
assert v % f == 0
return min(v // f, CAP)
def place_gens(K, p):
"""At the one place P over p: (t, pi), t a generator of (O/P)^x and
v_P(pi) = 1, both searched over boxes of O_K growing from 2."""
if (K.name, p) not in GENS:
e, f, g = K.residue(p)
q, mod = p ** f, p ** (f * (CAP + 1))
rs = list(factor(q - 1)) if q > 2 else []
t, pi = None, ([p] + [0] * (K.n - 1) if e == 1 else None)
for y in (y for B in range(2, p + 1) for y in box(K.n, B)):
if t is None and v_place(K, y, p, f, mod) == 0 and all(
v_place(K, sub1(ppow(y, (q - 1) // r, K.F, mod)), p, f,
mod) == 0 for r in rs):
t = y
if pi is None and v_place(K, y, p, f, mod) == 1:
pi = y
if t is not None and pi is not None:
break
assert t is not None and pi is not None
GENS[(K.name, p)] = (t, pi, f, mod)
return GENS[(K.name, p)]
def sub1(x):
return [x[0] - 1] + x[1:]
def depth_by_norm(K, p, L):
"""a_P = min over the generators t, 1 + t^j pi^b of v_P(g^L - 1), at
a place alone over p; b runs while b < the running min."""
t, pi, f, mod = place_gens(K, p)
F = K.F
a = v_place(K, sub1(ppow(t, L, F, mod)), p, f, mod)
b, pib = 1, pi
while b < a:
tj = [1] + [0] * (K.n - 1)
for j in range(f):
g = pmul(tj, pib, F, mod)
g[0] += 1
a = min(a, v_place(K, sub1(ppow(g, L, F, mod)), p, f, mod))
tj = pmul(tj, t, F, mod)
b += 1
pib = pmul(pib, pi, F, mod)
assert a < CAP
return a
def prime_disc(K):
if K.cyc:
return False
D = K.D
return len(factor(abs(D))) == 1
# -------------------------------------------------------------- sections
BOXES = {1: (60, 120), 2: (30, 45), 4: (4, 5), 6: (2, 3)}
ABOX = {1: 30, 2: 4, 4: 1, 6: 1}
def section_control(Ks):
section("C CONTROLS")
t0 = time.time()
# C1 the tower against the whole unit group
tested = bad = 0
seen = set()
for K in Ks:
for p in PR:
if p > 61:
break
e, f, g = K.residue(p)
if p ** f > 61:
continue
T = K.tower(p)[0]
key = (p, tuple(T.h), tuple(T.g))
if key in seen:
continue
seen.add(key)
a = 1
while T.q ** a <= 20000:
tested += 1
if not T.whole_exponent_is(a, T.lam(a)):
bad += 1
print(f" miss: {K.name} p {p} a {a}")
a += 1
check("C1 (N(P) - 1) E(a) is the whole unit group's exponent, every "
"ring a wall meets (N(P) <= 61), N(P)^a <= 20,000", bad == 0,
f"{tested} (ring, a), {bad} off, {len(seen)} rings")
rec = {"Z_2": ([0, 1], [-2, 1], [1, 2, 2, 4, 8, 16, 32, 64, 128]),
"x^2 + 2": ([0, 1], [2, 0, 1], [1, 2, 4, 4, 4, 8, 8, 16, 16]),
"Q_2(i)": ([0, 1], [2, 2, 1], [1, 2, 4, 4, 4, 4, 4, 8, 8]),
"Q_2(sqrt -5)": ([0, 1], [6, 2, 1],
[1, 2, 4, 4, 4, 4, 8, 8, 16])}
ok = True
for nm, (h, g, seq) in rec.items():
T = Tower(2, h, g)
got = [T.E(a) for a in range(1, 10)]
ok &= got == seq
if got != seq:
print(f" {nm}: {got} against {seq}")
check("C1 E(1..9) at Z_2, x^2 + 2, Q_2(i), Q_2(sqrt -5) as "
"module_law.py printed", ok)
# C2 K = Q
Q = Ks[0]
bad = 0
for L in LS:
W = wall(Q, L)
WL = adams_closed(L)
vals = (wall_norm(Q, W), contraction(Q, W), w_def(Q, L),
norm_wall(Q, L, BOXES[1][0]))
if any(v != WL for v in vals):
bad += 1
print(f" Q, L {L}: {vals} against {WL}")
check("C2 K = Q: N(W) = c = w = n = W(L) at every even L <= 60",
bad == 0, f"{bad} off")
print(f" ({time.time() - t0:.1f} s)")
def run_census(Ks):
section("THE CENSUS every field, every even L <= 60")
t0 = time.time()
R = {}
for K in Ks:
for L in LS:
W = wall(K, L)
R[(K.name, L)] = dict(
W=W, NW=wall_norm(K, W), c=contraction(K, W),
WL=adams_closed(L), w=w_def(K, L),
n=norm_wall(K, L, BOXES[K.n][1]))
print(f" {len(Ks)} fields x {len(LS)} L ({time.time() - t0:.1f} s)")
return R
def section_checks(Ks, R):
section("C3-C8 THE SECOND ROUTES")
t0 = time.time()
# C3 the Adams ideal
bad = n_ = 0
for K in Ks:
Lset = LS if K.n <= 2 else [L for L in (2, 4, 6, 12, 24, 60)
if L in LS]
for L in Lset:
n_ += 1
idx = adams_index(K, L, ABOX[K.n])
if idx != R[(K.name, L)]["NW"]:
bad += 1
if bad <= 8:
print(f" {K.name} L {L}: index {idx}, N(W) "
f"{R[(K.name, L)]['NW']}")
check("C3 the Adams gcd ideal over a box has index N(W_K)", bad == 0,
f"{n_} (field, L), {bad} off")
# C4
pairs = (("Q(mu_3)", "Q(sqrt-3)"), ("Q(mu_4)", "Q(i)"))
ok = all(R[(a, L)][k] == R[(b, L)][k] for a, b in pairs for L in LS
for k in ("NW", "c", "w", "n"))
check("C4 Q(mu_3), Q(mu_4) agree with d = -3, -1 on N(W), c, w, n",
ok)
# C5
bad = 0
for K in Ks:
for L in LS:
if w_cheb(K, L) != R[(K.name, L)]["w"]:
bad += 1
if bad <= 8:
print(f" {K.name} L {L}: Chebotarev "
f"{w_cheb(K, L)}, definition "
f"{R[(K.name, L)]['w']}")
check("C5 w by definition = w by the Chebotarev gcd, N(v) <= 4000",
bad == 0, f"{len(Ks) * len(LS)} (field, L), {bad} off")
# C6
hand = {"Q(i)": ({2: 2}, 2, 24, 24), "Q(sqrt-3)": ({3: 1}, 3, 24, 24),
"Q(sqrt5)": ({}, 1, 120, 120),
"Q(sqrt-15)": ({2: 3, 3: 1}, 24, 24, 120)}
ok = True
for nm, (W, c, w, n) in hand.items():
r = R[(nm, 2)]
got = (r["W"], r["c"], r["w"], r["n"])
ok &= got == (W, c, w, n)
print(f" {nm}, L = 2: W {r['W']} (norm {r['NW']}), c {r['c']}, "
f"w {r['w']}, n {r['n']}")
check("C6 the four hand values at L = 2", ok)
# C7
bad = 0
for K in Ks:
for L in LS:
if norm_wall(K, L, BOXES[K.n][0]) != R[(K.name, L)]["n"]:
bad += 1
check("C7 n read at two boxes agrees", bad == 0,
f"{len(Ks) * len(LS)} (field, L), {bad} off")
# C8 the depth by the norm, at every place alone over its p
n_ = bad = past = 0
for K in Ks:
for p in PR:
e, f, g = K.residue(p)
if p ** f > 61:
if p > 61:
break
continue
if g != 1:
continue
T = K.tower(p)[0]
for L in LS:
a1, a2 = T.depth(L), depth_by_norm(K, p, L)
n_ += 1
bad += a1 != a2
if a1 and T.q ** a1 > 20000:
past += 1
print(f" past C1: {K.name} p {p} L {L}: tower {a1}, "
f"norm {a2}")
elif a1 != a2:
print(f" {K.name} p {p} L {L}: tower {a1}, norm {a2}")
check("C8 the depth read off the norm = the tower's, every place alone "
"over its p", bad == 0,
f"{n_} (field, place, L), {past} past C1, {bad} off")
print(f" ({time.time() - t0:.1f} s)")
def section_verdict(Ks, R):
section("T THE PREDICTIONS")
t1 = []
t2 = []
t3 = []
t5 = []
t6 = []
for K in Ks:
for L in LS:
r = R[(K.name, L)]
c, WL, w, n = r["c"], r["WL"], r["w"], r["n"]
if WL % c or w % WL or n % w:
t1.append((K.name, L))
if (K.cyc or prime_disc(K)) and n != w:
t2.append((K.name, L))
if not K.cyc and K.n == 2:
if L * 2 <= 120 and w_def(K, 2 * L) % n:
t3.append((K.name, L, "n | w_2L"))
for l in factor(n // w) if n % w == 0 else []:
if l not in K.ram:
t3.append((K.name, L, l))
for l in set(factor(n)) | set(factor(WL)):
if l not in K.ram and vp(n, l) != vp(WL, l):
t5.append((K.name, L, l))
for l in factor(w):
if vp(w, l) > vp(WL, l) and l not in K.ram:
t6.append((K.name, L, l))
tot = len(Ks) * len(LS)
check("T1 c | W(L) | w | n at every (K, L)", not t1,
f"{tot} (field, L), {len(t1)} off {t1[:5]}")
nt2 = sum(len(LS) for K in Ks if K.cyc or prime_disc(K))
check("T2 n = w at every cyclotomic and prime-discriminant field",
not t2, f"{nt2} (field, L), {len(t2)} off {t2[:5]}")
check("T3 quadratic: n | w_2L and n / w on primes dividing D",
not t3, f"{len(t3)} off {t3[:5]}")
check("T5 v_l(n) = v_l(W(L)) at every l unramified in K", not t5,
f"{len(t5)} off {t5[:5]}")
check("T6 v_l(w) > v_l(W(L)) only at l ramified in K", not t6,
f"{len(t6)} off {t6[:5]}")
def section_observed(Ks, R):
section("O OBSERVED")
tot = len(Ks) * len(LS)
cW = sum(r["c"] == r["WL"] for r in R.values())
wW = sum(r["w"] == r["WL"] for r in R.values())
nw = [(k, r["n"] // r["w"]) for k, r in R.items() if r["n"] != r["w"]]
triv = sum(r["NW"] == 1 for r in R.values())
print(f" c = W(L) at {cW} of {tot}; w = W(L) at {wW} of {tot}; "
f"W_K = (1) at {triv} of {tot}; n != w at {len(nw)} of {tot}")
byK = {}
for (nm, L), q in nw:
byK.setdefault(nm, []).append((L, q))
for nm, rows in byK.items():
print(f" n / w at {nm}: {rows[:6]}{' ...' if len(rows) > 6 else ''}"
f" ({len(rows)} L)")
odd, two, form = {}, [], 0
for nm, rows in byK.items():
for L, q in rows:
for l, e in factor(q).items():
if l > 2:
form += (e == 1 + vp(L, l) and L % ((l - 1) // 2) == 0
and L % (l - 1) != 0)
odd.setdefault(l, set()).add(nm)
if len(rows) == len(LS) and all(q % 4 == 2 for L, q in rows):
two.append(nm)
nodd = sum(1 for (nm, L), q in nw for l in factor(q) if l > 2)
print(f" {len(byK)} fields with n != w; odd (field, L, l) in n / w: "
f"{nodd}, "
f"of the form l^(1 + v_l(L)), (l - 1)/2 | L, (l - 1) not | L: "
f"{form}")
for l in sorted(odd):
print(f" l = {l}: {sorted(odd[l])}")
print(f" 2 || n / w at every L: {two}")
print(" per field at L = 2, 12, 60: (N(W), c, W(L), w, n)")
for K in Ks:
row = [(R[(K.name, L)]["NW"], R[(K.name, L)]["c"],
R[(K.name, L)]["WL"], R[(K.name, L)]["w"],
R[(K.name, L)]["n"]) for L in (2, 12, 60)]
print(f" {K.name:12s} {row}")
def main():
t0 = time.time()
Ks = fields()
print(f"numwall.py: {len(Ks)} fields, L over every even L <= 60")
section_control(Ks)
R = run_census(Ks)
section_checks(Ks, R)
section_verdict(Ks, R)
section_observed(Ks, R)
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks PASS "
f"({time.time() - t0:.1f} s)")
return 0 if all(CHECKS) else 1
if __name__ == "__main__":
sys.exit(main())