A further suggestion that P!=NP

There are a class of mathematical problems known as “P”: these can be solved in “polynomial time” or, to cut to the chase, they are problems for which we know how (algorithmically) to solve when we see them. A trivial example is -if you are given a number X, how do you calculate Y which is  X times 10. (If you don’t know the algorithm to multiply a base 10 number by 10 then stop reading this now!)

There are another class of problems – the “NP” (as in “Not P”) problems for which we know how to check if we have a correct solution to the problem, but not how to solve the problem itself. A typical example is producing the factors of a very large number created by multiplying two very large prime numbers together. If I gave you the factors you could probably verify that their product was the larger number, but if I gave you the larger number you might be here until the end of the universe trying to figure out what the factors were, as the only real way we know of (today) is to eliminate every prime number, one by one.

But, it may just be the case that “NP” problems are actually “P” problems after all, and it’s just we have yet to discover the algorithm to solve them. If we could show that NP=P in this way then we could do things like simply draw up train and class timetables instead of fiddling with expensive and approximate software tools to get these right.

But we’d also be able to crack internet encryption, which essentially relies on large numbers produced by two very large primes (public and private keys). These “one way functions” – i.e. bits of maths easy to do one way (multiply the two primes) but essentially impossible the other way – factor their product – are at the core of internet encryption.

Encryption and mathematics are deeply entwined and so communications intelligence agencies like the NSA in the United States and GCHQ in the UK are also centres of mathematical excellence – trying to break codes and, we must assume, test whether P=NP after all.

So this fascinating story about the state of encryption software in the US might suggest to us that the NSA have not been able to prove P=NP (most mathematicians think P!=NP but that is not proved either).

