Введение
В математике лемма Диксона утверждает, что любое множество кортежей натуральных чисел имеет конечное число минимальных элементов. Этот простой факт из комбинаторики приписывается американскому алгебраисту Л. Э. Диксону, который использовал его для доказательства теоремы в теории чисел о совершенных числах.
Пример
Пусть K – фиксированное натуральное число, и пусть S – множество пар чисел, произведение которых не меньше K. Когда S определено над положительными действительными числами, оно имеет бесконечно много минимальных элементов вида (x, K/x), по одному для каждого положительного числа x; этот набор точек образует одну из ветвей гиперболы. Пары на этой гиперболе минимальны, поскольку не существует другой пары, принадлежащей S, которая была бы меньше или равна (x, K/x) по обеим своим координатам. Однако, лемма Диксона касается только кортежей натуральных чисел, и над натуральными числами существует лишь конечное число минимальных пар. Каждая минимальная пара (x, y) натуральных чисел имеет x и y не больше K, поскольку если бы x было больше K, то (x − 1, y) также принадлежало бы S, что противоречило бы минимальности (x, y), а симметрично, если бы y было больше K, то (x, y − 1) также принадлежало бы S. Следовательно, над натуральными числами, S имеет не более K² минимальных элементов, то есть конечное число.
Обобщения и применения
Диксон использовал свою лемму, чтобы доказать, что для любого заданного числа , может существовать только конечное число нечетных совершенных чисел, имеющих не более простых множителей. Однако остается открытым вопрос о том, существуют ли вообще какие-либо нечетные совершенные числа. Отношение делимости между P-гладкими числами, натуральными числами, все простые множители которых принадлежат конечному множеству P, наделяет эти числа структурой частично упорядоченного множества, изоморфного . Таким образом, для любого множества S P-гладких чисел существует конечное подмножество S, такое что каждый элемент S делится на один из элементов этого подмножества. Этот факт был использован, например, для доказательства существования алгоритма классификации выигрышных и проигрышных ходов из начальной позиции в игре «Монетная система Сильвера», хотя сам алгоритм остается неизвестным. Кортежи в соответствуют один к одному мономам относительно множества переменных. При этом соответствии лемма Диксона может рассматриваться как частный случай теоремы о базисе Гильберта, утверждающей, что каждый полиномиальный идеал имеет конечный базис, для идеалов, порожденных мономами. Действительно, Поль Гордан использовал эту переформулировку леммы Диксона в 1899 году как часть доказательства теоремы о базисе Гильберта.