41
$\begingroup$

Let $D_1,\dots,D_n \subset \mathbb{Z}^2$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name).

Does there always exist finite $B \subset \mathbb{Z}^2$ that can be partitioned into disjoint translates of $D_i$ for all $i \in [n]$?

For instance, if $D_1= {\tiny \square\square} , D_2 ={\tiny \square}\hspace{-6.5pt}{\ ^{^{ _\square}}},$ one can simply take $B=\boxplus.$ However, if we add just one domino $D_3 = {\tiny \square}\hspace{-1.4mm}{\ ^{^{ _\square}}},$ or two dominoes $D_3 = {\tiny \square}\hspace{-1.4mm}{\ ^{^{ _\square}}}, D_4 = \hspace{-1.4mm}{\ ^{^{ _\square}}}\hspace{-1mm}{\tiny \square},$ then the suitable shapes become much more complex: \begin{align} & \large \square \square \phantom{\square \square \square \square \square \square \square} \large \large\square \square\\[-10pt] \large \square & \large \square \square \square \phantom{\square \square \square \square \square} \square \square \square \square \\[-10pt] \large \square & \large \square \square \square \phantom{\square \square \square \square \square} \square \square \square \square \\[-10pt] \large\square \square & \large \square \square \phantom{\square \square \square \square \square} \square \square \square \square \square \square \\[-10pt] \large\square \square & \large \phantom{\square \square \square \square \square \square \square} \square \square \square \square \square \square \\[-10pt] &\large \phantom{\square \square \square \square \square \square \square \square}\square \square \square \square \\[-10pt] &\large \phantom{\square \square \square \square \square \square \square \square} \square \square \square \square \\[-10pt] &\large \phantom{\square \square \square \square \square \square \square \square \square} \square \square \\[-10pt] \end{align}

I expect the answer to be negative in general, though I do not see a way to prove non-existence of the desired $B$ for some specific sets of dominoes. Note that if we don't require $B$ to be finite, the question becomes trivial: one can always take $B = \mathbb{Z}^2$.

Assuming the negative answer, one can further ask how to decide, for a given set of dominoes, if such $B$ exists. Some related polyomino tiling problems are known to be NP-complete, and some are even undecidable. So, this question could also appear to be not so 'elementary' as it might look.

Finally, I am also interested in the natural generalization to $\mathbb{Z}^m$. Observe that the case $m=1$ is trivial. Indeed, if $D_i=\{0,d_i\}$ for all $i \in [n]$, then one can take $B=[2\cdot\text{lcm}(d_1,\dots,d_n)]$, where $\text{lcm}$ stands for the least common multiple.

Perhaps, the questions of this flavor have been already studied, but I was unable to find something related. Though this is not my field of research, so I probably missed something. Apologize in advance if this topic is well known.

