— 1. Introduction —
Recently, Florian Richter and I uploaded to the arXiv our paper titled `Large subsets of discrete hypersurfaces in contain arbitrarily many collinear points’.
This was the outcome of a fun project which started when we learned about Pomerance’s theorem:
there exist points among 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.
there exist points among which are collinear.
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 with positive upper density contains arbitrarily long arithmetic progressions) as:
Theorem 3 (Szemerédi’s theorem, reformulated) For every there exists such that for any with average gap bounded by , there exist points among them which form an arithmetic progression.
A (naive) way to attempt to generalize Szemerédi’s theorem to would be to ask whether a sequence in 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 with each difference being a basis vector (i.e. either or ) and without -term arithmetic progressions (an earlier similar construction by Justin contained no -term arithmetic progressions). I do not know whether this result can be improved to -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 contains arbitrarily many collinear points. Again this is not true; Gerver and Ramsey constructed an infinite sequence in with at most collinear points and where each step is a basis element. It is however true that any sequence with bounded average gaps in contains arbitrarily many points contained in the same plane. To deduce this, simply project the sequence onto 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 be a Lipschitz function. Then for every there exists with cardinality such that the set is contained in a single line.
One can also reformulate Pomerance’s theorem along these lines:
Theorem 5 (Pomerance’s theorem, reformulated) Let be a Lipschitz function and let have positive upper Banach density. Then for every there exists with cardinality such that the set is contained in a single line.
It now becomes clear how one can extend these results to higher dimensions: instead of considering Lipschitz functions , we consider Lipschitz functions . Our main result is then
Even in the case and this result is new. From this result one can also obtain equivalent finitistic formulations:
Theorem 7 Let , let be a Lipschitz function and let be a Følner sequence on . For every there exists such that for any with there exists with for which the set 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 . It seems natural to call a discrete hypersurface to a subset of which “looks like” 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 , whenever is a quasi-isometry between and a subset of , it is a Lipschitz map. Therefore, any subset of which is quasi-isomorphic to contains the image of a Lipschitz map from .
Definition 8 A discrete hypersurface in is the image of a an injective Lipschitz map .
A discrete hypersurface in comes equipped with a Banach upper density, inherited from through the map which defines it. Since the same discrete hypersurface can be obtained from different Lipschitz functions , 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 . With these terminology, one can rephrase Theorem 6 as `Large subsets of discrete hypersurfaces in contain arbitrarily many collinear points’.
One can extend the definition of discrete hypersurfaces to discrete submanifolds of higher co-dimension:
Definition 9 Let . A discrete submanifold of codimension in is the image of a Lipschitz map . A set is large if there exists with positive upper Banach density such that .
It turns out that Theorem 6 can be easily extended do higher codimensions; indeed we obtain:
Theorem 10 Let and let be a discrete submanifold of codimension . Then for every large subset and any , there exists a hyperplane of dimension such that .
Proof: Let be the projection onto the first coordinates. It is easy to see that is a hypersurface in , that is a large subset of . It follows from Theorem 6 that for any there exists a line such that . Since is surjective, this implies that . But is a -dimensional subspace of and this finishes the proof.
— 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 and 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 (inside ).
Translating back to the discrete world, this gives us a very long, and relatively thin cylinder in which contains a substantial amount of points of the form with 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 points.
The use of Rademacher’s theorem implies that we obtain no quantitative bounds (i.e., we have no control of in terms of and in Theorem 7). An effective version of Rademacher’s theorem would potentially allow for some quantitative bound on .