Factorisation de fractions rationnelles
et de suites récurrentes

par

JEAN BERSTEL (Paris)

1. **Introduction.** Il est bien connu [8] qu'un polynôme $f$ à coefficients entiers est puissance $k$-ième d'un polynôme $h$ de même nature si $f(n)$ est puissance $k$-ième d'un entier pour tout $n \in N$, et même s'il en est ainsi pour tout $n \in A$, où $A$ est une partie de $N$ qui rencontre toute progression arithmétique [5]. D'autres propriétés analogues de factorisation, pour la composition des fonctions, de polynômes ou de fractions rationnelles peuvent se formuler comme solutions partielles au problème général suivant:

(*) „Etant donnés deux ensembles de nombres $E$ et $F$, deux applications $f$ et $g$ de $E$ dans $F$, et une partie $A$ de $E$, déterminer les conséquences de l'inclusion $f(A) \subset g(E)$”.

L'inclusion $f(A) \subset g(E)$ équivaut à l'existence d'une application $h$
de $A$ dans $E$ telle que $f_{1,A} = g \circ h$. La conclusion cherchée est que $h$ est
„de même nature” que $f$ ou $g$, et de déterminer la forme particulière
que prend alors la fonction $f$. Ainsi, si $f \in Z[t]$, et $g = t^k$, le théorème rap-
pelé ci-dessus affirme que $h$ est également un polynôme, et donc que $f$
se factorise en $f = h^k$.

On constate que des propriétés établies lorsque $A = N$ ou $A = Z$
restent souvent vraies lorsque $A$ n'est plus qu'une partie de $N$ ou de $Z$
rencontrant toute progression arithmétique. Il en est ainsi pour l'énoncé cité
plus haut; c'est le cas également du théorème de Fatou, comme l'a prouvé
Rauzy [10]. Un tel ensemble $A$ est appelé *arithmétiquement dense* par Rauzy.

Dans cet article, nous examinons le problème (*) dans quelques
situations très particulières, qui trouvent leur application dans l'étude
des propriétés arithmétiques de langages formels [3]; les ensembles $E$
et $F$ seront $N$, $Z$ ou $Q$, et les fonctions $f$ et $g$ des polynômes, des fractions
rationnelles ou ce que nous appelons des fonctions *adrationnelles*, c'est-à-dire
des fonctions $u$ telles que la suite $(u(n))_{n \ge 0}$ soit une suite récurrente.

Dans la deuxième section, nous rassemblons quelques propriétés
des ensembles arithmétiquement denses. Les résultats que nous avons
obtenus se formulent en trois théorèmes principaux qui seront démontrés avec leurs corollaires dans les sections 3, 4 et 5. Ces théorèmes sont les suivants:

**THÉORÈME I.** *Soit $\mathcal{A} = \sum u_n t^n$ une série rationnelle à coefficients entiers et $A \subseteq N$ un ensemble arithmétiquement dense; s'il existe un entier $k \ge 1$ tel que, pour tout $n \in A$, $u_n$ a au plus k facteurs premiers distincts, alors $\mathcal{A}$ se met sous la forme:*

$$ (1) \qquad \mathcal{A} = P(t) + \sum_{m=0}^{M-1} \frac{a_m t^m}{1 - b_m t^M}, $$

où $P \in \mathbb{Z}[t]$, $M \ge 1$, et $a_m, b_m \in \mathbb{Z}$ pour $m = 0, \dots, M-1$.

Ce théorème précise un résultat dû à G. Pólya [6]. Remarquons qu'il implique que, sauf si $\mathcal{A}$ se met sous la forme (1), le nombre de facteurs premiers divisant $u_n$, et donc la taille du plus grand facteur premier divisant $u_n$, ne sont pas bornés lorsque $n$ tend vers l'infini. Dans le cadre du problème (*) on peut formuler les hypothèses du théorème I comme suit:

L'ensemble $\{u_n: n \ge 0\}$ est contenu dans l'ensemble $b(N)$ des valeurs d'une fonction $b$ qui énumère les entiers ayant au plus $k$ facteurs premiers distincts.

**THÉORÈME II.** *Soit $f \in Q(t)$ une fraction rationnelle et $A \subset Z$ un ensemble arithmétiquement dense;*

(1) si $f(A) \subset g(Z)$ pour $g \in Q(t)$, il existe $r \in Q[t]$ tel que $f = g \circ r$;

(2) si $f(A) \subset p(Q)$ pour $p \in Q[t]$, il existe $g \in Q(t)$ tel que $f = p \circ g$.

Ceci représente l'extension aux fractions rationnelles du théorème cité plus haut.

**THÉORÈME III.** *Soit $\mathcal{A} = \sum_{n=0}^{\infty} u(n) t^n$ une série rationnelle à coefficients entiers ayant un pôle unique simple sur son cercle de convergence; si $u(N) \subset p(Z)$, pour $p \in C[t]$, il existe une série rationnelle $\mathcal{B} = \sum_{n=0}^{\infty} v(n) t^n$ à coefficients entiers telle que $u = p \circ v$.*

Ce théorème est une généralisation d'un résultat dû à Ch. Pisot (cf. [1]).

