wojtask
4.7-4
There is a high chance there is no proper solution to this exercise. Instead of a solution, in the document I put a clarification that details this problem, and provides a sketch of a proof for this statement.
I have also described it on Stack Exchange hoping to get some feedback from the mathematics community. Later, when no one could find issues in my reasoning, I am going to confront the Authors and present them the proof sketch. By then, I am going to keep this issue open, and keep marked as "blocked".
My answer on Stack Exchange got deleted, allegedly due to the "low quality posts" rule. Let me paste the answer here:
I have also tried many functions but none of them fit, so I started to wonder if any such function exists. If not, that would be quite surprising, since that would contradict the statement in the book (page 116, just under the definition of PGC). The book also mentions that there exist functions that don't satisfy PGC while being upper bounded by a polynomial.
Let's negate that long definition from the book. A function $f(n)$ (defined on sufficiently large reals) does not satisfy PGC if $$\forall(\widehat n>0),\exists(\phi\ge1),\forall (d>1),\exists(1\le\psi\le\phi),\exists(n\ge\widehat n),(df(\psi n)<f(n))\text{ or }(f(\psi n)/d>f(n)).$$
Now let's interpret that. Suppose we picked $\phi\ge1$. Then no matter how big $d>1$ we choose, we can find an interval $I=[n,\phi n]$ of arguments, such that for some $\psi n\in I$, $f(\psi n)$ dominates $f(n)$ by more than the factor of $d$ OR the other way round, $f(n)$ dominates $f(\psi n)$ by more than the factor of $d$. Thus, that local dominance of $f(\psi n)$ over $f(n)$ should be either $o(1)$ or $\omega(1)$, not $\Theta(1)$. And such a dominance should hold consistently across the whole domain, perhaps except for some small numbers, i.e., for $n$ no less than some arbitrary $\widehat n$.
As an example of a non-PGC function consider an exponential function $f(n)=a^n$. We can pick $\phi=2$, so that $I=[n,2n]$ and $f(2n)=a^{2n}=a^n\cdot a^n=a^nf(n)$. If $0<a<1$, then $f(2n)=o(1)f(n)$, and if $a>1$, then $f(2n)=\omega(1)f(n)$.
Another example is $g(n)=n^{\lg n}$. Pick $\phi=2$, so $I=[n,2n]$, and we have $$g(2n)=(2n)^{\lg(2n)}=(2n)^{\lg n+1}=(2n)2^{\lg n}n^{\lg n}=2ng(n)=\omega(1)g(n).$$
On the other hand, $f(\Theta(n))=\Theta(f(n))$, when for any function $g(n)=\Theta(n)$ there exist constants $c_1>0$, $c_2>0$, $n_0>0$ such that for all $n\ge n_0$, $f(g(n))$ is defined and $$0\le c_1f(n)\le f(g(n))\le c_2f(n).$$
But we can't have a function that preserves $\Theta$-notation, while also not meet PGC. This is because $\psi n=\Theta(n)$ for any constant $\psi\ge1$, so $f(\psi n)$ (for sufficiently large n) is lower bounded and upper bounded by $f(n)$ times a constant (not $o(1)$ or $\omega(1)$ as required by the non-PGC condition earlier).
Nevertheless, I do believe that such functions really exist but I have a strong belief the issues we've shown arise only under the definition of PGC found in the book. There are other formulations of this condition, that driving functions should hold in Akra-Bazzi recurrences, e.g. in the original paper, or in the Wikipedia article about the Akra-Bazzi method. It is shown here that the latter implies the former.
To rephrase the above reasoning, PGC definition from the book more or less states that function $f(n)$ satisfies PGC, if it preserves $\Theta$-notation for functions like $\psi n$, where $\psi\ge1$ is a constant. So how can we have a $\Theta$-preserving function for any $g(n)=\Theta(n)$ but not for $g(n)=\psi n$?
Thanks! Let me familiarize with the paper you linked and with your observation on how to treat expressions involving asymptotic notations, and confront them with my previous reasoning.
I have added to my post mentioned in my previous message an example of a polynomially bounded function that doesn't satisfy the PGC. Just to make the text more complete.
BTW: I have reported to the authors an issue with the current PGC definition. Namely, it must disallow the possibility of having an empty (trivial) function f(n)=0 for all $n \ge \hat n$ in order for the PGC to imply that f(n) is asymptotically positive. Once they respond I will then provide a new comment and solution to Exercise 4.7-3 as a further hint for Exercise 4.7-4.
You mean Exercise 4.7-3, right? I have already contacted the Authors, mentioning the same function that zeroes for sufficiently large n, but I complained about the exercise itself, instead of the PGC definition. I haven't yet received any word from them.
But I like your approach. Hopefully the authors will answer to your remarks and improve the definition of PGC, so my concerns are addressed.