Prouhet-Tarry-Escott problem

I matematikk , spesielt innen tallteori og kombinatorikk , er problemet Prouhet-Tarry-Escott å finne, for hvert heltall , to sett og med heltall hver, for eksempel: ikke{\ displaystyle n}PÅ{\ displaystyle A}B{\ displaystyle B}ikke{\ displaystyle n}

∑på∈PÅpåJeg=∑b∈BbJeg{\ displaystyle \ sum _ {a \ in A} a ^ {i} = \ sum _ {b \ in B} b ^ {i}}

for hvert av opptil et gitt heltall . Hvis og verifiserer disse forholdene, skriver vi . Jeg{\ displaystyle i}1{\ displaystyle 1}k{\ displaystyle k}PÅ{\ displaystyle A}B{\ displaystyle B}PÅ=kB{\ displaystyle A = _ {k} B}

Vi ser etter en løsning av minimumsstørrelse for en gitt grad . Dette fortsatt åpne problemet er oppkalt etter Eugène Prouhet , som studerte det i 1851, og Gaston Tarry og Edward Brind Escott, som vurderte det tidlig på 1910-tallet. ikke{\ displaystyle n}k{\ displaystyle k}

Den største verdien vi kjenner en løsning med er . En tilsvarende løsning er gitt av følgende sett: k{\ displaystyle k}ikke=k+1{\ displaystyle n = k + 1}k=11{\ displaystyle k = 11}

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

Eksempel

Heltallet av definisjonen er graden , og heltallet er størrelsen . Det er lett å se at det har vi for enhver løsning . Vi ser derfor etter en løsning av minimumsstørrelse. k{\ displaystyle k}ikke{\ displaystyle n}ikke>k{\ displaystyle n> k}

For størrelse og grad , begge settene ikke=6{\ displaystyle n = 6}k=5{\ displaystyle k = 5}

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

er en løsning på problemet, siden:

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

En ideell løsning er en løsning hvis størrelse er lik grad +1. Løsningen ovenfor er derfor ideell.

Historie

I 1851, Eugène Prouhet utgjøres den mer generelle problemet med en inndeling av hele tall x fra 1 til n m i n klasser, slik at summen av kreftene k -ths av de hele tall hver klasse er den samme, for k = 0, 1 , ... Prosessen han foreslår tilsvarer å nummerere klassene fra 0 til n - 1, for å spalte hvert heltall x - 1 i tallbasen n , for å legge sammen sifrene, for å beregne resten r av denne summodulen n og tilordne heltallet x til klassen r .

I tilfelle der n = 2, blir plasseringen av heltallet x i en av de to klassene med indeks 0 eller 1 gjort i henhold til om den x- th-termen til Prouhet-Thue-Morse-sekvensen er 0 eller 1. For eksempel, de første 8 heltallene er delt inn i: 1, 4, 6, 7 på den ene siden og 2, 3, 5, 8 på den andre siden, og summen av kreftene k- th av heltallene i disse to klassene sammenfaller til k = 2.

Leonard Eugene Dickson viet et kapittel av sin History of Number Theory til "  Sets of integers with like sums of like powers  " , og lister opp ikke mindre enn 70 artikler om dette emnet. I sin historiske artikkel bemerker Edward Maitland Wright at artikkelen til Prouhet ikke ble gjenoppdaget før 1948.

Nyere utvikling er beskrevet av Peter Borwein og hans medforfattere; se også artikkelen til Filaseta og Markovich. En todimensjonal versjon er studert av Alpers og Tijdeman (2007) .

Egenskaper og resultater

• Hvis paret og er en grad løsning , så for alle og alle paretPÅ={på1,på2,...,påikke}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}B={b1,b2,...,bikke}{\ displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}k{\ displaystyle k}IKKE≠0{\ displaystyle N \ neq 0}M{\ displaystyle M}PÅ′={IKKEpå1+M,IKKEpå2+M,...,IKKEpåikke+M}etB′={IKKEb1+M,IKKEb2+M,...,IKKEbikke+M}{\ displaystyle A '= \ {Na_ {1} + M, Na_ {2} + M, \ ldots, Na_ {n} + M \} \ quad {\ rm {and}} \ quad B' = \ {Nb_ {1} + M, Nb_ {2} + M, \ ldots, Nb_ {n} + M \}}er fremdeles en løsning i samme grad. Så løsningen{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 \}}gir også løsningen{1,6,7,17,18,23}=5{2,3,11,1. 3,21,22}.{\ displaystyle \ {1,6,7,17,18,23 \} = _ {5} \ {2,3,11,13,21,22 \}.}Denne observasjonen gjør det mulig å standardisere løsningene ved å for eksempel pålegge at de bare inneholder positive eller null heltall, og at null vises i dem.
• Vi kjenner ikke en ideell løsning for hver grad, men vi vet at det for hver grad finnes en løsning av størrelse .k{\ displaystyle k}ikke≤k(k+1)/2+1{\ displaystyle n \ leq k (k + 1) / 2 + 1}
• Symmetriske løsninger: en løsning med jevn størrelse er symmetrisk hvis hver komponent har formenikke=2m{\ displaystyle n = 2m}{±vs.1,±vs.2,...,±vs.m}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}Løsningen gitt i innledningen er av dette skjemaet.
• En odd-sized løsning er symmetrisk hvis komponentene i løsningen er motsatte, dvs.PÅ={på1,på2,...,påikke}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} og B={-på1,-på2,...,-påikke}.{\ displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Ideelle og symmetriske løsninger

Ideelle og symmetriske løsninger er kjent for grader , bortsett fra  : 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,±1. 3}=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,1. 3,38,50}=6{51,33,24,-7,-1. 3,-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,1. 3,16,69,75,99}=8{98,82,58,34,-1. 3,-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 \}}

