Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it:

$o(2^n/n)\log(o(2^n/n) + n)$

I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + n) = o(2^n/n)$, but then I can't say $\log(o(2^n/n)) = o(\log(2^n/n))$, can I? The rest would follow easily.

At least, it's not true in general that if $g(n)$ is $o(f(n))$ then $\log(g(n)) = o(\log(f(n)))$ (e.g., use $n$ and $n^2$). Is there some other way to do it? (Or is it plain not true?)

[EDIT] While it's not entirely relevant to the question, I suppose I should give the context. I'm working on an exercise from Gems of Theoretical Computer Science where you give a lower bound of $\Omega(2^n/n)$ on the circuit size of a boolean function generated from an incompressible string. So far, I have that if there are $g$ gates and $n$ variables, then the total circuit requires $g(c+2\log(g+n))$ bits to describe. Then supposing that the number of gates is $o(2^n/n)$, we should arrive that the total circuit description length (and hence the Kolmogorov complexity of the string) is $o(2^n)$, a contradiction.

share|improve this question
    
I am not quite sure if these steps are valid (other viewers please correct me if they are not, but my intuition says to do something along the lines of $\log(o(2^n/n)) = \log((2^n/n)o(1)) = \log(2^n/n)+\log(o(1)) = \log(2^n/n)+o(1) = o(\log(2^n/n)).$ –  nullUser Apr 22 '12 at 3:06
    
$f(n)$ is not $o(f(n))$ though... and isn't $o(1)$ just zero? –  JeremyKun Apr 22 '12 at 3:09
1  
You are correct, I was thinking $O$ not $o$. However, $o(1)$ does not have to be zero, it just has to tend to 0 as $n \to \infty$. For example $1/n = o(1)$ since $(1/n)/1 \to 0$ as $n \to \infty$. –  nullUser Apr 22 '12 at 3:16
add comment

2 Answers 2

up vote 1 down vote accepted

Consider $a_n=\log(n+x_n)$ with $x_n=o(2^n/n)$. Since $\log(2^n/n)=n\log2-\log n=\Theta(n)$, our question is to know whether $a_n=o(n)$.

With no restriction on the sign of $x_n$, there is no hope. Assume for example that $x_n=-n+\mathrm e^{-y_n}$ with $y_n\to+\infty$. Then $x_n=-n+o(1)$ hence $x_n=o(2^n/n)$ but $a_n=-y_n$ hence $(a_n)$ may be any sequence such that $a_n\to-\infty$.

Even assuming that $x_n\geqslant0$ for every $n$, the conclusion that $a_n=o(n)$ is not guaranteed. For example, $x_n=2^{n/2}$ yields $x_n=o(2^n/n)$ and $a_n=n/2$, which is not $o(n)$. But for every nonnegative $(x_n)$, $\log n\leqslant a_n\leqslant n$ for every $n$ large enough, hence $a_n=O(n)$.

share|improve this answer
    
Aha! But this still works for my overall goal, since $o(2^n/n)O(n)$ is still $o(2^n)$. Thanks! –  JeremyKun Apr 22 '12 at 16:42
add comment

I think the fact that this is $o(2^n/n)\log(o(2^n/n)+n)$ gives you a representation of f as $cn(2^n/n)\log (dn(2^n/n)+n)=cn(2^n)\log(dn(2^n/n)+n)/n$ and I think it's pretty clear if the dn go to 0 then $\log(dn(2^n/n)+n)/n$ is at LEAST bounded, and the cn go to zero yielding the whole thing as o(2^n).

share|improve this answer
    
I think I'm confused by your notation, what are the $cn$ and $dn$? Are those sequences? –  JeremyKun Apr 22 '12 at 3:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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