mersenneforum.org > Math General Solution to Polynomial Equations
 Register FAQ Search Today's Posts Mark Forums Read

 2004-09-10, 14:18 #1 jfollas   Jul 2004 168 Posts General Solution to Polynomial Equations What are the implications for factoring/primality testing (if any) of the newly announced general solution to polynomial equations? This piqued my interest because I remembered something about FFT being based on representing numbers as polynomial equations (sorry if I'm incorrect). http://arxiv.org/ftp/math/papers/0408/0408264.pdf
2004-09-10, 19:15   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by jfollas What are the implications for factoring/primality testing (if any) of the newly announced general solution to polynomial equations? This piqued my interest because I remembered something about FFT being based on representing numbers as polynomial equations (sorry if I'm incorrect). http://arxiv.org/ftp/math/papers/0408/0408264.pdf
(1) The so-called "new" solution to polynomial equations is at least 100
years old. It is a lot of media ignorance and hype. Methods have been around
since the time of Hermite (or earlier). Since polynomials are 1-1 in the close
neighborhood of any root, you can always find an infinite series representation
to the root (by the Inverse Function Thm). This so-called "new" method is
nothing more than an infinite series solution. But it has been known for a long
time that roots could be expressed in terms of Elliptic or Hypergeometric or
Theta functions.

(2) It has ZERO implications for factoring/prime testing.

I am curious as to why you think there MIGHT be a connection?

 2004-09-10, 19:27 #3 Xyzzy     "Mike" Aug 2002 22×7×281 Posts Apparently this is hitting the news big time... http://science.slashdot.org/science/.../1229221.shtml
2004-09-11, 12:51   #4
jfollas

Jul 2004

2×7 Posts

Quote:
 Originally Posted by Bob Silverman I am curious as to why you think there MIGHT be a connection?
What stuck in my mind was that when you multiply using FFT, you first represent the number as a polynomial equation:

57829 = 5x^4 + 7x^3 + 8x^2 + 2x + 9

I wasn't sure if the roots of such an equation were useful for factoring, etc, since the article made it seem like it was one of nature's unsolved mysteries (or something) to have a general equation for numerically solving polynomial equations.

 2004-09-11, 14:10 #5 jinydu     Dec 2003 Hopefully Near M48 2·3·293 Posts Hmm, I thought that the Newton-Rhapson method already provided a method for finding the roots of any polynomial numerically to arbitrarily high accuracy. Last fiddled with by jinydu on 2004-09-11 at 14:12
2004-09-13, 11:36   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by jfollas What stuck in my mind was that when you multiply using FFT, you first represent the number as a polynomial equation: 57829 = 5x^4 + 7x^3 + 8x^2 + 2x + 9 I wasn't sure if the roots of such an equation were useful for factoring, etc, since the article made it seem like it was one of nature's unsolved mysteries (or something) to have a general equation for numerically solving polynomial equations.
But all numbers have an instantiation as a polynomial (in a particular base)
What makes you think that there is something special here?

2004-09-13, 11:38   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by jinydu Hmm, I thought that the Newton-Rhapson method already provided a method for finding the roots of any polynomial numerically to arbitrarily high accuracy.

I suggest that you apply Newton's method to (say) x^3 - 3x^2 + 4.

2004-09-13, 20:49   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

289E16 Posts

Quote:
 Originally Posted by Bob Silverman Your premise is not correct. I suggest that you apply Newton's method to (say) x^3 - 3x^2 + 4.

For extra points, explain why it all goes badly wrong.

Paul

2004-09-14, 02:26   #9
jinydu

Dec 2003
Hopefully Near M48

175810 Posts

Quote:
 Originally Posted by Bob Silverman Your premise is not correct. I suggest that you apply Newton's method to (say) x^3 - 3x^2 + 4.
Ok, here goes my attempt:

Let f(x) = x^3 - 3x^2 + 4
Then f '(x) = 3x^2 - 6x

My first guess will be x = 1
f(1) = 2
f '(1) = -3
Next guess = 1 - (2/-3) = 5/3 ~= 1.6666666666666666666

Second guess is x = 5/3
f(5/3) = 8/27
f '(5/3) = -5/3
Next guess = (5/3) - ([8/27]/[-5/3]) = 83/45 ~= 1.8444444444444444

The next two iterations give:

21563/11205 ~= 1.92440875
1422643403/724840245 ~= 1.96269925

The method seems to be working, or did I just get lucky with my starting guess?

2004-09-14, 13:00   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by jinydu Ok, here goes my attempt: Let f(x) = x^3 - 3x^2 + 4 Then f '(x) = 3x^2 - 6x My first guess will be x = 1 f(1) = 2 f '(1) = -3 Next guess = 1 - (2/-3) = 5/3 ~= 1.6666666666666666666 Second guess is x = 5/3 f(5/3) = 8/27 f '(5/3) = -5/3 Next guess = (5/3) - ([8/27]/[-5/3]) = 83/45 ~= 1.8444444444444444 The next two iterations give: 21563/11205 ~= 1.92440875 1422643403/724840245 ~= 1.96269925 The method seems to be working, or did I just get lucky with my starting guess?
May I suggest that you continue..... You will find that convergence
gets slower and slower and slower and.......

I did not choose it randomly....

2004-09-14, 14:27   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×1,733 Posts

Quote:
 Originally Posted by Bob Silverman May I suggest that you continue..... You will find that convergence gets slower and slower and slower and....... Ask yourself: what is special about the polynomial I gave? I did not choose it randomly....
To be fair, he did say "to arbitrarily high accuracy". He didn't say it would do so rapidly. Neither did he say that he'd use floating point arithmetic with precision so low that he'd run into rounding errors.

That's why I put a smiley after quoting your example, and why I asked him to explain why it all goes terribly wrong.

I'm well aware, of course, why you chose that particular polynomial.

Paul

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 21 2019-08-19 14:59 carpetpool Miscellaneous Math 14 2017-02-18 19:46 Joshua2 Homework Help 9 2009-10-30 07:37 mfgoode Math 1 2006-10-09 16:02 dsouza123 Math 2 2004-07-30 09:03

All times are UTC. The time now is 09:08.

Fri Dec 4 09:08:39 UTC 2020 up 1 day, 5:19, 0 users, load averages: 1.81, 1.46, 1.46