Let $\sigma :\mathbb{N}\rightarrow\mathbb{R}$ an injective sequence of real numbers.
There exists an infinite set $A=$ { ${a_{1},a_2,\ldots ,a_n,\}\ldots$ } $ \subset{N}$ such that
i) $\sigma_{|A}$ is monotone
ii) $a_n=O(n^2)$ ?
Let $\sigma :\mathbb{N}\rightarrow\mathbb{R}$ an injective sequence of real numbers.
There exists an infinite set $A=$ { ${a_{1},a_2,\ldots ,a_n,\}\ldots$ } $ \subset{N}$ such that
i) $\sigma_{|A}$ is monotone
ii) $a_n=O(n^2)$ ?
For $0 \leq k \lt 2^j$ , let $\sigma(k+2^j)=(2k+1)/2^{j+1}$ . Let A be a subset of integers such that $\sigma\mid_A$ is monotonic. Then $a_{n+1} - a_n$ is greater than $a_n/4$ infinitely often, which cannot hold if $a_n$ is $O(n^d)$ for any positive integer $d$.
Gerhard "Can't Make It Much Simpler" Paseman, 2013.04.22
m interested in a slighty different problem, i.e. if exists an infinite subset $A$ such that $\sigma_{|A}$ is monotone and $$ \sum_{n=1}^{+\infty}\frac{1}{a_{n+1}-a_n}=+\infty$$ Your example don
t contradict this weakened version of the problem. Do you have some suggestion about this?
$\endgroup$
– ilcapu
Apr 23 '13 at 0:47
If $\sigma$ alternates in sign slowly enough, then any subsequence whose indices are $O(n^2)$ must also alternate in sign, hence must not be monotone.
Let $r:\mathbb N \to \mathbb N$ be a rapidly growing function, so rapid that
$$\lim_{n\to \infty} \frac{r(n+1)}{r(n)^2} = \infty.$$
In other words, for any $c$, for large enough $n$, $r(n+1) \gt c r(n)^2$.
For example, we can recursively define $r(n+1) = n r(n)^2$, or take
$$r(n) = 2^{2^{n^2}}.$$
Then for any increasing sequence $\lbrace a_n \rbrace$ so that $a_n \lt c n^2$, for large enough $m$, $a_{n-1} \le r(m) \implies a_n \le r(m+1)$. So, if $a_n = O(n^2)$, then $\lbrace a_n \rbrace$ must hit all but finitely many intervals $(r(m),r(m+1)]$.
Then choose $\sigma$ so that it is positive on even intervals $(r(2m),r(2m+1)]$ and negative on odd intervals $(r(2m+1),r(2m+2)]$. Any subsequence whose indices are $O(n^2)$ must change sign infinitely often, hence more than once, so it can't be monotone.