On Golomb's self describing sequence (Q1896582)

The self-describing sequence introduced by \textit{S. W. Golomb} [Problem 5407, Am. Math. Mon. 73, 674 (1966)] is defined by: \(F(1) = 1\), \(F(n) = \# \{m; F(m) = n\}\) and \(F\) is nondecreasing. It has been proved by \textit{N. J. Fine} [Solution to Problem 5407, Am. Math. Mon. 74, 740-743 (1967)]\ that \(F(n) = cn^{\varphi - 1} + E(n)\), where \(\varphi = {1 + \sqrt 5 \over 2}\) is the golden ratio, \(c = \varphi^{2 - \varphi}\) and \(E(n) = o(n^{\varphi - 1})\). D. E. Knuth asked whether a better bound can be found for \(E(n)\) and whether \(E(n)\) is bounded. Computations by \textit{I. Vardi} confirmed the boundedness of \(E\) and he proved [J. Number Theory 40, No. 1, 1-11 (1992; Zbl 0758.11012)]\ that \(E(n) = O({n^{\varphi - 1} \over \log n})\). Vardi conjectured that \(E(n) = \Omega_\pm ({n^{\varphi - 1} \over \log n})\). The author of the paper under review shows that \(E(n) = \Omega_\pm (n^{\varphi - 1 - \varepsilon})\) \(\forall \varepsilon > 0\). The proof is both ingenious and elementary which makes it very interesting.