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

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.


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


Zbl 0636.10003
Full Text: DOI Numdam EuDML


[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.