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

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

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

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