Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.4 — modular rank and image lattice of a rounding matrix

Proved
InfoLossLAR.WorstCase.lemma_2_4

by Shuze Chen · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

latticesp2o-gran-per-chapterp2o-plan-bookp2o-v1smith-normal-form

Let qqq be an odd prime, d≥1d\ge1d≥1, and T∈Zd×dT\in\mathbb Z^{d\times d}T∈Zd×d a rounding matrix of modular rank rrr, with unimodular U,VU,VU,V such that UTV=diag⁡(Ir,qIℓ)UTV=\operatorname{diag}(I_r,qI_\ell)UTV=diag(Ir​,qIℓ​), ℓ=d−r\ell=d-rℓ=d−r, and P=E⊤UP=E^\top UP=E⊤U (the last ℓ\ellℓ rows of UUU). Then

rank⁡Fq(T mod q)=r,dim⁡Fqker⁡(T mod q)=ℓ,∣det⁡T∣=qℓ,\operatorname{rank}_{\mathbb F_q}(T\bmod q)=r,\qquad \dim_{\mathbb F_q}\ker(T\bmod q)=\ell,\qquad |\det T|=q^\ell,rankFq​​(Tmodq)=r,dimFq​​ker(Tmodq)=ℓ,∣detT∣=qℓ,

qZd⊆L(T)q\mathbb Z^d\subseteq\mathcal L(T)qZd⊆L(T), the map z↦Pz mod qz\mapsto Pz\bmod qz↦Pzmodq from Zd\mathbb Z^dZd to Fqℓ\mathbb F_q^\ellFqℓ​ is onto with kernel exactly L(T)\mathcal L(T)L(T) (so it induces Zd/L(T)≅Fqℓ\mathbb Z^d/\mathcal L(T)\cong\mathbb F_q^\ellZd/L(T)≅Fqℓ​), the quotient Zd/L(T)\mathbb Z^d/\mathcal L(T)Zd/L(T) has qℓq^\ellqℓ elements, and it is nontrivial exactly when ℓ≥1\ell\ge1ℓ≥1.

The lemma identifies the output space of algebraic rounding: rounded outputs are read modulo L(T)\mathcal L(T)L(T), a group of size qℓq^\ellqℓ with explicit coordinates.

Differences from the source:

  • encoding: L(T)⊆Zd\mathcal L(T)\subseteq\mathbb Z^dL(T)⊆Zd → holds by construction (L(T)\mathcal L(T)L(T) is a Z\mathbb ZZ-submodule of Zd\mathbb Z^dZd); reason: not a separate clause in Lean
  • encoding: Zd/L(T)≅Fqℓ\mathbb Z^d/\mathcal L(T)\cong\mathbb F_q^\ellZd/L(T)≅Fqℓ​ via the last ℓ\ellℓ coordinates of UzUzUz mod qqq → z↦Pz mod qz\mapsto Pz\bmod qz↦Pzmodq is surjective with kernel L(T)\mathcal L(T)L(T); reason: exactly the statement that the induced map is an isomorphism
  • encoding: odd prime qqq, fixed Smith matrices, indices 1..d1..d1..d → [Fact q.Prime], q ≠ 2, SmithData q r d T, Fin d and ℓ=d−r\ell=d-rℓ=d−r; 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
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me