Prove that $f(n)=o(g(n))$ implies there is computable $h(n)=o(g(n)) \in O_C(g(n))$ s.t. $f(n)=o(h(n))$

Question

I want to show that for time constructible $f,g$ if $f(n)=o(g(n))$ then there is a computable function $h(n)$ such that $h(n)=o(g(n))$ and further $f(n)=o(h(n))$ and $h$ is computable in $O(g(n))$.

I am having difficulty even constructing any $h$ that is "in-between" the bounds, that is, for any $a$ there is $k,k\leq n$:

$$f(n)\leq ag(n)$$ $$f(n)\leq ah(n)$$ $$h(n)\leq ag(n)$$

Or perhaps I am going about it wrong, and using a non-constructive argument gives the result? Time-hierarchy theorem may be helpful, for any time-constructible $g(n)$:

$$\text{DTime}((\frac{g(n)}{\text{log}(n)}))\subset \text{DTime}(g(n))$$

But using the theorem involves taking logarithms, and I do not see how they can appear.

Answer 1

No, you cannot involve log or any other specific function in g, because you cannot know order difference between f and g. So let's put

p = f/g, then p = o(1)

and use real x instead of natural n as an argument.

You need to prove that there exists some q that

q = o(1) and p = o(q)

Then h = g/q will be a function you are looking for.

The answer is yes and I can give you some hint.

Review the functions $F(x) = \frac{1}{f(1/x)}$ and $G(x) = \frac{1}{g(1/x)}$ for positive x around 0.

Now you deal with a modulus of continuity. You can read about the subject here

What you simply need is to find another modulus of continuity $H(x) = \frac{1}{h(1/x)}$ where

G < H < F for small x > 0

Then h(x) will be the function you need.

Of course, generally speaking F and G are not necessary modulus of continuity, but you can bring it to the form without change or order class.

Also for all functions f(x) >> x (x = o(f)) after the conversion, corresponding F(x) won't be actual modulus of continuity, but it will be an element of the similar set of functions symmetric to all modula of continuity over F(x) = x.

So if functions belong to the same set, you find modulus of continuity or its symmetric function in between. Otherwise, you can use h(x) = x

This is not a proof, just an idea.