{"ID":22919237,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17614","arxiv_id":"2609.17614","title":"Low-Degree Polynomial Approximation of the Cross-Polytope","abstract":"We determine the degree-distortion tradeoff for polynomial approximation of the $d$-dimensional cross-polytope $B_1^d$. For every $1\\le t\\le d$, every globally nonnegative degree-$2t$ form that is positive away from the origin has multiplicative sandwich distortion at least $(2e)^{-1/2}\\sqrt{d/t}$, while an explicit sum-of-squares (SoS) form achieves distortion at most $(2e)^{1/2}\\sqrt{d/t}$. Hence both the nonnegative-form and SoS optima are $Θ(\\sqrt{d/t})$, and degree $Θ(d)$ is necessary and sufficient for constant distortion. The lower bound is representation-free. Averaging over signed permutations and evaluating on flat points of the $\\ell_1$ sphere reduces every candidate to a support-size profile $V(k)=k^{-2t}Q(k)$ with $°Q\\le t$ and $Q(0)=0$. After the substitution $u=1/k$, Lagrange interpolation shows that this degree budget cannot keep the profile nearly constant across $d$ support scales. A matching SoS construction averages even powers of sign-vector facet normals and reduces the upper bound to a Rademacher moment. We also isolate a weighted reciprocal-grid lemma, derive consequences for $\\ell_p$ balls, and contrast the polar cube. For a general symmetric polytope, weighted facet powers yield a one-sided certificate whose boundary-floor objective is concave and whose worst-direction oracle reduces to convex dual-norm problems; at degree two, its optimizers recover classical optimal design and the John ellipsoid. This is an oracle-model certificate optimization, not an end-to-end complexity result or a characterization of the full SoS optimum.","short_abstract":"We determine the degree-distortion tradeoff for polynomial approximation of the $d$-dimensional cross-polytope $B_1^d$. For every $1\\le t\\le d$, every globally nonnegative degree-$2t$ form that is positive away from the origin has multiplicative sandwich distortion at least $(2e)^{-1/2}\\sqrt{d/t}$, while an explicit su...","url_abs":"https://arxiv.org/abs/2609.17614","url_pdf":"https://arxiv.org/pdf/2609.17614v1","authors":"[\"Xiaoyu Li\"]","published":"2026-09-14T14:42:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}