Incrustación de Z en Z^2 con gran distorsión

Question

¿Es posible encontrar un camino infinito (auto-evitativo) de 2 vías $\{x_i\}_{i\in \mathbb Z}$ en el gráfico de Cayley estándar de $\mathbb Z^2$ es decir, la red cuadrada, tal que la distancia entre $x_i$ y $x_{i+n}$ es de orden $o(n)$ ? En caso afirmativo, ¿cómo de pequeña puede ser esta distancia? Aquí estoy preguntando por los límites superiores $f(n)$ que son independientes de $i$ . Permítanme ser más preciso:

¿Existe un camino infinito de 2 vías (auto-evitadas) $\{x_i\}_{i\in \mathbb Z}$ en $\mathbb Z^2$ y un número M, tal que para cada i y cada $n>M$ tenemos $d(x_i,x_{i+n}) < f(n)$ donde $f(n)$ es $o(n)$ ?

Aquí $d$ denota la distancia gráfica en $\mathbb Z^2$ .

Si la respuesta es afirmativa, me gustaría saber cuál es la menor $f(n)$ para los que esto es posible. Fácilmente, $f(n)= \Omega(\sqrt{n})$ .

Answer 1

Es posible conseguir $\Theta(\sqrt{n})$ para todos $n$ . A continuación presento la construcción. Dudo que haya una única incrustación que minimice $f(n)$ simultáneamente para todos $n$ .

Comience con la curva de Peano (la imagen es de Wikipedia (hecho por el usuario António Miguel de Campos)

Es naturalmente una incrustación $\phi\colon\mathbb{Z}_{+}\to\mathbb{Z}_+^2$ con $f(n)=O(\sqrt{n})$ donde el origen es el elemento situado más abajo a la izquierda en la imagen anterior. Podemos entonces definir una incrustación de $\mathbb{Z}_-$ reflejando alrededor del origen, y luego pegar las dos incrustaciones en el origen.

Answer 2

Esta pregunta se responde, con mayor generalidad, en un papel por Richard Stong. Para cualquier dimensión $r \leq s$ construye una incrustación ${\phi}: {\mathbb Z}^r\longrightarrow {\mathbb Z}^s$ tal que para todo $x,y\in {\mathbb Z}^r$ , $$\parallel {\phi}(x)-{\phi}(y)\parallel \, <\, C \parallel x-y \parallel^{r/s}$$ para alguna constante $C$ . (A la inversa, hay una constante $K$ tal que para cualquier incrustación ${\mathbb Z}^r\longrightarrow {\mathbb Z}^s$ existen infinitos pares $x,y\in {\mathbb Z}^r$ con $\parallel {\phi}(x)-{\phi}(y)\parallel \, >\, K \parallel x-y \parallel^{r/s}$ .)

En cuanto a la pregunta original $( {\mathbb Z}\longrightarrow {\mathbb Z}^2)$ esto da $f=\Theta(\sqrt{n})$ . Para seguir con el comentario de la respuesta anterior, observe que Stong da una única incrustación que funciona para todos $n$ .