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)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

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

27.13.1 n=x1k+x2k++xmk

has nonnegative integer solutions for all n1. The smallest m that exists for a given k is denoted by g(k). Similarly, G(k) denotes the smallest m for which (27.13.1) has nonnegative integer solutions for all sufficiently large n.

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

27.13.2 g(k)2k+3k2k-2,

for all k2, with equality if 4k200,000. If 3k=q2k+r with 0<r<2k, then equality holds in (27.13.2) provided r+q2k, a condition that is satisfied with at most a finite number of exceptions.

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

§27.13(iv) Representation by Squares

For a given integer k2 the function rk(n) is defined as the number of solutions of the equation

27.13.3 n=x12+x22++xk2,

where the xj are integers, positive, negative, or zero, and the order of the summands is taken into account.

Jacobi (1829) notes that r2(n) is the coefficient of xn in the square of the theta function ϑ(x):

27.13.4 ϑ(x)=1+2m=1xm2,
|x|<1.

(In §20.2(i), ϑ(x) is denoted by θ3(0,x).) Thus,

27.13.5 (ϑ(x))2=1+n=1r2(n)xn.

One of Jacobi’s identities implies that

27.13.6 (ϑ(x))2=1+4n=1(δ1(n)-δ3(n))xn,

where δ1(n) and δ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

27.13.7 r2(n)=4(δ1(n)-δ3(n)).

Hence r2(5)=8 because both divisors, 1 and 5, are congruent to 1(mod4). In fact, there are four representations, given by 5=22+12=22+(-1)2=(-2)2+12=(-2)2+(-1)2, and four more with the order of summands reversed.

By similar methods Jacobi proved that r4(n)=8σ1(n) if n is odd, whereas, if n is even, r4(n)=24 times the sum of the odd divisors of n. Mordell (1917) notes that rk(n) is the coefficient of xn in the power-series expansion of the kth power of the series for ϑ(x). Explicit formulas for rk(n) have been obtained by similar methods for k=6,8,10, and 12, but they are more complicated. Exact formulas for rk(n) have also been found for k=3,5, and 7, and for all even k24. For values of k>24 the analysis of rk(n) 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.