nvanmaastricht

December 18, 2012

Time Lapse Video

Over the last few days, I spent a bit of time programming. My initial goal was to see if I could write a program which could capture images from my webcam. I run Ubuntu, so the install process of all the packages I needed was exciting!

I initially got the configuration for one of the packages wrong, and due to many things, when my test program wouldn’t work, I went and asked a question of a friend, in the stupidest way possible. In the end, I just reinstalled pretty much everything and it worked because I didn’t get the configuration wrong a second time, so I guess there wasn’t too much harm done, just a slightly frustrated friend.

So my weapon of choice for tackling this project was OpenCV, along with the pile of dependencies it has. There are some nice tutorials on using OpenCV, which can be found here. It gave me a way to quickly start and see where I was going, it gave a bit of background maths, and it even linked to a paper which I’ve enjoyed reading.

The first program I wrote was to simply display a stream of the webcam. It allowed me to find the error in the configuration, and verify that it was fixed after I reinstalled everything. There wasn’t much to it, the program is essentially supplied in the documentation of OpenCV.

Next I figured out how to save a frame of the stream to an image file. This went fairly smoothly with only a few lines of code to achieve. So far everything was going well but I didn’t really have any idea what I was going to do with my new found knowledge of OpenCV.

I decided to see if I could detect a person in the frame. To do this, I took a frame of the stream without a person in it. I saved that and called it my “base” picture. I was doing comparisons of the base and the frames in the stream, and then if they differed significantly I would declare a person is in the frame. The comparison I was using is what is known as a SSIM index, which is a method of testing the structural similarity of an image after compression. Obviously what I’m doing is completely different to this, but so far I’ve had promising results using this method. I will look at different methods at a later date if I continue working on this project.

I was able to get a true positive on about 95% of all the frames that had a person in them, but I was getting a lot of false positives as well, somewhere in the order of about 30%, which is unacceptably high for me. The SSIM index, is a number between 0 and 1, with 1 being a perfect match. I decided that 0.73 was a good SSIM index to be the boundary, after calculating the SSIM index of a few images against my base, some with the light in the room off, some with the light on, some with a person, some without a person, and combining these. 0.73 seemed to be the appropriate mark to set. Unfortunately my results say otherwise.

To rectify this, I wrote another program. The purpose of it was to capture an frame of the stream every 20 seconds for an undetermined amount of time. I let it capture 4320 frames, or exactly 24hrs worth of images. These were all written to disk and are now able to be analysed to find a more accurate SSIM index. I have written a program to do a comparison with my base and these images (it’s the same one I used earlier, I just have a larger sample size now), and hopefully it will give me a much better SSIM index, which will give me the same amount of true positives, but far less false positives. I am yet to analyse these images though as I’ve only just finished the capturing process.

I also wrote another program, while the capturing was taking place. It takes all the images that have been captured, and creates a video out of it. It gives every image three consecutive frames in the video, and the video runs at 24fps. It compiled the video much quicker than I anticipated it would, taking only about a minute and sixteen seconds to compose the 12960 frames together. The video has a resolution of $640\times 480$ , and I’m tempted to make another video with a higher resolution. I’m reluctant to show anyone the video though because it does show me, and I’m not entirely sure I want people to see the expressions that come across my face over the course of 24hrs. There is also a small bit of the video which is entirely black where I was asleep (the webcam being attached to my computer, it is in my room with me and hence there is not enough light to capture an image while I sleep).

It is a really odd sensation watching how you look in certain situations mere hours after you were in that situation and it is still fresh in your mind. For example, I was working on some maths last night while the capturing was taking place, there are some very odd looks that come over my face, my head is often in my hands while I think and over all, I think I look pretty silly. Then I’m texting in other frames, and I’m laughing at my phone, or thinking about what to respond with and have an odd expression, again I look quite silly. From the whole video, I have learnt that I pull a lot of strange faces throughout the day. It also proves that I have done some work through my break from uni, albeit, it makes it look like doing the work was painful.

