φ-NTT: An Exact Integer Transform with a Built-In Wavelet Structure
A summary of "φ-NTT: A Carry-Free Transform on Z₁₀^B with Hierarchical Wavelet Structure"
The FFT is everywhere — audio, imaging, communications, compression. But it has a silent cost: every computation passes through complex floating-point arithmetic, accumulating rounding errors that are impossible to eliminate entirely.
φ-NTT takes a different path. It is a signal transform where every operation stays in exact integers, from start to finish. No approximations. No rounding. Lossless reconstruction is not a goal — it is a structural guarantee.
The Core Idea: Carry-Free Arithmetic
In ordinary arithmetic, digits interact. Add 19 + 1 and you get a carry: the ones digit resets, the tens digit increments. This cross-digit coupling is exactly what makes standard modular convolution hard to diagonalize cleanly at scale.
φ-NTT lives in a different world. It operates on the carry-free group Z₁₀^B — the B-fold direct product of Z₁₀ — where each decimal digit evolves independently under mod-10 arithmetic:
carry-free addition: (n ⊕ m)ᵢ = (dᵢ(n) + dᵢ(m)) mod 10
No carry ever crosses a digit boundary. This is not a restriction — it is the structure that makes everything work. Because digits are independent, the transform can be built as a clean B-stage tensor product, with zero inter-stage twiddle factors at any depth.
The Coefficient Ring: Z[φ]
All arithmetic runs over Z[φ] = Z[√5], the golden-ratio integer ring. Elements are integer pairs (a, b) representing a + b·φ, where φ = (1+√5)/2. Multiplication is:
(a, b) · (c, d) = (ac + bd, ad + bc + bd)
Three coefficient values cover the entire C₅-twisted DFT basis: (2,0), (-1,1), (0,-1). No irrational numbers appear at runtime. Every intermediate value is an exact integer pair.
A 2^B Channel Filterbank
Transforming a length-10^B signal produces 2^B output channels, each labeled by a string of T's and U's of length B (e.g., for B=3: TTT, TUT, UUU, …).
- T at digit b — low-pass projection: extracts the slowly-varying component of the signal across digit position b (C₅-twisted DFT side)
-
U at digit b — high-pass projection: extracts the parity alternation
(-1)^{d_b}at digit b (Z₂ side)
The B-stage tensor product applies these operators independently at each digit, giving a complete decomposition. Exact reconstruction is guaranteed by the inverse transform, with scale factors 40^B (round-trip) or 80^B (after convolution) that divide exactly in Z[φ] — verified by assertion for B = 1..5.
It Looks Like a Wavelet Transform
The channel label set {T, U}^B maps naturally onto the leaves of a complete binary tree of depth B:
root
/ \
T(d₂) U(d₂)
/ \ / \
T(d₁) U(d₁) T(d₁) U(d₁)
/ \ / \ / \ / \
T U T U T U T U
(d₀) (d₀) (d₀) (d₀)
The channel TT…T (leftmost leaf) captures the coarsest approximation. The channel UU…U (rightmost) captures the finest detail — the checkerboard pattern across all digits simultaneously.
This structure is directly analogous to Haar multiresolution analysis (MRA), with T playing the role of the scaling function and U the wavelet. The differences are significant but structural:
| Property | Haar MRA | φ-NTT |
|---|---|---|
| Signal length | 2^B | 10^B |
| Channels | 2^B | 2^B |
| Approximation | scaling function | TT…T channel |
| Detail | wavelet coeff. | T…TU_bT…T channels |
| Arithmetic | real (±1 basis) | Z[φ] integer ring |
| Orthogonality | exact | conjectured (open problem) |
Where Does the Energy Go?
For a low-frequency test signal sin(2πn/100) (period 100 ≈ 2·10¹), energy concentrates sharply in just a few channels:
| B | Top channel | Energy | Top-3 combined | UU…U |
|---|---|---|---|---|
| 3 | TUT | 86.4% | 99.8% | < 0.01% |
| 4 | TUTT | 68.7% | 98.1% | < 0.01% |
| 5 | TUTTT | 68.2% | 97.6% | < 0.01% |
Why TUT…T? A period-100 signal is dominated by variation in the tens digit d₁. The U operator at stage b=1 extracts exactly that: the parity alternation (-1)^{d₁}. Other digit positions vary slowly, so T suffices there. The result is a digit-frequency correspondence: signals with period ≈ 2·10^b concentrate in the channel with U only at position b.
This is formalized as the Spectral Concentration Quasi-Theorem:
For a signal with dominant period P ≈ 2·10^b, under digit-wise smoothness assumptions, the energy fraction captured by the level-b detail channel satisfies:
α_b ≥ C · (1 − ε)^{B−1}
Empirically: top-3 channels cover ≥ 97% of total energy for B = 3..5.
The bound decays exponentially in B — not a defect, but a reflection of the fact that more digit stages means more channels competing for energy. The top-3 coverage stays stable because the nearest neighbor channels (at levels b±1) absorb most of the leakage.
What the Convolution Theorem Gives You
Just as FFT diagonalizes cyclic convolution on Z/(N), φ-NTT diagonalizes carry-free convolution on Z₁₀^B:
(x ⋆ h)[n] = Σ_m h[m] · x[cf_sub(n, m)]
In the channel domain, this becomes a pointwise product with a simple T/U cross-coupling rule per stage:
2·Y_T[k] = X_T[k]·H_T[k] − SIN2 · X_U[k]·H_U[k]
2·Y_U[k] = X_T[k]·H_U[k] + X_U[k]·H_T[k]
where SIN2 = (3,−1) ∈ Z[φ] ≈ 1.382 = 4sin²(2π/10). Verified for B = 1..5 against direct O(N²) computation. Carry-free cross-correlation reduces to convolution with the carry-free-reversed kernel h_rev[m] = h[cf_neg(m)].
Open Problems
Three things remain unproved or unresolved:
T/U orthogonality (P1) — numerical evidence is clear (energy partitions cleanly, reconstruction is exact), but the algebraic proof of T_b ⊥ U_b over Z[φ] is open. Proving this would upgrade the quasi-theorem to a full theorem.
Closed forms for C and ε (P2) — the spectral concentration constants are currently back-derived from observations. Explicit expressions in terms of P, base 10, and Z[φ] basis would make the bound signal-class independent.
Bridging to carry-based convolution (P3) — φ-NTT handles carry-free signals natively. Connecting it to ordinary integer sequences via overlap-add requires handling the non-isomorphism Z₁₀^B ≇ Z/(10^B)Z for B ≥ 2.
How It Compares
vs. FFT — FFT diagonalizes cyclic convolution on Z/(N) with complex floating-point twiddles. φ-NTT diagonalizes a different algebra (carry-free convolution on Z₁₀^B) with exact integer coefficients. The two are not interchangeable — they solve different problems.
vs. NTT (Number Theoretic Transform) — classical NTT swaps complex roots of unity for modular roots, but keeps the cyclic group Z/(N). φ-NTT uses the direct product group Z₁₀^B and the ring Zφ, trading the standard group structure for twiddle-free recursion and exact arithmetic.
vs. Haar wavelets — the binary tree structure and T/U split are genuinely analogous to Haar MRA. But Haar lives over ℝ with ±1 basis on Z/(2^B)Z; φ-NTT lives over Z[φ] on Z₁₀^B. Whether a precise isomorphism exists is an open question.
Try the Minimal Test
The reference implementation phi_carry_free.py is self-contained pure Python. The 30-second sanity check:
from phi_carry_free import phi_conv_carry_free
from random import seed, randint
seed(42)
B, N = 3, 1000
x = [(randint(-5, 5), randint(-1, 1)) for _ in range(N)]
h = [(0, 0)] * N
h[0] = (1, 0) # delta kernel
y = phi_conv_carry_free(x, h, B)
print("delta conv B=3:", "✓" if all(y[i] == x[i] for i in range(N)) else "✗")
If it prints ✓, the transform is working correctly. The convolution theorem, scale factor divisibility, and exact reconstruction are all confirmed in that one check.
Source: Handoff notes v2–v12 (2026-02-25) / Reference implementation: phi_carry_free.py
Top comments (0)