The binary pigeonhole principle ,
DefinitionLiftSAParity_Supplement_bphpp2o-gran-per-chapterp2o-plan-paperp2o-v1pigeonhole-principleproof-complexity
Let and , and let . The binary pigeonhole principle has variables for pigeons and bits ; the bits encode the hole of pigeon . For every pair of distinct pigeons and every hole it has the clause
which is falsified exactly when pigeons and both sit in hole . An assignment satisfies the formula iff the pigeons sit in pairwise distinct holes, so is unsatisfiable iff . The blocks are the pigeons, each a block of variables.
Formalization Note The paper does not list the clauses; this is the standard collision encoding. In the CNF convention the literal is true iff , so is the literal . The ordered pairs and give the same clause.
Definition code
import Mathlib
import Definitions.Def_LiftSAParity_CNF
namespace LiftSAParity
namespace Supplement
/-- The clause of `BPHP^m_n` saying that the distinct pigeons `u ≠ u'` are not both in the hole
`a ∈ {0,1}^k`: `⋁_t (x_{u,t} ≠ a_t) ∨ ⋁_t (x_{u',t} ≠ a_t)`. In the CNF convention the literal
`(v, b)` is true iff `x_v = b`, so `x_{u,t} ≠ a_t` is the literal `((u,t), !a_t)`. -/
def bphpClause {m k : ℕ} (u u' : Fin m) (a : Fin k → Bool) : Clause (Fin m × Fin k) :=
(Finset.univ.image fun t : Fin k => ((u, t), !a t)) ∪
(Finset.univ.image fun t : Fin k => ((u', t), !a t))
/-- **The binary pigeonhole principle** `BPHP^m_n`, `n = 2^k` (de Rezende–Engström–Shekhovtsov,
*Lifting Sherali-Adams Degree to Unary Sherali-Adams over Parities Size*, manuscript (sha256
cab5a032…), §1.1, p.5 and §6.2, p.23): "m pigeons cannot sit in n = 2^ℓ holes … For each of m
pigeons we have ℓ bits encoding its hole. The formula's variables are indexed by [m] × [ℓ]."
Blocks are pigeons (`Fin m`), each of `k` bits (`Fin k`).
**Formalization Note** The paper gives no clause list. This is the standard collision CNF: for
every ordered pair of distinct pigeons `u ≠ u'` and every hole `a ∈ {0,1}^k`, the clause
`bphpClause u u' a`, falsified exactly when both pigeons sit in hole `a` (the pairs `(u,u')` and
`(u',u)` give the same clause). An assignment satisfies every clause iff the pigeons sit in
pairwise distinct holes, so the formula is unsatisfiable iff `m > 2^k`. -/
def bphp (m k : ℕ) : CNF (Fin m × Fin k) :=
((Finset.univ.filter (fun p : Fin m × Fin m => p.1 ≠ p.2)) ×ˢ
(Finset.univ : Finset (Fin k → Bool))).image
(fun q => bphpClause q.1.1 q.1.2 q.2)
end Supplement
end LiftSAParity
Source
de Rezende, Engström, Shekhovtsov, Lifting Sherali-Adams Degree to Unary Sherali-Adams over Parities Size (manuscript, sha256 cab5a032…), §1.1, p.5; §6.2, p.23