simple but (seemingly?) tricky recurrence

Question

I'm cross-posting from math stack exchange after receiving no answers there.

I came across the following very simple recurrence-style expression but am having trouble solving it: $$T(2n) \in \theta(T(n) \log(T(n)))$$ for sufficiently large $n \in \mathbb{N}$.

My first thought was to take the logarithm of both sides and apply the Master Theorem but the "$f(n)$" term unfortunately is not in the right form. Repeated expanding quickly yields a mess. Wolfram Alpha was no use.

Plugging in $T(n) = n^a$ makes the left side grow too slowly so $T$ must grow faster than any polynomial. But plugging in $T(n) = \exp(\log(n)^b)$, $b>1$, causes the left side to grow too fast so $T$ must grow more slowly. So it seems $T$ is super-polynomial but barely.

What approaches are viable for such an equation?

Answer 1

We shall asymptotically solve $\color{blue}{ f(2n) = f(n)·\log(f(n))·2^c }$ for any $c∈ℝ$ as $n → ∞$ (where $\log = \log_2$). $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $

~ ~ ~

Note that $\log\log(2n) = \log(\log(n)+1)$ $= \log\log(n)+\lfrac{r}{\log(n)}+\cdots$ where $r = \lfrac1{\ln(2)}$. (Omitted terms are asymptotically smaller.)

And $\log\log\log(2n) = \log\big(\log\log(n)+\lfrac{r}{\log(n)}+\cdots\big)$ $= \log\log\log(n)+\lfrac{r^2}{\log(n)·\log\log(n)}+\cdots$.

Let $g$ be a function such that $f(n) = 2^{\log(n)·\log\log(n)+g(n)}$. We shall take for granted (I believe it can be proven with some effort) that $g(n) ≪ \log(n)·\log\log(n)$.

Then $f(2n) = 2^{\log(2n)·\log\log(2n)+g(2n)}$

  $= 2^{\log(2n)·\big(\log\log(n)+\lfrac{r}{\log(n)}+\cdots\big)+g(2n)}$

  $= 2^{\log(2n)·\log\log(n)+g(2n)+r·\big(1+\lfrac1{\log(n)}\big)+\cdots}$.

And $f(n)·\log(f(n))·2^c$

  $= 2^{\log(n)·\log\log(n)+g(n)+\log(\log(n)·\log\log(n)+g(n))+c}$

  $= 2^{\log(n)·\log\log(n)+g(n)+\log(\log(n)·\log\log(n))+\lfrac{r·g(n)}{\log(n)·\log\log(n)}+c}$

  $= 2^{\log(2n)·\log\log(n)+g(n)+\log\log\log(n)+c+\lfrac{r·g(n)}{\log(n)·\log\log(n)}}$.

Thus $g(2n)-g(n) = \log\log\log(n)+(c-r)−\lfrac{r}{\log(n)}+\lfrac{r·g(n)}{\log(n)·\log\log(n)}+\cdots$.

So $g(2^{k+1})-g(2^k) = \log\log(k)+(c-r)+\cdots$ as $k → ∞$.

Thus $g(2^k) = \sum_{i=2}^{k-1} \log\log(i) + k·(c-r) + \cdots$.

  $ = k·\log\log(k) + k·(c-r) + \cdots$.

Thus $g(n) = \log(n)·\log\log\log(n)+\log(n)·(c-r)+\cdots$.

Therefore $\color{blue}{ f(n) = 2^{\log(n)·(\log\log(n)+\log\log\log(n)+(c-r)+\cdots)} }$.

~ ~ ~

To check, letting $f_1(n) = 2^{\log(n)·(\log\log(n)+\log\log\log(n)+(c-r))}$ we get:

$\log(f_1(2n))$

  $= \log(2n)·(\log\log(2n)+\log\log\log(2n)+(c-r))$

  $= (\log(n)+1)·\big(\log\log(n)+\log\log\log(n)+(c-r)+\frac{r}{\log(n)}+\cdots\big)$

$\log(f_1(n)·\log(f_1(n))·2^c)$

  $= \log(n)·(\log\log(n)+\log\log\log(n)+(c-r))+\log\log(n)+\log\log\log(n)+c+\cdots$.

So $\log(f_1(2n)) - \log(f_1(n)·\log(f_1(n))·2^c) = \frac{r}{\log(n)} + \cdots$, as expected.

~ ~ ~

It may be possible to get an exact asymptotic solution, since we just have to find some $h$ such that $f(n) ∈ 2^{\log(n)·\big(\log\log(n)+\log\log\log(n)+(c-r)+h(n)+O(\lfrac1{\log(n)})\big)}$, but I'm not sure it's worth the trouble.

Answer 2

Let us attempt to solve the easier recurrence $T(2n) = T(n) \log T(n)$. Define $S(m) = \log T(2^m)$. Then $S(m+1) = S(m) + \log S(m)$. Let us heuristically convert this into a differential equation: $S' = \log S$. The solution to this equation is $S = \mathrm{li}^{-1} + C$, where $\mathrm{li}$ is the logarithmic integral. Roughly speaking, $\mathrm{li}(x) \approx x/\log x$, and so $\mathrm{li}^{-1}(x) \approx x\log x$. This heuristic implies that $S(m) \approx m \log m$, and so $T(n) \approx \exp \Theta(\log n \log \log n)$. Of course, at this point this is just an educated guess.

As a sanity check, suppose that $T(n) = \exp (\log n \log \log n)$, where all logarithms are base 2. Then $$ \begin{align*} T(n) \log T(n) &= \exp (\log n \log \log n) \log n \log \log n \\ &= \exp (\log n \log \log n + \log \log n + \log \log \log n) \\ &= \exp (\log (2n) \log \log n + \log \log \log n). \end{align*} $$ This is quite similar to $T(2n) = \exp (\log (2n) \log \log (2n))$ (though not the same).