Covering the ternary cube by binary subcubes

Abstract

For an integer $n\ge0$, let $f(n)$ be the minimum number of subcubes of $\mathbb{Z}_3^n$ of the form $A_1\times\cdots\times A_n$, where $|A_i|=2$ for every $i$, whose union covers $\mathbb{Z}_3^n$. A simple counting argument gives $f(n)\ge(3/2)^n$, while $f(n)=O(n(3/2)^n)$ by random construction. We prove that $f(n)\le2(3/2)^n-1$, answering a problem of Imre Leader. We also show that $f(n)/(3/2)^n$ is nondecreasing and there exists a constant $C_3$ such that $f(n)=(C_3+o(1))(3/2)^n$ where $1.62227<C_3\le2$.

Disclosure

“q ≥ 3? Moreover, can Cq be bounded by an absolute constant independent of q? Acknowledgements We thank Oleg Pikhurko for bringing the problem to our attention. We also thank Jun Gao for a helpful discussion. Declaration on the use of AI Generative AI tools were used to simplify some proofs and check arguments. All mathematical results and proofs were independently reviewed and verified by the authors, who take full responsibility for the content of this work.”

PDF page 5

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:13:17.153287Z

Structural counts