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

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 ${\displaystyle 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 : ${\displaystyle {\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 :

${\displaystyle 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.

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 :

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

Exemples :

${\displaystyle 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},}$ ${\displaystyle 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).