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.

Divergence of Fourier series

In this post, we discuss divergence results of Fourier series; this previous post was about convergence results. We showed earlier that quite general functions, such as Hölder continuous functions, have pointwise convergent Fourier series. It is natural to ask, how far one can push these results so that they remain true. In particular. the cases of arbitrary continuous and integrable functions are very natural to consider, and it turns out that these spaces admit counterexamples. Already in 1873, du Bois-Reymond constructed a continuous function whose Fourier series diverges at a point. The $L^1$-case is even more pathological, as Kolmogorov was able to produce in 1923 an $L^1$-function whose Fourier series diverges pointwise almost everywhere. In 1966, Kahane and Katznelson gave a strengthening of du Bois-Reymond's result: For any set $E\subset(0,1)$ of measure zero, there exits a function whose Fourier series diverges on $E$. This also complements nicely Carleson's result mentioned in the earlier post, since continuous periodic functions have pointwise almost everywhere convergent Fourier series, as they are $L^2$-functions.

We are going to prove the two first mentioned divergence results. Both du Bois-Reymond's and Kolmogorov's proofs are good examples of a general method to construct counterexamples in analysis: Take a set of functions each of which is ''closer'' to being a counter example than the previous ones, and use these functions to form a series that is pathological enough to give the desired counter example. This is also for example the method one usually uses to construct a nowhere differentiable continuous function. However, for du Bois-Reymond's result, we will apply the Banach-Steinhaus theorem, as it is perhaps clearer and emphasizes another important method to show the existence of counterexamples: Suppose there is no counterexample in the function space under consideration, and show that the lack of bad functions leads to too good properties for the space to be true. Another application of that principle would be the proof that there exists a sequence $(a_n)_{n=-\infty}^{\infty}$ converging to zero that is not the sequence of Fourier coefficients of any $L^1$-function (by the Riemann-Lebesgue lemma, the condition for $(a_n)$ is necessary). A drawback of such proofs is that they give no explicit example, but in practice, the constructive proofs are in many cases also not very explicit.

Cyclotomic polynomials

In this post, we consider cyclotomic polynomials, which are a special class of polynomials with various connections to number theory, algebra, and even the constructability of regular polygons using ruler and compass. After deriving the basic properties of cyclotomic polynomials, we use them to give an elementary proof of the infinitude of primes $p\equiv 1 \pmod n$, as well as to determine which regular polygons are constructable. In a later post, we will also see Zsigmondy's theorem on the prime divisors of $a^n-b^n$ as an application of the properties of these polynomials. We assume mostly just basic properties of complex numbers, so the post is suitable for olympiad level.

The cyclotomic polynomials arise from a very simple equation: the equation $z^n=1$, whose complex roots, the $n$th roots of unity, are given by $1,e^{\frac{2\pi i}{n}},...,e^{\frac{2\pi i(n-1)}{n}}$, where $e^{ix}=\cos x +i\sin x$. The number $n$ will always be a positive integer. The roots form a regular $n$-gon in the complex plane. A root $\zeta$ of the equation $z^n=1$ is called a primitive $n$th root of unity if $\zeta^k\neq 1$ for $k<n$, or equivalently if the set $\{1,\zeta,...,\zeta^{n-1}\}$ contains all the roots of $z^n=1$. Then we define the $n$th cyclotomic polynomial as

\[\begin{eqnarray}\Phi_n(x):=\prod_{\zeta\in S_n}(x-\zeta),\end{eqnarray}\]

where $S_n$ is the set of primitive $n$th roots of unity. Clearly the primitive roots are $e^{\frac{2\pi i k}{n}},$ where $(k,n)=1$, so there are $\varphi(n)$ of them. Hence $\Phi_n(x)$ is a monic polynomial of degree $\varphi(n)$. If $\zeta$ is any $n$th root of unity, then $\zeta$ is in a unique $S_d$ where $d\leq n$. We have $d\mid n$ since if $n=kd+r$ with $0<r<d$, we would actually have $\zeta\in S_r$. This gives the important identity

\[\begin{eqnarray}x^n-1=\prod_{d\mid n}\Phi_d(x),\end{eqnarray}\]

since both sides are monic polynomials and the roots of the right-hand side are the elements of the sets $S_d$ for $d\mid n$ (there are no multiple roots as each root belongs to a unique $S_d$). This formula allows us for example to calculate cyclotomic polynomials explicitly. Obviously $\Phi_1(x)=x-1$, and then
\[\begin{eqnarray}\Phi_n(x)=\frac{x^n-1}{\prod'_{d\mid n} \Phi_d(x)},\end{eqnarray}\]

where $'$ denotes that the term $d=n$ is ignored. Hence each cyclotomic polynomial is determined by the previous ones. In particular, the following holds.

Convergence of Fourier series

In this post, we discuss some non-trivial convergence results for Fourier series. Convergence questions for Fourier series have been historically an important motivation for developing entire branches of analysis, such as Lebesgue integration theory and functional analysis. Fourier himself did not address convergence issues when considering Fourier series in 1807, but Dirichlet and Riemann already made significant progress around 1830-1860. Another early result was Dini's test ($\sim$ 1880) which for example implies pointwise convergence of Fourier series of any Hölder continuous function. A bit later, Fejér ($\sim$ 1900) showed that the averages of the Fourier partial sums convergence in the case of a continuous function. Shortly after that, in 1907, Riesz and Fischer proved an elegant theorem about $L^2$ convergence of Fourier series.

We are going to prove the theorems mentioned above. This post deals only with positive results on convergence, as negative results will be considered in a later post. One of course has to mention the marvelous results by Carleson from 1966 that the Fourier series of an $L^2$ function converges pointwise almost everywhere, and by Hunt from 1968 that the same folds for $L^p$ functions $1<p<\infty$. The proofs are notoriously difficult, and we will not address them.

Fourier series and sum identities

We derive the basic properties of Fourier series in this post and apply them to prove some elegant sum and product identities, namely a  formula for the value of the zeta function at even integers and the product formula for the sine function. As mentioned in the introductory post, we want to represent periodic functions (we may assume that the period is $1$ by scaling) that are integrable over the period in the form

\[\begin{eqnarray}f(x)\stackrel{?}{=}\sum_{n=-\infty}^{\infty}\hat{f}(n)e^{2\pi i n x}, \quad x \in \mathbb{R},\end{eqnarray}\]

where the Fourier coefficients for $n\in \mathbb{Z}$ are given by

\[\begin{eqnarray}\hat{f}(n)=\int_{0}^1 f(x)e^{-2\pi i x }dx, \quad n \in \mathbb{Z},\quad f\in L^1([0,1])\end{eqnarray}\]

(by $f\in L^1([0,1]),$ we mean that the restriction of $f$ to $[0,1]$ is Lebesgue integrable).

First of all, if $f$ is a trigonometric polynomial, say $f(x)=\sum_{n=-N}^Na_ne^{2\pi i n x}$, then

\[\begin{eqnarray}\int_ {0}^1 f(x)e^{-2\pi i m x}dx=\sum_{n=-N}^N\int_{0}^1 a_n e^{2\pi i n x}e^{-2\pi i m x}dx=a_m,\end{eqnarray}\]

and more generally whenever integration and summation can be interchanged, the coefficients $\hat{f}(n)$ offer the only possible way to represent $f$ (pointwise) as a trigonometric sum.

Some natural questions about Fourier series arise:

(1) When is a Fourier series convergent, and in what sense:

(1a) pointwise,

(1b) absolutely,

(1c) uniformly,

(1d) on average (in Cesàro sense),

(1e) in $L^p$ norms,

(1f) almost everywhere?

(2) How does smoothness or integrability of $f$ affect the size of the Fourier coefficients $\hat{f}(n)$?

(3) Do the Fourier coefficients $\hat{f}(n)$ characterize $f$ almost everywhere?

(4) Given a convergent trigonometric series, is it the Fourier series of some function?

(5) Does the Fourier series always converge to $f$ if it converges in the first place?

These have been important questions in Fourier analysis for centuries. Nowadays, quite general answers are known to these questions; especially between 1850's and 1960's, a huge amount of progress was made. We will discuss these questions in the following posts.

A very short introduction to Fourier analysis

In later posts, we consider properties of Fourier series (for instance, convergence and divergence results), as well as lacunary trigonometric series and applications of Fourier series to sum identities, combinatorics and number theory. After that, we discuss the Fourier transform in $\mathbb{R}^d$ and phenomena related to it (uncertainty principles, $L^2$ theory, tempered distributions), and applications to the central limit theorem and PDE.

In this post, we say a a bit about Fourier analysis in general. In classical Fourier analysis, we have a function $f:G\to \mathbb{C}$, where $G$ is is usually the integers modulo $N$, that is $\mathbb{Z}_N$, or the real numbers $\pmod 1$, that is $\mathbb{R}/ \mathbb{Z}$, or the whole Euclidean space $\mathbb{R}^d$ ($G$ can also be the integers $\mathbb{Z}$, but that situation is just dual to $G=\mathbb{R}/\mathbb{Z}$). More generally, in harmonic analysis, $G$ could be any locally compact abelian group, and then the analogue of an exponential function would be a homomorphism from $G$ to $\mathbb{C}$. We want to represent the function $f:G\to \mathbb{C}$ as a sum or integral (depending on the domain) of combinations of trigonometric functions. It turns out that a general function, with some mild regularity properties, has such a representation, so many ''linear'' problems concerning arbitrary functions can be reduced to corresponding problems for trigonometric functions (a ''linear'' problem could for instance be a linear PDE, such as the heat equation, which was Joseph Fourier's original motivation, or a problem about arithmetic progressions). We use the trigonometric exponentials $e^{2\pi in x}$ instead of sines and cosines, since otherwise we would have to do everything separately for them. Besides, cosines and sines can be recovered from trigonometric exponentials by taking real and imaginary parts. The representations we are looking for are

$\begin{eqnarray}f(n)&=&\sum_{k\in \mathbb{Z}_N}\hat{f}(k)e^{\frac{2\pi i k}{N}},\quad\quad\,\,\,\,\, \,f:\mathbb{Z}_N\to \mathbb{C}\\f(x)&=&\sum_{n=-\infty}^{\infty}\hat{f}(n)e^{2\pi i n x},\quad \quad f:\mathbb{R}/\mathbb{Z}\to \mathbb{C}\\f(x)&=&\int_{\mathbb{R}^d}\hat{f}(\xi)e^{2\pi i x\cdot\xi}d\xi,\quad \quad f:\mathbb{R}^d\to \mathbb{C},\end{eqnarray}$
where $x\cdot \xi$ is the inner product of two vectors from $\mathbb{R}^d$.

The functions $\hat{f}$ are some coefficient functions, but not just any functions, as these are called the Fourier transform in the continuous case and Fourier coefficients in the discrete case. From the orthogonality relation

$\begin{eqnarray}\int_{0}^{1}e^{2\pi i (m-n)x}dx=\begin{cases} 0, \quad m \neq n\\ 1,\quad m=n,\end{cases}\end{eqnarray}$

(the name comes from the fact that this relation says that the pairwise inner products of distinct functions $e^{2\pi in x}$ are $0$) or from its equivalent for sums it follows, by multiplying both sides of the three equations above by exponentials and integrating (or summing) both sides, that if we formally change the order of integration (or summation), we arrive at

$\begin{eqnarray}\hat{f}(n)&=&\frac{1}{N}\sum_{k\in \mathbb{Z}_N}f(k)e^{-\frac{2\pi i k}{N}},\quad \quad n \in \mathbb{Z}_N\\\hat{f}(n)&=&\int_{0}^1 f(x)e^{-2\pi i n x}dx,\quad\,\,\,\,\,\, n \in \mathbb{Z}\\ \hat{f}(\xi)&=&\int_{\mathbb{R}^d}f(x)e^{-2\pi i x \cdot\xi}dx,\quad \,\,\,\xi \in \mathbb{R}^d\end{eqnarray}$

(in the first case, there is no problem in changing the order of summations). By definition, this is called a Fourier coefficient of $f$ (or the Fourier transform of $f$ in the third case). Notice that these three formulas resemble very much the three representation formulas given above, so the Fourier transform is essentially its own dual operation, and this is of course an important fact. Next we say a few words about the properties of these transforms.

Primitive roots and their applications

In this post we prove the existence of primitive roots modulo prime powers, using elementary number theory and presenting numerous problems in which primitive roots can be applied. This post is suitable for instance for olympiad training.

Introduction

When doing modular arithmetic modulo $n$, whose prime factorization is $p_1^{\alpha_1}...p_k^{\alpha_k},$ it is sensible to consider each of the moduli $p_i^{\alpha_i}$ separately. Indeed, the Chinese remainder theorem guarantees that if we solve a congruence equation modulo each of these prime powers, we can recover the original solution $\pmod n$. This is not only numerically a lot more effective, but also shows that any polynomial congruence problem in $\mathbb{Z}_n$ (the integers $\pmod n$) is reduced to understanding the structure of $\mathbb{Z}_{p^{\alpha}}$ for prime powers (we will encounter this fact many times).

The basic operations are easy to perform in $\mathbb{Z}_{p^{\alpha}}$. Three of them are no harder than in the ordinary integers, and division is also quite easy in $\mathbb{Z}_{p^{\alpha}}$ since the congruence $ax\equiv b \pmod{p^{\alpha}}$ has a unique solution, denoted by $x\equiv \frac{b}{a} \pmod{p^{\alpha}}$, if and only if $a$ and $p$ are coprime. This solution is given by Euclid's algorithm in an effective way. Therefore, it is natural to ask what is an effective way to take roots modulo a prime power or to solve exponential congruences.

The answer lies in exploiting the existence of a primitive root $g$ modulo $p^{\alpha}$, which is an integer such that its powers $g^k$ are noncongruent for $0\leq k<\varphi(p^{\alpha})$ ($\varphi(\cdot)$ is Euler's totient function). By Euler's theorem, $g^{\varphi(q)}\equiv 1 \pmod q$, so a primitive root is an integer whose powers repeat themselves as rarely as possible. Clearly every residue class coprime to $p$ is given by a power of $g$, so if $x\equiv g^{y}\pmod{p^{\alpha}},$ the equation $x^k\equiv a \pmod{p^{\alpha}}$ becomes $g^{ky}\equiv a \pmod{p^{\alpha}}$. In order to solve this new equation, we just need to determine which power of $g$ is congruent to $a$ (the answer is unique modulo $\varphi(p^{\alpha})$), and then perform a division, which is easy. Similarly, if we write $a\equiv g^m \pmod{p^{\alpha}}$, the equation $a^x \equiv b \pmod{p^{\alpha}}$ reduces to $g^{mx}\equiv b \pmod{p^{\alpha}}$, which can be solved in the same way as the former congruence. Hence, primitive roots work much in the same way as logarithms do in $\mathbb{R}$, but they are much more interesting, since they are by no means trivial despite their usefulness.

To appreciate primitive roots, it is good to know that before calculators people computed using logarithm tables. This is because all the basic operations are reduced to easier ones by taking logarithms, so one only needs a table of the values of the logarithm. However, in modular arithmetic, calculators have not replaced discrete logarithms, which are based on primitive roots, since the numbers that one computes with can be enormous (for example, one may want to compute $2^n\pmod m$, where $n$ is some number greater than one million, say), while the results are of reasonable size, namely smaller than the modulus. The fact that computing discrete logarithms, or equivalently finding primitive roots, is hard is the basis of many cryptosystems that are used for secure data transfer.