Pomerance Theorem on colinear points in certain paths in a two dimensional lattice

— 1. Introduction —

Van der Waerden’s theorem (to which I gave two proofs in previous posts on this blog) states that if one colors the positive integers with finitely many colors, then one can always find a monochromatic arithmetic progression of arbitrary length.

It is not too hard to show that this result is equivalent to the following:

Theorem 1 Let ${(a_n)_{n\in{\mathbb N}}}$ be an increasing sequence of positive integers such that for all ${n\in{\mathbb N}}$ we have ${a_{n+1}-a_n<d}$ for some fixed ${d\in{\mathbb N}}$ . Then the set ${\{a_n:n\in{\mathbb N}\}}$ contains arbitrarily long arithmetic progressions.

Proof: Let ${A=\{a_n:n\in{\mathbb N}\}}$ and notice that ${A\cup(A-1)\cup\cdots\cup(A-d)}$ covers all of ${{\mathbb N}}$ (here, as usual, we use the convention that ${E-x:=\{e-x:e\in E\}}$ whenever ${E}$ is a set and ${x}$ and integer). Thus by the van der Waerden theorem one of the shifts ${A-i}$ contains arbitrarily long arithmetic progressions. Since a shift of an arithmetic progression is still an arithmetic progression we conclude that ${A}$ contains arbitrarily long arithmetic progressions. $\Box$

The proof that Theorem 1 implies van der Waerden’s theorem is a little bit more complicated and I will omit it. Now there are many ways in which one can extend this theorem. The most well known extension is Szemerédi’s theorem, which states that a set with positive upper density contains arbitrarily long arithmetic progressions. Recall that the upper density of a set ${E\subset{\mathbb N}}$ is defined as

$\displaystyle \bar d(E)=\limsup_{N\rightarrow\infty}\frac{\big|E\cap\{1,2,\dots,N\}\big|}N$

Since in a finite coloring of ${{\mathbb N}}$ one of the colors must have positive density, it follows that van der Waerden’s theorem is an easy corollary of Szemerédi’s theorem. Another way to see this is to reformulate Szemerédi’s theorem:

Theorem 2 Let ${(a_n)_{n\in{\mathbb N}}}$ be an increasing sequence of positive integers such that

$\displaystyle \liminf_{N\rightarrow\infty}\frac1N\sum_{i=1}^Na_{i+1}-a_i<\infty$

Then ${A:=\{a_n:n\in{\mathbb N}\}}$ contains arbitrarily long arithmetic progressions.

This means that if the averaged difference between consecutive terms of the sequence ${(a_n)_{n\in{\mathbb N}}}$ is uniformly bounded, then ${A}$ contains arbitrarily long arithmetic progressions. Of course the sum in this formulation is telescopic, but below it will be clear why I formulated the result this way.

Other extensions include multidimensional extensions. For instance, we have the multidimensional Szemerédi theorem (due to Furstenberg and Katznelson) which we formulate here for 2 dimensions.

Theorem 3 Let ${E\subset{\mathbb N}^2}$ be such that

$\displaystyle \limsup_{N\rightarrow\infty}\frac{\big|E\cap\{1,\dots,N\}^2\big|}{N^2}>0$

Then for every ${k}$ there exists ${a\in{\mathbb N}^2}$ and ${b\in{\mathbb N}}$ such that ${\big\{a+b(i,j):i,j\in\{0,\dots,k\}\big\}\subset E}$ .

Another direction in which one can move to higher dimensions is the following: Let ${(a_n)_{n\in{\mathbb N}}}$ be a sequence in ${{\mathbb N}^2}$ such that

$\displaystyle \liminf_{N\rightarrow\infty}\frac1N\sum_{i=1}^N\|a_{i+1}-a_i\|<\infty$

then does ${A=\{a_n:n\in{\mathbb N}\}}$ contain arbitrarily long arithmetic progressions? And what if impose the stronger condition that ${a_{n+1}-a_n\leq d}$ for some fixed ${d}$ and every ${n}$ ? It turns out that the answer is negative, although this is not at all obvious. The counterexample works for ${d=1}$ and is due to Justin (see this paper), and an easier construction was found by Dekking, with no four terms in an arithmetic progression.

The next question is whether one can obtain arbitrarily many collinear points. The answer is true and is due to Pomerance.

Theorem 4 (Pomerance’s theorem) Let ${(a_n)_{n\in{\mathbb N}}}$ be a sequence in ${{\mathbb N}^2}$ such that

$\displaystyle \liminf_{N\rightarrow\infty}\frac1N\sum_{i=1}^N\|a_{i+1}-a_i\|<\infty$

Then ${A:=\{a_n:n\in{\mathbb N}\}}$ has arbitrarily many collinear points.

