Polynomial Approximation of Multiplicative Function

265 Views Asked by At

Motivation: I am a undergrad studying number theory and all the multiplicative functions I studied in the course note has a polynomial upper bound, leading me to inquire where this holds for all multiplicative functions.

Given a multiplicative function $f$, does it necessarily have a polynomial upper bound?

(I suspect that the statement is false, and I had tried to construct some exponentially growing multiplicative functions (such as $f(p^a) = p^{p^a}$) as counterexample, but I had difficulty proving that they indeed grow faster than any polynomial)

1

There are 1 best solutions below

1
On BEST ANSWER

Not polynomially bounded

As you suspected, a multiplicative function $f$ does not necessarily have a polynomial upper bound.

For example, let $f$ be the completely multiplicative function such that $f(p_i)=i{p_i}^i$, where $p_i$ is the $i$-th prime number. Given any $i, c, n_0>0$, let $q$ be the $\lceil i+c+n_0\rceil$-th prime. Then $q>n_0$ and $$f(q)= \lceil i+c+n_0\rceil q^{\lceil i+c+n_0\rceil}>cq^i.$$ Hence, $f(n)\not\in O(n^i)$

Similarly, $f$ does not necessarily have an exponential upper bound nor double exponential upper bound.

More generally, $f$ does not necessarily have an upper bound that can be bounded by countably many functions.

Faster than any polynomial

Although the function $f$ given above is not bounded by any polynomial, it does not grow faster than, for example, $n\mapsto n^2$ since $f(2^k)=2^k$ for all $2^k$.

Let $g$ be the multiplicative function such that $g(p_i^k)={p_i}^{ki}$, where $p_i$ is the $i$-th prime number, $k=1,2,\cdots$. It is not hard to show that $g$ grows faster than every polynomial function.

Your function, $h(p^a)=p^{p^a}$ also grows faster than every polynomial function.

More generally, given countably many functions, there is a multiplicative function that grows faster than every given function.