Shortlist 2009, N5¶

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Hungary

Concepts : Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Double comptage

Solution officielle : Shortlist officielle 2009 (avec solutions), p. 76 (page 78 du PDF)

Énoncé¶

Let \(P(x)\) be a non-constant polynomial with integer coefficients. Prove that there is no function \(T\) from the set of integers into the set of integers such that the number of integers \(x\) with \(T^n(x) = x\) is equal to \(P(n)\) for every \(n \geq 1\), where \(T^n\) denotes the \(n\)-fold application of \(T\).

Indices : les idées clés

Points de période exacte : avec \(A(n) = \{x : T^n(x) = x\}\) et \(B(n)\) les points de plus petite période \(n\), on a \(\lvert A(n) \rvert = \sum_{d \mid n}\lvert B(d) \rvert\) (décomposition) et \(n \mid \lvert B(n) \rvert\), car \(T\) permute \(B(n)\) en cycles de longueur \(n\).
Solution 2, congruences : \(P(0) \equiv P(pq) \equiv \lvert B(1) \rvert + \lvert B(p) \rvert \pmod q\) pour tout grand premier \(q\), donc \(P(p) = P(0)\) pour tout premier \(p\).
Polynôme constant : un polynôme non constant ne peut pas prendre la même valeur en une infinité de points.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions et une remarque).

Solution 1¶

Supposons qu'il existe un polynôme \(P\) de degré au moins \(1\) ayant la propriété voulue pour une fonction \(T\) donnée. Notons \(A(n)\) l'ensemble des \(x \in \mathbb{Z}\) tels que \(T^n(x) = x\), et \(B(n)\) l'ensemble des \(x \in \mathbb{Z}\) tels que \(T^n(x) = x\) et \(T^k(x) \neq x\) pour tout \(1 \leq k < n\). Ces deux ensembles sont finis sous l'hypothèse faite. Pour tout \(x \in A(n)\), il existe un plus petit \(k \geq 1\) tel que \(T^k(x) = x\), c'est-à-dire \(x \in B(k)\). Posons \(d = \gcd(k, n)\). Il existe des entiers \(r, s > 0\) tels que \(rk - sn = d\), et donc \(x = T^{rk}(x) = T^{sn+d}(x) = T^d(T^{sn}(x)) = T^d(x)\). La minimalité de \(k\) implique \(d = k\), c'est-à-dire \(k \mid n\). D'autre part, on a évidemment \(B(k) \subset A(n)\) si \(k \mid n\), donc \(A(n) = \bigcup_{d \mid n} B(d)\) est une réunion disjointe, et par conséquent

\[\lvert A(n) \rvert = \sum_{d \mid n}\lvert B(d) \rvert.\]

De plus, pour tout \(x \in B(n)\), les éléments \(x, T^1(x), T^2(x), \ldots, T^{n-1}(x)\) sont \(n\) éléments distincts de \(B(n)\). Qu'ils soient dans \(A(n)\) est évident. Si, pour un certain \(k < n\) et un certain \(0 \leq i < n\), on avait \(T^k(T^i(x)) = T^i(x)\), c'est-à-dire \(T^{k+i}(x) = T^i(x)\), cela impliquerait \(x = T^n(x) = T^{n-i}(T^i(x)) = T^{n-i}(T^{k+i}(x)) = T^k(T^n(x)) = T^k(x)\), ce qui contredit la minimalité de \(n\). Donc \(T^i(x) \in B(n)\) et \(T^i(x) \neq T^j(x)\) pour \(0 \leq i < j \leq n - 1\).

Ainsi, \(T\) permute les éléments de \(B(n)\) en cycles (disjoints) de longueur \(n\), et en particulier \(n \mid \lvert B(n) \rvert\).

Soit maintenant \(P(x) = \sum_{i=0}^{k} a_ix^i\), avec \(a_i \in \mathbb{Z}\), \(k \geq 1\), \(a_k \neq 0\), et supposons \(\lvert A(n) \rvert = P(n)\) pour tout \(n \geq 1\). Soit \(p\) un nombre premier quelconque. Alors

\[p^2 \mid \lvert B(p^2) \rvert = \lvert A(p^2) \rvert - \lvert A(p) \rvert = a_1(p^2 - p) + a_2(p^4 - p^2) + \cdots\]

Donc \(p \mid a_1\), et comme c'est vrai pour tout nombre premier, on doit avoir \(a_1 = 0\).

Considérons maintenant deux nombres premiers distincts quelconques \(p\) et \(q\). Comme \(a_1 = 0\), on a

\[\lvert A(p^2q) \rvert - \lvert A(pq) \rvert = a_2(p^4q^2 - p^2q^2) + a_3(p^6q^3 - p^3q^3) + \cdots,\]

qui est un multiple de \(p^2q\). Mais on a aussi

\[p^2q \mid \lvert B(p^2q) \rvert = \lvert A(p^2q) \rvert - \lvert A(pq) \rvert - \lvert B(p^2) \rvert.\]

Cela implique

\[p^2q \mid \lvert B(p^2) \rvert = \lvert A(p^2) \rvert - \lvert A(p) \rvert = a_2(p^4 - p^2) + a_3(p^6 - p^3) + \cdots + a_k(p^{2k} - p^k).\]

Comme c'est vrai pour tout nombre premier \(q\), on doit avoir \(a_2(p^4 - p^2) + a_3(p^6 - p^3) + \cdots + a_k(p^{2k} - p^k) = 0\) pour tout nombre premier \(p\). Comme cette expression est un polynôme en \(p\) de degré \(2k\) (car \(a_k \neq 0\)), c'est une contradiction, puisqu'un tel polynôme a au plus \(2k\) racines. \(\blacksquare\)

Remarque. On peut aussi atteindre la dernière contradiction par

\[a_k = \lim_{p \to \infty}\frac{1}{p^{2k}}\left(a_2(p^4 - p^2) + a_3(p^6 - p^3) + \cdots + a_k(p^{2k} - p^k)\right) = 0.\]

Solution 2¶

Comme dans la première solution, définissons \(A(n)\) et \(B(n)\), et supposons qu'un polynôme \(P\) ayant la propriété voulue existe. Là encore, \(\lvert A(n) \rvert\) et \(\lvert B(n) \rvert\) sont finis pour tout entier \(n > 0\), et

\[P(n) = \lvert A(n) \rvert = \sum_{d \mid n}\lvert B(d) \rvert \qquad \text{et} \qquad n \mid \lvert B(n) \rvert.\]

Pour deux nombres premiers distincts quelconques \(p\) et \(q\), on a alors

\[P(0) \equiv P(pq) \equiv \lvert B(1) \rvert + \lvert B(p) \rvert + \lvert B(q) \rvert + \lvert B(pq) \rvert \equiv \lvert B(1) \rvert + \lvert B(p) \rvert \pmod q.\]

Ainsi, pour \(p\) fixé, l'expression \(P(0) - \lvert B(1) \rvert - \lvert B(p) \rvert\) est divisible par des nombres premiers \(q\) arbitrairement grands, ce qui signifie que \(P(0) = \lvert B(1) \rvert + \lvert B(p) \rvert = P(p)\) pour tout nombre premier \(p\). Cela implique que le polynôme \(P\) est constant, ce qui est une contradiction. \(\blacksquare\)