Lipschitz AP-Free Graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A function $f:\mathbb N\to\mathbb Z$ is Lipschitz if there is a constant $K\ge0$ such that $|f(m)-f(n)|\le K|m-n|$ for all $m,n\in\mathbb N$. Its graph is $\Gamma_f=\{(n,f(n)):n\in\mathbb N\}\subset\mathbb Z^2$. A nontrivial three-term arithmetic progression in $\Gamma_f$ consists of the three distinct points with first coordinates $n,n+d,n+2d$ for some $n,d\in\mathbb N$, and therefore requires $f(n)+f(n+2d)=2f(n+d)$.

Statement recorded in the supplied source.

Does there exist a Lipschitz function $f:\mathbb N\to\mathbb Z$ whose graph contains no nontrivial three-term arithmetic progression, that is, such that \[ f(n)+f(n+2d)\ne2f(n+d)\qquad\text{for every }n,d\in\mathbb N? \] Equivalently, is there a strictly increasing sequence $(a_n)_{n\ge1}$ of positive integers with uniformly bounded successive gaps for which there are no $i<j<k$ satisfying both $i+k=2j$ and $a_i+a_k=2a_j$? [S1][S2] The natural-number domain agrees with the bounded-gap-sequence formulation. To pass from $f$ to that formulation, choose an integer $L>K$ and a constant integer $C$ making $a_1=f(1)+L+C>0$, and put $a_n=f(n)+Ln+C$. The gaps are positive and bounded, and the linear added term does not change the three-term-progression equation. Conversely, a bounded-gap increasing sequence defines a Lipschitz function $f(n)=a_n$. [S2]

Short English statement

Can an integer-valued function with a fixed bound on its slope have a graph containing no three equally spaced collinear graph points? Equivalently, can an increasing integer sequence with bounded gaps avoid every progression in which both the indices and the values form three-term arithmetic progressions?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 104 (GREEN-015). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Tom Brown, Veselin Jungić and Andrew Poelstra, On Double 3-Term Arithmetic Progressions, arXiv:1304.1829v3, 16 November 2013, section 1, Conjecture 1 and Problem 1, pp. 1--3, giving the equivalent bounded-gap and additive-square formulations. The existence question here is the negation of the universal question in Problem 1. https://arxiv.org/pdf/1304.1829v3.
• S3 Ben Green, 100 Open Problems, author manuscript with December 2025 updates, Problem 15, p. 10. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.