(The story essentially suggests that the NSA have paid to have a widely used form of internet encryption – Dual_EC_DRBG – operate like an Enigma Machine where the starting positions are always known. As with Enigma, once you had that, everything else would fall into place and what looks like a random sequence of letters is quickly converted to plain text.

Of course it could all be paranoid nonsense or even a cover to make us think that they haven’t cracked the P=NP problem (as, after all, you’d guard that secret with everything you’d got – except internet encryption!) – paying out a few million dollars to make someone think you had doctored one way functions because you could crack them no other way would be money very well spent!


A further point about Scottish referendum polls

Free Celtic Nationalist Jesus Surfers Sunshine...
Free Celtic Nationalist Jesus Surfers Sunshine Vote Yes Van (Photo credit: GerardFerry)

One (smallish) point I left out of my discussion of opinion polling a few days ago was that the “margin of error” for a 95% confidence interval varies according to the reported score.

This range of possible error is actually highest for parties or opinions that score 50% – which is more or less where the “no” vote in the Scottish referendum is polling now – for a 1000 sample poll with 95% confidence interval the range at 50% is:

\pm 2 \times \sqrt{\frac{0.5 \times 0.5}{1000}} = \pm 3.2\%

Good news for the yes camp? Not really, because apart from the obvious point that it is mathematically equally likely to be an over-estimate as an under-estimate, the corollary is that the error in smaller figures is less. For 30%, roughly where the yes campaign are, the error is:

\pm 2 \times \sqrt{\frac{0.3 \times 0.7}{1000}} = \pm 2.9\%

More on the Riemann sphere

In my previous discussion on the Riemann Sphere I talked of it as a closed sphere of infinite extent, but it can also be represented as a sphere of finite extent.

Display of complex number on the Riemann sphere.
Display of complex number on the Riemann sphere. (Photo credit: Wikipedia)

In this case imagine a sphere centred on the origin and of unit radius. Then any complex number can be represented as a point on the sphere’s surface by simply drawing a line from the pole to that point on the (complex) plane – where the line intersects the sphere is the point that represents the number (numbers of magnitude of less than one are represented by the underside of the sphere).

This is, in one sense, a consequence of the infinity of the continuum – we are projecting an infinite line on to a finite line, but as the points on both lines have the same cardinality there can be a one to one correspondence – it’s another thing of beauty, I think.

y^2 + x^2 = 1

This entry is based on the prologue for the book Elliptic Tales: Curves, Counting, and Number Theory (challenging but quite fun reading on the morning Tube commute!):
y^2 + x^2 = 1 is the familiar equation for the unit circle and in the prologue the authors show how a straight line with a rational slope intersects a circle at two point which is rational i.e, of the form (x, y) = (\frac{a}{b},\frac{c}{d}) then the second point is also rational and that all such lines trace out the full set of rational points on the circle.

But then the book goes further –

We say that circle C has a “rational parametrization”. This means that the coordinates of every point on the circle are given by a couple of functions that are themselves quotients of polynomials in one variable. The rational parametrization for C we have found is the following:

(x,y) = (\frac{1 - m^2}{1+m^2},\frac{2m}{1+m^2})

So this is what I wanted to check… it surely isn’t claiming that all the points on the circle are rational, is it? Merely that the above – if m (which corresponds to the slope of our line through the two points) is rational, generates the full set of rational points on the circle. Because if m is not rational then the second point will not be either? Is that right?

From http://tilings.math.uni-bielefeld.de/substitution_rules/square_chair

Maths or physics ‘A’ level student? Then read this book…

Differences between Euclidean and non-Eucl. ge...
Differences between Euclidean and non-Eucl. geometries (Photo credit: Wikipedia)

The Language of Mathematics: making the invisible visible

Although I want to warmly recommend this book, it is not what I expected when I started reading it – another popular explanation of maths that just might contain an insight or two.

Instead it is much more like a tour d’horizon of a first year of a degree course in mathematics – but without much of the maths itself.

We get a quick tour of number theory, logic, infinitesimals, Euclidean and non-Euclidean geometry, group theory, topology, Gaussian distributions, Bayesian probability, relativistic space-time and super-symmetry.

The absence of detailed mathematical explanations for much of the ideas presented here (and the occasionally sloppy writing) can be a bit frustrating, but generally Keith Devlin gets away with it because he paces the book well and sticks to his underlying theme – that mathematics is the science of patterns and that patterns underly much of reality.

As such the book taught me a lot and reminded me of quite a bit too – I wish I had read it when I was an ‘A’ level student or even when I was an undergraduate.

Well worth buying and reading – though strangely it seems to be about to go out of print in Britain. My copy suggests it is the 13th impression of the 2000 edition, so clearly demand is high – at least in the United States – perhaps readers on this side of the pond are put off by two of the least important but most egregious errors – the description of the Scots James Clerk Maxwell and the Scots-Irish William Thomson (Lord Kelvin) as “English” within three pages of each other.

Some questions about group theory

I am trying to read too many books at the moment, and one of them is Keith Devlin’s fascinating, but occasionally infuriating The Language of Mathematics: Making the Invisible Visible.

The book skates through mathematical concepts at a dizzying speed – often pausing only briefly to explain them. It is allowed to do this, it is not a text book. I wish I had read it before because it does at least explain the bare background to some concepts I have come across in the last year while reading other maths books – such as Fermat’s method of infinite descent.

But it is sometimes a little imprecise – at least I think so – in its language. And so it sometimes confuses almost as much as explains – and this is where I come to group theory.

Now, before I read Chapter 5 of the book I knew that groups were like sets, except they were not the same. And I had – while reading Higgs (another one of the too many books right now) come across the (essentially unexplained in that book) concept of the “symmetry group” when discussing sub-atomic particles. Devlin’s book brilliantly and effortless explains what groups are and does so, handily enough, through the question of transformational symmetry.

But this is where the questions begin.

Let us examine the case of a (unmarked) circle. As the book states:

The transformations that leave the circle invariant are rotations round the center (through any angle, in either direction)

Thus there are surely an infinite number of these.

The book then defines three conditions for a group (and later a fourth condition for an abelian group):

G1 For all x, y, z in G , (x * y) * z = x * (y * z) (where * is an operation)

G2 There is an element e in G such that x * e = e * x = x for all x

G3 For each element x in G , there is an element y in G such that x * y = y * x = e (where e is as in G2)

We can see that G1 is a stipulation of associativity, G2 is of the existence of an identity element and G3 of an inverse transformation.

(The condition for an abelian group is that of commutativity, ie., that x * y = y * x for all in G – but that is not particularly relevant here.)

So back to our circle. The book states that there is precisely one inverse transformation for each element – ie., that y in G3 is unique for each x . But in our circle, how can this be so? Is not each and every transformation its own inverse as well as the inverse of every other transformation? Because the unmarked circle is, by definition, exactly the same – indeed doesn’t this lead us to conclude that there is only one transformation of the circle – namely the identity transformation (ie., the one where we do nothing) ? At least it feels like a contradiction to me…

Which then takes me on to the precise case of the completely irregular shape. This has a symmetry group with a membership of  one, namely the identity transformation, but then the book (and this is, I suspect, a sloppy piece of wording that fails to take account of degenerate cases rather than what looks like a contradiction) states:

Condition G2 asserts the existence of an identity element. Such an element must be unique, for if e and i have the property expressed by G2 then … e = e * i = i

Which is surely precisely what we do have!

Now, I don’t for an instant think I have ripped a hole in the fabric of mathematics – I just think I need this explained to me a bit more clearly: so how many rotational (or reflectional) transformations are in the symmetry group of an unmarked circle and presumably there is no problem with e = i in single member groups? Can anyone help?

Update: Ian Peackcock (@iancpeacock) makes the point to me that, of course, all symmetrical transformations look the same – that is the point. So I guess that knocks down the contradiction between infinite and one – and presumably we can put down the book’s claims about identity being unique to just sloppy wording – after all if a group has a single member, it is of course unique?

A neat contradiction

English: A contradiction in terms! Whatever go...
(Photo credit: Wikipedia)

the smallest natural number that cannot be described by an English sentence of up to one thousand letters

Such a number cannot exist – if we take the sentence above as a legitimate description of the number – as the sentence above both describes the number that cannot be described in less than one thousand letters and yet takes quite a lot less than one thousand letters to do it.

Stolen from P, NP, and NP-Completeness: The Basics of Computational Complexity – which is a less than easy read (for me at least).

What ever happened to errata?

Julian Havil’s The Irrationals: A Story of the Numbers You Can’t Count On is a fascinating and quite challneging (for me, at least) book.

Pi: The Transcendental Number
Pi: The Transcendental Number (Photo credit: tj.blackwell)

But it also contains at least two errors – that I can spot – one on the inside dust cover and one on page 79 where roots are presented as squares. I doubt either are the author’s responsibility.

Perhaps there are others – page 79 is as far as I have got and I am not an expert reader.

I am disappointed that Princeton University Press have not seen fit to publish an errata. Does anyone publish them these days?

Graph cartesian products

On the basis that knowing some more about Graph Theory won’t do me any harm when thinking about operating system behaviour, I am reading about that too right now.

But I found the book’s explanation of a Graph Cartesian Product rather less than full, so here is my attempt to make it a bit clearer.

Say we have graph G_1 with vertices (v_1, v_2, v_3) and graph G_2 with vertices (w_1, w_2, w_3, w_4) , then our cartesian product graph is G_3 with vertices ((v_1, w_1), (v_1, w_2), (v1, w_3), (v_2, w_4),(v_2, w_1), (v_2, w_2), (v2, w_3), (v_2, w_4),(v_3, w_1), (v_3, w_2), (v3, w_3), (v_3, w_4))

Which vertices in this new graph are adjacent?

The vertices are adjacent if – and only if – taking the new vertices to be of the form (v_n, w_n) (v^{\prime}_n, w^{\prime}_n) – if v_n = v^{\prime}_n and w_n is adjacent to w^{\prime}_n in G_2 OR w_n = w^{\prime}_n and v_n is adjacent to v^{\prime}_n in G_1.

A circle inscribing a pentagon

This is also from The Irrationals – though I had to ask for assistance over at Stack Exchange to get the right answer (as is so often the case the solution is reasonably obvious when you are presented with it).

Anyway, the question is: given a regular pentagon (of sides with length of 10 units) which is inscribed by a circle, what is the diameter of the circle?

This figure helps illustrate the problem:


We are trying to find 2R and we know that x=10 .

If we knew r then we could answer as R^2 = r^2 + (\frac{x}{2})^2 . We do not know that but we do know that \sin(\frac{\pi}{5})=\frac{x}{2R} and hence, from the \cos^2 + \sin^2 = 1 identity: \sin\frac{\pi}{5} = \frac{10}{2R} = \sqrt{1-\cos^2(\frac{\pi}{5})}.

From our knowledge of the pentagon with sides of unit length (you’ll have to trust me on this or look it up – it’s too much extra to fit in here) we also know that \cos(\frac{\pi}{5}) = \frac{\phi}{2} = \frac{1}{4}(1+\sqrt{5}), where \phi is the golden ratio.

Hence 2R = … well, the rest is left as an exercise for the reader 🙂