Prouhet-Tarry-Escott probléma

A matematika , különösen a számelmélet és a kombinatorika , a probléma Prouhet-Tarry-Escott , hogy megtaláljuk az egyes integer , két és az egész minden, mint például: nem{\ displaystyle n}NÁL NÉL{\ displaystyle A}B{\ displaystyle B}nem{\ displaystyle n}

∑nál nél∈NÁL NÉLnál nélén=∑b∈Bbén{\ displaystyle \ sum _ {a \ in A} a ^ {i} = \ sum _ {b \ B} b ^ {i}}

minden egyes a akár egy adott egész szám . Ha és ellenőrizni ezeket a feltételeket, írunk . én{\ displaystyle i}1{\ displaystyle 1}k{\ displaystyle k}NÁL NÉL{\ displaystyle A}B{\ displaystyle B}NÁL NÉL=kB{\ displaystyle A = _ {k} B}

Minimális megoldást keresünk egy adott fokozatra . Ezt a még mindig nyitott problémát Eugène Prouhet nevezte el , aki 1851-ben tanulmányozta, valamint Gaston Tarry és Edward Brind Escott , akik az 1910-es évek elején fontolóra vették. nem{\ displaystyle n}k{\ displaystyle k}

A legnagyobb értéke , amelyekre tudjuk a megoldást IS . Megfelelő megoldást adnak a következő halmazok: k{\ displaystyle k}nem=k+1{\ displaystyle n = k + 1}k=11.{\ displaystyle k = 11}

NÁL NÉL={±22.,±61,±86,±127.,±140,±151} ,B={±35,±47,±94. o,±121,±146,±148}{\ displaystyle A = \ {\ pm 22, \ pm 61, \ pm 86, \ pm 127, \ pm 140, \ pm 151 \} \, qqad B = \ {\ pm 35, \ pm 47, \ pm 94, \ pm 121, \ pm 146, \ pm 148 \}}

Példa

A meghatározás egész száma a fok , az egész pedig a méret . Könnyű belátni, hogy bármilyen megoldás esetén van . Ezért minimális méretű megoldást keresünk. k{\ displaystyle k}nem{\ displaystyle n}nem>k{\ displaystyle n> k}

Méret és fokozat szempontjából mindkét készlet nem=6.{\ displaystyle n = 6}k=5.{\ displaystyle k = 5}

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

megoldást jelentenek a problémára, mivel:

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+5.2+6.2+16.2+17.2+22.2=1090=12+22+10.2+12.2+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+5.3+6.3+16.3+17.3+22.3=19998=13+23+10.3+12.3+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+5.4+6.4+16.4+17.4+22.4=385234=14+24+10.4+12.4+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.+5.5.+6.5.+16.5.+17.5.+22.5.=7632966=15.+25.+10.5.+12.5.+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ális megoldás az a megoldás, amelynek mérete megegyezik a +1 fokkal, ezért a fenti megoldás ideális.

Történelem

1851-ben, Eugène Prouhet okozott általánosabb elosztásának problémája az egész számok x 1-től n- m a n osztályok, úgy, hogy az összeget a hatásköre k -ths az egész számok az egyes osztályok azonos, a k = 0, 1 , ... az eljárás azt javasolja, összegek a számozási az osztályok 0 és n - 1, elbontására minden egész x - 1 számának bázis N , összefoglalva a számjegyek, hogy kiszámítja a fennmaradó R ezen összeg modulo n és hozzárendelése az x egész szám az r osztályig .

Abban az esetben, ha n = 2, akkor az x egész elhelyezése a 0 vagy 1 index két osztályának egyikében attól függően történik, hogy a Prouhet-Thue-Morse szekvencia x- edik tagja 0 vagy 1. Például az első 8 egész számok vannak elosztva: 1, 4, 6, 7 egyrészt, és a 2, 3, 5, 8 másrészt, és az összeget a hatásköre k -edik az egész számok a két osztály k = 2- ig egybeesik .

Leonard Eugene Dickson egy fejezetet szentel az ő története Számelmélet , hogy „  készletei egészek egyenlő összegű erőkkel  ” , és felsorolja a nem kevesebb, mint 70 cikket erről a témáról. Edward Maitland Wright történelmi cikkében megjegyzi, hogy Prouhet cikkét csak 1948-ban fedezték fel újra.

A legújabb fejleményeket Peter Borwein és társszerzői írják le ; lásd még Filaseta és Markovich cikkét. Kétdimenziós változatot tanulmányozott Alpers és Tijdeman (2007) .

Tulajdonságok és eredmények

