Claim A.1 —
ProvedCSPSubsample.claim_A_1concentration-inequalitiesconstraint-satisfactionmax-cspp2o-gran-per-chapterp2o-plan-paperp2o-v1subsampling
For integers , with the falling factorial,
It measures the gap between the two normalizations of the paper (the number of distinct-variable tuples versus the power ) and enters the bias bound (Lemma 4.4) and the lower half of the subsampling theorem.
Differences from the source: none.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace CSPSubsample
/-- **Claim A.1** (arXiv:2608.00203 (PDF sha256 fd9ae011…), p.26 = PDF p.28). For integers
`1 ≤ k ≤ N`, `1 − k²/N ≤ N^{\underline k}/N^k ≤ 1`.
**Formalization Note** `N^{\underline k} = N(N−1)⋯(N−k+1)` is `Nat.descFactorial N k`; `N^k` is
the power. Both inequalities are stated. -/
theorem claim_A_1 (k N : ℕ) (hk : 1 ≤ k) (hkN : k ≤ N) :
1 - (k : ℝ) ^ 2 / N ≤ (N.descFactorial k : ℝ) / (N : ℝ) ^ k ∧
(N.descFactorial k : ℝ) / (N : ℝ) ^ k ≤ 1 := by sorry
end CSPSubsample
Source
Bernasconi, Castiglioni, Celli, Farina, Malavolta, A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity, arXiv:2608.00203 (PDF sha256 fd9ae01113266fee273c46c14c8a1a39f36a958dba3fc276cd74bf4c3daff445), Claim A.1, p.26 (PDF p.28)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.