Problem Prouheta-Tarry-Escotta

W matematyce , zwłaszcza w teorii liczb i kombinatoryki The problem Prouhet-Zostańże-Escott jest znaleźć dla każdej liczby całkowitej , dwa zestawy i z całkowitymi każdy, takich jak: nie{\ displaystyle n}W{\ displaystyle A}b{\ displaystyle B}nie{\ displaystyle n}

∑w∈Wwja=∑b∈bbja{\ Displaystyle \ sum _ {a \ in A} a ^ {i} = \ sum _ {b \ in B} b ^ {i}}

dla każdego z maksymalnie podanej liczby całkowitej . Jeśli i zweryfikujemy te warunki, piszemy . ja{\ displaystyle i}1{\ displaystyle 1}k{\ displaystyle k}W{\ displaystyle A}b{\ displaystyle B}W=kb{\ displaystyle A = _ {k} B}

Poszukujemy rozwiązania o minimalnej wielkości dla danego stopnia . Ten wciąż otwarty problem został nazwany na cześć Eugène'a Prouheta , który badał go w 1851 roku, oraz Gastona Tarry'ego i Edwarda Brinda Escotta, którzy rozważali go na początku 1910 roku. nie{\ displaystyle n}k{\ displaystyle k}

Największą wartością, dla której znamy rozwiązanie, jest . Odpowiednie rozwiązanie dają następujące zbiory: k{\ displaystyle k}nie=k+1{\ Displaystyle n = k + 1}k=11{\ displaystyle k = 11}

W={±22,±61,±86,±127,±140,±151} ,b={±35,±47,±94,±121,±146,±148}{\ Displaystyle A = \ {\ pm 22 \ pm 61 \ pm 86 \ pm 127 \ pm 140 \ pm 151 \} \ \ qquad B = \ {\ pm 35 \ pm 47 \ pm 94, \ pm 121, \ pm 146, \ pm 148 \}}

Przykład

Liczba całkowita w definicji to stopień , a liczba całkowita to rozmiar . Łatwo zauważyć, że dla każdego rozwiązania mamy . Dlatego szukamy rozwiązania o minimalnych wymiarach. k{\ displaystyle k}nie{\ displaystyle n}nie>k{\ displaystyle n> k}

Dla rozmiaru i stopnia , oba zestawy nie=6{\ displaystyle n = 6}k=5{\ displaystyle k = 5}

{0,5,6,16,17,22}{\ Displaystyle \ {0,5,6,16,17,22 \}} i {1,2,10,12,20,21}{\ Displaystyle \ {1,2,10,12,20,21 \}}

są rozwiązaniem problemu, ponieważ:

0+5+6+16+17+22=66=1+2+10+12+20+21{\ Displaystyle 0 + 5 + 6 + 16 + 17 + 22 = 66 = 1 + 2 + 10 + 12 + 20 + 21}02+52+62+162+172+222=1090=12+22+102+122+202+212{\ Displaystyle 0 ^ {2} + 5 ^ {2} + 6 ^ {2} + 16 ^ {2} + 17 ^ {2} + 22 ^ {2} = 1090 = 1 ^ {2} + 2 ^ { 2} + 10 ^ {2} + 12 ^ {2} + 20 ^ {2} + 21 ^ {2}}03+53+63+163+173+223=19998=13+23+103+123+203+213{\ Displaystyle 0 ^ {3} + 5 ^ {3} + 6 ^ {3} + 16 ^ {3} + 17 ^ {3} + 22 ^ {3} = 19998 = 1 ^ {3} + 2 ^ { 3} + 10 ^ {3} + 12 ^ {3} + 20 ^ {3} + 21 ^ {3}}04+54+64+164+174+224=385234=14+24+104+124+204+214{\ Displaystyle 0 ^ {4} + 5 ^ {4} + 6 ^ {4} + 16 ^ {4} + 17 ^ {4} + 22 ^ {4} = 385234 = 1 ^ {4} + 2 ^ { 4} + 10 ^ {4} + 12 ^ {4} + 20 ^ {4} + 21 ^ {4}} 05+55+65+165+175+225=7632966=15+25+105+125+205+215{\ Displaystyle 0 ^ {5} + 5 ^ {5} + 6 ^ {5} + 16 ^ {5} + 17 ^ {5} + 22 ^ {5} = 7632966 = 1 ^ {5} + 2 ^ { 5} + 10 ^ {5} + 12 ^ {5} + 20 ^ {5} + 21 ^ {5}}.

