Razborov's distributional bound for disjointness (displayed in the proof of Theorem 1)
ProvedExtensionComplexity.TSP.razborov_distributionalcommunication-complexitydisjointnessp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1razborov
For -bit strings write for the number of common ones. There are constants , independent of , such that for every sufficiently large there exist sets and a probability distribution on with
- for all , and for all ;
- ;
- for every rectangle with ,
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 -monochromatic rectangle of the support of avoids and therefore carries little -mass of . The paper notes that and work for large .
Formalization Note "Sufficiently large " is for some ; are chosen before and . is a nonnegative function summing to , is the sum of over , and 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.