staircase.py
Checks: OBSERVATORY: The jump set as the class maxima theorem.
Cited on: OBSERVATORY.
To run it: save staircase.py, with clock.py, module_law.py, rung.py, tame.py, triangle.py, weld.py, wild.py beside it; standard library only.
"""staircase.py -- the jump set is the staircase of the class maxima in
every field holding zeta_p, however many p-power roots of unity it holds.
QUESTION. Let K/Q_p be totally ramified of degree e, cut out by an
Eisenstein F with root pi and u = p/pi^e (triangle.py), holding zeta_p,
so the bend s = e/(p - 1) = c_0 p^M with p not dividing c_0, and e* = p
s. Let p^N be the order of the p-power roots of unity in K. rung.py read
the jump set of Pagano (Jump sets in local fields, arXiv:1810.09975) off
the highest landings of the classes Gamma_m = (s/p^m, m), 0 <= m <= M, at N
= 1. Does the same staircase hold at N >= 2, where Q_2(i), Q_2(zeta_2e)
and Q_3(zeta_9) live?
THE DERIVATION (on paper, before the engine).
(1) THE CLASS MAXIMUM, AT EVERY N. Let G(m) be the largest v(zeta_p h
- 1) over h in H_m = U_1^(p^m), infinite when zeta_p lies in H_m.
rung.py's step (1) never used N = 1: for y of level s in H_m,
v(y^p - 1) > e* (ubar = -1), and if it is e* + j then y = zeta_p^a
y' with y' in U_(s+j) (the p-th roots of unity are still mu_p), so a
landing of Gamma_m is e* + v(zeta_p^(-a) y - 1) - s, at most e* + G(m)
- s, attained when G(m) > s. zeta_p = zeta^(p^(N-1)) for zeta a
generator of order p^N, so G(m) is infinite exactly at m < N: the
class Gamma_m holds a primitive p^(m+1)-th root of unity, level
s/p^m, and its maximum is infinite.
(2) G OFF THE JUMP SET. In Pagano's presentation U_1 = F/R v, v =
sum_(i in I) p^beta(i) e_i, the torsion generator is m~ = sum
p^(beta(i) - N) e_i (N = min beta, Proposition 3.42), and zeta_p
is p^(N-1) m~ = sum p^(beta(i) - 1) e_i. The proof of his
Proposition 3.35, which he imitates for 3.39, runs unchanged on
this vector: modulo p^m F it is the sum over beta(i) <= m, whose
weight is the least rho^(beta(i) - 1)(i); a multiple r v = p r
(p^(N-1) m~) only multiplies it by the unit 1 + p r; and an added
p^m z that raised the weight would need rho^m(w(z)) =
rho^(beta(i_0) - 1)(i_0) with m >= beta(i_0), putting i_0 in rho's
image, which no element of T* is but e*, excluded as in his proof.
So
G(m) = min{ rho^(beta(i) - 1)(i) : beta(i) <= m },
infinite when no beta is at most m, that is at m < N. The minimum
sits at the point with the largest beta <= m, since rho is
strictly increasing and preserves the order of the weights. For
beta(i) <= M the weight exceeds e*, so G(m) > s at N <= m <= M and
the class maximum is
H(m) = G(m) + e = min{ rho^beta(i)(i) : beta(i) <= m },
the N = 1 formula verbatim, with H infinite below N. The staircase
of H above the first point (c_0, M + 1) is the jump set, its last
step at beta = N. The lower bound G(m) >= rho^(N-1)(g(m - N + 1)),
g the weight of zeta modulo p^n-th powers, is elementary (the p-th
power map never falls below rho); the upper bound is the step that
needs the presentation, since an element whose orbit meets level s
can jump past rho there.
(3) THE FLOOR. The readouts (tame.py, wild.py) give the least landing
e* + min(dep_m, X_m), the class one value iff dep_m < X_m; they
never used N = 1. A class with an infinite maximum is not one
value, so at m < N, dep_m >= X_m: at odd p every field with
zeta_(p^N) has l >= p^(N - 1), and over 2 a field holding
zeta_(2e) has lam >= 3e/2. The spectrum of Gamma_m lies in
[min(H(m), e* + X_m), H(m)] at every m.
(4) THE SECOND POINT. At a rigid seat (M >= N, dep_M < X_M), W_2 = e*
+ D with D = dep_M. At N >= 2, D > e is possible (the N = 1 bound
D <= e used that zeta_p is not a p-th power). Pulling e* + D back
through rho: write D = q e + r, 0 <= r < e. If r = 0 the point is
(e*, q); otherwise q + 1 steps of -e reach s + r in (s, e*), then
division by p while p divides, v = v_p(s + r):
(i_2, beta_2) = ((s + r)/p^v, q + 1 + v).
At N = 1 this is rung.py's form (q = 0, or D = e giving (e*, 1)).
At N >= 2 every beta is at least 2, so D = e never occurs; over 2 a
rigid top class with lam in (e, 3e/2) reads q = 1.
THE ENGINE. G(n) as weld.py reads g: the filtered echelon of H_n in
U_1/U_L, zeta_p lifted from 1 + pi^s. N is the least n with G(n) below
precision. Independently, a primitive p^N-th root of unity is found by a
pruned digit search in the class of level s/p^(N-1): a K-digit
truncation of a root differs from it by a factor in U_(c+K), so its
p^N-th power sits at rho^N(c + K) or deeper, and the search keeps
exactly the truncations passing that test; at precision L + N e + 1 a
survivor agrees with a root modulo U_(L+1). PAGANO'S READING, verbatim:
Proposition 3.39 on that root, gz(n) its weight modulo p^n-th powers,
breaks at n = beta(i) - N with gz(n + 1) = rho^n(i), so each break is
the point (pullback of gz(n + 1) through rho^n, n + N). The class maxima
by brute force (rung.py's method, with its own precision): every unit of
Gamma_m to K digits past its level, K the least >= 4 with rho^(m+1)(c + K)
above the target (G(m) + e, or e* + X_m where G is infinite); a class
with more than CAP truncations is skipped and counted.
TRANSPLANTS. rung.py's derivation at N = 1 is imported for (1) and (3);
the claim that neither used N = 1 is this slate's, re-read above. The
generalized closed form (4) is new.
POPULATIONS. Over 2, fields designed with lam > e at e = 4, 8, 16 (lam
from e + 1 to 3e/2 + 2 and two random lam in (e, 2e + 4]), which hold
i (weld.py I). The polynomials Phi_(p^N)(1 + x^k + p Omega(x)), deg
Omega < k, Eisenstein of degree k (p - 1) p^(N-1), whose root pi gives
zeta = 1 + pi^k + p Omega(pi) of order p^N: (p, N, k) = (2, 2, 2), (2,
2, 4), (2, 2, 6), (2, 2, 8), (2, 3, 2), (2, 3, 4), (2, 4, 2), (3, 2,
2), (3, 2, 3), (3, 3, 1), (5, 2, 1), Omega = 0 and two random Omega
with digits below p^2. N is read, never assumed.
PREDICTIONS, fixed before the run.
C CONTROL, run first. Pagano's reading and the brute staircase both
print: x^6 + 3x^3 + 3 (N = 1) (1, 2), (7, 1); x^12 - 2 (N = 1) (3,
3), (9, 2), (21, 1); Q_3(zeta_9) = Phi_9(x + 1) (N = 2) (1, 2);
Q_2(zeta_8) (N = 3) (1, 3); Q_2(zeta_16) (N = 4) (1, 4). At each,
the root search finds an element of order exactly p^N, finds none
of order p^(N+1), and N, the least n with G(n) finite, is the
field's.
Z THE ROOT. At every population field the search finds a root of
order p^N with N read off G, and none of order p^(N+1); at the
cyclotomic polynomials N is at least the generator's.
R THE CLASS MAXIMUM. At every enumerated class with m >= N the
largest brute landing is G(m) + e; at m < N some truncation reaches
its own floor rho^(m+1)(c + K).
S THE STAIRCASE. At every field with every class enumerated, the
staircase of the brute maxima (H infinite below N) equals Pagano's
reading off the root and equals the set rebuilt from G by (2); the
last point has beta = N (by construction: H is finite from N on,
and N <= M + 1 since p^(N-1) divides s, the first point itself at
N = M + 1), the first (c_0, M + 1) at e*.
F THE FLOOR. At every enumerated class the least brute landing is
min(H(m), e* + X_m), the class is one value iff dep_m < X_m, and
dep_m >= X_m at every m < N.
P THE SECOND POINT. At every rigid seat with M >= N the point with
the second largest beta is (4)'s closed form.
KILLS, as printed observables: a C line off (nothing below is read); a
field with no root found or one of order p^(N+1); one class off R; one
field whose three sets are not equal; one
class off F; one rigid seat off P.
FINDINGS. Every prediction landed: 10/10 checks PASS, no kill fired.
C Pagano's reading off the lifted root and the brute staircase both
print x^6 + 3x^3 + 3's (1, 2), (7, 1) and x^12 - 2's (3, 3), (9,
2), (21, 1) at N = 1, and (1, 2), (1, 3), (1, 4) at Q_3(zeta_9),
Q_2(zeta_8), Q_2(zeta_16), with N = 2, 3, 4 read off G.
Z 59 fields, by N: 46 at 2, 10 at 3, 2 at 4, 1 at 5 (Phi_16(1 + x^2
+ 2 Omega), Omega = 3x, is Q_2(zeta_32) at e = 16). A root of order
exactly p^N at all 59, none of order p^(N+1). Over 2 the designed
fields carry N built = 1 (they hold i, read N >= 2), so their
N >= N built cannot fail.
R 168 classes: every maximum at m >= N is G(m) + e, every class
below N reaches its truncation floor.
S At all 59 fields (no class over CAP) the three sets agree, the
last beta N by construction; up to four points (p = 2, e = 16,
N = 2, Omega = 0: (1, 5), (5, 4), (13, 3), (29, 2)).
F At all 168 classes the least landing is min(H(m), e* + X_m), one
value exactly when dep_m < X_m, and never one value below N.
P At the 20 rigid seats the closed form holds, every one over 2 with
D > e, the q = 1 branch: e = 8, lam = 10 reads (5, 3), e = 16, D =
20 reads (5, 4). No rigid seat at an odd prime with N >= 2 occurred
(the Phi family gives l >= p^M there), so that branch is proved and
not exercised. (cofactor.py designs rigid seats at p = 3, N = 2, e
= 18, and the closed form holds at all four.)
Tiers: (1) and (3) a theorem with no outside result; (2) and (4) a
theorem given Pagano's presentation (Theorem 1.5) and the proof of
his Proposition 3.35, run on p^(N-1) m~.
RUN RECORD. 10/10, 38.1 s wall, peak working set 13.7 MB under
a memory guard. A first run also held (p, N, k) = (3, 2, 6), e = 36; it had
passed the controls and printed its first fields with no OFF line when
it was stopped at twice its time estimate, the e = 36 fields costing
minutes each with their seat class over CAP. The spec was dropped
before any check was read, and the run above is the second.
"""
import os
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import random
from module_law import check, section, CHECKS, vp
from tame import local, INF
import wild
from weld import Units, power_subgroup, zeta_p, pullback, rho, weight, \
jump_set
from rung import class_dep
SEED = 1428
CAP = 20000
SURVIVORS = 4000
# ------------------------------------------------------------ polynomials
def pmul(a, b):
out = [0] * (len(a) + len(b) - 1)
for i, x in enumerate(a):
if x:
for j, y in enumerate(b):
out[i + j] += x * y
return out
def padd(a, b):
n = max(len(a), len(b))
return [(a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0)
for i in range(n)]
def ppow(a, k):
r = [1]
while k:
if k & 1:
r = pmul(r, a)
a = pmul(a, a)
k >>= 1
return r
def cyclo(p, N, k, r):
"""(e, b, d) of Phi_(p^N)(1 + x^k + p Omega(x)), r Omega's
coefficients."""
h = [0] * (k + 1)
h[k] = 1
for i, c in enumerate(r):
h[i] += p * c
y = [1 + h[0]] + h[1:]
yq = ppow(y, p ** (N - 1))
total, acc = [0], [1]
for _ in range(p):
total = padd(total, acc)
acc = pmul(acc, yq)
e = len(total) - 1
assert total[e] == 1 and all(c % p == 0 for c in total[:e])
assert total[0] % p ** 2 != 0
b = [0] + [total[i] // p for i in range(1, e)]
return e, b, -total[0] // p
# ------------------------------------------------------------ the field
def cap_X(p, e, c):
return class_dep(p, e, [0] * e, 1, c)[1]
def read_deep(p, e, b, d):
"""G(0..M+2), N, and the echelons, at precision L."""
s = e // (p - 1)
M = vp(s, p)
es = p * s
L = es + (M + 1) * e + 3
U = Units(p, e, b, d, L)
Z = Units(p, e, b, d, L + e)
z = [c % U.mod for c in zeta_p(Z, s)]
ech = {n: power_subgroup(U, n)[0] for n in range(1, M + 3)}
G = {0: L}
for n in range(1, M + 3):
G[n] = ech[n].reduce(z)[1]
N = min(n for n in range(1, M + 3) if G[n] < L)
return dict(s=s, M=M, c0=s // p ** M, es=es, L=L, U=U, G=G, N=N,
ech=ech)
def root_search(p, e, b, d, n, Lp):
"""A unit of level s/p^(n-1) with z^(p^n) = 1 mod pi^Lp, or None."""
s = e // (p - 1)
if s % p ** (n - 1):
return None
c = s // p ** (n - 1)
V = Units(p, e, b, d, Lp)
pis = {}
def pi(j):
if j not in pis:
pis[j] = V.loc.pi_pow(j, V.mod)
return pis[j]
def add(z, a, j):
return [(x + a * y) % V.mod for x, y in zip(z, pi(j))]
cands = [add(V.one, a, c) for a in range(1, p)]
K = 1
while True:
floor = c + K
for _ in range(n):
floor = rho(p, e, floor)
floor = min(floor, Lp)
keep = [z for z in cands if V.lead(V.pw(z, p ** n))[0] >= floor]
if not keep:
return None
if floor >= Lp:
return keep[0]
if len(keep) > SURVIVORS:
raise RuntimeError("root search: too many survivors")
cands = [add(z, a, c + K) for z in keep for a in range(p)]
K += 1
def pagano_reading(p, e, rec, zeta):
"""Proposition 3.39 on the torsion generator: the jump set."""
U, N, M, L = rec["U"], rec["N"], rec["M"], rec["L"]
z = [x % U.mod for x in zeta]
gz = {0: L}
for n in range(1, M + 3 - N):
gz[n] = rec["ech"][n].reduce(z)[1]
pts = []
for n in range(0, M + 2 - N):
if gz[n] != gz[n + 1]:
pts.append((pullback(p, e, gz[n + 1], n), n + N))
return sorted(pts), gz
def landings(p, e, b, d, c, m, K, bound):
"""v(z^(p^(m+1)) - 1), capped past bound, over the K-digit units of
level c."""
prec = bound // e + 3
mod = p ** prec
loc = local(p, e, b, d)
pis = [loc.pi_pow(c + j, mod) for j in range(K)]
out = []
for idx in range((p - 1) * p ** (K - 1)):
digs = [1 + idx % (p - 1)]
rest = idx // (p - 1)
for _ in range(K - 1):
digs.append(rest % p)
rest //= p
z = [1] + [0] * (e - 1)
for a, t in zip(digs, pis):
if a:
z = [(x + a * y) % mod for x, y in zip(z, t)]
for _ in range(m + 1):
z = loc.power(z, p, mod)
out.append(loc.val([z[0] - 1] + z[1:], prec))
return out
def brute(p, e, b, d, rec):
"""{m: (hi, lo, values, K)} over 1 <= m <= M, and the skipped count."""
s, G, L, es = rec["s"], rec["G"], rec["L"], rec["es"]
out, skipped = {}, 0
for m in range(1, rec["M"] + 1):
c = s // p ** m
X = cap_X(p, e, c)
target = G[m] + e if G[m] < L else es + X
K = 4
while True:
fl = c + K
for _ in range(m + 1):
fl = rho(p, e, fl)
if fl > target:
break
K += 1
if (p - 1) * p ** (K - 1) > CAP:
skipped += 1
continue
land = landings(p, e, b, d, c, m, K, fl)
out[m] = (max(land), min(land), set(land), fl)
return out, skipped
def staircase(p, e, s, M, H):
pts, prev = [(s // p ** M, M + 1)], INF
for bt in range(1, M + 1):
if H[bt] < prev:
pts.append((pullback(p, e, H[bt], bt), bt))
prev = H[bt]
return sorted(pts)
def second_closed(p, e, D):
s = e // (p - 1)
q, r = divmod(D, e)
if r == 0:
return (p * s, q)
v = vp(s + r, p)
return ((s + r) // p ** v, q + 1 + v)
def second_point(pts):
return sorted(pts, key=lambda t: -t[1])[1]
def shaped(p, e, pts, rec):
"""First point (c_0, M + 1) at e*, beta down, weights up."""
by = sorted(pts, key=lambda t: -t[1])
return (all(i is not None for i, _ in by)
and by[0] == (rec["c0"], rec["M"] + 1)
and weight(p, e, *by[0]) == rec["es"]
and all(weight(p, e, *by[k]) < weight(p, e, *by[k + 1])
for k in range(len(by) - 1)))
def read_all(p, e, b, d):
"""Everything one field prints."""
rec = read_deep(p, e, b, d)
N, L = rec["N"], rec["L"]
Lp = L + N * e + 1
root = root_search(p, e, b, d, N, Lp)
higher = root_search(p, e, b, d, N + 1, Lp)
J = pagano_reading(p, e, rec, root)[0] if root is not None else None
br, skipped = brute(p, e, b, d, rec)
H = {m: (br[m][0] if m >= N else INF) for m in br}
st = (staircase(p, e, rec["s"], rec["M"], H) if skipped == 0
else None)
fromG = jump_set(p, e, rec["G"], rec["M"] + 1)
return dict(rec=rec, root=root, higher=higher, J=J, br=br,
skipped=skipped, H=H, st=st, fromG=fromG)
# ------------------------------------------------------------ populations
CONTROLS = [("x^6 + 3x^3 + 3", 3, 6, [0, 0, 0, 1, 0, 0], -1, 1,
[(1, 2), (7, 1)]),
("x^12 - 2", 2, 12, [0] * 12, 1, 1, [(3, 3), (9, 2), (21, 1)])]
CYCLO_CONTROLS = [("Q_3(zeta_9)", 3, 2, [(1, 2)]),
("Q_2(zeta_8)", 2, 3, [(1, 3)]),
("Q_2(zeta_16)", 2, 4, [(1, 4)])]
SPECS = [(2, 2, 2), (2, 2, 4), (2, 2, 6), (2, 2, 8), (2, 3, 2), (2, 3, 4),
(2, 4, 2), (3, 2, 2), (3, 2, 3), (3, 3, 1), (5, 2, 1)]
def population(rng):
out = []
for e in (4, 8, 16):
lams = list(range(e + 1, 3 * e // 2 + 3))
lams += [rng.randrange(e + 1, 2 * e + 5) for _ in range(2)]
for lam in lams:
b, d = wild.designed(rng, e, lam, 2 * e + 4)
out.append((f"lam={lam}", 2, e, b, d, 1))
for p, N, k in SPECS:
for t in range(3):
r = [] if t == 0 else [rng.randrange(p ** 2) for _ in range(k)]
e, b, d = cyclo(p, N, k, r)
out.append((f"Phi_{p}^{N}(1+x^{k}+p Omega) Omega={r}",
p, e, b, d, N))
return out
# ------------------------------------------------------------ sections
def section_control():
section("C CONTROL: Pagano's reading and the brute staircase print "
"known sets")
rows = [(n, p, e, b, d, N, want) for n, p, e, b, d, N, want in CONTROLS]
for name, p, N, want in CYCLO_CONTROLS:
e, b, d = cyclo(p, N, 1, [])
rows.append((name, p, e, b, d, N, want))
for name, p, e, b, d, N, want in rows:
f = read_all(p, e, b, d)
rec = f["rec"]
ok = (rec["N"] == N and f["root"] is not None
and f["higher"] is None and f["J"] == want
and f["st"] == want)
check(f"C {name}: N = {N}, {want}", ok,
f"N read {rec['N']}, root {'found' if f['root'] else 'NONE'},"
f" order p^(N+1) {'FOUND' if f['higher'] else 'none'}, "
f"Pagano {f['J']}, staircase {f['st']}")
def section_fields(rng):
section("Z, R, S, F, P THE ROOT, THE CLASS MAXIMA, THE STAIRCASE, "
"THE FLOOR, THE SECOND POINT")
bad = dict(Z=0, R=0, S=0, F=0, P=0)
n = dict(Z=0, R=0, S=0, F=0, P=0, skipped=0)
byN = {}
for label, p, e, b, d, Ngen in population(rng):
f = read_all(p, e, b, d)
rec = f["rec"]
s, M, N, es, G, L = (rec["s"], rec["M"], rec["N"], rec["es"],
rec["G"], rec["L"])
byN[N] = byN.get(N, 0) + 1
n["Z"] += 1
okZ = f["root"] is not None and f["higher"] is None and N >= Ngen
bad["Z"] += not okZ
n["skipped"] += f["skipped"]
row = []
for m, (hi, lo, vals, fl) in sorted(f["br"].items()):
c = s // p ** m
dep, X = class_dep(p, e, b, d, c)
n["R"] += 1
okR = hi == G[m] + e if m >= N else hi >= fl
bad["R"] += not okR
H = f["H"][m]
n["F"] += 1
okF = (lo == min(H, es + X)
and (len(vals) == 1) == (dep < X)
and (m >= N or dep >= X))
bad["F"] += not okF
row.append(f"m={m}:[{lo - es},"
f"{'inf' if H >= INF else H - es}]")
if not (okR and okF):
print(f" OFF p={p} e={e} {label} m={m}: brute "
f"[{lo},{hi}] G+e={G[m] + e} dep={dep} X={X} "
f"floor {fl} values {sorted(vals)[:12]}")
if f["skipped"] == 0:
n["S"] += 1
okS = (f["J"] is not None and f["st"] == f["J"] == f["fromG"]
and shaped(p, e, f["J"], rec))
bad["S"] += not okS
if not okS:
print(f" OFF p={p} e={e} {label}: staircase {f['st']}, "
f"Pagano {f['J']}, from G {f['fromG']}")
dep, X = class_dep(p, e, b, d, s // p ** M)
if M >= N and dep < X and f["J"] is not None:
n["P"] += 1
want = second_closed(p, e, dep)
got = second_point(f["J"])
bad["P"] += got != want
if got != want:
print(f" OFF p={p} e={e} {label}: second point {got}, "
f"closed form {want} (dep {dep})")
if not okZ:
print(f" OFF p={p} e={e} {label}: root "
f"{'found' if f['root'] else 'NONE'}, higher "
f"{'FOUND' if f['higher'] else 'none'}, N {N} "
f"(generator {Ngen})")
print(f" p={p} e={e:2d} N={N} M={M} {label:30s} "
f"Pagano {f['J']} excess {' '.join(row)}")
print(f" fields by N: {dict(sorted(byN.items()))}; "
f"{n['skipped']} classes over CAP skipped")
check("Z a root of order exactly p^N, N read off G", bad["Z"] == 0,
f"{n['Z']} fields, {bad['Z']} off")
check("R class maximum G(m) + e at m >= N, at or past the "
"truncation's floor below N",
bad["R"] == 0, f"{n['R']} classes, {bad['R']} off")
check("S brute staircase = Pagano's reading = the set from G",
bad["S"] == 0, f"{n['S']} fields, {bad['S']} off")
check("F least landing min(H, e* + X), one value iff dep < X, "
"dep >= X below N", bad["F"] == 0,
f"{n['F']} classes, {bad['F']} off")
check("P the rigid seat's second point in closed form", bad["P"] == 0,
f"{n['P']} fields, {bad['P']} off")
def main():
rng = random.Random(SEED)
section_control()
if not all(CHECKS):
print("\ncontrol failed: nothing below is read")
raise SystemExit(1)
section_fields(rng)
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks PASS")
if not all(CHECKS):
raise SystemExit(1)
if __name__ == "__main__":
main()