7
$\begingroup$

Consider $f:[0,1]^d \to \mathbb{R}$. Suppose that $f$ is $L$-Lipschitz w.r.t. the Euclidean norm. Can we provide an upper bound on $\|f\|_\infty$ in terms of $\|f\|_1 := \int_{[0,1]^d} |f(x)|dx$ ?

In dimension 1, I would think that the way to construct such a function $f$ with as large as possible supremum norm, under the constraint that for example $\|f\|_1 = 1$, if $L > 2$, is to pick a $f$ of the form

$$f: x \mapsto \begin{cases} 0 \text{ if } x \in [0, 1-2/L] \\ L(x - 2/L) \text{ if } x \in (1-2/L, 1] \end{cases},$$ which would give us $\|f\|_{\infty} = 2$.

In higher dimensions, I conjecture that the largest supremum norm you can get under $\|f\|_1 = 1$ is achieved by a function whose graph is some type of hyperpyramid, as in the case $d=1$, which would give us that $\|f\|_\infty \lesssim (d/L)^{1/d}$. Would anyone know how to prove this?

This sounds like a result that should be documented, but I couldn't find a good source.

$\endgroup$
2
  • 1
    $\begingroup$ A trivial bound could be $\|f\|_\infty \le \inf |f| + L \le \|f\|_1 + L$. Your hyperpyramid doesn't seem right as its sup norm should increase with $L$. $\endgroup$ Dec 22, 2020 at 4:35
  • 1
    $\begingroup$ I think you might want to look at generalizations of the Poincaré inequality. In particular, if $f$ is $L$-Lipschitz, then the constant function with value $L$ should be an upper gradient for $f$. This should be enough to get you started along this path. $\endgroup$
    – J Loreaux
    Dec 22, 2020 at 5:18

3 Answers 3

6
$\begingroup$

$\newcommand\Om\Omega$Now consider the general case of any natural $d$. Here we will give an upper bound on $\|f\|_\infty$ in terms of $\|f\|_1$, $L$, and $d$. This bound will be optimal up to a factor depending only on $d$; as follows from a comment of yours, such factors do not matter to you. The mentioned bound will be exact in the case $d=1$.

Indeed, let $I:=[0,1]$, $\Om:=I^d$, $$M:=\|f\|_\infty=\max_{x\in\Om}|f(x)|=|f(a)|$$ for some $a=(a_1,\dots,a_d)\in\Om$. Then \begin{equation} |f(x)|\ge h_a(x):=(M-L|x-a|)_+=L(r-|x-a|)_+ \tag{1} \end{equation} for all $x\in\Om$, where $|x-a|$ is the Euclidean norm of $x-a$, $u_+:=\max(0,u)$, and $$r:=M/L$$ (assuming $L>0$). So, $$\frac{\|f\|_1}L=\frac1L\int_\Om|f|\ge\int_\Om dx\,(r-|x-a|)_+ =E(r-R)_+,$$ where $$R:=\sqrt{\sum_1^d(U_i-a_i)^2}$$ and $U_1,\dots,U_d$ are independent random variables each uniformly distributed on $[0,1]$.

