M337 Complex Analysis

For some time since 2018 my maths studies had fallen by the wayside and I was beginning to miss that regular challenge of learning something new. About this time last year I decided to pick up The Open University's M337 Complex Analysis course again and I have been plodding along with it very slowly. I started from the beginning again because I thought I would have forgotten what I had already learnt.

So, at the moment I am nearly at the end of book A3 on continuity and, if anyone wonders, this is not the advised rate of reading for study of this course at the OU (it should take a year to finish the whole course). Not that I am worried. This is just an interesting slow ramble for me and sometimes I don't pick it up again for weeks at a time. There has been nothing so far that has completely flumoxed me and it all seems relatively familiar having previously studied the OU's M208 (Pure Mathematics). I do like to work consistently through all the problems and exercises and this is probably why I tend to go so slowly - these are the best bits!

At the moment I am on chapter 5 of A3 and have enjoyed this diversion into sets and the Extreme Value Theorem and I am sure it will play its part in later books. I have just been working on Problem 5.5 and part (b) had me tying myself up in knots as I was trying to find an estimate for the upper bound of |sin z| for the set {z : |z| <= 27} without using the Triangle Inequality. This wasn't intentional - I just had forgotten to apply this theorem. In the end I won out but it was messy. I think by the time I had finished I had a 'better' (i.e. lower value) estimate than the triangle inequality gave. My estimate was that |sin z| <= (1/2)(e^54 + 3)^(1/2). The OU solution using the triangle inequality was |sin z| <= e^(27).

This reminded me that there was a similar remark about 'best possible' constraints at the end of the chapter on inequalities in book A1. It said that the inequality |z^2 - 4z - 3| <= 15 for |z| = 2 is not the 'best possible'. It said with more work it is possible to prove that the best possible inequality is |z^2 - 4z - 3| <= 7(7/3)^(1/2). This, of course, set me off trying to work this out for myself and after a couple of pages of working out I agreed. Here is the result written out in my fair hand:-

Update

I haven't posted anything here for nearly two years - where does the time go! Since that time I have continued on with my study of number theory and getting through chapters 9 and 10 of John Stillwell's Elements of Number Theory on Quadratic Reciprocity and Rings. I was making very slow progress I must say. I started chapter 11 on Ideals but before I had got very far I felt like a change and last September began reading the books in the OU's M337 Complex Analysis course. So far I have only worked through book A1 and am halfway through A2. Slow progress indeed! I just do enough to keep the old brain ticking over.

Book A1 of M337 introduces complex numbers and goes over some familiar stuff that we have seen in MS221 and M208 (e.g. nth roots of a complex number). Book A2 is a bit more interesting as it starts to deal with complex functions where the domain and image are sets of complex numbers. Here, nothing is very obvious as we are mapping from a 2d plane to a 2d plane and it is not easy to see what a function is doing. One thing that struck me, that I hadn't really thought about before, is that the complex plane is not an ordered field like the set of real numbers. For example, you can't write an inequality like 1+2i > 1+i. So any ordering can only be done with functions that map to a real line (such as the modulus).

I also liked the approach to determining the image of a complex function. For example, Problem 1.2(b) asks you to determine the image of the function f with rule f(z) = (3z+1)/(z+i). Now there is a convention which states that if a function is specified by just its rule then it is understood that its domain is the set of all complex numbers to which the rule is applicable and its codomain is C (the set of all complex numbers). So here the domain A = C - {-i} (i.e. the whole of the complex plane except the point -i) because when z = -i the denominator in the rule is zero. So the image of f is

$$ f(A) =  \{ w = \frac{3z+1}{z+i} : z \in A \}$$

The aim is to write this set in terms of the image point w and a condition on w. Since

$$  w = \frac{3z+1}{z+i} \Leftrightarrow w(z+i)=3z+1 \Leftrightarrow  z(w-3)=1-wi \Leftrightarrow z = \frac{1-wi}{w-3}$$

the the image of f is

$$ f(A) =  \{ w : z = \frac{1-wi}{w-3} \neq -i \}$$

Now we can imagine the image point w moving around the complex plane and at the same time see the point z in the domain from which it is mapped. We want both w to exist and z not to be equal to -i. You can see that z is never equal to -i for any w in C. Also, (1-wi)/(w-3) is just another complex number and so, as w ranges over all of C, so does z. The only point that is excluded in the image is when w=3 as again this would make the denominator in z zero. Thus we have that

$$ f(A) =  \{ w : w \neq 3 \} $$

and so the image of f is C - {3}. Neat!

Proof that there are infinitely many quaternion primes

Sometimes proofs can be annoyingly difficult. I have been reading about quaternions in Elements of Number Theory and Exercise 8.4.2 asks you to prove that there are infinitely many quaternion primes without assuming that every natural number is the sum of four squares. I have been racking my brains over this one for a few days and finally I came up with a proof that I think works today.

