Tag Archives: mathematics

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 :)


Computer or maths books for kids – any recommendations?

In a fortnight my Code Club will end with the last Friday of the school year – and I want to leave my small (4) group with a useful present – a book about maths or computing that will engage and stretch them (they are 10/11 and bright but, as far as I can tell not budding Nobel winners – though I could always be wrong!).

What would you recommend?

The proof that frightened Pythagoras

I have been meaning to do this for a while …

Pythagoras was said to be shocked by the proof that \sqrt 2 is an irrational number (i.e., that it cannot be represented as a ratio of two whole numbers). The proof (by contradiction) is a simple one.

If \sqrt 2 is rational then \sqrt 2 = \frac{a}{b} and 2 = \frac{a^2}{b^2} where a and b are the smallest nominator and denominator possible, i.e, in the lowest terms.

Hence a^2 = 2b^2 and so a must be even (as two odd numbers multiplied always give an odd number – let l = 2x and m = 2y be even numbers then (l + 1)(m + 1) = lm + l + m + 1 ). Hence a = 2k .

But we also have 4k^2 = a^2 and thus 4k^2 = 2b^2 and b^2 = 2k^2 and so b is even.

So we have a and b sharing a common factor of 2, so they cannot be the nominator and denominator of the fraction in the lowest terms.

But if a and b are both even then they share a common factor of 2 and \frac{a}{b} = \frac{2k}{2p} = \frac{k}{p} : implying that a = k and a = 2k , an obvious contradiction: hence \sqrt 2 cannot be a rational.

Update: I have made the final step of this shorter and clearer.

Further update: I have been told (see comments below) I would have been better sticking with a clearer version of the original ending ie., we state that \frac{a}{b} are the lowest terms. Then, plainly as they have a factor in common (2) they cannot be the lowest terms and so we have a contradiction. Would be great if someone could explain why we cannot use the a = 2k = k contradiction.

And another update: Should have stuck with the original explanation – which I have now restored in a hopefully clearer way. The comments below are really interesting and from serious mathematicians, so please have a look!

Euler’s formula proof

Reading An Introduction to Laplace Transforms and Fourier Series I reach the point where it is stated, rather axiomatically, that: e^{ix} = \cos x + i \sin x .

This is a beautiful formula and has always suggested to me some sort of mystical inner mathematical harmony (yes, I am a materialist, but I cannot help it).

But these days I also want to see the proof, so here is one:

We know that complex numbers can be described in polar co-ordinates:

z = |z| (\cos \theta + i\sin \theta)

So too e^{ix} = r(\cos \psi + i \sin \psi) where r and \psi depend on x .

Now (and applying the product rule) \frac{d}{dx}e^{ix} = ie^{ix} = \frac{dr}{dx}(\cos \psi + i\sin \psi) + \frac{d \psi}{dx}r(-\sin \psi + i \cos \psi)

So we equate the real and imaginary sides of both sides of this equality we have:

ie^{ix} = (\cos \psi \frac{dr}{dx} - r \sin \psi \frac{d \psi}{dx}) + i(\sin \psi \frac{dr}{dx} + r \cos \psi \frac{d\psi}{dx})

Then, recalling e^{ix} = r(\cos \psi + i \sin \psi) , we have ir (\cos \psi + i \sin \psi) = ir \cos \psi - r sin \psi = ( \cos \psi \frac{dr}{dx} - r \sin \psi \frac{d\psi}{dx}) + i( \sin \psi \frac{dr}{dx} + r \cos \psi \frac{d\psi}{dx})

By inspection we can see that \frac{dr}{dx} = 0 and \frac{d\psi}{dx} = 1, giving us:

ie^{ix} = - r \sin \psi + ir \cos \psi and multiplying both sides by i we have: -e^{ix} = -r \cos \psi - i r \sin \psi

Reversing the signs: e^{ix} = r \cos \psi + i r \sin \psi

But what of r and \psi ? Well, we have \frac{dr}{dx} = 0 and \frac{d \psi}{dx} = 1.

So r is constant with respect to x while \psi varies as x .

If we set x = 0 then e^{i \times 0} = 1 – a wholly real number, so \sin \psi = 0 and \psi = 0. Thus r ( \cos 0 ) = e^0 = r = 1 and we can replace \psi with x throughout.

Hence: e^{ix} = \cos x + i \sin x .

Centenary of Paul Erdős

Paul Erdős was born 100 years ago today.

picture of paul erdös at student seminar in Bu...
picture of paul erdös at student seminar in Budapest (fall 1992) (Photo credit: Wikipedia)

As the most prolific mathematician of all time I am rather disappointed he hasn’t been deemed worth a “Google doodle“.

Erdős was victimised in the McCarthy era in the US and certainly seems to have had a warm relationship with the Hungarian Communist authorities (though there is nothing to suggest he was a spy), though eventually boycotted the country over its treatment of Israeli citizens.

To see some of his work have a look at the Erdős-Straus conjecture.