A few words about PWW #20

A couple commenters quickly figured out what my previous post without words was about. The dots making up the image are at integer grid points (m,n), with the center at (0,0). There is a dot at (m,n) if and only if m and n are relatively prime, that is, \gcd(m,n) = 1. Here is a slightly smaller version so it’s easier to see what is going on:

I learned from Lucas A. Brown that this is sometimes known as “Euclid’s Orchard”. Imagine that there is a tall, straight tree growing from each grid point other than the origin. If you stand at the origin, then the trees you can see are exactly those at grid points (m,n) with \gcd(m,n) = 1. This is because if a tree is at (dm,dn) for some d > 1, then it is blocked from your sight by the tree at (m,n): both lie exactly along the line from the origin with slope n/m. But if a tree is at some point with relatively prime coordinates (m,n), then it will be the first thing you see when you look along the line with slope exactly n/m.

(…well, actually, all of the above is only really true if we assume the trees are infinitely skinny! Otherwise trees will end up blocking other trees which are almost, but not quite, in line with them. So try not to breathe while standing at the origin, OK? You might knock over some of the infinitely skinny trees.)

Here’s the 9 \times 9 portion of the grid surrounding the origin, with the lines of sight drawn in along with the trees you can’t see because they are exactly in line with some closer tree. (I’ve made the trees skinny enough so that they don’t accidentally block any other lines of sight—but if we expanded the grid we’d have to make the trees even skinner.)

Now, what about the colors of the dots? Commenter Snowball guessed this correctly: each point is colored according to the number of steps needed for the Euclidean algorithm needed to reach 1. Darker colors correspond to more steps. It is interesting to note that there seems to be (eight symmetric copies of) one particularly dark radial stripe, indicated below:

In fact, the slope of this stripe is exactly \varphi = (1 + \sqrt 5)/2! This corresponds to the fact (first proved by Gabriel Lamé in 1844) that consecutive Fibonacci numbers are worst-case inputs to the Euclidean algorithm—that is, it takes more steps for the Euclidean algorithm to compute \gcd(F_{n+1}, F_n) = 1 than for any other inputs of equal or smaller magnitude. Since the ratio of consecutive Fibonacci numbers tends to \varphi, the dots with the darkest color relative to their neighbors all lie approximately along the line with slope \varphi. What’s interesting to me is that lots of other dots that lie close to this line are also relatively dark. Why does this happen?

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in pattern, pictures, posts without words and tagged , , . Bookmark the permalink.

10 Responses to A few words about PWW #20

  1. Pingback: New top story on Hacker News: Euclid’s Orchard, the Euclidean algorithm, and Fibonacci numbers, with pictures – The Internet Yard

    • Brent says:

      They certainly look similar because of the radial lines, but actually I think they are quite different. Though if someone knows of a deeper relationship between them I’d love to hear about it!

      • Snowball says:

        Visual: https://i.imgur.com/MiBpss0.png

        Claim: gcd(n,k) = 1 if and only if \omega_n^k is a primitive n^\text{th} root of unity.

        Proof:

        Consider the point (n,k), where k < n.

        Suppose \gcd(n,k) = \ell \ne 1. Then (\omega_n^k)^{n/\ell} = (\omega_n^n)^{k/\ell} = 1, so \omega_n^k is a n/\ell^\text{th} root of unity. As n/\ell < n and \omega_n^k is a n/\ell^\text{th} root of unity, \omega_n^k is not a primitive n^\text{th} root of unity.

        Suppose \gcd(n,k) = 1. Suppose that \omega_n^k is not a primitive n^\text{th} root of unity. Then there is some m<n such that \omega_n^k is an m^\text{th} root of unity, i.e., 1 = (\omega_n^k)^m. Thus n|km. As \gcd(n,k) = 1, we must have n|m. This is a contradiction, since m<n. Therefore \omega_n^k must be a primitive n^\text{th} root of unity.

  2. Pingback: From primitive roots to Euclid’s orchard | The Math Less Traveled

  3. sn0wleopard says:

    What a beautiful visualisation of Euclid’s Orchard! I can’t stop looking at it and want to tile my floor with it 🙂

    > What’s interesting to me is that lots of other dots that lie close to this line are also relatively dark. Why does this happen?

    I think I have one possible answer. Points with Fibonacci coordinates can be obtained by starting with coordinate (1, 1) and then climbing upwards via the x(n+1) = x(n) + x(n – 1) rule.

    But we can start with any (a, b) coordinate where a and b are co-prime. This will give us:

    x(0) = a
    x(1) = b
    x(2) = a + b
    x(3) = a + 2b
    x(4) = 2a + 3b
    etc.

    For example, for a = 1 and b = 3 we get: 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, etc, which are still pretty bad for Euclidean algorithm. And the ratio between the neighbours also tends to the golden ratio (e.g. 123/76 = 1.618), in fact almost by the very definition of golden ratio. Indeed, at infinity we have:

    ratio = x(n+1) / x(n) = x(n) / x(n – 1)

    Rewriting this via x(n + 1) = x(n) + x(n – 1) we get:

    (x(n) + x(n – 1)) / x(n) = x(n) / x(n – 1)

    or (p + q) / p = p / q — which is how the golden ratio is defined.

    So, regardless of the starting coordinate (a, b) our generalised Fibonacci climb will eventually bring us close to the dark side of the Euclid’s Orchard 🙂

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s