colorings of ${\mathbb Z}^d$ with constraints

Question

For a lattice $\mathbb Z^d$, denote by lattice line any line that contains two (and thus infinitely many) lattice points.

For $2\le k<n$, define a $(n,k)$-coloring, or $C_d(n,k)$ for short, as a $n$-coloring $\mathbb Z^d\to \{0,1,\dots,n-1\}$ such that

• in each lattice line, exactly $k$ colors occur,
• each color is used for at least $2$ points of $\mathbb Z^d$.

It seems obvious that a $C_d(n,k)$, if it exists, must always be periodic in all directions (i.e. on each lattice line), although I cannot see a simple argument for that. Possibly there are some parallels with the Hales-Jewett theorem.

• Is there an easy proof for the periodicity?

For a periodic coloring $C_d(n,k)$, let $D$ be a fundamental domain, i.e. a colored minimal cuboid such that its periodic continuation in all coordinate directions yields the given coloring. Some easy examples, all for $k=2$:

• For a prime $p$, let $D$ be a $p\times p$ diagonal matrix with $r$ 1’s and $p-r$ 2’s on the diagonal, where $0<r<p$. This yields a $C_2(3,2)$.
• A $C_2(3,2)$ is also obtained by $D= \pmatrix{ 0 & 0 & 0 & 1\\ 0 & 2 & 0 & 2 \\ 0 & 0 & 0 & 1\\ 1 & 2 & 1 & 2 }$ or $D= \pmatrix{ 0 & 0 & 0 & 1\\ 1 & 2 & 1 & 2 }$. Note that the last $D$ is not square.
• EDIT: this one doesn't work for $d>2$. For a prime $p$, take for $D$ the cube $\{0,1,\dots,p-1\}^d$ with a point $x\in D$ getting color $d-\#x$, where $\#x$ is the number of coordinates equal to zero. It is easy to check that this yields a $C_d(d+1,2)$ for each prime $p$; these colorings will be called "simplex constructions". The special case $d=2$ yields $C_2(3,2)$'s which are again non-isomorphic to the above ones, with e.g. $D= \pmatrix{ 0 & 1 & 1\\ 1 & 2 & 2 \\ 1 & 2 & 2 }$ for $p=3$.
• A $C_d(2^d,2)$ is defined by a $2^d$-hypercube $D$ in which each color is used once (and it is not hard to see that all $C_d(2^d,2)$ are of this form). We may call this one the "rainbow construction" and note that it generalizes immediately to a $C_d(k^d,k)$. For this one, $k$ does not need to be a prime!

Questions:

• For which triples $(d,n,k)$ do such colorings $C_d(n,k)$ exist?
• Which periods (i.e. side lengths of $D$) can occur for a given triple?
• Are there other examples where $D$ is not a hypercube?

It seems like there are no $C_d(n,2)$ for $n>d+1$ unless $n=2^d$. Is there an easy way to prove that?

Now for $k>2$, apart from the rainbow construction, it is much harder to find general constructions. I wonder if it is possible to tweak certain combinatorical designs in order to obtain a suitable $D$ or, for dimension $d=2$, to build one from an appropriate set of latin squares. Or is there a construction for $k=3$ based on the above simplex constructions?
As $k$ grows, searching for small $D$'s by hand feels a bit like solving a sudoku. While a $C_2(6,3)$ is still quite easy to find (e.g. $D= \pmatrix{ 0 & 1 & 2 & 0\\ 1 & 2 & 1 &3 \\ 0 & 1 & 2 & 0\\ 4& 3&4&5 }$), I have the impression that no $C_2(n,3)$ exists for $n>6$, except of course $n=9=3^2$. The following question seems well motivated:

For given naturals $d,k\ge2$, denote by $m(d,k)$ the biggest $n<k^d$ such that a $C_d(n,k)$ exists. What are good lower and upper bounds for $m(d,k)$ ?

By the above, we have supposedly $m(d,2)=d+1$ and $m(2,3)=6$.

Answer 1

No there are non-periodic colourings of this type.

