Archive for the ‘polymath5’ Category

EDP9 — a change of focus

February 24, 2010

The discussion in the last thread has noticeably moved on to new topics. In particular, multiplicative functions have been much less in the spotlight. Some progress has been made on the question of whether the Fourier transform of a sequence of bounded discrepancy must be very large somewhere, though the question is far from answered, and it is not even clear that the answer is yes. (One might suggest that the answer is trivially yes if EDP is true, but that is to misunderstand the question. An advantage of this question is that there could in theory be a positive answer not just for \pm 1-valued functions but also for [-1,1]-valued functions with L_2 norm at least c>0, say.)

Another question that has been investigated, mostly by Sune, is the question about what happens if one takes another structure (consisting of “pseudointegers”) for which EDP makes sense. The motivation for this is either to find a more general statement that seems to be true or to find a more general statement that seems to be false. In the first case, one would see that certain features of \mathbb{N} were not crucial to the problem, which would decrease the size of the “proof space” in which one was searching (since now one would try to find proofs that did not use these incidental features of \mathbb{N}). In the second case, one would see that certain features of \mathbb{N} were crucial to the problem (since without them the answer would be negative), which would again decrease the size of the proof space. Perhaps the least satisfactory outcome of these investigations would be an example of a system that was very similar to \mathbb{N} where it was possible to prove EDP. For example, perhaps one could find a system of real numbers X that was closed under multiplication and had a counting function very similar to that of \mathbb{N}, but that was very far from closed under addition. That might mean that there were no troublesome additive examples, and one might even be able to prove a more general result (that applied, e.g., to [-1,1]-valued functions). This would be interesting, but the proof, if it worked, would be succeeding by getting rid of the difficulties rather than dealing with them. However, even this would have some bearing on EDP itself, I think, as it would be a strong indication that it was indeed necessary to prove EDP by showing that counterexamples had to have certain properties (such as additive periodicity) and then pressing on from there to a contradiction. (more…)


EDP8 — what next?

February 19, 2010

It’s taken noticeably longer than usual for the number of comments on the previous EDP post to reach 100, so this is perhaps a good moment to think strategically about what we should do. Individual researchers continually have a choice — whether to take a break from the problem and work on other, possibly more fruitful, projects or to tackle that blank page head on and push towards a new level of understanding — and I see no difference with a Polymath project.

I would be interested in the views of others, but my own feeling is that there is still plenty to think about here. There has been a certain amount of talk about Fourier analysis, and that still feels like an insufficiently explored avenue. A good preliminary question, it seems to me, is this. Suppose that {}f is a quasirandom \pm 1-valued function defined on \{1,2,\dots,N\} for some large N, in the sense that all its Fourier coefficients are small. Must there be some HAP along which the sum has absolute value at least C? If so, how quasirandom does {}f need to be? What I like about this question is that I think it should be substantially easier than EDP itself. It could be that a simple calculation would solve it: my attempts so far have failed, but not catastrophically enough to rule out the possibility that they could succeed next time. It also seems a pertinent question, because the functions we know of with very low discrepancy have some very high Fourier coefficients. (I don’t really mean Fourier coefficients, so much as real numbers \alpha such that \sum_{n=1}^n e(\alpha n) has very large absolute value.) Therefore, proving that low discrepancy implies a high Fourier coefficient would be a result in the direction of proving that these examples are essentially the only ones, which would solve the problem. (more…)

EDP7 — emergency post

February 8, 2010

I don’t feel particularly ready for a post at this point, but the previous one has got to 100 comments, so this is one of the quick summaries again — but this one is even shorter than usual.

We are still doing an experimental investigation of multiplicative functions, trying to understand how special they have to be if they have low discrepancy. Ian Martin has produced some beautiful plots of the graphs of partial sums of multiplicative functions generated by various greedy algorithms. See this comment and the ensuing discussion.

Terence Tao has some thoughts about how one might try to reduce to the character-like case.

I came up with a proof strategy that I thought looked promising until I realized that it made predictions that are false for character-like functions such as \lambda_3 and \mu_3. Even if the idea doesn’t solve the problem, I think it may be good for something, so I have written a wiki page about it. Gil has had thoughts of a somewhat similar, but not identical, kind. Here is a related comment of Gil’s, and here are some more amazing plots of Ian’s. (I think we should set up a page on the wiki devoted to these plots and the ideas that led to them.) Regardless of what happens with EDP itself, I think we have some fascinating problems to think about, which can be summed up as, “What is going on with these plots?”