What we know is that a quaternion "prime" is defined to have a norm which is prime in Z otherwise the norm will end up being the product of two quaternions of smaller norm. I was originally thinking that we should adopt the proof of showing that there are infinitely many primes in Z (see page 2 of the book) by assuming a finite number of quternion primes q₁,q₂,...,q_k and then forming a product of their norms and then adding 1. This new natural number is then not divisible by any of the norms norm (q₁), norm (q₂), ..., norm(q_k). But this hits snags straight away because you don't know if this new number is prime in Z and you don't know if it even relates to a quaternion.

After much thought, here is my proof.

Let us suppose to the contrary that there are only a finite number of quaternion primes q₁,q₂,...,q_k (where k is some natural number). Now the norm of each of these quaternion primes must be a prime in Z, so norm (q₁)=p₁, norm (q₂)=p₂, ... ,norm(q_k)=p_k where p₁,p₂,...,p_k are primes in Z.

Now there are an infinite number of primes in Z of the form 4n+1 (see page 113) and so we can always choose a prime p of this form which is not one of p₁,p₂,...,p_k. Further by the two-square theorem (see page 109) p=a²+b² for some a, b in Z. Now this is the norm of quaternion q where q=a1+bi+0j+0k since det (q)=a²+b² but q is not one of q₁,q₂,...,q_k since norm (q) is not any one of norm (q₁), norm (q₂), ..., norm (q_k). Further q must be a quaternion prime since norm (q) is prime in Z. Therefore we have reached a contradiction. It follows that there must be infinitely many quaternion primes.

RSA Factoring Challenge (part 7)

In my previous post I considered an example of trying to find the two primes in the product 9980651 by satisfying equations (1) to (4) in part 3. So just how many possible solutions would we come up with if we went about this in a systematic way? As we saw there were 3 possible solutions in solving equation (1), and 10 each for equations (2), (3) and (4). This means that we would have at most 3x10x10x10=3000 potential solutions to search through until we found the pair of primes (2029,4919) that we were looking for.

How does this compare with, say, trial division? We know that the product consists of two primes each of which contain four decimal digits. Therefore a simple approach would be to divide 9980651 by all the integers between 1000 and 9999, a total of 9000 numbers. An alternative approach would be to divide by all the primes between 1000 and 9999, a total of 1061 such numbers. This is fewer than the 3000 pairs of solutions we would come up with but then you would have to calculate what these primes were in advance.

If we consider the products of primes which are 100 digits or more, then we can see that the challenge is enormous. For example, for RSA-220 there would be 3x10¹⁰⁹ pairs of numbers to search through. Even if processing one pair corresponded to one instruction on a computer, then a computer operating at 10¹⁰ instructions per second could take 10⁹² years to find the right pair! So, unless this method can somehow be improved then it is not going to be a viable method for this challenge. In fact, it illustrates just how difficult it is to crack these products of large primes.

Reading the same book for 3 years

I have been reading Elements of Number Theory by John Stillwell for the last three years and I have only just started Chapter 8 (out of 12). It was a birthday present and so I would say it has been good value for money! Not that I have been reading it consistently. Sometimes I don't seem to have time to read much for several months and then I will pick it up again and have a burst of working and reading. The way I like to work through a text like this is to read and understand all the proofs and to work religiously through the exercises. Sometimes the proofs require a bit of extra work on paper to be able to understand them. Other times, by thinking about each sentence, I can understand a proof without the need to write anything down.

It may seem a bit bizarre to work through all of the exercises in the order in which they are presented but I find that if you complete one it gives you the confidence to tackle the next one. It also helps with the understanding of the text and, if there weren't exercises, all those proofs would seem a bit dry. So far I have done them all apart from those in section 3.8 until the end of chapter 3. I stopped working on this chapter when I gave up my OU studies as I felt I needed to start afresh on a new chapter. I have covered 56 pages of A4 with my workings! It would be nice to publish them all here but I don't think the publishers of the book, or the universities that use it, would be very happy about this.

I have finished chapter 7 on quadratic integers. This culminated in a proof of Fermat's last theorem for n=3 which I was pleased as punch to understand, especially when it says that this is "probably the most difficult result in this book...". It looks horrible when you just read through it quickly and nothing seems to make sense. You just have to take one sentence at a time and it may be that to understand a small point you have to go away and work at it until the penny drops. This was certainly the case for understanding the congruence classes mod √-3 in Z[ζ₃] in figure 7.3. I had to go back to basics to get to grip with this but it was key to some of the pre-stage proofs.

The next chapter in the book is about the four square theorem; that every natural number is the sum of four squares. For this we are introduced to Quaternions and Hurwitz integers. It all looks very intriguing.

