Satz von Erdös-Suranyi

Der Satz von Erdős-Suranyi ist ein mathematischer Satz der Zahlentheorie mit folgender Aussage:

Jede ganze Zahl ${\displaystyle n}$ kann auf unendlich viele Arten in der folgenden Form geschrieben werden:

${\displaystyle n=\sum _{k=1}^{N}{a_{k}k^{2}}\quad {\rm {mit}}\quad a_{k}\in \{1,-1\}}$

Der Name stammt von den beiden ungarischen Mathematikern Paul Erdős und János Surányi.^[1][2]

• Sei ${\displaystyle n=2}$. Dann gilt:

${\displaystyle 2=1^{2}-2^{2}+3^{2}-4^{2}+5^{2}+6^{2}-7^{2}}$

• Sei ${\displaystyle n=9}$. Dann gilt:

${\displaystyle {\begin{array}{rcl}9&=&1^{2}+2^{2}+3^{2}-4^{2}-5^{2}+6^{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{array}}}$

In diesem Abschnitt wird ein Algorithmus vorgestellt, wie man unendlich viele solche Darstellungen für eine ganze Zahl ${\displaystyle n}$ erhält.

Es gilt:

${\displaystyle {\begin{array}{rcl}m^{2}-(m+1)^{2}-(m+2)^{2}+(m+3)^{2}&=&m^{2}-(m^{2}+2m+1)-(m^{2}+4m+4)+(m^{2}+6m+9)\\&=&m^{2}-m^{2}-2m-1-m^{2}-4m-4+m^{2}+6m+9\\&=&-1-4+9\\&=&4\end{array}}}$

Dieser Term ist also unabhängig von ${\displaystyle m}$ und hat immer den Wert ${\displaystyle 4}$.

Somit hat man unendlich viele Möglichkeiten, ${\displaystyle n=4}$ in der gewünschten Form darzustellen, zum Beispiel:

${\displaystyle {\begin{array}{rcl}4&=&1^{2}-2^{2}-3^{2}+4^{2}\\&=&4+4-4\\&=&(1^{2}-2^{2}-3^{2}+4^{2})+(5^{2}-6^{2}-7^{2}+8^{2})-(9^{2}-10^{2}-11^{2}+12^{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}\\&=&4+4-4-4+4\\&=&\ldots \\\end{array}}}$

Auch für alle Vielfachen von ${\displaystyle 4}$ erhält man so unendlich viele Darstellungsmöglichkeiten, zum Beispiel für ${\displaystyle n=12}$:

${\displaystyle {\begin{array}{rcl}12&=&3\cdot 4\\&=&4+4+4\\&=&(1^{2}-2^{2}-3^{2}+4^{2})+(5^{2}-6^{2}-7^{2}+8^{2})+(9^{2}-10^{2}-11^{2}+12^{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}\\&=&4+4+4-4+4\\&=&\ldots \end{array}}}$

Etwas problematischer wird es, wenn man ${\displaystyle n}$ betrachtet, die keine Vielfachen von ${\displaystyle 4}$ sind und von der man eine obige Darstellung haben will. Teilt man diese Zahl durch ${\displaystyle 4}$, so ergibt sich einer von vier Resten, nämlich ${\displaystyle 0,1,2}$ oder ${\displaystyle 3}$. Für diese vier möglichen Reste betrachte man die Modulo-4-Zerlegungen:

${\displaystyle {\begin{array}{rcl}0&=&{\rm {leere}}\;{\rm {Summe}}\\1&=&1^{2}\\2&\equiv &\pm (1^{2}\pm 2^{2}+3^{2}){\pmod {4}}\\3&=&-1^{2}+4\equiv -1^{2}{\pmod {4}}\end{array}}}$

Für jedes ${\displaystyle n}$ kann man die Zerlegung wie folgt beginnen:

${\displaystyle n=\sum _{k=1}^{N}{a_{k}k^{2}}+4q}$

Alle Terme ${\displaystyle N,k}$ und ${\displaystyle q}$ hängen erstens vom Rest ${\displaystyle r}$ ab, der entsteht, wenn man diese Zahl ${\displaystyle n}$ durch ${\displaystyle 4}$ dividiert (siehe Division mit Rest) und zweitens von der Wahl einer Zerlegung von ${\displaystyle r}$ modulo ${\displaystyle 4}$. Dann ersetzt man ${\displaystyle 4q=\pm 4|q|}$ (dabei ist mit ${\displaystyle |q|}$ der Betrag der Zahl ${\displaystyle q}$ gemeint) durch ${\displaystyle |q|}$ aufeinanderfolgende Zerlegungen von ${\displaystyle \pm 4=\pm (m^{2}-(m+1)^{2}-(m+2)^{2}+(m+3)^{2})}$, beginnend mit ${\displaystyle m=N+1}$. Aus einer Zerlegung von ${\displaystyle n}$ kann man eine immer längere konstruieren, indem man auf ähnliche Weise zwei aufeinanderfolgende Zerlegungen von ${\displaystyle 4}$ und ${\displaystyle -4}$ hinzufügt.

• Sei ${\displaystyle n=9}$. Dividiert man ${\displaystyle n=9}$ durch ${\displaystyle 4}$, so erhält man den Rest ${\displaystyle r=1}$. Es ist also ${\displaystyle 9=1+4\cdot 2}$, somit ist ${\displaystyle 9\equiv 1{\pmod {4}}}$ und folglich ist ${\displaystyle r=1}$ und ${\displaystyle q=2}$. Es gilt:

${\displaystyle {\begin{array}{rcl}9&=&1+4\cdot 2\\&=&1^{2}+4+4\\&=&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}\\&=&1^{2}+4+4+4-4\\&=&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{array}}}$

Leider führt dieser Algorithmus nicht unbedingt zur kürzest möglichen Darstellung der Zahl ${\displaystyle n}$, wie schon im obigen Beispiel gezeigt wurde:

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

Es ist also dieser Algorithmus, wenn man seine Länge betrachtet, nicht optimal.

• Sei ${\displaystyle n=14}$. Es ist ${\displaystyle 14=2+4\cdot 3}$ und somit ${\displaystyle 14\equiv 2{\pmod {4}}}$. Also ist ${\displaystyle r=2}$ und ${\displaystyle q=3}$. Es gilt:

${\displaystyle {\begin{array}{rcl}14&=&2+4\cdot 3\\&=&6+4\cdot 2\\&=&(1^{2}-2^{2}+3^{2})+4+4\\&=&1^{2}-2^{2}+3^{2}+(4^{2}-5^{2}-6^{2}+7^{2})+(8^{2}-9^{2}-10^{2}+11^{2})\\&=&1^{2}-2^{2}+3^{2}+4^{2}-5^{2}-6^{2}+7^{2}+8^{2}-9^{2}-10^{2}+11^{2}\\&=&\ldots \end{array}}}$

Die kürzeste Variante, die man aber mit diesem Algorithmus allerdings nicht bekommt, wäre ${\displaystyle 14=1^{2}+2^{2}+3^{2}}$.

• Sei ${\displaystyle n=19}$. Es ist ${\displaystyle 19=3+4\cdot 4}$ und somit ${\displaystyle 19\equiv 3{\pmod {4}}}$. Also ist ${\displaystyle r=3}$ und ${\displaystyle q=4}$. Es gilt:

${\displaystyle {\begin{array}{rcl}19&=&3+4\cdot 4\\&=&-1^{2}+4\cdot 5\\&=&-1^{2}+4+4+4+4+4\\&=&-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})+(18^{2}-19^{2}-20^{2}+21^{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}+18^{2}-19^{2}-20^{2}+21^{2}\\&=&\ldots \end{array}}}$

Die kürzeste Variante, die man aber mit diesem Algorithmus allerdings nicht bekommt, wäre ${\displaystyle 19=1^{2}+2^{2}+3^{2}+4^{2}+5^{2}-6^{2}}$.

Obige Darstellung von ${\displaystyle n}$ kann verallgemeinert werden, indem man den Exponenten ${\displaystyle 2}$ durch einen beliebigen positiven Exponenten ${\displaystyle p}$ ersetzt. Es gilt also:

Jede ganze Zahl ${\displaystyle n}$ kann auf unendlich viele Arten in der folgenden Form geschrieben werden:

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

Diesen Satz konnte der Mathematiker Bleicher beweisen.^[2]

• Sei der Exponent ${\displaystyle p=3}$:

${\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}}$

