Euler’s proof of pentagonal theorem

A masterpiece argument to establish the infamous pentagonal identity due to Euler. It is believed that the proof discussed in this blog post is due to Euler.

Fedya Petrov's blog

View original post

Course materials

Hello everyone. Recently, I decided to upload some course materials, which I have prepared based on lectures I have been a part of, on the course materials webpage .

These notes will be updated regularly.

In some instances, I may also share some sections from my unpublished book, or other course related documents I have prepared.

Waring’s problem and an introduction to the circle method

This blog post aims to discuss about Waring’s problem, its formulation and a proof in terms of the circle method (which is also known as Hardy-Littlewood method).

Let for any positive integers k, s, N we denote the number of solutions to the equation

N = x_1^k + ....... + x_s ^k ~~~~~~ (1),

with x_1 , ...... , x_s \in \mathbb{Z}_{ \ge 0}, as r_{s,k}(N).

In 1770, Edward Waring posed the following problem :

For every positive integer k there exists some positive integer s such that, r_{s,k} (N) > 0 for every positive integer N.

It remained unanswered for a long time, until building up on a partial progress due to Hurwitz, David Hilbert proved the assertion to be true, thereby solving the infamous Waring’s problem. We shall not discuss Hilbert’s proof in this blog post, since it happens to be well-known and can easily be found on the internet.

Consider the number r_{s,k}(N). In following the circle method, we write this number r_{s,k}(N) of solutions as an integral.

Here, I shall be demonstrating this basic instance of the circle method by writing the number r_{s,k} (N) as an integral in this case.

We begin by recalling the notation e(t) = e^{2 \pi i t} where as usual i is the imaginary unit, and e is Euler’s infamous number.

For any \alpha \in \mathbb{R}, suppose

\displaystyle T(\alpha) = \sum_{x= 1}^{P} ( e( \alpha x) ^k) ~~~~~ (2),

where P is a positive integer.

We may write T(\alpha)^s as

\displaystyle T(\alpha)^s = \sum_m r'(m) e(m \alpha) ~~~~~~ (3),

where r'(m) represents the number of solutions to m = x_1 ^k + .... + x_s ^k with 1 \le x_i \le P. This can be seen by multiplying the expression of T(\alpha) (in (2)) s many times, and observing that in the power of exponential we would get sum of k th powers, and then taking it as m.

If P \ge \lfloor N ^{1/k} \rfloor then, r'(N) would be the same as r_{s,k}(N).

Now, multiplying both sides of equation (3) with e(-N \alpha), and integrating it over (0,1) (and by exploiting the orthogonality of complex exponential integral) yields

\boxed{r_{s,k}(N) = \int_{0}^{1} (T(\alpha)^s \cdot e(-N \alpha) )d \alpha}. ~~~~~~ (4)

The expression in (4) above allows us to write the number of solutions to the equation (1) as an integral.

Now, we make a claim the proof of which is left as an easy exercise for the reader :

Exercise : Prove that in the asymptotic formula given for r_{s,k}(N) above, the main term is of order N^{s/k - 1} = P^{s-k}.

(Hint : Try to prove this combinatorially)

This observation allows us to neglect all those \alpha which contribute an amount of order strictly lower than P^{s-k} to the integral in (4).

We consider s \ge 2^k +1, and regard the absolute value of the integrand as

\displaystyle |T( \alpha) | ^s = |T(\alpha)|^{s-2^k} \cdot |T(\alpha)|^{2^k} ~~~~~~ (5).

Then, an appeal to Hua’s inequality allows us to neglect all those \alpha for which |T(\alpha)| << P^{1- \delta}, where as usual << denotes the Vinogradov asymptotic symbol.

A general plan in working with Waring’s problem and other similar problems is to divide the values of \alpha into two sets : the major arcs whose contribution shapes the main term, and the minor arcs the contribution of which goes to the error term. The distinction between these sets depend very much on the available results about the main term.

Loosely speaking, while powerful (although involved) methods are available for dealing with the major arcs, the crux of the problem lies with the minor arcs. Once a method to deal with minor arcs is known, one tries to extend the method as much as the setup of the problem permits, to ease the work of dealing with major arcs (though dealing with major arcs are usually more straightforward).

