Английская Википедия:Erdős–Fuchs theorem
Шаблон:Short description In mathematics, in the area of additive number theory, the Erdős–Fuchs theorem is a statement about the number of ways that numbers can be represented as a sum of elements of a given additive basis, stating that the average order of this number cannot be too close to being a linear function.
The theorem is named after Paul Erdős and Wolfgang Heinrich Johannes Fuchs, who published it in 1956.[1]
Statement
Let <math>\mathcal{A}\subseteq\mathbb{N}</math> be an infinite subset of the natural numbers and <math>r_{\mathcal{A},h}(n)</math> its representation function, which denotes the number of ways that a natural number <math>n</math> can be expressed as the sum of <math>h</math> elements of <math>\mathcal{A}</math> (taking order into account). We then consider the accumulated representation function <math display="block">s_{\mathcal{A},h}(x) := \sum_{n\leqslant x} r_{\mathcal{A},h}(n),</math> which counts (also taking order into account) the number of solutions to <math>k_1 + \cdots + k_h \leqslant x</math>, where <math>k_1,\ldots,k_h \in \mathcal{A}</math>. The theorem then states that, for any given <math>c>0</math>, the relation <math display="block">s_{\mathcal{A},2}(n) = cn + o\left(n^{1/4}\log(n)^{-1/2} \right) </math> cannot be satisfied; that is, there is no <math>\mathcal{A}\subseteq\mathbb{N}</math> satisfying the above estimate.
Theorems of Erdős–Fuchs type
The Erdős–Fuchs theorem has an interesting history of precedents and generalizations. In 1915, it was already known by G. H. Hardy[2] that in the case of the sequence <math>\mathcal{Q}:=\{0,1,4,9,\ldots\}</math> of perfect squares one has <math display="block">\limsup_{n\to +\infty} \frac{\left|s_{\mathcal{Q},2}(n)- \pi n\right|}{n^{1/4}\log(n)^{1/4}} > 0 </math> This estimate is a little better than that described by Erdős–Fuchs, but at the cost of a slight loss of precision, P. Erdős and W. H. J. Fuchs achieved complete generality in their result (at least for the case <math>h=2</math>). Another reason this result is so celebrated may be due to the fact that, in 1941, P. Erdős and P. Turán[3] conjectured that, subject to the same hypotheses as in the theorem stated, the relation <math display="block">s_{\mathcal{A},2}(n) = cn + O(1)</math> could not hold. This fact remained unproven until 1956, when Erdős and Fuchs obtained their theorem, which is even stronger than the previously conjectured estimate.
Improved versions for h = 2
This theorem has been extended in a number of different directions. In 1980, A. Sárközy[4] considered two sequences which are "near" in some sense. He proved the following:
- Theorem (Sárközy, 1980). If <math>\mathcal{A} = \{a_1 < a_2 <\ldots\}</math> and <math>\mathcal{B} = \{b_1 < b_2 < \ldots\}</math> are two infinite subsets of natural numbers with <math>a_i - b_i = o\big(a_i ^{1/2}\log(a_i)^{-1} \big)</math>, then <math>|\{(i,j):a_i+b_j \leqslant n\}| = cn + o\big(n^{1/4}\log(n)^{-1/2} \big)</math> cannot hold for any constant <math>c > 0</math>.
In 1990, H. L. Montgomery and R. C. Vaughan[5] were able to remove the log from the right-hand side of Erdős–Fuchs original statement, showing that <math display="block">s_{\mathcal{A},2}(n) = cn + o(n^{1/4})</math> cannot hold. In 2004, Gábor Horváth[6] extended both these results, proving the following:
- Theorem (Horváth, 2004). If <math>\mathcal{A}=\{a_1<a_2<\ldots\}</math> and <math>\mathcal{B}=\{b_1<b_2<\ldots\}</math> are infinite subsets of natural numbers with <math>a_i-b_i = o\big(a_i^{1/2}\big)</math> and <math>|\mathcal{A}\cap[0,n]| - |\mathcal{B}\cap[0,n]| = O(1)</math>, then <math>|\{(i,j):a_i+b_j \leqslant n\}| = cn + o\big(n^{1/4} \big)</math> cannot hold for any constant <math>c>0</math>.
General case (h ≥ 2)
The natural generalization to Erdős–Fuchs theorem, namely for <math>h \geqslant 3</math>, is known to hold with same strength as the Montgomery–Vaughan's version. In fact, M. Tang[7] showed in 2009 that, in the same conditions as in the original statement of Erdős–Fuchs, for every <math>h \geqslant 2</math> the relation <math display="block">s_{\mathcal{A},h}(n) = cn + o(n^{1/4})</math> cannot hold. In another direction, in 2002, Gábor Horváth[8] gave a precise generalization of Sárközy's 1980 result, showing that
- Theorem (Horváth, 2002) If <math>\mathcal{A}^{(j)}=\{a^{(j)}_1<a^{(j)}_2<\ldots\}</math> (<math>j=1,\ldots,k</math>) are <math>k</math> (at least two) infinite subsets of natural numbers and the following estimates are valid:
- <math>a^{(1)}_i - a^{(2)}_i = o\big((a^{(1)}_i) ^{1/2}\log(a_i^{(1)})^{-k/2} \big)</math>
- <math>|\mathcal{A}^{(j)}\cap[0,n]| = \Theta\big(|\mathcal{A}^{(1)}\cap[0,n]|\big)</math> (for <math>j=3,\ldots,k</math>)
- then the relation:
- <math>|\{(i_1,\ldots, i_k):a^{(1)}_{i_1}+\ldots+a^{(k)}_{i_k} \leqslant n,~ a^{(j)}_{i_j} \in \mathcal{A}^{(j)} (j =1,\ldots,k)\}| = cn + o\big(n^{1/4}\log(n)^{1-3k/4} \big)</math>
- cannot hold for any constant <math>c >0</math>.
Non-linear approximations
Yet another direction in which the Erdős–Fuchs theorem can be improved is by considering approximations to <math>s_{\mathcal{A},h}(n)</math> other than <math>cn</math> for some <math>c>0</math>. In 1963, Paul T. Bateman, Eugene E. Kohlbecker and Jack P. Tull[9] proved a slightly stronger version of the following:
- Theorem (Bateman–Kohlbecker–Tull, 1963). Let <math>L(x)</math> be a slowly varying function which is either convex or concave from some point onward. Then, on the same conditions as in the original Erdős–Fuchs theorem, we cannot have <math>s_{\mathcal{A},2}(n) = nL(n) + o\big(n^{1/4}\log(n)^{-1/2}L(n)^\alpha \big)</math>, where <math>\alpha = 3/4</math> if <math>L(x)</math> is bounded, and <math>1/4</math> otherwise.
At the end of their paper, it is also remarked that it is possible to extend their method to obtain results considering <math>n^{\gamma}</math> with <math>\gamma \neq 1</math>, but such results are deemed as not sufficiently definitive.
See also
- Erdős–Tetali theorem: For any <math>h \geq 2</math>, there is a set <math>\mathcal{A}\subseteq \mathbb{N}</math> which satisfies <math>r_{\mathcal{A},h}(n) = \Theta(\log(n))</math>. (Existence of economical bases)
- Erdős–Turán conjecture on additive bases: If <math>\mathcal{A}\subseteq\mathbb{N}</math> is an additive basis of order 2, then <math>r_{\mathcal{A},2}(n) \neq O(1)</math>. (Bases cannot be too economical)
References
Further reading
