Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an integer $y$, how can I find the biggest $x$, such that $\lambda(x)=y$, where $\lambda(x)$ is the Carmichael-function?

share|improve this question
2  
Can you even do this for $\phi(n)$, Euler's Totient Function? –  Eric Naslund May 24 '11 at 14:29
2  
Inverting Euler's $\phi$ is already hard: mathoverflow.net/questions/31691/inverting-the-totient-function –  lhf May 24 '11 at 14:33
2  
For those who aren't familiar with this function: en.wikipedia.org/wiki/Carmichael_function –  Matthew Conroy May 24 '11 at 18:21
1  
Technically speaking, I suppose there is no inverse... –  Aryabhata May 24 '11 at 19:22
    
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$. –  lhf May 24 '11 at 22:09

1 Answer 1

up vote 4 down vote accepted
+50

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.

share|improve this answer
    
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). –  Gerry Myerson Jun 1 '11 at 7:06
    
Thanks Gerry. Here is the link: ams.org/journals/mcom/2001-70-236/S0025-5718-00-01282-5/… –  Dan Brumleve Jun 1 '11 at 7:17
    
Curses, I copied the wrong reference! I updated the answer with the correct citation and a link. –  Dan Brumleve Jun 1 '11 at 7:26
    
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)). –  Dan Brumleve Jun 2 '11 at 3:00
    
@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? –  Gerry Myerson Jun 3 '11 at 5:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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