Embedding Z into Z^2 with large distortion

Question

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})$.

Answer 1

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$.

Start with the Peano curve (image is from Wikipedia, made by user António Miguel de Campos)

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.

Answer 2

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$.