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.