A few ideas I’ve had that relate to this include, putting the capturing program onto a Raspberry Pi and sitting it outside to capture the sun at the same time each day over the course several months, doing more 24hr, 12960 frame videos in different locations, again, it’d be possible to use a Raspberry Pi hopefully. I’d also like to do more on detecting a person, I skimmed a blog post on using OpenCV to detect faces, and eyes, so that may be a possibility, I may also be able to capture every frame for about 300 seconds and then calculate the SSIM index over sequential frames to see if I can detect motion, instead of just people, a person being a large object, it changes the SSIM index fairly significantly, but if a tennis ball was introduced, a much smaller change in the SSIM index will be seen. I will continue to fiddle, and if I get any exciting results, I’ll probably write a blog post about them!

December 14, 2012

Linear Algebra

Linear algebra is a study of vector spaces as far as I’m aware. It has many applications throughout science, engineering and of course mathematics.

So what is a vector space? A vector space is defined over a field is a set $V$ with two binary operations. The first operation, commonly called vector addition, which takes $v,w\in V$ and produces a new vector $v+w\in V$ . The second operation is takes a scalar from a field, $\mathbb{F}$ , lets call it $a$ , and takes $v\in V$ , and produces a new vector $av$ .

A vector space satisfies the following axioms:

Commutativity – $u+v=v+u$ , $\forall u,v\in V$ .
Associativity – $(u+v)+w=u+(v+w)$ , $\forall u,v,w \in V$ .
Identities – $\exists$ $0\in V$ such that $0+v=v$ , $\forall v\in V$ . $\exists$ $1\in V$ such that $1v=v$ , $\forall v\in V$ .
Additive inverse – $\forall v\in V$ , $\exists w\in V$ such that $v+w=0$ .
Distibutive – $a(u+v)=au+av$ and $(a+b)u=au+bu$ , $\forall a,b\in\mathbb{F}$ and $\forall u,v\in V$ .

Now from these axioms, we can say a couple of things about vector spaces almost immediately.

Lemma 1: A vector space has a unique additive identity.

Proof: Suppose that $0$ and $0'$ are both additive identities for some vector space $V$ . Then $0'=0'+0$ as $0$ is an additive identity. But, $0'+0=0$ as well, because $0'$ is also an additive identity. And as $0'=0'+0=0$ then $0'=0$ so there is only a single additive identity in $V$ .

Lemma 2: $0v=0$ , $\forall v\in V$ .

Proof: For $v\in V$ we have $0v=(0+0)v=0v+0v$ . Now if we add the additive inverse of $0v$ to both sides of the equality, we get $0v+(-0v)=0v + 0v + (-0v)$ and this simplifies to $0=0v$

You can also consider a subspace of a vector space. To check if a subset of $V$ , lets call it $U$ , is a subspace of $V$ , we only need to check that $U$ satisfies the following properties:

$0\in U$ .
$\forall u,v\in U$ , then $u+v\in U$ as well.
$a\in \mathbb{F}$ and $u\in U$ , then $au\in U$ .

For an example of a vector space, and a subspace, consider the space $\mathbb{R}^3$ , it can be checked that the standard vector operations make $\mathbb{R}^3$ a vector space. Now if we consider the set $\{(x_1,x_2,0) : x_1,x_2\in\mathbb{F}\}$ , then you can check that that satisfies the three properties required for a subspace. Notice though, that a subspace is a vector space in its own right.

Now this just touches the very tip of linear algebra, these are the very basics. It gets much more interesting, both in terms of the pure side of maths, and the applied side. The wikipedia page on linear algebra is quite a good read, it has a couple of applications. It also expands on what I’ve already stated here. A couple of things I’ve used linear algebra for include:

Solving linear programs
Finding interpolating polynomials
Cryptography
Very basic network analysis

And many, many more things. It’s a very useful topic.

December 14, 2012

Myself

