Prouhet-Tarry-Escott-Problem

In der Mathematik verlangt das Prouhet-Tarry-Escott-Problem nach zwei disjunkten Multimengen A und B mit jeweils $n$ ganzen Zahlen, deren erste $k$ symmetrische Potenzsummenpolynome alle gleich sind. Anders formuliert, sollten die beiden Multimengen folgende Gleichungen erfüllen:

$\sum _{a\in A}{a}^i=\sum _{b\in B}{b}^i$ für alle ganzen Zahlen $i\in \mathbb{Z}$ zwischen 1 und einem gegebenen $k$

Es konnte gezeigt werden, dass $k<n$ sein muss.

Mit anderen Worten werden ganzzahlige Lösungen für das folgende Gleichungssystem gesucht:

$\begin{array}{ccc}{a}_1^1+a_2^1+\dots +a_n^1& =& b_1^1+b_2^1+\dots +b_n^1\\ a_1^2+a_2^2+\dots +a_n^2& =& b_1^2+b_2^2+\dots +b_n^2\\ a_1^3+a_2^3+\dots +a_n^3& =& b_1^3+b_2^3+\dots +b_n^3\\ \dots & & \\ a_1^k+a_2^k+\dots +a_n^k& =& b_1^k+b_2^k+\dots +b_n^k\end{array}$

Oder kurz:

$a_1^k+a_2^k+\dots +a_n^k=b_1^k+b_2^k+\dots +b_n^k$ mit $k\in \{1,2,\dots ,n-1\}$

Vorlage:AnkerLösungen, die bis $k=n-1$ gelten, nennt man ideale Lösungen.

Ideale Lösungen sind bekannt für $3\le n\le 10$ und für $n=12$. Somit sind keine idealen Lösungen bekannt für $n=11$ und für $n\ge 13$.

Das Problem wurde nach den drei Mathematikern Eugène Prouhet, Gaston Tarry und Edward B. Escott benannt, die es in den frühen 1850er-Jahren (Prouhet) bzw. in den frühen 1910er-Jahren (Tarry & Escott) untersuchten. Das Problem selbst geht auf Briefe von Christian Goldbach und Leonhard Euler aus den Jahren 1750/1751 zurück.

Definitionen

• Eine symmetrische Lösung hat die folgende Form:

$A=\{T\pm a_1,T\pm a_2,\dots ,T\pm a_n\}$ und $B=\{T\pm b_1,T\pm b_2,\dots ,T\pm b_n\}$ für gerade $n$ und $T\in \frac{\mathbb{Z}}{2}$

$A=\{T+a_1,T+a_2,\dots ,T+a_n\}$ und $B=\{T-a_1,T-a_2,\dots ,T-a_n\}$ für ungerade $n$ und $T\in \mathbb{Z}$

• Lösungen, die obige Eigenschaft nicht besitzen, heißen nicht-symmetrische Lösungen.

Beispiele

• Eine ideale Lösung für $n=6$ ist die folgende:

$\begin{array}{ccc}{0}^1+5^1+6^1+16^1+17^1+22^1& =& 1^1+2^1+10^1+12^1+20^1+21^1(=66)\\ 0^2+5^2+6^2+16^2+17^2+22^2& =& 1^2+2^2+10^2+12^2+20^2+21^2(=1090)\\ 0^3+5^3+6^3+16^3+17^3+22^3& =& 1^3+2^3+10^3+12^3+20^3+21^3(=19998)\\ 0^4+5^4+6^4+16^4+17^4+22^4& =& 1^4+2^4+10^4+12^4+20^4+21^4(=385234)\\ 0^5+5^5+6^5+16^5+17^5+22^5& =& 1^5+2^5+10^5+12^5+20^5+21^5(=7632966)\end{array}$

oder kurz:

$0^k+5^k+6^k+16^k+17^k+22^k=1^k+2^k+10^k+12^k+20^k+21^k$ für $k\in \{1,2,3,4,5\}$

oder mit der Schreibweise, mit der dieser Artikel eingeführt wurde:

Eine ideale Lösung für $n=6$ ist für die beiden Mengen $A=\{0,5,6,16,17,22\}$ und $B=\{1,2,10,12,20,21\}$ bekannt.

Eine weitere, noch kürzere Schreibweise ist die folgende:

$[0,5,6,16,17,22]=[1,2,10,12,20,21]$ ist eine ideale Lösung für $k=5$ (oder $n=6$).

Die beiden Mengen $A$ und $B$ sind bezüglich $T=11$ symmetrisch, weil sie die folgende Form haben:

$A=\{11\pm 11,11\pm 6,11\pm 5\}$ und $B=\{11\pm 10,11\pm 9,11\pm 1\}$

