Issue 20

The problem with addition

It doesn’t add up for Patrick Creagh

post

8 November 2024

Addition is easy, it’s one of the first things we teach to primary school kids. $1 + 1 = 2,~ 2 + 2 = 4$, etc. A much more difficult operation to learn is multiplication. The numbers get bigger much more quickly, there are whole tables to memorise and there’s something I still don’t quite believe about $7\times 8 = 56$. However, precisely because of multiplication being ‘more restrictive’ an operation than addition in some sense, many of the biggest unsolved problems in maths are difficult, at least in part, because of addition.

The Goldbach conjecture asserts that any even number bigger than 2 is the sum of two prime numbers and the conjecture is still unsolved. If the problem were instead asking about representing integers $n$ as products of primes, we would quickly see that multiplication is too restrictive, and we can always find some large $n$ that can only be written as a product of any number of primes we desire. Even partially solved additive problems are unwieldy. The partition function of a positive integer (denoted $p(n)$) is the number of ways $n$ can be written as a sum of positive integers (up to reordering); so
$$
\begin{aligned}
p(1) = 1\!\!: & \quad 1=1, \\ p(2)=2\!\!: & \quad 2 = 2,\, 1+1, \\ p(3)=3\!\!: & \quad 3=3,\, 1+2,\, 1+1+1,
\end{aligned}
$$
and so on.
However, no closed form expression for $p(n)$ is known and the best we can do is a recurrence relation or approximate $p(n)$ (which ‘looks like’ \[\frac{1}{4n \sqrt{3}} \exp\left( \pi\sqrt{\frac{2n}{3}}\right)\] for large $n$). However, if the problem was instead: how many ways a positive integer $n$ can be written as a product of integers (denoted by say $\tilde{p}(n)$), then $\tilde{p}(n)$ will be smaller in general than $p(n)$ and depends only on the prime decomposition of $n$ (which admittedly has a whole host of other problems). “But maybe these two problems are just outliers!” I hear you cry. Let’s slowly build up to an additive problem called Waring’s problem and showcase some of the techniques used to tackle it by first looking at how a similar multiplicative problem might be dealt with.

Given some positive integer $n$, can we find non-negative integers $x$ and $y$ which satisfy \[x^2 \times y^2 = n?\] To solve this problem we can use a trick: $n=(xy)^2$, so $n$ must be a square number. Say $n = m^2$ for some positive integer $m$ so we can re-write \[x \times y = \sqrt{n} = m.\] Now we can appeal to the fundamental theorem of arithmetic, which tells us that $m$ can be written as a unique product of prime numbers, up to reordering. Thus, any $x$ and $y$ must themselves be products of these primes also. Then, after a simple counting exercise, we can even find all possible pairs $x$ and $y$ which solve this equation. Even if we throw more variables than just $x$ and $y$ into the mix, we will only ever find solutions where $n$ is a square number.

This technique will also work for powers other than 2, or for problems with more variables than just $x$ and $y$. In general, for a power $k$ and $s$-many variables $x_1,\dots, x_s$, the equation \[x_1^k x_2^k \cdots x_s^k = n,\] has solutions only when $n = m^k$ for some integer $m$. In this case, exactly as before, the fundamental theorem of arithmetic tells us there exists some (not necessarily distinct) primes $p_1, \dots, p_t$ such that \[ x_1x_2 \cdots x_s = m = p_1p_2\cdots p_t.\] To find all solutions we can set each $x_i~(i=1,\dots,s)$ to some product of the $p_j~(j=1,\dots,t)$, ensuring that each $p_j$ occurs for only one of the $x_i$. This is easy to do precisely because of how ‘restrictive’ multiplication is compared to addition and it shows just how powerful a result the fundamental theorem of arithmetic really is.

Now let’s change this from a multiplicative problem to an additive one, and ask the same question. Given some positive integer $n$, can we find non-negative integers $x$ and $y$ which satisfy
\begin{equation}
\label{eqn:simple}
x^2 + y^2 = n?
\tag{1}
\end{equation}
Suddenly, and despite using the ‘easier’ operation of addition, this has become a much more difficult problem to solve. It’s not even obvious if there are solutions for every $n$. As always, a good place to start when stuck is to try some test cases. Cases $n = 1$ and $n=2$ are both straightforward:
\begin{equation*}
1^2 + 0^2 = 1, \qquad 1^2 + 1^2 = 2.
\end{equation*}
But what about $n = 3$? We can’t have $x$ or $y \geq 2$ as then the left hand side of equation (\ref{eqn:simple}) would be at least 4, a contradiction. We are stuck again. Maybe if we allow more variables we can find solutions for more numbers $n$? Maybe, 3 variables is enough. So the question becomes: given some positive integer $n$, can we find non-negative integers $x,y,z$ which satisfy
\begin{equation*}
x^2 + y^2 + z^2= n?
\end{equation*}
Now, we can find solutions for all $n$ up to 7. But, similarly to $n=3$ in equation \eqref{eqn:simple}, 7 itself poses another problem. Maybe given a positive number $n$ we need four square numbers to be able to write $n$ as a sum of squares, ie
\begin{equation*}
x^2 + y^2 + z^2 + w^2 = n.
\end{equation*}
This now seems promising as we check more and more integers $n$ we can keep finding integers $x,y,z,w$ which satisfy this equation. In fact, Lagrange proved in 1770, by looking at remainders of numbers and their squares when divided by primes, his four-square theorem, which guarantees that 4 variables is enough for any positive integer $n$ we choose.