**2. Ensembles arithmétiquement denses.** Un sous-ensemble $A$ de $N$ (resp. de $Z$) est arithmétiquement dense dans $N$ (resp. $Z$) s'il rencontre toute progression arithmétique infinie de $N$ (resp. de $Z$), donc si pour tout $a, b \in N$ (resp. $a, b \in Z$), $a \ne 0$, on a $A \cap (aN + b) \ne \emptyset$ (resp. $A \cap (aZ + b) \ne \emptyset$). La terminologie, due à Rauzy, est justifiée par la marque suivante [10]:

Si l'on munit $N$ (resp. $Z$) de la topologie la moins fine qui rende continue les injections canoniques de $N$ (resp. $Z$) dans $Q_p$, pour tout nombre premier $p$, alors les progressions arithmétiques $aN+b$ (resp. $aZ+b$) pour tout $a \in N \setminus \{0\}$, forment une base de voisinages de $b$, et par conséquent $A$ est un sous-ensemble dense de $N$ (resp. $Z$) pour cette topologie.

Si $A$ est arithmétiquement dense dans $N$, il l'est également dans $Z$, mais si $A$ est arithmétiquement dense dans $Z$, alors $A \cap N$ ne l'est pas nécessairement dans $N$. Donnons, pour références ultérieures, quelques propriétés élémentaires des ensembles arithmétiquement denses:

**PROPOSITION 2.1.** *Soit $A$ arithmétiquement dense dans $Z$. *

(i) L'ensemble $A$ rencontre toute progression arithmétique une infinité de fois;

(ii) *Soient $a, b \in Z$, $a \ne 0$; l'ensemble $B = \{k \in Z | ak + b \in A\}$ est arithmétiquement dense;*

(iii) *L'ensemble $B = \{n \in A | |n| \ge N_0 \text{ fixé}\}$ est arithmétiquement dense.*

