Arithmetic Progressions in slowly oscillating sequences

Far from a full answer, but I have some (hopefully) new information. Length $4$ equally spaced, AP subsequences can be found from all finite $(a_n)_{n=1}^N$ with $N>10$ and $\forall n(|a_{n+1}-a_n|=1)$. This can very easily be brute forced, as there exist only $2^N$ distinct length $N$ sequences which obey the absolute value condition. That comes out to only $2048$ distinct sequences which require checking.

Here is an example of a length $10$ sequence which does not contain any length $4$, equally spaced, AP subsequences. However, appending either $a_{10}+1$ or $a_{10}-1$ to it will negate this.

| /\
|/  \/\  /
|      \/
|

So I thought that there is probably some finite length $N$ after which every such sequence will contain length $8$, equally spaced, AP subsequences. Turns out that even for length $5$, $N$ would have to be greater than $32$. There are $2^{32}$ distinct sequences, and filtering out those sequences where length $5$ APs have already been found, over $3$ million sequences are left. This was when I got a memory error.

Perhaps some of you out there with better hardware and/or programming prowess (or just more time) could brute force the solution, if there is indeed such a finite $N$. Of course, a positive answer for $k$ will beg the same question for $k+1$ and eventually you will run out of processing power or memory, which is why this is a rather inelegant method of doing it.

So, I wrote a program too. For natural $n$ as $f(n)$ I denote the least number $m$ such that each appropriate sequence of length $m$ contains an equally spaced arithmetic progression of length $m$. So, regret calculated $f(4)=11$ and $f(5)>32$. My program confirmed these results. Moreover, It claims that f(5)>4200 (this sounds somewhat strange for me. Maybe, there is a bug in my program) as shows the following sequence of signs of $a_{i+1}-a_i$:

oooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxoooxooxxxoooxooxoxxxoxoooxxoxxxooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxxxoxxxoooxoxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoxxxoxoooxoooxoxxoxxoooxoooxoooxoxxoooxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoxxoxxoxxoooxoxoxxxoooxxxoxoxoooxoxoxxxoxxoooxoooxxoxoooxoooxoooxoxxoooxoooxoxxoxxoooxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxoxxxoooxoxoxxxoooxxoxxxoxxoooxxoooxooxxoxxoxoxxoooxoxxxoxxxoxxxoooxxoooxxoooxooxxxooxoooxoxoxxxooxooxxoooxxoooxxoxxxoxooxxxoxxoxxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoxxoxxoxxoooxoooxxxooxxoooxoxxxoxoooxxxoooxooxxxoxxxoxxxoooxooxoxxxoooxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoxxoxxoooxxoxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxxoooxoxoxxxooxxoooxooxxoxxoooxoxxxoxxxooxoxoooxoxxoooxoxxoxxxoooxxxoxxoooxooxoxxxoxxxoxxxooxoooxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxxoooxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxooxxxoxooxxxoxxxoxxxoooxoooxoooxxoxoxxoooxoxoxxxooxoxooxxxoxxoooxoooxoxxoooxoooxoxxoxxoooxoxxoxxxooxoxxxoxxxoxooxxxoooxoooxoxxoxxxoooxxxooxooxxxoxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoooxoxxoooxoxxxoxoooxooxxoxxooxoooxoxxoooxoxxxoxoooxoxxxoxxxooxooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoxxoooxooxxoxxoooxoxxxoxooxxxoxxxoxxxoooxoooxoxxoooxoooxoooxoxxoxxxoooxoxoxxxooxxxoooxxoxoooxoooxoooxoxxoxxoooxoxoxxxoxoooxoxxxoxxxoxxxooxoooxooxxoxxoooxooxxxooxoxxxoxxxoxxxoooxooxoxxxoxoxoooxooxxxoooxxoxoooxoooxoooxoxxoooxoxoxxxoxoooxooxoxxxoooxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxxoxxxooxxoooxoxoxxxooxxxooxooxoooxxoxoooxooxxxooxoxxxoxoxxoooxooxxxoxxxoxxxooxoxxxooxoooxooxxoxxoooxooxxoxxoooxooxxoxxxoxxoooxxxoxooxxxoxxxoxxxoooxooxxxoooxooxxoxxxooxoxxxoxxxoxxxoooxooxoxxxooxxxooxxxoxooxooxxoooxxooxxxoooxoooxxxoxxoooxoooxoooxoxxxooxooxxoxxoxoxxoooxoxoxxxooxxxooxoxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxxoooxoooxxxooxooxoxxxooxoxxxoxoooxoxooxxxoxxoxoooxoooxoxxoooxxooxxxoxxooxooxoxxxoxxxoxxxoooxoooxoxxxoooxxooxoooxxxoxxxoxooxxxooxoxxxoxxxooxoxoooxoxxxoxxxoxxxooxoxxxoooxooxxxooxxoooxooxxoooxxoxxooxxxooxooxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxxxoxoxoxxxooxxoooxooxxoooxxoxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxxoxxooxxxooxxoooxxxoxoooxoooxoooxoxxoooxxooxxxoooxxooxxxoooxoxxxoxxxoxxxooxoooxooxxoxxoooxooxxoxxoooxooxxoxxoxxxoooxxxoxxxoxxxoxoooxoxooxxxoooxooxxoooxxoooxxxoxxoooxoooxxoxxxoooxoooxoooxoxxoxxoxxoooxoxoxxxoxxoooxoxxxoxxxoxxxooxoooxooxxoxxoooxoxxxoxooxxxoooxoooxoooxoxxoooxoooxoxxoooxoxxoxxooxxxooxxoooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoxxoooxooxxoxxoooxoxoxxxooxoxxxoxxoooxoooxoooxoxxoooxoooxoxxxoooxoxoxxxooxxoooxooxxoxxoxxxoooxxxoxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoxxoxxoooxxoxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxoxxxoxoooxoxooxxxoooxooxxxooxxxoxxoooxxoxoxxxoxoooxoooxoooxoxxoooxoooxxoxxxooxoxxxoooxoooxoxxoxxxooxoxxxoxxxoxoooxoooxoooxoxxxooxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxooxoxxxoxxxoxxxooxooxxxoooxxxoxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxxoxxoxxxooxooxoxxxoxxxoxxxoooxoooxoooxoxxxoooxooxxoxxoxxoxoooxoxxoxxxooxoxxxoxxxoxooxxxoooxoooxoooxoxxoooxoooxoxxoooxxxooxxoxxoooxoooxoooxoxxoooxxoxxooxoooxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxxoxxxoxxoooxoooxxoxoooxoooxoxxoxxoooxooxoxxxoxxxoooxooxoxxxoxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoxxoxxoooxxoxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxxxoxxxoooxoxxxoxxxoxxxoooxoooxxoxoxxoooxoxoxxxoooxoxxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoxxoxxoooxoxxoxxoooxoooxoooxoxxoxxoxxoooxxoxxxoooxooxoxxxoxxxoxxxooxoooxooxxoxxoooxooxxoxxooxoooxoxxoxxxoxooxxxoxxxoxooxxxoxooxooxxoooxxooxxxoooxoooxxxoxxoooxoooxoooxoxxxooxooxxoxxoxxoxoooxoxxoooxxxoxxxoxxxoxooxoooxoxxoooxoxxoxxoooxxxoxxooxoooxxxoxxxoxxxooxoxxxoxxxoxxxoooxxooxooxxoxxoooxoooxoooxoxxoooxxoxxooxxxoooxoxoooxxoxxoxoooxoxooxxxoxxxoooxxxoxoxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxoooxooxxxoooxooxoxxxoxoooxxoxxxooxxxoooxoooxoooxoxxoooxxxoxxxoooxxoxxoooxooxoxxxoxxxooxoxoooxxoxxxoxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxxoxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoxxoxxxoxooxxxoooxoooxxoxxxoxooxoooxoxxxooxoooxoxxoooxxxoxxxoxxxoxoooxooxxoxxoooxooxxoooxxoxxxoooxoooxxoxxxooxoxxxoxxxoxooxxxoooxoooxoxxoxxxoooxooxxoxxxoxooxxxooxoooxxoooxxoooxooxxxooxxxoxxoooxxoooxxoxoooxoooxoooxoxxoooxoooxoooxxxooxxoooxoxoxxxoooxoxoooxxoxxoxxxoooxxxoxoxxxoooxoooxoooxoxxoooxooxooxxxoxxoooxxooxxxoxxoooxxoooxooxxxooxoxxxoxxxooxoxxxoxxoooxoxoooxxoxoxxoooxoooxoooxoxxxoooxoxoxxxoooxoxxxoxxxoxxxoooxoooxoooxoxxoxxoooxooxxoxxoooxoxxxoxxxoxxxoooxxoooxoxoxxxooxxxoooxoxoxxxoooxoooxoooxoxxoooxxoxxxoooxoxoxxxooxxxoooxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxooxoxxxoxxxoooxxoooxoxoxxxoxxoooxxoxxooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxxoooxxoxxxoxxoooxooxooxxxoooxoooxoooxoxxoooxoxxoxxooxxxooxxoooxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxoooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxxoxxxooxoxooxxxoxxxoxxxooxoxooxxxooxooxoooxxoxoooxooxxxooxxxooxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxxxooxxoooxooxxoooxxxooxoxxxoxxxooxoxxxoxxoooxooxooxxxoooxooxoxxxoooxxooxoo

