Inequality in a bounded real sequence

Solution 1:

Here is a counter-example using Hurwitz's theorem

Let $\phi = \frac{1+\sqrt 5}2$ be the golden ration. Since the inequality $|\phi - p/q| < 1/3q^2$ has finitely many solution for integers $p,q$, let $N$ be an integer greater than all the $|p|$ occurring in those solutions.

Let $x_n = 3n\phi \pmod {3N}$

Suppose you find distinct integers $u$ and $v$ such that $|x_u - x_v||u-v| < 1$. Then there are integers $p_u$ and $p_v$ such that $x_u = 3u\phi - 3Np_u$ and $x_v = 3v\phi - 3Np_v$. So $|3(u-v)\phi-3N(p_u-p_v)||u-v| < 1$, and $|\phi - N(p_u-p_v)/(u-v)| < 1/3(u-v)^2$. Hence $(N(p_u-p_v), u-v)$ is one of the finitely many solutions to the inequality above, hence $N > |N(p_u-p_v)|$. This implies $p_u = p_v$, and we get $|\phi| < 1/3(u-v)^2 \le 1/3 < \phi$, which is a contradiction.

Solution 2:

I don't have any solid proof, but I do have some evidence to suggest that the proposition might be false: a proof that if there are always such $u,v$ pairs, then they occur frequently in any sequence, and second, a computed example of a sequence that has no such $u,v$ pairs, yet appears to be bounded.

Take a bound $[a,b]$. Consider $S_n$, the set of finite sequences such that $|x_u-x_v|\cdot|u-v|<1$ for some $u,v$. Then, $|x_u-x_v|=\frac{1}{|u-v|}-\epsilon$ for some $\epsilon>0$, and so the set $$ [a,b]\times [a,b]\times\cdots\times(x_u-\frac{\epsilon}{2},x_u+\frac{\epsilon}{2})\times[a,b]\times\cdots\times[a,b]\times(x_v-\frac{\epsilon}{2},x_v+\frac{\epsilon}{2})\times[a,b]\times\cdots\times[a,b] $$ is open in $[a,b]^n$ and is a subset of $S_n$, meaning that $S_n$ is open in $[a,b]^n$. It follows that, since $[0,b]$ is compact, by Tychonoff's theorem, $[a,b]^n$ is compact, and therefore, $\overline{S_n}$ is closed and thus compact. Let $C_n$ be the extension of $\overline{S_n}$ to $[a,b]^\omega$ by appending copies of $[a,b]$, so that by Tychonoff's Theorem, $C_n$ is compact. However, $\{C_n\}$ is a sequence of decreasing compact sets, whose intersection $\bigcap_{n\in N} C_n$ is nonempty if each $C_n$ is. An element of $\bigcap_{n\in N} C_n$ would be a sequence such that $|x_u-x_v|\cdot|u-v|\ge1$ for all $u,v$.

Thus, for a sequence bounded by $[a,b]$, if we can always find some finite sequence of length $n$ such that $|x_u-x_v|\cdot|u-v|\ge1$ for all $u,v$, we can find an infinite sequence violating the proposition. This means that, if the proposition is true, pairs $u,v$ will appear "commonly", in the sense that there is some $n$ at which all finite sequences of length $n$ must have a $u,v$ pair with $|x_u-x_v|\cdot|u-v|<1$, and so $u,v$ pairs will take up at least $\frac{2}{n}$ of the sequence.

A simple strategy of setting $x_0=0$ and $x_n$ to the minimum positive number such that $\{x_0,\cdots,x_n\}$ has $|x_u-x_v|\cdot|u-v|\ge1$ seems to work well, as demonstrated by the computer program below. The output of the program will have the bound on $\{x_n\}$ taper off to just above $2.5$ all the way into a sequence of length $250,000$, which seems to indicate that this naive sequence is bounded.

#include <stdbool.h>
#include <stdio.h>
#include <float.h>

#define EPS 0.0000000000000000002
#define NUM 250000
long double data[NUM];

static bool within(long double x, long double y, int n){
        long double test = (x-y)*n;
        return test >= (long double)(-1.0) && test <= (long double)(1.0);
}

main(){
        long double max = 0.0;
        int i;
        data[0] = 0.0;
        for(i=1; i<NUM; i++){
                long double test = ((long double)1.0)/i;
                int j;
                for(j=i-1; j>0; j--){
                        if(within(test,data[j],i-j)){
                                test = data[j]+((long double)1.0)/(i-j)+EPS;
                                j=i;
                        }
                }
                data[i] = test;
                if(test > max){
                        max = test;
                }
                if(i%100==0) printf("Got %d/%d -- max=%.15Lf\n",i,NUM,max);
        }
}