← All problems

Erdős Problem #196 — Monotone arithmetic progressions in permutations

46 years old · traced to

Let N\mathbb{N} denote the positive integers, and let x=(x1,x2,…)x=(x_1,x_2,\ldots) be a permutation of N\mathbb{N}, meaning a bijective sequence. Must there exist indices i1<i2<i3<i4i_1<i_2<i_3<i_4 and integers a>0a>0 and d≠0d\ne 0 such that

xir=a+(r−1)d,r=1,2,3,4?x_{i_r}=a+(r-1)d,\quad r=1,2,3,4?

Equivalently, must every permutation of the positive integers contain a four-term arithmetic progression as a subsequence whose terms are monotone—increasing if d>0d>0, decreasing if d<0d<0? Erdős Problem #196 Erdős and Graham (1979)

Background

Erdős and Graham raised the question in their discussion of arithmetic progressions in ordered sequences. The infinite-permutation setting differs from the finite one: their account notes that finite sets can be ordered to avoid monotone three-term progressions, whereas every permutation of the positive integers contains one. This contrast makes the four-term case a natural next question. Erdős and Graham (1979)

The elementary reason a three-term progression is unavoidable is that, after the first term x1x_1, take the earliest term xk>x1x_k>x_1. The positive integer 2xk−x12x_k-x_1 occurs somewhere in the permutation; since it exceeds xkx_k, its occurrence must be later than position kk. Thus x1,xk,2xk−x1x_1,x_k,2x_k-x_1 form an increasing three-term progression in their sequence order. On Permutations Avoiding Arithmetic Progressions (arXiv:1004.1740)

References

Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).

Source: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.