Problema di Prouhet-Tarry-Escott

In matematica , specialmente nella teoria dei numeri e nella combinatoria , il problema di Prouhet-Tarry-Escott è trovare, per ogni numero intero , due insiemi e di numeri interi ciascuno, come: non{\ displaystyle n}A{\ displaystyle A}B{\ displaystyle B}non{\ displaystyle n}

∑a∈Aaio=∑b∈Bbio{\ Displaystyle \ sum _ {a \ in A} a ^ {i} = \ sum _ {b \ in B} b ^ {i}}

per ciascuno di fino a un determinato numero intero . Se e verifichi queste condizioni, scriviamo . io{\ displaystyle i}1{\ displaystyle 1}K{\ displaystyle k}A{\ displaystyle A}B{\ displaystyle B}A=KB{\ displaystyle A = _ {k} B}

Cerchiamo una soluzione di dimensione minima per un dato grado . Questo problema ancora aperto prende il nome da Eugène Prouhet , che lo studiò nel 1851, e da Gaston Tarry e Edward Brind Escott, che lo considerarono all'inizio degli anni '10. non{\ displaystyle n}K{\ displaystyle k}

Il valore più grande per il quale conosciamo una soluzione è . Una soluzione corrispondente è data dai seguenti insiemi: K{\ displaystyle k}non=K+1{\ displaystyle n = k + 1}K=11{\ displaystyle k = 11}

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

Esempio

L'intero della definizione è il grado e l'intero è la dimensione . È facile vedere che per qualsiasi soluzione, abbiamo . Cerchiamo quindi una soluzione di minimo ingombro. K{\ displaystyle k}non{\ displaystyle n}non>K{\ displaystyle n> k}

Per taglia e grado , entrambi i set non=6{\ displaystyle n = 6}K=5{\ displaystyle k = 5}

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

sono una soluzione del problema, poiché:

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

Una soluzione ideale è una soluzione la cui dimensione è pari al grado +1, la soluzione di cui sopra è quindi ideale.

Storia

Nel 1851, Eugène Prouhet posto il problema più generale della divisione interi x da 1 a n m in n classi, in modo che la somma delle potenze k -ths degli interi di ciascuna classe è la stessa, per k = 0, 1 , ... Il processo che propone consiste nel numerare le classi da 0 an - 1, scomporre ogni intero x - 1 nella base numerica n , sommare le sue cifre, calcolare il resto r di questa somma modulo n e assegna l'intero x alla classe r .

Nel caso in cui n = 2, il posizionamento dell'intero x in una delle due classi di indice 0 o 1 è fatto a seconda che il termine x -esimo della sequenza Prouhet-Thue-Morse sia 0 o 1 Ad esempio, i primi 8 numeri interi sono divisi in: 1, 4, 6, 7 da un lato e 2, 3, 5, 8 dall'altro, e la somma delle potenze k -esima degli interi di queste due classi coincide fino a che k = 2.

Leonard Eugene Dickson dedica un capitolo della sua Storia della teoria dei numeri a "  Insiemi di numeri interi con uguali somme di poteri simili  " ed elenca non meno di 70 articoli su questo argomento. Nel suo articolo storico, Edward Maitland Wright osserva che l'articolo di Prouhet non fu riscoperto fino al 1948.

Gli sviluppi recenti sono descritti da Peter Borwein e dai suoi coautori; vedi anche l'articolo di Filaseta e Markovich. Una versione bidimensionale è stata studiata da Alpers e Tijdeman (2007) .

Proprietà e risultati

• Se la coppia ed è una soluzione di laurea , allora per tutti e per tutta la coppiaA={a1,a2,...,anon}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}B={b1,b2,...,bnon}{\ displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}K{\ displaystyle k}NON≠0{\ displaystyle N \ neq 0}M{\ displaystyle M}A′={NONa1+M,NONa2+M,...,NONanon+M}etB′={NONb1+M,NONb2+M,...,NONbnon+M}{\ displaystyle A '= \ {Na_ {1} + M, Na_ {2} + M, \ ldots, Na_ {n} + M \} \ quad {\ rm {e}} \ quad B' = \ {Nb_ {1} + M, Nb_ {2} + M, \ ldots, Nb_ {n} + M \}}è ancora una soluzione dello stesso grado. Quindi la soluzione{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 \}}dà anche la soluzione{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 \}.}Questa osservazione permette di standardizzare le soluzioni, imponendo ad esempio che contengano solo numeri interi positivi o nulli, e che in esse compaia zero.
• Non conosciamo una soluzione ideale per ogni grado, ma sappiamo che per ogni grado esiste una soluzione di dimensione .K{\ displaystyle k}non≤K(K+1)/2+1{\ Displaystyle n \ leq k (k + 1) / 2 + 1}
• Soluzioni simmetriche: una soluzione di dimensione pari è simmetrica se ogni componente è della formanon=2m{\ displaystyle n = 2 m}{±vs1,±vs2,...,±vsm}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}La soluzione data nell'introduzione è di questa forma.
• Una soluzione di dimensioni dispari è simmetrica se i componenti della soluzione sono opposti, ad es.A={a1,a2,...,anon}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} e B={-a1,-a2,...,-anon}.{\ displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Soluzioni ideali e simmetriche

Le soluzioni ideali e simmetriche sono note per i gradi , ad eccezione di  : 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 \}}

