Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9.9 — the fixed family admits fixed-order Gaussian T-AFTs with accuracy CRqL−(R+1)/4+neglR(L)+ϵnumC_RqL^{-(R+1)/4}+\mathrm{negl}_R(L)+\epsilon_{\mathrm{num}}CR​qL−(R+1)/4+neglR​(L)+ϵnum​

Proved
InfoLossLAR.WorstCase.theorem_9_9

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

discrete-gaussianlatticeslearning-with-roundingp2o-gran-per-chapterp2o-plan-bookp2o-v1

Consider the family of §9.9: L=λ+2L=\lambda+2L=λ+2, N=λN=\lambdaN=λ, σ=L\sigma=Lσ=L, qqq the least prime ≥216L64\ge2^{16}L^{64}≥216L64, d=qL96+2L128d=qL^{96}+2L^{128}d=qL96+2L128, and TTT, P=1⊤P=\mathbf 1^\topP=1⊤ of Definition 6.3. For every calibration order RRR there are a constant CR>0C_R>0CR​>0 and a nonnegative negligible function neglR\mathrm{negl}_RneglR​, both depending only on RRR, such that for every integer c≥1c\ge1c≥1 with R≥4c+267R\ge4c+267R≥4c+267 and every numerical budget ϵnum=14L−(e+2)\epsilon_{\mathrm{num}}=\frac14L^{-(e+2)}ϵnum​=41​L−(e+2) with an integer e≥ce\ge ce≥c (so ϵnum≤14L−(c+2)\epsilon_{\mathrm{num}}\le\frac14L^{-(c+2)}ϵnum​≤41​L−(c+2)), there is a uniform PPT sampler Samplec(1λ,pp)→(Q,β)∈Zd×d×Zd\mathrm{Sample}_c(1^\lambda,\mathrm{pp})\to(Q,\beta)\in\mathbb Z^{d\times d}\times\mathbb Z^dSamplec​(1λ,pp)→(Q,β)∈Zd×d×Zd whose every execution returns Q mod q∈GLd(Fq)Q\bmod q\in\mathrm{GL}_d(\mathbb F_q)Qmodq∈GLd​(Fq​), such that for all sufficiently large λ\lambdaλ, with e←DZd,σe\leftarrow D_{\mathbb Z^d,\sigma}e←DZd,σ​ independent,

Δ(L(Qe+β mod q),U(FT,0))≤CR q L−(R+1)/4+neglR(L)+ϵnum,\Delta\big(\mathcal L(Qe+\beta\bmod q),U(\mathcal F_{T,0})\big)\le C_R\,q\,L^{-(R+1)/4}+\mathrm{negl}_R(L)+\epsilon_{\mathrm{num}},Δ(L(Qe+βmodq),U(FT,0​))≤CR​qL−(R+1)/4+neglR​(L)+ϵnum​,

and which satisfies Definition 5.3: the same distance is at most λ−c\lambda^{-c}λ−c for all sufficiently large λ\lambdaλ.

Differences from the source:

  • reading: "for the fixed calibration order RRR chosen above" (R≥4c+267R\ge4c+267R≥4c+267, §9.10) and the constants CRC_RCR​, neglR\mathrm{negl}_RneglR​ → for every RRR, constants depending only on RRR, valid for every c≥1c\ge1c≥1 with R≥4c+267R\ge4c+267R≥4c+267; reason: the subscript RRR and Proposition 9.6 fix them by RRR alone
  • reading: "ϵnum≤14L−(c+2)\epsilon_{\mathrm{num}}\le\frac14L^{-(c+2)}ϵnum​≤41​L−(c+2)" (§9.10) → every budget 14L−(e+2)\frac14L^{-(e+2)}41​L−(e+2) with integer e≥ce\ge ce≥c; reason: §9.10 chooses one budget below ¼L^{−(c+2)} without pinning it; e = c is the printed bound ¼L^{−(c+2)} itself, and every smaller inverse power of L is covered as well, so the statement contains the source's choice
  • reading: "uniform PPT sampler" → IsPPTAffineSampler: one classical polynomial-time map from (coins, code of (1λ,pp)(1^\lambda,\mathrm{pp})(1λ,pp)) to the code of (Q,β)(Q,\beta)(Q,β), with polynomially many coins; reason: the paper names no model; reading only 1λ1^\lambda1λ, pp and coins is the source independence
  • encoding: e←DZd,σe\leftarrow D_{\mathbb Z^d,\sigma}e←DZd,σ​ and Qe+β mod qQe+\beta\bmod qQe+βmodq → e←χG=DZd,σ mod qe\leftarrow\chi_G=D_{\mathbb Z^d,\sigma}\bmod qe←χG​=DZd,σ​modq and Qe+βQe+\betaQe+β over Fq\mathbb F_qFq​; reason: the same law, as Q,βQ,\betaQ,β are integral
  • encoding: the label in Fq\mathbb F_qFq​ → a vector of Fq1\mathbb F_q^1Fq1​; reason: ℓ=1\ell=1ℓ=1
