Problema Prouhet-Tarry-Escott

În matematică , în special în teoria numerelor și combinatorică , problema Prouhet-Tarry-Escott este de a găsi, pentru fiecare număr întreg , două seturi și de numere întregi fiecare, cum ar fi: nu{\ displaystyle n}LA{\ displaystyle A}B{\ displaystyle B}nu{\ displaystyle n}

∑la∈LAlaeu=∑b∈Bbeu{\ displaystyle \ sum _ {a \ in A} a ^ {i} = \ sum _ {b \ in B} b ^ {i}}

pentru fiecare dintre până la un număr întreg dat. Dacă și verificăm aceste condiții, scriem . eu{\ displaystyle i}1{\ displaystyle 1}k{\ displaystyle k}LA{\ displaystyle A}B{\ displaystyle B}LA=kB{\ displaystyle A = _ {k} B}

Căutăm o soluție de dimensiuni minime pentru un anumit grad . Această problemă încă deschisă poartă numele lui Eugène Prouhet , care a studiat-o în 1851, și Gaston Tarry și Edward Brind Escott, care au considerat-o la începutul anilor 1910. nu{\ displaystyle n}k{\ displaystyle k}

Cea mai mare valoare pentru care cunoaștem o soluție este . O soluție corespunzătoare este dată de următoarele seturi: k{\ displaystyle k}nu=k+1{\ displaystyle n = k + 1}k=11{\ displaystyle k = 11}

LA={±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 \}}

Exemplu

Numărul întreg al definiției este gradul , iar numărul întreg este mărimea . Este ușor de văzut că pentru orice soluție avem . Prin urmare, căutăm o soluție de dimensiuni minime. k{\ displaystyle k}nu{\ displaystyle n}nu>k{\ displaystyle n> k}

Pentru dimensiune și grad , ambele seturi nu=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 \}}

sunt o soluție a problemei, deoarece:

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}}.

O soluție ideală este o soluție a cărei dimensiune este egală cu gradul + 1. Prin urmare, soluția de mai sus este ideală.

Istorie

În 1851, Eugène Prouhet a pus problema mai generală a distribuției numerelor întregi x de la 1 la n m în n clase, astfel încât suma puterilor k- mii întregi ale fiecărei clase să fie aceeași, pentru k = 0, 1 ... procesul propune sume pentru numerotarea claselor de la 0 la n - 1, pentru a descompune fiecare număr întreg x - 1 din numărul de bază n , pentru a adăuga până cifrelor sale, pentru a calcula restul r acestei modulo sum n și atribuiți numărul întreg x clasei r .

În cazul în care n = 2, plasarea numărului întreg x într-una din cele două clase de index 0 sau 1 se face în funcție de dacă al x -lea termen al secvenței Prouhet-Thue-Morse este 0 sau 1 De exemplu, primele 8 numere întregi sunt împărțite în: 1, 4, 6, 7 pe de o parte și 2, 3, 5, 8 pe de altă parte, iar suma puterilor k -th a numerelor întregi ale acestor două clase coincid până când k = 2.

Leonard Eugene Dickson dedică un capitol al lui Istoria teoria numerelor la „  seturi de numere întregi , cu sume egale de puteri cum ar fi  “ , și liste nu mai puțin de 70 de articole pe acest subiect. În articolul său istoric, Edward Maitland Wright notează că articolul lui Prouhet nu a fost redescoperit până în 1948.

Dezvoltările recente sunt descrise de Peter Borwein și de coautorii săi; vezi și articolul lui Filaseta și Markovich. O versiune bidimensională a fost studiată de Alpers și Tijdeman (2007) .

Proprietăți și rezultate

• Dacă cuplul și este o soluție de grad , atunci pentru toți și toți cuplulLA={la1,la2,...,lanu}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}B={b1,b2,...,bnu}{\ displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}k{\ displaystyle k}NU≠0{\ displaystyle N \ neq 0}M{\ displaystyle M}LA′={NUla1+M,NUla2+M,...,NUlanu+M}etB′={NUb1+M,NUb2+M,...,NUbnu+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 \}}este încă o soluție de același grad. Deci soluția{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 \}}oferă, de asemenea, soluția{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 \}.}Această observație face posibilă standardizarea soluțiilor, impunând de exemplu că acestea conțin doar numere întregi pozitive sau zero și că zero apare în ele.
• Nu știm o soluție ideală pentru fiecare grad, dar știm că pentru fiecare grad există o soluție de dimensiune .k{\ displaystyle k}nu≤k(k+1)/2+1{\ displaystyle n \ leq k (k + 1) / 2 + 1}
• Soluții simetrice: o soluție de dimensiuni uniforme este simetrică dacă fiecare componentă are formanu=2m{\ displaystyle n = 2m}{±vs.1,±vs.2,...,±vs.m}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}Soluția dată în introducere este de această formă.
• O soluție de dimensiuni impare este simetrică dacă componentele soluției sunt opuse, adicăLA={la1,la2,...,lanu}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} și B={-la1,-la2,...,-lanu}.{\ displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Soluții ideale și simetrice

Soluțiile ideale și simetrice sunt cunoscute pentru grade , cu excepția  : 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, \ pm 308 \}}

