Function $f$ such that $|f(x)-f(y)| \ge \sqrt{|x-y|}$

It is possible to prove that such a function does not exist. At first I considered a local approach (taking a continuous restriction of $f$ with Blumberg theorem, etc...) but @Mizar proved me wrong.

Then I tried to consider a global approach, by trying to find a contradiction when considering the sets $f \left ( \left \{ \frac{k}{n}\ | \ 0 \le k \le n \right \}\right )$. Fortunately, this problem already has a solution. It was given at a St Petersburg Olympiad. Vesselin Dimitrov gave the following reference : A nice one from St Petersburg. The following was asked during the contest with $C = 10$.

For all $C>0$, given $n^2$ points in a circle of radius $C n$, prove that if $n$ is large enough, then for some distinct $i,j$, the distance between $A_i$ and $A_j$ is less than $\sqrt{|j-i|}$.

Proof : there is a nice proof for $C=10$ on the aforementioned link "A nice one from St Petersburg", I will edit my post and copy it here later

It is quite a hard problem : according to Fedor Petrov, "Nobody solved it during the contest, and, as I know, after the contest, too."

---

Now that we have the result above, it is easy to conclude : ad absurdum, assume that there is a function $f : [0,1] \rightarrow \mathbb{C}$ such that $\forall (x,y) \in [0,1]^2,\ |f(y)-f(x)| \ge \sqrt{|y-x|}$, and such that $f$ is bounded by $M$.

For $n \in \mathbb{N}$, denote $A_i = n \cdot f \left( \frac{i}{n^2} \right)$ for $i \in [\![ 1, n^2 ]\!]$. Then the $A_i$ are all in the disk of radius $M n$, but for all $i,j$, $$|A_j-A_i| = n \left | f \Big( \frac{j}{n^2} \Big) - f \Big (\frac{i}{n^2} \Big) \right | \ge n \left | \frac{\sqrt{|j-i|}}{n} \right | = \sqrt{|j-i|}$$

and this is absurd because of the result stated above.

Claim. Fix $0<k<\ell$ and an arbitrary constant $C$. If $n$ is sufficiently large, there does not exist a function $f:\{0,\dots,n\}^k\to [0,Cn^{k/\ell}]^\ell$ such that $|f(x)-f(y)|\ge|x-y|^{k/\ell}$ for any $x,y\in\{0,\dots,n\}^k\subset\mathbb{R}^k$.

Proof. Assume by contradiction that such an $f$ exists. Given a closed cube $Q\subset\mathbb{R}^\ell$, we call $\delta(Q):=\frac{\# f^{-1}(Q)}{|Q|}$ its density (here $|Q|$ is the volume of the cube).

Lemma 1. Fix any $\epsilon>0$. There exist $N>0$ (integer) and $a_0>0$ (both depending only on $\epsilon$, $k$ and $\ell$) with the following property: if a cube $Q$ has $\delta(Q)\ge\epsilon$ and sidelength $a\ge a_0$, then there exists a subcube $Q'\subset Q$ with sidelength $\frac{a}{N}$ and $\delta(Q')\ge(1-N^{-\ell})^{-1}\delta(Q)$.

Proof. Split $Q$ into $N^\ell$ subcubes $\{Q_i\}$ (with sidelength $\frac{a}{N}$ and disjoint interiors). It suffices to prove that one of these cubes, say $Q_{i_0}$, has empty preimage: then it follows that $$ a^\ell\delta(Q)=\# f^{-1}(Q)\le\sum_{i\neq i_0}\# f^{-1}(Q_i)\le(N^\ell-1)\left(\frac{a}{N}\right)^\ell\max_{i\neq i_0}\delta(Q_i), $$ so we can choose any $Q_i$ realizing the maximum as our $Q'$.

Assume by contradiction that all $Q_i$ intersect the image of $f$. Choose $x,y\in f^{-1}(Q)$ such that $|x-y|$ has the maximum possible value. We can find a chain of at most $\ell N$ cubes $Q_{i_0},\dots,Q_{i_s}$ such that two consecutive cubes in the chain share an $(\ell-1)$-dimensional face and such that $x\in Q_{i_0}$, $y\in Q_{i_s}$.

By hypothesis, for all $j=1,\dots,s-1$ we can find $x_j\in f^{-1}(Q_{i_j})$. We also put $x_0:=x$ and $x_s:=y$. We have $|f(x_j)-f(x_{j-1})|\le 2\ell\frac{a}{N}$, so $|x_j-x_{j-1}|\le (2\ell)^{\ell/k}\left(\frac{a}{N}\right)^{\ell/k}$.

