numquartic.py
Checks: GROWTH: The gap read off the completions theorem; rule.
Cited on: GROWTH.
To run it: save numquartic.py, with numchar.py, numcubic.py, numgap.py, numwall.py beside it; standard library only.
"""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 = <U(d1), U(d2)>: 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 = <U(d1), U(d2)> 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())