Teorth: New page: One approach to finding non-smooth numbers (which, assuming a factoring oracle, would lead to progress on the finding primes problem) is as follows. Suppose we wish to s...

2009-08-12T17:43:02Z

New page: One approach to finding non-smooth numbers (which, assuming a factoring oracle, would lead to progress on the finding primes problem) is as follows. Suppose we wish to s...

New page

One approach to finding non-smooth numbers (which, assuming a [[factoring|factoring oracle]], would lead to progress on the [[finding primes]] problem) is as follows.

Suppose we wish to show that at least one integer in <math>[n,n+\log n]</math> contains a prime factor larger than, say, <math>\log^{100} n</math> (thus breaking the square root barrier). We suppose this is not the case and obtain a contradiction.

It is then plausible that most integers in this interval contain about <math>\log^{1-o(1)} n</math> or so factors between, say, <math>\log^{10} n</math> and <math>\log^{100} n</math>. (Using the [[W-trick]], one can probably eliminate primes much less than log n from consideration.) In particular, we get a set <math>p_1,\ldots,p_k</math> of about <math>\log^{2-o(1)} n</math> primes in <math>[\log^{10} n, \log^{100} n]</math> which each divide an integer in <math>[n,n+\log n]</math>, which implies in particular that the n/p_i lies within <math>O(1/\log^9 n)</math> of an integer. This implies that all of the 3^k signed sums

: <math> \epsilon_1 n / p_1 + \ldots + \epsilon_k n / p_k</math>

with <math>\epsilon_i = -1,0,1</math> lie within <math>O( 1 / \log^{7-o(1)} n )</math> of an integer. Hopefully this sort of concentration leads to some sort of contradiction. For instance, it implies that <math>\epsilon_1/p_1 + \ldots + \epsilon_k/p_k</math> cannot be used to approximate too many reciprocals 1/q too closely.

Signed sums of prime reciprocals - Revision history

Teorth: New page: One approach to finding non-smooth numbers (which, assuming a factoring oracle, would lead to progress on the finding primes problem) is as follows. Suppose we wish to s...