Lemma A.6, inequality (32) — rank of a polynomial matrix at versus its evaluations
ProvedLatticePrepro.card_mul_rank_eval_leLet be a finite field with elements, a field that is an -algebra (an extension of ), and . Let be natural numbers and an matrix over all of whose entries have degree at most . Write and () for the entrywise evaluations. Then
Equivalently, when : .
This is the Fancsali–Sziklai-type estimate (32) in the proof of Lemma A.6. Applied to the polynomial matrix of an evaluation table (Definition A.5), whose value at is the Hankel matrix of the moments and whose value at has rank at most the weight of column , it gives the weight bound used for soundness in Theorem A.8.
Formalization Note: The inequality is stated without natural-number subtraction. The paper bounds the rank of over and separately notes ; the Lean statement bounds directly, which is what the soundness argument needs. Ranks are Mathlib's Matrix.rank, and the matrix is indexed by Fin ℓ. The statement is generic and involves no evaluation tables.
import Mathlib open Polynomial Matrix
theorem LatticePrepro.card_mul_rank_eval_le {𝕊 : Type*} [Field 𝕊] [Fintype 𝕊] [DecidableEq 𝕊]
{K : Type*} [Field K] [Algebra 𝕊 K] (γ : K) {ℓ Δ : ℕ}
(H : Matrix (Fin ℓ) (Fin ℓ) 𝕊[X]) (hdeg : ∀ i j, (H i j).natDegree ≤ Δ) :
Fintype.card 𝕊 * (H.map (aeval γ)).rank ≤
(∑ s : 𝕊, (H.map (eval s)).rank) + Δ * (H.map (aeval γ)).rank := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.