<s>[INST] Functional Equation $ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) $ I have the following functional equation:
$$ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) $$
Under the precondition that $ f ( n ) = \omega ( 1 ) $, monotonicity and an initial value $ f ( 1 ) = \Theta ( 1 ) $, one can show (by induction) that $ \Omega \big( ( \log n ) ^ k \big) = f ( n ) = O ( n ^ \alpha ) $ for arbitrary large $ k $ and small $ \alpha $ (see below).
It seems to me that these bounds are very tight so the question is:

Is there a (simple) function that satisfies these conditions?


Proof sketch:
$$ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) \le 2 \left( \frac n { f ( n ) } \right) ^ \alpha = \left( \frac 2 { f ( n ) ^ \alpha } \right) n ^ \alpha \le n ^ \alpha $$
for sufficiently large $ n $.
$$ f ( n ) = 2 f\left( \frac n { f ( n ) } \right) \ge 2 \left( \log \frac n { f ( n ) } \right) ^ k \ge 2 \left( \log \frac n { n ^ \alpha } \right) ^ k = 2 ( 1 - \alpha ) ^ k ( \log n ) ^ k \ge ( \log n ) ^ k $$
for sufficiently large $ n $ and small $ \alpha $.
 [/INST] First of all, note that for a nonnegative constant $ c $, the function $ f $ defined by
$$ f ( n ) = 2 ^ { - \frac 1 2 + \sqrt { 2 \log _ 2 n + c } } $$
satisfies the functional equation
$$ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) \text . $$
Also, $ f $ is strictly positive and strictly increasing, and as $ n \to + \infty $, $ f ( n ) \in o ( n ^ \alpha ) \cap \omega \big( ( \log _ 2 n ) ^ k \big) $ for any $ k $ and any positive $ \alpha $.
But how can one find such solutions? For more simplicity in the upcoming calculations, first define the function $ g $ with $ g ( n ) = \log _ 2 f ( 2 ^ n ) $, so that we have $ f ( n ) = 2 ^ { g ( \log _ 2 n ) } $. Then, the functional equation is simplified to
$$ g ( n ) = g \big( n - g ( n ) \big) + 1 \text . $$
Assuming we have $ g ( n ) = m $ for some fixed $ n $, using induction we get
$$ g \left( n - m k + \frac { k ( k - 1 ) } 2 \right) = m - k $$
for any nonnegative integer $ k $. Assuming that $ f $, and thus $ g $, is well-behaved enough, we can consider the above equation for all nonnegative real values of $ k $. By letting $ y = m - k $ and $ x = n - m k + \frac { k ( k - 1 ) } 2 $, we can see that
$$ m - y = k = m + \frac 1 2 \pm \sqrt { \left( m + \frac 1 2 \right) ^ 2 - 2 ( n - x ) } \text , $$
which for $ y > 0 $ gives
$$ g ( x ) = y = - \frac 1 2 + \sqrt { 2 x + c } \text , $$
where $ c = \left( m + \frac 1 2 \right) ^ 2 - 2 n $. This holds for any $ x \le n $, as we had the previous equations for any $ k \ge 0 $. Thus, we can see that $ \left( g ( x ) + \frac 1 2 \right) ^ 2 - 2 x $ is in fact constant on the whole domain (the constant must be nonnegative if we want the square root above to be well-defined for all positive values of $ x $). Therefore, the above formula for $ g ( x ) $ holds for any desired input, and writing it in terms of $ f $ gives the claimed result for all $ n \ge 1 $.
</s>