First Year Presentation

Tomorrow I give my first year presentation, which determines whether I’m allowed to continue my studies. At 20-30 minutes, it’s a rather condensed version of my recent geometry club talk on the point counting problem, although this time I’m skipping more quickly through the fundamentals so that I can discuss some of the algorithms in depth, and taking a (hopefully) clearer route.

Both the report itself and the OHP slides version are available (pdf). Content covered: hyperelliptic curves, points, divisors, mumford polynomials and the Picard group/Jacobian; the discrete logarithm problem; explicit group law computation; characteristic polynomial of Frobenius and Weil theorems/interval; group-theoretic approaches; Schoof’s algorithm, SEA in genus 1, genus 2 hybrid algorithms.

On logic

As part of my postgraduate life here in Edinburgh, I’m expected to tutor a couple of dozen first (of four) year undergraduate Mathematics students. Thus I was involved in the marking of their group theory exam last Friday. As the questions were being assigned to markers, there seemed to be a reluctance to take the logic question, probably because students manage to tie themselves in hard-to-follow knots with this material. However, I spent some of my previous year at Bath tutoring on set theory and logic to Physicists, so was prepared for the worst, and I’d also spotted that the question was multiple choice, so the actual marking shouldn’t be too taxing, so I took responsibility for that one.

Still, 207 scripts later I was somewhat worried by the general standard. There were quite a few attempts which received full marks, but many more received zero, including elsewhere high-scoring candidates. Whilst the emphasis of a group theory exam should be group theory, the pressure of an exam and lack of access to notes will always dampen performance, and I probably received a few scripts that were pure guesswork, that’s still a disappointment. Whilst it pains me to say it, a student could become competent at first year undergraduate mathematics just by learning how to ‘turn the handle’ of appropriate bits of mathematical machinery, and as this is pretty much all that they do at school, they may find that university-level mathematics isn’t really the subject they thought it was. To make the leap from computation to understanding, it strikes me as vital to gain mastery of basic logical manipulation. Nor should this just be the domain of Mathematicians; if anything, a precise understanding of the structure of an argument (and its falsification) should be even more crucial to the Humanities.

So I’m going to reproduce the question here and then attempt to unravel it in a precise manner but without recourse to the more abstract approaches of formal logic, in the hope that everyone can follow. Here goes:

Consider the statements:

A. All people who can sing in tune are musical.

B. Some people who cannot sing in tune are musical.

C. Some unmusical people can sing in tune.

D. Some unmusical people cannot sing in tune.

E. No unmusical person can sing in tune.

Mark with the number 1 any of the statements B,C,D,E that are logically equivalent to statement A, with 2 any that are (logically equivalent to) the negation of A, with 3 any that are (logically equivalent to) the converse of A, with 4 any that are (logically equivalent to) the negation of the converse of A and with 0 any which are in none of the above categories.

Solution is behind the cut, so if you want to try this yourself without spoilers, now’s the time!

Continue reading ‘On logic’ »

Mathematical tourism

The Quaternions
The plaque marking the discovery of the quarternions, Dublin.

I’ve spent the last three days in Dublin, and whilst there I couldn’t resist taking a rare opportunity for mathematical tourism. Hamilton figured out the structure of the quarternions in “a flash of genius” during a morning walk along Dublin’s royal canal, carving them into the nearby Brougham bridge. Whilst the carving does not survive, there is a plaque at the spot to mark this discovery, and it was that I set off to see.

Getting there doesn’t seem too difficult, though: I got the 120 bus from Parnell Street (conveniently close to my hotel on Parnell Square) to Broombridge road. This is the opposite of advice found elsewhere online, but the suggested 20 route doesn’t seem to exist any more. If you have a map, it’s easy enough to follow the bus route, but as I didn’t I just asked the driver to give me a shout when we got there. Brougham is pronounced broom, so all you need to do is to find where Broombridge road crosses the canal and (it turns out) railway tracks: presumably taking the western suburban line would be an even easier way to get there, as the platform is next to the bridge. Of course, I went the wrong way along Broombridge road, which is easily detected by reaching the end without finding a bridge!

It’s been described as “the least visited tourist attraction in Dublin”, partly because the area isn’t particularly appealing today but presumably because there aren’t that many mathematical tourists!

It does seem a shame that the site – and Hamilton – are so overlooked compared to the attention that, say, local authors or artists get. But it’s better than nothing, as mathematical tourist attractions are few and far between, especially outside of universities. The bridges of Konigsberg are often suggested; I’d also be fascinated to tour Japan in search of sangaku. If you have other ideas, why not mention them in the comments?

The Carnival of Mathematics

Welcome to the sixth edition of the Carnival of Mathematics! I’ve certainly enjoyed looking through this fortnight’s submissions, and hope you will too.

Trivium Pursuit‘s series on when best to introduce formal arithmetic to children continues with this article, setting out their arguments for providing an informal experience of mathematics before the age of ten. I remember plodding through worksheets at that age, where “harder” simply meant “more tedious”, perfoming larger calculations with by-then familiar processes; it’d be interesting to know how my mathematical career would have been shaped by avoiding such drill in favour of the suggested approach. I suspect most mathematicians will also find it a very strange idea, assuming they also took to formal arithmetic at a very young age and thus find it hard to imagine struggling with such material.

Of course, the beauty of mathematics often lies not in getting an answer, but getting there in a clever way. Political Calculations presents criss-cross multiplication; an easier way to multiply two digit numbers in your head; whilst Let’s play math offers some guidelines for K-12 students to help organise their thoughts in problem solving. But over in the universe of discourse, Mark Dominus warns of the danger of over-thinking a problem where brute-force may suffice. This is particularly true when computers are thrown into the mix, as the time taken to devise and program an elegant solution may well exceed the runtime of the naive approach.

