The Toom–Cook polynomials and the coefficients of
DefinitionGaussToomCook_Supplement_tcPolyalgebragaussian-integersinteger-multiplicationnumber-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1toom-cook
Let and let be a commutative ring ( in the rational-to-Gaussian reduction, in Gaussian Toom–Cook). From the parts of an input , step (II) of the algorithm forms the homogeneous polynomial of degree
so that .
For two such polynomials (parts of ) and (parts of ), the product is homogeneous of degree ; its coefficients are
These are the unknowns that the interpolation step of both schemes retrieves.
Formalization Note is a polynomial in two variables (MvPolynomial (Fin 2) R, with X 0 = X, X 1 = Y), and is read off with MvPolynomial.coeff from the actual product; no convolution formula is built in. The index runs over Fin (2k − 1).
Definition code
import Mathlib
namespace GaussToomCook.Supplement
open MvPolynomial
/-- **The Toom–Cook polynomials `P₁`, `P₂`**, Spiizer, Steiner, *Rational and Gaussian long integer multiplication*,
manuscript (STOC 2027 submission; sha256 f50b5362…27ad70), §3, eq. (2), p. 9 (PDF 11) and §6, eq. (8), p. 13 (PDF 15):
from the parts `[a]_0, …, [a]_{k−1}` of an input `a`, the homogeneous polynomial of degree `k − 1`
`P(X, Y) = ∑_{j=0}^{k−1} [a]_j X^j Y^{k−1−j}`.
**Formalization Note.** A polynomial in two variables over a commutative semiring `R` (`X 0 = X`, `X 1 = Y`);
the parts are a family `A : Fin k → R`. The paper uses `R = ℤ` (§3) and `R = ℤ[i]` (§6). -/
noncomputable def tcPoly {R : Type*} [CommSemiring R] (k : ℕ) (A : Fin k → R) :
MvPolynomial (Fin 2) R :=
∑ j : Fin k, monomial (Finsupp.single 0 (j : ℕ) + Finsupp.single 1 (k - 1 - j)) (A j)
/-- **The coefficients `q_0, …, q_{2k−2}` of `Q = P₁ · P₂`**, Spiizer, Steiner, *Rational and Gaussian long integer
multiplication*, manuscript (STOC 2027 submission; sha256 f50b5362…27ad70), §3 step (VI), p. 9 (PDF 11) and §6
step (V), p. 13 (PDF 15): `q_j` is the coefficient of the monomial `X^j Y^{2k−2−j}` in the product
`Q = P₁ · P₂`, `j = 0, …, 2k − 2`.
**Formalization Note.** Read off with `MvPolynomial.coeff` from the product `tcPoly k A * tcPoly k B`
(no convolution formula is built in). For `k ≥ 1`, `Q` is homogeneous of degree `2k − 2`, so these are all
of its coefficients. -/
noncomputable def prodCoeff {R : Type*} [CommSemiring R] (k : ℕ) (A B : Fin k → R)
(j : Fin (2 * k - 1)) : R :=
coeff (Finsupp.single 0 (j : ℕ) + Finsupp.single 1 (2 * k - 2 - j)) (tcPoly k A * tcPoly k B)
end GaussToomCook.Supplement
Source
Y. Spiizer, R. S. Steiner, Rational and Gaussian long integer multiplication, manuscript (STOC 2027 submission; held version sha256 f50b53628a53a03bd55785424af241d0ac5ea751714330838e4017b90b27ad70), §3, eq. (2) and step (VI), p. 9 (PDF p. 11); §6, eq. (8) and step (V), p. 13 (PDF p. 15)