Theorem 10.1 — the division factor is divisible by
OpenGaussToomCook.Supplement.theorem_10_1Let and let be evaluation points of Gaussian Toom–Cook- (nonzero pairs in , pairwise non-proportional over ). The interpolation linear transformation of the algorithm is , the inverse of the evaluation map on homogeneous polynomials of degree in the monomial basis. Let be the division factor of : a nonzero Gaussian integer of minimal norm such that has Gaussian-integer entries for some . Let be a representative set of the Gaussian primes up to association. Then
Only primes with have a positive exponent, so the product is finite. The Lean statement asserts: for every finite set of pairwise non-associated Gaussian primes none of which divides , divides .
The theorem is the Gaussian analogue of the Nissim–Schwartz–Spiizer lower bound on the division factor of rational Toom–Cook algorithms; it shows that the denominators of every Gaussian Toom–Cook- interpolation grow with at every odd Gaussian prime of small norm.
Formalization Note is computed over from the published vandMatrix (it is invertible because the points are pairwise non-proportional). is the published norm, and the floor is natural-number division.
Differences from the source:
- reading: the division factor of the algorithm (§10, after [NSS25, Def. 2.4]: the least for which an equivalent algorithm with only divisions by powers of computes times the product) → the division factor (§2.2.3) of the interpolation matrix ; reason: §2.2.3 defines the division factor of a matrix, and the proof of Theorem 10.1 (p. 34) works with exactly the denominators of
- reading: "the Gaussian integer with minimal norm" → the nonzero Gaussian integer with minimal norm; reason: trivially clears every matrix, so minimality is meant among nonzero elements
- encoding: the product over a representative set with → for every finite set of pairwise non-associated primes not dividing , the product over it divides ; reason: only finitely many factors differ from , so taking the set of contributing representatives gives (102), and every such product divides (102)
- encoding: over → over ; reason: the inverse of a matrix over has entries in , and integrality of entries is tested through the embedding
import Mathlib import Definitions.Def_GaussToomCook_Nr import Definitions.Def_GaussToomCook_IsEvalPoints import Definitions.Def_GaussToomCook_vandMatrix import Definitions.Def_GaussToomCook_Supplement_IsDivisionFactor
namespace GaussToomCook.Supplement
/-- **Theorem 10.1** (lower bound on the division factor), Spiizer, Steiner, *Rational and Gaussian long integer
multiplication*, manuscript (STOC 2027 submission; sha256 f50b5362…27ad70), §10, p. 34 (PDF 36), eq. (102):
"Denote by `𝒫 ⊆ ℤ[i]` a representative set of all Gaussian primes up to association (multiplication by unit).
The division factor of any Gaussian Toom–Cook-k algorithm is divisible by
`∏_{p ∈ 𝒫, p ∤ 2} p^{⌊(2k−2)/(Nr(p)+1)⌋}`."
Let `k ≥ 1`, `S` be `2k − 1` evaluation points, and `α` a division factor (§2.2.3) of the interpolation matrix
`W^T = V(S)^{−1}`. Then for every finite set `P` of pairwise non-associated Gaussian primes none of which divides
`2`, `∏_{p ∈ P} p^{⌊(2k−2)/(Nr(p)+1)⌋}` divides `α`.
**Formalization Note.** `V(S)^{−1}` is computed over `ℂ` (`V(S)` is invertible because the points are pairwise
non-proportional). Only primes with `Nr(p) + 1 ≤ 2k − 2` have a positive exponent, so (102) is a finite product;
taking `P` to contain every such prime (one per association class) gives (102) for any representative set `𝒫`.
The floor is natural-number division. -/
theorem theorem_10_1 (k : ℕ) (hk : 0 < k) (S : Fin (2 * k - 1) → GaussianInt × GaussianInt)
(hS : GaussToomCook.IsEvalPoints k S) (α : GaussianInt)
(hα : IsDivisionFactor α ((GaussToomCook.vandMatrix k S).map GaussianInt.toComplex)⁻¹)
(P : Finset GaussianInt) (hPprime : ∀ p ∈ P, Prime p) (hP2 : ∀ p ∈ P, ¬ p ∣ 2)
(hPassoc : (P : Set GaussianInt).Pairwise fun p q => ¬ Associated p q) :
∏ p ∈ P, p ^ ((2 * k - 2) / (GaussToomCook.Nr p + 1)) ∣ α := by sorry
end GaussToomCook.Supplement