Lemma 3.5 — basic properties of LAR: quotient encoding, translation equivariance, balanced fibers
ProvedInfoLossLAR.WorstCase.lemma_3_5latticeslearning-with-roundingp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be an odd prime, , and a rounding matrix of modular rank with chosen Smith matrices, (the case included), , , and as in Definitions 3.1–3.4. Then:
Well-defined quotient encoding. For all , ; the map is onto with kernel , so it induces ; and for every and every integer lift of , .
Translation equivariance. The columns of are linearly independent over and span , and
Balanced fibers. For every , .
Differences from the source:
- encoding: " encodes the quotient output " → the isomorphism clause (surjective, kernel ) applied to ; reason: this is what "encodes" means
- encoding: " has full column rank over " → the columns of are linearly independent; reason: same notion
- encoding: odd prime , fixed Smith matrices, indices →
[Fact q.Prime],q ≠ 2,SmithData q r d T,Fin d; reason: Lean conventions
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 3.5 (Basic properties of LAR), p. 19, for a rounding matrix `T` of modular rank `r`
with chosen Smith matrices (`q` an odd prime, `d ≥ 1`, `ℓ = d − r`, `ℓ = 0` allowed):
well-defined quotient encoding (`AR_T(x + qz) = AR_T(x) + Tz`; `z ↦ Pz mod q` is onto `𝔽_q^ℓ`
with kernel `L(T)`; `f_T(x)` is the same for every integer lift of `x`), translation
equivariance (the columns of `J` are linearly independent over `𝔽_q` and span
`ker(T mod q)`; `f_T(x + Ja) = f_T(x) + a`), and balanced fibers (`|f_T^{-1}(y)| = q^r`). -/
theorem lemma_3_5 (q r d : ℕ) [Fact q.Prime] (hq2 : q ≠ 2) (hd : 1 ≤ d)
(T : Matrix (Fin d) (Fin d) ℤ) (S : SmithData q r d T) :
(∀ x z : Fin d → ℤ, AR q T (x + (q : ℤ) • z) = AR q T x + T.mulVec z) ∧
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) ∧
(∀ (x : Fin d → ZMod q) (y : Fin d → ℤ), modq q y = x →
modq q (S.P.mulVec (AR q T y)) = S.fT x) ∧
LinearIndependent (ZMod q) (fun j : Fin (d - r) => fun i : Fin d => S.J i j) ∧
Submodule.span (ZMod q) (Set.range fun j : Fin (d - r) => fun i : Fin d => S.J i j) =
LinearMap.ker (Matrix.mulVecLin (matModq q T)) ∧
(∀ (x : Fin d → ZMod q) (a : Fin (d - r) → ZMod q), S.fT (x + S.J.mulVec a) = S.fT x + a) ∧
(∀ y : Fin (d - r) → ZMod q,
(Finset.univ.filter fun x : Fin d → ZMod q => S.fT x = y).card = q ^ 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. 19, Lemma 3.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.