Given a primitive substitution, we define different binary operations on infinite subsets of the nonnegative integers. These binary operations are defined with the help of the Dumont-Thomas numeration system; that is, a numeration system associated with the substitution. We give conditions for these semigroups to have an identity element. We show that they are not finitely generated. These semigroups define actions on the set of positive integers. We describe the orbits of these actions. We also estimate the density of these sets as subsets of the positive integers. 1. Introduction Integer semigroups have been studied in different contexts (cf. [1–4]). One of the well known binary operations is the Fibonacci multiplication, introduced by Knuth [1]. This operation is related to the dynamical system obtained by the Fibonacci substitution (cf. [3]). It has been generalized in different ways to the tribonacci substitution; see [4–6]. The author studied the usage of binary operations on the set of nonnegative integers, in order to describe the self-similar structure of the -bonacci substitutions [4] and on the so-called flipped tribonacci substitution [7]. In the present article, we introduce binary operations on infinite subsets of the nonnegative integers so that they are integer semigroups. These binary operations are associated with a substitution, in particular to the numeration system defined by the substitution, the so-called Dumont-Thomas numeration system. These numeration systems play an important role in the study of Rauzy fractals; for details see [8, 9] and references within. The integer semigroups defined in the paper, in general, do not have identity elements. We explore when they have identity elements. In Theorem 3, we show that these semigroups are not finitely generated. Moreover, we show that these semigroups define actions on the set of positive integers, and we describe the orbits of these actions. In Section 4, we study the density of these semigroups as subsets of the positive integers. 2. Substitutions and Automata A substitution on a finite alphabet is a map from to the set of finite words on ; that is, . This map extends to by concatenation by and , for all , . Let denote the set of one-sided infinite sequences in . The map is extended to in the obvious way. We call a fixed point of if and periodic if there exists so that it is fixed for . There is a dynamical system associate to the sequence , called substitution dynamical system; for details see [8–10]. The incidence matrix of the substitution is defined as the matrix whose entry
References
[1]
D. E. Knuth, “Fibonacci multiplication,” Applied Mathematics Letters, vol. 1, no. 1, pp. 57–60, 1988.
[2]
A. S. Fraenkel, H. Porta, and K. B. Stolarsky, “Some arithmetic semigroups,” in Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, B. C. Berndt, Ed., pp. 255–264, Birkhauser, Boston, Mass, USA, 1990.
[3]
P. Arnoux, “Some remarks about Fibonacci multiplication,” Applied Mathematics Letters, vol. 2, no. 4, pp. 319–320, 1989.
[4]
V. F. Sirvent, “A semigroup associated with the -bonacci numbers with dynamic interpretation,” The Fibonacci Quarterly, vol. 35, no. 4, pp. 335–340, 1997.
[5]
A. Messaoudi, “Généralisation de la multiplication de Fibonacci,” Mathematica Slovaca, vol. 50, no. 2, pp. 135–148, 2000.
[6]
A. Messaoudi, “Tribonacci multiplication,” Applied Mathematics Letters, vol. 15, no. 8, pp. 981–985, 2002.
[7]
V. F. Sirvent, “Semigroups and the self-similar structure of the flipped Tribonacci substitution,” Applied Mathematics Letters, vol. 12, no. 1, pp. 25–29, 1999.
[8]
V. Berthé and M. Rigo, Eds., Combinatorics, Automata and Number Theory, vol. 135 of Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, UK, 2010.
[9]
N. P. Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, vol. 1794 of Lecture Notes in Mathematics, Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel, Springer, Berlin, Germany, 2002.
[10]
G. Rauzy, “Nombres algébriques et substitutions,” Bulletin de la Société Mathématique de France, vol. 110, no. 2, pp. 147–178, 1982.
[11]
G. Rauzy, “Sequences defined by iterated morphisms,” in Sequences, R. M. Capocelli, Ed., pp. 275–286, Springer, New York, NY, USA, 1990.
[12]
S. Eilenberg, Automata, Languages, and Machines, Academic Press, New York, NY, USA, 1974.
[13]
J.-M. Dumont and A. Thomas, “Systemes de numeration et fonctions fractales relatifs aux substitutions,” Theoretical Computer Science, vol. 65, no. 2, pp. 153–169, 1989.
[14]
J.-M. Dumont and A. Thomas, “Digital sum moments and substitutions,” Acta Arithmetica, vol. 64, no. 3, pp. 205–225, 1993.
[15]
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge University Press, Cambridge, UK, 2003.
[16]
V. Berthé and M. Rigo, “Abstract numeration systems and tilings,” in Proceedings of the 32nd Symposium, Mathematical Foundations of Computer Science, vol. 3618 of Lecture Notes in Computer Science, pp. 131–143, Springer, 2007.
[17]
C. Frougny, “Representations of numbers and finite automata,” Mathematical Systems Theory, vol. 25, no. 1, pp. 37–60, 1992.
[18]
P. J. Grabner, P. Liardet, and R. F. Tichy, “Odometers and systems of numeration,” Acta Arithmetica, vol. 70, no. 2, pp. 103–123, 1995.
[19]
N. Bourbaki, Elements of Mathematics: Algebra I, Springer, Berlin, Germany, 2007.
[20]
F. Gantmacher, The Theory of Matrices, vol. 2, American Mathematical Society, Providence, RI, USA, 2000.
[21]
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.
