You're reading: Posts By Christian Lawson-Perfect

Steinberg’s conjecture is false

Conjecture   Every planar graph without 4-cycles and 5-cycles is 3-colourable.

Nope!

In a paper just uploaded to the arXivVincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado show the construction of a graph with no cycles of length 4 or 5 which isn’t 3-colourable: it isn’t possible to assign colours to its vertices so that no pair of adjacent vertices have the same colour, using only three different colours. This is a counterexample to a conjecture of Richard Steinberg from 1976.

The problem was listed in the Open Problem Garden as of “outstanding” importance.

Read the paper: Steinberg’s conjecture is false

via Parcly Taxel on Twitter

Approximate a ratio by folding a piece of paper

towel-ratio

Warning: you could make a very strong argument I’ve thought far too much about something inconsequential. If that makes your stomach turn, look away now.

This morning in the shower, I had an idle thought about my towel. It was, as always, folded neatly on the toilet seat. A problem that’s been bugging me for a few days is how to pick up the towel by a section of the long edge, so when it unfolds it’s the right way round.

* quiet in the back

The problem is that the short edge and the long edge look the same, and once I’ve folded the towel over a couple of times and had a shower only a madman* would remember which is which. But my towel isn’t square, so it occurred to me that either the longer or the shorter edge, after folding, could be the edge I want. Since I never make a diagonal fold, the long edge is only ever folded on top of the long edge, and likewise for the short edge. I fold the towel until it fits comfortably on top of the toilet seat, and by the time I’ve finished my shower I can’t be relied upon to remember which sequence of folds I did.

Which got me thinking about the ratio between the width and height of my towel: if I know this ratio then, by looking at the towel and counting the number of folds, I can work out which folds I’ve done, and hence which of the sides will unfold to be the long edge.

Maths Object: Correntator

Here’s another one of my favourite maths objects: the Correntator. It’s a simple mechanical tool to add up amounts of money. I bought it for about a tenner (new money) at a market.

This video is extremely shonky. Blame my phone, which can’t bring itself to record for more than 250 seconds at a time.

More information about the Correntator.

Not mentioned on The Aperiodical, March 2016

There’s been a lot of maths news this month, but we’ve all been too busy to keep up with it. So, in case you missed anything, here’s a summary of the biggest stories this month. We’ve got two new facts about primes, the best way of packing spheres in lots of dimensions, and the ongoing debate about the place of maths in society, as well as the place of society in maths.

A surprisingly simple pattern in the primes

Kannan Soundararajan and Robert Lemke Oliver have noticed that the last digits of adjacent prime numbers aren’t uniformly distributed – if one prime ends in a 1, for example, the next prime number is less likely to end in a 1 than another odd digit. Top maths journos Evelyn Lamb and Erica Klarreich have both written very accessible pieces about this, in the Nature blog and Quanta magazine, respectively.

Oliver and Soundararajan’s paper on the discovery is titled “Unexpected biases in the distribution of consecutive primes”.

GCHQ has declassified James Ellis’s papers on public key cryptography

secret-squirrel-gchq

Robert Hannigan, the Director of British intelligence agency GCHQ, gave a speech at MIT recently on the currently contentious issue of backdoors into encryption.

To accompany his speech, and maybe to reaffirm GCHQ’s credentials on the subject, he published two papers written by James Ellis in 1970 about what would become public key encryption: “The Possibility of Secure Non-Secret Digital Encryption” and “The Possibility of Secure Non-Secret Analogue Encryption”.

The story famously goes that two decades after Rivest, Shamir and Adleman announced the RSA algorithm for public key cryptography, GCHQ admitted that their employee Clifford Cocks had come up with essentially the same thing four years before, inspired by James Ellis’s papers on the possibility of cryptography without a secret key.

More information

Rober Hannigan’s speech, Front doors and strong locks: encryption, privacy and intelligence gathering in the digital era.

Read the papers: “The Possibility of Secure Non-Secret Digital Encryption” and “The Possibility of Secure Non-Secret Analogue Encryption” by James Ellis.