11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mark L. Stone Jun 26 '18 at 15:50
  • 1
    $\begingroup$ @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. $\endgroup$ – Arnold Neumaier Jun 26 '18 at 15:55
  • 1
    $\begingroup$ 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}}$. $\endgroup$ – Paata Ivanishvili Jun 26 '18 at 19:35
  • 1
    $\begingroup$ @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}$ $\endgroup$ – Paata Ivanishvili Jun 27 '18 at 16:09
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Paata Ivanishvili Jun 27 '18 at 20:13
9
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I have added a few remarks. $\endgroup$ – Iosif Pinelis Jun 27 '18 at 15:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Arnold Neumaier Jun 26 '18 at 19:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you Paata. I will study your answer at a later time (unfortunately, cannot do it right now). $\endgroup$ – Iosif Pinelis Jul 6 '18 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.