Graeffe's root squaring method

[Albert Chan]

11-20-2022, 06:13 AM

Werner Wrote:I see what you mean - roots will be closer to -1 so there's no need to try out the complex roots to the right of the origin, you just took one 3/4 of the way, and it happens to produce the right answer. What if it didn't?
Werner

Guessing way is again bisect phase angle: 7/8*pi, 5/8*pi

(11-16-2022 01:28 PM)Albert Chan Wrote:  If we consider polynomial coefficients with geometric progression:

f(x) = 1 + (r*x) + (r*x)^2 + ... + (r*x)^n = ((r*x)^(n+1) - 1) / ((r*x) - 1)

From RHS numerator, all f roots abs = 1/r

P(x) = 2 + 3x + 5x^2 + 7x^3 + 11x^4 + ...

P roots, sorted in abs: (-0.6458±0.4832i), (0.4472±0.7248i), (-0.2853±0.8292i), ...
With corresponding abs: 0.8065, 0.8517, 0.8769, ...

Primes does not grow as fast as geometric progression. (sum of reciprocal primes diverges)

P min abs root is due to ratio, (5/2=2.5) > (11/5=2.2)
If the ratios were about the same, we expected f(x) roots pattern, with similar sized roots.

Example, R(x) = P(x)+0.5, 5/(2+0.5) = 2.

R roots, sorted in abs: (-0.6811±0.5122i), (0.4692±0.7114i), (-0.2905±0.8666i), ...
With corresponding abs: 0.8522, 0.8522, 0.9140, ...

If guess close enough, we can use Newton's method to zeroed in P min abs root.

More direct way is to try smaller degree polynomial, say, all primes under 100.
Roots in polar form, sorted in abs, with root that "belongs" to 2 and 2.5 bolded.
(2nd proot needed, to confirm location of root that really "belongs" to 2)

proot(2.0 + 3x + 5x^2 + ... + 97*x^24) = 0.788∠±2.50, 0.810∠±1.03, ...
proot(2.5 + 3x + 5x^2 + ... + 97*x^24) = 0.815∠±1.01, 0.818∠±2.50, ...

--> P(x) min abs root around 0.8∠±2.5