Généralisation d’un résultat de Loxton et van der Poorten. (Generalization of a result of Loxton and van der Poorten). (French) Zbl 0778.11015

Gonzalez, Patrick

Sémin. Théor. Nombres Bordx., Sér. II 4, No. 1, 43-51 (1992).

This paper presents an interesting application of the theory of finite automata to a problem which arose in diophantine approximation. Let \(g\) be an integer with \(g\geq 2\) and let \(C\) be a finite set of non-negative integers. The set \(C\) is called \(g\)-free if it is not possible to find elements \(c_ i\), \(c_ i'\) in \(C\) with \(\sum^ n_{i=0} c_ i g^ i=\sum^ n_{i=0} c_ i' g^ i\) and \((c_ 0,\dots,c_ n) \neq (c_ 0',\dots,c_ n')\). It is relatively easy to see that if \(| C|>g\) then \(C\) cannot be \(g\)-free and if \(| C|<g\) then there are arbitrarily large integers which cannot be written in the form \(\sum c_ k g^ k\). Thus the most interesting case is \(| C|=g\). The author uses the algebra of finite automata to characterise these sets \(C\) which are \(g\)-free.
Suppose, without loss of generality, that 0 is in \(C\). Let \(P(X)= \sum_{c\in C} X^ c\) and \(P_ n(X)= \prod^{n-1}_{h=0} P(X^{g^ h})\), let \(Z_ n\) be the set of roots of \(P_ n\) and let \(U_{g^ n}\) be the set of \(g^ n\)-th roots of unity. Then \(C\) is \(g\)-free if and only if \(| U_{g^ n} \setminus Z_ n|\) is bounded independent of \(n\).
The case \(g=4\) and \(C=\{0,1,k,k+1\}\) recovers a result of J. H. Loxton and A. J. van der Poorten [Acta Arith. 49, 193-203 (1987; Zbl 0636.10003)]. Suppose integers in base 4 are written using digits \(- 1\), 0, 1 and 2. The given set \(C\) is not 4-free if and only if there are integers \(s_ i\), \(s_ i'\) whose base 4 representations contains only the digits 0 and 1 such that \(s_ 2k+s_ 1=s_ 2' k+s_ 1'\) and \((s_ 1,s_ 2)\neq (s_ 1',s_ 2')\). This equation gives \(k\) as the quotient of two integers whose base 4 representations contain only the digits 0, 1 and \(-1\). By the main theorem, the integers \(k\) with this property are those \(k=4^ \alpha k'\) with \(k'\) odd.

Reviewer: J.H.Loxton (North Ryde)

MSC:

11B83	Special sequences and polynomials
68Q70	Algebraic theory of languages and automata
11A67	Other number representations

Keywords:

base \(g\) representations; finite automata; integers in base 4

Citations:

Zbl 0636.10003

References:

[1]	Loxton, J.H. et Poorten, A. J. van der, An awful problem about integers in base 4, Acta Arith.49 (1987), 193-203. · Zbl 0636.10003
[2]	Rauzy, G., Systèmes de numération, Journées de théorie élémentaire et analytique des nombres, 1982, Valenciennes.