Let $f_n: [0, 1] \to \mathbb R$ be a sequence of positive functions in $L^\infty$ (hence a fortiori in $L^1$) that are equibounded in $L^\infty$ norm - that is $\sup_{n \in \mathbb N} \|f_n\|_{L_\infty} \leq M$ for some $M > 0$.

Is it true that there exists some absolute positive constant $c < 1$ such that

$$\inf_{n_k} \sup_{i, j > N} \|f_{n_i} - f_{n_j}\|_{L^1} \leq cM$$

for all such sequences $f_n$?

Where the first infimum is taken over all increasing sequences $n_k$ of naturals.

  • $\begingroup$ Hm $f_n$ are positive, so in fact $c = 1$ works, but the question wants $c < 1$. $\endgroup$
    – Nate River
    Jul 17, 2021 at 3:51
  • 1
    $\begingroup$ Oh, I missed that! Never mind. $\endgroup$
    – Nik Weaver
    Jul 17, 2021 at 4:00
  • $\begingroup$ Rademacher functions? $\endgroup$ Jul 17, 2021 at 4:19
  • 2
    $\begingroup$ If that refers to what I think it is, then I believe that has $c = 1/2$. $\endgroup$
    – Nate River
    Jul 17, 2021 at 6:00
  • 1
    $\begingroup$ I don't understand the purpose of the "$\lim_{N \to \infty}$" in the fomula. Isn't $\inf_{n_k} \lim_{N \to \infty} \sup_{i, j > N} \|f_{n_i} - f_{n_j}\|_{L^1} = \inf_{n_k} \sup_{i, j \in \mathbb{N}} \|f_{n_i} - f_{n_j}\|_{L^1}$, since increasing sequences in $\mathbb{N}$ can start arbitrarily late? $\endgroup$ Jul 17, 2021 at 12:55

2 Answers 2


Edit: I improved the constant to $c = \frac{2}{3}$. (Later edit: But the optimal constant turns out to be $c = \frac{1}{2}$, see Yuval Peres' answer.)

Answer: Yes, we have $$ \inf_{(n_k)} \sup_{i,j \in \mathbb{N}} \|f_{n_i} - f_{n_j}\|_{L^1} \le \frac{2}{3} M, \label{1}\tag{$\ast$} $$ for each sequence $(f_n)$ in $(L^1)_+$ whose sup norm is bounded by $M$. So we can choose $c = \frac{2}{3}$.

To see this, let $[0,\mathbf{1}] \subseteq L^\infty$ denote the positive unit ball in $L^\infty$.

Lemma. Three functions $f_1, f_2, f_3 \in [0,\mathbf{1}]$ cannot have mutual $L^1$-distances that are all strictly larger than $\frac{2}{3}$.

Proof. Set $g_1 = |f_1 - f_2|$, $g_2 = |f_1 - f_3|$ and $g_3 = |f_2 - f_3|$. For any three numbers $r_1,r_2,r_3 \in [0,1]$, the sum of their three mutual distances in $\mathbb{R}$ is at most $2$.

Hence, $\int g_1 + \int g_2 + \int g_3 \le 2$, which shows that it can't happen that all three functions $g_k$ have norm strictly larger than $\frac{2}{3}$. $\square$

Proof of the claim. We may, and will, assume that $M=1$. Assume for a contradiction that we can find a sequence $(f_n)$ in $[0,\mathbf{1}]$ such that the infimum in the question is strictly larger than $\frac{2}{3}$.

Then there exists $n_0$ such that $\|f_{n_0} - f_n\|_{L^1} > \frac{2}{3}$ for infinitely many $n$ (otherwise we could recursively construct a subsequence $(f_{n_k})$ such that the supremum in \eqref{1} is no more than $\frac{2}{3}$); let's denote the set of these $n$ by $J$.

For any two $j,k \in J$, it follows from the lemma that $\|f_j - f_k\| \le \frac{2}{3}$. Thus, you can take the elements of $J$ to be the indices of your wanted subsequence $(f_{n_k})$. Contradiction, since we assumed no such subsequence exists. $\square$

Remark. It's easy to see that the constant $\frac{2}{3}$ is optimal for the lemma (divide $[0,1]$ into three distjoint intervals $I_k$ of measure $\frac{1}{3}$ and define $f_k = \mathbf{1} - \mathbf{1}_{I_k}$), but I don't know whether it is optimal for the answer to the question.

  • $\begingroup$ I think one can also argue that $\|f-g\|_1\simeq 1$ for such functions is only possible if essentially $f=\chi_A$, $g=\chi_{A^c}$ (off a set of small measure, and up to small (in $L^{\infty}$) perturbations), but then on a whole sequence the sets will start overlapping. But considering three functions at once is a neat trick that makes this less messy. $\endgroup$ Jul 17, 2021 at 14:42
  • $\begingroup$ @ChristianRemling: Yepp, that was my first thought, too. I think it yields readily that the infimum is strictly smaller than $M$ for each fixed sequence $(f_n)$. But then I wasn't able to show that we get a uniform constant $c$ for all sequences (the usual trick to mix up sequences in order to show that a strict estimate for each sequence actually implies a uniform estimate, doesn't work here since we are allowed to take subsequences); so after a while I thought, it might be easier to just find an explicit estimate. $\endgroup$ Jul 17, 2021 at 15:01
  • $\begingroup$ Very nice answer! $\endgroup$
    – Nate River
    Jul 18, 2021 at 1:21
  • $\begingroup$ @NateRiver: Thanks for the extra points! :-) $\endgroup$ Jul 23, 2021 at 18:28

