5
$\begingroup$

Given any function $f: \mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$ we define the environment sum of $(x,y)\in\mathbb{Z}\times \mathbb{Z}$ with respect to $f$ by $$\text{es}_f(x,y) = \sum\{f(x', y'): |(x',y') - (x,y)|=1\}.$$ Question. Is there a bijection $\varphi:\mathbb{Z}\times \mathbb{Z} \to \mathbb{Z}$ such that there is an integer $K\geq 0$ such that for all $(x,y)\in \mathbb{Z}\times\mathbb{Z}$ the following holds?

whenever $(x',y')\in \mathbb{Z} \times \mathbb{Z}$ with $|(x',y') - (x,y)|=1$ then $|\text{es}_\varphi(x,y) - \text{es}_\varphi(x',y')|<K$.

Bonus question in case of Yes above. (Need not be answered for acceptance) If yes, what is the smallest possible value for the constant $K$?

$\endgroup$
2
  • 3
    $\begingroup$ And which norm is $|(x,y)|$ ? $\endgroup$ Commented Jul 4, 2019 at 12:57
  • 4
    $\begingroup$ Sorry forgot to specify this. I mean the Euclidean norm, i.e. $|(x,y)| = (x^2+y^2)^{1/2}$ for all $x,y \in \mathbb{Z}$. Equivalently we could take the "taxi norm" $|(x,y)| = |x| + |y|$ as $|(x,y)|= 1$ (in the Euclidean norm) iff $|(x,y)|= 1$ in the taxi norm for $x,y\in \mathbb{Z}$. $\endgroup$ Commented Jul 4, 2019 at 13:14

1 Answer 1

5
$\begingroup$

There exist bijections $f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ with $\text{es}_f(x,y)$ vanishing identically, which directly answer the bonus question.

Note that the infinite set of equations that such a bijection must satisfy, $$\begin{align} {f(x,y+1)+f(x,y-1)+f(x+1,y)+f(x-1,y)=0,\\ \forall (x,y)\in \mathbb{Z}\times\mathbb{Z},} \end{align}\tag{1}$$ splits into two disjoint subsets of equations, according to the parity of $x+y$. Therefore we may express this $f$ gluing two maps:

$$\begin{equation}f(x,y)=\cases{g\big({x+y\over2},{x-y\over2}\big)&if $x+y=0\mod 2$\\ \\ h\big({x+y+1\over2},{x-y+1\over2}\big)&if $x+y=1\mod 2$ } \tag{2}\end{equation}$$ where $g:\mathbb{Z}\times\mathbb{Z}\to G$ and $h:\mathbb{Z}\times\mathbb{Z}\to H$ are bijections onto complementary subset $G$, resp., $H$, of $\mathbb{Z}$, and satisfy, for all $(u,v)\in\mathbb{Z}\times\mathbb{Z}$ the equations $$\begin{equation}g(u,v)+g(u+1,v)+g(u,v+1)+g(u+1,v+1)=0 \tag{3}\end{equation}$$ $$\begin{equation}h(u,v)+h(u+1,v)+h(u,v+1)+h(u+1,v+1)=0 \tag{3'}\end{equation}$$ which translate $(1)$. We may choose $G:=3\mathbb{Z}$ and $H:=\mathbb{Z}\setminus3\mathbb{Z}$, and proceed to construct bijections $g:\mathbb{Z}\times\mathbb{Z}\to 3\mathbb{Z}$ and $h:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}\setminus3\mathbb{Z}$ satisfying $(3)$ and $(3')$, thus producing via $(2)$ a bijection $f:\mathbb{Z}\times\mathbb{Z}\to \mathbb{Z}$ satisfying $(1)$ as promised.

Let $A$ the set of nonnegative integer numbers of the form $a=\sum_{k=0}^p a_i 9^{i}$ with $a_i\in\{0,1,2\}$, that is, those $a\in\mathbb{ Z}_+$ whose base $3$ expansion is supported on the even-order places. So $B:=3A$ is the set of the nonnegative numbers $b$ whose base $3$ expansion is supported on the odd-order places.

Recall:

Elementary fact: Every $n\in\mathbb{Z}$ can be expressed uniquely as $a-b$. In other words, every integer $n$ has a unique base $-3$ expansion. We can summarize it with the (slightly abusing?) notation $$\begin{equation}\mathbb{Z}=A\oplus(-3A)\tag{4}\end{equation}$$ and with the same meaning, always looking at the digits in base $-3$,

$$\begin{equation}\mathbb{Z}\setminus3\mathbb{Z}= (A\setminus9A)\oplus(-3A)\tag{4'}\end{equation}.$$

Note the bijection $\alpha:\mathbb{Z}\to A$ defined by $\alpha(u):=\sum_{i=0}^p u_i9^{i}\in A $ for all $u:=\sum_{i=0}^p u_i(-3)^i\in \mathbb{Z}$. So $\mathbb{Z}\ni v\mapsto3\alpha(v)\in B$ is a bijection too. Also note $u=\alpha(u)=3\alpha(u)\mod 2$.

Then define:

$$g(u,v):=(-1)^{u+v}\big(3\alpha(u)-9\alpha(v)\big),$$ which immediately satisfies equations $(3)$. To check that $g$ is a bijection $\mathbb{Z}\times\mathbb{Z}$ onto $3\mathbb{Z}$ as stated, note that the equation $g(u,v)=3n$ is equivalent to $(-1)^nn= \alpha(u)-3\alpha(v) $ (recall that $u=\alpha(u)=3\alpha(u)\mod 2$ for all $u$). The bijectivity then follows from the above mentioned elementary fact $(4)$, in addition to the maps $$\begin{align} \mathbb{Z}\ni n&\mapsto (-1)^nn\in \mathbb{Z},\\ \mathbb{Z}\ni u&\mapsto \alpha(u)\in A, \\ \mathbb{Z}\ni v&\mapsto 3\alpha(v)\in 3A, \end{align}$$ all being bijective.

In order to define the map $h:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}\setminus3\mathbb{Z}$ we need a further bijection $\phi:\mathbb{Z} \to \mathbb{Z} \setminus 3 \mathbb{Z} $ such that $u=\phi(u)\mod 2$. Clearly there exist such maps because $\mathbb{Z} \setminus 3 \mathbb{Z} $ contains infinitely many odd and infinitely many even numbers; one can easily check that an example is $$\displaystyle\phi(u):={3u+\omega(u)\over 2},$$ where $\omega$ is $4$-periodic, $\omega(0)=-4$, $\omega(1)=-1$, $\omega(2)=-2$, $\omega(3)=1$). Moreover, since $\alpha(\mathbb{Z} \setminus 3 \mathbb{Z} )=A\setminus9A$, we obtain by composition a bijection $\alpha\circ\phi:\mathbb{Z} \to A\setminus9A$. Again, $\alpha(\phi(u))=\phi(u)=u\mod 2$ holds for all $u\in\mathbb{Z}$.

Finally define: $$h(u,v):=(-1)^{u+v}\big(\alpha(\phi(u))-3\alpha(v) \big),$$ which again immediately satisfies $(3')$. To check that $h$ is a bijection of $\mathbb{Z}\times\mathbb{Z}$ onto $\mathbb{Z}\setminus 3\mathbb{Z}$, note that the equation $h(u,v)=m\in \mathbb{Z}\setminus 3\mathbb{Z}$ is equivalent to $(-1)^mm= \alpha(\phi(u))-3\alpha(v)$, because $\alpha(\phi(u))-3\alpha(v)=u+v\mod 2$. The bijectivity then follows by the elementary fact $(4')$, together with the bijectivity of the maps $$\begin{align} \mathbb{Z}\ni m&\mapsto (-1)^mm\in \mathbb{Z},\\ \mathbb{Z}\ni u&\mapsto \alpha(\phi(u))\in A\setminus9A, \\ \mathbb{Z}\ni v&\mapsto 3\alpha(v)\in 3A, \end{align}$$ concluding the proof.

$\endgroup$
3
  • 1
    $\begingroup$ Note that Catholics write $f(x,y+1)+f(x,y-1)+f(x+1,y)+f(x-1,y)$ while Orthodoxians have $f(x,y+1)+f(x,y-1)+f(x-1,y)+f(x+1,y)$. $\endgroup$ Commented Jul 19, 2019 at 5:35
  • 1
    $\begingroup$ Thanks Pietro for this wonderful answer and your effort of writing this up in such an understandable manner! $\endgroup$ Commented Jul 19, 2019 at 5:42
  • $\begingroup$ I had the impression that the inverse map of $f$ (or of some version of it) $$f^{-1}:\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}$$ is a sort of discrete Peano curve. Note that the Peano square filling curve is based on merging ternary expansions too... $\endgroup$ Commented Jul 19, 2019 at 6:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .