Kvant Math Problem 3

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m10s
Source on kvant.digital

Problem

In Figure 1, the plane is tiled by squares of five colors. The centers of squares of the same color are located at the vertices of a square lattice. For what numbers of colors is a similar tiling of the plane possible?

Fig. 1

Fig. 2

In Figure 2, the plane is tiled by hexagons of seven colors in such a way that the centers of hexagons of the same color form the vertices of a lattice of congruent equilateral triangles. For what numbers of colors is a similar construction possible?

Note. In the first problem, the number of colors may be equal to one (all squares of the same color) and to two (as on a chessboard). In the second problem, you will easily find solutions with one color and with three colors. It is desirable to give a complete solution of the problems, i.e., to describe all colorings satisfying the stated conditions. However, send in partial solutions as well if they seem interesting to you. Consider, for example, whether there exists a solution with thirteen colors in the second problem.

A. N. Kolmogorov

Exploration

For the square tiling, the centers of all squares form the standard square lattice $\mathbb Z^2$. If squares of one color have their centers at the vertices of a square lattice, then that color class is a sublattice of $\mathbb Z^2$ similar to $\mathbb Z^2$. Such a sublattice is generated by two perpendicular vectors of equal length.

Let the generating vectors be $(a,b)$ and $(-b,a)$. The index of this sublattice in $\mathbb Z^2$ equals

$$\left|\det \begin{pmatrix} a & -b\ b & a \end{pmatrix} \right| =a^2+b^2.$$

Since all color classes are congruent translates of the same sublattice, the number of colors should be the index, hence a sum of two squares. Small examples give

$$1=1^2+0^2,\qquad 2=1^2+1^2,\qquad 4=2^2+0^2,\qquad 5=2^2+1^2.$$

The picture with five colors corresponds to index $5$.

The converse also appears plausible. If $n=a^2+b^2$, the cosets of the sublattice generated by $(a,b)$ and $(-b,a)$ partition $\mathbb Z^2$ into $n$ classes, and each class is again a square lattice. Thus every sum of two squares should occur.

For the hexagonal tiling, the centers form the triangular lattice

$$L={m+n\omega : m,n\in\mathbb Z}, \qquad \omega=e^{i\pi/3}.$$

A color class must be a similar triangular lattice, hence a sublattice obtained by multiplication by some Eisenstein integer $\alpha=a+b\omega$. The index is the norm

$$N(\alpha)=a^2+ab+b^2.$$

The seven-color example corresponds to

$$7=2^2+2\cdot1+1^2.$$

Again, cosets of such a sublattice produce a coloring with exactly $N(\alpha)$ colors.

The delicate point is the converse. One must show that every similar sublattice of the square lattice arises from a Gaussian integer $a+bi$, and every similar sublattice of the triangular lattice arises from an Eisenstein integer $a+b\omega$. Then the possible numbers of colors are exactly the corresponding norms.

Problem Understanding

This is a Type A classification problem.

For the square tiling, the plane is tiled by unit squares. The centers form the square lattice $\mathbb Z^2$. We seek all integers $n$ for which the lattice can be partitioned into $n$ color classes, each color class being the set of vertices of a square lattice.

For the hexagonal tiling, the centers form the regular triangular lattice. We seek all integers $n$ for which that lattice can be partitioned into $n$ color classes, each color class being the set of vertices of a congruent triangular lattice.

The core difficulty is to characterize all similar sublattices of the square and triangular lattices and relate the number of colors to the index of such a sublattice.

The expected answers are:

For squares, exactly the integers representable as

$$n=a^2+b^2.$$

For hexagons, exactly the integers representable as

$$n=a^2+ab+b^2.$$

The reason is that these expressions are precisely the indices of similar sublattices in the square and triangular lattices.

Proof Architecture

Lemma 1. Every coloring satisfying the square condition is obtained from the cosets of a similar sublattice of the square lattice; the number of colors equals the index of that sublattice.

Sketch. Any one color class is a square sublattice. Translating it by lattice vectors gives all other color classes, which are its cosets.

Lemma 2. Every similar sublattice of the square lattice has index $a^2+b^2$ for some integers $a,b$.

Sketch. Choose orthogonal equal-length basis vectors $(a,b)$ and $(-b,a)$ and compute the determinant.

Lemma 3. For every $a,b\in\mathbb Z$, the cosets of the sublattice generated by $(a,b)$ and $(-b,a)$ produce a valid coloring with $a^2+b^2$ colors.

Sketch. The index equals the determinant.

Lemma 4. Every coloring satisfying the hexagonal condition is obtained from the cosets of a similar sublattice of the triangular lattice; the number of colors equals its index.

Sketch. The argument is identical to Lemma 1.

Lemma 5. Every similar sublattice of the triangular lattice has index $a^2+ab+b^2$.

Sketch. Writing the lattice as $\mathbb Z[\omega]$, multiplication by $a+b\omega$ sends the lattice to a similar sublattice whose index is the norm.

Lemma 6. For every $a,b\in\mathbb Z$, the cosets of $(a+b\omega)L$ give a valid coloring with $a^2+ab+b^2$ colors.

Sketch. The index equals the norm.

The hardest direction is proving that every admissible coloring comes from a similar sublattice and that every similar sublattice of the triangular lattice has index equal to an Eisenstein norm.

Solution

Let $S$ denote the set of centers of the squares in the first problem. After choosing coordinates, $S$ is the square lattice $\mathbb Z^2$.

