Shortlist 2019, A7¶
Domaine : Algèbre · Difficulté : ★★★★★ · Proposé par : Netherlands
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Valuations p-adiques et lemme LTE · Principe extrémal
Solution officielle : Shortlist officielle 2019 (avec solutions), section A7 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(\mathbb{Z}\) be the set of integers. We consider functions \(f : \mathbb{Z} \to \mathbb{Z}\) satisfying
for all integers \(x\) and \(y\). For such a function, we say that an integer \(v\) is \(f\)-rare if the set
is finite and nonempty.
(a) Prove that there exists such a function \(f\) for which there is an \(f\)-rare integer.
(b) Prove that no such function \(f\) can have more than one \(f\)-rare integer.
Indices : les idées clés
- Équations fonctionnelles : substitutions : itérer l'équation (\(x \mapsto x + ky\)) puis choisir \(y = a - f(x)\) pour que \(f(\ldots) + y\) tombe dans \(X_v\).
- Valuations p-adiques (partie (a), solution 1) : \(f(x) = 2^{v_2(x)+1}\), la plus grande puissance de \(2\) divisant \(2x\), avec \(f(0) = 0\).
- Principe extrémal (solution 1) : avec \(a = \min X_v\) et \(b = \max X_v\), \(f\) atteint son minimum et son maximum en \(x\) sur des progressions arithmétiques, donc est constante sur une progression.
- Points fixes (solution 2) : un entier \(f\)-rare vérifie \(f(v) = v\) ; après translation on suppose \(v = 0\) et on montre \(f(kv') = v'\) pour tout \(k \geq 1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions, la seconde pour la partie (b) seulement, et trois remarques).
Solution 1¶
(a) Soit \(f\) définie par \(f(0) = 0\) et, pour \(x \neq 0\), \(f(x)\) = la plus grande puissance de \(2\) divisant \(2x\) (autrement dit \(f(x) = 2^{v_2(x)+1}\), valuation \(2\)-adique). L'entier \(0\) est évidemment \(f\)-rare (\(X_0 = \{0\}\)) ; il reste à vérifier l'équation fonctionnelle.
Comme \(f(2x) = 2f(x)\) pour tout \(x\), l'équation pour \((2x, 2y)\) se déduit de celle pour \((x,y)\) ; il suffit donc de la vérifier quand \(x\) ou \(y\) est impair (le cas \(x = y = 0\) étant trivial). Si \(y\) est impair, alors
car toutes les valeurs de \(f\) sont paires, donc \(f(x+y) + y\) et \(f(x) + y\) sont impairs. Si \(x\) est impair et \(y\) pair, alors déjà \(f(x+y) = 2 = f(x)\), et l'équation en découle immédiatement.
(b) Une récurrence facile (en remplaçant \(x\) par \(x + ky\)) donne
pour tous entiers \(x\), \(y\), \(k\). Soit \(v\) un entier \(f\)-rare et \(a\) le plus petit élément de \(X_v\). En prenant \(y = a - f(x)\) dans \((*)\), le membre de droite vaut \(f(a) = v\), donc
pour tous \(x\), \(k\) ; en particulier, par minimalité de \(a\),
pour tous entiers \(x\) et \(k\). Autrement dit, sur la progression arithmétique (éventuellement dégénérée) passant par \(x\) de raison \(a - f(x)\), \(f\) atteint son minimum en \(x\).
Le même argument avec le plus grand élément \(b\) de \(X_v\) donne
pour tous \(x\), \(k\). En combinant (la progression de raison \((a - f(x))(b - f(x))\) est contenue dans les deux précédentes),
pour tous entiers \(x\) et \(k\).
Ainsi, si \(f(x) \neq a\) et \(f(x) \neq b\), l'ensemble \(X_{f(x)}\) contient une progression arithmétique non dégénérée, donc est infini. Les seuls entiers \(f\)-rares possibles sont donc \(a\) et \(b\).
En particulier, l'entier \(f\)-rare \(v\) de départ est égal à \(a\) ou à \(b\), d'où \(f(v) = f(a) = f(b) = v\). Il ne peut pas exister d'autre entier \(f\)-rare \(v'\) : d'une part il devrait être égal à \(a\) ou à \(b\), donc appartenir à \(X_v\) et vérifier \(f(v') = v\) ; d'autre part (même raisonnement appliqué à \(v'\)) il devrait vérifier \(f(v') = v'\). Donc \(v' = v\) : \(v\) est l'unique entier \(f\)-rare. \(\blacksquare\)
Solution 2 (partie (b) seulement)¶
Soit \(v\) un entier \(f\)-rare, et \(a\), \(b\) le plus petit et le plus grand élément de \(X_v\). La substitution \(x = v\), \(y = a - v\) donne \(f\big(f(v) - v + a\big) = f(a) = v\), c'est-à-dire
et en particulier \(f(v) \geq v\). Le même argument avec \(x = v\), \(y = b - v\) donne \(f(v) \leq v\), donc \(f(v) = v\).
Supposons maintenant que \(v'\) soit un second entier \(f\)-rare. On peut supposer \(v = 0\) (voir la remarque 1). On a vu que \(f(v') = v'\) ; montrons que \(f(kv') = v'\) pour tout entier \(k \geq 1\). Cela donne une contradiction sauf si \(v' = v = 0\) (sinon \(X_{v'}\) serait infini).
Preuve par récurrence sur \(k\). Si c'est vrai pour \(k\), on substitue \(x = 0\) et \(y = kv'\) dans l'équation ; le membre de gauche vaut \(f\big(f(kv') + kv'\big) = f\big((k+1)v'\big)\), d'où
en utilisant \(f(0) = 0\). Ceci achève la récurrence et la preuve. \(\blacksquare\)
Remarques¶
Remarque 1. Si \(f\) est solution, toute conjuguée de \(f\) par une translation, \(x \mapsto f(x+n) - n\) (\(n \in \mathbb Z\)), est encore solution. Pour la partie (b), on peut donc se limiter aux fonctions pour lesquelles \(0\) est \(f\)-rare.
Remarque 2. Il existe beaucoup de solutions possédant un entier \(f\)-rare. On généralise la construction de (a) : on prend une suite \(1 = a_0, a_1, a_2, \ldots\) d'entiers positifs, chaque \(a_i\) diviseur strict de \(a_{i+1}\), et des fonctions arbitraires \(f_i\) des classes non nulles modulo \(a_i\) vers les multiples non nuls de \(a_i\). On pose \(f(0) = 0\) et \(f(x) = f_{i+1}(x \bmod a_{i+1})\) si \(a_i \mid x\) mais \(a_{i+1} \nmid x\). En notant \(v(x)\) le plus grand \(i\) tel que \(a_i \mid x\) (\(v(0) = \infty\)), on vérifie l'équation séparément dans les cas \(v(y) > v(x)\) et \(v(x) \geq v(y)\) ; \(0\) est alors \(f\)-rare.
Remarque 3. En fait, si \(v\) est \(f\)-rare, alors \(X_v = \{v\}\). Supposons \(v = 0\). On a vu (solution 1) que \(0\) est le plus petit ou le plus grand élément de \(X_0\) ; quitte à remplacer \(f\) par \(x \mapsto -f(-x)\), c'est le plus petit. Soit \(b\) le plus grand élément de \(X_0\) ; supposons par l'absurde \(b > 0\) et posons \(N = (2b)!\). D'après \((*)\),
donc \(f(Nb) + b \in X_0 \subseteq [0, b]\). Comme \(Nb \notin X_0\), on a \(f(Nb) \in [-b, 0)\). Alors \(\big(f(Nb) - 0\big)\big(f(Nb) - b\big)\) divise \(N\) (produit de deux entiers distincts de valeurs absolues au plus \(2b\)), et \((\dagger)\) appliquée en \(x = Nb\) donne \(f(Nb) = f(0) = 0\) : contradiction.