В математике , в области аддитивной теории чисел , теорема Эрдеша – Фукса - это утверждение о количестве способов, которыми числа могут быть представлены в виде суммы элементов данного аддитивного базиса , утверждающее, что средний порядок этого числа не может быть слишком близко к линейной функции .
Теорема названа в честь Пауля Эрдеша и Вольфганга Генриха Йоханнеса Фукса , опубликовавших ее в 1956 году.
Позволять - бесконечное подмножество натуральных чисел иего функция представления , которая обозначает число способов , что натуральное число можно выразить как сумму элементы (с учетом заказа). Затем мы рассматриваем функцию накопленного представления
который учитывает (также с учетом порядка) количество решений , где . Затем теорема утверждает, что для любого данного , Соотношение не может быть удовлетворен; то есть нет удовлетворяющие приведенной выше оценке. Теорема Эрдеша – Фукса имеет интересную историю прецедентов и обобщений. Еще в 1915 г. Г. Х. Харди [1] знал, что в случае последовательностииз совершенных квадратов один имеет
Эта оценка немного лучше, чем оценка Эрдеша-Фукса, но ценой небольшой потери точности П. Эрдеш и У. Дж. Фукс достигли полной общности своего результата (по крайней мере, для случая ). Другая причина, по которой этот результат так прославлен, может быть связана с тем, что в 1941 году П. Эрдёш и П. Туран [2] предположили, что при тех же предположениях, что и в сформулированной теореме, соотношение не мог удержать. Этот факт оставался недоказанным до 1956 г., когда Эрдеш и Фукс получили свою теорему, которая даже сильнее, чем предполагаемая ранее оценка. Улучшенные версии для h = 2
Эта теорема получила развитие в нескольких направлениях. В 1980 г. А. Шаркози [3] рассмотрел две последовательности, которые в некотором смысле «близки». Он доказал следующее:
- Теорема (Шаркози, 1980) . Если а также два бесконечных подмножества натуральных чисел с , тогда не может выполняться для любой постоянной .
В 1990 году Х.Л. Монтгомери и Р.К. Воан [4] смогли удалить запись из правой части исходного заявления Эрдеша – Фукса, показав, что
не могу удержать. В 2004 г. Г. Хорват [5] расширил оба этих результата, доказав следующее: - Теорема (Хорват, 2004). Если а также бесконечные подмножества натуральных чисел с а также , тогда не может выполняться для любой постоянной .
Общий случай (h ≥ 2)
Естественное обобщение теоремы Эрдеша – Фукса, а именно для , как известно, имеет ту же силу, что и версия Монтгомери-Вона. Фактически, М. Танг [6] показал в 2009 г., что в тех же условиях, что и в исходной формулировке Эрдеша – Фукса, для каждого Соотношение
не могу удержать. В другом направлении, в 2002 г. Г. Хорват [7] дал точное обобщение результата Шаркози 1980 г., показав, что - Теорема (Хорват, 2002) Если () находятся (не менее двух) бесконечных подмножеств натуральных чисел и справедливы следующие оценки:
-
- (для )
- тогда отношение:
- не может выполняться для любой постоянной .
Нелинейные приближения
Еще одно направление, в котором теорема Эрдеша – Фукса может быть улучшена, - это рассмотрение приближений к Кроме как для некоторых . В 1963 г. П. Т. Бейтман , Э. Колбеккер и Дж. П. Талл [8] доказали несколько более сильную версию следующего утверждения:
- Теорема (Бейтман – Кольбекер – Талль, 1963). Позволять- медленно меняющаяся функция, которая с некоторой точки становится либо выпуклой, либо вогнутой . Тогда при тех же условиях, что и в исходной теореме Эрдеша – Фукса, мы не можем иметь , где если ограничен, и иначе.
В конце статьи также отмечается, что их метод можно расширить для получения результатов с учетом с участием , но такие результаты считаются недостаточно окончательными.