Covering the ternary cube by binary subcubes

Abstract

For an integer $n\ge 0$, 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)\le 2(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\le 2$.