Claim 3.7 — sensitivity of reciprocal products
ProvedCountingLLL.DetCount.claim_3_7approximate-countingconstraint-satisfactionlovasz-local-lemmap2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and , and let . Then
This elementary estimate converts errors in the recursive marginals into errors in the expansion (14).
Differences from the source:
- encoding: indices 1 ≤ i ≤ ℓ → indices in Fin ℓ (0-based); reason: relabelling
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace CountingLLL.DetCount
/-- Claim 3.7: for `0 < t < 1`, `ℓ ≥ 1` and `x, y ∈ [−t, t]^ℓ`,
`|∏_{i=1}^ℓ 1/(1 − x_i) − ∏_{i=1}^ℓ 1/(1 − y_i)| ≤ ℓ/(1 − t)^{ℓ+1} · max_i |x_i − y_i|`. -/
theorem claim_3_7 (t : ℝ) (ht₀ : 0 < t) (ht₁ : t < 1) (ℓ : ℕ) (hℓ : 1 ≤ ℓ)
(x y : Fin ℓ → ℝ) (hx : ∀ i, x i ∈ Set.Icc (-t) t) (hy : ∀ i, y i ∈ Set.Icc (-t) t) :
|∏ i, 1 / (1 - x i) - ∏ i, 1 / (1 - y i)| ≤
(ℓ : ℝ) / (1 - t) ^ (ℓ + 1) *
(Finset.univ : Finset (Fin ℓ)).sup' (Finset.univ_nonempty_iff.mpr ⟨⟨0, hℓ⟩⟩)
(fun i => |x i - y i|) := by sorry
end CountingLLL.DetCount
Source
Hongyang Liu, Chunyang Wang, Yitong Yin, Yiyao Zhang, Can Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 submission #442 (October 2026), Claim 3.7, equation (17), PDF p. 11 (printed p. 10); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.