Preamble
import Mathlib
import Definitions.Def_InfoLossLAR_WorstCase_QPT
import Definitions.Def_InfoLossLAR_WorstCase_Rounding
import Definitions.Def_InfoLossLAR_WorstCase_Laws
import Definitions.Def_InfoLossLAR_WorstCase_Family

set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase

/-- Theorem 9.9 (Constructive fixed-order Gaussian AFT), p. 59, for the fixed family of §9.9
(`L = λ + 2`, `N = λ`, `σ = L`, `q` the least prime `≥ 2^{16} L^{64}`,
`d = qL^{96} + 2L^{128}`, `T` and `P = 1ᵀ` of Definition 6.3). For every calibration order `R`
there are a constant `C_R > 0` and a nonnegative negligible function `negl_R` such that for every
integer `c ≥ 1` with `R ≥ 4c + 267` (§9.10) and every numerical budget
`ε_num = (1/4) L^{−(e+2)}` with an integer `e ≥ c` (so `ε_num ≤ (1/4) L^{−(c+2)}`, §9.10) there is
a uniform classical PPT sampler
`Sample_c(1^λ, pp) → (Q, β) ∈ ℤ^{d×d} × ℤ^d` whose every output has `Q mod q ∈ GL_d(𝔽_q)`, such
that for all sufficiently large `λ`, with `x ← D_{ℤ^d,σ}` independent,
`Δ(L(Qx + β mod q), U(F_{T,0})) ≤ C_R q L^{−(R+1)/4} + negl_R(L) + ε_num`,
and which satisfies Definition 5.3: this distance is at most `λ^{−c}` for all large `λ`. -/
theorem theorem_9_9 (R : ℕ) :
    ∃ C_R : ℝ, 0 < C_R ∧ ∃ negl_R : ℕ → ℝ, Negligible negl_R ∧
      ∀ c : ℕ, 1 ≤ c → 4 * c + 267 ≤ R → ∀ e : ℕ, c ≤ e →
        ∃ (m : Polynomial ℕ)
          (S : (lam : ℕ) → (Fin (m.eval lam) → Bool) →
            Matrix (Fin (famd lam)) (Fin (famd lam)) ℤ × (Fin (famd lam) → ℤ)),
          IsPPTAffineSampler famInput famd m S ∧
          (∀ (lam : ℕ) (ρ : Fin (m.eval lam) → Bool), IsUnit (matModq (famq lam) (S lam ρ).1).det) ∧
          (∃ lam₀ : ℕ, ∀ lam ≥ lam₀,
            sdist (transportLaw (S lam) (chiG (famq lam) (famd lam) (famσ lam)))
                (unifZeroFiber (famLabel lam)) ≤
              C_R * (famq lam : ℝ) * (famL lam : ℝ) ^ (-((R : ℝ) + 1) / 4) +
                negl_R (famL lam) + (1 / 4) * (famL lam : ℝ) ^ (-((e : ℝ) + 2))) ∧
          (∃ lam₀ : ℕ, ∀ lam ≥ lam₀,
            sdist (transportLaw (S lam) (chiG (famq lam) (famd lam) (famσ lam)))
                (unifZeroFiber (famLabel lam)) ≤ (lam : ℝ) ^ (-(c : ℝ))) := 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. 58 §§9.9–9.10, p. 59, Theorem 9.9
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