"""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()