Lemma 2.3 — restrictions and modular shifts
ProvedBarelyTestable.LowerBound.restrictions_modularlowerboundp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingsubmodularity
Let be any real submodular function on a Boolean cube. Fix any set of free coordinates and any assignment outside it. Let be any modular function, including one with a nonzero constant term. Then both assertions hold:
The first conclusion ranges over every coordinate restriction, including no free coordinates and all free coordinates. These closure facts justify working within individual slices.
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: fix any set of coordinates → restriction f R Z evaluates at (Z minus R) union T; reason: Z is an arbitrary assignment and the free set T has the subtype R as its coordinate type
Preamble
import Mathlib import Definitions.Def_BarelyTestable_LowerBound_Cube set_option autoImplicit false
Formal statement
namespace BarelyTestable.LowerBound
open NonmonotoneSubmod.Shared MeasureTheory
/-- Lemma 2.3, p.10: restrictions and arbitrary modular shifts, including constants. -/
theorem restrictions_modular {n : ℕ} (f : Oracle (Fin n)) (hf : Submodular f) :
(∀ R Z : Cube (Fin n), Submodular (restriction f R Z)) ∧
(∀ h : Oracle (Fin n), Modular h → Submodular (fun S => f S + h S)) := by sorry
end BarelyTestable.LowerBound
Source
Diptaksho Palit, Yuichi Yoshida, STOC 2027 submission #722 (October 2026), Lemma 2.3, p. 10 (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.