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: 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.
A: $\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$.
A: 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}}.$$
