Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Eq. (13) — Exact distance with a one-complex

Proved
ZengPryadko2019.exactDistanceWithOneComplex

by Rui Chao · Sep 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

chaincomplexescodingtheoryhomologicalalgebraquantumerrorcorrectiontensorproducts

Let A\mathcal AA be a finite based binary chain complex and let B=K(P)\mathcal B=\mathcal K(P)B=K(P) be the one-complex induced by a binary matrix PPP. Then

dj(A×B)=min⁡ ⁣(dj−1(A)d1(B),dj(A)d0(B)).d_j(\mathcal A\times\mathcal B)= \min\!\left( d_{j-1}(\mathcal A)d_1(\mathcal B), d_j(\mathcal A)d_0(\mathcal B) \right).dj​(A×B)=min(dj−1​(A)d1​(B),dj​(A)d0​(B)).

This is the main theorem stated as Eq. (13) in the arXiv version of Weilei Zeng and Leonid P. Pryadko, Higher-Dimensional Quantum Hypergraph-Product Codes with Finite Rates. Distances take values in N∪{∞}\mathbb N\cup\{\infty\}N∪{∞}, and the distance of a trivial homology group is ∞\infty∞.

Formalization Note. The theorem is not restricted to a CSS-code degree or to full-rank PPP. It includes both the full-row-rank and non-full-row-rank cases and allows empty chain groups at the endpoints. At j=0j=0j=0, the predecessor distance d−1(A)d_{-1}(\mathcal A)d−1​(A) is interpreted as ∞\infty∞.

Preamble
import Definitions.Def_ZengPryadko2019
Formal statement

namespace ZengPryadko2019

/--
Zeng--Pryadko, arXiv:1810.01519, Eq. (13): when one tensor factor is the
one-complex `K(P)`, the upper bound on homological distance is exact.
-/
theorem exactDistanceWithOneComplex
    (A : BasedBinaryChainComplex) {r c : ℕ}
    (P : BinaryWord (Fin c) →ₗ[ZMod 2] BinaryWord (Fin r)) (j : ℕ) :
    tensorProductDistanceAt A (oneComplex P) j =
      min (chainDistanceBefore A j * chainDistanceAt (oneComplex P) 1)
        (chainDistanceAt A j * chainDistanceAt (oneComplex P) 0) := by
  sorry

end ZengPryadko2019
Source
Weilei Zeng and Leonid P. Pryadko, Higher-dimensional quantum hypergraph-product codes, arXiv:1810.01519v2, Eq. (13), https://arxiv.org/abs/1810.01519
Read-back

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

For every finite-length based binary chain complex AAA over F2=Z/2ZF_2 = Z/2ZF2​=Z/2Z, every pair of natural numbers r,cr,cr,c (including zero), every F2F_2F2​-linear map P:F2c→F2rP:F_2^c → F_2^rP:F2c​→F2r​, and every natural number jjj, the declaration asserts the exact equality in WithTop(N)=N∪∞WithTop(N)=N ∪ {∞}WithTop(N)=N∪∞:

Dj(A⊗K)=min(d<j(A)d1(K),dj(A)d0(K)),D_j(A ⊗ K)=min(d_{<j}(A)d_1(K), d_j(A)d_0(K)),Dj​(A⊗K)=min(d<j​(A)d1​(K),dj​(A)d0​(K)),

