This page contains explanations pertaining to the "Some Number Theory" section of Roth's paper.
The Dirichlet Box Principle
Let $\alpha$ be a positive real number and $\widehat{M}$ a positive integer. Then there exists a positive integer $q$ and and integer $h$ with $0<q< \widehat{M}$ for which $- \frac{1}{\widehat{M}} < q\alpha - h < \frac{1}{\widehat{M}}$.
This result follows, perhaps surprisingly, from the Pigeonhole Principle. That is, the fact that if you have $l$ pigeonholes and strictly more than $l$ pigeons, than at least one pigeonhole must contain more than one pigeon.
We consider the following numbers
(1)and note that each $\alpha_i$ (being the non-integral part of $i\alpha$) is contained in the interval $[0,1)$.
We now split $[0,1)$ into $\widehat{M}$ subintervals:
(2)We now have $\widehat{M}$ subintervals and $widehat{M}+1$ numbers, so by the pigeonhole principle there exists at least one subinterval containing two of the numbers, say $\alpha_k$ and $\alpha_j$.
We therefore know that
(3)Then we see that by using the definition of the $\alpha_i$ we have
(4)Repeating with $\alpha_j - \alpha_k$ and denoting $(\lfloor k \alpha \rfloor) - \lfloor j \alpha \rfloor)$ by $H$ we get
(5)Now to finish the proof, if $k>j$ put $q=k-j$ and $h=H$. If $k<j$ we set $q=j-k$ and $h=-H$. It follows from our construction that these choices satisfy the needed condition.
When q is greater than 1, S' vanishes
If $q>1$ then $S'=0$.
If $q>1$ then we look at the factor
(6)Now as $(h,q)=1$ we see that $rh$ modulo $q$ produces all the integers from 0 to $q-1$ and so the sum (as $q \neq 1$) gives us 0.
Inequality on S and S'
The following inequality holds $|S - S'| < M a(m) - U + O\left( m \sqrt{M} \right)$ (Recall that $U$ is the size of our $\mathcal{A}$-set in $\{1,2,\ldots, M\}$ and that $m<M$)
We prove this result through the use of the following two lemmata
Rewriting S
We can rewrite S as $S = \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M \sum e(\alpha u_k) + O\left(mq\right)$where the inner sum ranges over $n \leq u_k n+mq$ such that $u_k \equiv r \mod q$.
First we note that for a fixed $u_k$, fixed $m$ and fixed $q$ then there are precisely $mq$ integers $n$ satisfying
(7)namely, the set $\{u_k - mq + 1, u_k - mq + 2, \ldots, u_k - 1, u_k\}.$
Also if
(8)then it is clear that these values of $n$ must lie in $[1,M]$.
Now, if $mq \leq u_k < M-mq$ then from above the coefficient of $e(\alpha u_k)$ simplifies to $\frac{mq}{mq}$, that is, 1. This gives us the summation of exponential terms in our restatement of $S$.
However, if $u_k < mq$ or $M-mq \leq u_k \leq M$ then there are at most $2mq$ terms to consider, which is compensated for, by the $O(mq)$ term.
Relation of S and S'
We will show that $S = S' - \left( \frac{1}{mq} \sum_{r=1}^q e\left( \frac{rh}{q} \right) \sum_{n=1}^M e(\beta n)D(n,m,q,r) \right) + O(mq) + O(mqM|\beta|)$ where $D(n,m,q,r)\geq 0$.
We begin by looking at the inner sum in our representation of S. By the Dirichlet Box Principle we have
(9)But we can now use the fact that all the terms in this inner sum obey
(10)to rewrite $u_k$ as $Qq+r$ so that this becomes
(11)We now write $u_k$ as $n + \eta$ where $0 \leq \eta < mq$ (as we are only dealing with terms such that $n \leq u_k < n+mq$) to simplify furhter:
(12)We know that at most the number of terms in this inner section is $A(m)$ (as $A(m)$ also applies to arithmetic sequences). We can write this number as $A(m) - D(n,m,q,r)$ where $D \geq 0$.
We now replace each term in the representation of S and so we can rewrite $S$ as follows:
(13)as required.
Completing proof of the inequality on S and S'
We can now prove the statement:
The following inequality holds $|S - S'| < M a(m) - U + O\left( m \sqrt{M} \right)$ (Recall that $U$ is the size of our $\mathcal{A}$-set in $\{1,2,\ldots, M\}$ and that $m<M$)
We start by setting $\beta$ and $h$ to be zero to make some estimations. This is allowed as we have not yet used $(h,q)=1$. We are first going to estimate
(14)To do this we substitute $\beta = 0$ and $h=0$ back into the relationship between S and S' to get
(15)But now, if $\beta$ and $h$ are 0, then so is $\alpha$ and so
(16)and
(17)We can then substitute back to get
(18)and so when $h$ and $\beta$ are zero we have:
(19)As $\alpha$ is positive, we can estimate as follows:
(20)and we use the fact that $q\leq \sqrt{M}$ and $q|\beta| \leq (\sqrt{M})^{-1}$ and get
(21)which is what was required.