Anyway, for all those of you who will be medling with some maths this Christmas instead of the usual crosswords or suduko, have a great time. Happy Christmas!

RSA Factoring Challenge (part 6)

I want to consider an example to show how we can attempt to find a solution to the eight simultaneous equations (1) to (8). I will start with an example where we know the two four digit primes p and q and then attempt to recover p and q from their product n using equations (1) to (8).

Let p be 2029 and q be 4919 then their product n is 9980651. If we didn't know what p and q were then following our analysis in part (1) then (X₀,Y₀) are either (1,1), (3,7) or (9,9). Let's suppose we try the middle pair first. Plugging (X₀,Y₀)=(3,7) back into equation (1) we find that C₁=2. Equation (2) then becomes equivalent to

$$7X_{1}+3Y_{1} \equiv 3\;\mbox{(mod 10)}$$

From what we discussed in part 5 our possible solutions for (X₁,Y₁) are (3i,7(3-i)) modulo 10 (where i runs from 0 to 9) and these are the pairs (0,1), (3,4), (6,7), (9,0), (2,3), (5,6), (8,9), (1,2), (4,5) and (7,8).

Let's take the pair (X₁,Y₁)=(2,3). Substituting the values (X₀,Y₀)=(3,7), (X₁,Y₁)=(2,3) and C₁=2 into equation (2) we find that C₂=2. Equation (3) then becomes equivalent to

$$7X_{2}+3Y_{2} \equiv 8\;\mbox{(mod 10)}$$

and our possible solutions for (X₂,Y₂) are (3i,7(8-i)) modulo 10 and these are the pairs (0,6), (3,9), (6,2), (9,5), (2,8), (5,1), (8,4), (1,7), (4,0) and (7,3).

Let's take the pair (X₂,Y₂)=(2,8). Substituting the values (X₀,Y₀)=(3,7), (X₁,Y₁)=(2,3),  (X₂,Y₂)=(2,8) and C₂=2 into equation (3) we find that C₃=4. Equation (4) then becomes equivalent to

$$7X_{3}+3Y_{3} \equiv 4\;\mbox{(mod 10)}$$

and our possible solutions for (X₃,Y₃) are (3i,7(4-i)) modulo 10 and these are the pairs (0,8), (3,1), (6,4), (9,7), (2,0), (5,3), (8,6), (1,9), (4,2) and (7,5).

So what are these solutions for p and q? They are the following ten pairs of numbers; (223,8837), (3223,1837), (6223,4837), (9223,7837), (2223,837), (5223,3837), (8223,6837), (1223,9837), (4223,2837) and (7223,5837). Rather than showing that these numbers fail to satisfy equations (5) to (8) we can just multiply them together and compare them to n which is 9 980 651. We find that 223x8837=1 970 651, 3223x1837=5 920 651, 6223x4837=30 100 651, 9223x7837=72 280 651, 2223x837=1 860 651, 5223x3837=20 040 651, 8223x6837=56 220 651, 1223x9837=12 030 651, 4223x2837=11 980 651 and 7223x5837=42 160 651.

As expected none of them equal n. What it does demonstrate is that the method works, since each of the ten products ends in the number 0651, the same as the last four digits of n. This is to be expected as this was what was demanded by satisfying equations (1) to (4).

RSA Factoring Challenge (part 5)

I want to consider the solutions of equation (11) specifically for the values of a and b that we are likely to encounter. From the discussion in that blog entry we can see that in each of the equations (2) to (4) coefficient a takes the values of Y₀ and coefficient b takes the values of X₀. This means that in these cases a and b are elements of {1,3,7,9} and all the numbers in this set are coprime to 10.

Now suppose the RHS of equation (11) takes the value 5 then there are ten ways in which this number may be obtained on the LHS of the equation. We can have, modulo 10, 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 6+9, 7+8, 8+7 and 9+6. So if the RHS takes the value c then the 10 possibilities for the LHS are i+(c-i) where i runs through 0 to 9. Note that if c-i<0 then c-i is congruent to 10+c-i modulo 10.

So in essence our solutions for x and y boil down to two equations:-

$$ax \equiv i \;\mbox{(mod 10)}...(14)$$

and

$$by \equiv c-i \;\mbox{(mod 10)}...(15)$$

where i runs through 0 to 9. As a and b are coprime to 10, then a and b have an inverse a^-1 and b^-1 such that

$$aa^{-1} \equiv 1 \;\mbox{(mod 10)}...(16)$$

and

$$bb^{-1} \equiv 1 \;\mbox{(mod 10)}...(17)$$

Hence our solutions for x and y are

$$x \equiv a^{-1}i \;\mbox{(mod 10)}...(18)$$

and

$$y \equiv b^{-1}(c-i) \;\mbox{(mod 10)}...(19)$$