To see why one can not ask for infinitely many collinear points, consider a sequence ${(a_n)}$ which roughly follows the path of a parabola.

In this scenario, the analog of van der Waerden’s theorem was discovered by Ramsey and Gerver:

Theorem 5 Let ${(a_n)_{n\in{\mathbb N}}}$ be a sequence in ${{\mathbb N}^2}$ and assume that there exists ${d\in{\mathbb N}}$ such that ${\|a_n-a_{n-1}\|\leq d}$ for all ${n\in{\mathbb N}}$ . Then ${A:=\{a_n:n\in{\mathbb N}\}}$ has arbitrarily many collinear points.

As a corollary of Theorem 4 we get:

Corollary 6 Let ${(a_n)_{n\in{\mathbb N}}}$ be a sequence of positive integers such that the set ${A=\{a_n:n\in{\mathbb N}\}}$ has positive density. Then for every ${k\in{\mathbb N}}$ there are ${k}$ collinear points of the ${(n,a_n)}$ .

Proof: Let ${b_n=(n,a_n)}$ . Then

$\displaystyle \liminf_{N\rightarrow\infty}\frac1N\sum_{i=1}^N\|b_{i+1}-b_i\|\leq \liminf_{N\rightarrow\infty}\frac2N\sum_{i=1}^Na_{i+1}-a_i=\liminf_{N\rightarrow\infty}\frac{2a_N}N=\frac2{\bar d(A)}<\infty$

The result now follows directly from Theorem 4 $\Box$

Another related result of Pomerance says that the conclusion of this corollary remains true when one replaces ${A}$ with the set of prime numbers (the analogous extension of Szemerédi’s theorem is the famous Green-Tao theorem). In the rest of this post I will outline Pomerance’s proof of theorem 4

— 2. Proof of Pomerance’s theorem —

To prove theorem 4 it is more convenient to work with finite sequences. We will use ${m\in{\mathbb N}}$ to denote the length of the sequence and hence we work with sequences of the form ${U=(u_0,u_1,\dots,u_m)}$ . We denote

$\displaystyle d(U)=\frac1m\sum_{i=1}^m\|u_i-u_{i-1}\|$

to be the average step of this finite sequence. We will fix ${k\in{\mathbb N}}$ and we prove the result for each ${k}$ separately. Thus, from now on we will omit any reference to ${k}$ in the notation. We define ${C(m)}$ to be the set of sequences ${U}$ of length ${U=(u_0,u_1,\dots,u_m)}$ without ${k}$ collinear points. By ${d(m)=\min\{d(U):U\in C(m)\}}$ we denote the minimum average step a sequence of length ${m}$ can have an still avoid ${k}$ collinear points. Also let ${d=\liminf_md(m)}$ be the minimum average step an arbitrarily long sequence can have and still avoid ${k}$ collinear points.

The theorem is equivalent to say that ${d=\infty}$ . Assume, for the sake of contradiction that it is finite. Thus for each ${m\in{\mathbb N}}$ and ${\epsilon>0}$ let

$\displaystyle D(m,\epsilon)=\{U\in C(m):|d(U)-d|<\epsilon\}$

denote the sequences of length ${m}$ without ${k}$ collinear points which have average step close to the minimum possible ${d}$ . We will consider sequences as stretched as possible, and among those we will consider the sequences as steep as possible. Then for such sequences it turns out that most points belong to a thin rectangle around the line connecting ${u_0}$ and ${u_m}$ , which allow us to deduce the result from a pigeonhole principle argument.

Let ${l(U)=(u_m-u_0)/m}$ be the average length of ${U}$ (counting cancelations), let ${l(m,\epsilon)=\max\{l(U):U\in D(m,\epsilon)\}\cup\{0\}}$ be the maximum average length of a sequence in ${D(m,\epsilon)}$ (or ${0}$ if ${D(m,\epsilon)}$ is empty), let ${l(\epsilon)=\limsup_ml(m,\epsilon)}$ the maximum average length of arbitrarily long sequences in ${D(m,\epsilon)}$ and let ${l=\lim_{\epsilon\rightarrow0^+}l(\epsilon)}$ be the maximal average length of arbitrarily long sequences without ${k}$ collinear points which have average step arbitrarily close to the minimum possible ${d}$ .

Let ${L(m,\epsilon)=\{U\in D(m,\epsilon):|l(U)-l|<\epsilon\}}$ be the set of sequences of length ${m}$ with average step very close to the minimum possible ${d}$ and average length very close to the maximum possible ${l}$ . Let ${\lambda(U)}$ denote the line segment connecting ${u_0}$ and ${u_m}$ and let

$\displaystyle x(U)=\frac1m\max\left\{d\big(\lambda(U),u_j\big):\frac m4\leq j\leq\frac{3m}4\right\}$

