Section II, (39), p. 8 — max_r |x_r + a₂x_r² + … + a_kx_r^k| ≥ 1/k at x_r = cos(πr/k), k odd
ProvedQAOAE3Lin2.General.eq_39chebyshevmax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-inequality
Let be an odd positive integer and for . For all real ,
A polynomial with linear coefficient cannot be uniformly small on the Chebyshev extreme points. The paper cites it as Corollary 2.7 of Dinur–Friedgut–Kindler–O'Donnell and uses it to find a grid angle where the main term of (37) is large.
Formalization Note. The maximum over a finite set is stated as the existence of an attaining the bound. Both the absolute value and the oddness of are essential: for even the statement is false.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_39 (k : ℕ) (hk : Odd k) (a : ℕ → ℝ) :
∃ r ∈ Finset.range (k + 1), 1 / (k : ℝ) ≤
|Real.cos (Real.pi * r / k) + ∑ j ∈ Finset.Icc 2 k, a j * Real.cos (Real.pi * r / k) ^ j| := by sorry
end QAOAE3Lin2.General
Source
Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062v2, p. 8, Section II, (39) (citing Dinur, Friedgut, Kindler, O'Donnell, Corollary 2.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.