Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Razborov's distributional bound for disjointness (displayed in the proof of Theorem 1)

Proved
ExtensionComplexity.TSP.razborov_distributional

by mikedeng1 · 1 vote · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

communication-complexitydisjointnessp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1razborov

For nnn-bit strings a,ba,ba,b write a⊤ba^\top ba⊤b for the number of common ones. There are constants α,δ>0\alpha,\delta>0α,δ>0, independent of nnn, such that for every sufficiently large nnn there exist sets A,B⊆{0,1}n×{0,1}nA,B\subseteq\{0,1\}^n\times\{0,1\}^nA,B⊆{0,1}n×{0,1}n and a probability distribution μ\muμ on {0,1}n×{0,1}n\{0,1\}^n\times\{0,1\}^n{0,1}n×{0,1}n with

  1. a⊤b=0a^\top b=0a⊤b=0 for all (a,b)∈A(a,b)\in A(a,b)∈A, and a⊤b=1a^\top b=1a⊤b=1 for all (a,b)∈B(a,b)\in B(a,b)∈B;
  2. μ(A)=3/4\mu(A)=3/4μ(A)=3/4;
  3. for every rectangle R=R1×R2R=R_1\times R_2R=R1​×R2​ with R1,R2⊆{0,1}nR_1,R_2\subseteq\{0,1\}^nR1​,R2​⊆{0,1}n,
μ(R∩B) ≥ α⋅μ(R∩A)−2−δn.\mu(R\cap B)\ \ge\ \alpha\cdot\mu(R\cap A)-2^{-\delta n}.μ(R∩B) ≥ α⋅μ(R∩A)−2−δn.

The paper quotes this result of Razborov (in the form of Kushilevitz and Nisan) without proof; it is the input to Theorem 1, since a 111-monochromatic rectangle of the support of M(n)M(n)M(n) avoids BBB and therefore carries little μ\muμ-mass of AAA. The paper notes that α=1/135\alpha=1/135α=1/135 and δ=0.017\delta=0.017δ=0.017 work for large nnn.

Formalization Note "Sufficiently large nnn" is n≥Nn\ge Nn≥N for some NNN; α,δ\alpha,\deltaα,δ are chosen before NNN and nnn. μ\muμ is a nonnegative function summing to 111, μ(S)\mu(S)μ(S) is the sum of μ\muμ over SSS, and 2−δn2^{-\delta n}2−δn is a real power.

Preamble
import Mathlib
import Definitions.Def_ExtensionComplexity_TSP_CorrelationMatrix

open Classical
Formal statement
namespace ExtensionComplexity.TSP

/-- Fiorini et al., J. ACM 62(2) (2015), Art. 17, §2, p. 17:8, the result displayed in the proof of
Theorem 1 (Kushilevitz–Nisan 1997, Example 3.22 and §4.6; Razborov 1992): there are constants
`α, δ > 0`, independent of `n`, such that for every sufficiently large `n` there are sets
`A, B ⊆ {0,1}^n × {0,1}^n` and a probability distribution `μ` on `{0,1}^n × {0,1}^n` with
`aᵀb = 0` on `A`, `aᵀb = 1` on `B`, `μ(A) = 3/4`, and for every rectangle `R = R₁ × R₂`,
`μ(R ∩ B) ≥ α · μ(R ∩ A) − 2^{−δn}`. -/
theorem razborov_distributional :
    ∃ α δ : ℝ, 0 < α ∧ 0 < δ ∧ ∃ N : ℕ, ∀ n ≥ N,
      ∃ (A B : Finset ((Fin n → Bool) × (Fin n → Bool))) (μ : (Fin n → Bool) × (Fin n → Bool) → ℝ),
        (∀ p, 0 ≤ μ p) ∧ (∑ p, μ p) = 1 ∧
        (∀ p ∈ A, bitDot p.1 p.2 = 0) ∧ (∀ p ∈ B, bitDot p.1 p.2 = 1) ∧
        (∑ p ∈ A, μ p) = 3 / 4 ∧
        ∀ R₁ R₂ : Set (Fin n → Bool),
          α * (∑ p ∈ A.filter (fun p => p.1 ∈ R₁ ∧ p.2 ∈ R₂), μ p)
              - (2 : ℝ) ^ (-(δ * n)) ≤
            ∑ p ∈ B.filter (fun p => p.1 ∈ R₁ ∧ p.2 ∈ R₂), μ p := by sorry

end ExtensionComplexity.TSP
Source
Fiorini, Massar, Pokutta, Tiwary, de Wolf, Exponential lower bounds for polytopes in combinatorial optimization, J. ACM 62(2) (2015), Art. 17, §2, p. 17:8, displayed result in the proof of Theorem 1 (Kushilevitz–Nisan 1997, Example 3.22 and §4.6; Razborov 1992)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

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