El lema de Dickson

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

Dejar${\displaystyle K}$Sea un número natural fijo, y sea${\displaystyle S=\{(x,y)\mid xy\geq K\}}$sea ​​el conjunto de pares de números cuyo producto es al menos${\displaystyle K}$. Cuando se define sobre los números reales positivos ,${\displaystyle S}$tiene infinitos elementos mínimos de la forma${\displaystyle (x,K/x)}$uno por cada número positivo${\displaystyle x}$; 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 que pertenezca a${\displaystyle S}$ser menor o igual que${\displaystyle (x,K/x)}$en ambas coordenadas. Sin embargo, el lema de Dickson se refiere solo a tuplas de números naturales, y sobre los números naturales solo hay un número finito de pares mínimos. Cada par mínimo${\displaystyle (x,y)}$de los números naturales tiene${\displaystyle x\leq K}$y${\displaystyle y\leq K}$, porque 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, ${\displaystyle S}$tiene como máximo${\displaystyle K^{2}}$elementos mínimos, un número finito. ^{[ nota 1 ]}

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

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

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

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

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${\displaystyle (\mathbb {N} ^{|P|},\leq )}$Así, 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 los movimientos ganadores y perdedores desde la posición inicial en el juego de acuñación de monedas de Sylver , aunque el algoritmo en sí sigue siendo desconocido. ^{[ 6 ]}

Las tuplas${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$en${\displaystyle \mathbb {N} ^{n}}$se corresponden uno a uno con los monomios${\displaystyle x_{1}^{a_{1}}x_{2}^{a_{2}}\dots x_{n}^{a_{n}}}$sobre un conjunto de${\displaystyle n}$variables${\displaystyle x_{1},x_{2},\dots x_{n}}$En este contexto, el lema de Dickson puede considerarse un caso particular 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 Gordon utilizó esta reformulación del lema de Dickson en 1899 como parte de una demostración del teorema de la base de Hilbert. ^{[ 2 ]}

• El lema de Gordon