## Large subsets of discrete hypersurfaces in Z^d contain arbitrarily many collinear points

— 1. Introduction —

Recently, Florian Richter and I uploaded to the arXiv our paper titled Large subsets of discrete hypersurfaces in ${{\mathbb Z}^d}$ contain arbitrarily many collinear points’.

This was the outcome of a fun project which started when we learned about Pomerance’s theorem:

Theorem 1 (Pomerance’s theorem) For every ${B,k\in{\mathbb N}}$ there exists ${n\in{\mathbb N}}$ such that for any ${u_0,\dots,u_n\in{\mathbb Z}^2}$ with average gap bounded by ${B}$, i.e.

$\displaystyle \frac1n\sum_{i=1}^n\|u_i-u_{i-1}\|\leq B,$

there exist ${k}$ points among ${u_1,\dots,u_n}$ which are collinear.

I have presented the proof of Pomerance’s theorem in this post. A weakening of Pomerance’s theorem was proved earlier by L. T. Ramsey (it is Lemma 1 in that paper) as a combinatorial intermediate step in a problem in Fourier analysis.

Lemma 2 (Ramsey’s lemma) For every ${B,k\in{\mathbb N}}$ there exists ${n\in{\mathbb N}}$ such that for any ${u_0,\dots,u_n\in{\mathbb Z}^2}$ with gaps bounded by ${B}$, i.e.

$\displaystyle \forall i\in\{1,\dots,n\}\qquad\qquad\|u_i-u_{i-1}\|\leq B$

there exist ${k}$ points among ${u_1,\dots,u_n}$ which are collinear.

Even when ${B=1}$ Lemma 2 is nontrivial (and in fact it is easy to derive Lemma 2 from the case when ${B=1}$).

The question we asked (and eventually answered) was whether these results could be extended to higher dimensions. The first problem here is how to even formulate such a generalization!

— 2. Statement of our main result —

One can think of Theorem 1 as a 2-dimensional analogue of Szemerédi’s theorem. Indeed one can formulate Szemerédi’s theorem (which states that a subset of ${{\mathbb Z}}$ with positive upper density contains arbitrarily long arithmetic progressions) as:

Theorem 3 (Szemerédi’s theorem, reformulated) For every ${B,k\in{\mathbb N}}$ there exists ${n\in{\mathbb N}}$ such that for any ${u_0,\dots,u_n\in{\mathbb Z}}$ with average gap bounded by ${B}$, there exist ${k}$ points among them which form an arithmetic progression.

A (naive) way to attempt to generalize Szemerédi’s theorem to ${{\mathbb Z}^2}$ would be to ask whether a sequence in ${{\mathbb Z}^2}$ with bounded average gaps contains arbitrarily long arithmetic progressions. This turns out to be false, and in fact it is a theorem of Dekking that there exist infinite sequences ${u_1,u_2,\dots \in{\mathbb Z}^2}$ with each difference ${u_i-u_{i-1}}$ being a basis vector (i.e. either ${(0,1)}$ or ${(1,0)}$) and without ${4}$-term arithmetic progressions (an earlier similar construction by Justin contained no ${5}$-term arithmetic progressions). I do not know whether this result can be improved to ${3}$-term arithmetic progressions.

By relaxing the condition of being an arithmetic progression to being contained in a line, one obtains Pomerance’s Theorem. The next naive step would be to ask whether a sequence with bounded average gaps in ${{\mathbb Z}^3}$ contains arbitrarily many collinear points. Again this is not true; Gerver and Ramsey constructed an infinite sequence in ${{\mathbb Z}^3}$ with at most ${5^{11}}$ collinear points and where each step is a basis element. It is however true that any sequence with bounded average gaps in ${{\mathbb Z}^3}$ contains arbitrarily many points contained in the same plane. To deduce this, simply project the sequence onto ${{\mathbb Z}^2}$ and apply Pomerance’s theorem.

