Does $C(n)$ grow exponential versus $n$?

71 Views Asked by At

Let $λ(m)=n$ be the Carmichael Function of $m$. For each (even) number $n$, there is a largest number $m$ such that $λ(m)=n$. Let $C(n)$ denote the largest integer $m$ such that $λ(m)=n$. For instance, $C(2)=24$ and $C(4)=240$ since $24$ and $240$ are the largest numbers with Carmichael Function equal to $2$ and $4$ respectively. In these cases, $n$ is really small, and $C(n)$ is rather large compared to $n$. However for other $n$, $C(n)$ and $n$ are about the same size so there is no significant growth rate of $C(n)$ compared to $n$. Suppose this is not the case. So as $n$ gets larger and larger, is it possible that $C(n)$ will grow exponential compared to $n$? If not, what is the maximum growth rate of $C(n)$ compared to $n$?

1

There are 1 best solutions below

0
On BEST ANSWER

According to the Wikipedia page, there is a positive constant $c$ such that for sufficiently large $A$, there is $n > A$ with $\lambda(n) < (\ln A)^{c \ln \ln \ln A}$. That says if $m = \lambda(n)$, $C(m) \ge n > A$. Note that $$m = \lambda(n) < \exp(c (\ln \ln A)(\ln \ln \ln A)) < \exp(c (\ln \ln A)^2)$$ so $$C(m) > \exp(\exp(\ln(m)^{1/2}/c^{1/2}))$$ This is not quite as good as exponential growth, but I guess it is the best result known (or was at the time of writing).