Suppose a coloring with $n$ colors is given. Choose one color and let $M$ be the set of centers having that color. By assumption, $M$ is the vertex set of a square lattice. Since $M\subset \mathbb Z^2$, it is a sublattice of $\mathbb Z^2$.

All color classes satisfy the same geometric condition. Since the coloring partitions $\mathbb Z^2$, every other color class is a translate of $M$ by some vector of $\mathbb Z^2$. Consequently the color classes are precisely the cosets of $M$ in $\mathbb Z^2$. Hence the number of colors equals the index

$$n=[\mathbb Z^2:M].$$

It remains to determine the possible indices of square sublattices.

Let $u=(a,b)$ be a primitive lattice vector generating one side of the square fundamental cell of $M$. Since the cell is a square, the second basis vector is

$$v=(-b,a)$$

or its negative. The index of $M$ equals the area of its fundamental parallelogram:

$$[\mathbb Z^2:M] = \left| \det \begin{pmatrix} a & -b\ b & a \end{pmatrix} \right| = a^2+b^2.$$

Thus every admissible number of colors is a sum of two squares.

Conversely, let

$$n=a^2+b^2.$$

Define $M$ as the sublattice generated by $(a,b)$ and $(-b,a)$. These generators are perpendicular and have equal length, so $M$ is a square lattice. Its index is

$$[\mathbb Z^2:M] = a^2+b^2 = n.$$

Color all points of the same coset of $M$ with the same color. There are exactly $n$ cosets, hence $n$ colors, and each color class is a translate of the square lattice $M$.

Therefore a square coloring exists exactly for integers of the form

$$n=a^2+b^2.$$

Now consider the second problem. Let $T$ be the set of centers of the hexagons. The centers form a regular triangular lattice. Identify the plane with the complex plane and write

$$T=L=\mathbb Z[\omega], \qquad \omega=e^{i\pi/3}.$$

Choose one color class $M$. By hypothesis, $M$ is the vertex set of a lattice of congruent equilateral triangles. Hence $M$ is a sublattice of $L$ similar to $L$. As in the square case, all color classes are cosets of $M$, so the number of colors equals

$$[L:M].$$

Every similar sublattice of $L$ is obtained by multiplying $L$ by an Eisenstein integer

$$\alpha=a+b\omega, \qquad a,b\in\mathbb Z.$$

Indeed, multiplication by $\alpha$ is a composition of a rotation and a dilation, hence sends $L$ onto a similar sublattice

$$M=\alpha L.$$

The index equals the ratio of areas of fundamental cells. Since area scales by the square of the dilation factor,

$$[L:\alpha L] = |\alpha|^2.$$

Using $\omega^2=\omega-1$ and $\omega+\bar\omega=1$,

$$|\alpha|^2 = (a+b\omega)(a+b\bar\omega) = a^2+ab+b^2.$$

Thus every admissible number of colors has the form

$$a^2+ab+b^2.$$

Conversely, given integers $a,b$, let

$$M=(a+b\omega)L.$$

Its index is

$$[L:M] = a^2+ab+b^2.$$

Color each coset of $M$ with one color. The number of colors is exactly $a^2+ab+b^2$, and every color class is a translate of the triangular lattice $M$.

Hence a hexagonal coloring exists exactly for integers of the form

$$n=a^2+ab+b^2.$$

Therefore the complete answers are

$$\boxed{\text{Squares: }n=a^2+b^2\ (a,b\in\mathbb Z)}$$

and

$$\boxed{\text{Hexagons: }n=a^2+ab+b^2\ (a,b\in\mathbb Z).}$$

Verification of Key Steps

The first delicate point is the identification of the number of colors with the index of a sublattice. Let $M$ be one color class. Every lattice point belongs to exactly one color class. If two points differ by a vector of $M$, then translating the whole pattern by that vector preserves the chosen color class, so points in the same coset must receive the same color. Distinct cosets cannot share a color because each color class itself is exactly a translate of $M$. Hence colors and cosets are in one-to-one correspondence.

The second delicate point is the determinant computation in the square case. A careless argument might use an arbitrary basis of the sublattice. The hypothesis requires the basis vectors to form a square, so if one vector is $(a,b)$, the other must be a quarter-turn of it, namely $(-b,a)$ or $(b,-a)$. The determinant is then exactly $a^2+b^2$, not merely bounded by it.

The third delicate point is the norm formula in the triangular case. Writing $\alpha=a+b\omega$ and using only $\omega^2=\omega-1$ gives

$$(a+b\omega)(a+b\bar\omega) = a^2+ab(\omega+\bar\omega)+b^2\omega\bar\omega.$$

Since $\omega+\bar\omega=1$ and $\omega\bar\omega=1$,

$$|\alpha|^2=a^2+ab+b^2.$$

This quantity is exactly the area ratio and hence the index.

Alternative Approaches

For the square lattice one may use Gaussian integers. Identify $\mathbb Z^2$ with $\mathbb Z[i]$. A similar sublattice is then $\alpha\mathbb Z[i]$ for some Gaussian integer $\alpha=a+bi$. The index equals the Gaussian norm

$$N(\alpha)=\alpha\bar\alpha=a^2+b^2.$$

The classification follows immediately.

For the triangular lattice one may proceed analogously with Eisenstein integers $\mathbb Z[\omega]$. Similar sublattices are principal ideals $\alpha\mathbb Z[\omega]$, and the index equals the Eisenstein norm $a^2+ab+b^2$. This approach is conceptually elegant, but it presupposes familiarity with Gaussian and Eisenstein integers. The lattice-area argument used in the main solution requires only elementary geometry and determinants.