Good weights for the Erdős discrepancy problem

Good weights for the Erdős discrepancy problem, Discrete Analysis 2020:8, 23 pp.

The Erdős discrepancy problem, solved by Terence Tao in 2015 (see the very first article in this journal) was the following question. Let $f\colon\mathbb N\to\{-1,1\}$ be an arbitrary function. Is it necessarily the case that for every $C$ there exist $d$ and $m$ such that $|\sum_{k=1}^mf(kd)|\geq C$? Tao proved not only that the answer is positive, but that it remains positive if $f$ takes values in the unit circle in $\mathbb C$, or even in the unit sphere of a real or complex Hilbert space.

This paper is concerned with generalizations of the problem where now one attaches a sequence of weights to the sum that is supposed to be large. That is, if $w\colon\mathbb N\to\mathbb C$ is a function that takes values of modulus at most 1 and $f\colon\mathbb N\to\mathbb C$ is a function that takes values of modulus exactly 1, must there necessarily exist $d$ and $m$ such that $|\sum_{k=1}^mw(k)f(kd)|\geq C$? (As with Tao’s result, the results of this paper carry over to unit vectors in a Hilbert space as well.) If the answer is yes, then the author calls $w$ a good weight. Thus, Tao’s result says that the constant function $w\equiv 1$ is a good weight.

An instructive example of a sequence of weights that is not good is any function of the form $w(k)=(-1)^kf(k)$, where $f\colon\mathbb N\to\mathbb C$ is a completely multiplicative function (meaning that it satisfies the condition $f(mn)=f(m)f(n)$ for every $m,n\in\mathbb N$) taking values of modulus 1. Then
$$\sum_{k=1}^mw(k)\overline{f(kd)}=f(d)\sum_{k=1}^m(-1)^k|f(k)|^2,$$
which equals 0 or $f(d)$, so the weighted partial sums are bounded in this case. Thus, if one is looking for sufficient conditions for a weight $w$ to be good, it is important that those conditions should rule out examples of this kind.

The main results of the paper are about two different classes of weights, which can be thought of loosely as a “structured” class and a “random” class.

The structured class includes the weight $w(k)=\exp(2\pi i\alpha k^2)$, where $\alpha$ is irrational. It is important that the power of $k$ is at least 2, since the partial sums of $\exp(2\pi i\alpha k)$ are bounded, but higher powers work. This follows from a general statement that gives sufficient conditions in terms of ergodic-theoretic properties of associated dynamical systems.

The result about the random class gives conditions on a sequence of independent random variables for the resulting weight to be almost surely good. The most obvious example is that if the values $w(k)$ are chosen independently and uniformly from $\{-1,1\}$, then $w$ is almost surely a good weight.

Some of Tao’s arguments are used in this paper, but not all of them are needed: the conditions imposed on the weight $w$ make the results easier to prove than in the case $w\equiv 1$. (In particular, the results of this paper do not imply Tao’s result.) However, these weighted versions have interesting corollaries. An interesting one proved in the paper is that if $f$ is a multiplicative function taking values of modulus 1, $\alpha$ is irrational, and $r\geq 2$, then the partial sums $\sum_{k=1}^nf(k)f(k+1)\exp(2\pi i\alpha k^r)$ are unbounded. There are also a number of attractive open problems stated in the paper. One of them is whether the characteristic function of the set of integers of the form $n^2+1$ is a good weight. This is equivalent to asking whether for every function $f$ taking values of modulus 1 and every constant $C$ there exist $d,m\in\mathbb N$ such that
$$|\sum_{k=1}^mf((k^2+1)d)|\geq C.$$