Problema de Prouhet-Tarry-Escott

En matemáticas , especialmente en teoría de números y combinatoria , el problema Prouhet-Tarry-Escott es encontrar, para cada número entero , dos conjuntos y de números enteros cada uno, tales como: no{\ Displaystyle n}A{\ Displaystyle A}B{\ Displaystyle B}no{\ Displaystyle n}

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

para cada uno de hasta un número entero determinado. Si y verificamos estas condiciones, escribimos . I{\ Displaystyle i}1{\ Displaystyle 1}k{\ Displaystyle k}A{\ Displaystyle A}B{\ Displaystyle B}A=kB{\ Displaystyle A = _ {k} B}

Buscamos una solución de tamaño mínimo para una titulación determinada. Este problema aún abierto lleva el nombre de Eugène Prouhet , quien lo estudió en 1851, y Gaston Tarry y Edward Brind Escott, quienes lo consideraron a principios de la década de 1910. no{\ Displaystyle n}k{\ Displaystyle k}

El mayor valor del que conocemos una solución es . Una solución correspondiente viene dada por los siguientes conjuntos: k{\ Displaystyle k}no=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 \}}

Ejemplo

El número entero de la definición es el grado y el número entero es el tamaño . Es fácil ver que para cualquier solución, tenemos . Por tanto, buscamos una solución de tamaño mínimo. k{\ Displaystyle k}no{\ Displaystyle n}no>k{\ Displaystyle n> k}

Por tamaño y grado , ambos conjuntos no=6{\ Displaystyle n = 6}k=5{\ Displaystyle k = 5}

{0,5,6,dieciséis,17,22}{\ Displaystyle \ {0,5,6,16,17,22 \}} y {1,2,10,12,20,21}{\ Displaystyle \ {1,2,10,12,20,21 \}}

son una solución del problema, ya que:

0+5+6+dieciséis+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+dieciséis2+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+dieciséis3+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+dieciséis4+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+dieciséis5+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 solución ideal es una solución cuyo tamaño es igual al grado +1. Por lo tanto, la solución anterior es ideal.

Historia

En 1851, Eugène Prouhet planteó el problema más general de la distribución de los números enteros x de 1 a n m en n clases, de modo que la suma de las potencias k -ths de los números enteros de cada clase es el mismo, para k = 0, 1 , ... el método que propone cantidades a numerar las clases de 0 a n - 1, para descomponer cada entero x - 1 en el número de base n , para sumar sus dígitos, para calcular el resto r de esta suma módulo n y asigne el entero x a la clase r .

En el caso donde n = 2, la ubicación del número entero x en una de las dos clases de índice 0 o 1 se realiza según si el término x -ésimo de la secuencia Prouhet-Thue-Morse es 0 o 1 Por ejemplo, los primeros 8 enteros se dividen en: 1, 4, 6, 7 por un lado, y 2, 3, 5, 8 por otro lado, y la suma de las potencias k -ésimas de los enteros de estas dos clases coinciden hasta k = 2.

Leonard Eugene Dickson dedica un capítulo de su Historia de la teoría de números a "  Conjuntos de enteros con sumas iguales de potencias similares  " , y enumera no menos de 70 artículos sobre este tema. En su artículo histórico, Edward Maitland Wright señala que el artículo de Prouhet no fue redescubierto hasta 1948.

Peter Borwein y sus coautores describen los desarrollos recientes ; véase también el artículo de Filaseta y Markovich. Alpers y Tijdeman (2007) han estudiado una versión bidimensional .

Propiedades y resultados

• Si la pareja y es una solución de grado , entonces para todos y para todos los noviosA={a1,a2,...,ano}{\ Displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}B={B1,B2,...,Bno}{\ Displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}k{\ Displaystyle k}NO≠0{\ Displaystyle N \ neq 0}METRO{\ Displaystyle M}A′={NOa1+METRO,NOa2+METRO,...,NOano+METRO}mitB′={NOB1+METRO,NOB2+METRO,...,NOBno+METRO}{\ Displaystyle A '= \ {Na_ {1} + M, Na_ {2} + M, \ ldots, Na_ {n} + M \} \ quad {\ rm {y}} \ quad B' = \ {Nb_ {1} + M, Nb_ {2} + M, \ ldots, Nb_ {n} + M \}}sigue siendo una solución del mismo grado. Entonces la solucion{0,5,6,dieciséis,17,22}=5{1,2,10,12,20,21}{\ Displaystyle \ {0,5,6,16,17,22 \} = _ {5} \ {1,2,10,12,20,21 \}}también da la solución{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 \}.}Esta observación permite estandarizar las soluciones, imponiendo por ejemplo que contengan solo enteros positivos o cero, y que aparezca cero en ellas.
• No conocemos una solución ideal para cada titulación, pero sabemos que para cada titulación hay una solución de tamaño .k{\ Displaystyle k}no≤k(k+1)/2+1{\ Displaystyle n \ leq k (k + 1) / 2 + 1}
• Soluciones simétricas: una solución de tamaño par es simétrica si cada componente tiene la formano=2metro{\ Displaystyle n = 2m}{±vs1,±vs2,...,±vsmetro}.{\ Displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}La solución dada en la introducción es de esta forma.
• Una solución de tamaño impar es simétrica si los componentes de la solución son opuestos, es decir,A={a1,a2,...,ano}{\ Displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}} y B={-a1,-a2,...,-ano}.{\ Displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}

