14
$\begingroup$

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!

$\endgroup$

3 Answers 3

9
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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?).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.