Next, $$E(r-R)_+=E\int_0^r dv\,1(R<v)=\int_0^r dv\,P(R<v),$$ \begin{align*} P(R<v)&=P\Big(\sum_1^d(U_i-a_i)^2<v^2\Big) \\ &\ge\prod_1^d P(|U_i-a_i|<v/\sqrt d) \tag{2} \\ &\ge\prod_1^d P(|U_i|<v/\sqrt d) \tag{3} \\ &=\min\Big(1,\frac{v}{\sqrt d}\Big)^d=:Q(v). \end{align*} So, \begin{align*} \frac{\|f\|_1}L&\ge\int_0^r dv\,P(R<v) \\ &\ge\int_0^r dv\,Q(v) \\ &=g(r):=\left\{\begin{aligned} \frac{r^{d+1}}{c_d^{d+1}}&\text{ if }r\le\sqrt d, \\ r-\frac{d\sqrt d}{d+1}&\text{ if }r\ge\sqrt d, \end{aligned} \right. \end{align*} where \begin{equation*} c_d:=((d+1)d^{d/2})^{1/(d+1)}. \end{equation*} Solving now the inequality $\frac{\|f\|_1}L\ge g(r)$ for $r$ and recalling that $r=M/L=\|f\|_\infty/L$, we get \begin{align*} \|f\|_\infty&\le B_0(\|f\|_1,L) \\ &:=Lg^{-1}\Big(\frac{\|f\|_1}L\Big) \\ &=\left\{\begin{aligned} c_d L^{d/(d+1)}\|f\|_1^{1/(d+1)}&\text{ if }\|f\|_1\le\frac{\sqrt d}{d+1}\,L, \\ %\|f\|_1&\text{ if }\|f\|_1\le\frac{\sqrt d}{d+1}\,L, \\ \|f\|_1+\frac{d\sqrt d}{d+1}\,L&\text{ if }\|f\|_1\ge\frac{\sqrt d}{d+1}\,L. \end{aligned} \right. \end{align*}


Remark 1: Obviously, the inequality in (1) will turn into the equality if we choose $f=h_a$ with $a=0$, and then the inequality in (3) will turn into the equality as well. Moreover, the inequality in (2) will change the direction if we replace $v/\sqrt d$ in (2) by $v$. Therefore, the bound $B_0(\|f\|_1,L)$ is optimal up to a factor depending only on $d$. It also follows that the bound $B_0(\|f\|_1,L)$ is exact when $d=1$, in which case $B_0(\|f\|_1,L)$ is
exactly the same as the exact upper bound on $\|f\|_\infty$ presented in the other answer of mine on this web page (previously obtained somewhat differently).

Remark 2: We have $\|f\|_1\le\|f\|_2$, since the Lebesgue measure on $\Om$ is a probability measure. Also, $B_0(\cdot,L)$ is nondecreasing. So, $$\|f\|_\infty\le B_0(\|f\|_1,L)\le B_0(\|f\|_2,L).$$

Remark 3: One can show that $c_d\le\sqrt{2d}$ for all natural $d$.

Remark 4: It follows from Remark 3 that \begin{align*} \|f\|_\infty&\le B_1(\|f\|_1,L) \\ &:=\left\{\begin{aligned} \sqrt{2d}\, L^{d/(d+1)}\|f\|_1^{1/(d+1)}&\text{ if }\|f\|_1<\frac{\sqrt d}{d+1}\,L, \\ %\|f\|_1&\text{ if }\|f\|_1\le\frac{\sqrt d}{d+1}\,L, \\ (d+1)\|f\|_1&\text{ if }\|f\|_1\ge\frac{\sqrt d}{d+1}\,L. \end{aligned} \right. \end{align*} Note that $B_1(\|f\|_1,L)$ differs from $B_0(\|f\|_1,L)$ by, at most, a factor depending only on $d$. So, in view of Remark 1, the bound $B_1(\|f\|_1,L)$ is optimal as well up to a factor depending only on $d$. Note also that the exponent of $\|f\|_1$ in the bound $B_1(\|f\|_1,L)$ is $1/(d+1)$ if $\|f\|_1$ is not too large as compared with $L$, and this exponent is $1$ otherwise.

In view of Remark 2, we also have $$\|f\|_\infty\le B_1(\|f\|_2,L).$$

Remark 5: As shown in Willie Wong's comment, if we had a bound on $\|f\|_\infty$ of the form $C(d)L^a\|f\|_1^b$, then the only possible values for $a$ and $b$ would be $d/(d+1)$ and $1/(d+1)$, respectively. However, in view of Remark 4, it is clear that such a bound on $\|f\|_\infty$ is impossible: the exponent of $\|f\|_1$ cannot be greater than $1/(d+1)$ for values of $\|f\|_1$ not too large as compared with $L$, and this exponent cannot be less than $1$ for values of $\|f\|_1$ large enough as compared with $L$.

$\endgroup$
9
  • $\begingroup$ Incidentally, the correct powers in the bound can be divined using a simple scaling argument. By considering rescalings $f_\lambda(x) = f(x/\lambda)$, we see that the only comparable estimate of the form $$\|f_\lambda\|_{L^\infty} \lesssim \|f_\lambda\|_{L^1}^\beta \|\nabla f_\lambda\|_{L^\infty}^{\alpha}$$ requires $\alpha + \beta = 1$ and $-\alpha + d\beta = 0$ which solves to get $\beta = 1/(d+1)$ and $\alpha = 1 - 1/(d+1)$. // Did you perhaps have a typo on the final line? As it stands the estimate you wrote is not homogeneous to $f \mapsto \mu f$ with $\mu\in (0,\infty)$. $\endgroup$ Dec 22, 2020 at 14:34
  • $\begingroup$ @WillieWong : Thank you very much for this illuminating comment. Dimension/homogeneity arguments can indeed be very powerful. I did try to keep track of the dimensions, but did not do that at the last step, where I computed the exponent of $L$ incorrectly, adding $1/(d+1)$ to $1$ instead of subtracting. Now this is fixed. $\endgroup$ Dec 22, 2020 at 15:45
  • $\begingroup$ I have corrected the mistake stemming from the fact that $P(|U_i|<v/\sqrt d)$ is $\min(1,{v}/{\sqrt d})$, not ${v}/{\sqrt d}$. It is also noted that in the case $d=1$ the bound obtained in the above answer for general $d$ coincides with the exact upper bound on $\|f\|_\infty$ presented in the other answer of mine on this web page. $\endgroup$ Dec 23, 2020 at 5:30
  • $\begingroup$ Also, it is now shown that, for all natural $d$, the bound on $\|f\|_\infty$ is optimal up to a factor depending only on $d$. $\endgroup$ Dec 23, 2020 at 12:54
  • $\begingroup$ Ah! That makes a lot more sense now. I've tried a bit to prove the pure product type bound without success, and was hoping to study your answer a bit to figure out how it worked. $\endgroup$ Dec 23, 2020 at 15:25
9
$\begingroup$

It can be shown that for $d=1$ the best upper bound on $\|f\|_\infty$ is given by $$\|f\|_\infty\le\sqrt{2L\|f\|_1}\,1(\|f\|_1\le L/2)+(L/2+\|f\|_1)\,1(\|f\|_1>L/2).$$ If there is a sufficient interest, I can later provide details on this.

One can see that, if $L=O(\|f\|_1)$, then the above bound is of the same order of magnitude as the bound $\|f\|_1+L$ given in a comment by Nate Eldredge. On the other hand, the above bound goes to $0$ (as it should) when e.g. $\|f\|_1\to0$ while $L\asymp1$.

We see that the optimal bound is rather complicated already for $d=1$.

The case of $d>1$ is much more complicated -- in particular, because it is hard to evaluate or even estimate the volume of the intersection of the hypercube and an arbitrary Euclidean ball -- cf. e.g. https://math.stackexchange.com/a/2008339/96609.

Anyhow, as Nate Eldredge pointed out, your conjectured bound cannot hold because it should increase with $L$. Also, the bound should of course depend on $\|f\|_1$. So, I think further help depends on whether you can tell us what kind of bound on $\|f\|_\infty$ will suffice for the purposes of your research.

$\endgroup$
1
  • $\begingroup$ Thank you very much @Iosif Pinelis, this is very helpful. For the specific problem I am working on, it would be enough to have that there exists some positive constants $a(d,L) > 0$ and $C(d,L)$ such that $\|f\|_{\infty} \leq C(d,L) \|f\|_2^a$. (I am writing the bound in terms of $\|f\|_2$ instead of $\|f\|_1$ as I actually know how to control the $\| \cdot \|_2$ norm of the function I care about, not only the $\|\cdot\|_1$ norm.) $\endgroup$
    – Aurelien
    Dec 22, 2020 at 7:22
1
$\begingroup$

I give a proof that gives tighter sup-norm bounds when you have control of the $L^2$ norm (or $L^q$ norm more generally). The following proof should also be generalizable to general Holder classes (e.g. functions with Lipschitz derivatives). I give the rigorous proof for $d=1$ as the generalization to dimension $d$ follows easily.

Dimension 1

Suppose that $f_n$ and $f_0$ are L-Lipschitz on the interval $I:=[A,B]$. Let $\varepsilon_n := \|f_n-f_0\|_{\infty, I}$.

The key idea of the proof is the following proposition.

Proposition (1). Suppose $\varepsilon_n := \|f_n-f_0\|_{\infty, I}$. Then, there exists there exists some $c \in [A, B - \delta_n]$ such that $\text{inf}_{x \in [c,c+\delta_n]} |f_n(x) - f_0(x)| \geq \varepsilon_n/2$ where $\delta_n := \frac{\varepsilon_n}{4L}$.

Proof. Note that I implicitly assume $\frac{\varepsilon_n}{4L} \leq (B-A)$. With some minor modifications, the proposition remains true for the general case with different constants.

It suffices to prove the following contrapositive: If for all $c \in [A, B - \delta_n]$ we have $\text{inf}_{x \in [c,c+\delta_n]} |f_n(x) - f_0(x)| \leq \varepsilon_n/2$ then $ \|f_n-f_0\|_{\infty, I} \leq \varepsilon$.

To this end, suppose that for all $c \in [A, B - \delta_n]$ that $\text{inf}_{x \in [c,c+\delta_n]} |f_n(x) - f_0(x)| \leq \varepsilon_n/2$. Take some $c \in [A, B - \delta_n]$ and let $t_n \in [c,c+\delta_n]$ be such that $ |f_n(t_n) - f_0(t_n)| \leq \varepsilon_n/2$, which we can do by assumption. Then, $$\text{sup}_{x \in [c,c+\delta_n]} |f_n(x) - f_0(x)| \leq \text{sup}_{x \in [c,c+\delta_n]} |f_n(x) - f_n(t_n)| + |f_n(t_n) - f_0(t_n)| + \text{sup}_{x \in [c,c+\delta_n]} |f_0(t_n) - f_0(x)| \leq 2L\delta_n + \varepsilon_n/2,$$ where the RHS bound holds independent of $c$ and $t_n$. Thus, we actually have $$\text{sup}_{x \in I} |f_n(x) - f_0(x)| \leq 2L\delta_n + \varepsilon_n /2\leq \varepsilon_n$$ by our choice of $\delta_n$. This proves the claim. (One can prove similar propositions for Holder classes more generally (e.g. functions with Lipschitz derivative.) End Proof.

Let $B_n = [c,c+\delta_n]$ be the interval guaranteed by Proposition 1. with $\inf_{x \in B_n}|f_n(x) - f_0(x)| \geq \|f_n-f_0\|_{\infty} = \varepsilon_n$ (where we will ignore constants for simplicity). It follows that $$ \varepsilon_n^{2} \lessapprox {\delta_n} \varepsilon_n \lessapprox {\int_{B_n} |f_n-f_0|(x) dx} \leq \|f_n - f_0\|_{L^1}$$ which gives $$\|f_n - f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^1}^{1/2},$$ and $$ \varepsilon_n^{3/2} \lessapprox \sqrt{\delta_n} \varepsilon_n \lessapprox \sqrt{{\int_{B_n} |f_n-f_0|^2(x) dx}} \leq \|f_n - f_0\|_{L^2}$$ which gives $$\|f_n - f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^2}^{2/3}.$$ More generally, we can show for $q > 0$ $$\|f_n - f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^q}^{\frac{q}{q+1}}.$$

Higher dimensions

Proposition (1) can be generalized to dimension $d$ with virtually no changes but an addition of a constant $O(\sqrt{d})$ in some places. In particular, one can show that $\|f_n-f_0\|_{\infty} = C_1\varepsilon_n$ implies there is a rectangle $B_n$ with sides at most $C_2\varepsilon_n$ such that $\inf_{x\in B_n}|f_n(x)-f_0(x)| \geq C_3 \varepsilon_n$ for constants $C_i$>0. Thus, $$ \varepsilon_n \varepsilon_n^{ d} \lessapprox {\int_{B_n} |f_n-f_0|(x) dx} \leq \|f_n - f_0\|_{L^1}$$ and $$ \varepsilon_n \varepsilon_n^{d/2 } \lessapprox \sqrt{\int_{B_n} |f_n-f_0|(x)^2 dx} \leq \|f_n - f_0\|_{L^2}$$ which implies $$ \|f_n-f_0\|_{\infty}\lessapprox \|f_n - f_0\|_{L^1}^{\frac{1}{1+d}}$$ and $$ \|f_n-f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^2}^{\frac{2}{d+2}}.$$ More generally, we can show for $q > 0$ $$ \|f_n-f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^q}^{\frac{q}{d+q}}.$$ A simple but interesting consequence of the above is as follows. Since $$ \|f_n - f_0\|_{L^p} \lessapprox \|f_n-f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^q}^{\frac{q}{d+q}},$$ we have $$ \|f_n - f_0\|_{L^q}^{\frac{d+p}{p}} \lessapprox \|f_n - f_0\|_{L^p} \lessapprox \|f_n - f_0\|_{L^q}^{\frac{q}{d+q}}$$ for all $p,q>0$.

Higher-order smoothness

If one has that $f_n$ and $f_0$ are univariate Lipschitz with $L$-Lipschitz derivatives, one can show by a similar argument (proving a tighter version of proposition (1) with first order taylor expansions and with $\delta_n = C\varepsilon_n^{1/2}$) that $$\|f_n - f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^1}^{\frac{2}{3}}.$$ $$\|f_n - f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^2}^{\frac{4}{5}}.$$ More generally, we can show for dimension $d$ and functions with $(\alpha-1)$-order derivative being $L$-Lipschitz that $$ \|f_n-f_0\|_{\infty} \lessapprox \|f_n - f_0\|_{L^q}^{\frac{q\alpha}{d+q\alpha}}.$$

$\endgroup$

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.