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

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

n=\sum _{k=1}^{N}{a_{k}k^{2}}\quad {\rm {avec}}\quad a_{k}\in \{1,-1\}.

Démonstration[modifier | modifier le code]

On vérifie aisément que m² – (m + 1)² – (m + 2)² + (m + 3)² 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 = 1², 2 ≡ ±(1² ± 2² + 3²) (mod 4) et 3 ≡ –1² (mod 4).

On obtient ainsi un début de décomposition de n, de la forme $n=\sum _{k=1}^{N}{a_{k}k^{2}}+4q$ (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 ±[m² – (m + 1)² – (m + 2)² + (m + 3)²], 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 : ${\begin{aligned}9&=1^{2}+4\times 2\\&=1^{2}+(2^{2}-3^{2}-4^{2}+5^{2})+(6^{2}-7^{2}-8^{2}+9^{2})\\&=1^{2}+(2^{2}-3^{2}-4^{2}+5^{2})+(6^{2}-7^{2}-8^{2}+9^{2})+(10^{2}-11^{2}-12^{2}+13^{2})-(14^{2}-15^{2}-16^{2}+17^{2})\\&=\ldots \end{aligned}}$

mais on a aussi :

$9=1^{2}+2^{2}+3^{2}-4^{2}-5^{2}+6^{2},$

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

Généralisations[modifier | modifier le code]

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 :

n=\sum _{k=1}^{N}{a_{k}k^{p}}\quad {\rm {avec}}\quad a_{k}\in \{1,-1\}.

Exemples :

$3=1^{3}-2^{3}+3^{3}+4^{3}+5^{3}+6^{3}-7^{3}+8^{3}-9^{3}+10^{3}-11^{3}-12^{3}+13^{3},$ $2=-1^{4}+2^{4}+3^{4}-4^{4}+5^{4}+6^{4}-7^{4}+8^{4}+9^{4}-10^{4}-11^{4}+12^{4}+13^{4}+14^{4}+15^{4}-16^{4}-17^{4}-18^{4}+19^{4}.$

De manière apparemment indépendante^[3], Bodini et al.^[4] et Yu^[5] ont étendu ce résultat en remplaçant k^p 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[modifier | modifier le code]

↑ (en) Paul Erdős et János Surányi, Topics in the Theory of Numbers, Springer Science & Business Media, 2003 (lire en ligne), chap. 7, p. 227-228, ex. 15.
↑ ^{a et b} (en) Michael N. Bleicher, « On Prielipp's Problem on Signed Sums of kth Powers », Journal of Number Theory, vol. 56, n^o 1,‎ 1996, p. 36-51 (DOI 10.1006/jnth.1996.0004).
↑ ^{a et b} (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,‎ 2004, p. 5071-5088 (lire en ligne).
↑ 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.
↑ (en) Hong Bing Yu, « Signed sums of polynomial values », Proc. Amer. Math. Soc., vol. 130,‎ 2002, p. 1623-1627 (lire en ligne).