$\endgroup$
29
  • 2
    $\begingroup$ Here is a formulation in terms of polynomials: associate a 'rising' domino consisting of (0,0) and (m,n) with $p_{m,n}:=(1+x^my^n)$ and a 'falling' domino consisting of (0,0) and (r,-s) with $q_{r,s}=(x^r+y^s)$. Then for a given finite set of non-negative pairs $\{(m_i,n_i)\}\cup\{(r_j,s_j)\}$, the question is about the existence of a polynomial in $\mathbb Z[x,y]$ with coefficients only $0$ and $1$ which is divisible by all the $p_{m_i,n_i}$ and by all the $q_{r_j,s_j}$. This formalizes the problem, but I have no idea whether it helps... $\endgroup$
    – Wolfgang
    Jun 23 at 16:42
  • 2
    $\begingroup$ If there's a positive answer, then I think there's also a positive answer when the dominoes are allowed to be arithmetic progressions of arbitrary length. Indeed, suppose we can tile with the dominoes $\{0,x\}$, $\{0,2x\}$, ... , $\{0,rx\}$, where $x\in\mathbb Z^2$. Then let $b\in B$ be such that $b-tx\notin B$ for all positive $t$. It follows that $b,b+x,\dots,b+(2r-1)x\in B$ and that if we use the domino $\{0,rx\}$ then we have to tile that portion in the obvious way. Then by induction the rest also partitions into copies of $\{0,x,\dots,(2r-1)x\}$. $\endgroup$
    – gowers
    Jul 3 at 19:58
  • 2
    $\begingroup$ @gowers : I think the induction here is not well founded. For example "xxxxxxxxoxxxxxxxx" can be tiled by "xx". "xox" and "xoox", but is not made of copies of "xxxxxx". (Here your $r=3$). However the idea works for powers of 2, in that tiling, say, by "xx", "xox" and "xooox" is equivalent to tiling by "xxxxxxxx", etc. Perhaps you were assuming that there would be no gaps? $\endgroup$ Jul 4 at 11:37
  • 2
    $\begingroup$ With a SAT solver one can get some nice pictures. Here's a figure tilable by $D_1, D_2, D_3, D_4$, and also by $D_1$ with a gap: paste. And here's one tilable by $D_1, D_2, D_4$, as well as gapped $D_1$ and $D_2$: paste. Both are smallest, in the sense that they have minimal bounding boxes. $\endgroup$ Jul 7 at 11:25
  • 2
    $\begingroup$ @YaakovBaruch With my current setup I wouldn't be able to tell if there's no solution, or it's just larger than, say, $200 \times 200$. Also holes are necessary in some similar settings. $\endgroup$ Jul 7 at 23:14

1 Answer 1

1
$\begingroup$

Not an answer to the original question! Proof that the ‘arithmetic progressions’ version of the problem is equivalent to the originally posted ‘dominoes’ version based on the discussion in the comments above.

More formally, for ${\mathbf x} \in {\mathbb Z}^2\!\setminus\!(0,0)$ and $k \ge 2$, put $D_{k}({\mathbf x}) := \{0, {\mathbf x}, 2{\mathbf x}, \dots, (k-1){\mathbf x}\}$. One might ask the following.

Question 1 Is it true that for all $n \in {\mathbb N}$, ${\mathbf x}_1,\dots,{\mathbf x}_n \in {\mathbb Z}^2\!\setminus\!(0,0)$, and $k_1,\dots,k_n \ge 2$, there exists a finite $B \subset {\mathbb Z}^2$ such that $D_{k_j}({\mathbf x}_j)$ tiles $B$ for all $j \in [n]$?

Substitution $k_1=\dots=k_n=2$ trivially shows that this question generalize the original ‘dominoes’ one. However, this answer proves that they are in fact equivalent. This circumstance either provides a pretty generalization of the original question (if the answer to both is positive), or perhaps simplifies the search for a counterexample (otherwise).

We start the proof with some notation. Denote by $f(s)$ the least common multiple of all odd positive integers not larger than $s$. In particular, $f(1) = 1$ and $f(9) = 3^2\cdot5\cdot7$. Given $i \in {\mathbb N}$, denote the domino $\{0,i\}$ by $D(i)$. The main tool to prove the desired equivalence is the following technical statement.

Proposition 1 There exists an increasing family $T(1) \subseteq T(3) \subseteq T(5) \subseteq \dots$ of finite subsets of ${\mathbb N}$ with the following property. For all odd $s \in {\mathbb N}$, there exists $n_0(s)$ such that for all $n \ge n_0(s)$, the following two statements are equivalent for all finite $A \subset {\mathbb Z}$:
$\hspace{5mm}$I) $\hspace{0.2mm}$ $D(i)$ tiles $A$ for all $i \in T(s) \cup \{1,2,4,\dots,2^{n-1}\}$,
$\hspace{5mm}$II) $A$ consists of blocks of length $f(s)\cdot2^n$.

Proof. We begin with three simple observations.

Observation 1. For all $i, N \in {\mathbb N}$ such that $2i$ divides $N$, $D(i)$ tiles all finite $A \subset {\mathbb N}$ that consist of blocks of length $N$.

Observation 2. For all $i,N \in {\mathbb N}$ such that $2i$ divides $N$, and all finite $A \subset {\mathbb N}$ such that $[N]\subseteq A$, $D(i)$ tiles $A$ if and only if $D(i)$ tiles $A \!\setminus\! [N]$.

