I’ve been pretty busy over the last month or so — hence my blog silence — and continue to be busy. But here is one more discussion of a problem that was on my earlier list of possible future Polymath projects. The problem in question is sometimes known as Erdős’s discrepancy problem. This will be a shortish post, because I don’t have much of a programme for solving the problem: if it were adopted, then we would be starting almost from scratch, but that could be an interesting experiment.
Here is the question.
Problem. Is it possible to find a -valued sequence and a constant such that for every and every ?
With the help of a little terminology we can ask this question in a slightly different way. If is a collection of subsets of a set and , define the discrepancy of to be the maximum value of over all . In our case, is the collection of all arithmetic progressions of the special form , and the question is whether there is any function that has bounded discrepancy for this . I say “bounded” rather than “finite” because one can define the function to be the discrepancy of with respect to all those sets in that are subsets of . Then the question is equivalent to asking whether there is any function for which is a bounded function of . The advantage of this formulation is that one can consider more precise questions such as what the best growth rate is. In particular, it allows one to prove results in the other direction. Here is one such result, observed by Mark Walters (and very possibly by several other people).
Theorem. Let if the last non-zero digit of is 1 when is written in its ternary representation, and let if the last non-zero digit is a 2. Then the growth rate of the discrepancy function is logarithmic in .
Proof. Note that for any and , since the map , is an isomorphism from the multiplicative group of non-zero integers mod 3 to the group under multiplication and last non-zero digits multiply together mod whatever base you’re working in. It follows that the theorem is true if and only if the partial sums grow logarithmically.
To see that this is the case, partition the integers from 1 to into subsets according to which digit is the last non-zero digit. As you go through the elements of any one of these sets in increasing order, the values alternate between 1 and -1. Therefore, their sum is either 0 or 1. There are at most such sets (that are non-empty), so the partial sum in question is at most . QED
This example rules out any approach that attempts to prove that the arithmetic progressions are “approximately orthogonal” and to deduce the result from some kind of coordinate expansion, since such results would give bounds more like .
The thought that goes into it also shows that we cannot hope to prove a more general conjecture that replaces the condition that by a looser condition that asks merely for to be bounded away from 0 on average. Indeed, the sequence has discrepancy at most 1 on all arithmetic progressions of the given form. However, I do not at this stage know of any counterexample to the following generalization that is designed to avoid this problem.
Problem. Let , let and suppose that for every the lim inf of the partial averages is greater than . Can there be a constant such that for every and ?
One might want to make map to to rule out boring counterexamples. The motivation for generalizing the problem in this way would be to try to make it more amenable to analytic techniques, but Walters’s example will always be a serious obstacle.
If I think of more to say about this problem, then I’ll add it. But since this post is quite short, and since this is the last problem I wish to describe in detail for now, let me also discuss my current thoughts about the next Polymath project for this blog.
It has been interesting to find how much my perception of a problem changes when I blog about it. For example, the effort to describe my tentative approach to the P versus NP problem led to my understanding that it couldn’t work, and I now do not regard that as a suitable project (though I would very much like to tackle a more realistic complexity question at some point in the future). I have found the discussion about modelling mathematically the origin of life extremely interesting: I think we are still some way from formulating a problem that is clearly good, so I would still like to wait a few months at least before embarking on a project on that general theme. (However, it might well be that formulating a good problem would be a necessary part of any such project — in that respect it would differ in an interesting way from projects where the aim is to prove a clearly stated conjecture.) I found myself regrabbed by Littlewood’s conjecture as soon as I posted about that, with the result that I now know the answers to many of the problems that I thought (rightly, as it turns out) would be significantly easier than the main problem. The result is that the drawback with that project, that it is a notoriously hard problem, is shown in rather sharper relief. If I felt that that was clearly the most popular choice, then I would certainly be happy to go along with it, but I am not sure it is the most suitable.
The least risky choices, in the sense that they are the most similar in nature to DHJ, would be the polynomial-DHJ-related problem about graph differences or Erdős’s discrepancy problem.
I welcome any thoughts that people might have about this. Once there has been some discussion, I will put up a poll, though I must warn in advance that the process will not be fully democratic, since I will attach more than one vote’s worth of weight to my own enthusiasm and to my perception of whether there is likely to be a nucleus of people who are ready to think seriously about the given problem. One reason I am drawn to the polynomial-DHJ project is that I already know of people who are very interested in that and ready to think about it. If you are keen on one of the other problems in a similar way, then feel free to let me know. If you don’t want to declare yourself publicly on this blog, then you could always drop me an email.
An additional thought about the problem.
I forgot to mention a variant of the problem that occurred to me, which is to look at the complex case instead. That is, one could ask the following.
Problem. Let be a sequence of complex numbers, each of modulus 1. Is it necessarily true that for every constant there exist and such that ?
And once one has asked that, one sees straight away that it is not really a complex version of the problem so much as an version. So here is a more general variant.
Problem. Let be a positive integer and let be a sequence of unit vectors in . Is it necessarily true that for every there exist and such that ?
I feel it should be easier than the original problem. Obviously, the larger is, the easier it is to find a sequence that works in . But if it is not possible to find such a sequence in any dimension, then I think that trying to prove it in a higher dimension ought to be easier because it forces you not to use special and ultimately irrelevant properties of sequences.
It suggests yet another problem, this one a generalization of the original problem but a specialization of the problem in .
Problem. Let be a partition of , let be a sequence, and let . Must there exist some and positive integers and such that , where ?
If the answer to this problem is no, then the answer to the previous problem is no as well, since one can take an orthonormal sequence and define to be , where is the colour class that contains .
However, I hope that the answer is yes, as is suggested by the Walters example. There, as I commented earlier, you can define a sequence that has bounded discrepancy, but if you want to make it a sequence then you are forced to assign values to multiples of 3 as well. In fact, that suggests a slight variant of the previous problem that is more explicitly Ramsey-like.
Problem. Let be a partition of . Does there exist such that for every and every sequence there exist and such that ?
The difference between this problem and the previous one is that is not allowed to depend on the sequence . It may be that the two problems are equivalent: I haven’t checked.
Another way to make the problem easier by making it more difficult, so to speak, would be to try to prove that there is no infinite sequence with bounded discrepancy even if one restricts to arithmetic progressions with common difference d that is not divisible by any of 2,3,5,7,…,101 or something like that. Then it would be an easy matter to create extremely long finite sequences that did have bounded discrepancy, so in trying to prove that there couldn’t be an infinite sequence, one would not be distracted by small-number difficulties and would be forced to come up with more global arguments. Let me state this formally as yet another problem.
Problem. Let be a positive integer, let and let be a sequence. Must there exist and such that is not divisible by any prime and such that ?
I’m not quite sure whether this is the most interesting problem that results from restricting the possible . Other possibilities are just to insist that or to insist that is divisible by a prime that is at least .