1
$\begingroup$

I'm recently interested in whether a sub-shift of finite type contains a doubly-periodic problem, when the set of configurations is of the sort $\mathcal{A}^{\mathbb{Z}^2}$. When $Q_2=\{0,1\}^2$, and our forbidden patches are in $\mathcal{A}^{Q_2}$, this problem translates naturally to a domino tiling problem. I was wondering whether people have already given informative immediate tests in this case for there to be a doubly periodic tiling in the sub-shift.

For example, it is clear that if the patch $P:Q_2\to \{a\}$ is permitted for any $a\in \mathcal{A}$ is not forbidden, then the tiling $\omega:\mathbb{Z}^2\to \{a\}$ is periodic and in the sub-shift. Likewise, when $\vert \mathcal{A}\vert \geq 2$ and we have at most $2$ forbidden patches, then there must also be a doubly periodic tiling in the sub-shift.

Are there any immediately checkable combintorial conditions for the existence of a doubly periodic tiling? I'm assuming that there are, but I just don't know how to find them.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

If I understand your question correctly, you are asking for a procedure to decide if a two-dimensional shift of finite type contains a (doubly) periodic word. This is known not to be decidable. This is a result of Berger.

See here for more info.

Improve this answer
$\endgroup$
14
  • $\begingroup$ I know that this is an undecidable problem. However, I am asking for specific classes of Wang tiles for which the problem is decidable. For example, given enough colors for the Wang tilings having a large amount of Wang tiles to work with, must imply a doubly periodic word. I'm more asking about what classes of Wang tiles are known to be decidable. $\endgroup$
    – Keen-ameteur
    Commented Oct 26, 2022 at 9:03
  • 1
    $\begingroup$ Your question title is "Definitive conditions". This is synonymous with "Necessary and Sufficient Conditions". I believe from your comment you are actually looking for sufficient conditions. I suggest you edit your posting (and title) accordingly. My rough thought is that the conditions for the existence of a periodic tiling will roughly turn out to be that you can write down a periodic tiling. There is one exception to this in a paper of Tom Ward where he shows that a "strongly irreducible" shift of finite type in 2D necessarily has a periodic tiling. $\endgroup$
    – Anthony Quas
    Commented Oct 27, 2022 at 6:48
  • 1
    $\begingroup$ The paper is "Automorphisms of Zd-subshifts of finite type" by Tom Ward from 1994 (first para of section 2). His condition is called "strong specification": for any two subsets $A$ and $B$ such that all elements of $A$ are at a distance at least $R$ from all elements of $B$; and given any two elements $x$,$y$ of the SFT, there exists a third point $z$ in the SFT such that $z$ agrees with $x$ on $A$ and with $y$ on $B$. I don't know of examples where it is easier to check strong specification than to check the existence of a periodic point. $\endgroup$
    – Anthony Quas
    Commented Oct 27, 2022 at 6:56
  • 1
    $\begingroup$ I guess strong specification is also undecidable. A sketch: given a Turing machine (TM) consider a tile set $T$ that simulates the computation of the TM from the empty tape, and $T$ has a tiling iff the TM does not halt. When non-empty, $T$ is not specified. Then augment $T$ into a subshift $X$ which is also not specified in the presence of an infinite computation, but a halting computation yields a rectangular tiling $R$ surrounded by a new buffer symbol $b$. Then all valid tilings are of the form where copies of $R$ are embedded in an infinite sea of $b$'s, and $X$ is strongly specified. $\endgroup$
    – Johan Kopra
    Commented Oct 27, 2022 at 17:04
  • 1
    $\begingroup$ hal.archives-ouvertes.fr/hal-03454594 if the number of $m \times n$ patterns is at most $mn$ then there is a doubly periodic tiling. $\endgroup$
    – Ville Salo
    Commented Oct 29, 2022 at 6:37
0
$\begingroup$

I believe I have found some nontrivial conditions from two papers.

First, if the number of colors used in the Wang tiles is strictly less than $4$, the Wang tiles must allow a periodic tiling. This relies on the paper, Non-emptiness problems of Wang tiles with three colors, from 2014.

Secondly, in the important paper by Jeandel and Rao, An aperiodic set of 11 Wang tiles, they show in section 3, that there is no aperiodic tiling of the plane using only $10$ Wang tiles.

I also think that, using $k$ colors in a collection of Wang tiles, there must be some threshold $t(k)<k^4$ such that if the collection of Wang tiles has more than $t(k)$ tiles, there must be a periodic tiling admitted.

Since I was pleased to find at least these two simple criteria, I thought to add them in an answer to this post.

I also saw a paper by Sebastian LABBÉ, A self-similar aperiodic set of 19 Wang tiles, invoking a more complicated criteria with 'markers'. Since I don't completely understand those arguments, I am not certain if they are easily checkable conditions like the two criteria above. If anyone at some point reading, has any more conditions, I would be thankful.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I don't think (and scrolling over it seems to confirm) Labbé's paper has any sufficient condition for periodic points. Technically "not being recognizable" is a necessary condition, but this observation is trivial once you know what recognizability is, and is not due to Labbé. $\endgroup$
    – Ville Salo
    Commented Jan 4, 2023 at 18:21
  • $\begingroup$ @VilleSalo From what I understood, Labbé's paper gives a somewhat algorithmic method to look for a criteria of "not being regonizable". I think Jeandel and Rao use the same sort of argument for the specific Wang tiles example they gave implicitly, while Labbé writes it much more explicitly. Though it might be in a follow up paper, arxiv.org/abs/1808.07768. $\endgroup$
    – Keen-ameteur
    Commented Jan 6, 2023 at 14:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .