How hard is it to tell when a finite set tiles the integers?

Question

Given a nonempty set $B$ of integers between 1 and $n$, we wish to determine whether or not $\mathbb{Z}$ can be tiled with translates of $B$ (that is, covered by disjoint translates of $B$). I know an algorithm for answering this question whose running time can be bounded by a doubly-exponential function of $n$; is there a better algorithm? On the one hand, it seems plausible that some sort of greedy approach to fitting together translates of $B$ might be guaranteed to yield a tiling if one exists (and to terminate quickly if none exists), in which case the decision problem might be efficiently solvable. On the other hand, it seems plausible (and to me more likely) that the one-dimensional tiling problem is computationally complete for a seemingly much broader class of one-dimensional existence problems, much as is the case for two-dimensional tiling.

Answer 1

If I understand what you are asking, there is a directed graph on $2^{n-2}$ nodes with in and out degrees bounded by $1$. The set tiles the integers exactly if this graph has any directed cycles (one of which might be a loop).

There is an easy sufficient condition which is necessary if $|B|$ is of the form $p^i q^j$. The proof which establishes that won't work for $|B|=30$ but Ethan and I conjectured that it is always necessary.

Izabella Laba and associates may have some advances.

LATER Here is the basic idea. I'll have the prototile $B$ be a set of integers with $\min(B)=0$ and $\max(B)=n-1.$ Define a state to be any subset $S$ of $\{{1,\cdots, n-2 \}}.$ A tiling of $\mathbb{Z}$ by translates of $B$ is a disjoint union $$\mathbb{Z}=\bigcup_{t \in T}\left( B+t\right)$$ Where $T$ is the set of translations. A state describes the equivalence class of (potential) partial tilings $(- \infty,k) \bigcup (S+k)$ which might be $$\bigcup_{t \in T \cap (-\infty,m]}\left( B+t\right)$$ for some $m$ (the initial position of the most recently placed translate of $B.$) The rest of the tiling is uniquely determined any one partial tiling, the next translate of $B$ must be $B+q$ where $q$ is the first integer not in the partial tiling. We can also determine the evolution of the (partial) tiling. The last tile placed must have been $B+v$ where $v+n-1$ is the largest member of the partial tiling.

THE GRAPH: The nodes are the states. If $S$ is a state disjoint from $B$ then add a directed arc from $S$ to $S'$ where $S'$ is obtained from $S^*=S \cup B$ by taking the first positive integer $j \notin S^*$ and setting $S'=\left( S^*-j\right) \cap [0,\infty)$. If $S$ is not disjoint from $B$ then no arc leaves $S.$

A directed cycle in this digraph gives a tiling and vice-versa.

With obvious adjustments one could have a collection of several different prototiles and essentially the same analysis. In that extended situation what I will call the algebraic approach won't work.

The algebraic approach hardly pays attention to $n$ being more interested in $|B|.$ For details I will modestly recommend the paper Gerry links. It uses cyclotomic polynomials to give a strong necessary condition (T1) for a prototile to tile $\mathbb{Z}$. The addition of a second condition (T2) is sufficient. There are no known prototiles which tile $\mathbb{Z}$ and fail (T2.)

EVEN LATER The shortest cycle can be as large as the width of $B.$ That happens for $B=\{{0,2^j\}}.$ My conjectures imply that that is as large as it can get and that that is the only way it happens.

Given a tiling of the integers by $B$, there is a minimal $N$ so that the tiling is $B \oplus \left(A \oplus N\mathbb{Z}\right)=\mathbb{Z}.$ I call $N$ the period. In terms of the graph I described, the cycle length would be $\frac{N}{|B|}$ (which is an integer.)

Just to spell out the conjecture (in part), let $B(x)=\sum_Bx^b$ and $S_B$ be the set of prime powers such that the cyclotomic polynomial $\Phi_{p^j}(x)$ divides $B(x).$

FACTS: if $B$ tiles the integers then it must be the case that $$|B|=\prod_{p^j \in S_B}p. \tag{T1}$$ The period of any tiling will be a multiple of $\operatorname{lcm}(S_B).$ Consider the further condition:

(T2): $\Phi_k$ divides $B(x)$ for every $k=\prod p_i^{e_i}$ with the $p_i$ distinct primes and each $p_i^{e_i} \in S_B.$

(T1) and (T2) together are sufficient for $B$ to tile and imply that the minimal period of a tiling is $\operatorname{lcm}(S_B).$

CONJECTURE: (T2) is necessary for a tiling so T1 & T2 is necessary and sufficient

If the conjecture is true then it is quite easy indeed to decide if $B$ tiles. But if the conjecture is wrong then maybe longer periods(cycles) are possible. However (T1) alone is still a quick necessary condition likely to quickly reject a (sparse) random set.