Digital Library of Mathematical Functions
About the Project
NIST
27 Functions of Number TheoryAdditive Number Theory

§27.13 Functions

Contents

§27.13(i) Introduction

Whereas multiplicative number theory is concerned with functions arising from prime factorization, additive number theory treats functions related to addition of integers. The basic problem is that of expressing a given positive integer n as a sum of integers from some prescribed set S whose members are primes, squares, cubes, or other special integers. Each representation of n as a sum of elements of S is called a partition of n, and the number S(n) of such partitions is often of great interest. The subsections that follow describe problems from additive number theory. See also Apostol (1976, Chapter 14) and Apostol and Niven (1994, pp. 33–34).

§27.13(ii) Goldbach Conjecture

Every even integer n>4 is the sum of two odd primes. In this case, S(n) is the number of solutions of the equation n=p+q, where p and q are odd primes. Goldbach’s assertion is that S(n)\geq 1 for all even n>4. This conjecture dates back to 1742 and was undecided in 2009, although it has been confirmed numerically up to very large numbers. Vinogradov (1937) proves that every sufficiently large odd integer is the sum of three odd primes, and Chen (1966) shows that every sufficiently large even integer is the sum of a prime and a number with no more than two prime factors.

The current status of Goldbach’s conjecture is described in the Wikipedia.

§27.13(iii) Waring’s Problem

Show Annotations
Notes:
See Apostol (1976, p. 306) and Ellison (1971, p. 23).
Defines:
\mathop{g\/}\nolimits\!\left(k\right): Waring’s function and \mathop{G\/}\nolimits\!\left(k\right): Waring’s function
Keywords:
Waring’s problem, additive number theory, number theory
Permalink:
http://dlmf.nist.gov/27.13.iii

This problem is named after Edward Waring who, in 1770, stated without proof and with limited numerical evidence, that every positive integer n is the sum of four squares, of nine cubes, of nineteen fourth powers, and so on. Waring’s problem is to find, for each positive integer k, whether there is an integer m (depending only on k) such that the equation

has nonnegative integer solutions for all n\geq 1. The smallest m that exists for a given k is denoted by \mathop{g\/}\nolimits\!\left(k\right). Similarly, \mathop{G\/}\nolimits\!\left(k\right) denotes the smallest m for which (27.13.1) has nonnegative integer solutions for all sufficiently large n.

Lagrange (1770) proves that \mathop{g\/}\nolimits\!\left(2\right)=4, and during the next 139 years the existence of \mathop{g\/}\nolimits\!\left(k\right) was shown for k=3,4,5,6,7,8,10. Hilbert (1909) proves the existence of \mathop{g\/}\nolimits\!\left(k\right) for every k but does not determine its corresponding numerical value. The exact value of \mathop{g\/}\nolimits\!\left(k\right) is now known for every k\leq 200,000. For example, \mathop{g\/}\nolimits\!\left(3\right)=9, \mathop{g\/}\nolimits\!\left(4\right)=19, \mathop{g\/}\nolimits\!\left(5\right)=37, \mathop{g\/}\nolimits\!\left(6\right)=73, \mathop{g\/}\nolimits\!\left(7\right)=143, and \mathop{g\/}\nolimits\!\left(8\right)=279. A general formula states that

27.13.2\mathop{g\/}\nolimits\!\left(k\right)\geq 2^{k}+\left\lfloor\frac{3^{k}}{2^{k}% }\right\rfloor-2,

for all k\geq 2, with equality if 4\leq k\leq 200,000. If 3^{k}=q2^{k}+r with 0<r<2^{k}, then equality holds in (27.13.2) provided r+q\leq 2^{k}, a condition that is satisfied with at most a finite number of exceptions.

The existence of \mathop{G\/}\nolimits\!\left(k\right) follows from that of \mathop{g\/}\nolimits\!\left(k\right) because \mathop{G\/}\nolimits\!\left(k\right)\leq\mathop{g\/}\nolimits\!\left(k\right), but only the values \mathop{G\/}\nolimits\!\left(2\right)=4 and \mathop{G\/}\nolimits\!\left(4\right)=16 are known exactly. Some upper bounds smaller than \mathop{g\/}\nolimits\!\left(k\right) are known. For example, \mathop{G\/}\nolimits\!\left(3\right)\leq 7, \mathop{G\/}\nolimits\!\left(5\right)\leq 23, \mathop{G\/}\nolimits\!\left(6\right)\leq 36, \mathop{G\/}\nolimits\!\left(7\right)\leq 53, and \mathop{G\/}\nolimits\!\left(8\right)\leq 73. Hardy and Littlewood (1925) conjectures that \mathop{G\/}\nolimits\!\left(k\right)<2k+1 when k is not a power of 2, and that \mathop{G\/}\nolimits\!\left(k\right)\leq 4k when k is a power of 2, but the most that is known (in 2009) is \mathop{G\/}\nolimits\!\left(k\right)<ck\mathop{\mathrm{log}\,\/}\nolimits k for some constant c. A survey is given in Ellison (1971).