EDP6 — what are the chances of success?

February 5, 2010

I thought it might be good to have a post where I tried to take stock and assess the chances that Polymath5 will actually result in a solution to the Erdős discrepancy problem. But before I talk about that, I want to make the point, which I have made before, that solving the problem one sets out to solve is not a necessary condition for the attempt to count as worthwhile. There is easily enough material on the blog now for it to be possible to base a publishable paper on it, even if quite a lot of that paper ends up being a combination of a survey about the problem and a report on the interesting phenomena that have become apparent as a result of computations, some of which we understand reasonably well and some of which are still rather mysterious.

I am not saying this in order to hint that I think that it might be time to give up. At the moment it feels to me as though we still have momentum, so my enthusiasm is not flagging. What is mathematical momentum? I might define it as follows: an assault on an open problem has momentum if one’s understanding of the problem is continuing to develop. Right now I feel as though with each passing day I understand things about EDP that I did not understand before — and I presume that applies to everyone else too. And for as long as that is the case, one can never quite be sure that the problem won’t suddenly yield. (more…)

EDP5 — another very brief summary

February 2, 2010

I wasn’t expecting to have to write another post quite this soon, so this is another one where I don’t have much to say. Here are a few bits and bobs from the last lot of comments, but there’s plenty more in the comments themselves, and actually I think that it’s not that hard to browse through them now that we have depth-1 threading and quite a lot of the comments are very short.

Johan de Jong came up with a very interesting variant of the problem, in which \mathbb{N} is replaced by the space of polynomials over \mathbb{F}_2. I confess to being a little sad when the problem was solved negatively soon afterwards, as it had looked as though it might be a rather good model problem. However, the solution was nice.

One of the general aims at the moment is to try to show that a multiplicative function of bounded discrepancy must have some kind of character-like behaviour. Terence Tao has come up with an intriguing argument that shows not that but at least something in the right ball park.

Work has continued on a human proof that completely multiplicative sequences must have discrepancy greater than 2. It looks as though the proof will be complete before too long, and not too painful. Some nice tricks of Jason Dyer have come in helpful in reducing the amount of case analysis that is needed.

EDP4 — focusing on multiplicative functions

January 30, 2010

Just as I thought that Polymath5 was perhaps beginning to lose momentum, it has received a sudden boost, in the form of this comment of Terry’s, which has potentially completed one of the hoped-for steps of the proof strategy, by establishing that if there is a counterexample to EDP, then there is a “moral counterexample” that is completely multiplicative.

There are a few points that need clarifying here (which I am just repeating from Terry’s comment). The first is that the multiplicative counterexample is over the complex numbers: that is, it is a sequence with values in \mathbb{T}. The second is that instead of having bounded partial sums (and hence bounded discrepancy), it has mean-square partial sums with bounded lim inf. That is, there exists a constant C such that N^{-1}\sum_{n=1}^N|f(1)+\dots+f(n)|^2\leq C infinitely often. Turning this round, in order to prove EDP it is sufficient to prove that for every completely multiplicative function f:\mathbb{N}\rightarrow\mathbb{T} we have the inequality N^{-1}\sum_{n=1}^N|f(1)+\dots+f(n)|^2\geq\omega(N) for some function \omega that tends to infinity. (more…)

EDP3 — a very brief report on where we are

January 26, 2010

Right at the moment I’d say that Polymath5 has quietened down a little bit but is nevertheless continuing to make progress. There is quite a lot I could write about, but I thought it made more sense to put it on the wiki, so here I shall just briefly draw attention to some recent additions to the wiki (not just by me).

On the experimental side, I am losing track of how new everything is, but a list of the main data can be found at the start of the experimental page on the wiki.

On the theoretical side, Terence Tao has put proofs of some nice facts. One is a very clean proof of Mathias’s result that if the HAP sums of a sequence never go below -1 then they must be unbounded above. The cleanness of the argument comes partly from working with the positive rationals rather than the positive integers and partly from making use of results from topological dynamics. In particular, the latter allows one to talk about a “random rational number x” and give a sensible meaning to quantities such as the probability that f(x)=f(2x).

