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)$ ?

  • $\begingroup$ Not likely. Consider listing the dyadic rationals by denominator first. Gerhard "Or Think Of Farey Fractions" Paseman, 2013.04.22 $\endgroup$ – Gerhard Paseman Apr 22 '13 at 18:24
  • $\begingroup$ Also, one can extend the example to find an injection sigma such that there is no set A with analogous properties, where n^2 is replaced by any primitive recursive function. Gerhard "That Should Make Enough Counterexamples" Paseman, 2013.04.22 $\endgroup$ – Gerhard Paseman Apr 22 '13 at 18:43
  • $\begingroup$ Gerhard, I'm not convinced by your argument since every sequence of length $n$ has a monotone subsequence of length about $\sqrt{n}$. Still, I think $O(n^2)$ is too optimistic for the infinite case. $\endgroup$ – François G. Dorais Apr 22 '13 at 19:52
  • $\begingroup$ The problem is to make a subsequence with indices that do not grow quickly. Suppose I decide to make an increasing sequence and pick a_1000. If the next 2^1000 terms are less than sigma(a_1000), I am unlikely to pick a_1001 to look like (1001)^2. Having finitely many obstructions like this does not matter, but since his step size is recursively bounded, I can come up with infinitely many such obstructions and eventually defeat his O condition. There may be a version which defeats arbitrary recursive bounds too. Gerhard "Or Try Sine Of Log" Paseman, 2013.04.22 $\endgroup$ – Gerhard Paseman Apr 22 '13 at 20:26

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

| cite | improve this answer | |
  • $\begingroup$ Thank you Gerhard, your counterexample works. Actually im 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 dont contradict this weakened version of the problem. Do you have some suggestion about this? $\endgroup$ – ilcapu Apr 23 '13 at 0:47
  • $\begingroup$ (Clearly the condition $a_n=O(n^2)$ would immediately imply the divergence of the series of reciprocals of gaps, but it`s effectively too strong.) $\endgroup$ – ilcapu Apr 23 '13 at 0:52
  • $\begingroup$ Why is it a contradiction if $a_{n+1}-a_n \gt a_n/4$ infinitely often? If $a_n$ reads the decimal expansion of $n$ as a base $100$ number, then $a_{n+1} \gt 10 a_n$ infinitely often, whenever $n+1$ is a power of $10$, but $a_n \le n^2$. This construction may work, but it needs another argument. $\endgroup$ – Douglas Zare Apr 23 '13 at 9:13
  • 1
    $\begingroup$ There are monotone subsequences of this sequence with $a_n = O(n^2)$. $1/8, 3/8, 17/32, 19/32, 21/32, 23/32, 97/128, 99/128, ..., 111/128, 449/512, ...$. That is monotone. $a_1=4, a_2=5, a_3=24, a_4=25, a_5=26, a_6=27, a_7=112, a_8=113,... a_{14}=119, a_{15}=480...$. In this monotone subsequence, $a_{2^n-1} \lt 2^{2n+1}, a_n \le 4n^2$. $\endgroup$ – Douglas Zare Apr 23 '13 at 20:39

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.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.