Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 14 — sign-rank bounds for OR compositions of regular relations

Proved
SignRankMargin.OREquality.Supplement.theorem_14

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

communication-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sign-rank

Let n,D,kn,D,kn,D,k be integers with 1≤D<n1\le D<n1≤D<n and k≥1k\ge1k≥1. Let BBB be any n×nn\times nn×n Boolean matrix with exactly DDD ones in every row and exactly DDD ones in every column; equivalently, BBB is the biadjacency matrix of a DDD-regular bipartite graph with nnn vertices on each side. No symmetry, connectedness or diagonal condition is imposed. The OR composition ORk∘B\mathrm{OR}_k\circ BORk​∘B has rows and columns indexed by all tuples x,y∈[n]kx,y\in[n]^kx,y∈[n]k, with

(ORk∘B)(x,y)=1[∃i∈[k]:B(xi,yi)=1].(\mathrm{OR}_k\circ B)(x,y)=\mathbf 1[\exists i\in[k]: B(x_i,y_i)=1].(ORk​∘B)(x,y)=1[∃i∈[k]:B(xi​,yi​)=1].

Regard BBB as a real 0/10/10/1 matrix, let JJJ be the n×nn\times nn×n all-ones matrix, and let λ=∥B−(D/n)J∥op\lambda=\|B-(D/n)J\|_{\mathrm{op}}λ=∥B−(D/n)J∥op​ be the Euclidean (ℓ2→ℓ2\ell_2\to\ell_2ℓ2​→ℓ2​) operator norm of the centered matrix. Write rank⁡±\operatorname{rank}_\pmrank±​ for the minimum real rank of a strict sign realization. Then

rank⁡±(ORk∘B)≤(3D)k,\operatorname{rank}_\pm(\mathrm{OR}_k\circ B)\le(3D)^k,rank±​(ORk​∘B)≤(3D)k,

and, whenever n≥2(6D)k+1n\ge 2^{(6D)^{k+1}}n≥2(6D)k+1, also

(Dλ)k≤rank⁡±(ORk∘B).\left(\frac{D}{\lambda}\right)^k\le\operatorname{rank}_\pm(\mathrm{OR}_k\circ B).(λD​)k≤rank±​(ORk​∘B).

The upper bound needs no size threshold. The lower bound is a direct-sum statement: the sign-rank of the kkk-fold OR composition is at least the kkk-th power of the spectral ratio D/λD/\lambdaD/λ of a single copy. The equality matrix is the case D=1D=1D=1, where it recovers an exponential lower bound of the same shape as the mission's goal.

Formalization Note Sign-rank and OR composition are the published definitions signRank and orComposition of this mission. Row and column regularity are stated as exact counts of true entries. λ\lambdaλ is the norm of (Matrix.toEuclideanLin Z).toContinuousLinearMap for the real matrix Z(x,y)=1[B(x,y)]−D/nZ(x,y)=\mathbf 1[B(x,y)]-D/nZ(x,y)=1[B(x,y)]−D/n, the same operator-norm convention as Lemma 13. The lower bound compares real numbers, with the natural-number sign-rank cast to R\mathbb RR; D/λD/\lambdaD/λ is real division. The source assumptions force λ≥1\lambda\ge1λ≥1, so no positivity hypothesis on λ\lambdaλ is added.

Differences from the source:

  • encoding: vertex set [n] and coordinates [k]; B ∈ {0,1}^{n×n} with exactly D ones per row and column → Fin n and Fin k indices; B : Matrix (Fin n) (Fin n) Bool with row and column counts of true entries equal to D; reason: finite relabelling; the counts express exactly the source's regularity
  • encoding: λ = ‖B − (D/n)J‖_op, real comparison (D/λ)^k ≤ rank± → norm of the continuous linear map of the real matrix 1[B]−D/n between Euclidean spaces; signRank cast to ℝ; reason: this is the ℓ₂→ℓ₂ operator norm of the same real matrix, and the comparison is the same real inequality
  • encoding: if n ≥ 2^{(6D)^{k+1}} then both bounds; the upper bound holds for any n ≥ 1 → unconditional upper bound conjoined with the threshold-conditional lower bound, under the standing 1 ≤ D < n; reason: expresses both source clauses without imposing the threshold on the upper bound
Preamble
import Mathlib
import Definitions.Def_SignRankMargin_OREquality_SignRank
import Definitions.Def_SignRankMargin_OREquality_Composition
Formal statement
namespace SignRankMargin.OREquality.Supplement

/-- Theorem 14, p.15 (assumptions p.14). `B` is an arbitrary n×n Boolean matrix with exactly
`D` ones in every row and every column, `1 ≤ D < n`. The upper bound `(3D)^k` holds for all
such `n`; only the lower bound `(D/λ)^k` needs `n ≥ 2^((6D)^(k+1))`. Here
`λ = ‖B − (D/n)J‖_op` is the Euclidean ℓ₂→ℓ₂ operator norm of the centered real matrix,
taken on the continuous linear map between real Euclidean spaces. -/
theorem theorem_14 (n D k : ℕ) (hD : 1 ≤ D) (hDn : D < n) (hk : 1 ≤ k)
    (B : Matrix (Fin n) (Fin n) Bool)
    (hrows : ∀ x, (∑ y, if B x y then (1 : ℕ) else 0) = D)
    (hcols : ∀ y, (∑ x, if B x y then (1 : ℕ) else 0) = D) :
    signRank (orComposition k B) ≤ (3 * D) ^ k ∧
    (2 ^ ((6 * D) ^ (k + 1)) ≤ n →
      ((D : ℝ) / ‖(Matrix.toEuclideanLin
          (fun x y => (if B x y then (1 : ℝ) else 0) - (D : ℝ) / (n : ℝ))
          ).toContinuousLinearMap‖) ^ k ≤
        (signRank (orComposition k B) : ℝ)) := by sorry

end SignRankMargin.OREquality.Supplement
Source
Gabriel Hart, Kaave Hosseini, STOC 2027 submission #728 (October 2026), Theorem 14, p. 15; standing assumptions (B, D, n, λ, OR_k ∘ B) p. 14; proof p. 15

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