# Bounding supremum norm of Lipschitz function by L1 norm

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.

• 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$. Dec 22, 2020 at 4:35
• 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. Dec 22, 2020 at 5:18

$$\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 \begin{align*} P(R So, \begin{align*} \frac{\|f\|_1}L&\ge\int_0^r dv\,P(R 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$$.

• 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)$. Dec 22, 2020 at 14:34
• @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. Dec 22, 2020 at 15:45
• 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. Dec 23, 2020 at 5:30
• 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$. Dec 23, 2020 at 12:54
• 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. Dec 23, 2020 at 15:25

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.

• 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.) Dec 22, 2020 at 7:22

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