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

After having spent some time on this problem and having found little on this topic in existing articles, I decided to post it here.

My question is :

Does there exist a bounded (injective) function $f: [0,1] \rightarrow \mathbb{C}$ such that $$\forall (x,y) \in [0,1]^2,\ |f(x)-f(y)| \ge \sqrt{|x-y|}$$

(It is not necessary to assume $f$ to be injective, as it follows from the last hypothesis.)

Note that I am not asking the function to be continuous.

Indeed, using a result of Besicovitch and Schoenberg, I can prove that such a function can not be continuous (however this is not really easy to prove ; see On Jordan Arcs and...).

By the way, in the same paper, they proved that given any $\varepsilon>0$ there exists a continuous injection $f : [0,1] \rightarrow \mathbb{C}$ such that $\forall (x,y) \in [0,1],\ |f(x)-f(y)| \ge |x-y|^{\frac{1}{2}+\varepsilon}$.

I really find this result noteworthy. At first I thought I could directly use it, by taking the limit (in a certain sense) to answer my question, but the supremum of the functions they give goes to $+\infty$ when $\varepsilon$ goes to $0$, and I am requiring boundedness : it did not work.

Regarding my problem, I believe that there are no such functions, but did not manage to prove it.

I tried to consider the reciprocal function : from this point of view, we must study Holder continuous functions of order $2$ defined on subsets of $\mathbb{C}$. However, not much is known about Holder continuous functions of order $>1$ (when they are not constant), or rather, I did not manage to find articles investigating this matter.

I also tried to study the discrete case : assuming such a function exists, and taking the image of $\left \{ \frac{k}{n}\ |\ 0 \le k \le n \right \}$, we have, for all $n \in \mathbb{N}^*$, $n$ complex points $x_1,...,x_n$ such that for all $i,j$, $|x_i-x_j| \ge \sqrt{\frac{|i-j|}{n}}$. All those points are in the same bounded set (because $f$ is bounded). However I think that the diameter of such sets grows unbounded when $n$ approaches $+\infty$. Same problem here, I could not find a proper reference dealing with this topic.

I would be glad if someone had an idea on how to tackle this problem, or references to related articles.

Edit : I posted an answer, which I hope is correct, but I would still be glad to see suggestions or different solutions.

• $|f(x)-f(y)| \ge \sqrt{|x-y|}$ directly follows injectivity.! Feb 22, 2017 at 6:54
• @S717717 Do you mean that this condition implies injectivity ? I already pointed this out in the post (I felt it was useful to emphasize that it was injective because one of my first reactions was to consider the inverse function. By the way, I now think that it might not be a really relevant idea) Feb 22, 2017 at 16:28
• I tried to prove that if you have $n$ points as you describe, the diameter grows unbounded, but then I found a counter example: if you arrange the points in a triangle of length $1$, you can put $(k+1)(k+2)$ points that have a distance of $\frac 1 k$. That means a bounded triangle is enough to put $n$ points, no matter big $n$ is. This means we can't prove the answer is no with this strategy, but it does not tell us what the answer is.
– oak
Feb 26, 2017 at 20:49
• @oak Thank you for your interest in the problem ; where do you place your points in the triangle ? On horizontal rows ? Feb 26, 2017 at 20:58
• Actually I read somewhere that it was more or less asked during St Petersburg Math Olympiads to show that the diameter does grow unbounded, so I still think this is the right approach (but I don't know yet if your conterexample works) Feb 26, 2017 at 20:59

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$

• Great answer ! Thank you very much for taking the time to write the whole proof Mar 1, 2017 at 6:32

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 hard a 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.

• Very nice! A couple of remarks: a similar proof shows that there is no bounded map $f:[0,1]^k\to\mathbb{R}^\ell$ with $|f(x)-f(y)|\ge|x-y|^{k/\ell}$ if $k<\ell$. Moreover, using e.g. Baire category theorem, one can show that the boundedness assumption is not necessary. Feb 27, 2017 at 19:41
• @Mizar (if you have the time of course) maybe you can write down the proof that the boundedness assumption is not necessary in another post (and I would give you the bounty) Feb 28, 2017 at 12:51