Soluciones ideales y simétricas

Las soluciones ideales y simétricas se conocen por grados , excepto por  : 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,±dieciséis,±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,dieciséis,69,75,99}=8{98,82,58,34,-13,-dieciséis,-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 \}}

Esta última solución se da, junto con otras, en Borwein et al. (2003) . No se conoce ninguna solución ideal . k=10{\ Displaystyle k = 10}

Una formulación algebraica

Hay una forma más algebraica de formular el problema:

Propuesta  -  Las siguientes condiciones son equivalentes:

1. ∑I=1noaIj=∑I=1noBIj,(j=1,...,k){\ Displaystyle \ sum _ {i = 1} ^ {n} a_ {i} ^ {j} = \ sum _ {i = 1} ^ {n} b_ {i} ^ {j}, \ quad (j = 1, \ ldots, k)}
2. grados⁡(∏I=1no(X-aI)-∏I=1no(X-BI))≤no-(k+1){\ Displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ derecha) \ leq n- (k + 1)}
3. (X-1)k+1|∑I=1noXaI-∑I=1noXBI.{\ Displaystyle (x-1) ^ {k + 1} \ left | \ sum _ {i = 1} ^ {n} x ^ {a_ {i}} - \ sum _ {i = 1} ^ {n} x ^ {b_ {i}} \ right ..}

Notas y referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado “  Problema de Prouhet - Tarry - Escott  ” ( ver la lista de autores ) .

Notas

1. Borwein (2002) , p.  85
2. Solución dada por Nuutti Kuosa, Jean-Charles Meyrignac y Chen Shuwen, en 1999, ver El problema de Prouhet-Tarry-Escott .
3. ME Prouhet, Memorias sobre algunas relaciones entre los poderes de los números , CR Acad. Sci. París, serie I, vol. 33, 1851, pág.  225 .
4. (en) Leonard Eugene Dickson , Historia de la teoría de los números  (en) [ ediciones detalladas ], Vuelo. 2, 1919, c. XXIV, pág.  705-716 .
5. Wright (1959)
6. Borwein y Ingalls (1944)
7. Borwein (2002)
8. Borwein, Lisonĕk y Percival 2003
9. (in) Michael Filaseta y Maria Markovich , "Los  polígonos de Newton y el problema de Prouhet-Tarry-Escott  " , Journal of Number Theory , vol.  174, 2017, p.  384–400 ( DOI  10.1016 / j.jnt.2016.10.009 ).
10. Borwein (2002) y El problema de Prouhet-Tarry-Escott .
11. Ver Borwein e Ingalls (1944) para referencias.

Referencias

• (en) Andreas Alpers y Robert Tijdeman , “  El problema bidimensional de Prouhet-Tarry-Escott  ” , J. Number Theor. , vol.  123,2007, p.  403-412
• (en) Peter Borwein , Computational Excursions in Analysis and Number Theory , Nueva York / Berlín / Heidelberg, Springer , coll.  "Libros CMS en matemáticas",2002, 220  p. ( ISBN  0-387-95444-9 , leer en línea )El capítulo 11: El problema Prouhet-Tarry-Escott (páginas 85-96) está dedicado al problema.
• (en) Peter Borwein y Colin Ingalls , “  El problema Prouhet-Tarry-Escott revisitado  ” , Profesor. Matemáticas. , vol.  40, n hueso  1-2,1994, p.  3-27 ( leer en línea )
• (en) Peter Borwein , Petr Lisonĕk y Colin Percival , “  Investigaciones computacionales del problema Prouhet-Tarry-Escott  ” , Math. Comp. , vol.  72, n o  244,2003, p.  2063-2070 ( leer en línea )
• (de) Albert Gloden  (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Revisiones de matemáticas  0019638 )
• GH Hardy y EM Wright ( traducido  del inglés por F. Sauvageot), Introducción a la teoría de los números [“  Introducción a la teoría de los números  ”], París y Heidelberg, Vuibert y Springer,2007La sección 20.5 “El teorema de los cuatro cuadrados” trata este tema. Secciones 21.9 “El problema de Prouhet y Tarry: el número  ” y 21.10, p. 423-427, están dedicados al problema de Prouhet-Tarry.PAG(k,j){\ Displaystyle P (k, j)}
• (en) Edward M. Wright , “  La solución de Prouhet de 1851 del problema de Tarry-Escott de 1910  ” , Amer. Matemáticas. Mensual , vol.  66,Marzo de 1959, p.  199-201

Ver también

Artículos relacionados

• Suite Prouhet-Thue-Morse
• Conjetura de Euler
• Teorema de Erdős-Suranyi

enlaces externos

• (en) Chen Shuwen, El problema Prouhet-Tarry-Escott
• (en) Eric W. Weisstein , "  Problema de Prouhet-Tarry-Escott  " , en MathWorld

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