12
$\begingroup$

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

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

2 Answers 2

16
$\begingroup$

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)

enter image description here

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.

$\endgroup$
0
9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – Boris Bukh
    Oct 14, 2015 at 1:30
  • $\begingroup$ Thanks for clarifying the comment. (I interpreted it as a single minimizer that works asymptotically.) $\endgroup$ Oct 14, 2015 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.