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.

Let $\mu\left(n\right)$ be the Möbius function. Let $\phi\left(n\right)$ be Euler's totient function. Let $\sigma\left(n\right)$ be the sum of divisors and $\tau\left(n\right)$ be the number of divisors functions. I am curious to know whether or not the system:

$\mu\left(n\right)=a$

$\phi\left(n\right)=b$

$\sigma\left(n\right)=c$

$\tau\left(n\right)=d$

has at most one solution.

Motivation: I remember a number theory assignment I had where we were given particular values for each of these functions and asked to recover the original number. I can't for the life of me remember how (or if) I managed to solve this problem. I tried to work out a general proof, but couldn't. I also wrote a loop in maple to check for counterexamples, but haven't found any yet. I feel like this is something I should know, but probably have forgotten the relevant facts to approaching this problem.

share|improve this question
    
For small values of a, b, c, d it's just casework on the prime factorization of n. That's probably how you did it. –  Qiaochu Yuan Nov 22 '10 at 18:52
1  
Now that we've found that the answer is "no", the next question is can we add more number-theoretic functions so that the answer becomes "yes". I believe that each pair of Alon's counterexamples have different values of big-omega(n), the number of prime factors of n counted with multiplicity. –  Unreasonable Sin Nov 22 '10 at 18:56
5  
My guess, based on no evidence whatsoever, is that it'll be hard to come up with a reasonable list of functions to make the function injective. Of course the function "n" would be really helpful here... but honest number theoretic functions admit lots of collisions. –  Alon Amit Nov 22 '10 at 19:05
    
"Number of divisors" and "product of divisors" would do it on their own. –  Oscar Cunningham Nov 22 '10 at 19:08
2  
Well, "product of prime divisors (with repetition)" will do it on its own, as well :-) I guess the super-vague claim is that the standard functions mu, phi, tau etc. won't do. –  Alon Amit Nov 22 '10 at 19:20

2 Answers 2

up vote 28 down vote accepted

The answer is No. The smallest counterexamples I could find are {1836, 1824), {5236, 4960}, {5742, 5112}, {6764, 6368}, {9180, 9120} and {9724, 9184}. I think those are all the pairs in which both numbers are less than 10,000.

For example, both $n=1836$ and $n=1824$ satisfy $\mu(n)=0$, $\varphi(n)=576$, $\sigma(n)=5040$ and $\tau(n)=24$.

EDIT: here's the code of the program I used in GAP.

vec := function(n)
 return [MoebiusMu(n), Phi(n), Sigma(n), Tau(n)];
end;

dic:=NewDictionary([1,2,3,4], true);

for i in [2..10000] do
 v:=vec(i);
 if (LookupDictionary(dic, v) <> fail) then Print(i," <=> ", LookupDictionary(dic, v), "\n"); fi;
 AddDictionary(dic, v, i);
od;
share|improve this answer
    
Out of curiosity, how did you write your search algorithm? I haven't had to program in a long time and I was trying to write one in maple. I set up a for-loop but couldn't figure out how to compare the output data without inspecting the list myself. –  WWright Nov 22 '10 at 18:35
2  
I made it super-easy for myself: I used GAP, so all the number-theoretic functions were available. In order to test for collisions, I used a hash table; GAP has built-in functions for that, too (I actually used GAP's "dictionary" concept). The complete code is like 8 lines. –  Alon Amit Nov 22 '10 at 18:42
    
Thanks for sharing the code! I might try modifying this myself to see what number theoretic properties the multiple solutions have in common. –  WWright Nov 22 '10 at 19:05

First, congratulations on asking a number theory question which is quite unlike any I have seen before. It's certainly more fun to read about questions like this rather than computing $a^b$ modulo $n$.

Regarding the assignment you got: one can certainly find particular values of $a$, $b$, $c$ and $d$ such that there is exactly one $n$ solving the equations. For instance, if $p$ is a prime number then taking $a = -1$, $b = p-1$, $c = p+1$, $d = 2$ has the unique solution $n = p$: $\tau(n) = 2$ forces $n$ to be prime and thus $\varphi(n) = n-1$.

Although I am a number theorist, I don't have an expert opinion on the general question. (I'm not really "the right kind" of number theorist to answer this question. You might ask Carl Pomerance, for instance.) I suppose the more reasonable guess is that there are values of $a,b,c,d$ which yield more than one solution.

Probably the first thing to do is what you're doing: search for counterexamples by computer. When you get tired of doing that, let us know how far you looked (and, of course, whether you've found any). The second thing to do is to come up with a heuristic on how often one might expect multiple solutions to be found...

share|improve this answer
1  
I would vote up this answer multiple times if I could. Incidentally, my opinion (as a probabilist who is amused by number-theoretic heuristics) is that examples should get rarer as the numbers involved get larger, but I won't hazard a guess off the top of my head as to whether the number of counterexamples is finite or infinite. –  Michael Lugo Nov 22 '10 at 19:20
    
Now the original question has been answered, perhaps Pete, WWright or Alon could post the natural follow up question concerning the frequency of multiple solutions as no doubt many of you are already wondering about this; I know I am. (I don't want to post it, as I wasn't involved in this question before this comment.) I expect the follow up question may not yield so readily. –  Derek Jennings Nov 22 '10 at 20:24
    
@Derek Jennings - I was hesitant to post the follow up until I'd thought about the problem on my own a bit more. I also thought it might be inappropriate to ask multiple questions on the same topic in a short period of time. If you have a precise way of writing out what it means to define the frequency of multiple solutions, I'd encourage you to post the question. I find my own background a bit to modest to formulate the question very precisely, but am certainly curious about the answer :) –  WWright Nov 22 '10 at 20:58
    
@WWright As you're ok with that, and I'm certainly curious about the answer too (although sadly I've no time to work on it at the moment), I've just posted the follow up question. –  Derek Jennings Nov 22 '10 at 22: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.