Большой набор (комбинаторика)

Чтобы узнать о других значениях этого термина, см. Большой набор .

В комбинаторной математике большой набор натуральных чисел

$S=\{s_{0},s_{1},s_{2},s_{3},\dots \}$

такой, что бесконечная сумма обратных величин

${\frac {1}{s_{0}}}+{\frac {1}{s_{1}}}+{\frac {1}{s_{2}}}+{\frac {1}{s_{3}}}+\cdots$

расходится . Малый набор — это любое небольшое подмножество натуральных чисел; то есть тот, у которого сумма обратных величин сходится.

Большие множества появляются в теореме Мюнца-Саса и в гипотезе Эрдеша об арифметических прогрессиях .

Примеры

• Каждое конечное подмножество натуральных чисел мало.
• Набор $\{1,2,3,4,5,\dots \}$ всех натуральных чисел — это большой набор; это утверждение эквивалентно расходимости гармонического ряда . В более общем смысле, любая арифметическая прогрессия (т. е. набор всех целых чисел вида an + b с a ≥ 1, b ≥ 1 и n = 0, 1, 2, 3, ...) представляет собой большой набор.
• Набор квадратных чисел невелик (см. Базельскую задачу ). То же самое относится и к набору чисел куба , набору четвертых степеней и так далее. В более общем смысле, набор положительных целых значений любого многочлена степени 2 или выше образует небольшой набор.
• Набор {1, 2, 4, 8, ...} степеней 2 представляет собой небольшой набор, как и любая геометрическая прогрессия (т. е. набор чисел вида ab ^н с a ≥ 1, b ≥ 2 и n = 0, 1, 2, 3, ...).
• Множество простых чисел велико . Набор простых чисел-близнецов невелик (см. константу Брюна ).
• Набор степеней простых чисел , которые не являются простыми (т. е. все числа вида p ^н при n ≥ 2 и p простое число) мало, хотя простые числа большие. Это свойство часто используется в аналитической теории чисел . В более общем смысле набор совершенных способностей невелик; даже набор мощных чисел невелик.
• Набор чисел, разложение которых по данному основанию исключает данную цифру, невелик. Например, набор

$\{1,2,\dots ,5,6,8,9,\dots ,15,16,18,19,\dots ,65,66,68,69,80,81,\dots \}$

целых чисел, десятичное разложение которых не включает цифру 7, мало. Такие ряды называются сериями Кемпнера .

• Любое множество, верхняя асимптотическая плотность которого не равна нулю, велико.

Характеристики

• Каждое подмножество малого множества мало.
• Объединение конечного числа малых множеств невелико, поскольку сумма двух сходящихся рядов является сходящимся рядом. (В терминологии теории множеств малые множества образуют идеал .)
• Состав каждого маленького набора велик.
• Теорема Мюнца –Саса утверждает, что множество $S=\{s_{1},s_{2},s_{3},\dots \}$ велико тогда и только тогда, когда набор многочленов, натянутый на $$\{1,x^{s_{1}},x^{s_{2}},x^{s_{3}},\dots \}$$ плотна . в равномерной нормы топологии непрерывных функций на отрезке положительных действительных чисел Это обобщение теоремы Стоуна-Вейерштрасса .

Открытые задачи, связанные с большими множествами

Пол Эрдеш предположил , что все большие множества содержат сколь угодно длинные арифметические прогрессии . За доказательство он предложил приз в 3000 долларов — больше, чем за любое другое его предположение , — и пошутил, что это предложение приза нарушает закон о минимальной заработной плате. Вопрос все еще открыт.

Неизвестно, как вообще определить, является ли данный набор большим или маленьким. В результате существует множество множеств, о которых неизвестно, являются ли они большими или малыми.

См. также

• Список сумм обратных величин

Ссылки

• А.Д. Вадхва (1975). Интересная подсерия гармонического ряда. Американский математический ежемесячник 82 (9) 931–933. JSTOR   2318503