Idealnym rozwiązaniem jest rozwiązanie, którego wielkość jest równa stopniowi 1. Powyższe rozwiązanie jest zatem idealne.

Historia

W 1851 roku Eugène Prouhet postawił bardziej ogólny problem polegający na rozkładaniu liczb całkowitych x od 1 do n m na n klas, tak aby suma potęg k -tych liczb całkowitych każdej klasy była taka sama, dla k = 0, 1 , ... Proces, który proponuje, sprowadza się do numerowania klas od 0 do n - 1, do rozłożenia każdej liczby całkowitej x - 1 na podstawę liczby n , do zsumowania jej cyfr, do obliczenia reszty r tej sumy modulo n i przypisz liczbę całkowitą x do klasy r .

W przypadku, gdy n = 2, umieszczenie liczby całkowitej x w jednej z dwóch klas indeksu 0 lub 1 odbywa się w zależności od tego, czy x- ty człon ciągu Prouheta-Thue-Morse'a wynosi 0 lub 1 Na przykład: pierwszych 8 liczb całkowitych jest rozłożonych w: 1, 4, 6, 7 z jednej strony i 2, 3, 5, 8 z drugiej, a suma potęg k -tej liczb całkowitych tych dwóch klas pokrywają się, aż k = 2.

Leonard Eugene Dickson poświęca jeden rozdział swej historii teorii liczb do „  Zestawy liczb całkowitych z równych sum jak uprawnienia  ” , a list nie mniej niż 70 artykułów na ten temat. W swoim artykule historycznym Edward Maitland Wright zauważa, że ​​artykuł Prouheta został ponownie odkryty dopiero w 1948 roku.

Ostatnie wydarzenia opisał Peter Borwein i jego współautorzy; zobacz także artykuł Filasety i Markovicha. Wersja dwuwymiarowa została zbadana przez Alpersa i Tijdemana (2007) .

Właściwości i wyniki

