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

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

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

Заявление

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

{\ displaystyle s _ {{\ mathcal {A}}, h} (x): = \ sum _ {n \ leqslant 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 + o \ left (n ^ {1/4} \ log (n) ^ {- 1/2} \ right)}

не может быть удовлетворен; то есть не удовлетворяет приведенной выше оценке.

{\ Displaystyle {\ mathcal {A}} \ substeq \ mathbb {N}}

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

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

{\ displaystyle \ limsup _ {n \ to + \ infty} {\ frac {\ left | s _ {{\ mathcal {Q}}, 2} (n) - \ pi n \ right |} {n ^ {1 / 4} \ log (n) ^ {1/4}}}> 0}

Эта оценка немного лучше, чем оценка, описанная Эрдешем – Фуксом, но ценой небольшой потери точности П. Эрдеш и У. Дж. Фукс достигли полной общности своего результата (по крайней мере, для данного случая ). Другая причина, по которой этот результат так прославлен, может быть связана с тем, что в 1941 году П. Эрдеш и П. Туран предположили, что при тех же гипотезах, что и в сформулированной теореме, соотношение

{\ displaystyle h = 2}

{\ displaystyle s _ {{\ mathcal {A}}, 2} (n) = cn + O (1)}

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

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

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

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

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

{\ displaystyle s _ {{\ mathcal {A}}, 2} (n) = cn + o (n ^ {1/4})}

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

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

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

Естественное обобщение теоремы Эрдеша – Фукса, а именно для , как известно, имеет ту же силу, что и версия Монтгомери – Вона. Фактически, М. Танг показал в 2009 г., что в тех же условиях, что и в исходной формулировке Эрдеша – Фукса, для каждого соотношения ${\ displaystyle h \ geqslant 3}$ ${\ displaystyle h \ geqslant 2}$

{\ displaystyle s _ {{\ mathcal {A}}, h} (n) = cn + o (n ^ {1/4})}

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

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

${\ displaystyle a_ {i} ^ {(1)} - a_ {i} ^ {(2)} = o {\ big (} (a_ {i} ^ {(1)}) ^ {1/2} \ журнал (a_ {i} ^ {(1)}) ^ {- k / 2} {\ big)}}$
${\ displaystyle | {\ mathcal {A}} ^ {(j)} \ cap [0, n] | = \ Theta {\ big (} | {\ mathcal {A}} ^ {(1)} \ cap [ 0, n] | {\ big)}}$ (для ) ${\ Displaystyle J = 3, \ ldots, k}$

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

{\ displaystyle | \ {(i_ {1}, \ ldots, i_ {k}): a_ {i_ {1}} ^ {(1)} + \ ldots + a_ {i_ {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)}}

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

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

Еще одно направление, в котором теорема Эрдеша – Фукса может быть улучшена, - это рассмотрение приближений к другим, а не к некоторым . В 1963 году

П. Т. Бейтман , Э. Колбеккер и Дж. П. Талл доказали несколько более сильную версию следующего утверждения:

{\ displaystyle s _ {{\ mathcal {A}}, h} (n)}

{\ displaystyle cn}

{\ displaystyle c> 0}

Теорема (Бейтман – Кольбекер – Талль, 1963). Позвольте быть

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

{\ Displaystyle L (х)}

, где if ограничено, и иначе.

{\ displaystyle s _ {{\ mathcal {A}}, 2} (n) = nL (n) + o {\ big (} n ^ {1/4} \ log (n) ^ {- 1/2} L (п) ^ {\ alpha} {\ big)}}

{\ Displaystyle \ альфа = 3/4}

{\ Displaystyle L (х)}

${\ displaystyle 1/4}$

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

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

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

использованная литература

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

^ Erdős, П .; Фукс, WHJ (1956). «К проблеме теории аддитивных чисел». J. London Math. Soc . 31 (1): 67–73. DOI : 10,1112 / jlms / s1-31.1.67 . hdl : 2027 / mdp.39015095244037 .

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

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

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

^ Монтгомери, HL; Vaughan, RC (1990). «О теореме Эрдеша – Фукса». Дань Полю Эрдёшу . Cambridge Univ. Пресс: 331–338.

^ Хорват, Г. (2004). «Улучшение расширения теоремы Эрдеша и Фукса» . Acta Math. Повесили. 104 : 27–37. DOI : 10,1023 / Б: AMHU.0000034360.41926.5a .

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

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

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

Languages

In other projects