Preuve. (i) est due à [5], et (iii) en découle immédiatement. Pour vérifier (ii), soit $a'Z + b'$ ($a' \ne 0$) une progression arithmétique et soit $x \in A \cap (ax'Z + ab' + b)$. Il existe $k' \in Z$ tel que $x = a(a'k' + b') + b \in A$, donc $k = a'k' + b' \in B$ et $B \cap (a'Z + b')$ n'est pas vide.

**PROPOSITION 2.2.** *Si la densité supérieure $d^+P$ de $P \subset N$ est 1, alors $P$ est arithmétiquement dense.*

Supposons en effet que

$$ d^+P = \limsup_{n \to \infty} \frac{1}{n} \text{Card}(P \cap \{0, \dots, n\}) = 1, $$

et que $P$ re rencontre pas la progression arithmétique $aN+b$ ($a \ge 1$, $b \ge 0$). Alors

$$ \text{Card}(P \cap \{0, \dots, ak+b\}) \le (a-1)k+b, \quad \text{et} \quad d^+P \le 1-1/a. $$

Des exemples d'ensembles arithmétiquement denses $A \subset N$ sont fournis par les ensembles de fréquence $> 1$ de Rauzy [9]. Rappelons que $J \subset N$ est de fréquence $> 1$ s'il existe un nombre réel $q > 1$, tel que, pour tout $x_0 > 0$, il existe $x \in N$, avec $x \ge x_0$, et $\{n: x \le n < qx\} \subset J$. Les ensembles de fréquence $> 1$ ne forment pas tous les ensembles arithmétiquement denses de $N$, comme le montre l'ensemble $A = \bigcup_{n \in N} \{n^3, n^3+1, \dots, n^3+n-1\}$. L'ensemble $A$ contient des intervalles arbitrairement grands de nombres entiers conséutifs, et est par conséquent arithmétiquement dense, sans être de fréquence $> 1$. Cet exemple montre de plus qu'il existe des ensembles arithmétiquement denses de densité asymptotique nulle. Une autre différence importante entre les ensembles arithmétiquement denses de $N$ et les ensembles de fréquence $> 1$ est que les
premiers peuvent ne pas contenir de nombres premiers, alors que les derniers en contiennent nécessairement une infinité. L'ensemble $\mathcal{B}$ des entiers qui possèdent un facteur carré est en effet arithmétiquement dense, comme on le voit immédiatement.

**3. Une généralisation d'un théorème de G. Pólya.** Soit $K$ un corps commutatif; une série formelle $\mathcal{A} = \sum_{n=0}^{\infty} a_n t^n$ à coefficients dans $K$ est rationnelle s'il existe $q_1, \dots, q_h \in K$, $q_h \neq 0$, $n_0 \in \mathbb{N}$ tels que:

$$ (3.1) \qquad a_{n+h} = q_1 a_{n+h-1} + \dots + q_h a_n $$

pour tout $n \ge n_0$. La série $\mathcal{A}$ représente alors le développement en série de Taylor, autour de l'origine, d'une fraction rationnelle $P/Q$, où $P, Q \in K[t]$, et

$$ Q(t) = 1 - q_1 t - \dots - q_h t^h. $$

La relation (3.1) est la plus courte relation de récurrence que vérifie la suite $(a_n)_{n \ge 0}$ si, et seulement si $P$ et $Q$ sont sans facteur commun; elle est vérifiée pour tout $n \ge 0$ si, et seulement si degré $P <$ degré $Q$. Une série rationnelle pour laquelle cette condition est vérifiée est dite normalisée.

Appelons, avec B. Benzaghou [1], suite de Pólya une suite $(a_n)_{n \ge 0}$ de nombres rationnels telle que la valuation p-adique $v_p$ est triviale sur $(a_n)_{n \ge 0}$ pour tous les nombres premiers à l'exception d'un nombre fini d'entre eux. G. Pólya [5] a caractérisé les séries rationnelles normalisées

$$ \mathcal{A} = \sum_{n=0}^{\infty} a_n t^n \quad \text{à coefficients rationnels dont la suite des coefficients } (a_n)_{n \ge 0} $$

est une suite de Pólya (résultat généralisé aux séries à coefficients dans un corps de nombres quelconque par Benzaghou [1]), en prouvant que ces séries sont de la forme suivante, appelées séries de Pólya:

$$ (3.2) \qquad \mathcal{A} = \sum_{m=0}^{M-1} \frac{a_m t^m}{1 - b_m t^M}, $$

où $M \ge 1$, et $b_0, \dots, b_{M-1} \in Q$. Nous prouvons ici que la même conclusion reste vraie lorsque les hypothèses du théorème de Pólya sont affaiblies. D'une part, on ne considère qu'une sous-suite de la suite des coefficients dont les indices forment un ensemble $\mathcal{A}$ arithmétiquement dense dans $\mathbb{N}$ (suivant ainsi la démarche de Rauzy [10] pour le théorème de Fatou), et d'autre part, on n'impose de restrictions que sur le nombre de facteurs premiers distincts des coefficients $a_n$ ($n \in \mathbb{N}$).

Appelons suite de Pólya généralisée une suite $(a_n)_{n \ge 0}$ de nombres rationnels pour laquelle il existe un ensemble arithmétiquement dense $\mathcal{A}$

de $\mathbb{N}$, et un entier $k \ge 0$ vérifiant: pour tout $n \in \mathcal{A}$ tel que $a_n \neq 0$, on a $v_p(a_n) \neq 0$ pour au plus $k$ nombres premiers. Toute suite de Pólya est une suite de Pólya généralisée. La suite $(a_n)_{n \ge 0}$ définie par $a_p = p$ si $p$ est premier, $a_n = 0$ sinon, est une suite de Pólya généralisée sans être une suite de Pólya.

**THÉORÈME I.** Soit $\mathcal{A} = \sum_{n=0}^{\infty} a_n t^n$ une série rationnelle normalisée à coefficients rationnels; la suite $(a_n)_{n \ge 0}$ est une suite de Pólya généralisée si, et seulement si $\mathcal{A}$ est une série de Pólya.

Remarque. On construit facilement des exemples montrant que ce résultat est le meilleur possible en ce sens que si l'ensemble $\mathcal{A}$ a une intersection vide avec au moins une progression arithmétique $b\mathbb{N}+c$, la conclusion du théorème cesse d'être vraie.

Dans l'exemple d'application suivant, $d(m)$ est le nombre de diviseurs de $m \in \mathbb{Z} \setminus \{0\}$, et $d(0) = 0$.

**COROLLAIRE 3.1.** Soit $\mathcal{A} = \sum_{n=0}^{\infty} a_n t^n$ une série rationnelle à coefficients entiers; pour que les coefficients de $\mathcal{A}$ soient bornés, il faut et il suffit qu'il existe un ensemble arithmétiquement dense $\mathcal{A} \subset \mathbb{N}$ tel que $\sup\{d(a_n) | n \in \mathcal{A}\} < \infty$.

Preuve. Si $\sup\{d(a_n) | n \in \mathcal{A}\} = k < \infty$, chaque $a_n$ ($n \in \mathcal{A}$) a au plus $k$ facteurs premiers. On peut d'autre part supposer la série $\mathcal{A}$ normalisée en modifiant au plus un nombre fini de coefficients; par le théorème, la série $\mathcal{A}$ est donc de la forme (3.2), et comme chacune des séries $\frac{a_m t^m}{1 - b_m t^M}$ contient une infinité de coefficients d'indice dans $\mathcal{A}$ (par 2.1), on a $b_m \in \{-1, 0, 1\}$, ce qui prouve le corollaire.

Pour la preuve du théorème I, on utilise les trois lemmes suivants dus à Benzaghou [1].

**LEMME 3.2.** Soit $\mathcal{A} = \sum_{n=0}^{\infty} a_n t^n$ une série rationnelle à coefficients complexes. Il existe un entier $M$ tel que pour tout $m = 0, \dots, M-1$, les séries $\mathcal{A}_{m,M} = \sum_{r=0}^{\infty} a_{m+rM} t^r$ satisfont la propriété (S) suivante:

(S) aucun des quotients $a_i/a_j$ de deux pôles $a_i$ et $a_j$ de $\mathcal{A}_{m,M}$ n'est une racine de l'unité autre que 1.

**LEMME 3.3.** Soit $\mathcal{A} = \sum_{n=0}^{\infty} a_n t^n$ une série rationnelle à coefficients rationnels, et p un nombre premier. Il existe $N \ge 1$, et un entier $n_0$ tels que l'application $r \to v_p(a_{n_0+rN})$ soit une fonction affine.

Autrement dit, il existe $\lambda, \mu$ tels que $v_p(a_{n_0+rN}) = \lambda r + \mu$.
LEMME 3.4. Si la série $\mathcal{A} = \sum_{n=0}^{\infty} a_n t^n$ à coefficients complexes, satisfait à la propriété (S), et si, pour des entiers $r, T$, il existe une relation de la forme $a_{r+nT} = cd^n$ pour une infinité de $n \in \mathbb{N}$, alors $a_n$ est de la forme $a_n = c'd^n$ pour tout $n \in \mathbb{N}$.

Preuve du théorème I. a). D'après le théorème d'Eisenstein, il existe un entier $q \in \mathbb{N} \setminus \{0\}$ tel que $b_n = q^{n+1} a_n \in \mathbb{Z}$ pour tout $n \ge 0$. Comme $(a_n)_{n \ge 0}$ est une suite de Pólya généralisée si, et seulement si $(b_n)_{n \ge 0}$ l'est, on peut supposer $\mathcal{A}$ à coefficients entiers. D'autre part, il suffit de prouver le théorème pour les séries $\mathcal{A}_{m,M}$ données par le lemme 3.2. Comme les ensembles $A'_m = \{k : m+kM \in \mathcal{A}\}$ sont arithmétiquement denses par 2.1 (ii), on peut supposer que la série $\mathcal{A}$ vérifie la condition (S).

b). Notons, pour une suite $(u_n)_{n \in \mathbb{N}}$ d'entiers, et une partie $P \subset \mathbb{N}$, par $\mathcal{P}((u_n)_{n \in P})$ l'ensemble des nombres premiers divisant au moins un $u_n$ avec $n \in P$. Nous allons vérifier qu'il existe un ensemble arithmétiquement dense $B \subset \mathbb{N}$, et deux entiers $r, T$ ($T \ge 1$) tels que $\mathcal{P}((a_{r+nT})_{n \in B})$ est fini.

