Golden powers are nearly integers(johndcook.com)
johndcook.com
Golden powers are nearly integers
https://www.johndcook.com/blog/2017/03/22/golden-powers-are-nearly-integers/
7 comments
Another way to get at this:
So φ^n = F(n)φ + F(n-1) → F(n+1) + F(n-1) = L(n) as n → ∞. This gets close to being an integer because F(n+1) and F(n-1) are both integers.
φ^1 = φ
φ^2 = φ + 1 [this is the definition of φ]
φ^3 = φ(φ + 1) = 2φ + 1
φ^4 = φ(2φ + 1) = 3φ + 2
φ^5 = φ(3φ + 2) = 5φ + 3
φ^6 = φ(5φ + 3) = 8φ + 5
...
φ^n = F(n)φ + F(n-1)
So φ^n = F(n)φ + F(n-1) → F(n+1) + F(n-1) = L(n) as n → ∞. This gets close to being an integer because F(n+1) and F(n-1) are both integers.
I'm almost with you, but you need a bit more.
To show what we want, we must prove the stronger condition that F(n)φ - F(n+1) → 0. Merely knowing that F(n+1)/F(n) → φ only shows that the difference grows more slowly than F(n).
To show what we want, we must prove the stronger condition that F(n)φ - F(n+1) → 0. Merely knowing that F(n+1)/F(n) → φ only shows that the difference grows more slowly than F(n).
[deleted]
>To show what we want, we must prove the stronger condition that F(n)φ - F(n+1) → 0.
Noting that {F(n+1)/F(n)} is the sequence of convergents of the continued fraction expansion of φ, your stronger condition follows from Theorem 5 at https://en.wikipedia.org/wiki/Continued_fraction .
Noting that {F(n+1)/F(n)} is the sequence of convergents of the continued fraction expansion of φ, your stronger condition follows from Theorem 5 at https://en.wikipedia.org/wiki/Continued_fraction .
[deleted]
I've always enjoyed that formula for the Fibonacci numbers, primarily because it's so unintuitive that the right hand side would actually even be an integer. It's a fun exercise to prove that (without resorting to the fact that the Fibonacci numbers are obviously integers). Hint: start with -1/phi = 1-phi and use phi=(sqrt(5)+1)/2.
That is a special case of an even more amazing result.
Given a polynomial P(x), any expression that can be written as a symmetric polynomial in the roots of P, can be written as a polynomial in the coefficients of P. See https://en.wikipedia.org/wiki/Elementary_symmetric_polynomia... for more.
This applies to arbitrary rings. So if P(x) and Q(x) are both polynomials, then any polynomial which is symmetric in the roots of P(x) and also symmetric in the roots of Q(x) can be written as polynomials in the coefficients of Q(x) and P(x). Therefore, for example, (x-sqrt(2)-sqrt(3))(x-sqrt(2)+sqrt(3))(x+sqrt(2)-sqrt(3))(x+sqrt(2)+sqrt(3)) will work out to be a polynomial in the coefficients of x^2-2 and x^2-3. It will therefore be an integer polynomial with those 4 roots.
This is actually the original way in which people proved that the algebraic integers formed a ring.
Given a polynomial P(x), any expression that can be written as a symmetric polynomial in the roots of P, can be written as a polynomial in the coefficients of P. See https://en.wikipedia.org/wiki/Elementary_symmetric_polynomia... for more.
This applies to arbitrary rings. So if P(x) and Q(x) are both polynomials, then any polynomial which is symmetric in the roots of P(x) and also symmetric in the roots of Q(x) can be written as polynomials in the coefficients of Q(x) and P(x). Therefore, for example, (x-sqrt(2)-sqrt(3))(x-sqrt(2)+sqrt(3))(x+sqrt(2)-sqrt(3))(x+sqrt(2)+sqrt(3)) will work out to be a polynomial in the coefficients of x^2-2 and x^2-3. It will therefore be an integer polynomial with those 4 roots.
This is actually the original way in which people proved that the algebraic integers formed a ring.
> start with -1/phi = 1-phi and use phi=(sqrt(5)+1)/2.
This is the same fact twice. (Well, the second part is just one of the two roots of the polynomial equation x^2 = x + 1.)
This is the same fact twice. (Well, the second part is just one of the two roots of the polynomial equation x^2 = x + 1.)
[deleted]
Dude seriously explain in simpleton...?
If people are interested in this sort of thing, there's some nice linear algebra underlying the idea.
The Fibonacci recurrence is a linear recurrence, meaning that if you have two different sequences such that
Well, remember that the recurrence gives you everything if you also specify the first two numbers F[0] and F[1]. We know that these two sequences that we just computed are
Similarly for the case of the powers of phi, we can use this argument in reverse to say "I know I want P1 plus something times P2 which causes all of the terms to be integers," P2 will then approach zero (since it has modulus less than 1).
For this, we can look at the recurrence and say "oh, we just need the first two terms to be integers and then the recurrence makes everything else integers," so choosing a = 1, b = 1 gives us F[0] = 2, F[1] = 1, and these happen to be called the "Lucas numbers".
Similarly we could expect that the powers of any solution to p² = m p + n, integer m, n, p > 1 will be close to the integers as long as the other solution q lies somewhere in the unit interval -1 < q < 1. Completing the square gives (p − m/2)² = n + m²/4, the solutions are evenly spaced about m/2 with a distance from center to solution of √(m²/4 + n).
So for example the recurrence T[n] = 3 T[n-1] - T[n-2] is solved by the numbers (3 ± √5)/2 and so (3 + √5)/2 must also have this property, whereas T[n] = 3 T[n-1] + T[n-2] gives you (3 ± √13)/2 and has this property too.
The Fibonacci recurrence is a linear recurrence, meaning that if you have two different sequences such that
F[n] = F[n - 1] + F[n - 2]
G[n] = G[n - 1] + G[n - 2]
Well, remember that the recurrence gives you everything if you also specify the first two numbers F[0] and F[1]. We know that these two sequences that we just computed are
P1 = [1, (1 + √5)/2, ...]
P2 = [1, (1 − √5)/2, ...]
a P1[0] + b P2[0] = F0,
a P1[1] + b P2[1] = F1.
Similarly for the case of the powers of phi, we can use this argument in reverse to say "I know I want P1 plus something times P2 which causes all of the terms to be integers," P2 will then approach zero (since it has modulus less than 1).
For this, we can look at the recurrence and say "oh, we just need the first two terms to be integers and then the recurrence makes everything else integers," so choosing a = 1, b = 1 gives us F[0] = 2, F[1] = 1, and these happen to be called the "Lucas numbers".
Similarly we could expect that the powers of any solution to p² = m p + n, integer m, n, p > 1 will be close to the integers as long as the other solution q lies somewhere in the unit interval -1 < q < 1. Completing the square gives (p − m/2)² = n + m²/4, the solutions are evenly spaced about m/2 with a distance from center to solution of √(m²/4 + n).
So for example the recurrence T[n] = 3 T[n-1] - T[n-2] is solved by the numbers (3 ± √5)/2 and so (3 + √5)/2 must also have this property, whereas T[n] = 3 T[n-1] + T[n-2] gives you (3 ± √13)/2 and has this property too.
Suppose f(x) = x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0 is a monic polynomial with integer coefficients. Let x_1, ..., x_n be all its (complex) roots. If it happens that the absolute value of x_1 is larger than 1, but absolute values of all x_2, x_3, ..., x_n are smaller than 1, the powers of x_1 will be close to integers. The golden ratio (1+sqrt(5)/2 is a root of x^2 - x - 1, and the other root (1-sqrt(5))/2 is smaller than 1 in absolute value, so the observation follows.
One way to prove the assertion is following: note that for large n, x_1^n + x_2^n + ... + x_3^n is very close in value to x_1^n, because all the other summands are very small in absolute value, since they start out smaller than 1, and they decrease exponentially to 0. But it just so happens that x_1^n + x_2^n + ... + x_3^n is an integer -- indeed, this is a symmetric polynomial with integer coefficients in x_1, ..., x_n, and every such polynomial has a unique expression as a polynomial in elementary symmetric polynomial with integer coefficients -- this is the fundamental theorem of symmetric polynomials[1]. But, if you plug the roots of a given polynomial into elementary symmetric polynomials, you'll just get the coefficients of the original polynomial times (-1)^k, that is, the original a_0, a_1, ..., a_{n-1} -- for example, a_0 is clearly the product (-1)^n x_1 * x_2 * ... * x_n, a_{n-1} is the sum (-1)^1 (x_1 + ... + x_n), a_{n-2} is a sum of two-products (-1)^2 (x_1 x_2 + x_1 x_3 + ... + x_{n-1} x_n) and so on.
For concrete example, note that x_1^2 + ... + x_n^2 = (x_1 + ... + x_n)^2 - 2(x_1 x_2 + ... + x_{n-1} x_n) = a_{n-1} - 2 a_{n-2}, which is an integer. Try expressing x_1^3 + ... + x_n^3 i n terms of a_{n-1}, a_{n-2} and a_{n-3}.
[1] - https://en.wikipedia.org/wiki/Elementary_symmetric_polynomia...
One way to prove the assertion is following: note that for large n, x_1^n + x_2^n + ... + x_3^n is very close in value to x_1^n, because all the other summands are very small in absolute value, since they start out smaller than 1, and they decrease exponentially to 0. But it just so happens that x_1^n + x_2^n + ... + x_3^n is an integer -- indeed, this is a symmetric polynomial with integer coefficients in x_1, ..., x_n, and every such polynomial has a unique expression as a polynomial in elementary symmetric polynomial with integer coefficients -- this is the fundamental theorem of symmetric polynomials[1]. But, if you plug the roots of a given polynomial into elementary symmetric polynomials, you'll just get the coefficients of the original polynomial times (-1)^k, that is, the original a_0, a_1, ..., a_{n-1} -- for example, a_0 is clearly the product (-1)^n x_1 * x_2 * ... * x_n, a_{n-1} is the sum (-1)^1 (x_1 + ... + x_n), a_{n-2} is a sum of two-products (-1)^2 (x_1 x_2 + x_1 x_3 + ... + x_{n-1} x_n) and so on.
For concrete example, note that x_1^2 + ... + x_n^2 = (x_1 + ... + x_n)^2 - 2(x_1 x_2 + ... + x_{n-1} x_n) = a_{n-1} - 2 a_{n-2}, which is an integer. Try expressing x_1^3 + ... + x_n^3 i n terms of a_{n-1}, a_{n-2} and a_{n-3}.
[1] - https://en.wikipedia.org/wiki/Elementary_symmetric_polynomia...
I don't have any advanced math experience, but this is one of the coolest things I've read in a long time - kudos to the author for explaining a couple interesting things about a complex topic in a simple way.
But he didn't explain why it happens at all?
You're right, he didn't explain why it happens. But like I said, he explained "a couple interesting things", showing readers that these interesting patterns exist. To people outside of mathematics like me, it's cool just that these patterns and phenomena are present, even if we don't grasp the math behind why.
That being said, an easy-to-understand explanation of why it happens (to the extent that is possible), like in some of the other comments, would be super interesting as well.
That being said, an easy-to-understand explanation of why it happens (to the extent that is possible), like in some of the other comments, would be super interesting as well.
Some more discussion of the same article on Reddit:
https://www.reddit.com/r/math/comments/60uua3/powers_of_the_...
https://www.reddit.com/r/math/comments/60uua3/powers_of_the_...
At least he clearly explained the problem (or really phenomenon), so anyone can understand it.
I mean, I'm not knocking the blog. It's fine. But I'm having a hard time identifying what the complex topic was that was given a simple explanation. "Here's a graph" isn't a complex topic, and saying "here's a graph" doesn't really explain it either.
Another interesting relationship between powers and infinity is that on an infinite N-dimensional lattice, taking an infinitely long random walk, starting with dimension 3 you have a 34% chance to return to origin with each successive dimension reducing your chance. The graph of this probability follows a log curve. (dimensions 1 and 2 have a 100% probability of returning to origin)
So what this is saying is, if you don't have "1" in your numerical system, you can recover it by taking φ to the power of infinity and then dividing by infinity?
Any "number system" (be it a field, ring, or multiplicative group) has a "1"
Depends on your definition of "ring"; for some people, a ring need not have a multiplicative identity. But yes, any number system worth its salt has at least a couple of integers in it.
I was joking. :X
[deleted]
φ is expressed in terms of 1, so if you have "φ" you have "1."
Yeah, it's really obvious too if you know basic algebra. The article doesn't even attempt to explain it, so what's the point, except for blogspam?
I thought I knew basic algebra... I guess not. It definitely is not obvious to me.
To be fair, "algebra" means very different things to different people, so I don't think Grue3 meant to be quite as brash as it may have sounded.
What's the definition of basic algebra that makes that fact obvious? I took 3 semesters of algebra in college (Linear Algebra, Abstract Algebra I and II), and don't see anything obvious about it. But then, neither does Terry Tao:
> "the powers φ, φ2, φ3, … of the golden ratio lie unexpectedly close to integers...
> "the powers φ, φ2, φ3, … of the golden ratio lie unexpectedly close to integers...
It becomes obvious when you know closed form expression for Fibonacci numbers as a sum of powers of phi (which I'm sure Tao is aware of). I was taught that in high school. The only reason this wouldn't be obvious to Tao is if he was working on much harder problems for so long that he forgot the basic stuff.
It's not basic algebra in the sense of my high-school "Maths B" class. But it is just the kind of thing we did in "Maths C".
Here a hint: use the definition of φ that
Here a hint: use the definition of φ that
1 = φ - 1/φ
F[k] = φ^k + 1/(-φ)^k
F[k+1] = φ^(k+1) + 1/(-φ)^(k+1)
That seems like a clever proof, and I understand it and even admire it. But it doesn't look like that the kind of thing that's "obvious" unless you frequently work with this kind of thing.
The Fibonacci numbers, meanwhile, can be given by the formula F_n = (phi^n - (-1/phi)^n) / sqrt(5). So a similar thing holds for them.
More generally, phi is a Pisot number: https://en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_n... Any Pisot number will have its powers approach integers at an exponential rate. (In that, the distance to the nearest integer decreases exponentially.)