Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T08:14:54.596Z Has data issue: false hasContentIssue false
  • English
  • Français

The additive group of the rationals does not have an automatic presentation

Published online by Cambridge University Press:  12 March 2014

Todor Tsankov
Todor Tsankov*
Affiliation:
Analyse Fonctionnelle, Boîte 186, Université Paris6, 4 Place Jussieu, 75252 Paris Cedex 05, France,
*
Equipe de Logique, UFR de Mathématiques, Université Paris Diderot, 75205 Paris, CEDEX 13, France, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that the additive group of the rationals does not have an automatic presentation. The proof also applies to certain other abelian groups, for example, torsion-free groups that are p-divisible for infinitely many primes p, or groups of the form ⊕pϵIZ(p∞), where I is an infinite set of primes.

Keywords

automatic structuresFA-presentableabelian groupsadditive combinatorics
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 4 , December 2011 , pp. 1341 - 1351
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Epstein, David B. A., Cannon, James W., Holt, Derek F., Levy, Silvio V. F., Paterson, Michael S., and Thurston, William P., Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992.CrossRefGoogle Scholar
[2] Freiman, G. A., Nachala strukturnoi teorii slozheniya mnozhestv, Kazan. Gosudarstv. Ped. Inst, 1966.Google Scholar
[3] Green, Ben, Structure theory of set addition, lecture notes available at http://www.dpmms.cam.ac.uk/~bjg23/notes.html, 2002.Google Scholar
[4] Green, Ben and Ruzsa, Imre Z., Freiman's theorem in an arbitrary abelian group, Journal of the London Mathematical Society. Second Series, vol. 75 (2007), no. 1, pp. 163–175.CrossRefGoogle Scholar
[5] Hodgson, Bernard R., On direct products of automaton decidable theories, Theoretical Computer Science, vol. 19 (1982), no. 3, pp. 331–335.CrossRefGoogle Scholar
[6] Khoussainov, Bakhadyr and Minnes, Mia, Three lectures on automatic structures, Logic Colloquium 2007 (Delon, F., Kohlenbach, U., Maddy, P., and Stephan, F., editors), Lecture Notes in Logic, vol. 35, Association for Symbolic Logic, 2010, pp. 132–176.CrossRefGoogle Scholar
[7] Khoussainov, Bakhadyr and Nerode, Anil, Automatic presentations of structures, Logic and computational complexity (Indianapolis, IN, 1994), Lecture Notes in Computer Science, vol. 960, Springer, Berlin, 1995, pp. 367–392.CrossRefGoogle Scholar
[8] Khoussainov, Bakhadyr, Open questions in the theory of automatic structures, Bulletin of the European Association for Theoretical Computer Science, vol. 94 (2008), pp. 181–204.Google Scholar
[9] Khoussainov, Bakhadyr, Nies, André, Rubin, Sasha, and Stephan, Frank, Automatic structures: richness and limitations, Logical Methods in Computer Science, vol. 3 (2007), no. 2:2, 18 pp. (electronic).Google Scholar
[10] Nies, André, Describing groups. The Bulletin of Symbolic Logic, vol. 13 (2007), no. 3, pp. 305–339.CrossRefGoogle Scholar
[11] Nies, André and Semukhin, Pavel, Finite automata presentable abelian groups, Logical foundations of computer science (Nerode, A. and Artemov, S., editors), Lecture Notes in Computer Science, vol. 4514, Springer, Berlin, 2007, pp. 422–436.CrossRefGoogle Scholar
[12] Nies, André and Thomas, Richard M., FA-presentable groups and rings, Journal of Algebra, vol. 320 (2008), no. 2, pp. 569–585.CrossRefGoogle Scholar
[13] Oliver, Graham P. and Thomas, Richard M., Automatic presentations for finitely generated groups, STACS 2005 (Diekert, V. and Durand, B., editors), Lecture Notes in Computer Science, vol. 3404, Springer, Berlin, 2005, pp. 693–704.CrossRefGoogle Scholar
[14] Rubin, Sasha, Automatic structures, Ph.D. thesis, 2004.Google Scholar
[15] Ruzsa, I. Z., Generalized arithmetical progressions and sumsets, Acta Mathematica Hungarica, vol. 65 (1994), no. 4, pp. 379–388.CrossRefGoogle Scholar
[16] Tao, Terence and Vu, Van, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006.CrossRefGoogle Scholar