\documentclass[12pt]{article}
\usepackage{amssymb}
\newcommand{\Z}{{\mathbb Z}}
\title{Some questions about three-term progressions on monotone paths}
\begin{document}
\maketitle
Starting at the origin, consider a walk on neighboring integer lattice points,
where at each step you can either go right one unit or up one unit.
We will refer to such a walk as a {\it monotone path}. An example of
such a walk is the set of points
$$
(0,0)\ \to\ (1,0)\ \to\ (1,1)\ \to\ (1,2)\ \to\ (1,3)\ \to\ (2,3)\ \to\ \cdots
$$
A first question, easily answered, is:
\bigskip
\noindent {\bf Question 1.} Must every such monotone path have a
three-term progression?
\bigskip
The answer is ``yes'', because by just considering the first three or
four points in the walk, you will find that there must always be a
three-term progression.
Let us now consider the somewhat harder question:
\bigskip
\noindent {\bf Question 2.} For every $d > 0$, must every such monotone
path have a three-term progression of points, say
$$
x,\ x+v,\ x+2v,\ v \in \Z^2,
$$
such that
$$
||v||_2\ \geq\ d\ ?
$$
\bigskip
I believe the answer to this question is also ``yes'', but have not
attempted to check the details. Before I explain why, let me begin
with a simple observation: If I give you a non-crossing closed
curve in the plane whose interior is not convex, then it is
not too difficult to show that there must be three points on
the curve that are in arithmetic progression. Of course,
if the curve is close to being convex, in that you can make some
small perturbations to it to make it convex, then you cannot guarantee
that the three points of your arithmetic progression
are far apart. However, if the curve is somewhat far from being
convex, then it should always be possible to find three points in
progression, such that the common difference between points is ``large''.
Take the monotone path, and connect pairs of consecutive walk
points by line segments. This is not a closed curve, but one can pretend
it is a fragement of one. Now, if this fragment is roughly convex
(convex here means that every non-horizontal and non-vertical
line hits it in at most two points), then
there should be long stretches of consecutive walk points of the form
\footnote{What I am thinking here is: Any monotone path approximation
to a convex curve must be ``flat'' -- the are long stretches where
you just go up, or long stretches where you just go to the right.}
\begin{equation} \label{type1}
(x,y)\ \to\ (x+1,y)\ \to\ (x+2, y)\ \to\ \cdots\ \to\ (x+k, y),
\end{equation}
or
\begin{equation} \label{type2}
(x,y)\ \to\ (x,y+1)\ \to\ (x,y+2)\ \to\ \cdots\ \to\ (x,y+k).
\end{equation}
In either case, the monotone path has a three-term progression with
consecutive terms a distance at least about $k/2$ apart, and this
would then answer the question in the affirmative if $k/2 > d$.
On the other hand, if the monotone path (with segments added)
is far from being convex, then there will be three points on the curve
that are far apart, and in arithmetic progression. These three points
are not necessarily walk points, but they are within 1 (in either the
x or y direction) of a walk point. Take the nearest walk points to
the three points in progression. These walk points are themselves
in progression, or are 1 off from being in progression. Ok, so you
can get three walk points that are nearly in progression, and probably
you can get three that really are in progression.
\bigskip
Let's assume that the answer to Question 2 is indeed ``yes''. It has
the following amusing Ramsey-Theoretical interpretation:
\bigskip
\noindent {\bf Claim.} For every $d \geq 1$, if one $2$-colors
the natural numbers, there will exist three numbers $x, x + t, x + 2t$,
$t > d$, such that the number of integers between $x$ and $x+t$ of the
first color, is exactly the same as the number between $x+t$ and
$x+2t$ of the first color (the same holds for the second color).
\bigskip
To prove this claim, you use the coloring of the natruals to form a
monotone path as follows: As you run through the natruals, if you
encounter a number of the first color, move up by 1, and if you
encounter a number of the second color, move to the right by 1.
A three-term progression in the path corresponds to a three-term
progression down on the natruals with the property sought by the
claim.
\bigskip
Now we come to what I feel is a quite difficult question, and I am
not even sure what the answer should be, as I have no good heuristics:
\bigskip
\noindent {\bf Question 3.} Is it the case that for all densities
$d \in (0,1]$, there exists $N > 0$, such that for any density
$d$ subset of a monotone path of length $N$, there are always three
points in this subset that are in arithmetic progression?
\bigskip
In the case where the path is near to being ``convex'', the answer is
almost certainly ``yes''. The reason is that, not only will we have
long stretches of type (\ref{type1}) or (\ref{type2}) in this case,
but in fact most of the points should be on such stretches if the
cuve is nearly convex (so, some such stretch contains a positive
fraction of the points of the subset, and then just apply Roth).
On the other hand, if the curve is far from being ``convex'', one
needs another trick.
\end{document}