Lemma 6.2 — Positive contrast and the full invariant-law classifier
OpenZLIPPadding.Padding.Supplement.positive_fourth_momentcomputational-complexitylattice-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Assume and integer . Let be any automorphism-invariant law on , and put for . Define , and . Then
The complete label-recovery algorithm applies to independent samples from , with the same explicit bounds of Theorem 4.1 and . It uses the positive sign and the empirical moments of ; it does not substitute uniform-shell moments or perform unnecessary uniform-shell sign counting. This includes the algorithmic clause of the lemma, not only its inequality.
Differences from the source:
- encoding: moments of the first one and two coordinates of an invariant law → averages over all coordinate choices and uniform finite-program witnesses for its classifier; reason: signed permutation invariance makes these the same moments; the positive sign avoids uniform-shell preprocessing
Preamble
import Definitions.Def_ZLIPPadding_Padding_Supplement_Reductions
Formal statement
namespace ZLIPPadding.Padding.Supplement
open scoped BigOperators ENNReal
theorem positive_fourth_moment :
(∀ (n m : ℕ) (μ : PMF (ZVec n)), shortRange n m →
ShellLaw m μ → SignedInvariant μ →
momentKappa m μ ≥ (m : ℝ)*(n+2-3*m)/((n : ℝ)*(n-1)) ∧
(m : ℝ)*(n+2-3*m)/((n : ℝ)*(n-1)) ≥ (m : ℝ)/(4*n) ∧
0 < (m : ℝ)/(4*n)) ∧
PositiveLabelRecovery := by sorry
end ZLIPPadding.Padding.Supplement
Source
Shengmao Jiang, STOC 2027 submission #496 (October 2026), printed p. 25 (PDF p. 26), Lemma 6.2