At the other extreme, though, there are computations which you wouldn’t survive to see the result of if you took the brute-force option. I’m reminded of this e2 writeup, which describes a particularly daft hello world program along with a curious question: if hardware performance continues to double with Moore’s law, how long should you wait before running such a program? After all, if you estimate a function will take 4 years to execute on your current machine, but one twice as fast will be available in 18 months, then you can save 6 months (and a load of electricity) by waiting a year and a half, obtaining the faster kit, and running your program for just two years. Conversely, if you want to guard against brute-force attacks for a given length of time, just how good does your encryption have to be?

Also on e2 (hey, if I’m hosting, I can plug my favourite site, right?), sam512 has been exploring very, very large numbers, inspired by this edition of xkcd: so far the clarkkkkson, hyper operator and linear array notation have been covered.

Many of this weeks submissions presented problems, of varying difficulty. As a warm-up, Sharp Brains‘ new puzzle master offers a brainteaser entitled ‘Party For Polyglots’. More demanding are two entries from MathNotations, aimed at calculus students: the first concerning properties of the ellipse, the second, more advanced post is on exploring infinite series. We close with the most amibitious material, the Unapolagetic Mathematician‘s examination of the knot colouring problem: for the background, see here; this week’s submission explains what’s going on. I feel that I had an unfair advantage since my flatmate is a knot-theorist; I’m often intrigued by the techniques applied to this field. Plus I rarely get to draw pictures during my own research!

Thanks to all who submitted content, and to those of you reading this! The next stop for the carnival is Nonoscience, on the 4th of May.

Formal Analysis of Cryptographic Protocols

(this post merges several previous ones.)

I attended an Informatics postgraduate course, Formal Analysis of Cryptographic Protocols during the second semester of 2006/07. The full notes from lecturer Sibylle Fröschle can be found here, but I also tried to make some more accessible summaries of my own, which subsequently found their way to E2.

I actually wrote a piece on Massey-Omura encryption before the course started, but it’s of a similar theme. The presentation is mostly in lay terms (featuring the usual cast of Alice, Bob, Eve and Mallory posting boxes to each other), but the mathematics of the three-pass system is covered towards the end. Specifically, I outline how factorisation isn’t a suitable technique but (assuming it’s as hard as everyone suspects) the discrete logarithm problem is.

My interest in this course came from a number of modules in formal logic I pursued as an undergraduate, and I’m often fascinated by ideas in this field. There are natural connections between cryptographic protocol analysis and string rewriting, and with enough freedom one can emulate general models of computation such as Turing machines by protocols. One particularly neat side effect of this is that it allows an elegant proof of the undecidability of the secrecy problem: namely, given a protocol and a secret message, is there a decision procedure to establish whether an intruder can learn the secret? By reducing to Post’s Correspondence Problem, it can be shown that the answer is no! Of course, this raises issues of intruder strength and ‘honest’ protocols; here’s the article.

Next up were a few protocols and attacks against them: Authentication sets notation and discusses one-way identity verification such as central locking for cars. The challenge-response protocol and the replay attack are included. Mutual authentication demonstrates the reflection attack on running challenge-response in both directions; three-pass mutual authentication is introduced to resolve this (at the price of some extra complexity).

Finally, I covered the type flaw attack; a particularly devious vulnerability that is invisible to many formal analytic techniques.

Lecture notes- Galois Theory

Galois Theory

To save carrying the original paperwork about, and to give myself a recap on the material, I’ve written up the lecture notes from MA40037:Galois Theory as taught at the University of Bath by Geoff Smith.

The content is broadly as follows: Rings, Integral Domains, Fields of Fractions, Units, Ideals, Homomorphisms, The First Isomorphism Theorem, The Chinese Remainder Theorem, Irreducibles, Field Extensions, Characteristic, Minimal Polynomials and Algebraic Numbers, Galois Theory.

The notes very closely match those I made and hence the lectures given, except the section on the Chinese Remainder Theorem, which was adapted from problem sheets. There have been various minor linguistic tweaks, but few mathematical ones.

It should be noted (to avoid confusion under composition) that the convention of writing function arguments to the left (i.e., (x)f rather than f(x)) is adopted here; and that square brackets are sometimes used for factors in polynomials where these appear in expressions also featuring function or polynomial evaluations (which are denoted by round brackets).

Proof reading would be appreciated!

A second survey of game theory

I’ve now converted the majority of my game theory project to E2nodes, through a dedicated account. The content has been significantly rearranged for some topics, to make better use of E2′s nodal structure; hopefully individual entries stand alone a bit better so that it isn’t necessary to read the entire report to understand what’s going on. I’ll also be adding more content to that account to clarify or expand upon the original document.

NP vs Co-NP

view as PDF

The NP vs co-NP problem is related to the more famous P vs NP question. As part of CM30071:Logic and its applications (University of Bath Computer Science), my group gave a presentation on this topic, and its connections to propostional logic (through the satisfiability and validity problems). The attached file contains a two page summary of the main ideas from the talk.

A survey of game theory

For my final year project (MA40128 at the University of Bath), I studied game theory, and now that I’ve completed it, I’m making the report available here. There’s a choice of [ps] or [pdf] format; I intend to node the whole thing at a later date. The report discusses Von Neumann’s minimax theorem; Nash’s theorem and equilibria; the Prisoner’s dilemma (including recent results on IPD tournaments); and Shapley value.