Tag: Number Theory

Struggling with coin tossing paradox


The method of Eratosthenes used to sieve out p...
The method of Eratosthenes used to sieve out prime numbers is employed in this proof. (Photo credit: Wikipedia)

I was led to this by the discussion on the non-random nature of prime numbers – as apparently it inspired one of the authors of the paper that noted this. I am struggling a bit with the maths of this, so hopefully writing it out might either help me grasp what is wrong with my exposition or else somebody will explain to me what I am doing wrong.

The paradox, taking H for heads and T for tails, is this – if you have a coin and toss it twice there is an equal probability (0.25) that you will see the sequence HH or HT.

But if you have two coins and toss them then, on average, it will take six tosses before you see HH but ocannly four to see HT.

I have no problem with the HT sequence – inside four tosses you can reach this via:

HT
HHT
HHHT
THT
THHT
TTHT

which a simple sum of probabilities shows comes to: \frac{4}{16} + \frac{2}{16} + \frac{1}{16} + \frac{2}{16} + \frac{1}{16} + \frac{1}{16} = \frac{11}{16}, greater than half, while just three tosses would give a probability of 0.5.

So, the issue is with the HH combination. With just five tosses we can get:

HH
HTHH
HTTHH
THH
TTHH
TTTHH
THTHH

Which sums to: \frac{8}{32} + \frac{2}{32} + \frac{1}{32} + \frac{4}{32} + \frac{2}{32} + \frac{1}{32} + \frac{1}{32} = \frac{19}{32} – i.e., more than half (four tosses give us odds of 0.5).

So where is the flaw in my reasoning?

Related articles

The beauty of the Riemann sphere


renering of the graph of the Sphere of Rieman
rendering of the graph of the Sphere of Riemann (Photo credit: Wikipedia)

Reading Elliptic Tales: Curves, Counting, and Number Theory today, I came across the Riemann Sphere – a thing of beauty: a closed surface of infinite extent.

I will explain the maths of the sphere in a moment, but I am left wondering if one of two things apply:

(a) We are terrible at teaching maths in this country because although it produces such beautiful concepts too many children – perhaps a majority – think it is a thing of drudgery; or

(b) The appeal of maths is inherently limited and the number of people fascinated by a concept as seemingly contradictory as a closed surface of infinite extent is always going to be limited.

Anyway, here’s an explanation of the sphere…

We want to think about infinity but we will, at first, restrict our thinking to a single, straight line. We can say how far along this line we are by measuring the distance from an arbitrary starting point. So, we could be 1 unit along, \pi units along or -\pi units along and so on.

In fact we can represent where we are on the line by a ratio \frac{a}{b} and represent each point in the form a:b . So \pi can be \pi:1 for instance, so we are not restricted to the rationals in this form.

Now , think of this as one way to get further and further from our arbitrary starting point – first we go 1 unit and so are at 1:1 then we go to 1:\frac{1}{2} then \frac{1}{3} and so on – and we approach the limit 1:0 which is the furthest we can possibly be and which we call infinitely far away from our starting point.

But what if we went in the other (negative) direction? Then we’d go to 1:-1 , 1:-\frac{1}{2} and so on … but at the limit we’d go to 1:0 – exactly the same place we’d go to if we started in the opposite direction: hence the “negative” and “positive” infinities are the same and this line is actually a loop.

To go from this loop to the sphere we need to consider complex numbers. Here every number is of the form a + b\Im, where \Im is the square root of -1.

Then we have to plot numbers on a plane, not a line and so every number has two co-ordinates, one of the form we discussed above in the form of the reals – eg 1:\frac{1}{7} and one along the imaginary axis of the form \Im:\frac{1}{7} – we thus we get an infinite set of infinite closed loops – a sphere.

Related articles

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?

Related articles

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.

Related articles

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

Related articles

Yitang Zhang latest…


A few weeks ago the world of maths was pleasantly shocked when a hitherto largely unnoticed mathematician, Yitang Zhang, demonstrated that there are infinitely many (pairs of primes) primes at most 70,000,000 apart – ie find a prime, any prime, no matter how large, and there is another two  at most 70,000,000 numbers away.

Zhang’s story is a great one – someone who loved maths so much he kept plugging away even when most other people would have given up and gotten a “proper” job. And, then, finally it all pays off with a breakthrough discovery of enormous importance.

But this his paper was published other have been working to refine his work and the latest proposal – this has been updated even since I started writing this blog minutes ago – is that there are infinitely many primes just 388,284 numbers apart.

Related articles

A (partial) answer to my Goedelian conundrum?


Douglas Hofstadter in Bologna, Italy
Douglas Hofstadter in Bologna, Italy (Photo credit: Wikipedia)

Last week I puzzled over what seemed to me to be the hand waiving dismissal, by both Alan Turing and Douglas Hofstadter of what I saw as the problem of humans being able to write true statements that the formal systems employed by computers could not determine – the problem thrown up by Goedel’s Incompleteness Theorems.

Well, Douglas Hofstadter has now come to his own (partial) rescue as I continue to read on through Godel, Escher, Bach – as he describes Tarski’s Theorem, which essentially states that humans cannot determine all such statements either (unless we posit the Church-Turing thesis is wrong, of course and there is some inner human computational magic we have yet to describe).