Previously, in equation (12) we considered the situation where a was 7, b was 3 and c was 4. Now the inverse of 7 modulo 10 is 3 (and vice versa since 3x7=21 which is congruent to 1 modulo 10) and so the 10 pairs of solutions are (3i,7(4-i)) modulo 10 where i runs from 0 to 9. This is congruent to (3i,8-7i) modulo 10. So we obtain the pairs (0,8), (3,1), (6,4), (9,7), (2,0), (5,3), (8,6), (1,9), (4,2) and (7,5) as before.

RSA Factoring Challenge (part 4)

Looking back at my previous post, is it possible to solve these eight simultaneous equations given that a number n is the product of two prime numbers p and q each of four digits long? The first thing to notice is that equation (1) is equivalent to

$$X_{0}Y_{0} \equiv Z_{0} \;\mbox{(mod 10)}...(9)$$

which is as I discussed in part 1. So for a given Z₀ there are either two or three solutions for the pair (X₀,Y₀) (I shall ignore the fact that we can swap the values for X₀ and Y₀, as this just reflects the commutative property of the product, that is n=pq=qp).

So, it seems that we could make progress as follows. We take one of the pairs of solutions (X₀,Y₀) and we plug it back into equation (1) to find C₁, the multiple of 10 to be carried over into equation (2). That second equation then becomes equivalent to

$$X_{1}Y_{0}+X_{0}Y_{1} \equiv Z_{1}-C_{1}\;\mbox{(mod 10)}...(10)$$

and this equation is of the form

$$ax+by \equiv c\;\mbox{(mod 10)}...(11)$$

where a,b,c,x and y are elements of {0,1,2,...9} and a, b and c are known and x and y are not. Actually, as we saw in part 1 a and b in this case (being X₀ and Y₀) are not zero. This equation may or may not have solutions and I will consider this in future blogs. However, consider the case when (X₀,Y₀) is (3,7) (so Z₀ is 1 and C₁ is 2) and suppose Z₁ is 6 then we have the equation

$$7x+3y \equiv 4\;\mbox{(mod 10)}...(12)$$

By considering all 100 possibilities for x and y we find that there are exactly 10 possible solutions for the pair (x,y) and these are (0,8), (1,9), (2,0), (3,1), (4,2), (5,3), (6,4), (7,5), (8,6) and (9,7). Note that any one solution (x,y) can be obtained from another solution by adding multiples of (1,1) modulo 10.

So it follows that for our one choice of (X₀,Y₀) we can end up with 10 possibilities for (X₁,Y₁). Now we can again choose one of these solutions for (X₁,Y₁), substitute it into equation (2) and using our original values for (X₀,Y₀) and C₁ arrive at a value for C₂.

We can use these values in equation (3) which can be written as

$$X_{2}Y_{0}+X_{0}Y_{2} \equiv Z_{2}-X_{1}Y_{1}-C_{2}\;\mbox{(mod 10)}...(13)$$

and this is again of the form of equation (11). Not only that but the coefficients of x and y (a and b) are the same as before since a is Y₀ and b is X₀. This means that if we have already calculated a table of the hundred possibilities of ax+by modulo 10 then we can just pick out the solutions.

It is no surprise that we can continue in a similar vein until we reach equation (4). By then we have a set of possible solutions for (X₀,Y₀), (X₁,Y₁), (X₂,Y₂) and (X₃,Y₃), that is for the four digits of both p and q. However, only one of those solutions will satisfy the four remaining equations (5) to (8).

RSA Factoring Challenge (part 3)