• Jeśli para i jest rozwiązaniem stopnia , to dla wszystkich i całej paryW={w1,w2,...,wnie}{\ Displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}b={b1,b2,...,bnie}{\ Displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}k{\ displaystyle k}NIE≠0{\ Displaystyle N \ neq 0}M{\ displaystyle M}W′={NIEw1+M,NIEw2+M,...,NIEwnie+M}mitb′={NIEb1+M,NIEb2+M,...,NIEbnie+M}{\ Displaystyle A '= \ {Na_ {1} + M, Na_ {2} + M, \ ldots, Na_ {n} + M \} \ quad {\ rm {i}} \ quad B' = \ {Nb_ {1} + M, Nb_ {2} + M, \ ldots, Nb_ {n} + M \}}jest nadal rozwiązaniem w tym samym stopniu. A więc rozwiązanie{0,5,6,16,17,22}=5{1,2,10,12,20,21}{\ Displaystyle \ {0,5,6,16,17,22 \} = _ {5} \ {1,2,10,12,20,21 \}}również podaje rozwiązanie{1,6,7,17,18,23}=5{2,3,11,13,21,22}.{\ Displaystyle \ {1,6,7,17,18,23 \} = _ {5} \ {2,3,11,13,21,22 \}.}Ta obserwacja pozwala na ujednolicenie rozwiązań, narzucając np., Że zawierają one tylko dodatnie lub zerowe liczby całkowite, a zero w nich występuje.
• Nie znamy idealnego rozwiązania dla każdego stopnia, ale wiemy, że dla każdego stopnia jest rozwiązanie według wielkości .k{\ displaystyle k}nie≤k(k+1)/2+1{\ Displaystyle n \ równoważnik k (k + 1) / 2 + 1}
• Rozwiązania symetryczne: rozwiązanie o równych rozmiarach jest symetryczne, jeśli każdy składnik ma formęnie=2m{\ displaystyle n = 2m}{±vs1,±vs2,...,±vsm}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}Rozwiązanie podane we wstępie ma taką formę.
• Rozwiązanie o nieparzystej wielkości jest symetryczne, jeśli składniki rozwiązania są przeciwne, tj.W={w1,w2,...,wnie}{\ Displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} i b={-w1,-w2,...,-wnie}.{\ Displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Idealne i symetryczne rozwiązania

Idealne i symetryczne rozwiązania są znane dla stopni , z wyjątkiem  : k≤11{\ displaystyle k \ leq 11}k=10{\ displaystyle k = 10}

• k=1{\ displaystyle k = 1}

{±2}=1{±1}{\ displaystyle \ {\ pm 2 \} = _ {1} \ {\ pm 1 \}}

• k=2{\ displaystyle k = 2}

{-2,-1,3}=2{2,1,-3}{\ Displaystyle \ {- 2, -1,3 \} = _ {2} \ {2,1, -3 \}}

• k=3{\ Displaystyle k = 3}

{±3,±11}=3{±7,±9}{\ Displaystyle \ {\ pm 3 \ pm 11 \} = _ {3} \ {\ pm 7 \ pm 9 \}}

• k=4{\ displaystyle k = 4}

{-8,-7,1,5,9}=4{8,7,-1,-5,-9}{\ Displaystyle \ {- 8, -7,1,5,9 \} = _ {4} \ {8,7, -1, -5, -9 \}}

• k=5{\ displaystyle k = 5}

{±4,±9,±13}=5{±1,±11,±12}{\ Displaystyle \ {\ pm 4 \ pm 9 \ pm 13 \} = _ {5} \ {\ pm 1 \ pm 11 \ pm 12 \}}

• k=6{\ displaystyle k = 6}

{-51,-33,-24,7,13,38,50}=6{51,33,24,-7,-13,-38,-50}{\ Displaystyle \ {- 51, -33, -24,7,13,38,50 \} = _ {6} \ {51,33,24, -7, -13, -38, -50 \}}

• k=7{\ displaystyle k = 7}

{±2,±16,±21,±25}=7{±5,±14,±23,±24}{\ Displaystyle \ {\ pm 2 \ pm 16 \ pm 21 \ pm 25 \} = _ {7} \ {\ pm 5 \ pm 14 \ pm 23 \ pm 24 \}}

• k=8{\ displaystyle k = 8}

{-98,-82,-58,-34,13,16,69,75,99}=8{98,82,58,34,-13,-16,-69,-75,-99}{\ Displaystyle \ {- 98, -82, -58, -34,13,16,69,75,99 \} = _ {8} \ {98,82,58,34, -13, -16, - 69, -75, -99 \}}

• k=9{\ displaystyle k = 9}

{±99,±100,±188,±301,±313}=9{±71,±131,±180,±307,±308}{\ Displaystyle \ {\ pm 99 \ pm 100 \ pm 188 \ pm 301 \ pm 313 \} = _ {9} \ {\ pm 71 \ pm 131 \ pm 180 \ pm 307 \ po południu 308 \}}

To ostatnie rozwiązanie podano, wraz z innymi, w Borwein i in. (2003) . Nie jest znane żadne idealne rozwiązanie . k=10{\ displaystyle k = 10}

Sformułowanie algebraiczne

Istnieje bardziej algebraiczny sposób sformułowania problemu:

Wniosek  -  Następujące warunki są równoważne:

1. ∑ja=1niewjajot=∑ja=1niebjajot,(jot=1,...,k){\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} ^ {j} = \ sum _ {i = 1} ^ {n} b_ {i} ^ {j}, \ quad (j = 1, \ ldots, k)}
2. deg⁡(∏ja=1nie(x-wja)-∏ja=1nie(x-bja))≤nie-(k+1){\ Displaystyle \ deg \ lewo (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ po prawej) \ leq n- (k + 1)}
3. (x-1)k+1|∑ja=1niexwja-∑ja=1niexbja.{\ Displaystyle (x-1) ^ {k + 1} \ lewo | \ suma _ {i = 1} ^ {n} x ^ {a_ {i}} - \ suma _ {i = 1} ^ {n} x ^ {b_ {i}} \ dobrze ..}