I am now going to quickly run through Hofstadter’s exposition – it might not mean too much to those of you not familiar with GEB, but if so and if you are interested in computation (and genetics and music) and you want to improve your mind this summer you could always think about buying the book. I don’t promise it’s an easy read, the style can vary from the nerdy to the deeply frustrating, but it is still a rewarding read.

So here goes:

We imagine we have a procedure that can determine the truth of a number theoretical statement, i.e.:

TRUE\{a\} can tell us whether the number theoretical statement with Goedel number a is true.

So now we posit, T with Goedel number t :

\exists a:<\sim TRUE\{a\} \wedge ARITHMOQUINE\{a^{\prime\prime},a\}>

Now, of you have read GEB you will know that to “arithmoquine” a number theoretical statement is to replace the free variable – in this case a^{\prime\prime}, with the Goedel number for the statement itself…

\exists a:<\sim TRUE\{a\} \wedge ARITHMOQUINE\{SSS \ldots SSS0,a\}>

Which we can state as “the arithmoquinification of t is the Goedel number of a false statement”.

But the arithmoquinification of t is T ‘s own number, so this statement is the equivalent of saying “this statement is false”: just another version of the famous Epimenides Paradox, but one that is decidedly not hand waving in form: it’s about natural numbers.

The outcome is that TRUE\{a\} cannot exist without our whole idea of natural numbers collapsing and we are forced to conclude there is no formal way of deciding what is a true statement of theoretical number theory using only theoretical number theory – and so humans are no better off than computers in this regard: we use concepts from without the formal theory to establish truth and we could surely program our computers to do the same. Turing’s “imitation game” conception of intelligent machines thus survives.

At least I think so!

Related articles

How I discovered the fundamental theorem of arithmetic by chance


Cover of "Gödel, Escher, Bach: An Eternal...
Cover via Amazon

Actually, of course, I rediscovered it.

I have been attempting to read, for the third time Douglas Hofstadter‘s celebrated Godel, Escher, Bach: I bought a copy in Washington DC in 2009 and loved it (though didn’t get very far before I put it down for some reason) but I have always struggled to get deeply into it: it’s plainly a great book – though having read more on Turing these days I am not sure I’d subscribe to what appears to be the core thesis – but it’s not an easy read.

(Though Hofstadter’s preface did inspire me three years ago to read the brilliantly compact Godel’s Proof– buy, steal or borrow a copy if you are at all interested in maths.)

This time round I am feeling more confident I’ll make progress, it just seems a bit easier to grasp – possibly because I am feeling more confident about maths these days (not that there is any higher maths in it – but grasping some of the more complex stuff does seem to help with all of it.)

So I got the part known as the “MU puzzle” – can you go from the axiom MI to the theorem MU following the rules of the formal system he sets out. I thought – oh, yes, easy, just find a power of two that is also a multiple of three – and in my head I start going 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 – a list I have been familiar with for thirty three years or so. But none of them are multiples of three.

Now, presumably anyone who knows anything about prime numbers has by now said “of course they are not, haven’t you heard of the fundamental theorem of arithmetic?” – well it seems the answer to that is “err, no”.

Or, if I had, I never really grasped its meaning. Each number cn be factorised into a unique set of primes (if a prime then just itself, of course). That precludes any power of two having as a factor any other prime number (of which three is of course one). It’s really epically important in terms of understanding numbers and I am slightly shocked and puzzled I have never really understood it before now.

Related articles

Finding “new” primes


To accompany How to Solve it, I also bought How to Prove It: A Structured Approach which deals with the construction of proofs.

I am puzzled, though, by its treatment of Euclid’s famous proof of the infinite order of the set of primes.

Not because it gets the proof wrong – but because I do not understand the answer it gives to one part of one exercise.

Now the proof (this is my summary not the book’s) runs like this:

Suppose you decide that the number of primes is finite, the set p_1 ... p_n (where p_1 is 2 and so on). You then form a number m from the product of these primes plus 1 – m = p_1 \times p_2 \times ... \times p_n + 1. This number cannot be a prime and yet is not divisible by any of the primes. Hence we have a contradiction and the set of primes must be infinite.

Now the book asks the following:

The proof of [the theorem] gives a method for finding a prime number from any in a given list of prime numbers:
(a) Use this method to find a prime different from 2, 3, 5 and 7
(b) Use this method to find a prime different from 2, 5 and 11

Now, the first seems easy enough:

p_{new} = 2 \times 3 \times 5 \times 7 + 1 = 211

and the book agrees with my calculation.

But what of the second?

Well, 2 \times 5 \times 11 + 1 = 111, but that’s not a prime at all. The book gives the answer as “3 and 37” (which obviously are primes) but I cannot see what formal method is used from the list of “2, 5 and 11” to generate these numbers.

The obvious suggestion is that I have missed the “method” in the theorem as set out in the book, but I have reread it many times and I cannot see where I have missed anything (it is really just a longer version of my summary).

Can someone set out the formal method that would work with a partial list such as 2, 5 and 11?

Related articles