25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By "subsequence such that the terms are equally spaced on the original sequence" do you mean that the subsequence is of the form $\displaystyle b_n = a_{xn+y}$ where $x,y$ are integers? $\endgroup$ – Regret Dec 9 '14 at 7:44
  • $\begingroup$ Yes. That's the definition. $\endgroup$ – user198454 Dec 9 '14 at 7:46
  • 2
    $\begingroup$ @TheMathTroll: You could append the proof for $n=4$ to the question, or post it as a (partial) answer. Either way, it would be interesting to see. $\endgroup$ – Regret Dec 15 '14 at 7:07
  • 2
    $\begingroup$ For many problems like this the number of terms explodes rapidly. $11$ terms guarantee a sequence of $4$, but it might be something enormous for $5$. It looks similar to the Ramsey numbers to me. $\endgroup$ – Ross Millikan Dec 19 '14 at 18:14
  • 1
    $\begingroup$ yeah... I am still thinking about it; no progress. Btw, are you the 40-point scorer at IMO 2012 or is that just a confusion in name? $\endgroup$ – user198454 Dec 24 '14 at 17:15
8
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How you checked subsequences isn’t very interesting, but where is a counterexample? We must construct an infinite sequence, and can’t use periodic sequences since any of them contains an (infinite) equally spaced constant subsequence. $\endgroup$ – Incnis Mrsi Dec 19 '14 at 7:58
  • $\begingroup$ @Incnis: I think you may have misinterpreted the aim of my post. If there exists an $N$ such that all $(a_n)_{n=1}^N$ contain equally spaced, length 8 subsequences of arithmetic progression, then that $N$ may be found computationally. If $N$ is found, then the answer to OP's question is yes. $\endgroup$ – Regret Dec 19 '14 at 8:41
  • 1
    $\begingroup$ @Incnis: In addition, an easy "proof" for AP length $4$ is readily available, you just need to confirm that all $2048$ length $11$ sequences contain one. $\endgroup$ – Regret Dec 19 '14 at 8:45
7
$\begingroup$

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\}$:

enter image description here

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;
$\endgroup$
  • 2
    $\begingroup$ Why has this answer been downvoted? $\endgroup$ – Regret Dec 21 '14 at 14:51
5
+200
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Congrats! May be better and more easily provable bounds can be obtained if we take another periodical function instead of the sinus. For instance, a “saw” $f(x)=g(x-\lfloor x\rfloor)$, where $g(x)=x$, if $0\le x\le 1/2$ and $g(x)=1-x$, if $1/2\le x\le 1$. $\endgroup$ – Alex Ravsky Dec 25 '14 at 16:32
  • 2
    $\begingroup$ @AlexRavsky Yes I tried that(the same function...) but it didn't turn out well. The part where sine function becomes a good use is, interestingly $$f(x-y)-2f(x)+f(x+y)=-4f(x)f(y/2)^2$$where $f(x)=\sin x$. I could not think of any other function satisfying this kind of 'separating' equation and could not modify that part. $\endgroup$ – karvens Dec 25 '14 at 16:45
  • $\begingroup$ This does look like the kind of answer that could be fiddled with to get tighter bounds; it looks like we might be able to replace the intervals $[\pi/6,5\pi/6]$ and $[7\pi/6,11\pi 6]$ with some larger intervals (i.e. whatever values still force a positive result at the end) or that we might be able to require less terms to ensure one in those bounds (since currently, a rather primitive bound is used). $\endgroup$ – Milo Brandt Dec 25 '14 at 16:55
  • $\begingroup$ @karvens Maybe this functional equation has no essentially different (bounded) solutions (see, for instance, this first page. Nevertheless, the situation may be not so bad, because, as I understand, we don’t need exact equalities for the function but only some bounds. Can you formulate the needed conditions for the function as inequalities (or equalities)? $\endgroup$ – Alex Ravsky Dec 25 '14 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy