Given an integer $y$, how can I find the biggest $x$, such that $\lambda(x)=y$, where $\lambda(x)$ is the Carmichael-function?
What is the inverse of the Carmichael-function?
-
2Can you even do this for $\phi(n)$, Euler's Totient Function? – 2011-05-24
-
2Inverting Euler's $\phi$ is already hard: http://mathoverflow.net/questions/31691/inverting-the-totient-function – 2011-05-24
-
2For those who aren't familiar with this function: http://en.wikipedia.org/wiki/Carmichael_function – 2011-05-24
-
1Technically speaking, I suppose there is no inverse... – 2011-05-24
-
0It'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$. – 2011-05-24
-
0@lhf: If I am not mistaken, it's pretty clear that $\lambda$ is *not* surjective: it is the exponent of a group which is -- for all $n > 2$ -- of even order, so like $\varphi$ it cannot take on any odd value greater than $1$. – 2011-06-03
-
0lhf and all, I cross-posted a link to my answer to that MO thread: http://mathoverflow.net/questions/31691/inverting-the-totient-function/66791#66791 – 2011-06-03
-
0@Pete, right. I meant whether $\lambda$ takes all even values. – 2011-06-03
-
0@lhf: okay. Probably it doesn't take all even values either, but (as with $\varphi$) it would require some work to find a particular unattained value. – 2011-06-03
-
0@Pete, I've posted a question about this issue. – 2011-06-03
1 Answers
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.
-
1I 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). – 2011-06-01
-
0Thanks Gerry. Here is the link: http://www.ams.org/journals/mcom/2001-70-236/S0025-5718-00-01282-5/S0025-5718-00-01282-5.pdf – 2011-06-01
-
0I'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)). – 2011-06-02
-
1@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? – 2011-06-03
-
0Gerry, I see that helps for large n if we use a small positive δ < 1. You may also be right about the terminology (I realize I need to review Landau notation to know for sure) and "ineffective" also captures my intended meaning. – 2011-06-03
-
1@Dan, "conditional" means "depending on some unproved hypothesis or another." In analytic number theory, it usually means "depending on the Riemann Hypothesis." – 2011-06-03
-
0What I meant is "depending on an inequality with an unknown constant" which I think is the same as "ineffective" and the meaning of the o(1) term. I'll try to fix the ambiguity. – 2011-06-03