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.
The first reason is a remark of Sune’s. He points out that if such a proof exists, then we should see how it applies to the Walters-type examples (where is 1 if the last non-zero digit of base 3 is a 1 and -1 otherwise). These examples have so much alternation of signs that they demonstrate that you can have an infinite multiplicative sequence such that any subsequence of drift at least needs to be exponentially long in . Thus, it seems pretty hard to find “clusters” of a kind that would be helpful.
I find that an important argument, but a small part of me thinks there might conceivably be a way round it. However, that lingering hope is crushed by a second argument, which is derived from my experiences of building long low-discrepancy multiplicative sequences by hand.
To explain this second argument, I’d like to distinguish more explicitly between two kinds of constraint that a multiplicative sequence of low discrepancy must satisfy. At the risk of stating the embarrassingly obvious, it must be multiplicative, and it must have low discrepancy. Why did I bother to say that? Well, let’s suppose that, as happens when one tries to build up a sequence, we are given the values on a certain set of integers. The way my by-hand algorithm works, I then try to write down all other values that I can deduce from these ones by directly using either the multiplicativity condition or the low-discrepancy condition. By “directly”, I mean that I do not allow arguments of the following kind: if you set then you are forced by the following chain of implications to get five 1s in a row over here; therefore, . I would count that as an indirect implication.
So what are the direct implications? I can describe these by explaining how I would program a computer to work them out. I would start by calculating everything that follows from multiplicity. That is, if I have three numbers such that and I know the values at two of them, then I can deduce the value at the third. (In practice, the values I know have most often been those at and , but deducing from and is more interesting when you get the chance.)
There are of course infinitely many values that follow from multiplicity, so before I start I fix a large and only go up to that .
Once I have made all the multiplicity deductions I can, I then make discrepancy deductions. One useful one is the following lemma: if the discrepancy is at most 2 and , then the partial sum up to is 0. (The proof is that it must be even and for obvious reasons it can’t be either 2 or -2.) From this it follows, for example, that if , then . More generally, if you can work out what the partial sum up to a certain point must be, and if that point belongs to an interval of values that have been decided, then you can work out the partial sums everywhere in that interval — and it is often possible to do that even if you don’t know all the values before that interval.
So the second stage of my procedure is to make all discrepancy deductions of that kind. They then allow me to make more multiplicativity deductions, which in turn allow further discrepancy deductions, and so on.
The point I want to make is this: in practice, I found myself doing several alternations between multiplicative and discrepancy deductions before I had deduced everything I could. I might add that when I ran out of deductions, I would typically find that making a choice for just one more prime would unleash a surprisingly long chain of implications before I next ran out.
What has this to do with the proposal in my previous post? Well, the clusters argument in that proposal seems to be suggesting that for every assignment of values to all the primes up to some , there will be a cluster of -odd-friable numbers somewhere such that the values you have chosen will force a drift that is too large (at least , say). But the actual experience of searching for long multiplicative sequences of low discrepancy doesn’t feel like this: the contradiction is reached not after one step, when all you’ve done is explore the consequences of multiplicativity, but after several, when you’ve alternated quite a bit between using multiplicativity and using the low discrepancy. So it now seems to me that what I was asking for before was too strong.
There is a trivial sense in which it wasn’t too strong, which is that the numbers up to are themselves a cluster of -odd-friable numbers. But that is reducing the problem to itself, which does not count as a serious proof strategy.
So I now think that the right approach is to try to examine the following question: if you are given a certain set of values that a multiplicative sequence of discrepancy at most must take, how many other values do you expect to be able to deduce? Ultimately, one is hoping to be able to make two contradictory deductions: if is the set of all primes up to , can we make some kind of guess about how large needs to be in order to force us to make two contradictory deductions (whatever values we choose at those primes)?
That second question suggests another. Up to now, we have looked for the longest multiplicative sequence of discrepancy at most 2, and Alec has shown that the best possible bound is 246. However, in choosing such a sequence, we probably commit ourselves to a contradiction much earlier. So a more fundamental question (from the point of view of finding a proof that the partial sums of a multiplicative function must be unbounded) is this. What is the largest prime such that one can choose values for all primes up to , follow through all the implications of multiplicativity and discrepancy at most 2, and not reach a contradiction? This is still a computational question and I think it should be easy to program and quick to run.
At this point I’d briefly like to highlight an interesting post of Guy Srinivasan. He was interested in the question of when one would expect contradictory constraints to arise in the general problem, and devised a probabilistic model for it. (An example of contradictory constraints for him would be something like that and , making it impossible to choose without violating the discrepancy-2 condition.) His model appears to agree remarkably well with the actually observed data, so perhaps it can give us some real insights into what is going on. It would be nice if we could use such a model to guess what the right lower bound should be for the discrepancy of a sequence of length . (Even without a formal proof, it is good to have as precise an idea as possible of what we think ought to be true.) It would be good to try to develop heuristic arguments for the multiplicative case as well. Is there some probabilistic model that would allow us to predict how broad and long the chain of implications described above should be, given the set where the values have already been assigned?
Now let me move on to step 2 of the proposed proof strategy. Here I think I can claim that there has been some progress, though of a rather modest kind. In this comment and the subsequent one, I proposed an argument for showing that if there is a counterexample to EDP then there is a counterexample such that for every the sequence has a well-defined density. Terence Tao confirmed that this does indeed almost certainly follow from well-known dynamical-systems techniques. I haven’t thought about it yet, but I feel fairly confident that one should be able to get the same result simultaneously for all geometric progressions and not just those with common ratio 2. (It seems as though all it would need is a relatively standard generalization to several commuting operators — maybe Terry can confirm this too.)
Why does it help to have well-defined densities along GPs? Well, I don’t know for sure that it does. But I am hoping we could use averaging arguments of the kind introduced in this comment, to produce from a hypothetical counterexample a much nicer example, obtained from averaging along GPs. That brings me to my next point: a discussion of step 3 in my previous post.
Here I think we have something surprisingly simple: I said we should walk before we fly, but in fact it seems to be easy to prove that if you can walk then you can fly. That is, it seems to be easy to prove that if there is a quasimultiplicative example, then there is a multiplicative one. (So although the very long and mostly quasimultiplicative examples that have been generated experimentally are very interesting, they now appear to be a red herring from a theoretical point of view.) The argument is in the comment referred to in the previous paragraph.
I would also like to mention an entirely different proof strategy, which is to modify the problem by shifting the HAPs in order to destroy structured examples, so that all you have to do is analyse much more random-looking ones. A few experiments need to be done before we will know whether this is a promising idea — it seems that we will learn a lot from them whatever they turn out to yield. More details about the modified problem can be found in this comment. [Added slightly later: in the responses to the comment, Sune makes an observation that rather pours cold water on this idea. But the experiment may still be interesting.]
A quick thing to report on the numerical side: if you follow the responses to this comment, you will see that Alec has come up with a completely multiplicative sequence of length 1530, and you can get some idea of how he did it. This sequence holds the current record for the longest sequence yet to have been generated that is of significance to the project. The sequence itself is displayed here.
Finally, I would like to draw attention to a problem I like that ought to be easier than the EDP itself. I also think that if we can solve it then we will have a lemma that could be extremely useful when it comes to “cleaning up” hypothetical counterexamples. Rather than repeat myself, I refer you to this comment and the one after it (and the responses to them). Roughly speaking, a positive solution to this problem would show that there were “few” counterexamples to EDP, which would then tend to show that the operators had to have some kind of stronger compactness property than the trivial one (since after you iterate a few times, you’d have to get a sequence that was substantially more similar to your original sequence than the pigeonhole principle would guarantee). This, coupled with limiting arguments, could enable siginificantly greater tidying up to be done of the original sequence.