"""cofactor.py -- at an odd prime, the departure of a field holding zeta_(p^N) is p^(N-1) times the level of that root's cofactor, capped at the bend, and it can sit below p^M. QUESTION. Let p be odd and K/Q_p totally ramified of degree e, cut out by an Eisenstein F with root pi and u = p/pi^e (triangle.py), holding zeta_(p^N) and no higher p-power root of unity, so the bend s = e/(p - 1) = c_0 p^M with p not dividing c_0, and M >= N - 1. staircase.py proved that no class below N is rigid, so the departure l = v(u + 1) of tame.py is at least p^(N-1). Every field it read with N >= 2 had l >= p^M, so its seat class (level c_0, m = M) was never rigid there. Is l >= p^M forced when N >= 2, or does a field exist with p^(N-1) <= l < p^M? And what fixes min(l, s), the number the width reads? THE DERIVATION (on paper, before the engine). (1) THE PRIME ROOT. Write zeta_p - 1 = pi^s tau_p, tau_p a unit. Phi_p(zeta_p) = 0 reads p (1 + (p - 1)/2 (zeta_p - 1) + ...) = -(zeta_p - 1)^(p-1), so -p/(zeta_p - 1)^(p-1) = eps with v(eps - 1) = s exactly ((p - 1)/2 is a unit at odd p). Since p = u pi^((p-1)s), u = -tau_p^(p-1) eps, and u + 1 = 1 - tau_p^(p-1) eps. tau_p^(p-1) is a principal unit whose level j is that of tau_p's principal part (tau_p over its Teichmueller digit), since p - 1 is a unit exponent. So l >= min(j, s), with equality unless j = s: min(l, s) = min(j, s). (2) THE CLIMB. Let zeta be a primitive p^N-th root of unity and mu = zeta - 1 = pi^c tau, c = s/p^(N-1), tau a unit; call i_tau the level of tau's principal part. For Xi of level y <= s/p, (1 + Xi)^p - 1 = Xi^p (1 + delta), delta = sum over 1 <= k <= p - 1 of C(p, k) Xi^(k - p), at level at least e - (p - 1) y >= (p - 1)^2 s/p, which exceeds s at every odd p (p^2 - 3p + 1 > 0). Each later p-th power keeps a principal correction at or above its level, so zeta_p - 1 = mu^(p^(N-1)) (1 + delta'), v(delta') > s, and tau_p = tau^(p^(N-1)) (1 + delta'). Below the bend a p-th power multiplies a principal level by p, so j = p^(N-1) i_tau whenever p^(N-2) i_tau < s, and j > s otherwise. With (1): min(l, s) = min(p^(N-1) i_tau, s), the COFACTOR READOUT. At N = 1 it is (1) itself. It gives the floor l >= p^(N-1) at once (i_tau >= 1), and more: below s, l is a multiple of p^(N-1). i_tau is not a field invariant, but min(l, s) is (tame.py), so min(p^(N-1) i_tau, s) is too. (3) THE DESIGN. Over L = Q_p(zeta_(p^N)), varpi = zeta - 1, the polynomial x^k + a varpi x^i - varpi (1 <= i < k, p not dividing a) is Eisenstein, and its root pi has varpi = pi^k/(1 - a pi^i): tau = 1/(1 - a pi^i), i_tau = i. Its norm to Q_p is the homogenized cyclotomic polynomial F = sum over 0 <= j < p of A^(j q) B^((p-1-j) q), A = 1 - a x^i + x^k, B = 1 - a x^i, q = p^(N-1), monic of degree e = k (p - 1) p^(N-1), F = (A - B)^e = x^e mod p, F(0) = p: Eisenstein, and F(pi) = B^e Phi_(p^N)(A/B)(pi) with A/B = zeta. So s = k p^(N-1), and (2) predicts l = p^(N-1) i for every i < k. The seat is rigid iff l < p^M, and M = v_p(k) + N - 1, so iff i < p^(v_p(k)): at p = 3, N = 2, k = 3, e = 18, the designs i = 1, 2 give l = 3, 6 < 9 = p^M, a rigid seat at an odd prime with N = 2. N stays the design's when i < p: a higher root would force l >= p^N > p^(N-1) i. (4) THE SECOND POINT there. staircase.py's closed form at D = l < e: q = 0, r = l, (i_2, beta_2) = ((s + l)/p^v, 1 + v), v = v_p(s + l); at s = 9, l = 3 gives (4, 2), l = 6 gives (5, 2), each after the first point (1, 3). beta_2 >= N = 2 needs p^(N-1) | l, which (2) supplies: the jump set's constraint and the readout's divisibility are one fact. THE ENGINE. N and the root as staircase.py reads them (read_deep's G, root_search at N and N + 1); i_tau at every primitive root zeta^a, 1 <= a < p^N, p not dividing a, as v(mu^(p-1) - pi^(c(p-1))) - c(p - 1), which is v(tau^(p-1) - 1), the level of tau's principal part. l is tame.py's departure off the coefficients. At the rigid designs, staircase.py's read_all prints the brute staircase, Pagano's reading and the set from G. TRANSPLANTS. None in the readout: (1) and (2) are this slate's, and the claim that a correction exceeds s is odd-p only. The rigid-seat prediction (3)-(4) uses staircase.py's closed form, a theorem there. POPULATIONS. The designs (p, N, k; i; a): (3, 2, 3; i = 1, 2; a = 1, 2), (3, 2, 2; i = 1; a = 1, 2), (3, 2, 4; i = 1, 2, 3; a = 1, 2), (5, 2, 2; i = 1; a = 1, 2); at i >= k the norm is not monic, so the capped case is read on the cyclotomic family instead: staircase.py's Phi_(p^N)(1 + x^c + p Omega(x)), c (staircase.py's k), at (p, N, c) = (3, 2, 2), (3, 2, 3), (3, 3, 1), (5, 2, 1), Omega = 0 and two random Omega of degree below c with digits below p^2. Its root pi gives zeta = 1 + pi^c + p Omega(pi), so tau = 1 + p Omega(pi)/pi^c sits at level e - c or deeper, past the bend. PREDICTIONS, fixed before the run. C CONTROL, run first. (a) The level reader returns j on pi^c (1 + pi^j), j = 1..5, at x^6 + 3x^3 + 3 and at Q_3(zeta_9). (b) At x^6 + 3x^3 + 3 (N = 1, s = 3) and Q_3(zeta_3) = Phi_3(x + 1) (N = 1, s = 1) and Q_3(zeta_9) (N = 2, s = 3) the readout holds, and at both cyclotomic fields min(l, s) = s. R THE READOUT. At every field and every primitive root, min(l, s) = min(p^(N-1) i_tau, s). D THE DESIGN. At every design, N is the design's when i < p, and l = p^(N-1) i. K THE RIGID SEAT. At (3, 2, 3), i = 1, 2, both a: the seat class is one value, e* + l = 30 or 33; the brute staircase, Pagano's reading and the set from G all print [(1, 3), (4, 2)] at i = 1 and [(1, 3), (5, 2)] at i = 2, and the second point is the closed form. This kills the suspicion that zeta_(p^2) forces l >= p^M. KILLS, as printed observables: a C line off (nothing below is read); one (field, root) off R; one design off D; one rigid design whose seat prints more than one value or whose three sets differ from K's. FINDINGS. Every prediction landed: 8/8 checks PASS, no kill fired. C The reader returns 1..5 at both fields. The readout holds at x^6 + 3x^3 + 3 (l = 3, i_tau 3 or the precision cap 18), Q_3(zeta_3) (l = 1) and Q_3(zeta_9) (N = 2, l = 3 = s, i_tau 1, 2 or the cap 22 by root). R 26 fields, every primitive root: min(l, s) = min(p^(N-1) i_tau, s). i_tau moves with the root only at or above c, where the cap hides it. D 14 designs: l = 3, 6, 9 at p = 3 (k = 2, 3, 4) and l = 5 at p = 5, e = 40, each p^(N-1) i, N = 2 wherever read (i < p). K At (3, 2, 3), e = 18, s = 9, M = 2: l = 3 and 6, below p^M = 9; the seat class lands at the one value 30 or 33, and the brute staircase, Pagano's reading and the set from G print [(1, 3), (4, 2)] and [(1, 3), (5, 2)], the closed form's second point. The suspicion that zeta_(p^2) forces l >= p^M is dead; the cyclotomic family missed the rigid seat because its tau = 1 + p Omega(pi)/pi^c sits past the bend, and its l printed exactly s at all twelve. Tiers: the cofactor readout (2) a theorem; the design (3) a theorem given (2); the rigid seat's staircase an instance of staircase.py's. RUN RECORD. 8/8, 88.6 s wall, peak working set 16.1 MB under a memory guard. """ import os os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import random from module_law import check, section, CHECKS, vp from tame import departure, INF from weld import Units from staircase import read_deep, root_search, read_all, cyclo, \ second_closed, second_point, pmul, padd, ppow SEED = 1429 # ------------------------------------------------------------ designs def design(p, N, k, i, a): """(e, b, d) of the norm of x^k + a varpi x^i - varpi.""" q = p ** (N - 1) B = [1] + [0] * (i - 1) + [-a] A = padd(B, [0] * k + [1]) Aq, Bq = ppow(A, q), ppow(B, q) total = [0] for j in range(p): total = padd(total, pmul(ppow(Aq, j), ppow(Bq, p - 1 - j))) while total and total[-1] == 0: total.pop() e = len(total) - 1 assert e == k * (p - 1) * q and total[e] == 1 assert all(c % p == 0 for c in total[:e]) and total[0] % p ** 2 != 0 b = [0] + [total[j] // p for j in range(1, e)] return e, b, -total[0] // p # ------------------------------------------------------------ the reader def val(U, z): """v_pi(z), capped at U.L.""" best = U.L for j, c in enumerate(z): c %= U.mod if c: best = min(best, U.e * vp(c, U.p) + j) return best def cofactor_level(U, mu, c): """Level of the principal part of mu/pi^c: v(mu^(p-1) - pi^(c(p-1))) - c(p - 1).""" p = U.p w = U.pw(mu, p - 1) pc = U.loc.pi_pow(c * (p - 1), U.mod) return val(U, [(x - y) % U.mod for x, y in zip(w, pc)]) - c * (p - 1) def read_field(p, e, b, d, full=False): """N, l, and i_tau at every primitive p^N-th root.""" if full: f = read_all(p, e, b, d) rec, root, higher = f["rec"], f["root"], f["higher"] else: f, rec = None, read_deep(p, e, b, d) Lp = rec["L"] + rec["N"] * e + 1 root = root_search(p, e, b, d, rec["N"], Lp) higher = root_search(p, e, b, d, rec["N"] + 1, Lp) s, N, L = rec["s"], rec["N"], rec["L"] U = Units(p, e, b, d, L) c = s // p ** (N - 1) taus = [] if root is not None: z = [x % U.mod for x in root] for a in range(1, p ** N): if a % p: za = U.pw(z, a) taus.append(cofactor_level(U, [(za[0] - 1) % U.mod] + za[1:], c)) return dict(rec=rec, s=s, N=N, M=rec["M"], l=departure(p, e, b, d), taus=taus, root=root, higher=higher, f=f, U=U, c=c) def readout_ok(r, p): s, N = r["s"], r["N"] return (r["root"] is not None and r["higher"] is None and r["taus"] and all(min(r["l"], s) == min(p ** (N - 1) * t, s) for t in r["taus"])) def show(r, p, e, label): ts = sorted(set(r["taus"])) print(f" p={p} e={e:2d} N={r['N']} s={r['s']} M={r['M']} " f"{label:34s} l={'inf' if r['l'] >= INF else r['l']:>3} " f"i_tau {ts}") # ------------------------------------------------------------ sections def section_control(): section("C CONTROL: the level reader, and the readout at known " "fields") for name, p, e, b, d in [("x^6 + 3x^3 + 3", 3, 6, [0, 0, 0, 1, 0, 0], -1), ("Q_3(zeta_9)", 3, *cyclo(3, 2, 1, []))]: rec = read_deep(p, e, b, d) U = Units(p, e, b, d, rec["L"]) c = rec["s"] got = [] for j in range(1, 6): pc = U.loc.pi_pow(c, U.mod) pj = U.loc.pi_pow(c + j, U.mod) got.append(cofactor_level(U, [(x + y) % U.mod for x, y in zip(pc, pj)], c)) check(f"Ca {name}: the reader returns 1..5", got == [1, 2, 3, 4, 5], f"read {got}") for name, p, N, gen in [("x^6 + 3x^3 + 3", 3, 1, (6, [0, 0, 0, 1, 0, 0], -1)), ("Q_3(zeta_3)", 3, 1, cyclo(3, 1, 1, [])), ("Q_3(zeta_9)", 3, 2, cyclo(3, 2, 1, []))]: e, b, d = gen r = read_field(p, e, b, d) show(r, p, e, name) ok = r["N"] == N and readout_ok(r, p) if name.startswith("Q_"): ok = ok and min(r["l"], r["s"]) == r["s"] check(f"Cb {name}: N = {N}, the readout holds", ok, f"N {r['N']}, l {r['l']}, i_tau {sorted(set(r['taus']))}") DESIGNS = [(3, 2, 3, i, a) for i in (1, 2) for a in (1, 2)] \ + [(3, 2, 2, 1, a) for a in (1, 2)] \ + [(3, 2, 4, i, a) for i in (1, 2, 3) for a in (1, 2)] \ + [(5, 2, 2, 1, a) for a in (1, 2)] CYCLO = [(3, 2, 2), (3, 2, 3), (3, 3, 1), (5, 2, 1)] RIGID = {1: [(1, 3), (4, 2)], 2: [(1, 3), (5, 2)]} def section_designs(rng): section("R, D, K THE READOUT, THE DESIGN, THE RIGID SEAT") bad = dict(R=0, D=0, K=0) n = dict(R=0, D=0, K=0) for p, N, k, i, a in DESIGNS: e, b, d = design(p, N, k, i, a) rigid = (p, N, k) == (3, 2, 3) and i < 3 r = read_field(p, e, b, d, full=rigid) show(r, p, e, f"design k={k} i={i} a={a}") n["R"] += 1 okR = readout_ok(r, p) bad["R"] += not okR n["D"] += 1 want_l = p ** (N - 1) * i okD = (i >= p or r["N"] == N) and r["l"] == want_l bad["D"] += not okD if not (okR and okD): print(f" OFF: N {r['N']} l {r['l']} want {want_l}, " f"i_tau {sorted(set(r['taus']))}") if rigid: n["K"] += 1 f, rec = r["f"], r["rec"] M, es = rec["M"], rec["es"] vals = f["br"][M][2] want = RIGID[i] okK = (vals == {es + r["l"]} and f["st"] == want and f["J"] == want and f["fromG"] == want and second_point(f["J"]) == second_closed(p, e, r["l"])) bad["K"] += not okK print(f" seat m={M}: landings {sorted(vals)}; staircase " f"{f['st']}, Pagano {f['J']}, from G {f['fromG']}, " f"closed form {second_closed(p, e, r['l'])}") for p, N, k in CYCLO: for t in range(3): rr = [] if t == 0 else [rng.randrange(p ** 2) for _ in range(k)] e, b, d = cyclo(p, N, k, rr) r = read_field(p, e, b, d) show(r, p, e, f"Phi_{p}^{N}(1+x^{k}+p Omega) Omega={rr}") n["R"] += 1 okR = readout_ok(r, p) bad["R"] += not okR if not okR: print(f" OFF: N {r['N']} l {r['l']}, " f"i_tau {sorted(set(r['taus']))}") check("R min(l, s) = min(p^(N-1) i_tau, s) at every root", bad["R"] == 0, f"{n['R']} fields, {bad['R']} off") check("D the design: N kept below p, l = p^(N-1) i", bad["D"] == 0, f"{n['D']} designs, {bad['D']} off") check("K a rigid seat at p = 3, N = 2, its staircase as predicted", bad["K"] == 0, f"{n['K']} designs, {bad['K']} off") def main(): rng = random.Random(SEED) section_control() if not all(CHECKS): print("\ncontrol failed: nothing below is read") raise SystemExit(1) section_designs(rng) print() print(f"{sum(CHECKS)}/{len(CHECKS)} checks PASS") if not all(CHECKS): raise SystemExit(1) if __name__ == "__main__": main()