Re: numbers n with large sum of divisors compared to n

In article <h01bj60tkh@xxxxxxxxxxxxxxxxx>,
David Bernier <david250@xxxxxxxxxxxx> wrote:
David Bernier wrote:
The number-theoretical function sigma(n) is defined as
sigma(n) := sum_{ d | n} d .

For example, sigma(6) = 1+2+3+6 = 12.

The ratio sigma(n)/n can grow with n, but not very
fast if the Riemann Hypothesis is true.

According to Wikipedia,
http://en.wikipedia.org/wiki/Riemann_hypothesis#Consequences_of_the_Riemann_hypothesis


In 1984, Guy Robin published a paper:
"Grandes valeurs de la fonction somme des diviseurs et hypoth?se de
Riemann"

Cf.:
http://en.wikipedia.org/wiki/Robin%27s_theorem#CITEREFRobin1984
(also has Lagarias' criterion).

Robin showed that the statement
"sigma(n) < exp(gamma) n log(log(n)) for all n >= 5041"
is equivalent to RH.
[ Ramanujan had proved RH ==>
sigma(n) < exp(gamma) n log(log(n)) for all sufficiently large n ].


To get an idea of what kinds of numbers have large sigma(n) relative
to n, I wrote a computer program to show the integers n >=5041
for which sigma(n)/( n log(log(n)) ) > 1.71 .
We have exp(gamma) = exp(0.577...) ~= 1.7810724179901979 .

This is what I have so far:
==============================

n = 7560, sigma(n) = 28800, ratio = 1.7399165192
n = 10080, sigma(n) = 39312, ratio = 1.7558143389
n = 15120, sigma(n) = 59520, ratio = 1.7385586743
n = 20160, sigma(n) = 79248, ratio = 1.7138106151
n = 25200, sigma(n) = 99944, ratio = 1.7124820364
n = 27720, sigma(n) = 112320, ratio = 1.7425367238
n = 30240, sigma(n) = 120960, ratio = 1.7139536874
n = 55440, sigma(n) = 232128, ratio = 1.7512465149
n = 65520, sigma(n) = 270816, ratio = 1.7178890011
n = 83160, sigma(n) = 345600, ratio = 1.7121096531
n = 110880, sigma(n) = 471744, ratio = 1.7348490103
n = 166320, sigma(n) = 714240, ratio = 1.7269287425
n = 277200, sigma(n) = 1199328, ratio = 1.7112437558
n = 332640, sigma(n) = 1451520, ratio = 1.7160969754
n = 360360, sigma(n) = 1572480, ratio = 1.7118721101
n = 720720, sigma(n) = 3249792, ratio = 1.7330653562
n = 1441440, sigma(n) = 6604416, ratio = 1.7277402116
n = 2162160, sigma(n) = 9999360, ratio = 1.7255702285
n = 2882880, sigma(n) = 13313664, ratio = 1.7106690213
n = 3603600, sigma(n) = 16790592, ratio = 1.7164672141
n = 4324320, sigma(n) = 20321280, ratio = 1.7235466599
n = 7207200, sigma(n) = 34122816, ratio = 1.7157791493
n = 10810800, sigma(n) = 51663360, ratio = 1.7160732878
n = 21621600, sigma(n) = 104993280, ratio = 1.7178999371
n = 24504480, sigma(n) = 118879488, ratio = 1.7117986886
n = 36756720, sigma(n) = 179988480, ratio = 1.7135828536
==============================

where ratio(n) := sigma(n)/( n log(log(n)) ) .


24504480 = 2^5 * 3^2 * 5 * 7 * 11 * 13 * 17 .

Looking at n = 360360, 720720 and 1441440 with largest
ratio of 1.73306 for the number 720720 suggests
there's an optimal allocation of '2' factors ...


I believe sigma is a multiplicative function.

With n = 288807105787200 ( = 64*27*25*7*11*13*17*19*23*29*31 )

I get sigma(n) = 1755535638528000 ( = 127*40*31*8*12*14*18*20*24*30*32 )

So Log( sigma(n)/n) =

log(127/64) + log(40/27) + log(31/25) + log(8/7) + log(12/11)
+ log(14/13) + log(18/17) + log(20/19) + log(24/23) + log(30/29)
+ log(32/31)

~ = 1.8047702852299

so sigma(n)/(n log(log(n)) ) ~= 1.734030266168 ,
and exp(gamma) ~= 1.781 .

David Bernier


Gr?nwall's theorem says that
lim sup_{ n -> oo} sigma(n)/( n log(log(n)) ) = exp(gamma).

Robin showed Robin's inequality ==> RH.

I wonder if it's known what kind of anomaly in the distribution
of the primes would allow a violation of Robin's inequality
(apart from what was clear from RH and what it says about
pi(x) - li(x) ) ...

sigma(n) is multiplicative, so therefore is sigma(n)/n. Furthermore,
for any prime p,

sigma(p^k) p^{k+1}-1
---------- = --------- [1]
p^k p^k(p-1)

Thus,

sigma(p) p+1
-------- = --- [2]
p p

and

sigma(p^k) p
lim ---------- = --- [3]
k->oo p^k p-1

In any case, for k > 0,

p+1 sigma(p^k) p
--- <= ---------- < --- [4]
p p^k p-1

Therefore, knowing only the prime factors, but not their exponents
(except that each exponent is at least 1), we can estimate

sigma(n) --- p+1
-------- ~ | | sqrt( --- ) [5]
n p|n p-1

and this estimate is accurate to within a factor of

--- p^2
| | sqrt( ----- ) [6]
p|n p^2-1

Since the product over all primes

--- p^2
| | ----- = pi^2/6 [7]
p p^2-1

the estimate [5] is accurate to within a factor of pi/sqrt(6).

This means that by adjusting the exponents of the prime factors of n,
we can only affect the value of sigma(n)/n by at most a factor of
pi^2/6.

However, there can still be something gained by adjusting the
exponents since log(log(n)) also varies very slowly with n.

---
log(n) = > log(p^k) [8]
---

The change in log(n) is thus

---
d log(n) = > log(p) dk [9]
---

Using [1] and the multiplicativity of sigma(n)/n, we also have

sigma(n) --- p-p^{-k}
log -------- = > log -------- [10]
n --- p-1

The change in this is

sigma(n) --- log(p)
d log -------- = > ----------- dk [11]
n --- p^{k+1} - 1

The standard way to find, for a given set of primes, the exponents
that maximize [10] whlle holding [8] constant, is to have the vector
of coefficients of dk in [11] be a multiple of the vector of
coefficients of dk in [9]. In this case, that means setting k so
that 1/(p^{k+1} - 1) is a constant p^{k+1} is a constant for all
primes in our given set. Of course, this cannot be done exactly when
the exponents are integers, but it gives a target.

For example, let's try a factor of 4 and compute the exponents as
k = 4/log(p) - 1 (rounded to the nearest integer):

p k
2 5
3 3
5 1
7 1
11 1
13 1

n = 4324320
sigma(n) = 20321280
sigma(n)/(n log(log(n))) = 1.72354665986337

This is one of the numbers in the table above.

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages

  • Re: numbers n with large sum of divisors compared to n
    ... The ratio sigma/n can grow with n, ... Since the product over all primes ... This means that by adjusting the exponents of the prime factors of n, ... Using and the multiplicativity of sigma/n, ...
    (sci.math)
  • Re: Proof Attempt For Fermats Last Theorem
    ... takes time to learn from your mistakes and finally suceed. ... primefactors and the possible exponents. ... numbers, squarefreeness of Mersenne numbers, Sophie Germain-primes, ... then the problem of the difficult properties of Wieferich primes, ...
    (sci.math)
  • Re: Hardness of DDH with short exponents
    ... guarantee privacy in their "Direct Anonymous Attestation" protocol. ... They use non-shifted but shortened exponents (split into two parts, ... Sounds equivalent if the group order |G| is known and odd. ... of safe primes is less efficient it does not really matter here, ...
    (sci.crypt)
  • Re: Factoraization of n! as power of primes
    ... I thought the original poster wanted to obtain BOTH the list of primes ... and their exponents. ... factorization of n! ... super-linear in n (and fancier sieve methods exist that are mildly ...
    (sci.math)