numgap.py

"""numgap.py -- the gap n_L(K) / w_L(K) at a quadratic field, whole.

QUESTION. numwall.py finds n != w only at quadratic fields of composite
discriminant and proves its odd primes (l^(1 + v_l(L)) where
(l - 1)/2 | L and l - 1 does not). What is n / w exactly, at every L?

THE ARGUMENT (written before the engine). D = prod D_l, the prime
discriminants -4, 8, -8 and l* = (-1)^((l - 1)/2) l. v_l(n) is the
largest k with N_l of exponent dividing L mod l^k, N_l the norms of the
local units of O_K (x) Z_l in Z_l^x; v_l(w) is read the same way off
G_l = Gal(K(mu_(l^oo))/K) in Z_l^x; G_l = Z_l^x unless D = D_l, where
G_l is the kernel of chi_D.
  l not | D: N_l = Z_l^x, no gap.
  l odd, l | D: a^2 - d b^2 = a^2 mod l, so N_l is the squares; at
    D = l* G_l is too. Else the gap l^(1 + v_l(L)) when (l - 1)/2 | L
    and l - 1 does not.
  l = 2, 2 | D: N_2 holds the squares 1 + 8Z_2, and its residues mod 8
    are {1, 5} at D_2 = -4, {1, 3} at -8, {1, 7} at 8 (a^2 - d b^2
    over the units: a + b odd at -4, a odd at +-8). So N_2 is 1 + 4Z_2
    at -4 and +-(1 + 8Z_2) at 8. Mod 2^k, k >= 2, its exponent is the
    full group's, max(2, 2^(k - 2)), at -8; at -4 it is 1 at k = 2 and
    2^(k - 2) from k = 3; at 8 it is max(2, 2^(k - 3)). At even L that
    makes v_2(n) = v_2(L) + 3 at D_2 = 8, one past W(L), and
    v_2(W(L)) otherwise. At odd L only k <= 2 can enter
    (a 2-group of exponent dividing L is trivial): N_2 is trivial mod
    4 exactly at D_2 = -4, so v_2(n) = 2 there and 1 elsewhere. G_2 is
    N_2 at D = -4, 8, -8 and Z_2^x otherwise.
  THE LAW: n / w = prod over l | D, D_l != D, gamma_l(L), with
  gamma_l = l^(1 + v_l(L)) at odd l with (l - 1)/2 | L, l - 1 not | L;
  gamma_2 = 2 at D_2 = 8 and L even, and at D_2 = -4 and L odd; 1
  otherwise.

DESIGN. Imports numwall.py's fields, w by definition and n by the norm
Adams gcd at its larger box. Every quadratic field of numwall.py (d
squarefree, 2 <= |d| <= 50, and d = -1), every L <= 60.
  C  CONTROLS, read first: Q(sqrt -15), L = 2: n / w = 5 (numwall.py's
     hand values 120 / 24); Q(sqrt -6), L = 2 by hand: norms of units
     mod 16 are {1, 7, 9, 15}, exponent 2, and 7^2 = 17 mod 32, so
     v_2(n) = 4; squares mod 9 have order 3, so v_3(n) = 1: n = 48,
     w = 24. Q(i), L = 1: unit norms are 1 mod 4 and 5 appears mod 8,
     G_2 = 1 + 4Z_2: n = w = 4. Q(sqrt 3), L = 1: gamma_3 = 3,
     gamma_2 = 2, n / w = 6.

PREDICTIONS AND KILLS, frozen before the engine.
  T7 n / w is the law's product at every quadratic (field, L).
  So 2 || n / w at every even L exactly at d = 2 mod 8, d != 2, and at
  every odd L exactly at d = 3 mod 4, d != -1.
  A KILL is any printed T7 miss; a control miss fails the instrument.

FINDINGS (from the printed run, 5/5 checks PASS).
  C  every control held: Q(sqrt -15) n 120, w 24; Q(sqrt -6) n 48,
     w 24; Q(i) at L = 1 n = w = 4; Q(sqrt 3) at L = 1 n 12, w 2.
  T7 held at 3660 (field, L), 0 off: 61 fields x 60 L. 2 || n / w at
     every even L over d = -46, -38, -30, -22, -14, -6, 10, 26, 34, 42,
     the d = 2 mod 8 other than 2, and at every odd L over the 19 d =
     3 mod 4, d != -1, from -41 to 47; 2 divides n / w at 870
     (field, L) of the 1363 with n != w. The same law with the even-L
     2-factor at every L, in a scratch copy, misses 870.
  Since w is computed by its definition and the law derives the true
  n, the box gcd n is the true n at every quadratic (field, L) run.

RUN RECORD. 3.8 s, peak commit 13.2 MB.
"""

