Теорема Берендса - Behrends theorem

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

Заявление

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

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

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

Примеры

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

В подмножестве ${ Displaystyle { lceil (п + 1) / 2 rceil, точки п }}$ , все пары чисел находятся в пределах менее двух раз друг от друга, поэтому никакие два числа не могут быть кратными. В него входит примерно половина номеров из ${ displaystyle 1}$ к ${ displaystyle n}$ . К Теорема Дилворта (используя разбиение целых чисел на цепочки степеней двойки, умноженных на нечетное число) это подмножество имеет максимальную мощность среди всех подмножеств, в которых нет двух кратных. Но поскольку все его элементы большие, это подмножество имеет низкую логарифмическую плотность, только ${ Displaystyle О (1 / журнал п)}$ .
Еще одно примитивное подмножество - это набор простые числа. Несмотря на то, что простых чисел меньше, чем количество элементов в предыдущем примере, этот набор имеет большую логарифмическую плотность, ${ Displaystyle О ( журнал журнал п / журнал п)}$ , согласно расхождение суммы обратных простых чисел.

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

{ displaystyle { frac {1 + o (1)} { sqrt {2 pi log log n}}},}

в точности соответствует форме теоремы Беренда.^[3] Этот пример является наилучшим из возможных в том смысле, что никакое другое примитивное подмножество не имеет логарифмической плотности с такой же формой и большей ведущей константой.^[4]

История

Эта теорема известна как теорема Беренда, потому что Феликс Беренд доказал это в 1934 году,^[1] и опубликовал его в 1935 году.^[5] Пол Эрдёш доказал тот же результат во время поездки на поезде в 1934 году, в которой он путешествовал из Венгрии в Кембридж, чтобы избежать растущего антисемитизма в Европе того времени, но по прибытии он обнаружил, что доказательство Беренда уже было известно.^[1]

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

^ ^а ^б ^c ^d Шаркози, А. (2013), «О свойствах делимости последовательностей целых чисел», в Грэм, Рональд Л.; Нешетржил, Ярослав (ред.), Математика Пола Эрдёша, I, Алгоритмы и комбинаторика, 13 (2-е изд.), Берлин: Springer, стр. 221–232, Дои:10.1007/978-3-642-60408-9_19, МИСТЕР 1425189. См. В частности п. 222.
^ Эрдеш, П.; Шаркози, А.; Семереди, Э. (1967), «Об одной теореме Беренда» (PDF), Журнал Австралийского математического общества, 7: 9–16, МИСТЕР 0209246
^ Эрдеш, П. (1948), "О целых числах, имеющих ровно ${ displaystyle K}$ главные факторы" (PDF), Анналы математики, Вторая серия, 49: 53–66, Дои:10.2307/1969113, МИСТЕР 0023279
^ Эрдеш, П.; Шаркози, А.; Семереди, Э. (1967), «Об одной экстремальной задаче о примитивных последовательностях» (PDF), Журнал Лондонского математического общества, Вторая серия, 42: 484–488, Дои:10.1112 / jlms / s1-42.1.484, МИСТЕР 0218325
^ Беренд, Феликс (Январь 1935 г.), «О последовательностях чисел, не делящихся одно на другое», Журнал Лондонского математического общества, с1-10 (1): 42–44, Дои:10.1112 / jlms / s1-10.37.42

[s13-1] а ^б ^c ^d Шаркози, А. (2013), «О свойствах делимости последовательностей целых чисел», в Грэм, Рональд Л.; Нешетржил, Ярослав (ред.), Математика Пола Эрдёша, I, Алгоритмы и комбинаторика, 13 (2-е изд.), Берлин: Springer, стр. 221–232, Дои:10.1007/978-3-642-60408-9_19, МИСТЕР 1425189. См. В частности п. 222.

[ess67a-2] Эрдеш, П.; Шаркози, А.; Семереди, Э. (1967), «Об одной теореме Беренда» (PDF), Журнал Австралийского математического общества, 7: 9–16, МИСТЕР 0209246

[e48-3] Эрдеш, П. (1948), "О целых числах, имеющих ровно ${ displaystyle K}$ главные факторы" (PDF), Анналы математики, Вторая серия, 49: 53–66, Дои:10.2307/1969113, МИСТЕР 0023279

[ess67b-4] Эрдеш, П.; Шаркози, А.; Семереди, Э. (1967), «Об одной экстремальной задаче о примитивных последовательностях» (PDF), Журнал Лондонского математического общества, Вторая серия, 42: 484–488, Дои:10.1112 / jlms / s1-42.1.484, МИСТЕР 0218325

[b35-5] Беренд, Феликс (Январь 1935 г.), «О последовательностях чисел, не делящихся одно на другое», Журнал Лондонского математического общества, с1-10 (1): 42–44, Дои:10.1112 / jlms / s1-10.37.42

[1]

[2]

[3]

[4]

[5]