where KKK is the one-complex constructed from PPP. These are all the quantified arguments, and there are no further hypotheses on A,P,r,cA,P,r,cA,P,r,c, or jjj. Concretely, AAA consists of dimensions dimA(n)∈Ndim_A(n) ∈ NdimA​(n)∈N, binary word spaces An=(Fin(dimA(n))→F2)A_n=(Fin(dim_A(n)) → F_2)An​=(Fin(dimA​(n))→F2​), and boundary maps indexed by their domain degree: ∂0A:A0→(Empty→F2)∂^A_0:A_0 → (Empty → F_2)∂0A​:A0​→(Empty→F2​), necessarily the zero map to the one-element zero vector space, and ∂n+1A:An+1→An∂^A_{n+1}:A_{n+1} → A_n∂n+1A​:An+1​→An​ for n≥0n ≥ 0n≥0. They satisfy ∂nA∘∂n+1A=0∂^A_n ∘ ∂^A_{n+1}=0∂nA​∘∂n+1A​=0 for every nnn. The structure also has a natural-number length LAL_ALA​ such that dimA(n)=0dim_A(n)=0dimA​(n)=0 whenever LA<nL_A<nLA​<n, but LAL_ALA​ need not be minimal and dimensions at or below it may also vanish. For any such complex XXX, its degree-nnn distance is the infimum in N∪∞N ∪ {∞}N∪∞ of the Hamming weights of exactly those x∈Xnx ∈ X_nx∈Xn​ for which ∂nXx=0∂^X_nx=0∂nX​x=0 and xxx is not in the range of ∂n+1X∂^X_{n+1}∂n+1X​. This distance is ∞∞∞ when that candidate set is empty and otherwise is the least occurring finite Hamming weight. It is never zero, because a word of weight zero is the zero word and zero belongs to every linear-map range. At degree zero, ∂0X=0∂^X_0=0∂0X​=0, so every word is a cycle and the candidates are precisely the words outside the range of ∂1X∂^X_1∂1X​. The one-complex KKK has K0=F2rK_0=F_2^rK0​=F2r​, K1=F2cK_1=F_2^cK1​=F2c​, and the zero vector space in every degree n≥2n ≥ 2n≥2; its boundaries are ∂0K=0∂^K_0=0∂0K​=0, ∂1K=P∂^K_1=P∂1K​=P, and ∂nK=0∂^K_n=0∂nK​=0 for n≥2n ≥ 2n≥2, and its recorded length is 111, even if one or both displayed spaces vanish. Consequently,

d1(K)=infwt(x):x∈F2c,Px=0,x≠0,d_1(K)=inf{wt(x):x ∈ F_2^c, Px=0, x ≠ 0},d1​(K)=infwt(x):x∈F2c​,Px=0,x=0,

so d1(K)=∞d_1(K)=∞d1​(K)=∞ exactly when PPP is injective, while

d0(K)=infwt(y):y∈F2r,y∉range(P),d_0(K)=inf{wt(y):y ∈ F_2^r, y ∉ range(P)},d0​(K)=infwt(y):y∈F2r​,y∈/range(P),

so d0(K)=∞d_0(K)=∞d0​(K)=∞ exactly when PPP is surjective. The quantity d<j(A)d_{<j}(A)d<j​(A) is ∞∞∞ when j=0j=0j=0 and is dk(A)d_k(A)dk​(A) when j=k+1j=k+1j=k+1; it does not introduce an actual negative-degree chain group. The tensor degree-nnn coordinate type is the dependent disjoint union of Fin(dimA(p))×Fin(dimK(q))Fin(dim_A(p)) × Fin(dim_K(q))Fin(dimA​(p))×Fin(dimK​(q)) over all ordered pairs of nonnegative degrees (p,q)(p,q)(p,q) satisfying exactly p+q=np+q=np+q=n, with each pair retained as a tag. Since KqK_qKq​ is zero for q≥2q ≥ 2q≥2, the only potentially nonempty components are (p,q)=(n,0)(p,q)=(n,0)(p,q)=(n,0), using coordinates of AnA_nAn​ and F2rF_2^rF2r​, and, when n≥1n ≥ 1n≥1, (p,q)=(n−1,1)(p,q)=(n-1,1)(p,q)=(n−1,1), using coordinates of An−1A_{n-1}An−1​ and F2cF_2^cF2c​; either component can still be empty when one of its dimensions is zero. Write TnT_nTn​ for the binary word space on this tensor coordinate type. The tensor boundary indexed by its domain is Δ0:T0→(Empty→F2)Δ_0:T_0 → (Empty → F_2)Δ0​:T0​→(Empty→F2​), defined to be zero, and Δn+1:Tn+1→TnΔ_{n+1}:T_{n+1} → T_nΔn+1​:Tn+1​→Tn​ for n≥0n ≥ 0n≥0. At a target coordinate tagged by (p,q)(p,q)(p,q) with p+q=np+q=np+q=n, basis coordinates aaa of ApA_pAp​ and bbb of KqK_qKq​, and source word e∈Tn+1e ∈ T_{n+1}e∈Tn+1​, its value is exactly

