4 ms·

If (efficiently) searching for a disproof requires fast (prime) factorization, are there connections to other open problems?

FartyMcFarter 7y ago
I think you could just generate candidate counter-examples by multiplying factors, rather than the other way around.
- macawfish 7y ago
  Yes! I was just in the middle of doing this in a sage notebook! Good thinking :) I have to think some mathematician had already done this for like every pattern they could think of but ya never know. Never hurts to try... As long as you don't delude yourself that is. update: Okay so the tricky thing here is that in order to naively generate the divisors (and sum over them), you'd have to consider butt-tons of combinations of prime factors, including many, many, many repeated ones. So finding divisors given a list of factors scales very rapidly. It's really fun to take shots at these hard problems. It's like any way you attack them they're hard, even when you don't intuitively expect it.
lmm 7y ago
Oh yes. The Riemann Hypothesis is connected to just about everything; lots of statements have been shown to either follow from it or be equivalent to it.
etatoby 7y ago
Yes. In fact, if we ever manage to build a quantum computer with a non-trivial amount of qubits, we can expect exponential improvement in the performance of any prime number-related numerical research.
ColinWright 7y ago
In this case efficiently searching for an example n does not require fast factorization. We are search for a number n such that σ(n)/(n ln(ln (n))) is large. That mean we want σ(n) large, and that means n will have to have lots and lots of small factors. So your comment is relevant, but in this case, it doesn't provide new insight.
- 7373737373 7y ago
  I just checked how one could implement the search, finding all the divisors for σ(n) can be done with a prime factoring algorithm and then calculating the number of their combinations. But that's just one way.
  - ColinWright 7y ago
    You can make that more efficient by noting that you need σ(n) to be large, so if you know that, for example, the smallest factor of n is more than ln(n)^4 then you already know this won't be a counter-example. So general purpose factoring doesn't really help in this search, even though, as you say, it's one (naive and simple) approach. It will work for small n, but it will quickly become infeasible.
    - 7373737373 7y ago
      I see it now, thanks!

FartyMcFarter 7y ago

I think you could just generate candidate counter-examples by multiplying factors, rather than the other way around.

macawfish 7y ago
Yes! I was just in the middle of doing this in a sage notebook! Good thinking :) I have to think some mathematician had already done this for like every pattern they could think of but ya never know. Never hurts to try... As long as you don't delude yourself that is. update: Okay so the tricky thing here is that in order to naively generate the divisors (and sum over them), you'd have to consider butt-tons of combinations of prime factors, including many, many, many repeated ones. So finding divisors given a list of factors scales very rapidly. It's really fun to take shots at these hard problems. It's like any way you attack them they're hard, even when you don't intuitively expect it.

lmm 7y ago

Oh yes. The Riemann Hypothesis is connected to just about everything; lots of statements have been shown to either follow from it or be equivalent to it.

etatoby 7y ago

Yes. In fact, if we ever manage to build a quantum computer with a non-trivial amount of qubits, we can expect exponential improvement in the performance of any prime number-related numerical research.

ColinWright 7y ago

In this case efficiently searching for an example n does not require fast factorization. We are search for a number n such that σ(n)/(n ln(ln (n))) is large. That mean we want σ(n) large, and that means n will have to have lots and lots of small factors. So your comment is relevant, but in this case, it doesn't provide new insight.

7373737373 7y ago
I just checked how one could implement the search, finding all the divisors for σ(n) can be done with a prime factoring algorithm and then calculating the number of their combinations. But that's just one way.
- ColinWright 7y ago
  You can make that more efficient by noting that you need σ(n) to be large, so if you know that, for example, the smallest factor of n is more than ln(n)^4 then you already know this won't be a counter-example. So general purpose factoring doesn't really help in this search, even though, as you say, it's one (naive and simple) approach. It will work for small n, but it will quickly become infeasible.
  - 7373737373 7y ago
    I see it now, thanks!