Degree Filtration and Domain-Tower FFTs over M31 via the Boolean Zeta Transform and Kernel Polynomials

Abstract

We study Boolean kernel polynomials for degree-bounded univariate polynomials built from arbitrary monic coordinates of degrees 1, 2, 4, . . .. The coefficient map from the kernel polynomials to the associated degree-ordered product basis is a complemented Boolean zeta transform. Our main theorem gives an exact description of the ordinary degree bound deg U < 2^k directly in the full kernel coefficient array: after the low and high bits of the Boolean index are separated, the coefficients for fixed low bits follow an alternating-sign pattern determined by the high bits. Equivalently, the degree-< 2^k projector is a tensor product of local one-dimensional projectors. In characteristic two the signs disappear, so the coefficients are simply constant when the low bits are fixed and the high bits vary.

When the polynomial coordinates are generated by a quadratic map, the same representation gives an O(N log N) recursive transform on evaluation sets organized in pairs of preimages. Over the Mersenne prime p = 2^31 − 1, the rescaling s = 2c turns s ↦ s^2 − 2 exactly into the one-variable map c ↦ 2c^2 − 1 used by the recursive stages of Circle FFTs. A construction from the norm-one subgroup supplies 29 levels in which every point has two distinct preimages. The optimized Rust/ARM64 implementation agrees exactly with a scalar reference for the quadratic recursion on 543 test vectors. Seven-round measurements at N = 2^18, 2^19, 2^20 give transform-kernel running times in the same range as Stwo’s SIMD Circle FFT under the stated measurement boundary; at N = 2^20 the median per-round kernel/Stwo ratio is 0.979510.

Research contribution

The paper links Boolean zeta coordinates to a kernel-polynomial basis built from arbitrary monic degree-doubling coordinates. Ordinary degree below 2^k becomes an explicit alternating-sign rule on the high-bit kernel coefficients and an equivalent tensor product of local one-dimensional projectors.

For coordinates generated by a quadratic map, this structure yields an O(N log N) recursive evaluator. Over M31, the exact rescaling s = 2c connects s ↦ s² − 2 to the one-variable Circle-FFT recursion c ↦ 2c² − 1, with a 29-level paired-preimage domain tower.

Implementation evidence

The optimized Rust/ARM64 implementation agrees exactly with a scalar reference for the quadratic recursion on 543 test vectors. The stability experiment uses seven independent rounds and nine repetitions per round at each tested size.

Research artifacts

Public paper PDF, complete LaTeX source, Rust implementation, exact-output checks, benchmark evidence, experiment summaries, and reproducibility metadata are available in the repository.

GitHub repository · Paper PDF · Algorizk Labs