# Embedding Z into Z^2 with large distortion

Is it possible to find a 2-way infinite (self-avoiding) path $\{x_i\}_{i\in \mathbb Z}$ in the standard Cayley graph of $\mathbb Z^2$, i.e. the square grid, such that the distance between $x_i$ and $x_{i+n}$ is of order $o(n)$? If yes, how small can this distance be? Here I'm asking for upper bounds $f(n)$ that are independent of $i$. Let me make this more precise:

Is there a 2-way infinite (self-avoiding) path $\{x_i\}_{i\in \mathbb Z}$ in $\mathbb Z^2$, and a number M, such that for every i and every $n>M$, we have $d(x_i,x_{i+n}) < f(n)$ where $f(n)$ is $o(n)$?

Here $d$ denotes the graph-distance on $\mathbb Z^2$.

If the answer is yes, I would like to know what is the smallest $f(n)$ for which this is possible. Easily, $f(n)= \Omega(\sqrt{n})$.

• Do you mean easily $f(n)=\Omega(\sqrt n)$? Sep 27, 2015 at 18:28
• Doesn't the obvious thing work? A double spiral? Sep 28, 2015 at 3:28
• The "obvious" spiral does not work, because it contains arbitrary large segments, and on these segments there is no distortion.
– YCor
Sep 28, 2015 at 10:09

It is possible to achieve $\Theta(\sqrt{n})$ for all $n$. I present the construction below. I doubt that there is a single embedding that minimizes $f(n)$ simultaneously for all $n$.
It is naturally an embedding $\phi\colon\mathbb{Z}_{+}\to\mathbb{Z}_+^2$ with $f(n)=O(\sqrt{n})$, where the origin is the bottom-leftmost element in the picture above. We can then define an embedding of $\mathbb{Z}_-$ by reflecting around the origin, and then glue the two embeddings at the origin.
This question is answered, in greater generality, in a paper by Richard Stong. For any dimensions $r \leq s$ he constructs an embedding ${\phi}: {\mathbb Z}^r\longrightarrow {\mathbb Z}^s$ such that for all $x,y\in {\mathbb Z}^r$, $$\parallel {\phi}(x)-{\phi}(y)\parallel \, <\, C \parallel x-y \parallel^{r/s}$$ for some constant $C$. (Conversely, there is a constant $K$ such that for any embedding ${\mathbb Z}^r\longrightarrow {\mathbb Z}^s$ there exist infinitely many pairs $x,y\in {\mathbb Z}^r$ with $\parallel {\phi}(x)-{\phi}(y)\parallel \, >\, K \parallel x-y \parallel^{r/s}$.)
In terms of the original question $( {\mathbb Z}\longrightarrow {\mathbb Z}^2)$ this gives $f=\Theta(\sqrt{n})$. To follow up on the comment in the answer above, note that Stong gives a single embedding that works for all $n$.
• My comment pertained to whether one can minimize $f(n)$ exactly for all $n$. (Actually, the answer is no. Indeed, in original version of the problem the smallest values of $f(3)$ is $1$ as an infinite zig-zag easily shows. However, if we have a embedding for which $f(3)=1$, then it is infinite zigzag, and other values of $f$ are very large.) Oct 14, 2015 at 1:30