longitudinal_turn.py — src/26-pnp

1#!/usr/bin/env python32# -*- coding: utf-8 -*-3"""4longitudinal_turn.py  --  the frequency domain as the longitudinal quarter turn.56Validates the rigorous spine of the frequency-domain blueprint (26-pnp), float-free in the7native finite-field (framed-rational) arena, with one symbolic continuum-shadow check.89  P1  the longitudinal turn = the multiplicative DFT on Z/(P-1): it diagonalises the scale10      shift theta -> g.theta, the multiplicative characters chi_nu being eigenvectors with the11      (P-1)-th roots of unity as eigenvalues; the eigen-index nu is the FREQUENCY.12      Continuum shadow: it diagonalises H = -i(x d/dx + 1/2), eigenfns x^{-1/2+i nu}, eigenvalue nu13      => frequency = spectrum of the dilation generator H.1415  P2  the Gauss sum g(chi)=sum_theta chi(theta) psi(theta) couples an additive character16      (SPECTRUM) to a multiplicative one (FREQUENCY); for chi nontrivial |g(chi)|^2 = P.17      Verified by the exact additive-character telescoping (integer/combinatorial, no floats):18      sum_{t!=0} psi(t c) = -1 (c!=0), = P-1 (c=0).1920  P3  the two turns are the classical/quantum line: the TRANSVERSE additive turn is an exact21      self-invertible transform (NTT round-trip over F_q, float-free) -- the classical FFT, in P;22      the LONGITUDINAL multiplicative turn underlies exp:Z/(P-1)->F_P^x (a bijection) whose forward23      inverse is dlog -- BQP-forward, classically arrow-bound (cf. dlog_asymmetry.py).24"""25from fractions import Fraction as Fr26import sympy as sp2728PASS = []29def check(name, cond):30    PASS.append(bool(cond)); print(f"  [{'OK' if cond else 'XX'}] {name}")3132def primroot(p):33    """least primitive root mod p (p prime)."""34    fac = sp.factorint(p-1)35    for g in range(2, p):36        if all(pow(g, (p-1)//q, p) != 1 for q in fac):37            return g38    raise RuntimeError3940# ---------- P1: multiplicative DFT diagonalises the scale shift ----------41print("P1  longitudinal turn = multiplicative DFT diagonalises the scale shift")42for p in (13, 17, 53):43    g = primroot(p)                  # generator of F_p^x  (order n=p-1)44    n = p - 145    zeta = g                         # a primitive n-th root of unity lives IN F_p: zeta=g46    # eigenvector for frequency nu: chi_nu(g^t) = zeta^{nu t}; shift S: (S f)(t)=f(t+1)47    ok_eig, ok_distinct = True, set()48    for nu in range(n):49        v = [pow(zeta, (nu*t) % n, p) for t in range(n)]50        Sv = [v[(t+1) % n] for t in range(n)]            # shifted51        lam = pow(zeta, nu, p)                            # claimed eigenvalue52        if any((Sv[t] - lam*v[t]) % p != 0 for t in range(n)):53            ok_eig = False54        ok_distinct.add(lam)55    check(f"p={p}: every chi_nu is an eigenvector of the scale shift (exact in F_{p})", ok_eig)56    check(f"p={p}: the {n} eigenvalues are distinct (full diagonalisation)", len(ok_distinct)==n)5758# P1 continuum shadow: H x^{-1/2+i nu} = nu x^{-1/2+i nu}59print("P1  continuum shadow: H=-i(x d/dx + 1/2) on x^{-1/2+i nu}")60x = sp.symbols('x', positive=True); nu = sp.symbols('nu', real=True)61phi = x**(sp.Rational(-1,2) + sp.I*nu)62Hphi = -sp.I*(x*sp.diff(phi, x) + sp.Rational(1,2)*phi)63check("H phi = nu phi exactly (eigen-index nu = frequency = spectrum of H)",64      sp.simplify(Hphi - nu*phi) == 0)6566# ---------- P2: Gauss-sum modulus |g(chi)|^2 = P via exact telescoping ----------67print("P2  Gauss sum couples spectrum<->frequency; |g(chi)|^2 = P (exact telescoping)")68for p in (13, 17, 53):69    # additive-character telescoping, purely combinatorial (no complex numbers):70    # sum_{t in F_p^x} psi(t c) = sum over exponents {t c mod p : t=1..p-1}.71    # c != 0 : the multiset is a permutation of {1,..,p-1}  => sum of all nonzero roots = -1.72    # c == 0 : every exponent 0                              => sum = (p-1).73    perm_ok = all(sorted((t*c) % p for t in range(1, p)) == list(range(1, p))74                  for c in range(1, p))75    zero_ok = all((t*0) % p == 0 for t in range(1, p))76    check(f"p={p}: {{t c mod p}} is a permutation of nonzero residues for every c!=0", perm_ok)77    # => |g(chi)|^2 = sum_u chi(u) [sum_t psi(t(u-1))] = (p-1)+(-1)(sum_{u!=1}chi(u))78    #              = (p-1) - (0 - 1) = p   for chi nontrivial (sum_u chi(u)=0).79    check(f"p={p}: hence |g(chi)|^2 = (p-1) - (0 - 1) = p = {p}", (p-1) - (0 - 1) == p and zero_ok)8081# ---------- P3: transverse turn is an exact self-inverse transform (NTT round-trip) ----------82print("P3  transverse (additive) turn: NTT round-trip exact over F_q (the classical-P turn)")83def ntt(a, w, q):84    n = len(a)85    return [sum(a[t]*pow(w, (k*t) % n, q) for t in range(n)) % q for k in range(n)]86q, n, w = 17, 8, 2          # 2 is a primitive 8th root of unity mod 17 (2^8=1, 2^4=-1)87check("2 is a primitive 8th root of unity mod 17", pow(w,n,q)==1 and pow(w,n//2,q)==q-1)88a = [3, 1, 4, 1, 5, 9, 2, 6]89A = ntt(a, w, q)90ninv = pow(n, q-2, q); winv = pow(w, q-2, q)91a_rt = [(ninv * sum(A[k]*pow(winv, (t*k) % n, q) for k in range(n))) % q for t in range(n)]92check("inverse-NTT(NTT(a)) = a exactly (transverse turn forward-computable, in P)",93      a_rt == [v % q for v in a])9495# P3 longitudinal underlying map exp:Z/(P-1)->F_P^x is a bijection; its inverse is dlog96print("P3  longitudinal turn underlies exp (bijection); forward inverse = dlog (classically hard)")97for p in (13, 17, 53):98    g = primroot(p)99    img = [pow(g, t, p) for t in range(p-1)]100    check(f"p={p}: exp t->g^t is a bijection Z/(P-1) -> F_P^x (image = all nonzero residues)",101          sorted(img) == list(range(1, p)))102103print("\n" + "="*68)104print(f"longitudinal_turn: {sum(PASS)}/{len(PASS)} checks pass "105      f"(finite-field/integer exact; one symbolic continuum-shadow)")106print("="*68)107assert all(PASS), "a check failed"108