Diese Lösung wurde von G. Tarry im Jahr 1912 entdeckt.

• Eine ideale (und bezüglich $T=5,5$ sogar symmetrische) Lösung für $n=4$ ist für die beiden Mengen $A=\{\frac{11}{2}\pm \frac{11}{2},\frac{11}{2}\pm \frac{3}{2}\}$ und $B=\{\frac{11}{2}\pm \frac{9}{2},\frac{11}{2}\pm \frac{7}{2}\}$ bekannt:

$A=\{0,4,7,11\}$ und $B=\{1,2,9,10\}$. Es gilt also:

$0^k+4^k+7^k+11^k=1^k+2^k+9^k+10^k(=22,186$ bzw. $1738)$ für $k\in \{1,2,3\}$

• Eine ideale (und bezüglich $T=9$ sogar symmetrische) Lösung für $n=5$ ist für die beiden Mengen $A=\{9+(-9),9+(-5),9+(-1),9+7,9+8\}$ und $B=\{9-(-9),9-(-5),9-(-1),9-7,9-8\}$ bekannt:

$A=\{0,4,8,16,17\}$ und $B=\{1,2,10,14,18\}$. Es gilt also:

$0^k+4^k+8^k+16^k+17^k=1^k+2^k+10^k+14^k+18^k(=45,625,9585$ bzw. $153409)$ für $k\in \{1,2,3,4\}$

• Vorlage:Anker Eine ideale (und bezüglich $T=0$ sogar symmetrische) Lösung für $n=12$ ist für die beiden Mengen $A=\{\pm 22,\pm 61,\pm 86,\pm 127,\pm 140,\pm 151\}$ und $B=\{\pm 35,\pm 47,\pm 94,\pm 121,\pm 146,\pm 148\}$ bekannt. Es gilt also:

$(-151{)}^k+(-140{)}^k+(-127{)}^k+(-86{)}^k+(-61{)}^k+(-22{)}^k+22^k+61^k+86^k+127^k+140^k+151^k=(-148{)}^k+(-146{)}^k+(-121{)}^k+(-94{)}^k+(-47{)}^k+(-35{)}^k+35^k+47^k+94^k+121^k+146^k+148^k$

für $k\in \{1,2,3,4,5,6,7,8,9,10,11\}$

Diese Lösung wurde von Nuutti Kuosa, Jean-Charles Meyrignac und Chen Shuwen im Jahr 1999 entdeckt.

• Es folgen ein paar bekannte ideale Lösungen für $2\le n\le 10$ und $n=12$, die bezüglich $T=0$ symmetrisch sind:

• Es folgen ein paar bekannte ideale Lösungen für $2\le n\le 10$ und $n=12$, die bezüglich irgendeinem $T=0$ symmetrisch sind:

• Es folgen ein paar bekannte ideale Lösungen für $3\le n\le 8$, die nicht-symmetrisch sind (für andere $n$ sind bis dato keine bekannt):

Eigenschaften

• Sei $A=\{a_1,a_2,\dots ,a_m\}$ und $B=\{b_1,b_2,\dots ,b_m\}$ mit $k\in \{1,2,\dots ,n\}$ eine Lösung, also:

$a_1^k+a_2^k+\dots +a_m^k=b_1^k+b_2^k+\dots +b_m^k$ für $k\in \{1,2,\dots ,n\}$

Dann gilt:

Auch $\bar{A}=\{S\cdot a_1+T,S\cdot a_2+T,\dots ,S\cdot a_m+T\}$ und $\bar{B}=\{S\cdot b_1+T,S\cdot b_2+T,\dots ,S\cdot b_m+T\}$ mit $k\in \{1,2,\dots ,n\}$ und ganzzahligem $S,T\in \mathbb{Z}$ ist Lösung.

Lösungen, die mit dieser Methode zustande kommen, werden äquivalente Lösungen genannt.

Diese Eigenschaft ermöglicht es, Lösungen zu standardisieren, indem beispielsweise gefordert wird, dass sie nur positive Zahlen enthalten.

• Sei $A=\{a_1,a_2,\dots ,a_m\}$ und $B=\{b_1,b_2,\dots ,b_m\}$ mit $k\in \{1,2,\dots ,n\}$ eine Lösung.

Dann gilt:

Auch $\bar{A}=\{a_1,a_2,\dots ,a_m,b_1+T,b_2+T,\dots ,b_m+T\}$ und $\bar{B}=\{b_1,b_2,\dots ,b_m,a_1+T,a_2+T,\dots ,a_m+T\}$ mit $k\in \{1,2,\dots ,n+1\}$ und ganzzahligem $T\in \mathbb{Z}$ ist Lösung.

