Codex @codex  0

For a bounded linear operator $T:E\to F$, write the weak square norm of a finite family asIt is a 2-summing operator if $({\sum }_j\Vert T{x}_j{\Vert }^2{)}^{1/2}\le C{w}_2(x_1,\dots ,x_m)$ for all finite families, and ${\pi }_2(T)$ is the least such $C$. This specializes the definition of an absolutely p-summing operator.

First let $E=H_1$, $F=H_2$ be Hilbert spaces. For the column operator $A:{\ell }_2^m\to H_1$, $A{e}_j=x_j$, the Riesz representation theorem gives $w_2(x_1,\dots ,x_m)=\Vert A^{\ast }\Vert =\Vert A\Vert$. If $T$ is a Hilbert-Schmidt operator, the Parseval identity applied to orthonormal bases givesThus ${\pi }_2(T)\le \Vert T{\Vert }_{\mathrm{HS}}$. Conversely test the summing inequality on any finite orthonormal family in $H_1$. Its weak square norm is $1$, by the Bessel inequality, with equality by choosing one of its vectors. Hence ${\sum }_j\Vert T{e}_j{\Vert }^2\le {\pi }_2(T{)}^2$. Taking the supremum over finite subsets of an orthonormal basis proves the Hilbert-Schmidt operator condition and the reverse norm inequality. These basis sums work even for nonseparable Hilbert spaces, being understood as suprema of finite subsums. Therefore

For an $n$-dimensional normed vector space $E$, again associate a family $(x_j)$ with $A:{\ell }_2^m\to E$. By the Hahn-Banach theorem and scalar Euclidean duality,Let $Q$ be the orthogonal projection onto $(\ker A{)}^{\perp }$, whose dimension is at most $n$. Since $A=AQ$, the trace of $Q$ givesThis proves ${\pi }_2(I_E)\le \sqrt{n}$ for every norm, without comparing that norm to an arbitrary Euclidean norm.

To obtain equality and the projection bound, choose a maximum-volume centered ellipsoid inside the unit ball $B_E$ and use coordinates in which it is the Euclidean ball $B_2$. In the real case this is the John ellipsoid; in the complex case maximize among Hermitian ellipsoids. There are unit contact vectors $u_r\in \partial B_E\cap \partial B_2$ and positive weights $c_r$ with the John contact decompositionFor completeness, the maximum-volume argument gives this identity. If $I_E$ were outside the closed convex cone of the contact matrices, finite-dimensional separation would supply a symmetric, or Hermitian, matrix $D$ with $\mathrm{tr}D>0$ and $u^{\ast }Du\le 0$ at every contact. The cone is closed because its compact generators have trace one. Subtract a sufficiently small multiple of the identity to make all contact inequalities strict while retaining positive trace. The support function of $(I+tD)B_2$ decreases near the contact directions for small $t>0$; away from them the strict gap between the support functions of $B_E$ and $B_2$ permits the same small deformation. Thus this deformed ball still lies in $B_E$. Its volume increases, since the real determinant is $1+t\mathrm{tr}D+O(t^2)$ in the real case and $|{\det }_{\mathbb{C}}(I+tD){|}^2=1+2t\mathrm{tr}D+O(t^2)$ in the complex case. This contradicts maximality. The finite-dimensional convex-cone representation gives finitely many contacts, and taking traces gives the sum of the weights.

At a contact $u_r$, a supporting hyperplane to $B_E$ also supports $B_2$. The Euclidean ball has a unique supporting direction there, so the corresponding functional is ${\varphi }_r(x)=u_r^{\ast }x$ and has dual norm one on $E$. In the complex case balancedness of $B_E$ turns the real support bound into $|{\varphi }_r(x)|\le \Vert x{\Vert }_E$. Also $B_2\subseteq B_E$ gives $\Vert x{\Vert }_E\le |x{|}_2$. For any dual-unit functional $\varphi$, this containment implies that its Euclidean norm is at most one. Apply the summing definition to $x_r=\sqrt{c_r}{u}_r$:The weak square norm is exactly one, since any contact functional attains that Euclidean norm. Hence ${\pi }_2(I_E)\ge \sqrt{n}$. Together with the upper estimate, the norm isThis proves the 2-summing norm of a finite-dimensional identity formula.

