Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite centered grid: exact mean power and Gaussian tail

Open
QAlgorithms.Papers.Independent.Intakenext100.P08.classicalGrid_gaussianTail

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let d≥2d\ge2d≥2 be an integer, t>0t>0t>0, and v>0v>0v>0. Use symbols xj=(2j−d+1)tx_j=(2j-d+1)txj​=(2j−d+1)t, 0≤j<d0\le j<d0≤j<d, and the nearest-symbol decoder. Their exact uniform mean power and conditional symbol errors pjp_jpj​ under additive noise ξ∼N(0,v)\xi\sim N(0,v)ξ∼N(0,v) satisfy

1d∑j=0d−1xj2=d2−13t2,pj≤erfc⁡(t2v).\frac1d\sum_{j=0}^{d-1}x_j^2=\frac{d^2-1}{3}t^2,\qquad p_j\le\operatorname{erfc}\left(\frac{t}{\sqrt{2v}}\right).d1​j=0∑d−1​xj2​=3d2−1​t2,pj​≤erfc(2v​t​).

In particular, for any P>0P>0P>0, the choice tP=3P/dt_P=\sqrt{3P}/dtP​=3P​/d gives mean power at most PPP and

pj≤erfc⁡(3P2d2v).p_j\le\operatorname{erfc}\left(\sqrt{\frac{3P}{2d^2v}}\right).pj​≤erfc(2d2v3P​​).

This retains the source's conservative spacing while replacing its explicitly approximate integral power calculation with the exact finite sum. Uniform mean-symbol power alone does not enforce a power bound for every outer-code word.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P08
Formal statement
namespace QAlgorithms.Papers.Independent.Intakenext100.P08

open MeasureTheory ProbabilityTheory Matrix

open scoped BigOperators ENNReal

-- Accepted grouped index and source-sign matrix; no paper-local copies.

open QAlgorithms.Papers.Independent.Dependency50.P10 (Phase sigma)
-- The accepted predicate uses column bases and -sigma: apply it to S.transpose.

open QAlgorithms.Papers.Independent.Frontier30.P02 (IsSymplectic)
-- The accepted pairing has the opposite sign: exchange its two arguments below.

open QAlgorithms.Papers.Independent.Frontier30.P10 (symplecticPair)

/-- PDF p.10, (90)–(92): finite centered-grid power and nearest-decoding tail.
Printed/changed/why: (90) is explicitly an integral approximation; the finite
alphabet has exact power (d^2-1)t^2/3. The source's t=sqrt(3P)/d therefore
satisfies the conservative mean-symbol power inequality. No assertion is made
that every outer-code word meets the block-power constraint. -/
theorem classicalGrid_gaussianTail (d : ℕ) [NeZero d] (hd : 2 ≤ d)
    (v : NNReal) (hv : 0 < v) (t : ℝ) (ht : 0 < t) :
    gridMeanPower d t = ((d : ℝ) ^ 2 - 1) * t ^ 2 / 3 ∧
    (∀ y : ℝ, ∀ j : Fin d,
      |y - gridSymbol d t (gridDecode d t y)| ≤ |y - gridSymbol d t j|) ∧
    (∀ j : Fin d, gridSymbolError d t v j ≤
      complementaryErrorFunction (t / Real.sqrt (2 * (v : ℝ)))) ∧
    (∀ P : ℝ, 0 < P →
      let spacing := Real.sqrt (3 * P) / (d : ℝ)
      gridMeanPower d spacing ≤ P ∧
      ∀ j : Fin d, gridSymbolError d spacing v j ≤
        complementaryErrorFunction (Real.sqrt (3 * P / (2 * (d : ℝ) ^ 2 * (v : ℝ))))) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P08
Source
Achievable rates for the Gaussian quantum channel, arXiv:quant-ph/0105058v1, PDF p. 10, §VII, (90)–(92): equally spaced classical inner-code Gaussian tail
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every nonzero natural number ddd with d≥2d\ge2d≥2, every strictly positive nonnegative real number vvv, and every positive real number ttt, define sj(t)=(2j−d+1)ts_j(t)=(2j-d+1)tsj​(t)=(2j−d+1)t for j=0,…,d−1j=0,\ldots,d-1j=0,…,d−1. For a positive spacing uuu, define the decoded index

ku(y)=min⁡ ⁣{max⁡ ⁣{round⁡ ⁣(y/u+d−12),0},d−1},k_u(y)=\min\!\left\{\max\!\left\{\operatorname{round}\!\left(\frac{y/u+d-1}{2}\right),0\right\},d-1\right\},ku​(y)=min{max{round(2y/u+d−1​),0},d−1},

where rounding produces an integer and its nonnegative part is regarded as a natural number. Let γv\gamma_vγv​ be the real Gaussian probability measure of mean 000 and variance vvv, and set E(s)=1−2π∫0se−x2 dxE(s)=1-\frac{2}{\sqrt{\pi}}\int_0^s e^{-x^2}\,dxE(s)=1−π​2​∫0s​e−x2dx. Then the mean squared grid symbol satisfies

1d∑j=0d−1sj(t)2=(d2−1)t23.\frac1d\sum_{j=0}^{d-1}s_j(t)^2=\frac{(d^2-1)t^2}{3}.d1​j=0∑d−1​sj​(t)2=3(d2−1)t2​.

For every real yyy and every j∈{0,…,d−1}j\in\{0,\ldots,d-1\}j∈{0,…,d−1},

∣y−skt(y)(t)∣≤∣y−sj(t)∣,|y-s_{k_t(y)}(t)|\le|y-s_j(t)|,∣y−skt​(y)​(t)∣≤∣y−sj​(t)∣,

and for every such jjj,

γv{x:kt(sj(t)+x)≠j}≤E ⁣(t2v).\gamma_v\{x:k_t(s_j(t)+x)\ne j\} \le E\!\left(\frac{t}{\sqrt{2v}}\right).γv​{x:kt​(sj​(t)+x)=j}≤E(2v​t​).

Moreover, for every positive real number PPP, setting u=3P/du=\sqrt{3P}/du=3P​/d gives

1d∑j=0d−1sj(u)2≤P,γv{x:ku(sj(u)+x)≠j}≤E ⁣(3P2d2v)for every j∈{0,…,d−1}.\frac1d\sum_{j=0}^{d-1}s_j(u)^2\le P, \qquad \gamma_v\{x:k_u(s_j(u)+x)\ne j\} \le E\!\left(\sqrt{\frac{3P}{2d^2v}}\right) \quad\text{for every }j\in\{0,\ldots,d-1\}.d1​j=0∑d−1​sj​(u)2≤P,γv​{x:ku​(sj​(u)+x)=j}≤E(2d2v3P​​)for every j∈{0,…,d−1}.
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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