Lemma 7 — assignment-independent price range
ProvedContiguousCake597.Approximate.lemma_7cake-cuttingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1ppad
Let be arbitrary. Let and be arbitrary permutations of , with a single cycle traversing every index. Let and let be arbitrary real prices. If
then
Equivalently, every ordered pair satisfies . The singleton case and zero error are included; no positivity or rationality of prices is required. This is a standalone combinatorial lemma, with no cake-specific parameters or assignment restriction.
Differences from the source:
- encoding: the finite maximum minus minimum is at most Nη → every ordered pair satisfies q_j−q_i≤Nη; reason: on a nonempty finite set the largest pairwise difference is exactly the maximum minus minimum; this avoids default extrema and includes N=1
Preamble
import Definitions.Def_ContiguousCake597_Approximate_Analysis
Formal statement
namespace ContiguousCake597.Approximate
/-- Lemma 7, printed p.9 (PDF 10). Pairwise differences are equivalent
to the finite maximum-minus-minimum bound; n=1 and eta=0 are included. -/
theorem lemma_7 (n : ℕ) (hn : 1 ≤ n) (p sigma : Equiv.Perm (Fin n))
(hp : SingleCycle p) (e : ℝ) (he : 0 ≤ e) (q : Fin n → ℝ)
(hq : ∀ i, max (q i) (q (p i)) - e ≤ q (sigma i)) :
∀ i j : Fin n, q j - q i ≤ (n : ℝ) * e := by sorry
end ContiguousCake597.Approximate
Source
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui, STOC 2027 submission #597 (October 2026), p. 9 (PDF 10), Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.