Roth's theorem on arithmetic progressions

In this post, we give an application of Fourier analysis to combinatorics, more precisely to Ramsey theory. In Ramsey theory, a typical result tells that certain large but otherwise arbitrary objects (sets of integers, graphs, collections of points, etc.) are forced to contain some structure in them, thus implying intuitively that there is no complete randomness. The desired structure in these objects could mean for example large cliques or independent sets of vertices in the case of graphs, or some arithmetic structure in the case of sets of integers. One of the most basic arithmetic structures is of course an arithmetic progression, and there are several Ramsey theoretic results about their occurrence. We mention the following two theorems.

Theorem 1 (van der Waerden). Let $k$ and $\ell$ be positive integers. Then there exists a number $W(k,\ell)$ such that whenever the numbers in $\{1,2,...,N\}$ with $N\geq W(k,\ell)$ are colored using $\ell$ colors, there is a monochromatic arithmetic progression of length $k$ .

Theorem 2 (Szemerédi). Let $\delta>0$, and let $k$ be a positive integer. Then, if $A$ is any subset of $\{1,2,...,N\}$ with $N\geq N(k,\delta)$ and having density at least $\delta$ (that is, $|A|\geq \delta N$), the set $A$ contains an arithmetic progression of length $k$.

The first result was proved by van der Waerden in 1927 (back then, the result was an open problem that many famous mathematicians attempted to resolve, but it was the young van der Waerden who solved it). The latter result is a very deep and important result of Szemerédi from 1975 (the proof was so complicated that Szemerédi refused to write it down himself). Szemerédi's proof was based on his graph regularity lemma, and virtually every proof of the theorem has started a fruitful new research direction. For instance, Furstenberg proved the theorem using ergodic theory in 1977, and Gowers using Fourier analytic methods and his uniformity norms in 2001, and the latter proof also improved bounds on $W(k,\ell)$ enormously.

It is easy to see that van der Waerden's theorem is a special case of Szemerédi's; indeed, if $\{1,2,...,N\}$ is colored with $\ell$ colors, there is at least one monochromatic subset of density at least $\frac{1}{\ell}$. In addition, both theorems allow immediately an infinite version. For Szemerédi's theorem, the infinite version is that any subset of the natural numbers with a positive lower density contains arbitrarily long arithmetic progressions. In fact, there is a nice compactness argument that can be used to deduce the finite versions of the theorems from their infinite versions, but that is a different story.

We will not try to prove Szemerédi's theorem in this post, but we will prove its special case $k=3$ due to Roth from 1953. This case is an elegant and relatively short application of Fourier analysis into combinatorics. For convenience, we also formulate this claim.

Quadratic reciprocity via discrete Fourier analysis

In this post, we give a proof of the law of quadratic reciprocity based on discrete Fourier analysis and more precisely Gauss sums. This celebrated theorem has numerous proofs, but the most elementary ones usually boil down to some tedious combinatorial computations. In particular, after one has derived Gauss' lemma or some similar statement that is usually used in the proof, the big picture may become unclear, and one is left with some combinatorial counting problem. On the other hand, if one uses discrete Fourier analysis to prove the reciprocity law, the structure of the proof is simple, and one works in the context of trigonometric sums instead of solving an isolated combinatorial problem. Moreover, this method generalizes to higher reciprocity laws as well, and similar ideas as in what follows can be applied for example in proving the functional equation of the $L$-functions, the class number formula or the Pólya-Vinogradov inequality. Some of these results will be discussed in later posts.

Lacunary trigonometric series

In this post, we consider trigonometric series that do not necessarily arise from Fourier series. In particular, we consider lacunary trigonometric series

\[\begin{eqnarray}\sum_{n=0}^{\infty}(a_k\cos(2\pi n_k x)+b_k\sin(2\pi n_k x)),\quad\frac{n_{k+1}}{n_k}\geq \lambda >1\quad \text{for all}\quad k. \quad \quad (1)\end{eqnarray}\]

(It turns out that the sine and cosine form is more convenient than the complex exponential form in what follows). In other words, the frequencies of the trigonometric functions always grow by at least a factor of $\lambda$. It turns out that for such series, one can formulate some interesting convergence and integrability results that are not generally valid for trigonometric series. For example, Zygmund showed in 1930 that a lacunary series converges in a set of positive measure iff the sum of squares of its coefficients converges iff the lacunary series converges almost everywhere. This answers very broadly the question of convergence of such a series, while for a general trigonometric series the task of finding such a convergence criterion is hopeless. In the same paper, Zygmund proved that a lacunary series always converges in a dense set that even has the cardinality of the real numbers, unless the series is trivially divergent, that is $a_k^2+b_k^2\not \to 0$.

Another intriguing property of lacunary trigonometric series is that if such a series converges pointwise almost everywhere, its value distribution is random; in fact, the value distribution of its partial sums approaches the normal distribution. This was shown by Salem and Zygmund in 1947. It is also interesting to study whether a lacunary series is the Fourier series of some integrable function. Kolmogorov proved in 1924 that if this is the case, then this lacunary Fourier series converges almost everywhere, so for lacunary Fourier series, there are no problems with convergence (this of course follows from Carleson's result about pointwise almost everywhere convergence of $L^2$-functions, but the proof for lacunary series is much simpler, though not trivial).

It must also be mentioned that lacunary trigonometric series, whose frequencies grow too fast compared to the decay of the coefficients, are a good way to construct continuous nowhere differentiable functions, and indeed Weierstrass' example is a lacunary series.

The study of trigonometric series is also closely related to complex analysis, since the boundary values of an analytic function $f(z)=\sum_{n=0}^{\infty}a_nz^n$, defined in the unit disc, are given by the series $\sum_{n=0}^{\infty}a_ne^{in x}$, and conversely, a trigonometric series gives rise to an analytic function in the unit disc, whose boundary values are given by the trigonometric series, unless the coefficients grow too fast.

The above results (which are just a tiny proportion of what is known) should motivate the study of (lacunary) trigonometric series quite well. We will prove some of the mentioned results, following closely the original papers mentioned above.

Irreducibility of polynomials

In many contexts, it is important to know whether a polynomial is irreducible. In algebraic number theory, the properties of an algebraic number $\alpha$ are determined by its minimal polynomial, the irreducible monic polynomial of least degree having $\alpha$ as a root. In Galois theory, it is important to know whether a field extension arises from an irreducible polynomial. In algebraic geometry, one is interested in varieties arising from the zero set of a set of multivariate polynomials, and if some of the polynomials are reducible, the variety can be represented in simpler terms. There are many more examples as well.

By the fundamental theorem of algebra, polynomials with complex coefficients always factor into linear factors in $\mathbb{C}[x].$ From this it follows that real polynomials factor into at most quadratic factors in $\mathbb{R}[x]$. However, in $\mathbb{Q}[x]$ and $\mathbb{Z}[x]$, irreducibility is much more interesting. By Gauss' lemma, irreducibility in both of them is the same thing, so we consider only $\mathbb{Z}[x]$ (every polynomial in $\mathbb{Q}[x]$ becomes a polynomial with integer coefficients when multiplied by a suitable integer).

In what follows, by polynomials we mean polynomials with integer coefficients in one variable and irreducibility is considered in $\mathbb{Z}[x]$, unless otherwise noted. In this post, we present a few methods to determine whether a polynomial is irreducible. For some reason, it seems that the Eisenstein criterion is almost the only irreducibility criterion that is truly well-known, even though it fails for many polynomials.