Low-Degree Polynomial Approximation of the Cross-Polytope

Abstract

How much approximation power does polynomial degree buy for a symmetric convex body? Barvinok’s lifted ellipsoid construction shows that degree 2t always suffices for distortion O(√(d/t)) when t ≤ d, but the construction itself does not identify a body that forces this curve throughout the degree range. We show that the cross-polytope does. If κ_t denotes the optimum over positive sum-of-squares forms and κ_t^nn the optimum over all globally nonnegative forms, then (1/√(2e))√(d/t) ≤ κ_t^nn(B₁ᵈ) ≤ κ_t(B₁ᵈ) ≤ √(2e)√(d/t), for 1 ≤ t ≤ d. Thus degree Θ(d) is necessary and sufficient for constant distortion, even when the lower-bound adversary may use any nonnegative form rather than an SoS certificate. The lower proof is representation-free. Signed-permutation averaging removes orientation but still leaves a large invariant algebra. Evaluating instead on the flat points of the ℓ₁-sphere makes every invariant monomial forget its partition structure and remember only the support size k. Every candidate then has the profile V(k) = k^(−2t)Q(k), where deg Q ≤ t and Q(0) = 0; after the substitution u = 1/k, Lagrange interpolation shows that this degree budget cannot keep the profile nearly level across d support scales. The matching SoS construction is dictated by the same symmetry: averaging the powers of the sign-vector facet normals gives the Rademacher form E_ε(εᵀx)^(2t). The mechanism also diagnoses what does and does not generalize. The polar cube has a constant certificate at logarithmic degree, and a two-dimensional quartic shows that its familiar coordinate certificate need not be optimal. For a general symmetric polytope, weighted facet powers yield a concave boundary-floor program whose worst-direction oracle reduces to convex dual-norm problems; at degree two it recovers classical optimal design and the John ellipsoid. This is an oracle-model certificate optimization, not an end-to-end complexity result. Finally, a weighted reciprocal-grid lemma for k^(−α)Q(k) yields the ℓ_p consequences and identifies p = 2 as the precise point where the interpolation mechanism stops.