Prouhet-Tarry-Escott problém

V matematiky , zejména v teorii čísel a kombinatorika je problém Prouhet-Tarry-Escott je najít, pro každé celé číslo , dvě sady a z celých čísel každý, jako jsou: ne{\ displaystyle n}NA{\ displaystyle A}B{\ displaystyle B}ne{\ displaystyle n}

∑na∈NAnai=∑b∈Bbi{\ displaystyle \ sum _ {a \ v A} a ^ {i} = \ sum _ {b \ v B} b ^ {i}}

pro každý z až do určité celé číslo . Pokud a ověříme tyto podmínky, píšeme . i{\ displaystyle i}1{\ displaystyle 1}k{\ displaystyle k}NA{\ displaystyle A}B{\ displaystyle B}NA=kB{\ displaystyle A = _ {k} B}

Hledáme řešení minimální velikosti pro daný titul . Tento stále otevřený problém je pojmenován podle Eugèna Prouheta , který jej studoval v roce 1851, a Gastona Tarryho a Edwarda Brinda Escotta, kteří o něm uvažovali počátkem 10. let 20. století. ne{\ displaystyle n}k{\ displaystyle k}

Největší hodnota, pro kterou známe řešení, je . Odpovídající řešení je dáno následujícími sadami: k{\ displaystyle k}ne=k+1{\ displaystyle n = k + 1}k=11{\ displaystyle k = 11}

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

Příklad

Celé číslo definice je stupeň a celé číslo je velikost . Je snadné vidět, že pro každé řešení máme . Hledáme proto řešení minimální velikosti. k{\ displaystyle k}ne{\ displaystyle n}ne>k{\ displaystyle n> k}

Pro velikost a stupeň obě sady ne=6{\ displaystyle n = 6}k=5{\ displaystyle k = 5}

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

jsou řešením problému, protože:

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

Ideálním řešením je řešení, jehož velikost se rovná stupni +1. Výše ​​uvedené řešení je proto ideální.

Dějiny

V roce 1851 představil Eugène Prouhet obecnější problém distribuce celých čísel x od 1 do n m do n tříd, takže součet mocnin k- th celých čísel každé třídy je stejný, pro k = 0, 1 , ... Proces, který navrhuje, spočívá v číslování tříd od 0 do n - 1, k rozložení každého celého čísla x - 1 v číselné bázi n , sečtením jeho číslic, k výpočtu zbytku r tohoto součtu modulo n a přiřadit celé číslo x třídě r .

V případě, že n = 2, je umístění celého čísla x do jedné ze dvou tříd indexu 0 nebo 1 provedeno podle toho, zda je x -tý člen sekvence Prouhet-Thue-Morse 0 nebo 1. prvních 8 celých čísel je distribuováno v: 1, 4, 6, 7 na jedné straně a ve 2, 3, 5, 8 na druhé straně a součtu mocnin k -tý celých čísel těchto dvou tříd shodovat, dokud k = 2.

Leonard Eugene Dickson věnuje jednu kapitolu své historie teorie čísel pro „  Sady čísel se stejnými částkami jako síly  “ , a seznamy ne méně než 70 článků na toto téma. Edward Maitland Wright ve svém historickém článku uvádí, že Prouhetův článek byl znovuobjeven až v roce 1948.

Nedávný vývoj popisuje Peter Borwein a jeho spoluautoři; viz také článek Filasety a Markovicha. Dvojrozměrnou verzi studovali Alpers a Tijdeman (2007) .

Vlastnosti a výsledky

