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.
Since this is asking for something substantially stronger than unbounded partial sums, it makes sense to ask whether this stronger conjecture is true. The answer is that it seems to be about as plausible as EDP itself: that is, the key examples we have seem to behave similarly for both measures of growth. In particular, the mean-square partial sums of the function (the multiplicative function that’s -1 at 3, 1 at numbers that are 1 mod 3 and -1 at numbers that are 2 mod 3) grow logarithmically (so the root mean square grows like the square root of log, with log being the maximum it ever reaches).
Now it seems reasonable to regard this problem as “morally the same” as the problem of proving that a completely multiplicative function has unbounded discrepancy. That is, from a practical point of view, it seems to make sense to focus on the multiplicative case of the original EDP and hope that any proof we manage to come up with will give similar results for complex numbers and mean square averages. In fact, using mean square averages, though it requires us to prove something stronger, is likely to be easier than proving something about the maximum partial sum, since the norm tends to be easier to work with than the norm. (A little example of that is this calculation, which shows that the mean square partial sum of grows logarithmically by taking the sequence of partial sums and splitting it up as an orthogonal sum.)
At the moment, quite a lot of attention is being given to algorithms of the kind I discussed in EDP2. These are algorithms where each time you choose a value at a prime, you follow through all its easy consequences (there are various ways that this notion can be formalized) before looking at the next prime. Some time ago, I used an algorithm like this to find a maximal-length multiplicative sequence of discrepancy 2. The interest now is in whether one can prove by hand that that length (which was 246) is maximal. To read more about this, I recommend looking at a page on the wiki that Sune created, in which he gave a rather clear and concise description of the kind of algorithm we are talking about. And there is also a lengthy discussion of the algorithm following this comment.
I have to admit that from a theoretical point of view, my enthusiasm for this algorithm has dwindled. I had hoped that we would be able to identify regions that were full of odd-smooth numbers, and show that the discrepancy and multiplicativity constraints from those regions were too numerous to be simultaneously satisfiable. If that were the case, then it might be possible to prove it by examining carefully how the algorithm performed, and showing that for each discrepancy it would always terminate with a proof that no infinite multiplicative sequence had discrepancy .
Before embarking on an attempt like this, it is worth thinking about when, in general, analysing an algorithm can be useful for proving a theorem. Here, for example, is a theorem where it does not seem to be useful. One can prove van der Waerden’s theorem for 2 colours and arithmetic progressions of length 3 as follows. At each stage I choose R if I can, and otherwise blue, and if I can’t choose R or blue I backtrack. The proof then goes like this: R, RR, RRB, RRBR, RRBRR, RRBRRB, RRBRRBB, RRBRB, RRBRBB, RRBB, RRBBR, RRBBRR, RRBBRRB, RRBBRRBB, RRBBRB, RRBBRBR, RB, RBR, RBRR, RBRRB, RBRRBR, RBRRBRB, RBRRBB, RBRB, RBRBB, RBRBBR, RBRBBRR, RBRBBRB, RBRBBRBR, RBB, RBBR, RBBRR, RBBRRB, RBBRRBB, RBBRRBBR, RBBRB, RBBRBR, B. At that point I can argue by symmetry: if there is no sequence beginning with R then there cannot be one beginning with B.
Now I actually have a soft spot for this proof, which is simply a depth-first search, and would be quite interested to know more about it. For example, if I run a depth-first search but looking for progressions of length 4, then how will the lengths of the sequences I look at at each stage behave? (The maximum length will be the van der Waerden number W(2,4).) How many sequences will I end up looking at? Can I cut this down a lot by exploiting self-similarities in the tree? (To put that another way, I could build up little lemmas that would tell me that certain subsequences would lead fairly quickly, but not instantly, to contradictions, and I would then not have to keep demonstrating those contradictions over and over again. That would happen every time I backtracked, and the further back the backtracking went, the more powerful the lemma would be.) However, the point I want to make is the negative one that it seems incredibly unlikely that a proof of van der Waerden’s theorem could come out of analysing this algorithm. I don’t know how to justify this assertion convincingly, but what goes on in my head is a thought like this: oh dear, if van der Waerden’s theorem is false, then this algorithm won’t ever terminate, so to prove that it terminates I’m going to need van der Waerden’s theorem. Perhaps another way of putting it is to say that the algorithm merely searches through all possible colourings: it doesn’t have an obvious theoretical advantage over literally writing out all colourings of and checking every single one, as runs through the positive integers, until you reach an such that there is no colouring without a monochromatic progression. (Once, a very long time ago, I hoped that the patterns one sees in the way the sequences expand and contract could be understood in great detail and proved to backtrack right to the beginning, but I soon came to think that the chances that that could be done were minuscule.)
How about an example where analysing an algorithm does help to prove a theorem? One such is a proof of Hall’s theorem. This can be done by describing an algorithm for creating a matching, and proving that the only reason it could have for getting stuck would be if Hall’s condition was violated. Similarly, Bézout’s theorem can be proved by using Euclid’s algorithm to define better and better integer combinations of the original two numbers. Somehow, in both these cases the algorithm is what one might call the algorithmic version of an already existing theoretical proof, whereas this is not the case for brute-force algorithms.
That was not a very successful attempt to distinguish between algorithms that help you prove things and algorithms that don’t. (One other point is that efficient algorithms seem to be more useful for proving theorems than inefficient ones. I’d be interested to know of a counterexample to this — a situation where one can obtain an interesting theorem by proving that a certain inefficient algorithm terminates.) However, in the particular case of searching for long multiplicative sequences of low discrepancy, there is another argument that I find particularly convincing, which I think of as Sune’s test. It can be summarized with the following slogan: your analysis has to apply to the function . And it seems to me that that function shows that the kinds of algorithms we have been looking at will not work unless a significant degree of backtracking is allowed, which is a polite way of saying that it is a brute-force algorithm with a few clever tricks added that do not make it efficient. (I visualize it as follows: the brute-force backtracking algorithm has a tree structure, and brute-force with tricks is a kind of “quotient” of this tree that doesn’t collapse enough for the tree structure to be lost.)
My reason for being so pessimistic is based on what the algorithm would do to the function . I claim that it would not be able to tell that up to cannot be extended to an infinite sequence of discrepancy without lots and lots of backtracking, and that none of the tricks that work so well for small sequences and discrepancy 2 would be of any help. A slightly more detailed argument can be found in this comment.
As a result, I think we are more or less forced to look for theoretical arguments. Here is one possible general proof strategy.
1. Develop a notion of “almost character-like” functions.
2. Prove that a multiplicative sequence that is not almost character-like must have unbounded discrepancy.
3. Prove that a multiplicative sequence that is almost character-like must have unbounded discrepancy.
I would expect 3 to be easy once one had a decent answer to 1. The real challenge is to answer 1 in a way that allows one to prove a good theorem that answers 2.
I have suggested a couple of very preliminary ideas in the direction of 1. I won’t repeat them here. However, I will mention that there is a notion of closeness for multiplicative sequences that has proved itself useful in several contexts. An interesting discussion can be found in this paper of Granville and Soundararajan, starting on page 207. The simplest notion of closeness they mention is this: given multiplicative functions and and a positive integer , we define to be . Note that if and are functions, then for this distance to be finite we need for all primes except in a fairly sparse set.
Granville and Soundararajan have various results that show that multiplicative functions with certain properties (such as partial sums that grow linearly) must be close to characters that very obviously have those properties. Two questions we might think about are these. Suppose we have a multiplicative function that is except on multiples of and 0 at multiples of . Suppose also that its partial sums are bounded. Must it be the Legendre character mod ? (Equivalently, must it be periodic with period ?) And if we make the weaker assumption that the partial sums grow slowly, can we show that the function is close to the Legendre character mod ?
More generally, if is a multiplicative function with partial sums that grow slowly (the meaning of slowly to be chosen in response to the proof), does it follow that is close to a character-like function? (Or as Granville and Soundararajan put it, does it follow that the function pretends to be character-like?)