Observation 3. For all $i, N \in {\mathbb N}$ such that $i \le (N \! \mod 2i) < 2i$, and all finite $A \subset {\mathbb N}$ such that $D(i)$ tiles $A$, if $[N] \subseteq A$, then $N+1 \in A$.

These observations have the following corollary.

Lemma 1. For all $n \in {\mathbb N}$ and all finite $A \subset {\mathbb Z}$, $D(i)$ tiles $A$ for all $i \in \{1,2,4,\dots,2^{n-1}\}$ if and only if $A$ consists of blocks of length $2^n$.

Proof. Note that the ‘if’ part of the statement is trivial in the light of Observation 1. The proof in the other direction is by induction on $n$. If $n=1$, then there is nothing to do. So, assume that $n>1$ and $D(i)$ tiles $A$ for all $i \in \{1,2,4,\dots,2^{n-1}\}$. By the induction hypothesis, $A$ consists of blocks of length $2^{n-1}$. Without loss of generality, assume that $A \subset {\mathbb N}$ and $[2^{n-1}]\subset A$. Taking into account the fact that $D(2^{n-1})$ tiles $A$, and since $(2^{n-1} \! \mod 2\cdot2^{n-1}) = 2^{n-1}$, Observation 3 implies that $2^{n-1}+1 \in A$. Therefore, the ‘doubled’ segment $[2^n]$ belongs to $A$ as well (because $A$ consists of blocks of length $2^{n-1}$). Finally, Observation 2 implies that $D(i)$ tiles $A \!\setminus\! [2^n]$ for all $i \in \{1,2,4,\dots,2^{n-1}\}$ as well. This is sufficient to conclude that $A$ consists of blocks of length $2^{n}$. Indeed, one can replace $A$ with $A \!\setminus\! [2^n]$ and repeat the same argument to find another block of length $2^{n}$ in the beginning until the whole set is examined. $\square$

We prove Proposition 1 by induction on $s$. Note that the base case $s=1$ holds by Lemma 1 with $T(1)=\varnothing$ and $n_0(1)=1$. If $f(s)=f(s-2)$, then the statement of the induction step $(s-2 \to s)$ holds by the induction hypothesis with $T(s) = T(s-2)$ and $n_0(s)=n_0(s-2)$. So, let us assume without loss of generality that $f(s)>f(s-2)$, i.e., that $s=p^{\alpha}$, where $p$ is an odd prime, $\alpha \in {\mathbb N}$, and $f(s)=p\cdot f(s-2)$.

Note that the sequence $(f(s-2)\cdot2^n \! \mod 2s)_{n=1}^{\infty}$ is periodic. Besides, $p^{\alpha-1}$ is the largest power of $p$ that divides each if its elements, and thus none of them equals $0$. Moreover, each next element is ‘twice the previous one’. Therefore, there exists $n_0(s) \ge \max\big(n_0(s-2), \log_2s\big)$ such that $s \le \big(f(s-2)\cdot2^{n_0(s)} \! \mod 2s\big) < 2s$, i.e., that \begin{equation} f(s-2)\cdot2^{n_0(s)} = q_0\cdot(2s)+r_0, \hspace{10mm} (1) \end{equation} where $q_0 \in {\mathbb N}, s \le r_0 < 2s$.

We show that the statement of Proposition 1 holds with $T(s) = T(s-2)\cup\{s,2s,\dots,(p-1)s\}$ and with $n_0(s)$ constructed above. For all $n \ge n_0(s)$, the implication $(II) \to (I)$ is almost clear in the light of Observation 1 since $2i$ divides $f(s)\cdot2^n$ for all $i \in T(s) \cup \{1,2,4,\dots,2^{n-1}\}$ by construction. Indeed, the only non-trivial verification here is when $i \in \{s,2s,\dots,(p-1)s\}$. In this case, we represent $i$ as $(2j+1)s\cdot2^m$. Note that $2j+1 < p$ and thus $(2j+1)s$ divides $f(s)$, while $m < \log_2p \le \log_2s \le n_0(s) \le n$ and thus $2^{m+1}$ divides $2^n$.

To prove in the other direction, we fist fix an arbitrary finite $A \subset {\mathbb Z}$ that satisfies condition $(I)$ with $n = n_0(s)$. By the induction hypothesis, $A$ consists of blocks of length $f(s-2)\cdot2^{n_0(s)}$. Without loss of generality, assume that $A \subset {\mathbb N}$ and $\big[f(s-2)\cdot2^{n_0(s)}\big]\subseteq A$.

Recall that $D(s)$ tiles $A$. Thus, equality (1) along with Observation 3 applied with $s$ playing the role of $i$ and $f(s-2)\cdot2^{n_0(s)}$ playing the role of $N$ implies that $f(s-2)\cdot2^{n_0(s)}+1 \in A$. Hence, $A$ begins with at least two consecutive blocks of length $f(s-2)\cdot2^{n_0(s)}$, i.e., $\big[2\cdot f(s-2)\cdot2^{n_0(s)}\big]\subseteq A$.

We proceed in the same vein. Namely, given $2\le j \le p-1$, after the previous step we know that $\big[j\cdot f(s-2)\cdot2^{n_0(s)}\big]\subseteq A$. Recall that $D(js)$ tiles $A$, and multiply both sides of (1) by $j$. Note that this allows to apply Observation 3 with $js$ playing the role of $i$ and $j\cdot f(s-2)\cdot2^{n_0(s)}$ playing the role of $N$ to conclude that $j\cdot f(s-2)\cdot2^{n_0(s)}+1 \in A$. Hence, $A$ begins with at least $j+1$ consecutive blocks of length $f(s-2)\cdot2^{n_0(s)}$, i.e., $\big[(j+1)\cdot f(s-2)\cdot2^{n_0(s)}\big]\subseteq A$.

After the $(p-1)^{th}$ step, we obtain that $\big[p\cdot f(s-2)\cdot2^{n_0(s)}\big] = \big[f(s)\cdot2^{n_0(s)}\big] \subseteq A$. Therefore, Observation 2 implies that $A \!\setminus\! \big[f(s)\cdot2^{n_0(s)}\big]$ also satisfies condition $(I)$ with $n = n_0(s)$. (Indeed, we have already checked all the required divisibilities during the proof of the implication $(II) \to (I)$.) As in the proof if Lemma 1, this is sufficient to conclude that $A$ has the desired block structure. Indeed, one can replace $A$ with $A \!\setminus\! \big[f(s)\cdot2^{n_0(s)}\big]$ and repeat all the above argumentation to find another block of length $f(s)\cdot2^{n_0(s)}$ in the beginning until the whole set is examined. So, $A$ consists of blocks of length $f(s)\cdot2^{n_0(s)}$ which proves the implication $(I) \to (II)$ if $n=n_0(s)$.

To prove this implication in the general case, fix an arbitrary $n \ge n_0(s)$ and a finite $A\subset {\mathbb Z}$ that satisfies condition $(I)$. Note that on the one hand, $D(i)$ tiles $A$ for all $i \in T(s) \cup \big\{1,2,4,\dots,2^{n_0(s)-1}\big\}$, and thus $A$ consists of blocks of length $f(s)\cdot2^{n_0(s)}$ as shown in the previous paragraph. On the other hand, $D(i)$ tiles $A$ for all $i \in \{1,2,4,\dots,2^{n-1}\}$, and thus Lemma 1 implies that $A$ consists of blocks of length $2^n$. Therefore, $A$ in fact consists of blocks of length equal to the least common multiple of these two numbers, namely $f(s)\cdot2^{n}$ as desired. This completes the proof of the implication $(I) \to (II)$ in the general case and finishes the proof of Proposition 1 by induction on $s$. $\square$

How does Proposition 1 help to prove the desired equivalence between the ‘arithmetic progressions’ and the the ‘dominoes’ versions of the original question?

