Lemma 6.13 —
ProvedQuantumXoP.Security.lemma_6_13fourier-analysisp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-cryptographyxor-of-permutations
For real numbers ,
It bounds the cross terms in the degree-6 computation (Lemma 6.14).
Formalization Note is natural-number subtraction; at both sides are .
Differences from the source:
- generalization: r is the XoP parameter, r ≥ 2 (standing assumption of §6) → every natural number r; reason: the statement specializes to every r ≥ 2
Preamble
import Mathlib
Formal statement
namespace QuantumXoP.Security
/-- Lemma 6.13 (p. 31): for `x, y ∈ ℝ`, `|(x + y)^r − x^r| ≤ r |y| (|x| + |y|)^{r−1}`. -/
theorem lemma_6_13 (r : ℕ) (x y : ℝ) :
|(x + y) ^ r - x ^ r| ≤ r * |y| * (|x| + |y|) ^ (r - 1) := by sorry
end QuantumXoP.Security
Source
Wonseok Choi, Minki Hhan, Junyoung Jang, Quantum Security of XOR of Permutations via Fourier Analysis, STOC 2027 submission #815 (October 2026), p. 31 (PDF p. 33), Lemma 6.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.