Recently I watched the following Ted talk by Susan Cain. In the talk, should you not want to watch it, she describes a lot of traits that describe me well, so I thought I would share a little bit about myself, which includes my behaviour and how I perceive my mind working.

Firstly, it should be noted that if someone is an introvert, that does not necessarily mean they are shy. It just means that they do not need as much external stimulation to be happy as an extrovert. I consider myself highly introverted, I live very much in my own mind a lot of the time, thinking about maths, philosophy, or science for a lot of that time. Although introverts aren’t necessarily shy, I definitely am shy.

In her talk, Susan mentions she went to crowded bars. I do spend quite a lot of my time at one of the bars on campus. I play pool in there when I get the chance and I interact with a couple of great people. Apart from that trip into the social side of life though, I much prefer to sit in my room working on maths, writing programs which range from apps for smart phones, to prime number generators and a lot of stuff in between. Even while writing this, I was completely distract by a maths problem and got set back about an hour from trying to solve it.

When I’m in social situations, I am generally very uncomfortable. It’s not because I don’t like the people I’m with, I just don’t like groups of people. I have trouble making eye contact with people, when talking to them, and occasionally it is interpreted as a sign of rudeness. I in no way mean for it to be rude, I’m just not comfortable around people. Earlier in the year, I did a talk on the history of Fermat’s Last Theorem. I presented it to a room full of people and on the whole, I received fairly positive feedback. No one mentioned that I didn’t make eye contact much though, I definitely noticed that I wasn’t making eye contact. It’s slightly upsetting that I couldn’t make eye contact, I was confident I knew all the material I was talking about, I was confident that I had prepared for the talk well enough that I knew the slides well enough not to need to read from them, but the majority of the time, I was either looking out the windows at the back of the room, or looking towards the floor between two desks in the front of the room. This disappointed me much more than I first thought it would.

Because I don’t enjoy meeting new people, I always buy food from the same people at uni, I pay my phone bill through the same person, I even get my mother to buy me items such as DVDs. I try to shop online whenever I can as well. Interacting with people I don’t know is a horrible experience for me, which also contributes to me not making many friends.

As someone can probably imagine, I don’t like working in groups if I can help it. I definitely do my best work when I’m working by myself. I find that if I’m not being distracted by the people I’m working with, I can follow a train of thought through to the end, which is a much harder thing to do when working in a room with other people. This is also the reason I stay up to the early hours of the morning. The night time is a very quite time and I can structure my thoughts correctly, a lot of my favourite work has been done after 12am.

In saying that, I have recently done some collaborative work which I’ve really enjoyed. I’ve been collaborating with a friend from America and we’ve done some maths which I think is really cool. Although we haven’t managed to find a connection between our work and mainstream maths (which I’m aware of). This collaboration is slowly changing my outlook on collaborative work, and I could see myself doing more collaborative work of a similar style.

I have been asked at least a few times what goes through my head when I see a string of numbers as well, so I will address that and then leave you back to what is almost surely your more extroverted life.

Lets imagine I’m seeing the string of numbers $11235813213455$ . Firstly I notice that $112358$ is the the beginning of the Fibonacci sequence, I find it much easier to notice this initially than the following $13$ as they are all single digit numbers, $13$ not being a single digit is harder to see at first. After noticing $112358$ I then check to see if the Fibonacci sequence continues, and I find that it does and I stop worrying about these numbers.

What if the string is not so simple though and I was asked to memorise it, such as a phone number. An Australian mobile phone number consists of ten digits, often displayed as xxxx-xxx-xxx, which I assume is to aid in the memorisation of the number. I do not remember phone numbers like this in general (the notable exception here is my own number which does not exhibit any nice patterns). The other day I was presented with a phone number for the first time. I immediately noticed that it had what I term the “standard” first four numbers, so that was no problem to memorise, almost every number seems to start with them. Of the remaining six numbers, I quickly noticed that if I took substrings of length two, then two of the numbers produced are prime, which I find fascinating and hence I seem to remember easier, so that leaves only two more numbers, which I needed to know, which I just grouped together even though they showed no particularly stand out property. So summing up, I needed to remember that a standard four numbers starts the number, then the order of not six numbers, but three numbers, all of which were two digits each, and only one of those I didn’t find intrinsically interesting. So the way I see it, I only have to remember one number and the order of a couple of interesting numbers.

