Find a good configuration of HAPs

Click here to return to the main Polymath5 page.

Introduction

One of the difficulties of thinking about the Erdős discrepancy problem is that one can get hung up on HAPs with small common differences, when ultimately what should matter is the more typical HAPs, which have large common differences. This is less of a problem when one is looking at multiplicative sequences, since then all one cares about is partial sums. However, the strategy to be described on this page concerns a direct attack on the general problem.

The rough idea is this. Recall that a hypergraph is a collection of subsets of some set X. We borrow graph terminology and call the elements of X verticesand the sets in H edges (or sometimes hyperedges if we want to make it clear that our graph is hyper). If H is a hypergraph with vertex set X and f is a function from X to {-1,1}, then the discrepancy of f is the maximum of [math]\displaystyle{ |\sum_{x\in A}f(x)| }[/math] over all edges A of H. The discrepancy of H is the minimum discrepancy of any function [math]\displaystyle{ f:X\to\{-1,1\} }[/math].

The Erdős discrepancy problem is asking us to prove that the discrepancy of the hypergraph whose vertex set is [math]\displaystyle{ \mathbb{N} }[/math] and whose edges are all finite HAPs is infinite. One obvious strategy for doing this is to identify within this hypergraph a collection of hypergraphs [math]\displaystyle{ H_n }[/math] that have properties that allow us to prove arbitrarily good lower bounds for the discrepancy. What makes this a strategy, rather than a trivial reformulation of the problem (after all, one might suggest that there is no point in taking all HAPs) is that one would be aiming to find subhypergraphs of the HAP hypergraph that lent themselves particularly well to certain kinds of combinatorial arguments.

This point will be much clearer if we discuss an actual example of a subhypergraph that might do the trick. (I shall follow the usual practice, when talking informally about asymptotic arguments, of talking about "a subhypergraph" when strictly speaking what I mean is a sequence of larger and larger subhypergraphs. I shall picture a single subhypergraph that is very large.

A collection of HAPs that might be useful

Let us pick three very large integers L, M and N, with N much larger than M and M much larger than L. Let us then take the set of all HAPs of length L that live inside the interval [N,N+M] and have common difference d such that dL is at most o(M). (This o(M) is shorthand for some convenient function we choose later.) I should make clear that what I am calling a HAP here is an arithmetic progression of the form (x,x+d,...,x+(L-1)d) such that d is a factor of x (so that if you continued the progression backwards it would include zero).

One might hope that if L, M and N are sufficiently large, then a general principle along the following lines should hold: almost all numbers behave like average numbers. An example of where this principle does hold is in the number of prime factors. If n is a random number close to N, then not only does n have, on average, roughly log log N prime factors, but the Erdős-Kac theorem tells us that the number of prime factors is approximately normally distributed with mean log log N and standard deviation [math]\displaystyle{ \sqrt{\log n} }[/math]. Unfortunately, this suggests that the number of factors (as opposed to prime factors) is not concentrated. This could be a problem.

A toy model of what is going on

Let f be a function from [N,N+M] to {-1,1}. We would like to obtain a lower bound for the sum

[math]\displaystyle{ \sum_{x=N}^{N+M}\sum_{d|x}|f(x)+f(x+d)+\dots+f(x+(L-1)d)|^2. }[/math]

Here, the second sum should be taken to be over all d such that x+Ld also lives in the interval [N,N+M].

Now let us take the attitude that for each d the probability that d is a factor of x is [math]\displaystyle{ d^{-1} }[/math]. (That is because we are imagining that x mod d is uniformly distributed.) According to this very simple model (which ignores all sorts of dependences), we ought to be able to get a good iea of the above sum if we replace it by the sum

[math]\displaystyle{ \sum_{x=N}^{N+M}\sum_dd^{-1}|f(x)+f(x+d)+\dots+f(x+(L-1)d)|^2. }[/math]

Expanding out the square and interchanging the order of summation, we get

[math]\displaystyle{ \sum_{1\leq i,j\leq L}\sum_{x=N}^{N+M}\sum_d d^{-1}f(x+id)f(x+jd). }[/math]

The i=j contribution to this quantity is [math]\displaystyle{ L\sum_{x=N}^{N+M}\sum_dd^{-1}. }[/math] For a typical x, we sum over d in an interval [-A,B] with both A and B at least [math]\displaystyle{ M^{1-\epsilon}, }[/math] so this sum works out at about [math]\displaystyle{ LM\log M. }[/math]

If [math]\displaystyle{ i\ne j, }[/math] then the pair [math]\displaystyle{ (x+id,x+jd) }[/math] can be made to equal some pair [math]\displaystyle{ (u,v) }[/math] (by an appropriate choice of x and d) only if j-i is a factor of v-u, and that's sort of an if as well, give or take a few edge effects. The probability of this is [math]\displaystyle{ |j-i|^{-1}. }[/math] Also, [math]\displaystyle{ d=(j-i)^{-1}(v-u), }[/math] so we can rewrite the inner sum in this case as [math]\displaystyle{ \sum_{u,v}|v-u|^{-1}f(u)f(v). }[/math] (This is not supposed to be a rigorous argument.)

What I now hope is that if the partial sums of f remain bounded, then a sum like [math]\displaystyle{ \sum_{u,v}|v-u|^{-1}f(u)f(v) }[/math] has to be small, so that in total we find that

[math]\displaystyle{ \sum_{x=N}^{N+M}\sum_dd^{-1}|f(x)+f(x+d)+\dots+f(x+(L-1)d)|^2\geq LM\log M/2, }[/math]

from which we can conclude that there exist x and d such that [math]\displaystyle{ |f(x)+f(x+d)+\dots+f(x+(L-1)d)|^2\geq L, }[/math] giving us the unboundedness we were looking for.

For this to work we would need to show that it really is the case that the off-diagonal contribution to the sum is small, and, probably more challengingly (unless the first step is plain wrong), that the probabilistic assumptions we made can be justified. A justification would consist in showing that the actual weights (which are 1 if d divides x and 0 otherwise) are sufficiently quasirandom that they approximate, in an appropriate sense, the idealized weights (which are [math]\displaystyle{ d^{-1} }[/math]). And we would need to justify the second probabilistic approximation as well.