3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Not likely. Consider listing the dyadic rationals by denominator first. Gerhard "Or Think Of Farey Fractions" Paseman, 2013.04.22 $\endgroup$ Apr 22, 2013 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$ Apr 22, 2013 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$ Apr 22, 2013 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$ Apr 22, 2013 at 20:26

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • $\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, 2013 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, 2013 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$ Apr 23, 2013 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$ Apr 23, 2013 at 20:39
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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