Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 10, valid clauses (B1)–(B3)

Open
QAlgorithms.Papers.Independent.Intakenext100.P20.specht_bounds_and_type_count

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

prove2quantum

Let d,n≥1d,n\ge1d,n≥1. Let YnY_nYn​ be the Young diagrams with nnn boxes and at most ddd rows, and write λ=(λ1≥⋯≥λd≥0)\lambda=(\lambda_1\ge\cdots\ge\lambda_d\ge0)λ=(λ1​≥⋯≥λd​≥0) for padded row lengths. Put bi=λi/nb_i=\lambda_i/nbi​=λi​/n, H(b)=−∑ibilog⁡biH(b)=-\sum_i b_i\log b_iH(b)=−∑i​bi​logbi​, and let VλV_\lambdaVλ​ be the actual symmetric-group Specht factor. Then

enH(b)(n+d)−d(d+1)/2≤dim⁡Vλ≤(n+d)2denH(b),∣Yn∣≤(n+1)d.e^{nH(b)}(n+d)^{-d(d+1)/2}\le\dim V_\lambda\le(n+d)^{2d}e^{nH(b)},\qquad |Y_n|\le(n+1)^d.enH(b)(n+d)−d(d+1)/2≤dimVλ​≤(n+d)2denH(b),∣Yn​∣≤(n+1)d.

These are exactly clauses (B1)-(B3), which can be retained independently of the defective Schur-factor bound (B4).

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P20
Formal statement
noncomputable section

open scoped Matrix ENNReal ComplexOrder Topology

namespace QAlgorithms.Papers.Independent.Intakenext100.P20

open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)

open QAlgorithms.Papers.Independent.Information100.P47 (IsProbability)

open QAlgorithms.Papers.Independent.Information100.P53 (SpectralData)

open QAlgorithms.Papers.Independent.Gap48.P19 (shannonNats)

open QAlgorithms.Papers.Independent.Dependency50.P28 (classicalD)

attribute [local instance] Classical.propDecidable

/-- Lemma 10, PDF pp.9-10, precisely the valid clauses (B1)-(B3).
The separately false Schur-factor bound (B4) is excluded and deferred. -/
theorem specht_bounds_and_type_count {d n : ℕ} (hd : 0 < d) (hn : 0 < n) :
    (∀ shape : Schur.Partition d n,
      Real.exp ((n : ℝ) * shannonNats (Schur.normalizedRows hd hn shape)) * lowerPrefactor d n ≤
        (Module.finrank ℂ (Schur.spechtSpace shape) : ℝ) ∧
      (Module.finrank ℂ (Schur.spechtSpace shape) : ℝ) ≤
        (n + d : ℝ) ^ (2 * d) *
          Real.exp ((n : ℝ) * shannonNats (Schur.normalizedRows hd hn shape))) ∧
    Fintype.card (Schur.Partition d n) ≤ (n + 1) ^ d := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P20

end
Source
Exponents of quantum fixed-length pure state source coding, arXiv:quant-ph/0202002v6, PDF p. 9, Lemma 10, valid clauses (B1)–(B3)
Read-back

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

For any positive natural numbers d,nd,nd,n, and every Young diagram λ\lambdaλ with exactly nnn cells and at most ddd rows, let bi=λi/nb_i=\lambda_i/nbi​=λi​/n for 0≤i<d0\le i<d0≤i<d, where λi\lambda_iλi​ is row iii's length and missing rows have length 000, and put H(b)=−∑ibilog⁡biH(b)=-\sum_i b_i\log b_iH(b)=−∑i​bi​logbi​, using natural logarithms and 0log⁡0=00\log0=00log0=0. Fix the chosen bijection between the cells and {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}, let Rλ,Cλ⊆SnR_\lambda,C_\lambda\subseteq S_nRλ​,Cλ​⊆Sn​ be the permutations preserving respectively the row and the column of each numbered cell, and let Vλ⊆CSnV_\lambda\subseteq\mathbb C^{S_n}Vλ​⊆CSn​ be the range of the matrix

(Yλ)g,h=∑a∈Rλ∑b∈Cλ1{g=hab}sgn⁡(b).(Y_\lambda)_{g,h} =\sum_{a\in R_\lambda}\sum_{b\in C_\lambda} \mathbf1_{\{g=hab\}}\operatorname{sgn}(b).(Yλ​)g,h​=a∈Rλ​∑​b∈Cλ​∑​1{g=hab}​sgn(b).

Then

enH(b)(n+d)−d(d+1)/2≤dim⁡CVλ≤(n+d)2denH(b).e^{nH(b)}(n+d)^{-d(d+1)/2} \le \dim_{\mathbb C}V_\lambda \le (n+d)^{2d}e^{nH(b)}.enH(b)(n+d)−d(d+1)/2≤dimC​Vλ​≤(n+d)2denH(b).

In addition, the number of Young diagrams with nnn cells and at most ddd rows is at most (n+1)d(n+1)^d(n+1)d. Both positivity assumptions are required; zero row lengths within an allowed diagram are included.

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