Phew! That was a lot of work compared to the multiplicative case where the fundamental theorem of arithmetic solves all our woes. To make matters worse the techniques of looking at remainders of cubed numbers and higher powers aren’t as nicely behaved as squares, so, the method to prove Lagrange’s four-square theorem breaks down for these higher powers. We’ve only answered the question for squares! If we allow any power and as many variables as needed, we can state the aforementioned Waring’s problem in full generality.


The intervals for Waring’s problem with $n = 2^k, 3^k, 4^k$ respectively on unit circles in the complex plane are shown by the sections in pink, which are the points $\mathrm{e}^{2\pi\mathrm{i}\alpha}$ satisfying $|\alpha-a/q|<n^{-1+1/(5k)}$

for each $1\leq q\leq n^{1/k}$ and $0\leq a/q\leq 1$. The intervals with smaller contributions are the leftover sections in blue. Notice how the intervals shrink as there are more and more disjoint intervals. In reality the pink sections are much much smaller than what is shown here but then they would be too difficult to see!

Waring’s problem

For a given integer $k$, is there some integer $s$ such that given any positive integer $n$ we can find non-negative integers $x_1, x_2, \dots, x_s$ satisfying
\begin{equation*}
x_1^k + x_2^k + \dots + x_s^k = n?
\end{equation*}
To try and solve this problem we can appeal to techniques from a branch of maths called analytic number theory.

The goal for the problem (and indeed much of analytic number theory) is to find an asymptotic formula, which is an approximation for some desired function that gets better and better with bigger and bigger numbers, then manually check the finitely many numbers leftover which aren’t approximated well. For Waring’s problem, we define the function $r_{k,s}(n)$ to be the number of solutions $(x_1, \dots, x_s)$ to the above equation. Waring’s problem can now be equivalently stated as: Given some $k$, is there an $s$ such that $r_{k,s}(n) \geq 1$ for all positive integers $n$? But, we still need a clever trick to rewrite $r_{k,s}(n)$ in a way that is useful to us. This clever trick comes from a large branch of mathematics called complex analysis.

Complex analysis is a branch of mathematics largely concerned with the theory of functions of complex numbers, but all we need are some results about integrating complex functions in the complex plane. Given some $n$ we can take the seemingly arbitrary function
\begin{equation*}
f(z) = \sum_{m=0}^N z^{m^k},
\end{equation*}
where we require $N \geq n^{1/k}$ and we finally get the integral:
$$
\begin{aligned}
\label{eqn:r}
r_{k,s}(n) = & \frac{1}{2\pi \mathrm{i}}\int_{|z|=1} \frac{f(z)^s}{z^{n+1}}\,\mathrm{d}z \\ = & \int_0^1 f(\mathrm{e}^{2\pi \mathrm{i} \alpha})^s \mathrm{e}^{-2\pi \mathrm{i} \alpha n}\,\mathrm{d}\alpha .
\end{aligned}
$$
Some of you may recognise this as the formula for computing the Fourier coefficients of the periodic function $f(\mathrm{e}^{2\pi \mathrm{i} \alpha})^s$.

The rest of the work is finding suitable bounds and estimates for this integral. It turns out that most of the size of the integral comes from small intervals around rational numbers between 0 and 1 with small denominator. Everything else has a relatively small contribution to the integral.

An example of what these intervals look like on the unit circle can be seen above.

Eventually, after approximating the integral on these small intervals, we ultimately find that for ‘sufficiently large’ $n$, if $s \geq 2^k + 1$ then $r_{k,s}(n)$ behaves like $C n^{s/k – 1}$ for some positive constant $C$, as seen on the next page.

Or, to put it another way, for sufficiently large $n$, $r_{k,s}(n) \geq 1$ and there is at least one solution for every $n$.

The circle method

Under the hood of the proof of Waring’s problem is a technique known as the circle method. Attributed to Hardy, Ramanujan and Littlewood, this method is used by analytic number theorists to solve a wide range of problems. The crux of this method is to find the Fourier coefficients of the function or series in question. This translates the problem from one about, in this case, the integers, to a problem about a sequence or function around a circle. The hope is that there are separate regions around the circle where the evaluation of the function is small (known as the minor arcs) and large (known as the major arcs). The minor arcs, which will form most of the circle, can then be bounded. This leaves the major arcs, where the contribution is most significant, to be studied. This will often result in a more tractable problem.

The values of $r(n)$ (blue) and $Cn^{1.5}$ (orange) for $k=2$, $s=5$. For large $n$, $r(n)$ is bounded between approximately $Cn^{1.5}/2$ and $3Cn^{1.5}/2$.

This is certainly a far cry from the simple method we came up with for our multiplicative problem! But we have our general method that works for any integer $k$. This is an example of a powerful tool called the circle method, which has been used to solve many problems in number theory.

Remember Goldbach’s conjecture mentioned at the start? There’s a similar, weaker problem which has been solved by the circle method called the ternary Goldbach problem, which claims every odd number bigger than 5 can be written as a sum of three prime numbers.

It should be noted however that there are many shortcomings to our work here. The keen-eyed reader may have noticed that at no point did we find a minimal $s$ for each $k$ (and often we massively overshot the minimum). It is also extremely difficult to specify what ‘sufficiently large’ actually means and even when we can the estimate is often in the region of $10^{10,000,000}$. Another drawback is that we are limited by how well we can estimate various integrals along the way, which is often not an easy thing to do. Thus the circle method stands as a warning to all despite popular perception, addition is hard!

Patrick is in the first year of his PhD investigating aspects of the $\ell$-adic Langlands programme (which tries to show two specific numbers being the same isn’t a coincidence) at Durham University. To escape from maths he spends his free time counting rests while playing trombone.
All articles by Patrick

More from Chalkdust