Is there a function with this property?

Is there a real function over the real numbers with this property $\ \sqrt{|x-y|} \leq |f(x)-f(y)|$ ? My guess is no but can anyone tell me why? This came up as a question of one of my collegues and i cant give an answer.

-

Indeed, no such function $f$ is possible.

Let $Y$ be the image of $f$, and let $g$ be the inverse of $f$. Then as pointed out by Eric Nitardy, $|g(x)-g(y)|\le(x-y)^2$ for all $x,y$ in $Y$.

From this inequality it now follows that $g(Y)$ has measure zero, which contradicts the fact that $g(Y)$ is the whole real line. To prove $g(Y)$ has measure zero, it suffices to show that for any integer $n$, $g(Y_n)$ has measure zero where $Y_n=Y\cap[n,n+1].$ But for any $N$, $Y_n$ is contained in a union of $N$ intervals of diameter $1/N$ whose images under $g$ have diameter not exceeding $1/N^2$.

-
Nice! The inverse image of an interval of length $l$ is contained in an interval of length $l^2$. So we can make the inverse image of $[n,n+1]$ as small as we please. +1! – TonyK Jan 27 '11 at 13:17

There is such a function on the rationals:

Let $(q_0,q_1,...)$ be any enumeration of the rationals. For each $i \ge 0$, let $f(q_i) = q_r$, where $r$ is the smallest index that maintains the required property of $f$. That is, $r$ is the smallest index such that $|q_r - f(q_j)| \ge \sqrt{|q_i - q_j|}$ for all $j \lt i$.

Edited to add: What's more, given any infinite subset $X \subset \mathbb{N}$, there is such a function $f: \mathbb{Q} \rightarrow X$. Just let $f(q_i)$ be the smallest $n \in X$ such that $|n - f(q_j)| \ge \sqrt{|q_i - q_j|}$ for all $j \lt i$.

-
Using this idea one can produce such a function with domain any countable subset $(x_i)_{i\geq 0}$ of ${\mathbb R}$: Put $f(x_0):=0$ and $f(x_n):=\max_{0\leq i<n} \{f(x_i) + \sqrt{|x_n-x_i|}\}$ $\ (n\geq1)$. It follows that to prove the nonexistence of such a function $f:{\mathbb R}\to{\mathbb R}$ one would have to use the uncountability of ${\mathbb R}$ in an essential way. – Christian Blatter Jan 26 '11 at 18:46

Observe that $f(x) = f(y)$ implies $x = y$, so if $f$ is continuous then it must be monotonic. Now we are done by a fairly simple pigeonhole argument: if, say, $|f(1) - f(0)| = d$, then at least one of $|f(1) - f((n-1)/n)|, |f((n-1)/n) - f((n-2)/n)|, ...$ is at most $\frac{d}{n}$, and taking $n$ large enough this leads to a contradiction.

I have no idea what happens if $f$ isn't required to be continuous. But the idea here is that the condition gets harder to satisfy the closer $x$ and $y$ are.

-

Whenever $f(x_0)$ and $f(x_1)$ fall in an interval $[a, b]$, we must have $$|x_0 - x_1| \le (f(x_0) - f(x_1))^2 \le (a - b)^{2}.$$ Therefore, the pre-image of any interval $[a,b]$ under $f$ is contained in some interval of length $(a-b)^2$. Now let $a_0=0$ and $a_k=\sum_{n=1}^{k}n^{-1}$ for $k=1,2,3...$ Since $a_k$ diverges, we have $\cup_k [a_k, a_{k+1}] = [0, \infty)$. So we can write $$\begin{eqnarray} f^{-1}\left([0, \infty)\right) &=& f^{-1}\left(\cup_k [a_k, a_{k+1}]\right) \\ &=& \cup_k f^{-1}\left([a_k, a_{k+1}]\right) \\ &\subseteq& \cup_k I_k, \end{eqnarray}$$ where each $I_k$ is an interval of length $(a_{k+1} - a_{k})^2 = 1/(k+1)^2$. This countable union of intervals is measurable, and has measure $\le \sum_{k=0}^{\infty} 1/(k+1)^2 = \pi^2/6$. Similarly, we can show that $f^{-1}\left((-\infty, 0]\right)$ is also contained in a measurable set with measure $\le \pi^2/6$. Combining these results, we have $f^{-1}(\mathbb{R}) \subseteq Q$, where $Q$ is measurable with measure $\pi^2/3$. Clearly $Q \neq \mathbb{R}$ (since $\mathbb{R}$ has infinite measure); hence $f^{-1}(\mathbb{R}) \neq \mathbb{R}$, and $f$ cannot be defined over the entire real line.

The same argument with $a_k$ replaced by $\sum_{n=1}^{k}(n+\alpha)^{-1}$ can be used to make the measure of $Q$ arbitrarily small (by choosing $\alpha$ sufficiently large), and we conclude that the domain of $f$ cannot contain any set of positive measure.

-
This is just Bob Pego's answer with all the messy details :-) – TonyK Jan 27 '11 at 17:04
Yes, it basically is... his answer was so compact I didn't see it was the same reasoning until after I posted... – mjqxxxx Jan 27 '11 at 17:14

I think you're right, there are indeed none. It's pretty easy to prove that $\left |\frac{f(x+\varepsilon) - f(x)}{\varepsilon} \right | \geq \frac{1}{\sqrt{\left |\varepsilon \right |}}$, now think about what this means when $\varepsilon$ tends to zero.

I'm not 100% sure about the non-differentiable/non-continuous case though.

-
I've already made this thought.The problem is exactly what you 're not sure about.Ok it's derivative is infinite at every point.But do we know that there is no function with this property? – t.k Jan 26 '11 at 10:41
The Weierstrass function is continuous (even Hölder continuous) but is nowhere differentiable. Still, I don't think it will satisfy the condition of your OP. – Raskolnikov Jan 26 '11 at 11:11

This is not a complete answer, but a small lemma that may be useful: If $f$ exists, it is unbounded on any interval.

Without loss of generality, let the interval be $[0,\ell]$. For some $n$, consider the $n+1$ values $f(0)$, $f(\ell/n)$, $f(2\ell/n)$, $\ldots,$ $f(\ell)$. Any two of these must differ by at least $\sqrt{\ell/n}$, so the $n+1$ values together must span a range of $n\sqrt{\ell/n} = \sqrt{n\ell}$. Let $n$ go to infinity, and the lemma follows.

Of course, there do exist functions that are unbounded on any interval (for example, $g(x) = q$ if $x = p/q$, and $0$ otherwise), so this doesn't rule out the existence of the proposed function. But if it does exist, it would have to be fairly pathological.

-