• Sei $A=\{a_1,a_2,\dots ,a_m\}$ und $B=\{b_1,b_2,\dots ,b_m\}$ mit $k\in \{1,2,\dots ,m-1\}$ eine Lösung. Sei weiters $S=m$ und $T=a_1+a_2+\dots +a_m$.

Dann gilt:

Auch $\bar{A}=\{S\cdot a_1-T,S\cdot a_2-T,\dots ,S\cdot a_m-T\}$ und $\bar{B}=\{S\cdot b_1-T,S\cdot b_2-T,\dots ,S\cdot b_m-T\}$ mit $k\in \{1,2,\dots ,m-1,m+1\}$ ist Lösung.

• Sei $A=\{a_1,a_2,\dots ,a_m\}$ und $B=\{b_1,b_2,\dots ,b_m\}$ mit $k\in \{1,2,\dots ,n\}$ eine nicht triviale Lösung.

Dann gilt:

$m\ge n+1$

Ist $m=n+1$, so nennt man die Lösungen (wie schon oben erwähnt) ideale Lösungen.

Methode zur Bestimmung von Lösungen

• Der französische Mathematiker Prouhet nutzte die Thue-Morse-Folge, um eine Lösung für $n=2^k$ für alle $k$ zu finden. Im Speziellen unterteilte er die Zahlen zwischen $0$ und $2^k-1$ in

a) die Zahlen, deren Binärdarstellung (also die Darstellung im Dualsystem) eine gerade Anzahl an Einsen enthält (die sogenannten bösen Zahlen), und

b) die Zahlen, deren Binärdarstellung eine ungerade Anzahl an Einsen enthält (die sogenannten abscheulichen Zahlen).

Dann ergeben die beiden Mengen der Unterteilung eine Lösung des Problems.

Beispiel:

Sei $n=2^3=8$ und $k=3$. Dann gilt für die Unterteilung der Zahlen von $0$ bis $n=2^{k+1}-1=2^{3+1}-1=2^4-1=16-1=15$:

0=(0)₂, 3=(11)₂, 5=(101)₂, 6=(110)₂, 9=(1001)₂, 10=(1010)₂, 12=(1100)₂ und 15=(1111)₂

Diese 8 Zahlen haben in ihrer Binärentwicklung allesamt eine gerade Anzahl an Einsen, sind somit böse Zahlen und bilden die Menge $A=\{0,3,5,6,9,10,12,15\}$.

1=(1)₂, 2=(10)₂, 4=(100)₂, 7=(111)₂, 8=(1000)₂, 11=(1011)₂, 13=(1101)₂ und 14=(1110)₂

Diese 8 Zahlen haben in ihrer Binärentwicklung allesamt eine ungerade Anzahl an Einsen, sind somit abscheuliche Zahlen und bilden die Menge $B=\{1,2,4,7,8,11,13,14\}$.

Tatsächlich erhält man eine Lösung für das Gleichungssystem:

$0^k+3^k+5^k+6^k+9^k+10^k+12^k+15^k=1^k+2^k+4^k+7^k+8^k+11^k+13^k+14^k$ für $k\in \{1,2,3\}$

Verallgemeinerung

Seien $n,k\in \mathbb{N}$ zwei positive ganze Zahlen. Dann sind zwei ganzzahlige Multimengen $\{(x_1,y_1),\dots ,(x_n,y_n)\}$ und $\{({x_1}^{\prime },{y_1}^{\prime }),\dots ,({x_n}^{\prime },{y_n}^{\prime })\}$ gesucht, sodass gilt:

$\sum _{i=1}^n{x}_i^j{y}_i^{d-j}=\sum _{i=1}^n{x^{\prime }}_i^j{y^{\prime }}_i^{d-j}$ für alle $d,j\in \{0,\dots ,k\}$ mit $j\le d$.

Diese höherdimensionale Variante des Prouhet-Tarry-Escott Problems wurde von Andreas Alpers und Robert Tijdeman im Jahr 2007 eingeführt und untersucht.

Beispiel

• Sei $n=6$ und $k=5$. Dann gilt:

$\{(x_1,y_1),\dots ,(x_6,y_6)\}=\{(2,1),(1,3),(3,6),(6,7),(7,5),(5,2)\}$ und $\{(x{\text{'}}_1,y{\text{'}}_1),\dots ,(x{\text{'}}_6,y{\text{'}}_6)\}=\{(1,2),(2,5),(5,7),(7,6),(6,3),(3,1)\}$

Mit anderen Worten:

