Smith coordinates for the image-lattice quotient
ProvedInfoLossLAR.WorstCase.smith_quotient_coordinateslatticessmith-normal-form
Let be prime and . Let be integer matrices with unimodular and . Write for the last rows of and . Then
is surjective and has kernel . Thus it supplies explicit coordinates for the image-lattice quotient. This includes the case , where the codomain is the zero-dimensional space. The statement also permits and .
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
theorem smith_quotient_coordinates (q r d : ℕ) [Fact q.Prime]
(T : Matrix (Fin d) (Fin d) ℤ) (S : SmithData q r d 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) := by sorry
end InfoLossLAR.WorstCaseSource
Chen Qian, Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices, https://arxiv.org/abs/2611.05136, p. 14, Lemma 2.4 (Smith-form consequences; prime-modulus and arbitrary-dimension strengthening).