Soit en effet $k$ le plus petit entier $k'$ tel que pour tout $n \in \mathcal{A}$, $a_n$ a au plus $k'$ facteurs premiers distincts. Si $k = 0$, l'assertion est triviallement vraie pour $r = 0$, $T = 1$, $B = \mathcal{A}$.

Supposons donc $k > 0$, et supposons que la suite $(a_n)$ vérifie la relation de récurrence (3.1). Dans l'ensemble $J$ des indices $n \in \mathcal{A}$ tels que $a_n$ a exactement $k$ facteurs premiers distincts, soit $r$ un de ceux pour lesquels le nombre $s$ de facteurs premiers $p$ ne divisant pas $q_h$ soit maximal. Par construction, on a donc Card{$p | p | a_n$ et $p \nmid q_h$} $\le s$ pour tout $n \in J$. Soient $p_1, p_2, \dots, p_s$ les facteurs premiers de $a_r$ ne divisant pas $q_h$, et $P = p_1 p_2 \dots p_s$. La suite $(a_n)_{n \in \mathbb{N}}$ est purement périodique mod $P$ [4]. Soit $T$ sa période, et soit $B = \{n : r+nT \in \mathcal{A}\}$. Par 2.1 (ii), $B$ est arithmétiquement dense dans $\mathbb{N}$. Pour tout $n \in B$, $a_{r+nT} = 0 \pmod{P}$, et en vertu de la maximalité de $s$, $a_{r+nT}$ ne possède comme facteurs premiers, en dehors de $p_1, p_2, \dots, p_s$, au plus les facteurs premiers de $q_h$, qui sont en nombre fini. Les diviseurs premiers de la suite $(a_{r+nT})_{n \in B}$ sont donc en nombre fini, ce qu'il fallait prouver.

c). Posons $\mathcal{P}((a_{r+nT})_{n \in B}) = \{p_1, \dots, p_l\}$. La démonstration se fait par récurrence sur $l$. Si $l=0$, alors $a_{r+nT} \in \{0, 1, -1\}$ pour tout $n \in B$; par le lemme 3.4, on a $a_n = \epsilon$ pour tout $n \in \mathbb{N}$ où $\epsilon \in \{0, 1, -1\}$, et la série est bien de Pólya. Si $l > 0$, posons pour tout $n \in B$,

$$a_{r+nT} = \epsilon_n p_1^{q_1(n)} \dots p_l^{q_l(n)}, \quad \epsilon_n \in \{-1, +1\}, \quad q_i(n) \in \mathbb{N}.$$

La série $\sum a_{r+nT} t^n$ étant rationnelle, il existe, par lemme 3.3, des entiers $n_0$ et $N$ tels que l'application $n \to v_{p_1}(a_{r+n_0T+NTn})$ soit affine. Posons $v_{p_1}(a_{r+n_0T+NTn}) = \lambda n + \mu$. L'ensemble $C = \{n : n_0 + Nn \in B\}$ est arithmétiquement dense,

