§8.4 — choice of l₁ < l₂ in (p/3 − 2|D|, p/3) with s(1^{l₁}0…) = s(1^{l₂}0…)
ProvedAlgebraicPCSP.OneInThree.section_8_4_pigeonholecyclic-operationsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite set, any map, a prime with , and any operation. Then there are natural numbers with
where are evaluated in through .
This is the pigeonhole step that opens §8.4: the interval contains integers, so two of the -tuples receive the same value of . The two matrices built from and then have equal -values but areas on opposite sides of .
Formalization Note The inequalities are in . No property of is needed. The paper prints " integers", meaning .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_AlgebraicPCSP_OneInThree_Structures import Definitions.Def_AlgebraicPCSP_OneInThree_Matrices
Formal statement
namespace AlgebraicPCSP.OneInThree
/-- §8.4 (pp. 57–58), the choice of `l₁, l₂`: for any `p`-ary operation `s` on a finite set
`D`, any `f : {0, 1} → D`, and a prime `p > 60|D|`, there are natural numbers `l₁, l₂` with
`p/3 − 2|D| < l₁ < l₂ < p/3` and `s(f ∘ (1^{l₁} 0^{p−l₁})) = s(f ∘ (1^{l₂} 0^{p−l₂}))`. -/
theorem section_8_4_pigeonhole {D : Type} [Fintype D] [DecidableEq D] (f : Fin 2 → D)
{p : ℕ} (hp : p.Prime) (hpD : 60 * Fintype.card D < p) (s : (Fin p → D) → D) :
∃ l₁ l₂ : ℕ, (p : ℚ) / 3 - 2 * (Fintype.card D : ℚ) < l₁ ∧ l₁ < l₂ ∧
(l₂ : ℚ) < (p : ℚ) / 3 ∧
s (fun j => f (prefixOnes p l₁ j)) = s (fun j => f (prefixOnes p l₂ j)) := by sorry
end AlgebraicPCSP.OneInThree
Source
L. Barto, J. Bulín, A. Krokhin, J. Opršal, Algebraic approach to promise constraint satisfaction, arXiv:1811.00970v3, pp. 57–58, §8.4 (unnumbered: choice of l₁ and l₂)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.