Lemma 6.4 — , index , Smith form
ProvedInfoLossLAR.WorstCase.lemma_6_4latticesp2o-gran-per-chapterp2o-plan-bookp2o-v1smith-normal-form
Let be an odd prime, , and the matrix of Definition 6.3. Then
this lattice has index in , and the Smith normal form of is : there are unimodular with . Consequently is a rounding matrix with and (Definition 2.3).
Differences from the source:
- encoding: "index in " →
AddSubgroup.indexof equals ; reason: same notion - encoding: "the Smith normal form of is ; is a rounding matrix with , " →
IsRoundingMatrix q (d-1) d T(unimodular with ); reason: the two clauses say the same thing
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding import Definitions.Def_InfoLossLAR_WorstCase_FixedT set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 6.4 (Image lattice and Smith normal form), p. 27: for `q` an odd prime, `d ≥ q` and
`T` of Definition 6.3, `L(T) = {z ∈ ℤ^d : ∑_j z_j ≡ 0 (mod q)}`, this lattice has index `q` in
`ℤ^d`, and the Smith normal form of `T` is `diag(I_{d−1}, q)` (there are unimodular `U, V` with
`UTV = diag(I_{d−1}, q)`), so `T` is a rounding matrix with `r = d − 1`, `ℓ = 1`. -/
theorem lemma_6_4 (q d : ℕ) (hq : q.Prime) (hq2 : q ≠ 2) (hdq : q ≤ d) :
(∀ z : Fin d → ℤ, z ∈ imageLattice (TDef63 q d) ↔ (q : ℤ) ∣ ∑ j, z j) ∧
(imageLattice (TDef63 q d)).toAddSubgroup.index = q ∧
IsRoundingMatrix q (d - 1) d (TDef63 q d) := 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. 27, Lemma 6.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.