Punctual presentation of abelian groups

Niniejsza praca bada efektywne prezentacje grup ze szczególnym uwzględnieniem prezentacji punktualnych. Ramy teoretyczne struktur punktualnych, opracowane w artykule “Algebraic structures computable without delay” autorstwa Kalimullina, Melnikova i Ng (Theoretical Computer Science, 2017), są wykorzystywane do analizy własności struktur obliczalnych bez opóźnienia i były intensywnie badane w ostatnich latach. Struktura o skończonym sygnaturze jest punktualna, jeśli jej dziedziną jest zbiór liczb naturalnych (lub jego początkowy segment), a wszystkie funkcje i relacje w sygnaturze są pierwotnie rekurencyjne.

Aby zapewnić lepszy kontekst dla głównych rezultatów, praca zaczyna się od opisu własności grup abelowych w dwóch ważnych, mniejszych podklasach struktur obliczalnych: strukturach automatycznych oraz strukturach działających w czasie wielomianowym (PTIME). Następnie przedstawione są zasadnicze wyniki dotyczące punktualnej prezentowalności dwóch głównych klas grup abelowych. Po pierwsze wykazano, że każda obliczalna grupa abelowa beztorsyjna dopuszcza punktualną prezentację. W przeciwieństwie do tego, praca pokazuje, że nie wszystkie obliczalne grupy abelowe torsyjne są punktualnie prezentowalne. Dowody zostały pierwotnie opublikowane w “Algebraic structures computable without delay”, lecz jedynie w sposób szkicowy. W niniejszej pracy przedstawiono je w pełnych detalach oraz skorygowano błąd w dowodzie drugiego z tych twierdzeń.

Razem wyniki te ilustrują zarówno siłę wyrazu, jak i wewnętrzne ograniczenia punktualnej prezentowalności.

This thesis investigates effective presentations of groups with a particular focus on punctual presentations. The framework of punctual structures, developed in paperpaper “Algebraic structures computable without delay” by Kalimullin, Melnikov and Ng (Theoretical Computer Science, 2017), is used to analyze properties of structures computable without delay and has been extensively studied in recent years. A structure over a finite signature is punctual if its domain is the set of natural numbers (or an initial segment thereof) and all functions and relations in its signature are primitive recursive.

To provide better context for the main results, the thesis begins by describing properties of abelian groups in two important smaller subclasses of computable structures: automatics and polynomial-time (PTIME) structures. Then the core results are presented that concern punctual presentability of two major classes of abelian groups. First, it is shown that every computable torsion-free abelian group admits a punctual presentation. In contrast, the thesis demonstrates that not all computable torsion abelian groups are punctually presentable. The proofs were originally published in “Algebraic structures computable without delay” but only in a sketchy way. Here the proofs are presented with all detail and a mistake in the proof of the latter theorem is corrected.

Together, these results exemplify both the expressive power and inherent limitations of punctual presentability.