Random Subgroups of Rationals.

Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander G. Melnikov, Karen Seidel, Frank StephanMFCS 2019 · OpenReview

TL;DR

This paper introduces a novel definition of algorithmic randomness for subgroups of rational numbers. They demonstrate that these "random" subgroups share the same decidable theory as the integers and explore their learnability, finding that while some aspects are learnable, others are not, revealing a deep connection between the complexity of their generators and learnability.

What Problem Does This Paper Address?

The field of algorithmic randomness has seen significant success in defining and studying random strings and infinite sequences. However, extending these notions to more complex structures like graphs and groups has been a long-standing challenge. Specifically, this paper tackles the question of how to define and study "random" infinite algebraic structures, focusing on subgroups of the rational numbers ($\mathbb{Q}, +$). The authors aim to understand the model-theoretic (e.g., decidability of their theories) and recursion-theoretic (e.g., complexity of their word problems) properties of these random subgroups, as well as their learnability properties, particularly for their finitely generated substructures.

Methods

The core of the paper's methodology lies in encoding a Martin-Löf random binary sequence directly into the generators of a subgroup of rationals. A subgroup $G_R$ is constructed based on a random sequence $R$, where its generators are derived from prime powers whose exponents are determined by the patterns of 0s and 1s in $R$. This approach allows them to leverage the established theory of algorithmic randomness for sequences to define randomness for these groups.

Key techniques employed include:

  • Martin-Löf Tests: Used to define randomness for infinite binary sequences, which are then used to construct the random subgroups.
  • Model Theory: To analyze the first-order theories of the random subgroups and compare them to known structures like $(\mathbb{Z}, +)$.
  • Recursion Theory: To study the complexity of the word problem for these subgroups and the learnability of their substructures.
  • Inductive Inference (Learning Theory): To investigate whether finitely generated subgroups can be identified in the limit from examples, distinguishing between behavioral correctness (Bc-learnability) and explanatory learnability (Ex-learnability).

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and properties rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Randomness for Groups: The paper provides a concrete and well-motivated way to define algorithmic randomness for infinite algebraic structures, specifically subgroups of rationals. This bridges a gap in the study of random structures.
  • Decidable Theory: Surprisingly, despite their "random" and potentially incomputable nature, these random subgroups of rationals share the same decidable first-order theory as the integers $(\mathbb{Z}, +)$. This suggests that algorithmic randomness, in this context, doesn't necessarily imply complex logical properties.
  • Word Problem Complexity: While the word problem for these random subgroups is generally not even semi-decidable, the authors show that a specific generating sequence can be constructed to make it co-recursively enumerable (co-r.e.). This highlights the crucial role of the chosen generating sequence.
  • Learnability Dichotomy: A significant finding is the contrast in learnability for finitely generated subgroups. The class of these subgroups is behaviorally correctly learnable (meaning they can be identified up to semantic equivalence), but not explanatorily learnable (meaning they cannot be identified with a unique syntactic representation) with respect to any generating sequence. This reveals a fundamental limitation in learning these structures syntactically.
  • Connection between Generators and Learnability: The paper establishes a strong link between the arithmetical complexity of the group's generators (specifically, whether the set of generators is limit-recursive) and the learnability of its finitely generated subgroups.

Key Results

  • The theory of any randomly generated subgroup of rationals coincides with that of $(\mathbb{Z}, +)$ and is therefore decidable.
  • For a randomly generated subgroup $G_R$, a generating sequence $\beta$ can be constructed such that its word problem is co-r.e. (assuming $R$ is limit-recursive).
  • There exists a generating sequence $\beta$ for $G_R$ such that every non-trivial finitely generated subgroup $F$ of $G_R$ has a recursively enumerable (r.e.) representation $F_\beta$, and the class of all such representations is behaviorally correctly learnable.
  • However, the class of these representations cannot be syntactically identified in the limit (i.e., is not explanatorily learnable).
  • The paper also shows that for a randomly generated subgroup $G_R$, equality modulo 1 with respect to some generating sequence is r.e.

Limitations and Future Work

  • Abelian Groups: The definition of randomness is currently tailored to subgroups of rationals. The authors note that extending this to more general Abelian groups, especially those of rank 2, is challenging due to the current lack of classification of their isomorphism types.
  • General Structures: The paper doesn't explore the application of this randomness definition to other algebraic structures beyond subgroups of rationals, leaving open questions about its broader applicability.
  • Syntactic vs. Semantic Learnability: The paper highlights a clear distinction between semantic and syntactic learnability for these structures. Future work could explore conditions under which syntactic learnability might be achieved or investigate other forms of learning.
  • Complexity of Generators: The reliance on the limit-recursiveness of the generator set for certain learnability results suggests further investigation into how different levels of complexity in the generator set impact the properties of the random subgroup.

Summary updated

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.
BibTeX
@inproceedings{gao2019random,
  author = {Ziyuan Gao and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Alexander G. Melnikov and Karen Seidel and Frank Stephan},
  title = {{Random Subgroups of Rationals.}},
  booktitle = {MFCS},
  year = {2019},
  url = {https://openreview.net/forum?id=-vThwA6-Kc},
}
Figure