Лемма Диксона

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

Пример

Позволять $K$ — фиксированное натуральное число, и пусть $S=\{(x,y)\mid xy\geq K\}$ — набор пар чисел, произведение которых не менее $K$ . При определении над положительными числами действительными $S$ имеет бесконечно много минимальных элементов вида $(x,K/x)$ , по одному на каждое положительное число $x$ ; этот набор точек образует одну из ветвей гиперболы . Пары в этой гиперболе минимальны, потому что не может быть другой пары, принадлежащей $S$ быть меньше или равно $(x,K/x)$ по обеим его координатам. Однако лемма Диксона касается только наборов натуральных чисел, а среди натуральных чисел существует только конечное число минимальных пар. Каждая минимальная пара $(x,y)$ натуральных чисел имеет $x\leq K$ и $y\leq K$ , поскольку если бы x было больше K , то ( x − 1, y ) также принадлежало бы S , что противоречит минимальности ( x , y ), и симметрично, если бы y было больше K , тогда ( x , y − 1) также было бы принадлежат С. Следовательно, над натуральными числами $S$ имеет не более $K^{2}$ минимальные элементы, конечное число. ^{[ примечание 1 ]}

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

Позволять $\mathbb {N}$ — набор неотрицательных целых чисел ( натуральных чисел ), пусть n — любая фиксированная константа, и пусть $\mathbb {N} ^{n}$ быть набором $n$ -кортежи натуральных чисел. Этим кортежам может быть задан поточечный частичный порядок , порядок произведения , в котором $(a_{1},a_{2},\dots ,a_{n})\leq (b_{1},b_{2},\dots b_{n})$ тогда и только тогда, когда $a_{i}\leq b_{i}$ для каждого $i$ . Набор кортежей, которые больше или равны определенному кортежу. $(a_{1},a_{2},\dots ,a_{n})$ образует положительный ортант с вершиной в данном кортеже.

С помощью этих обозначений лемму Диксона можно сформулировать в нескольких эквивалентных формах:

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

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

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

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

Кортежи $(a_{1},a_{2},\dots ,a_{n})$ в $\mathbb {N} ^{n}$ одночленам соответствуют $x_{1}^{a_{1}}x_{2}^{a_{2}}\dots x_{n}^{a_{n}}$ над набором $n$ переменные $x_{1},x_{2},\dots x_{n}$ . В соответствии с этим соответствием лемму Диксона можно рассматривать как частный случай базовой теоремы Гильберта, утверждающей, что каждый полиномиальный идеал имеет конечный базис для идеалов, порожденных мономами. Действительно, Пол Гордан использовал эту повторную формулировку леммы Диксона в 1899 году как часть доказательства базовой теоремы Гильберта. ^{[ 2 ]}

См. также

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

Примечания

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

Ссылки

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

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

[dickson-1] Jump up to: ^а ^б Диксон, Л.Е. (1913), «Конечность нечетных совершенных и примитивно обильных чисел с n различными простыми делителями», American Journal of Mathematics , 35 (4): 413–422, doi : 10.2307/2370405 , JSTOR 2370405 .

[buchberger-2] Jump up to: ^а ^б Бухбергер, Бруно ; Винклер, Франц (1998), Базы Грёбнера и приложения , Серия лекций Лондонского математического общества, том. 251, Издательство Кембриджского университета, стр. 251. 83, ISBN 9780521632980 .

[kruskal-4] Краскал, Джозеф Б. (1972). «Теория хорошего квазиупорядочения: часто обнаруживаемая концепция» . Журнал комбинаторной теории . Серия А. 13 (3): 298. doi : 10.1016/0097-3165(72)90063-5 .

[ffss-5] Jump up to: ^а ^б Фигейра, Диего; Фигейра, Сантьяго; Шмитц, Сильвен; Шнобелен, Филипп (2011), «Акермановы и примитивно-рекурсивные границы с леммой Диксона», 26-й ежегодный симпозиум IEEE по логике в информатике (LICS 2011) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 269, arXiv : 1007.2989 , doi : 10.1109/LICS.2011.39 , MR 2858898 , S2CID 9178090 .

[6] Онн, Шмуэль (2008), «Выпуклая дискретная оптимизация», во Флудасе, Христодулос А .; Пардалос, Панос М. (ред.), Энциклопедия оптимизации, Vol. 1 (2-е изд.), Springer, стр. 513–550, arXiv : math/0703575 , Bibcode : 2007math......3575O , ISBN 9780387747583 .

[7] Берлекамп, Элвин Р .; Конвей, Джон Х.; Гай, Ричард К. (2003), «18 Император и его деньги», Пути победы в ваших математических пьесах, Том. 3 , Академик Пресс, стр. 609–640 . См. особенно «Вычислимы ли результаты», с. 630.

[ 1 ]

[ 2 ]

[ примечание 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]