Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — the hypergraph product of a full-rank (n−k)×n check matrix of an [n,k,d] code with itself has length n²+(n−k)², dimension k², distance d and row weights i+j

Proved
TillichZemor.HGP.theorem_1

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

hypergraph-productldpc-codesminimum-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-codes

Let 0≤k≤n0\le k\le n0≤k≤n and let HHH be a full-rank (n−k)×n(n-k)\times n(n−k)×n binary parity-check matrix of a classical linear code C=ker⁡H\mathcal C=\ker HC=kerH of parameters [n,k,d][n,k,d][n,k,d], where ddd is the minimum distance of C\mathcal CC (d=∞d=\inftyd=∞ if k=0k=0k=0). Let Q=Q(G×G)\mathcal Q=\mathcal Q(\mathcal G\times\mathcal G)Q=Q(G×G) be the hypergraph-product CSS code built from two copies of the Tanner graph G\mathcal GG of HHH, with check matrices

HX=(H⊗In ∣ In−k⊗HT),HZ=(In⊗H ∣ HT⊗In−k).H_X=\big(H\otimes I_n\ \big|\ I_{n-k}\otimes H^{T}\big),\qquad H_Z=\big(I_n\otimes H\ \big|\ H^{T}\otimes I_{n-k}\big).HX​=(H⊗In​ ​ In−k​⊗HT),HZ​=(In​⊗H ​ HT⊗In−k​).

Then:

  1. CZ⊥⊆CX\mathcal C_Z^{\perp}\subseteq\mathcal C_XCZ⊥​⊆CX​, so (CX,CZ)(\mathcal C_X,\mathcal C_Z)(CX​,CZ​) is a CSS code;
  2. its length is N=n2+(n−k)2N=n^2+(n-k)^2N=n2+(n−k)2;
  3. its dimension is kQ=k2k_Q=k^2kQ​=k2;
  4. its quantum minimum distance is dQ=dd_Q=ddQ​=d;
  5. every row of HXH_XHX​ and of HZH_ZHZ​ has weight i+ji+ji+j, where iii is the weight of a row of HHH and jjj the weight of a column of HHH: row (c,v)(c,v)(c,v) of HXH_XHX​ has weight ∣Hc,⋅∣+∣H⋅,v∣|H_{c,\cdot}|+|H_{\cdot,v}|∣Hc,⋅​∣+∣H⋅,v​∣, and row (v,c)(v,c)(v,c) of HZH_ZHZ​ has weight ∣H⋅,v∣+∣Hc,⋅∣|H_{\cdot,v}|+|H_{c,\cdot}|∣H⋅,v​∣+∣Hc,⋅​∣.

In particular a family of classical LDPC codes of fixed rate and linear minimum distance gives quantum LDPC codes of fixed rate and minimum distance proportional to N\sqrt NN​.

Formalization Note. "There is a construction … with HHH as building block" is formalized as the specific construction of the paper, the hypergraph product of HHH with itself (p. 18: Theorem 1 is Theorem 15 with G1=G2\mathcal G_1=\mathcal G_2G1​=G2​). The hypothesis k≤nk\le nk≤n is added: it is implicit in "[n,k,d][n,k,d][n,k,d]", and without it the matrix would have no rows and the dimension claim would fail. The qualifier "LDPC" is a property of families of codes and is not formalized; its finite content is the row-weight clause. The dimension kkk of C\mathcal CC is not assumed: it follows from the full rank of HHH. The minimum distance takes values in N∪{∞}\mathbb N\cup\{\infty\}N∪{∞}.

Preamble
import Mathlib
import Definitions.Def_CodingTheory
import Definitions.Def_TillichZemor_HGP_Setting
open Matrix
Formal statement
namespace TillichZemor.HGP

theorem theorem_1 (n k : ℕ) (hk : k ≤ n) (H : Matrix (Fin (n - k)) (Fin n) (ZMod 2))
    (hH : H.rank = n - k) :
    CodingTheory.dualCode (ZMod 2) ((Fin n × Fin n) ⊕ (Fin (n - k) × Fin (n - k)))
        (code (hz H H)) ≤ code (hx H H) ∧
    Fintype.card ((Fin n × Fin n) ⊕ (Fin (n - k) × Fin (n - k))) = n ^ 2 + (n - k) ^ 2 ∧
    quantumDim H H = k ^ 2 ∧
    quantumDist H H = minDist (code H) ∧
    (∀ (c : Fin (n - k)) (v : Fin n),
      hammingNorm (hx H H (c, v)) = hammingNorm (H c) + hammingNorm (fun c' => H c' v)) ∧
    (∀ (v : Fin n) (c : Fin (n - k)),
      hammingNorm (hz H H (v, c)) = hammingNorm (fun c' => H c' v) + hammingNorm (H c)) := by sorry

end TillichZemor.HGP
Source
Tillich and Zémor, Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}, arXiv:0903.0566v2, p. 3, Theorem 1 (construction: Definition 3, pp. 7–8, matrix form p. 18)
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 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