EDP4 — focusing on multiplicative functions

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 . 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 such that infinitely often. Turning this round, in order to prove EDP it is sufficient to prove that for every completely multiplicative function we have the inequality for some function that tends to infinity.

EDP3 — a very brief report on where we are

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 ” and give a sensible meaning to quantities such as the probability that .

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

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.

EDP1 — the official start of Polymath5

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 (for the discrepancy of a sequence of length ). 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.)

The Erdős discrepancy problem V

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.)

The Erdős discrepancy problem IV

Again, this is just a brief report on what is going on. Plenty of work is still being put into making sure that the main results, questions, ideas, etc. are appearing on the Polymath5 wiki and especially (for the moment) the experimental results page, so looking at that is still a good way to keep up.

Alec came up with a sequence of length 1112 that is fairly different from the sequences of length 1124. See this comment and succeeding ones for information about it. I am particularly intrigued by the diagram showing partial sums of pointwise products of different HAP-subsequences. There is data here that demands to be explained, but the focus of the discussion is elsewhere for now.

Kevin has suggested thinking about how the number of sequences of length n compares with the number of sequences of length m, where by “sequences” I mean sequences with relevant properties such as having discrepancy 2 and perhaps being multiplicative as well. There is some interesting data here too.

The logarithm of the number of multiplicative sequences of discrepancy 2 and length n behaves in a suggestive way. Yet more to chew over.

I myself have started thinking about an algorithm for generating long low-discrepancy multiplicative sequences in the hope of proving that the discrepancy of such sequences can grow more slowly than logarithmically.

Gil has suggested looking at randomized modifications of the problem with a view to obtaining insights about the problem itself.

Alec has looked at the behaviour of Dirichlet series built out of some of the good examples we have.

Finally, I am hoping for good news from Klas in the not too distant future.

The Erdős discrepancy problem III

I’m having to write posts at a ridiculous rate now, but until the official launch (at which point I expect a significant theoretical component to add to the experimental one — one decision we should make is whether to have separate theoretical and experimental threads or whether it is better to have a unified discussion) I’ll keep them short and mainly aimed at summarizing what is going on for the benefit of people who want to keep up with the discussion without reading hundreds of comments.

Most of the comments in the last post have concerned sequences with low discrepancy and additional constraints. If we define the map to be the one that takes the sequence to the sequence , then it is notable that the long sequences that we have found satisfy, not quite all the time but certainly most of the time, constraints such as or more generally . This suggests searching for sequences that satisfy these constraints exactly. One reason for doing so is that there are many fewer such sequences, so searching for low-discrepancy examples should be much quicker, and we have some reason to expect them to exist. And indeed, although we have not matched the length 1124, we have got sequences of length well over 500 that satisfy additional constraints.

The best way to keep up with what has been done is probably to check out the experimental results page on the Polymath5 wiki. And the wiki itself is still growing fairly quickly, so if you read through that then you will have a digest of most of what has been discussed in the comments.

A phenomenon that has recently been observed is that sometimes pairs of HAP-subsequences of good sequences do not agree all that well to start with, but after a while “lock in” to each other. We have not yet properly thought about this, but it seems pretty interesting.

Erdős discrepancy problem, continued

This is another post for the sake of not having too many comments on any single post. I actually wrote a completely different one yesterday, but it contained some theoretical thoughts that are probably better held back until the project starts in earnest. So I’m going to make this post very short indeed.

A quick report on what’s going on right at the moment. We have just been fed some more data: several more sequences of length 1124 and discrepancy 2, some sequences that have HAP-sums bounded between numbers like -1 and 3 instead of -2 and 2, and some nice two-dimensional examples. The Polymath5 wiki has some details about these and other aspects of the problem.

If anyone feels like doing an experiment that I’d be interested to know the result of, they could investigate the following sequence. I want to know whether it is good for anything. It’s the simplest example I can think of of a sequence that appears to exhibit multiplicative behaviour but keeps breaking the pattern. Let be the completely multiplicative function that takes every prime to , where . Then define to be 1 or -1 according to whether the imaginary part of is positive or negative. (Of course, .) At what kind of rate does the discrepancy of this sequence seem to grow?

Another experimental question: are all the HAP subsequences of the new 1124 examples significantly different from all the HAP subsequences of the old one? In other words, is it reasonable to say that they are completely different examples, or are they more like modifications of HAP subsequences of the original one?

Erdős’s discrepancy problem as a forthcoming Polymath project

This is an emergency post, since the number of comments on the previous post about Erdős’s discrepancy problem has become unwieldy while I’ve been away enjoying a bit of sunshine in Luxor. My head is full of amazing details from the walls and columns of ancient Egyptian tombs and temples. The main thing I didn’t see, or at least not until I finally saw them sticking up through the mist from my plane window yesterday morning, was the pyramids, since those are near Cairo. However, I didn’t feel too bad about that as my guide book, the Lonely Planet guide to Egypt, assured me that the pyramids never fail to disappoint (which was just one of many little gems of bad writing in that book).

For the first time for ages, I was completely away from all email and internet for a week, but just before I left, the results of the polls, as they then stood, about the next Polymath project were already suggesting that the Erdős discrepancy problem was the clear favourite, so I couldn’t help thinking about it a certain amount while I was in Egypt. I said that the process of choosing the next problem was not going to be fully democratic, but the fact is that I love the Erdős discrepancy problem and am currently somewhat grabbed by it, so I see no reason to go against such a clear majority, especially as it also has a clear majority of people who say that they are ready to work on it.