dualmult.py
Checks: DUAL: The chain at depth pattern; property.
Cited on: DUAL.
To run it: save dualmult.py, with dualdeg.py, dualn.py beside it; standard library only.
"""dualmult.py -- the multiple side of the chain law: does the chain miss
only at ideals read at no depth?
QUESTION. dualn.py's setting: f monic of degree n, q = |f(0)| >= 2, O =
Z[x]/(f), G = O/I, g_k = beta^k mod I, the chain law C (S grows by any
k < j with q g_k in G_S; C iff G_S = G). C is sufficient at every
degree and a criterion at N = q^j; at the cubic sweep q^J <= 128 it
misses 12 hidden pairs, Q^2 and 2Q, Q = (2, beta^2 + beta + 1), each
at an ideal read at no depth. Does C miss only at ideals read at no
depth?
HAND (frozen before this file). Read at some depth iff beta is
nilpotent in O/I iff beta^T in I, T = ceil(log2 N): the subgroups
(beta^k O + I)/I fall strictly until they stop, each strict step at
least halving. N_n = [O : I + beta^T O] is the nilpotent part, N / N_n
the unit part; at Q^2 N_n = 1, at 2Q = Q^2 (2, beta) N_n = 2.
PREDICTIONS (frozen). Bases: the 250 cubic bases of dualn.py at q^J <=
256, and 108 quartic x^4 + a x^3 + b x^2 + c x +/- q, q = 2, 3, a, b, c
in -1..1, at q^J <= 64 (q = 2) and 81 (q = 3).
C1 the cubic pairs with q^j <= 128 give dualn.py's 12 misses.
C2 beta^j O, found among the ideals, read at depth exactly j, j <= J,
at every base; Q at x^3 + x^2 + x + 2 at no depth.
P5 every miss (hidden, C false) at an ideal read at no depth. PLANT:
the depth test on q beta in place of beta must break P5.
R (a read) the misses by base, q, (N, j), the multiplicity q^j/N,
N_n and the unit part; the denominator: hidden pairs at ideals
read at no depth, C true and C false.
E (a check added after the run, pinning its count) the early
pairs, hidden with j below the depth t, by q, and C at each: at j >= t, beta^j is in I, q
g_k lies in the span of g_(k+1), ..., g_(j-1) (q being in beta O),
and the chain runs down from j - 1, so only early pairs test P5.
KILL. P5's count of misses read at some depth > 0, over both families.
A clean P5 is a run, not a theorem: that side forbids, so it owes a
proof.
FINDINGS (entered after the run, from its printed output).
C1 12, dualn.py's. C2 1400/1400 cubic, 648/648 quartic; Q at none.
P5 0 misses read at some depth, both families; the plant 36.
R cubic: 14138 hidden pairs, 6612 at no depth (C true 6588, false
24); the 24 misses at x^3 +/- x^2 + x +/- 2, q = 2, by (N, j)
(16, 6), (16, 7), (16, 8), (32, 7), (32, 8), (64, 8), 4 each,
N_n 1, 2, 4 and the unit part 16 at every one. Quartic: 4338
hidden, 2124 at no depth (2112, 12); the 12 misses at x^4 +/- x^3
- x^2 +/- 2 and x^4 +/- x +/- 2, q = 2, (16, 6) 8 and (32, 6) 4,
N_n 1, the unit part 16 or 32. No miss at q >= 3. At all 36,
|G_S| = 1: no k < j has q g_k = 0.
K The kill misses: C misses only at ideals read at no depth, at
this scale (cubic q^J <= 256, quartic 64 and 81), a pattern; the
side owes a proof, its content the early pairs (E). Every miss
has a unit part of order >= 16 and a chain that never starts.
E 606 early pairs, all cubic at q = 4, C at all 606; quartic 0.
RUN RECORD. 6/6, 453.9 s, peak commit 15.8 MB under a memory guard.
"""
import os
import sys
import time
HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, os.path.join(HERE, "..", "code"))
from dualdeg import powers, hidden_by_count, mul, fmt # noqa: E402
from dualn import Base, chain, cubic_bases, addv # noqa: E402
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" {'PASS' if ok else 'FAIL'} {name}" +
(f" ({detail})" if detail else ""))
def quartic_bases():
for q in (2, 3):
for c0 in (q, -q):
for a3 in (-1, 0, 1):
for a2 in (-1, 0, 1):
for a1 in (-1, 0, 1):
yield (c0, a1, a2, a3)
def depth(L, a, gen):
"""The least t with gen^t in L, t <= ceil(log2 N), else None."""
T = max(1, (L.N - 1).bit_length())
x = tuple([1] + [0] * (len(a) - 1))
for t in range(T + 1):
if x in L:
return t
x = mul(x, gen, a)
return None
def span_size(L, gens):
zero = L.key(tuple([0] * len(gens[0])))
H = {zero}
for g in gens:
g = L.key(g)
if g in H:
continue
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
return len(H)
def nil_part(L, a):
"""N_n = [O : I + beta^T O], T = ceil(log2 N)."""
n = len(a)
T = max(1, (L.N - 1).bit_length())
pw = powers(a, T + n)
return L.N // span_size(L, [pw[T + i] for i in range(n)])
def run(bases, points_of):
rows, c2 = [], []
for a in bases:
q = abs(a[0])
B = Base(a, points_of(q))
n = B.n
beta = B.pw[1]
qbeta = tuple(q * x for x in beta)
ext = powers(a, B.J + n + 1)
for j in range(B.J + 1):
K = [L for L in B.Is if L.N == q ** j
and all(ext[j + i] in L for i in range(n))]
c2.append(len(K) == 1 and depth(K[0], a, beta) == j)
for L in B.Is:
c = chain(B, L)
dep = dp = None
for j in range(1, B.J + 1):
if (q ** j) % L.N:
continue
hid = hidden_by_count(L, B.T[j])
if not hid:
continue
if dep is None:
dep = (depth(L, a, beta),)
dp = (depth(L, a, qbeta),)
rows.append(dict(a=a, q=q, N=L.N, j=j, c=c[j] == L.N,
reach=c[j], dep=dep[0], dp=dp[0], L=L))
return rows, c2
def report(name, rows):
miss = [r for r in rows if not r["c"]]
nod = [r for r in rows if r["dep"] is None]
p5 = sum(r["dep"] is not None for r in miss)
p5p = sum(r["dp"] is not None for r in miss)
print(f" {name}: hidden pairs {len(rows)}, at no depth {len(nod)} "
f"(C true {sum(r['c'] for r in nod)}, C false "
f"{sum(not r['c'] for r in nod)}); misses {len(miss)}")
print(f" P5 misses read at some depth: {p5}; plant (q beta) {p5p}")
tally = {}
for r in miss:
key = (r["q"], r["N"], r["j"])
tally[key] = tally.get(key, 0) + 1
print(f" by (q, N, j): {dict(sorted(tally.items()))}")
early = [r for r in rows if r["dep"] is not None and r["j"] < r["dep"]]
byq = {}
for r in early:
byq[r["q"]] = byq.get(r["q"], 0) + 1
print(f" E early pairs {len(early)}, by q {dict(sorted(byq.items()))},"
f" C at {sum(r['c'] for r in early)}")
seen = set()
for r in miss:
L = r["L"]
k = (r["a"], tuple(L.rows()))
first = k not in seen
seen.add(k)
Nn = nil_part(L, r["a"]) if first else None
print(f" {fmt(r['a']):28s} q {r['q']} j {r['j']} N {r['N']:3d} "
f"mult {r['q'] ** r['j'] // r['N']:3d} depth {r['dep']} "
f"|G_S| {r['reach']}"
+ (f" N_n {Nn} unit {r['N'] // Nn}" if first else "")
+ f" H {[x[1:] for x in L.H[:-1]]}")
return miss, p5, p5p, early
def main():
t0 = time.time()
print("CUBIC 250 bases, q^J <= 256")
rows, c2 = run(cubic_bases(), lambda q: 256)
small = [r for r in rows if r["q"] ** r["j"] <= 128]
m128 = [r for r in small if not r["c"]]
check("C1 the q^j <= 128 pairs give dualn.py's 12 misses",
len(m128) == 12 and all(r["q"] == 2 for r in m128),
f"{len(m128)}")
Bq = Base((2, 1, 1), 128)
Q = [K for K in Bq.Is if K.N == 4 and (2, 0, 0) in K and (1, 1, 1) in K]
check("C2 beta^j O read at depth j at every cubic base; Q at none",
all(c2) and len(Q) == 1 and depth(Q[0], (2, 1, 1), Bq.pw[1])
is None, f"{sum(c2)}/{len(c2)}")
miss3, p5, p5p, e3 = report("cubic", rows)
print(f" {time.time() - t0:.1f} s")
print()
print("QUARTIC 108 bases, q^J <= 64 (q = 2), 81 (q = 3)")
rows4, c24 = run(quartic_bases(), lambda q: 64 if q == 2 else 81)
check("C2 beta^j O read at depth j at every quartic base", all(c24),
f"{sum(c24)}/{len(c24)}")
miss4, p54, p5p4, e4 = report("quartic", rows4)
print()
print("K the kill")
check("P5 no miss read at some depth, both families",
p5 + p54 == 0, f"{p5 + p54}")
check("P5's plant (q beta) fires", p5p + p5p4 > 0, f"{p5p + p5p4}")
check("E the early pairs, all at q = 4, C at every one",
len(e3) == 606 and not e4
and all(r["q"] == 4 and r["c"] for r in e3),
f"{len(e3)} cubic, {len(e4)} quartic")
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())