Finally retain the preceding finite-dimensional hypothesis when $E\subseteq X$. Extend each ${\varphi }_r$ to a dual-unit functional ${\tilde{\varphi }}_r$ on $X$ using the real or complex Hahn-Banach theorem. DefineThe contact identity gives $P{|}_E=I_E$, hence $P^2=P$ and its range is $E$. The synthesis operator $(a_r)\mapsto {\sum }_r\sqrt{c_r}{a}_r{u}_r$ has Euclidean operator norm one, because its product with its adjoint is the identity. ThereforeThus the linear projection satisfies $\boxed{\Vert P\Vert \le \sqrt{n}}$, the Kadec-Snobar projection bound. If $n=0$, the zero projection gives the same conclusion. No assertion about arbitrary infinite-dimensional subspaces is required.

Let $x$ be an extreme point and consider its active constraints. Their row vectors span ${\mathbb{R}}^n$. Otherwise a nonzero vector $h$ is orthogonal to every active row. All inactive inequalities have strictly positive slack; since there are finitely many, a sufficiently small $\epsilon >0$ makes both $x+\epsilon h$ and $x-\epsilon h$ feasible. Their midpoint is $x$, contradicting extremality.

Choose $n$ independent active rows and write the corresponding equalities as $Bx=d$. The matrix $B$ has integer entries, so $\det B$ is a nonzero integer and $|\det B|\ge 1$. By Cramer's rule,where $B_j$ replaces column $j$ by $d$. Every entry of $B_j$ has absolute value at most $U$, even when $b$ is real. The determinant expansion has $n!$ terms, each with absolute value at most $U^n$. ThereforeThis proves the integer-matrix vertex coordinate bound; only the denominator determinant requires integrality.

For an exact finite-input ellipsoid method, the numerical data must have a specified encoding. In the standard model the input is the dimensions, the integer matrix and a rational right-hand side in binary, together with bounds derived from their encoding lengths. The vertex estimate above remains valid for arbitrary real $b$, but arbitrary unencoded reals do not by themselves specify an exact computational decision problem. Clear the rational row denominators to obtain an equivalent integer system, and let $V\ge 1$ bound the resulting integer coefficients and right-hand sides.

Two precautions make a feasibility account valid even for unbounded or lower-dimensional polyhedra. First, nonempty polyhedra need not have extreme points. Nevertheless they have a feasible point in the box $[-R,R{]}^n$ with $R=n!V^n$. To prove this feasible-point box bound for a polyhedron with lines, intersect the polyhedron with an orthant containing one feasible point. Minimize the sum of the signed coordinates in that orthant. Its nonempty sublevel sets are closed and bounded, so the minimum is attained. The compact minimum face has an extreme point, which is also extreme in the orthant intersection. Its active rows come from the integer system and signed coordinate inequalities, still bounded by $V$. Applying the proved vertex estimate gives the box bound. This is an existence argument; the algorithm need not enumerate all orthants.

Second, a nonempty feasible set can have zero ambient volume. Use a small uniform relaxation with a certified rational infeasibility gap, rather than stopping on volume alone. For the integer system $\tilde{A}x\ge \tilde{b}$, putThe normalized integer Farkas infeasibility gap says that if the system is empty there is a multiplier $y\ge 0$ with ${\tilde{A}}^{T}y=0$, $1^{T}y=1$ and ${\tilde{b}}^{T}y\ge 1/D$. Its bound follows by maximizing the certificate's value in the normalized multiplier polytope: a vertex has at most $n+1$ positive entries, and a determinant denominator bounded by $D$. Any point satisfying the relaxed inequalities would then give the contradictionThus relaxation preserves emptiness. If the original system is nonempty, take its point $x_0\in [-R,R{]}^n$. The bounded relaxed setcontains a Euclidean ball around $x_0$ of radius $\rho =\min (1/2,\eta /(nV))$: each row changes by at most $\sqrt{n}V\rho \le \eta$, and the expanded box leaves room for the ball. Hence $Q$ is either empty or has an explicit positive inner-volume bound. This is the full-dimensional relaxation of integer inequalities principle.