import os
import sys
import time

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))

import numwall as nw  # noqa: E402

CHECKS = []
LS = list(range(1, 61))


def check(name, ok, detail=""):
    CHECKS.append(bool(ok))
    print(f"  [{'PASS' if ok else 'FAIL'}] {name}"
          + (f" -- {detail}" if detail else ""))


def prime_discs(D):
    """{l: D_l}, D the product of the D_l."""
    out, rest = {}, D
    for l in nw.factor(abs(D)):
        if l > 2:
            out[l] = l if l % 4 == 1 else -l
            rest //= out[l]
    if D % 2 == 0:
        out[2] = rest
    return out


def gap_law(D, L):
    g = 1
    for l, Dl in prime_discs(D).items():
        if Dl == D:
            continue
        if l == 2:
            g *= 2 if Dl == (8 if L % 2 == 0 else -4) else 1
        elif L % ((l - 1) // 2) == 0 and L % (l - 1):
            g *= l ** (1 + nw.vp(L, l))
    return g


def run(Ks):
    return {(K.name, L): (nw.w_def(K, L), nw.norm_wall(K, L, nw.BOXES[2][1]))
            for K in Ks for L in LS}


def section_controls(R):
    print("C  CONTROLS")
    w, n = R[("Q(sqrt-15)", 2)]
    check("C Q(sqrt -15), L = 2: n / w = 5", n == 5 * w, f"n {n}, w {w}")
    w, n = R[("Q(sqrt-6)", 2)]
    check("C Q(sqrt -6), L = 2: n = 48, w = 24", (n, w) == (48, 24),
          f"n {n}, w {w}")
    w, n = R[("Q(i)", 1)]
    check("C Q(i), L = 1: n = w = 4", (n, w) == (4, 4), f"n {n}, w {w}")
    w, n = R[("Q(sqrt3)", 1)]
    check("C Q(sqrt 3), L = 1: n / w = 6", n == 6 * w, f"n {n}, w {w}")
    for D in (-15, -24, 40, 8, -4):
        print(f"    D = {D}: prime discriminants {prime_discs(D)}")


def section_law(Ks, R):
    print("T  THE LAW")
    miss = []
    for K in Ks:
        for L in LS:
            w, n = R[(K.name, L)]
            if n % w or n // w != gap_law(K.D, L):
                miss.append((K.name, L, n // w, gap_law(K.D, L)))
    check("T7 n / w = the law's product at every quadratic (field, L)",
          not miss, f"{len(Ks) * len(LS)} (field, L), {len(miss)} off "
          f"{miss[:5]}")

    def d(K):
        return K.D // (4 if K.D % 4 == 0 else 1)

    def two_at_every(K, parity):
        return all(nw.vp(R[(K.name, L)][1] // R[(K.name, L)][0], 2) == 1
                   for L in LS if L % 2 == parity)
    print(f"  2 || n / w at every even L: d = "
          f"{sorted(d(K) for K in Ks if two_at_every(K, 0))}")
    print(f"  d = 2 mod 8, d != 2:        d = "
          f"{sorted(d(K) for K in Ks if K.D % 32 == 8 and K.D != 8)}")
    print(f"  2 || n / w at every odd L:  d = "
          f"{sorted(d(K) for K in Ks if two_at_every(K, 1))}")
    print(f"  d = 3 mod 4, d != -1:       d = "
          f"{sorted(d(K) for K in Ks if K.D % 16 == 12 and K.D != -4)}")
    some2 = sum(1 for (w, n) in R.values() if nw.vp(n // w, 2))
    print(f"  (field, L) with 2 | n / w: {some2}; with n != w: "
          f"{sum(1 for w, n in R.values() if n != w)}")


def main():
    t0 = time.time()
    Ks = [K for K in nw.fields() if not K.cyc]
    print(f"numgap.py: {len(Ks)} quadratic fields, every L <= 60")
    R = run(Ks)
    section_controls(R)
    section_law(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())