et la série $b = \sum b_{r'+nT} t^n$ où $b_{r'+nT} p_1^{2n+\mu} = a_{r'+nT}$ ($r' = r+n_0T, T' = NT$) est évidemment rationnelle. Il existe donc un ensemble arithmétiquement dense $C$ tel que $\mathcal{P}((b_{r'+nT})_{n \in C})$ soit fini et de cardinalité $l-1$. Par hypothèse de récurrence la série $b$ est de Pólya donc $a_{r'+nT}$ s'écrit sous la forme $a_{r'+nT} = p_1^{2n+\mu} cd^n$. Par le lemme 3.4, on a $a_n = c'd^n$ pour tout $n \in \mathbb{N}$. Ceci achève la démonstration.

**4. Factorisation des fractions rationnelles.** Dans cette section, nous prouvons le théorème suivant qui est l'analogue du théorème de factorisation des polynômes.

**THÉORÈME II.** Soit $f \in \mathcal{Q}(t)$, une fraction rationnelle, et $A$ un ensemble arithmétiquement dense dans $\mathbb{Z}$;

(1) si $f(\mathcal{A}) \subset g(\mathbb{Z})$ pour une fraction rationnelle $g \in \mathcal{Q}(t)$, il existe un polynôme $p \in \mathcal{Q}[t]$ tel que $f = g \circ p$;

(2) si $f(\mathcal{A}) \subset p(\mathcal{Q})$ pour un polynôme $p \in \mathcal{Q}[t]$, il existe une fraction rationnelle $g \in \mathcal{Q}(t)$ telle que $f = p \circ g$.

Ce résultat est une légère généralisation de [2]. Nous donnons la preuve entière par souci de complétude. Si l'on pose $p(t) = t^k$, on déduit de (2) le:

**COROLLAIRE 4.1.** Soit $f \in \mathcal{Q}(t)$ et $A$ un ensemble arithmétiquement dense dans $\mathbb{Z}$; si pour tout $n \in \mathcal{A}$, $f(n)$ est puissance k-ième d'un nombre rationnel, il existe une fraction rationnelle $g \in \mathcal{Q}(t)$ telle que $f = g^k$.

A la base de la preuve est un théorème de Davenport, Lewis et Schinzel [5] que nous formulons comme lemme:

LEMME 4.2. Soit $F(t, t') \in \mathbb{Z}[t, t']$, et $A$ un ensemble arithmétiquement dense dans $\mathbb{Z}$, si pour tout $n \in \mathcal{A}$, il existe $m \in \mathbb{Z}$ tel que l'on ait $F(n, m) = 0$, alors il existe un polynôme $r \in \mathbb{Z}[t]$ tel que identiquement $F(t, r(t)) = 0$.

Pour $F(t, t') = f(t) - t^k$, ce résultat donne le corollaire suivant, déjà mentionné dans l'introduction et dont on peut d'ailleurs donner une preuve élémentaire (cf. [3]):

**COROLLAIRE 4.3.** Soit $f \in \mathbb{Z}[t]$, et $A \subset \mathbb{N}$ arithmétiquement dense; si $f(n)$ est puissance k-ième d'un entier pour tout $n \in \mathcal{A}$, il existe un polynôme $g \in \mathbb{Z}[t]$ tel que $f = g^k$.

Nous utiliserons dans la preuve du théorème II le lemme suivant, dont la première partie est classique et la deuxième est immédiate.

LEMME 4.4. Deux polynômes $a, b \in \mathbb{Z}[t]$ sont sans facteur commun sauf peut-être une constante, si et seulement s'il existe un entier $N$ tel que $(a(n), b(n))$ divise $N$ pour tout $n \in \mathbb{Z}$; de plus, si $n = n'(\text{mod } N)$, alors

$$(a(n), b(n)) = (a(n'), b(n')).$$

Preuve du théorème II. a). La première partie du théorème découle du lemme 4.2 comme suit: Posons $f = a/b$, $g = a'/b'$, avec
a, b, a', b' ∈ Z[t], et soit $F ∈ Z[t, t']$ défini par:

$$F(t, t') = a(t)b'(t') - a'(t')b(t).$$

Par hypothèse, le lemme 4.2 peut être appliqué, et il existe un polynôme $p \in Q[t]$ tel que $F(t, p(t)) = 0$ identiquement; autrement dit, on a $f = g \circ p$.

b). Pour prouver la deuxième partie, posons $f = a/b$, avec $a, b \in Z[t]$ sans facteur commun, le coefficient directeur de $b$ étant positif. Supposons d'abord le polynôme $p$ unitaire et à coefficients entiers:

$$p(t) = t^k + p_1 t^{k-1} + \dots + p_k, \quad p_1, \dots, p_k \in Z.$$

Pour tout $n \in A$, il existe deux entiers $y_n, z_n$ premiers entre eux, avec $z_n > 0$, tels que $f(n) = p(y_n/z_n)$, d'où:

$$\frac{a(n)}{b(n)} = \frac{y_n^k + p_1 y_n^{k-1} z_n + \dots + p_k z_n^k}{z_n^k},$$

et comme cette dernière fraction ne peut être réduite, on a, pour tout $n \in A$:

$$(4.1) \qquad b(n) = \varepsilon_n(a(n), b(n)) z_n^k \quad \text{avec} \quad \varepsilon_n \in \{-1, 1\}.$$

c). Soit maintenant $N$ l'entier dont l'existence est assurée par le lemme 4.4, et posons $\bar{d} = (a(0), b(0))$. Les polynômes $\bar{a}$ et $\bar{b}$ définis par:

$$\bar{a}(t) = \frac{a(tN)}{\bar{d}}, \quad \bar{b}(t) = \frac{b(tN)}{\bar{d}}$$

sont à coefficients entiers par construction; l'ensemble $B = \{n \in Z : nN \in A\}$ est arithmétiquement dense dans $Z$ par 2.1 (ii), et il résulte de (4.1) que:

$$(4.2) \qquad \bar{b}(n) = \varepsilon_{nN}(z_{nN})^k \quad \text{pour tout } n \in B.$$

Le polynôme $b' = \bar{b}^2$ vérifie les hypothèses du corollaire 4.3, et il existe un polynôme $u \in Z[t]$ tel que $b' = u^{2k}$. On peut supposer le coefficient directeur de $u$ positif comme l'est celui de $\bar{b}$; on en tire $\bar{b} = u^k$.

d). Soit maintenant $B' = \{n \in B : |n| \ge N_0\}$, où $N_0$ est assez grand pour que $|n| \ge N_0$ implique $u(n) > 0$ si le degré $l$ de $u$ est pair, $nu(n) > 0$ si $l$ est impair. L'ensemble $B'$ est arithmétiquement dense dans $Z$ par 2.1 (iii). De (4.2), on déduit que pour tout $n \in B'$, on a $u(n) = z_{nN}$ si $k$ ou $l$ est pair, et $u(n) = -z_{nN}$ si $k$ et $l$ sont impairs; donc l'équation

$$\frac{\bar{a}(n)}{\bar{b}(n)} = p\left(\frac{m}{u(n)}\right)$$

a, pour tout $n \in B'$, la solution $m = y_{nN}$ dans le premier cas et $m = -y_{nN}$ dans le deuxième cas. On peut donc appliquer le lemme 4.2 au polynôme

$$F(t, t') = \bar{a}(t) - (t'^k + p_1 t'^{k-1} u(t) + \dots + p_k u(t))^k,$$

d'où l'on tire l'existence d'un polynôme $v \in Z[t]$ tel que $\bar{a}/\bar{b} = p \circ (v/u)$, d'où finalement $f = p \circ g$ avec $g(t) = \frac{v(t/N)}{u(t/N)}$.

e). Supposons maintenant que le polynôme $p$ soit à coefficients entiers:

$$p(t) = p_0 t^k + p_1 t^{k-1} + \dots + p_k$$

et soit $p' \in Z[t]$ le polynôme unitaire:

$$p'(t) = t^k + \sum_{i=1}^{k} p_i t^{k-i}$$

où $p_i' = p_0^{i-1} p_i$ pour $i = 1, \dots, k$. Clairement, on a $p'(p_0 t) = p_0^{k-1} p(t)$, et si par conséquent $f(A) \subset p(Q)$, on a $f'(A) \subset p'(Q)$, avec $f' = p_0^{k-1} f$. En vertu de ce qui précède, il existe une fraction rationnelle $g' \in Q(t)$ telle que $f' = p' \circ g'$, d'où l'on déduit que $p_0 f' = p_0^k f = (p_0 p') \circ g'$, et comme $p_0 p'(t) = p(t/p_0)$, également $f = p \circ g$, avec $g = g'/p_0$.

Soit enfin $p \in Q[t]$ quelconque, et $m$ le pgcd des dénominateurs des coefficients de $p$. Le polynôme $mp$ est donc à coefficients entiers, et comme $f(A) \subset p(Q)$ implique que $mf(A) \subset mp(Q)$, il existe d'après ce qui précède une fraction rationnelle $g \in Q(t)$ telle que l'on ait $mf = mp \circ g$, d'où l'on tire que $f = p \circ g$. Le théorème est complètement démontré.

**5. Factorisation de suites récurrentes.** Soit $a$ une fonction ad rationnelle à valeurs rationnelles, et $\mathcal{A} = \sum_{n=0}^{\infty} a(n) t^n$ la série rationnelle associée. Nous donnons ici des réponses partielles au problème de factorisation dans les cas $a(N) \subset p(Z)$, où $p$ est un polynôme, et $a(N) \subset b(N)$, où $b$ est une autre fonction ad rationnelle.

La première inclusion se ramène, dans le cas particulier où la série $\mathcal{A}$ n'a que le pôle 1, à l'inclusion des ensembles de valeurs prises par deux polynômes. De même, le deuxième problème se ramène au premier si la série $\mathcal{B} = \sum_{n=0}^{\infty} b(n) t^n$ n'a que le pôle 1. Nous examinons le cas particulier du premier problème où $\mathcal{A}$ possède un pôle unique et simple sur son cercle de convergence. Nous n'avons pu déterminer les conséquences de la deuxième relation d'inclusion que dans le cas où la série $\mathcal{B}$ est une série de Pólya, mais pensons que la même conclusion est valable sans cette restriction.

**PROPOSITION 5.1.** *Soient*

$$\mathcal{A} = \sum_{n=0}^{\infty} a(n) t^n \quad \text{et} \quad \mathcal{B} = \sum_{n=0}^{\infty} b(n) t^n$$
deux séries rationnelles normalisées à coefficients rationnels, et soit $\mathcal{A}$ un ensemble arithmétiquement dense dans $\mathcal{N}$; si $a(\mathcal{A}) \subset b(\mathcal{N})$ et si $\mathcal{B}$ est une série de Pólya, alors $\mathcal{A}$ est une série de Pólya, et de plus, il existe un entier $M \ge 1$, et des entiers $r_m, M_m \ge 0$ pour $m = 0, \dots, M-1$, tels que l'on ait:

$$a(m+nM) = b(r_m+nM_m) \quad \text{pour tout } n \in \mathcal{N}.$$

Preuve. La condition $a(\mathcal{A}) \subset b(\mathcal{N})$ exprime le fait que la suite $(a(n))_{n \in \mathcal{N}}$ est une suite de Pólya généralisée. En vertu du théorème I, la série $\mathcal{A}$ est une série de Pólya. Il suffit donc de prouver la deuxième assertion pour une série $\mathcal{A}$ telle que $a(n)$ soit de la forme $a(n) = ac^n$ pour tout $n \in \mathcal{N}$, avec $a, c \in \mathcal{Q}$, et on peut supposer que $c \notin \{0, 1, -1\}$. Posons alors

$$\mathcal{B} = \sum_{m=0}^{M-1} \frac{b(m)t^m}{1 - d_m t^M},$$

et pour tout $k = 0, \dots, M-1$, soit

$$A_k = \{n \in \mathcal{N}, \exists s \in \mathcal{N}: a(n) = b(k)d_k^s\}.$$

Nous allons prouver que si $A_k \ne \emptyset$, alors $A_k$ est de la forme $A_k = r_k + M_k \mathcal{N}$, avec $r_k, M_k \in \mathcal{N}$. Pour cela, soit $r_k$ le plus petit élément de $A_k$ supposé non vide. L'ensemble

$$I_k = \{n \in \mathcal{Z}, \exists s \in \mathcal{Z}: c^n = d_k^s\}$$

est un idéal, donc de la forme $I_k = M_k \mathcal{Z}$, et $n \in I_k \cap \mathcal{N}$ si $r_k + n \in A_k$. L'ensemble $A_k$ est donc bien de la forme annoncée. Il en découle que $B = \bigcup \{A_k: k = 0, \dots, M-1\}$ est, à un nombre fini d'éléments près, une union de progressions arithmétiques de même raison $M$, et comme l'ensemble $\mathcal{A}$ est arithmétiquement dense, on a $B = \mathcal{N} \setminus S$ où $S$ est un ensemble fini. Puisque $\mathcal{B}$ est une série rationnelle normalisée, on a $S = \emptyset$ et la proposition est établie.

**THÉORÈME III.** Soit $\mathcal{A} = \sum_{n=0}^{\infty} a(n)t^n$ une série rationnelle à coefficients entiers ayant un pôle unique simple sur son cercle de convergence, et p un polynôme à coefficients complexes; si $a(\mathcal{N}) \subset p(\mathcal{Z})$, il existe une série rationnelle $\mathcal{B} = \sum_{n=0}^{\infty} b(n)t^n$ à coefficients entiers telle que l'on ait $a = p \circ b$.

Nous ne savons pas remplacer l'inclusion $a(\mathcal{N}) \subset p(\mathcal{Z})$ par $a(\mathcal{A}) \subset p(\mathcal{Z})$, où $\mathcal{A}$ est un ensemble arithmétiquement dense.

Pour $p(t) = t^k$, on obtient le résultat suivant dû à Ch. Pisot (cf. [1]):

**COROLLAIRE 5.2.** Soit $\mathcal{A}$ comme dans l'énoncé précédent; si $a(n)$ est puissance k-ième d'un entier pour tout $n \in \mathcal{N}$, il existe une série rationnelle $\mathcal{B} = \sum_{n=0}^{\infty} b(n)t^n$ à coefficients entiers telle que $a = b^k$.

Soit $d$ le degré du polynôme $p$. Si $d$ est impair, l'équation $a(n) = p(y)$ a au plus une solution si $u(n)$ est assez grand. Si par contre, $d$ est pair, cette équation peut avoir une ou deux solutions. Le caractère rationnel de la série $\sum b(n)t^n$ dépend bien entendu de la solution $b(n) = y$ retenue. En fait, le lemme suivant dit essentiellement que si $d$ est pair, l'équation $a(n) = p(y)$ a soit toujours une, soit toujours deux solutions, et donc qu'un choix convenable de $b(n)$ est possible.

**LEMME 5.3.** Soit $p \in C[t]$ un polynôme; si l'ensemble

$$K = \{x \in \mathcal{N}, \exists y \in -\mathcal{N}: p(x) = p(y)\}$$

est infini, il existe $s \in \mathcal{Q}$ tel que

$$p(s+t) = p(-s-t).$$

Preuve. Posons $p(t) = p_0 t^d + p_1 t^{d-1} + \dots + p_d$, avec $d$ pair. Pour tout $x \in K$ assez grand, il existe un entier $y = y(x) \in -\mathcal{N}$ unique tel que $p(x) = p(y(x))$; posons :

$$y(x) = -x - \zeta(x) = -x(1 + \varepsilon(x)).$$

Comme $(\frac{y(x)}{x})^d \to \frac{p(y(x))}{p(x)} = 1$, lorsque $x \to \infty$ dans $K$, on a $\varepsilon(x) \to 0$ lorsque $x \to \infty$ dans $K$.

Pour tout $x \in K$, l'équation $p(x) = p(-x(1+\varepsilon(x)))$ donne :

$$p_0(1+\varepsilon(x))^d = p_0 + \frac{p_k}{\omega^k} (1-(-1)^k (1+\varepsilon(x))^{d-k}) + O(\omega^{-1-k}),$$

où $k$ est le plus petit entier tel que $p_k \ne 0$ (et $k = d+1$ si $p_1 = \dots = p_d = 0$). En développant, on obtient $\varepsilon(x) = O(x^{-1})$, d'où $\zeta(x) = O(1)$.

Comme $\zeta(x)$ est entier pour tout $x \in K$, il existe un entier $z \in \mathcal{Z}$, et un sous-ensemble infini $L$ de $K$ tel que l'on ait $\zeta(x) = z$ pour tout $x \in L$, donc $p(-x-z) = p(x)$ pour tout $x \in L$, donc pour tout $x \in \mathcal{Z}$. Posant $s = -z/2$, on en déduit l'assertion.

Preuve du théorème III. Par le lemme, l'équation $a(n) = p(y)$ possède, pour $n$ assez grand, ou bien une solution $b(n) = y$, ou bien deux solutions $b(n) > 0$ et $y'_n$ liées par la relation $b(n) + y'_n = h$, où $h$ est un entier fixe.
Par hypothèse, $a(n)$ est, pour $n$ assez grand, de la forme

$$a(n) = b_0 a^n + \sum_{i=1}^{r} P_i(n) a_i^n,$$

où $a$ est réel, $|a| > |a_i|$ et $P_i \in \mathbb{C}[t]$ pour $i = 1, \dots, r$. Posant

$$\gamma_n = \frac{1}{b_0 a^n} \left( \sum_{i=1}^{r} P_i(n) a_i^n \right),$$

il existe des nombres $C > 0$, et $0 < \rho < 1$ tels que $|\gamma_n| \le C\rho^n$ pour $n$ assez grand.

Considérons alors le développement de Puiseux de $x = p(y)$:

$$y = u_0 x^{1/d} + u_1 + x^{-1/d} O(1),$$

et posons d'autre part:

$$a(n)^{1/d} = (b_0 a^n (1 + \gamma_n))^{1/d} = (b_0 a^n)^{1/d} \left(1 + \sum_{j=1}^{l-1} d_j \gamma_n^j + \gamma_n^l O(1)\right),$$

où $l$ est choisi suffisamment grand pour que $|\alpha^{1/d} \rho^l| < 1$. D'où:

$$b(n) = u_0 b_0^{1/d} a^{n/d} \left(1 + \sum_{j=1}^{l-1} d_j \gamma_n^j\right) + u_1 + u_0 b_0^{1/d} a^{n/d} \gamma_n^l O(1) + \alpha^{-n/d} O(1),$$

ce qui montre qu'en posant:

$$w(n) = u_0 b_0^{1/d} a^{n/d} \left(1 + \sum_{j=1}^{l-1} d_j \gamma_n^j\right) + u_1,$$

$b(n)$ s'écrit sous la forme $b(n) = w(n) + \varepsilon(n)$, où $\sum_{n=0}^{\infty} w(n) t^n$ est une série rationnelle, et où la série $\sum_{n=0}^{\infty} \varepsilon(n) t^n$ a un rayon de convergence $> 1$. Par le théorème de Pólya-Carlson [7], la série $\sum_{n=0}^{\infty} b(n) t^n$ est rationnelle et le théorème est établi.

Je remercie J. F. Perrot pour les discussions que j'ai pu avoir avec lui pendant la rédaction de cet article.

Références

[1] B. Benzaghou, *Algèbres de Hadamarà*, Bull. Soc. Math. France 98 (1970), p. 209-252.

[2] J. Berstel, *Sur des fractions rationnelles particulières*, C. R. Acad. Sc. Paris 270 (1970), p. 304-306.

[3] — *Contribution à l'étude des propriétés arithmétiques des langages formels*, Thèse, Paris 1972.

[4] R. D. Carmichael, *On sequences of integers defined by recurrence relations*, Quart. J. Math. 48 (1920), p. 343-372.

[5] H. Davenport, D. J. Lewis and A. Schinzel, *Polynomials of certain special types*, Acta Arith. 9 (1964), p. 107-116.

[6] G. Pólya, *Arithmetische Eigenschaften der Reihenentwicklung rationaler Funktionen*, J. Reine Angew. Math. 151 (1921), p. 1-31.

[7] — *Über gewisse notwendige Determinantenkriterien für die Fortsetzbarkeit einer Potenzreihe*, Math. Ann. 99 (1928), p. 687-706.

[8] G. Pólya und G. Szegő, *Aufgaben und Lehrsätze aus der Analysis*, Springer, 3. ed., 1964.

[9] G. Rauzy, *Suites partiellement récurrentes*, Ann. Inst. Fourier 16 (1966), fasc. 1, p. 159-234.

[10] — *Ensembles arithmétiquement denses*, C. R. Acad. Sc. Paris 265 (1967), p. 37-38.

UNIVERSITÉ PIERRE ET MARIE CURIE

Paris, France

Reçu le 7. 3. 1974

et dans la forme modifiée le 2. 12. 1974

(543)

<figure><img src="image_1.png" /></figure>