On asymptotic estimates for arithmetic cost functions

Abstract:

Let $\tau (n)$ (the cost of $n$) be the minimum number of arithmetic operations needed to obtain $n$ starting from 1. We prove that $\tau (n)\ge \frac {\log n}{\log \log n}$ for almost all $n\in \mathbf {N}$, and, given $\varepsilon >0$, $\tau (n)\le \frac {(1+ \varepsilon )\log n}{\log \log n}$ for all $n$ sufficiently large. We prove analogous results for costs of polynomials with integer coefficients.