20 Waring and Goldbach type problems, and Schnirelman’s constant

20.1 Waring Problem

Definition 20.1

Let $A \subset N$ be such that there exists $k$ for which

\underset{k times}{\underset{⏟}{A + A + \dots + A}} = N

Then $A$ is called an additive basis of $N$ . The minimum $k$ for which 1 holds is the order of $A$ .

Definition 20.2

For any $k \geq 1$ let $A_{k} = {n^{k} : n \in N \cup {0}}$ . Let $g (k)$ be the order of $A_{k}$ when it exists. That is, $g (k)$ is the minimum number of $k$ powers needed to write any natural number as the sum of (not necessarily unique) $g (k)$ many $k$ powers including 0.

Definition 20.3

For any $k \geq 1$ , let $G (k)$ be the minimum $m$ such that there exists $N \geq 1$ for which

\underset{m times}{\underset{⏟}{A_{k} + \dots + A_{k}}} = N ∖ J_{N} .

where $J_{N} = {1, \dots, N}$ . That is, $G (k)$ is the minimum number of $k$ powers such that every sufficiently large integer may be written as the sum of (not necessarily unique) $G (k)$ many $k$ powers including 0.

20.1.1 Known values of g(k)

Theorem 20.4 Lagrange’s Four Square Theorem

We have $g (2) = 4$ ; that is every natural number may be written as the sum of $4$ perfect squares.

Theorem 20.5 Linnik [ 147 ]

$g (k)$ exists for all $k \geq 1$ .

Linnik’s proof relied on the notion of Schnirelmann density, which will be discussed later.

In fact, the exact value of $g (k)$ is known for almost all $k \geq 1$ . We have

g (k) = 2^{k} + {[\frac{3}{2}]}^{k} - 2 if 2^{k} {\frac{3}{2}}^{k} + {[\frac{3}{2}]}^{k} \leq 2^{k}

and, otherwise,

g (k) = 2^{k} + {[\frac{3}{2}]}^{k} + {[\frac{4}{3}]}^{k} - ξ

where $ξ = 2$ if

{[\frac{3}{2}]}^{k} + {[\frac{4}{3}]}^{k} + {[\frac{3}{2}]}^{k} {[\frac{4}{3}]}^{k} \geq 2^{k}

and $3$ otherwise. Note that $[x]$ is the greatest integer less than $x$ and ${x} = x - [x]$ . It has been shown that there at at most finitely many exceptions [ 159 ] . To complete the proof, it suffices to show

{{(\frac{3}{2})}^{k}} \leq 1 - {(\frac{3}{4})}^{k - 1}

It has been shown for all $k > 5000$ , ${(3 / 2)^{k}} \leq 1 - a^{k}$ where $a = 2^{- 0.9} \approx 0.53$ , and for sufficiently large $k$ , ${(3 / 2)^{k}} \leq 1 - (0.5769 \dots)^{- k}$ [ 48 ] [ 12 ] .

20.1.2 Known values of $G (k)$

Only 2 values of $G (k)$ are known definitively: $G (2) = 4$ as shown by Lagrange and $G (4) = 16$ as shown by Davenport [ 43 ] .

Definition 20.6

Let $G_{1} (k)$ be the smallest number $m$ such that

d (\underset{m times}{\underset{⏟}{A_{k} + \dots + A_{k}}}) = 1

where $d (A)$ represents the natural density of $A$ :

