← All problems

Erdős Problem #195 — Monotone arithmetic progressions in permutations of the integers

1 year old · traced to

For a bijection f:Z→Zf:\mathbb{Z}\to\mathbb{Z}, regard the values f(n)f(n) as ordered by increasing index nn. A monotone kk-term arithmetic progression in this order means that there are indices n1<⋯<nkn_1<\cdots<n_k and integers x,dx,d, with d≠0d\ne 0, such that

f(nj)=x+(j−1)d(1≤j≤k).f(n_j)=x+(j-1)d\qquad(1\le j\le k).

Thus d>0d>0 gives increasing values and d<0d<0 decreasing values along the selected indices. The question is to determine the largest k∈Nk\in\mathbb{N} such that every bijection f:Z→Zf:\mathbb{Z}\to\mathbb{Z} has such indices and such x,dx,d. This is the doubly infinite ordering convention, not an enumeration indexed only by the positive integers. Erdős Problems #195 Adenwalla, Avoiding Monotone Arithmetic Progressions in Permutations of Integers (2024 preprint)

Background

This is an ordering problem: the permutation uses every integer, and the question is whether some arithmetic progression appears as a subsequence in that order. The one-sided and doubly infinite conventions matter. For example, results about enumerations a1,a2,…a_1,a_2,\ldots of the positive integers do not by themselves describe orders indexed by all of Z\mathbb{Z}. The problem is listed with the original references [ErGr79] and [ErGr80]; later work also studies permutations of the positive integers and restricted sets of common differences. Erdős Problems #195 Adenwalla, Avoiding Monotone Arithmetic Progressions in Permutations of Integers (2024 preprint)

References

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.