EDP22 — first guest post by Gil Kalai

The purpose of this post is to ignite some new activity related to polymath5 about Erdős’ Discrepancy Problem. This post is thus a polymath5 research thread and comments (also unrelated to the suggestions in this post) are welcome.

The general form of a discrepancy problem

Let be a hypergraph, i.e., a collection of subsets of a ground set . The discrepancy of , denoted by is the minimum over all functions of the maximum over all of

.

We will mention one additional definition, that of hereditary discrepancy. When is a hypergraph and , the restriction of to is the hypergraph with vertex set whose edges are all sets of the form for edges of . The hereditary discrepancy of is the maximum over all of the discrepancy of restricted to .
Here is a link for a recent post discussing discrepancy and the famous Beck-Fiala theorem. The Beck-Fiala theorem assert that if every element in is included in at most sets in then . (Of course, the theorem applies also to the hereditary discrepancy.)

EDP: a possible revival

A few months ago, Gil Kalai got in touch to suggest that it was time to revisit Polymath5, the attempt to prove the Erdős discrepancy problem. I agreed, but we have both been rather busy in the interim, so it is only now that we are ready. One of the things that Gil did was write three posts, which I shall be putting up as guest posts, the first one today and the others over the next few days. I hope that people who contributed to the project the first time round will consider having another go, and that people who didn’t, but would be interested, will find that they can use the wiki that we created to record our progress to get up to speed with what is already known. Once Gil’s posts are up, I’ll probably write a post myself, and I hope that some serious work might start in early September. I always felt that when the original attempt petered out, it was just a kind of loss of energy that individual mathematicians often feel, rather than the result of hitting a brick wall. And just as having a break from a problem is often useful for individuals, I hope it will turn out to be for this polymath project. If it doesn’t, then maybe I’ll do something I meant to do much earlier, which is write up in paper form the progress that has already been made. (Of course, if I do that, then anybody is free to contribute to the writing.)

If you want to look at some of the earlier posts, they are collected together in the polymath5 category on this blog.

What are dense Sidon subsets of {1,2,…,n} like?

The short answer if you don’t feel like reading a post with some actual mathematics in it is that I don’t know.

Now for the longer answer. A subset of is called a Sidon set if the only solutions of the equation with are the trivial ones with and or and . Since the number of pairs with is and whenever , it is trivial that if is a Sidon set, then , which gives an upper bound for of around .

A trip to Watford Grammar School for Boys

As I said would happen in my post about a possible approach to teaching maths to non-mathematicians aged 16-18, I went last Wednesday to Watford Grammar School for Boys to try the approach out. The headmaster there, Martin Post, was remarkably helpful and assembled a usefully varied group of pupils, some from his school, some from the equivalent school for girls, and some from a nearby mixed comprehensive school (I wasn’t told which one) whose pupils receive some of their teaching in scientific subjects from Watford Grammar School. What’s more, some of the people there were doing maths and further maths, some were doing just maths, and some were not doing either. The one thing that was not representative about the group was that they were much brighter than average: for example, the non-mathematicians there had been chosen by their teachers as clever people who could have done maths but decided that they were more interested in other things. For most of the rest of this post, I’ll say what questions I discussed and how the discussions went. All but two of them were taken from the list in the earlier post.

A new open-access venture from Cambridge University Press

The formal launch has just taken place at the European Congress of Mathematicians in Krakow of the Forum of Mathematics, which to a first approximation is a new open-access electronic journal. However, the singular “journal” is misleading, because in some ways it is more like a whole set of journals. But there will be considerable interdependence between the elements of the set, so “journals” is misleading too. We need an intermediate number between singular and plural. Also, although the journal(s) is/are primarily electronic, there will be a print-on-demand option if anyone wants it.

What is the Forum of Mathematics?

Terminological questions aside, how will this new journal-like object work? I think the easiest way of explaining it is to describe the process for submitting an article, which is similar to the process for submitting an article to a conventional maths journal, but with one or two unusual aspects.