Start off with a periodic $(n,k)$ lattice colouring and generate a new $(2n,2k)$ lattice colouring by splitting each of the $n$ colours into two "hues". Let the original colours be $\{2,4,6,\ldots,2n\}$ and the new colours be $\{1,2,3,\ldots,2n\}$. If $\xi$ is your original lattice colouring, you can make the new lattice colouring, $\tilde\xi$ by randomly choosing $\tilde\xi_{\mathbf j}$ to be either $\xi_{\mathbf j}$ or $\xi_{\mathbf j}-1$.

To see that this is indeed a $(2n,2k)$-colouring, firstly it's obvious that there are $2n$ colours. Now for any lattice line, it's easy to check by Borel-Cantelli II that it contains all $2k$ hues of the original $k$ colours with probability 1. Since there are countably many lines, it's a probability 1 event that all lattice lines are coloured with exactly $2k$ colours.

Answer 2

A periodic $(n,k)$ coloring can be modified to give a non-periodic $(mn+\ell,mk+\ell)$ coloring for any non-negative $m,\ell$ not both $0$ (this uses some comments to improve my previous answer, although there seem to be even better answers given) ). This is a modification of Anthony's construction without need of probabilities. This allows the periodic $(3,2)$-colorings to give non-periodic $(a+b,a)$ colorings for any $a \ge 2b$ (except $(a+b,a)=(3,2)$)

Let the $n$ colors be $\{{1,2,\cdots ,n\}}$ and let the new colors be $c_i$ for $1 \le i \le m$ and $1 \le c \le n$ along with new colors $-1,-2,\cdots,-\ell.$ Start with the $(n,k)$ coloring and draw imaginary circles (or spheres etc.) centered at the origin of radii $3.5,3.5^2,3.5^3,...$ This splits the lattice points into concentric zones. Go through the zones and in each do one of the following (being sure to do each thing infinitely often in each possible way)

• change each color $c$ to $c_i$ (for an $1 \le i \le m$ constant on that zone.)

• change everything to $-j$ (for a $1 \le j \le \ell$, constant on that zone)

The lattice points on a lattice line occur with equal spacing so eventually (as you travel along a line, increasing the distance from the origin) you will experience a full period (maybe several) all in a single zone, then several full periods in the next zone etc.

Answer 3

If we change the setup and require that each line have infinitely many points of every color, we can extend Anthony Quas's idea to show that you can add any two patterns. That is, if there is a $C_d(n_1,k_1)$ and a $C_d(n_2, k_2)$, there is a $C_d(n_1 + n_2, k_1 + k_2)$. Overlay the two patterns, and at each lattice point, pick randomly which pattern to display. With probability 1, every line will contain infinitely many points of each color it contained in the original patterns. In particular, there is a $C_d(1,1)$, so given a $C_d(n,k)$, we can find a $C_d(n+1,k+1)$.

If we only want periodic patterns, you can replace the random mask we chose with another periodic pattern. Pick a prime which doesn't divide the periods of the two patterns, and construct a $C_d(2,2)$ with that period, then overlay the three patterns and choose which of the two original ones to display based on the color of the third. (Note that this doesn't require the periods of the original patterns to be relatively prime.)

If we do have relatively prime periods for our $C_d(n_1,k_1)$ and $C_d(n_2, k_2)$, then we can produce a $C_d(n_1 n_2, k_1 k_2)$, just by overlaying the two and taking the new colors to be ordered pairs of colors from the two patterns.

Like I said in the comments, I don't think your simplex construction actually works for $d>2$, but it's fine for $d=2$. You can make a slightly more general construction for a $C_2(2k-1,k)$ with period $p^{k-1}$: Given a lattice point $(x,y)$, let $n_x$ be the number of times $p$ divides $x$, up to a maximum of $k-1$, and similarly for $n_y$. Then color the point $(x,y)$ with the number $n_x + n_y$.

Since we're free to add $1$ to both $n$ and $k$, this means we can construct every $C_2(n,k)$ for $k \leq n < 2k$. By adding these to the rainbow constructions which give us $C_2(k^2,k)$, we can also fill chunks of the range $2k \leq n \leq k^2$, in particular, something like the range $k \leq n < C k^2$ for some $C < 1$. There are no $C_2(n,k)$ for $n > k^2$, so we have the asymptotic answer.