Q:
Let \(\mathbb{Z}^n\) be the integer lattice in \(\mathbb{R}^n\). Two points in \(\mathbb{Z}^n\) are called neighbors if they differ by exactly 1 in one coordinate and are equal in all other coordinates. For which integers \(n \geq 1\) does there exist a set of points \(S \subset \mathbb{Z}^n\) satisfying the following two conditions?
- If \(p\) is in \(S\), then none of the neighbors of \(p\) is in \(S\).
- If \(p \in \mathbb{Z}^n\) is not in \(S\), then exactly one of the neighbors of \(p\) is in \(S\).
A:
Remark:
If we can prove that a cross shape tessellates \(\mathbb{Z}^n\), then we satisfy conditions for a set S.
Proof:
To satisfy condition 1, we can form around every point in \(S\) a set of \(2n + 1\) points not in \(S\), calling the \(2n + 1\) points the \(\textit{spikes}\) and the point in \(S\) the \(\textit{center}\) for obvious reasons. We will call this shape a \(\textit{cross}\), based on the \(n=2\) case. We note that, as long as the spikes touch points not in S besides the center, then condition 2 is satisfied for all points in the cross. We also note that, no point in the cross can cause another point outside of it to neighbor a point in S, which means that a tessellation of crosses would satisfy both conditions. Then, this problem becomes a question of tessellating \(\mathbb{Z}^n\) with crosses.
Consider in \(\mathbb{Z}^n\), with coordinates \(x_1, ...., x_n\). Consider the line \(x_2 = ... = x_n = 0\), and see what happens along this line. First, we must have at some point a point in S, let us say at the origin, W.L.O.G. Now, we have the point immediately before it and immediately after it as the two spikes along the \(x_1\) axis. Now, expecting the density to be \(\frac{1}{2n +1}\), we try to find if there are \(2(n-1)\) points we can place along this line before reaching the same pattern. In fact, we can. Each point along the line represents a spike from another center, only offset by 1 in another one of the \(n-1\) dimensions. Denote by \(x_i^+\) the spike from the center which has \(x_i = 1\) and by \(x_i^-\) the center which has \(x_i = -1\). \(x_i^+\) can intuitively be thought of as the spike from the center “above” the line \(x_2 = ... = x_n = 0\) in terms of the coordinate \(x_i\). Also, note that \(x_1^+\) and \(x_1^-\) are already defined, simply as the points to the left and right of the origin. Also, let us define \(x_0\) as the center point in our sequence.
Now, the question is, does this line tessellate? Consider going from the line \(x_2 = ... = x_n = 0\) to \(x_j = 1, x_2 = ... = x_{j-1} = x_{j+1} = ... = x_n = 0\), incrementing the \(x_j\) coordinate by 1. Our same tessellation should hold, but it will be shifted. However, we also must note that the \(x_j = 0\) center is where the \(x_j^-\) spike is, simply by definition. Also, the \(x_j^+\) spike is now where the \(x_j = 1\) center is. In short, we should see that \(x_j^- \rightarrow x_0\), \(x_0 \rightarrow x_j^+\).
W.L.O.G, assume \(j = 2\).
Now, we have so far, we have in our sequence, \(x_1^-, x_0, x_1^+, ...\), where there are \(2(n-1)\) terms to fill in. First, let us rewrite so that \(x_1^-\) appears at the end, as the sequence should repeat anyways. Then, let us place \(x_2^\pm\) such that they satisfy the conditions so far. We have:
\[x_0, x_1^+, x_2^+, … , x_2^-, x_1^-\]
Turns, out, this is all we need. We can see that, if we shift this by 2 to the right, we have:
\[x_2^+, … , x_2^-, x_1^-, x_0, x_1^+\]
Which satisfies our one constraint. This holds for the line with \(x_2 = -1\) as well, which has \(x_2^+ \rightarrow x_0\), \(x_0 \rightarrow x_2^-\), only now we have shifted to the left by 2:
\[x_2^-, x_1^-, x_0, x_1^+, x_2^+, … \]
By the same argument, taking one step in each direction, we have:
\[x_0, x_1^+, x_2^+, …, x_n^+, x_n^-, … , x_2^-, x_1^-\]
Now, this tessellates in every direction, but we also should show that this tessellation is self-consistent. That is, if we go increment \(x_i\), then \(x_j\), do we get the same result as if we increment \(x_j\) then \(xi\)?
By construction, we do. Each time we increase the \(x_i\) coordinate by \(\pm1\), we shift the tessellation by \(\pm i\). In fact, if we place a center \(x_0\) at \((0,0)\), and we have the sequence: \(x_0, x_1^+, x_2^+, ..., x_n^+, x_n^-, ... , x_2^-, x_1^-\) along the \(x_1\)-axis, then we have that other line \(x_2 =k_2, ..., x_n = k_n\) is shifted by exactly:
\[\sum i k_i\]
This also allows us to explicitly give the set of all centers, which is precisely the set S. To clean up the notation, let the point \(k = (x_1 = k_1, x_2 =k_2, ..., x_n = k_n)\), and let \(f(k) = \sum i k_i\). Then, we have:
\[ S = \lbrace k \in \mathbb{Z}^n \; \vert \; f(k) = 0\pmod{2n + 1} \rbrace \]
Short Addendum
(By John Zhao, who could not resist adding this because once we have the construction, the proof of the question is actually three sentences.)
Define
\[ S = \lbrace p \in \mathbb{Z}^n \mid f(p) \equiv 0 \pmod{2n + 1} \rbrace \]
Then Condition 1 is true because given \(p \in S\) and any neighbor \(p'\) of \(p\) that differs by \(\pm 1\) from \(p\) in the \(i\)th direction, we have
\[ f(p’) = f(p) \pm i \equiv \pm i \not\equiv 0 \pmod{2n + 1} \]
since \(i \in \lbrace 1, 2, ..., n \rbrace\).
Condition 2 is true because given any \(p'\) not in \(S\), we know that \(f(p)\) has nonzero residual \(\pmod{2n + 1}\), and there exists a unique integer \(i \in \lbrace \pm 1, \pm 2, ..., \pm n \rbrace\) such that \(f(p') + i \equiv 0\), which identifies the unique neighbor of \(p'\) that is in \(S\).