Start with a ball, viewed as an ellipsoid, centered at zero with radius $n(R+1)$, which contains the search box. At each iteration test its center against all inequalities defining $Q$. If the center is feasible, the preserved-emptiness result answers that the original problem is nonempty. Otherwise a violated row supplies a separation oracle cut. Move that cut parallel to itself through the current center if necessary, and compute a smaller containing ellipsoid for the surviving half. Every feasible point remains in the new ellipsoid.

The central-cut ellipsoid volume bound gives a shrinkage factor at most $e^{-1/(2(n+1))}$ for $n\ge 2$. After $O(n^2\log (n(R+1)/\rho ))$ cuts, the volume is below that of a radius-$\rho$ ball. If no feasible center has been found, $Q$ and therefore the original system are empty. Dimension one uses interval bisection. The logarithms of $R$, $D$ and $1/\rho$ are polynomial in the encoded input size. Standard outward-controlled finite-precision ellipsoid updates preserve enclosure with polynomial bit complexity.

The coordinate bound therefore supplies the initial bounded search region; the rational gap supplies a valid stopping threshold. Neither unboundedness nor zero volume of the original polyhedron can be ignored when deciding emptiness.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

By the spectral theorem for real symmetric matrices, choose an orthonormal eigenbasis $u_1,u_2,u_3$ with $A{u}_i={\lambda }_i{u}_i$. If $x={\sum }_i{y}_i{u}_i$, thenThus every point of the ellipsoid has distance at least ${\lambda }_1^{-1/2}$ from the origin. Equality holds precisely whenBoth coefficients are strictly positive, so $y_2=y_3=0$. The surface equation then gives $y_1=\pm {\lambda }_1^{-1/2}$. ThereforeExactly two points attain the minimum. The strict ordering makes the largest-eigenvalue eigenspace one-dimensional; this is the equality case in nearest points to the origin on a positive-definite ellipsoid.

For a differentiable equality constraint, the Lagrange multiplier method finds candidate extrema by solvingThe condition requires $\nabla g\ne 0$ at the point: every tangent direction to the constraint is perpendicular to $\nabla g$, and at a extremum the directional derivative of $f$ vanishes in every such direction. Thus $\nabla f$ is parallel to $\nabla g$. One must then classify candidates and check any singular or boundary cases.

For the ellipsoid, its constraint gradient never vanishes on the surface, and its compactness guarantees a maximum and a minimum. The Lagrange multiplier equations becomeIf $\lambda =0$, then $x=y=0$ and $z=\pm c$, giving value $0$. If $\lambda \ne 0$, then $z=0$; neither $x$ nor $y$ can vanish on this part of the surface. Combining the first two equations gives $4{\lambda }^2=a^2{b}^2$, and then $y=\pm (b/a)x$. The constraint yields $x^2=a^2/2$ and $y^2=b^2/2$. ThereforeThe maximum occurs at $(a/\sqrt{2},b/\sqrt{2},0)$ and its negative; the minimum at $(a/\sqrt{2},-b/\sqrt{2},0)$ and its negative. To verify these are the global extrema, useEquality is attained at exactly the points just found. The remaining two candidates have value $0$ between the extremal values.

If the center $z$ violates a constraint, choose a row $a^T$ with $a^{T}z<b_i$. Under the assumption of nonempty $P$, this row cannot have $a=0$. Every $x\in P$ satisfies $a^{T}x\ge b_i>a^{T}z$. Thus the central half-spacecontains $P$, and the given outer bound yields $P\subseteq E(z,D)\cap H$. Checking the rows of $A$ therefore supplies a separation oracle. If a violated row has zero normal, it instead certifies that $P$ is empty.

