Infinite cube and divisible sums

elementary-number-theory

Given is an infinite cube, extended infinitely in all directions. Is it possible to place each positive integer exactly once, so that for any positive integer $n$, the sum of the numbers in any $n\times n\times n$ cube is divisible by $n$?

The condition is trivial when $n=1$, but already gets interesting for $n=2$. If we only care about $n=2$, it should not be hard by iterative construction to make sure that the sum of any $2\times 2\times 2$ cube is even. The difficulty comes in because of higher $n$. For values of $n$ that are coprime (such as $2$ and $3$), it may be helpful to use the Chinese Remainder Theorem, though it is unclear how we would maintain the requirement that every positive integer gets used exactly once.

Best Answer

I'll give an inductive construction -- sorry this turned out to be a long answer, I probably included too many details. The main idea is that since we're in three dimensions (in fact this works for any number of dimensions $\geq 2$), the constraints are actually not so restrictive, so there's enough freedom to insert whatever numbers are missing as we go.

Let's say a labelling of the points in $C_n := \{0, \dots, n-1\}^3$ (i.e. a function $C_n \to \mathbb{N}$) is $k$-good if the sum of the numbers in each $k \times k \times k$ subcube is divisible by $k$, and say that the labelling is good if it is $k$-good for each $1 \leq k \leq n$. Note that by the CRT, to show a labelling is good, it suffices to show that it's $k$-good for all prime power $k$ in this range.

Similarly say that a labelling $C_n \to \mathbb{Z}/p^k\mathbb{Z}$ is $p^\ell$-good (where $\ell \leq k$) if the same condition holds, and is good if it is $p^\ell$-good for $1 \leq \ell \leq k$. Then it follows that $f : C_n \to \mathbb{N}$ is good if and only if $f$ mod $q$ is good for each maximal prime power $q \leq n$ (where $q = p^k$ is maximal if $p^{k+1} > n$).

We will show the following:

Proposition. Given a good labelling $f : C_n \to \mathbb{N}$ with all labels distinct, such that $\{1, \dots, n\}$ appear as labels, we can extend $f$ to a good labelling $f' : C_{n+1} \to \mathbb{N}$ with all labels distinct, such that $\{1, \dots, n+1\}$ appear as labels.

Step 1: For each prime $p \leq n+1$, extend $f$ mod $p$ to a $p$-good labelling $f_p : C_{n+1} \to \mathbb{Z}/p\mathbb{Z}$.

For a candidate $f_p$ extending $f$ mod $p$, since $f$ is $p$-good the only constraints we need to check are that $$\sum_{y \in C_p} f_p(x - y) \equiv 0 \text{ (mod $p$)}$$ for each $x = (x_1, x_2, x_3) \in C_{n+1} \setminus C_n$ with $x_1, x_2, x_3 \geq p-1$. Each such constraint uniquely determines $f_p(x)$ for such an $x$ in terms of $f_p(x')$ for $x'$ with $x_1' + x_2' + x_3' < x_1 + x_2 + x_3$. It follows that we are free to set the values of $f_p(x)$ for those $x \in C_{n+1} \setminus C_n$ with some $x_i < p-1$ (particularly $x = (n, 0, 0)$), and $f_p(x)$ will be uniquely determined for the other points $x \in C_{n+1} \setminus C_n$.

Step 2: If $p^k$ is not maximal, given a good labelling $f_{p^k} : C_{n+1} \to \mathbb{Z}/p^k\mathbb{Z}$ which extends $f$ mod $p^k$, find a good labelling $f_{p^{k+1}} : C_{n+1} \to \mathbb{Z}/p^{k+1}\mathbb{Z}$ extending $f$ mod $p^{k+1}$.

We will take a candidate $f_{p^{k+1}}$ extending $f$ mod $p^{k+1}$ which agrees with $f_{p^k}$ mod $p^k$. Then using $f_{p^k}$ to denote the corresponding function $C_{n+1} \to \{0, \dots, p^k-1\}$, we can write $f_{p^{k+1}}(x) = f_{p^k}(x) + p^k g(x)$, for some $g : C_{n+1} \to \{0, \dots, p-1\}$. Note that $g(x)$ is determined for $x \in C_n$ since we assumed that $f_{p^{k+1}}$ extends $f$. We know that $f_{p^{k+1}}$ is $p^\ell$-good for $\ell \leq k$, since we assumed that $f_{p^k}$ was good. Thus we only need to check that it is $p^{k+1}$-good, and since $f$ was $p^{k+1}$-good, the only constraints to check are that $$\sum_{y \in C_{p^{k+1}}} g(x - y) \equiv - \frac{1}{p^k} \sum_{y \in C_{p^{k+1}}} f_{p^k}(x - y) \text{ (mod $p$)}$$ for each $x = (x_1, x_2, x_3) \in C_{n+1} \setminus C_n$ with $x_1, x_2, x_3 \geq p^{k+1}-1$. Similar to the argument in step 1, we are free to choose the values of $g(x)$ for $x \in C_{n+1} \setminus C_n$ with some $x_i < p^{k+1} - 1$ (including $x = (n, 0, 0)$), and $g(x)$ is uniquely determined on the rest of $C_{n+1} \setminus C_n$.

Step 3: Given $f_q$ for all maximal prime powers $q \leq n+1$, construct an extension $f'$ of $f$ to $C_{n+1}$ which agrees with each $f_q$ mod $q$.

For a candidate $f'$ agreeing with $f$ on $C_n$, the only constraints are that $f'(x) \equiv f_q(x)$ (mod $q$) for all $x \in C_{n+1} \setminus C_n$ and maximal $q$. By the CRT, these constraints indeed admit solutions, and in particular, since they only determine $f'(x)$ modulo some large factor, we can choose these labels $f'(x)$ so that all labels are distinct. If $n+1$ was already a label appearing in $f$, then any such choice of $f'$ will do. In the case where $n+1$ did not appear, then since in steps 1 and 2 we could freely set each $f_{p^k}(n, 0, 0)$, we can ensure that each $f_q(n, 0, 0) \equiv n+1$ (mod $q$), in order to label $f'(n, 0, 0) = n+1$. Since $f_q = f'$ mod $q$ is good for each $q$, $f'$ is good, and so it satisfies all of our conditions.

Iteratively extending the initial labelling $f(0, 0, 0) = 1$, we get the desired labelling of $\{0, 1, 2, \dots\}^3$, which includes each positive number exactly once. If you wanted a labelling of $\mathbb{Z}^3$, that can also be done by instead using the domain cubes $\cdots \subset \{-n, \dots, n\}^3 \subset \{-n, \dots, n+1\}^3 \subset \{-n-1, \dots, n+1\}^3 \subset \cdots$.

Related Question