Given an integer $y$, how can I find the biggest $x$, such that $\lambda(x)=y$, where $\lambda(x)$ is the Carmichael-function?
$\begingroup$
$\endgroup$
10
-
2$\begingroup$ Can you even do this for $\phi(n)$, Euler's Totient Function? $\endgroup$– Eric NaslundCommented May 24, 2011 at 14:29
-
2$\begingroup$ Inverting Euler's $\phi$ is already hard: mathoverflow.net/questions/31691/inverting-the-totient-function $\endgroup$– lhfCommented May 24, 2011 at 14:33
-
2$\begingroup$ For those who aren't familiar with this function: en.wikipedia.org/wiki/Carmichael_function $\endgroup$– Matthew ConroyCommented May 24, 2011 at 18:21
-
1$\begingroup$ Technically speaking, I suppose there is no inverse... $\endgroup$– AryabhataCommented May 24, 2011 at 19:22
-
$\begingroup$ It's not even clear whether $\lambda$ is surjective; it's known that $\phi$ isn't surjective: for instance, 14 is not a value taken by $\phi$. $\endgroup$– lhfCommented May 24, 2011 at 22:09
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
7
The wiki article on the Carmichael function gives a bound that can be simplified to the statement that for all $x > x_0$, $\lambda(x) > \log(x)^{\log(\log(\log(x)))}$. So to find the largest x such that $\lambda(x)=y$, or to determine that none exists, check all values of $\lambda(x)$ for $x \le x_0$ or $\log(x)^{\log(\log(\log(x)))} \le y$. The only missing piece is the value of $x_0$. Unfortunately, I don't know. Wiki cites the bound from this paper:
Paul Erdős, Carl Pomerance, Eric Schmutz (1991) Carmichael's lambda function, Acta Arithmetica, vol. 58, 363–385.
The proof doesn't state a constant, and it relies on other asymptotics of the divisor function. I'll spend some more time on this later and if I find anything I'll add it to this answer. The other paper linked in the comments may also be worth looking at.
EDIT: If we replace the ineffective upper bound on the divisor function used by Erdős et al. with the inequality $d(y) \le y$, this yields $x \le (4 y)^{3 y}$. So to find the largest x such that $\lambda(x)=y$, or to determine that none exists, check all values of $\lambda(x)$ for $x \le (4 y)^{3 y}$.
EDIT: In the comments Gerry Myerson gives a tighter effective upper bound on the divisor function which can be used to create a more efficient algorithm by taking the size of $y$ into account.
answered Jun 1, 2011 at 6:57
-
1$\begingroup$ I think that journal is freely available to all on the Amer Math Soc website (and, if not, all three authors are friendly and outgoing folks who wuld be happy to share their work with interested parties). $\endgroup$ Commented Jun 1, 2011 at 7:06
-
$\begingroup$ Thanks Gerry. Here is the link: ams.org/journals/mcom/2001-70-236/S0025-5718-00-01282-5/… $\endgroup$ Commented Jun 1, 2011 at 7:17
-
$\begingroup$ I'm having no luck chasing down an explicit version of the upper bound on the divisor function used by Erdős et al. to prove the stated lower bound on the Carmichael function. I guess it should still be possible to show the existence of this algorithm by weakening the lower bound to something like log(x) or even log(log(x)). $\endgroup$ Commented Jun 2, 2011 at 3:00
-
1$\begingroup$ @Dan, I don't know what you mean by "the conditional upper bound on the divisor function used by Erdos et al." It appears to me that the bound is unconditional. Perhaps what you mean is more like "ineffective", due to the o$(1)$ term. Hardy and Wright have (18.1.3) $d(n)\le n^{\delta}\exp(2^{1/\delta}/(\delta\log2))$ for all positive $\delta$. Does that help? $\endgroup$ Commented Jun 3, 2011 at 5:08
-
1$\begingroup$ @Dan, "conditional" means "depending on some unproved hypothesis or another." In analytic number theory, it usually means "depending on the Riemann Hypothesis." $\endgroup$ Commented Jun 3, 2011 at 6:12