Theorem 4.1 — Statistical recovery of the complete orbit label
OpenZLIPPadding.Padding.Supplement.orbit_label_recoverycomputational-complexitylattice-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , integer , , and suppose the nonempty uniform shell has . For a prescribed and every , a uniform executable algorithm returns the multiset with probability at least . It uses two independent batches of positive integer sizes satisfying
The sign is determined by exact shell counting with integer operations. Remaining computation is polynomial in and input and sample representation lengths. The numerical contract uses all ordered eigenvalues to error at most , with multiplicities and zeros, and reports failure at zero estimated contrast. The hidden basis and true label are never inputs. This is a companion theorem to the padding goal.
Differences from the source:
- encoding: a randomized algorithm consuming two independent batches → a deterministic finite program on the two supplied batches, then its law under independent iid batches; reason: all randomness is in the oracle samples; exact rational encoding and spectral rounding recover the identical multiset
Preamble
import Definitions.Def_ZLIPPadding_Padding_Supplement_Reductions
Formal statement
namespace ZLIPPadding.Padding.Supplement
open scoped BigOperators ENNReal
theorem orbit_label_recovery :
∃ (P : Program) (c d C : ℕ), LabelProgram P c d ∧ 0 < C ∧
(∀ n m, 2 ≤ n → 1 ≤ m →
((countLog n m).operations : ℝ) ≤ (C : ℝ)*n*m*Real.sqrt m) ∧
∀ (n m : ℕ) (μ : PMF (ZVec n)) (kap0 : ℝ), 2 ≤ n → 1 ≤ m →
UniformOn μ (shell n m) → 0 < kap0 → kap0 ≤ |shellKappa n m| →
LabelGuarantee P c d false n m μ kap0 := by sorry
end ZLIPPadding.Padding.Supplement
Source
Shengmao Jiang, STOC 2027 submission #496 (October 2026), printed p. 16 (PDF p. 17), Theorem 4.1