0
$\begingroup$

I have proved the following result in arXiv:1005.3371v8 Lemma 3.31:


Let $n$ be a natural number greater than or equal to 2. There exists a bijection $f$ from $\mathbb{N}$ onto $\mathbb{Z}^n$ so that $\Vert f(k + 1) - f(k) \Vert_\infty = 1$ for all natural numbers $k$.


Here is a simpler proof:


$$ \newcommand{\naturalnumbers}{\mathbb{N}} \newcommand{\integers}{\mathbb{Z}} \newcommand{\positiveintegers}{{\mathbb{Z}_+}} \newcommand{\natnumberset}[1]{N(#1)} \newcommand{\integerset}[1]{Z(#1)} \newcommand{\setzeroton}[1]{Z_{0+}(#1)} \newcommand{\zeron}[1]{0_{#1}} \newcommand{\card}[1]{\#{#1}} \newcommand{\onto}{\twoheadrightarrow} \newcommand{\setsep}{:} \newcommand{\spaceafter}{\;\;\;\;} $$

$$ \textbf{Definitions} $$

$$\natnumberset{k} := \{ j \in \naturalnumbers \setsep j \leq k \}, \spaceafter k \in \naturalnumbers$$

$$\integerset{k} := \{ j \in \integers \setsep \vert j \vert \leq k \}, \spaceafter k \in \naturalnumbers$$

$$\zeron{n} := (0,\ldots,0) \in \integers^n, \spaceafter n \in \positiveintegers$$

$$A_{n,k} := \left( \integerset{k} \right)^n, \spaceafter n \in \positiveintegers, \; k \in \naturalnumbers$$

$$A_{n,-1} := \emptyset$$

$$B_{n,k} := A_{n,k} \setminus A_{n,k-1}, \spaceafter n \in \positiveintegers, \; k \in \positiveintegers$$

$$B_{n,0} := A_{n,0} = \{ \zeron{n} \}, \spaceafter n \in \positiveintegers$$

Let $S \subset \naturalnumbers$, $n \in \positiveintegers$, and $f$ a function from $S$ into $\integers^n$. We say that $f$ $\textit{preserves neighbours}$ if $k, k+1 \in S$ implies $\Vert f(k+1)-f(k) \Vert_\infty = 1$.

Define $$\beta_{2,k}(i) := \left\{ \begin{array}{ll} (-k+1+c,-k) ; & i = c \in \natnumberset{2k-1} \\ (k, -k+c+1) ; & i = 2k + c, c \in \natnumberset{2k-1} \\ (k-c-1, k) ; & i = 4k + c, c \in \natnumberset{2k-1} \\ (-k, k-c-1) ; & i = 6k + c, c \in \natnumberset{2k-1} \end{array} \right.$$ where $i \in \natnumberset{8k-1}$ and $k \in \positiveintegers$. Define also $\beta_{2,0}(0) := (0,0)$.

Define $ \alpha_{2,k}(i) := \beta_{2,j}(i-\card{A_{2,j-1}}) $ where $\card{A_{2,j-1}} \leq i < \card{A_{2,j}}$ and $i \in \natnumberset{\card{A_{2,k}}-1}$, $j \in \natnumberset{k}$ and $k \in \positiveintegers$. When $k=0$ let $\alpha_{2,0}(0) = (0,0)$. Let also $\alpha'_{2,k}(i) := \alpha_{2,k}(\card{A_{2,k}}-1-i)$ for $i \in \natnumberset{\card{A_{2,k}}-1}$.

If $k < j$ we define $\sum_{i=j}^k x_i = 0$.

$$ \textbf{Lemma 1} $$

Let $k \in \naturalnumbers$. Function $\beta_{2,k}$ is a bijection from $\natnumberset{\card{B_{2,k}}-1}$ onto $B_{2,k}$ preserving neighbours and $\alpha_{2,k}$ is a bijection from $\natnumberset{\card{A_{2,k}}-1}$ onto $A_{2,k}$ preserving neighbours.

$$ \textbf{Lemma 2} $$

Let $n \in \naturalnumbers$, $n \geq 3$. There exist bijections $\beta_{n,k} : \natnumberset{\card{B_{n,k}}-1} \onto B_{n,k}$, $k \in \naturalnumbers$, so that $\beta_{n,k}$ preserves neighbours, $\beta_{n,k}(0) = (k, \zeron{n-1})$, and $\beta_{n,k}(\card{B_{n,k}}-1) = (-k, \zeron{n-1})$ for all $k \in \naturalnumbers$.

$$ \textit{Proof.} $$ We prove case (n = 3) first. Suppose that $k \in \positiveintegers$. Let $$C_0 := \{(k,\mathbf{x}) \setsep \mathbf{x} \in A_{2,k}\}$$ and $$p_0(i) := (k,\alpha_{2,k}(i))$$ for $i \in \natnumberset{\card{A_{2,k}}-1}$. Let $$C_m := \{(k-m,\mathbf{x}) \setsep \mathbf{x} \in B_{2,k}\}$$ and $$p_m(i) := (k-m,\beta_{2,k}(i))$$ for $i \in \natnumberset{\card{B_{2,k}}-1}$ and $m = 1, \ldots, 2k-1$. Let $$C_{2k} := \{(-k,\mathbf{x}) \setsep \mathbf{x} \in A_{2,k}\}$$ and $$p_{2k}(i) := (-k,\alpha'_{2,k}(i))$$ for $i \in \natnumberset{\card{A_{2,k}}-1}$. Define $$\beta_{3,k}(i) := p_m\left(i - \sum_{m'=0}^{m-1}\card{C_{m'}}\right)$$ when $$ \sum_{m'=0}^{m-1} \card{C_{m'}} \leq i < \sum_{m'=0}^m \card{C_{m'}} $$ and $i \in \natnumberset{\card{B_{3,k}}-1}$ Now functions $\beta_{3,k}$ satisfy the conditions of the lemma.

Suppose that the lemma is true for some $n \in \naturalnumbers$, $n \geq 3$. Define $\beta^1_{n,k} := \beta_{n,k}$ for all $k \in \naturalnumbers$, $\beta^{-1}_{n,k}(i) := \beta_{n,k}(\card{B_{n,k}}-1-i)$ for all $i \in \natnumberset{\card{B_{n,k}}-1}$, $k \in \naturalnumbers$. Define also $ \alpha_{n,k}(i) := \beta^{(-1)^{k-j}}_{n,j}(i-\card{A_{n,j-1}}) $ where $\card{A_{n,j-1}} \leq i < \card{A_{n,j}}$ and $i \in \natnumberset{\card{A_{n,k}}-1}$, $j \in \natnumberset{k}$ and $k \in \positiveintegers$. When $k=0$ let $\alpha_{n,0}(0) = \zeron{n}$. Let also $$ \alpha'_{n,k}(i) := \beta^{(-1)^j}_{n,k-j}\left( i - \sum_{j'=0}^{j-1} \card{B_{n,k-j'}} \right) $$ for $i \in \natnumberset{\card{A_{n,k}}-1}$ where $$ \sum_{j'=0}^{j-1} \card{B_{n,k-j'}} \leq i < \sum_{j'=0}^j \card{B_{n,k-j'}} . $$ Let $k \in \positiveintegers$. Let $$C_0 := \{(k,\mathbf{x}) \setsep \mathbf{x} \in A_{n,k}\}$$ and $$p_0(i) := (k,\alpha_{n,k}(i))$$ for $i \in \natnumberset{\card{A_{n,k}}-1}$. Let $$C_m := \{(k-m,\mathbf{x}) \setsep \mathbf{x} \in B_{n,k}\}$$ and $$ p_m(i) := (k-m, \beta^{(-1)^m}_{n,k}(i)) $$ for $i \in \natnumberset{\card{B_{n,k}}-1}$ and $m = 1, \ldots, 2k-1$. Let $$C_{2k} := \{(-k,\mathbf{x}) \setsep \mathbf{x} \in A_{n,k}\}$$ and $$p_{2k}(i) := (-k,\alpha'_{n,k}(i))$$ for $i \in \natnumberset{\card{A_{n,k}}-1}$. Define $$\beta_{n+1,k}(i) := p_m\left(i - \sum_{m'=0}^{m-1}\card{C_{m'}}\right)$$ when $$ \sum_{m'=0}^{m-1} \card{C_{m'}} \leq i < \sum_{m'=0}^m \card{C_{m'}} . $$ and $i \in \natnumberset{\card{B_{n+1,k}}-1}$ Now functions $\beta_{n+1,k}$ satisfy the conditions of the lemma.

$$ \textbf{Theorem} $$ Let $n \in \naturalnumbers$, $n \geq 2$. There exists a bijection $\sigma_n : \naturalnumbers \onto \integers^n$ so that $\sigma_n$ preserves neighbours.

$$ \textit{Proof.} $$ Case $n = 2$ is simple and we don't prove it here. Case $n \geq 3$ follows from lemma 2 when we set $$ \sigma_n(i) := \beta^{(-1)^k}_{n,k}\left( i - \card{A_{n,k-1}}\right) $$ for $$ \card{A_{n,k-1}} \leq i < \card{A_{n,k}} $$ and $i \in \naturalnumbers$.


Could somebody verify the proof?

  Tommi Höynälänmaa
$\endgroup$
  • $\begingroup$ You should show your proof. Otherwise, it could be difficult to decide whether there is a simpler way. $\endgroup$ – Peter Feb 7 at 11:12
  • 1
    $\begingroup$ If the proof is written in latex, why don't just copy it here, so one doesn't have to search through the linked document. $\endgroup$ – Viktor Glombik Feb 8 at 16:27
  • $\begingroup$ The claim is not true for $n=1$. For $n=2$ you can just draw the square spiral. My thought would be to use induction on $n$, showing you can build up the new faces of the hypercube. You should extract the proof from the linked paper, which seems to be about something else, and describe it here. $\endgroup$ – Ross Millikan Feb 8 at 17:05

Your Answer

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

Browse other questions tagged or ask your own question.