One of the first things I do when I see a number is to see if it’s prime, assuming the number is small enough, I can determine easily enough if it is prime due to either having the first few primes memorised, or generating a few primes so I can perform a quick trial division in my head. If the number is larger, I perform what is more closely linked to a probabilistic primality test, although a lot of composite numbers slip through the cracks so it’s not a very good test. I like knowing properties of numbers when I see them. I also like pointing out interesting numbers to people, for example, the other day the number of text messages that a friend and I had exchanged was $314$ . When I pointed out that this was $\left [100\pi\right ]$ where $[\cdot ]$ denotes the integer part of a number, she seemed unimpressed, but I find it very interesting.

Another interesting thing that I get to experience on my way to uni each day on the bus, is to pass a taxi zone. People who know the story of the uninteresting number of Hardy’s knows what is coming next. A taxi in Australia has a number plate “T xxxx” where xxxx is the taxi number, so far I’m yet to see “T 1729 ” unfortunately. I am always on the look out for it though no matter where I go.

I often find myself bored with a clock handy, and have been inspired by

which is from the great webcomic, xkcd (click the image to be taken to the original page), I factor the time quite regularly. This aids in memorising small primes, which I mentioned I enjoy above.

Although this is only a small amount of how I see the world, and what goes on in my mind, I hope it is enough to appreciate and it gives you a small idea about what is happening within my head.

2 Comments

October 4, 2012

What is the point of time zones in the modern day world?

Back fifty years ago when there wasn’t a particularly large number of international communication between a lot of people, it made sense to have time zones. There are common words such as “midday” and “midnight” which make perfect sense if we have time zones, and they are a useful reference for the majority of communication. I argue that in the modern world, where electronic communication is so popular among the developed world, there is no need for time zones.

A question which naturally arises from destroying time zones is, “what will we use to tell time instead?” Why not just use POSIX time? It would mean that people who often communicate with people from different time zones would not need to clarify whether they are talking about their time zone or their companions time zone, and that would, as a result reduce ambiguity in everyday conversation.

If we did use POSIX time, that would mean it would be dark for some people at 21:00 and light for other people at 21:00, which could be a bit unsettling at first. After a couple of months though, most people would get used to this. Day light savings changes the time by an hour, and hence the hours which are perceived to be light and dark change, and everyone adjusts to this fine. I find it difficult to believe that people would find it difficult to adjust to calling a time where the sun is not above them 09:00, espcially considering the ease of use when communicating with people from what is currently a different time zone.

I can only predict that more international communication is going to happen with the rise in use of the internet. Email makes it easy to carry out a conversation with someone from the other side of the world, but as social media becomes more and more popular, there is more and more communication happening. Personally I communicate with people from time zones which are 10hrs, 14hrs and 15hrs different from my current time zone using social media such as Facebook and Twitter. If we include sites such as Reddit, then I’ve more than likely communicated with at least one person from every time zone.

There is a lot of ambiguity in our conversations though, we’ve always got to clarify what time zone we’re referring to if we’re planning a Skype conversation. If we had an international standard time, such as POSIX, then we wouldn’t have this ambiguity, I could say that I’m free at 17:00 and that would not need to be transformed to a different time for my conversation partner, and they wouldn’t have to ask if that is 17:00 my time or their time, etc.

The only issue with swapping to a system which only uses POSIX would be things such as automatic back ups which operate at 00:00 each day, this would not work when time zones are removed. It would not be hard to stagger when things like this run though, anything that uses cron would quite easily be able to manage it, as for any other devices, I’m not sure what schedulers there are, but I’m almost certain that they exist.

