On orbit sets generated by semigroups of one-dimensional affine functions

Technical Summary: On Orbit Sets Generated by Semigroups of One-Dimensional Affine Functions

Problem Statement
This paper investigates the asymptotic growth of one-dimensional orbit sets $\langle F : s \rangle$ and orbit multisets $\langle F : s \rangle^\#$, generated by a set of integer affine functions $F = \{f_i(x) = a_i x + b_i\}_{i=1}^n$ acting on a starting value (or set) $s$. The central problem is determining the density of these sets, specifically whether the growth function $|\langle F : s \rangle \cap [0, x]|$ is positive (i.e., has a non-zero lower asymptotic density) under specific conditions.

The study focuses on the critical case where the slopes $a_i$ satisfy the equation $\sum_{i=1}^n \frac{1}{a_i} = 1$. Previous work by P. Erdős established an upper bound of $O(x^{\sigma+\epsilon})$ for the growth function when $\sum a_i^{-\sigma} = 1$. Erdős and Graham posed a specific open question: if $F$ forms a basis of a free semigroup (meaning no non-trivial composition relations exist among the functions) and $\sum a_i^{-1} = 1$, does the orbit set $\langle F : s \rangle$ have positive density? While it was known that if $\sum a_i^{-1} < 1$ the density is zero, the case of equality remained unresolved for general free semigroups.

Methodology
The authors employ a combination of combinatorial analysis, induction, and algebraic techniques to derive lower bounds for the size of these orbit sets.

1. Lower Bound for Multisets: The paper first establishes a lower bound for the size of the orbit multiset $\langle F : s \rangle^\#$. By analyzing the composition of affine functions, the authors derive an auxiliary inequality (Lemma 4) bounding the image of a point under a composition of functions. Using this, they prove a lower bound of $\Omega(x^\sigma)$ for the multiset size when $\sum a_i^{-\sigma} = 1$. This complements the existing Erdős-Lagarias upper bound, though the authors note a gap remains between the upper bound $O(x^{\sigma+\epsilon})$ and the lower bound $\Omega(x^\sigma)$, leaving the precise asymptotic behavior ($\Theta(x^\sigma)$) an open question for general cases.

2. Sublinear Bound for Free Semigroups: To address the Erdős-Graham question, the authors utilize the properties of free semigroups. They construct a set of function compositions with equal slopes but distinct free coefficients (Lemma 6). By applying Stirling's approximation to the count of these compositions, they derive a sublinear lower bound for the orbit set size when $\sum a_i^{-1} = 1$ and $F$ is a free semigroup basis.

3. Exact Covering Systems: The paper introduces a connection between orbit sets and "exact covering systems" (partitions of integers into disjoint arithmetic progressions). By applying a version of the Ping-Pong Lemma to the direct functions on the set of integers $\mathbb{Z}$, the authors show that if the functions in $F$ form an exact covering system (i.e., $f_1(\mathbb{Z}) \sqcup \dots \sqcup f_n(\mathbb{Z}) = \mathbb{Z}$), the orbit set has positive density.

Key Contributions and Results

• Theorem 2 (Multiset Lower Bound): The authors prove that for a finite set of affine functions with $\sum a_i^{-\sigma} = 1$, the size of the orbit multiset satisfies $|\langle F : s \rangle^\# \cap [0, x]| = \Omega(x^\sigma)$. This provides the first general lower bound complementing the Erdős-Lagarias upper bound.
• Theorem 5 (Sublinear Bound for Free Semigroups): Addressing the Erdős-Graham question, the paper establishes that if $F$ is a basis of a free semigroup and $\sum a_i^{-1} = 1$, then for any $s \ge 0$, the orbit set size satisfies:
  $$|\langle F : s \rangle \cap [0, x]| = \Omega\left(\frac{x}{\log^{\frac{n-1}{2}} x}\right)$$
  This result demonstrates that the growth is at least sublinear, though it falls short of proving positive density (which would require $\Omega(x)$) for the general free semigroup case.
• Theorem 7 (Positive Density for Exact Covering Systems): The paper proves that if the functions in $F$ form an exact covering system of integers, the orbit set $\langle F : s \rangle$ has positive density. The proof relies on showing that under these conditions, the multiplicity of elements in the orbit multiset is at most one, reducing the multiset size to the set size, which is then bounded below by the linear term derived from Theorem 2.
• Application to Klarner Tuples: The authors apply their results to specific "Klarner tuples" (integer triples $(a, b, c)$ where $2x+a, 3x+b, 6x+c$ form a free semigroup). While the density problem remains open for the classic slopes $\{2, 3, 6\}$, the authors demonstrate that for the slope set $\{2, 4, 4\}$ with specific coefficients derived from exact covering systems, the orbit set has positive density.

Significance and Claims
The paper claims to complement the foundational work of Erdős and Lagarias by providing a matching lower bound for the multiset size, thereby narrowing the gap in understanding the growth of these sets. Specifically, it provides an "almost linear" lower bound for the Erdős-Graham question in the context of free semigroups.

Furthermore, the paper claims to resolve the Erdős-Graham question in the affirmative for the specific sub-case where the generating functions form an exact covering system. The authors highlight that this connects two previously distinct topics in number theory: the study of orbit sets and the theory of exact covering systems (a topic popularized by Erdős). The work clarifies that while the general case for free semigroups with $\sum a_i^{-1} = 1$ remains open (with only a sublinear bound currently proven), the condition of forming an exact covering system is sufficient to guarantee positive density. The paper does not claim to solve the general Erdős-Graham question for all free semigroups, nor does it resolve the density problem for the specific slopes $\{2, 3, 6\}$, noting that these remain open.