norm inequalities

Question

Let $p>2$ . I'd like to know the best possible lower and upper bound for $\|x\|_p$ given that $x\in R^n$ and $\|x\|_1$ , $\|x\|_2$ , and $\|x\|_\infty$ have fixed values.

It is well-known that $\|x\|_\infty\le \|x\|_p\le \|x\|_2^{2/p}\|x\|_\infty^{1-2/p}~~~ \Big[\le \|x\|_2\le \|x\|_1\Big].$ But these bounds cannot be sharp when an arbitrary value of $\|x\|_1$ is specified.

In case no closed form solution is known, I'd also appreciate pointers to explicit suboptimal bounds that are stronger than the stated ones. For example, I conjecture that a bound of the form $\|x\|_p\le C_p\|x\|_2\Big(\frac{\|x\|_\infty}{\|x\|_1}\Big)^r$ should hold with $r=(p-2)/(2p-2)$ and a constant $C_p$ depending on $p$ only, but I don't have a proof of such an inequality.

As I'm sure you know, the sharpest lower and upper bounds on $|x|p $given particular values of$ |x|_1, |x|_2, |x||\infty $can be obtained by numerical global optimization: minimizing (for lower bound) and maximizing (for upper bound)$ |x|p $subject to$ x\in R^n $and the values of$ |x|_1, |x|_2, |x||\infty$. I suppose you want an analytical bound? — Mark L. Stone, Jun 26 '18 at 15:50
@MarkL.Stone: Global optimization gives bounds for specific values of $p,n$ and the norms, but for each choice a different optimization problem must be solved. I want closed formulas. — Arnold Neumaier, Jun 26 '18 at 15:55
I think the upper bound is $\frac{(|x|{2}^{2}-|x|{1}^{2})|x|{\infty}^{p}+(|x|{\infty}|x|{1}-|x|{2}^{2})^{p}(|x|{\infty}-|x|{1})^{2-p}}{(|x|{\infty}-|x|{1})^{2}+|x|{2}^{2}-|x|{1}^{2}}$. — Paata Ivanishvili, Jun 26 '18 at 19:35
And the lower bound seems to be $|x|{2}^{2(p-1)}|x|{1}^{2-p} $. Both are independent of$ n $and sharp. These are bounds for$ |x|{p}^{p} $(not for$ |x|{p}$). — Paata Ivanishvili, Jun 26 '18 at 20:01
Here by $|x|{q} $I mean normalized$ \ell{q} $norm, i.e.,$ |x|{q} = \left( \sum{j=1}^{n}|x_{j}|^{q}/n\right)^{1/q}$ — Paata Ivanishvili, Jun 26 '18 at 22:15
@Thomas Dybdahl Ahle, lower bound follows from Holder's inequality: $|x|{2}\leq |x|{1}^{\theta}|x|_{p}^{1-\theta} $where$ \theta $solves the equation$ \frac{\theta}{1}+\frac{1-\theta}{p}=\frac{1}{2} $, i.e.,$ \theta =\frac{p-2}{2(p-1)}$ — Paata Ivanishvili, Jun 27 '18 at 15:55
@Thomas Dybdahl Ahle, for the upper bound the claim is that given $A>0$ the function $B(x,y) = \frac{(y-x^{2})A^{p}+(Ax-y)^{2}(A-x)^{2-p}}{(A-x)^{2}+y-x^{2}}$ is concave in the domain $\Omega_{A}={(x,y), :, Ax\geq y\geq x^{2}, , x\geq 0}$ , with the boundary condition $B(t,t^{2})=t^{p}$ .If so, then take any $z=(z_{1},\ldots, z_{n})$ , with $|z|{\infty}\leq A $. WLOG$ z{j}\geq 0 $. Then By Jensen we have$ \frac{1}{n}\sum_{j=1}^{n}z_{j}^{p} = \frac{1}{n}\sum_{j=1}^{n}B(z_{j},z_{j}^{2})\leq B(|z|{1},|z|{2}^{2}) $. Again here I mean normilized$ |z|{q} $norms. Put$ A=|z|{\infty}$ — Paata Ivanishvili, Jun 27 '18 at 16:09
To verify concavity of $B$ in $\Omega_{A}$ it is a little bit tricky, and it depends which tools one is allowed to use. First one can verify that $B_{xx}B_{yy}-B_{xy}^{2}=0$ , i.e., the graph of $B$ has zero Gaussian curvature (and in fact this is the way $B$ was constructed initially as a solution of homogeneous Monge--Ampere equation with the boundary condition $B(t,t^{2})=t^{p}$ ). Now to finish proving concavity of $B$ it remains to verify only $B_{yy}\leq 0$ . One can also do it in a different way as well. — Paata Ivanishvili, Jun 27 '18 at 16:18
@Paata : I think your comments are interesting, in that the Monge--Ampere eq. may provide a useful method. However, I don't see how it can produce the optimal upper bound in this particular setting. Indeed, it seems that your instance of Jensen's inequality turns into the equality only if all the $z_j$ 's are the same, and then necessarily $|z|1=|z|_2=|z|\infty $. On the other hand, your upper bound coincides with the one in my answer (given the assumption$ |x|_\infty=1$), and I wonder how this can be. Also, how do you conclude that your bound is optimal? — Iosif Pinelis, Jun 27 '18 at 19:05
@Paata : Also, there seems to be a typo in your definition of $B$ -- your boundary condition does not check for me. — Iosif Pinelis, Jun 27 '18 at 19:15
@Iosif, regarding typo, yes it should be $B(x,y)=\frac{(y-x^{2})A^{p}+(Ax-y)^{p}(A-x)^{2-p}}{(A-x)^{2}+y-x^{2}}$ . In other words, B is just the upper bound where instead of $|x|{1}=x $,$ |x|{2}^{2}=y $, and$ A=|x|_{\infty}$. — Paata Ivanishvili, Jun 27 '18 at 19:54
@Iosif, regarding optimality, $z_{j}$ being the same that is not necessary for the equality cases. For example, $B$ is linear along a certain family of line segments, $\ell_{c}:={ t(c,c^{2})+(1-t)(A,A^{2}), t\in [0,1]}$ where $c$ is any fixed number $c \in [0,A]$ . So we can have equalities if and only if when the points $(z_{j}, z_{j}^{2})$ belong to $\ell_{c}$ for some fixed $c$ . I would agree with you if $B$ were strictly convex, but it is not! — Paata Ivanishvili, Jun 27 '18 at 20:02
The graph of $B$ represents the upper boundary of the convex hull of the 3D curve $(t,t^{2}, t^{p})$ , $t \in [0,A]$ . Just by definition this is exactly $B(p,q)=\sup_{x} { |x|{p}^{p}, ; (|x|{1}, |x|{2}^{2})=(p,q), |x|{\infty}\leq A} $. And since by Caratheodory any point of the convex hull is the convex combination of$ 3 $points of its extreme points (This justifies Robert Israerl's guess), then extremizers PDF is the sum of at most 3 delta masses. But in this case$ 2 $is enough because$ B $happens to be linear on$ \ell_{c} $,$ c\in [0,A] $which folliates$ \Omega_{A}$. — Paata Ivanishvili, Jun 27 '18 at 20:13
@Paata : Thank you for your responses. At this point, I have just two related questions: (i) How do you prove that the graph of $B$ is the upper boundary of the convex hull and (ii) precisely what role does the Monge--Ampere equation play in that proof? Also, I think your comments certainly deserve to be presented as a formal answer, and that may even be preferable. — Iosif Pinelis, Jun 28 '18 at 01:41
@Iosif, if you ask why $B(p,q)=\sup_{x}{ |x|{p}^{p}, (|x|{1}, |x|{2}^{2})=(p,q), , |x|{\infty}\leq A} $is this upper boundary of the convex hull of the 3D curve$ (t,t^{2},t^{p})$, then it follows, for example, from Theorem 1 in https://arxiv.org/pdf/1402.4690.pdf — Paata Ivanishvili, Jun 30 '18 at 03:47
@Iosif, if you ask why this explicit formula that I wrote on $B(x,y)$ represents the upper boundary of the convex hull of $(t,t^{2},t^{p})$ , then here is the claim that needs to be proved: Let $\gamma(t)=(t,f(t),g(t))$ for $t \in [0,1]$ be a smooth 3D curve, so that tha graph $(t,f(t))$ is strictly convex in $\mathbb{R}^{2}$ . Assume that the curvature of $\gamma$ never vanishes, and the torsion is nonnegative. Then the surface ${s(c,f(c),g(c))+(1-s)(1,f(1),g(1)), , a \in [0,1],, c \in [0,1]}$ represents the upper boundary of the convex hull of the curve $\gamma$ . — Paata Ivanishvili, Jun 30 '18 at 03:52
@Iosif, Homogeneous Monge--Ampere, or the fact that the surfsace has the zero gaussian curvature helps a little bit, for example, it is known that such a surface consists by stright line segments, i.e., it is a developable surface, such that the gradient of the function (graph of which represents locally the surface) is constant along each such line. This helps to understand how to try to easily parametrize such surface in 2D, 3D, 4D, and in general in an arbitrary dimension. See for example https://projecteuclid.org/euclid.ijm/1348505534 to see how it helped to find Burkholder's function — Paata Ivanishvili, Jun 30 '18 at 04:01
@Paata : Thank you for your latest comments. Can you also provide a proof of "the claim [in your penultimate comment] that needs to be proved"? — Iosif Pinelis, Jul 04 '18 at 14:08
@Iosif, I will try to do it when I find some time since it is not a short computation. — Paata Ivanishvili, Jul 04 '18 at 15:20
@Iosif, see the answer below. I could not fit it in the comment. — Paata Ivanishvili, Jul 05 '18 at 20:58

Iosif Pinelis · Accepted Answer · 2018-06-27T15:36:40.940

By rescaling, without loss of generality (wlog) $\|x\|_\infty=1$ . Let $X$ be a random variable such that $P(X=|x_i|)=1/n$ for $x=(x_1,\dots,x_n)$ and all $i=1,\dots,n$ . Then $\begin{equation*} \|x\|_r^r=nm_r,\quad m_r:=EX^r, \end{equation*}$ for $r\ge1$ . Let us find the best possible bounds on $m_p$ in terms of $m_0=1,m_1,m_2$ ; these bounds can then be easily translated back in the terms of $\|x\|_r$ . Wlog $\begin{equation*} 0<m_1<\sqrt{m_2}<\sqrt{m_1}<1. \tag{1} \end{equation*}$ Everywhere here $0\le t,u\le1$ .

Lemma 1. $d_1(t):=(p-1) u^{p-2}t^2+(2-p) u^{p-1}t-t^p\le0$ , and $d_1(t)=0$ if $t\in\{0,u\}$ .

Lemma 2. $d_2(t):=c t^2+b t+a-t^p\ge0$ , and $d_2(t)=0$ if $t\in\{u,1\}$ , where $\begin{align*} a&:=\frac{(p-2) u^{p+1}-(p-1) u^p+u^2}{(1-u)^2}, \\ b&:=\frac{p u^{p-1}-(p-2) u^{p+1}-2 u}{(1-u)^2}, \\ c&:=\frac{-p u^{p-1}+(p-1) u^p+1}{(1-u)^2}. \end{align*}$

These lemmas will be proved at the end of this answer.

It follows from Lemma 1 that $\begin{equation*} 0\ge Ed_1(X)=(p-1) u^{p-2}m_2+(2-p) u^{p-1}m_1-m_p, \tag{2} \end{equation*}$ and this inequality turns into the equality if $u=u_*:=m_2/m_1$ and $P(X=u_*)=m_1^2/m_2=1-P(X=0)$ ; in view of (1), such a r.v. $X$ exists, and $u_*\in(0,1)$ . So, substituting $u=u_*$ into (2), we have the best possible lower bound on $m_p$ : $\begin{equation} m_p\ge m_1(m_2/m_1)^{p-1}. \end{equation}$

Similarly, it It follows from Lemma 2 that $\begin{equation*} 0\le Ed_2(X)=c m_2+b m_1+a-m_p, \tag{3} \end{equation*}$ and this inequality turns into the equality if $u=u_{**}:=(m_1-m_2)/(1-m_1)$ and $P(X=u_{**})=(1-m_1)/(1-u_{**})=1-P(X=1)$ ; in view of (1), such a r.v. $X$ exists, and $u_{**}\in(0,1)$ . So, substituting $u=u_{**}$ into (3), we have the best possible upper bound on $m_p$ : $\begin{equation} m_p\le \frac{m_2-m_1^2+(1-m_1)^2 (\frac{m_1-m_2}{1-m_1})^p}{1+m_2-2 m_1}. \end{equation}$

It remains to prove Lemmas 1 and 2.

Proof of Lemma 1. We have $d_1(0)=0=d_1(u)=d'_1(u)$ . Also, $d''_1(t)=(p-1) (2 u^{p-2} - p t^{p-2})$ switches in sign from $+$ to $-$ (only once) as $t$ increases from $0$ to $1$ , and the switch point is $<u$ . Now Lemma 1 follows. $\Box$

Proof of Lemma 2. We have $\begin{align*} d''_2(t)(1-u)^2u &=2 \left((p-1) u^{p+1}-p u^p+u\right)-(p-1) p (1-u)^2 u t^{p-2} \\ &>2 \left((p-1) u^{p+1}-p u^p+u\right)-(p-1) p (1-u)^2 u^{p-1} \\ &=:f(u) \end{align*}$ if $0<t<u$ . We have $\begin{equation} f''(u)=(p-2) (p-1) p (1-u) u^{p-3} ((p+1)u-(p-1)), \end{equation}$ so that $f''(u)$ switches in sign from $-$ to $+$ (only once) as $u$ increases from $0$ to $1$ . Also, $f(0)=f(1)=f'(1)=0$ . So, $f>0$ and hence $d''_2(t)>0$ if $0<t<u$ . Also, clearly $d_2$ has at most one inflection point. Also, $d_2(1)=0=d_2(u)=d'_2(u)$ . Now Lemma 2 follows. $\Box$

Remark 1. The lower bound on $\|x\|_p$ or, equivalently, on $m_p$ , is an easy corollary of Hölder's inequality or, equivalently, of the log-convexity of $\|x\|_r$ in $r$ . However, in this case, it seemed to make sense to use a similar approach to both the lower bound and (the much more difficult) upper bound.

Remark 2. The bounds in terms of $m_r$ seem more natural than those in terms of $\|x\|_r$ (even though these two kinds of bounds are very easy to translate into each other). One reason for this preference is that restrictions (1) when translated into the $\|x\|_r$ terms will contain $n$ . Moreover, the restrictions $m_1<\sqrt{m_2}$ and $\sqrt{m_1}<1$ in (1), when translated into the $\|x\|_r$ terms, become rather restrictions on $n$ : $n>\|x\|_1^2/\|x\|_2^2$ and $n>\|x\|_1$ , respectively. In these remarks, it is still assumed that $\|x\|_\infty=1$ .

Remark 3. The lower bound on $m_p$ , when translated into the $\|x\|_r$ terms, is free of $n$ : $\begin{equation} \|x\|_p^p\ge\|x\|_2^{2p-2}/\|x\|_1^{p-2}. \end{equation}$

However, if one insists on a free of $n$ upper bound on $\|x\|_p$ in terms of $p$ , $\|x\|_1$ , and $\|x\|_2$ only, then the bound cannot be substantially better than the trivial upper bound given by the inequality $\|x\|_p^p\le\|x\|_2^2$ , as in the first display in the OP. Indeed, we have

Proposition 1. Suppose that $\begin{equation} \|x\|_p\le F(\|x\|_1,\|x\|_2^2) \end{equation}$ for all vectors $x$ , where the function $F=F_p$ is continuous (and does not depend on $n$ ). Then $\begin{equation} F(A,B)\ge B^{1/p} \end{equation}$ for all natural $B$ and all real $A>B$ .

The restriction $A>B$ corresponds to the restriction $\sqrt{m_2}<\sqrt{m_1}$ in (1).

Proof of Proposition 1. Take indeed any natural $B$ and any real $A>B$ . For natural $n>A$ , let $y=(y_1,\dots,y_n)$ , where $y_1=\dots=y_B=1$ and $y_{B+1}=\dots=y_n=\frac{A-B}{n-B}[\in(0,1)]$ . Then $\|y\|_1=A$ , $\|y\|_2^2\to B$ , $\|y\|_p^p\to B$ , and hence $\begin{equation} B^{1/p}\leftarrow\|y\|_p\le F(\|y\|_1,\|y\|_2^2)\to F(A,B) \end{equation}$ as $n\to\infty$ . $\Box$

In particular, it follows from Proposition 1 that the conjecture $\|x\|_p\le C_p\|x\|_2\Big(\frac{\|x\|_\infty}{\|x\|_1}\Big)^r$ with $r=(p-2)/(2p-2)$ , proposed by the OP, is false in general. This can also be seen directly by letting $x_i=1$ for all $i=1,\dots,n$ .

I have added a few remarks. – Iosif Pinelis Jun 27 '18 at 15:37 — Iosif Pinelis, Jun 27 '18 at 15:37

score 2 · Answer 2 · answered Jun 26 '18 at 18:29

A likely candidate for the optimal solution is when the $x_i$ take $3$ different values, say $x_i = a$ for $i=1 \ldots n_1$ , $b$ for $i=n_1+1 \ldots n_1 + n_2$ , $\|x\|_\infty$ for $i=n_1+n_2+1 \ldots n$ , where $n_i \ge 0$ , $n_1 + n_2 \le n$ , and $a$ and $b$ must satisfy
$\eqalign{ n_1 a + n_2 b + (n-n_1-n_2) \|x\|_\infty &= \|x\|_1\cr n_1 a^2 + n_2 b^2 + (n-n_1-n_2) \|x\|_\infty^2 &= \|x\|_2^2\cr 0 \le a,b &\le \|x\|_\infty }$ For given $n, n_1, n_2, \|x\|_1, \|x\|_2, \|x\|_\infty$ , this will determine $a$ and $b$ (up to interchange) as the roots of a quadratic, when that quadratic has two roots in the interval $[0, \|x\|_\infty]$ . Which $n_1$ and $n_2$ give the maximum or minimum value of $\|x\|_p$ will likely vary.

For large $n$ I rather expect (based on an analysis of the Kuhn-Tucker conditions) something of your form, but with $n-n_1-n_2$ replaced by a smaller number $n_3$ . — Arnold Neumaier, Jun 26 '18 at 19:16

score 1 · Answer 3 · answered Jul 05 '18 at 20:57

This answers the question of Iosif that was asked in comments (see comments under OP).

Theorem Let $\gamma(t)=(t,f(t),g(t)) : [0,1] \to \mathbb{R}^{3}$ be a space curve such that $f''>0$ , and the torsion of $\gamma$ is positive, then the surface parametrized as $P(s,t)=s\gamma(t)+(1-s)\gamma(1)$ , $(s,t) \in [0,1]^{2}$ represents the upper boundary of the convex hull of the curve $\gamma$ .

Since the surface consists of the line segments $[\gamma(t),\gamma(1)]$ , $t \in [0,1]$ ; and $P(1,t)=\gamma(t)$ , therefore it is enough to show that the surface is concave. To prove the latter fact one may try to compute the first and the second fundamental forms of a surface given in a parametric way. One obtains certain long expressions and it is not clear to me right now how to say something about their signs, however, I would be interested to see if one can push this path until the end.

The proof of the concavity of $P(s,t)$ that I knew involved plenty of computations in the spirit of Section 3 (see the reference below). Here I will present a short argument of Pavel Zatitskiy.

Proof: We need to prove that for any point $t_{0}\in [0,1)$ , one can draw a supporting hyperplane $T$ to the surface $P$ such that $T$ contains the segment $[\gamma(t_{0}),\gamma(1)]$ . Let us subtract from $g$ a linear combination of $f(t),t,1$ so that the new function $h(t)=g(t)-c_{1}f(t)-c_{2}t-c_{3}$ would satisfy the properties: $h(t_{0})=h'(t_{0})=h(1)=0$ . Such linear combination exists for example beacuse the vectors $(1,f'(t_{0})), (f(t_{0})-f(1),t_{0}-1)$ are linearly independent. So what we did so far is that we translated and rotated the picture so that our hypothetical tangent plane $T$ to be horizontal just for convenience. Thus it is enough to show that $h\leq 0$ on $[0,1]$ .
Next, positivity of the torsion of $\gamma$ means that $f''g'''-f'''g''>0$ , i.e., $g''/f''$ is increasing. This in partiuclar means that $h''/f''$ is increasing. Since $f''>0$ this implies that $h''$ changes sign from - to + at most once, i.e., $h$ is concave and then convex. We need to check that the point $t_{0}$ lies in the domain where $h$ is concave, i.e., $h''(t_{0})<0$ (this should follow from the initial conditions on $h$ ). Then we obtain that $h$ is concave on a certain segment $[0,t_{1}]$ , and then convex on $[t_{1},1]$ , in addition $t_{0}<t_{1}$ . Using the facts that $h(t_{0})=h'(t_{0})=h(1)=0$ we obtain the inequality $h\leq 0$ on $[0,1]$ . $\square$