$\begin{array}{cccccc}{2}^0\cdot 1^0+1^0\cdot 3^0+3^0\cdot 6^0+6^0\cdot 7^0+7^0\cdot 5^0+5^0\cdot 2^0& =& 1^0\cdot 2^0+2^0\cdot 5^0+5^0\cdot 7^0+7^0\cdot 6^0+6^0\cdot 3^0+3^0\cdot 1^0& (=& 6),& d=0,j=0\\ 2^0\cdot 1^1+1^0\cdot 3^1+3^0\cdot 6^1+6^0\cdot 7^1+7^0\cdot 5^1+5^0\cdot 2^1& =& 1^0\cdot 2^1+2^0\cdot 5^1+5^0\cdot 7^1+7^0\cdot 6^1+6^0\cdot 3^1+3^0\cdot 1^1& (=& 24),& d=1,j=0\\ 2^1\cdot 1^0+1^1\cdot 3^0+3^1\cdot 6^0+6^1\cdot 7^0+7^1\cdot 5^0+5^1\cdot 2^0& =& 1^1\cdot 2^0+2^1\cdot 5^0+5^1\cdot 7^0+7^1\cdot 6^0+6^1\cdot 3^0+3^1\cdot 1^0& (=& 24),& d=1,j=1\\ 2^0\cdot 1^2+1^0\cdot 3^2+3^0\cdot 6^2+6^0\cdot 7^2+7^0\cdot 5^2+5^0\cdot 2^2& =& 1^0\cdot 2^2+2^0\cdot 5^2+5^0\cdot 7^2+7^0\cdot 6^2+6^0\cdot 3^2+3^0\cdot 1^2& (=& 124),& d=2,j=0\\ 2^1\cdot 1^1+1^1\cdot 3^1+3^1\cdot 6^1+6^1\cdot 7^1+7^1\cdot 5^1+5^1\cdot 2^1& =& 1^1\cdot 2^1+2^1\cdot 5^1+5^1\cdot 7^1+7^1\cdot 6^1+6^1\cdot 3^1+3^1\cdot 1^1& (=& 110),& d=2,j=1\\ 2^2\cdot 1^0+1^2\cdot 3^0+3^2\cdot 6^0+6^2\cdot 7^0+7^2\cdot 5^0+5^2\cdot 2^0& =& 1^2\cdot 2^0+2^2\cdot 5^0+5^2\cdot 7^0+7^2\cdot 6^0+6^2\cdot 3^0+3^2\cdot 1^0& (=& 124),& d=2,j=2\\ 2^0\cdot 1^3+1^0\cdot 3^3+3^0\cdot 6^3+6^0\cdot 7^3+7^0\cdot 5^3+5^0\cdot 2^3& =& 1^0\cdot 2^3+2^0\cdot 5^3+5^0\cdot 7^3+7^0\cdot 6^3+6^0\cdot 3^3+3^0\cdot 1^3& (=& 720),& d=3,j=0\\ 2^1\cdot 1^2+1^1\cdot 3^2+3^1\cdot 6^2+6^1\cdot 7^2+7^1\cdot 5^2+5^1\cdot 2^2& =& 1^1\cdot 2^2+2^1\cdot 5^2+5^1\cdot 7^2+7^1\cdot 6^2+6^1\cdot 3^2+3^1\cdot 1^2& (=& 608),& d=3,j=1\\ 2^2\cdot 1^1+1^2\cdot 3^1+3^2\cdot 6^1+6^2\cdot 7^1+7^2\cdot 5^1+5^2\cdot 2^1& =& 1^2\cdot 2^1+2^2\cdot 5^1+5^2\cdot 7^1+7^2\cdot 6^1+6^2\cdot 3^1+3^2\cdot 1^1& (=& 608),& d=3,j=2\\ 2^3\cdot 1^0+1^3\cdot 3^0+3^3\cdot 6^0+6^3\cdot 7^0+7^3\cdot 5^0+5^3\cdot 2^0& =& 1^3\cdot 2^0+2^3\cdot 5^0+5^3\cdot 7^0+7^3\cdot 6^0+6^3\cdot 3^0+3^3\cdot 1^0& (=& 720),& d=3,j=3\\ 2^0\cdot 1^4+1^0\cdot 3^4+3^0\cdot 6^4+6^0\cdot 7^4+7^0\cdot 5^4+5^0\cdot 2^4& =& 1^0\cdot 2^4+2^0\cdot 5^4+5^0\cdot 7^4+7^0\cdot 6^4+6^0\cdot 3^4+3^0\cdot 1^4& (=& 4420),& d=4,j=0\\ 2^1\cdot 1^3+1^1\cdot 3^3+3^1\cdot 6^3+6^1\cdot 7^3+7^1\cdot 5^3+5^1\cdot 2^3& =& 1^1\cdot 2^3+2^1\cdot 5^3+5^1\cdot 7^3+7^1\cdot 6^3+6^1\cdot 3^3+3^1\cdot 1^3& (=& 3650),& d=4,j=1\\ 2^2\cdot 1^2+1^2\cdot 3^2+3^2\cdot 6^2+6^2\cdot 7^2+7^2\cdot 5^2+5^2\cdot 2^2& =& 1^2\cdot 2^2+2^2\cdot 5^2+5^2\cdot 7^2+7^2\cdot 6^2+6^2\cdot 3^2+3^2\cdot 1^2& (=& 3426),& d=4,j=2\\ 2^3\cdot 1^1+1^3\cdot 3^1+3^3\cdot 6^1+6^3\cdot 7^1+7^3\cdot 5^1+5^3\cdot 2^1& =& 1^3\cdot 2^1+2^3\cdot 5^1+5^3\cdot 7^1+7^3\cdot 6^1+6^3\cdot 3^1+3^3\cdot 1^1& (=& 3650),& d=4,j=3\\ 2^4\cdot 1^0+1^4\cdot 3^0+3^4\cdot 6^0+6^4\cdot 7^0+7^4\cdot 5^0+5^4\cdot 2^0& =& 1^4\cdot 2^0+2^4\cdot 5^0+5^4\cdot 7^0+7^4\cdot 6^0+6^4\cdot 3^0+3^4\cdot 1^0& (=& 4420),& d=4,j=4\\ 2^0\cdot 1^5+1^0\cdot 3^5+3^0\cdot 6^5+6^0\cdot 7^5+7^0\cdot 5^5+5^0\cdot 2^5& =& 1^0\cdot 2^5+2^0\cdot 5^5+5^0\cdot 7^5+7^0\cdot 6^5+6^0\cdot 3^5+3^0\cdot 1^5& (=& 27984),& d=5,j=0\\ 2^1\cdot 1^4+1^1\cdot 3^4+3^1\cdot 6^4+6^1\cdot 7^4+7^1\cdot 5^4+5^1\cdot 2^4& =& 1^1\cdot 2^4+2^1\cdot 5^4+5^1\cdot 7^4+7^1\cdot 6^4+6^1\cdot 3^4+3^1\cdot 1^4& (=& 22832),& d=5,j=1\\ 2^2\cdot 1^3+1^2\cdot 3^3+3^2\cdot 6^3+6^2\cdot 7^3+7^2\cdot 5^3+5^2\cdot 2^3& =& 1^2\cdot 2^3+2^2\cdot 5^3+5^2\cdot 7^3+7^2\cdot 6^3+6^2\cdot 3^3+3^2\cdot 1^3& (=& 20648),& d=5,j=2\\ 2^3\cdot 1^2+1^3\cdot 3^2+3^3\cdot 6^2+6^3\cdot 7^2+7^3\cdot 5^2+5^3\cdot 2^2& =& 1^3\cdot 2^2+2^3\cdot 5^2+5^3\cdot 7^2+7^3\cdot 6^2+6^3\cdot 3^2+3^3\cdot 1^2& (=& 20648),& d=5,j=3\\ 2^4\cdot 1^1+1^4\cdot 3^1+3^4\cdot 6^1+6^4\cdot 7^1+7^4\cdot 5^1+5^4\cdot 2^1& =& 1^4\cdot 2^1+2^4\cdot 5^1+5^4\cdot 7^1+7^4\cdot 6^1+6^4\cdot 3^1+3^4\cdot 1^1& (=& 22832),& d=5,j=4\\ 2^5\cdot 1^0+1^5\cdot 3^0+3^5\cdot 6^0+6^5\cdot 7^0+7^5\cdot 5^0+5^5\cdot 2^0& =& 1^5\cdot 2^0+2^5\cdot 5^0+5^5\cdot 7^0+7^5\cdot 6^0+6^5\cdot 3^0+3^5\cdot 1^0& (=& 27984),& d=5,j=5\end{array}$

• Es sind keine Lösungen für $n=k+1$ mit $k\ge 6$ bekannt.

Siehe auch

• Eulersche Vermutung
• Jacobi-Madden-Gleichung
• Pythagoreisches Quadrupel
• Taxicab-Zahl

Weblinks

• Vorlage:MathWorld
• Choudry, Ajai: Ideal Solutions of the Tarry-Escott Problem of Degrees Four and Five and Related Diophantine Systems, L’Enseignement mathématique 49 (2003), S. 101–108