Lemma A.3 — a symmetric-mean (Maclaurin) inequality for a uniform s-subset
ProvedAcycTesting.NearLinear.lemma_A_3directed-graphsinequalitiesp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquery-complexity
Let and let be a uniformly random subset of size (). Then
Equivalently for the elementary symmetric polynomial . It gives the exponential lower tail of balanced cuts (Lemma A.4).
Differences from the source:
- encoding: E over a uniform s-subset I ⊆ [N] → the average of ∏_{i∈I} z_i over Finset.powersetCard s (Fin N), i.e. the sum divided by choose N s, with s ≤ N; reason: a uniform s-subset exists exactly when s ≤ N; Fin N for [N]
Preamble
import Mathlib
Formal statement
namespace AcycTesting.NearLinear
/-- Lemma A.3 (a symmetric-mean inequality): for `z₁, …, z_N ≥ 0` and a uniform `s`-subset
`I ⊆ [N]`, `E ∏_{i ∈ I} z_i ≤ ((1/N) ∑_i z_i)^s`. -/
theorem lemma_A_3 (N s : ℕ) (hs : s ≤ N) (z : Fin N → ℝ) (hz : ∀ i, 0 ≤ z i) :
(∑ I ∈ (Finset.univ : Finset (Fin N)).powersetCard s, ∏ i ∈ I, z i) / (N.choose s : ℝ) ≤
((1 / (N : ℝ)) * ∑ i, z i) ^ s := by sorry
end AcycTesting.NearLinear
Source
Czumaj, Peng, Wang, Near-Linear Lower Bounds for Testing Directed Acyclicity, arXiv:2611.04901v1 (sha256 5685fc7b…), p. 39 (PDF 42), Lemma A.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.