Denne siste løsningen er gitt sammen med andre i Borwein et al. (2003) . Ingen ideelle løsninger er kjent for . k=10{\ displaystyle k = 10}

En algebraisk formulering

Det er en mer algebraisk måte å formulere problemet på:

Forslag  -  Følgende betingelser er likeverdige:

1. ∑Jeg=1ikkepåJegj=∑Jeg=1ikkebJegj,(j=1,...,k){\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} ^ {j} = \ sum _ {i = 1} ^ {n} b_ {i} ^ {j}, \ quad (j = 1, \ ldots, k)}
2. grader⁡(∏Jeg=1ikke(x-påJeg)-∏Jeg=1ikke(x-bJeg))≤ikke-(k+1){\ displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ høyre) \ leq n- (k + 1)}
3. (x-1)k+1|∑Jeg=1ikkexpåJeg-∑Jeg=1ikkexbJeg.{\ displaystyle (x-1) ^ {k + 1} \ left | \ sum _ {i = 1} ^ {n} x ^ {a_ {i}} - \ sum _ {i = 1} ^ {n} x ^ {b_ {i}} \ høyre ..}

Merknader og referanser

(fr) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen “  Prouhet - Tarry - Escott problem  ” ( se listen over forfattere ) .

Merknader

1. Borwein (2002) , s.  85
2. Solution gitt av Nuutti Kuosa, Jean-Charles Meyrignac og Chen Shuwen, i 1999, se The Prouhet-Tarry-Escott problem .
3. ME Prouhet, Memoir on some relations between the powers of numbers , CR Acad. Sci. Paris, serie I, vol. 33, 1851, s.  225 .
4. (in) Leonard Eugene Dickson , History of the Theory of Numbers  (no) [ detaljutgaver ], flygning. 2, 1919, c. XXIV, s.  705-716 .
5. Wright (1959)
6. Borwein og Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk og Percival 2003
9. (in) Michael Filaseta og Maria Markovich , "  Newton polygoner and the Prouhet-Tarry-Escott problem  " , Journal of Number Theory , vol.  174, 2017, s.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) og problemet Prouhet-Tarry-Escott .
11. Se Borwein og Ingalls (1944) for referanser.

Referanser

• (no) Andreas Alpers og Robert Tijdeman , “  The two-dimensional Prouhet-Tarry-Escott problem  ” , J. Number Theor. , vol.  123,2007, s.  403-412
• (en) Peter Borwein , Computational Excursions in Analysis and Number Theory , New York / Berlin / Heidelberg, Springer , koll.  "CMS Books in Mathematics",2002, 220  s. ( ISBN  0-387-95444-9 , les online )Kapittel 11: Prouhet - Tarry - Escott-problemet (side 85-96) er viet til problemet.
• (en) Peter Borwein og Colin Ingalls , "  Prouhet-Tarry-Escott-problemet revisited  " , lærer. Matte. , vol.  40, n bein  1-2,1994, s.  3-27 ( les online )
• (en) Peter Borwein , Petr Lisonĕk og Colin Percival , "  Computational investigations of the Prouhet-Tarry-Escott problem  " , Math. Komp. , vol.  72, n o  244,2003, s.  2063-2070 ( les online )
• (de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Matematikkanmeldelser  0019638 )
• GH Hardy og EM Wright ( oversatt  fra engelsk av F. Sauvageot), Introduksjon til tallteorien ["  En introduksjon til teorien om tall  "], Paris og Heidelberg, Vuibert og Springer,2007Avsnitt 20.5 "The Four Squares Theorem" tar for seg dette emnet. Avsnitt 21.9 “Problemet med Prouhet og Tarry: tallet  ” og 21.10, s. 423-427, er viet til problemet med Prouhet-Tarry.P(k,j){\ displaystyle P (k, j)}
• (en) Edward M. Wright , "  Prouhet's 1851-løsning av Tarry-Escott-problemet i 1910  " , Amer. Matte. Månedlig , vol.  66,Mars 1959, s.  199-201

Se også

Relaterte artikler

• Prouhet-Thue-Morse-suite
• Eulers antagelse
• Erdős-Suranyi-setning

Eksterne linker

• (no) Chen Shuwen, Prouhet-Tarry-Escott-problemet
• (no) Eric W. Weisstein , “  Prouhet-Tarry-Escott problem  ” , på MathWorld

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