Low-Degree Polynomial Approximation of the Cross-Polytope

The degree law

• The degree law holds throughout 1≤t≤d, and degree of order d is necessary and sufficient for constant distortion, with a lower bound applying to all globally nonnegative forms.The matching construction is an SoS form, while the lower bound is representation-free.Source: §1 · pp. 2–3

How the obstruction is isolated

• Signed-permutation averaging and flat-point evaluation reduce every candidate to a support-size profile V(k)=k^-2tQ(k), where deg Q≤t and Q(0)=0.After u=1/k, Lagrange interpolation shows that the degree budget cannot independently flatten the profile across all support scales.Source: §1 · p. 3

How the matching form emerges

• Averaging even powers of sign-vector facet normals produces the matching symmetric form, whose extremal values on the ℓ1 sphere occur at a vertex and the diagonal.The construction reduces the upper bound to a Rademacher moment.Source: §1 · p. 3

Polarity as a stress test

• At t=⌈log2 d⌉, the cube has an SoS certificate of distortion at most 2, whereas the cross-polytope requires a different degree scale for prescribed distortion.The coordinate cube certificate suffices for this separation but is not claimed to be optimal; in B2, a quartic SoS form uses a negative mixed coefficient unavailable to coordinate fourth powers.Source: §1 · p. 4

General symmetric polytopes

• For general symmetric polytopes, weighted facet powers give a one-sided certificate with a concave boundary-floor objective and worst-direction oracles reducible to convex dual-norm problems.At degree two, the optimizers recover classical optimal design and the John ellipsoid.Source: §1 · p. 4

Scope of the facet model

• The facet-design certificate does not characterize the full SoS optimum: even a fully symmetric optimized facet design can miss it.The quartic example separates nonnegative mixtures of coordinate facet powers from the full SoS cone.Source: §1 · p. 4

Extensions to ℓp balls

• For ℓp balls, the weighted flat-profile obstruction yields the exact quadratic law, exact algebraic resonance points, and matching dimension exponents up to do(1) for fixed p<2 with log t=o(log d).Beyond the stated threshold, the argument does not predict the answer.Source: §1 · p. 4

2 Preliminaries

• The SoS cone is contained in the globally nonnegative-form cone, so a lower bound against all nonnegative forms also applies to SoS candidates.Barvinok’s construction is an SoS form, while the cross-polytope lower bound applies to the larger cone.Source: §2 · pp. 5–6
• The sandwich ratio is the maximum boundary value divided by the minimum, measuring the multiplicative loss between the body and the polynomial’s unit sublevel set.At degree two, the best sandwich factor is the ellipsoidal one.Source: §2 · p. 6
• The degree index specifies exact homogeneous degree 2t, so successive feasible classes are not literally nested.A monotone cumulative degree budget can instead be formed from the envelopes of the exact-degree bounds.Source: §2 · p. 6
• Facet-power forms built from weighted powers of facet normals provide an upper-bound certificate family, narrower than the full SoS class.Their sublevel sets can be viewed as inverse images of possibly degenerate ellipsoids under a degree-t Veronese map.Source: §2 · pp. 6–7
• For the cube, an explicit SoS certificate gives constant distortion at logarithmic degree, whereas the cross-polytope has order-d distortion at degrees four and six.The displayed cube quantity is an upper bound, not its exact full-cone distortion.Source: §2 · p. 7

3.1 The extremal cross-polytope

• For every fixed C > 1, degree 2t = Θ_C(d) is necessary and sufficient for either cross-polytope distortion to be at most C.The cross-polytope matches Barvinok’s universal SoS upper bound up to an absolute constant.Source: §3.1 · p. 8

3.2 The lower bound, in one variable

• Averaging over signed permutations and evaluating flat points reduces the lower-bound problem to a positive profile V(k) = k^-2t Q(k), with deg Q ≤ t and Q(0) = 0.Reciprocal-grid interpolation forces variation in this profile; the proof applies to the full cone of nonnegative forms.Source: §3.1 · p. 8, §3.2 · pp. 9–10

3.3 A same-degree contrast with the cube

