Теорема Эрдеша – Фукса

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

Теорема названа в честь Пауля Эрдеша и Вольфганга Генриха Йоханнеса Фукса , опубликовавших ее в 1956 году.

Заявление

Позволять ${\mathcal {A}}\subseteq \mathbb {N}$ быть бесконечным подмножеством натуральных чисел и $r_{{\mathcal {A}},h}(n)$ его функция представления , которая обозначает количество способов, которыми натуральное число $n$ можно выразить как сумму $h$ элементы ${\mathcal {A}}$ (с учетом заказа). Затем мы рассматриваем накопленную функцию представления $$s_{{\mathcal {A}},h}(x):=\sum _{n\leqslant x}r_{{\mathcal {A}},h}(n),$$ который подсчитывает (также с учетом порядка) количество решений задачи $k_{1}+\cdots +k_{h}\leqslant x$, где $k_{1},\ldots ,k_{h}\in {\mathcal {A}}$. Тогда теорема утверждает, что для любого данного $c>0$, отношение $$s_{{\mathcal {A}},2}(n)=cn+o\left(n^{1/4}\log(n)^{-1/2}\right)$$ не может быть удовлетворен; то есть нет ${\mathcal {A}}\subseteq \mathbb {N}$ удовлетворяющие приведенной выше оценке.

Теоремы типа Эрдеша–Фукса.

Теорема Эрдеша-Фукса имеет интересную историю прецедентов и обобщений. В 1915 году он был уже известен Г.Х. Харди. что в случае последовательности ${\mathcal {Q}}:=\{0,1,4,9,\ldots \}$ идеальных квадратов есть $$\limsup _{n\to +\infty }{\frac {\left|s_{{\mathcal {Q}},2}(n)-\pi n\right|}{n^{1/4}\log(n)^{1/4}}}>0$$ Эта оценка немного лучше, чем оценка, описанная Эрдёшем–Фуксом, но ценой небольшой потери точности П. Эрдёш и WHJ Фукс добились полной общности своего результата (по крайней мере, для случая $h=2$). Другая причина, по которой этот результат так прославляется, может быть связана с тем, что в 1941 г. П. Эрдеш и П. Туран предположил, что при тех же предположениях, что и в сформулированной теореме, соотношение $$s_{{\mathcal {A}},2}(n)=cn+O(1)$$ не смог удержаться. Этот факт оставался недоказанным до 1956 года, когда Эрдёш и Фукс получили свою теорему, которая даже сильнее, чем высказанная ранее оценка.

Улучшенные версии для h=2

Эта теорема была расширена в ряде различных направлений. В 1980 году А. Саркози рассматривались две последовательности, которые в некотором смысле «близки». Он доказал следующее:

• Теорема (Саркози, 1980) . Если ${\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}$ и ${\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}$ представляют собой два бесконечных подмножества натуральных чисел с $a_{i}-b_{i}=o{\big (}a_{i}^{1/2}\log(a_{i})^{-1}{\big )}$, затем $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}\log(n)^{-1/2}{\big )}$ не может выполняться ни для какой константы $c>0$.

В 1990 году Х. Л. Монтгомери и Р. К. Воган смогли удалить запись из правой части исходного утверждения Эрдеша-Фукса, показав, что $$s_{{\mathcal {A}},2}(n)=cn+o(n^{1/4})$$ не может держаться. В 2004 году Габор Хорват расширил оба этих результата, доказав следующее:

• Теорема (Хорват, 2004). Если ${\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}$ и ${\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}$ представляют собой бесконечные подмножества натуральных чисел с $a_{i}-b_{i}=o{\big (}a_{i}^{1/2}{\big )}$ и $|{\mathcal {A}}\cap [0,n]|-|{\mathcal {B}}\cap [0,n]|=O(1)$, затем $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}{\big )}$ не может выполняться ни для какой константы $c>0$.

Общий случай (h ≥ 2)

