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$.