This discussion shows that no obvious non-trivial extension of Pomerance’s theorem holds for higher dimensions. To motivate our main theorem, let’s first reformulate Lemma 2:

Lemma 4 (Ramsey’s lemma, reformulated) Let ${u:{\mathbb Z}\rightarrow{\mathbb Z}^2}$ be a Lipschitz function. Then for every ${k\in{\mathbb N}}$ there exists ${X\subset{\mathbb Z}}$ with cardinality ${|X|=k}$ such that the set ${\{u(x):x\in X\}}$ is contained in a single line.

One can also reformulate Pomerance’s theorem along these lines:

Theorem 5 (Pomerance’s theorem, reformulated) Let ${u:{\mathbb Z}\rightarrow{\mathbb Z}^2}$ be a Lipschitz function and let ${A\subset{\mathbb Z}}$ have positive upper Banach density. Then for every ${k\in{\mathbb N}}$ there exists ${X\subset A}$ with cardinality ${|X|=k}$ such that the set ${\{u(x):x\in X\}}$ is contained in a single line.

It now becomes clear how one can extend these results to higher dimensions: instead of considering Lipschitz functions ${f:{\mathbb Z}\rightarrow{\mathbb Z}^d}$, we consider Lipschitz functions ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+1}}$. Our main result is then

Theorem 6 Let ${d,k\in{\mathbb N}}$ and let ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+1}}$ be a Lipschitz function. For any set ${A\subset{\mathbb Z}^d}$ with positive upper Banach density there exists ${X\subset A}$ with cardinality ${|X|=k}$ such that the set ${\{f(x):x\in X\}}$ is contained in a single line.

Even in the case ${d=2}$ and ${A={\mathbb Z}^2}$ this result is new. From this result one can also obtain equivalent finitistic formulations:

Theorem 7 Let ${d\in{\mathbb N}}$, let ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+1}}$ be a Lipschitz function and let ${(F_N)_{N\in{\mathbb N}}}$ be a Følner sequence on ${{\mathbb Z}^d}$. For every ${B,k\in{\mathbb N}}$ there exists ${N\in{\mathbb N}}$ such that for any ${A\subset F_N}$ with ${|A|>|F_N|/B}$ there exists ${X\subset A}$ with ${|X|=k}$ for which the set ${\{f(x):x\in X\}}$ is contained in a single line.

— 3. Geometric interpretation —

There is a nice geometric interpretation of Theorem 6 (spoiler alert: it’s the title of the paper).

An hypersurface is a submanifold of codimension ${1}$. It seems natural to call a discrete hypersurface to a subset of ${{\mathbb Z}^{d+1}}$ which “looks like” ${{\mathbb Z}^d}$ in some way.

A modern notion of a morphism between metric spaces is that of quasi-isometry. Every Lipschitz map is a quasi-isometry. Moreover, due to the discrete nature of ${{\mathbb Z}^d}$, whenever ${f}$ is a quasi-isometry between ${{\mathbb Z}^d}$ and a subset of ${{\mathbb Z}^{d+1}}$, it is a Lipschitz map. Therefore, any subset of ${{\mathbb Z}^{d+1}}$ which is quasi-isomorphic to ${{\mathbb Z}^d}$ contains the image of a Lipschitz map from ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+1}}$.

Definition 8 A discrete hypersurface in ${{\mathbb Z}^{d+1}}$ is the image of a an injective Lipschitz map ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+1}}$.

A discrete hypersurface in ${{\mathbb Z}^{d+1}}$ comes equipped with a Banach upper density, inherited from ${{\mathbb Z}^d}$ through the map ${f}$ which defines it. Since the same discrete hypersurface can be obtained from different Lipschitz functions ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+1}}$, this Banach upper density is not unique. It is still possible to define large subsets of discrete hypersurfaces, as those which are the image, under a Lipschitz map, of a set of positive upper Banach density in ${{\mathbb Z}^d}$. With these terminology, one can rephrase Theorem 6 as Large subsets of discrete hypersurfaces in ${{\mathbb Z}^d}$ contain arbitrarily many collinear points’.