Terry has also proved, by a fairly intricate combinatorial argument, that there must exist a HAP such that the difference between the maximum and minimum partial sums along that HAP is at least 3. (In the terminology we have been using, the drift is at least 3.)

I have created some pages about general proof strategies. These are linked to from a section of the main Polymath5 page. One is a proof strategy that I have already discussed in some detail in recent posts: showing that a counterexample must have multiplicative structure, tidying up that multiplicative structure as much as possible, and eventually showing that there cannot be any examples with multiplicative structure. A newer idea is to define a different parameter, a bit like drift but measured on a number of different distance scales and averaged. More details about this idea and the motivation for it can be found here.

Incidentally, it is easy to find out what the most recent changes to the wiki have been: on the left of each page is an internal link called Recent Changes.

EDP2 — a few lessons from EDP1

January 21, 2010

I plan to continue my policy of writing a new Polymath5 post every time the number of comments on the current one threatens to go into three figures. Since I won’t always have a substantial post’s worth to say, I shall simply write whatever I do feel like saying and have time for. I can’t guarantee that it will always be a full and accurate summary of the discussion so far.

In this post I want to highlight a couple of ways in which my view of the broad proof strategy explained in the previous post has changed. Let me begin with the multiplicative case of the problem (item 1 of the proof strategy). My proposal for this was to attempt to find clusters of odd-smooth (there is now a suggestion that these should be called odd-friable) numbers, and argue that the constraints that these put on small primes cannot all be satisfied simultaneously. I would like to explain now why I do not think it likely that an argument along these lines can be developed. (more…)

EDP1 — the official start of Polymath5

January 19, 2010

After several hundred comments (including everything, we’re at 688 at the time of writing) about the Erdős discrepancy problem, it may seem odd to be talking about the project starting. However, the focus of the discussion so far has been on experimental results, and I have deliberately restrained myself from saying too much about the theoretical side of the problem — that is, proposing approaches, trying to prove partial results, etc. — and I think others have too. So from now on any theoretical comments are welcome. I have been trying to delay this moment as long as possible in order to have a chance of doing various other things I have to do, but I have a relatively free couple of weeks coming up, the experimental evidence is starting to lead to the possibility of making some precise conjectures, and Terence Tao recently came in with a theoretical comment: this conjunction of circumstances fatally weakens the argument for holding out any further.

I had planned, in this first theoretical post, to concentrate on approaches that don’t work. The idea behind this was that the more you can rule out, the more your moves are forced and the more likely you are to find whatever correct argument might remain. However, I am less inclined to do this now because the body of experimental evidence does the proof-constraining very effectively without it. As I have already commented, the fact that there is a sequence of length 1124 and discrepancy 2 probably rules out a simple inductive argument for a lower bound of the form c\log n (for the discrepancy of a sequence of length n). And the fact that this example has so much structure strongly suggests that we should attempt to prove that an infinite bounded-discrepancy sequence must have structure of this kind. (A key property seems to be quasi-multiplicativity. We basically know what a quasi-multiplicative sequence is, though we have not yet settled on a formal definition.) (more…)

The Erdős discrepancy problem V

January 16, 2010

To a casual observer it may look as though the frequency of comments to Polymath5 is dauntingly fast — much faster than it was for Polymath1, say. However, I think appearances are misleading, because many of the comments are very short, and on the whole they are easy to understand because they are not too theoretical. I’ll give the usual roundup later in this post, but I thought I’d begin with a few remarks about the polymath process itself, because I think that Polymath5 has already demonstrated a few things that were not clear, or at least were less clear, before.

The most obvious, given the way the discussion has been going so far, is that the process is ideal for problems where there is the potential for an interplay between theory and experiment. When looking at DHJ, we looked at both theory and experiment, but the two were fairly disjoint. This was due to the nature of the problem: it is not computationally feasible to gather data about DHJ except in very low dimensions, and it is therefore difficult to draw any general conclusions from the results. But for the Erdős discrepancy problem the situation is quite different, and we have learned a huge amount from looking at long sequences that have been generated experimentally. (The main three things we have learned are that they can be surprisingly long, that if they are surprisingly long then they probably have to have some multiplicative structure, and that they have this structure in a approximate sense rather than an exact one.) (more…)