d (A) = lim_{N \to \infty} \frac{# (A \cap J_{N})}{N}

$G_{1} (k)$ has been determined for $5$ values:

Davenport [ 44 ]	$G_{1} (3) = 4$
Hardy and Littlewood [ 70 ]	$G_{1} (4) = 15$
Vaughan [ 221 ]	$G_{1} (8) = 32$
Wooley [ 232 ]	$G_{1} (16) = 64$
Wooley [ 232 ]	$G_{1} (32) = 128$

Table 20.1 Known values of

G_{1} (k)

20.1.3 General bounds for $G (k)$

Theorem 20.7 Brudern and Wooley 2022 [ 22 ]

For all $k \geq 1$ ,

G (k) < k (\log k + C_{1}) + C_{2}

Furthermore,

G (k) \leq ⌈ k (\log k + 4.20032) ⌉

This bound is the sharpest to date and was a significant improvement over the previous bound by Wooley [ 232 ] : for sufficiently large $k$ ,

G (k) \leq k (\log k + \log \log k + 2 + O (\log \log k / \log k))

20.1.4 Bounds for special cases for $G (k)$

$k = 3$

Lemma 20.8

$G (3) \geq 4$

Proof ▶

Note cubes are congruent $1, - 1, 0$ modulo $9$ . Thus, numbers congruent $4, 5$ modulo $9$ may not be expressed as the sum of $3$ cubes. □

Theorem 20.9 Linnik [ 151 ]

$G (3) \leq 7$

The exact value of $G (3)$ is conjectured to be $4$ , but has not been proven.

Conjectured $G (k)$ for small $k$

Table 20.2 summarizes the best upper bounds for $G (k)$ and the conjectured values of $G (k)$ for $7 \leq k \leq 20$ .

	7	8	9	10	11	12	13	14	15	16	17	18	19	20
Best Bound	31	39	47	55	63	72	81	89	97	105	113	121	129	137
Conjectured	8	32	13	12	12	16	14	15	16	64	18	27	20	25

Table 20.2 Conjectured and best upper bounds for

G (k)

for

7 \leq k \leq 20

The upper bounds for $k \leq 13$ were deduced from Wooley [ 233 ] and the bounds for $14 \leq k \leq 20$ are from Theorem 20.7.

20.1.5 Generalized Waring problem and connections to the Generalized Riemann Hypothesis

Waring’s Problem concerns the solvability of equations of the form

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

for $m, n, k \in N$ , and Theorem 20.5 states that for any fixed $k \geq 1$ , there exists $n \in N$ such that (2) is solvable for all $m \in N$ . A more generalized problem arises when $k$ is not fixed. Given any $k = (k_{1}, \dots, k_{n}) \in N^{n}$ , the generalized Waring problem concerns the solvability of the equations of the form

x_{1}^{k_{1}} + x_{2}^{k_{2}} + \dots + x_{n}^{k_{n}} = m

The following theorem due to Erich Kamke provides a partial result.

Theorem 20.10 Kamke

Let $f (x)$ be an integer valued polynomial such that there does not exist $d \in N$ such that $d | f (n)$ for all $n \in N$ . Then for sufficiently large $k$ ,

f (x_{1}) + f (x_{2}) + \dots + f (x_{k}) = m

is solvable for all large enough $m$ .

Assuming the Generalized Riemann Hypothesis (GRH), The solvability of (3) can be guaranteed for specific $k$ . For example:

Theorem 20.11 Wooley

Assuming GRH, then

x_{1}^{2} + x_{2}^{2} + x_{3}^{3} + x_{4}^{3} + x_{5}^{6} + x_{6}^{6} = n

is solvable for sufficiently high $n$ . Furthermore, (4) is not solvable for at most $O ((\log N)^{3 + ϵ})$ integers between $1$ and $N$ .

20.2 Goldbach-Style Problems

Goldbach’s original conjecture stated that every positive integer could be written as the sum of $3$ primes. In light of Waring’s problem, a natural extension of Goldbach’s problem asks when

p_{1}^{k} + p_{2}^{k} + \dots + p_{m}^{k} = n

is solvable for all $n \in N$ for $p_{1}, \dots p_{k}$ prime and $k \in N$ . It is conjectured when $m \geq k + 1$ and for sufficiently large $n$ satisfying local conditions, which will be made more explicit for specific values of $k$ , (5) is solvable.

20.2.1 When $k = 2$

It is conjectured that

n = p_{1}^{2} + p_{2}^{2} + p_{3}^{2} + p_{4}^{2}

is solvable whenever $n \equiv 4 (\mod 24)$ . The following theorem gives the closest solution.

Theorem 20.12 Liu, Wooley, Yu [ 152 ]

Let $E (N)$ be the number of integers $n \equiv 4 (\mod 24)$ for which (6) is not solvable. For any $ϵ > 0$ ,

E (N) ≪ O (N^{\frac{3}{8} + ϵ})

20.2.2 When $k = 4, 5$

Following Kawada and Wooley, we define the following quantities to give the relevant local conditions for the cases $k = 4$ and $k = 5$ . Let $θ = θ (p, k)$ be the greatest power of $p$ dividing $k$ ; that is $p^{θ} | k$ but $p^{θ + 1} ∤ k$ . Then, let

γ (k, p) = {\begin{matrix} θ + 2 & when p = 2, θ > 0 \\ θ + 1 & otherwise \end{matrix}}

and

K (k) = \prod_{(p - 1) | k} p^{γ (k, p)}

In particular, $K (4) = 240$ and $K (5) = 2$ .

Definition 20.13

For $k \in N$ , let $H (k)$ be the minimum integer $s$ such that

p_{1}^{k} + p_{2}^{k} + \dots + p_{s}^{k} = n

is solvable for sufficiently large $n$ whenever $n \equiv s (\mod K (k))$ .

Finding the value of $H (k)$ is the main focus of the modern Waring-Goldbach problem.

Theorem 20.14 Wooley, Kawada 2001 [ 129 ]

We have

$H (4) \leq 14$
For any positive $A$ ,

$p_{1}^{4} + p_{2}^{4} + \dots + p_{7}^{4} = n$

has at most $O (N (\log N)^{- A})$ exceptions for $n \equiv 7 (\mod 240)$ and $1 \leq n \leq N$ .
$H (k) \leq 21$
For any positive $A$ ,

$p_{1}^{5} + p_{2}^{5} + \dots + p_{11}^{5} = n$

has at most $O (N (\log N)^{- A})$ exceptions for $n$ odd and $1 \leq n \leq N$ .

In 2014, Zhao improved the bound for $k = 4$ and showed $H (4) \leq 13$ [ 241 ] .

20.2.3 When $k \geq 7$

Theorem 20.15 Kumchev, Wooley 2016 [ 138 ]

For large values of $k$ ,

H (k) \leq (4 k - 2) \log k - (2 \log 2 - 1) k - 3

Table 20.3 summarizes the best bounds on $H (k)$ for $7 \leq k \leq 20$ .

7	8	9	10	11	12	13	14	15	16	17	18	19	20
45	57	69	81	93	107	121	134	149	163	177	193	207	223

Table 20.3 Upper bounds for

H (k)

20.3 Schnirelmann Density

20.3.1 Existence of Additive Basis

Definition 20.16

Define the Schnirelmann density of $A \subset N$ as

σ A = inf_{n \geq 1} \frac{# (A \cap J_{n})}{n}

Definition 20.17

Define the lower asymptotic density of $A \subset N$ as

δ A = \underset{n \to \infty}{lim inf} \frac{# (A \cap J_{n})}{n}

Theorem 20.18 Schnirelmann [ 204 ]

Suppose $σ A > 0$ . Then $A$ is an additive basis for $N$ .

With Theorem 20.18, it is possible to prove many sets form additive bases. For example:

Theorem 20.19 Schnirelmann [ 204 ]

Let $P$ denote the set of primes. Then, $δ (P + P) > 0$ . Therefore, $P$ is an additive basis for $N$ . The order of $P$ is denoted $C$ and called Schnirelmann’s constant.

Schnirelmann originally bounded $C < 80000$ and Helfgott showed in 2013 that $C \leq 4$ [ 87 ] . Goldbach’s conjecture claims that $C = 3$ .

Theorem 20.20 Romanoff [ 189 ]

Let $S_{a} = {p + a^{k} : p \in P, k \in N}$ . Then, $σ S_{a} > 0$ for all $a \in N$ . Thus, each integer $n$ may be written as the sum of at most $C_{a}$ primes and $C_{a}$ powers of $a$ , where $C_{a}$ is a constant depending only on $a$ .

20.3.2 Essential Components

Definition 20.21

$B \subset N$ is called an essential component if $σ (A + B) > σ (A)$ for any $A \subset N$ with $0 < σ A < 1$ .

Linnik showed in 1933 gave the first example of an essential component that is not a basis [ 150 ] . Erdos showed in 1936 that every basis is also an essential component [ 51 ] . The minimum possible size of an essential component remained an open problem until Ruzsa showed in 1984 [ 200 ] that for any $ϵ > 0$ , there exists an essential component $H$ such that

# (H \cap J_{n}) ≪ (\log n)^{1 + ϵ}

but there does not exist an essential component such that

# (H \cap J_{n}) ≪ (\log n)^{1 + o (1)}

7	8	9	10	11	12	13	14	15	16	17	18	19	20
45	57	69	81	93	107	121	134	149	163	177	193	207	223

7	8	9	10	11	12	13	14	15	16	17	18	19	20
45	57	69	81	93	107	121	134	149	163	177	193	207	223

20 Waring and Goldbach type problems, and Schnirelman’s constant

20.1 Waring Problem

20.1.1 Known values of g(k)

20.1.2 Known values of G(k)

20.1.3 General bounds for G(k)

20.1.4 Bounds for special cases for G(k)

k=3

Conjectured G(k) for small k