"""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())