Теорема Эрдеша – Фукса - Erdős–Fuchs theorem

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

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

Заявление

Позволять ${displaystyle {mathcal {A}}subseteq mathbb {N} }$ быть бесконечным подмножеством натуральные числа и ${displaystyle r_{{mathcal {A}},h}(n)}$ это функция представления, который обозначает количество способов, которыми натуральное число ${displaystyle n}$ можно выразить как сумму ${displaystyle h}$ элементы ${displaystyle {mathcal {A}}}$ (с учетом заказа). Затем мы рассматриваем функция накопленного представления

$${displaystyle s_{{mathcal {A}},h}(x):=sum _{nleqslant x}r_{{mathcal {A}},h}(n),}$$

который учитывает (также с учетом порядка) количество решений ${displaystyle k_{1}+cdots +k_{h}leqslant x}$, куда ${displaystyle k_{1},ldots ,k_{h}in {mathcal {A}}}$. Затем теорема утверждает, что для любого данного ${displaystyle c>0}$, Соотношение

$${displaystyle s_{{mathcal {A}},2}(n)=cn+oleft(n^{1/4}log(n)^{-1/2}ight)}$$

не можешь быть довольным; то есть есть нет ${displaystyle {mathcal {A}}subseteq mathbb {N} }$ удовлетворяющие приведенной выше оценке.

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

Теорема Эрдеша – Фукса имеет интересную историю прецедентов и обобщений. В 1915 году о нем уже знали Г. Х. Харди^[1] что в случае последовательности ${displaystyle {mathcal {Q}}:={0,1,4,9,ldots }}$ из идеальные квадраты надо

$${displaystyle limsup _{n o +infty }{frac {left|s_{{mathcal {Q}},2}(n)-pi night|}{n^{1/4}log(n)^{1/4}}}>0}$$

Эта оценка немного лучше, чем оценка Эрдеша – Фукса, но ценой небольшой потери точности П. Эрдеш и У. Х. Дж. Фукс достигли полной общности своего результата (по крайней мере, для случая ${displaystyle h=2}$). Другая причина, по которой этот результат так прославлен, может быть связана с тем, что в 1941 г. П. Эрдёш и П. Туран^[2] предположил, что при тех же предположениях, что и в сформулированной теореме, соотношение

$${displaystyle s_{{mathcal {A}},2}(n)=cn+O(1)}$$

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

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

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

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

В 1990 г. Х. Л. Монтгомери и Р. К. Воган^[4] смогли удалить лог из правой части исходного заявления Эрдеша – Фукса, показав, что

$${displaystyle s_{{mathcal {A}},2}(n)=cn+o(n^{1/4})}$$

не могу удержать. В 2004 г. Г. Хорват^[5] расширили оба этих результата, доказав следующее:

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

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

Естественное обобщение теоремы Эрдеша – Фукса, а именно для ${displaystyle hgeqslant 3}$, как известно, имеет ту же силу, что и версия Монтгомери-Вона. Фактически, М. Тан^[6] в 2009 г. показал, что в тех же условиях, что и в исходном утверждении Эрдеша – Фукса, для каждого ${displaystyle hgeqslant 2}$ Соотношение

$${displaystyle s_{{mathcal {A}},h}(n)=cn+o(n^{1/4})}$$

не могу удержать. В другом направлении, в 2002 г. Г. Хорват^[7] дал точное обобщение результата Шаркози 1980 г., показав, что

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

1. ${displaystyle a_{i}^{(1)}-a_{i}^{(2)}=o{ig (}(a_{i}^{(1)})^{1/2}log(a_{i}^{(1)})^{-k/2}{ig )}}$
2. ${displaystyle |{mathcal {A}}^{(j)}cap [0,n]|=Theta {ig (}|{mathcal {A}}^{(1)}cap [0,n]|{ig )}}$ (за ${displaystyle j=3,ldots ,k}$)

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

${displaystyle |{(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{ig (}n^{1/4}log(n)^{1-3k/4}{ig )}}$

не может выполняться для любой постоянной ${displaystyle c>0}$.

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

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

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

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

Смотрите также

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

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

• Эрдеш, П.; Фукс, В. Х. Дж. (1956). «К проблеме теории аддитивных чисел». J. London Math. Soc. 31 (1): 67–73. Дои:10.1112 / jlms / s1-31.1.67. HDL:2027 / mdp.39015095244037.
• Ньюман, Д. Дж. (1998). Аналитическая теория чисел. GTM. 177. Нью-Йорк: Спрингер. С. 31–38. ISBN  0-387-98308-2.
• Хальберштам, Х.; Рот, К.Ф. (1983) [1966]. Последовательности (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag. ISBN  978-0-387-90801-4. МИСТЕР  0210679.

Харди, Г. Х. (1915). «О выражении числа как суммы двух квадратов». Кварта. J. Math. 46: 263–83.

Erdős, P .; Туран, П. (1941). «О проблеме Сидона в аддитивной теории чисел и некоторых смежных проблемах». J. London Math. Soc. 16: 212–5.

Шаркози, А. (1980). «Об одной теореме Эрдеша и Фукса». Acta Arith. 37: 333–338.

Montgomery, H.L .; Воган, Р. К. (1990). «О теореме Эрдеша – Фукса». Дань Павлу Эрдёшу. Cambridge Univ. Пресс: 331–338.

Хорват, Г. (2004). «Улучшение расширения теоремы Эрдеша и Фукса». Acta Math. Подвешенный. 104: 27–37.

Тан, Мин (2009). «Об обобщении теоремы Эрдеша и Фукса». Дискретная математика. 309: 6288–6293.

Хорват, Г. (2002). «Об одной теореме Эрдеша и Фукса». Acta Arith. 103 (4): 321–328.

Bateman, P.T .; Kohlbecker, E.E .; Талл, Дж. П. (1963). «Об одной теореме Эрдеша и Фукса в аддитивной теории чисел». Proc. Являюсь. Математика. Soc. 14: 278–84.