Arithmetic Progressions in slowly oscillating sequences

Question

An infinite sequence ($a_0$, $a_1$, ...) is such that the absolute value of the difference between any 2 consecutive terms is equal to $1$. Is there a length-8 subsequence such that the terms are equally spaced on the original sequence and the terms form an arithmetic sequence from left to right?

Clarifications: 1. The Common difference can be negative or 0

Example: the sequence 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 10

works because the 3rd term is 3, 6th term is 4, 9th term is 5, ..., 24th term is 10.

and 3rd, 6th, ..., 24th terms are equally spaced. They also form an arithmetic sequence.

I am thinking about Szekeres theorem but idk if that would work

EDIT: I was able to show it for $n=$. I am actually more interested in indefinitely long ones. But hey, it could be that one can construct something that an indefinitely long one will never happen.

Answer 1

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.

Answer 2

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;

Answer 3

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.