a thoughtful web.
Good ideas and conversation. No ads, no tracking.   Login or Take a Tour!
comment by tvirlip
tvirlip  ·  3172 days ago  ·  link  ·    ·  parent  ·  post: Roots, Roots!

But you really want to get the original one and zoom in... There are places of beauty which are not that visible in the scaled down version.





wasoxygen  ·  3172 days ago  ·  link  ·  

That's really something. I didn't know what to expect, but it wasn't that.

Can you talk us through this, in Fisher-Price math? Let me see how far I can get on my own.

A complex number, like 2 + 3i, has a real (2) and imaginary (3i) part. The real part is simple enough, and we can pretend the i in the imaginary part is just another variable like x, except that when two i's get multiplied together they change into a -1.

You wrote a program to solve an equation, actually a lot of equations. Let's start with one equation. A simple polynomial might have the form ax² + bx + c = something, you didn't say what but I'll guess it's zero.

You restricted the coefficients, a, b, and c to the values 1 and -1. Each of the three coefficients can take two values, so we should get 2 × 2 × 2 = 8 equations.

   1x² + 1x + 1 = 0

1x² + 1x - 1 = 0

1x² - 1x + 1 = 0

1x² - 1x - 1 = 0

-1x² + 1x + 1 = 0

-1x² + 1x - 1 = 0

-1x² - 1x + 1 = 0

-1x² - 1x - 1 = 0

To find solutions, we ask what values x can take that give true equations. Considering real numbers first, we might be lazy and plot all eight equations on a graph and see where they cross the x-axis.

We find four values of x that work, each time yielding zero in two different polynomials. The highest is near x = 1.618, where the fourth and fifth polynomials both equal zero. In other words,

  1x² - 1x - 1 = -1x² + 1x + 1

so

  2x² - 2x - 2 =  0

or

  x² - x - 1 =  0

Now we turn to the quadratic formula to solve for x:

  x = (-b ± √(b² - 4ac)) / 2a 

= (1 ± √(1 - 4(1)(-1)))/2

= (1 ± √5)/2

which, in agreement with the graph, is about -0.618 and 1.618, the latter of which is phi, the golden ratio. I thought that number looked familiar.

So we could plot these values on a number line, but it would be two boring dots.

So let's consider complex numbers. Now x can have two parts, one a real number like before and the other imaginary. For the first equation, 1x² + 1x + 1 = 0, we need the imaginary part or it's hopeless, because the sum is always positive if x is real. If x is complex, the equation takes the form 1(a + b)² + (a + b) + 1 = 0, and when we solve it we will change any b² to a -1 and hopefully the b coefficient will be zero at the end because we're trying to get to zero and there's no i in zero.

So

  a² + 2ab + b² + a + b + 1 = 0

a² + 2ab - 1 + a + b + 1 = 0

a² + 2ab + a + b = 0

a² + a + 2ab + b = 0

a² + a + b(2a + 1) = 0

Maybe now we just assume b is zero so that part drops out, and

  a² + a = 0

a(a + 1) = 0

and a = 0 or -1. But those don't satisfy the first equation, so maybe it was a bad assumption and this equation has no complex roots.

How about the second one, 1x² + 1x - 1 = 0. It has two real roots, near x = -1.618 and x = 0.618. If x is complex, it takes the form

  1(a + b)² + 1(a + b) - 1 = 0

a² + ab + b² + a + b - 1 = 0

a² + ab - 1 + a + b - 1 = 0

a² + ab + a + b - 2 = 0

a² + a + ab + b - 2 = 0

a² + a + b(a + 1) - 2 = 0

b(a + 1) = 2 - a² - a

b = (2 - a² - a) / (a + 1)

and cheating again with the graphing tool I find that when a = -2 or 1 the b equals zero.

So that gives me x = (-2 + 0i) and x = (1 + 0i), but these are both real. Is my Fisher-Price arithmetic off, or did I get off track by assuming you would set the polynomials to zero, or perhaps do things only get interesting in the higher degree polynomials?

tvirlip  ·  3172 days ago  ·  link  ·  

Side comment first: yes, root of the polynomial is something that makes it to be equal to zero, so there is 0 in the right side of every equation.

Square equations

You're completely right up to the point where you're trying to find complex roots of a square equation. It is done using exactly the same way as for real roots:

  x = (-b ± √(b² - 4ac)) / 2a 

So if your equation is 1x² + 1x + 1 = 0, then a=1, b=1, c=1 and roots are

  (-b ± √(b² - 4ac)) / 2a = (-1 ± √(1 - 4)) / 2 = (-1 ± √(-3)) / 2

Since √(-3) = i√3 (because i√3 x i√3 = (i x i) x (√3 x √3) = -1 x 3 = -3), the roots are -1/2 ± (√3/2)i

It is possible to find complex roots your way

You can find the roots the way you calculate things, but be more careful with imaginary part; let's represent x not as 'a + b' as you do but as 'a + bi', where both a and b are real numbers, and i is, well, square root of -1. Then we will get:

  1(a + bi)² + 1(a + bi) + 1 = 0 =>

a² + 2abi + (bi)² + a + bi + 1 = 0 =>

a² + 2abi - b² + a + bi + 1 = 0 =>

(a² - b² + a + 1) + (2ab + b)i = 0

Now look at the number at the left side: it has real part (a² - b² + a + 1) and imaginary part (2ab + b)i. For this number to be zero, both parts should be zero (you cannot make zero out of real number by adding imaginary part to it).

So we got that

  a² - b² + a + 1 = 0 and (2ab + b)i = 0

I'm going to look at the imaginary part first.

  (2ab + b)i = 0 =>

2ab + b = 0 =>

(2a + 1)b = 0

Now we have two numbers (2a + 1 and b) such that their product is zero, so one of those numbers is zero. It cannot be b (try to substitute b = 0 -- the equation turns out to a² + a + 1 = 0, which has no real solutions, and a was a real number). Hence

  2a + 1 = 0 => a = -1/2

Now, when we know a, let's look at the real part.

  a² - b² + a + 1 = 0 =>

1/4 - b² - 1/2 + 1 = 0 =>

b² = 3/4 =>

b = ±√3/2

We substituted x = a + bi, so we can get our two roots now: -1/2 ± (√3/2)i

General situation

There is a theorem that the number of (complex) roots a polynomial has is equal to its degree. Well, the whole thing is a bit less straightforward as some roots can repeat themselves, like in x² - 2x + 1 = 0 -- there is only one solution, x = 1, but since the same equation can be represented as (x - 1)(x - 1) = 0, the solution x = 1 is, well, counted twice -- once for each "x - 1". I'm not going deeper here, but what's important to know: if you take random polynomial of degree n, almost always it will have exactly n different complex roots.

It is not possible to calculate exact roots for general polynomial of degree over 4 -- not that we don't know how, it's proven theorem that the formula cannot exist.

About my picture

So, I have equations which look like ..x^24 + ..x^23 + ...and so on... + ..x^2 + ..x + .. = 0, where every '..' is either 1 or -1. I lose nothing assuming that x^24 always has 1 (think about it), so there are 24 coefficients left. It gives me 2^24 = 16777216 equations. I find approximate solutions for each of those, and each has exactly 24 solutions. In this way I'm getting 2^24 x 24 = 402653184 complex numbers. For each such number, if it is a + bi, I put a point with coordinates (a, b). And that's how I've got my picture!