The graph of the respective sequence $\{a_i\}$:

The calculating block of my Delphi program:

procedure TForm1.Button1Click(Sender: TObject); 
label
 0,1;
const
 prLen0=4; // Length of Progression -1
 seqLen0=7000; // Length of Sequence -1
var
 prLen,l:Byte;
 i,j,k,d,d0,imin,seqLen:Word;
 l1:Integer;
 b:array[0..seqLen0-1]of Byte; // b[i]=a[i+1]-a[i]
 SOut:String;
begin
Memo1.Lines.Add('Seq.Length='+IntToStr(seqLen0+1));
Memo1.Lines.Add('Prog.Length='+IntToStr(prLen0+1));
FillChar(b,SizeOf(b),0);
imin:=seqLen0-prLen0;
prLen:=prLen0-1;
seqLen:=seqLen0-1;
repeat
for i:=imin downto 0 do for j:=1 to (seqLen0-i) div prLen0 do begin
 d0:=b[i];for k:=i+1 to i+j-1 do inc(d0,b[k]);
 for l:=1 to prLen do begin
  d:=b[i+j*l];for k:=i+j*l+1 to i+j*(l+1)-1 do inc(d,b[k]);
  if d<>d0 then goto 1; // Search for next progression
 end;
 // Progression found, go to the next sequence
 for l1:=i-1 downto 0 do b[l1]:=0;
 l1:=i; while b[l1]=1 do begin b[l1]:=0;inc(l1) end;
 b[l1]:=1;
 goto 0;
1:
end;
// No progessions found
SOut:='';
for i:=seqLen downto 0 do if b[i]=1 then SOut:=SOut+'x' else SOut:=SOut+'o';
Memo1.Lines.Add(SOut);
Break;
0:
until b[seqLen]=1; // by the symmetry , without loss of genearily we can assume b[0]=0
Memo1.Lines.Add('Done');
end;

There exist a sequence that has no length $54$ equally spaced arithmetic subsequence. This is a modified counterexample from this link.

Let $$u(x)=\frac{3}{2\pi}\sum_{n=1}^\infty 18^n\sin(\frac{2\pi x}{3(36)^n})$$ and put $a_n$ to be an even number in the interval $[u(x)-1,u(x)+1)$ when $n$ is even and an odd number when $n$ is odd.

Then we have \begin{align}|a_k-a_{k+1}|\leq|u(k)-u(k+1)|+2&\leq\frac{3}{2\pi}\sum_{n=1}^\infty 18^n\left|\sin(\frac{2\pi k}{3(36)^n})-\sin(\frac{2\pi(k+1)}{3(36)^n})\right|+2\\&<\frac{3}{2\pi}\sum_{n=1}^\infty18^n\frac{2\pi}{3}\frac1{36^n}+2=3\end{align}

Since $a_k-a_{k+1}$ is odd, we see that $|a_k-a_{k+1}|=1$

