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

Tout entier n s'écrit sous la forme :

$n = \sum_{k=1}^{N}{a_kk^2}$ où $a_k \in \{1,-1\}$.

Les décompositions des premiers entiers sont :

0 = 0²

1 = 1²

2 = − 1² − 2² − 3² + 4²

3 = − 1² + 2² − 3² − 4² + 5²

Démonstration

On démontre aisément que m² − (m + 1)² − (m + 2)² + (m + 3)² est indépendant de m et vaut 4. Il suffit alors de faire la division euclidienne de n par 4. On peut alors écrire n sous la forme 4q + r avec $0\leqslant r<4$. Les valeurs prises par r sont 0, 1, 2 et 3 respectivement, et leurs décompositions ont été données en début de l'article. On ajoute à la décomposition de r, q fois une décomposition du type m² − (m + 1)² − (m + 2)² + (m + 3)².

Exemple : pour n = 9, q = 2 et r = 1
$9 = 1 + 2 \times 4 = 1^2 + (2^2 - 3^2 - 4^2 + 5^2) + (6^2 - 7^2 - 8^2 + 9^2)$

mais on a aussi :

9 = + 1² + 2² + 3² − 4² − 5² + 6² ce qui montre que cette décomposition n'est pas optimale d'un point de vue longueur.

Le théorème d'Erdös-Suranyi-Bodini

Olivier Bodini a eu l'idée de remplacer l'exposant 2 par n'importe quel exposant p positif. Ça marche encore ! Ainsi tout entier n peut s'écrire sous la forme :

$n = \sum_{k=1}^{N}{a_kk^p}$ où $a_k \in \{1,-1\}$.

Exemples :

3 = + 1³ − 2³ + 3³ + 4³ + 5³ + 6³ − 7³ + 8³ − 9³ + 10³ − 11³ − 12³ + 13³

2 = − 1⁴ + 2⁴ + 3⁴ − 4⁴ + 5⁴ + 6⁴ − 7⁴ + 8⁴ + 9⁴ − 10⁴ − 11⁴ + 12⁴ + 13⁴ + 14⁴ + 15⁴ − 16⁴ − 17⁴ − 18⁴ + 19⁴

Liens et documents externes

"Autour d'un théorème d'Erdös sur les combinaisons à coefficients + ou -1 des premiers carrés", Revue de l'enseignement supérieur (sept 2001) p. 3-8. O. Bodini, P. Duchet, S. Lefranc.

• Algorithmes et appliquettes JAVA associés au théorème