Test CircleCount PRO now!
Login now

Not your profile? Login and get free access to your reports and analysis.

Tags

Sign in

The following tags have been added by users of CircleCount.com.
You can login on CircleCount to add more tags here.

  • Mathematics

Are you missing a tag in the list of available tags? You can suggest new tags here.

Login now

Do you want to see a more detailed chart? Check your settings and define your favorite chart type.

Or click here to get the detailed chart only once.

Richard Green has been at 2 events

HostFollowersTitleDateGuestsLinks
Science on Google+902,850Join mathematicians Dana Ernst , Sara Del Valle , Vincent Knight , Luis Guzman  and Robert Jacobson  as they talk with Amy Robinson  about their favorite math gifs and ideas and what it's like to be a mathematician. How many numbers are there? Do mathematicians see the world differently? And why is the last panel of this xkcd comic funny? http://xkcd.com/804/ +Dana Ernst   is an assistant professor in the Department of Mathematics and Statistics at Northern Arizona University in Flagstaff, AZ, USA.  +Sara Del Valle   is a mathematical epidemiologist at Los Alamos National Laboratory in Los Alamos, NM, USA. +Vincent Knight   is a LANCS lecturer at the Cardiff University School of Mathematics in Operational Research in Cardiff, Wales, UK. +Luis Guzman   is a graduate student in mathematics at the University of West Florida in FL, USA. +Robert Jacobson   is Assistant Professor of Mathematics at Roger Williams University in RI, USA. Hangout hosted by Science on Google+'s +Amy Robinson Math: from GIFs to xkcd2013-11-22 02:00:0064  
Science on Google+902,850We will be updating and sharing this General Science Page Circle (see http://goo.gl/9muuE) on Tuesday (10/9) at 9:00 PM (EST). Please add your Science Page to this database (http://goo.gl/WCohT) if you would like to add your page to the circle. Here's the form: http://goo.gl/bfqHa. You do not have to fill out the form if you are already in the database. Here's the link to the updated Science Page circle, http://goo.gl/aGQPB.Science Page Circle2012-10-10 03:00:00133  

Shared Circles including Richard Green

Shared Circles are not available on Google+ anymore, but you can find them still here.

The Google+ Collections of Richard Green

New!
Login and checkout your own profile to see the average response per collection.
Or check out how it looks like on the profile page of +CircleCount.

Looks like this is your profile but we haven't loaded your posts yet to show you here the average numbers per collection.
Just open your dashboard and let the server work for you.

Top posts in the last 50 posts

Most comments: 99

posted image

2015-05-16 17:18:14 (99 comments; 47 reshares; 1,418 +1s; )Open 

For #caturday, here's my sister's British Blue Shorthair cat, Aslan. You can find out more about the breed here: http://en.wikipedia.org/wiki/British_Shorthair

Most reshares: 136

posted image

2015-02-22 20:38:12 (85 comments; 136 reshares; 311 +1s; )Open 

A matter of scale

I'm not usually much of a fan of the Fahrenheit scale, but as this graphic illustrates, it does produce convenient numbers for the purposes of discussing the weather.

(Image credit unknown; Googling it produces many hits.)

#sciencesunday


Most plusones: 1418

posted image

2015-05-16 17:18:14 (99 comments; 47 reshares; 1,418 +1s; )Open 

For #caturday, here's my sister's British Blue Shorthair cat, Aslan. You can find out more about the breed here: http://en.wikipedia.org/wiki/British_Shorthair

Latest 50 posts

posted image

2017-06-08 20:34:52 (6 comments; 1 reshares; 62 +1s; )Open 

Here's a picture I took in April during my visit to Estes Park, Colorado. I think it shows some interesting details when viewed in full screen mode.

Here's a picture I took in April during my visit to Estes Park, Colorado. I think it shows some interesting details when viewed in full screen mode.___

posted image

2017-06-07 21:12:43 (24 comments; 22 reshares; 150 +1s; )Open 

Self-similar polygonal tilings

This picture, by Michael Barnsley and Andrew Vince, shows a self-similar polygonal tiling. These tilings of the plane are reminiscent of the more well known Penrose tilings, although their properties are somewhat different. Barnsley and Vince have many more examples of these tilings in their paper Self-Similar Polygonal Tiling (https://arxiv.org/abs/1611.02218) from November 2016.

The tiling in the picture is a tiling of order 2, which means that there are two different sizes of tiles. All the tiles of a given size are congruent, which means that they are the same shape, or more precisely, that any of them can be transformed into any of the others by a combination of reflections, rotations, and translations. Another important feature of this particular tiling is that all the tiles are similar. This means that the... more »

Self-similar polygonal tilings

This picture, by Michael Barnsley and Andrew Vince, shows a self-similar polygonal tiling. These tilings of the plane are reminiscent of the more well known Penrose tilings, although their properties are somewhat different. Barnsley and Vince have many more examples of these tilings in their paper Self-Similar Polygonal Tiling (https://arxiv.org/abs/1611.02218) from November 2016.

The tiling in the picture is a tiling of order 2, which means that there are two different sizes of tiles. All the tiles of a given size are congruent, which means that they are the same shape, or more precisely, that any of them can be transformed into any of the others by a combination of reflections, rotations, and translations. Another important feature of this particular tiling is that all the tiles are similar. This means that the large tiles are simply scaled versions of the small tiles; more precisely, by enlarging by an appropriate scale factor, any of the tiles can be transformed into a tile that is congruent to any of the others.

A tiling is said to be self-similar if it is possible to transform the tiling using a combination of enlargements, reflections, rotations and translations in such a way that the enlarged tiling fits neatly over the original tiling, in the sense that each enlarged tile is a union of some of the original tiles. It is not generally possible to see if a tiling has this property just from looking at a partial picture, like the one shown here.

A tiling is said to be quasiperiodic if, given any patch of tiles, there exists a (possibly large) number R with the property that any disc of radius R in the tiling contains a copy of the patch, up to congruence (i.e., up to reflections, rotations, and translations).

Finally, a self-similar polygonal tiling is a tiling of the plane by similar polygons that is (a) self-similar, (2) quasiperiodic, and (3) of finite order. The authors are interested in the situation in which the tiles can be pieced together to make a larger copy of the same tile, and in which there exists a constant s with the property that the size ratio between any two tiles is an integer power of s. The main result of the paper (Theorem 4.1) shows that, in this situation, there are infinitely many different ways to construct a self-similar polygonal tiling with those particular tiles.

The authors are also interested in tilings using a polygon known as the golden bee. This polygon is shaped roughly like a lower case letter b, and it has the distinction of being the only polygon (other than a non-isosceles right triangle) that can be partitioned into a pair of non-congruent scaled copies of itself. The word golden refers to the fact that the golden ratio plays an important role in the dimensions of the polygon. Perhaps not surprisingly, the tilings arising from the golden bee polygon have close connections to the Fibonacci sequence.

I've posted about tilings several times before; one such post, which links
to another, is here: https://plus.google.com/101584889282878921052/posts/dhPpRnwNmsR

People have been complaining that I haven't posted for a very long time, for which I apologise!

#mathematics #scienceeveryday
___

posted image

2016-10-18 21:34:43 (33 comments; 9 reshares; 200 +1s; )Open 

I saw this aspen tree earlier this month when I was walking my dogs near Altona Middle School in Longmont, Colorado. I think the picture looks a bit like it has failed a red-green colour blindness test, although this is an accurate depiction of what it actually looked like.

The picture was taken with my iPhone 5. The phone is wearing out, although the camera still works well.

#treetuesday

I saw this aspen tree earlier this month when I was walking my dogs near Altona Middle School in Longmont, Colorado. I think the picture looks a bit like it has failed a red-green colour blindness test, although this is an accurate depiction of what it actually looked like.

The picture was taken with my iPhone 5. The phone is wearing out, although the camera still works well.

#treetuesday___

posted image

2016-10-11 16:52:17 (21 comments; 7 reshares; 155 +1s; )Open 

Here's a picture I took back in August of an owl that was temporarily living in our weeping willow. The squirrels and our dogs were not happy with this arrangement, but the owl only stayed a few days.

#treetuesday   #birds  

Here's a picture I took back in August of an owl that was temporarily living in our weeping willow. The squirrels and our dogs were not happy with this arrangement, but the owl only stayed a few days.

#treetuesday   #birds  ___

posted image

2016-09-24 19:13:13 (17 comments; 1 reshares; 101 +1s; )Open 

For #caturday, here is our cat Lily. Lily is three months old, and we adopted her from Longmont Humane Society.

This picture was taken by Daughter 1 with her iPhone 5, and edited by her using Snapseed.

For #caturday, here is our cat Lily. Lily is three months old, and we adopted her from Longmont Humane Society.

This picture was taken by Daughter 1 with her iPhone 5, and edited by her using Snapseed.___

posted image

2016-09-23 21:56:15 (39 comments; 33 reshares; 287 +1s; )Open 

Knot mosaics

This picture by Samuel J. Lomonaco Jr and Louis H. Kauffman gives some examples of knot mosaics. A knot mosaic is the result of tiling a rectangular grid using the 11 types of symbols listed in the diagram, in such a way that (a) the connection points between adjacent tiles are compatible, and (b) there are no connection points on the outer boundary of the rectangle.

A natural combinatorial question is: how many ways are there to inscribe a knot mosaic in a rectangular grid of a given size? To make things slightly easier, we may assume that the grid is an n by n square, rather than an m by n rectangle. For a 1 by 1 grid, we have no choice other than to use the blank tile. For a 2 by 2 grid, we can either use four blank tiles, or we can arrange four tiles to draw a circle in the middle of the grid. For a 3 by 3 grid, there are a lot more... more »

Knot mosaics

This picture by Samuel J. Lomonaco Jr and Louis H. Kauffman gives some examples of knot mosaics. A knot mosaic is the result of tiling a rectangular grid using the 11 types of symbols listed in the diagram, in such a way that (a) the connection points between adjacent tiles are compatible, and (b) there are no connection points on the outer boundary of the rectangle.

A natural combinatorial question is: how many ways are there to inscribe a knot mosaic in a rectangular grid of a given size? To make things slightly easier, we may assume that the grid is an n by n square, rather than an m by n rectangle. For a 1 by 1 grid, we have no choice other than to use the blank tile. For a 2 by 2 grid, we can either use four blank tiles, or we can arrange four tiles to draw a circle in the middle of the grid. For a 3 by 3 grid, there are a lot more possibilities: it turns out that there are 22 in all. As n increases, the number of knot mosaics grows very quickly. The first few values are 1, 2, 22, 2594, 4183954 and 101393411126.

To get an idea for how quickly this sequence might be growing, consider the much easier problem of filling a square grid with tiles that do not have to fit together compatibly at their edges. There are 11 types of tiles, and n^2 spaces in the grid, so the total number of ways to fill the grid is 11 to the power n^2. The great majority of these do not lead to knot mosaics, but the recent paper Quantum knot mosaics and the growth constant by Seungsang Oh (http://arxiv.org/abs/1609.00517) proves that there exists a constant δ, called the knot mosaic constant, with the property that the number of knot mosaics in an n by n grid, for large n, is approximately δ to the power n^2. Because there are 11 types of tiles, it follows immediately that δ must be less than 11. The paper gives a much better estimate, namely that δ lies between 4 and 4.303.

Although knot mosaics might seem like an isolated curiosity, they have applications to knot theory and quantum physics. If one imagines the left and middle knot mosaics in the diagram as physical loops made out of an elastic material, it is possible to see that it would be possible to deform one of these links into the other without breaking the material. Mathematically, there is an operation on knot mosaics that has the effect of interchanging these two knots. However, the third knot turns out not to be equivalent to the others, in a way that can be made mathematically precise.

In their 2008 paper Quantum Knots and Mosaics (https://arxiv.org/abs/0805.0339) Lomonaco and Kauffman use the knot mosaics as a basis for a Hilbert space called the quantum knot state space. The paper defines a group of symmetries generated by mosaic versions of the Reidemeister moves and mosaic versions of planar isotopies, and this group acts on the mosaics. The Hilbert space is meant to capture the quantum embodiment of a closed knotted physical piece of rope, and the group represents all the possible ways to move the rope around, without cutting it or letting it pass through itself. However, unlike classical knotted pieces of rope, quantum knots can model superpositions of several pieces of rope, as well as quantum entanglements.

Relevant links

The picture comes from the arXiv version of Lomonaco and Kauffman's paper.

The On-Line Encyclopedia of Integer Sequences has a longer list of values for the numbers of n by n knot mosaics. This one goes up to 11: http://oeis.org/A261400

Here's another post by me with more details on the Reidemeister moves: https://plus.google.com/101584889282878921052/posts/4e4STv3FLa4

#mathematics #scienceeveryday___

posted image

2016-08-18 00:06:25 (50 comments; 56 reshares; 383 +1s; )Open 

Primes in the Gaussian integers

This picture by Oliver Knill shows the prime numbers in the Gaussian integers. A Gaussian integer is a complex number of the form a + bi, where a and b are integers and i is a square root of –1.

An important result about the ordinary integers is the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 can be expressed as a product of prime numbers in an essentially unique way. For example, the integer 21 can be written as 3 x 7, or 7 x 3, or (–3)x(–7), or (–7)x(–3). However, these factorizations are essentially the same, in the sense that they differ only in the order of the factors and by multiplication by +1 or –1. The numbers +1 and –1 are called units, which means that they are the only integers z for which 1/z is also an integer.

An integer c can be defined to be primeif it is not ... more »

Primes in the Gaussian integers

This picture by Oliver Knill shows the prime numbers in the Gaussian integers. A Gaussian integer is a complex number of the form a + bi, where a and b are integers and i is a square root of –1.

An important result about the ordinary integers is the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 can be expressed as a product of prime numbers in an essentially unique way. For example, the integer 21 can be written as 3 x 7, or 7 x 3, or (–3)x(–7), or (–7)x(–3). However, these factorizations are essentially the same, in the sense that they differ only in the order of the factors and by multiplication by +1 or –1. The numbers +1 and –1 are called units, which means that they are the only integers z for which 1/z is also an integer.

An integer c can be defined to be prime if it is not zero or a unit, but the only way to factorize c = ab is for either a or b to be a unit. If c is an integer bigger than 1, then this is equivalent to the familiar definition of prime, namely that the number has no factors other than 1 and itself. The negatives of prime numbers (such as –3 and –7, as above) also satisfy the definition of prime. However, the units +1 and –1 are not defined to be prime, because this would cause problems; for example, the Fundamental Theorem of Arithmetic would be false as stated.

It turns out, somewhat remarkably, that the analogue of the Fundamental Theorem of Arithmetic also holds for the Gaussian integers, which means that the Gaussian integers have a unique factorization property. It can be shown that the only units in the Gaussian integers are the numbers 1, i, –1 and –i; in other words, these are the only Gaussian integers z for which 1/z is also a Gaussian integer. Some primes in the ordinary sense, like 7 and 11, are also prime in the Gaussian integers. However, other primes, like 2 and 5, are not prime when regarded as Gaussian integers: they can be factorized further as 2 = (1+i)(1–i) and 5 = (1+2i)(1–2i), and none of the factors is a unit. It is also possible to write 5 = (2–i)(2+i), but this is essentially the same as the previous factorization because the factors are unit multiples of the previous factors. (More precisely: we have 2–i = (–i)(1+2i) and 2+i = (i)(1–2i), where –i and i are both units.)

The picture plots the locations of the primes in the Gaussian integers. The prime numbers in the integers that remain prime in the Gaussian integers, such as 3, 7, 11 and 19, appear on the positive horizontal axis as the points (3,0), (7,0), (11,0) and (19,0). These are the prime numbers that congruent to 3 modulo 4; in other words, they leave a remainder of 3 when divided by 4. The entire picture is symmetric under rotation by a right angle, because a unit multiple of a prime is always a prime, and multiplying by the complex number i rotates the complex plane anticlockwise by a right angle.

In light brown, near the origin, we have the primes 1+i, 1–i, –1+i, and –1–i. These are the four primes that are factors of 2 = (1+i)(1–i). A knight's move from the origin, we have the eight primes (2+i), (1+2i), (–1+2i), (–2+i) and their negatives; these are the primes that are factors of 5, and we find the same behaviour for factors of a prime integer p whenever p is congruent to 1 modulo 4.

The Gaussian primes are closely related to the problem of writing a number as a sum of two squares. Pierre de Fermat proved 1640 that if a prime is congruent to 1 mod 4, then it can always be written as a sum of two squares; for example, 13 = 9 + 4 = 3^2 + 2^2, and 29 = 25 + 4 = 5^2 + 2^2. (As usual, Fermat did not bother to provide a proof of this result; the first rigorous proof was provided by Euler in the 1740s.) The problem of factorizing ordinary primes in the Gaussian integers is essentially the same: 13 = (3+2i)(3–2i) and 29 = (5+2i)(5–2i).

Relevant links

The picture appears in Knill's paper Goldbach for Gaussian, Hurwitz, Octavian and Eisenstein primes (http://arxiv.org/abs/1606.05958), which, among other things, formulates a version of the Goldbach conjecture for Gaussian integers. Chapter 4 of the paper considers some more surprising questions, such as the frogger problem, which asks what happens if we think of the picture as a scenario in the popular 1980s computer game Frogger.

Another paper by Knill on a similar topic is the 71-page Some experiments in number theory (http://arxiv.org/abs/1606.05971). Chapter 14 of that paper conjectures that if one runs Conway's Game of Life on the picture shown, then there is motion arbitrarily far from the origin. Knill has a website on these topics at http://math.harvard.edu/~knill/primes/

Wikipedia has more information about the Gaussian integers here: https://en.wikipedia.org/wiki/Gaussian_integer

Here's another post by me about the Gaussian integers in the work of my colleague Katherine Stange: https://plus.google.com/101584889282878921052/posts/eM3adto6nsj

I thank +Owen Maresh for bringing some of these links to my attention in his post from June. I have been extremely busy for the last seven months, which is why I have barely posted, but this is no longer the case, so you can expect a decent level of output from me in the coming months.

#mathematics #scienceeveryday  ___

posted image

2016-05-23 20:45:22 (33 comments; 5 reshares; 149 +1s; )Open 

I've been criticised in the past for not posting enough pictures of my dogs. Here's a recent picture of my dog Luna, which my stepson took with his Samsung Galaxy phone.

The camera on his phone is sufficiently good that I'm tempted to switch to an Android phone. The drawback would be that my magic watch wouldn't work with it.

I've been criticised in the past for not posting enough pictures of my dogs. Here's a recent picture of my dog Luna, which my stepson took with his Samsung Galaxy phone.

The camera on his phone is sufficiently good that I'm tempted to switch to an Android phone. The drawback would be that my magic watch wouldn't work with it.___

posted image

2016-05-21 00:41:20 (17 comments; 5 reshares; 140 +1s; )Open 

For #floralfriday , here are some apple blossoms I saw while walking my dogs earlier this month. There are a lot more flowers than last year, which would be a good thing if anyone ever used the resulting apples.

This was taken with my iPhone 5 and edited with Snapseed. For contrast, my next post is likely to be a picture of one of the aforementioned dogs, taken with an Android phone.

For #floralfriday , here are some apple blossoms I saw while walking my dogs earlier this month. There are a lot more flowers than last year, which would be a good thing if anyone ever used the resulting apples.

This was taken with my iPhone 5 and edited with Snapseed. For contrast, my next post is likely to be a picture of one of the aforementioned dogs, taken with an Android phone.___

posted image

2016-05-19 19:29:40 (46 comments; 40 reshares; 304 +1s; )Open 

When does a random jigsaw puzzle have a unique solution?

Consider an n by n jigsaw puzzle, whose pieces have q different types of edges. If n is large, how big does q need to be so that the puzzle fits together in a unique way (up to rotation)? According to two recent papers, the answer is that q needs to be slightly greater than n.

A piece of a physical jigsaw puzzle has four edges, and two pieces match up if their edges lock together neatly. However, a mathematically equivalent way of thinking about this is to think of puzzle pieces as squares on which a picture has been drawn. From this point of view, two pieces lock together if it is possible to place the pieces next to each other along a common edge so that the picture matches up. The illustration shows what a picture might look like if cut up into squares and randomly rearranged. The question then becomes: how many... more »

When does a random jigsaw puzzle have a unique solution?

Consider an n by n jigsaw puzzle, whose pieces have q different types of edges. If n is large, how big does q need to be so that the puzzle fits together in a unique way (up to rotation)? According to two recent papers, the answer is that q needs to be slightly greater than n.

A piece of a physical jigsaw puzzle has four edges, and two pieces match up if their edges lock together neatly. However, a mathematically equivalent way of thinking about this is to think of puzzle pieces as squares on which a picture has been drawn. From this point of view, two pieces lock together if it is possible to place the pieces next to each other along a common edge so that the picture matches up. The illustration shows what a picture might look like if cut up into squares and randomly rearranged. The question then becomes: how many different types of edges are necessary so that the picture can be uniquely reconstructed from a randomly rearranged version?

If there are too few edge types, it is clearly impossible to reconstruct the puzzle uniquely. One degenerate case involves an n by n square puzzle with square pieces and a blank picture, which is the case q = 1. This puzzle looks the same scrambled up as it does when solved, so it can be reconstructed by reassembling the puzzle into any arrangement of pieces with the correct overall shape, and the solution is highly non-unique.

At the other extreme, if every pair of interlocking edges in a jigsaw puzzle is different from every other pair, then clearly the puzzle can be solved uniquely. For an n by n puzzle with square pieces, there is a total of 2n^2 - 2n pairs of edges that fit together in the interior of the puzzle, and a total of 4n single edges along the outer boundary. This is a total of 2n^2 + 2n types of edges, which means that if q is at least 2n^2 + 2n, the puzzle can be reconstructed in a unique way.

We have glossed over a technicality here, which is that, in a real jigsaw puzzle, the edges on the outer boundary are all the same shape: perfectly straight. This does not affect the mathematical argument, because as n gets very large, the fraction of puzzle pieces that are boundary pieces tends to zero.

The two extreme cases above show that q has to be at least 1 and at most 2n^2 + 2n. It turns out that we can do better than a bound of about 2n^2. In order for a random puzzle to have a high probability of being uniquely solvable, we just need q to be greater than n to the power 1 + ε, where ε is any small positive number. This result was proven recently in the recent paper Unique reconstruction threshold for random jigsaw puzzles (http://arxiv.org/abs/1605.03043) by Rajko Nenadov, Pascal Pfister, and Angelika Steger. The same result was proved independently (and on the same day!) in the paper Shotgun Assembly of Random Jigsaw Puzzles (http://arxiv.org/abs/1605.03086) by Charles Bordenave, Uriel Feige, and Elchanan Mossel.

The paper by Nenadov et al contains the additional result that if q is considerably smaller than n, then there is a high probability that the puzzle does not have a unique solution. Here, “considerably smaller” means that q = o(n), i.e. that the ratio q/n approaches zero when n tends to infinity.

Relevant links

Both the papers above were written as an answer to a question posed in the 2015 paper Shotgun assembly of labeled graphs (http://arxiv.org/abs/1504.07682) by Elchanan Mossel and Nathan Ross. The paper by Mossel and Ross considers a number of related questions, including the problem of reconstituting DNA from fragments, and the problem of reconstructing a big neural network from subnetworks that are observed in experiments.

The notation “q = o(n)” is called little-o notation. There are many variants of this concept, including big-O notation. More information on this can be found at https://en.wikipedia.org/wiki/Big_O_notation

The illustration comes from the paper Jigsaw Puzzles with Pieces of Unknown Orientation by Andrew C. Gallagher of the Eastman Kodak Research Laboratories.

(I apologise for not having posted for months. I was very busy at work.)

#mathematics #scienceeveryday___

posted image

2016-01-26 02:13:31 (15 comments; 4 reshares; 222 +1s; )Open 

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  

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  ___

posted image

2016-01-25 04:43:48 (34 comments; 109 reshares; 380 +1s; )Open 

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 eachnetwork is its ... more »

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  ___

posted image

2015-12-13 15:30:38 (81 comments; 101 reshares; 607 +1s; )Open 

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... more »

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___

posted image

2015-11-04 20:03:05 (71 comments; 89 reshares; 545 +1s; )Open 

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... more »

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___

posted image

2015-11-03 17:55:56 (35 comments; 28 reshares; 308 +1s; )Open 

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.

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.___

posted image

2015-10-19 13:28:21 (42 comments; 19 reshares; 286 +1s; )Open 

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


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
___

posted image

2015-10-03 02:23:16 (28 comments; 12 reshares; 200 +1s; )Open 

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

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___

posted image

2015-09-20 19:53:44 (41 comments; 112 reshares; 580 +1s; )Open 

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, thelargest kno... more »

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 ___

posted image

2015-09-08 19:53:00 (48 comments; 4 reshares; 209 +1s; )Open 

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

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___

posted image

2015-09-07 18:01:11 (42 comments; 59 reshares; 308 +1s; )Open 

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... more »

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___

posted image

2015-08-31 17:10:20 (23 comments; 6 reshares; 170 +1s; )Open 

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.

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.___

posted image

2015-08-30 13:05:19 (58 comments; 119 reshares; 443 +1s; )Open 

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 foreac... more »

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___

posted image

2015-08-16 16:41:35 (37 comments; 49 reshares; 314 +1s; )Open 

Keleti's Perimeter to Area Conjecture

It is clear that dividing the perimeter of a square of side 1 by its area results in a ratio of 4. Doing the same for two adjacent unit squares that share an edge results in a smaller ratio, in this case 3. So what can be said about this ratio in the case of an arbitrary union of (possibly overlapping) unit squares in the plane? Keleti's Perimeter to Area Conjecture was that this ratio never exceeds 4, although this is now known to be false. The picture shows a counterexample to the conjecture in which the ratio is approximately 4.28.

A problem related to this one appeared as Problem 6 on the famous Hungarian Schweitzer Competition in 1998. That problem asked for a proof that the perimeter-to-area ratio of a union of unit squares in the plane has an upper bound. Impressively, several Hungarian undergraduates were able to prove... more »

Keleti's Perimeter to Area Conjecture

It is clear that dividing the perimeter of a square of side 1 by its area results in a ratio of 4. Doing the same for two adjacent unit squares that share an edge results in a smaller ratio, in this case 3. So what can be said about this ratio in the case of an arbitrary union of (possibly overlapping) unit squares in the plane? Keleti's Perimeter to Area Conjecture was that this ratio never exceeds 4, although this is now known to be false. The picture shows a counterexample to the conjecture in which the ratio is approximately 4.28.

A problem related to this one appeared as Problem 6 on the famous Hungarian Schweitzer Competition in 1998. That problem asked for a proof that the perimeter-to-area ratio of a union of unit squares in the plane has an upper bound. Impressively, several Hungarian undergraduates were able to prove this for the competition. In the same year, Tamás Keleti published his Perimeter to Area Conjecture that the bound was exactly 4. This is now known to be incorrect; the best known bound is about 5.551 and was found by Keleti's student Zoltán Gyenes in his 2005 Master's thesis.

I found out about this problem from the paper Bounded – yes, but 4? (http://arxiv.org/abs/1507.08536) by Paul D. Humke, Cameron Marcott, Bjorn Mellem and Cole Stiegler. This paper was posted recently but is dated November 2013, and it does not mention progress on the problem that has been made since then. The 2014 paper Unions of regular polygons with large perimeter-to-area ratio (http://arxiv.org/abs/1402.5452) by Viktor Kiss and Zoltán Vidnyánszky proves that Keleti's conjecture is false. The picture here comes from Kiss and Vidnyánszky's paper.

The counterexample in the picture uses 25 unit squares, but Kiss and Vidnyánszky use a systematic method to construct (in Theorem 2.4) a counterexample using only five unit squares, and use an ad hoc method to construct (in Section 3) a counterexample using only four squares. They also (in Theorem 2.8) show that the analogue of Keleti's conjecture for equilateral triangles is false, by exhibiting a counterexample involving four triangles. The authors conjecture that similar constructions can be made for other regular polygons; more specifically, that their systematic method can be used to produce an analogous configuration of n+1 regular n-gons that has a greater perimeter-to-area ratio than a single regular n-gon. 

Kiss and Vidnyánszky pose a number of other interesting questions in their closing section. For example, is n the minimal possible number of n-gons in a counterexample? And does something analogous happen in three dimensions, with regular polyhedra?

Although Keleti's conjecture is false, it is known to be true under certain additional hypotheses. In his Master's thesis and in a 2011 paper, Gyenes proved that the conjecture holds (a) if the squares have a common centre, or (b) if all the squares have sides parallel to the x or y axes, or (c) if only two squares are involved.

Relevant links

Gyenes' Masters thesis: http://www.cs.elte.hu/~dom/z.pdf

A mathoverflow discussion of Keleti's Perimeter to Area Conjecture from 2010 (http://mathoverflow.net/questions/15188/) includes some interesting commentary on the problem from various people, including +Timothy Gowers.

The picture contains an oblique reference to Betteridge's law of headlines (https://en.wikipedia.org/wiki/Betteridge's_law_of_headlines) which states that Any headline that ends in a question mark can be answered by the word “no”. This principle also applies to the title of the paper by Humke et al. 

#mathematics #sciencesunday #spnetwork arXiv:1507.08536___

posted image

2015-07-30 23:27:29 (63 comments; 58 reshares; 286 +1s; )Open 

A hidden signal in the Ulam sequence

The Ulam sequence is a sequence of positive integers a_n, where a_1=1, a_2=2, and where each a_n for n > 2 is defined to be the smallest integer that can be expressed as the sum of two distinct earlier terms in a unique way.

The first few terms of the sequence are shown in the picture: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47. The third term is 3, because 3=1+2. The fourth term is 4, because although 4 can be expressed in two ways as the sum of two earlier terms (1+3, or 2+2) the sum “2+2” is not a sum of distinct earlier terms. The fifth term is not 5, because 5=1+4=2+3; rather, it is 6, which is 2+4. The sixth term is not 7, because 7=1+6=3+4, but rather 8, which is 2+6. And so on.

The Ulam sequence is named after the Polish-American mathematician Stanisław Ulam (1909–1984) who introduced it in1964 i... more »

A hidden signal in the Ulam sequence

The Ulam sequence is a sequence of positive integers a_n, where a_1=1, a_2=2, and where each a_n for n > 2 is defined to be the smallest integer that can be expressed as the sum of two distinct earlier terms in a unique way.

The first few terms of the sequence are shown in the picture: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47. The third term is 3, because 3=1+2. The fourth term is 4, because although 4 can be expressed in two ways as the sum of two earlier terms (1+3, or 2+2) the sum “2+2” is not a sum of distinct earlier terms. The fifth term is not 5, because 5=1+4=2+3; rather, it is 6, which is 2+4. The sixth term is not 7, because 7=1+6=3+4, but rather 8, which is 2+6. And so on.

The Ulam sequence is named after the Polish-American mathematician Stanisław Ulam (1909–1984) who introduced it in 1964 in a survey on unsolved problems. Ulam remarked that it can be notoriously difficult to answer questions about the properties of sequences like this one, even if they are defined by a simple rule. 

In particular, Ulam was interested in whether one could find the asymptotic density of this particular sequence. Roughly speaking, this is asking what proportion of the integers in between 1 and N are members of the Ulam sequence if N is very large. Empirically, the answer seems to be about 7.4%, but there is not even a proof that the density is bigger than Ulam's predicted value of zero. Ulam's sequence has been described as “quite erratic” and it has been said that it “does not appear to follow any recognizable pattern”. 

Even though the Ulam sequence has been around for 50 years, very little is known about it. However, the recent paper A Hidden Signal in the Ulam sequence by Stefan Steinerberger (http://arxiv.org/abs/1507.00267) unearths some surprisingly rigid structure in the sequence. In the context of Fourier series, it is natural to study the function f_N(x) obtained by summing the values of cos(a_n x) from n=1 to N. The expected result here is that whenever x is not zero, the absolute value of f_N(x) should be approximately equal to the square root of N. However, this is not what happens, because there is a mysterious constant α, equal to about 2.571, such that f_N(α) is approximately equal to c times N, for a negative constant c around –0.8.

The existence of such a constant can be thought of (metaphorically) as a signal embedded in the sequence. Steinerberger shows that the constant α is given by 2.5714474995...; there is another such constant at 2π–α by symmetry. The signal can be demonstrated in an elementary way by considering the values of cos(α a_n), measuring angles in radians: remarkably, with a very small number of exceptions, the values are all negative.

The paper also considers versions of the Ulam sequence in which the first two terms are replaced with other numbers, and similar phenomena occur. The case where a_1=2 and a_2=3 seems to be especially striking.

Relevant links

Stanisław Ulam was the bomb: he participated in the Manhattan Project and originated the Teller–Ulam design of thermonuclear weapons. He was also the chair of my department in Boulder in the 1960s. More information on Ulam can be found here: https://en.wikipedia.org/wiki/Stanislaw_Ulam

The On-Line Encyclopedia of Integer Sequences has more about the Ulam sequence: https://oeis.org/A002858

#mathematics #scienceeveryday #spnetwork arXiv:1507.00267___

posted image

2015-07-11 23:15:49 (24 comments; 31 reshares; 220 +1s; )Open 

Average pace and the Universal Chord Theorem

If you run a three-mile race at an average pace of six minutes per mile, it will always be the case that you ran for one consecutive mile in exactly six minutes. But if you run a 3.1-mile race at an average pace of six minutes per mile, it does not necessarily follow that you ran a consecutive mile in exactly six minutes.

The key issue here is not the units of measurement, but whether or not the total length of the race is an integer multiple of the length of the subinterval of interest. Assuming for simplicity that this subinterval is one mile, then the following two theorems can be proved, as explained in the recent expository paper Average pace and horizontal chords by Keith Burns, Orit Davidovich and Diana Davis (http://arxiv.org/abs/1507.00871).

Theorem 1. If the length of the race is an... more »

Average pace and the Universal Chord Theorem

If you run a three-mile race at an average pace of six minutes per mile, it will always be the case that you ran for one consecutive mile in exactly six minutes. But if you run a 3.1-mile race at an average pace of six minutes per mile, it does not necessarily follow that you ran a consecutive mile in exactly six minutes.

The key issue here is not the units of measurement, but whether or not the total length of the race is an integer multiple of the length of the subinterval of interest. Assuming for simplicity that this subinterval is one mile, then the following two theorems can be proved, as explained in the recent expository paper Average pace and horizontal chords by Keith Burns, Orit Davidovich and Diana Davis (http://arxiv.org/abs/1507.00871).

Theorem 1. If the length of the race is an integer number of miles, then there must be some mile-long interval of the race that was run at exactly the average pace of the whole race.

Theorem 2. If, on the other hand, the length of the race is not an integer number of miles, then it is possible that the race was run in such a way that no mile-long interval was run at exactly the overall average pace.

Of course, it is always possible that a mile-long interval of any race is run at exactly the overall average pace; for example, if the entire race were run at a constant speed. What the second result is asserting is that, if the race is not an integer number of miles long, it is possible to find a (smooth) position function for the race so that no mile-long interval is run at the average pace.

The diagram in the bottom right, which comes from the paper, shows an example of the situation covered by Theorem 2. The situation is motivated by two athletic word records: (a) Molly Huddle, who ran a 12km race in a time of 37:49, an average of 3:09 per kilometer; and (b) Mary Keitany, who ran a half marathon (21.1km) in a time of 65:50, an average of 3:07 per kilometer. It is tempting to conclude that Keitany must have run a consecutive 12km stretch of the race at an average pace of 3 minutes and 7 seconds per kilometer, thus beating Huddle's record. However, Theorem 2 shows that this is not necessarily true, because 21.1km is not an integer multiple of 12km. More precisely, the diagram shows a way this could happen: if there is a long, slow stretch in the middle of the race, then every consecutive stretch of 12km will contain the entire slow section of the race and will therefore be run at less than the average pace.

Theorem 1 can be proved with basic calculus, and it was known to the French physicist and mathematician André-Marie Ampère (of electric current fame) as early as 1806. The idea behind the proof is that if a race is n miles long and is subdivided into n consecutive miles, then at least one of these miles was run at greater than equal to the average pace, and at least one of them was run at less than or equal to the average pace. The result then follows by applying the Intermediate Value Theorem.

Theorem 2 was first proved by Paul Lévy in 1934. Lévy considered an equivalent form of the problem, in which the diagram shown is sheared vertically so that the beginning and end of the race both sit on the horizontal axis. A mile-long stretch of the race that is run at average pace then shows up as a horizontal chord of unit length, which partly explains why this result is sometimes known as the Universal Chord Theorem.

The paper also considers some generalizations of Lévy's result, including one proved by Heinz Hopf in 1937. Hopf proved that a set of positive real numbers is the horizontal chord set of a function if and only if the complement of the set is a topologically open set that is additively closed. What Hopf's result means for the athletics scenario is as follows. Given the position function of a race of length L (like the one in the diagram), consider the set S consisting of the lengths of all the distance subintervals of the race that were run at exactly the overall average pace; one of these numbers will be L itself. Hopf's theorem then shows that S is a topologically closed set, meaning that it has an open complement. The theorem also shows that the sum of two lengths that are not in S is also not in S. This forces all the numbers L/n to lie in S whenever n is a positive integer, which is the statement of Theorem 1.

Relevant links

Historical mathematicians mentioned in this post:
https://en.wikipedia.org/wiki/André-Marie_Ampère
https://en.wikipedia.org/wiki/Paul_Lévy_(mathematician)
https://en.wikipedia.org/wiki/Heinz_Hopf

Intermediate value theorem: https://en.wikipedia.org/wiki/Intermediate_value_theorem

Photo credit unknown. I found it via Google Images, whose best guess is 5k runners.

The Lonely Runner Conjecture is a problem that superficially sounds like the one in this post, but in fact it is much harder. Here are two posts by me about it:
https://plus.google.com/101584889282878921052/posts/YHJkEdKg3jz
https://plus.google.com/101584889282878921052/posts/JMtPiZeVVnT

#mathematics #sciencesunday #spnetwork arXiv:1507.00871___

posted image

2015-07-04 03:51:44 (53 comments; 108 reshares; 352 +1s; )Open 

Why your friends, on average, have more friends than you do

The friendship paradox is the observation that your friends, on average, have more friends than you do. This phenomenon, which was first observed by the sociologist Scott L. Feld in 1991, is mathematically provable, even though it contradicts most people's intuition that they have more friends than their friends do.

Wikipedia gives a nice intuitive explanation for this phenomenon: People with more friends are more likely to be your friend in the first place; that is, they have a higher propensity to make friends in the first place. However, it is also possible to explain the phenomenon using graph theory and mathematical statistics. I give an outline of the mathematical proof at the end of this post for those who are interested, but the upshot is that if we look at everybody's numbers of friends,... more »

Why your friends, on average, have more friends than you do

The friendship paradox is the observation that your friends, on average, have more friends than you do. This phenomenon, which was first observed by the sociologist Scott L. Feld in 1991, is mathematically provable, even though it contradicts most people's intuition that they have more friends than their friends do.

Wikipedia gives a nice intuitive explanation for this phenomenon: People with more friends are more likely to be your friend in the first place; that is, they have a higher propensity to make friends in the first place. However, it is also possible to explain the phenomenon using graph theory and mathematical statistics. I give an outline of the mathematical proof at the end of this post for those who are interested, but the upshot is that if we look at everybody's numbers of friends, and these numbers have a mean of μ and a variance of σ^2, then the average number of friends that an average friend has is μ + (σ^2/μ), which will be greater than μ assuming that someone has at least one friend and that not everyone has the same number of friends.

The recent paper The Majority Illusion in Social Networks (http://arxiv.org/abs/1506.03022) by Kristina Lerman, Xiaoran Yan, and Xin-Zeng Wu explores some phenomena that are related to the friendship paradox. The authors explain how, under certain conditions, the structure of a social network can make it appear to an individual that certain types of behaviour are far more common than they actually are.

The diagram here, which comes from the paper, illustrates this point. It shows two social networks, (a) and (b), each containing 14 individuals. In each case, three vertices are marked in red; let's suppose that these correspond to the heavy drinkers in the group. In social network (a), the heavy drinkers are three of the most popular people, and the configuration of the network means that each of the other eleven individuals observes that at least half of their friends are heavy drinkers. This will lead these eleven people to think that heavy drinking is common in their society, when in fact it is not: only 3/14 of the group are heavy drinkers. In social network (b), there are the same number of heavy drinkers, but they are not particularly popular, and nobody in the group will have heavy drinkers as most of their friends. 

Network (a) is experiencing what the authors call the majority illusion, whereas network (b) is not. The illusion will tend to occur when the behaviour in question is correlated with having many friends. The paper shows that the illusion is likely to be more prevalent in disassortative networks, which means networks in which people have less tendency to be friends with people like themselves. Observe that in network (b), many of the non-heavy drinkers are friends with each other, whereas in network (a), they are not. This suggests that network (a) is more disassortative, and thus more susceptible to the majority illusion.

The authors also study the phenomenon using three real-world data sets: (a) the coauthorship network of high energy physicists (HepTh), (b) the social network Digg, studying only the mutual-following links, and (c) the network representing the links between political blogs. It turns out that networks (a) and (b) are assortative, and (c) is disassortative. They also look at the the case of Erdős–Rényi-type networks, which can be thought of as random. 

As the paper points out, the friendship paradox has real life applications. For example, if one is monitoring a contagious outbreak, it is more efficient to monitor random friends of random people than it is to monitor random people. This is because the friends are more likely to be better connected, are more likely to get sick earlier, and are more likely to infect more people once sick. The reason for this has to do with the fact that these attributes are positively correlated with having many friends. 

If you're wondering why your coauthors are on average cited more often than you are, or why your sexual partners on average have had more sexual partners than you have, now you know. I found out about this paper via my Facebook friend +Paul Mitchener, who has more Facebook friends than I do.

Relevant links

Wikipedia's page on the Friendship Paradox contains much of the information in this post, including a sketch of the proof given below: https://en.wikipedia.org/wiki/Friendship_paradox

Wikipedia on assortativity: https://en.wikipedia.org/wiki/Assortativity

Here's another post by me about the mathematics of social networks, in which I explain why it is impossible for everyone on Google+ to have more than 5000 followers. It provoked a surprisingly hostile reaction:  https://plus.google.com/101584889282878921052/posts/YV7j9LRqKsX

A post by me about Erdős and Rényi's construction of the random graph: https://plus.google.com/101584889282878921052/posts/34guwy4ftWX


Appendix: Mathematical proof of the friendship paradox

Assume for simplicity that friendship is a symmetric relation: in other words, that whenever A is a friend of B, then B is also a friend of A. We can then model a friendship network with an undirected graph G, with a set of vertices V and a set of edges E. Each vertex v in V represents an individual, and each edge e in E connects a pair of individuals who are friends. For each vertex v in V, the number d(v) (the degree of v) is the number of edges connected to v; in other words, the number of friends v has. 

The average number of friends of everyone in the network is then given by summing d(v) over all vertices v of V, and then dividing by |V|, the total number of people. Using basic graph theory, this number, μ, can be shown to be equal to 2 times |E| divided by |V|, where |E| is the number of edges.

In order to find the number of friends that a typical friend has, one first chooses a random edge of E (which represents a pair of friends) and one of the two endpoints of E (representing one of the pair of friends); the degree of this latter vertex is the number of friends that a friend has.  Summing these degrees over all possible choices amounts to summing d(v)^2 over all possible vertices, and since the number of choices is 2 times |E|, it follows that the average number of friends a friend has is the sum of d(v)^2 divided by 2 times |E|. Using the formula for μ above, it follows that μ times the average number of friends that a friend has is equal to the average value of d(v)^2. However, the average value of d(v)^2 is also equal, by basic mathematical statistics, to the sum of the square of the mean of the d(v) plus the variance of the d(v). The result follows from this.

#mathematics #scienceeveryday #spnetwork arXiv:1506.03022___

posted image

2015-06-20 21:47:18 (38 comments; 76 reshares; 242 +1s; )Open 

The mathematics of Boggle logic puzzles

This picture shows a logic puzzle based on the popular word game Boggle. The object of the game is to place the fourteen letters shown at the bottom into the grid in such a way that the grid spells out each of the ten words in the list on the right. The words must be constructed from the letters of sequentially adjacent squares, where adjacent refers to squares that are horizontal, vertical or diagonal neighbours, and where squares may not be reused.

It turns out that Boggle logic puzzles have mathematically interesting aspects; for example, they are related to the subgraph isomorphism problem, which is an example of an NP-complete problem. The recent paper 10 Questions about Boggle Logic Puzzles by Jonathan Needleman (http://arxiv.org/abs/1506.04173) gives a survey of what is known and proposes a number (ten!) of related... more »

The mathematics of Boggle logic puzzles

This picture shows a logic puzzle based on the popular word game Boggle. The object of the game is to place the fourteen letters shown at the bottom into the grid in such a way that the grid spells out each of the ten words in the list on the right. The words must be constructed from the letters of sequentially adjacent squares, where adjacent refers to squares that are horizontal, vertical or diagonal neighbours, and where squares may not be reused.

It turns out that Boggle logic puzzles have mathematically interesting aspects; for example, they are related to the subgraph isomorphism problem, which is an example of an NP-complete problem. The recent paper 10 Questions about Boggle Logic Puzzles by Jonathan Needleman (http://arxiv.org/abs/1506.04173) gives a survey of what is known and proposes a number (ten!) of related problems.

The paper starts with what seems like an easy challenge: construct a filling of a 3 by 3 Boggle grid that contains each of the words ACT, APE, ATE, COP, END and OLD. It is clear that the nine letters in the grid must be ACDELNOPT, but the puzzle is a lot harder than I thought it would be, and this is partly because there are only six words in the list.

If B is a Boggle grid that has been filled in with letters, Needleman defines the set W(B) to be the set of all words in the board B that are at least two letters long. Here, the term words refers to strings of letters that may or may not be valid English words. The paper also makes the simplifying assumption that each letter appearing in the grid should appear only once, like in the grid in the picture, although the paper also discusses how this second assumption may be removed.

Two boards B and B' are said to be equivalent if they produce the same list of words. It can be shown that if two boards are equivalent, it must be the case that they differ from each other only by mirror reflection or by rotation by a multiple of a right angle. [Precise statement for mathematicians: the group of automorphisms of the adjacency graph of the Boggle grid is dihedral of order 8.]

The formal definition of a Boggle logic puzzle is as a list of words P satisfying two conditions: (1) P is a subset of W(B) for some board B, and (2) if P is a subset of W(B') for some other board B', then B and B' are equivalent. For example, the assertion that “ACT, APE, ATE, COP, END, OLD” is a Boggle logic puzzle for n=3 is the claim that (1) there exists a 3x3 Boggle board that spells out all of these six words and (2) up to symmetry, there is no other Boggle board with this property. The puzzle in the picture has two letters already filled in. As well as making the puzzle easier, this also provides enough information to break the symmetry of the solution and give a unique answer.

Two of the main themes studied in the paper are minimal solutions and maximal non-solutions of Boggle logic puzzles. Theorem 3.1 says something about the minimal solutions of a 3x3 grid. What it proves is that a puzzle consisting only of three-letter words, on a board with no repeated letters, must contain at least six words. Recall the “ACT, APE, ATE, COP, END, OLD” puzzle from earlier, which contains six three-letter words and no repeated letters. The theorem then says that any list of only five three-letter words cannot possibly lead to a unique solution. One of the open questions in the paper concerns 3x3 grids with no repeated letters whose puzzles contain only two-letter words. It can be proved that one would need at least 11 two-letter words to achieve a unique solution, but it is not known if this bound is sharp, because the smallest known example of such a puzzle contains 12 two-letter words.

The maximal non-solutions arise from lists of words that lead to a puzzle that is as inefficiently long as possible. To see what this means, suppose that you have played a game of Boggle and produced a long list of words. Is it possible to reconstruct the board (up to symmetry) using only the words you have written down? How long does your list of words have to be before this is inevitable? Even on a 3x3 grid, the number turns out to be surprisingly large: one needs 137 distinct three-letter words (out of a possible total of 160) to guarantee that the puzzle can be reconstructed uniquely. For four-letter words, the number is 377 words (out of a possible total of 496).

Relevant links

The game Boggle was designed by Allan Turoff. It was originally manufactured by Parker Brothers, and is now manufactured by Hasbro. More information on the game is here: http://en.wikipedia.org/wiki/Boggle

Image source: http://www.aspenhouse21.com/gc/boggle_east.jpg

Details of the subgraph isomorphism problem: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

Boggle logic puzzles are reminiscent of the game Sudoku. In 2012, Gary McGuire, Bastian Tugemann and Gilles Civario proved that the smallest possible number of clues on a standard Sudoku board that can lead to a unique solution is 17. +Richard Elwes has included this result in a recent blog post about his personal top 10 mathematical achievements of the last 5ish years. You can find this post at http://goo.gl/Nl7IwX. (I've abbreviated the URL because it is rather long.)

#mathematics #scienceeveryday #spnetwork arXiv:1506.04173___

posted image

2015-06-12 17:31:24 (19 comments; 15 reshares; 180 +1s; )Open 

For #floralfriday, here are some azalea flowers from my mother's garden in Southampton (UK). 

More information about azaleas can be found at https://en.wikipedia.org/wiki/Azalea. Google Images suggests Iggy Azalea as a related search term, but I'm pretty sure they aren't related, at least not closely.

For #floralfriday, here are some azalea flowers from my mother's garden in Southampton (UK). 

More information about azaleas can be found at https://en.wikipedia.org/wiki/Azalea. Google Images suggests Iggy Azalea as a related search term, but I'm pretty sure they aren't related, at least not closely.___

posted image

2015-06-04 19:46:06 (43 comments; 23 reshares; 315 +1s; )Open 

Christopher Wren and John Wallis

During my visit to Cambridge last month, I took this picture of Emmanuel College, where I stayed for one night. The building shown here is the chapel, which was designed by the English architect Sir Christopher Wren (1632–1723).

Wren designed many other buildings in England that are still in good condition. One of these is the Sheldonian Theatre in Oxford, which is remarkable for having a large flat roof. The roof of the theatre is supported Wren considered supporting the roof of the theatre by an ingenious network of wooden beams designed by the mathematician John Wallis (1616–1703), who was an alumnus of Emmanuel College, Cambridge. Each beam in the network is supported at each end, either by another beam or by the side of the building, and each beam in turn supports two others. 

Wallis was acalc... more »

Christopher Wren and John Wallis

During my visit to Cambridge last month, I took this picture of Emmanuel College, where I stayed for one night. The building shown here is the chapel, which was designed by the English architect Sir Christopher Wren (1632–1723).

Wren designed many other buildings in England that are still in good condition. One of these is the Sheldonian Theatre in Oxford, which is remarkable for having a large flat roof. The roof of the theatre is supported Wren considered supporting the roof of the theatre by an ingenious network of wooden beams designed by the mathematician John Wallis (1616–1703), who was an alumnus of Emmanuel College, Cambridge. Each beam in the network is supported at each end, either by another beam or by the side of the building, and each beam in turn supports two others. 

Wallis was a calculating genius, and one night calculated the square root of a 53 digit number in his head. In order to design the network of beams to support the flat roof, Wallis had to solve a 25 by 25 system of linear equations by hand, some of which involved ratios such as 3088694/340167. The result was a structurally sound pattern of beams that stays intact without the use of glue or screws at the joints.

The Wikipedia page on Christopher Wren (http://en.wikipedia.org/wiki/Christopher_Wren) has many more pictures of buildings he designed. These include the library at Trinity College, Cambridge, which I visited with my host +Timothy Gowers, but which has a clear no-photography policy. The library has an original Winnie-the-Pooh manuscript on display, because the author A.A. Milne and his son, Christopher Robin Milne, both studied at Trinity College, where they were both mathematicians.

Other relevant links

The Sheldonian Theatre: http://en.wikipedia.org/wiki/Sheldonian_Theatre

Wikipedia on John Wallis: http://en.wikipedia.org/wiki/John_Wallis

An article on Wallis's design of the Sheldonian Theatre roof, showing the supporting pattern of beams: http://www.soue.org.uk/souenews/issue4/wallis.html

Emmanuel College, Cambridge: http://en.wikipedia.org/wiki/Emmanuel_College,_Cambridge

#mathematics #architecture  ___

posted image

2015-05-24 16:20:12 (26 comments; 127 reshares; 455 +1s; )Open 

The Gamma Function and Fractal Factorials!

This fractal image by Thomas Oléron Evans was created by using iterations of the Gamma function, which is a continuous version of the factorial function.

If n is a positive integer, the factorial of n, n!, is defined to be the product of all the integers from 1 up to n; for example, 4!=1x2x3x4=24. It is clear from the definition that (n+1)! is the product of n+1 and n!, but it is not immediately clear what the “right” way is to extend the factorial function to non-integer values.

If t is a complex number with a positive real part, the Gamma function Γ(t) is defined by integrating the function x^{t–1}e^{–x} from x=0 to infinity. It is a straightforward exercise using integration by parts and mathematical induction to prove that if n is a positive integer, then Γ(n) is equal to (n–1)!, thefactorial of... more »

The Gamma Function and Fractal Factorials!

This fractal image by Thomas Oléron Evans was created by using iterations of the Gamma function, which is a continuous version of the factorial function.

If n is a positive integer, the factorial of n, n!, is defined to be the product of all the integers from 1 up to n; for example, 4!=1x2x3x4=24. It is clear from the definition that (n+1)! is the product of n+1 and n!, but it is not immediately clear what the “right” way is to extend the factorial function to non-integer values.

If t is a complex number with a positive real part, the Gamma function Γ(t) is defined by integrating the function x^{t–1}e^{–x} from x=0 to infinity. It is a straightforward exercise using integration by parts and mathematical induction to prove that if n is a positive integer, then Γ(n) is equal to (n–1)!, the factorial of (n–1). Since Γ(1)=1, this gives a justification (there are many others) that the factorial of zero is 1.

Using a technique called analytic continuation, the Gamma function can then be extended to all complex numbers except negative integers and zero. The resulting function, Γ(t), is infinitely differentiable, except at the nonpositive integers, where it has simple poles; the latter are the same kind of singularity that the function f(x)=1/x has at x=0. A particularly nice property of the Gamma function is that it satisfies Γ(t+1)=tΓ(t), which extends the recursive property n!=n(n–1)! satisfied by factorials. It is therefore natural to define the factorial of a complex number z by z!=Γ(z+1).

At first, it may not seem very likely that iterating the complex factorial could produce interesting fractals. If n is an integer that is at least 3, then taking repeated factorials of n will produce a sequence that tends to infinity very quickly. However, if one starts with certain complex numbers, such as 1–i, repeated applications of the complex factorial behave very differently. It turns out that (1–i)! is approximately 0.653–0.343i, and taking factorials five times, we find that (1–i)!!!!! is approximately 0.991–0.003i. This suggests that iterated factorials of 1–i  may produce a sequence that converges to 1.

It turns out that if one takes repeated factorials of almost any complex number, we either obtain a sequence that converges to 1 (as in the case of 1–i) or a sequence that diverges to infinity (as in the case of 3). However, it is not possible to take factorials of negative integers, and there are some rare numbers, like z=2, that are solutions of z!=z and do not exhibit either type of behaviour.

By plotting the points that diverge to infinity in one colour, and the points that converge to 1 in a different colour, fractal patterns emerge. The image shown here uses an ad hoc method of colouring points to indicate the rate of convergence or divergence. The points that converge to 1 are coloured from red (fast convergence) to yellow (slow convergence), and the points that diverge to infinity are coloured from green (slow divergence) to blue (fast divergence)

Relevant links

Thomas Oléron Evans discusses these fractals in detail in a blog post (http://www.mathistopheles.co.uk/2015/05/14/fractal-factorials/) which contains this image and many others. He (and I) would be interested in knowing if these fractals have been studied before.

The applications of the Gamma function in mathematics are extensive. Wikipedia has much more information about the function here: http://en.wikipedia.org/wiki/Gamma_function

This post appears in my Mathematics collection at https://plus.google.com/collection/8zrhX

#mathematics #sciencesunday  

Various recent posts by me
Camellia flower: https://goo.gl/8WNrlu
Horse chestnut tree: https://goo.gl/FPCGI3
A Curious Property of 82000: https://goo.gl/1rVg8y___

posted image

2015-05-22 21:09:27 (7 comments; 6 reshares; 161 +1s; )Open 

For #floralfriday, here's a Camellia flower from my mother's garden in Southampton (UK).

More information on Camellias can be found here: http://en.wikipedia.org/wiki/Camellia

For #floralfriday, here's a Camellia flower from my mother's garden in Southampton (UK).

More information on Camellias can be found here: http://en.wikipedia.org/wiki/Camellia___

posted image

2015-05-19 17:05:05 (17 comments; 3 reshares; 176 +1s; )Open 

For #treetuesday, here's a picture I took during my recent trip to Cambridge (UK). My host, +Timothy Gowers, identified this tree as a horse chestnut. In the autumn, the horse chestnut sheds its distinctive large nut-like seeds, which are called conkers.

Just behind the tree is King's College, Cambridge, where the pioneering computer scientist Alan Turing was an undergraduate in the early 1930s.

Relevant links
The horse chestnut (Aesculus hippocastanum): http://en.wikipedia.org/wiki/Aesculus_hippocastanum

King's College, Cambridge: http://en.wikipedia.org/wiki/King's_College,_Cambridge

Alan Turing: http://en.wikipedia.org/wiki/Alan_Turing

For #treetuesday, here's a picture I took during my recent trip to Cambridge (UK). My host, +Timothy Gowers, identified this tree as a horse chestnut. In the autumn, the horse chestnut sheds its distinctive large nut-like seeds, which are called conkers.

Just behind the tree is King's College, Cambridge, where the pioneering computer scientist Alan Turing was an undergraduate in the early 1930s.

Relevant links
The horse chestnut (Aesculus hippocastanum): http://en.wikipedia.org/wiki/Aesculus_hippocastanum

King's College, Cambridge: http://en.wikipedia.org/wiki/King's_College,_Cambridge

Alan Turing: http://en.wikipedia.org/wiki/Alan_Turing___

posted image

2015-05-17 16:55:34 (60 comments; 75 reshares; 375 +1s; )Open 

A Curious Property of 82000

The number 82000 in base 10 is equal to 10100000001010000 in base 2, 11011111001 in base 3, 110001100 in base 4, and 10111000 in base 5. It is the smallest integer bigger than 1 whose expressions in bases 2, 3, 4, and 5 all consist entirely of zeros and ones.

What is remarkable about this property is how much the situation changes if we alter the question slightly. The smallest number bigger than 1 whose base 2, 3, and 4 representations consist of zeros and ones is 4. If we ask the same question for bases up to 3, the answer is 3, and for bases up to 2, the answer is 2. The question does not make sense for base 1, which is what leads to the sequence in the picture: [undefined], 2, 3, 4, 82000.

The graphic comes from a blog post by Thomas Oléron Evans. Most of the post discusses the intriguing problem of finding the next term... more »

A Curious Property of 82000

The number 82000 in base 10 is equal to 10100000001010000 in base 2, 11011111001 in base 3, 110001100 in base 4, and 10111000 in base 5. It is the smallest integer bigger than 1 whose expressions in bases 2, 3, 4, and 5 all consist entirely of zeros and ones.

What is remarkable about this property is how much the situation changes if we alter the question slightly. The smallest number bigger than 1 whose base 2, 3, and 4 representations consist of zeros and ones is 4. If we ask the same question for bases up to 3, the answer is 3, and for bases up to 2, the answer is 2. The question does not make sense for base 1, which is what leads to the sequence in the picture: [undefined], 2, 3, 4, 82000.

The graphic comes from a blog post by Thomas Oléron Evans. Most of the post discusses the intriguing problem of finding the next term in this sequence, and whether the next term even exists. In other words, does there exist an integer greater than 1 whose representations in bases 2, 3, 4, 5, and 6 all consist entirely of zeros and ones? 

The number 82000 does not satisfy these conditions, because the representation of this number in base 6 is 1431344. This means that the next number in the sequence, if it exists, must be some number bigger than 82000 whose representations in bases 2, 3, 4, and 5 all consist entirely of zeros and ones. Unfortunately, even these weaker conditions are very difficult to satisfy. An exhaustive search has been carried out up to 3125 digits in base 5 and no solution exists in this range. 

The upshot of this is that, if the next term in the sequence exists, it must have more than 2184 digits in base 10. (The 2184 comes from multiplying 3125 by the base 10 logarithm of 5.) However, there is also no known proof that the next term in the sequence does not exist.

Relevant links

Thomas Oléron Evans's blog post has much more discussion of this problem, at http://www.mathistopheles.co.uk/maths/covering-all-the-bases/solution-covering-all-the-bases/

Details of the exhaustive search can be found in the notes to the sequence http://oeis.org/A146025 in the On-Line Encyclopedia of Integer Sequences.

There is a nice online number base converter tool at http://www.cleavebooks.co.uk/scol/calnumba.htm

#mathematics #sciencesunday  ___

posted image

2015-05-16 17:18:14 (99 comments; 47 reshares; 1,418 +1s; )Open 

For #caturday, here's my sister's British Blue Shorthair cat, Aslan. You can find out more about the breed here: http://en.wikipedia.org/wiki/British_Shorthair

For #caturday, here's my sister's British Blue Shorthair cat, Aslan. You can find out more about the breed here: http://en.wikipedia.org/wiki/British_Shorthair___

posted image

2015-05-08 15:51:17 (23 comments; 9 reshares; 148 +1s; )Open 

I took this picture of an apple blossom with my phone during my morning dog walk last Monday. It has been unusually wet here recently, as you might guess from the picture.

#floralfriday


I took this picture of an apple blossom with my phone during my morning dog walk last Monday. It has been unusually wet here recently, as you might guess from the picture.

#floralfriday
___

posted image

2015-05-04 03:40:10 (16 comments; 36 reshares; 210 +1s; )Open 

Penrose Land Cover by Daniel P. Huffman

This land cover map of the continental United States was produced by Daniel P. Huffman using Penrose tiles.

A more traditional way to do this would be to use the technique of hexagonal binning, which achieves a similar result by using hexagonal cells, as in a honeycomb. It is possible to tile the entire plane using either identical hexagonal tiles or Penrose tiles. A key difference between the two is that the hexagons will produce a tiling with full translational symmetry, whereas the Penrose tiles will not.

Daniel Huffman recently remarked that “Penrose tilings are the new hexbins”. You can find this map, and some others of the same type, on Huffman's Twitter page: https://twitter.com/pinakographos

Wikipedia seems not to have a good description of hexbins, but cartographer ZacharyFor... more »

Penrose Land Cover by Daniel P. Huffman

This land cover map of the continental United States was produced by Daniel P. Huffman using Penrose tiles.

A more traditional way to do this would be to use the technique of hexagonal binning, which achieves a similar result by using hexagonal cells, as in a honeycomb. It is possible to tile the entire plane using either identical hexagonal tiles or Penrose tiles. A key difference between the two is that the hexagons will produce a tiling with full translational symmetry, whereas the Penrose tiles will not.

Daniel Huffman recently remarked that “Penrose tilings are the new hexbins”. You can find this map, and some others of the same type, on Huffman's Twitter page: https://twitter.com/pinakographos

Wikipedia seems not to have a good description of hexbins, but cartographer Zachary Forest Johnson wrote a nice blog post about them a few years ago, which you can find here: http://indiemaps.com/blog/2011/10/hexbins/

Wikipedia has more on Penrose tilings here: http://en.wikipedia.org/wiki/Penrose_tiling

I have posted about Penrose tilings and related tilings several times, for example here: https://plus.google.com/101584889282878921052/posts/dhPpRnwNmsR

#mathematics #cartography #sciencesunday
___

posted image

2015-04-26 00:34:40 (22 comments; 60 reshares; 223 +1s; )Open 

Tiling an octagon with centrally symmetric pieces

It is easy to cut an equilateral triangle into four smaller equilateral triangles, or to cut a square into four smaller squares, or to cut a regular hexagon into six equilateral triangles (think of a Trivial Pursuit playing piece). Less obviously, it is possible to cut a regular octagon into polygon-shaped pieces that are both centrally symmetric and convex. Some of these are illustrated in this picture.

The picture comes from the recent paper Decompositions of a polygon into centrally symmetric pieces by Júlia Frittmann and Zsolt Lángi (http://arxiv.org/abs/1504.05418). The introduction of the paper gives a brief survey of some related problems. For example, it is trivial to cut a square into a set of triangles of the same area as each other, as anyone who has tried to cut a square piece of bread into trianglesw... more »

Tiling an octagon with centrally symmetric pieces

It is easy to cut an equilateral triangle into four smaller equilateral triangles, or to cut a square into four smaller squares, or to cut a regular hexagon into six equilateral triangles (think of a Trivial Pursuit playing piece). Less obviously, it is possible to cut a regular octagon into polygon-shaped pieces that are both centrally symmetric and convex. Some of these are illustrated in this picture.

The picture comes from the recent paper Decompositions of a polygon into centrally symmetric pieces by Júlia Frittmann and Zsolt Lángi (http://arxiv.org/abs/1504.05418). The introduction of the paper gives a brief survey of some related problems. For example, it is trivial to cut a square into a set of triangles of the same area as each other, as anyone who has tried to cut a square piece of bread into triangles will know. (Note, however, that the resulting triangles will probably not be centrally symmetric.) Given this, it may be surprising to discover that that P. Monsky proved in 1970 that it is impossible to cut a square into an odd number of triangles, all of the same area.

Frittmann and Lángi's paper illustrates all 111 irreducible edge-to-edge decompositions of a regular octagon into convex polygonal pieces (tiles), where each tile is rotationally symmetric about its centre. The 18 decompositions shown in the picture are among the 111 irreducible decompositions.

In order for this classification to make complete sense, some terms need to be defined. A decomposition is called edge-to-edge if each edge of each tile either lies in the boundary of the surrounding polygon, or if it meets the edge of some other tile along the entire length of the edge. A shape is called convex if, whenever two distinct points are chosen within the shape, the straight line connecting the two points lies entirely within the shape. A decomposition with n tiles is called irreducible if, whenever at least 1 but at most n–2 tiles are removed from the decomposition, the remaining tiles form a non-convex shape. 
 
If A and B are tilings of the same polygon, we say that A is equivalent to B if there is a one to one correspondence between the set of tiles of A and the set of tiles of B, in such a way that two tiles of A touch each other in the same way that the corresponding two tiles of B touch each other. [Precise definition for mathematicians: two tilings are equivalent if the face lattices of the corresponding CW-decompositions are isomorphic.] There are infinitely many ways to tile an octagon under the constraints mentioned above, but there are only finitely many different ways up to equivalence. 

The main result of Frittmann and Lángi's paper generalizes this result to the case of a polygon with an even number, 2k, of sides, where k is at least 4. It turns out that in order for such a decomposition to be possible at all, the big polygon needs to be centrally symmetric. The authors show that up to equivalence, there will be a finite number of irreducible edge-to-edge decompositions of a centrally symmetric polygon into centrally symmetric, convex, polygonal parts. For an octagon, this number is 111, and G. Horváth proved in 1997 that the corresponding number for a hexagon is only 6. In their paper, Frittmann and Lángi give an upper bound for the number of decompositions for larger values of k.

It would be interesting to know what happens in the case where the big polygon has an odd number of sides. As I mentioned in the first paragraph, it is clearly possible to do something analogous for an equilateral triangle, although I don't know what would happen in the case of, say, a regular pentagon.

Relevant link
I mentioned CW decompositions above. These are associated to a CW complex, which is an important type of topological space. The “CW” is not somebody's initials, or an American TV channel, but rather stands for “closure-finite” and “weak topology”. The definition of a CW complex is rather technical, but it can be found here: http://en.wikipedia.org/wiki/CW_complex

#mathematics #sciencesunday #spnetwork arXiv:1504.05418___

posted image

2015-04-24 14:51:44 (36 comments; 22 reshares; 418 +1s; )Open 

I don't have time to post anything substantial at the moment, but I thought you might enjoy these tulips I saw growing on campus this morning. I'm hoping I'll have a lot more time to post in the near future.

#floralfriday  

I don't have time to post anything substantial at the moment, but I thought you might enjoy these tulips I saw growing on campus this morning. I'm hoping I'll have a lot more time to post in the near future.

#floralfriday  ___

posted image

2015-04-16 21:32:45 (29 comments; 8 reshares; 163 +1s; )Open 

Spring in Colorado often means sweeping snow off my satellite dish. Snow doesn't usually disrupt the satellite signal in the winter unless there is a lot of it, but wet spring snow can disrupt TV reception even in small amounts.

The tree in the front is a crabapple of some kind, and the one further away is a weeping willow.

I took this picture with my iPhone today from the top of a ladder, and edited it with Snapseed.

#snapseed

Spring in Colorado often means sweeping snow off my satellite dish. Snow doesn't usually disrupt the satellite signal in the winter unless there is a lot of it, but wet spring snow can disrupt TV reception even in small amounts.

The tree in the front is a crabapple of some kind, and the one further away is a weeping willow.

I took this picture with my iPhone today from the top of a ladder, and edited it with Snapseed.

#snapseed___

posted image

2015-04-15 22:04:12 (69 comments; 45 reshares; 391 +1s; )Open 

It can't be true... can it?

Yes, it is indeed true that the square root of 2 and two thirds is equal to 2 times the square root of two thirds. This particular equation is an example of a prompt on the UK-based website Inquiry maths. The website explains:

Inquiry maths is a model of teaching that encourages students to regulate their own activity while exploring a mathematical statement (called a prompt). Inquiries can involve a class on diverse paths of exploration or in listening to a teacher's exposition. In inquiry maths, students take responsibility for directing the lesson with the teacher acting as the arbiter of legitimate mathematical activity.

Remarkably, this particular prompt was found by a year 10 student of teacher Rachael Read. It is recommended for students with high prior attainment in years 10 and 11. Reportedly, students are... more »

It can't be true... can it?

Yes, it is indeed true that the square root of 2 and two thirds is equal to 2 times the square root of two thirds. This particular equation is an example of a prompt on the UK-based website Inquiry maths. The website explains:

Inquiry maths is a model of teaching that encourages students to regulate their own activity while exploring a mathematical statement (called a prompt). Inquiries can involve a class on diverse paths of exploration or in listening to a teacher's exposition. In inquiry maths, students take responsibility for directing the lesson with the teacher acting as the arbiter of legitimate mathematical activity.

Remarkably, this particular prompt was found by a year 10 student of teacher Rachael Read. It is recommended for students with high prior attainment in years 10 and 11. Reportedly, students are quickly hooked in to the prompt, particularly when one of them claims it “works” after checking on a calculator. 

Relevant links

There is more discussion of the educational value of this equation, and on the teaching of surds in general, in the original blog post on this topic: http://www.inquirymaths.co.uk/home/number-prompts/surds

The word “surd”, referring to n-th roots, is a Latin translation of a term tracing back to the 9th century Persian mathematician al-Khwārizmī, after whom algorithms are named. He also invented the term algebra (al-jabr in Arabic).

Surds: http://en.wikipedia.org/wiki/Nth_root

al-Khwārizmī: http://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi

(Seen via Cliff Pickover on Twitter.)

#mathematics #education  ___

posted image

2015-04-06 23:24:24 (35 comments; 55 reshares; 362 +1s; )Open 

Prime factorizations of small numbers, by John Graham-Cumming

The Fundamental Theorem of Arithmetic states that every natural number greater than 1 can be expressed as a product of prime numbers, and that the product is unique up to changing the order of the factors. For example, the number 12 can be expressed as 2x2x3, or as 2x3x2, or as 3x2x2, where 2 and 3 are prime numbers. These factorizations are all rearrangements of each other, and there are no other ways to write 12 as a product of prime numbers.

This picture by John Graham-Cumming shows the factorizations into primes of the numbers from 2 to 100. Note that the circle representing 1 is blank, because 1 is not prime: if we allowed 1 to be prime, then we would have 12=2x2x3=1x2x2x3, which would break the Fundamental Theorem of Arithmetic.

The picture comes from an April 2012 blog post by... more »

Prime factorizations of small numbers, by John Graham-Cumming

The Fundamental Theorem of Arithmetic states that every natural number greater than 1 can be expressed as a product of prime numbers, and that the product is unique up to changing the order of the factors. For example, the number 12 can be expressed as 2x2x3, or as 2x3x2, or as 3x2x2, where 2 and 3 are prime numbers. These factorizations are all rearrangements of each other, and there are no other ways to write 12 as a product of prime numbers.

This picture by John Graham-Cumming shows the factorizations into primes of the numbers from 2 to 100. Note that the circle representing 1 is blank, because 1 is not prime: if we allowed 1 to be prime, then we would have 12=2x2x3=1x2x2x3, which would break the Fundamental Theorem of Arithmetic.

The picture comes from an April 2012 blog post by Graham-Cumming, which you can find here: http://blog.jgc.org/2012/04/make-your-own-prime-factorization.html. In the post, he provides links to source code that you can use to generate similar pictures for yourself. There is also a link to order this picture on a T-shirt.

The Fundamental Theorem of Arithmetic appears in Volume VII of Euclid's 13-volume treatise Elements, which he wrote around 300 BC. Wikipedia has more information about the theorem here: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic.

(Found via Clare Sealy on Twitter.)

#mathematics
___

posted image

2015-03-30 21:27:11 (21 comments; 76 reshares; 279 +1s; )Open 

Pulsar Planet by Ron Miller

Ron Miller is an American illustrator and writer who specializes in astronomical, astronautical and science fiction books. This striking image by Miller shows a pulsar planet, which is a planet that orbits a highly magnetized rotating neutron star (or “pulsar”).

You can see much more of Miller's work in his recent interview (http://qz.com/366109/how-space-art-is-made/) in Quartz. He says:

I'm always specially interested in discoveries that inspire interesting scenes or visuals. For instance, a great many exoplanets are super-Jupiters that are all very much alike so there is little to choose between them visually. Once you’ve illustrated a few you have pretty much covered them all. What I look for are discoveries of planets that are very different such as an Earth-like world orbiting a red dwarf or a giant planetwith ... more »

Pulsar Planet by Ron Miller

Ron Miller is an American illustrator and writer who specializes in astronomical, astronautical and science fiction books. This striking image by Miller shows a pulsar planet, which is a planet that orbits a highly magnetized rotating neutron star (or “pulsar”).

You can see much more of Miller's work in his recent interview (http://qz.com/366109/how-space-art-is-made/) in Quartz. He says:

I'm always specially interested in discoveries that inspire interesting scenes or visuals. For instance, a great many exoplanets are super-Jupiters that are all very much alike so there is little to choose between them visually. Once you’ve illustrated a few you have pretty much covered them all. What I look for are discoveries of planets that are very different such as an Earth-like world orbiting a red dwarf or a giant planet with multiple suns.

Nowadays Miller does all his work digitally, but his pictures are often mixed media pieces, which may incorporate drawings that have been scanned and manipulated. He also creates portions of landscapes from small models he has constructed, or from photographs he has taken of textures and rocks.

Relevant links

Ron Miller: http://en.wikipedia.org/wiki/Ron_Miller_(artist_and_author)

Pulsar planet: http://en.wikipedia.org/wiki/Pulsar_planet

(I've just checked, and #spaceporn  is a tag that people actually use.)

#art  #artist  ___

posted image

2015-03-29 17:00:20 (19 comments; 35 reshares; 200 +1s; )Open 

The 30 MacMahon Cubes

Given a palette of six colours, there are 30 rotationally distinct ways to colour the faces of a cube in such a way that each face is a different colour. These 30 ways are shown in the table in the picture.

The British mathematician Percy Alexander MacMahon (1854–1929) posed some problems regarding this set of 30 cubes. Some of these problems are discussed in the recent paper Automorphisms of S6 and the Colored Cubes Puzzle by Ethan Berkove, David Cervantes Nava, Daniel Condon, and Rachel Katz (http://arxiv.org/abs/1503.07184). Two of the problems are as follows.

1. Select one coloured cube. Find seven other distinct coloured cubes and assemble all eight into a 2 × 2 × 2 cube where each face is the same colour.
2. Proceed as above, but select the cubes so that all touching internal faces also have matching colours.

Thedia... more »

The 30 MacMahon Cubes

Given a palette of six colours, there are 30 rotationally distinct ways to colour the faces of a cube in such a way that each face is a different colour. These 30 ways are shown in the table in the picture.

The British mathematician Percy Alexander MacMahon (1854–1929) posed some problems regarding this set of 30 cubes. Some of these problems are discussed in the recent paper Automorphisms of S6 and the Colored Cubes Puzzle by Ethan Berkove, David Cervantes Nava, Daniel Condon, and Rachel Katz (http://arxiv.org/abs/1503.07184). Two of the problems are as follows.

1. Select one coloured cube. Find seven other distinct coloured cubes and assemble all eight into a 2 × 2 × 2 cube where each face is the same colour.
2. Proceed as above, but select the cubes so that all touching internal faces also have matching colours.

The diagram on the left of the picture shows a solution to problem 2, due to John H. Conway. Each of the 30 cubes is labelled by a pair of distinct letters. The first (upper case) letter indexes the row of the table in which a particular cube appears, and the second (lower case) letter indexes the column of the table in which the cube appears. Suppose we want to make a 2 × 2 × 2 cube that looks like a larger version of the cube “Ab”. The way the cubes are labelled ensures that “Ba” is the mirror image of “Ab”. If we take the eight cubes that appear in the same row or column as “Ba” (but not “Ba” itself) then Conway's result ensures that these eight cubes can be reassembled into a 2 × 2 × 2 cube with the same colouring as “Ab”.

In Lemma 3.1 of their paper, Berkove et al show that a permutation of the palette of six colours will induce a permutation of the rows of the table, as well as a permutation of the columns of the table. For example, suppose we decide to switch the roles of red and dark blue in all the cubes. By inspecting the table, we see that this transforms the cube “Ab” into the cube “Ef”. According to the lemma above, this means that the entire “A” row (Ab, Ac, Ad, Ae, Af) will be moved, in some order, to the “E” row (Ea, Eb, Ec, Ed, Ef). The same argument shows that the five cubes in the “b” column will be replaced by those in the “f” column, in some order.

In fact, the act of switching the roles of blue and red will exchange the  “A” row with the “E” row. It would be reasonable to expect that the cubes in the “B” row will stay in the “B” row after the red-blue switch, but surprisingly, this does not happen! What happens instead is that the “B” row is exchanged with the “F” row, and the “C” row is exchanged with the “D” row. The reason that this can happen is that the group S6 of permutations of six objects has outer automorphisms; remarkably, this is not true for any number other than 6. 

Roughly speaking, this means that there are two completely different ways for the group S6 to act on six objects, or that there are symmetries of the group of symmetries that do not arise from symmetries of the original set of objects. [Technical explanation for mathematicians: outer automorphisms are isomorphisms from S6 to itself that do not arise from conjugation by a fixed element. These automorphisms do not preserve cycle type. This never happens for S_n for any other value of n.]

The main results in the paper by Berkove et al are about the problem of building an n × n × n cube using an arbitrary collection of the 30 cubes, such that each visible face of the big cube is the same colour, but without the condition that touching internal faces must have the same colour. (The word “arbitrary” means that one is allowed to use multiple copies of the same cube.)

In the case n=3, what this means is that we are trying to construct something that looks like a solved Rubik's Cube, but without the requirement that the six faces must have different colours. It is obvious that one needs a supply of at least 27 of MacMahon's cubes for this construction to be physically possible. However, the middle cube of the 27 is invisible and be chosen arbitrarily. Furthermore, the pieces making up the internal part of each face can also be chosen arbitrarily, because they each only have one visible face and each MacMahon cube has a face of each colour. The only nontrivial part of the construction is the remaining 27–6–1=20 cubes, which the authors call the frame of the cube.

Because a cube has twelve edges and eight corners, it is an easy exercise to prove that the frame of an n × n × n cube will be constructed out of 12n–16 MacMahon cubes. Theorem B of the paper shows that if n is at least 4, any collection of 12n–16 MacMahon cubes can be used to construct the frame of a cube with the required properties. It follows that given any supply of n^3 MacMahon cubes, it is possible to construct an n × n × n cube for which every face has a uniform colour. Theorem A of the paper shows that for n=2 and n=3, the result about the frame is no longer true. The authors show that in both these cases, it is necessary to have a supply of at least 24 MacMahon cubes to guarantee that the construction can be done. However, this still means that any collection of 27 cubes will be enough to solve the problem for n=3.

Relevant links

Percy Alexander MacMahon was one of the first people to write a book about algebraic combinatorics, which he called “Combinatory Analysis”. The two-volume work was published in 1915–16. The major index of a permutation is named after MacMahon, because he was once a major in the British Army. http://en.wikipedia.org/wiki/Percy_Alexander_MacMahon

John H. Conway: http://en.wikipedia.org/wiki/John_Horton_Conway

Rubik's Cube was invented by +Erno Rubik.

This post is partly based on the following page by Jürgen Köller. The diagram on the left is also due to him: http://www.mathematische-basteleien.de/macmahon.htm

I have posted about the outer automorphisms of S6 more than once before, most recently here: https://plus.google.com/101584889282878921052/posts/ioQW2zGjwwM

Having written this post, I am left wondering whether 30 Cube was MacMahon's rap name.

#mathematics #sciencesunday #spnetwork arXiv:1503.07184___

posted image

2015-03-22 02:55:45 (18 comments; 78 reshares; 246 +1s; )Open 

Hultman numbers: measuring genetic distance

If two genomes contain the same genes, but they have been rearranged by a sequence of reversals, translocations, fusions and fissions, how can we measure how closely related the two genomes are? It turns out that a key parameter in this problem is the number of cycles in the graph shown on the right of the picture. These cycles are enumerated by the Hultman numbers.

It is possible for a genome to experience genome rearrangements, which are evolutionary events that change the order of the genes in a genome. However, a single genome rearrangement will not scramble the genes in a random permutation, but instead it will typically cut the genome in a small number of places and reattach the pieces in a different order. A genome rearrangement that cuts the genome in exactly k places is known as a k-break.

The most... more »

Hultman numbers: measuring genetic distance

If two genomes contain the same genes, but they have been rearranged by a sequence of reversals, translocations, fusions and fissions, how can we measure how closely related the two genomes are? It turns out that a key parameter in this problem is the number of cycles in the graph shown on the right of the picture. These cycles are enumerated by the Hultman numbers.

It is possible for a genome to experience genome rearrangements, which are evolutionary events that change the order of the genes in a genome. However, a single genome rearrangement will not scramble the genes in a random permutation, but instead it will typically cut the genome in a small number of places and reattach the pieces in a different order. A genome rearrangement that cuts the genome in exactly k places is known as a k-break.

The most common types of genome rearrangement can be modelled as 2-breaks, (also known as Double-Cut-and-Join, or DCJ) which means that the genome is cut in exactly two places and the resulting pieces reattached. Examples of such rearrangements include reversals, which flip segments of a chromosome; translocations, which exchange segments of two chromosomes; fusions, which merge two chromosomes into one; and fissions, which split a single chromosome into two. The 2-break distance (or DCJ distance) between two genomes is the smallest number of 2-breaks required to transform one of the genomes into the other. 

An easier special case of the problem treats the case where the genome consists of one chromosome that is linear (as opposed to circular); in other words, the genome consists of a one unbroken string of genes. Each gene in the genome is considered to have a head and a tail, which gives it an orientation. It is also convenient to include a virtual gene numbered 0 which, if it actually existed, would link the last gene in the genome to the first gene.

The diagram on the left of the picture shows the genome graph of a toy model of a genome called Q, which has five genes numbered 1 to 5, together with a virtual gene, numbered 0. The genes in Q are denoted by solid line segments, with an arrow pointing from the tail of the gene to the head. (The tail and head of a gene are indicated by the superscripts t and h, respectively.) The dashed lines show the order in which the genes are connected in the genome. This information can be represented more concisely by the signed permutation (1, –3, 5, 2, –4). If we ignore the signs, this gives (1, 3, 5, 2, 4), which is the order in which the genes appear in the genome, reading clockwise from the virtual gene 0. The negative signs appear in front of 3 and 4 to signify that the orientation of those genes is opposite to that of the other genes.

If we define the genome P to be the one corresponding to the signed permutation (1, 2, 3, 4, 5), then we see that P and Q have the same genes, but in a different order and with different orientations. The diagram on the right of the picture shows that breakpoint graph, G(P, Q), which can be used to visualise the evolutionary closeness of P and Q. The numbers with superscripts that appear around the perimeter of the breakpoint graph are the same ones that would appear in the genome graph of P if we drew it, and the solid lines in the breakpoint graph correspond to the dashed lines in the genome graph of P. On the other hand, the dashed lines in the breakpoint graph correspond to the dashed lines in the genome graph of Q. For example, there is a dashed line from 2^t to 5^h in the breakpoint graph of G(P, Q) because there is also a dashed line from 2^t to 5^h in Q, even though the line itself appears in a different position.

The key feature of the breakpoint graph is the way it decomposes into cycles. For example, the graph G(P, Q) shown on the right of the picture splits up into three cycles, each of which contains some dashed edges and an equal number of solid edges. A cycle containing r dashed and r solid edges is called an r-cycle. In our example, the breakpoint graph contains one 1-cycle (involving the points 0^h and 1^t), one 2-cycle, and one 3-cycle. It is a theorem about breakpoint graphs that the 2-break distance between genomes P and Q is equal to n+1–c, where n is the number of genes (5 in our case) and c is the number of cycles in the breakpoint graph (3 in our case). In other words, the 2-break distance between P and Q is 3 (because 3=5+1–3). 

The (signed) Hultman number H(n,d) is the number of unichromosomal genomes with n genes whose breakpoint graph (relative to a fixed genome) contains a total of d cycles. There is a closed formula for these numbers, but it is rather complicated. The recent paper Generalized Hultman Numbers and the Distribution of Multi-break Distances by Nikita Alexeev, Anna Pologova, and Max A. Alekseyev (http://arxiv.org/abs/1503.05285) generalizes the notion of Hultman numbers from the context of 2-break distance to the context of k-break distance. Although k-break distances have not been observed in evolution, they are used in cancer genomics to measure a catastrophic event called chromothripsis in which multiple breakages happen simultaneously. The authors give recurrence relations for the generalized Hultman numbers in the unichromosomal case, but no closed formula. They intend to treat the multichromosomal case in a future paper. Asymptotically, the 2-break distance is known to be normally distributed, but it is not known what happens for general values of k.

Relevant links

The paper Efficient sorting of genomic permutations by translocation, inversion and block interchange by S. Yancopoulos, O. Attie, and R. Friedberg contains many interesting results in this area. It is freely downloadable from http://bioinformatics.oxfordjournals.org/content/21/16/3340.full.pdf+html

The unsigned Hultman numbers deal with the case where the orientations of the genes are ignored. The unsigned and signed numbers appear in the On-Line Encyclopedia of Integer Sequences at https://oeis.org/A164652 and https://oeis.org/A189507 respectively.

Wikipedia on chromothripsis: http://en.wikipedia.org/wiki/Chromothripsis

This post is about the applications to genomics that I mentioned in passing in a previous post about pancake sorting. You can find the earlier post here: https://plus.google.com/101584889282878921052/posts/GyEPJkT5769

The picture comes from page 3 of the arXiv paper by Alexeev, Pologova and Alekseyev discussed above.

#mathematics #genetics #sciencesunday #spnetwork arXiv:1503.05285___

posted image

2015-03-14 03:35:46 (53 comments; 109 reshares; 307 +1s; )Open 

How to remember 100,000 digits of pi

The retired Japanese engineer Akira Haraguchi (1946–) claims to hold the world record for reciting the most memorized digits of the number pi. He set the record starting at 9am on October 3, 2006, and reached digit number 100,000 at 1.28am on October 4, 2006. 

The event was filmed in a public hall near Tokyo. Haraguchi took 5-minute breaks to eat every two hours, and even his trips to the toilet were filmed to prove that the feat was genuine. This broke Haraguchi's previous record of 83,431 digits, which he performed from July 1–2, 2005.

The reason I say that Haraguchi claims to hold the record is that, for some reason, the Guinness World Records organization has failed to recognize this achievement, despite the existence of witnesses and detailed documentation. The Guinness-recognized record for reciting pi is67,8... more »

How to remember 100,000 digits of pi

The retired Japanese engineer Akira Haraguchi (1946–) claims to hold the world record for reciting the most memorized digits of the number pi. He set the record starting at 9am on October 3, 2006, and reached digit number 100,000 at 1.28am on October 4, 2006. 

The event was filmed in a public hall near Tokyo. Haraguchi took 5-minute breaks to eat every two hours, and even his trips to the toilet were filmed to prove that the feat was genuine. This broke Haraguchi's previous record of 83,431 digits, which he performed from July 1–2, 2005.

The reason I say that Haraguchi claims to hold the record is that, for some reason, the Guinness World Records organization has failed to recognize this achievement, despite the existence of witnesses and detailed documentation. The Guinness-recognized record for reciting pi is 67,890 digits by Lu Chao, a 24-year-old graduate student from China, who recited the digits, without error, in 24 hours and 4 minutes.

Haraguchi's technique for memorizing long lists of numbers is quite interesting. He assigns kana characters to each number, each of which represents a Japanese syllable. In his system, the digit 0 can be read as o, ra, ri, ru, re, ro, wo, on or oh; the digit 1 can be read as a, i, u, e, hi, bi, pi, an, ah, hy, hyan, bya, or byan; and there are analogous rules for the other digits.

Using this system, Haraguchi has created many stories and poems, including a story about the 12th century hero Minamoto no Yoshitsune. The first 15 digits of pi, which are 3.14159265358979, are rendered in Haraguchi's system as the words saishi ikokuni mukosan kowakunaku, whose approximate meaning is “the wife and children have gone abroad; the husband is not scared.”

Given all this, it may be surprising to learn that as a child, Haraguchi was neither a prodigy nor a mathematical genius. On the contrary, one of his teachers once made him stand to attention in the hallway as a punishment for badly failing to memorize multiplication tables of one-digit numbers.

Relevant links

Akira Haraguchi: http://en.wikipedia.org/wiki/Akira_Haraguchi

Minamoto no Yoshitsune: http://en.wikipedia.org/wiki/Minamoto_no_Yoshitsune

The Kana writing system: http://en.wikipedia.org/wiki/Kana

A 2006 article from the Japan Times about Haraguchi: http://goo.gl/d4H2pB
It looks as if the article's URL may change at some point, so you may want to Google the article's title instead: How can anyone remember 100,000 numbers?

The web site http://pi-world-ranking-list.com/ maintains a list of records of reciting from memory digits of the irrational numbers pi, e, and the square root of 2.

Picture credit: Travis Morgan

Picture source and associated poem: https://www.flickr.com/photos/morgantj/5575500301/in/photolist

#mathematics #piday  ___

posted image

2015-03-08 04:56:57 (32 comments; 80 reshares; 281 +1s; )Open 

Infinitude of the primes

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number, or is the product of prime numbers, and that the product is unique up to changing the order of the factors. A version of this result appears in Book VII of Euclid's Elements, a 13 volume mathematical treatise which was written in about 300 BC. 

In Book IX of Elements, Euclid used these ideas to construct the following famous argument, which proves that there are infinitely many primes. Suppose that p_1, p_2, ..., p_n is any finite list of distinct prime numbers and let P be the product of all of them. Since the number P+1 leaves remainder 1 when divided by any of the primes p_1, p_2, ..., p_n, it cannot have any of them as a factor. It follows that P+1 is either prime itself or has a prime factor not on the original list, which means that... more »

Infinitude of the primes

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number, or is the product of prime numbers, and that the product is unique up to changing the order of the factors. A version of this result appears in Book VII of Euclid's Elements, a 13 volume mathematical treatise which was written in about 300 BC. 

In Book IX of Elements, Euclid used these ideas to construct the following famous argument, which proves that there are infinitely many primes. Suppose that p_1, p_2, ..., p_n is any finite list of distinct prime numbers and let P be the product of all of them. Since the number P+1 leaves remainder 1 when divided by any of the primes p_1, p_2, ..., p_n, it cannot have any of them as a factor. It follows that P+1 is either prime itself or has a prime factor not on the original list, which means that the original list must have been incomplete.  The conclusion is that there must in fact be infinitely many prime numbers.

In his mathematical blog Cut The Knot,  +Alexander Bogomolny describes a simple proof of the infinitude of the primes that was new to me. The argument constructs an explicit number, f(n), which has at least n+1 distinct prime factors. This shows that arbitrarily large finite sets of prime numbers exist, from which it follows that the set of primes is infinite.

The argument, which is summarized in the picture, relies on the polynomial factorization x^4 + x^2 + 1 = (x^2 – x + 1)(x^2 + x + 1).  One key point about the factorization is that if x is a positive integer, the factors x^2 – x + 1 and x^2 + x + 1 are coprime (i.e., relatively prime) numbers. What this means is that they have no positive integer factors in common, other than 1. 

The reason that the factors  x^2 – x + 1 and x^2 + x + 1 are coprime is that any factor common to both of them, say c, would also have to divide the difference of x^2 + x + 1 and x^2 – x + 1, which is 2x. The numbers x^2 + x + 1 and x^2 – x + 1 are both odd, which forces c to divide x. However, x^2 + x + 1 and x^2 – x + 1 both leave a remainder of 1 when divided by x, which means that they also leave a remainder of 1 when divided by c, and this can only happen if c=1.

The proof can then be completed by the standard technique of mathematical induction. If n=0, the formula for f(n) shows that  f(0)=2^2 + 2^1 + 1 = 7, which is the product of n+1 primes (a single prime in this case) as claimed. If we substitute the integer x=2^{2^{n-1}} into the identity x^4 + x^2 + 1 = (x^2 – x + 1)(x^2 + x + 1), we obtain the equation f(n)=(x^2 – x + 1)f(n–1). We may assume by induction that f(n–1) is a product of (n–1)+1=n distinct primes. Since x^2 – x + 1 is coprime to f(n–1), it follows that the prime factors of x^2 – x + 1 are all different from those of f(n–1), and thus that f(n) has at least n+1 distinct prime factors.

Relevant links

+Alexander Bogomolny's original blog post can be found here:  http://www.cut-the-knot.org/proofs/InfinitudeOfPrimesViaPowersOfTwo.shtml

The values of f(n) appear in The On-Line Encyclopedia of Integer Sequences at http://oeis.org/A220161, although this application of the sequence is not (yet) mentioned there. The first four values of the sequence are 7, 21 (=3x7), 273 (=3x7x13), and 65793 (=3x7x13x241).

Euclid of Alexandria: http://en.wikipedia.org/wiki/Euclid

Euclid's Elements: http://en.wikipedia.org/wiki/Euclid's_Elements

Fundamental Theorem of Arithmetic: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

This would have made a good examination question for an undergraduate number theory course.

#mathematics #sciencesunday  ___

posted image

2015-03-01 14:54:20 (23 comments; 13 reshares; 216 +1s; )Open 

March the First

This is the first sunrise of March, which means it's time to wish “happy St David's Day” to any Welsh people reading this. It is a Welsh custom to wear a daffodil on the first of March, although as you might guess from this picture, it's too early to see any daffodils growing in Longmont, Colorado.

More information on St David's Day is here: http://en.wikipedia.org/wiki/Saint_David's_Day

I took this photo with my iPhone 5 and edited it with Snapseed.

#longmont #colorado #stdavidsday #snapseed

March the First

This is the first sunrise of March, which means it's time to wish “happy St David's Day” to any Welsh people reading this. It is a Welsh custom to wear a daffodil on the first of March, although as you might guess from this picture, it's too early to see any daffodils growing in Longmont, Colorado.

More information on St David's Day is here: http://en.wikipedia.org/wiki/Saint_David's_Day

I took this photo with my iPhone 5 and edited it with Snapseed.

#longmont #colorado #stdavidsday #snapseed___

posted image

2015-02-22 20:38:12 (85 comments; 136 reshares; 311 +1s; )Open 

A matter of scale

I'm not usually much of a fan of the Fahrenheit scale, but as this graphic illustrates, it does produce convenient numbers for the purposes of discussing the weather.

(Image credit unknown; Googling it produces many hits.)

#sciencesunday


A matter of scale

I'm not usually much of a fan of the Fahrenheit scale, but as this graphic illustrates, it does produce convenient numbers for the purposes of discussing the weather.

(Image credit unknown; Googling it produces many hits.)

#sciencesunday
___

posted image

2015-02-15 23:14:07 (23 comments; 85 reshares; 273 +1s; )Open 

Squaring and adding two

This picture from Dave Radcliffe is a digraph (directed graph) illustrating the function f(n) = n^2 + 2 mod 1000. More precisely, the little red dots in the picture represent the numbers 0 up to 999, in some order, and the grey arrows show what happens if you take one of these numbers, square it, add 2, and then take the last three digits of the result.

For example, if one starts with the number 125, squaring it gives 15625, and adding 2 gives 15627. Taking the last three digits leaves us with 627. We represent this in the picture by joining the dot numbered 125 to the dot numbered 627 with a grey line whose arrow points towards 627.

There are a lot of other numbers that map to 627 under this function. Any numbers n that leave a remainder of 25 when divided by 50 (i.e., any n with n = 25 mod 50) will have the same property. There are... more »

Squaring and adding two

This picture from Dave Radcliffe is a digraph (directed graph) illustrating the function f(n) = n^2 + 2 mod 1000. More precisely, the little red dots in the picture represent the numbers 0 up to 999, in some order, and the grey arrows show what happens if you take one of these numbers, square it, add 2, and then take the last three digits of the result.

For example, if one starts with the number 125, squaring it gives 15625, and adding 2 gives 15627. Taking the last three digits leaves us with 627. We represent this in the picture by joining the dot numbered 125 to the dot numbered 627 with a grey line whose arrow points towards 627.

There are a lot of other numbers that map to 627 under this function. Any numbers n that leave a remainder of 25 when divided by 50 (i.e., any n with n = 25 mod 50) will have the same property. There are twenty such numbers in the range 0 to 999: 25, 75, 125, and so on, all the way up to 975. Each number n in this list satisfies n^2 + 2 = 627 mod 1000. 

What this means is that point corresponding to 627 in this list is one of the five points with twenty incoming arrows, shown near the top of the picture. Another number with twenty incoming arrows is 102: any number n that ends with the digits 10 or 90 (i.e., n = ±10 mod 100) has the property that n^2 + 2 ends in the digits 102. The other three such numbers are 402 (which corresponds to n = ±20 mod 100), 902 (which corresponds to n = ±30 mod 100), and 602 (which corresponds to n = ±40 mod 100).

There are two other striking points in the picture that have even more incoming arrows: forty, in fact. The forty numbers of the form ±5 mod 100 all map to 27, and the forty numbers of the form ±15 mod 50 all map to 227.

Although this may be recreational mathematics, the resulting graph provides an illustration of some other mathematical phenomena, as well as being aesthetically pleasing. One of these is that, if one ignores the directions of the arrows, the graph features a huge connected component that contains most of the vertices. In network theory, this sort of thing is called a giant component. One would expect to see something like this in a model of the connections between individuals in an established social network.

Another feature of the graph is that it has no self-loops; in other words, no arrow connects a point to itself. The reason for this is that the congruence n = n^2 + 2 mod 1000 has no solutions in integers; this in turn follows from the easier observation that n = n^2 + 2 mod 5 has no solutions. In contrast, the function g(n) = n^2 mod 1000 would not have had this property, because g(0) = 0.

Relevant links
This picture was recently posted on Twitter by Dave Radcliffe (@daveinstpaul). I think that he is also the creator of the picture.

Another aesthetically pleasing mathematical object that is generated by repeated squaring and adding is the famous Mandelbrot set: http://en.wikipedia.org/wiki/Mandelbrot_set

Wikipedia on giant components: http://en.wikipedia.org/wiki/Giant_component

There is a graph with a countably infinite set of vertices called the random graph. If its parameters are tuned appropriately, this graph also features a giant component. Here's a post by me from two years ago about the random graph: https://plus.google.com/101584889282878921052/posts/34guwy4ftWX

#mathematics #sciencesunday  ___

posted image

2015-02-14 04:54:35 (22 comments; 71 reshares; 226 +1s; )Open 

Happy Valentine's Day!

This animation is a good illustration of a pantograph. Wikipedia says:
A pantograph (Greek roots παντ- "all, every" and γραφ- "to write", from their original use for copying writing) is a mechanical linkage connected in a manner based on parallelograms so that the movement of one pen, in tracing an image, produces identical movements in a second pen. If a line drawing is traced by the first point, an identical, enlarged, or miniaturized copy will be drawn by a pen fixed to the other. Using the same principle, different kinds of pantographs are used for other forms of duplication in areas such as sculpture, minting, engraving and milling.

The Wikipedia page http://en.wikipedia.org/wiki/Pantograph includes this animation, which is attributed to the user AlphaZeta.

#happyvalentinesday

Happy Valentine's Day!

This animation is a good illustration of a pantograph. Wikipedia says:
A pantograph (Greek roots παντ- "all, every" and γραφ- "to write", from their original use for copying writing) is a mechanical linkage connected in a manner based on parallelograms so that the movement of one pen, in tracing an image, produces identical movements in a second pen. If a line drawing is traced by the first point, an identical, enlarged, or miniaturized copy will be drawn by a pen fixed to the other. Using the same principle, different kinds of pantographs are used for other forms of duplication in areas such as sculpture, minting, engraving and milling.

The Wikipedia page http://en.wikipedia.org/wiki/Pantograph includes this animation, which is attributed to the user AlphaZeta.

#happyvalentinesday___

Buttons

A special service of CircleCount.com is the following button.

The button shows the number of followers you have directly on a small button. You can add this button to your website, like the +1-Button of Google or the Like-Button of Facebook.



You can add this button directly in your website. For more information about the CircleCount Buttons and the description how to add them to another page click here.

Richard GreenTwitterFacebookCircloscope