Suppose you had two prime numbers p and q, both m digits long, and these were, respectively, X_m-1X_m-2...X₁X₀ and Y_m-1Y_m-2...Y₁Y₀ (where the subscripted X and Y's represent the decimal digits of p and q) then the product of p and q can be written as the product of

$$(X_{m-1} \times 10^{m-1} + X_{m-2} \times 10^{m-2} + ... + X_{1} \times 10 + X_{0}) \times (Y_{m-1} \times 10^{m-1} + Y_{m-2} \times 10^{m-2} + ... + Y_{1} \times 10 + Y_{0})$$

Ignoring the powers of 10 for the moment, the terms in the above can be written as a matrix of products of digits in p and q. For example for m=4, we get

$$\begin{pmatrix} X_{0}Y_{0} & X_{0}Y_{1} & X_{0}Y_{2} & X_{0}Y_{3} \\
                               X_{1}Y_{0} & X_{1}Y_{1} & X_{1}Y_{2} & X_{1}Y_{3} \\
                               X_{2}Y_{0} & X_{2}Y_{1} & X_{2}Y_{2} & X_{2}Y_{3} \\
                               X_{3}Y_{0} & X_{3}Y_{1} & X_{3}Y_{2} & X_{3}Y_{3}
\end{pmatrix}$$

Suppose that the result of the product was n then, as we have seen in my previous post, we can say that n is either 2m or 2m-1 digits long and we can write n as Z_2m-1Z_2m-2Z_2m-3...Z₁Z₀ (where the subscripted Z's represent the decimal digits of n). This means that Z_2m-1 may be zero. We can now relate the products of the digits in p and q to the digits in n by noticing that the terms along any diagonal line in the above matrix parallel to the one that passes through X₃Y₀ and X₀Y₃ have a multiple of 10 which is the same for each term. Since Z_i (i running from 0 to 2m-1) involves the sum of these terms modulo 10 we can write a set of simultaneous equations, which for m=4 are:-

$$X_{0}Y_{0}-10C_{1}=Z_{0}...(1)$$
$$X_{1}Y_{0}+X_{0}Y_{1}+C_{1}-10C_{2}=Z_{1}...(2)$$
$$X_{2}Y_{0}+X_{1}Y_{1}+X_{0}Y_{2}+C_{2}-10C_{3}=Z_{2}...(3)$$
$$X_{3}Y_{0}+X_{2}Y_{1}+X_{1}Y_{2}+X_{0}Y_{3}+C_{3}-10C_{4}=Z_{3}...(4)$$
$$X_{3}Y_{1}+X_{2}Y_{2}+X_{1}Y_{3}+C_{4}-10C_{5}=Z_{4}...(5)$$
$$X_{3}Y_{2}+X_{2}Y_{3}+C_{5}-10C_{6}=Z_{5}...(6)$$
$$X_{3}Y_{3}+C_{6}-10C_{7}=Z_{6}...(7)$$
$$C_{7}=Z_{7}...(8)$$

Note that we have to include a carry term C_i for each equation so that we can accommodate the multiples of 10 accumulated in the previous equation. We also know that Z₇ may be zero in which case so might be C₇ (via equation 8).

RSA Factoring Challenge (part 2)

In my previous blog I asked the question "If you knew that a number was the product of two primes of the same length (in decimal digits) could you use the knowledge of the product to determine what the factors were?" In what follows I will assume that for a number n we want to find the m-digit primes p and q such that n=pq.

So a question that you could ask is how many digits does n have if p and q have m digits? Primes p or q can't exceed 10^m-1 as 10^m is an m+1 digit number and

$$(10^{m}-1)^{2}=10^{2m}-2 \times 10^{m}+1$$

For m>1 this is the number 999...800...1 which is 2m digits long. The m+1 digit from the right is an 8 and all the digits to the left of the 8 are 9's (there are m-1 of them) and all the digits to the right are 0's except the last which is a 1.

Primes p and q cannot be less than 10^m-1 as one less than this is an m-1 digit number and

$$(10^{m-1})^{2}=10^{2m-2}$$

which is a 2m-1 digit number. It follows then that if p and q have m digits, then n will have between 2m-1 and 2m digits. It also follows that if n has k digits, then p and q will have k/2 digits if k is even and (k+1)/2 digits if k is odd.

So, if RSA-220 was the product of two prime factors containing the same number of decimal digits, then we would be looking for primes that are 110 digits long.

RSA Factoring Challenge (part 1)

In a diversion away from my continuing study of number theory, I have been thinking about the difficulty of factoring large integers. My attention was caught by the RSA Factoring Challenge which was set up by the RSA Laboratories to "learn about the actual difficulty of factoring large numbers of the type used in RSA keys." I have described RSA encryption in my other concurrent blog and the keys are used in the modulus of the encryption and decryption. The RSA challenge was terminated in 2007 and the monetary prizes that were offered were withdrawn, however, not all of the numbers were factored. So what were these numbers?

Wikipedia has a list of the RSA numbers and reports on the success of people factoring them. These numbers are semiprimes, that is they are a product of two primes (not necessarily distinct). One thing that I noticed as I was looking down the list of factorisations was that in most cases the two primes had the same number of decimal digits and this got me thinking about this specific problem. If you knew that a number was the product of two primes of the same length (in decimal digits) could you use the knowledge of the product to determine what the factors were?

My first thought was that you could probably have a guess at what the last digit of each prime was. If the last digit of the product n=pq was Z and the last digits of the two primes p and q were X and Y, then

$$XY \equiv Z \;\mbox{(mod 10)}$$

This is true because the products of all the other digits involve multiples of 10 and these products are congruent to zero modulo 10 and therefore can't contribute to the remainder here. This result is also true regardless of the number of digits in p and q. Now because prime numbers larger than 5 can only end in 1, 3, 7 or 9, then if Z was 1 then (X,Y) are either (1,1), (3,7) or (9,9) (or vice versa for X and Y). The other pairings for (X,Y) are (1,3) and (7,9) for Z=3, (1,7) and (3,9) for Z=7 and (1,9), (3,3) and (7,7) for Z=9 (or vice versa).

So, for example, for RSA-220 which is the 220 decimal digit number

2260138526203405784941654048610197513508038915719776718321197768109445641817
9666766085931213065825772506315628866769704480700018111497118630021124879281
99487482066070131066586646083327982803560379205391980139946496955261

we can say that the last digits of the two primes that divide it could be (1,1), (3,7) or (9,9).

The division property in integer-like sets

In 'Elements of Number Theory' John Stillwell considers the division property in the integer-like sets of numbers Z[i] (the Gaussian integers, p107) and Z[√-2] (an example of a set of quadratic integers, p119). In the case of the Gaussian integers it is relatively easy to visualize 'multiples' of integers as forming a square grid as in Figure 6.1. However, for the quadratic integers Z[√-2] this doesn't appear to be so easy and you wonder how the grid in Figure 7.1 arises and how Pythagoras' theorem in this case can be applied in the proof.

I will attempt to go through both cases and explain how I see it. Firstly, the Gaussian integers. Suppose μ and β are the Gaussian integers
$$ \mu=m+ni...(1)$$
$$ \beta=r+si...(2)$$

where m, n, r and s are elements of Z and i=√-1. Then
$$\mu\beta=m\beta+n\beta i...(3)$$
Now we have that
$$\beta i=ri+si^{2}=-s+ri...(4)$$
If we think of β and βi as vectors on the complex plane, then β is the vector (r,s) and βi is the vector (-s,r). So, as Stillwell says, i rotates the vector β anticlockwise through 90 degrees. We can see that using the standard dot product of these vectors
$$(r,s)\cdot(-s,r)=r(-s)+sr=0...(5)$$
as expected for mutually orthogonal vectors. We can see therefore that equation (3) is telling us that μβ is the sum of real multiples of β and βi. We can therefore think of this as a square grid with β and βi as base vectors, as anticipated.

Now what about the quadratic integers Z[√-2]? Suppose that this time μ and β are the quadratic integers
$$ \mu=a+b\sqrt{-2}...(6)$$
$$ \beta=c+d\sqrt{-2}...(7)$$
where a, b, c, and d are elements of Z. Then
$$\mu\beta=a\beta+b\beta\sqrt{-2}...(8)$$
What is β√-2? We have
$$\beta\sqrt{-2}=c\sqrt{-2}+d(\sqrt{-2})^{2}=-2d+c\sqrt{-2}...(9)$$
If we again think about μ and β as being vectors, then β is the vector (c,d) and  β√-2 is the vector (-2d,c). In the normal sense it does not look like these two vectors are orthogonal, however, if we define the dot product of two vectors (w,x) and (y,z) to be
$$(w,x)\cdot(y,z)=wy+2xz...(10)$$
then
$$(c,d)\cdot(-2d,c)=-2cd+2dc=0...(11)$$
and so we retrieve the orthogonality of β and β√-2. The definition in equation (10) also fits in with the definition of the norm since
$$norm\beta=(c,d)\cdot(c,d)=c^{2}+2d^{2}...(12)$$
which is as defined by Stillwell (p120). Hence we can again think that equation (8) is telling us that μβ is the sum of real multiples of β and β√-2; i.e. we can think of a grid with β and β√-2 being base vectors, as described in the book (Figure 7.1). Note, however, that this is not a square grid as β and β√-2 are not the same length.

I want to go one step further and show that the proof on page 119 doesn't have to rely on Pythagoras' Theorem. We can see from Figure 7.1 that |ρ| is less than or equal to the length of the vector from the origin to the centre of the figure. That is the vector
$$\frac{\beta}{2}+\frac{\beta\sqrt{-2}}{2}...(13)$$
which is
$$\frac{1}{2}(c,d)+\frac{1}{2}(-2d,c)=\frac{1}{2}(c-2d,d+c)...(14)$$
It follows that
$$\left|\rho\right|^{2}\le\frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)...(15)$$
Expanding the RHS we get
$$ \frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)=\frac{1}{4}((c-2d)^{2}+2(d+c)^{2})=\frac{1}{4}(c^{2}-4cd+4d^{2}+2d^{2}+4cd+2c^{2})...(16)$$
and so
$$ \frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)=\frac{1}{4}(3c^{2}+6d^{2})=\frac{3}{4}(c^{2}+2d^{2})=\frac{3}{4}\left|\beta\right|^{2}...(17)$$
Hence we have
$$\left|\rho\right|^{2}\le\frac{3}{4}\left|\beta\right|^{2}...(18)$$
as obtained in the book.