Remark 1: For the curve $\gamma(t)=(t,t^{2},t^{p})$ , $t\in [0,A]$ , since $\tau_{\gamma}>0$ , the theorem immediately gives the concavity of $P(s,t)$ , which explicity can be rewritten as the graph of the function $B(x,y)=\frac{(y-x^{2}) A^{p}+(Ax-y)^{p}(A-x)^{2-p}}{(A-x)^{2}+y-x^{2}}, \quad p\geq 2,$ in the domain $\Omega_{A} = \{(x,y)\, :\, Ax \geq y \geq x^{2},\, x\geq 0\}$ with the boundary condition $B(t,t^{2})=t^{p}$ . This gives the sharp upper bound in OP. Indeed, take any $z=(z_{1},\ldots, z_{n})$ with $\|z\|_{\infty}\leq A$ . WLOG $z_{j}\geq 0$ . Let $\|z\|^{q}_{q}:=(1/n)\sum_{j=1}^{n}z^{q}$ , then $\|z\|_{p}^{p}=\frac{1}{n}\sum_{j=1}^{n}z_{j}^{p} = \frac{1}{n}\sum_{j=1}^{n}B(z_{j},z_{j}^{2})\leq B(\|z\|_{1}, \|z\|_{2}^{2}) =\frac{(\|z\|_{2}^{2}-\|z\|_{1}^{2})\|z\|_{\infty}^{p}+(\|z\|_{\infty}\|z\|_{1}-\|z\|_{2}^{2})^{p}(\|z\|_{\infty}-\|z\|_{1})^{2-p}}{(\|z\|_{\infty}-\|z\|_{1})^{2}+\|z\|_{2}^{2}-\|z\|_{1}^{2}}.$

Remark 2: The theorem, in particular, gives the positive answer to When is the convex hull of two space curves the union of lines? in the case of a curve discussed in the theorem. We verified the upper boundary. The lower boundary of the convex hull will be $s\gamma(0)+(1-s)\gamma(t)$ , $[s,t]\in [0,1]^{2}$ by the same reasons. And then it is not difficult to see that everythign between upper and lower boundary can be filled out also by the stright line segments

Ivanisvili, Paata, Inequality for Burkholder’s martingale transform, Anal. PDE 8, No. 4, 765-806 (2015). ZBL1341.60031.

Thank you Paata. I will study your answer at a later time (unfortunately, cannot do it right now). — Iosif Pinelis, Jul 06 '18 at 01:06

norm inequalities

3 Answers3