Claim 3.15 — nonzero mass under independent Bernoulli coordinates
ProvedBarelyTestable.LowerBound.bernoulli_nonzerolowerboundp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingsubmodularity
Let , let be submodular with , and let have independent coordinates with probabilities . Then
The probabilities may differ by coordinate, and zero and one are allowed. This gives a lower bound on the support of a real submodular function without imposing a global sign condition.
Differences from the source:
- encoding: Boolean vectors with coordinates numbered from 1 → finite subsets of Fin n, numbered from 0; reason: the incidence-vector bijection preserves every vertex, union, intersection and coordinate square
- encoding: the law of independent Bernoulli coordinates → the exact product-weight sum over all subsets; reason: independence determines this law uniquely, so every source random vector has precisely this probability; the finite minimum initialized at one equals the stated minimum for ℓ ≥ 1
Preamble
import Mathlib import Definitions.Def_BarelyTestable_LowerBound_Cube set_option autoImplicit false
Formal statement
namespace BarelyTestable.LowerBound
open NonmonotoneSubmod.Shared MeasureTheory
/-- Claim 3.15, p.19: independent, nonidentical Bernoulli probabilities, including endpoints. -/
theorem bernoulli_nonzero {ℓ : ℕ} (hℓ : 1 ≤ ℓ) (f : Oracle (Fin ℓ))
(hf : Submodular f) (h0 : 0 < f ∅) (q : Fin ℓ → ℝ)
(hq : ∀ i, 0 ≤ q i ∧ q i ≤ 1) :
minBias q ≤ bernoulliProb q (fun S => f S ≠ 0) := by sorry
end BarelyTestable.LowerBound
Source
Diptaksho Palit, Yuichi Yoshida, STOC 2027 submission #722 (October 2026), Claim 3.15, p. 19 (printed = PDF page); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/722.pdf; PDF SHA256 a095e6ef801edf5b0ce3967efca977e04b7a0b4374e874116509d73837bd14f3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.