Repository navigation
feat(AdditiveNTT): the additive NTT over a coset, and its inverse - #405
Conversation
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
🤖 PR SummaryMathematical FormalizationThis PR formalizes the additive NTT over an arbitrary coset Core definitions and theorems in
Bridge file
Refactoring
Documentation
Notes
Statistics
Lean Declarations ✏️ Added: 84 declaration(s)
📄 **Per-File Summaries**
Specifically, it proves:
Last updated: 2026-10-27 12:46 UTC. |
dhsorens
left a comment
There was a problem hiding this comment.
Thanks for this. It's a substantial piece of work, and it's nice to see the coset transform and its inverse proved over any field of characteristic 2, with no Fintype.
Before going through it line by line, I'd like to settle a design question. This file sits next to the existing additive-NTT development in the same directory, but it builds its own point, vanishing, normalized, novel and ntt from scratch against Mathlib alone. NovelPolynomialBasis.lean already defines the subspace polynomial W, its normalisation normalizedW and the novel basis Xⱼ. As it stands we'd have two parallel formalisations of the same objects that know nothing about each other, and a reader can't tell which one to use or whether they agree.
I'd like this PR to either:
- reuse the existing definitions where they fit, or
- if this point-indexed,
ℕ → Fpresentation is genuinely the better one to prove the coset results in (which may well be true), add a bridge showing thatvanishing/normalized/novelagree withW/normalizedW/Xⱼon the existing domain, and thatntt β l 0agrees with the current transform. That ties the new results to the code people already use.
I'd also like to hear what you have in mind downstream (Plonky3's binary-dft?), since that affects which way round the bridge should go.
Smaller points are inline.
Note that CI hasn't run on this yet: workflows on a first PR need a maintainer to approve them.
| def point (β : ℕ → F) (m : ℕ) : F := ∑ r ∈ range m, if m.testBit r then β r else 0 | ||
|
|
||
| /-- The subspace polynomial W_i: the product of x - s over the 2^i points s of S_i. -/ | ||
| def vanishing (β : ℕ → F) (i : ℕ) (x : F) : F := ∏ m ∈ range (2 ^ i), (x - point β m) |
There was a problem hiding this comment.
This is the design question from my review: vanishing, normalized and novel duplicate W, normalizedW and Xⱼ in NovelPolynomialBasis.lean. Please either reuse those, or prove that these agree with them on the existing domain.
| ∑ k ∈ range (2 ^ l), novel β l k x • d k | ||
|
|
||
| /-- The additive NTT over shift + S_l: entry i is sum_k d_k X_k at shift + point(i). -/ | ||
| def ntt (β : ℕ → F) (l : ℕ) (shift : F) (d : ℕ → V) : ℕ → V := |
There was a problem hiding this comment.
Likewise, if the bridge goes this way round, I'd like a lemma that ntt β l 0 agrees with the existing transform, so the coset results connect to the code people already use.
| public import Mathlib.Algebra.Module.BigOperators | ||
| public import Mathlib.Data.Nat.Bitwise | ||
| public import Mathlib.Logic.Function.Iterate | ||
| public import Mathlib.Tactic.LinearCombination |
There was a problem hiding this comment.
If LinearCombination, Module and Linarith are only used inside proofs, a plain (non-public) import keeps them out of downstream files.
| open Finset | ||
|
|
||
| variable {F : Type _} [Field F] {V : Type _} [AddCommGroup V] [Module F V] | ||
|
|
There was a problem hiding this comment.
Nit: there's a run of blank lines here.
|
|
||
| /-! ## Points -/ | ||
|
|
||
| theorem testBit_of_lt {m r n : ℕ} (hm : m < 2 ^ n) (hr : n ≤ r) : m.testBit r = false := |
There was a problem hiding this comment.
This follows from core's Nat.testBit_lt_two_pow plus a monotonicity step. Please use that directly, or at least make this private.
| Nat.testBit_eq_false_of_lt (lt_of_lt_of_le hm (Nat.pow_le_pow_right two_pos hr)) | ||
|
|
||
| /-- The sum over the bits of m below a bound stops changing once the bound covers m. -/ | ||
| theorem sum_bits_eq {M : Type _} [AddCommMonoid M] (f : ℕ → M) {m a b : ℕ} (hab : a ≤ b) |
There was a problem hiding this comment.
Generic Nat/Finset helpers like this one (and partner_lt, partner_up, partner_down) would become public API under AdditiveNTT.Coset. Please make them private.
|
|
||
| /-! ## Row arithmetic of one stage -/ | ||
|
|
||
| theorem two_pow_succ' (j : ℕ) : 2 ^ (j + 1) = 2 ^ j + 2 ^ j := by rw [pow_succ]; ring |
There was a problem hiding this comment.
This is core's Nat.two_pow_succ (2 ^ (n + 1) = 2 ^ n + 2 ^ n). Please use that instead.
…ctic imports in Coset Replace two_pow_succ' with Nat.two_pow_succ and testBit_of_lt with Nat.testBit_lt_two_pow, make the generic Nat helpers private, import the proof-only tactics without public, and drop the runs of blank lines. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
…nd additiveNTT The point-indexed vanishing, normalized and novel evaluate the existing polynomials W, normalizedW and Xⱼ, for any natural-number basis that agrees with the Fin r basis. With beta_0 = 1, additiveNTT is ntt with zero shift, and the inverse network recovers the coefficients from its output. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
|
Thanks for the careful read!
|
The additive NTT here follows Diamond and Posen.
It runs one transform over the subspace S_l, tiled for the rate.
Implementations such as Plonky3's binary-dft also transform over a coset shift + S_l, and invert.
This adds that transform, from Lin, Chung and Han (FOCS 2014).
Results
Scope
Everything holds over any field of characteristic 2 and any basis.
No
Fintypeis needed.The domain may be the whole field, which
ℓ + R_rate < rexcludes today.The file imports only Mathlib.
🤖 Generated with Claude Code