Ken Ono and Factoring?

[epsi00]

Does anyone think that factoring will be shown to be "fractal" in nature, following the work of Ken Ono. Are there patterns in composite numbers, as yet unknown, that make factoring easier?

 

[Raphie]

I personally believe the answer to be "yes." If partition numbers exhibit fractal behavior, it only makes perfect sense to suggest that the primes upon which they are based (and thus factoring in general) may also be found to exhibit fractal behavior.

As a (somewhat, perhaps...) illustrative exercise, take Pascal's triangle and set it to modulo p_(pi(row_n)), for p a prime and pi the prime counting function, meaning that every time you get to a row with an index number that is prime, then that prime number becomes the modulus. You will see quite plainly that Pascal's triangle begins to repeat itself, but gets truncated every time you get to a new prime. In principle, however, since the gap between primes can be arbitrarily wide, then somewhere in the infinity that is Pascal's triangle you will be able to find a perfect copy of Pascal's triangle to any row desired.

That might not fit the pure definition of fractal, but it would seem to come close in the same way that Pascal's Triangle is an approximation of the Sierpinski Triangle, which is a fractal...

via Wikipedia
THE SIERPINSKI TRIANGLE
Properties

The Sierpinski triangle has Hausdorff dimension log(3)/log(2) ≈ 1.585, which follows from the fact that it is a union of three copies of itself, each scaled by a factor of 1/2.

If one takes Pascal's triangle with 2n rows and colors the even numbers white, and the odd numbers black, the result is an approximation to the Sierpinski triangle. More precisely, the limit as n approaches infinity of this parity-colored 2n-row Pascal triangle is the Sierpinski triangle.

The area of a Sierpinski triangle is zero (in Lebesgue measure). The area remaining after each iteration is clearly 3/4 of the area from the previous iteration, and an infinite number of iterations results in zero. Intuitively one can see this applies to any geometrical construction with an infinite number of iterations, each of which decreases the size by an amount proportional to a previous iteration.

More here:
http://en.wikipedia.org/wiki/Sierpinski_triangle

Also worth checking out (the Sacks Spiral is also briefly discussed)...

The Ulam Spiral
http://en.wikipedia.org/wiki/Ulam_spiral

The line from this Wikipedia entry I find the most intriguing in relation to primes and fractals (bold added for emphasis), is this one:

Tests so far confirm that there are diagonal lines even when many numbers are plotted. The pattern also seems to appear even if the number at the center is not 1 (and can, in fact, be much larger than 1). This implies that there are many integer constants b and c such that the function:

f(n) = 4n^2 + bn + c

generates, as n counts up {1, 2, 3, ...}, a number of primes that is large by comparison with the proportion of primes among numbers of similar magnitude.

 

[Raphie]

Here is a related thread...

are prime fractals, or have a fractal geometry ??
https://www.physicsforums.com/showthread.php?t=317545

One poster, dragonfall, states that...

If I interpret your question correctly: no, they don't, because of the prime number theorem.

If anyone would care to expand on that statement, please do feel free, because I can't say as how I see the prime number theorem ruling out an aperiodic fractal distribution of the primes.

- RF

 

[Goongyae]

There is a very interesting recursive property that can be used to deduce if a number is prime or not.

Check out this stuff from Euler: http://www.math.dartmouth.edu/~euler/
English translation: http://lambentresearch.com/euler/e175.pdf

The basic idea is, let d(n) be the sum of the divisors of n. For example d(6)=1+2+3+6=12. If d(n) = n+1, then n must be prime.

The amazing thing is d(n) can be computed recursively:
d(n) = d(n-1)+d(n-2)-d(n-5)-d(n-7)+d(n-12)+d(n-15)-...
except if you get d(0) on the right hand-side, you must put in the number n itself.

For example:
d(5) = d(4)+d(3)-5 = 7 + 4 - 5 = 6, which means 5 must be prime

Note: there are variations involving a few powers of Euler's phi function mulitplied or divided, such as the function 1+x+x^3+x^6+x^10+x^15+..., that lead to similar recursive properties.

 

[Raphie]

The amazing thing is d(n) can be computed recursively:
d(n) = d(n-1)+d(n-2)-d(n-5)-d(n-7)+d(n-12)+d(n-15)-...
except if you get d(0) on the right hand-side, you must put in the number n itself.

Those numbers up above there are all generalized Pentagonal numbers, so I'm wondering how the identity you posted relates to Euler's Pentagonal number theorem:

p(n-0)-p(n-1)-p(n-2)+p(n-5)+p(n-7)-p(n-12)-p(n-15)++-- =0^n
where p(n) is the partition function
http://oeis.org/A001318

Multiply any generalized Pentagonal number by 3, by the way, and you get triangular numbers of the form T_(3n + 2) and T_(3n+3) e.g. 3, 6, 15, 21, 36, 45. Multiply by 24 and add 1, and you get square numbers, including a nice little straight run of prime squares from 5 --> 23, not surprising since all of those square numbers take the form (6n + 1)^2 or (6n - 1)^2...

24*0 + 1 = 1^2
---------------------
24* 1 + 1 = 5^2
24* 2 + 1 = 7^2
24* 5 + 1 = 11^2
24* 7 + 1 = 13^2
24*12 + 1 = 17^2
24*15 + 1 = 19^2
24*22 + 1 = 23^2
---------------------
24*26 + 1 = 25^2

In other words, all primes greater than 3 are constructible in the following manner: sqrt (24*(Generalized Pentagonal Number_n) + 1), a fact which might naturally lead one to ask: Is this in some manner related to the Dedekind eta function? Conversely, working backwards, then (p^2 - 1)/24 for p > 3, will always be a Generalized Pentagonal Number

Also, via summation, the Pentagonal Numbers can be quite simply related to both Cubes and Squares. e.g. 4^3 - 40 = 24, for 40 = 1 + 5 + 12 + 22 and 24 = 0 + 2 + 7 + 15. The difference between 24 and 40 = 4^2.

UPDATE: via Wolfram Mathworld
Letting x_i be the set of numbers relatively prime to 6, the generalized pentagonal numbers are given by (x_i^2-1)/24. Also, letting y_i be the subset of the x_i for which x_i=5 (mod 6), the usual pentagonal numbers are given by (y_i^2-1)/24 (D. Terr, pers. comm., May 20, 2004).
http://mathworld.wolfram.com/PentagonalNumber.html

 

[Raphie]

In other words, all primes greater than 3 are constructible in the following manner: sqrt (24*(Generalized Pentagonal Number_n) + 1), a fact which might naturally lead one to ask: Is this in some manner related to the Dedekind eta function? Conversely, working backwards, then (p^2 - 1)/24 for p > 3, will always be a Generalized Pentagonal Number

Well this is rather interesting and more than a bit related to the topic of this thread...

via Wikipedia

Pentagonal number theorem
http://en.wikipedia.org/wiki/Pentagonal_number_theorem
SEE ALSO

The pentagonal number theorem occurs as a special case of the Jacobi triple product. http://en.wikipedia.org/wiki/Jacobi_triple_product

Q-series http://en.wikipedia.org/wiki/Q-series generalizes Euler's function, which is closely related to the Dedekind eta function, and occurs in the study of modular forms. The modulus of the Euler function (see Q-series for picture) shows the fractal modular group symmetry and occurs in the study of the interior of the Mandelbrot set.

There is a very interesting recursive property that can be used to deduce if a number is prime or not.
Check out this stuff from Euler: http://www.math.dartmouth.edu/~euler/
English translation: http://lambentresearch.com/euler/e175.pdf

That paper you linked to (second link above) is great stuff, Goongyae. Thanks for posting it.

 

[Goongyae]

>Those numbers up above there are all generalized Pentagonal numbers, so I'm wondering how the identity you posted relates to Euler's Pentagonal number theorem

It's derived in Eulers paper (French: http://math.dartmouth.edu/~euler/docs/originals/E175.pdf English: http://lambentresearch.com/euler/e175.pdf). The expansion of (1-x)(1-x^2)(1-x^3)... leads to the generalized pentagonal numbers and the recursive property of the divisor function.

>all primes greater than 3 are constructible in the following manner: sqrt (24*(Generalized Pentagonal Number_n) + 1)

Well, a generalized pentagonal number G can be written as n(3n-1)/2.
And 24G+1 = 12n(3n-1)+1 = 36nn-6n+1 = (6n-1)^2
So what you are saying is that a prime bigger than 3 is either 5 mod 6 (achieved by letting n > 0) or it's 1 mod 6 (achieved by letting n <= 0). Which is true because it can't be 0,2, or 4 mod 6 (then it would be divisible by 2) or 3 mod 6 (then it would be divisible by 3).

>That paper you linked to (second link above) is great stuff, Goongyae. Thanks for posting it.

No problem, I learned more reading Euler than reading anyone else. Euler is the bees' knees :)