One can extend the definition of discrete hypersurfaces to discrete submanifolds of higher co-dimension:

Definition 9 Let ${d,h\in{\mathbb N}}$. A discrete submanifold of codimension ${h}$ in ${{\mathbb Z}^{d+h}}$ is the image ${S}$ of a Lipschitz map ${f:{\mathbb Z}^d\rightarrow{\mathbb Z}^{d+h}}$. A set ${A\subset S}$ is large if there exists ${B\subset{\mathbb Z}^d}$ with positive upper Banach density such that ${A=f(B)}$.

It turns out that Theorem 6 can be easily extended do higher codimensions; indeed we obtain:

Theorem 10 Let ${d,h\in{\mathbb N}}$ and let ${S\subset{\mathbb Z}^{d+h}}$ be a discrete submanifold of codimension ${h}$. Then for every large subset ${A\subset S}$ and any ${k\in{\mathbb N}}$, there exists a hyperplane ${H}$ of dimension ${h}$ such that ${|H\cap A|\geq k}$.

Proof: Let ${\pi:{\mathbb Z}^{d+h}\rightarrow{\mathbb Z}^{d+1}}$ be the projection onto the first ${d+1}$ coordinates. It is easy to see that ${\pi(S)}$ is a hypersurface in ${{\mathbb Z}^{d+1}}$, that ${\pi(A)}$ is a large subset of ${\pi(S)}$. It follows from Theorem 6 that for any ${k\in{\mathbb N}}$ there exists a line ${\ell\subset{\mathbb Z}^{d+1}}$ such that ${|\pi(A)\cap\ell|\geq k}$. Since ${\pi}$ is surjective, this implies that ${|A\cap\pi^{-1}(\ell)|\geq k}$. But ${\pi^{-1}(\ell)}$ is a ${h}$-dimensional subspace of ${{\mathbb Z}^{d+h}}$ and this finishes the proof. $\Box$

— 4. Brief words about the proof —

The main idea behind the proof Theorem 6 is to convert the discrete setup of its statement to a continuous version. Then we used the classical Rademacher’s theorem, which in particular states that a Lipschitz function between ${{\mathbb R}^d}$ and ${{\mathbb R}^{d+1}}$ is (Lebesgue) almost everywhere differentiable! This means that, locally, the image of a Lipschitz function will be very concentrated around an affine subspace of dimension at most ${d}$ (inside ${{\mathbb R}^{d+1}}$).

Translating back to the discrete world, this gives us a very long, and relatively thin cylinder in ${{\mathbb Z}^{d+1}}$ which contains a substantial amount of points of the form ${f(a)}$ with ${a\in A}$ and whose axis has a slope which is almost rational. Finally, we use a counting argument, already used by Ramsey and Pomerance, to finish the proof: We cover the cylinder with not too many lines with rational slope almost parallel to the axis. If we count things carefully, it follows from the pigeonhole principle that one of the lines must have at least ${k}$ points.

The use of Rademacher’s theorem implies that we obtain no quantitative bounds (i.e., we have no control of ${N}$ in terms of ${B}$ and ${k}$ in Theorem 7). An effective version of Rademacher’s theorem would potentially allow for some quantitative bound on ${N}$.

This entry was posted in Analysis, Combinatorics, paper and tagged , , , , , . Bookmark the permalink.

### 2 Responses to Large subsets of discrete hypersurfaces in Z^d contain arbitrarily many collinear points

1. Rongqing Ye says:

Which distance shall be used in $\mathbb{Z}^2$? I am asking because I am confused about the remark after Ramsey’s Lemma.

• Joel Moreira says:

The norm doesn’t matter for the lemma itself, since they are all equivalent; but the remark didn’t make sense as it was. I changed the strict inequality to $\leq$, and you can think of the $\|\cdot\|_1$ norm (sum of the absolute value of the coordinates)