How should mathematics be taught to non-mathematicians?

Michael Gove, the UK’s Secretary of State for Education, has expressed a wish to see almost all school pupils studying mathematics in one form or another up to the age of 18. An obvious question follows. At the moment, there are large numbers of people who give up mathematics after GCSE (the exam that is usually taken at the age of 16) with great relief and go through the rest of their lives saying, without any obvious regret, how bad they were at it. What should such people study if mathematics becomes virtually compulsory for two more years?

A couple of years ago there was an attempt to create a new mathematics A-level called Use of Mathematics. I criticized it heavily in a blog post, and stand by those criticisms, though interestingly it isn’t so much the syllabus that bothers me as the awful exam questions. One might think that a course called Use of Mathematics would teach you how to come up with mathematical models for real-life situations, but these questions did the opposite, and still do. They describe a real-life situation, then tell you that it “may be modelled” by some formula, and proceed to ask you questions that are purely mathematical, and extremely easy compared with A-level maths.

EPSRC update update

This brief post is to update further a recent post that was itself an update on the situation with EPSRC. The good news is that EPSRC postdoctoral fellowships in mathematics are now available for “intradisciplinary research” (as was already the case with the early career and established career fellowships). I am told that a certain amount of work went on behind the scenes to achieve this: we should be very grateful to the mathematicians involved, and grateful also to EPSRC for being prepared to show a degree of flexibility in this instance. I am also told, though only time will tell how true this is, that the interpretation of the word “intradisciplinary” will be generous, so unless your research is extremely narrow, you should be able to present it in a way that will qualify.

A look at a few Tripos questions X

Since time is short, I am going to discuss a couple of Groups questions but in slightly less detail than I have been giving up to now: instead of working through the questions completely, I’ll try to zero in on the most important points. Because there wasn’t a separate Groups course until 2008, I am taking my questions from that year.

5E. For a normal subgroup of a group , explain carefully how to make the set of (left) cosets of into a group.

For a subgroup of a group , show that the following are equivalent:

(i) is a normal subgroup of ;

(ii) there exist a group and a homomorphism such that is the kernel of .

Let be a finite group that has a proper subgroup of index (in other words, ). Show that if , then cannot be simple. [Hint: Let act on the set of left cosets of by left multiplication.]

A look at a few Tripos questions IX

Exam day approaches, so I’ve decided to prioritize. Instead of doing question 7C, which isn’t all that interesting (in the sense that it doesn’t give me much scope to emphasize principles of more general use in exams), I’m going to skip it, and instead, if I get time, go through a groups question or two. But first I will do the final Numbers and Sets question because it involves something a lot of people dislike: the inclusion-exclusion principle. It’s worth getting comfortable with this, because it comes up year after year (either in Numbers and Sets or in Probability). You may think that applying the principle requires some ingenuity. The aim of this post is to convince you that it can be done on autopilot.

8C. Let be a finite set with elements. How many functions are there from to ? How many relations are there on ?

Show that the number of relations on such that, for each , there exists at least one with , is .

Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations for which, in addition, for each , there exists at least one with , is

.

A look at a few Tripos questions VIII

Now for a question on modular arithmetic. As with countability, there is a very high chance of a question on this topic. [Added after the post was written: as usual I wrote down my thoughts about this question as I had them, and I didn't spot the best approach to part (ii) of the question until after I had come up with some less good approaches. So my recommendations evolve through the post, with some of the later ones superseding some of the earlier ones.]

6C. (i) Prove Wilson’s theorem: if is prime then (mod ).

Deduce that if (mod 4) then

(mod ).

(ii) Suppose that is a prime of the form . Show that if (mod ) then (mod ).

(iii) Deduce that if is an odd prime, then the congruence

(mod )

has exactly two solutions (modulo ) if (mod 4), and none otherwise.