• At t = ⌈log2 d⌉, the cube has a constant-distortion SoS certificate, while the polar cross-polytope still has diverging distortion and requires degree of order d for constant distortion.The comparison does not require knowing the cube’s exact optimum.Source: §3.3 · p. 10

3.4 An oracle max–min design

• The facet-design certificate maximizes a concave boundary floor, and its worst-direction oracle reduces to finitely many convex dual-norm problems.At t = 1, its optimizers recover D-optimal design and the symmetric John ellipsoid.Source: §3.4 · pp. 10–11
• An exact oracle gives additive ε-accuracy in O(max{1, log n}/ε^2) outer calls, but this does not bound the numerical cost or conditioning of the oracle.The optimized certificate neither minimizes the true ratio within the facet-power family nor characterizes the full SoS optimum; a symmetric quartic example has a strict gap.Source: §3.4 · p. 11

3.5 Extensions to ℓp balls

• For fixed p < 2 and log t = o(log d), both ℓp-ball distortions equal d^(1/p−1/2+o(1)).The argument does not determine the interior regime p > 2.Source: §3.5 · p. 12

4.1 Choosing the witness profile

• Signed-permutation averaging preserves nonnegativity and does not increase the sandwich ratio, allowing the lower-bound analysis to restrict to invariant forms.Invariant forms are combinations of products of even power sums, whose flat-point values depend only on support size.Source: §4.1 · pp. 12–13
• On flat points, every invariant degree-2t form has profile V(k) = k^-2t Q(k), where deg Q ≤ t and Q(0) = 0; its profile variation lower-bounds the form’s boundary ratio.The argument uses these d witness directions and does not claim that the form’s true extrema occur there.Source: §4.1 · p. 13

4.2 Weighted grid rigidity by interpolation

• Substituting u = 1/k turns the profile into a low-degree polynomial times a known weight, so its first t reciprocal-grid values control the value at 1/d.Weighted Lagrange interpolation yields the lower bound; strict positivity ensures sampled values are positive, and the proof does not inspect the nonnegativity certificate.Source: §4.2 · pp. 13–15

5.1 Averaging the facet orbit

• Averaging even powers of the sign-vector facet normals gives a symmetric form that is an SoS, and its boundary extrema occur at the diagonal and a vertex.The diagonal value reduces the construction’s analysis to a Rademacher moment.Source: §5.1 · pp. 15–16
• The Rademacher moment’s upper bound follows by Gaussian replacement, while retaining terms with t distinct indices each appearing twice gives its lower bound.Those collision-free terms number (2t −1)!! d↓t, and their 2t-th root supplies the gain over the quadratic approximation.Source: §5.1 · p. 16

5.2 Optimizing a restricted construction

• For general symmetric polytopes, the normalized facet-power construction has boundary ceiling one, so its certificate maximizes the concave minimum boundary value over facet weights.The maximum is attained and is strictly positive when the facet normals span the space.Source: §5.2 · pp. 16–18
• The worst-direction oracle reduces to n convex dual-norm problems, and an exact oracle yields additive ε-accuracy in O(max{1, log n}/ε^2) calls.The reduction uses homogeneity to replace boundary minimization with dual-norm evaluations.Source: §5.2 · pp. 17, 19
• At t = 1, the certificate’s maximizers are D-optimal designs, and the associated ellipsoid is the symmetric John ellipsoid.The result connects the quadratic case to classical ellipsoidal design.Source: §5.2 · pp. 17, 19
• The facet-design certificate is only one-sided: it bounds the floor of a restricted family and does not characterize the full SoS optimum.The analysis also replaces the actual boundary maximum by its upper bound of one.Source: §5.2 · pp. 17–18

5.3 What the facet model misses

• Signed-permutation symmetry alone does not make the facet-power certificate optimal over the full SoS cone, although the cross-polytope’s sign design is order-optimal there.The distinction is between exact optimality within the restricted family and order-optimality over the full cone.Source: §5.3 · p. 20
• For the square quartic, the best actual ratio in this facet-power family is 2^(1/4); its gap below is not caused by ceiling relaxation, since the boundary maximum is exactly one.A nonnegative mixture of coordinate facet powers cannot use a negative x2y2 coefficient, unlike the full SoS cone.Source: §5.3 · p. 20