Uwagi i odniesienia

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu z angielskiej Wikipedii zatytułowanego „  Prouhet - Tarry - Escott problem  ” ( zobacz listę autorów ) .

Uwagi

1. Borwein (2002) , str.  85
2. Rozwiązanie podane przez Nuutti Kuosa, Jean-Charlesa Meyrignaca i Chen Shuwen w 1999 roku, patrz Problem Prouheta-Tarry-Escotta .
3. ME Prouhet, Pamiętnik o niektórych relacjach między potęgami liczb , CR Acad. Sci. Paryż, seria I, t. 33, 1851, s.  225 .
4. (w) Leonard Eugene Dickson , Historia teorii liczb  (en) [ wydanie szczegółowe ], lot. 2, 1919, ok. XXIV, s.  705-716 .
5. Wright (1959)
6. Borwein i Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk i Percival 2003
9. (w :) Michael Filaseta i Maria Markovich , „  Polygony Newtona i problem Prouheta-Tarry-Escotta  ” , Journal of Number Theory , vol.  174, 2017, s.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) i Problem Prouheta-Tarry-Escotta .
11. Zobacz Borwein i Ingalls (1944) dla odniesień.

Bibliografia

• (en) Andreas Alpers i Robert Tijdeman , „  The dwuwymiarowy problem Prouheta-Tarry-Escotta  ” , J. Number Theor. , vol.  123,2007, s.  403-412
• (en) Peter Borwein , Computational Excursions in Analysis and Number Theory , New York / Berlin / Heidelberg, Springer , coll.  „Książki CMS w matematyce”,2002, 220  s. ( ISBN  0-387-95444-9 , czytaj online )Rozdział 11: Problem Prouheta - Tarry - Escotta (strony 85-96) jest poświęcony temu problemowi.
• (en) Peter Borwein i Colin Ingalls , „  The Prouhet-Tarry-Escott problem revisited  ” , nauczyciel. Matematyka. , vol.  40, n kość  1-2,1994, s.  3-27 ( czytaj online )
• (en) Peter Borwein , Petr Lisonĕk i Colin Percival , „  Obliczeniowe badania problemu Prouheta-Tarry-Escotta  ” , Math. Comp. , vol.  72, n o  2442003, s.  2063-2070 ( czytaj online )
• (de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Recenzje matematyczne  0019638 )
• GH Hardy i EM Wright ( przetłumaczone  z języka angielskiego przez F. Sauvageota), Wprowadzenie do teorii liczb [„  Wprowadzenie do teorii liczb  ”], Paryż i Heidelberg, Vuibert i Springer,2007Rozdział 20.5 „Twierdzenie o czterech kwadratach” dotyczy tego tematu. Rozdziały 21.9 „Problem Prouheta i Tarry'ego: liczba  ” i 21.10, s. 423-427, poświęcone są problemowi Prouheta-Tarry'ego.P.(k,jot){\ Displaystyle P (k, j)}
• (en) Edward M. Wright , „  Prouhet's 1851 solution of the Tarry-Escott problem of 1910  ” , Amer. Matematyka. Miesięcznie , vol.  66,Marzec 1959, s.  199-201

Zobacz też

Powiązane artykuły

• Apartament Prouhet-Thue-Morse
• Hipoteza Eulera
• Twierdzenie Erdősa-Suranyiego

Linki zewnętrzne

• (en) Chen Shuwen, Problem Prouheta-Tarry-Escotta
• (en) Eric W. Weisstein , „  Problem Prouheta-Tarry-Escotta  ” , na MathWorld

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">