Document Open Access Logo

Random Subgroups of Rationals

Authors Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander Melnikov, Karen Seidel, Frank Stephan

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.25.pdf
  • Filesize: 492 kB
  • 14 pages

Document Identifiers

Author Details

Ziyuan Gao
  • Department of Mathematics, National University of Singapore, Singapore
Sanjay Jain
  • School of Computing, National University of Singapore, Singapore
Bakhadyr Khoussainov
  • Department of Computer Science, University of Auckland, New Zealand
Wei Li
  • Department of Mathematics, National University of Singapore, Singapore
Alexander Melnikov
  • Institute of Natural and Mathematical Sciences, Massey University, New Zealand
Karen Seidel
  • Hasso Plattner Institute, University of Potsdam, Germany
Frank Stephan
  • Department of Mathematics, National University of Singapore, Singapore

Funding

Sanjay Jain was supported in part by NUS grant C252-000-087-001. Furthermore, Ziyuan Gao, Sanjay Jain and Frank Stephan have been supported in part by the Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE2016-T2-1-019 / R146-000-234-112. Bakhadyr Khoussainov was supported by the Marsden fund of Royal Society of New Zealand. Karen Seidel was supported by the German Research Foundation (DFG) under Grant KO 4635/1-1 (SCL) and by the Marsden fund of Royal Society of New Zealand.

Acknowledgements

The authors would like to thank Philipp Schlicht and Tin Lok Wong for helpful discussions, as well as thank Timo Kötzing for pointers to the literature.

Cite As Get BibTex

Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander Melnikov, Karen Seidel, and Frank Stephan. Random Subgroups of Rationals. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.25

Abstract

This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup (G,+) of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of (G,+); second, what learnability properties can one extract from G and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of (G,+) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for G with respect to any generating sequence for G is not even semi-decidable, one can build a generating sequence beta such that the word problem for G with respect to beta is co-recursively enumerable (assuming that the set of generators of G is limit-recursive). In regard to the second question, it is proven that there is a generating sequence beta for G such that every non-trivial finitely generated subgroup of G is recursively enumerable and the class of all such subgroups of G is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of G is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of G cannot be syntactically identified in the limit with respect to any generating sequence for G. The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Inductive inference
Keywords
  • Martin-Löf randomness
  • subgroups of rationals
  • finitely generated subgroups of rationals
  • learning in the limit
  • behaviourally correct learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Reinhold Baer. Abelian groups without elements of finite order. Duke Mathematical Journal, 3(1):68-122, March 1937. Google Scholar
  2. Janis Bārzdiņs̆. Two theorems on the limiting synthesis of functions. Latv. Gos. Univ. Uch. Zapiski, 210:82-88, 1974. (In Russian). Google Scholar
  3. Ross A. Beaumont and Herbert S. Zuckerman. A characterization of the subgroups of the additive rationals. Pacific Journal of Mathematics, 1(2):169-177, 1951. Google Scholar
  4. Lenore Blum and Manuel Blum. Toward a Mathematical Theory of Inductive Inference. Information and Control, 28:125-155, 1975. Google Scholar
  5. John Case and Carl Smith. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science, 25:193-220, 1983. Google Scholar
  6. Rod Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, Berlin, Heidelberg, 2010. Google Scholar
  7. Jerome A. Feldman. Some decidability results on grammatical inference and complexity. Information and Control, 20(3):244-262, 1972. Google Scholar
  8. Mark A. Fulk. A Study of Inductive Inference Machines. PhD thesis, State University of New York at Buffalo, Buffalo, NY, USA, 1986. Google Scholar
  9. E. M. Gold. Language Identification in the Limit. Information and Control, 10:447-474, 1967. Google Scholar
  10. Mikhail Gromov. Random walk in random groups. Geometric and Functional Analysis, 13:73-146, 2003. Google Scholar
  11. Nazif G. Khisamiev. Chapter 17:Constructive abelian groups. In Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, and V. W. Marek, editors, Handbook of Recursive Mathematics, volume 139 of Studies in Logic and the Foundations of Mathematics, pages 1177-1231. Elsevier, 1998. Google Scholar
  12. Bakhadyr Khoussainov. A Quest for Algorithmically Random Infinite Structures. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, pages 56:1-56:9, 2014. Google Scholar
  13. Bakhadyr Khoussainov. A Quest for Algorithmically Random Infinite Structures, II. In Logical Foundations of Computer Science - International Symposium, LFCS 2016, pages 159-173, 2016. Google Scholar
  14. Ming Li and Paul Vitány. A New Approach to Formal Language Theory by Kolmogorov Complexity. SIAM Journal on Computing, 24(2):398-410, 1995. Google Scholar
  15. Ming Li and Paul Vitány. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, New York, NY, USA, 3rd edition, 2008. Google Scholar
  16. David Marker. Model theory: an introduction, volume 217 of Graduate Texts in Mathematics. Springer-Verlag, New York, NY, USA, 2002. Google Scholar
  17. Eric Martin and Daniel N. Osherson. Elements of scientific inquiry. MIT Press, Cambridge, Massachusetts, 1998. Google Scholar
  18. Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602-619, 1966. Google Scholar
  19. André Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009. Google Scholar
  20. André Nies and Volkher Scholz. Martin-Löf random quantum states. arXiv preprint arXiv:1709.08422, 2017. Google Scholar
  21. Piergiorgio Odifredd. Classical Recursion Theory. North-Holland, Amsterdam, 1989. Google Scholar
  22. Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, MA, USA, 1987. Google Scholar
  23. Claus-Peter Schnorr. A Unified Approach to the Definition of a Random Sequence. Mathematical Systems Theory, 5(3):246-258, 1971. Google Scholar
  24. Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer Berlin Heidelberg, 1999. Google Scholar
  25. Frank Stephan and Yuri Ventsov. Learning algebraic structures from text. Theoretical Computer Science, 268(2):221-273, 2001. Google Scholar
  26. Sándor Szabó and Arthur D. Sands. Factoring groups into subsets. Lecture Notes in Pure and Applied Mathematics. Chapman and Hall/CRC Press, 6000 Broken Sound Parkway NW, Suite 300, 2009. Google Scholar
  27. Wanda Szmielew. Elementary properties of Abelian groups. Fundamenta Mathematicae, 41(2):203-271, 1955. Google Scholar
  28. Todor Tsankov. The additive group of the rationals does not have an automatic presentation. Journal of Symbolic Logic, 76(4):1341-1351, 2011. Google Scholar
  29. Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-Learning Applications of Algorithmic Randomness. In Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999), pages 444-453, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact