Cobham's theorem for the Gaussian integers

Technische Samenvatting: Cobhams Stelling voor de Gaussische Hele Getallen

Probleemstelling
Cobhams stelling is een fundamenteel resultaat in de automatentheorie en getaltheorie, dat stelt dat een reeks natuurlijke getallen zowel $k$-automatisch als $\ell$-automatisch is (waarbij $k$ en $\ell$ multiplicatief onafhankelijke gehele getallen zijn) dan en slechts dan als de reeks uiteindelijk periodiek is. Hoewel deze stelling is gegeneraliseerd naar diverse logische en dynamische contexten, bleef er een significante kloof bestaan bij de uitbreiding ervan van de gehele getallen $\mathbb{Z}$ naar de Gaussische gehele getallen $\mathbb{Z}[i]$.

Vorig werk door Hansel en Safer behandelde numeratiesystemen met basis $\alpha = -m + i$ (waarbij $m \ge 1$) en niet-negatieve gehele getal-digitsets. Zij toonden aan dat als een deelverzameling $S \subset \mathbb{Z}[i]$ herkenbaar is door twee dergelijke bases, de deelverzameling syndetisch is. Zij vermoedden dat een dergelijke deelverzameling uiteindelijk periodiek moet zijn (dat wil: invariant onder translatie door twee $\mathbb{Z}$-lineair onafhankelijke vectoren buiten een eindige verzameling). Echter, hun bewijs steunde op de Vier Exponenten Conjectuur, een diepe en onbewezen hypothese in de analytische getaltheorie, waardoor de conjectuur onbeslist bleef.

Methodologie
De auteurs leveren een bewijs van Cobhams stelling voor de Gaussische gehele getallen dat niet steunt op de Vier Exponenten Conjectuur. Hun benadering generaliseert de stelling naar de grootste mogelijke familie van Gaussische numeraties (elke eindige genererende digitset) en verwijdert de afhankelijkheid van diepe analytische getaltheorie.

De kernmethodologie omvat:

1. Dirichlet-benadering in $\mathbb{Z}[i]$: In plaats van te vertrouwen op de dichtheid van de multiplicatieve groep $\langle \alpha, \beta \rangle$ in $\mathbb{C}$ (wat de Vier Exponenten Conjectuur vereist), maken de auteurs gebruik van een zwakker resultaat: dat $1$ geen geïsoleerd punt is in de multiplicatieve groep gegenereerd door twee multiplicatief onafhankelijke Gaussische gehele getallen. Dit wordt vastgesteld via Lemma 3, dat bewijst dat als $1$ geïsoleerd zou zijn, de groep discreet zou zijn, hetgeen multiplicatieve afhankelijkheid impliceert.
2. Pumping Lemma en Return Numbers: De auteurs analyseren de structuur van eindige toestandsautomaten (DFAOs) die opereren op Gaussische gehele getal-expansies. Zij definiëren "return numbers" naar specifieke toestanden in de automaat. Door van der Waerden's stelling toe te passen op de toestanden van de automaten, identificeren zij rekenkundige progressies van indices die corresponderen met return numbers.
3. Collineariteitsanalyse: Een cruciale stap is Lemma 14, die aantoont dat als een reeks return numbers op een lijn ligt (collineair is), de basis een wortel van een geheel getal moet zijn. Bijgevolg, als de basis geen wortel van een geheel getal is, moeten de return numbers niet-collineair zijn. Dit maakt de constructie van twee $\mathbb{Z}$-lineair onafhankelijke perioden mogelijk.
4. Periode-propagatie: Met behulp van een versie van de stelling van Fine en Wilf, aangepast voor de Gaussische gehele getallen (Lemma's 18 en 19), tonen de auteurs aan dat lokale periodiciteit (stap-periodiciteit) op overlappende bollen kan worden gepropageerd naar globale periodiciteit. Zij construeren een dekking van $\mathbb{Z}[i]$ door bollen waar de configuratie specifieke perioden vertoont die afgeleid zijn van de niet-collineaire return numbers.

Belangrijkste Bijdragen en Resultaten
Het primaire resultaat is Stelling 1, die stelt:

Laat $\alpha$ en $\beta$ twee multiplicatief onafhankelijke Gaussische gehele getallen zijn met $|\alpha|, |\beta| > 1$. Indien één van $\alpha$ of $\beta$ geen wortel is van een geheel getal, dan is een configuratie $(a_z)_{z \in \mathbb{Z}[i]}$ $\alpha$- en $\beta$-automatisch dan en slechts dan als deze uiteindelijk periodiek is.

Belangrijke technische bevindingen zijn onder meer:

• Resolutie van de Hansel en Safer Conjectuur: Het artikel bewijst de conjectuur dat verzamelingen herkenbaar door bases van de vorm $-m+i$ uiteindelijk periodiek zijn. Aangezien $-m+i$ voor $m > 1$ nooit een wortel van een geheel getal is (volgens de Stelling van Niven), wordt aan de voorwaarde van Stelling 1 voldaan.
• Noodzakelijkheid van de Voorwaarde: De auteurs tonen aan dat de voorwaarde "één basis is geen wortel van een geheel getal" scherp is. Indien beide bases wortels van gehele getallen zijn, kunnen niet-uiteindelijk periodieke configuraties voorkomen (bijv. de karakteristieke functie van $\mathbb{N}$ is $\alpha$-automatisch als $\alpha$ een wortel van een geheel getal is).
• Generalisatie van Numeratiesystemen: Het bewijs geldt voor elke eindige digitset $D$ die een numeratiesysteem genereert, en niet alleen voor de "natuurlijke" niet-negatieve gehele getal-digitsets die door Hansel en Safer werden overwogen.
• Bijgerecht over Conjunctie: Het artikel stelt vast dat indien een verzameling $U \subset \mathbb{Z}[i]$ $\beta$-automatisch is en gelijk is aan zijn complexe conjugaat ($U = \bar{U}$), en niet uiteindelijk periodiek is, dan $\beta$ een wortel van een geheel getal moet zijn.

Betekenis
Het artikel beweert de uitbreiding van de Cobham-stelling naar de Gaussische gehele getallen te hebben beslecht zonder te steunen op onbewezen analytische conjecturen. Door aan te tonen dat het resultaat gebaseerd is op elementaire eigenschappen van automaten en de geometrie van de Gaussische gehele getallen (specifiek de niet-isolatie van 1 in de multiplicatieve groep), "opent het de weg naar Cobham voor algemene getalringen".

Het werk generaliseert de Cobham-Semenov stelling naar Gaussische numeraties. Het verbindt ook met het werk van Cabezas en Petite over constant shape substituties, wat impliceert dat niet-triviale configuraties gegenereerd door Gaussische bases die geen wortels van gehele getallen zijn, niet gereproduceerd kunnen worden door standaard $(k, k)$-automatische configuraties. De auteurs merken op dat hoewel dit een eerste stap is, de uitbreiding naar andere ringen van gehele getallen (zoals $\mathbb{Z}[\zeta]$ of kwadratische gehele getalringen) een natuurlijke richting is voor toekomstig onderzoek.