Geometric characterization of the primes that are sums of two squares

Previously, we saw that Fermat's two square theorem says that all primes of the form 4n+1 are the sum of two integer squares. Using Euclid's integer solutions to the Pythagorean equation z²=x²+y² we obtain the following geometric characterization of the primes that are the sum of two squares (Elements of Number Theory p112):-

"The primes that are the sums of two squares are those that occur as hypotenuses of right-angled triangles with integer sides."

This is a nice result. We can now imagine all of these sorts of primes as being part of right-angled triangles with integer sides and there are infinitely many of them. It is a very satisfactory geometric picture of these types of primes. However, is the triangle with hypotenuse prime p unique? This is the basis of Exercise 6.6.2 (p112):-

"6.6.2. Given a prime p=4n+1, is the integer right-angled triangle with hypotenuse p unique?"

As an example of some of the work that I have done with this book, I thought I would show how I proved this.

We aim for a proof by contradiction. Given a prime p=4n+1 we suppose to the contrary that the integer right-angled triangle with  hypotenuse p is not unique. So there are at least two integer right-angled triangles with hypotenuse p. Let the non-hypotenuse sides of two of these triangles be a₁, b₁, and a₂, b₂.

Firstly, we can show that a₁ and b₁ are coprime. Suppose that they are not then there exists a positive integer c (not equal to 1) that divides a₁ and b₁ such that a₁=cx₁ and b₁=cy₁. Then by Pythagoras for a right-angled triangle:-

