Erdős Problem #195

Erdős Problem 195: integer permutations and the three-versus-four gap

1. Statement and the indexing convention

A permutation of $\mathbb Z$ here is a one-sided enumeration $p_1,p_2,\ldots$ containing every integer exactly once, as in the cited primary paper. Determine the largest $k$ for which every such enumeration contains a monotone $k$-term arithmetic progression as a subsequence. We prove that the answer is either three or four: a triple is unavoidable, and we reconstruct Adenwalla's explicit enumeration avoiding five-term progressions. The four-term question remains unresolved.

A doubly infinite ordering indexed by $\mathbb Z$ is a separate convention. In particular, a subsequence of such an ordering need not be an enumeration indexed by $\mathbb N$. The earlier draft's reduction using those incompatible conventions is not retained.

2. An increasing triple is unavoidable

Let $x=p_1$, and let $y$ be the first later entry larger than $x$. Such an entry exists since the values are unbounded above. The integer $z=2y-x$ is larger than $y$ and must occur somewhere. It could not occur before $y$, because all those entries are at most $x$. Hence $x,y,z$ occur in that order and form an increasing arithmetic progression. This elementary argument also applies to a permutation of $\mathbb N$; it is the Davis--Entringer--Graham--Simmons observation.

3. The explicit avoiding enumeration

Let \[ p=(0,4,2,6,1,5,3,7),\qquad q=(7,3,5,1,6,2,4,0) \] be reverse orders of the residues modulo eight. Start with \[ X_1=(-8,-4,4,-6,2,-2,6,-7,1,-3,5,-5,3,7). \] For $i\ge1$, obtain $X_{i+1}$ by concatenating the eight lists $8X_i+r$, in residue order $p$ if $i+1$ is odd and $q$ if $i+1$ is even. Then $X_i$ enumerates exactly \[ [-8^i,-8^{i-1}-1]\ \cup\ [8^{i-1},8^i-1].\tag{1} \] This follows inductively by taking all residues after multiplying the endpoints by eight. The disjoint blocks in $1$, together with $0,-1$, cover the integers. Therefore \[ P=(0,X_1,-1,X_2,X_3,X_4,\ldots)\tag{2} \] is an enumeration of $\mathbb Z$.

We will show it has no five-term arithmetic progression in subsequence order, allowing either sign of the common difference.

4. A binary comparison that controls the residue orders

In the order $p$, a residue's rank is obtained by reading its three binary digits from lowest to highest. If $8\nmid d$ and $s=v_2(d)\in\{0,1,2\}$, comparison of $a$ and $a+d$ modulo eight is decided by bit $s$: the first comes earlier in $p$ exactly when this bit of $a$ is zero. Adding $d$ flips that bit, while adding $2d$ leaves it unchanged. Thus the two comparisons \[ a\ \text{versus}\ a+d, \qquad a+2d\ \text{versus}\ a+3d \tag{3} \] have the same direction in $p$, whereas consecutive comparisons in a three-term progression have opposite directions. Reversing the residue order reverses every comparison, so the same latter property holds in $q$.

It follows that every $X_i$ avoids three-term progressions. For $X_1$, its residue groups are in order $p$ and have at most two entries each, so a progression with $8\mid d$ cannot fit in a group, and the binary comparison excludes all other $d$. Inductively, a three-term progression in $X_{i+1}$ with $8\nmid d$ is again excluded by the residue comparisons. If $8\mid d$, all three terms are in one subblock $8X_i+r$ and would give such a progression in $X_i$ after subtracting $r$ and dividing by eight.

5. Adjacent blocks cannot support a two-plus-two progression

We claim that there is no four-term progression with its first two terms in $X_i$ and its last two in $X_{i+1}$, in subsequence order. If $8\nmid d$, the first comparison and the last comparison in $3$ have the same direction in $p$, but the two blocks use opposite residue orders. They therefore cannot both be forward comparisons in their respective blocks.

If $8\mid d$ and $i\ge2$, all four terms have a common residue $r$. The first two lie in $8X_{i-1}+r$ and the last two in $8X_i+r$. Subtracting $r$ and dividing by eight preserves their order and produces the same forbidden pattern one block earlier. This reduces the issue to $i=1$.

The only ordered pairs in $X_1$ whose nonzero difference is divisible by eight are \[ (-4,4),\ (-6,2),\ (-2,6),\ (-7,1),\ (-3,5),\ (-5,3). \] Each is $(x,x+8)$ with $-7\le x\le-2$. Its forced continuation is $(x+16,x+24)$, lying in one residue subblock of $X_2$ and corresponding there to the entries $1,2$ of $X_1$. But $2$ precedes $1$ in $X_1$, so this continuation is reversed. This checks the base case and proves the claim for every adjacent pair of blocks.

6. Exceptional entries and the global five-term argument

There is no three-term progression ending at the final $-1$ of the finite prefix $(0,X_1,-1)$. In a proposed ordered triple $(a,b,-1)$, $a$ must be odd. All even entries of $X_1$ precede its odd entries, so $b$ would also have to be odd. Then $a\equiv3\pmod4$, leaving only \[ (-5,-3,-1),\quad(3,1,-1),\quad(7,3,-1). \] In each case the displayed middle entry actually precedes the first one in $X_1$. Thus $-1$ cannot be the third, fourth or fifth term of any five-term progression in $2$, since its two immediate preceding progression terms would give such a triple in the prefix. The entry zero cannot be any term after the first, because it is the first entry of the enumeration.

If $-1$ is the second term, its predecessor lies in $[-8,7]$, so the common difference has absolute value at most eight. The final three terms have absolute value at most $25$ and appear after $-1$. They must all lie in $X_2$, contradicting its three-term avoidance.