Around every rational number a/q (in lowest form), we put an interval \mathfrak{M}_{a,q} given by the conditions

\displaystyle \mathfrak{M}_{a,q} ~~ : ~~ |\alpha - a/q| < P^{\delta - k} ~~~~~~ (6),

and we do this for 1 \le q \le P^{\delta},  1 \le a \le q, and (a,q)=1.

It is easy to notice that the distance between the centres of these intervals is \ge P^{-2 \delta} and this being greater than their length implies that these intervals do not overlap. Moreover by rounding and translation, we can assume that these intervals are contained in [0,1].

Invoking Weyl’s inequality, one can see that these intervals \mathfrak{M}_{a,q} gives the major arcs, and their complement relative to [0,1] give the minor arcs, the totality of which we denote by \mathfrak{m}.

Lemma : If s \ge 2^k + 1, then we have

\displaystyle \int_{\mathfrak{m}} | T(\alpha)| ^s d \alpha << P^{s-k-\delta'} ~~~~~~ (7),

where \delta' is a positive number depending upon \delta.

Proof : Invoking a classical result due to Dirichlet on rational approximations, we get that : for every \alpha one can find a rational number a/q satisfying 1 \le q \le P^{k- \delta}, and

\displaystyle |\alpha - a/q| < q^{-1} P^{-k + \delta} ~~~~~~ (8).

Furthermore, if 0 < \alpha <1, then we shall have : 1 \le a \le q. Since (8) gives a stronger criteria than (6), so it follows that : we should have \alpha \in \mathfrak{M}_{a,q} if q \le P^{\delta}. In other words, this means for every \alpha \in \mathfrak{m} we must have q > P^{\delta}.

Since, |\alpha - a/q| \le q^{-2}, so applying Weyl’s inequality to the exponential sum T(\alpha), and using the fact that P^k / q \ge P^{\delta}, we get :

|T(\alpha)| << P^{1 + \varepsilon - \delta / K}, where K= 2^{k-1}.

Now, applying Hua’s inequality to this we get :

\displaystyle \int_{\mathfrak{m}} |T(\alpha)|^s d \alpha << P^{(s-2^k)(1 + \varepsilon - \delta / K)} \int_{0}^{1} |T(\alpha)|^{2^k} d \alpha << P^{s - k- \delta'},

where \delta' >0 and depends on \delta.

This concludes the proof of the above lemma. \square

We now turn our attention to the major arcs \mathfrak{M}_{a,q}.

Lemma : For \alpha = \beta + a/q \in \mathfrak{M}_{a,q}, we have

\displaystyle T(\alpha) = q^{-1} S_{a,q} I(\beta) + O(P^{2 \delta} ) ~~~~~~ (9),


S_{a,q} = \sum_{z=1}^{q} e(az^k / q), and I(\beta) = \int_{0}^{P} e(\beta \xi ^k) d \xi.

Proof : To begin with, we collect those values of x in the sum defining T(\alpha) which are in the same residue class modulo q. To do this, we write x = qy+z, with 1 \le z \le q. Here, y runs through an interval depending upon z, corresponding to 0 < x \le P. Now, doing this and making use of the fact that e^{2 \pi i h} = 1 for any integer h, we conclude that :

\displaystyle T(\alpha) = \sum_{z = 1}^{q} e(az^k / q) \sum_{y} e(\beta (q y + z)^k) ~~~~~~ (10).

Now, we attempt to replace the discrete variable y by a continuous variable \eta in a quest to replace the \sum_y by an integral \int over \eta. After this, we can make a change of variable from \eta to \xi = q \eta + z. This would allow us to replace the summation over y by the integral q^{-1} I(\beta).

So, all that remains now, is to estimate the error in going from the summation to the integral.

Exercise : If f is a differentiable function, then prove that for |\eta - y| \le 1/2, we must have |f(y) - f( \eta ) | \le \frac{1}{2} \cdot \max | f' (\eta) |.

(Hint : Use Lagrange’s Mean Value Theorem)

From the above exercise, we see that if we divide any interval A < \eta < B into intervals of length 1, together with two possibly broken intervals, then we obtain :

\displaystyle  \left | \int_{A}^{B} f( \eta) d \eta - \sum_{A < y< B} f(y) \right | << (B-A) \max | f' (\eta)| + \max | f( \eta) |.

In this case, we have : f( \eta) = e ( \beta (q \eta + z)^k), and hence \max | f' (\eta )| <<  q |B| P^{k-1}, and \max |f( \eta ) | = 1.

Also, in this case B - A << P / q. Furthermore, from the very definition of \mathfrak{M}_{a,q} we would have : |\beta| << P^{-k + \delta}.

Hence the error in replacing the sum by the integral is << P q^{-1} q | \beta| P^{k-1} + 1 << P^{ \delta }.

Finally we notice that q \le P^{ \delta} and hence multiplying by q from outside gives us the error bound we had in (9).

This completes the proof of the lemma. \square

Remark : The above proof of the lemma demonstrates a way to replace summation by integrals. There are other effective ways to do this. Such techniques of replacing summations by integrals and bounding the error term play a crucial role when one deals with asymptotic behaviour of terms as we are doing here.

In a previous lemma, we dealt with the minor arcs. Now, we consider dealing with the major arcs.

Now, we define the singular series \mathfrak{S}(N) for Waring’s problem as :

\displaystyle \mathfrak{S}(N) = \sum_{q=1}^{\infty} \sum_{1 \le a \le q ; (a,q)=1} (q^{-1} S_{a,q})^{s} e(-N a/q) ~~~~~~ (11).

Lemma : If \mathfrak{M} denotes the totality of the major arcs, then

\displaystyle \int_{\mathfrak{M}} T(\alpha)^s e(-N \alpha) d \alpha = P^{s-k} \mathfrak{S}(P^{\delta} , N) J(P^{\delta} + O(P^{s-k-\delta'}) ~~~~~~ (12)

where J(P^{\delta}) = \int_{| \gamma | < P^{\delta}} \left ( \int_0 ^1 e( \gamma \xi ^k) d \xi \right ) ^s e(- \gamma) d \gamma.

We notice that, the above quantities allows us to deal with r_{s,k}(N) = \int_{\mathfrak{m}} T(\alpha)^s e(-N \alpha) d \alpha + \int_{\mathfrak{M}} T(\alpha)^s e(-N \alpha) d \alpha.

In fact we shall have :

Theorem : If s \ge 2^k +1, then

\displaystyle r_{s,k}(N) = C_{k,s}N^{s/k - 1} \mathfrak{S}(N) + O(N^{s/k -1 - \delta'})

for some fixed \delta ' >0, and where C_{k,s} = \frac{ \Gamma (1 + 1/k) ^s}{ \Gamma ( s/k) } > 0.

We shall gloss over the proof of this theorem, because it is quite technical in nature. One may refer to a paper by Landau for the proof.

Finally we notice that, the above theorem would give us what we aimed to prove.

There are several other equations, where the circle method finds a prominent place. For a survey on the remarkable circle method, one may refer to the book on Hardy-Littlewood method authored by Vaughan. The interested reader is suggested to take a look at this wonderful blog post on circle methods and its limitations (heuristics) authored by Prof. Terence Tao.

#circle-method, #number-theory, #warings-problem

A note on Combinatorial Nullstellensatz

Hi everyone !

Last year around this time I was introduced to the immensely powerful technique of combinatorial nullstellensatz (devised by prof. Noga Alon) by prof. Fedor Petrov.

I wanted to share a note on this remarkable technique with the audience here. I had two options : make a blog post and use the LaTeX feature of wordpress to type everything out here, or upload a file for the audience to read. I chose the latter one, since in my opinion it is more convenient.

Hope you enjoy reading this note. Feel free to comment below.

Dilworth’s, Mirsky’s and Erdős–Szekeres’s theorems for partially ordered sets

Just today morning, after solving a problem here using the infamous Erdős–Szekeres theorem, I felt like posting some details of it over here, which I wrote earlier, and edited recently to add some examples.

So, I wrote this post, to share the handout I prepared on these contents. This is a part of the write-up on the notes from the advanced combinatorics course at St. Petersburg State University delivered during the 2019-2020 session.

For viewing the images, please click on the image to view it better.