$$ a_{1}^{2}+b_{1}^{2}=p^{2} $$
$$ \Rightarrow c^{2}x_{1}^{2}+c^{2}y_{1}^{2}=p^{2}$$
$$ \Rightarrow c^{2}(x_{1}^{2}+y_{1}^{2})=p^{2}$$

Now as c divides the LHS, c must divide p², but the only divisors of p² are 1, p or p². If c was p² this would imply

$$ x_{1}^{2}+y_{1}^{2}=1/p^{2}$$

and x₁ and y₁ would not be integers. If c was p then this would imply

$$ x_{1}^{2}+y_{1}^{2}=1$$

and so either x₁=0 and y₁=1 or x₁=1 and y₁=0 and these are not right-angled triangles. Hence c=1 and we have reached a contradiction. Thus a₁ and b₁ are coprime (as are a₂ and b₂).

Hence, by the theorem for Primitive Pythagorean Triples (top of page 112) we can say that

$$a_{1}=u_{1}^{2}-v_{1}^{2}$$
$$b_{1}=2u_{1}v_{1}$$
$$a_{2}=u_{2}^{2}-v_{2}^{2}$$
$$b_{2}=2u_{1}v_{2}$$

for some integers u₁,v₁,u₂,v₂. It follows that

$$a_{1}^{2}+b_{1}^{2}=(u_{1}^{2}+v_{1}^{2})^{2}=p^{2}$$

and

$$a_{2}^{2}+b_{2}^{2}=(u_{2}^{2}+v_{2}^{2})^{2}=p^{2}$$

However, we know that as p=4n+1 there is only one u, v such that p=u²+v² (top of page 110) and so there is only one u, v such that p²=(u²+v²)². Thus, we have reached a contradiction. Hence the integer right-angled triangle with hypotenuse p must be unique.

Gaussian Integers and Fermat's two square theorem

I was trying to explain to someone recently what I thought mathematics was all about and why it interests me. I found it difficult to put into words some of the ideas and complexities I have seen over the last few years and I had trouble explaining why mathematics is such never-ending treasure chest of ideas. Sometimes you do get the odd glimpse of a fundamental principle and the topic I have just read about Gaussian integers seems to exemplify that.

What is a Gaussian integer? These are a generalization of the ordinary set of integers Z and can be defined as the set of complex numbers

$$ \mathbb{Z} \left[i\right]=\left\{a+bi:a,b\in  \mathbb{Z}\right\}$$

Is it possible to find similarities between this set and the set of ordinary integers and if so what do these common properties tell us about the nature of integers in general? Well it turns out that these two sets do have properties that are in common. For example, it is possible to show that there are Gaussian prime numbers much as there are ordinary prime numbers and you can go on to define properties such as division, greatest common divisor, unique prime factorisation etc which is all very interesting.

So how does this come about? Well, firstly you define the norm of an element of Z[i] to be

$$norm(a+bi)=|a+bi|^{2}=a^{2}+b^{2}$$

and from the properties of the modulus we know that

$$|z_{1}z_{2}|=|z_{1}||z_{2}|$$

and so norms multiply, that is

$$norm\left(z_{1}z_{2}\right)=norm\left(z_{1}\right)norm\left(z_{2}\right)$$

