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.)
When I first suggested the Erdős discrepancy problem as a possible Polymath project, one thing that worried me about it was that, unlike with the density Hales-Jewett theorem (for ) I did not have a suggestion for how one might go about solving it. However, that has changed, thanks to this experimental work. I now have a suggestion for a broad approach, and slightly more detailed suggestions for how one might go about proving the various steps. I haven’t forgotten that my initial suggestions for DHJ3 were eventually abandoned, and that could happen again here. But it is still somehow helpful to have the initial suggestions.
My view of the problem before the 1124 structure emerged was something like this. There was a natural special case of the problem, where you assume that your sequence is completely multiplicative, and not only was this probably already very hard, but it probably wouldn’t help all that much with the general problem. Now I feel a little bit more optimistic about the problem for multiplicative functions (after a small amount of thought about how to produce good ones, and why one might fail) and a lot more optimistic about their relevance to the general problem, at least if one generalizes to quasimultiplicative sequences. So I would suggest the following broad approach to the Erdős discrepancy problem.
1. Prove that completely multiplicative sequences cannot have bounded discrepancy.
2. Prove that every infinite sequence of bounded discrepancy can be “cleaned up” so that it becomes quasimultiplicative, in some yet to be determined, but pretty strong, sense.
3. Generalize 1 to quasimultiplicative sequences.
Let me now say a little bit more about 1-3 in an effort to explain why I don’t feel that carrying out those steps is necessarily hopeless.
A few thoughts about 1.
The best way to understand why I feel optimistic (but only moderately so, as I think there could be some serious difficulties with what I am about to propose) about 1 is to do a little exercise that I did a few days ago, namely generate by hand a completely multiplicative sequence of length 246, all of whose partial sums lie between -2 and 2. It turns out not to be that hard, provided that you are prepared to look ahead at all the consequences of your choices so far (up to 246 — the significance of which is that Alec and his computer have proved that that is as far as you can get). Once you have done that, you start to see that awkward constraints can arise if you have a longish interval with many numbers in it that I’ll call odd-smooth, until someone proposes a better, or more standard, name. By this I mean the product of a perfect square with a product of distinct small primes. Equivalently, I mean a number such that every prime that occurs an odd number of times in the prime factorization is small. The relevance of this is that if is your completely multiplicative function and you want to be 1 (respectively -1), and if are the primes that occur an odd number of times in the prime factorization of , then an even (respectively odd) number of the values must be -1. Thus, each for which you want to be -1 imposes a constraint on the values of the that can be thought of as a linear constraint over . The hope is that if you have too many of these constraints applying to too few primes , then you won’t be able to satisfy them all simultaneously.
The situation isn’t quite as simple as that, because you are rarely forced to take a particular value for . However, if you have several odd-smooth numbers in close succession, then you do at least have many constraints on the values they can take, and there seems to be at least some hope of demonstrating that they cannot all hold simultaneously.
This line of thought suggests a further division of 1 into two subproblems.
1a. Can we say anything about the distribution of odd-smooth numbers? How dense is the set of numbers such that the primes that occur an odd number of times in the prime factorization of are all at most ? (Obviously they will get sparser as you go on. A typical number around will have around prime factors, so most of these will be large, and typically a large prime factor will occur only once.) And can one show that the distribution is somewhat irregular, so that there are intervals that are particularly rich in odd-smooth numbers? (Because the odd-smooth numbers thin out, such an interval would have to be not too far out.) Can one at least argue heuristically that this ought to be the case?
This is the part of the proof strategy that I feel least confident about. It could be that these questions are known to be very hard. But I’m crossing my fingers and hoping for the best: are there any number theorists out there who can help? Would sieves be useful perhaps? If nobody comes forward then I’ll ask on mathoverflow whether anything is known about odd-smooth numbers.
1b. Can some kind of -linear algebra argument be developed that proves that the discrepancy of an infinite multiplicative sequence is unbounded, subject to reasonable assumptions about the distribution of odd-smooth numbers (and their factorizations)?
I admit that 1a looks pretty hard and 1b doesn’t obviously work. But I hope it’s at least a start.
A few thoughts about 2.
I feel much more hopeful that something can be done here, and I think that if we managed to show that the Erdős discrepancy problem was equivalent to the Erdős discrepancy problem for a highly structured class of sequences, then we could be pretty satisfied.
Very roughly, the programme would be this. Over at mathoverflow I asked a question about how much a sequence of 1s and -1s could be tidied up if you are allowed to take pointwise limits of sequences of translates. To see the relevance to us, consider the operation that we have talked about quite a bit. This is the map that takes a sequence to the sequence . If we look at the iterates of , then it is natural to partition the natural numbers into geometric progressions of common ratio 2, one for each odd number, since on each such GP behaves like a shift. The reason this is of some interest is that if has discrepancy C, then so does , and hence so does for every . Furthermore, every pointwise limit of sequences of discrepancy has discrepancy at most .
Let us call a property of sequences stable if it is closed under translates and pointwise limits. An example of a stable property is that of never having three 1s in a row. An example of an unstable property is that of having density 1 (meaning that the density of such that is 1). The reason that the latter is unstable is that one could have arbitrarily long blocks of -1s but far enough out that the density of the sequence was 1, and then one would be able to find a pointwise limit of translates that was zero everywhere. Periodicity and almost periodicity (by which I mean the type of behaviour you see in sequences such as ) are stable properties, and highly relevant to us. Let us call a property inevitable if for every sequence there is a pointwise limit of translates that has the property. Of particular interest are properties that are both stable and inevitable.
Let be a stable and inevitable property. If we keep applying to a sequence , we can ignore everything except the subsequence and pass to a new sequence where this subsequence has property . We can then repeat the exercise for the subsequence , and the stability means that we will not lose the property on the first GP. Continuing in this way, we can in fact get all GPs to have any stable and inevitable properties we like. So it seemed to make sense to find out what such properties were. There have been several helpful answers to this question on mathoverflow.
Unfortunately, but not at all surprisingly, for a general sequence the kind of properties we can get are far too weak to be useful for showing that our original sequence can be converted into one with multiplicative structure. (We can get quasiperiodicity, but the kind of thing we are looking for is much much stronger than that.) However, our sequences are very far from general: they are subsequences along geometric progressions of a sequence of bounded discrepancy. This raises all sorts of possibilities. For example, if we can prove that some rather weak property must hold, then perhaps we can pass to some limit and greatly strengthen the property. (An example of this, though not a very interesting one, is that if we have a sequence of density 1 we can turn it into the all-1s sequence.)
I have made a list of weak properties that bounded-discrepancy sequences ought to have, and for some of them I think there ought to be a good chance of proving that they really do have the properties. Rather than repeating the list here, I refer you to the interesting subquestions section on the first page of the Polymath5 wiki.
To summarize what I’ve been saying here, I think that, given that the discrepancy can be very low indeed for very long sequences, the best chance of proving the conjecture may well be to use infinitary methods. I hope that we may be able to prove some weakish facts about hypothetical counterexamples to the conjecture that suggest some kind of weak multiplicative structure, and then to argue that in the limit there is a much nicer multiplicative structure — some kind of quasimultiplicativity of the kind we have been observing.
Non-thoughts about 3.
I don’t have much to say about this: we should probably walk before we try to fly.
The other direction.
Of course, I don’t think we should abandon the attempt to find longer and longer sequences of low discrepancy: it has been extremely fruitful already, but the patterns we have found have a tantalizing way of breaking up when the numbers get large. At the moment it feels as though we won’t understand the breaking up properly unless we can get our hands on more data. And it’s probably a bit dangerous to assume that the conjecture is true, or at least it should be healthier to attempt to disprove it as well as attempting to prove it. There are many loose ends arising from the discussion so far, and there are likely to be many more. (See the wish-list section on the experimental results page of the wiki for a sample of these — others are scattered in the comments.) Even if the conjecture is true, it would still be interesting to have an efficient algorithm that could generate better sequences than we know how to describe theoretically. (It feels as though we are closing in on the 1124 sequence, or rather sequences, but it also feels as though the description of those would involve some slightly arbitrary elements that would not generalize straightforwardly to infinity.)
At one point I raised the question of whether it would be good to have separate threads for the theoretical and experimental aspects of this project. At the moment I don’t plan to do this: the two seem too closely intertwined, and the experience with DHJ was that having two parallel threads didn’t really work unless they were fairly disjoint. (That applied both to the material being discussed and, to a lesser extent, to the participants.) So what I hope will happen is that the experimental part of the project will continue apace, but that anyone who might have been holding back on discussing the theory will no longer do so — just as I, by posting this, have no longer done so.