Quest'ultima soluzione è data, insieme ad altre, in Borwein et al. (2003) . Nessuna soluzione ideale è nota . K=10{\ displaystyle k = 10}

Una formulazione algebrica

C'è un modo più algebrico per formulare il problema:

Proposta  -  Le seguenti condizioni sono equivalenti:

1. ∑io=1nonaioj=∑io=1nonbioj,(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⁡(∏io=1non(X-aio)-∏io=1non(X-bio))≤non-(K+1){\ Displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ destra) \ leq n- (k + 1)}
3. (X-1)K+1|∑io=1nonXaio-∑io=1nonXbio.{\ displaystyle (x-1) ^ {k + 1} \ left | \ sum _ {i = 1} ^ {n} x ^ {a_ {i}} - \ sum _ {i = 1} ^ {n} x ^ {b_ {i}} \ right ..}

Note e riferimenti

(it) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato “  Problema Prouhet - Tarry - Escott  ” ( vedere l'elenco degli autori ) .

Appunti

1. Borwein (2002) , p.  85
2. Soluzione data da Nuutti Kuosa, Jean-Charles Meyrignac e Chen Shuwen, nel 1999, vedi The Prouhet-Tarry-Escott problem .
3. ME Prouhet, Memoir su alcune relazioni tra i poteri dei numeri , CR Acad. Sci. Parigi, serie I, vol. 33, 1851, p.  225 .
4. (in) Leonard Eugene Dickson , History of the Theory of Numbers  (en) [ edizioni dettagliate ], volo. 2, 1919, c. XXIV, p.  705-716 .
5. Wright (1959)
6. Borwein e Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk e Percival 2003
9. (in) Michael Filaseta e Maria Markovich , "I  poligoni di Newton e il problema di Prouhet-Tarry-Escott  " , Journal of Number Theory , vol.  174, 2017, p.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) e The Prouhet-Tarry-Escott problem .
11. Vedi Borwein e Ingalls (1944) per i riferimenti.

Riferimenti

• (it) Andreas Alpers e Robert Tijdeman , "  Il problema bidimensionale di Prouhet-Tarry-Escott  " , J. Number Theor. , vol.  123,2007, p.  403-412
• (en) Peter Borwein , Escursioni computazionali in analisi e teoria dei numeri , New York / Berlino / Heidelberg, Springer , coll.  "Libri CMS in matematica",2002, 220  p. ( ISBN  0-387-95444-9 , leggi online )Il Capitolo 11: Il problema Prouhet - Tarry - Escott (pagine 85-96) è dedicato al problema.
• (it) Peter Borwein e Colin Ingalls , "  Il problema di Prouhet-Tarry-Escott rivisitato  " , Insegnante. Matematica. , vol.  40, n osso  1-2,1994, p.  3-27 ( leggi online )
• (it) Peter Borwein , Petr Lisonĕk e Colin Percival , "  Indagini computazionali del problema di Prouhet-Tarry-Escott  " , Math. Comp. , vol.  72, n o  244,2003, p.  2063-2070 ( leggi in linea )
• (de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Recensioni di matematica  0019638 )
• GH Hardy e EM Wright ( tradotto  dall'inglese da F. Sauvageot), Introduzione alla teoria dei numeri ["  Un'introduzione alla teoria dei numeri  "], Parigi e Heidelberg, Vuibert e Springer,2007La sezione 20.5 "Il teorema dei quattro quadrati" tratta questo argomento. Sezioni 21.9 "Il problema di Prouhet e Tarry: il numero  " e 21.10, p. 423-427, sono dedicati al problema di Prouhet-Tarry.P(K,j){\ displaystyle P (k, j)}
• (it) Edward M. Wright , "  La soluzione di Prouhet del 1851 del problema di Tarry-Escott del 1910  " , Amer. Matematica. Mensile , vol.  66,Marzo 1959, p.  199-201

Vedi anche

Articoli Correlati

• Suite Prouhet-Thue-Morse
• Congettura di Eulero
• Teorema di Erdős-Suranyi

link esterno

• (it) Chen Shuwen, Il problema Prouhet-Tarry-Escott
• (it) Eric W. Weisstein , "  Prouhet-Tarry-Escott problem  " , su MathWorld

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