Summing up, I don’t see why we still use time zones when there is a system that is almost already implemented and seems to be simpler on the surface for most forms of communication.

4 Comments

July 3, 2012

Prime Numbers and Encryption

Prime numbers are often regarded as the basic building blocks of numbers. They were known to the ancient Greeks, most notably appearing in the famous collection of books, Euclid’s Elements. The Elements have some fundamental theorems about the primes, such as the infinitude of the primes and the fundamental theorem of arithmetic. We’ll get to both of these later though.

First, what is a prime? A number, $p\in\mathbb{N}$ is said to be prime if, when expressed as a product of other numbers that are from the set of natural numbers, then the only way it can be express is $p=1\times p$ (down to a permutation of the product). So take for example $17=1\times 17$ , which is prime because there is no other way to express 17 as the product of other numbers from the set of natural numbers. Now consider $12=3\times 4 = 1\times 12$ , as there is at least two ways to express 12 as the product of natural numbers, it is not prime.

Now that we know what a prime is, lets move on to the fundamental theorem of arithmetic. The fundametal theorem of arithmetic states:

Every natural number, except 1, can be represented uniquely as the product of prime numbers, or is itself a prime number.

By “represented uniquely” this means that the order of the product does not matter. The proof of this theorem, though not complicated, will be omitted (a proof can be found here).

Now that we have the fundamental theorem of arithmetic at our disposal, we can talk about the infinitude of prime numbers, that is, there are an infinite number of prime numbers. Now the original proof by Euclid talks about measuring A, B, C, all of which are prime, I’ll do a quick summary. Give me a list of all the primes, lets call them $p_1, p_2, p_3, \ldots, p_n$ , now multiply all these together and add 1 to give $p_1p_2p_3\cdots p_n+1$ now this new number is not divisible by any of the original primes in our list, and by the fundamental theorem of arithmetic we know that this new number can be written as the product of primes or it is a prime itself. If it is a prime then we are done, if it’s not a prime then there are other primes which uniquely define this number, hence our list was not complete to begin with. If we add these new primes to our list and start again we can generate more primes, and then repeat again and again, therefore there are an infinite number of primes.

The above proof is called a proof of existence, it merely says that the prime numbers exist, not what they are. So the natural question to ask is, how can we find prime numbers? The easiest way, but not particularly efficient, is called the Sieve of Eratosthenes and dates back to Eratosthenes of Cyrene of the ancient Greeks. The sieve is very simple to use if you want to find all the prime numbers below a given $n$ :

Make a list of all the integers from 2 up to $n$ .
Start with $p=2$ which is the first prime number (and the only even prime number).
Cross of every multiple of $p$ that is greater than $p$ in the list you generated in step 1.
If it exists, find the first number greater then $p$ that has not been crossed of, that is your new $p$ . Repeat from step 3.

As you can probably see, this sieve is not particularly fast, but it works. There are much faster sieves which can be used, but they are also much more complicated.

A different question that can be asked about primes is, how do we know when a number is prime? This question is not an easy question to answer. If the number is even (except for 2), it is easy to tell that a number is not prime. If it is odd it is more difficult. We could use what is known as trial division to see if a number has any factors, which would imply that it is not prime as it will be representable in at least two different ways as the product of natural numbers, this way is not particularly good though. A very quick improvement is to notice that if a number is odd, it won’t have an even number as a factor, so we can skip over every even number in our trial division.

A further improvement we can make to this scheme is to use a small amount of number theory and realise that if a number, $n$ has factors, $p_1, p_2$ , then we can bound at least one of them, with an upper bound of $p_1\leq \sqrt{n}$ , and if $p_1=\sqrt{n}$ then $p_1=p_2$ . This is already much quicker then what we initially started with, albeit still very slow.