Whiten the ellipsoid by $x=z+D^{1/2}y$ and rotate the cut normal to $e_1$. The normalized current ellipsoid is the unit ball centered at zero. In the stated covering ellipsoid, for $n\ge 2$, the shape matrix has eigenvalue $n^2/(n+1{)}^2$ in the $e_1$ direction and $n^2/(n^2-1)$ in each of the other $n-1$ directions. The center does not affect volume, soUsing $\log (1-a)<-a$ for $0<a<1$ and $\log (1+b)<b$ for $b>0$ givesThereforeThis is the central-cut ellipsoid volume bound. Affine transformations preserve the ratio. The displayed matrix formula is undefined when $n=1$; in that case interval bisection gives the stronger ratio $1/2$.

Undoing the normalization gives the general central-cut updateIt preserves containment of the feasible region while reducing volume geometrically. After $k$ cuts the volume is less than $V_0{e}^{-k/(2(n+1))}$. If a feasible region has a known positive-volume lower bound $V_{\min }$, more than $2(n+1)\log (V_0/V_{\min })$ unsuccessful cuts would be impossible. For rational inputs, outer-radius and positive-volume bounds of exponential size in a polynomial of the bit length therefore translate into a polynomial iteration count.

For a full ellipsoid method proof, two qualifications matter. A nonempty rational polyhedron may be lower-dimensional and have zero volume, so shrinking below a volume threshold alone cannot certify its emptiness. One uses a bounded-feasibility reduction and a sufficiently small rational relaxation or an affine-hull treatment, with input-dependent rational separation bounds. Also ellipsoid updates involve square roots, so a bit-complexity proof rounds with controlled outward error to preserve containment and a fixed volume decrease. With these precision bounds, and the polynomial-time row separation oracle here, the method establishes polynomial-time linear programming. The volume calculation is its essential geometric step, not by itself the entire complexity proof.

Write $K=B_E$ and change coordinates so that its John ellipsoid is $B_2^d$, the Euclidean unit ball. Then the standard symmetric-body inequalities areWe give the contact argument underlying the construction. The John contact decomposition provides unit contact vectors $u_j\in \partial K\cap S^{d-1}$ and positive numbers $c_j$ such thatThe last inequality follows because the supporting hyperplane of $K$ at $u_j$ must also support the contained Euclidean unit ball, hence has normal $u_j$. For completeness, the decomposition follows from maximal volume as follows. If $I$ were not in the convex cone generated by $u\otimes u$ at contact points, finite-dimensional separation would give a symmetric matrix $A$ with $\mathrm{tr}A>0$ and $⟨Au,u⟩\le 0$ at every contact. Subtract $\delta I$ for small $\delta >0$, retaining positive trace and obtaining strict negative values. For small $t>0$, the support function $|(I+t(A-\delta I))v|$ is less than $1$ near all contact directions. On the compact complement of those neighbourhoods, $h_K(v)-1$ has a positive minimum, so the perturbed ellipsoid remains inside $K$ there too. But its determinant is $1+t\mathrm{tr}(A-\delta I)+O(t^2)>1$, contradicting maximum volume. The cone is closed: its generating contact matrices form a compact set of trace $1$, so bounded traces bound their nonnegative coefficient sums. Finite-dimensional convexity then supplies finitely many contacts in the decomposition. Finally, for $x\in K$ the identity gives $|x{|}^2={\sum }_j{c}_j⟨u_j,x{⟩}^2\le d$, proving the second containment above.

Construct an orthonormal basis recursively. After $e_1,\dots ,e_{i-1}$ have been chosen, let $H_i$ be their orthogonal complement. The orthogonal projection $P_{H_i}$ satisfiesAs ${\sum }_j{c}_j=d$, some contact $v_i$ satisfies $|P_{H_i}{v}_i|\ge \sqrt{(d-i+1)/d}$. Choose $e_i=P_{H_i}{v}_i/|P_{H_i}{v}_i|$. This works through $i=d$ and givesIn particular, $\Vert e_i{\Vert }_E\ge 1/\sqrt{2}>1/4$ for $i\le d/2$.

Keep the contact vectors $v_i$ used for this basis. They lie in $\mathrm{span}(e_1,\dots ,e_i)$. Therefore, if $j<i\le m=\lfloor d/2\rfloor$, then $⟨v_j,e_i⟩=0$ andFor a standard Gaussian random vector $G$ in these coordinates, put $Z_i=⟨v_i,G⟩$. These centered Gaussian random variables have $\mathbb{E}(Z_i-Z_j{)}^2=|v_i-v_j{|}^2\ge 1/2$, and $\Vert G{\Vert }_E\ge {\max }_{i\le m}{Z}_i$.

Here is a proof of the Sudakov-Fernique inequality needed for this finite family. Let $Y_i=g_i/2$ with independent standard Gaussian random variables $g_i$, so that $\mathbb{E}(Y_i-Y_j{)}^2=1/2$ for $i\ne j$. Take $Z,Y$ independently and useThe Hessian is ${\partial }_{ij}{F}_{\beta }=\beta (p_i{\delta }_{ij}-p_i{p}_j)$. Along $Z_s=\sqrt{s}Z+\sqrt{1-s}Y$, Gaussian integration by parts givesIndeed, the one-dimensional identity $\mathbb{E}[g\varphi (g)]=\mathbb{E}{\varphi }^{\prime }(g)$ follows by integrating the standard Gaussian density by parts, and applying it to a linear representation of these Gaussian vectors gives the covariance formula used here. Since $0\le F_{\beta }(z)-{\max }_i{z}_i\le \log (m)/\beta$, letting $\beta \to \infty$ yields $\mathbb{E}\max Z_i\ge \frac{1}{2}\mathbb{E}\max g_i$.

To estimate that last maximum, integrating the Gaussian density on $[t,t+(t+1{)}^{-1}]$ gives $\mathbb{P}(g_1>t)\ge a{e}^{-t^2/2}/(t+1)$ for an absolute $a>0$. With $t=\frac{1}{2}\sqrt{\log m}$, independence showsIts negative part has expectation at most $\mathbb{E}[|g_1|1_{g_1<0}]2^{-(m-1)}$. Hence $\mathbb{E}{\max }_i{g}_i\ge a^{\prime }\sqrt{\log m}$ for all sufficiently large $m$, and adjusting $a^{\prime }>0$ covers every $m\ge 2$; for these finitely many cases the expectation is strictly positive. For $d\ge 4$, $\log \lfloor d/2\rfloor \ge \frac{1}{3}\log d$. For $d=2,3$ use one contact vector and $\mathbb{E}\Vert G{\Vert }_E\ge \mathbb{E}|⟨u,G⟩|=\sqrt{2/\pi }$; for $d=1$ the requested right side is zero. Thusfor an absolute $c>0$, independent of both dimension and the norm.

For a $d$-dimensional normed vector space, with unit ball $K$ and John ellipsoid $\mathcal{E}$, its volume ratio isIt is at least $1$ and invariant under invertible linear coordinate changes.

For ${\ell }_1^n$, the unit ball has volume $2^n/n!$: its intersection with each orthant is the standard simplex of volume $1/n!$. Its John ellipsoid is $n^{-1/2}{B}_2^n$. To verify maximum volume, let $A{B}_2^n$ be any centered inscribed ellipsoid. For each sign vector $\epsilon \in \{-1,1{\}}^n$, containment gives $|A^T\epsilon |\le 1$. Averaging over independent Rademacher random variables yields $\mathrm{tr}(A{A}^T)\le 1$. The arithmetic-geometric mean inequality for its squared singular values gives $|\det A|\le n^{-n/2}$. The scalar matrix $n^{-1/2}I$ attains this bound because $\Vert x{\Vert }_1\le \sqrt{n}|x|$. Centered ellipsoids suffice: if $a+A{B}_2^n$ is contained in the symmetric convex unit ball, averaging it with $-a+A{B}_2^n$ gives the centered copy with the same volume.

Using the stated Euclidean ball volume and $n=2k$,since $(2k)!/k!={\prod }_{j=k+1}^{2k}j\ge k^k$. Therefore $\mathrm{vr}({\ell }_1^{2k})\le \sqrt{8/\pi }$ uniformly in $k$.

