A Lipschitz function on the natural numbers whose graph has no three-term progression
A function $f : \mathbb{N} \to \mathbb{Z}$ is Lipschitz if $|f(n+1) - f(n)|$ is bounded. Its graph is $\Gamma = \{(n, f(n)) : n \in \mathbb{N}\} \subset \mathbb{Z}^2$, and a three-term progression in $\Gamma$ is a set $\{x, x + d, x + 2d\} \subset \Gamma$ with $d \ne 0$. For four-term progressions the answer to the question below is yes: Cassaigne, Currie, Schaeffer and Shallit constructed an infinite word over the alphabet $\{0, 1, 3, 4\}$ with no three consecutive blocks of the same length and the same sum, and the partial sums of such a word give a Lipschitz function whose graph has no four-term progression. The finitary version, with domain $[N]$ for arbitrarily large $N$ and a Lipschitz constant independent of $N$, is also of interest.
Problem. Is there a Lipschitz function $f : \mathbb{N} \to \mathbb{Z}$ whose graph contains no three-term progression?
Source: Equivalent to the avoidability of additive squares over a finite alphabet of integers (G. Pirillo and S. Varricchio, 1994); Green heard it from J. Fox in 2005 and from N. Morrison around 2014; considered in print by T. Brown, V. Jungić and A. Poelstra (2014). Listed as Problem 15 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Keywords
- additive squares, arithmetic progressions, combinatorics on words
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@article{brown2014double,
author = {Brown, Tom and Jungi{\'c}, Veselin and Poelstra, Andrew},
title = {On double 3-term arithmetic progressions},
journal = {Integers},
volume = {14},
pages = {Paper No. A43},
year = {2014},
eprint = {1304.1829},
archivePrefix = {arXiv}
}
@article{cassaigne2014avoiding,
author = {Cassaigne, Julien and Currie, James D. and Schaeffer, Luke and Shallit, Jeffrey},
title = {Avoiding three consecutive blocks of the same size and same sum},
journal = {Journal of the ACM},
volume = {61},
number = {2},
pages = {Art. 10},
year = {2014},
doi = {10.1145/2590775},
eprint = {1106.5204},
archivePrefix = {arXiv}
}
@article{justin1972,
author = {Justin, J.},
title = {G{\'e}n{\'e}ralisation du th{\'e}or{\`e}me de van der {W}aerden sur les semi-groupes r{\'e}p{\'e}titifs},
journal = {Journal of Combinatorial Theory, Series A},
volume = {12},
number = {3},
pages = {357--367},
year = {1972},
doi = {10.1016/0097-3165(72)90101-X}
}
@article{pirillo1994varricchio,
author = {Pirillo, G. and Varricchio, S.},
title = {On uniformly repetitive semigroups},
journal = {Semigroup Forum},
volume = {49},
number = {1},
pages = {125--129},
year = {1994},
doi = {10.1007/BF02573477}
}
@article{rao2018rosenfeld,
author = {Rao, Micha{\"e}l and Rosenfeld, Matthieu},
title = {Avoiding two consecutive blocks of same size and same sum over $\mathbb{Z}^2$},
journal = {SIAM Journal on Discrete Mathematics},
volume = {32},
number = {4},
pages = {2381--2397},
year = {2018},
doi = {10.1137/17M1149377}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 15; version of January 2026, most recent update December 2025},
year = {2026}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00934, "A Lipschitz function on the natural numbers whose graph has no three-term progression", clopen.solutions.