Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For any positive integer $n$, we define $$\sigma(n) := \sum_{d \mid n} d,$$ and $$\delta(n) := \frac{\sigma(n)}{n} = \sum_{d \mid n} \frac{1}{d}.$$ Is there an (efficient) way to determine $\delta^{-1}$? In particular,

If $q \in \mathbb{Q}$ is given, can we determine whether $q \in \operatorname{im}(\delta)$?

And more precisely,

If $q \in \mathbb{Q}$ is given, can we find all positive integers $n$ such that $\delta(n) = q$? Is the set $\{ n \in \mathbb{N} \mid \delta(n) = q \}$ bounded? Can we at least find interesting restrictions on the possible values for $n$ with $\delta(n)=q$?

Of course, one obvious restriction is the fact that if $q = a/b$ with $\gcd(a,b)=1$, then any $n$ with $\delta(n)=q$ has to be a multiple of $b$.

share|improve this question
11  
The case of the value 2 being perfect numbers, the question seems over-ambitious. –  Charles Matthews Feb 23 '11 at 10:02
    
@Charles : the question of finding all $n$ such that $\delta(n)=q$ seems indeed very difficult, but at least one can try to prove some qualitative results on $\delta$. For example, is there an integer $N$ such that $\{n \in \mathbb{N} | \delta(n) \in \frac{1}{N} \mathbb{Z}\}$ is infinite ? –  François Brunault Feb 23 '11 at 10:11
    
@Charles: good point; this part of the question is indeed too ambitious. –  Tom De Medts Feb 23 '11 at 10:18
4  
We have $\frac{\sigma(n)}{n} \geq \prod_p (1+\frac{1}{p})$ where $p$ runs over the prime factors of $n$. In particular if $n$ is divisible by $6$ then $\sigma(n)/n \geq 2$ ($n$ is abundant). This shows that some values like $\frac{7}{6}$ or $\frac{11}{6}$ are never attained. –  François Brunault Feb 23 '11 at 10:21
5  
@Francois: Something more general is true indeed; namely if $m \mid n$, then $\delta(n) \geq \delta(m)$. Your observation is the case $m=6$. –  Tom De Medts Feb 23 '11 at 10:42
add comment

2 Answers

up vote 13 down vote accepted

For the first question, note that the set $\Delta=\operatorname{im} (\delta)$ is not known very well understood. For example $5/3\in \Delta$ implies the existence of an odd perfect number. (C.W. Anderson showed that $\frac{\sigma(n)}{n}=\frac{5}{3}$ implies $5n$ is an odd perfect number.) It is also conjectured that $\Delta$ is recursive

A main reference is Carl Pomerance's "Multiply perfect numbers, Mersenne primes, and effective computability", where you can see Baker's method applied to such problems and references to other work. The second question is hard for most rationals $q > 1$. It is not known if $\delta^{-1}(q)$ is infinite for any $q$. On the other hand, Hornfeck and Wirsing have shown that the number of solutions to $\frac{\sigma(n)}{n}=q$ with $n\le x$ is $o(x^{\epsilon})$ for any $\epsilon > 0$ uniformly for all $q$.

Another interesting theorem in this topic is Kanold's result that if there are infinitely many elements in $\delta^{-1}(q)$ which have a constant number of prime factors then there are infinitely many Mersenne primes. There also were some Monthly problems where one proves that there is a dense set of $q$ with $\delta^{-1}(q)=\emptyset$ and a dense set of $q$ with $|\delta^{-1}(q)|=1$.

share|improve this answer
    
Pomerance's website math.dartmouth.edu/~carlp contains a direct link to this paper and 175 (!) others. –  SJR Feb 23 '11 at 13:43
    
Thanks a lot! Are there more recent developments since Pomerance's paper (which is from 1977)? Do you know of any kind of efficient algorithms to try to compute, for example, the smallest element in $\delta^{-1}(q)$ for given $q$ (up to some given upper bound)? –  Tom De Medts Feb 23 '11 at 15:51
    
@Tom : A natural idea to compute integers $n$ such that $\delta(n)=q$ is to find (recursively) conditions on the decomposition of $n$ into prime factors (this is just an extension of the last remark in your question). I think such a procedure is very familiar to people searching for perfect and multiperfect numbers (which I'm not, so there may be improvements on this idea). –  François Brunault Feb 23 '11 at 18:22
    
@Francois: What I'm doing at the moment is a combination of recursively writing $n = bc$ with $b,c$ coprime (maybe the coprimeness is too restrictive, but it makes the computation easier), together with a fast lookup-table containing the values for $\delta(n)$ for $n$ going from $1$ to $10^7$. But I find this somehow rather down-to-the-earth, and I was wondering whether there exist more advanced methods instead. –  Tom De Medts Feb 23 '11 at 20:31
    
By the way, the "$b$" in my previous comment is really the "$b$" from the comment below my question, so $q=a/b$ with $a,b$ coprime. So only looking at $n=bc$ with $b,c$ coprime really is a restriction. –  Tom De Medts Feb 24 '11 at 8:42
show 2 more comments

I got a PARI/GP script that does this. For instance, for 7/2 (05:45) gp > solveBA(7, 2, 10^10) %1 = [4680, 26208, 4320, 197064960, 20427264, 57575890944, 21857648640]

share|improve this answer
add comment

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.