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

Abstract

The one-dimensional orbit set $⟨F:s⟩$ is formed by the images of a number $s$ under the action of a semigroup generated by integer affine functions $f_i=a_{i}x+b_i$ taken from the set $F=\{f_1,\dots ,f_n\}$. P.Erdős established an upper bound $O(x^{\ddot{I}ƒ+\hat{I}\mu })$ for the growth function $|⟨F:s⟩\cap [0,x]|$, where $1/a_1^{\ddot{I}}ƒ+1/a_2^{\ddot{I}}ƒ+\dots +1/a_n^{\ddot{I}}ƒ=1$ and $\epsilon >0$, which was extended to orbit multisets and real affine functions by J.Lagarias. We complement this by a lower bound $\hat{I}\text{c◯}(x^{\ddot{I}}ƒ)$ for the multiset size $|⟨F:s{⟩}^{\#}\cap [0,x]|$. P.Erdős and R.Graham asked whether an orbit set $⟨F:s⟩$ has positive density when $F$ is a basis of a free semigroup and $1/a_1+1/a_2+\dots +1/a_n=1$. Under these two conditions, we establish a sublinear lower bound $|⟨F:s⟩\cap [0,x]|=\hat{I}\text{c◯}(x/{\log }^{\frac{n-1}{2}}x)$. We also show that in the case when the functions of $F$ form an exact covering system of integers, i.e. when $f_1(\mathbb{Z})\bigsqcup \dots \bigsqcup f_n(\mathbb{Z})=\mathbb{Z}$, this bound can be strengthened to $\hat{I}\text{c◯}(x)$, so the set $⟨F:s⟩$ has positive density.

10 pages