Suppose $H:\mathbb{N}\times\mathbb{N}\mapsto\mathbb{N}$ is a injective map. Let $C=\{c|c=H(i,j)-H(i-1,j)$ or $H(i,j)-H(i,j-1)\}$. Is $C$ an infinite set?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Notation is not nice but lets say for numbers, $\pm$ means $\{n\pm c\} = \{ n-c,n-c+1,\cdots,n+c\}$
Let me only consider the set $\{H(i,j)-H(i-1,j)\}$.
Note that, for fixed $j$, $H(i,j) \to \infty$ as $i\to \infty.$ Assume $H(i,j) - H(i-1,j) < c$.
Consider the set $\{n\pm c\}$, and note that for any $j$ there exists $n$ s.t. $H(1,j)\in \{n\pm c\}$ and further $H(i',j)\in \{n+k\pm c\}$ since they cannot make jumps larger than $c$ and it must tend to $\infty$.
Therefore, $|\{H(i,j)\in\{n \pm c \}\}|\to \infty$ as $n\to\infty$, which contradicts with injective.
$\begingroup$
$\endgroup$
2
Suppose that $|H(i,j)-H(i-1,j)|,|H(i,j)-H(i,j-1)|\le m$ for all $i,j\in\Bbb N$. If $0\le i,j\le k\in\Bbb N$, then
$$H(0,0)-2km\le H(i,j)\le H(0,0)+2km\,.$$
(My $\Bbb N$ includes $0$.) Thus, there are only $4km+1$ possible values for $H(i,j)$ with $i,j\le k$, but there are $(k+1)^2$ pairs $\langle i,j\rangle$ with $i,j\le k$. Clearly $(k+1)^2>4km+1$ for sufficiently large $k$, so $C$ must be infinite.
answered Nov 23, 2020 at 2:28