A few words about PWW #20

Posted on July 22, 2017 by Brent

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?

About Brent

Associate 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:
      July 23, 2017 at 2:58 pm

      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:
        July 23, 2017 at 5:06 pm

        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.

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

  5. sn0wleopard says:
    July 27, 2017 at 5:38 pm

    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 🙂

Comments are closed.