Now because the norm is a real natural number we can define a Gaussian prime to be a Gaussian integer that is not the product of Gaussian integers of smaller norm. For example, 3+2i is a Gaussian prime because norm(3+2i)=13 which is prime in Z and so not the product of Gaussian integers of smaller norm. On the other hand 3+i is not a Gaussian prime because norm(3+i)=10 and since 2 and 5 divide 10 then we might expect 3+i to be factorisable, which it is since 3+i=(1-i)(1+2i) and the norm of 1-i is 2 and that of 1+2i is 5.

When it comes to deciding whether ordinary primes are also Gaussian primes we come to an interesting property. For example, 2 is not a Gaussian prime because 2=(1+i)(1-i) and so can be divided by 1+i or 1-i. On the other hand 3 is a Gaussian prime. This is because norm(3)=9 and there are no Gaussian integers with norm 3 which divide 9 (the smallest non-trivial norms are 2, 5, 8...). Now 2 is the sum of two squares, whilst 3 is not and you can go on to show that ordinary prime p is a Gaussian prime if and only if p is not the sum of two squares (or alternatively ordinary prime p is the sum of two squares if and only if p is not a Gaussian prime).

This leads on to the proof of what I think is a fascinating theorem. Fermat's two square theorem states that if p=4n+1 is prime, then p=a²+b² for some a,b in Z. Since for p>2 every prime is either of the form 4n+1 or 4n+3, then this characterises half the primes as being the sum of two squares. The proof comes from the use of Lagrange's Lemma which states that a prime p=4n+1 divides m²+1 for some integer m (this comes from Wilson's theorem). Since m²+1=(m-i)(m+i) in Z[i] although p divides m²+1 it does not divide m-i or m+i as m/p - i/p and m/p + i/p are not Gaussian integers. By the Gaussian prime divisor property if a Gaussian prime divides the product of Gaussian numbers (m-i)(m+i) then it should divide either m-i or m+i and, as it doesn't, then p can't be a Gaussian prime. As we have seen from above this means that p is the sum of two squares.

Why I find this fascinating is that although prime numbers appear to be a random sequence of numbers we do have this structured form for half the set. It makes me wonder if there is any construction for primes of the form 4n+3? Also, are the a,b that are used to construct the primes of the form 4n+1 drawn from all of Z or are there numbers which are missing? All this gets me thinking!

AWOL

As you can see I haven't posted anything here for six months and some of you may be wondering what has happened. Well, to cut a long story short I abandoned my OU studies in February and, at present, I am not sure if I will be continuing on with them. Though I was reluctant to stop working on these courses, in the end I had to because they were taking up far too much of my time. On reflection it would have been better for me to have started just one of these courses instead of both of them and if I had I would probably have kept going. However, due to the changes that the OU made to the time limits for the degree I was taking and the fact that these courses were going to be discontinued, it wasn't possible for me to do this and so eventually I sort of gave in and didn't have the will power to continue. It is a pity but it isn't the end of the world. I feel it is a shame that the OU made these wholesale changes to their degree structure that left people like myself, who like to take things at a considered pace, high and dry. It's their loss as well as mine.

So what now? I have gone back to reading Elements of Number Theory by John Stillwell and have nearly got half way through the book. I am both reading and understanding the text as well as answering the exercises. It is a well written book and the exercises bring out what is in the text without being overly difficult. I have just finished the chapter on the Pell Equation and I liked the visual approach of Conway which is described. I also went through the previous chapter on the RSA cryptosystem and this enhances what we learnt at the OU. I have written some programs for coding and decoding messages on my other calculator blog.

As for the future I am not really sure what direction I should now take. I suspect I will continue on with the personal study until I get that desire to study more formally again. There are plenty of courses that are appearing online as Chris has been pointing out.

Slogging on

I am still slogging on with the number theory and groups courses. Regularly I ask myself why I am doing this, but then I know that I like having something to focus on that keeps me busy. But sometimes it is just so blooming difficult!

At the moment I am trying to cram in some work on TMA03 of the numbers course. I sort of dread it in advance because these TMAs are really quite difficult. Often the questions don't relate directly to the course material. They use the ideas but in a way that you haven't seen before, so it really makes you think. There is, however, the feeling of huge elation when you do manage to conquer a problem. I take these questions a small chunk at a time. Often I will read the next part of a question and start mulling it over in my head. At first it seems impossible, but after a few glints of ideas, you get an idea of the framework for an answer and then you can flesh the whole thing out. I often go to bed thinking about a knotty problem. It is a good time to give a problem your undevoted attention without distraction, but I can't say it is a good way to get to sleep!

I have now finished NT6 on quadratic reciprocity. One more book and I would have the third block finished for M381. The groups course is going ok. The problem is that the ideas are increasingly complicated and although I tenuously understand a book when I have read it, it rapidly gets forgotten after a few weeks. I have finished GE3 and am currently on GR4 which is investigating finite groups and what we know about them.

Still on track

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!

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!

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.

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.