By the triangle inequality, we deduce $$ |x-y|\le (\ell N)(2\ell)^{\ell/k}\left(\frac{a}{N}\right)^{\ell/k}=\ell(2\ell)^{\ell/k} a^{\ell/k}N^{1-\ell/k}. $$ Since all points in $f^{-1}(Q)$ have distance at most $|x-y|$ from $x$, we deduce that $$ \epsilon\le\delta(Q)=a^{-\ell}\# f^{-1}(Q)\le a^{-\ell}(2|x-y|+1)^k\le a^{-\ell}\cdot 2^{k-1}(2^k|x-y|^k+1)\le 2^{2k-1}\ell^k(2\ell)^\ell N^{k-\ell}+2^{k-1}a^{-\ell}. $$ Since $k-\ell<0$, we obtain a contradiction if $N$ and $a_0$ are large enough. $\blacksquare$

Lemma 2. If $Q$ has sidelength in $\left[\frac{a_0}{N},a_0\right]$, then $\delta(Q)\le\delta_0$ (for some $\delta_0$ depending only on $N,a_0,k,\ell$).

Proof. For any distinct $x,y\in f^{-1}(Q)$ we have $|x-y|\ge 1$, so that $|f(x)-f(y)|\ge 1$. Thus, the cubes centered at $f(x)$ and $f(y)$ with sidelength $\frac{1}{\sqrt{n}}$ are disjoint. So the cube $\tilde Q$ with the same center as $Q$ and sidelength $a_0+\frac{1}{\sqrt{n}}$ contains $\# f^{-1}(Q)$ such disjoint cubes. Comparing the volumes, this gives $$ \# f^{-1}(Q)\cdot\left(\frac{1}{\sqrt{n}}\right)^\ell\le\left(a_0+\frac{1}{\sqrt{n}}\right)^\ell, $$ so that $\delta(Q)\le\left(\frac{a_0}{N}\right)^{-\ell}\# f^{-1}(Q)\le N^\ell a_0^{-\ell}(a_0\sqrt{n}+1)^\ell$. $\blacksquare$

Proof of the claim (continued). Now the cube $Q_0:=[0,Cn^{k/\ell}]^\ell$ has density $\frac{(n+1)^k}{C^\ell n^k}\ge C^{-\ell}=:\epsilon$. Let $N$ and $a_0$ be the corresponding constants given by Lemma 1. Let then $\delta_0$ be the constant given by Lemma 2. Fix a positive integer $m$ such that $$ \epsilon\cdot(1-N^{-\ell})^{-m}>\delta_0. $$ Assume $n$ is so large that $Cn^{k/\ell}\ge N^m a_0$. Applying Lemma 1 to $Q_0$ we find a subcube $Q_1$ with density at least $\epsilon\cdot(1-N^{-\ell})^{-1}$. Then we can apply Lemma 1 again to $Q_1$, and so on. We apply Lemma 1 as long as the sidelength of the cube is at least $a_0$, obtaining a finite sequence of cubes $Q_0,\dots,Q_s$, where $Q_s$ has sidelength $N^{-s}Cn^{k/\ell}\in\left[\frac{a_0}{N},a_0\right)$.

From $N^m a_0\le Cn^{k/\ell}\le N^s a_0$ we deduce $s\ge m$, so $\delta(Q_s)\ge(1-N^{-\ell})^{-s}\epsilon>\delta_0$. However, the cube $Q_s$ contradicts Lemma 2. $\blacksquare$

Theorem. If $0<k<\ell$, there does not exist a function $f:[0,1]^k\to\mathbb{R}^\ell$ such that $|f(x)-f(y)|\ge|x-y|^{k/\ell}$ for any $x,y\in [0,1]^k$.

Proof. Assume such an $f$ exists. Let $S_i:=\{x\in [0,1]^k:|f(x)|\le i\}$. The increasing sequence $\overline{S}_1,\overline{S}_2,\dots$ of closed sets covers $[0,1]^k$. By Baire's theorem, for some $i>0$ the set $\overline{S}_i$ contains a subcube $[a,a+b]^k$. For any $x\in [a,a+b]^k\setminus S_i$ we choose a sequence $(x_m)\subseteq S_k$ with $x_m\to x$ and (up to extracting subsequences) we assume that $f(x_m)$ has a limit (this can be done since $|f(x_m)|\le i$). We replace $f(x)$ with this limit. The new function, still denoted by $f$, satisfies $|f(x)|\le i$ and $|f(x)-f(y)|\ge|x-y|^{k/\ell}$ for any $x,y\in[a,a+b]^k$.

Now let us consider the function $g:\{0,\dots,n\}^k\to\mathbb{R}^\ell$ given by $$ g(x):=\left(\frac{n}{b}\right)^{k/\ell}f\left(a+\frac{b}{n}x\right)+\left(\frac{n}{b}\right)^{k/\ell}(i,\dots,i), $$ which takes values into $[0,2\ell i b^{-k/\ell} n^{k/\ell}]$. For $n$ large enough, this $f$ must contradict the Claim. $\blacksquare$