An Algebraic Approach to Nivat's Conjecture

Abstract

This thesis introduces a new, algebraic method to study multidimensional configurations, also sometimes called words, which have low pattern complexity. This is the setting of several open problems, most notably Nivat’s conjecture, which is a generalization of Morse-Hedlund theorem to two dimensions, and the periodic tiling problem by Lagarias and Wang.

We represent configurations as formal power series over d variables where d is the dimension. This allows us to study the ideal of polynomial annihilators of the series. In the two-dimensional case we give a detailed description of the ideal, which can be applied to obtain partial results on the aforementioned combinatorial problems.

In particular, we show that configurations of low complexity can be decomposed into sums of periodic configurations. In the two-dimensional case, one such decomposition can be described in terms of the annihilator ideal. We apply this knowledge to obtain the main result of this thesis – an asymptotic version of Nivat’s conjecture. We also prove Nivat’s conjecture for configurations which are sums of two periodic ones, and as a corollary reprove the main result of Cyr and Kra from [CK15].

Algebrallinen lähestymistapa Nivat’n konjektuuriin

Tässä väitöskirjassa esitetään uusi, algebrallinen lähestymistapa moniulotteisiin,matalan kompleksisuuden konfiguraatioihin. Näistä konfiguraatioista, joita moniulotteisiksi sanoiksikin kutsutaan, on esitetty useita avoimia ongelmia. Tärkeimpinä näistä ovat Nivat’n konjektuuri, joka on Morsen-Hedlundin lauseen kaksiulotteinen yleistys, sekä Lagariaksen ja Wangin jaksollinen tiilitysongelma.

Väitöskirjan lähestymistavassa d-ulotteiset konfiguraatiot esitetään d:n muuttujan formaaleina potenssisarjoina. Tämä mahdollistaa konfiguraation polynomiannihilaattoreiden ihanteen tutkimisen. Väitöskirjassa selvitetään kaksiulotteisessa tapauksessa ihanteen rakenne tarkasti. Tätä hyödyntämällä saadaan uusia, osittaisia tuloksia koskien edellä mainittuja kombinatorisia ongelmia.

Tarkemmin sanottuna väitöskirjassa todistetaan, että matalan kompleksisuuden konfiguraatiot voidaan hajottaa jaksollisten konfiguraatioiden summaksi. Kaksiulotteisessa tapauksessa eräs tällainen hajotelma saadaan annihilaattori-ihanteesta. Tämän avulla todistetaan asymptoottinen versio Nivat’n konjektuurista. Lisäksi osoitetaan Nivat’n konjektuuri oikeaksi konfiguraatioille, jotka ovat kahden jaksollisen konfiguraation summia, ja tämän seurauksena saadaan uusi todistus Cyrin ja Kran artikkelin [CK15] päätulokselle.