Algorizk Labs research artifact for
Degree Filtration and Domain-Tower FFTs over M31 via the Boolean Zeta Transform and Kernel Polynomials Ali Mkhida — Algorizk Labs, Bordeaux, France
This repository publishes the paper, Rust/ARM64 implementation, experiment summaries, and reproducibility tooling supporting the M31 domain-tower transform.
- Title: Degree Filtration and Domain-Tower FFTs over M31 via the Boolean Zeta Transform and Kernel Polynomials
- Author: Ali Mkhida
- Affiliation: Algorizk Labs, Bordeaux, France
- ORCID: https://orcid.org/0009-0009-2101-9070
- Contact: ali.mkhida@algorizk.xyz
- Research page: https://www.algorizk.xyz/research/zeta-kernel-m31-fft
- PDF:
paper/Kernel-Q1-main.pdf - LaTeX source:
paper/Kernel-Q1-main.texand the section files inpaper/ - Frozen paper tag:
v1.0.2-paper-freeze-candidate
Boolean zeta transform · kernel polynomials · degree filtration · finite-field FFT · Mersenne-31 (M31) · Circle FFT · domain-tower FFT · polynomial evaluation · Rust · ARM64
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.
The paper attaches Boolean kernel coordinates to arbitrary monic degree-doubling polynomial coordinates. The kernel-to-product coordinate map is a complemented Boolean zeta transform, and the ordinary degree bound below 2^k becomes an explicit alternating-sign rule on the high-bit kernel coefficients.
For a quadratic tower, the same coordinates yield an O(N log N) recursive evaluator. Over M31, the exact rescaling s = 2c connects the quadratic map s -> s^2 - 2 to the one-variable map c -> 2c^2 - 1 used by recursive Circle-FFT stages. A norm-one-subgroup construction supplies the complete 29-level distinct-preimage tower used in the specialization.
paper/— complete LaTeX paper source and compiled PDF.implementation/kernel_vs_stwo.rs— optimized M31 kernel-transform implementation used in the correctness and benchmark path.experiments/— raw seven-round stability data plus stability, optimization, and stage-profile evidence.crates/repro/— Rust-first reproducibility CLI.reproducibility/— upstream source revision, benchmark boundary, host metadata when available, and SHA-256 manifest.figures/andtables/— publication artifacts when present in the canonical evidence repository.
| log2 N | N | Kernel median (ms) | Stwo median (ms) | Median kernel/Stwo |
|---|---|---|---|---|
| 18 | 262,144 | 1.536916 | 1.542792 | 0.996191 |
| 19 | 524,288 | 3.218542 | 3.307583 | 0.974495 |
| 20 | 1,048,576 | 6.924750 | 7.058000 | 0.979510 |
The stability study used seven independent rounds and nine timed repetitions per round at each reported size. At log2 N = 20, the observed per-round ratio range was 0.976630 .. 0.996149, with all seven rounds inside ±5%.
Across the tested sizes, the measurements show stable, similar transform-kernel running times on the recorded Apple ARM64 configuration. The benchmark boundary is documented in the paper and reproducibility metadata.
Inspect the repository:
cargo run -p kernel-q1-repro -- doctor
cargo run -p kernel-q1-repro -- show-resultsBuild the paper:
cargo run -p kernel-q1-repro -- paperPrepare the recorded Stwo checkout and run the exact-output check:
cargo run -p kernel-q1-repro -- prepare-stwo
cargo run -p kernel-q1-repro -- equivalenceRun a fresh benchmark invocation:
cargo run -p kernel-q1-repro -- benchmarkThe frozen publication numbers remain the archived values in experiments/; a fresh benchmark is not silently substituted for the publication dataset.
The production path was checked against the scalar reference for exact M31 output on 543 vectors: all tested vectors for log2 N = 2..8 plus deterministic vectors at 9, 10, 12, 14, 16, 18, 20.
Stwo is fetched from its upstream repository at the source revision recorded in reproducibility/. Upstream Stwo code is not vendored or relicensed by this repository.
- implementation source:
a3a5a14353bd038e5a1f2ccf44d42ca880f2f137040a40ff9851479541ba2c7c - stability summary:
2391777c4872def6ecb903b5666b5ec0b47b87fa6bff79249d366e073c201232 - optimization evidence:
b7adee0d10c1700fe1fbf578e6db5b36db5259f2c31512123edd7f376c1e4c44 - stage-profile evidence:
50ff6be15f58946119426b8eade012b456b8e0221cb6549caa99a2a5f5360427
Use the repository CITATION.cff metadata. Once an ePrint identifier is assigned, it can be added as the canonical archival paper URL without changing the frozen manuscript tag.
Original Algorizk software and reproducibility tooling are released under the MIT License. See LICENSE and LICENSES.md for the exact scope. The paper text is supplied for research and reproducibility and is not automatically relicensed as software.
The repository covers the Boolean-zeta/kernel coordinate theory, its degree filtration, the quadratic domain-tower evaluator, the M31/Circle-FFT rescaling, the recorded Rust/ARM64 implementation evidence, and the associated reproducibility material. Hardware realization and the Sumcheck–FRI connection are follow-on research directions described in the paper.
Ali Mkhida — Algorizk Labs ali.mkhida@algorizk.xyz https://www.algorizk.xyz ORCID: https://orcid.org/0009-0009-2101-9070