7
$\begingroup$

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$.

Improve this question
$\endgroup$
5
  • 12
    $\begingroup$ The case of the value 2 being perfect numbers, the question seems over-ambitious. $\endgroup$
    – Charles Matthews
    Commented Feb 23, 2011 at 10:02
  • $\begingroup$ @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 ? $\endgroup$
    – François Brunault
    Commented Feb 23, 2011 at 10:11
  • $\begingroup$ @Charles: good point; this part of the question is indeed too ambitious. $\endgroup$
    – Tom De Medts
    Commented Feb 23, 2011 at 10:18
  • 4
    $\begingroup$ 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. $\endgroup$
    – François Brunault
    Commented Feb 23, 2011 at 10:21
  • 6
    $\begingroup$ @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$. $\endgroup$
    – Tom De Medts
    Commented Feb 23, 2011 at 10:42

2 Answers 2

Reset to default
14
$\begingroup$

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$.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Pomerance's website math.dartmouth.edu/~carlp contains a direct link to this paper and 175 (!) others. $\endgroup$
    – Sidney Raffer
    Commented Feb 23, 2011 at 13:43
  • $\begingroup$ 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)? $\endgroup$
    – Tom De Medts
    Commented Feb 23, 2011 at 15:51
  • $\begingroup$ @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). $\endgroup$
    – François Brunault
    Commented Feb 23, 2011 at 18:22
  • $\begingroup$ @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. $\endgroup$
    – Tom De Medts
    Commented Feb 23, 2011 at 20:31
  • $\begingroup$ 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. $\endgroup$
    – Tom De Medts
    Commented Feb 24, 2011 at 8:42
1
$\begingroup$

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]

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .