# Graph of Fibonacci Numbers in the Complex Plane

I'm going to make a better version with smaller line segments.

Edit: Higher quality version:

Oh and I just made an even higher quality one:

More precise version of the last one: (you will probably have to zoom in to see it)

To make this, I loaded the Bignums library, and did this:

The (fib n) block's definition is this, Binet's Formula:

And the (sqrt 5) block's definition is this:

I love Bignums.

You mean "I love the Scheme numeric tower." (This matters because JS now has native bignums, but not exact rationals or complex numbers, and we're going to have to talk Jens out of thinking we no longer need the library.)

I love that little loop-the-loop right around x=1. :~)

PS I still don't know what it means to have an exact sqrt(5), which is impossible. You can get an exact representation of a rational number that's pretty near sqrt(5), but it's not exactly sqrt(5). That call to EXACT should report an error, imho.

Yes, my mistake.

That loop is just a fact of fibonacci numbers.

Represent it as "$$\sqrt5$$"! The SCHEME NUMBER turns the inaccurate float to a x/y.

Imprecise, not inaccurate, according to the computer science understanding of those terms. (Mathematically, you're right, it's inaccurate, but it's still inaccurate when you represent it as an exact rational.)

I'm not sure if you've learned about irrational numbers and just don't see the connection with your present project, or if I should teach you about irrational numbers.

I haven't learned a lot, but I do know the basics, like it doesn't repeat, (a repeating decimal can always be represented as a fraction with the denominator some number of nines, BTW) it can't be represented perfectly with a fraction, (any terminating decimal can be represented as a fraction) etc.

? The project is going to have to have something to with irrationals no matter what I do with Binet's formula.

Ok.

Righto. So, in particular, any number that can be represented in IEEE floating point (the way real numbers are represented on all computers these days) is rational, because it has a finite number of (binary, but that doesn't matter) digits.

So when you ask (sqrt 5), if you get any answer that looks like a number (made of digits, decimal point, E, and one or two signs), you know it must be incorrect, because sqrt(5) is irrational and any number you get out of a computer will be rational. (This is even more obviously the case if it's in exact-rational format.)

(You know how to prove that sqrt(5) is irrational, right?)

No, but I do know that the square root of any perfect square, or of the reciprocal of a perfect square, is always rational. And the square root of any other integer is irrational.

Ah. But you know that every positive integer can be expressed as a unique product of powers of primes, e.g., 24 = 2³⋅3¹, right?

For clarity, probably.

I didn't know that! Interesting.

That is also one reason why 1 is not considered a prime number. If it was, you could construct a number from multiples of primes in multiple ways. For example, 24 = 2³⋅3¹, but it could also by written as 24 = 2³⋅3¹⋅1¹, or 24 = 2³⋅3¹⋅1³¹⁵²⁵⁹. By excluding 1 from the primes, each integer has one unique prime factorization.
https://blogs.scientificamerican.com/roots-of-unity/why-isnt-1-a-prime-number/
https://primes.utm.edu/notes/faq/one.html

Because when we get to proving that sqrt(5) is irrational, the exponents will be important.

It's called the Unique Prime Factorization Theorem, but it's also called the Fundamental Theorem of Arithmetic because it turns out to be so important. You'll see that we need it to prove that sqrt(5) is irrational.

So let's take a moment for a handwavy proof. First, we need to know that every positive integer n can be represented as a product of primes. Then we'll show that it can be done in only one way.

For the first part, we use proof by induction: We show that it's true for 2. (Really we should start with 1 but that gets us into arguments about products of no numbers, so let's just say that the Fundamental Theorem is true for numbers starting at 2, and we can discuss 1 later if you want.) Then we show that if it's true for all m < n, then it's true for n also. And that's enough, because if it's true for 2 then it must be true for 3; if it's true for 2 and 3 then it must be true for 4, etc. So, trivially, 2 can be represented as 2¹. (And that's the only way to represent it as a product of primes, because any other prime is too big.)

So, let's assume that every positive integer less than n can be represented as a product of primes. We want to know about n. Since n>1, either it's prime or it's composite. If it's prime, it's its own prime factorization, or if you want to be fancy, it's n¹. If it's composite, that means n=ab, where 1<a<n and 1<b<n. (The strict less-than signs (vs. ≤) are important; 1 as a factor would be useless and would imply that the other factor has to be n itself. We want two smaller factors.)

Okay, well, since a and b are less than n, we are assuming that the theorem applies to them. So each has a prime factorization. Well, just multiply those together, collect the like terms, and you have a prime factorization for n.

As for uniqueness, suppose we have two different prime factorizations for n. We're going to find the first prime in which they differ. So, if the exponent of 2 is the same in both factorizations (including 2⁰ if neither factorization includes a 2), just forget about 2 and go on to the next prime, 3. This time, let's say one factorization includes 3⁴ and the other includes 3¹ (and no higher exponent of 3). Divide n by the smaller of those: in this case, 3¹. So, looking at the factorization that had 3¹, we see that n/3 is not divisible by 3. But looking at the other factorization, we see that n/3 is divisible by 3³ (that is, 3⁴/3¹). So n/3 both is and isn't divisible by 3, which is a contradiction. So it has to be that there is no prime whose exponents in the two factorizations are different. In other words, they're not different at all. QED.

Okay, to prove that sqrt(5) is irrational. This will be a proof by contradiction: we assume that it's rational, and show that that leads to a contradiction.

Okay, sqrt(5) is rational; in other words, it's p/q where p and q are (positive) integers. So,

√5 = p/q
5 = p²/q²
p² = 5q²


Time out for a lemma: if an integer is a perfect square, all the exponents in its prime factorization are even. Proof: Let's say that for any positive integer p,

p=2^a⋅3^b⋅5^c⋅7^d⋅...


So

p² = 2^(2a)⋅3^(2b)⋅5^(2c)⋅7^(2d)⋅...


Right? And by the FTA that's the only prime factorization of p². So, if an integer is a perfect square, all the exponents in its prime factorization are even. QED.

Back to the main theorem. We have p²=5q². Since p² is a perfect square, the exponent of 5 in its prime factorization is even. What about q²? It's a perfect square, too, so the exponent of 5 in its prime factorization is even. So the exponent of 5 in the prime factorization of 5q² has to be odd. But 5q² is equal to p², which means its exponent of 5 is even. This is a contradiction. So our initial assumption that √5=p/q must have been wrong. QED!

As you might guess, this was first proved for √2, but you can see that the proof works for any prime number. For composite numbers, the arithmetic is a little messier, but not conceptually harder. The only way this proof fails to lead to a contradiction is if we're taking the square root of a square integer. Let's try it for 4. So we start with √4=p/q, so p²=4q². But 4=2², so if the exponent of 2 in q² is even, the exponent of 2 in 4q² is still even. So it's perfectly possible to have p²=4q². So (as you said earlier) it's only numbers with integer square roots that can have rational square roots.

So. The story goes that this proof (for √2) was invented by a student at Pythagoras's math school for smart mathematicians. Pythagoras, you may know, had a quasi-religion based on integers. The integers were holy, and so proving theorems about them was good work. He reluctantly allowed as how ratios of integers are okay, too, because he needed them to understand musical notes. (The note an octave up from here has frequency 2 times this note's frequency, but the note a fifth up has frequency 3/2 times this note's frequency.) But that's as far as he'd go; all numbers are ratios of integers.

So here comes this student proving that that's not true, that √2 isn't a ratio of integers. And they can't just say there's no such number, because it's the length of the hypotenuse of an isosceles right triangle, according to Pythagoras's great central theorem (which, by the way, apparently predates Pythagoras by a long time in China). So, says the story, they took the student down to the river and drowned him. This proves that studying math can be dangerous. (But of course it's probably not even slightly true; we don't even know for sure that it was a disciple of Pythagoras who proved it.)

(technically a bump, but...)

Can that proof be extended to non-integers? Like, proving, say, $$\sqrt{3\over2}$$ is irrational, but, say, $$\sqrt{9\over4}$$ is rational?

Edit before posting: I realized you can prove the numerator and/or denominator are irrational or not, making sure you use the simplest form of the fraction. Like, for $$\sqrt{3\over2}$$, you could have a proof of the irrationality of 3 and 2, and you would know $$\sqrt{3\over2}$$ is irrational, but for $$\sqrt{9\over4}$$, you could find that $$\sqrt{9}$$ and $$\sqrt{4}$$ are both rational, and know that $$\sqrt{9\over4}$$ would thus be rational.

Yup, except that you meant "rational" as the last word of that message. :~)

Sometimes I make mistakes. I'll fix it.

That's because you're not a teacher. :~P