Теорема Беренда

В арифметической комбинаторике теорема Беренда утверждает , что подмножества целых чисел от 1 до, в которых ни один член множества не является кратным любому другому, должны иметь логарифмическую плотность , которая стремится к нулю, когда становится большим. Теорема названа в честь Феликса Беренда , опубликовавшего ее в 1935 году. ${\ Displaystyle п}$ ${\ Displaystyle п}$

Логарифмическую плотность набора целых чисел от 1 до можно определить, установив вес каждого целого числа равным , и разделив общий вес набора на th частичную сумму гармонического ряда (или, что то же самое, для целей асимптотического анализ , деление на ). Результирующее число равно 1 или близко к 1, когда набор включает все целые числа в этом диапазоне, но меньше, когда пропущено много целых чисел, и особенно когда отсутствующие целые числа сами по себе малы. ^[1] ${\ Displaystyle п}$ ${\ Displaystyle я}$ ${\ Displaystyle 1 / я}$ ${\ Displaystyle п}$ ${\ Displaystyle \ журнал п}$

Подмножество называется примитивным , если оно обладает тем свойством, что ни один элемент подмножества не кратен любому другому элементу. Теорема Беренда утверждает, что логарифмическая плотность любого примитивного подмножества должна быть малой. Точнее, логарифмическая плотность такого набора должна быть . ^[1] ${\ Displaystyle \ {1, \ точки п \}}$ ${\ Displaystyle О (1 / {\ sqrt {\ журнал \ журнал п}})}$

Для бесконечных примитивных последовательностей максимально возможная плотность меньше, . ^[2] ${\ Displaystyle о (1 / {\ sqrt {\ журнал \ журнал п}})}$

Существуют большие примитивные подмножества . Однако эти множества все еще имеют небольшую логарифмическую плотность. ${\ Displaystyle \ {1, \ точки п \}}$

Оба этих подмножества имеют значительно меньшую логарифмическую плотность, чем оценка, данная теоремой Беренда. Разрешая гипотезу Г.Х. Харди , и Пол Эрдёш , и Суббайя Сивасанкаранараяна Пиллаи показали, что для множество чисел с точно простыми множителями (с учетом кратности) имеет логарифмическую плотность ${\ Displaystyle к \ приблизительно \ журнал \ журнал п}$ $k$