The sharp constant is $c=1/2$. As in Jochen's answer, we may and shall assume that $M=1$.

Proposition: Let $f_n: [0, 1] \to \mathbb R$ be a sequence of positive functions in $L^\infty$ such that $\sup_{n \in \mathbb N} \|f_n\|_{L_\infty} \leq 1$. Then

$$\inf_{\{n_k\}} \sup_{i, j \ge 1} \|f_{n_i} - f_{n_j}\|_{L^1} \leq 1/2 \,,$$ where the infimum is over all strictly increasing sequences $\{n_k\}$.

To see that this is sharp, consider the functions $\{b_n\}$ where $b_n(x)$ is the $n$th bit in the binary expansion of $x$. Note that $\|b_n-b_m\|_1=1/2$ for all $n \ne m$.

Lemma 1: For any $k$ numbers $y_1,\ldots ,y_k$ in $[0,1]$, we have $$ \sum_{i=1}^{k-1}\sum_{j=i+1}^k |y_j-y_i| \le \lfloor k/2 \rfloor \cdot \lceil k/2 \rceil \le k^2/4 \,.$$ Proof: We may reorder the $y_i$ so that $y_1 \le y_2\le\ldots \le y_k$. Every interval $[y_\ell,y_{\ell+1}]$ is included in $\ell(k-\ell)$ intervals of the form $[y_i,y_j]$ with $i \le \ell <j$, and $\max_\ell \ell(k-\ell)=\lfloor k/2 \rfloor \cdot \lceil k/2 \rceil$.

Lemma 2. Given $k$ measurable functions $f_1,\ldots, f_k$ taking values in $[0,1]$, there exist $i<j$ so that $$\|f_i-f_j\|_1 \le \frac{ \lfloor k/2 \rfloor \cdot \lceil k/2 \rceil}{{k \choose 2}} \le \frac{k}{2(k-1)} \,.$$.

Proof: By Lemma 1, for each $x \in [0,1]$ we have $$\sum_{i=1}^{k-1}\sum_{j=i+1}^k |f_j(x)-f_i(x)| \le \lfloor k/2 \rfloor \cdot \lceil k/2 \rceil \,, $$ so integrating gives $$\sum_{i=1}^{k-1}\sum_{j=i+1}^k \|f_j-f_i\|_1 \le \lfloor k/2 \rfloor \cdot \lceil k/2 \rceil \,.$$ Since the minimum of ${k \choose 2}$ numbers is at most their average, the claim follows.

Proof of proposition: Let $f_n: [0, 1] \to \mathbb R$ be a sequence of positive functions in $L^\infty$ such that $\sup_{n \in \mathbb N} \|f_n\|_{L_\infty} \leq 1$. It suffices to show that for every $c>1/2$ there is a strictly increasing sequence ${n_k}$ such that

$$ \quad \sup_{i, j \ge 1} \|f_{n_i} - f_{n_j}\|_{L^1} \leq c \,.\label{2}\tag{$\ast$}$$ By changing the values on a set of measure zero, we may assume that each $f_n$ takes values in $[0,1]$. Fix $c>1/2$ and find $k$ such that $\frac{k}{2(k-1)} <c$. Define a graph on the positive integers where there is an edge $\{i,j\}$ iff $\|f_i-f_j\|_1 > c$. By Lemma 2, this graph does not contain a clique of $k$ nodes, so by Ramsey's Theorem [1] there is an infinite independent set (i.e., an anti-clique) in this graph, which proves \eqref{2}.

Remark: Related considerations in Hilbert space are in [2].

[1] https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Infinite_graphs

[2] http://www.cs.tau.ac.il/~nogaa/PDFS/Publications/Euclidean%20Ramsey%20Theory%20and%20a%20construction%20of%20Bourgain.pdf

  • $\begingroup$ Really great answer! Are you aware of any results of this type for $L^q(0,1)$ and $L^p(0,1)$ for general $p < q$? If $(f_n)$ is in the positive $L^p$-unit ball, then I guess I'd expect a similar estimate for the $L^q$-norm, maybe with the constant $\big(\frac{1}{2}\big)^{1/p - 1/q}$ (but after thinking about it a bit I couldn't find, for instance, a simple interpolation argument to prove it). $\endgroup$ Jul 19, 2021 at 10:33
  • $\begingroup$ Thanks Jochen- of course my answer was inspired by yours. I think $p$ and $q$ are reversed in part of your comment. For functions in the positive unit ball in $L^\infty$ one can easily see that when switching from $L^1$ to $L^p$ the $1/2$ is replaced by $2^{-1/p}$. The positivity assumption is less natural once we leave $L^\infty$. In $L^\infty$ requiring positivity in the unit ball is equivalent to replacing the unit ball by the ball of radius $1/2$. $\endgroup$ Jul 20, 2021 at 2:10

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.