Lema de Dickson

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

Ejemplo

Hay un número infinito de pares mínimos de números reales x , y (la hipérbola negra), pero solo cinco pares mínimos de números enteros positivos (rojos) 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 por cada número positivo ; este conjunto de puntos forma una de las ramas de una hipérbola . Los pares de esta hipérbola son mínimos, porque no es posible que un par diferente que pertenece a sea menor o igual que en ambas de sus coordenadas. Sin embargo, el lema de Dickson solo concierne a tuplas de números naturales, y sobre los números naturales solo 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 lo tanto, sobre 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 los 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 producto , en el que si y solo si para cada . El conjunto de tuplas que son mayores o iguales que alguna tupla particular forma un ortante positivo 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 puede enunciarse en 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 tales 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 conjunto de orden parcial bien ordenado . ^[5] ${\displaystyle (\mathbb {N} ^{n},\leq )}$
• Cada subconjunto de puede estar cubierto por un conjunto finito de ortantes positivos, cuyos vértices pertenecen todos a . ${\displaystyle S}$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle S}$

Generalizaciones y aplicaciones

Dickson utilizó su lema para demostrar que, para cualquier número dado , solo puede existir un número finito de números perfectos impares que tengan como máximo factores primos . ^[1] Sin embargo, sigue abierto el interrogante de si existen o no números perfectos impares. ${\displaystyle n}$ ${\displaystyle n}$

La relación de divisibilidad entre los números P -suaves , números naturales cuyos factores primos pertenecen todos al conjunto finito P , da a estos números la estructura de un conjunto parcialmente ordenado isomorfo a . Por lo tanto, para cualquier conjunto S de números P -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 las jugadas ganadoras y perdedoras desde la posición inicial en el juego de acuñación de plata , aunque el algoritmo en sí sigue siendo desconocido. ^[6] ${\displaystyle (\mathbb {N} ^{|P|},\leq )}$

Las tuplas en se corresponden uno a uno con los monomios sobre un conjunto de variables . Bajo esta correspondencia, el lema de Dickson puede verse como un caso especial del teorema de la base de Hilbert que establece que todo ideal polinomial 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}}$

Véase también

• Lema de Gordan

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 perfectos impares y abundantes primitivos 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, London Mathematical Society Lecture Note Series, vol. 251, Cambridge University Press, pág. 83, ISBN 9780521632980.
3. Kruskal, Joseph B. (1972). "La teoría del buen ordenamiento: un concepto descubierto con frecuencia". Journal of Combinatorial Theory . 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 primitivo-recursivos con el lema de Dickson", 26.º Simposio anual IEEE sobre lógica en ciencias de la computación (LICS 2011) , IEEE Computer Soc., Los Alamitos, CA, pág. 269, arXiv : 1007.2989 , doi : 10.1109/LICS.2011.39, ISBN 978-1-4577-0451-2, MR  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.