by Chris Waring
Polish mathematician Wacław Sierpiński (1882–1969) invented another straightforward geometrical fractal, again based on a triangular theme. For Sierpiński’s triangle, you start with a solid equilateral triangle. You then cut out an equilateral triangle from the middle, which gives you three smaller triangles. At each iteration you cut a triangle out of the middle of any remaining triangles to produce the fractal.
Again, we see self-similarity, as each part of the triangle looks like the whole.
It turns out that there are two other unexpected ways to draw Sierpiński’s triangle. The first harks back to Blaise Pascal and his triangle. If you shade in all the odd numbers in the triangle, you get Sierpiński’s triangle.
The second way is an example of a Chaos Game. You draw the three corners of a triangle and pick a random point inside it. You then, again at random, pick one of the corners of the triangle and move halfway towards it, making a dot at your new position. If you continue this iterative process, you build up Sierpiński’s triangle again! It can take a while by hand, but a computer can do this sort of thing very quickly.
The ultimate fractal
There are many other fractals, but the daddy of them all was created by French-American mathematician Benoit Mandelbrot (1924–2010). As a researcher for the computer company IBM, Mandelbrot was initially interested in self-similarity because he felt it was a common feature of many things, including the stock markets and the way the stars are spread out across the universe. Mandelbrot’s access to the computers at IBM enabled him to perform many iterations quickly, which allowed his studies to thrive. In 1975 he coined the term ‘fractal’.
In the early 1980s he used a computer to investigate for the first time the fractal known as the Mandelbrot set. Like so many of the fractals we have looked at, it has a remarkably simple basis:
zn+1 = zn2 + c
This iterative equation says that you get the next number in the sequence, zn+1, by taking the current number zn, squaring it and adding another number, c, to it.
You choose a number, c, and test it using the iteration (starting with z0= 0). Some values of c cause z to get larger and larger, but for others it gets closer and closer to a stable value or else keeps moving around without ever getting larger than 2.
z and c are both complex numbers, which means they have both a real part and an imaginary part (see here). So each value of c has, in effect, two values, which we can plot on a graph as a point. If you plot all the points where c doesn’t ever lead to a value larger than 2, you get an image like this:
If you shade the unstable points on the graphs to indicate how many iterations it took them to become larger than two (the brighter the shade, the more iterations), the famous image emerges.
We can see many self-similar features on the Mandelbrot set, but what is perhaps most amazing is the complexity that arises even though the governing equation is so simple. You can literally zoom into the fractal for ever, a mystery that has led to this fractal assuming the mantle the Thumbprint of God.
As we have seen, the increasing use of computers has also enabled mathematicians to find numeric solutions to equations that cannot be solved using algebra. It is now commonplace for scientists, engineers, designers and inventors to use computer methods to help them in their work. The experiments at the Large Hadron Collider in Europe produce 15 million gigabytes of data each year.
This experiment and many others that require a large amount of number-crunching are now able to exploit the redundant computing power of home computers via the Internet. This distributed computing allows the data to be dealt with far more quickly and allows members of the public to be involved in the frontiers of scientific research.
Modern Mathematics
In the last 100 years mathematics has diversified into a vast number of fields, each of which requires years of work in order to excel at it – gone are the days of the generalist mathematician with equal facility across all fields. While a significant proportion of these mathematical developments are beyond the scope of this book – and, if I’m being perfectly honest, beyond the scope of this author, too – there are some interesting areas where, initially at least, we can appreciate the mathematics and the mathematicians that contributed to them.
Pick a prize
Named in honour of the original host of the American game show Let’s Make a Deal, the Monty Hall problem is a good example of maths at its most counter-intuitive. Problems such as this one have been around for some time. Parisian mathematician Joseph Bertrand (1822–1900) posed a very similar problem called Bertrand’s Box way back in 1889.
On Let’s Make a Deal, the winner of the game show was offered the opportunity to choose one box out of three. One box contained the grand prize – the keys to a brand-new car. The other two boxes contained consolation prizes of much less worth.
The contestant picked a box but was forbidden from opening it. The host, Monty Hall, then revealed that one of the two remaining boxes was a consolation prize. He gave the contestant the option to swap their box for the remaining closed box. The question was:
Should the contestant swap boxes or not?
On the surface it seems that it should not matter. After all, the contestant is choosing between his or her own box and the other box, so it’s a 50:50 call, right?
Wrong.
There are several ways of thinking about this problem and perhaps the most obvious way is to look at all possible outcomes of these events. Let’s call the boxes A, B and C and say that A contains the prize.
If we look at the outcome column, we can see that there are three ways to win and three ways to lose. So it was 50:50 after all!
Wrong.
If you look, one of the wins happens when you stick, and two of them happen when you swap. This means that the chance of winning if you swap is 2/3, and only 1/3 if you stick.
Another, less laborious way of thinking about it is this: when you pick initially, you have a 1 in 3 chance of choosing the correct box, which means there is a 2 in 3 chance that the prize box is one of the other two boxes. When the consolation box is revealed, it does not change the fact that there is a 2 in 3 chance that the remaining box is the prize.
A DIFFERENT LANGUAGE
We saw earlier how Alan Turing and other code breakers helped the Allies during the Second World War, but the discipline of cryptography precedes their efforts. People have been using codes and ciphers to communicate privately for thousands of years.
A code is, in effect, a language, and they work on the principle that A and B can communicate privately in a language that C does not know. The disadvantages here are that C can either find someone else who speaks the language, or they can find a dictionary or codebook and work out the information themselves.
Native Tongue
During the Second World War the USA used speakers of the native American dialect Navaho for secure radio communications because no Navaho dictionaries or non-American native speakers existed at the time.
Ciphers, on the other hand, involve altering the original message using a sort of algorithm; the art of the cryptologist is to break the cipher, often using mathematical means.
A new alphabet
The Roman army used Caesar’s cipher to encrypt orders. This simple cipher worked by taking the letter in the original or plaintext and shifting each letter in it along the alphabet by a predetermined amount to create the ciphertext. For example, ATTACK would become BUUBDL if each letter is shifted along one place.
Although, admittedly, it is not a terribly cunning device, it is nevertheless effective if the orders were very short term. The problem here is that if you can work out the shift, you can translate the whole message easily.
More effective would be to rewrite the alphabet in a more random fashion, assigning each letter a new cipher letter without a constant shift. I could write A as Q, T as G, C as X and K as Z, so ATTACK would become QGGQXZ. This cipher is a bit more secure, but maybe vulnerable to attack if I set my compute
r the task of trying out different combinations of the alphabet. Let’s see:
For A, I have 26 choices of letter (it might help to confuse things if sometimes the plaintext letter and the ciphertext are the same).
For B I have 25 choices, 24 for C, 23 for D, etc. This means there are 26 × 25 × 24 × 23 × … × 3 × 2 × 1 possible alphabets for the computer to check. The shorthand for this is written 26! or 26 factorial.
26! ≈ 403291461000000000000000000
This is a large number, but computers these days are so fast they can deal with a number of this size quite easily. Let’s say my computer can check 100 alphabets per second to see if they make sense, so it would take my computer:
26!/100 ≈ 4032914610000000000000000 seconds
≈ 17048866400000000000000 years
to check all the possible alphabets a message could be in. Clearly such a brute force approach would not work, but people have been able to break such ciphers for hundreds of years. How?
Language patterns
Arab mathematician Al-Kindi (801–73) developed something we now call frequency analysis. Al-Kindi discovered that every language uses its letters in unique proportions. For example, in English we use the letter e most often – 13% of the time, followed by t (9%), a (8%) and o (7.5%) and so on. Different languages have different percentages of letter distribution.
This means that, if you know an encrypted message is in English, you can count how many times each letter appears in the ciphertext and match it up with the real letters. For example, if the letter n appears 13% of the time it is most likely representing e. There are also idiosyncrasies in languages that help – such as q, which in English is nearly always followed by the letter u.
There are many other ciphers, each of which has become increasingly elaborate and difficult to break. However, in today’s online world we have started transmitting far more of our private information, to the point where sending personal details such as bank account details, dates of birth and passwords is commonplace. So how do we protect this information?
Keys to the lock
In the nineteenth century the Dutch cryptographer Auguste Kerckhoff (1835–1903) summed up what makes an ideal cipher: even if someone knows the full workings of your cipher, it should still be impossible for them to decipher your message. This relies on having a good cipher and something called a key, which is the crucial information without which you are unable to break the cipher. In the example of Caesar’s cipher, the key is how many letters along the alphabet you should shift.
Central to the workings of modern ciphers that control e-commerce, and also for people that like to keep their emails protected, are one-way functions, so-called because it’s a calculation that is easy to do one way, but very difficult to do in reverse. British economist William Jevons (1835–82) recognized that it is fairly easy to multiply two prime numbers together; much harder is to work backwards from the result to find out which two prime numbers had been multiplied together, especially if the numbers are large.
For example, in a matter of moments you can multiply 23 and 19 using a calculator to get 437. However, to work out which prime numbers multiply to make 437 you have to go through the rather laborious process of checking whether each prime number goes into 437. In this case, I would have to perform a check for 2, 3, 5, 7, 11, 13, 17 before getting to 19. Checking seven times is not a big deal, but imagine checking prime numbers with thousands of digits. The largest primes known at the moment have over 12 million digits. This will take you a very long time, even using a computer.
In effect we now have two keys: the product of the two primes, which can be used to encrypt information, and the two prime numbers themselves, which can be used to decipher anything encrypted with the product of the prime numbers in the first place. This pair of keys is referred to as public and private keys. They allow information to be transmitted safely, even though people can get access to our encrypted data and they know what method we used to encrypt it.
Security Guard
A common analogy for this system, which is called public key cryptography, is normal ‘snail’ mail. You can make where you live common knowledge (the public key) and people can put messages through your door. But only you have the key to your house (the private key) to get in and read the message. The security in this example is your sturdy front door and excellent lock, which could be broken into but would take a prohibitively long time, just as it would take a computer a very long time to work out the original prime numbers that make up the private key.
So, when you buy something online, the website’s computer lets your computer know its public key – a whopping great big number that is the sum of two big primes multiplied together. Your computer uses that number to encrypt all your details (which, if they weren’t already numbers, have been converted to numbers) and then sends it to the website. The website’s computer can then use its private key – the two prime numbers used in the first place – to decipher the message and remove the money from your account. Clever, eh?
GOING LARGE
When it comes to big numbers we have adopted the American system. Starting from 1 million, which originally derives from Italian, we then use Latin numbers as prefixes to indicate a number a thousand times larger. For example, 1 billion is 1,000 million, ‘bi’ being a prefix meaning two; 1 trillion is 1,000 billion, and 1 quadrillion is 1,000 trillion, and so forth.
The big and the small
The practical use for these numbers is limited to fields that deal with very large things (such as astronomy and cosmology) or very small things (such as chemistry and physics). For example, Avogadro’s constant tells us how many atoms or molecules there are in a standard measure of a particular element, and that it is roughly equal to 600 sextillion. The mass of the earth is approximately equal to 6 septillion kilograms.
Mathematicians have another system with large and small numbers called standard form or scientific notation. This system exploits the fact that a number with n zeros after it is the same as the number multiplied by 10n. Hence, Avogadro’s constant is often written 6 × 1023, which is much more convenient to use in calculations, and to enter into a calculator too. Standard form can also be convenient for very small numbers, because multiplying a number by a negative power of ten is the same as putting zeros and a decimal point in front of the number. For example, an electron’s mass is approximately 9 × 10-31 kg, e.g. a 9 preceded by 31 zeros with a decimal point between the first two: 0.0000000000000000000000000000009.
Where Google Got Its Name
When American mathematician Edward Kasner (1878–1955) wanted to create new words for large numbers he asked his young nephew for help. The boy suggested the word ‘googol’, which would have a value of 1 followed by 100 zeros:
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
The pair also quickly invented the ‘Googolplex’, which is 1 followed by a googol zeros, or 10googol. Kasner’s motivation here was to demonstrate that you could have these incredibly large numbers that still were not infinite.
The founders of Google used a modified version of the word googol to imply that their search engine could sift through a very large number of websites quickly.
PARTY TIME
In 1939 Austrian engineering scientist Richard von Mises (1883–1953) posed the Birthday problem: how many people need to be in a room for there to be a 50% chance of two of them sharing a birthday? The answer to this puzzle is surprising.
Most people’s first response to the conundrum goes something along the lines of: there would need to be 366 people in the room to guarantee two of them sharing a birthday, so 183 people (half of 366) in the room would give a 50% chance.
The correct answer, however, is only 23 people. Although this seems very unlikely, it is in fact true. Why?
Well, if there are two people in the room, Alan and Blaise, there is only one way they can both share a birthday. If a third pers
on, Carl, joins them, then there are three possible matches:
AB BC
AC
If a fourth person, Delia, joins them, the possible matches are:
AB BC CD
AC BD
AD
Now there are six chances for two people in the room to share a birthday. Each time a new person joins the room another layer is added to the triangle:
AB BC CD DE
AC BD CE
AD BE
AE
With five people in the room there are ten combinations that could result in a shared birthday. This triangular pattern stops you from having to add further layers because the triangular numbers that the pattern produces are well known to mathematicians.
Even more triangles!
Triangular numbers are formed by adding together consecutive whole numbers. Hence, the first triangular number is 1, the second is 1 + 2 = 3, the third is 1 + 2 + 3 = 6 etc.
The formula for the nth triangular number is ½ × n × (n+1), but I can also find the triangular numbers using Pascal’s triangle (see here), by looking down the third diagonal:
The triangular numbers also have a role to play in the carol ‘The Twelve Days of Christmas’. In this song, each day your ‘true love’ gives to you an ever-increasing quantity of gifts:
As you can see, the number of gifts awarded each day corresponds to the triangular numbers. But what about the running total of gifts? These numbers are the next diagonal of Pascal’s triangle and are known as the tetrahedral numbers, because each time you add another day you are adding another layer to the pyramid: