Lema de Dickson

En matemáticas , el lema de Dickson establece que todo conjunto de tuplas de números naturales tiene un número finito de elementos mínimos . Este simple hecho de la combinatoria se ha atribuido al algebrista estadounidense LE Dickson , quien lo utilizó para demostrar un resultado en teoría de números sobre números perfectos . ^[1] Sin embargo, el lema ciertamente era conocido antes, por ejemplo por Paul Gordan en su investigación sobre la teoría invariante . ^[2] ${\displaystyle n}$

Ejemplo

Infinitos pares mínimos de números reales x , y (la hipérbola negra) pero sólo cinco pares mínimos de números enteros positivos (rojo) tienen xy  ≥ 9.

Sea un número natural fijo y sea el conjunto de pares de números cuyo producto es al menos . Cuando se define sobre los números reales positivos , tiene infinitos elementos mínimos de la forma , uno para cada número positivo ; este conjunto de puntos forma una de las ramas de una hipérbola . Los pares en esta hipérbola son mínimos, porque no es posible que un par diferente al que pertenece sea menor o igual en ambas coordenadas. Sin embargo, el lema de Dickson se refiere sólo a tuplas de números naturales, y sobre los números naturales sólo hay un número finito de pares mínimos. Todo par mínimo de números naturales tiene y , pues si x fuera mayor que K entonces ( x  − 1, y ) también pertenecería a S , contradiciendo la minimalidad de ( x , y ), y simétricamente si y fuera mayor que K entonces ( x , y  − 1) también pertenecería a  S . Por tanto, respecto a los números naturales, tiene como máximo elementos mínimos, un número finito. ^{[nota 1]} ${\displaystyle K}$ ${\displaystyle S=\{(x,y)\mid xy\geq K\}}$ ${\displaystyle K}$ ${\displaystyle S}$ ${\displaystyle (x,K/x)}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle (x,K/x)}$ ${\displaystyle (x,y)}$ ${\displaystyle x\leq K}$ ${\displaystyle y\leq K}$ ${\displaystyle S}$ ${\displaystyle K^{2}}$

Declaración formal

Sea el conjunto de números enteros no negativos ( números naturales ), sea n cualquier constante fija y sea el conjunto de tuplas de números naturales. A estas tuplas se les puede dar un orden parcial puntual , el orden del producto , en el que si y sólo si para cada . El conjunto de tuplas que son mayores o iguales que alguna tupla particular forma una ortante positiva con su vértice en la tupla dada. ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle n}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{n})\leq (b_{1},b_{2},\dots b_{n})}$ ${\displaystyle a_{i}\leq b_{i}}$ ${\displaystyle i}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$

Con esta notación, el lema de Dickson se puede expresar de varias formas equivalentes:

• En cada subconjunto no vacío de hay al menos uno, pero no más de un número finito de elementos que son elementos mínimos de para el orden parcial puntual. ^[3] ${\displaystyle S}$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle S}$
• Para cada secuencia infinita de -tuplas de números naturales, existen dos índices que se cumplen con respecto al orden puntual. ^[4] ${\displaystyle (x_{i})_{i\in \mathbb {N} }}$ ${\displaystyle n}$ ${\displaystyle i<j}$ ${\displaystyle x_{i}\leq x_{j}}$
• El conjunto parcialmente ordenado no contiene anticadenas infinitas ni secuencias infinitas (estrictamente) descendentes de tuplas. ^[4] ${\displaystyle (\mathbb {N} ^{n},\leq )}$ ${\displaystyle n}$
• El conjunto parcialmente ordenado es un orden bien parcial . ^[5] ${\displaystyle (\mathbb {N} ^{n},\leq )}$
• Cada subconjunto de puede estar cubierto por un conjunto finito de orantes positivos, cuyos vértices pertenecen a . ${\displaystyle S}$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle S}$

Generalizaciones y aplicaciones.

Dickson usó su lema para demostrar que, para cualquier número dado , sólo puede existir un número finito de números perfectos impares que tengan como máximo factores primos . ^[1] Sin embargo, permanece abierto si existen números perfectos impares. ${\displaystyle n}$ ${\displaystyle n}$

La relación de divisibilidad entre los números P -lisos , números naturales cuyos factores primos pertenecen todos al conjunto finito P , da a estos números la estructura de un conjunto isomorfo parcialmente ordenado . Por tanto, para cualquier conjunto S de P -números suaves, existe un subconjunto finito de S tal que cada elemento de S es divisible por uno de los números de este subconjunto. Este hecho se ha utilizado, por ejemplo, para demostrar que existe un algoritmo para clasificar los movimientos ganadores y perdedores desde la posición inicial en el juego de monedas Sylver , aunque el algoritmo en sí sigue siendo desconocido. ^[6] ${\displaystyle (\mathbb {N} ^{|P|},\leq )}$

Las tuplas se corresponden uno por uno con los monomios sobre un conjunto de variables . Según esta correspondencia, el lema de Dickson puede verse como un caso especial del teorema de la base de Hilbert que establece que todo ideal polinómico tiene una base finita, para los ideales generados por monomios. De hecho, Paul Gordan utilizó esta reformulación del lema de Dickson en 1899 como parte de una prueba del teorema de la base de Hilbert. ^[2] ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle x_{1}^{a_{1}}x_{2}^{a_{2}}\dots x_{n}^{a_{n}}}$ ${\displaystyle n}$ ${\displaystyle x_{1},x_{2},\dots x_{n}}$

Ver también

• El lema de Gordon

Notas

1. Con más cuidado, es posible demostrar que uno de y es como máximo , y que hay como máximo un par mínimo para cada elección de una de las coordenadas, de lo que se deduce que hay como máximo elementos mínimos. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle {\sqrt {K}}}$ ${\displaystyle 2{\sqrt {K}}}$

Referencias

1. Dickson, LE (1913), "Finitud de los números abundantes primitivos y perfectos impares con n factores primos distintos", American Journal of Mathematics , 35 (4): 413–422, doi :10.2307/2370405, JSTOR  2370405.
2. Buchberger, Bruno ; Winkler, Franz (1998), Bases y aplicaciones de Gröbner, Serie de notas de conferencias de la London Mathematical Society, vol. 251, Cambridge University Press, pág. 83, ISBN 9780521632980.
3. Kruskal, Joseph B. (1972). "La teoría del cuasiordenamiento del bien: un concepto descubierto con frecuencia". Revista de teoría combinatoria . Serie A. 13 (3): 298. doi : 10.1016/0097-3165(72)90063-5 .
4. Figueira, Diego; Figueira, Santiago; Schmitz, Sylvain; Schnoebelen, Philippe (2011), "Límites ackermannianos y primitivos-recursivos con el lema de Dickson", 26º Simposio anual del IEEE sobre lógica en informática (LICS 2011) , IEEE Computer Soc., Los Alamitos, CA, p. 269, arXiv : 1007.2989 , doi : 10.1109/LICS.2011.39, SEÑOR  2858898, S2CID  9178090.
5. Onn, Shmuel (2008), "Optimización discreta convexa", en Floudas, Christodoulos A .; Pardalos, Panos M. (eds.), Enciclopedia de optimización, vol. 1 (2ª ed.), Springer, págs. 513–550, arXiv : math/0703575 , Bibcode : 2007math......3575O, ISBN 9780387747583.
6. Berlekamp, ​​Elwyn R .; Conway, John H.; Guy, Richard K. (2003), "18 El emperador y su dinero", Winning Ways for your Mathematical Plays, vol. 3 , Academic Press, págs. 609–640. Véase especialmente "¿Son computables los resultados?", pág. 630.