Лемма Диксона - Dicksons lemma

В математика, Лемма Диксона заявляет, что каждый набор ${\displaystyle n}$-наборы натуральные числа имеет конечное количество минимальные элементы. Этот простой факт из комбинаторика был приписан американскому алгебраисту Л. Э. Диксон, кто использовал его, чтобы доказать результат в теория чисел о идеальные числа.^[1] Однако лемма наверняка была известна ранее, например, Пол Гордан в своем исследовании теория инвариантов.^[2]

Пример

Бесконечно много минимальных пар действительных чисел Икс,у (черная гипербола), но только пять минимальных пар натуральных чисел (красные) имеют ху ≥ 9.

Позволять ${\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}$, если Икс были больше, чем K тогда (Икс −1,у) также будет принадлежать S, что противоречит минимальности (Икс,у), и симметрично, если у были больше, чем K тогда (Икс,у −1) также будет принадлежатьS. Следовательно, над натуральными числами ${\displaystyle S}$ имеет самое большее ${\displaystyle K^{2}}$ минимальные элементы, конечное число.^{[примечание 1]}

Официальное заявление

Позволять ${\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 i}$, ${\displaystyle a_{i}\leq b_{i}}$. Набор кортежей, которые больше или равны некоторому определенному кортежу. ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$ формирует положительный ортодоксальный с его вершиной в данном кортеже.

В этих обозначениях лемму Диксона можно сформулировать в нескольких эквивалентных формах:

• В каждом подмножестве ${\displaystyle S\neq \emptyset }$ из ${\displaystyle \mathbb {N} ^{n}}$, существует хотя бы один, но не более конечного числа элементов, которые минимальные элементы из ${\displaystyle S}$ для поточечного частичного порядка.^[3]
• Для каждой бесконечной последовательности ${\displaystyle (x_{i})_{i\in \mathbb {N} }}$ из ${\displaystyle n}$-наборы натуральных чисел, существует два индекса ${\displaystyle i<j}$ такой, что ${\displaystyle x_{i}\leq x_{j}}$ относительно поточечного порядка.^[4]
• Частично упорядоченный набор ${\displaystyle (\mathbb {N} ^{n},\leq )}$ не содержит бесконечного антицепи ни бесконечные (строго) убывающие последовательности из ${\displaystyle n}$- пары.^[4]
• Частично упорядоченный набор ${\displaystyle (\mathbb {N} ^{n},\leq )}$ это ну частичный порядок.^[5]
• Каждое подмножество ${\displaystyle S}$ из ${\displaystyle \mathbb {N} ^{n}}$ могут быть покрыты конечным множеством положительных ортантов, все вершины которых принадлежат ${\displaystyle S}$.

Обобщения и приложения

Диксон использовал свою лемму, чтобы доказать, что для любого данного числа ${\displaystyle n}$, может существовать лишь конечное число странный идеальные числа которые имеют самое большее ${\displaystyle n}$ главные факторы.^[1] Однако остается открытым вопрос, существуют ли вообще какие-либо нечетные совершенные числа.

В делимость отношения между п-гладкие числа, натуральные числа, все простые множители которых принадлежат конечный набор п, придает этим числам структуру частично упорядоченного множества, изоморфного ${\displaystyle (\mathbb {N} ^{|P|},\leq )}$. Таким образом, для любого набора S из п-гладких чисел существует конечное подмножество S так что каждый элемент S делится на одно из чисел этого подмножества. Этот факт использовался, например, чтобы показать, что существует алгоритм для классификации выигрышных и проигрышных ходов из начальной позиции в игре Серебряная чеканка, хотя сам алгоритм остается неизвестным.^[6]

Кортежи ${\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}}$. При таком соответствии лемму Диксона можно рассматривать как частный случай Базисная теорема Гильберта заявляя, что каждый многочлен идеальный имеет конечный базис идеалов, порожденных одночленами. В самом деле, Пол Гордан использовал эту переформулировку леммы Диксона в 1899 году как часть доказательства теоремы Гильберта о базисе.^[2]

Смотрите также

• Лемма Гордана

Примечания

1. С большей осторожностью можно показать, что один из ${\displaystyle x}$ и ${\displaystyle y}$ самое большее ${\displaystyle {\sqrt {K}}}$, и что существует не более одной минимальной пары для каждого выбора одной из координат, из чего следует, что существует не более ${\displaystyle 2{\sqrt {K}}}$ минимальные элементы.

Рекомендации

1. Диксон, Л.Э. (1913), «Конечность нечетных совершенных и примитивных изобильных чисел с п различные простые множители ", Американский журнал математики, 35 (4): 413–422, Дои:10.2307/2370405, JSTOR  2370405.
2. Бухбергер, Бруно; Винклер, Франц (1998), Основы Грёбнера и приложения, Серия лекций Лондонского математического общества, 251, Cambridge University Press, стр. 83, ISBN  9780521632980.
3. Крускал, Джозеф Б. (1972). «Теория хорошо квазиупорядочения: часто обнаруживаемая концепция». Журнал комбинаторной теории. Серия А. 13 (3): 298. Дои:10.1016/0097-3165(72)90063-5.
4. Фигейра, Диего; Фигейра, Сантьяго; Шмитц, Сильвен; Schnoebelen, Филипп (2011), "Аккермановы и примитивно-рекурсивные оценки с леммой Диксона", 26-й ежегодный симпозиум IEEE по логике в компьютерных науках (LICS 2011), IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 269, arXiv:1007.2989, Дои:10.1109 / LICS.2011.39, МИСТЕР  2858898.
5. Онн, Шмуэль (2008), «Выпуклая дискретная оптимизация», в Флудас, Христодулос А.; Пардалос, Панос М. (ред.), Энциклопедия оптимизации, Vol. 1 (2-е изд.), Springer, стр. 513–550, arXiv:математика / 0703575, Bibcode:2007математика ...... 3575O, ISBN  9780387747583.
6. Берлекамп, Элвин Р.; Конвей, Джон Х .; Гай, Ричард К. (2003), «Император и его деньги», Выигрышные способы для ваших математических игр, Vol. 3, Academic Press, стр. 609–640.. См. Особенно «Вычислимы ли результаты» на стр. 630.