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)$ ?
4
-
$\begingroup$ Not likely. Consider listing the dyadic rationals by denominator first. Gerhard "Or Think Of Farey Fractions" Paseman, 2013.04.22 $\endgroup$– Gerhard PasemanCommented 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$– Gerhard PasemanCommented 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$– François G. DoraisCommented 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$– Gerhard PasemanCommented Apr 22, 2013 at 20:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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
answered Apr 22, 2013 at 23:07
-
$\begingroup$ Thank you Gerhard, your counterexample works. Actually i
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 dont contradict this weakened version of the problem. Do you have some suggestion about this? $\endgroup$– ilcapuCommented 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$– ilcapuCommented 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$ Commented 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$ Commented Apr 23, 2013 at 20:39
$\begingroup$
$\endgroup$
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.
answered Apr 23, 2013 at 22:26