Lemma A.1 — Levin work investment (corrected: k ≥ 2)
ProvedPauliMixedness.Randomized.levin_work_investmentp2o-batch-stoc27ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-information
Let be an integer, uniform on a set of size , any real function on that set, and with . Set . Then
Nonpositive is included. The finite uniform expectation and tail probability are the corresponding sum and count divided by . This work-investment statement supports the Pauli influence lemma at support size .
Differences from the source:
- correction: no exclusion of → ; reason: at k=1, f(1)=μ=1 satisfies every printed premise but M=0 leaves no possible index; the application k=3^N≥3 is unaffected
- encoding: , base-three logarithm and uniform probability → , and finite counts divided by k; reason: reindexing preserves all values; signed real powers retain i−2 exactly when i=1
Preamble
import Mathlib open scoped BigOperators
Formal statement
namespace PauliMixedness.Randomized
/-- Lemma A.1 p.24 (corrected: k ≥ 2). At k=1, f=1 and μ=1 the printed
premises hold but the index set [ceil(log₃1)] is empty. μ may be nonpositive. -/
theorem levin_work_investment (k : ℕ) (hk : 2 ≤ k) (f : Fin k → ℝ) (μ : ℝ)
(hf : ∀ x, 0 ≤ f x) (hmean : μ ≤ (∑ x : Fin k, f x) / k) :
∃ i : ℕ, 1 ≤ i ∧ i ≤ ⌈Real.log (k : ℝ) / Real.log 3⌉₊ ∧
(3 : ℝ) ^ (-(i : ℤ)) / (⌈Real.log (k : ℝ) / Real.log 3⌉₊ : ℝ) ≤
((Finset.univ.filter (fun x => (3 : ℝ)^((i : ℤ) - 2) * μ ≤ f x)).card : ℝ) /
(k : ℝ) := by sorry
end PauliMixedness.Randomized
Source
Abhilash Dharmavarapu, Jayadev Acharya, Nengkun Yu, Yuhan Liu, STOC 2027 submission #231 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/231.pdf, Lemma A.1 p.24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.