3
$\begingroup$

What is the tightest lower bound currently known for the Carmichael function?

I imagine it must grow much more slowly than the Euler's totient function which according to here is bounded as

$$ \phi(n) \ge \frac{n}{e^{\gamma} \log \log n+ \frac{3}{\log \log n}} $$

But searching around on Google it's hard to find any literature on lower bounds of the carmichael function

Improve this question
$\endgroup$
5
  • $\begingroup$ Probably better to search around on MathSciNet, if you have access. $\endgroup$
    – Gerry Myerson
    Oct 11, 2019 at 20:55
  • $\begingroup$ sadly I do not have access to MathSciNet :( $\endgroup$
    – Sidharth Ghoshal
    Oct 11, 2019 at 20:56
  • 1
    $\begingroup$ Have you come across Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica. 58 (4): 363–385. MR 1121092. Zbl 0734.11047 and Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001? $\endgroup$
    – Gerry Myerson
    Oct 11, 2019 at 21:03
  • $\begingroup$ i have not come across that but i went to a certain source of articles, and looked for anything written by carl pomerance with carmichael in its title and I found an article titled "period of the power generator" by him which yielded a lower bound :). Thank you for inspiring the search! $\endgroup$
    – Sidharth Ghoshal
    Oct 11, 2019 at 21:15
  • 2
    $\begingroup$ Erdos' papers are collected at renyi.hu/~p_erdos/Erdos.html (although for some reason, the collection stops at 1989, so Erdos-Pomerance-Schmutz isn't there). The paper is available on Pomerance's website, math.dartmouth.edu/~carlp (and I think Acta Arithmetica has made most of its issues freely available on its website). But maybe you could write up what you found in the "period of the power generator" paper, and post it as an answer? $\endgroup$
    – Gerry Myerson
    Oct 11, 2019 at 21:34

1 Answer 1

Reset to default
7
$\begingroup$

An answer is given in Theorem 1 of the paper Carmichael's lambda function, by Erdos, Pomerance, and Schmutz.

Theorem $1$: For every $c < 1/\log{2}$, we have $\lambda(n) > (\log{n})^{c \log\log\log{n}}$ for all large enough $n$. On the other hand, for some constant $c'$, and infinitely many $n$, we also have $\lambda(n) < (\log{n})^{c' \log\log\log{n}}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Paper link: doi.org/10.1090/S0025-5718-00-01282-5 $\endgroup$
    – Sidharth Ghoshal
    Oct 14, 2019 at 1:25
  • $\begingroup$ I deleted my answer after noting your answer $\endgroup$
    – Sidharth Ghoshal
    Oct 14, 2019 at 1:26
  • 1
    $\begingroup$ I gave a direct link to the paper on Carl Pomerance's website in an earlier comment. $\endgroup$
    – Gerry Myerson
    Oct 14, 2019 at 4:36
  • 1
    $\begingroup$ Sorry, I should have been more careful - I should have noticed that the link in the above comment is to a different paper. Just in case something happens to the link on Carl Pomerance's website, here are also Wayback Machine and eudml link. $\endgroup$
    – Martin Sleziak
    Oct 15, 2019 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.