Profile

Cover photo
Richard Green
Works at University of Colorado Boulder
Attended University College, Oxford
Lives in Longmont, Colorado
115,143 followers|38,551,575 views
AboutPostsCollectionsPhotos

Stream

Richard Green

Shared publicly  - 
 
Here's a picture I took in a park near my house in Longmont, Colorado on January 10. Most of the snow is now gone. It was taken using my iPhone 5 using the HDR feature, but without any other editing.

#treetuesday #longmont   #colorado  
205
9
Irina T.'s profile photoRichard Green's profile photoAzlin Bloor's profile photo
33 comments
 
+Richard Green hi Richard, I'm sure you've heard of Create. Here's the site to apply: http://g.co/PlusCreate
Referrals are not a free entry but it does tell the selectors that you've been asked to apply or referred to by a Create member. At the moment, Create would love to see more educators on board and you would be great in there. 
Add a comment...

Richard Green

Shared publicly  - 
 
The complexity of integers

The complexity of an integer n is defined to be the smallest number of 1s required to build the integer using parentheses, together with the operations of addition and multiplication. 

For example, the complexity of the integer 10 is 7, because we can write 10=1+(1+1+1)x(1+1+1), or as (1+1+1+1+1)x(1+1), but there is no way to do this using only six occurrences of 1. You might think that the complexity of the number 11 would be 2, but it is not, because pasting together two 1s to make 11 is not an allowable operation. It turns out that the complexity of 11 is 8.

The complexity, f(n), of an integer n was first defined by K. Mahler and J. Popken in 1953, and it has since been rediscovered by various other people. A natural problem that some mathematicians have considered is that of finding upper and lower bounds of f(n) in terms of n. 

John Selfridge found a lower bound for f(n) by proving that f(n) is always greater than or equal to 3 log_3(n), where log_3(n) denotes the base 3 logarithm of n. This lower bound is sharp: it cannot be improved because the bound is achieved when n is a power of 3. For example, if n=81, we have n=3^4, which (by the definition of logarithm) means that log_3(n)=4. Selfridge's lower bound for f(n) is then 3x4=12. We can write 81=(1+1+1)x(1+1+1)x(1+1+1)x(1+1+1), which uses twelve occurrences of 1, and Selfridge's result shows that there is no way to achieve this using eleven or fewer 1s. Note that we are only allowed to use addition and multiplication in our expressions; using exponentiation is not allowed.

The problem of finding an upper bound is more complicated. Richard K. Guy found an upper bound for f(n), showing that it is bounded above by 3 log_2(n), which works out at about 4.755 log_3(n). (The 4.755 is an approximation to 3log(3)/log(2).) Guy found this bound using Horner's method, which is explained in the appendix below. The worst case of Guy's bound is achieved in the case that n has no zeros when it is expressed in base 2. 

More generally, it turns out to be difficult to improve the upper bound for f(n) because numbers whose binary digits contain a very uneven balance of 0s and 1s tend to cause problems. An example of this is the number 1439, which is 10110011111 in binary. It turns out that f(1439)=26, and an optimal expression for 1439 is 1+2(1+2(1+1+3((2)(2)(2)(2)+1)((3)(2)+1))), where 2 and 3 are shorthands for (1+1) and (1+1+1), respectively. This works out as about 3.928 log_3(1439).