Естественное обобщение теоремы Эрдеша – Фукса, а именно для $h\geqslant 3$, как известно, придерживается той же силы, что и версия Монтгомери-Воана. Фактически, М. Тан показали в 2009 году, что в тех же условиях, что и в исходном утверждении Эрдеша-Фукса, для каждого $h\geqslant 2$ отношение $$s_{{\mathcal {A}},h}(n)=cn+o(n^{1/4})$$ не может держаться. В другом направлении, в 2002 году, Габор Хорват дал точное обобщение результата Саркози 1980 года, показав, что

• Теорема (Хорват, 2002 г.) Если ${\mathcal {A}}^{(j)}=\{a_{1}^{(j)}<a_{2}^{(j)}<\ldots \}$ ( $j=1,\ldots ,k$) являются $k$ (не менее двух) бесконечных подмножеств натуральных чисел и справедливы следующие оценки:

1. $a_{i}^{(1)}-a_{i}^{(2)}=o{\big (}(a_{i}^{(1)})^{1/2}\log(a_{i}^{(1)})^{-k/2}{\big )}$
2. $|{\mathcal {A}}^{(j)}\cap [0,n]|=\Theta {\big (}|{\mathcal {A}}^{(1)}\cap [0,n]|{\big )}$ (для $j=3,\ldots ,k$)

тогда соотношение:

$|\{(i_{1},\ldots ,i_{k}):a_{i_{1}}^{(1)}+\ldots +a_{i_{k}}^{(k)}\leqslant n,~a_{i_{j}}^{(j)}\in {\mathcal {A}}^{(j)}(j=1,\ldots ,k)\}|=cn+o{\big (}n^{1/4}\log(n)^{1-3k/4}{\big )}$

не может выполняться ни для какой константы $c>0$.

Нелинейные приближения

Еще одно направление, в котором можно улучшить теорему Эрдеша – Фукса, — это рассмотрение аппроксимаций к $s_{{\mathcal {A}},h}(n)$ кроме $cn$ для некоторых $c>0$. В 1963 году Пол Т. Бейтман , Юджин Э. Кольбекер и Джек П. Талл. доказал несколько более сильную версию следующего:

• Теорема (Бейтман – Кольбекер – Талл, 1963). Позволять $L(x)$ — медленно меняющаяся функция , которая становится либо выпуклой , либо вогнутой с некоторого момента . Тогда при тех же условиях, что и в исходной теореме Эрдеша–Фукса, мы не можем иметь $s_{{\mathcal {A}},2}(n)=nL(n)+o{\big (}n^{1/4}\log(n)^{-1/2}L(n)^{\alpha }{\big )}$, где $\alpha =3/4$ если $L(x)$ ограничен, и $1/4$ в противном случае.

В конце статьи также отмечается, что их метод можно расширить для получения результатов, учитывая $n^{\gamma }$ с $\gamma \neq 1$, но такие результаты считаются недостаточно окончательными.

См. также

• Теорема Эрдеша–Тетала : для любого $h\geq 2$, есть набор ${\mathcal {A}}\subseteq \mathbb {N}$ который удовлетворяет $r_{{\mathcal {A}},h}(n)=\Theta (\log(n))$. (Наличие экономической основы)
• Гипотеза Эрдеша – Турана об аддитивных базисах : если ${\mathcal {A}}\subseteq \mathbb {N}$ является аддитивным базисом второго порядка, то $r_{{\mathcal {A}},2}(n)\neq O(1)$. (Базы не могут быть слишком экономичными)

Дальнейшее чтение

• Ньюман, диджей (1998). Аналитическая теория чисел . ГТМ . Том. 177. Нью-Йорк: Спрингер. стр. 31–38. ISBN  0-387-98308-2 .
• Хальберштам, Х. ; Рот, К.Ф. (1983) [1966]. Последовательности (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag . ISBN  978-0-387-90801-4 . МР   0210679 .