Această ultimă soluție este dată, împreună cu altele, în Borwein și colab. (2003) . Nu se cunoaște nicio soluție ideală . k=10{\ displaystyle k = 10}

O formulare algebrică

Există un mod mai algebric de a formula problema:

Propunere  -  Următoarele condiții sunt echivalente:

1. ∑eu=1nulaeuj=∑eu=1nubeuj,(j=1,...,k){\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} ^ {j} = \ sum _ {i = 1} ^ {n} b_ {i} ^ {j}, \ quad (j = 1, \ ldots, k)}
2. deg⁡(∏eu=1nu(X-laeu)-∏eu=1nu(X-beu))≤nu-(k+1){\ displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ dreapta) \ leq n- (k + 1)}
3. (X-1)k+1|∑eu=1nuXlaeu-∑eu=1nuXbeu.{\ displaystyle (x-1) ^ {k + 1} \ left | \ sum _ {i = 1} ^ {n} x ^ {a_ {i}} - \ sum _ {i = 1} ^ {n} x ^ {b_ {i}} \ right ..}

Note și referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „  Prouhet - Tarry - Escott problem  ” ( vezi lista autorilor ) .

Note

1. Borwein (2002) , p.  85
2. Soluție dată de Nuutti Kuosa, Jean-Charles Meyrignac și Chen Shuwen, în 1999, vezi Problema Prouhet-Tarry-Escott .
3. ME Prouhet, Memorie despre unele relații între puterile numerelor , CR Acad. Știință. Paris, seria I, vol. 33, 1851, p.  225 .
4. (în) Leonard Eugene Dickson , Istoria teoriei numerelor  (en) [ ediții detaliate ], zbor. 2, 1919, c. XXIV, p.  705-716 .
5. Wright (1959)
6. Borwein și Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk și Percival 2003
9. (în) Michael Filaseta și Maria Markovich , „  Newton polygons and the Prouhet-Tarry-Escott problem  ” , Journal of Number Theory , vol.  174, 2017, p.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) și Problema Prouhet-Tarry-Escott .
11. A se vedea Borwein și Ingalls (1944) pentru referințe.

Referințe

• (ro) Andreas Alpers și Robert Tijdeman , „  Problema bidimensională Prouhet-Tarry-Escott  ” , J. Number Theor. , vol.  123,2007, p.  403-412
• (ro) Peter Borwein , Excursii computaționale în analiză și teoria numerelor , New York / Berlin / Heidelberg, Springer , col.  „Cărți CMS în matematică”,2002, 220  p. ( ISBN  0-387-95444-9 , citit online )Capitolul 11: Problema Prouhet - Tarry - Escott (paginile 85-96) este dedicată problemei.
• (ro) Peter Borwein și Colin Ingalls , „  Problema Prouhet-Tarry-Escott revizuită  ” , profesor. Matematica. , vol.  40, n os  1-2,1994, p.  3-27 ( citiți online )
• (ro) Peter Borwein , Petr Lisonĕk și Colin Percival , „  Investigații computaționale ale problemei Prouhet-Tarry-Escott  ” , Math. Comp. , vol.  72, nr .  244,2003, p.  2063-2070 ( citiți online )
• (de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Recenzii matematice  0019638 )
• GH Hardy și EM Wright ( tradus  din engleză de F. Sauvageot), Introducere în teoria numerelor [„  O introducere în teoria numerelor  ”], Paris și Heidelberg, Vuibert și Springer,2007Secțiunea 20.5 „Teorema celor patru pătrate” tratează acest subiect. Secțiunile 21.9 „Problema lui Prouhet și Tarry: numărul  ” și 21.10, p. 423-427, sunt dedicate problemei Prouhet-Tarry.P(k,j){\ displaystyle P (k, j)}
• (ro) Edward M. Wright , „  Prouhet's 1851 solution of the Tarry-Escott problem of 1910  ” , Amer. Matematica. Lunar , vol.  66,Martie 1959, p.  199-201

Vezi și tu

Articole similare

• Suită Prouhet-Thue-Morse
• Conjectura lui Euler
• Teorema Erdős-Suranyi

linkuri externe

• (ro) Chen Shuwen, Problema Prouhet-Tarry-Escott
• (ro) Eric W. Weisstein , „  Problema Prouhet-Tarry-Escott  ” , pe MathWorld

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