Accueil🇫🇷Chercher

Théorème d'Erdős-Suranyi

En théorie des nombres, le théorème d'Erdős-Surányi (hu)[1] - [2] établit que tout entier n s'écrit, d'une infinité de façons, sous la forme :

Démonstration

On vérifie aisément que m2 – (m + 1)2 – (m + 2)2 + (m + 3)2 est indépendant de m et vaut 4. Il suffit alors de trouver pour 0, 1, 2 et 3 des décompositions modulo 4, par exemple :

0 = la somme vide, 1 = 12, 2 ≡ ±(12 ± 22 + 32) (mod 4) et 3 ≡ –12 (mod 4).

On obtient ainsi un début de décomposition de n, de la forme (dont tous les termes — en particulier N — dépendent du reste r de la division euclidienne de n par 4 et du choix d'une décomposition de r modulo 4). Il suffit alors de remplacer 4q = ±4|q| par |q| décompositions consécutives de ±4 du type ±[m2 – (m + 1)2 – (m + 2)2 + (m + 3)2], partant de m = N + 1. À partir d'une décomposition de n, on peut toujours en construire une plus longue, en ajoutant de même deux décompositions consécutives de 4 et –4.

Exemple : pour n = 9, congru à 1 modulo 4, on trouve ainsi :

mais on a aussi :

ce qui montre que l'algorithme n'est pas optimal d'un point de vue longueur.

Généralisations

Bleicher[2] a remplacé l'exposant 2 par n'importe quel exposant p positif : tout entier n peut s'écrire d'une infinité de façons sous la forme :

Exemples :

De manière apparemment indépendante[3], Bodini et al.[4] et Yu[5] ont étendu ce résultat en remplaçant kp par f(k), où f est n'importe quel polynôme à valeurs entières dont le PGCD des valeurs est égal à 1.

Boulanger et Chabert[3] l'ont encore étendu, en remplaçant de plus l'anneau des entiers relatifs par celui des entiers d'un corps cyclotomique (et ±1 par les racines de l'unité dans ce corps).

Notes et références

  1. (en) Paul Erdős et János Surányi, Topics in the Theory of Numbers, Springer Science & Business Media, (lire en ligne), chap. 7, p. 227-228, ex. 15.
  2. (en) Michael N. Bleicher, « On Prielipp's Problem on Signed Sums ofkth Powers », Journal of Number Theory, vol. 56, no 1, , p. 36-51 (DOI 10.1006/jnth.1996.0004).
  3. (en) Jacques Boulanger et Jean-Luc Chabert, « On the representation of integers as linear combinations of consecutive values of a polynomial », Trans. Amer. Math. Soc., vol. 356, , p. 5071-5088 (lire en ligne).
  4. Olivier Bodini, Pierre Duchet et Sandrine Lefranc, « Autour d'un théorème d'Erdős sur les combinaisons à coefficients + ou -1 des premiers carrés », RMS, vol. 112, 2001, p. 3-8.
  5. (en) Hong Bing Yu, « Signed sums of polynomial values », Proc. Amer. Math. Soc., vol. 130, , p. 1623-1627 (lire en ligne).

Voir aussi

Articles connexes

Lien externe

Jean-Paul Quelen, Algorithmes et appliquettes JAVA associés au théorème

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.