• Sei der Exponent ${\displaystyle p=4}$:

${\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}}$

Sei ${\displaystyle f(k)}$ ein ganzzahliges Polynom (also ein Polynom, dessen Funktionswerte ${\displaystyle f(k)}$ immer ganze Zahlen sind, solange man ganze Zahlen einsetzt) und dessen Koeffizienten nicht alle durch eine ganze Zahl ${\displaystyle d>1}$ teilbar sind.

Obige Darstellung von ${\displaystyle n}$ kann noch weiter verallgemeinert werden, indem man ${\displaystyle k^{p}}$ durch so ein beliebiges ganzzahliges Polynom ${\displaystyle f(k)}$ der soeben angegebenen Form ersetzt. Es gilt somit:

Jede ganze Zahl ${\displaystyle n}$ kann auf unendlich viele Arten in der folgenden Form geschrieben werden:

${\displaystyle n=\sum _{k=1}^{N}{a_{k}f(k)}\quad {\rm {mit}}\quad a_{k}\in \{1,-1\}}$

Diesen Satz konnte der Mathematiker Yu beweisen.^[3]

• Waringsches Problem
• Prouhet-Tarry-Escott-Problem

• R. L. Graham: Complete sequences of polynomial values. Duke Math. J. 31, 1964, S. 275–285, abgerufen am 17. Mai 2025. 
• Eiji Miyanohara: A generalization of the Erdős-Suranyi problem. Indagationes Mathematicae 28 (2), 2017, S. 353–361, abgerufen am 17. Mai 2025. 
• Finding the min of m such that k=±1ⁿ±2ⁿ±3ⁿ±⋯±mⁿ for a given pair (n,k). math.stackexchange.com, abgerufen am 17. Mai 2025. 

1. ↑ Paul Erdős, János Surányi: Topics in the Theory of Numbers. Springer Science+Business Media, 2003, S. 227–228, Kapitel 4, Exercise 15, abgerufen am 17. Mai 2025. 
2. ↑ ^{a b} Michael N. Bleicher: On Prielipp's Problem on Signed Sums of kth Powers. Journal of Number Theory 56 (1), 1996, S. 36–51, abgerufen am 17. Mai 2025. 
3. ↑ Hong Bing Yu: Signed sums of polynomial values. Proc. Amer. Math. Soc. 130 (6), 2002, S. 1623–1627, abgerufen am 17. Mai 2025.