Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $n$, a divisor $k$ of $n$, and a subset $S \subset \mathbb{Z}_n$ of size k. The problem is to decide whether $\mathbb{Z}_n$ can be covered with $n/k$ cyclic translations of $S$, i.e. sets of the form $S+a_i$ for various $a_i \in \mathbb{Z}_n$. This is simply a special case of the NP-complete EXACT COVER problem---namely, where the available sets are all cyclic shifts of each other, and where all cyclic shifts are available. My suspicion is that the special case is already NP-complete, while Ernest suspects that an $n^{O(1)}$ time algorithm exists. I searched Google (and Garey&Johnson) and couldn't find leads -- would appreciate any thoughts or references!
3 Answers
Here are a few references; the right keywords seem to be "tiling by translation" or a "factorization of a group":
Mihail N. Kolountzakis and Máté Matolcsi, Algorithms for translational tiling, Journal of Mathematics and Music, 3:2 (2009), 85-97, https://doi.org/10.1080/17459730903040899
Mihail N. Kolountzakis and Mate Matolcsi, Tilings by translation (2010), https://arxiv.org/abs/1009.3799
See also the following MO question about a more general problem about covering density (2013): Is this a known combinatorial problem?
A couple of more simple observations about this plus a conjecture. First, it's symmetric in $S$ and the set of shifts; you can rephrase it, "Given $n$ and $S$, find $A \subset \mathbb{Z}_{n}$ such that $|A|=n/|S|$ and $\{ s+a \: | \: s \in S, a \in A \} = \mathbb{Z}_{n}$." Second, for concreteness, to illustrate the kinds of things that can happen, with $S=\{ 0, 6,7,8, 13, 14\}$, $n=24$, a solution is $A = \{0,3,12,15\}$. Third, there are some invariants: if $\langle S,A \rangle$ is a solution, then so is $\langle d \cdot S+b, d\cdot A+c \rangle$ for constants $b,c,d$.
There is also a more complex invariant: Suppose that all the elements of $A$ are divisible by $b$. It is easily shown that $|S|$ is divisible by $b$. Let $j$ be a value in $0..b-1$ and let $Q_{j}=\{ s \in S \: | \: s \mod b = j \}$. Then you can replace $Q_{j}$ by $Q_{j}+cb$ in $S$. In the above example $b=3$. For $j=1$ we have $Q_{1}=\{7,13\}$. So we can replace $Q$ by $Q+3$ in $S$, giving us the pair $S=\{ 0,6,8,10,14,16\}, A=\{ 0,3,12,15 \}$.
I conjecture that the following may be true: Let $S_{i} = \{ s \in S \: | \: s \mod |S| = i \}$. If there is a solution, then all the non-empty $S_{i}$ have the same size. E.g. in the above example, $|S|=6$; $S_{0}=\{ 0,6\}; S_{1}=\{7,13\}; S_{2}=\{8,14\}$. If this is true, then I think I have a polynomial-time algorithm.
E.D., I think the conjecture is not true. If one tries it on the smallest non-periodic tiling (see below) it fails. The example is from N.G. de Bruijn, On the factorization of cyclic groups, Indag. Math. 15, 4, 1953.
The following Python program
# A + B is a tiling of Z mod 72
A = [0, 8, 16, 18, 26, 34]
B = [18, 54, 24, 60, 48, 12, 17, 41, 65, 45, 69, 21]
m = len(A)*len(B)
# Cheking tiling
S = m*[0]
for x in A:
for y in B:
S[(x+y) % m] += 1
if S == m*[1]: print("Yes, they tile")
L = [x % len(B) for x in B] # The elements of B mod len(B)
H = len(L)*[0] # Compute the histogram of L
for x in L: H[x] += 1
print(f"Frequencies of B mod {len(B)}: {H}")
prints
Yes, they tile
Frequencies of B mod 12: [4, 0, 0, 0, 0, 3, 2, 0, 0, 3, 0, 0]
I also believe the problem is polynomial. I do not even know if it is in co-NP (are there certificates for non-tiling?).