• Ha a pár és egy fokozatú megoldás , akkor mindenki és az egész pár számáraNÁL NÉL={nál nél1,nál nél2,...,nál nélnem}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}B={b1,b2,...,bnem}{\ displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}k{\ displaystyle k}NEM≠0{\ displaystyle N \ neq 0}M{\ displaystyle M}NÁL NÉL′={NEMnál nél1+M,NEMnál nél2+M,...,NEMnál nélnem+M}etB′={NEMb1+M,NEMb2+M,...,NEMbnem+M}{\ displaystyle A '= \ {Na_ {1} + M, Na_ {2} + M, \ ldots, Na_ {n} + M \} \ quad {\ rm {és}} \ quad B' = \ {Nb_ {1} + M, Nb_ {2} + M, \ ldots, Nb_ {n} + M \}}még mindig azonos fokú megoldás. Tehát a megoldás{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 \}}is megadja a megoldást{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 \}.}Ez a megfigyelés lehetővé teszi a megoldások egységesítését, előírva például azt, hogy csak pozitív vagy nulla egész számokat tartalmaznak, és ez a nulla megjelenik bennük.
• Nem ismerünk minden fokozatra ideális megoldást, de tudjuk, hogy minden fokozatra létezik méretmegoldás .k{\ displaystyle k}nem≤k(k+1)/2+1{\ displaystyle n \ leq k (k + 1) / 2 + 1}
• Szimmetrikus megoldások: a megoldás az egyenletes méretű is szimmetrikus , ha minden egyes komponens az űrlapnem=2m{\ displaystyle n = 2m}{±vs.1,±vs.2,...,±vs.m}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}A bevezetőben megadott megoldás ilyen formájú.
• A páratlan méretű megoldás akkor szimmetrikus, ha az oldat komponensei ellentétesek, azazNÁL NÉL={nál nél1,nál nél2,...,nál nélnem}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} és B={-nál nél1,-nál nél2,...,-nál nélnem}.{\ displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Ideális és szimmetrikus megoldások

Ideális és szimmetrikus megoldások ismeretesek a fokozatokhoz , kivéve  : 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 \}}

Ez az utolsó megoldás másokkal együtt Borwein et al. (2003) . Nem ismert ideális megoldás . k=10.{\ displaystyle k = 10}

Algebrai megfogalmazás

Van egy algebrai módszer a probléma megfogalmazására:

Javaslat  -  A következő feltételek egyenértékűek:

1. ∑én=1nemnál nélénj=∑én=1nembénj,(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⁡(∏én=1nem(x-nál nélén)-∏én=1nem(x-bén))≤nem-(k+1){\ displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ jobbra) \ leq n- (k + 1)}
3. (x-1)k+1|∑én=1nemxnál nélén-∑én=1nemxbén.{\ displaystyle (x-1) ^ {k + 1} \ balra | \ sum _ {i = 1} ^ {n} x ^ {a_ {i}} - \ sum _ {i = 1} ^ {n} x ^ {b_ {i}} \ right ..}

Megjegyzések és hivatkozások

(en) Ez a cikk részben vagy egészben a „  Prouhet - Tarry - Escott probléma  ” című angol Wikipedia cikkből származik ( lásd a szerzők felsorolását ) .

Megjegyzések

1. Borwein (2002) , p.  85
2. Nuutti Kuosa , Jean-Charles Meyrignac és Chen Shuwen által 1999-ben adott megoldást lásd The Prouhet-Tarry-Escott probléma .
3. ME Prouhet, Emlékirat a számok hatalmának néhány kapcsolatáról , CR Acad. Sci. Párizs, I. sorozat, vol. 33., 1851, p.  225 .
4. (in) Leonard Eugene Dickson , History of the Theory of Numbers  (hu) [ részletek kiadásban ], repülés. 2, 1919, kb. XXIV . O.  705-716 .
5. Wright (1959)
6. Borwein és Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk és Percival 2003
9. (in) Michael Filaseta és Maria Markovich , "  Newton poligonok és a Prouhet-Tarry-Escott probléma  " , Journal of Number Theory , vol.  174, 2017, P.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) és The Prouhet-Tarry-Escott probléma .
11. Lásd Borwein és Ingalls (1944) hivatkozásokat.

Hivatkozások

• (en) Andreas Alpers és Robert Tijdeman , „  A kétdimenziós Prouhet-Tarry-Escott probléma  ” , J. Number Theor. , vol.  123,2007, P.  403-412
• (en) Peter Borwein , Számítástechnikai kirándulások az elemzésben és a számelméletben , New York / Berlin / Heidelberg, Springer , coll.  "CMS Books in Mathematics",2002, 220  p. ( ISBN  0-387-95444-9 , online olvasás )11. fejezet: A Prouhet - Tarry - Escott problémát ( 85–96. Oldal) a problémának szentelik.
• (en) Peter Borwein és Colin Ingalls , „  A Prouhet-Tarry-Escott probléma újra áttekintve  ” , tanár. Math. , vol.  40, n csont  1-2,1994, P.  3–27 ( online olvasás )
• (en) Peter Borwein , Petr Lisonĕk és Colin Percival , „  Computational vizsgálatok a Prouhet-Tarry-Escott probléma  ” , Math. Comp. , vol.  72, n o  244,2003, P.  2063-2070 ( online olvasás )
• de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Matematikai vélemények  0019638 )
• GH Hardy és EM Wright (  angol fordítás : F. Sauvageot), Bevezetés a számok elméletébe [“  Bevezetés a számok elméletébe  ”], Párizs és Heidelberg, Vuibert és Springer,2007A 20.5. Szakasz „A négy négyzet tétel” foglalkozik ezzel a témával. 21.9. Szakasz: „Prouhet és Tarry problémája: a szám  ” és 21.10. 423–427., Prouhet-Tarry problémájának szentelik.P(k,j){\ displaystyle P (k, j)}
• (en) Edward M. Wright , „  Prouhet 1851-es megoldása az 1910-es Tarry-Escott-problémára  ” , Amer. Math. Havi , vol.  66,1959. március, P.  199-201

Lásd is

Kapcsolódó cikkek

• Prouhet-Thue-Morse lakosztály
• Euler sejtése
• Erdős-Suranyi tétel

Külső linkek

• (en) Chen Shuwen, A Prouhet-Tarry-Escott probléma
• (en) Eric W. Weisstein , „  Prouhet-Tarry-Escott probléma  ” , a MathWorld- on

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