Just a quick progress report. I am still just about keeping up with the work but I can see that next week I will probably get behind because of the Christmas holidays. Never mind.
Book 5 of mathematical logic (formal proof) was fine, just a bit boring, but there was nothing in it that caused too much hair pulling. Previously in book 4 we set about constructing a language of proof that had a specific structure that could be checked mechanically. That book was about taking a restricted set of basic symbols (the alphabet, if you like) and deciding what were terms and formulas (the equivalent of words and sentences). A term is an expression in mathematics, something like (x+y) and formulas are based around atomic formulas such as x=y that are then linked with the connectives such as or, and, implies etc. This is all very well, but a long string of symbols has to mean something (much as a sentence in English has to make sense). Meaning is obtained from interpreting the symbols (i.e. + means add!) and determining truth or falsity of formulas depending on their interpretations and the domains on which they operate. Some formulas are always true because of the logical construction of their connectives (what they call tautology) , others will depend on the given interpretation. An important idea is logical consequence - that a formula is true because it is true in every interpretation that certain other formulas are true.
Book 5 moves on to how we can construct proofs from formulas. Now we have something that looks more like sentences making up paragraphs and paragraphs making up chapters etc. With the aim of making everything systematic, formulas are arranged like lines of a basic computer program. In order to 'derive' one line from another we need certain rules of proof and these rules are introduced by analogy with everyday mathematics. For example, we need to start by making certain assumptions so there is a rule for introducing a formula that is an assumption. The difficulty for the new initiate is that it all looks like gobbledygook at the moment. You can follow the rules and do the exercises but it doesn't really make much sense yet. That will happen in the next two books when we try to get all this working for proofs in number theory.
In the mean time I have begun the geometry book GE3 on two-dimensional lattices. It's a bit of light relief to think about parallelograms and vectors.
I am looking forward to the next number theory/logic tutorial at the beginning of January but I must try and get that TMA written up so that I can hand it in then!
Thursday 19 December 2013
Monday 9 December 2013
Over halfway
I have just passed the halfway point of these two courses now. Perhaps it will feel more like downhill from now on. I hope so!
Having finished GR3 from M336 I switched back to Number Theory and went through book NT5 on multiplicative functions. The main multiplicative functions discussed were τ, σ and Euler's φ function. τ(n) is the number of distinct divisors of n, σ(n) is the sum of these distinct divisors of n and φ(n) is the number of positive integers not exceeding n which are coprime to n. Whenever I foray into number theory I always feel more at home. I love the eclectic mixture of puzzles and theories.
I then went back to completing GE2 from M336 on periodic and transitive tilings. This finally gave me the chance to thrash through some of the cards and overlays in the geometry envelope! A periodic tiling is just a tiling that has a translation subgroup that is generated by two independent non-zero translations (a so called wallpaper group). A transitive tiling is one where the symmetry group of the tiling acting on the tiling itself generates a single orbit. In essence, any tile can be mapped to any other tile by an element of the symmetry group of the whole tiling.
I quite liked this book. We delved into translational tilings and orbits of tiles, edges and vertices. We drew orbit diagrams and eventually pondered over the Grunbaum-Shephard classification of transitive tilings.
Now I have returned to unit 5 of Mathematical logic - Formal Proof - and I am beginning to feel that things are getting heavy again! In the mean time as Christmas is rushing up towards us I have been trying to get the next two TMAs completed. This I have nearly done. I have had my results for the first two and I scored a double 100, which surprised me a bit. My nerdy record at the OU is beginning to be a bit worrying because in the 21 assignments I have completed since 2009, I have only dropped 1 mark!
Having finished GR3 from M336 I switched back to Number Theory and went through book NT5 on multiplicative functions. The main multiplicative functions discussed were τ, σ and Euler's φ function. τ(n) is the number of distinct divisors of n, σ(n) is the sum of these distinct divisors of n and φ(n) is the number of positive integers not exceeding n which are coprime to n. Whenever I foray into number theory I always feel more at home. I love the eclectic mixture of puzzles and theories.
I then went back to completing GE2 from M336 on periodic and transitive tilings. This finally gave me the chance to thrash through some of the cards and overlays in the geometry envelope! A periodic tiling is just a tiling that has a translation subgroup that is generated by two independent non-zero translations (a so called wallpaper group). A transitive tiling is one where the symmetry group of the tiling acting on the tiling itself generates a single orbit. In essence, any tile can be mapped to any other tile by an element of the symmetry group of the whole tiling.
I quite liked this book. We delved into translational tilings and orbits of tiles, edges and vertices. We drew orbit diagrams and eventually pondered over the Grunbaum-Shephard classification of transitive tilings.
Now I have returned to unit 5 of Mathematical logic - Formal Proof - and I am beginning to feel that things are getting heavy again! In the mean time as Christmas is rushing up towards us I have been trying to get the next two TMAs completed. This I have nearly done. I have had my results for the first two and I scored a double 100, which surprised me a bit. My nerdy record at the OU is beginning to be a bit worrying because in the 21 assignments I have completed since 2009, I have only dropped 1 mark!
Thursday 14 November 2013
It's an endless battle
Oh for heavens sake! It's absolutely relentless. I have just 'finished' GR3 from M336 but towards the end I lost the plot in trying to follow the proof of the theorem for the canonical decomposition of finitely generated Abelian groups and gave up. Up until page 31 things had been going well and I was coping with the exercises and the proofs, but then the exercises on page 32 went up a level and I started to feel like I was drowning in complexity. I particularly hate the exercises that involve producing bits of proof that eventually are used in some much bigger proof. Often with the terminology, the difficulty of the arguments and the not really knowing where a proof is leading, I don't know my a&se from my elbow and I don't even understand what the hell they want us to do, let alone have an idea how to achieve it. It isn't very rewarding but you just have to say bu&&er it and carry on.
It is difficult producing proofs at the best of times. My irritation stems from the fact that whoever produced the proof in the first place had probably spent a great deal of time thinking about the problem and had a definite idea of what they wanted to prove. They were probably also fully conversant with all the terminology and had all the techniques at their fingertips. For us poor students it is rush, rush, rush. No sooner have you grasped one bit of terminology, another is thrown at you and before you can master anything very much you are on to the next topic. So do they really expect us to be able to be clever and come up with these sort of proofs in this type of environment? I think it is all a bit of a waste of time, to be honest.
The hilarious thing is that often having just finished a book, I am so subsumed by all the logic that I can't even recall what the book was about when I finished it!
So, progress. I finished ML4 on formal systems. That was ok and didn't cause any tantrums. I had to skip GE2 because at the time I needed the geometry envelope from the OU and it was due in the second mailing of books. So I went on to GR3.
What is GR3 all about? Well, it is trying to find out what the structure of an Abelian group looks like if it is presented as a finite set of generators with a finite set of relations. Towards the end of the book it goes on to give the structure of an Abelian group with a finite number of generators but with an unlimited number of relations (the bit that made me pull my hair out). Ok, so how do you do this?
Basically, we discovered in IB4 that the relations are essentially the elements of the kernel K of a homomorphism from the free group F with the same number of generators to the group G we want. The 'free' bit means that F is free from such non-trivial relations. It turns out that the quotient group F/K is isomorphic to G. In this book we consider only Abelian generated groups A. The clever bit is that we impose structure on the free group by demanding that it is also Abelian. It follows that the structure of the free Abelian group with n generators is just ZxZx...xZ, i.e. the direct product of n copies of Z. In the simple case where the relations that generate A are of the form da=0 where d is a multiple of the generator a, then A is isomorphic to a product of Zd's i.e. Z modulo d. For the case where the m relations are linear combinations of the n generators, then we can from an mxn matrix of the coefficients of the generators in each relation, which can be reduced to a diagonal matrix. Then A is isomorphic to a product of the Zd's again. There is a way of uniquely writing such a generated Abelian group - this is its canonical decomposition. The d's that are greater than 1 in this decomposition are called torsion coefficients.
It is difficult producing proofs at the best of times. My irritation stems from the fact that whoever produced the proof in the first place had probably spent a great deal of time thinking about the problem and had a definite idea of what they wanted to prove. They were probably also fully conversant with all the terminology and had all the techniques at their fingertips. For us poor students it is rush, rush, rush. No sooner have you grasped one bit of terminology, another is thrown at you and before you can master anything very much you are on to the next topic. So do they really expect us to be able to be clever and come up with these sort of proofs in this type of environment? I think it is all a bit of a waste of time, to be honest.
The hilarious thing is that often having just finished a book, I am so subsumed by all the logic that I can't even recall what the book was about when I finished it!
So, progress. I finished ML4 on formal systems. That was ok and didn't cause any tantrums. I had to skip GE2 because at the time I needed the geometry envelope from the OU and it was due in the second mailing of books. So I went on to GR3.
What is GR3 all about? Well, it is trying to find out what the structure of an Abelian group looks like if it is presented as a finite set of generators with a finite set of relations. Towards the end of the book it goes on to give the structure of an Abelian group with a finite number of generators but with an unlimited number of relations (the bit that made me pull my hair out). Ok, so how do you do this?
Basically, we discovered in IB4 that the relations are essentially the elements of the kernel K of a homomorphism from the free group F with the same number of generators to the group G we want. The 'free' bit means that F is free from such non-trivial relations. It turns out that the quotient group F/K is isomorphic to G. In this book we consider only Abelian generated groups A. The clever bit is that we impose structure on the free group by demanding that it is also Abelian. It follows that the structure of the free Abelian group with n generators is just ZxZx...xZ, i.e. the direct product of n copies of Z. In the simple case where the relations that generate A are of the form da=0 where d is a multiple of the generator a, then A is isomorphic to a product of Zd's i.e. Z modulo d. For the case where the m relations are linear combinations of the n generators, then we can from an mxn matrix of the coefficients of the generators in each relation, which can be reduced to a diagonal matrix. Then A is isomorphic to a product of the Zd's again. There is a way of uniquely writing such a generated Abelian group - this is its canonical decomposition. The d's that are greater than 1 in this decomposition are called torsion coefficients.
Wednesday 30 October 2013
Are all URM computable functions recursive? (Part 3)
Let's just summarise here. We know that primitive recursive functions are URM-computable in which case the set of primitive recursive functions is countably infinite. Previously we saw that the set of all functions is not countably infinite and so not all functions are primitive recursive. In the opening to unit ML3 of the mathematical logic course it is shown, using the diagonal argument again, that not all URM-computable functions are primitive recursive.
The key to progress in understanding the relationship between recursive functions and URM programs is to realise that not all programs halt for a given input (that is reach the stage where there are no more instructions to process and an output is obtained). Some can loop round indefinitely and never reach an instruction that points outside of the program. To incorporate this into our idea of recursive functions, partial functions are introduced. A URM program computes a partial function f if for a given input, the program either halts and produces the output of f or it does not halt and f is undefined.
This either finding an output or not is equivalent to unbounded searches and the new process that is introduced is called minimisation (previously we had bounded minimisation). A new definition of recursive function is introduced (as opposed to primitive recursive) which says that a function is recursive if it can be obtained from basic primitive recursive functions using the operations of substitution, primitive recursion and minimisation on a function a finite number of times.
This allows us to finally answer the question that we originally asked. Are all URM-computable functions recursive? The answer is yes! This is part of the course that I think I really understood. The reason is relatively simple (although the proof was quite long and only sketched out); if you are at a particular stage of processing a URM program you can always determine what instruction you should process next based on the current values in the registers and what the current instruction says you should do. Unless you are at a jump instruction the next instruction to process is the one following the one you are at. Jump instructions depend on the contents of the registers. The key is that you can again provide a code number for all these situations of the program (imagine the trace table and a code that went with each entry in the table). This is clearly a recursive process except that, as we have said, an output may or may not be defined.
The chapter goes on to discuss Kleene's Normal Form Theorem, a consequence of which is that each recursive function can be obtained from the basic primitive recursive functions using the operations of substitution, primitive recursion and at most one minimisation on a function. The discussion was then broadened to Church's Thesis which says that the notion of an algorithmically computable function coincides with that of a recursive function. This is not a mathematical theorem but a statement that is believed to be true. Finally, algorithmically undecidable problems were looked at and this is where I came close to chucking the book out of the window. I struggled with some of these proofs.
The key to progress in understanding the relationship between recursive functions and URM programs is to realise that not all programs halt for a given input (that is reach the stage where there are no more instructions to process and an output is obtained). Some can loop round indefinitely and never reach an instruction that points outside of the program. To incorporate this into our idea of recursive functions, partial functions are introduced. A URM program computes a partial function f if for a given input, the program either halts and produces the output of f or it does not halt and f is undefined.
This either finding an output or not is equivalent to unbounded searches and the new process that is introduced is called minimisation (previously we had bounded minimisation). A new definition of recursive function is introduced (as opposed to primitive recursive) which says that a function is recursive if it can be obtained from basic primitive recursive functions using the operations of substitution, primitive recursion and minimisation on a function a finite number of times.
This allows us to finally answer the question that we originally asked. Are all URM-computable functions recursive? The answer is yes! This is part of the course that I think I really understood. The reason is relatively simple (although the proof was quite long and only sketched out); if you are at a particular stage of processing a URM program you can always determine what instruction you should process next based on the current values in the registers and what the current instruction says you should do. Unless you are at a jump instruction the next instruction to process is the one following the one you are at. Jump instructions depend on the contents of the registers. The key is that you can again provide a code number for all these situations of the program (imagine the trace table and a code that went with each entry in the table). This is clearly a recursive process except that, as we have said, an output may or may not be defined.
The chapter goes on to discuss Kleene's Normal Form Theorem, a consequence of which is that each recursive function can be obtained from the basic primitive recursive functions using the operations of substitution, primitive recursion and at most one minimisation on a function. The discussion was then broadened to Church's Thesis which says that the notion of an algorithmically computable function coincides with that of a recursive function. This is not a mathematical theorem but a statement that is believed to be true. Finally, algorithmically undecidable problems were looked at and this is where I came close to chucking the book out of the window. I struggled with some of these proofs.
Good progess but it is hard going
I thought I would give a quick update on where I am at now with the courses. I finished unit 3 of Mathematical Logic but it was a huge struggle. The last parts had me ready to chuck the book out of the window in frustration. I don't think I really got all of it and at times some of the proofs seemed like pulling rabbits out of hats - you had no idea where they came from and they were as impenetrable as magic.
So I soldiered on to unit GR2 of the groups course, thinking it might be a relief but some of the proofs we are asked to come up with for ourselves are impossible at times and there is only a limited number of hours in the day I can struggle over them, so it isn't very satisfying. GR2 was about Abelian and cyclic groups and their classification. I have now moved on to book 4 of the logic course on formal systems and this has been relatively light relief.
On the other hand the TMA's are going well. I have completed both of the first TMAs for the two courses and done over half the second TMA for the groups course. The groups TMAs are, by far, much easier than the number theory and logic ones. I enjoyed the flag colouring exercise but how we are to count distinguishable flags without using any of the results from the unit and awarding only 4 marks for it beggars belief. Perhaps I missed something.
So I soldiered on to unit GR2 of the groups course, thinking it might be a relief but some of the proofs we are asked to come up with for ourselves are impossible at times and there is only a limited number of hours in the day I can struggle over them, so it isn't very satisfying. GR2 was about Abelian and cyclic groups and their classification. I have now moved on to book 4 of the logic course on formal systems and this has been relatively light relief.
On the other hand the TMA's are going well. I have completed both of the first TMAs for the two courses and done over half the second TMA for the groups course. The groups TMAs are, by far, much easier than the number theory and logic ones. I enjoyed the flag colouring exercise but how we are to count distinguishable flags without using any of the results from the unit and awarding only 4 marks for it beggars belief. Perhaps I missed something.
Saturday 19 October 2013
Are all URM computable functions recursive? (Part 2)
This is where ML2 becomes more interesting. So far it had been
shown that all primitive recursive functions are URM-computable. But are all URM-computable functions primitive recursive?
Are there any functions of any sort that are not primitive recursive?
To answer this question required a diversion into infinite sets and Cantor's theory of countably infinite sets. This is the rather neat idea that a set is countably infinite if you can find a one-to-one correspondence between it and the set of natural numbers {0, 1, 2, 3, ...}. So, rather bizarrely, the set of even numbers {0, 2, 4, ...} is countably infinite since there is a one-one function f(n)=n/2 that maps the even numbers to the natural numbers. In fact, any infinite subset of the natural numbers is countably infinite.
Now the text goes on to show how we can assign each URM program a unique code number using the properties of prime numbers. Recall that the fundamental theorem of arithmetic means that a given natural number can only be written as positive powers of primes in one way. So, by assigning each instruction in a program a unique positive number (also referred to as a code number) and then creating a new number which is a product of primes raised to the power of these instruction numbers, then each program can be assigned a unique code number drawn from the set of natural numbers. So, of course, this subset is countably infinite. The advantage is that given a code number, we can recover the program uniquely.
So we come to the question as to whether there are any functions of any sort which are not primitive recursive. Here we use a diagonal argument of Cantor's (the same one he used to show that the set of real numbers is not countably infinite) to show that there are, i.e. that the set of functions is not countably infinite (as the set of primitive recursive functions is).
The rest of unit ML2 works towards proving that the set Prog of code numbers of URM programs is primitive recursive. This involves showing that the characteristic function of the set of prime numbers, the function p which enumerates the prime numbers and the set Instr of code numbers of URM instructions are all primitive recursive. The function p that enumerates the primes is simply the one that says, for example, that the 4th prime number is 7, i.e. that P(4)=7. The important concepts of bounded minimisation on a function or a relation are introduced. This is the the process of looking for a minimal solution of a function within a bounded (i.e. known) range.
So what does it mean to say that the set Prog of code numbers of URM programs is primitive recursive? I think it means that there is a primitive recursive function that can determine what these code numbers are and that in turn means that such a function is URM-computable, i.e. that there is a URM program that can compute them.
To answer this question required a diversion into infinite sets and Cantor's theory of countably infinite sets. This is the rather neat idea that a set is countably infinite if you can find a one-to-one correspondence between it and the set of natural numbers {0, 1, 2, 3, ...}. So, rather bizarrely, the set of even numbers {0, 2, 4, ...} is countably infinite since there is a one-one function f(n)=n/2 that maps the even numbers to the natural numbers. In fact, any infinite subset of the natural numbers is countably infinite.
Now the text goes on to show how we can assign each URM program a unique code number using the properties of prime numbers. Recall that the fundamental theorem of arithmetic means that a given natural number can only be written as positive powers of primes in one way. So, by assigning each instruction in a program a unique positive number (also referred to as a code number) and then creating a new number which is a product of primes raised to the power of these instruction numbers, then each program can be assigned a unique code number drawn from the set of natural numbers. So, of course, this subset is countably infinite. The advantage is that given a code number, we can recover the program uniquely.
So we come to the question as to whether there are any functions of any sort which are not primitive recursive. Here we use a diagonal argument of Cantor's (the same one he used to show that the set of real numbers is not countably infinite) to show that there are, i.e. that the set of functions is not countably infinite (as the set of primitive recursive functions is).
The rest of unit ML2 works towards proving that the set Prog of code numbers of URM programs is primitive recursive. This involves showing that the characteristic function of the set of prime numbers, the function p which enumerates the prime numbers and the set Instr of code numbers of URM instructions are all primitive recursive. The function p that enumerates the primes is simply the one that says, for example, that the 4th prime number is 7, i.e. that P(4)=7. The important concepts of bounded minimisation on a function or a relation are introduced. This is the the process of looking for a minimal solution of a function within a bounded (i.e. known) range.
So what does it mean to say that the set Prog of code numbers of URM programs is primitive recursive? I think it means that there is a primitive recursive function that can determine what these code numbers are and that in turn means that such a function is URM-computable, i.e. that there is a URM program that can compute them.
Tuesday 15 October 2013
Are all URM-computable functions recursive? (Part 1)
I have just got to that point in ML3 of M381 where this question has been answered affirmatively and it has been an interesting read getting there. I can't help feeling that this is really important but as yet I haven't understood all the implications of the theory. Before I forget I will try and outline how we arrived at that point by way of a summary, so I don't forget the basic ideas.
What is a URM-computable function? A URM is an unlimited register machine and a URM-computable function is a function that can be computed by such a machine (in other words the machine and the function produce the same output for the same given input). So what is it? Well, its a theoretical computer that can process a program with a very limited set of instructions (4 in fact) but has an unlimited (but finite) set of registers in which to store numbers (the integers 0, 1, 2, ...). The four instructions are Z(n) (Zero n; replace the number in register n by 0), S(n) (Successor n; add 1 to the number in register n), C(m,n) (Copy m to n; copy the number in register m to register n) and J(m,n,q) (Jump m, n, q; jump to instruction q if the numbers in register m and n are equal, otherwise go to the next instruction).
ML1 deals with some simple functions of two variables that can be computed by such machines; add, multiply, max, min etc. by showing how they can be programmed directly. However, the focus of the investigations is to find new ways of creating URM-computable functions by building them up from more basic functions. Firstly it is shown how programs can be concatenated by placing one program after another, so that the output of one becomes the input for another. Then, using this technique, two important theorems are proved - that new URM-computable functions can be obtained from existing ones by substitution and primitive recursion. For substitution, the new URM-computable function is obtained from existing ones by substituting URM-computable functions for the inputs of another. For primitive recursion, a sequence of new URM-computable functions are obtained by basing each new function on the previous one, which is again a form of substitution and requires two URM-computable functions 'to start the process off'.
The more interesting and, at times, difficult material appears in unit ML2. As said before, instead of programming functions directly, new URM-computable functions are obtained from existing ones by substitution and primitive recursion. The basic URM-computable functions considered were the zero, successor and projection functions which are the one-line programs containing the instructions Z(1), S(1) and C(m,1), respectively. Confusingly, perhaps, these are called the basic primitive recursive functions. Another function is said to be primitive recursive if it can be obtained from these basic ones by substitution and primitive recursion a finite number of times. ML2 goes on to show how more and more complicated primitive recursive functions can be obtained from these basic ones.
An important idea was introduced as to how to define such functions by cases. This is of the form 'if such and such is true then the function has this form, but if this is true then it has this form'. This required a detour into characteristic functions of sets and relations and determining if such functions are primitive recursive. This culminated in a proof that a function defined by cases is primitive recursive if the functions and relations that defined it (i.e. the cases) were primitive recursive.
What is a URM-computable function? A URM is an unlimited register machine and a URM-computable function is a function that can be computed by such a machine (in other words the machine and the function produce the same output for the same given input). So what is it? Well, its a theoretical computer that can process a program with a very limited set of instructions (4 in fact) but has an unlimited (but finite) set of registers in which to store numbers (the integers 0, 1, 2, ...). The four instructions are Z(n) (Zero n; replace the number in register n by 0), S(n) (Successor n; add 1 to the number in register n), C(m,n) (Copy m to n; copy the number in register m to register n) and J(m,n,q) (Jump m, n, q; jump to instruction q if the numbers in register m and n are equal, otherwise go to the next instruction).
ML1 deals with some simple functions of two variables that can be computed by such machines; add, multiply, max, min etc. by showing how they can be programmed directly. However, the focus of the investigations is to find new ways of creating URM-computable functions by building them up from more basic functions. Firstly it is shown how programs can be concatenated by placing one program after another, so that the output of one becomes the input for another. Then, using this technique, two important theorems are proved - that new URM-computable functions can be obtained from existing ones by substitution and primitive recursion. For substitution, the new URM-computable function is obtained from existing ones by substituting URM-computable functions for the inputs of another. For primitive recursion, a sequence of new URM-computable functions are obtained by basing each new function on the previous one, which is again a form of substitution and requires two URM-computable functions 'to start the process off'.
The more interesting and, at times, difficult material appears in unit ML2. As said before, instead of programming functions directly, new URM-computable functions are obtained from existing ones by substitution and primitive recursion. The basic URM-computable functions considered were the zero, successor and projection functions which are the one-line programs containing the instructions Z(1), S(1) and C(m,1), respectively. Confusingly, perhaps, these are called the basic primitive recursive functions. Another function is said to be primitive recursive if it can be obtained from these basic ones by substitution and primitive recursion a finite number of times. ML2 goes on to show how more and more complicated primitive recursive functions can be obtained from these basic ones.
An important idea was introduced as to how to define such functions by cases. This is of the form 'if such and such is true then the function has this form, but if this is true then it has this form'. This required a detour into characteristic functions of sets and relations and determining if such functions are primitive recursive. This culminated in a proof that a function defined by cases is primitive recursive if the functions and relations that defined it (i.e. the cases) were primitive recursive.
Tuesday 8 October 2013
Crisis, what crisis?
How can I be having a crisis at this stage, I hear you say? Well it's perfectly possible. I pretty much know how much work I have left to do over the 8 months of these two courses. I reckon that to cram 32 books into 8 months I need to be reading roughly 6 pages a day (3 from each course) and as I have already done a third of the books, that leaves 4 pages a day. So, since my last post I have been trying to do just that but I am struggling! What with trying to answer the exercises, read the proofs and then start to think about the coursework, it ain't easy.
So lo and behold I have reasoned that I am going to have to adopt a new strategy which I don't like very much. It comes in three parts 1) don't try to answer all the exercises 2) when answering an exercise just sketch out the answer and don't try to answer it as you would properly 3) skip the proofs where possible. Yuk! I don't like this prescription very much but I would rather not be sitting for hours on end each day getting back ache. And surprise, surprise, I have found that by doing this I can get 4 pages done a day - welcome to the real world!!
Progress. Ok, NT4 is done and I have nearly worked through GE1 (counting theorem again, but in a slightly more advanced and detailed way). I have been away for a weeks holiday in Norfolk and so I decided, in my non-holiday moments, to see I could finish TMA01 of M336 and amazingly I have! I have also done all the number theory questions of TMA01 of M381. I think M381 is harder! So now I feel a bit more relaxed and I can crack on with what I think will be increasingly more difficult material.
So lo and behold I have reasoned that I am going to have to adopt a new strategy which I don't like very much. It comes in three parts 1) don't try to answer all the exercises 2) when answering an exercise just sketch out the answer and don't try to answer it as you would properly 3) skip the proofs where possible. Yuk! I don't like this prescription very much but I would rather not be sitting for hours on end each day getting back ache. And surprise, surprise, I have found that by doing this I can get 4 pages done a day - welcome to the real world!!
Progress. Ok, NT4 is done and I have nearly worked through GE1 (counting theorem again, but in a slightly more advanced and detailed way). I have been away for a weeks holiday in Norfolk and so I decided, in my non-holiday moments, to see I could finish TMA01 of M336 and amazingly I have! I have also done all the number theory questions of TMA01 of M381. I think M381 is harder! So now I feel a bit more relaxed and I can crack on with what I think will be increasingly more difficult material.
Tuesday 17 September 2013
Eyes down
My course materials have now arrived for M381 and M336 and the course websites opened today and so off we go again. It is good to be in touch with people once more. It is hard doing all this preparation in advance without contact with anyone and but now that I have the actual books in front of me and the forums are open, it is much more motivating.
So how well did I do in my 6 months or so of preparation. Well, I got through NT1, 2, 3 and ML1 and 2 of M381 and IB1, 2, 3, 4 and GR1 of M336, so 10 books in all, just under a third of each course. So this will give me a head start and make the progress smoother, I hope! But I do realise that even with this advantage, I am going to have to speed up from the way I have been working so far, which has been at my usual leisurely pace.
What I have found surprising in what I have seen so far is how much more difficult the set problems are. It has been a bit of a shock to the system that there are problems that I just can't do without having a peek at the solutions. I could devote more hours to trying to solve the problems without help but I don't think this is good use of my time. So I have had a reality check about what I can and can't do and I think this is a good thing.
So now its back to the books. I am reading NT4 on Fermat's and Wilson's theorems. Strangely enough the last book I read of M336, GR1 was all about the theory of integers again, a repeat really of NT1 and 2, but actually, the way it was dealt with in GR1 was more difficult! The problems were a pain and, not like me, I couldn't be bothered to attempt the last four in the book - I felt too drained!
Another thing about these two courses is that it is all about proofs (both in the text and the set problems). So if you don't like proofs you are in for a hard time!
At some point I would like to write a summary of ML1 and 2. There was a lot of interesting stuff and writing a summary would help me to recall it all.
Good luck to you all and I look forward to meeting up with Chris and Dan again.
So how well did I do in my 6 months or so of preparation. Well, I got through NT1, 2, 3 and ML1 and 2 of M381 and IB1, 2, 3, 4 and GR1 of M336, so 10 books in all, just under a third of each course. So this will give me a head start and make the progress smoother, I hope! But I do realise that even with this advantage, I am going to have to speed up from the way I have been working so far, which has been at my usual leisurely pace.
What I have found surprising in what I have seen so far is how much more difficult the set problems are. It has been a bit of a shock to the system that there are problems that I just can't do without having a peek at the solutions. I could devote more hours to trying to solve the problems without help but I don't think this is good use of my time. So I have had a reality check about what I can and can't do and I think this is a good thing.
So now its back to the books. I am reading NT4 on Fermat's and Wilson's theorems. Strangely enough the last book I read of M336, GR1 was all about the theory of integers again, a repeat really of NT1 and 2, but actually, the way it was dealt with in GR1 was more difficult! The problems were a pain and, not like me, I couldn't be bothered to attempt the last four in the book - I felt too drained!
Another thing about these two courses is that it is all about proofs (both in the text and the set problems). So if you don't like proofs you are in for a hard time!
At some point I would like to write a summary of ML1 and 2. There was a lot of interesting stuff and writing a summary would help me to recall it all.
Good luck to you all and I look forward to meeting up with Chris and Dan again.
Monday 19 August 2013
More on Generating Subgroups
I seem to be blogging more about the groups course M336 rather than the number theory and mathematical logic course M381, but I get the feeling this will all change at some point as I get further into mathematical logic.
Ok, time for an update. I finished the first mathematical logic unit of M381 without too much difficulty. I think the hardest part is dealing with a whole load of new concepts. Once you get the hang of these then it seems to be alright. I then moved onto unit 4 of groups and geometry and this was quite a time consuming book both from the length of it and the considerable number proofs that you have to wade through and also come up with yourself. A lot of the material was revision going over topics such as cosets, normal subgroups, quotient groups, isomorphisms and homomorphisms. However, there was quite a lot of new material and perhaps the most important was proving that you can generate a subgroup of a group using elements of that group (see my previous post).
The approach to this theory was different from what I expected and quite subtle. Firstly, the subgroup of a group G generated by an underlying set of elements S is defined to be the 'smallest' subgroup of G containing the set S. This is denoted <S>. The first step is to prove that there is a unique smallest subgroup of G that contains S. The trick is to consider all the subgroups of G that contain S. This collection is certainly not empty since it contains G (as G is a subgroup of itself). Now consider the intersection H of all these subgroups that contain S. The intersection of a set of subgroups is itself a subgroup (and this was proved in the unit). So H is a subgroup of G. It also contains S because our collection of subgroups each contained S. Further, H must be the 'smallest' subgroup of G containing S because H is the intersection of our set of subgroups and so is contained by those subgroups. Hence <S>=H.
Although this tells us that <S> exists it does not tell us what <S> looks like! The subgroup axioms come in handy here. <S> must contain the identity of G, e say, and the inverse of the elements of S in G. This means that <S> must also be generated by these elements (namely e, the elements of S and the inverse of the elements of S). We can call this set S'. The text then goes on to show that <S> is generated by the set of words in S', W(S'). As words in English are created by taking any finite arrangement of letters (in principle) drawn from our 26 letter alphabet, so the words in W(S') are formed by taking any finite arrangement of elements from S' (but in English we might suspect that eeeeeaaaaeeeooooaeaor isn't a word as it is in group theory!). It turns out that <S>=W(S').
Having been writing this blog over the last few days I have got further into unit 2 of mathematical logic and, surprise, surprise, I have found some of it increasingly difficult (if not impossible)! However, having said that I can't help thinking it is blooming neat and I am glad I am doing it as I think it has resonances in some of the things I have thought about number theory.
Ok, time for an update. I finished the first mathematical logic unit of M381 without too much difficulty. I think the hardest part is dealing with a whole load of new concepts. Once you get the hang of these then it seems to be alright. I then moved onto unit 4 of groups and geometry and this was quite a time consuming book both from the length of it and the considerable number proofs that you have to wade through and also come up with yourself. A lot of the material was revision going over topics such as cosets, normal subgroups, quotient groups, isomorphisms and homomorphisms. However, there was quite a lot of new material and perhaps the most important was proving that you can generate a subgroup of a group using elements of that group (see my previous post).
The approach to this theory was different from what I expected and quite subtle. Firstly, the subgroup of a group G generated by an underlying set of elements S is defined to be the 'smallest' subgroup of G containing the set S. This is denoted <S>. The first step is to prove that there is a unique smallest subgroup of G that contains S. The trick is to consider all the subgroups of G that contain S. This collection is certainly not empty since it contains G (as G is a subgroup of itself). Now consider the intersection H of all these subgroups that contain S. The intersection of a set of subgroups is itself a subgroup (and this was proved in the unit). So H is a subgroup of G. It also contains S because our collection of subgroups each contained S. Further, H must be the 'smallest' subgroup of G containing S because H is the intersection of our set of subgroups and so is contained by those subgroups. Hence <S>=H.
Although this tells us that <S> exists it does not tell us what <S> looks like! The subgroup axioms come in handy here. <S> must contain the identity of G, e say, and the inverse of the elements of S in G. This means that <S> must also be generated by these elements (namely e, the elements of S and the inverse of the elements of S). We can call this set S'. The text then goes on to show that <S> is generated by the set of words in S', W(S'). As words in English are created by taking any finite arrangement of letters (in principle) drawn from our 26 letter alphabet, so the words in W(S') are formed by taking any finite arrangement of elements from S' (but in English we might suspect that eeeeeaaaaeeeooooaeaor isn't a word as it is in group theory!). It turns out that <S>=W(S').
Having been writing this blog over the last few days I have got further into unit 2 of mathematical logic and, surprise, surprise, I have found some of it increasingly difficult (if not impossible)! However, having said that I can't help thinking it is blooming neat and I am glad I am doing it as I think it has resonances in some of the things I have thought about number theory.
Thursday 11 July 2013
T minus 86 days and counting
I received confirmation the day before yesterday that the SAAS are paying my course fees for M381 and M336 this October and so I am all set for my next year's work. I am very grateful to the Scottish system of support for the likes of me.
I am progressing ok. I finished unit 3 of the number theory half of M381 on congruence. This was fairly straight forward and didn't offer any particular difficulties. In the mean time I have also finished unit IB3 of M336 on frieze groups and again this wasn't particularly challenging. I can now see where this course is going with its classification of friezes and wallpaper patterns. I did always wonder what Alan, our tutor for M208, was always going on about when he said that there were 17 different types of wallpaper pattern and now I have an inkling of what he may mean. I have also now got through a fair chunk of unit 1 of the mathematical logic half of M381 on computability. This is ok as it is basic linear programming.
Going back to friezes, I thought I would show you an example of a frieze that can be found in our flat.
My Dad (who knows these things because he is an architect) pointed out to me that this type of cornice is called "egg and dart" which I think is an apt description. From a mathematical point of view, if you take the decoration bit in the middle as the frieze (ignoring the fact that it obviously doesn't extend indefinitely to the left and right), then it has a number of different symmetries. For example, if you take a basic element of an egg bounded by half a dart on either side, then you can translate this element horizontally left and right by multiples of the distance between two adjacent darts. This is what defines a frieze. There are also, obviously, reflections in a vertical axis (either through a dart or through the centre of an egg). There are, however, no rotational symmetries or reflections or glide reflections in a horizontal axis.
Each frieze can be analysed according to its group of symmetries and an algorithm is given in the unit for identifying the type of frieze according to its group. This is a type 2 frieze or in international notation a pm11. There are seven types of frieze in all, as defined by their symmetry group.
I am progressing ok. I finished unit 3 of the number theory half of M381 on congruence. This was fairly straight forward and didn't offer any particular difficulties. In the mean time I have also finished unit IB3 of M336 on frieze groups and again this wasn't particularly challenging. I can now see where this course is going with its classification of friezes and wallpaper patterns. I did always wonder what Alan, our tutor for M208, was always going on about when he said that there were 17 different types of wallpaper pattern and now I have an inkling of what he may mean. I have also now got through a fair chunk of unit 1 of the mathematical logic half of M381 on computability. This is ok as it is basic linear programming.
Going back to friezes, I thought I would show you an example of a frieze that can be found in our flat.
My Dad (who knows these things because he is an architect) pointed out to me that this type of cornice is called "egg and dart" which I think is an apt description. From a mathematical point of view, if you take the decoration bit in the middle as the frieze (ignoring the fact that it obviously doesn't extend indefinitely to the left and right), then it has a number of different symmetries. For example, if you take a basic element of an egg bounded by half a dart on either side, then you can translate this element horizontally left and right by multiples of the distance between two adjacent darts. This is what defines a frieze. There are also, obviously, reflections in a vertical axis (either through a dart or through the centre of an egg). There are, however, no rotational symmetries or reflections or glide reflections in a horizontal axis.
Each frieze can be analysed according to its group of symmetries and an algorithm is given in the unit for identifying the type of frieze according to its group. This is a type 2 frieze or in international notation a pm11. There are seven types of frieze in all, as defined by their symmetry group.
Thursday 23 May 2013
Generating subgroups
I have just finished going through book 2 of M336 Groups and Geometry and I am making reasonable progress. As usual I seem to be working at roughly half the speed that you are supposed to but I expect I will get through enough material to make life easier when the course actually starts in October. So now I have read four books in total from M336 and M381 and I am alternating between the two courses; i.e. when I finish a book from one course I start on a book from the other course. I will be looking at book 3 from M381 next which is on congruence.
Before I leave book 2 of M336, there are a few things I want to say about it. Firstly, I have noticed that the exercises in these level 3 courses require much more from the student. At level 2 it was pretty much spoon feeding - i.e. the books would give examples of how to do something and then there would be exercises where you repeat what you just learnt. Here at level 3 the questions are more demanding as the way to do an exercise is often left up to the student. I welcome this as I like thinking things through for myself, but at times it can be very time consuming. What has surprised me is that a certain amount of 'hand-waving' has appeared both in the text and in the answers to exercises; i.e. rather than thrashing out an answer exhaustively, a bit of 'well, the answer is like this because of such and such.' It can be a bit frustrating if the details are skipped over and a bit of shock after the intense rigour of M208.
I want to put down here some bits of this book which I thought ventured slightly into the hand-waving arena. This part of the book was the most difficult and the most time consuming and so it is worth going through so that later I have something to look back on for revision.
How can you generate subgroups? In M208 we have already met cyclic subgroups which are generated from integer powers of an element in a group. For example, if we consider the group of symmetries of the regular hexagon and label a rotation about its centre through π/3 as r then we can generate a cyclic subgroup from r as
$$<r>=\left\{r^{0}, r, r^{2}, r^{3}, r^{4}, r^{5}\right\}$$
Now the new idea is to expand this notion of generating subgroups to include two or more distinct elements of a group. In the text it says that "Informally, we define the subgroup generated by x,y,... to be the set obtained by forming all possible combinations of copies of x,y,.. and their inverses." In the margins it does say that a formal definition is given later in unit IB4 but I found it difficult to understand this without some formal definition. Here is my version of a formal definition for two distinct elements of a group x and y:-
$$<x,y>=\left\{uv:u,v \in \left\{ (x)^{i},(y)^{i}:i,j \in Z \right\} \right\}$$
Now it is clear that integer powers of x and integer powers of y are just the cyclic subgroups <x> and <y> and so we can rewrite this as
$$<x,y>=\left\{uv:u,v \in <x>\cup<y> \right\}$$
In other words we are taking combinations of elements taken from a union of the subgroups generated by x and y. This does not mean that the resulting subset is a subgroup. This still has to be verified by seeing if the subset satisfies the subgroup properties. One thing that becomes clear straight away is that <x,y> contains the elements of <x> and the elements of <y>. This is because if u and v are drawn from <x>, say, then because <x> is a cyclic subgroup, then the combinations of uv are also in <x>. What is new are products of elements which are not common to both sets.
Let's take an example. If we consider the regular hexagon again and call the symmetry that is a reflection in the horizontal axis s, then s is self-inverse and
$$<s>=\left\{e,s\right\}$$
If we also consider the half-turn about the centre r3 then this is also self-inverse and
$$<r^{3}>=\left\{e,r^{3}\right\}$$
But what about <r3,s>? We see from the above discussion that this is going to contain e, r3, and s but it also must contain combinations of elements which are not common to both sets, namely sr3 and r3s. These turn out to be the same element since sr3 is a reflection of some sort which is self-inverse so
$$sr^{3}=(sr^{3})^{-1}=r^{-3}s^{-1}=r^{3}s$$
Hence we have the subset
$$<r^{3},s>=\left\{e, r^{3}, s, r^{3}s\right\}$$
which does indeed turn out to be a subgroup of the symmetries of the regular hexagon and is isomorphic to the Klein group.
Before I leave book 2 of M336, there are a few things I want to say about it. Firstly, I have noticed that the exercises in these level 3 courses require much more from the student. At level 2 it was pretty much spoon feeding - i.e. the books would give examples of how to do something and then there would be exercises where you repeat what you just learnt. Here at level 3 the questions are more demanding as the way to do an exercise is often left up to the student. I welcome this as I like thinking things through for myself, but at times it can be very time consuming. What has surprised me is that a certain amount of 'hand-waving' has appeared both in the text and in the answers to exercises; i.e. rather than thrashing out an answer exhaustively, a bit of 'well, the answer is like this because of such and such.' It can be a bit frustrating if the details are skipped over and a bit of shock after the intense rigour of M208.
I want to put down here some bits of this book which I thought ventured slightly into the hand-waving arena. This part of the book was the most difficult and the most time consuming and so it is worth going through so that later I have something to look back on for revision.
How can you generate subgroups? In M208 we have already met cyclic subgroups which are generated from integer powers of an element in a group. For example, if we consider the group of symmetries of the regular hexagon and label a rotation about its centre through π/3 as r then we can generate a cyclic subgroup from r as
$$<r>=\left\{r^{0}, r, r^{2}, r^{3}, r^{4}, r^{5}\right\}$$
Now the new idea is to expand this notion of generating subgroups to include two or more distinct elements of a group. In the text it says that "Informally, we define the subgroup generated by x,y,... to be the set obtained by forming all possible combinations of copies of x,y,.. and their inverses." In the margins it does say that a formal definition is given later in unit IB4 but I found it difficult to understand this without some formal definition. Here is my version of a formal definition for two distinct elements of a group x and y:-
$$<x,y>=\left\{uv:u,v \in \left\{ (x)^{i},(y)^{i}:i,j \in Z \right\} \right\}$$
Now it is clear that integer powers of x and integer powers of y are just the cyclic subgroups <x> and <y> and so we can rewrite this as
$$<x,y>=\left\{uv:u,v \in <x>\cup<y> \right\}$$
In other words we are taking combinations of elements taken from a union of the subgroups generated by x and y. This does not mean that the resulting subset is a subgroup. This still has to be verified by seeing if the subset satisfies the subgroup properties. One thing that becomes clear straight away is that <x,y> contains the elements of <x> and the elements of <y>. This is because if u and v are drawn from <x>, say, then because <x> is a cyclic subgroup, then the combinations of uv are also in <x>. What is new are products of elements which are not common to both sets.
Let's take an example. If we consider the regular hexagon again and call the symmetry that is a reflection in the horizontal axis s, then s is self-inverse and
$$<s>=\left\{e,s\right\}$$
If we also consider the half-turn about the centre r3 then this is also self-inverse and
$$<r^{3}>=\left\{e,r^{3}\right\}$$
But what about <r3,s>? We see from the above discussion that this is going to contain e, r3, and s but it also must contain combinations of elements which are not common to both sets, namely sr3 and r3s. These turn out to be the same element since sr3 is a reflection of some sort which is self-inverse so
$$sr^{3}=(sr^{3})^{-1}=r^{-3}s^{-1}=r^{3}s$$
Hence we have the subset
$$<r^{3},s>=\left\{e, r^{3}, s, r^{3}s\right\}$$
which does indeed turn out to be a subgroup of the symmetries of the regular hexagon and is isomorphic to the Klein group.
Friday 26 April 2013
Tilings
I am still ploughing through the first unit of M336 'Groups and Geometry' and there have been a lot of new ideas to digest concerning the topic of tilings. Sometimes I find the definitions hard to fix in my mind and it is a bit like learning a new language. For example, I found adjacency and incidence bothersome and I keep having to go back to the definitions in order to understand what they mean.
A tiling can be divided into three different parts; the tiles themselves, the vertices and the edges. Each of these parts has a particular meaning. The vertices are points on the boundary where three or more tiles meet and the edges are points on the boundary which join vertices and are where two tiles meet. Now the edges don't have to be straight lines, they can be curved. Also, if the tiles are polygons, the tiles can have corners which are not necessarily vertices and sides that can be made up of more than one edge (and vice versa). All very confusing. Some of this confusion is removed by demanding that a tiling is edge-to-edge, i.e. that each side of the polygon corresponds to exactly one edge and vice versa.
Now adjacency is a relationship between the same parts of a tiling whereas incidence is a relationship between different parts of a tiling. Now here is the definition of these two concepts.
Two distinct tiles are adjacent if they share a common edge. Two distinct vertices are adjacent if they are joined by an edge. Two distinct edges are adjacent if they share a common vertex and bound a common tile.
The edges and vertices on the boundary of a tile T in a tiling are incident with T. Similarly, T is incident with the edges and vertices on its boundary. Also, if an edge E joins vertices V and W, then E is incident with V and W and these vertices are incident with E.
Another important definition is the degree of a tile or vertex. The degree of a tile in a tiling is the number of other tiles to which it is adjacent. The degree of a vertex in a tiling is the number of tiles (or alternatively the number of edges) with which it is incident.
Some examples of Archimedean tilings can be found here. An Archimedean tiling is an edge-to-edge tiling with regular polygons that is vertex-uniform. Only 11 such tilings can be constructed (allowing for one to be a reflection of the other). The first three are the regular tilings and the other 8 are semi-regular. Under each tile is a number. For example under the snub hexagonal tiling is the number 34.6. In OU parlance this is the vertex type (3,3,3,3,6). If V is any vertex in a tiling, then the vertex type of V is given by listing the degrees of the tiles incident with V, starting with any one of them and proceeding in either direction in clockwise or anticlockwise order. So you can see how you have to understand all these definitions!
If you look at the snub hexagonal tiling you notice that all the vertices look the same. Choosing any vertex, then incident with it are four equilateral shaped tiles and one hexagonal tile. If we look at the equilateral triangle tile, then there are three tiles to which it is adjacent, that is its degree is 3 (since this is an edge-to-edge tiling there are as many adjacent tiles as there are sides of the equilateral triangle). If we look at the hexagonal tile then its degree is obviously six. Thus going round the vertex that we chose in either direction we end up with a vertex type of (3,3,3,3,6) (allowing for cyclic permutations of these numbers). A tiling is vertex-uniform if all the vertex types in the tiling are the same.
Not only can you define a vertex type but you can also define a tile type. It is similar in definition to a vertex type, but instead you list the degrees of the vertices incident with a tile in a tiling. The tile type of our snub hexagonal tiling is not uniform. The tile type for the hexagon is [5,5,5,5,5,5] (notice that square brackets are used) but the tile type for the equilateral triangle is [5,5,5].
My method for remembering how to find a vertex type or a tile type is that for vertex types it is tile-tile (i.e. you are counting tiles around tiles incident to a vertex) and for tile types it is vertex-vertex (i.e. you are counting vertices around vertices incident to a tile).
A tiling can be divided into three different parts; the tiles themselves, the vertices and the edges. Each of these parts has a particular meaning. The vertices are points on the boundary where three or more tiles meet and the edges are points on the boundary which join vertices and are where two tiles meet. Now the edges don't have to be straight lines, they can be curved. Also, if the tiles are polygons, the tiles can have corners which are not necessarily vertices and sides that can be made up of more than one edge (and vice versa). All very confusing. Some of this confusion is removed by demanding that a tiling is edge-to-edge, i.e. that each side of the polygon corresponds to exactly one edge and vice versa.
Now adjacency is a relationship between the same parts of a tiling whereas incidence is a relationship between different parts of a tiling. Now here is the definition of these two concepts.
Two distinct tiles are adjacent if they share a common edge. Two distinct vertices are adjacent if they are joined by an edge. Two distinct edges are adjacent if they share a common vertex and bound a common tile.
The edges and vertices on the boundary of a tile T in a tiling are incident with T. Similarly, T is incident with the edges and vertices on its boundary. Also, if an edge E joins vertices V and W, then E is incident with V and W and these vertices are incident with E.
Another important definition is the degree of a tile or vertex. The degree of a tile in a tiling is the number of other tiles to which it is adjacent. The degree of a vertex in a tiling is the number of tiles (or alternatively the number of edges) with which it is incident.
Some examples of Archimedean tilings can be found here. An Archimedean tiling is an edge-to-edge tiling with regular polygons that is vertex-uniform. Only 11 such tilings can be constructed (allowing for one to be a reflection of the other). The first three are the regular tilings and the other 8 are semi-regular. Under each tile is a number. For example under the snub hexagonal tiling is the number 34.6. In OU parlance this is the vertex type (3,3,3,3,6). If V is any vertex in a tiling, then the vertex type of V is given by listing the degrees of the tiles incident with V, starting with any one of them and proceeding in either direction in clockwise or anticlockwise order. So you can see how you have to understand all these definitions!
If you look at the snub hexagonal tiling you notice that all the vertices look the same. Choosing any vertex, then incident with it are four equilateral shaped tiles and one hexagonal tile. If we look at the equilateral triangle tile, then there are three tiles to which it is adjacent, that is its degree is 3 (since this is an edge-to-edge tiling there are as many adjacent tiles as there are sides of the equilateral triangle). If we look at the hexagonal tile then its degree is obviously six. Thus going round the vertex that we chose in either direction we end up with a vertex type of (3,3,3,3,6) (allowing for cyclic permutations of these numbers). A tiling is vertex-uniform if all the vertex types in the tiling are the same.
Not only can you define a vertex type but you can also define a tile type. It is similar in definition to a vertex type, but instead you list the degrees of the vertices incident with a tile in a tiling. The tile type of our snub hexagonal tiling is not uniform. The tile type for the hexagon is [5,5,5,5,5,5] (notice that square brackets are used) but the tile type for the equilateral triangle is [5,5,5].
My method for remembering how to find a vertex type or a tile type is that for vertex types it is tile-tile (i.e. you are counting tiles around tiles incident to a vertex) and for tile types it is vertex-vertex (i.e. you are counting vertices around vertices incident to a tile).
Tuesday 9 April 2013
First books
Well, I have made a start on the course books for 'Groups and Geometry' (M336) and 'Number theory and mathematical logic' (M381). I began with M381 and the first book, which I have now gone through, 'Foundations' deals with four topics; Numbers from Patterns, Mathematical Induction, Divisibility and the Linear Diophantine Equation, much of which I have already encountered. The material is well written and the proofs are straight-forward but the exercises are a jump up in difficulty. I found myself struggling with a few and one I just couldn't see how to do at all. Still, it is to be expected in going up from level 2 to level 3.
I then started tackling the first book of M336 on Tilings and I must say that I think I like what I have read so far. It is refreshing to enter a new area of maths that I know nothing much about. This course also seems very well written and the ideas are being built up in nice easy stages.
In the mean time I have started on the second book of M381 which is on prime numbers. As this is something that interests me greatly, I will be relishing this book and am looking forward to its contents.
I have now signed up for M381 and M336 and my next aim will be to get together the funding I need to pay for the courses.
I then started tackling the first book of M336 on Tilings and I must say that I think I like what I have read so far. It is refreshing to enter a new area of maths that I know nothing much about. This course also seems very well written and the ideas are being built up in nice easy stages.
In the mean time I have started on the second book of M381 which is on prime numbers. As this is something that interests me greatly, I will be relishing this book and am looking forward to its contents.
I have now signed up for M381 and M336 and my next aim will be to get together the funding I need to pay for the courses.
Tuesday 26 March 2013
A change of heart
Well, contrary to everything I have said before about not continuing on with my OU studies, I have had a change of heart and have decided to see if I can finish my BSc honours maths degree that I signed up for in 2009. Why this change? Well, I realise that I do have a hankering to do something in maths and I may regret it in the future if I don't try and see how far I can get. I also realise that getting ends to meet from my current work in photography is getting harder and harder and so eventually I am going to have to do something else anyway. Coming back from a week in Berlin, I realised that I just have to give it a go, regardless of the potential difficulties of approaching the time of life when most people are thinking of retirement! Still, the government wants us all to work after retirement age, so I will be trying this out. I just hope the brain cells don't wear out before I get to the point where I can contribute something to this subject.
So having made the decision, it's all kind of exciting and daunting at the same time. The first thing is to concentrate on this degree which, due to the reorganisation of these qualifications, I now have to finish by the 31/12/17. This gives me four years and, at 60 points a year, I hope to get the additional 240 points I need to pass (I already have 120 points from MST121, MS221 and M208). There are now two routes a student can follow in this degree. Route A means following what was originally prescribed and, for me, at level 2 that would mean doing the 60 point 'Mathematical methods and models' (MST209) and the 10 point summer school 'Mathematical modelling' (MSXR209). For a number of reasons, I am going to plump for route B, which means doing the new 60 point 'Mathematical methods and models' (MST210) which does not require the summer school any more. However, this does mean that I will have to wait until October 2014 to start this course and it will also mean that I will have to do the new 30 point level 1 course 'Introducing statistics' (M140).
In the mean time I need to get another 60 points under my belt starting this October and I think the best option for me having only done M208 so far, is to do the level 3 30 point courses 'Groups and Geometry' (M336) and 'Number theory and mathematical logic' (M381). This is the final presentation of these two courses before they are replaced by 'Further pure mathematics' (M303). This new course will be available from 2014 and will be an amalgamated version of M336, M381 and the now extinct 'Topology' course (M338). I think I will be pursuing a more pure maths direction in my further studies and number theory is already something I think would like to specialise in, so it all makes good sense.
As for the remaining 90 points, I have only to do 60 more points at level 3 and 30 points from a free choice of OU modules. However, I agree with Chris that I want to squeeze in the level 3 30 point 'Complex Analysis' (M337) and at the moment this is presented on alternate years (I believe), though this could change. I expect I want to get a good grounding in both pure and applied maths in case this comes in useful, so a couple of level 3 30 point applied courses may be an option.
In the mean time it is eyes down again and time to start getting ahead to alleviate future stresses of workload. So I have already got hold of some of the books for the 'Number theory and mathematical logic' course and have started on the first book. It looks like some of this will already be covered by my reading of John Stillwell's book, which I am still making some progress on, so that's all well and good.
So having made the decision, it's all kind of exciting and daunting at the same time. The first thing is to concentrate on this degree which, due to the reorganisation of these qualifications, I now have to finish by the 31/12/17. This gives me four years and, at 60 points a year, I hope to get the additional 240 points I need to pass (I already have 120 points from MST121, MS221 and M208). There are now two routes a student can follow in this degree. Route A means following what was originally prescribed and, for me, at level 2 that would mean doing the 60 point 'Mathematical methods and models' (MST209) and the 10 point summer school 'Mathematical modelling' (MSXR209). For a number of reasons, I am going to plump for route B, which means doing the new 60 point 'Mathematical methods and models' (MST210) which does not require the summer school any more. However, this does mean that I will have to wait until October 2014 to start this course and it will also mean that I will have to do the new 30 point level 1 course 'Introducing statistics' (M140).
In the mean time I need to get another 60 points under my belt starting this October and I think the best option for me having only done M208 so far, is to do the level 3 30 point courses 'Groups and Geometry' (M336) and 'Number theory and mathematical logic' (M381). This is the final presentation of these two courses before they are replaced by 'Further pure mathematics' (M303). This new course will be available from 2014 and will be an amalgamated version of M336, M381 and the now extinct 'Topology' course (M338). I think I will be pursuing a more pure maths direction in my further studies and number theory is already something I think would like to specialise in, so it all makes good sense.
As for the remaining 90 points, I have only to do 60 more points at level 3 and 30 points from a free choice of OU modules. However, I agree with Chris that I want to squeeze in the level 3 30 point 'Complex Analysis' (M337) and at the moment this is presented on alternate years (I believe), though this could change. I expect I want to get a good grounding in both pure and applied maths in case this comes in useful, so a couple of level 3 30 point applied courses may be an option.
In the mean time it is eyes down again and time to start getting ahead to alleviate future stresses of workload. So I have already got hold of some of the books for the 'Number theory and mathematical logic' course and have started on the first book. It looks like some of this will already be covered by my reading of John Stillwell's book, which I am still making some progress on, so that's all well and good.
Friday 15 February 2013
Using group theory to prove Fermat's little theorem
Here is a demonstration of the use of group theory that I thought was quite neat. Fermat's little theorem states that if p is a prime number and a is a natural number that is not divisible by p (i.e. a is not congruent to 0 (mod p)) then
$$a^{p-1}\equiv 1 \;\mbox{(mod p) ...(1) }$$
Now recall from M208 that if p is prime then
$$(Z^{*}_{p},\times_{p})$$
is a group of order p-1 (see the Handbook for M208 on page 30). Now we can use Lagrange's Theorem (Handbook page 35) to prove Fermat's little theorem as follows. Let a be a natural number that is not divisible by a prime number p, then a will be congruent to an element of the above group, i.e. to one of the set
$$\left\{1,2,3,..,(p-1)\right\}$$
Let this element be g so that
$$a\equiv g \;\mbox{(mod p)}$$
Now g will generate a cyclic subgroup of order n (Handbook page 28) and by Lagrange's Theorem (page 35) n will divide p-1, the order of the group. Hence
$$p-1=mn$$
for some natural number m and thus
$$a^{p-1}\equiv g^{p-1}\equiv g^{mn}\equiv(g^{n})^{m}\;\mbox{(mod p)}$$
Now by definition
$$g^{n}\equiv 1 \;\mbox{(mod p)}$$
and so
$$a^{p-1}\equiv 1^{m}\equiv 1\;\mbox{(mod p)}$$
Hence (1) is proven.
$$a^{p-1}\equiv 1 \;\mbox{(mod p) ...(1) }$$
Now recall from M208 that if p is prime then
$$(Z^{*}_{p},\times_{p})$$
is a group of order p-1 (see the Handbook for M208 on page 30). Now we can use Lagrange's Theorem (Handbook page 35) to prove Fermat's little theorem as follows. Let a be a natural number that is not divisible by a prime number p, then a will be congruent to an element of the above group, i.e. to one of the set
$$\left\{1,2,3,..,(p-1)\right\}$$
Let this element be g so that
$$a\equiv g \;\mbox{(mod p)}$$
Now g will generate a cyclic subgroup of order n (Handbook page 28) and by Lagrange's Theorem (page 35) n will divide p-1, the order of the group. Hence
$$p-1=mn$$
for some natural number m and thus
$$a^{p-1}\equiv g^{p-1}\equiv g^{mn}\equiv(g^{n})^{m}\;\mbox{(mod p)}$$
Now by definition
$$g^{n}\equiv 1 \;\mbox{(mod p)}$$
and so
$$a^{p-1}\equiv 1^{m}\equiv 1\;\mbox{(mod p)}$$
Hence (1) is proven.
Sunday 3 February 2013
Why is the sun hot?
This is a slight departure from my usual posts here but I wanted to counter something that appears in the course notes for S382 Astrophysics and in the book "Stellar Evolution and Nucleosynthesis" which I think is misleading. Dan has raised the subject of 'Why is the sun hot' in his blog and I want to discuss some of the issues that have been raised here rather than trashing his blog with lots of comments.
First I am going to quote some bits and pieces from "Stellar Evolution and Nucleosynthesis" by Ryan and Norton. In chapter 2 of their book on page 46 they have a section 2.6 entitled "Why are stars hot? Putting fusion in its place". They say:-
"In Chapter 1 you saw that hydrogen fusion provides the power that is radiated by the Sun and other main-sequence stars. In this Chapter, you have seen the importance of the gravitation energy released by a collapsing cloud of gas. In order to understand the roles of these two sources of energy, before we go any further, we pause to consider exactly what fusion is and is not responsible for."
They go on to discuss how much energy is released per cubic metre in the core of the Sun by nuclear fusion and this turns out to be about 300 Watts.
They go on to say:-
"Think about this number: 300 Wm-3. Imagine putting three 100 W lightbulbs in a broom cupboard whose volume is about 1 cubic metre. Would that make the cupboard as bright and hot as the Sun?"
"No, clearly it would not. In fact, 300 W seems like a pathetically tiny power output for a volume as large as 1m3, especially in something as hot as the core of the Sun! Is the calculation grossly wrong? No, the power output per cubic metre is that small. Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse! (But it is a big reservoir!)"
After some further number crunching the books says:
"You might be tempted at this stage to think that, even though the power released in fusion is very small, the energy released heats up the core of a star, and this is why stars are hot. The energy released is indeed very important, but it is not the reason that stars heat up. In fact the opposite is true; fusion prevents a star from getting hotter!"
"In fact, a star's temperature and luminosity are not determined by nuclear burning. However, they are maintained by nuclear burning. Nuclear fusion replenishes the slow leakage of energy from the star's core and eventually from its surface. As you saw in the last Section, the release of gravitational potential energy can do exactly the same thing, but the nuclear fusion energy source has the advantage that it lasts for much longer. That is, nuclear fusion greatly delays the gravitational collapse of the star."
"If someone had asked you at the beginning of this book, 'What makes stars hot?', you could have been forgiven for answering 'It is because they have thermonuclear reaction in their cores.' That answer sounds plausible, but hopefully now you can see that it is incorrect. Stars are hot because they have collapsed from large diffuse clouds and gravitational potential energy has been converted to kinetic energy. That is why stars are hot."
I think that the above discussion and conclusion are very misleading. You could come away with the idea that nuclear fusion in the Sun is not an important source of its energy output ("Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse") but that release of energy from gravitational potential energy is ("the release of gravitational potential energy can do exactly the same thing"). This is of course, incorrect.
The question that needs to be asked is this. Would the Sun be hot now after having existed for approximately 4.6 billion years if nuclear reactions weren't taking place in its core? The answer to this is no. If there was no other energy source in the Sun apart from the release of gravitational potential energy, then at its current luminosity it would only shine for approximately 18 million years , a time-scale that is about 256 times too short. It follows then that the Sun would have cooled to well below its current temperature by now if heating by contraction was its only source of energy. We know, anyway, that the Sun is in equilibrium, which means that it is neither contracting nor expanding. You can't have energy released by gravitational potential if the Sun isn't contracting.
The argument about the three 100 Watt light bulbs in a cupboard is also misleading ("Would that make the cupboard as bright and hot as the Sun? No clearly, it would not!"). The cupboard could get as bright as the surface of the Sun and even as high as the core of the Sun, if the cupboard was perfectly insulated. This is how an ideal oven would work. In fact, I find the langauge used by the authors ("300 W seems like a pathetically tiny power output for a volume as large as 1m3") emotive and inappropriate for a science text.
So is nuclear fusion in the Sun much of a powerhouse? Yes, it is. Although of 300 Watts per metre cubed sounds like a small number it is sufficient to power the output of the Sun for billions of years and maintain the temperature in its core for the duration.
So why is the Sun hot? I would argue it is hot for both of the reasons discussed, neither of which can be disentagled or discounted. The collapse of the gas cloud that led to the formation of the Sun was responsible for getting the core of the Sun up to a temperature where nuclear fusion could take place and nuclear fusion is responsible for maintaining that temperature of the Sun, in both the core and on its surface, until now. To overemphasise the role of gravitational energy in the way that these authors have done in their book is, in my opinion, very misleading and it is disappointing if this is also true of the course notes for the OU Astrophysics course.
First I am going to quote some bits and pieces from "Stellar Evolution and Nucleosynthesis" by Ryan and Norton. In chapter 2 of their book on page 46 they have a section 2.6 entitled "Why are stars hot? Putting fusion in its place". They say:-
"In Chapter 1 you saw that hydrogen fusion provides the power that is radiated by the Sun and other main-sequence stars. In this Chapter, you have seen the importance of the gravitation energy released by a collapsing cloud of gas. In order to understand the roles of these two sources of energy, before we go any further, we pause to consider exactly what fusion is and is not responsible for."
They go on to discuss how much energy is released per cubic metre in the core of the Sun by nuclear fusion and this turns out to be about 300 Watts.
They go on to say:-
"Think about this number: 300 Wm-3. Imagine putting three 100 W lightbulbs in a broom cupboard whose volume is about 1 cubic metre. Would that make the cupboard as bright and hot as the Sun?"
"No, clearly it would not. In fact, 300 W seems like a pathetically tiny power output for a volume as large as 1m3, especially in something as hot as the core of the Sun! Is the calculation grossly wrong? No, the power output per cubic metre is that small. Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse! (But it is a big reservoir!)"
After some further number crunching the books says:
"You might be tempted at this stage to think that, even though the power released in fusion is very small, the energy released heats up the core of a star, and this is why stars are hot. The energy released is indeed very important, but it is not the reason that stars heat up. In fact the opposite is true; fusion prevents a star from getting hotter!"
"In fact, a star's temperature and luminosity are not determined by nuclear burning. However, they are maintained by nuclear burning. Nuclear fusion replenishes the slow leakage of energy from the star's core and eventually from its surface. As you saw in the last Section, the release of gravitational potential energy can do exactly the same thing, but the nuclear fusion energy source has the advantage that it lasts for much longer. That is, nuclear fusion greatly delays the gravitational collapse of the star."
"If someone had asked you at the beginning of this book, 'What makes stars hot?', you could have been forgiven for answering 'It is because they have thermonuclear reaction in their cores.' That answer sounds plausible, but hopefully now you can see that it is incorrect. Stars are hot because they have collapsed from large diffuse clouds and gravitational potential energy has been converted to kinetic energy. That is why stars are hot."
I think that the above discussion and conclusion are very misleading. You could come away with the idea that nuclear fusion in the Sun is not an important source of its energy output ("Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse") but that release of energy from gravitational potential energy is ("the release of gravitational potential energy can do exactly the same thing"). This is of course, incorrect.
The question that needs to be asked is this. Would the Sun be hot now after having existed for approximately 4.6 billion years if nuclear reactions weren't taking place in its core? The answer to this is no. If there was no other energy source in the Sun apart from the release of gravitational potential energy, then at its current luminosity it would only shine for approximately 18 million years , a time-scale that is about 256 times too short. It follows then that the Sun would have cooled to well below its current temperature by now if heating by contraction was its only source of energy. We know, anyway, that the Sun is in equilibrium, which means that it is neither contracting nor expanding. You can't have energy released by gravitational potential if the Sun isn't contracting.
The argument about the three 100 Watt light bulbs in a cupboard is also misleading ("Would that make the cupboard as bright and hot as the Sun? No clearly, it would not!"). The cupboard could get as bright as the surface of the Sun and even as high as the core of the Sun, if the cupboard was perfectly insulated. This is how an ideal oven would work. In fact, I find the langauge used by the authors ("300 W seems like a pathetically tiny power output for a volume as large as 1m3") emotive and inappropriate for a science text.
So is nuclear fusion in the Sun much of a powerhouse? Yes, it is. Although of 300 Watts per metre cubed sounds like a small number it is sufficient to power the output of the Sun for billions of years and maintain the temperature in its core for the duration.
So why is the Sun hot? I would argue it is hot for both of the reasons discussed, neither of which can be disentagled or discounted. The collapse of the gas cloud that led to the formation of the Sun was responsible for getting the core of the Sun up to a temperature where nuclear fusion could take place and nuclear fusion is responsible for maintaining that temperature of the Sun, in both the core and on its surface, until now. To overemphasise the role of gravitational energy in the way that these authors have done in their book is, in my opinion, very misleading and it is disappointing if this is also true of the course notes for the OU Astrophysics course.
Tuesday 29 January 2013
Map of relatively prime pairs
Here is something which I thought was impressive. Imagine dividing a plane into two halves with the vector (1,0) labelling the left half and the vector (0,1) labelling the right. Imagine then creating a downward split in this line, a bifurcation, such that the new region created below the point of the split is labelled with the vector that is the sum of (1,0) and (0,1) namely (1,1). Now create two new bifurcations on these lines with the labels for the newly created regions being the sum of the vectors for the regions either side of the line leading to the point of the split. So, we end up with two new regions labelled with the vectors (1,0)+(1,1)=(2,1) and (1,1)+(0,1)=(1,2). Now repeat this process again ad infinitum creating 4, then 8, then 16...regions. This is the map of relatively prime pairs.
The top of this map can be seen on the front of Stillwell's book. It has some interesting properties. Firstly, each region of the map (except (1,0) and (0,1)) is labelled by a relatively prime (or coprime) pair of natural numbers. This means that for such a region (a,b), a and b have no common divisor apart from 1 (that is gcd(a,b)=1). Now what is even more amazing is that every possible pair of relatively prime natural numbers (a,b) appears as a label once, and only once, in this diagram. What is more, starting from the top of the diagram you can follow a unique path down the tree to a particular pair (a,b) of your choosing.
I think if someone asked me if it was possible to come up with some orderly way of finding every possible pair of coprime natural numbers I would have said that it was impossible and yet here is a way. What's more, it is a fairly structured diagram. If natural number pair (k,l) is anywhere to the left of natural number pair (m,n) then (k/l)>(m/n), so the ratio of the pairings decreases from left to right. In fact, if we consider the fraction a/b for any natural number pair (a,b) then this diagram contains all possible reduced fractions (i.e. fractions where a and b have no common divisor) and the fractions decrease in size from left to right.
What a cool thing!
The top of this map can be seen on the front of Stillwell's book. It has some interesting properties. Firstly, each region of the map (except (1,0) and (0,1)) is labelled by a relatively prime (or coprime) pair of natural numbers. This means that for such a region (a,b), a and b have no common divisor apart from 1 (that is gcd(a,b)=1). Now what is even more amazing is that every possible pair of relatively prime natural numbers (a,b) appears as a label once, and only once, in this diagram. What is more, starting from the top of the diagram you can follow a unique path down the tree to a particular pair (a,b) of your choosing.
I think if someone asked me if it was possible to come up with some orderly way of finding every possible pair of coprime natural numbers I would have said that it was impossible and yet here is a way. What's more, it is a fairly structured diagram. If natural number pair (k,l) is anywhere to the left of natural number pair (m,n) then (k/l)>(m/n), so the ratio of the pairings decreases from left to right. In fact, if we consider the fraction a/b for any natural number pair (a,b) then this diagram contains all possible reduced fractions (i.e. fractions where a and b have no common divisor) and the fractions decrease in size from left to right.
What a cool thing!
Subscribe to:
Posts (Atom)