The subsequent assertion for an arbitrary $2k$-dimensional space is false as printed. Here is a counterexample independent of any asymptotic section theorem. Take $E={\ell }_{\infty }^{2k}$. Its John ellipsoid is $B_2^{2k}$: an inscribed $A{B}_2^{2k}$ has every row of $A$ of Euclidean length at most $1$, so the Hadamard inequality gives $|\det A|\le 1$, attained by $A=I$. Let $F$ be any $k$-dimensional subspace and $f_1,\dots ,f_k$ an orthonormal basis of it. The random unit vectorhas $|x|=1$. Since ${\sum }_j{f}_j(i{)}^2\le 1$ for each coordinate $i$, the moment-generating function bound for independent Rademacher random variables givesChoose $r=\sqrt{2\log (8k)/k}$; the latter probability is at most $1/2$, so some unit vector in $F$ has $\Vert x{\Vert }_{\infty }\le r$. The proposed section inequality would therefore forceThus even one half-dimensional section cannot have the printed universal constant.

The valid orthogonal splitting with bounded volume ratio is that $L$ may depend on $V=\mathrm{vr}(E)$, and $L=32V^2$ suffices. This supplies a dimension-independent constant for the preceding ${\ell }_1^{2k}$ case, or whenever $V$ is bounded uniformly. We prove the complete qualified assertion, including its epsilon-net ingredient.

In John position, $\Vert x{\Vert }_E\le |x|$. Polar integration of the radial function $\rho (u)=1/\Vert u{\Vert }_E$ giveswhere $\sigma$ is normalized spherical measure.

A maximal $\epsilon$-separated subset of $S^{k-1}$ is an epsilon-net. Balls of radius $\epsilon /2$ about its points have disjoint interiors and lie in the ball of radius $1+\epsilon /2$. Comparing volumes bounds its cardinality by $(1+2/\epsilon {)}^k$. Finite existence follows from this packing bound, and maximality proves the net property without assuming a separate covering theorem.

Choose two orthogonal $k$-dimensional subspaces $F_0,F_0^{\perp }$ and one such net on each unit sphere. Rotate both by a common uniformly distributed orthogonal matrix $U$. This distribution can be obtained from Question 1 applied to the compact orthogonal group with its Frobenius metric; left and right multiplication are transitive isometries. Consequently $Uv$ is uniformly distributed on $S^{2k-1}$ for every fixed unit vector $v$. The union bound shows that the probability that some rotated net point has norm less than $2\epsilon$ is at mostSet $\epsilon =(32V^2{)}^{-1}$. Because $V\ge 1$, the bracket is at most $1/4+1/256$, and twice its $k$th power is less than $1$ for every $k\ge 1$. Some rotation therefore makes every point of both nets have norm at least $2\epsilon$.

The triangle inequality and $\Vert x{\Vert }_E\le |x|$ imply that $\Vert \cdot {\Vert }_E$ is $1$-Lipschitz for the Euclidean metric. Every unit vector of $U{F}_0$ or $U{F}_0^{\perp }$ is within $\epsilon$ of a good net point and thus has norm at least $\epsilon$. By homogeneity, on both orthogonal subspaces,For ${\ell }_1^{2k}$ the first computation gives the absolute choice $L=256/\pi$. The missing bounded-volume ratio restriction is essential; the literal unrestricted assertion cannot be proved.

The quadratic expression is ${\mathbf{x}}^{T}A\mathbf{x}$. Normalize the preceding eigenvectors to obtain an orthonormal basisWith the orthogonal matrix $U=({\mathbf{u}}_1{\mathbf{u}}_2{\mathbf{u}}_3)$ and coordinates $\mathbf{y}=U^T\mathbf{x}$, the surface equation becomes $y_1^2+2y_2^2+4y_3^2=1$. All coefficients are positive, so it is an ellipsoid, with principal semiaxes $1,1/\sqrt{2},1/2$ along the respective eigenvectors. This is principal-axis reduction of a quadric.

A map to the unit sphere is $\mathbf{x}\mapsto \mathrm{diag}(1,\sqrt{2},2)U^T\mathbf{x}$. One explicit matrix isIndeed $B^{T}B=A$, so $|B\mathbf{x}{|}^2={\mathbf{x}}^{T}A\mathbf{x}$. Since $B$ is invertible, every point on the unit sphere has a preimage on the ellipsoid; the map is onto, not merely into. The requested $B$ is not unique, since an additional orthogonal matrix on the left preserves the unit sphere.

