Theorem 6.1 — Gaussian Toom–Cook- is well-defined and correct
OpenGaussToomCook.Supplement.theorem_6_1algebragaussian-integersinteger-multiplicationnumber-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1toom-cook
Let and let be a set of pairs that project onto distinct points of . Let , and parts with
let , and . Then the Gaussian Toom–Cook- scheme is well-defined and correct:
- the interpolation system of step (V),
whose matrix is the Vandermonde matrix , has exactly one solution , namely ; 2. the value returned in step (VI) is the product: .
This is the correctness statement underlying every Gaussian Toom–Cook- algorithm whose interpolation phase is analysed in §9 and §10.
Formalization Note is a family indexed by Fin (2k − 1) satisfying the published IsEvalPoints, and is the published vandMatrix. The system is solved over , with embedded by GaussianInt.toComplex.
Differences from the source:
- reading: "well-defined and correct" → the interpolation system of (V) has the coefficient vector of as its unique solution, and ; reason: this is what the paper's justification before the theorem (p. 13) establishes, and nothing else in the scheme can fail
- generalization: the system solved over → candidate solutions range over ; reason: the matrix remains invertible after the scalar extension , so the stronger uniqueness statement specializes to the source
- encoding: products in (IV) computed directly or recursively → exact products in ; reason: correctness depends only on the values computed, not on how
- encoding: the set of points → a family indexed by
Fin (2k − 1); reason: pairwise non-proportionality makes the indexing injective
Preamble
import Mathlib import Definitions.Def_GaussToomCook_IsEvalPoints import Definitions.Def_GaussToomCook_vandMatrix import Definitions.Def_GaussToomCook_Supplement_tcPoly
Formal statement
namespace GaussToomCook.Supplement
open MvPolynomial
/-- **Theorem 6.1** (Gaussian Toom–Cook is well-defined and correct), Spiizer, Steiner, *Rational and Gaussian long
integer multiplication*, manuscript (STOC 2027 submission; sha256 f50b5362…27ad70), §6, p. 13 (PDF 15):
"The Gaussian Toom–Cook integer multiplication scheme is well-defined and correct."
Let `k ≥ 1`, let `S` be `2k − 1` evaluation points (`IsEvalPoints`), `M ∈ ℤ_{>0}`, and `a = ∑ [a]_j M^j`,
`b = ∑ [b]_j M^j` with parts in `ℤ[i]` (7). With `P₁, P₂` as in (8) and `Q = P₁ · P₂`:
1. the interpolation system of step (V), `V(S) c = (P₁(x,y) · P₂(x,y))_{(x,y) ∈ S}`, has exactly one solution,
namely the coefficient vector `(q_0, …, q_{2k−2})` of `Q`;
2. the value returned in step (VI), `∑_j q_j M^j = Q(M, 1)`, equals `a · b`.
**Formalization Note.** The linear system is solved over `ℂ` (entries of `V(S)` and the right-hand side mapped
by `GaussianInt.toComplex`); uniqueness over `ℂ` implies uniqueness over `ℚ(i)`. The pointwise products of
step (IV) are modelled as exact products in `ℤ[i]` (the recursion is irrelevant to correctness). -/
theorem theorem_6_1 (k : ℕ) (hk : 0 < k) (S : Fin (2 * k - 1) → GaussianInt × GaussianInt)
(hS : GaussToomCook.IsEvalPoints k S) (M : ℤ) (hM : 0 < M) (a b : GaussianInt)
(A B : Fin k → GaussianInt) (ha : a = ∑ j : Fin k, A j * (M : GaussianInt) ^ (j : ℕ))
(hb : b = ∑ j : Fin k, B j * (M : GaussianInt) ^ (j : ℕ)) :
(∀ c : Fin (2 * k - 1) → ℂ,
(∀ r, ∑ j, GaussianInt.toComplex (GaussToomCook.vandMatrix k S r j) * c j =
GaussianInt.toComplex
(eval ![(S r).1, (S r).2] (tcPoly k A) * eval ![(S r).1, (S r).2] (tcPoly k B))) ↔
∀ j, c j = GaussianInt.toComplex (prodCoeff k A B j)) ∧
∑ j : Fin (2 * k - 1), prodCoeff k A B j * (M : GaussianInt) ^ (j : ℕ) = a * b := by sorry
end GaussToomCook.Supplement
Source
Y. Spiizer, R. S. Steiner, Rational and Gaussian long integer multiplication, manuscript (STOC 2027 submission; held version sha256 f50b53628a53a03bd55785424af241d0ac5ea751714330838e4017b90b27ad70), §6, Theorem 6.1, p. 13 (PDF p. 15); setting and steps (I)–(VI), p. 13 (PDF p. 15)