Some Number Theory

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

\begin{align} \alpha_i = (i\alpha) - \lfloor i\alpha \rfloor, \qquad i=0,1,2,\ldots,\widehat{M} \end{align}

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:

\begin{align} \left[ \frac{r}{\widehat{M}}, \frac{r+1}{\widehat{M}}\right), \qquad r=0,1,\ldots,\widehat{M}-1. \end{align}

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

\begin{align} -\frac{1}{\widehat{M}} < \alpha_k - \alpha_j < \frac{1}{\widehat{M}}. \end{align}

Then we see that by using the definition of the $\alpha_i$ we have

\begin{align} -\frac{1}{\widehat{M}} < (k-j)\alpha - (\lfloor k\alpha \rfloor - \lfloor j \alpha \rfloor). \end{align}

Repeating with $\alpha_j - \alpha_k$ and denoting $(\lfloor k \alpha \rfloor) - \lfloor j \alpha \rfloor)$ by $H$ we get

\begin{eqnarray} -\frac{1}{\widehat{M}} < &(k-j)\alpha - H& < \frac{1}{\widehat{M}}\\ -\frac{1}{\widehat{M}} < &(j-k)\alpha + H& < \frac{1}{\widehat{M}} \end{eqnarray}

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

\begin{eqnarray} \left( \sum_{r=1}^q e\left(\frac{rh}{q}\right) \right) &=& \left( \sum_{r=1}^q e^{2\pi i \left(\frac{rh}{q}\right)} \right)\\ &=& \left( \sum_{r=1}^q \left( e^{2\pi i \left(\frac{r}{q}\right)} \right)^h \right). \end{eqnarray}

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

\begin{equation} n 'leq u_k < n + mq, \end{equation}

namely, the set $\{u_k - mq + 1, u_k - mq + 2, \ldots, u_k - 1, u_k\}.$

Also if

\begin{align} mq \leq u_k < M-mq \end{align}

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

\begin{eqnarray} e(\alpha u_k) &=& e\left( \left( \frac{h}{q} + \beta \right) u_k \right)\\ &=& e\left( \frac{h}{q}u_k \right) e(\beta u_k). \end{eqnarray}

But we can now use the fact that all the terms in this inner sum obey

\begin{align} u_k \equiv r \mod q \end{align}

to rewrite $u_k$ as $Qq+r$ so that this becomes

\begin{eqnarray} e(\alpha u_k) &=& e\left( \frac{h(Qq+r)}{q} \right) e(\beta u_k)\\ &=& e(hQ) e\left(\frac{hr}{q}\right) e(\beta u_k). \end{eqnarray}

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:

\begin{eqnarray} e(\alpha u_k) &=& e(hQ) e\left(\frac{hr}{q}\right) e(\beta(n+\eta))\\ &=& e(hQ) e\left(\frac{hr}{q}\right) e(\beta n)e(\beta \eta)\\ &=& e\left( \frac{hr}{q} \right) e(\beta m) \left( e(hQ) e(\beta n) \right)\\ &\leq& e\left( \frac{hr}{q} \right) e(\beta n) \left( 1 + hQ|\beta| n\right)\\ &=& e\left(\frac{hr}{q}\right) e(\beta n) + O\left( mq|\beta| \right). \end{eqnarray}

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:

\begin{eqnarray} S &=& \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M \sum_{\substack{n \leq u_k n+mq\\u_k \equiv r \mod q}} e(\alpha u_k) + O(mq) \\ &=& \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M \sum_{\substack{n \leq u_k n+mq\\u_k \equiv r \mod q}} e\left( \frac{rh}{q} \right) e(\beta n) + O(mq|\beta|) + O(mq) \\ &=& \frac{1}{mq} \sum_{r=1}^q e\left(\frac{rh}{q}\right) \sum_{n=1}^M (A(m) - D(n,m,q,r))(e(\beta n) + O(mq|\beta|)) + O(mq)\\ &=& \left( \frac{A(m)}{m} \frac{1}{q} \sum_{r=1}^q e\left(\frac{rh}{q}\right) \sum_{n=1}^M e(\beta n) + O(mqM|\beta|) \right)\\ && \quad -\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) + O(mqM|\beta|) \right) + O(mq)\\ &=& 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|). \end{eqnarray}

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

\begin{align} \sum_{r=1}^q \sum_{n=1}^M D(n,m,q,r). \end{align}

To do this we substitute $\beta = 0$ and $h=0$ back into the relationship between S and S' to get

\begin{eqnarray} S &=& S' - \frac{1}{mq} \sum_{r=1}^q e(0) \sum_{n=1}^M e(0) D(n,m,q,r) + O(mq) + O(0)\\ &=& S' - \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M D(n,m,q,r) + O(mq). \end{eqnarray}

But now, if $\beta$ and $h$ are 0, then so is $\alpha$ and so

\begin{align} S = \sum_{k=1}^U 1 = U, \end{align}


\begin{eqnarray} S' &=& \frac{a(m)}{q} \left( \sum_{r=1}^q e(0) \right) \left( \sum_{n=1}^M e(0) \right)\\ &=& \frac{Ma(m)q}{q} = Ma(m). \end{eqnarray}

We can then substitute back to get

\begin{align} U = Ma(m) - \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M D(n,m,q,r) + O(mq) \end{align}

and so when $h$ and $\beta$ are zero we have:

\begin{align} \sum_{r=1}^q \sum_{n=1}^M D(n,m,q,r) = mMqa(m) - Umq + O(mq). \end{align}

As $\alpha$ is positive, we can estimate as follows:

\begin{eqnarray} |S-S'| &=& \left| - \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|) \right|\\ &<& \frac{1}{mq} (mMqa(m) - Umq) + O(mq) + O(mqM|\beta|)\\ &=& Ma(m) - U + O(mq) + O(Mmq|\beta|) \end{eqnarray}

and we use the fact that $q\leq \sqrt{M}$ and $q|\beta| \leq (\sqrt{M})^{-1}$ and get

\begin{eqnarray} |S-S'| &<& Ma(m) - U + O\left(m \sqrt{M} \right) + O\left( M m \sqrt{M}^{-1} \right)\\ &=& Ma(m) - U + O \left(m \sqrt{M} \right) \end{eqnarray}

which is what was required.