On a refinement of Waring's problem (Q1847774): Difference between revisions

Let \(R_X^s(n)\) denote the number of representations of \(n\) as a sum of \(s\) members of a set \(X\) of integers. The author is concerned with thin bases \(X\), for which \(R_X^s(n)\) is positive but small for each positive integer \(n\). An unproved but generally believed conjecture of P. Erdős and P. Turán states that if \(X\) is a basis of order \(2\) (so that \(R_X^2(n) \geq 1\) for all \(n\)) then \(\limsup_{n \to \infty}R_X^2(n)=\infty\). Thus it is not to be expected that one can show better in the desired direction than that there exists \(X\) for which \(R_X^s(n)\) is positive but bounded by a slowly increasing function of \(n\). The author's theorem is that for each \(k \geq 2\) the set \({\mathbb N}_0^k\) of non-negative \(k\)th powers contains a subset \(X\) such that \(R_X^s(n)=\Theta(\log n)\) when \(n \geq 2\), provided \(s\) is large enough in terms of \(k\). The notation \(\Theta\) is described as ``standard'', but the reviewer has not seen it before. It appears that \(A = \Theta(B)\) means that \(A=O(B)\) and \(B=O(A)\). A corollary of the theorem, which can be proved more simply but by the same methods, affirmatively answers a question of \textit{M. Nathanson} posed in [Analytic number theory, Proc. Conf., Temple Univ./Phila. 1980, Lect. Notes Math. 899, 301-310 (1981; Zbl 0476.10042)]. If the main conclusion is relaxed to \(R_X^s(n)=\Omega(\log n)\) then the number \(X(m)\) of members of \(X\) not exceeding \(m\) can be made to satisfy \(X(m) = O(m^{1/s}\log^{1/s}m)\). In the case \(k=1\), the author's theorem was established by \textit{P. Erdős} and \textit{P. Tetali} [Random Struct. Algorithms 1, 245---261 (1990; Zbl 0725.11007)], but the author's method leads to a generalisation of their result. The author's proof is probabilistic, the only currently known way of constructing thin bases. The strategy is to specify a suitable random subset \(X \subset {\mathbb N}_0^k\), show that its expectation satisfies \({\mathbb E} (R_X^s(n)) = \Theta(\log n)\) and that there is a small \(\varepsilon\) such that \(1-\varepsilon < R_X^s(n)/{\mathbb E} (R_X^s(n)) < 1+\varepsilon \) with probability at least \(1+O(n^{-2})\). The estimation of \({\mathbb E} (R_X^s(n))\) involves an upper bound on the number of solutions of \(\sum_{1 \leq j \leq s}x_j^k=n\) when the variables \(x_j\) are restricted to a suitable box. This estimate, which may be of some independent interest, is achieved via the circle method. The second part of the programme invokes an appeal to a ``concentration'' result of a type appearing in the author's paper with \textit{J. H. Kim} [Combinatorica 20, 417-434 (2000; Zbl 0969.60013)] and reviewed in his own survey [Random Struct. Algorithms 20, 262---316 (2002; Zbl 0999.60027)].