(Δn+1e)(p,a,q,b)=∂p+1A(a′↦e(p+1,a′,q,b))(a)+∂q+1K(b′↦e(p,a,q+1,b′))(b).(Δ_{n+1}e)(p,a,q,b) =∂^A_{p+1}(a' ↦ e(p+1,a',q,b))(a) +∂^K_{q+1}(b' ↦ e(p,a,q+1,b'))(b).(Δn+1​e)(p,a,q,b)=∂p+1A​(a′↦e(p+1,a′,q,b))(a)+∂q+1K​(b′↦e(p,a,q+1,b′))(b).

The first source coordinate is tagged by (p+1,q)(p+1,q)(p+1,q), the second by (p,q+1)(p,q+1)(p,q+1), and the two contributions are added in F2F_2F2​, with no sign factor. For the one-complex, the second contribution uses PPP exactly when q=0q=0q=0 and is zero when q≥1q ≥ 1q≥1. The imported declarations prove Δn∘Δn+1=0Δ_n ∘ Δ_{n+1}=0Δn​∘Δn+1​=0 for every nnn, including the endpoint involving Δ0Δ_0Δ0​. The left-hand side Dj(A⊗K)D_j(A ⊗ K)Dj​(A⊗K) is the infimum of the Hamming weights of exactly those e∈Tje ∈ T_je∈Tj​ satisfying Δje=0Δ_je=0Δj​e=0 and not belonging to the range of Δj+1Δ_{j+1}Δj+1​. It is ∞∞∞ if this candidate set is empty, including when TjT_jTj​ is the zero vector space, and otherwise is a positive finite minimum. At j=0j=0j=0, the only degree pair is (0,0)(0,0)(0,0), Δ0=0Δ_0=0Δ0​=0, and every tensor word is a cycle. Also d<0(A)=∞d_{<0}(A)=∞d<0​(A)=∞; because d1(K)d_1(K)d1​(K) is never zero, the first product on the right is ∞∞∞, so the asserted equality specializes exactly to

D0(A⊗K)=d0(A)d0(K).D_0(A ⊗ K)=d_0(A)d_0(K).D0​(A⊗K)=d0​(A)d0​(K).

At a positive degree j=k+1j=k+1j=k+1, it specializes exactly to

Dk+1(A⊗K)=min(dk(A)d1(K),dk+1(A)d0(K)).D_{k+1}(A ⊗ K)=min(d_k(A)d_1(K), d_{k+1}(A)d_0(K)).Dk+1​(A⊗K)=min(dk​(A)d1​(K),dk+1​(A)d0​(K)).

All products and minima are taken in N∪∞N ∪ {∞}N∪∞. Because none of the distance factors is zero, a displayed product is finite exactly when both factors are finite and is ∞∞∞ when either factor is ∞∞∞; the binary minimum is finite if at least one product is finite and is ∞∞∞ exactly when both products are ∞∞∞. Thus injectivity of PPP makes the d1(K)d_1(K)d1​(K) product infinite, surjectivity makes the d0(K)d_0(K)d0​(K) product infinite, and bijectivity makes both products infinite, forcing the asserted tensor distance to be ∞∞∞. If r=0r=0r=0, then PPP is automatically surjective and d0(K)=∞d_0(K)=∞d0​(K)=∞; if c=0c=0c=0, then PPP is automatically injective and d1(K)=∞d_1(K)=∞d1​(K)=∞. The theorem imposes no rank condition, no positivity condition on rrr or ccc, no nontrivial-homology or finite-distance condition, and no restriction of jjj by the recorded length of AAA. It asserts equality, not merely either inequality, and its right-hand side is a binary minimum rather than a minimum over an additional index set.

Human review
  • Endorsed by Shuze Chen · Sep 11, 2026

  • Endorsed by Rui Chao · Sep 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me