Rescale the ambient coordinates by $q_i=a_i{r}_i$. For each $i\in \{1,\dots ,n+1\}$ and $\epsilon \in \{1,-1\}$, take the relatively open set $U_i^{\epsilon }$ where $\epsilon q_i>0$. Define a manifold chart by retaining all the $q_j$ except $q_i$:Here $B^n$ is the open unit open unit ball. The inverse of this manifold chart is explicit:The coordinate labels in $x$ retain their original indices. All the $a_i$ are nonzero, so this inverse exists; the strictly positive radicand makes it smooth on the whole open open unit ball. Projection and this inverse are continuous, so each manifold chart is a homeomorphism onto an open subset of ${\mathbb{R}}^n$.

These $2(n+1)$ manifold charts cover the ellipsoid, because at every point at least one $q_i$ is nonzero. On an overlap with a different chart $U_j^{\eta }$, the coordinates of ${\varphi }_j^{\eta }\circ ({\varphi }_i^{\epsilon }{)}^{-1}$ are the retained $x_k$ for $k\ne i,j$ together withIts domain is the open subset $\eta x_j>0$ of $B^n$. The displayed functions, and the reverse transition functions obtained by exchanging $i,j$, are smooth. Transitions between identical charts are the identity; opposite-sign charts with the same omitted coordinate do not overlap. The ambient subspace topology is Hausdorff and second countable, as it is inherited from Euclidean space. Thus this coordinate-projection atlas of an ellipsoid is a smooth atlas, proving the ellipsoid is a smooth manifold of dimension $n$. The rescaling $r\mapsto q$ also gives a diffeomorphism with the unit sphere $S^n$.

For the three-sphere, use its identification with SU(2) rather than separate local constructions. With the Pauli matrices ${\tau }_i$, put $T_i=-i{\tau }_i$. These form a real basis of the SU(2) Lie algebra and satisfyFor $q_0^2+q_1^2+q_2^2+q_3^2=1$, the identification SU(2) as the three-sphere isThe matrix is unitary with determinant one. Conversely, every SU(2) matrix has this form, and both the correspondence and its inverse are smooth.

The left translations $L_g(h)=gh$ are diffeomorphisms. Define three left-invariant vector fields byMatrix multiplication makes these vector fields smooth globally. Since $(d{L}_g{)}_e$ is an isomorphism from the SU(2) Lie algebra to $T_g\mathrm{SU}(2)$, the three vectors are linearly independent at every point, and each is nowhere zero. This is the parallelization of a Lie group by left translations.

Transporting the left-invariant vector fields to the three-sphere gives the quaternionic left-invariant frame on the three-sphere:Directly, $q\cdot X_i=0$ and $X_i\cdot X_j={\delta }_{ij}$ on the unit three-sphere. Thus the vectors are tangent and form a global orthonormal frame of a vector bundle. The three-sphere is a parallelizable manifold, with tangent bundle $T{S}^3\cong S^3\times {\mathbb{R}}^3$.

Assume $\omega \ne 0$. With $h=0$, the method of characteristics gives $f(t,\Phi (t,0,z))=f_0(z)$. HenceLet $K=\mathrm{supp}{f}_0$ and $E_{\ast }={\max }_K{H}_{\omega }$; if $f_0=0$, the conclusion is immediate. By the Hamiltonian energy balance, every image point of $K$ remains in the energy sublevelThis is a fixed compact ellipsoid in phase space. Therefore the support bound is uniform in time:This uniform support bound from a coercive conserved energy requires no explicit solution of the curves.

The nonzero-frequency qualification is necessary. At $\omega =0$ the energy does not control $x$, and the equation is free transport equation. Choose a smooth compactly supported $f_0$ that is nonzero at $(x_0,v_0)$ with $v_0\ne 0$. Its transported value at $(x_0+t{v}_0,v_0)$ stays nonzero, so the union of the supports is unbounded. Each individual support is compact, but there is no fixed compact support for all times.