Cats in cubes

Noga Alon, Noah Kravitz

This paper, "Cats in Cubes," by Noga Alon and Noah Kravitz, provides a definitive answer to a playful yet deep combinatorial question: if you fill a $d$-dimensional grid with the letters C, A, and T, what is the maximum number of times the word "CAT" can appear?

TL;DR

Using tools from spectral graph theory and Fourier analysis, the authors prove that the word "CAT" can appear at most $(3^{d-1}/2)n^d$ times in a $d$-dimensional cube of side length $n$. This result confirms a previous conjecture for the 2D case and generalizes the problem to higher dimensions and a wider variety of words.

What Problem Does This Paper Address?

The problem originates from a "wordsearch" style puzzle. Imagine an $n \times n$ grid where each cell contains a C, A, or T. We count an occurrence of "CAT" if the letters appear consecutively in a straight line—horizontally, vertically, or diagonally.

In 2022, Patchell and Spiro investigated this in two dimensions. They showed that the number of "CAT"s is at most $2n^2$ and constructed a specific "striped" labeling that achieved $(3/2)n^2$ occurrences, conjecturing that this was the best possible asymptotic result. Alon and Kravitz set out to prove this conjecture, determine the exact maximum for any dimension $d$, and identify the specific patterns (labelings) that reach that maximum.

Methods

The authors move the problem from a standard grid to a discrete torus $(\mathbb{Z}/n\mathbb{Z})^d$. This "gluing" of opposite sides simplifies the math by removing boundary effects, which only contribute negligible $O(n^{d-1})$ terms anyway.

The core of the proof relies on spectral graph theory. They define an adjacency matrix $M$ for a Cayley graph where an edge exists between two points if they are "one step apart" in any direction (including diagonals).

  1. Eigenvalue Analysis: They use Fourier analysis (specifically the characters of the group $(\mathbb{Z}/n\mathbb{Z})^d$) to explicitly calculate the eigenvalues of $M$.
  2. Quadratic Forms: They define a function $f$ that maps points to $1$ (if labeled 'A') or $-1$ (if labeled 'C' or 'T'). By expressing the count of "AC" and "AT" pairs as a quadratic form $f^T M f$, they use the smallest eigenvalue of the matrix to establish a rigorous upper bound.
  3. Triple Counting: Since every "CAT" is composed of an "AC" pair and an "AT" pair sharing the same "A", bounding these pairs effectively bounds the total number of "CAT" triples.

Datasets

Not discussed in the paper. This is a theoretical mathematics paper; the results are derived through formal proofs rather than empirical testing on datasets.

Key Insights and Ideas

  • The Centrality of 'A': The word "CAT" is a triple $(x, x+y, x+2y)$. The letter 'A' is the midpoint. The authors realized that the problem is essentially about how many "C"s and "T"s you can pack around "A"s.
  • Spectral Bounds: The maximum density of a word is fundamentally limited by the "spread" of the adjacency matrix's spectrum. Specifically, the most negative eigenvalue dictates how much you can "separate" the 'A's from the 'C's and 'T's to maximize the count.
  • Optimal Geometry: The optimal way to pack "CAT"s isn't a random jumble; it's highly structured. The "best" grids are made of hyperplanes (stripes in 2D) where 'A's occupy every even-indexed plane, and 'C's and 'T's alternate in the odd-indexed planes.

Key Results

  • The Bound: For a $d$-dimensional cube, the maximum number of "CAT" occurrences is exactly $(3^{d-1}/2)n^d$.
  • Equality Conditions: The authors characterize exactly when this maximum is reached. It requires $n$ to be a multiple of 4, and the labeling must follow a "generalized Patchell-Spiro" construction (the hyperplane stripes mentioned above).
  • Generalization to Other Words: The result extends to any word $w$ of length $r$ with distinct letters (like "LION" or "TIGER"). The bound for such words is $(3^{d-1}/(r-1))n^d$.
  • Repeated Letters: They show the method even works for some words with repeated letters, such as "FELINE," provided the repetitions don't create complex internal overlaps (like the "EL" in "ELEPHANT").

Limitations and Future Work

The authors note that while their spectral approach is powerful, it doesn't immediately provide a "one-size-fits-all" formula for every possible word. Words with complex internal symmetries or frequent letter repetitions (like "ALFALFA") would require a more nuanced analysis of how those specific patterns overlap within the grid. They leave the detailed exploration of these "messier" words as an exercise for interested readers.

Summary updated

Abstract

Answering a recent question of Patchell and Spiro, we show that when a $d$-dimensional cube of side length $n$ is filled with letters, the word $\mathsf{CAT}$ can appear contiguously at most $(3^{d-1}/2)n^d$ times (allowing diagonals); we also characterize when equality occurs and extend our results to words other than $\mathsf{CAT}$.
BibTeX
@article{alon2024cats,
  author = {Noga Alon and Noah Kravitz},
  title = {{Cats in cubes}},
  journal = {Electron. J. Comb.},
  year = {2024},
  doi = {10.37236/11735},
}

Loading related content...

Figure