Well, first we note that for each $k$, there exist sufficiently large odd $s$ and $n\ge n_0(s)$ such that $k$ divides $f(s)\cdot2^n$. Therefore, by setting $T'(k) := T(s)\cup \{1,2,4,\dots,2^{n-1}\}$, we obtain the following corollary.

Corollary 1 For all $k \in {\mathbb N}$, there exists a finite set $T'(k)\subset {\mathbb N}$ such that the following holds. For all finite $A \subset {\mathbb Z}$, if $D(i)$ tiles $A$ for all $i \in T'(k)$, then $A$ consists of blocks of length $k$.

Second, we show that one can easily ‘increase the dimension’ of this statement.

Corollary 2 In the above notation, for all $k \in {\mathbb N}$, ${\mathbf x} \in {\mathbb Z}^2\!\setminus\!(0,0)$, and a finite $B \subset {\mathbb Z}^2$, if $D_2(i{\mathbf x})$ tiles $B$ for all $i \in T'(k)$, then $D_k({\mathbf x})$ tiles $B$.

Proof. The equivalence relation ‘$\mathbf{y}_1 \sim \mathbf{y}_2$ if and only if $\mathbf{y}_1 - \mathbf{y}_2 = z{\mathbf x}$ for some $z \in {\mathbb Z}$’ partitions $B$ into finitely many equivalence classes $B_1\sqcup\dots \sqcup B_m$, each of which has the form $B_j = \{\mathbf{y}_j+z{\mathbf x}: z \in A_j\}$ for some $\mathbf{y}_j \in {\mathbb Z}^2$ and some finite $A_j \subset {\mathbb Z}$. Note that $D_k({\mathbf x})$ and each domino of the form $D_2(i{\mathbf x})$ tiles $B$ if and only if it tiles $B_j$ for all $j \in [m]$. Hence, it is sufficient to deal with the equivalence classes separately.

So, we can assume without loss of generality that $B= \{\mathbf{y}+z{\mathbf x}: z \in A\}$, where $\mathbf{y} \in {\mathbb Z}^2$ and $A \subset {\mathbb Z}$ is finite. In this case, the bijection $\pi : B \to A$ defined by $\pi(\mathbf{y}+z{\mathbf x}) = z$ deduce Corollary 2 directly from Corollary 1. $\square$

Now it clear how to reduce Question 1 to the original ‘dominoes’ question. It is sufficient to replace each $D_{k_j}({\mathbf x}_j)$ with the set of dominoes $\big\{D_2(i{\mathbf x}_j): i \in T'(k_j)\big\}$ for all $j \in [n]$ and apply Corollary 2.

Remark 1 It is clear that the same argumentation works not only on the plane but in ${\mathbb Z}^m$ for all $m \in {\mathbb N}$ as well.

Remark 2 Note that the set $T(s)$ has quite a comprehensible recursive structure. For instance, one can easily see that \begin{equation*} |T(s)| = \sum_{p^\alpha \le s} (p-1) = \frac{s^2}{2\ln s} + O\Big(\frac{s^2}{\ln^2s}\Big) \end{equation*} as $s \to \infty$, where the sum is taken over all powers of odd primes. At the same time, the definition of $n_0(s)$ is rather implicit. However, it not hard do derive from the construction that \begin{equation*} n_0(s) \le \sum_{p^\alpha \le s} \log_2p = \log_2 f(s) \end{equation*} for all odd $s$. To evaluate this sum for large values of $s$, observe that \begin{equation*} \sum_{p^\alpha \le s} \log_2p = \sum_{t \le s} \frac{\Lambda(t)}{\ln2} -\lfloor\log_2s\rfloor = \frac{\psi(s)}{\ln2} -\lfloor\log_2s\rfloor = \frac{s}{\ln2} + O\left(\frac{s}{\ln s}\right), \end{equation*} where $\Lambda(x)$ and $\psi(x)$ are the von Mangoldt and the second Chebyshev functions respectively.

$\endgroup$
1
  • $\begingroup$ It took me a couple of days but I wrote the whole thing down! But perhaps I overcomplicated it, and someone could prove this equivalence two or three times shorter... $\endgroup$ Jul 13 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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