The ledger file frc/ledgers/p26_pnp.py of P versus NP: Computation as Counting, rendered with an anchor per line: the marked lines (# 26:C2 (p26010): a predicate and its accession key) are the checks that decide the predicates of the paper's predicate ledger — 23 of 23 checks passing; the predicates' theorems are the declarations of Pnp in the core. ▶ run the predicates on Google Colab.
1"""p26_pnp — the ledger file of 26-pnp (16 October 2026).23"P versus NP: Computation as Counting over Finite Relational Substrate" (Akhtman & Voether, 2026, preprint410.20944/preprints202606.1781.v1). The paper's predicate ledger is docs/26-pnp/26-pnp-ledger.json. This file binds its5predicates to the framework: the table of keys (generated from the ledger by ci/make_ledgers.py) and the checks of eight6blocks. The blocks follow the paper's sections; their checks compute what the paper's validation scripts computed7(validation/closure_pnp.py, chart_localization.py, longitudinal_turn.py, exact; dlog_asymmetry.py and8transform_charts.py, which timed the computer, are replaced by operation counts) and decide every theorem row that9admits a finite check. Each check names the predicate(s) it witnesses (LEDGER), under a `# 26:XN (<key>)` marker on the10check that decides it (PREDICATES). The Lean side is the horizon theme's Theme/Ladder.lean with 20-rh's11Theme/Horizon.lean, the foundation theme's Theme/Drive.lean and the frame theme's Transform.lean, the key files12Keys/Horizon.lean, Keys/Foundation.lean and Keys/Frame.lean (Mathlib: Keys/Chart.lean), and the certificates13lean/FrcCore/Ledgers/P26Pnp.lean and lean/FrcLedger/Ledgers/P26Pnp.lean.1415The checks call the horizon theme (frc/ladder.py: the ascent and the descent with their counts, the index dynamics, the16recentring, the Gauss sum in the cyclotomic ring, the number-theoretic transform, the affine systems over F_2;17frc/horizon.py: the scale shift), the foundation theme (frc/foundation.py), the quantum theme's cyclotomic ring18(frc/quantum.py) and the chart theme's certified bracket of Ω (frc/chart.py). This file itself is exact (gate G09): the19chart row is decided on the bracket's integer ends by bit length and integer square roots, no float, no random number,20no numeral above Ω.2122 python3 -m frc.ledgers.p26_pnp every block, the census; exit 1 if a check fails (≈ 3 s)23 python3 -m frc.ledgers.p26_pnp D one block24 from frc.ledgers.p26_pnp import R; R.predicate("26:F3") one predicate: its blocks run once per session2526Blocks, with the paper's section and the kind:27 L the longitudinal turn the characters as eigenvectors of the scale shift, the Gauss sum EXACT, L2 CHART (26:B3, B4, B5)28 H the horizon arithmetic the family's bits and the table beyond Ω^{1/4} on the bracket CHART, H2 EXACT (26:C2)29 C the localising chart the recentring, the index as counting distance, the bijection EXACT (26:E8, E10, F10)30 A the ascent square-and-multiply against 2ℓ EXACT (26:F2)31 D the descent baby-step–giant-step: the index recovered, the counts EXACT (26:F3, G4)32 R the roles and the closure the tower reduction, the phase formula, the counts, the image sizes EXACT (26:G2, G3, G4, G5)33 T the transforms the exact round trip over F_17, F_257, F_65537; the convolution counts EXACT (26:H3)34 W the affine witness sets Gaussian elimination over F_2 and the recentred chart EXACT (26:H4)3536A check is CHART when its verdict is a continuum reading: the dilation generator's eigenfunction (L2, the power rule37applied symbolically) and the family's bit length against the certified bracket of Ω = 4S + 1 (H1). The notebook38frc/ledgers/p26_pnp.ipynb runs one predicate per cell, the cell's id its key (gate G13).39"""40import sys41from fractions import Fraction as Fr42from math import isqrt4344from frc import arith45from frc import chart as CH46from frc import horizon as HZ47from frc import ladder as LD48from frc.quantum import Cyclotomic49from frc.registry import Registry5051# ---- generated by ci/make_ledgers.py from docs/26-pnp/26-pnp-ledger.json; edit the ledger, not this table ----52PAPER = "26-pnp"53KEYS = {"A1": "p26001", "A2": "p26002", "A3": "p26003", "A4": "p26004", "A5": "p26005", "A6": "p26006", "B1": "p26007", "B2": "p26008", "B3": "p26009", "B4": "p26010", "B5": "p26011", "C1": "p26012", "C2": "p26013", "D1": "p26014", "D2": "p26015", "D3": "p26016", "D4": "p26017", "E1": "p26018", "E2": "p26019", "E3": "p26020", "E4": "p26021", "E5": "p26022", "E6": "p26023", "E7": "p26024", "E8": "p26025", "E9": "p26026", "E10": "p26027", "E11": "p26028", "F1": "p26029", "F2": "p26030", "F3": "p26031", "F4": "p26032", "F5": "p26033", "F6": "p26034", "F7": "p26035", "F8": "p26036", "F9": "p26037", "F10": "p26038", "F11": "p26039", "G1": "p26040", "G2": "p26041", "G3": "p26042", "G4": "p26043", "G5": "p26044", "G6": "p26045", "H1": "p26046", "H2": "p26047", "H3": "p26048", "H4": "p26049", "H5": "p26050", "J1": "p26051", "J2": "p26052", "K1": "p26053", "K2": "p26054", "K3": "p26055", "K4": "p26056", "K5": "p26057", "K6": "p26058"} # every row of the ledger: its label and its accession key54LEAN = {"B3": "core", "B4": "ml", "B5": "core, ml", "C2": "ml", "E8": "core", "E10": "core", "F2": "core", "F3": "core", "F10": "core", "G2": "core", "G3": "core", "G4": "core", "G5": "core", "H3": "core"} # the rows with a Lean declaration: the libraries whose key files prove them55# ---- end of the generated table ----5657LEAN_ONLY = () # the predicates with a Lean declaration and no python check (gate G12): none5859# The paper's predicate ledger (predicates cited as 26:XN): the predicate(s) each check witnesses.60LEDGER = {61 "L1": "26:B3", "L2": "26:B4", "L3": "26:B5", "L4": "26:B5", "L5": "26:E10, 26:F10",62 "H1": "26:C2", "H2": "26:C2",63 "C1": "26:E8", "C2": "26:E10", "C3": "26:F10, 26:E10",64 "A1": "26:F2",65 "D1": "26:F3", "D2": "26:F3", "D3": "26:G4",66 "R1": "26:G2", "R2": "26:G3", "R3": "26:G4, 26:F2", "R4": "26:G5", "R5": "26:G2",67 "T1": "26:H3", "T2": "26:H3", "T3": "26:H3, 26:B3",68 "W1": "26:H4",69}7071BLOCK = {"L": "the longitudinal turn: the characters as eigenvectors of the scale shift, the Gauss sum",72 "H": "the horizon arithmetic: the family's bits and the table beyond the quarter root, on the bracket",73 "C": "the localising chart: the recentring, the index as counting distance, the bijection",74 "A": "the ascent: square-and-multiply against twice the bit length",75 "D": "the descent: baby-step-giant-step, the index recovered, the counts",76 "R": "the roles and the closure: the tower reduction, the phase formula, the counts, the image sizes",77 "T": "the transforms: the exact round trip and the convolution counts",78 "W": "the affine witness sets: Gaussian elimination over F_2 and the recentred chart"}7980# the deciding check of each witnessed predicate (the other checks that touch it are corroboration)81PREDICATES = {82 "26:B3": "L1", "26:B4": "L2", "26:B5": "L4", "26:C2": "H1", "26:E8": "C1", "26:E10": "C2", "26:F10": "C3",83 "26:F2": "A1", "26:F3": "D1", "26:G2": "R1", "26:G3": "R2", "26:G4": "R3", "26:G5": "R4", "26:H3": "T1",84 "26:H4": "W1",85}8687R = Registry("26", "pnp", LEDGER, PREDICATES, sources=[__file__])8889TURN = (13, 17, 53) # the suite's shells for the turn90CARRIERS = (10007, 1000003, 100000007) # the suite's carriers for the counts91LOCAL = (101, 1009, 10007, 100003) # the suite's shells for the localisation9293def g_of(p): return arith.primitive_root(p) # the least primitive root, the suite's generator949596# ---- L: the longitudinal turn --------------------------------------------------------------------------------------------97@R.block("L", BLOCK["L"])98def block_L():99 """Block L — longitudinal_turn.py (EXACT): the characters as eigenvectors of the scale shift (26:B3), the dilation100 generator (26:B4, CHART), the Gauss-sum telescoping and modulus (26:B5), the exponential bijection (26:E10, F10)."""101 # L1: the scale shift x ↦ g x on the units, the characters χ_ν(g^t) = g^{νt} its eigenvectors, eigenvalue g^ν, distinct102 ok, det = True, []103 for p in TURN:104 g, n = g_of(p), p - 1105 lams = set()106 for nu in range(n):107 v = [pow(g, nu * t % n, p) for t in range(n)]108 lam = pow(g, nu, p)109 ok &= all(v[(t + 1) % n] == lam * v[t] % p for t in range(n)) # (S v)_t = v_{t+1} = λ v_t110 lams.add(lam)111 ok &= len(lams) == n112 fixed = [len(HZ.fixed_points(p, g, r)) for r in (0, 1, n // 2, n, n + 1)]113 ok &= fixed == [n, 0, 0, n, 0]114 det.append(f"F_{p}: {n} eigenvectors, {len(lams)} distinct eigenvalues, fixed points {fixed}")115 # 26:B3 (p26009)116 R.check("L1", "the characters are eigenvectors of the scale shift x -> g x with the (P-1)-th roots of unity as distinct eigenvalues; the shift fixes every unit when (P-1) | r and none otherwise",117 ok, "; ".join(det))118119 # L2: Ĥ = -i(x d/dx + 1/2) on x^s with s = -1/2 + i ν: by the power rule x d/dx x^s = s x^s, so Ĥ x^s = -i(s + 1/2) x^s,120 # and -i(s + 1/2) = -i(i ν) = ν. Computed in Q(i)[ν]: a number is (re, im) with coefficients polynomials in ν (lists).121 def padd(a, b): return [x + y for x, y in zip(a + [0] * (len(b) - len(a)), b + [0] * (len(a) - len(b)))]122 def pmul(a, b):123 out = [Fr(0)] * (len(a) + len(b) - 1)124 for i, x in enumerate(a):125 for j, y in enumerate(b): out[i + j] += x * y126 return out127 def cmul(z, w): # (re, im) × (re, im)128 return padd(pmul(z[0], w[0]), [-c for c in pmul(z[1], w[1])]), padd(pmul(z[0], w[1]), pmul(z[1], w[0]))129 def strip(a):130 while a and a[-1] == 0: a = a[:-1]131 return a132 s = ([Fr(-1, 2)], [Fr(0), Fr(1)]) # s = -1/2 + i ν133 coef = cmul(([Fr(0)], [Fr(-1)]), (padd(s[0], [Fr(1, 2)]), s[1])) # -i (s + 1/2)134 nu = ([Fr(0), Fr(1)], [])135 ok = strip(coef[0]) == strip(nu[0]) and strip(coef[1]) == strip(nu[1])136 # 26:B4 (p26010)137 R.check("L2", "the dilation generator H = -i(x d/dx + 1/2) has x^(-1/2 + i nu) as eigenfunction of eigenvalue nu: the eigenvalue's coefficient -i(s + 1/2) with s = -1/2 + i nu is nu, computed in Q(i)[nu] (the power rule x d/dx x^s = s x^s is the chart's)",138 ok, "-i(s + 1/2) = nu exactly; the power rule x d/dx x^s = s x^s is the chart's", kind="CHART")139140 # L3: the telescoping: t ↦ tc permutes the units; Σ_{t≠0} ψ(tc) = -1 (c ≠ 0) or P-1 (c = 0) in Z[ζ_P]; Σ_u χ(u) = 0 for χ ≠ 1141 ok, det = True, []142 for p in TURN:143 g, n = g_of(p), p - 1144 ok &= all(LD.mul_perm(c, p) for c in range(1, p))145 Cp = Cyclotomic(p)146 ok &= all(LD.ramanujan(p, c, Cp) == Cp.const(-1) for c in range(1, p)) and LD.ramanujan(p, 0, Cp) == Cp.const(n)147 Cn = Cyclotomic(n)148 ok &= all(Cn.sum(Cn.zeta(nu * t % n) for t in range(n)) == Cn.zero for nu in range(1, n))149 ok &= Cn.sum(Cn.zeta(0) for t in range(n)) == Cn.const(n)150 det.append(f"F_{p}: every c permutes the units; the additive sums -1 and {n}; the {n - 1} nontrivial character sums vanish")151 R.check("L3", "the telescoping of the Gauss sum: multiplication by a unit permutes the units, the additive character sum over the units is -1 for c != 0 and P-1 for c = 0, every nontrivial multiplicative character sums to 0",152 ok, "; ".join(det))153154 # L4: |g(χ_ν)|² = P exactly in Z[ζ_{P(P-1)}]155 ok, det = True, []156 for p, nus in ((13, (1, 2, 5, 11)), (17, (1, 3, 8))):157 g, n = g_of(p), p - 1158 C = Cyclotomic(p * n)159 res = [LD.gauss_norm(p, g, nu, C) == C.const(p) for nu in nus]160 ok &= all(res)161 det.append(f"F_{p}: g(chi)·conj g(chi) = {p} in Z[zeta_{p * n}] for nu in {nus}")162 # 26:B5 (p26011)163 R.check("L4", "the Gauss sum of a nontrivial character against the additive character has modulus squared P, computed exactly in the cyclotomic ring Z[zeta_{P(P-1)}]",164 ok, "; ".join(det))165166 # L5: exp t ↦ g^t is a bijection C_{P-1} → the units167 ok, det = True, []168 for p in TURN:169 g, n = g_of(p), p - 1170 img = [pow(g, t, p) for t in range(n)]171 ok &= sorted(img) == list(range(1, p))172 det.append(f"F_{p}: the {n} powers of {g} are the units")173 R.check("L5", "the exponential t -> g^t is a bijection of the index cycle onto the units", ok, "; ".join(det))174175176# ---- H: the horizon arithmetic on the bracket --------------------------------------------------------------------------177@R.block("H", BLOCK["H"])178def block_H():179 """Block H (CHART on the bracket): the family P^2 < Ω has at most 205 bits, a 204-bit decision table exceeds the180 absolute horizon Ω^{1/4} (26:C2); the three scales on the worked carriers (EXACT)."""181 lo, hi = CH.omega_bracket()182 flo, fhi = lo.numerator // lo.denominator, hi.numerator // hi.denominator # the integer floors of the ends183 s_lo, s_hi = isqrt(flo), isqrt(fhi) # ⌊√Ω⌋ at the two ends184 q_lo, q_hi = isqrt(s_lo), isqrt(s_hi) # ⌊Ω^{1/4}⌋185 ok = (flo.bit_length() == 410 == fhi.bit_length() and 2 ** 204 < s_lo and s_hi < 2 ** 205186 and 2 ** 102 < q_lo and q_hi < 2 ** 103 and 2 ** 204 > q_hi and s_lo.bit_length() == 205 == s_hi.bit_length()187 and q_lo.bit_length() == 103 == q_hi.bit_length())188 # 26:C2 (p26013)189 R.check("H1", "on the certified bracket of Omega = 4S + 1: 2^204 < sqrt(Omega) < 2^205, so the family P^2 < Omega has shells of at most 205 bits; 2^102 < Omega^(1/4) < 2^103, so a 204-bit decision table (2^204 entries) lies beyond the absolute horizon and below sqrt(Omega)",190 ok, f"the bracket's ends have bit length {flo.bit_length()}; sqrt(Omega) has {s_lo.bit_length()} bits ({len(str(s_lo))} digits), Omega^(1/4) has {q_lo.bit_length()} bits ({len(str(q_lo))} digits); no numeral beyond the bracket's ends formed", kind="CHART")191192 # H2: the three scales on the worked carriers: P^2 < Omega (the family), the descent's count 2(isqrt(P-1)+1) < sqrt(P)·2 + 2 ≤ Omega^{1/4}, P < sqrt(Omega)193 ok, det = True, []194 for p in (13, 101, 1009, 10007, 1000003, 100000007):195 m = isqrt(p - 1) + 1196 ok &= p * p < flo and m * m >= p - 1 and (m - 1) ** 2 <= p - 1 and 2 * m < q_lo and p < s_lo197 det.append(f"P={p}: m={m}, 2m={2 * m}")198 R.check("H2", "the three scales at the worked carriers: P^2 < Omega (the family), the giant-step bound 2(isqrt(P-1)+1) is far below Omega^(1/4), and P itself below sqrt(Omega)",199 ok, "; ".join(det))200201202# ---- C: the localising chart -----------------------------------------------------------------------------------------------203@R.block("C", BLOCK["C"])204def block_C():205 """Block C — chart_localization.py (EXACT): the recentring chart (26:E8), the index as counting distance and the206 bijection (26:E10), the ascent as the coordinate map and the descent as its inverse (26:F10)."""207 # C1: for every index m the translation recentre(n, m, ·) carries m to 1, one step from the origin 0, and permutes the indices208 ok, det = True, []209 for p in (13, 101, 1009):210 g, n = g_of(p), p - 1211 for m in range(n):212 ok &= pow(g, LD.recentre(n, m, m), p) == g == pow(g, 0, p) * g % p213 ok &= sorted(LD.recentre(n, m, j) for j in range(n)) == list(range(n))214 det.append(f"F_{p}: every m carried to 1 by a permutation of the {n} indices")215 # 26:E8 (p26025)216 R.check("C1", "existence is free: for every witness index m the translated chart recentre(n, m, .) places m one counting step from the origin and is a bijection of the index cycle",217 ok, "; ".join(det))218219 # C2: the counting distance of a unit is its index 1..P-1 (the suite's convention: g^k reached after k steps, 1 = g^(P-1) after P-1); a bijection, mean P/2, maximum P-1 = 2^ell - O(1)220 ok, det = True, []221 for p in LOCAL:222 g, n = g_of(p), p - 1223 dist, x = {}, 1224 for k in range(1, p):225 x = x * g % p226 dist.setdefault(x, k)227 vals = sorted(dist.values())228 ell = (p - 1).bit_length() # ⌈log₂ P⌉ for P not a power of two229 mean = Fr(sum(vals), n)230 ok &= vals == list(range(1, p)) and mean == Fr(p, 2) and max(vals) == n and 2 ** (ell - 1) < n < 2 ** ell231 det.append(f"F_{p}: bijection onto 1..{n}, mean {mean}, max {n}, ell={ell} bits")232 # 26:E10 (p26027)233 R.check("C2", "the counting distance of a unit along the orbit of g is its index: a bijection onto 1..P-1 with mean P/2 and maximum P-1, between 2^(ell-1) and 2^ell for ell the bit length",234 ok, "; ".join(det))235236 # C3: a_P(j) = g^j is the coordinate map C_{P-1} -> units and d_P = dlog its inverse, agreeing with the index table237 ok, det = True, []238 for p in (13, 17, 53, 101):239 g, n = g_of(p), p - 1240 table = LD.index_table(g, p)241 ok &= sorted(table) == list(range(1, p)) and sorted(table.values()) == list(range(n))242 ok &= all(pow(g, m, p) == x for x, m in table.items()) # each index reproduces its unit243 ok &= all(LD.dlog(g, pow(g, j, p), p) == j for j in range(n)) and all(pow(g, LD.dlog(g, x, p), p) == x for x in range(1, p))244 ok &= all(LD.dlog(g, pow(g, j, p), p) == j % n for j in (n, n + 1, 2 * n + 3)) # an exponent beyond the cycle reads modulo n245 det.append(f"F_{p}: a_P a bijection, dlog its two-sided inverse on all {n} units")246 # 26:F10 (p26038)247 R.check("C3", "the ascent a_P: j -> g^j is a bijection of the index cycle onto the units and the descent dlog is its inverse on every unit",248 ok, "; ".join(det))249250251# ---- A: the ascent -----------------------------------------------------------------------------------------------------------252@R.block("A", BLOCK["A"])253def block_A():254 """Block A — closure_pnp.py T2 (EXACT): square-and-multiply within 2ℓ multiplications (26:F2)."""255 ok, det = True, []256 def exact_counts(e): # the counts the two scans must report, from the bit pattern of e alone257 b, ones = len(bin(e)) - 2 if e > 0 else 0, bin(e).count("1")258 return b - 1 + ones if e > 0 else 0, b + ones # right to left (the last squaring skipped), left to right259 for p in CARRIERS:260 g, ell = g_of(p), p.bit_length()261 for e in (p - 2, p // 3):262 v, ops = LD.sqmul(g, e, p); v2, ops2 = LD.sqmul_ltr(g, e, p)263 ok &= v == pow(g, e, p) == v2 and (ops, ops2) == exact_counts(e) and ops <= ops2 <= 2 * ell and ops2 <= 2 * LD.bits(e)264 det.append(f"P={p}: ell={ell}, {LD.sqmul(g, p - 2, p)[1]} and {LD.sqmul(g, p // 3, p)[1]} multiplications at e=P-2, P/3 (bound {2 * ell})")265 for e in range(1 << 10):266 v, ops = LD.sqmul(2, e, 13); v2, ops2 = LD.sqmul_ltr(2, e, 13)267 ok &= v == pow(2, e, 13) == v2 and (ops, ops2) == exact_counts(e) and ops2 <= 2 * LD.bits(e)268 ok &= (LD.bits(e) == 0 if e == 0 else (1 << (LD.bits(e) - 1)) <= e < (1 << LD.bits(e))) # bits(e) against the powers of two269 # 26:F2 (p26030)270 R.check("A1", "square-and-multiply computes g^j in at most 2·bits(j) modular multiplications, hence at most 2·ell for j < P, the counts those of the bit pattern (right to left with the last squaring skipped: bits(j) - 1 + popcount(j); left to right: bits(j) + popcount(j)): on the three carriers at j = P-2 and P/3, and on F_13 for every j < 2^10",271 ok, "; ".join(det) + "; F_13: every e < 1024 within 2·bits(e)")272273274# ---- D: the descent ------------------------------------------------------------------------------------------------------275@R.block("D", BLOCK["D"])276def block_D():277 """Block D — closure_pnp.py T3 (EXACT): baby-step–giant-step recovers the index with the stated counts (26:F3); the278 bound (26:F3); the ratio table (26:G4)."""279 ok, det = True, []280 counts = {}281 for p in CARRIERS:282 g, n = g_of(p), p - 1283 m = isqrt(n) + 1284 x = p // 3285 res = LD.bsgs(g, pow(g, x, p), p)286 i, j, giant = res287 ok &= pow(g, j + m * i, p) == pow(g, x, p) and (j + m * i) % n == x and giant <= m and j < m288 counts[p] = (m, giant, m + giant)289 det.append(f"P={p}: m={m}, {giant} giant steps, {m + giant} operations")290 ok &= [counts[p][2] for p in CARRIERS] == [134, 1334, 13334]291 for p, m in ((13, 4), (101, 10)):292 g = g_of(p)293 ok &= all(LD.descends(g, pow(g, x, p), p, m) for x in range(p - 1))294 res = [LD.bsgs(g, pow(g, x, p), p, m) for x in range(p - 1)]295 ok &= all(r is not None and r[1] < m and (r[1] + m * r[0]) % (p - 1) == x for x, r in enumerate(res)) # the pair itself296 ok &= not LD.descends(g_of(101), pow(g_of(101), 50, 101), 101, 3) and LD.descends(g_of(101), pow(g_of(101), 8, 101), 101, 3) # m = 3 reaches 8, not 50297 # 26:F3 (p26031)298 R.check("D1", "baby-step-giant-step with m = isqrt(P-1)+1 recovers the index of g^x: on the three carriers at x = P/3 with 134, 1334, 13334 operations (the m baby steps and the giant steps), and on F_13 (m = 4) and F_101 (m = 10) for every target",299 ok, "; ".join(det) + "; F_13 and F_101: every index recovered")300301 # D2: the bound: m^2 >= P-1 and the operation count m + i <= 2m = 2(isqrt(P-1)+1); every target on F_101 within the bound302 ok, det = True, []303 for p in (101, 1009, 10007):304 g, n = g_of(p), p - 1305 m = isqrt(n) + 1306 worst = 0307 for x in range(n):308 i, j, giant = LD.bsgs(g, pow(g, x, p), p)309 ok &= giant < m and (j + m * i) % n == x310 worst = max(worst, m + giant)311 ok &= m * m >= n and worst <= 2 * m312 det.append(f"F_{p}: m={m}, worst {worst} <= {2 * m}")313 R.check("D2", "the descent's bound: with m^2 >= P-1 every index is recovered within 2m = 2(isqrt(P-1)+1) operations, checked on every target of F_101, F_1009 and F_10007",314 ok, "; ".join(det))315316 # D3: the ratio table of prop:invlast, descent over ascent at the three carriers (the data the paper quotes)317 pairs = []318 for p in CARRIERS:319 g = g_of(p)320 asc = LD.sqmul(g, p // 3, p)[1]321 i, j, giant = LD.bsgs(g, pow(g, p // 3, p), p)322 pairs.append((isqrt(p - 1) + 1 + giant, asc))323 ratios = [Fr(d, a) for d, a in pairs]324 ok = pairs == [(134, 17), (1334, 26), (13334, 38)] and ratios[0] < ratios[1] < ratios[2] and ratios[-1] > 5 * ratios[0]325 R.check("D3", "the descent/ascent operation ratio at the three carriers: 134/17, 1334/26, 13334/38 (7.9, 51.3, 350.9), growing with the carrier",326 ok, "; ".join(f"P={p}: {d}/{a}" for p, (d, a) in zip(CARRIERS, pairs)))327328329# ---- R: the roles and the closure ----------------------------------------------------------------------------------------330@R.block("R", BLOCK["R"])331def block_R():332 """Block R — closure_pnp.py T1, T2, T4 (EXACT): the tower reduction (26:G2), the phase formula (26:G3), the four333 roles' counts (26:G4), the bijective and the compressive power maps (26:G5)."""334 # R1: a tower exponent is read modulo P-1; the index map m -> k m; the orbit of iterated exponentiation closes335 ok, det = True, []336 for p in (13, 101, 1009):337 g, n = g_of(p), p - 1338 ok &= all(LD.tower(g, j, p) == (pow(g, pow(g, j, p), p), pow(g, pow(g, j, p) % n, p)) for j in range(n)) # against pow339 ok &= all(pow(g, pow(g, j, p), p) == pow(g, pow(g, j, p) % n, p) for j in range(n)) # the identity itself340 ok &= any(pow(g, j, p) >= n for j in range(n)) # the reduction acts341 ok &= all(pow(pow(g, m, p), k, p) == pow(g, k * m % n, p) for m in range(n) for k in (2, 3, 5, 7))342 seen, j, steps = {}, 1, 0 # j ↦ (g^j mod P) mod n, the tower read as an index343 while j not in seen:344 seen[j] = steps; j = pow(g, j, p) % n; steps += 1345 ok &= steps <= n346 det.append(f"F_{p}: g^(g^j) = g^((g^j) mod {n}) for every j; the iterated exponential closes in {steps} steps")347 # 26:G2 (p26041)348 R.check("R1", "the two cyclic structures host every iterate: a tower exponent g^j is read modulo P-1, the power map acts on the index as multiplication, and iterated exponentiation closes on the index cycle",349 ok, "; ".join(det))350351 # R2: the phase formula P_k^r(g^m) = g^(k^r m mod n) over the suite's cases, and the ascent step352 ok, cases = True, 0353 for p in (13, 101, 1009, 10009):354 g, n = g_of(p), p - 1355 for k in (2, 3, 5, 7, 10):356 for m in (1, 2, 7):357 for r in (0, 1, 2, 3, 5):358 it, closed = LD.phase_index(g, m, k, r, p)359 x = pow(g, m, p)360 for _ in range(r): x = pow(x, k, p) # the iterate, by pow361 ok &= it == x == closed == pow(g, pow(k, r, n) * m % n, p); cases += 1 # the closed form, by pow362 ok &= all(pow(g, j + 1, p) == g * pow(g, j, p) % p for j in range(n))363 # 26:G3 (p26042)364 R.check("R2", "the phase-index dynamics: P_k^r(g^m) = g^(k^r m mod (P-1)) over the suite's cases on four carriers, and the ascent g^(j+1) = g · g^j is one multiplication per counted step",365 ok, f"{cases} (P, k, m, r) cases, no violation")366367 # R3: the four roles' counts on an instrumented residue (every modular operation counted): succession one, addition one,368 # multiplication one, the ascent at most 2ℓ; the descent recovers the index (the G18 round of 16 October 2026: the first369 # version compared the three lower roles' results with themselves)370 class Counted:371 """A residue mod p whose operations are counted: one per +, one per *, as the cost model (26:G1) reads them."""372 ops = 0373 def __init__(self, v, p): self.v, self.p = v % p, p374 def __add__(self, o): Counted.ops += 1; return Counted(self.v + (o.v if isinstance(o, Counted) else o), self.p)375 def __mul__(self, o): Counted.ops += 1; return Counted(self.v * (o.v if isinstance(o, Counted) else o), self.p)376 def __pow__(self, e): # square-and-multiply, right to left, through * only377 r, b = Counted(1, self.p), self378 while e > 0:379 if e % 2 == 1: r = r * b380 e //= 2381 if e > 0: b = b * b382 return r383 ok, det = True, []384 for p in CARRIERS:385 g, n, ell = g_of(p), p - 1, p.bit_length()386 a = Counted(p // 7, p)387 Counted.ops = 0; succ = a + 1; c1 = Counted.ops # succession: one operation388 Counted.ops = 0; add = a + a; c2 = Counted.ops # addition: one389 Counted.ops = 0; mult = a * a; c3 = Counted.ops # multiplication: one390 Counted.ops = 0; asc = Counted(g, p) ** (p // 3); c4 = Counted.ops # the ascent: at most 2ℓ391 ok &= (succ.v, add.v, mult.v, asc.v) == ((p // 7 + 1) % p, 2 * (p // 7) % p, (p // 7) ** 2 % p, pow(g, p // 3, p))392 ok &= (c1, c2, c3) == (1, 1, 1) and c4 <= 2 * ell and c4 == LD.sqmul(g, p // 3, p)[1]393 i, j, giant = LD.bsgs(g, asc.v, p)394 ok &= (j + (isqrt(n) + 1) * i) % n == p // 3 and giant <= isqrt(n) + 1395 det.append(f"P={p}: succession, addition, multiplication {c1}, {c2}, {c3} operations; ascent {c4} <= {2 * ell}; descent {isqrt(n) + 1 + giant} operations")396 # 26:G4 (p26043)397 R.check("R3", "on a residue whose modular operations are counted, succession, addition and multiplication cost one operation each and the ascent at most 2·ell multiplications; the descent recovers the index from its orbit position, the inverse of the last role",398 ok, "; ".join(det))399400 # R4: P_k is a bijection iff k is invertible mod P-1 (inverse exponent a with a k ≡ 1), else the image is the cycle of g^d, d = gcd(k, P-1), of size (P-1)/d401 ok, det = True, []402 for p, ks in ((1009, (2, 3, 4, 6, 7)), (10009, (2, 3, 4, 6, 7)), (13, tuple(range(1, 12)))):403 g, n = g_of(p), p - 1404 for k in ks:405 d, a, b = LD.bezout(k, n)406 ok &= a * k == b * n + d407 img = LD.power_image(k, p)408 ok &= len(img) == n // d409 if d == 1:410 ok &= all(pow(pow(x, k, p), a, p) == x for x in range(1, p))411 else:412 gd = pow(g, d, p)413 cyc = sorted(pow(gd, i, p) for i in range(n // d))414 ok &= img == cyc and all(pow(pow(pow(g, a, p), i, p), k, p) == pow(gd, i, p) for i in range(n // d))415 det.append(f"F_{p}: k in {ks}: image sizes {[n // LD.bezout(k, n)[0] for k in ks]}")416 # 26:G5 (p26044)417 R.check("R4", "the power map x -> x^k is a bijection of the units iff k is invertible modulo P-1, inverted by the exponent a with a k = 1; otherwise its image is the cycle of g^d, d = gcd(k, P-1), of (P-1)/d elements",418 ok, "; ".join(det))419420 # R5: the index-cycle orbit r -> k^r m mod n is eventually periodic (the suite's T4 period)421 ok, det = True, []422 for p in (1009, 10009):423 n = p - 1424 for k in (2, 3, 4, 6, 7):425 seen, m, r = {}, 1, 0426 while m not in seen:427 seen[m] = r; m = k * m % n; r += 1428 period = r - seen[m]429 ok &= 1 <= period <= n430 det.append(f"F_{p}, k={k}: period {period}")431 R.check("R5", "the iteration of the power map on the index, r -> k^r m mod (P-1), is eventually periodic: a finite counted orbit, not a new primitive role",432 ok, "; ".join(det))433434435# ---- T: the transforms ---------------------------------------------------------------------------------------------------436@R.block("T", BLOCK["T"])437def block_T():438 """Block T — transform_charts.py replaced by exact counts (EXACT): the additive transform's exact round trip on the439 shell and the convolution counts in the two charts (26:H3)."""440 ok, det = True, []441 for q, n, w in ((17, 8, 2), (257, 256, 3), (65537, 1 << 16, 3)):442 ok &= pow(w, n, q) == 1 and pow(w, n // 2, q) == q - 1443 a = [(i * i + 1) % q for i in range(n)]444 A, o1 = LD.ntt(a, w, q)445 b, o2 = LD.intt(A, w, q)446 ok &= b == a and o1 == o2 == (n // 2) * n.bit_length() - n // 2447 if n <= 256: # the transform is the matrix w^(jk): n^2 products448 ok &= A == [sum(a[j] * pow(w, j * k, q) for j in range(n)) % q for k in range(n)]449 else: # at n = 2^16: eight rows of the matrix450 ok &= all(A[k] == sum(a[j] * pow(w, j * k, q) for j in range(n)) % q for k in (0, 1, 2, 3, 255, 4096, 32768, n - 1))451 det.append(f"F_{q}, n={n}: T^-1 T a = a exactly, {o1} butterflies, T the matrix w^(jk)")452 # 26:H3 (p26048)453 R.check("T1", "the additive transform on the shell is exact and self-inverse: the number-theoretic transform over F_17 (n = 8), F_257 (n = 256) and F_65537 (n = 2^16) returns the vector exactly, with (n/2) log2 n butterflies",454 ok, "; ".join(det))455456 # T2: the convolution counts at n = 2^10 over F_65537: n^2 in the position chart against three transforms and n products457 q, n = 65537, 1 << 10458 w = pow(3, (q - 1) // n, q)459 a = [(i * i + 1) % q for i in range(n)]; b = [(3 * i + 7) % q for i in range(n)]460 c1, o1 = LD.convolve_direct(a, b, q)461 c2, o2 = LD.convolve_ntt(a, b, w, q)462 ok = c1 == c2 and o1 == n * n == 1048576 and o2 == 3 * ((n // 2) * 10) + n == 16384463 R.check("T2", "the same convolution target far in the position chart and near through the transform: n^2 = 1,048,576 multiplications against 16,384 at n = 2^10 over F_65537, the two results equal",464 ok, f"direct {o1}, through the transform {o2}")465466 # T3: the transform is the shell DFT of the frame (p, g): over F_17 with the full cycle n = 16 and w = g = 3, ntt agrees with the matrix g^(jk)467 p, g = 17, 3468 n = p - 1469 a = [(i * i + 1) % p for i in range(n)]470 A, _ = LD.ntt(a, g, p)471 W = [[pow(g, j * k, p) for j in range(n)] for k in range(n)]472 B = [sum(W[k][j] * a[j] for j in range(n)) % p for k in range(n)]473 ok = A == B474 R.check("T3", "the number-theoretic transform on the full cycle of F_17 (w = g = 3) is the shell's Fourier matrix g^(jk) applied to the vector", ok)475476477# ---- W: the affine witness sets -------------------------------------------------------------------------------------------478@R.block("W", BLOCK["W"])479def block_W():480 """Block W (EXACT): Gaussian elimination over F_2 returns a particular solution and a basis; every solution is481 reached from the recentred origin within the basis's size (26:H4)."""482 systems = [483 ([[1, 0, 1, 1, 1], [0, 1, 1, 0, 0], [1, 1, 0, 1, 1]], 4),484 ([[1, 1, 0, 0, 1, 0, 0], [0, 1, 1, 0, 0, 1, 1], [1, 0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1]], 6),485 ([[1, 1, 0, 0, 1, 0, 1], [0, 1, 1, 0, 0, 1, 0], [1, 0, 1, 1, 0, 0, 1], [0, 0, 0, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0]], 6),486 ([[(i * j + i + j) % 2 for j in range(8)] + [i % 2] for i in range(5)], 8),487 ]488 ok, det = True, []489 for rows, ncols in systems:490 res = LD.affine_f2(rows, ncols)491 sols = LD.f2_solutions(rows, ncols)492 if res is None:493 ok &= sols == []; det.append(f"{len(rows)}x{ncols}: inconsistent, no solution"); continue494 w0, basis = res495 ok &= w0 in sols and len(sols) == 2 ** len(basis) and len(basis) <= ncols496 span, steps = set(), {}497 for mask in range(1 << len(basis)):498 v = list(w0)499 for t, bvec in enumerate(basis):500 if mask >> t & 1: v = [x ^ y for x, y in zip(v, bvec)]501 span.add(tuple(v)); steps[tuple(v)] = min(steps.get(tuple(v), ncols + 1), bin(mask).count("1"))502 ok &= span == {tuple(s) for s in sols}503 # the recentred chart w ↦ w - w0: the origin (mask 0) is a witness, every solution within len(basis) basis steps504 ok &= steps.get(tuple(w0)) == 0 and all(steps.get(tuple(s), ncols + 1) <= len(basis) for s in sols) and max(steps.values()) == len(basis)505 det.append(f"{len(rows)}x{ncols}: {len(sols)} solutions = w0 + span of {len(basis)}")506 # 26:H4 (p26049)507 R.check("W1", "an affine F_2-system's solutions are w0 + the span of a basis returned by Gaussian elimination; in the recentred chart the origin is a witness and every solution lies within the basis's size in counting steps",508 ok, "; ".join(det))509510511if __name__ == "__main__":512 want = [a.upper() for a in sys.argv[1:]] or sorted(BLOCK)513 bad = [b for b in want if b not in BLOCK]514 if bad: sys.exit(f"no block {', '.join(bad)}: the blocks are {', '.join(sorted(BLOCK))}")515 for b in want: R.run_block(b)516 sys.exit(0 if R.summary(write=False, expect=list(LEDGER) if want == sorted(BLOCK) else None) else 1)517