Ken Ono and Factoring?

  1. 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?
     
  2. jcsd
  3. 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.
     
    Last edited: Feb 14, 2011
  4. 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 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
     
  5. 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.
     
  6. 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
     
    Last edited: Feb 24, 2011
  7. 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.


    That paper you linked to (second link above) is great stuff, Goongyae. Thanks for posting it.
     
    Last edited: Feb 24, 2011
  8. >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 :)
     
    Last edited: Feb 25, 2011
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?