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$
3
  • $\begingroup$ You should show your proof. Otherwise, it could be difficult to decide whether there is a simpler way. $\endgroup$
    – Peter
    Commented Feb 7, 2019 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$ Commented Feb 8, 2019 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$ Commented Feb 8, 2019 at 17:05

0

You must log in to answer this question.

Browse other questions tagged .