However, it is possible to replace this value of 3.928 by a lower number for “almost all” integers n; in particular, recent work of J. Arias de Reyna and J. van de Lune shows that it can be replaced by 3.655 for a set of natural numbers of density 1. The recent paper Applications of Markov Chain Analysis to Integer Complexity  (http://arxiv.org/abs/1511.07842) by Christopher E. Shriver improves this upper bound to 3.529 for suitably generic numbers. The paper mentions that extensive numerical computations by other authors suggest that it ought to be possible to improve the generic bound to 3.37.

Relevant links

The On-Line Encyclopedia of Integer Sequences lists the complexities f(n) of the first few natural numbers (https://oeis.org/A005245) and mentions that Guy conjectured that f(p) = f(p–1) + 1 whenever p is prime. Guy's conjecture turned out to be false, but the smallest counterexample, which was found by Martin Fuller in 2008, is surprisingly big: the smallest such prime is 353942783.

The OEIS is an extremely useful resource for researchers in discrete mathematics. They are currently running their annual appeal for donations, and you can donate on this page: http://oeisf.org/

The “extensive numerical computations” mentioned above are discussed in the paper by Iraids et al, which you can find at http://arxiv.org/abs/1203.6462

Appendix: proof of Guy's upper bound

Horner's method works by expressing a (nonzero) number n in base 2 as a sequence of binary digits a_0 a_1 ... a_k, where we may assume that the last digit a_k is equal to 1. It is not hard to show from this that log_2(n) is greater than or equal to k and less than k+1. It is also immediate that n can be expressed as the polynomial 
a_0 + x a_1 + x^2 a_2 + ... + x^k a_k
when x is replaced by 2. Rearranging, we find that
n = a_0 + 2(a_1 + 2(a_2 + ... + 2(a_{k-1} + 2)...)),
because we assumed that a_k was equal to 1. We then replace each occurrence of 2 with “1+1”, and replace each occurrence of a_i with either 0 or 1. Finally, we remove all the occurrences of “0+”. The number of 1s in the result is at most 3k, as required; the bound is achieved whenever n is one less than a power of 2.

For example, n=42 is 101010 in binary, which can be written as 0+2(1+2(0+2(1+2(0+2)))). This expands to (1+1)(1+(1+1)(1+1)(1+(1+1)(1+1))), which uses 12 ones. Since 42 lies between 2^5=32 and 2^6=64, it follows that log_2(42) is more than 5, and 3 log_2(n) is more than 12, as required.

#mathematics #sciencesunday #spnetwork arXiv:1511.07842
478
86
oliver olang''s profile photoAndrew Johna Achuri's profile photoPatrick Kisia's profile photoHendrik Boom's profile photo
52 comments
 
+oliver olang' That's better.
Add a comment...

Richard Green

Shared publicly  - 
 
For #treetuesday, here are two maple trees from near my house in Longmont, Colorado. They have a habit of dropping Canadian flags all over the ground.

This was taken with my iPhone 5 and edited with #snapseed.
293
28
afrooz mottahedy's profile photoAdda Bolivia's profile photoK.M Cantrell's profile photoaltimira jordão's profile photo
31 comments
 
Muito lindo
 ·  Translate
Add a comment...

Richard Green

Shared publicly  - 
 
Multiply-perfect numbers

A number n is said to be perfect if the sum of the divisors of n is 2n, and it is said to be k-perfect, or multiply-perfect, if the sum of the divisors of n is kn. For example, the number 120 is 3-perfect, because the divisors of 120 (which are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, and 120) add up to 360, which is 3 times 120.

A Mersenne prime is a prime number of the form 2^m – 1; for example, 7 = 2^3 – 1 is a Mersenne prime. It is a theorem that if 2^m – 1 is prime, then 2^{m–1}(2^m – 1) is an even perfect number, and furthermore, that every even perfect number arises in this way from a Mersenne prime. In the example of m=3, we see that 2^2(2^3 – 1) = 4x7 = 28, and 28 is a perfect number because the sum of its divisors, 1+2+4+7+14+28, is 56, which is twice 28. At the time of writing, the largest known prime number, 2^{57885161} − 1, is a Mersenne prime.

Although the concept of a perfect number was known to Euclid around 300 BC, some basic questions about perfect numbers remain open. For example, it is not known whether or not there are any odd perfect numbers, although it is known that if there is one, it must be very large. It is also not known whether or not there are infinitely many even perfect numbers, because it is also not known whether there are infinitely many Mersenne primes.

Furthermore, it is not known whether there are infinitely many k-perfect numbers where k is 3 or more, although it is expected that for each such k, there will only be finitely many k-perfect numbers. For example, the known 3-perfect numbers are 120, 672, 523776, 459818240, 1476304896, and 51001180160, and it is expected that this list is complete. However, if an odd perfect number m were to be discovered, then the number 2m would be an example of an even 3-perfect number that is not in the list! 

The reason for this comes from properties of the function σ(n). If n is a positive integer, then σ(n) is defined to be the sum of the divisors of n; for example, we proved earlier that σ(28)=56 and σ(120)=360. A number n will then be perfect if and only if σ(n)=2n, and k-perfect whenever σ(n)=kn. The function σ(n) is an example of a multiplicative function, which means that σ(mn)=σ(m)σ(n) whenever m and n have no factors in common. Since 120=8x15, and 8 and 15 share no common factors other than 1, it follows that σ(120)=σ(8)σ(15)=(1+2+4+8)(1+3+5+15)=15x24=360. This gives a much easier way to compute the sum of the divisors of a number without explicitly listing all the factors.

If we now suppose that m is an odd perfect number, then σ(m)=2m. Since m is odd, it follows that σ(2m)=σ(2)σ(m)=(1+2)σ(m)=6m=3x2m, which is precisely the condition for 2m to be 3-perfect. This proves that twice an odd perfect number would have to be 3-perfect.

Another theorem about multiply-perfect numbers that is not too hard to prove is that every 3-perfect number has at least three distinct prime factors; for example, the number 120 has 2, 3, and 5 as its distinct prime factors. There are also lower bounds for the number of prime factors of a k-perfect number for k greater than 3. All of these were derived over 100 years ago in a two-page paper by Derrick N. Lehmer entitled Multiply Perfect Numbers.

Relevant links

The On-Line Encyclopedia of Integer Sequences has a very informative page about multiply-perfect numbers: http://oeis.org/wiki/Multiply-perfect_numbers

Wolfram MathWorld's page on multiperfect numbers contains a number of interesting links: http://mathworld.wolfram.com/MultiperfectNumber.html

Wikipedia has detailed pages about Mersenne primes, perfect numbers and generalizations of the divisor function:
https://en.wikipedia.org/wiki/Mersenne_prime
https://en.wikipedia.org/wiki/Perfect_number
https://en.wikipedia.org/wiki/Divisor_function

Here's a previous post by me with more details about Mersenne primes and perfect numbers: https://plus.google.com/101584889282878921052/posts/cLWBTddiSyy

My previous post linked to a video of Dave Gorman's stand-up comedy routine on perfect numbers. That link seems not to work any more, but this one seems to: https://www.youtube.com/watch?v=8R2B7dInR_E

#mathematics #sciencesunday 
483
94
Bhupinder Singh Anand's profile photoDi Lung Move it Ya Fool!'s profile photoVidyasagar Patri's profile photo
33 comments
 
Novis in maths. Enjoyed reading comments.
A good post for youngsters who are interested in maths.
Bring out more such mind stormers.
Add a comment...

Richard Green

Shared publicly  - 
 
Links of links, and higher structures

A Brunnian link is a collection of linked loops with the property that cutting any one of the loops frees all the others. This picture, which comes from a paper by Nils A. Baas, shows a second order Brunnian link. This consists of six linked loops in a circle, but each of the linked loops is itself a Brunnian link of four linked loops, coloured purple, orange, beige and cyan.

One of the reasons that Baas is interested in such linked structures is because of their connections with physics. The Efimov effect in quantum mechanics refers to a bound state of three bosons in which the attraction between any two bosons is too weak to form a pair. In other words, removing any one of the particles results in the other two falling apart, like the links in the Borromean rings, a famous example of a Brunnian link. The hope is that the study of more general Brunnian links will predict generalized versions of the Efimov effect.

Baas expands on these themes in the recent paper On Higher Structures (http://arxiv.org/abs/1509.00403) which discusses the concept of hyperstructures in mathematics and their possible applications. The paper gives an intuitive outline of the notion of “hyperstructure”; the rigorous definition, which appears in some of Baas's earlier works, is given in terms of category theory. 

The basic idea is that a hyperstructure consists of a set of bonds at various levels: 0, 1, 2 and so on. The bonds at level 0 are objects with properties. A 1-bond binds together some of the properties of the level 0 objects. In turn, the 1-bonds have properties of their own, which are bound together by 2-bonds, and so on.

The paper elaborates the underlying philosophy as follows: 
Much of the intuition around hyperstructures comes from thinking of them as evolutionary structures. They are designed and defined in the same way as evolution works: collections interact forming new bonds of collections with new properties, these being selected for further interactions forming the next level of bonds, etc. In a sense, nature or the environment acts as a kind of observer (or “observation sheaf”). The success of evolutionary structures makes their theoretical counterparts — hyperstructures — a useful design model.

The paper explains in detail how hyperstructures can capture the essence of organized structures, and discusses how the theory might be applied to understanding biological systems (such as in genomics) and democratic structures, as well as to designing and synthesising new molecules and materials.

Relevant links 

The picture comes from the 2010 paper New States of Matter Suggested by New Topological Structures (http://arxiv.org/abs/1012.2698) by Nils A. Baas. In the recent paper, Baas acknowledges A. Stacey and M. Thaule for helping with the diagrams.

Here's a 2010 popular article about Baas's paper of that year: http://www.technologyreview.com/view/422055/topologist-predicts-new-form-of-matter/

Brunnian links are named after the German mathematician Hermann Brunn (1862–1939). The Borromean rings (https://en.wikipedia.org/wiki/Borromean_rings) are special case of Brunnian links (https://en.wikipedia.org/wiki/Brunnian_link)

Efimov states were predicted by Russian physicist V.N. Efimov in 1970: https://en.wikipedia.org/wiki/Efimov_state

Baas's recent paper appears in the General Mathematics section of the arXiv. This is remarkable because this section is typically used as a dumping ground for papers that the arXiv moderators don't like, such as this recent paper about the Riemann hypothesis whose authors don't understand what they're doing: http://arxiv.org/abs/1509.01554

(Maybe I should have had a Relevant links of links section, with a link to a list of links?)

#mathematics #scienceeveryday #spnetwork arXiv:1509.00403
275
55
rafika tatai's profile photoRichard Green's profile photoNadege Deudjeu's profile photo
38 comments
 
Coucou comment tu vas moi c nadege jaimerai faire ta connaissance ci possible
 ·  Translate
Add a comment...

Richard Green

Shared publicly  - 
 
Daughter 1 (aged 11) took this photo of a grasshopper outside our house yesterday. I was impressed that she managed to take such a good picture using her iPad.
166
7
Aaron Godolphin's profile photoAlexander Bogomolny's profile photoCHASING ORGASM Roland J. Ruttledge's profile photograham booys's profile photo
23 comments
 
WOW !!Pics are amazing!U should be proud of ur daughter she is talented at 1!
Add a comment...

Richard Green

Shared publicly  - 
 
The onion decomposition of a network

The onion decomposition of a network is a recently introduced network fingerprinting technique. It can be used to identify structural properties of a network, such as ”tree-like” structure, ”loopy” structure, or the property of having an ”interesting“ sub-network.

Examples of networks that can be analysed in this way include purely mathematical networks; physical networks like transportation networks and power grids; and social networks such as collaboration graphs. The picture shows three mathematical networks: (a) the Cayley tree, in which all but the terminal nodes are connected to exactly three other nodes; (b) the Erdős–Rényi random graph; and (c) the square lattice, in which each node not on the boundary of the network is connected to exactly four others.

Under the picture of each network is its onion spectrum. This can be thought of as a summary of the onion decomposition of the network, which we describe below. The number and nature of the pieces of the onion spectrum can be used to gain insight into the structure of the original network.

The onion decomposition was defined a few months ago in the paper Network structure at multiple scales via a new network statistic: the onion decomposition by Laurent Hébert-Dufresne, Joshua A. Grochow, and Antoine Allard (http://arxiv.org/abs/1510.08542), and the picture shown here comes from that paper. The decomposition is a refinement of the previously known k-core decomposition, and it is called the onion decomposition because it is reminiscent of peeling an onion.

To explain how this works, we use concepts from graph theory. A graph is a mathematical object that can be used to model a network. A graph consists of a set of nodes, called vertices, and a set of edges, which connect pairs of vertices. We do not allow our graphs to contain more than one edge connecting the same pair of vertices, or to have any edges that connect a vertex to itself. The degree of a vertex is the number of edges emanating from it.

To decompose a graph, one first removes all vertices of degree zero (isolated points); these vertices form the 0-shell of the graph. To form the 1-shell, one removes all vertices of degree 1, followed by all the vertices that become vertices of degree 1 as a result of this process, then iterating the procedure again and again until there are no more vertices of degree 0 or 1. The vertices that are removed at each iteration of the construction of the 1-shell are called the layers of the 1-shell. The construction of the 2-shell (and higher shells) follows a similar procedure: at each iteration, one removes all vertices of degree 2 or lower, until this is no longer possible.

The onion spectrum shown in the picture shows the relative abundance of vertices in each layer within each shell of the corresponding graph. Each connected piece of the picture is shown in a different colour and corresponds to a shell, and each dot corresponds to each successive layer of that shell. The vertical scale is logarithmic, which means that a straight line corresponds to exponential behaviour. The meaning of the colours in the pictures of the actual networks is different: the size of a vertex corresponds to its degree, and the colour of a vertex shows whether it is shallow or deep in the network. The original k-core decomposition gives less information, because it only keeps track of the k-shells, and not the layers within each shell.

The paper shows how to use the onion spectrum to read off properties of the original network. Exponential decay in the spectrum, like in the Cayley tree case, is indicative of the graph having a tree-like structure, whereas sub-exponential decay, like in the random graph case, suggests that the graph has a lot of circuits. It is a nice exercise to show that the Cayley tree consists of one big 1-shell, and the square lattice consists of one big 2-shell; it follows from this that the onion spectrum of each graph has only one connected component. 

Networks like these last two, whose onion spectrum has fewer components than a random graph, tend to be disassortative, which means that nodes tend to be connected to nodes that are somehow ”unlike” themselves. One way to illustrate this is to colour the vertices of the square lattice in alternating colours, like a chess board; something analogous can be done for the Cayley tree. 

Conversely, a network with more components than a random graph will tend to be assortative, meaning that nodes tend to be connected to nodes that are somehow like themselves. A good example of this that is studied in the paper is the collaboration graph of condensed matter physics papers on the arXiv preprint server. Some other real world graphs that are studied are the graph of a power grid, which is tree-like and assortative, and the network of roads in Pennsylvania. The road network graph has one particular shell that exhibits a change in its decay rate, which is indicative of the network having an interesting sub-network. In fact, the road system consists of several essentially isolated components.

Relevant links

Here's another post by me about assortative and disassortative networks: https://plus.google.com/101584889282878921052/posts/cHo5dMTQdsW
That post links to two other relevant posts by me, whose links I provide below for convenience.

A post by me about the mathematics of social networks: https://plus.google.com/101584889282878921052/posts/YV7j9LRqKsX

A post by me about the random graph: https://plus.google.com/101584889282878921052/posts/34guwy4ftWX

Wikipedia has more information about k-cores on its page about degeneracy in graph theory: https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)

I'm glad that Google has fixed the discouraging bug that was corrupting the plus-one counts of posts. On the negative side, it looks like the selectedpapers.net site (which was associated with the spnetwork hashtag) is no more. Can anyone confirm or deny this?

#mathematics #sciencesunday  
288
96
Nigil Haroon's profile photoShirley Sprague's profile photokishore tewary's profile photoAndrew Swann's profile photo
29 comments
 
This a good game

Add a comment...

Richard Green

Shared publicly  - 
 
The sandpile model with a billion grains of sand

This picture by Wesley Pegden shows an example of a stable configuration in the abelian sandpile model on a square lattice. This consists of a rectangular square array of a large number of pixels. Each pixel has one of four possible colours (blue, cyan, yellow and maroon) corresponding to the numbers 0, 1, 2 and 3 respectively. These numbers should be thought of as representing stacks of tokens, often called chips, which in this case might be grains of sand.

Despite its intricate fractal structure, this picture is generated by a simple iterative process, as follows. If a vertex of the grid (i.e., one of pixels) holds at least 4 chips, it is allowed to fire, meaning that it transfers one chip to each of its neighbours to the north, south, east and west. The boundary of the grid can be thought of as the edge of a cliff, meaning that any chips that cross the boundary will fall off and be lost. If no vertices can fire in a particular chip configuration, then the configuration is called stable. For example, the configuration in the picture is stable, because no pixel holds 4 or more chips.

One of the key theorems about this particular sandpile model is that any chip configuration will become stable after firing various vertices a finite number of times. More surprisingly, the ultimate stable configuration obtained does not depend on the order in which the vertices were fired. The irrelevance of the order in which the vertices are fired is why the model is called “abelian”.

If we start with 2^{30} chips, all placed on the same pixel, and we then perform firings repeatedly until a stable configuration is reached, the resulting stable configuration is the one shown in the picture. (The number 2^{30} is just over a billion.) It is clear from the symmetrical nature of the firing rules that the resulting picture will be symmetric under rotation by a right angle or mirror-reflection, but the fractal-like structures are much more surprising.

Relevant links

Wesley Pegden is an Assistant Professor of Mathematics at Carnegie Mellon University. His home page includes an interactive zoomable version of this image: http://www.math.cmu.edu/~wes/sand.html
The page also allows you to generate corresponding images on other lattices, including a triangular lattice with six colours, and a hexagonal lattice with three colours. You can also change the number of chips, like Dr Evil from Austin Powers. (One billion chips. No, one million chips.)

The article The Amazing, Autotuning Sandpile by Jordan Ellenberg appeared in Nautilus in April 2015: http://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile
The article discusses this picture, and also includes some details from it, including a close-up of the centre.

I have posted about the sandpile model before, here: https://plus.google.com/101584889282878921052/posts/QezmLcTCTMJ
The other post includes more technical details, and describes how to construct a group out of certain sandpiles. A surprising feature of this is that the identity element of the group has a very complicated appearance.

David Perkinson is a Professor of Mathematics at Reed College. He has a gallery of images relating to abelian sandpiles: http://people.reed.edu/~davidp/sand/gallery/gallery.html

(Found via Cliff Pickover (@pickover) on Twitter.)

#mathematics #scienceeveryday
453
84
fizixx's profile photoUTSAV DEWAN's profile photo
68 comments
 
Brilliant stuff, thanks a lot for sharing Sir..
Add a comment...

Richard Green

Shared publicly  - 
 
Here's a sunrise shot from my walk yesterday morning near my house in Longmont, Colorado. As usual, this was taken with my iPhone 5 and processed in Snapseed.

I have had a lack of good material for posts recently, but I am still hoping this is about to change.

#snapseed

267
19
altimira jordão's profile photoPatrizia Melis's profile photoAchan Maureen's profile photoLynette Dorling's profile photo
42 comments
 
I want to live in Longmont, Colorado! It's gorgeous there.
Add a comment...

Richard Green

Shared publicly  - 
 
Here's a picture I took yesterday near my house in Longmont, Colorado. I think this flower is a black-eyed susan (Rudbeckia hirta); does anyone know for sure? I took the picture with my iPhone 5 and edited it with Snapseed.

More information on this species is here: https://en.wikipedia.org/wiki/Rudbeckia_hirta

I'm sorry I haven't posted much recently; I plan to do better.

#floralfriday #snapseed
186
14
Trever McGhee's profile photoRaina R.'s profile photoRichard Green's profile photoEdith Kukla's profile photo
28 comments
 
Lovely photo +Richard Green :-))) 
Add a comment...

Richard Green

Shared publicly  - 
 
While we were watching Guardians of the Galaxy for the N-th time yesterday, Daughter 1 (aged 11) drew this picture of Groot, which I really like.

I expect that there will be comments below that say I am Groot, so I'm going to get that out of the way now by saying it myself.

#art #guardiansofthegalaxy #groot
206
5
Angela  Mack's profile photoSean Walker's profile photoNigil Haroon's profile photoK.M Cantrell's profile photo
46 comments
 
+Sean Walker I was going to say that as well for the variety of it. Since Groot dose say that were all Groot when he (shelters them) right before he dose what I call his pheniox moment.
Add a comment...

Richard Green

Shared publicly  - 
 
Fractals, Fibonacci, and factorizations

The rule for generating the famous Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, ... is that each number (after the first two) is the sum of the previous two numbers. The Fibonacci word is an infinite string of zeros and ones with properties reminiscent of the Fibonacci sequence, and the Fibonacci fractal, shown in the picture, is a way to represent the Fibonacci word in the form of a fractal.

One way to generate the Fibonacci word is to define strings of zeros and ones by the rules S(0)=0, S(1)=01 and S(n)=S(n–1)S(n–2) when n is at least 2. This gives rise to the sequence of strings 0, 01, 010, 01001, 01001010, 0100101001001, ..., whose limit, as n tends to infinity, is the Fibonacci word. There are other equivalent, but superficially very different, ways to generate this word, including (a) using an explicit formula for each digit given in terms of the golden ratio; (b) using a substitution rule; and (c) using the Zeckendorf representation of integers in terms of Fibonacci numbers.

By suitably interpreting the digits of the Fibonacci word as turtle graphics instructions in a Logo-like programming language, it is possible to represent the word as a fractal. More precisely, if one reads the digits in order, then the n-th digit corresponds to the following sequence of instructions:
1. draw a segment forwards;
2. if the digit is 0, then turn left 90 degrees is n is even, and turn right 90 degrees if n is odd.

The picture shows the result of this procedure after many iterations. The resulting curve has various interesting mathematical properties, some of which concern the square-shaped gaps. By inspection, we count one large square gap (in the middle, at the bottom); five smaller square gaps, and 21 square gaps of the next size down. The numbers of these gaps, sorted by size, turn out to be given by every third Fibonacci number starting with the second 1 (1, 5, 21, 89...) which means that there are 89 squares of the next size down. Furthermore, each square has a side length that is 1+√2 times the side length of the square of the next size down; the number 1+√2 is known as the silver ratio.

The recent paper Factorizations of the Fibonacci Infinite Word by Gabriele Fici (http://arxiv.org/abs/1508.06754) surveys some factorizations of the Fibonacci word and shows how to derive these factorizations using elementary properties of the Fibonacci numbers. In some cases, this gives easier derivations of the results than were previously known. An example of such a factorization involves the sequences S(n) from earlier. Proposition 1 of the paper proves that the Fibonacci word can be factorized as the infinite product 0.1.S(0).S(1).S(2)..., where the symbol . is used to separate the factors.

One of the most surprising factorizations in the paper is Proposition 9, which involves the reversals, T(n), of the strings S(n). The strings T(0), T(1) and so on are then given by the sequence 0, 10, 010, 10010, 01010010, ... Remarkably, the concatenation of the strings T(n) also gives the Fibonacci word, even though the ingredients being used to construct it are backwards and generally not palindromic. Another way to say this is that the Fibonacci word can be factorized as the infinite product T(0).T(1).T(2)...

Relevant links

The 2009 paper The Fibonacci Word fractal by Alexis Monnerot-Dumaine is an excellent guide to the mathematical properties of the fractal, and the picture of the fractal here comes from that paper. You can download the paper for free at https://hal.archives-ouvertes.fr/hal-00367972/document 
Monnerot-Dumaine's paper explains how to construct the Fibonacci word using a substitution rule, and explores what the fractal looks like if one makes turns at angles other than a right angle. 

Fici's paper explains how to construct the word using the Zeckendorf representation of natural numbers. It is a theorem that any positive integer can be expressed uniquely as the sum of one or more distinct non-consecutive Fibonacci numbers. This is called Zeckendorf's Theorem, even though Zeckendorf was not the first to prove it: https://en.wikipedia.org/wiki/Zeckendorf's_theorem

Wikipedia's article on the Fibonacci word gives an explicit formula for the n-th digit of the word and mentions many other interesting properties. For example, the Fibonacci word is often cited as the worst case for algorithms detecting repetitions in a string. https://en.wikipedia.org/wiki/Fibonacci_word

The On-Line Encyclopedia of Integer Sequences on the Fibonacci word: https://oeis.org/A003849

Wikipedia on turtle graphics: https://en.wikipedia.org/wiki/Turtle_graphics

I have posted about the Fibonacci word twice before, although not recently. 
My post from March 2013 discusses the word in the context of self-shuffling words: https://plus.google.com/101584889282878921052/posts/YnUkZ986LMM
My post from December 2012 discusses Fibonacci snowflakes and some generalizations of the Fibonacci word: https://plus.google.com/101584889282878921052/posts/KSuUFJV6tyv

If you're disappointed that I didn't talk about the golden ratio, have a look at the aspect ratio of the accompanying picture.

#mathematics #sciencesunday #spnetwork arXiv:1508.06754
414
113
Emily Fett's profile photofizixx's profile photoKameron Bodtke's profile photoHatice Serbest's profile photo
55 comments
 
Brilliance thank you for sharing.
Add a comment...
Richard's Collections
People
Have him in circles
115,143 people
Giang Nam's profile photo
ARPAN MISTRY's profile photo
Skeleton_Play - PvP & Random's profile photo
Garfield Rocha's profile photo
Heather Deere's profile photo
Thanuja Dhananjaya's profile photo
Traditional story's profile photo
Isabelle Fritts's profile photo
Ramlan Setiawan's profile photo
Work
Occupation
professor of mathematics
Skills
pedantry
Employment
  • University of Colorado Boulder
    Professor of Mathematics, present
  • Vodafone
  • Oxford University
    Postdoctoral Research Assistant, 1995 - 1997
  • Lancaster University
    Lecturer in Pure Mathematics, 1997 - 2003
  • Colorado State University
    Visiting Assistant Professor of Mathematics, 2001 - 2001
Places
Map of the places this user has livedMap of the places this user has livedMap of the places this user has lived
Currently
Longmont, Colorado
Previously
Winnipeg, Manitoba, Canada - Southampton, England - Middlesbrough, England - Nairobi, Kenya - Zomba, Malawi - Manzini, Swaziland - Oxford, England - Newbury, England - Leamington Spa, England - Coventry, England - Lancaster, England - Fort Collins, Colorado, USA
Story
Tagline
mathematician and father of twins
Introduction
I'm a professor of mathematics at the University of Colorado Boulder, interested mainly in algebra and combinatorics. 

Some of the best posts in my Google+ stream are those with the #mathematics tag.  My aim in these is to explain both new and historically interesting mathematical ideas to a general audience, and to produce posts that can be enjoyed on various levels.  My posts with the most reshares are often posts of this type.

Some of my non-mathematical posts are commentary on other people's photography and works of art, or various photos I took.

I am unlikely to give +1s to the following material:

(1) extreme sports;

(2) pictures of spiders;

(3) pornography;

(4) posts that can't spell “its”.

My main aim on Google+ is to post about difficult topics and still get decent amounts of engagement. I try to keep the quality of my posts as high as I can, and I'm not interested in trying to get vast numbers of +1s. Sometimes I post pictures of cats and dogs, but they're usually photographs I took. I don't always post gifs, but when I do, they're often gifs I created, either from scratch or from someone else's video. I don't usually post poorly executed or out of focus pictures, however amusing they are. Whatever I post, I try to include interesting commentary on it, and I'm careful to try to assign credit. I never want someone to feel that I stole their work with my post.

In the 90s, I wrote a Multi-User Dungeon called "Island."  I was once described by Stephen Fry as "sick".

Some other topics I may post about on occasion include the Beatles, British comedy, chess, linguistics, music theory, science in general, Star Trek, and Tolkien.
Bragging rights
I'm the author of "Combinatorics of Minuscule Representations", a book published by Cambridge University Press. I have graduated six PhD students.
Education
  • University College, Oxford
    BA (MA), mathematics, 1989 - 1992
  • University of Warwick
    MSc/PhD, mathematics, 1992 - 1995
  • St Bernadette's RC Primary School, Middlesbrough
  • Kestrel Manor School, Nairobi
  • Sir Harry Johnston Primary School, Zomba
Basic Information
Gender
Male
Birthday
February 10
Other names
R.M. Green