• Pokud je pár a je diplomovým řešením , pak pro všechny a pro všechny páryNA={na1,na2,...,nane}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}B={b1,b2,...,bne}{\ displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}k{\ displaystyle k}NE≠0{\ displaystyle N \ neq 0}M{\ displaystyle M}NA′={NEna1+M,NEna2+M,...,NEnane+M}EtB′={NEb1+M,NEb2+M,...,NEbne+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 \}}je stále řešením stejného stupně. Takže řešení{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 \}}také dává řešení{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 \}.}Toto pozorování umožňuje standardizovat řešení, například tím, že stanoví, že obsahují pouze kladná nebo nulová celá čísla, a že se v nich objeví nula.
• Neznáme ideální řešení pro každý stupeň, ale víme, že pro každý stupeň existuje řešení velikosti .k{\ displaystyle k}ne≤k(k+1)/2+1{\ Displaystyle n \ leq k (k + 1) / 2 + 1}
• Symetrická řešení: řešení sudé velikosti je symetrické, pokud je každá složka ve tvarune=2m{\ displaystyle n = 2 m}{±vs.1,±vs.2,...,±vs.m}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}Řešení uvedené v úvodu má tuto formu.
• Liché řešení je symetrické, pokud jsou komponenty řešení opačné, tj.NA={na1,na2,...,nane}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} a B={-na1,-na2,...,-nane}.{\ displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Ideální a symetrické řešení

Ideální a symetrická řešení jsou známa pro stupně , kromě  : 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, \ 308 hodin

Toto poslední řešení je uvedeno spolu s dalšími v Borwein et al. (2003) . Není známo žádné ideální řešení . k=10{\ displaystyle k = 10}

Algebraická formulace

Existuje více algebraický způsob formulování problému:

Návrh  -  Následující podmínky jsou rovnocenné:

1. ∑i=1nenaij=∑i=1nebij,(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⁡(∏i=1ne(X-nai)-∏i=1ne(X-bi))≤ne-(k+1){\ displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ vpravo) \ leq n- (k + 1)}
3. (X-1)k+1|∑i=1neXnai-∑i=1neXbi.{\ displaystyle (x-1) ^ {k + 1} \ vlevo | \ sum _ {i = 1} ^ {n} x ^ {a_ {i}} - \ sum _ {i = 1} ^ {n} x ^ {b_ {i}} \ vpravo ..}

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „  Prouhet - Tarry - Escott problém  “ ( viz seznam autorů ) .

Poznámky

1. Borwein (2002) , str.  85
2. Řešení poskytnuté Nuuttim Kuosou, Jean-Charlesem Meyrignacem a Chen Shuwenem v roce 1999, viz problém Prouhet-Tarry-Escott .
3. ME Prouhet, Monografie o některých vztazích mezi mocnostmi čísel , CR Acad. Sci. Paříž, řada I, sv. 33, 1851, str.  225 .
4. (in) Leonard Eugene Dickson , History of the Theory of Numbers  (en) [ podrobná vydání ], let. 2, 1919, c. XXIV, s.  705-716 .
5. Wright (1959)
6. Borwein a Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk a Percival 2003
9. (in) Michael Filaseta a Maria Markovich , „  Newtonovy polygony a Prouhet-Tarry-Escottův problém  “ , Journal of Number Theory , sv.  174, 2017, str.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) a problém Prouhet-Tarry-Escott .
11. Reference viz Borwein a Ingalls (1944) .

Reference

• (en) Andreas Alpers a Robert Tijdeman , „  Dvojrozměrný problém Prouhet-Tarry-Escott  “ , J. Number Theor. , sv.  123,2007, str.  403-412
• (en) Peter Borwein , Výpočetní exkurze v analýze a teorii čísel , New York / Berlín / Heidelberg, Springer , kol.  "CMS Books in Mathematics",2002, 220  s. ( ISBN  0-387-95444-9 , číst online )Kapitola 11: Problém Prouhet - Tarry - Escott (strany 85-96) je věnována problému.
• (en) Peter Borwein a Colin Ingalls , „  Prouhet-Tarry-Escottův problém se vrátil  “ , učitel. Matematika. , sv.  40, n kost  1-2,1994, str.  3-27 ( číst online )
• (en) Peter Borwein , Petr Lisonĕk a Colin Percival , „  Výpočetní vyšetřování problému Prouhet-Tarry-Escott  “ , Math. Comp. , sv.  72, n o  244,2003, str.  2063-2070 ( číst online )
• (de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Matematické recenze  0019638 )
• GH Hardy a EM Wright ( přeloženo  z angličtiny F. Sauvageotem), Úvod do teorie čísel [„  Úvod do teorie čísel  “], Paříž a Heidelberg, Vuibert a Springer,2007Tomuto tématu se věnuje část 20.5 „Věta o čtyřech čtvercích“. Sekce 21.9 „Problém Prouheta a Tarryho: počet  “ a 21.10, s. 423-427, jsou věnovány problému Prouhet-Tarryho.P(k,j){\ displaystyle P (k, j)}
• (en) Edward M. Wright , „  Prouhetovo řešení problému Tarry-Escott z roku 1910 z roku 1851  “ , Amer. Matematika. Měsíčně , sv.  66,Březen 1959, str.  199-201

Podívejte se také

Související články

• Apartmá Prouhet-Thue-Morse
• Eulerova domněnka
• Erdős-Suranyiova věta

externí odkazy

• (en) Chen Shuwen, problém Prouhet-Tarry-Escott
• (en) Eric W. Weisstein , „  Prouhet-Tarry-Escott problém  “ , 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;">