Lemma 2.4 — modular rank and image lattice of a rounding matrix
ProvedInfoLossLAR.WorstCase.lemma_2_4latticesp2o-gran-per-chapterp2o-plan-bookp2o-v1smith-normal-form
Let be an odd prime, , and a rounding matrix of modular rank , with unimodular such that , , and (the last rows of ). Then
, the map from to is onto with kernel exactly (so it induces ), the quotient has elements, and it is nontrivial exactly when .
The lemma identifies the output space of algebraic rounding: rounded outputs are read modulo , a group of size with explicit coordinates.
Differences from the source:
- encoding: → holds by construction ( is a -submodule of ); reason: not a separate clause in Lean
- encoding: via the last coordinates of mod → is surjective with kernel ; reason: exactly the statement that the induced map is an isomorphism
- encoding: odd prime , fixed Smith matrices, indices →
[Fact q.Prime],q ≠ 2,SmithData q r d T,Fin dand ; reason: Lean conventions, same instances
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 2.4 (Modular rank and image lattice), p. 14: for a rounding matrix `T` of modular rank
`r` with chosen Smith matrices `U, V` (`UTV = diag(I_r, qI_ℓ)`, `ℓ = d − r`, `q` an odd prime, `d ≥ 1`),
`rank_{𝔽_q}(T mod q) = r`, `dim ker(T mod q) = ℓ`, `|det T| = q^ℓ`, `qℤ^d ⊆ L(T)`, the map
`z ↦ (last ℓ coordinates of Uz) mod q` is onto `𝔽_q^ℓ` with kernel `L(T)` (so it induces
`ℤ^d/L(T) ≅ 𝔽_q^ℓ`), the quotient has `q^ℓ` elements, and it is nontrivial iff `ℓ ≥ 1`. -/
theorem lemma_2_4 (q r d : ℕ) [Fact q.Prime] (hq2 : q ≠ 2) (hd : 1 ≤ d)
(T : Matrix (Fin d) (Fin d) ℤ) (S : SmithData q r d T) :
(matModq q T).rank = r ∧
Module.finrank (ZMod q) (LinearMap.ker (Matrix.mulVecLin (matModq q T))) = d - r ∧
|T.det| = (q : ℤ) ^ (d - r) ∧
(∀ z : Fin d → ℤ, (q : ℤ) • z ∈ imageLattice T) ∧
Function.Surjective (fun z : Fin d → ℤ => modq q (S.P.mulVec z)) ∧
(∀ z : Fin d → ℤ, modq q (S.P.mulVec z) = 0 ↔ z ∈ imageLattice T) ∧
Nat.card ((Fin d → ℤ) ⧸ imageLattice T) = q ^ (d - r) ∧
(Nontrivial ((Fin d → ℤ) ⧸ imageLattice T) ↔ 1 ≤ d - r) := by sorry
end InfoLossLAR.WorstCase
Source
Chen Qian, Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices, arXiv:2611.05136 (held version, sha256 2ebdfbf3…), p. 14, Lemma 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.