dualn.py
Checks: DUAL: The chain law theorem.
Cited on: DUAL.
To run it: save dualn.py, with dualdeg.py beside it; standard library only.
"""dualn.py -- the two ends of a base of degree n: which ideals does span
j hide?
QUESTION. dualdeg.py's setting: f monic of degree n, q = |a_0| >= 2,
O = Z[x]/(f), digits 0, ..., q - 1, T_j = {sum_(k<j) d_k beta^k}. Span
j hides I iff every nonzero character chi of O/I has some k < j with
beta^k chi dead (chi(beta^k) != 0, q chi(beta^k) = 0). The colon law is
a degree-2 law, and H1 (for some k <= j, q beta^(j-k) in I and 1, ...,
beta^(k-1) span O/(I : beta^(j-k))) misses 84 cubic pairs, every one
hidden. Which law in ideal terms holds at every degree?
SECTION M (a read, no prediction). Every H1 miss printed whole: the
base, the ideal's row HNF and index, for each k <= j the two halves of
H1 (q beta^(j-k) in I; 1, ..., beta^(k-1) span O/(I : beta^(j-k))) and
the colon's index, and the l-primary parts I_l (the ideal over I of
index the l-part of [O : I]) with span j's count and H1 at each
(run with --misses). It read: at q = 6 all 40 at index 36 = 6^2, j =
2, each l-part meeting H1 at its own k; at q = 4 and 2 one prime, a k
with q beta^(j-k) in I never also spanning; 24 of the q = 4 ones at
N = q^j.
THE CHAIN LAW C (frozen before its code). G = O/I, g_k = beta^k mod
I. S grows from the empty set by any k < j with q g_k in G_S, the
subgroup the g_s, s in S, generate; C holds iff G_S reaches G.
(i) Greedy is the whole search: q g_k in G_S survives S growing.
(ii) IF. chi != 0; at the first step whose G_S chi is not zero on,
chi(g) != 0 for the g added, and q g lies in the earlier G_S,
so q chi(g) = 0: beta^k chi is dead, span j hides I.
(iii) ONLY IF at N = q^j. The sum of the D g_k is then a direct
factorization of G by the cyclic sets {0, g, ..., (q - 1) g},
so one D g_k is a subgroup (Hajos, Math. Z. 47 (1942) 427-467,
for cyclic sets of any length; Corradi and Szabo, Comment. Math.
Univ. Carolin. 51 (2010), Theorem 1): q g_k = 0, and G/<g_k> is
factored directly by the other images; induction.
(iv) C contains H1: with H1's k, beta^(j-k), ..., beta^(j-1) enter
first and generate (beta^(j-k) O + I)/I; on the quotient O/(I +
beta^(j-k) O) the chain of O/beta^(j-k) O, where T_(j-k) is
complete, by (iii), maps on. With the quadratic only if (hidden
implies the colon law, H1 at k = 1), C is exact at degree 2.
(v) N < q^j, a multiple factorization: C may fail. At q = 2 with
O/I = (Z/4)^2 and I + 2O the F_4 prime, beta is a unit mod I + 2O, no
g_k lies in 2G, and C fails at its first step.
PREDICTIONS (frozen). C0 the 100 quadratic bases of dualdeg.py's
sweep: C = hidden, 0 off. P1 C true and unhidden: 0 at every cubic
base. P2 C = hidden at every pair with N = q^j. P3 H1 true and C false:
0. P4 the misses (hidden, C false) only at N < q^j, H1's 12 at q = 2
among them, H1's other 72 repaired. PLANT: the step test 2q g_k in G_S
must break P1. KILL: P1, P2 or P3 off kills the run; C as the law at
degree n dies at one P4 miss, expected at the 12.
FINDINGS (entered after the run, from its printed output).
C0 38960 pairs, 17144 live, 9085 hidden: C off 0.
P1 0 over the 24966 pairs; the plant 3346. P2 0 off over the 4428 complete pairs of the
12626 live. P3 0.
P4 12 misses, none at N = q^j, exactly H1's 12 at q = 2; the other
72 of H1's 84 repaired. The 12 are Q^2 (j = 6 and 7) and 2Q (j =
7), Q = (2, beta^2 + beta + 1), at x^3 + x^2 + x +/- 2 and
x^3 - x^2 + x +/- 2: multiple factorizations of O/I by the sets
{0, beta^k}, k < j, with no chain.
K C dies as the law at degree n, at the 12 predicted; it is a
theorem as a sufficient condition at every degree and as a
criterion at N = q^j, and, by the quadratic only if, exact at every
quadratic pair. At all 12 every g_k, k < j, has order 4 and the
chain stops at its first step, |G_S| = 1. Toy scale: q^J <= 128
cubic, 10^4 quadratic.
RUN RECORD. 61.8 s, 44.2 MB under a memory guard. With the findings
as checks (the orders and |G_S| at the 12 added): 6/6, 63.9 s, 45.3 MB.
"""
import sys
import time
from dualdeg import powers, ideals, tiles, hidden_by_count, mul, fmt
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" {'PASS' if ok else 'FAIL'} {name}" +
(f" ({detail})" if detail else ""))
def primes_of(m):
out, p = [], 2
while m > 1:
if m % p == 0:
out.append(p)
while m % p == 0:
m //= p
p += 1
return out
class Base:
def __init__(self, a, points=128):
self.a, self.n, self.q = a, len(a), abs(a[0])
J = 0
while self.q ** (J + 1) <= points:
J += 1
self.J = J
self.pw = powers(a, J + 1)
self.Is = ideals(a, self.q ** J)
self.T = tiles(a, self.q, J, self.pw)
self.cq = tuple(self.q * x for x in self.pw[0])
def colon(self, L, i):
ks = [K for K in self.Is if all(mul(self.pw[i], r, self.a) in L
for r in K.rows())]
return min(ks, key=lambda K: K.N)
def spans(self, K, k):
n = self.n
gens = [K.key(self.pw[i]) for i in range(k)]
seen = {tuple([0] * n)}
frontier = list(seen)
while frontier:
nxt = []
for v in frontier:
for g in gens:
w = K.key(tuple(x + y for x, y in zip(v, g)))
if w not in seen:
seen.add(w)
nxt.append(w)
frontier = nxt
return len(seen) == K.N
def split(self, L, j):
"""For k = 1..j: (q beta^(j-k) in L, span, index of the colon)."""
out = []
for k in range(1, j + 1):
i = j - k
K = self.colon(L, i)
out.append((mul(self.pw[i], self.cq, self.a) in L,
self.spans(K, k), K.N))
return out
def h1(self, L, j):
return any(a_ and b_ for a_, b_, _ in self.split(L, j))
def part(self, L, l):
e = 1
while L.N % (l ** e) == 0:
e += 1
le = l ** (e - 1)
ps = [K for K in self.Is if K.N == le
and all(r in K for r in L.rows())]
assert len(ps) == 1
return ps[0]
def cubic_bases():
for q in range(2, 7):
for c in (q, -q):
for a2 in range(-2, 3):
for a1 in range(-2, 3):
yield (c, a1, a2)
def section_misses():
print("M every H1 miss, printed whole")
total = 0
for a in cubic_bases():
B = Base(a)
for L in B.Is:
for j in range(1, B.J + 1):
if (B.q ** j) % L.N:
continue
hid = hidden_by_count(L, B.T[j])
if hid == B.h1(L, j):
continue
total += 1
sp = B.split(L, j)
ks = " ".join(f"k{k + 1}:{'q' if x else '-'}"
f"{'s' if y else '-'}{N}"
for k, (x, y, N) in enumerate(sp))
parts = []
for l in primes_of(L.N):
P = B.part(L, l)
parts.append(f"{l}:{P.N} hid "
f"{int(hidden_by_count(P, B.T[j]))} h1 "
f"{int(B.h1(P, j))}")
print(f" {fmt(a):22s} q {B.q} j {j} N {L.N:3d} "
f"d {L.d} H {[r[1:] for r in L.H[:-1]]} "
f"hid {int(hid)} | {ks} | {'; '.join(parts)}")
print(f" {total} misses")
def addv(u, v):
return tuple(x + y for x, y in zip(u, v))
def chain(B, L, mult=1):
"""C at j = 1..J: the greedy closure of S, adding k < j while
mult q g_k lies in G_S; returns [|G_S| at j] for j = 0..J, C at j
being |G_S| = N."""
zero = L.key(tuple([0] * B.n))
H = {zero}
used = set()
out = [1]
for j in range(1, B.J + 1):
grew = True
while grew:
grew = False
for k in range(j):
if k in used:
continue
qg = L.key(tuple(mult * B.q * x for x in B.pw[k]))
if qg in H:
used.add(k)
g = L.key(B.pw[k])
if g not in H:
new, x = set(H), g
while x not in H:
new |= {L.key(addv(h, x)) for h in H}
x = L.key(addv(x, g))
H = new
grew = True
out.append(len(H))
return out
def order(L, v):
zero = L.key(tuple(0 for _ in v))
m, x = 1, L.key(v)
while x != zero:
m += 1
x = L.key(tuple(m * y for y in v))
return m
def sweep(bases, points, h1=False):
"""Per pair (L, j), j >= 1: hidden, C, the plant, live, H1."""
rows = []
for a in bases:
B = Base(a, points)
for L in B.Is:
c = chain(B, L)
cp = chain(B, L, 2)
for j in range(1, B.J + 1):
hid = hidden_by_count(L, B.T[j])
live = (B.q ** j) % L.N == 0
rows.append(dict(a=a, q=B.q, N=L.N, j=j, hid=hid,
c=c[j] == L.N, cp=cp[j] == L.N,
reach=c[j], live=live, full=L.N == B.q ** j,
h1=B.h1(L, j) if h1 and live else None,
L=L))
return rows
def quad_bases():
out = [(q, p) for q in range(2, 13) for p in range(-1, q + 1)]
return out + [(17, 8)]
def section_chain():
print()
print("C0 the positive control: the 100 quadratic bases, q^J <= 10^4")
rows = sweep(quad_bases(), 10 ** 4)
live = [r for r in rows if r["live"]]
off = sum(r["c"] != r["hid"] for r in rows)
print(f" pairs {len(rows)}, live {len(live)}, hidden "
f"{sum(r['hid'] for r in live)}, C off {off}")
check("C0 C = hidden at every quadratic pair", off == 0 and
(len(rows), len(live), sum(r["hid"] for r in live)) ==
(38960, 17144, 9085), f"{off} off")
print()
print("P the 250 cubic bases, q^J <= 128")
rows = sweep(cubic_bases(), 128, h1=True)
live = [r for r in rows if r["live"]]
p1 = sum(r["c"] and not r["hid"] for r in rows)
p1p = sum(r["cp"] and not r["hid"] for r in rows)
full = [r for r in live if r["full"]]
p2 = sum(r["c"] != r["hid"] for r in full)
p3 = sum(r["h1"] and not r["c"] for r in live)
miss = [r for r in live if r["hid"] and not r["c"]]
print(f" pairs {len(rows)}, live {len(live)}, hidden "
f"{sum(r['hid'] for r in live)}, complete (N = q^j) {len(full)}")
print(f" P1 C true and unhidden: {p1}; plant (2q) {p1p}")
print(f" P2 off at N = q^j: {p2}")
print(f" P3 H1 true and C false: {p3}")
h1miss = [r for r in live if r["hid"] and not r["h1"]]
print(f" P4 misses (hidden, C false): {len(miss)}, at N = q^j "
f"{sum(r['full'] for r in miss)}; H1's misses {len(h1miss)}, "
f"of them C false {sum(not r['c'] for r in h1miss)}")
names = {}
for a in sorted({r["a"] for r in miss}):
B = Base(a, 128)
Q = [K for K in B.Is if K.N == 4 and (2, 0, 0) in K
and (1, 1, 1) in K]
Qr = Q[0].rows()
sq = [mul(u, v, a) for u in Qr for v in Qr]
Q2 = [K for K in B.Is if K.N == 16 and all(s in K for s in sq)]
twoQ = [K for K in B.Is if K.N == 32
and all(tuple(2 * x for x in u) in K for u in Qr)]
names[a] = (len(Q), Q2, twoQ)
named = []
for r in miss:
L = r["L"]
nq, Q2, twoQ = names[r["a"]]
name = ("Q^2" if any(K.rows() == L.rows() for K in Q2) else
"2Q" if any(K.rows() == L.rows() for K in twoQ) else "?")
B = Base(r["a"], 128)
ords = sorted({order(L, B.pw[k]) for k in range(r["j"])})
named.append((name, r["j"], r["reach"], ords))
print(f" {fmt(r['a']):22s} q {r['q']} j {r['j']} N {r['N']:3d}"
f" d {L.d} H {[x[1:] for x in L.H[:-1]]} I = {name}"
f" (Q found {nq}), |G_S| {r['reach']}, orders of g_k {ords}")
check("P1 C true and unhidden: 0; the plant fires",
p1 == 0 and p1p == 3346 and len(rows) == 24966,
f"{p1} over {len(rows)}, plant {p1p}")
check("P2 C = hidden at every complete pair",
p2 == 0 and len(full) == 4428 and len(live) == 12626,
f"{p2} off over {len(full)} of {len(live)}")
check("P3 H1 true and C false: 0", p3 == 0, f"{p3}")
check("P4 the 12 misses: Q^2 or 2Q, none complete, H1's 84 hold "
"them", len(miss) == 12 and not any(r["full"] for r in miss)
and len(h1miss) == 84
and sum(not r["c"] for r in h1miss) == 12
and all(nm in ("Q^2", "2Q") for nm, _, _, _ in named))
check("P4 at every miss the chain stops at its first step, each g_k "
"of order 4", all(rc == 1 and o == [4] for _, _, rc, o in named))
return off, p1, p1p, p2, p3, miss
def main():
t0 = time.time()
if "--misses" in sys.argv:
section_misses()
section_chain()
print()
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())