"""numquartic.py -- n_L(K) / w_L(K) at 2 over a quartic with two ramified places. QUESTION. Over every number field the unit norms N_l are generated by the unit norms of the abelian parts of K's completions at l. At a Galois field the places over l are conjugate and share one norm group, and at a cubic that is not Galois a gap needs one place. At a quartic K that is not Galois with 2 O_K = P1^2 P2^2, each completion a ramified quadratic Q_2(sqrt d_i), is v_2(n) read off the group the two places' unit norm groups GENERATE? THE ARGUMENT (written before the engine). The class table. The unit norms of Q_2(sqrt d) are U(d) = {u : (u, d)_2 = 1}, an index-2 group holding 1 + 8Z_2: {1, 5} mod 8 at d = -1, 3, {1, 3} at -2, 6, {1, 7} at 2, -6, by the Hilbert symbol (u, 2) = (-1)^((u^2 - 1)/8), (u, w) = (-1)^((u - 1)/2 (w - 1)/2) at units. GUESS. N_2 = : Z_2^x when the two groups differ, two index-2 groups of (Z/8)^x = C2 x C2 generating it; the one group when they agree. G_2 = Gal(Q(mu_(2^oo)) / K cap Q(mu_(2^oo))): Z_2^x at A4 and S4, which have no subfield but Q; at D4, K holds one quadratic k, read off the resolvent cubic R(y) = y^3 - b y^2 + (ac - 4d) y - (a^2 d - 4bd + c^2) (disc R = disc F): with r its one rational root, x1 + x2 and x1 x2 lie in K, roots of t^2 + a t + (b - r) and t^2 - r t + d, so k = Q(sqrt D), D the nonzero non-square of a^2 - 4(b - r) and r^2 - 4d. G_2 = U(k) when k is Q(i), Q(sqrt 2) or Q(sqrt -2), else Z_2^x. Exponents mod 2^k (k >= 2): Z_2^x and {1, 3}: 2, then 2^(k - 2); {1, 5}: 1 at k = 2, then 2^(k - 2); {1, 7} = +-(1 + 8Z_2): max(2, 2^(k - 3)). So at G_2 = Z_2^x the gap at 2 is 2 at odd L for {1, 5} alone, 2 at even L for {1, 7} alone, and 1 for {1, 3} and for any two different groups. DESIGN. Standard library, numwall.py, numchar.py and numcubic.py. K = Q[x]/(F), F = x^4 + a x^3 + b x^2 + c x + d with a, c, d even and b odd, so F = x^2 (x + 1)^2 mod 2, and Hensel lifts F = G1 G2 over Z_2, G1 = x^2 and G2 = (x + 1)^2 mod 2, bit by bit to 2^40 (one of four corrections fits at each bit, asserted). K (x) Q_2 = Q_2[x]/(G1) x Q_2[x]/(G2) at any order, so the local data need no maximal order: each G_i is split, unramified or ramified as the class of disc(G_i) in Q_2^x / squares reads (x^2 + 2x + 4 = x^2 mod 2 is unramified, disc -12), and only both ramified are kept. A plain unit y of an order (N(y) odd) is a unit of O_K (x) Z_2, so the group B the box's norms make lies in N_2: n | n_box at 2, and with N_2 = N_guess agreement CERTIFIES v_2(n). The box runs over a 2-maximal order: from Z[x]/(F), adjoin every y / 2 in O_K, y in the order mod 2 (y / 2 integral when the characteristic polynomial of y is divisible by 2^k in degree k), until none is new; a box over a smaller order reads only that order's units, whose norms can fill a proper subgroup of N_2 at every size (the first full run, over Z[x]/(F), printed T1 off at 3240 (field, L), at 98 of the 274 polynomials failing Dedekind's criterion at 2 and none of the 516 passing it; a single step to 1/4 left 60 off at 2 polynomials). Exponents mod 2^k by numchar's exps, v_2 at L by its vl_at; boxes of half-width 3 and 5 in the four coordinates, stopped once B is Z_2^x. v_2(w) by the Chebotarev form: the least v_2(p^L - 1) over the degree-one places off 2, p <= 2000 not dividing disc F, stopped at v_2(W(L)) (w >= W at 2 always). The Galois group off R: irreducible, A4 or S4 by disc a square; one root, C4 when both quadratics above split over Q(sqrt disc) (Kappe and Warren), else D4; three, V4. Kept: D4, A4, S4, F irreducible over Q. Fields: |a| <= 2, |b|, |c|, |d| <= 11 under the parities, d != 0, both G_i ramified, one per disc F; two F can define one field, so the counts are of polynomials. Every L <= 60. C CONTROLS, read first: C0 the class table: the odd x^2 - d y^2 mod 8 over |x|, |y| <= 8 equal U(d) at d = -1, 3, 2, -2, 6, -6. C1 POSITIVE CONTROL, an answer known: the etale algebra Q(sqrt d1) x Q(sqrt d2), F = ((x - s1)^2 - d1)((x - s2)^2 - d2), the shifts putting the factors at x^2 and (x + 1)^2 mod 2, over the 36 pairs of the six classes: its unit norms are the products of the two quadratic rings', so N_2 = by construction. The recipe and the box equal it at every L <= 60; hand values at L = 1, 2: d1 = -1, d2 = 2: v_2(n) = 1, 3; d1 = -1, d2 = 3: 2, 3. C2 v_2 of the Chebotarev w equals the guess's at every (field, L). C3 the two boxes agree; at D4, the two square roots naming k agree where both are irrational; numcubic.py's root count, written for cubics, agrees with trial at the first 20 fields, odd p < 200. C4 the box's order is 2-maximal: v_2(disc F) - 2 v_2(its index over Z[x]/(F)) equals the two ramified quadratics' v_2(disc), 2 at a unit class and 3 at an even one (it caught the step to 1/4 at 6 polynomials). PREDICTIONS AND KILLS, frozen before the engine. T1 v_2(n_box) = v_2(n_guess) at every (field, L). A KILL is one printed (field, L) where they differ, the two boxes agreeing there. The bar sits on the arm where "generated by" acts: at least 10 fields with two different unit groups, each of the three pairs at least once, or the run is void, not a pass. OBSERVED: polynomials by Galois group and arm, the gaps at 2 by arm, the D4 ones whose k is Q(i), Q(sqrt 2) or Q(sqrt -2). FINDINGS (from the printed run, 7/7 checks PASS). C C0 the table, box and recipe alike. C1 at 2160 (algebra, L), 0 off, the hand values (1, 3) and (2, 3). C2 at 47400 (field, L), 0 off. C3 the boxes agree everywhere, k's roots agree, the root count agrees with trial. C4 at every field, 274 of them enlarged past Z[x]/(F). T1 held at 47400 (field, L) over 790 quartic polynomials, one per disc F, of fields not Galois with 2 = P1^2 P2^2, 0 off, so v_2(n) is CERTIFIED there. The bar met: 444 with two different unit groups, ({1,3}, {1,5}) at 168, ({1,3}, {1,7}) at 112, ({1,5}, {1,7}) at 164, and none has a gap at 2 at any L: two places close the gap that the pair's {1,5} or {1,7} group alone would open. O By group and arm, the gap at 2 at odd L, even L or none: A4, one {1,5}: odd at 2. D4: different groups, none at 36; one {1,3}, none at 23; one {1,5}, none at 18 and odd at 30; one {1,7}, none at 18 and even at 14. S4: different groups, none at 408; one {1,3}, none at 39; one {1,5}, odd at 167; one {1,7}, even at 35. 43 D4 polynomials have k = Q(i), Q(sqrt 2) or Q(sqrt -2), both places' unit norms U(k) at all 43, as N_2 <= G_2 forces. RUN RECORD. About 53 s, peak about 17.6 MB (rehearsal at |b|, |c|, |d| <= 3: 18 polynomials, 2.5 s). """ import os import sys import time from itertools import product from math import isqrt sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import numwall as nw # noqa: E402 import numchar as nc # noqa: E402 import numcubic as nq # noqa: E402 CHECKS = [] LS = list(range(1, 61)) BOXES = (3, 5) PREC = 40 FULL = nc.exps([1, 3, 5, 7, 9], 2) def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) # ------------------------------------------------------------ 2-adic data def rem_monic(F, G, m): """F mod G mod m, G monic, low to high.""" r = [x % m for x in F] n = len(G) - 1 for i in range(len(r) - 1, n - 1, -1): c = r[i] if c: for j in range(n + 1): r[i - n + j] = (r[i - n + j] - c * G[j]) % m return r[:n] def hensel(F, start): """The monic quadratic factor of F over Z_2 that is `start` mod 2.""" q, p = start for j in range(1, PREC): fits = [(q + e0 * 2 ** j, p + e1 * 2 ** j) for e0 in (0, 1) for e1 in (0, 1) if not any(rem_monic(F, [q + e0 * 2 ** j, p + e1 * 2 ** j, 1], 2 ** (j + 1)))] assert len(fits) == 1, (F, j, fits) q, p = fits[0] return q, p def klass(D): """D in Q_2^x / squares, D read mod 2^PREC: (v mod 2, unit mod 8).""" D %= 2 ** PREC assert D, D v = nw.vp(D, 2) assert v < PREC - 3, D return v % 2, (D >> v) % 8 def kind(c): v, u = c return "split" if (v, u) == (0, 1) else \ "unramified" if (v, u) == (0, 5) else "ramified" def hilbert(u, c): v, w = c s = (u * u - 1) // 8 * v + (u - 1) // 2 * ((w - 1) // 2) return 1 - 2 * (s % 2) def U(c): return frozenset(u for u in (1, 3, 5, 7) if hilbert(u, c) == 1) def local(F): """The two places' classes at 2.""" out = [] for start in ((0, 0), (1, 0)): q, p = hensel(F, start) out.append(klass(p * p - 4 * q)) return out # ------------------------------------------------------------ the field def evalp(F, x): return sum(a * x ** i for i, a in enumerate(F)) def divisors(n): n = abs(n) return [k for k in range(1, n + 1) if n % k == 0] def int_roots(P): """The distinct integer roots of a monic integer polynomial.""" P, out = P[:], set() while P[0] == 0 and len(P) > 1: out.add(0) P = P[1:] for r in divisors(P[0]): for s in (r, -r): if evalp(P, s) == 0: out.add(s) return sorted(out) def irreducible4(F): d, c, b, a = F[0], F[1], F[2], F[3] if int_roots(F): return False for q in divisors(d): for q_ in (q, -q): s = d // q_ t = a * a - 4 * (b - q_ - s) if t < 0 or isqrt(t) ** 2 != t: continue for p in ((a + isqrt(t)) // 2, (a - isqrt(t)) // 2): if (a + isqrt(t)) % 2 == 0 and p * s + q_ * (a - p) == c: return False return True def resolvent(F): d, c, b, a = F[0], F[1], F[2], F[3] return [-(a * a * d - 4 * b * d + c * c), a * c - 4 * d, -b, 1] def sqfree(D): s = -1 if D < 0 else 1 D = abs(D) for p in nw.PR: if p * p > D: break while D % (p * p) == 0: D //= p * p return s * D def galois(F): """(group, k's squarefree D or None, the two roots agreeing).""" d, c, b, a = F[0], F[1], F[2], F[3] R = resolvent(F) disc = nq.disc3(R) rs = int_roots(R) if not rs: return ("A4" if nq.is_square(disc) else "S4"), None, True if len(rs) == 3: return "V4", None, True r = rs[0] Ds = [a * a - 4 * (b - r), r * r - 4 * d] def splits(D): return D == 0 or nq.is_square(D) or nq.is_square(D * disc) if all(splits(D) for D in Ds): return "C4", None, True irr = [sqfree(D) for D in Ds if D and not nq.is_square(D)] return "D4", irr[0], len(set(irr)) == 1 class Quartic: def __init__(self, name, F, group=None, kD=None, agree=True): self.name, self.F, self.n = name, F, 4 self.D = nq.disc3(resolvent(F)) self.cls = local(F) self.group, self.kD, self.agree = group, kD, agree self.max2 = nq.dedekind_ok(F, 2) self.basis, self.ind2 = order2(self) # ------------------------------------------------------------- the guess def k_class(kD): return {-1: (0, 7), 2: (1, 1), -2: (1, 7)}.get(kD) def n2_guess(K): return nc.exps(sorted(U(K.cls[0]) | U(K.cls[1])) + [9], 2) def w2_guess(K): c = k_class(K.kD) return FULL if c is None else nc.exps(sorted(U(c)) + [9], 2) # ------------------------------------------------------------- the box def mult_matrix(z, F): rows, v = [], z[:] for _ in range(4): rows.append(v) v = nw.pmul(v, [0, 1, 0, 0], F) return rows def minors_sum(M, k): from itertools import combinations return sum(nw.det([[M[i][j] for j in S] for i in S]) for S in combinations(range(4), k)) def integral_over(z, F, m): """z / m in O_K, z in Z[theta]: its characteristic polynomial integral.""" M = mult_matrix(list(z), F) return all(minors_sum(M, k) % m ** k == 0 for k in range(1, 5)) def hnf(rows): """A Z-basis of the lattice the integer rows span, triangular.""" rows = [r[:] for r in rows] out = [] for col in range(4): live = [r for r in rows if r[col]] rows = [r for r in rows if not r[col]] while len(live) > 1: live.sort(key=lambda r: abs(r[col])) piv = live[0] nxt = [piv] for r in live[1:]: q = r[col] // piv[col] r = [a - q * b for a, b in zip(r, piv)] (nxt if r[col] else rows).append(r) live = nxt out.append(live[0]) return out def order2(K): """A 2-maximal order: from Z[theta], adjoin the y / 2 in O_K, y in the order mod 2, until none is new. Its basis as 2^e times vectors over Z[theta], and v_2 of its index over Z[theta].""" basis, e = [[int(i == j) for j in range(4)] for i in range(4)], 0 while True: new = [] for r in product(range(2), repeat=4): z = [sum(c * b[j] for c, b in zip(r, basis)) for j in range(4)] if any(r) and integral_over(z, K.F, 2 ** (e + 1)): new.append(z) if not new: break basis = hnf([[2 * x for x in b] for b in basis] + new) e += 1 det = 1 for i, r in enumerate(basis): det *= r[i] return (basis, e), nw.vp(2 ** (4 * e) // abs(det), 2) def box2(K, B): """Exponents mod 2^k of the group the box's plain unit norms make, the box over order2's order.""" K_ = nc.kmax(2) mod = 2 ** K_ cur, gens = [1] * (K_ + 1), set() basis, e = K.basis for t in product(range(-B, B + 1), repeat=4): z = [sum(c * b[j] for c, b in zip(t, basis)) for j in range(4)] N4 = nw.norm(z, K.F) assert N4 % 2 ** (4 * e) == 0, (K.name, z) N = N4 >> (4 * e) if N % 2 == 0: continue u = N % mod if u in gens: continue gens.add(u) for k in range(1, K_ + 1): cur[k] = nw.lcm(cur[k], nc.order_lk(u, 2, k)) if cur == FULL: break return cur def disc2_local(K): """v_2(disc O_K) off the two ramified quadratics: 2 at a unit class, 3 at an even one.""" return sum(2 if v == 0 else 3 for v, u in K.cls) # ------------------------------------------------------------------- w def has_root(F, p): return nq.nroots(F, p) > 0 def w2_cheb(K, L, primes): floor, m = nw.vp(nq.W(L), 2), None for p in primes: v = nw.vp(pow(p, L, 2 ** 40) - 1, 2) m = v if m is None else min(m, v) if m == floor: break return m def deg1_primes(K, bound=2000): return [p for p in nw.PR[1:] if p <= bound and K.D % p and has_root(K.F, p)] # --------------------------------------------------------------- fields def searched(lim=11): out, seen = [], set() for a in (-2, 0, 2): for b in range(-lim, lim + 1): if b % 2 == 0: continue for c in range(-lim, lim + 1, 1): if c % 2: continue for d in range(-lim, lim + 1): if d % 2 or d == 0: continue F = [d, c, b, a, 1] if not irreducible4(F): continue D = nq.disc3(resolvent(F)) if D in seen: continue cls = local(F) if any(kind(x) != "ramified" for x in cls): continue g, kD, agree = galois(F) if g in ("C4", "V4"): continue seen.add(D) out.append(Quartic(f"x^4{a:+d}x^3{b:+d}x^2{c:+d}x{d:+d}", F, g, kD, agree)) return out def shifted(d, s): """(x - s)^2 - d, low to high.""" return [s * s - d, -2 * s, 1] def algebra(d1, d2): A = shifted(d1, d1 % 2) B = shifted(d2, 1 - d2 % 2) F = [0] * 5 for i, x in enumerate(A): for j, y in enumerate(B): F[i + j] += x * y return Quartic(f"Q(sqrt{d1}) x Q(sqrt{d2})", F) # ------------------------------------------------------------- sections CLASSES = (-1, 3, 2, -2, 6, -6) TABLE = {-1: {1, 5}, 3: {1, 5}, 2: {1, 7}, -6: {1, 7}, -2: {1, 3}, 6: {1, 3}} def section_control(): print("C CONTROLS") got = {d: {(x * x - d * y * y) % 8 for x in range(-8, 9) for y in range(-8, 9) if (x * x - d * y * y) % 2} for d in CLASSES} rec = {d: set(U(klass(d))) for d in CLASSES} check("C0 the class table", got == TABLE == rec, f"box {got}, recipe {rec}") off, hand, rows = [], {}, 0 for d1 in CLASSES: for d2 in CLASSES: K = algebra(d1, d2) known = nc.exps(sorted(TABLE[d1] | TABLE[d2]) + [9], 2) if K.cls != [klass(d1), klass(d2)]: off.append((K.name, "classes", K.cls)) ex = box2(K, BOXES[1]) g = n2_guess(K) for L in LS: rows += 1 a, b, c = (nc.vl_at(x, L) for x in (known, g, ex)) if not a == b == c: off.append((K.name, L, a, b, c)) hand[(d1, d2)] = tuple(nc.vl_at(ex, L) for L in (1, 2)) check("C1 the recipe and the box equal the etale algebra's N_2", not off and rows, f"{rows} (algebra, L), {len(off)} off {off[:4]}") check("C1 hand values at L = 1, 2", hand[(-1, 2)] == (1, 3) and hand[(-1, 3)] == (2, 3), f"(-1, 2): {hand[(-1, 2)]}, (-1, 3): {hand[(-1, 3)]}") def pair(K): a, b = sorted(tuple(sorted(U(c))) for c in K.cls) return (a,) if a == b else (a, b) def section_census(Ks): print("T THE CENSUS") R, c2, boxoff, kill = {}, [], [], [] for K in Ks: e1, e2 = box2(K, BOXES[0]), box2(K, BOXES[1]) g, wg = n2_guess(K), w2_guess(K) pr = deg1_primes(K) for L in LS: n1, n2, ng = (nc.vl_at(x, L) for x in (e1, e2, g)) w, wgL = w2_cheb(K, L, pr), nc.vl_at(wg, L) if w != wgL: c2.append((K.name, L, w, wgL)) if n1 != n2: boxoff.append((K.name, L, n1, n2)) elif n2 != ng: kill.append((K.name, L, n2, ng)) R[(K.name, L)] = (w, ng, n2) check("C2 v_2 of the Chebotarev w equals the guess's", not c2, f"{len(R)} (field, L), {len(c2)} off {c2[:3]}") bad = [K.name for K in Ks if not K.agree] roots = [(K.name, p) for K in Ks[:20] for p in nw.PR[1:46] if has_root(K.F, p) != any(evalp(K.F, r) % p == 0 for r in range(p))] check("C3 the two boxes agree; k's two roots agree; the root test " "by trial", not boxoff and not bad and not roots, f"{len(boxoff)} off {boxoff[:4]}; k {bad[:4]}; roots {roots[:4]}") mx = [K.name for K in Ks if nw.vp(K.D, 2) - 2 * K.ind2 != disc2_local(K)] check("C4 the box's order is 2-maximal: v_2(disc F) - 2 v_2(index) " "equals the two places' v_2(disc)", not mx, f"{sum(K.ind2 > 0 for K in Ks)} polynomials enlarged past Z[x]/(F), " f"{len(mx)} off {mx[:4]}") offK = {nm for nm, _, _, _ in kill} m2 = {K.name: K.max2 for K in Ks} print(f" the off polynomials: {len(offK)}, of them 2-maximal (Dedekind): " f"{sum(m2[nm] for nm in offK)}; not 2-maximal: " f"{sum(not v for v in m2.values())}, of them off: " f"{sum(not m2[nm] for nm in offK)}") diff = [K for K in Ks if len(pair(K)) == 2] pairs = {} for K in diff: pairs[pair(K)] = pairs.get(pair(K), 0) + 1 print(f" different groups: {len(diff)} polynomials, {sorted(pairs.items())}") void = len(diff) < 10 or len(pairs) < 3 check("T1 v_2(n_box) = v_2(n_guess) at every (field, L)", not kill and not void, f"{len(R)} (field, L) over {len(Ks)} polynomials, {len(kill)} off " f"{kill[:4]}{'; VOID, the bar unmet' if void else ''}") return R def section_observed(Ks, R): print("O OBSERVED") tab = {} for K in Ks: arm = "different" if len(pair(K)) == 2 else f"one {pair(K)[0]}" gaps = tuple(sorted({L % 2 for L in LS if R[(K.name, L)][2] > R[(K.name, L)][0]})) key = (K.group, arm, gaps) tab[key] = tab.get(key, 0) + 1 for key in sorted(tab): g, arm, gaps = key print(f" {g} {arm:18s} gap at 2 at L mod 2 in {list(gaps)}: " f"{tab[key]}") cyc = [(K.name, K.kD, pair(K)) for K in Ks if k_class(K.kD)] same = sum(p_ == (tuple(sorted(U(k_class(kD)))),) for _, kD, p_ in cyc) print(f" D4 with k = Q(i), Q(sqrt 2), Q(sqrt -2): {len(cyc)}, both " f"places' unit norms U(k) at {same}; {cyc[:6]}") def main(): t0 = time.time() section_control() Ks = searched(int(sys.argv[1]) if len(sys.argv) > 1 else 11) print(f"numquartic.py: {len(Ks)} quartic polynomials (one per disc F), " f"fields not Galois, 2 = P1^2 P2^2, every L <= 60 " f"({time.time() - t0:.1f} s)") R = section_census(Ks) section_observed(Ks, R) 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())