Problem 195

../

claims/: The 2 claim pages of Problem 195, one per claimant's result; the problem's standing derives from them.

---

Statement. What is the largest $k$ such that in any permutation of $\mathbb{Z}$ there must exist a monotone $k$-term arithmetic progression $x_1<\cdots<x_k$?

Formulation. A permutation of $\mathbb{Z}$ is read as a one-sided arrangement $a_1,a_2,\ldots$ of the integers, a bijection $\mathbb{N}\to\mathbb{Z}$, and a monotone $k$-term progression as a subsequence $a_{i_1},\ldots,a_{i_k}$, $i_1<\cdots<i_k$, that is an increasing or decreasing arithmetic progression. Erdős and Graham (1979, pp. 337-338) discuss permutations of $\mathbb{Z}$ in this singly-infinite case, Geneson and Adenwalla's Theorem 1 use it, and the formal-conjectures statement has used it since its correction of 2026-09-12, which replaced bijections $\mathbb{Z}\to\mathbb{Z}$. Doubly infinite arrangements have the same known bounds: Adenwalla's Theorem 2 gives one with no monotone five-term progression, and every one contains a monotone three-term progression (Davis, Entringer, Graham and Simmons, Fact 5, as Adenwalla's introduction notes).

Status. Open, the site's label (OPEN). The largest $k$ is $3$ or $4$. Every permutation of $\mathbb{Z}$ contains a monotone three-term progression: its positive terms, in order, form a permutation of the positive integers, and every such permutation contains an increasing three-term progression (Davis, Entringer, Graham and Simmons, Acta Arith. 34 (1977/78), Fact 3; source card), as Adenwalla's introduction notes. Adenwalla's permutation of $\mathbb{Z}$ with no monotone five-term progression gives $k\le4$ (claim page, accepted on its refereed publication), improving Geneson's $k\le5$ (claim page, accepted on its refereed publication). Neither result decides whether a monotone four-term progression is forced.

Source. erdosproblems.com/195, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #195, https://www.erdosproblems.com/195.

References.

• [Ad22] Adenwalla, S., Avoiding Monotone Arithmetic Progressions in Permutations of Integers. arXiv:2211.04451 (2022); Discrete Math. 347 (2024), no. 11, Paper No. 114183.
• [Ge19] Geneson, Jesse, Forbidden arithmetic progressions in permutations of subsets of the integers. Discrete Math. (2019), 1489-1491.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• adenwalla_2022_avoiding_monotone_arithmetic_progressions_permutations_integers
• davis_nd_permutations_containing_no_long_arithmetic_progressions
• erdos_1979_old_new_problems_results_combinatorial_number
• geneson_2019_forbidden_arithmetic_progressions_permutations_subsets_integers
• geneson_2019_forbidden_arithmetic_progressions_permutations_subsets_integers / proposition_1