§27.13(iv) Representation by Squares

Show Annotations
Notes:
See Grosswald (1985, pp. 8, 32). For solutions of (27.13.3) see Apostol (1976, p. 305). For (27.13.4) see (20.2.3).
Defines:
\mathop{r_{{k}}\/}\nolimits\!\left(n\right): number of squares
Keywords:
Jacobi’s identities, additive number theory, number theory
Referenced by:
§20.12(i)
Permalink:
http://dlmf.nist.gov/27.13.iv

For a given integer k\geq 2 the function \mathop{r_{{k}}\/}\nolimits\!\left(n\right) is defined as the number of solutions of the equation

27.13.3n=x_{1}^{2}+x_{2}^{2}+\dots+x_{k}^{2},

where the x_{j} are integers, positive, negative, or zero, and the order of the summands is taken into account.

Jacobi (1829) notes that \mathop{r_{{2}}\/}\nolimits\!\left(n\right) is the coefficient of x^{n} in the square of the theta function \mathop{\vartheta\/}\nolimits\!\left(x\right):

27.13.4\mathop{\vartheta\/}\nolimits\!\left(x\right)=1+2\sum_{{m=1}}^{\infty}x^{{m^{2% }}},|x|<1.
Show Annotations
Defines:
\mathop{\vartheta\/}\nolimits\!\left(x\right)=\mathop{\theta_{{3}}\/}\nolimits% \!\left(0,x\right): alternative notation
Symbols:
\mathop{\theta_{{j}}\/}\nolimits\!\left(z,q\right): theta function, m: positive integer and x: real number
A&S Ref:
16.27.3 (with z=0, q=x)
Referenced by:
§27.13(iv)
Permalink:
http://dlmf.nist.gov/27.13.E4
Encodings:
TeX, pMML, png

(In §20.2(i), \mathop{\vartheta\/}\nolimits\!\left(x\right) is denoted by \mathop{\theta_{{3}}\/}\nolimits\!\left(0,x\right).) Thus,

One of Jacobi’s identities implies that

where \delta_{1}(n) and \delta_{3}(n) are the number of divisors of n congruent respectively to 1 and 3 (mod 4), and by equating coefficients in (27.13.5) and (27.13.6) Jacobi deduced that

Hence \mathop{r_{{2}}\/}\nolimits\!\left(5\right)=8 because both divisors, 1 and 5, are congruent to 1\;\;(\mathop{{\rm mod}}4). In fact, there are four representations, given by 5=2^{2}+1^{2}=2^{2}+(-1)^{2}=(-2)^{2}+1^{2}=(-2)^{2}+(-1)^{2}, and four more with the order of summands reversed.

By similar methods Jacobi proved that \mathop{r_{{4}}\/}\nolimits\!\left(n\right)=8\!\mathop{\sigma_{{1}}\/}% \nolimits\!\left(n\right) if n is odd, whereas, if n is even, \mathop{r_{{4}}\/}\nolimits\!\left(n\right)=24 times the sum of the odd divisors of n. Mordell (1917) notes that \mathop{r_{{k}}\/}\nolimits\!\left(n\right) is the coefficient of x^{n} in the power-series expansion of the kth power of the series for \mathop{\vartheta\/}\nolimits\!\left(x\right). Explicit formulas for \mathop{r_{{k}}\/}\nolimits\!\left(n\right) have been obtained by similar methods for k=6,8,10, and 12, but they are more complicated. Exact formulas for \mathop{r_{{k}}\/}\nolimits\!\left(n\right) have also been found for k=3,5, and 7, and for all even k\leq 24. For values of k>24 the analysis of \mathop{r_{{k}}\/}\nolimits\!\left(n\right) is considerably more complicated (see Hardy (1940)). Also, Milne (1996, 2002) announce new infinite families of explicit formulas extending Jacobi’s identities. For more than 8 squares, Milne’s identities are not the same as those obtained earlier by Mordell and others.

© 2010–2013 NIST / Privacy Policy / Disclaimer / Feedback; Version 1.0.6; Release date 2013-05-06 Math-Image version (See MathML) . A Printed Companionis available.