where ${d(\cdot,\cdot)}$ is the usual metric in ${{\mathbb R}^2}$ , denote the maximum distance between a point from the middle half of the sequence ${U}$ and the segment ${\lambda(U)}$ , normalized by the length of ${m}$ .

Lemma 7 For every ${\epsilon>0}$ there exists ${\delta>0}$ and ${M\in{\mathbb N}}$ such that for every ${m\geq M}$ and ${U\in L(m,\delta)}$ we have ${x(U)<\epsilon}$ .

Now let ${X(m,\epsilon)=\{U\in L(m,\epsilon):x(U)<\epsilon\}}$ , let ${s(U)}$ denote the slope of ${\lambda(U)}$ (and make ${s(U)=\pm\infty}$ if ${\lambda(U)}$ is vertical or degenerates to a point). Let ${s(m,\epsilon)=\max\{s(U):U\in X(m,\epsilon)\}\cup\{0\}}$ be the maximum slope of a sequence in ${X(m,\epsilon)}$ (or ${0}$ if ${X(m,\epsilon)}$ is empty), let ${s(\epsilon)=\limsup_ms(m,\epsilon)}$ the maximum slope of arbitrarily long sequences in ${X(m,\epsilon)}$ and let ${s=\lim_{\epsilon\rightarrow0^+}s(\epsilon)}$ .

Lemma 8 For every ${\epsilon>0}$ there exists ${M\in{\mathbb N}}$ such that if ${m>M}$ then there exists some ${U\in X(m,\epsilon)}$ such that ${|s(U)-s|<\epsilon}$ .

We will now give a proof of Theorem 4 using this lemma.

Proof: Let ${(a_i)_{i\in{\mathbb N}},(b_i)_{i\in{\mathbb N}}}$ be sequences of positive integers, with ${b_i\rightarrow\infty}$ and such that

$\displaystyle \left|\frac{a_i}{b_i}-s\right|<\frac1{b_i^2}$

Such sequences exist by Dirichlet approximation theorem. Apply Lemma 8 with ${\epsilon=1/b_i^2}$ and let ${m_i\in{\mathbb N}}$ (with ${m_i>m_{i-1}}$ ) and ${U_i\in X(m_i,1/b_i^2)}$ be given by the lemma, so that ${|s(U_i)-s|<1/b_i^2}$ . Now let ${E(i)}$ be the set of lines with slope ${a_i/b_i}$ which contain lattice points and pass within ${m_i/b_i^2}$ of the segment ${\lambda(U_i)}$ . Since ${x(U^i)<1/b_i^2}$ we deduce that the union of the lines in ${E(i)}$ contains ${m_i/2}$ points of ${U^i}$ .

To finish the proof we just need to count how many lines belong to ${E(i)}$ . Assume without loss of generality that the first point of ${U_i}$ , ${u_0=0}$ . Observe that the slopes of the lines in ${E(i)}$ and that of ${\lambda(U_i)}$ differ by

$\displaystyle |a_i/b_i-s(U_i)|\leq|a_i/b_i-s|+|s-s(U_i)|<2/b_i^2 \ \ \ \ \ (1)$

Thus if ${\ell\in E(i)}$ then the (absolute value of) the ${x}$ coordinate of the intersection of ${\ell}$ with the ${x}$ -axis (in other words, the ${x}$ -intersect of ${\ell}$ ) is no bigger than

$\displaystyle \frac{l(U_i)m_i}{\sqrt{1+s(U_i)^2}}\left|1-s(U_i)\frac{b_i}{a_i}\right|+\frac{m_i}{b_i^2}$

Using (1) (and observing that ${s>1}$ and hence ${a_i>b_i}$ ) we can now bound that distance by

$\displaystyle \frac{m_i}{b_i^2}\left(\frac{l(U_i)}{\sqrt{1+s(U_i)^2}}+1\right)\leq 4l\frac{m_i}{b_i^2}$

Since two lines with the same slope and the same ${x}$ -intersect are the same, we conclude that

$\displaystyle |E(i)|\leq 4la_i\frac{m_i}{b_i^2}$

It follows from the pigeonhole principle that at least one of the lines in ${E(i)}$ contains at least

$\displaystyle \frac{m_i/2}{4la_im_i/b_i^2}=b_i\frac{b_i}{8la_i}$

and since ${b_i\rightarrow\infty}$ we will eventually have more than ${k}$ collinear points from ${U_i}$ $\Box$

1 Response to Pomerance Theorem on colinear points in certain paths in a two dimensional lattice

Pingback: Large subsets of discrete hypersurfaces in Z^d contain arbitrarily many collinear points | I Can't Believe It's Not Random!