• The lower-bound obstruction is representation-free: averaging and flat points reduce candidates to support-size profiles, and interpolation exposes the mismatch between d scales and degree t.The flat points need not contain every extremum; they suffice because invariant forms collapse to k^-2t Q(k), with deg Q ≤ t.Source: §6 · p. 21
• The weighted reciprocal-grid test applies when a symmetric body supplies an averaging group, support-indexed boundary representatives, and a profile V(k)=k^-αQ(k); α≥t then enables the interpolation bound.This is a diagnostic, not a universal theorem: finding a suitable orbit family is body-specific; for ℓp witnesses α=2t/p, locating p=2 as the stopping point.Source: §6 · p. 21
• The facet-weight program is a one-sided certificate, not the full SoS optimum: its ceiling relaxation and restriction to facet powers can each create slack.For the square, the boundary maximum is exactly one, yet the quartic example still gives a strict gap from restricting the form family.Source: §6 · pp. 21–22
• For the regular hexagon, the boundary-floor optimizer has boundary maximum 2/3, so the ceiling relaxation can itself create slack.At t=1 the averaged quadratic is optimal over the full quadratic cone, isolating the slack to the ceiling relaxation.Source: §6 · pp. 21–22
• The sign design has asymptotic constant e/2 while the interpolation lower bound has constant 1/(2e), leaving a factor-e gap with two plausible sources.A sharper grid inequality could improve the lower bound; mixed SoS interactions could improve the construction, and the proof does not determine which matters.Source: §6 · p. 22
• The exact cube optimum remains open: a coordinate certificate separates the cube from the cross-polytope but need not be optimal, as the quartic example demonstrates.The missing control is over mixed invariant terms omitted by facet powers.Source: §6 · p. 22
• For p>2, the profile exponent crosses the numerator degree, so the present interpolation comparison no longer controls oscillation or predicts the answer.The text identifies 2<p<4 at quartic degree as a concrete target requiring a replacement for the exponent-sensitive step.Source: §6 · p. 22
• The certificate algorithm has an additive outer-iteration guarantee, but inner convex programs may dominate runtime and the objective transformation is ill-conditioned when its optimum is small.A relative-error guarantee would require a quantitative lower bound on the optimum and an oracle whose complexity tracks the induced norm's conditioning.Source: §6 · p. 22

• Both nonnegative-form and SoS distortion have order Θ(√(d/t)), with the cross-polytope matching the universal symmetric-body upper bound up to constants.The lower bound applies to the larger nonnegative cone, while the upper bound is supplied by an explicit SoS construction.Source: §A.1 · pp. 24–25
• For every fixed C>1, degree 2t=Θ_C(d) is necessary and sufficient for either distortion to be at most C.Source: §A.1 · pp. 24–25
• The cross-polytope lower bound applies to every globally nonnegative form, whereas the upper bound combines Barvinok’s theorem with the sign-design construction.Source: §A.1 · pp. 24–25

• The cube has an explicit logarithmic-degree SoS certificate for constant distortion, while the polar cross-polytope still has diverging distortion and needs degree of order d.Source: §A.2 · p. 25
• The comparison uses the cube certificate and the cross-polytope degree lower bound, without establishing the cube’s exact optimum.Source: §A.2 · p. 25

• When p=2j and j divides t, an exact sum-of-squares representation gives distortion one, the minimum possible for either polynomial cone.Source: §A.3 · pp. 25–26
• For fixed p<2 with log t=o(log d), both distortions equal d^(1/p−1/2+o(1)).The lower bound comes from profile interpolation; the upper bound does not recover its t-dependence and needs an ℓp-adapted sign design.Source: §A.3 · pp. 25–26
• At t=1, both cones have exact distortion d^|1/2−1/p|, because averaging reduces every quadratic to a scalar multiple of the Euclidean form.Source: §A.3 · p. 26
• The three cases are distinct mechanisms, not samples from one smooth formula, and for p>2 even the correct power of d away from resonance remains open.Source: §A.3 · p. 26