Now let $k_1, k_2,\ldots,k_{54}$ be an arithmetic sequence with common difference $d>0$. Define $m$ to be $36^{m-1}\le d<36^{m}$ and $h\le18$ as the smallest integer that $36^m/2\le hd\le 36^m$. Then $\frac{2\pi k_{19}}{3(36)^m},\frac{2\pi k_{20}}{3(36)^m},\ldots,\frac{2\pi k_{36}}{3(36)^m}$ is an arithmetic sequence with common difference at least $\pi/54$ but less than $2\pi/3$. So one of $\frac{2\pi k_{19}}{3(36)^m},\frac{2\pi k_{20}}{3(36)^m},\ldots,\frac{2\pi k_{36}}{3(36)^m}$ must be in the interval $[\pi/6,5\pi/6]$ or $[7\pi/6,11\pi/6]$ in $\pmod{2\pi}$. Let $\frac{2\pi k_i}{3(36)^m}$ be one of it.

We now show that $a_{k_i-h},a_{k_i},a_{k_i+h}$ is not an arithmetic sequence.

Let $K=2\pi k_i/3$, $D=2\pi hd/3$. First we have $$\sin\frac{D}{2(36)^m},\left|\sin\frac{K}{36^m}\right|\geq\sin\frac\pi6$$

Now \begin{align} &|a_{k_i-h}-2a_{k_i}+a_{k_i+h}|\\&\ge |u(k_i-h)-2u(k_i)+u(k_i+h)|-4\\&\ge\frac{3(18)^m}{2\pi}\left|\sin\frac{K-D}{36^m}-2\sin \frac{K}{36^m}+\sin\frac{K+D}{36^m}\right|-\sum_{n=1}^{m-1}\frac{3(18)^n}{2\pi}\left|\sin\frac{K-D}{36^n}-2\sin\frac{K}{36^n}+\sin\frac{K+D}{36^n}\right|-\sum_{n=m+1}^\infty\frac{3(18)^n}{2\pi} \left|\sin\frac{K-D}{36^n}-2\sin\frac{K}{36^n}+\sin\frac{K+D}{36^n}\right|-4\\&\geq \frac{3(18)^m}{2\pi}4\sin^2\frac{D}{2(36)^m}\left|\sin\frac{K}{36^m}\right|-\sum_{n=1}^{m-1}\frac{3(18)^n}{2\pi}4-\sum_{n=m+1}^\infty \frac{3(18)^n}{2\pi} 4\sin^2\frac{D}{2(36)^n}\left|\sin\frac{K}{36^n}\right|-4\\&\geq\frac{3(18)^m}{2\pi}4\sin^2\frac\pi6\sin\frac\pi6-\frac{3}{2\pi}\frac{4(18)^m}{17}-\sum_{n=m+1}^\infty \frac{3(18)^n}{2\pi}4\left(\frac{36^m}{2(36)^n}\right)^2-4\\&=\frac{3(18)^m}{2\pi}\left(\frac12-\frac4{17}-\frac1{71}\right)-4 \end{align} So if $m\ge2$, $$|a_{k_i-h}-2a_{k_i}+a_{k_i+h}|\geq\frac{3(18)^2}{2\pi}\left(\frac12-\frac4{17}-\frac1{71}\right)-4>0$$

If $m=1$, we can actually have $$|a_{k_i-h}-2a_{k_i}+a_{k_i+h}|\geq\frac{3(18)^1}{2\pi}\left(\frac12-\frac1{71}\right)-4>0$$ as the term $$\sum_{n=1}^{m-1}\frac{3(18)^n}{2\pi}\left|\sin\frac{K-D}{36^n}-2\sin\frac{K}{36^n}+\sin\frac{K+D}{36^n}\right|$$ doesn't occur.

Therefore we always have $a_{k_i-h}-2a_{k_i}+a_{k_i+h}\ne0$ which proves the assertion.

Remark

The argument can be improved a bit more to prove for $36$ using the same equation. As shown in the argument, it is easy to prove for arithmetic sequences whose common difference is large(compare the cases $m=1$ and $m=2$). This post will be updated soon with some more tweaks attached to it.