The problem that we are trying to solve here is called prime factorisation. Since the time of Euclid people have been trying to determine whether a number is prime or not, that was about 2300 years ago! The truth is, we’re still not much further along in our quest to tell if a number is prime or not, we just have computers to do the calculations for us now. We do have an algorithm called AKS though which is theoretically the fastest way of checking to see if a number is prime, and if the algorithm says it is, then it definitely is, if it says it isn’t, then it definitely isn’t. This is called a deterministic algorithm. We have probabilistic algorithms which are reasonably quick, but even if one of these algorithms say a number is prime, it might not be, and similarly if it says it’s not prime, it still might be.

Now after reading all of this, I assume you hope it’s leading somewhere, and it is, to RSA, an encryption scheme which is used world wide. Now encryption has been pretty dodgy over the last 2000 or so years, we’ve got the simple Caesar shift cipher, where you replace each letter in the alphabet by the letter that is $k$ letters further along in the alphabet. This is easily broken though. An improvement is the Vigenère cipher which uses combinations of the Caesar shift, and is harder to break, but still quite easy to break. My personal favourite is called Enigma, it was used by the Germans in world war two and there has been a lot of press about it of late due to Alan Turing’s 100th birthday celebrations and he’s contribution to cracking the Engima cipher. It was a fairly advanced cipher, with an easy encryption and decryption method, a typewriter like machine which had a second alphabet on it which, when a key was pressed on the normal part of the typewriter, a light while illuminate on the second alphabet. The amazing thing was, to decrypt it, you only needed to type in what the illuminated character was onto an Enigma machine that was set up with the same configuration as when the encryption took place! This code had (assuming no wiring configurations were known) about $10^{114}$ possible configurations! Or about 380 bits! But as was already mentioned, it was cracked, and the last time I heard, it can be cracked in about 40 seconds on a modern laptop.

Now as the best of all the previous codes had been cracked, the world needed a secure encryption scheme, enter Ron Rivest, Adi Shamir and Leonard Adleman, the initials of these men make the name RSA. They developed an algorithm that could let you tell everyone how to encrypt a message that is to be delivered to you, but no one else could read it after it’s been encrypted but the intended recipient! This is now known as a public key scheme and this one in particular relies very heavily on the fact that we still can’t factor a number into it’s prime components!

RSA works with what is called a public key and a private key. They are named so it is hopefully obvious what they are for, one is given out to everyone and one is kept a secret, hopefully you can tell which is which.

One more thing before I tell you how the RSA scheme works. We have an idea called the greatest common divisor of two numbers $a,b$ , denoted $\gcd(a,b)$ . This is a natural number. To calculate it, we list all of the factors of $a$ and all of the factors of $b$ then take the largest number that appears in both lists. For example, $\gcd(4,6)=2$ and $\gcd(5,7)=1$ . If, for two numbers, $a,b$ it turns out $\gcd(a,b)=1$ then we call $a$ and $b$ relatively prime or coprime. Now we can define another function $\phi(n)$ such that it counts how many numbers are relatively prime to $n$ . For example $\phi(10)=4$ and $\phi(7)=6$ . This $\phi(n)$ function will be important in the RSA algorithm, so make sure you understand it before going on. Note that in general it is very hard to calculate what $\phi(n)$ is, but the RSA scheme exploits some facts about $\phi(n)$ which makes it easier to use the algorithm.

Now first lets start with the following algorithm:

Choose two distinct prime numbers $p$ and $q$ .
Compute $n=pq$ .
Compute $\phi(n)=(p-1)(q-1)$ .
Now choose a number $e$ such that $1< e < \phi(n)$ and $\gcd(e,\phi(n))=1$ . $e$ is part of the public key.
Compute $d=e^{-1}(\mod \phi(n))$ (this is potentially confusing, this says to pick $d$ in a way such that $d$ is the multiplicative inverse of $e$ mod $\phi(n)$ ). $d$ is part of the private key.

The public key is $(n, e)$ and the private key is $(n, d)$ .

Now that we have our public and private keys we can encrypt a message and then decrypt a message.

Encryption:

Assume that a secret message $M$ from Bob wants to be transmitted to Alice. First Bob uses a transform that is known as the padding scheme to change $M$ to $m$ such that $0 < m < n$ . He then calculates $c=m^e (\mod n)$ and transfers $c$ to Alice.

Decryption:

Now Alice needs to reverse what Bob did so she can read $M$ which is what Bob originally wanted Alice to read. Alice can calculate $m=c^d (\mod n)$ and hence recover the original message that Bob wanted to send her.

Breaking RSA:

The difficulty in someone trying to get the original message with knowing what $d$ is lies calculating $\phi(n)$ , which as already been stated, is very hard to calculate. It is easy to calculate if you know the two prime numbers which were used to create $n$ , it’s just $\phi(n)=(p-1)(q-1)$ , but not knowing these primes makes it essentially impossible to calculate in any reasonable time, so if you’re using very large prime numbers, you can be very sure that if you use RSA every message you send will be save from an eavesdropper, say Eve because Eve can not factor $n$ fast enough. This style of encryption scheme, where it’s easily possible to break given some additional details, in this case the factors of $n$ , is considered theoretically insecure, but due to the computation time required to find the secret factors of $n$ , it is computationally secure provided the original prime numbers used are large enough. What is large enough though? A larger number is obviously more secure, but that puts overhead in the computation time in carrying out the RSA algorithm, there are many different standards, with the prime numbers being 512, 1024, 2048, or 4196 bits long depending on how secure you need your information. There are additional restrictions put in place in real world applications due to some number theory which makes finding prime factors easier in certain situations, but these restrictions require more time to explain so I’ll leave it here.

There is a nice xckd comic which sides with Eve located here. If you got through all of that, well done!

NVM

Edit: The large chunk of text in italics was appended to the original post

1 Comment

June 28, 2012

Abstract Algebra

Of the fairly wide variety of topics I’ve covered at university so far, the one I knew the least about before going into the course turned out to be one of the best, namely abstract algebra. Having done a course on combinatorics and graph theory before doing abstract algebra I had an idea what a group was, what a ring was, what an ideal was and all that other fun stuff. I just wasn’t particularly competent at using them when required.

From this course and other experiences, I feel like mathematics is the study of objects, where the objects are a set of axioms, to make my point I’ll go over some stuff from my abstract algebra class. Take the axioms of a group:

Let $G$ be a set and $\circ$ be a composition, then $(G, \circ)$ is a group if it satisfies the following:

Closure: for any two elements $x,y\in G$ , $x\circ y\in G$
Associative: for any three elements $x,y,z\in G$ , $x \circ (y \circ z )=(x \circ y) \circ z$
Identity: there is an element $e\in G$ such that $\forall$ $x\in G$ , $x\circ e = e = e\circ x$ (Note from here on in $e$ will always be the identity unless otherwise stated)
Inverse: for every $x\in G$ $\exists x^{-1} \in G$ such that $x\circ x^{-1}=e$

This is the structure of a group, from here we can show things like the identity element being unique, things about the quaternions, things about matrices, we can even say the smallest number of eggs (or any multiple of that number) an old lady shopping has if she knows the remainder after division of some numbers (this was an amusing problem in the textbook we used for the course and demonstrates the Chinese remainder theorem).

Some concrete examples of groups are things like binary under addition. Our set $G={0,1}$ and our operation is addition. To see that it’s a group notice that we have $e=0$ , it’s easy to see that it is closed, the only four possibilities for composition are:

$0+0=0$
$0+1=1$
$1+0=1$
$1+1=0$

Now it may seem odd that I’ve counted $1+0$ and $0+1$ as different cases. This group is an example of an abelian group, which has the added requirement that $\forall$ $x,y\in G$ then $x\circ y=y\circ x$ .