It remains to consider a putative five-term progression $a_1,\ldots,a_5$ whose second and third terms lie in blocks. If $a_2\in X_i$ and $a_3$ is in a later block, then $a_1,a_2\in[-8^i,8^i-1]$, so $|d|<2\cdot8^i$. Consequently $|a_3|,|a_4|,|a_5|<7\cdot8^i$. All three occur after $X_i$, and the next block after $X_{i+1}$ has every absolute value at least $8^{i+1}$. Thus all three lie in $X_{i+1}$, a contradiction.

Finally, if $a_2,a_3\in X_i$, then $a_4$ cannot lie in $X_i$. The same bounds give $|a_4|<3\cdot8^i$ and $|a_5|<5\cdot8^i$, forcing both into $X_{i+1}$. This contradicts the adjacent-block claim. All cases are excluded, so $2$ avoids five-term progressions.

7. Assessment and attribution

The unavoidable triple and the five-term avoiding construction are fully proved, including residue comparisons and the exceptional entries. They leave exactly the four-term case. The construction is Adenwalla's, with its finite residue checks expressed through binary ranks; no novelty is claimed.

Sources: https://www.erdosproblems.com/195; S. Adenwalla, Avoiding Monotone Arithmetic Progressions in Permutations of Integers, Theorem 1, https://arxiv.org/abs/2211.04451; J. A. Davis, R. C. Entringer, R. L. Graham and G. J. Simmons, On permutations containing no long arithmetic progressions, Fact 3, https://doi.org/10.4064/aa-34-1-81-90.

Completion rate estimate: 45%.

Erdős problem 195

1) FORMAL RESTATEMENT

A permutation of $\mathbb{Z}$ is a bijection $\pi:\mathbb{Z}\to\mathbb{Z}$, viewed as the bi-infinite sequence $(\pi(n))_{n\in\mathbb{Z}}$. A monotone $k$-term arithmetic progression in $\pi$ means there exist indices $i_1<i_2<\dots<i_k$ such that the values $\pi(i_1),\dots,\pi(i_k)$ form a $k$-term arithmetic progression and are monotone (either increasing or decreasing) in that index order. Let $K^*$ be the largest $k$ such that every permutation of $\mathbb{Z}$ must contain such a monotone $k$-AP. Determine $K^*$.

2) QUICK LITERATURE/CONTEXT CHECK

Problem text states: Geneson proved $K^*\le 5$ and Adenwalla improved to $K^*\le 4$. Thus $K^*\in\{3,4\}$ is plausible.

3) ATTACK PLAN

Provide reductions and invariances: $1$ reduce from permutations of $\mathbb{Z}$ to permutations of $\mathbb{N}$ via subsequences, $2$ show symmetry operations preserve existence/nonexistence of monotone APs. Then record computational sanity checks in finite truncations.

4) WORK

Lemma 4.1 (Positive subsequence reduction).

Let $\pi$ be a permutation of $\mathbb{Z}$ and let $\pi^+$ be the subsequence of $\pi$ consisting of the positive integers (in the order they occur). Then $\pi^+$ is a permutation of $\mathbb{N}$ (indexed by $\mathbb{N}$). Any monotone $k$-AP appearing in $\pi^+$ also appears in $\pi$. Proof. Each positive integer appears exactly once in $\pi$, so the subsequence lists each element of $\mathbb{N}$ exactly once, hence is a permutation of $\mathbb{N}$. If $\pi^+$ contains indices $j_1<\dots<j_k$ giving a monotone $k$-AP in values, these correspond to indices $i_1<\dots<i_k$ in the original sequence $\pi$ with the same values in the same order, hence the same monotone $k$-AP occurs in $\pi$. $\square$

Lemma 4.2 (Symmetry invariance).

If $\pi$ contains a monotone $k$-AP, then so do: (a) the reversed permutation $\pi'(n)=\pi(-n)$, and (b) the negated permutation $\pi''(n)=-\pi(n)$. Conversely, if $\pi$ avoids monotone $k$-APs then so do $\pi'$ and $\pi''$. Proof. Reversal replaces the index order by its reverse but preserves the relative order type (increasing becomes decreasing). Negation reverses the numerical order of values (increasing AP becomes decreasing AP). In both cases, the arithmetic-progression property of the values is preserved (negation and index reversal are affine). Therefore existence/nonexistence of monotone $k$-APs is invariant. $\square$

FAST REALITY CHECK (finite evidence)

Finite permutations of $\{1,\dots,n\}$ can avoid monotone 4-APs for moderately large $n$ (heuristic search finds examples for $n=20,25,30$), so forcing a monotone 4-AP in an infinite permutation is not a simple finite obstruction.

6) FINAL

UNRESOLVED

(i) Strongest proved partial results: reduction from $\mathbb{Z}$ to $\mathbb{N}$ subsequences (Lemma 4.1) and symmetry invariances (Lemma 4.2).

(ii) First gap: decide whether every permutation of $\mathbb{Z}$ must contain a monotone 4-AP (i.e. whether $K^*=4$ or $3$).

(iii) Top 3 next moves: 1. Try to adapt the known unavoidable 3-AP arguments (DEGS77 for $\mathbb{N}$) to 4-APs. 2. Attempt to explicitly construct a permutation of $\mathbb{Z}$ avoiding monotone 4-AP (would show $K^*=3$). 3. Search for extension obstructions: characterize finite avoiders that cannot be extended.

(iv) Minimal counterexample structure (if $K^*=3$): an explicit infinite permutation with the property that for every 4-term AP $a,a+d,a+2d,a+3d$, the order of their positions is not monotone (neither increasing nor decreasing).