The idea of a group not being abelian seems odd at first, but consider a group $H$ that consists of every square matrix of order $n$ with real entries and the matrix does not have a 0 determinant. The composition is matrix multiplication. If we take two matrices $A,B$ , it is not necessarily true that $AB=BA$ (which is equivalent to $A\circ B=B \circ A$ , when it is clear from context what the composition is, I tend to leave out the $\circ$ ). Now that we know that it’s not abelian if it is a group, we need to check to see if it is a group. We’ve got an identity, the identity matrix fits all our criteria to be in the group so it is there. As the determinant of a matrix in our group is non zero, then it has an inverse. If you multiply two square matrices of order $n$ together you get another square matrix of order $n$ , so it’s closed. Associativity is true, but I’m not sure how to enter a matrix into wordpress so feel free to look up how to prove that matrix multiplication is associative. This proves that $(H,\circ)$ is a group, an in fact a non-abelian group. This group does have a special name, it’s called the general linear group of order $n$ , it is denoted as $GL_n(\mathbb{R})$ or $GL(n, \mathbb{R})$ . A remark on this, even though it is called the general linear group, it can be generalised further.

From groups you can add more structure, like a second composition and axioms to go along with that composition. This gives you a ring. Rings are what we use every day, the real numbers are rings, the composition being addition and multiplication (subtraction being additive inverse, division being multiplicative inverse). From a ring we can define things such as fields and domains. Rings are amazing, for a limited number of examples, there are rings where the number $2$ is not a prime element and they can be used to reduce some number theory proofs to almost obvious statements!

In the words of the great Andrew Wiles (who I’ll write a post about one day, probably soon), I think I’ll stop here.

June 27, 2012

0

This is a small test blog. The title 0 has a few different meanings, the first, as a keen computer programmer all of my preferred languages has 0 as the first entry of an array. If 0 is not the first entry of an array in a language it annoys me quite a lot (I’m looking at MATLAB here). Secondly it’s a very nice constant, it’s the additive identity over $\mathbb{C}$ and any sub group of $\mathbb{C}$ , it also appears in the beautiful identity $e^{\pi i}+1=0$ . 0 is also a relatively new thing compared with the natural numbers, 0 only started appearing often around the time of Fibonacci (assuming I’m recalling what I believe to be facts correctly), and blogging about mathematics is a relatively new thing to me.

A small bit of information about me: I’m currently a third year mathematics student, I’ve studied some real and complex analysis, abstract algebra, differential equations, numerical analysis, combinatorics, graph theory, and I’ve done a bit of work on computational mathematics, which includes a subset of the other topics I’ve studied as well as some stuff I don’t believe will be solved any other way. Outside of formal study, I’ve read some introductory books on the Riemann hypothesis, I’ve read a few books on the Millennium problems, I’ve read a book on Hilbert’s program, and I’ve even got a copy of Euclid’s Elements, which I’ve read some of in my spare time.

Outside of mathematics, I’ve taken a few courses on software engineering, which has allowed me to explore some computational mathematics more thoroughly. I’ve written polynomial classes in c++, I’ve calculated billions of primes, and I intend to write a server/client combination one day soon which will hopefully be used to determine the truth value of the following: “Is the 33rd Fermat number prime?” For those who aren’t aware, a Fermat number is of the form $F_n=2^{2^n}+1$ . It is known that the only prime Fermat numbers below $n=33$ is $F_0, F_1, F_2, F_3, F_4$ .

That last paragraph wasn’t too far from mathematics, I’m going to try again. I’m also an enthusiastic gamer, although not particularly good at gaming. The game I’ve played most lately is Mojang’s Minecraft. It is amazing and anyone who doesn’t have it already needs to obtain it! I’ve been playing it for almost a year and I’m still learning new things about it and I haven’t been bored with it once yet.

I’m hoping I have the time and energy to continue writing this blog. My plans for it are to go over some of the maths that I find exciting, report on the progress of my $F_{33}$ primality testing, and I’m working on another project which I’m hoping will work out successful, but I don’t want to share my ideas yet in case it ends in complete failure and I look like an idiot! Needless to say, if it does work, I will feel very good about myself.

NVM

3 Comments