I've been obsessed with this one problem for many months now, and today is the sad day that I admit to myself I won't be able to solve it and I need your help. The problem is simple. We let


denote the expected value of a function $f(n)$ (if it exists). This means that for some fixed choice of sequence $(a_n)_{n=1}^{\infty}$ the quantities $\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]$ will give the "average value of every $k$" elements. For example, $\mathbb{E}_{n\in\mathbb{N}}[a_{3n}]$ will be the average of $a_{3},a_{6},a_{9}$ etc... . If all of these quantities exist, we will call a sequence $a_n$ to be "sequentially summable". The problem is as follows:

Show that for any bounded sequentially summable $a_n$ \begin{equation}\sum_{k=1}^{\infty}\frac{\lambda(k)\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]}{k}=0\tag{1}\end{equation} where $\lambda(n)$ denotes the Liouville function

Swapping which side the term $\mathbb{E}_{n\in\mathbb{N}}[a_n]$ is on, this gives an absolutely lovely formula for $\mathbb{E}_{n\in\mathbb{N}}[a_n]$ from $\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]$ ($k\geq 2$) which can be appreciated by even people who have done no mathematics. Similarly, I would expect that the conjecture holds for $\lambda(n)$ replaced by its "twin" $\mu(n)$, the Mobius function. Throughout the rest of this question, I will give all of the partial results and a general outline of how they are obtained.

This first partial results answers the question "why on earth would these values be 0???":

Partial Result $\#1$: For any bounded sequentially summable sequence $a_n$, it holds that \begin{equation}\lim_{s\to1^+}\sum_{k=1}^{\infty}\frac{\lambda(k)\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]}{k^s}=\lim_{s\to1^+}\sum_{k=1}^{\infty}\frac{\mu(k)\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]}{k^{s}}=0\tag{2}\end{equation} and thus if the sum in (1) converges it must converge to $0$

This result is obtained by inverting the summation order and exploiting the fact that $$\sum_{d|n}\frac{\mu(n)}{n^s}=\prod_{p}\left(1-\frac{1}{p^s}\right)>0$$ which means that the triangle inequality does not "lose" any sign cancelation. The following partial result is much stronger:

Partial Result $\#2$: There exists an absolute constant $c_0$ such that for any sequentially summable sequence $a_n$ and $N>0$ \begin{equation}\left|\sum_{k=1}^N\frac{\lambda(k)\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]}{k}\right|<c_0m\tag{3}\end{equation} where $$m^2=\limsup_{N\to\infty}\frac{1}{N}\sum_{n=1}^Na^2_{n}$$

An outline of the proof of this result is given in this Math.SE question, but in essence the result comes from the fact that the boundedness of


for some function $f(k)$ is essentially equivalent to tight enough bounds on the partial sums


for all values of $m<N$, which $\mu(n)$ definitely has. The boundedness in Partial Result $\#2$ can be translated to bounds when $\mu(n)$ is replaced by $\lambda(n)$ by exploiting the identity $\lambda(n)=\sum_{d^2|n}\mu\left(\frac{n}{d^2}\right)$ and the relative uniformity of the bound w.r.t out choice of $a_n$. Here is the next partial result

Partial Result $\#3$: If, for any bounded sequentially summable sequence $a_n$, we have that \begin{equation} \lim_{N\to\infty}\frac{1}{N}\sum_{k=1}^{N}\lambda(k)\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]=0 \end{equation} then our conjecute (1) holds.

This is a very important partial result since it is often much easier to show that the average of coefficients is zero than to show that they converge when summed with a factor of $\frac{1}{k}$. This result is done in a "smoothing" manner where Partial Result $\#3$ can be considered as control over short intervals and Partial Result $\#2$ can be considered as control over large intervals which we can bound as error.

At this point I will note that the condition that $a_n$ be bounded is quite important. For example, if $a_n=\Lambda(n)$ is the Von-Magnolt function then by the PNT $\mathbb{E}_{n\in\mathbb{N}}[a_n]=1$ but since $kn$ will have "few" prime powers for $k>1$ we have that $\mathbb{E}_{n\in\mathbb{N}}[a_{kn}]=0$ and thus our sum converges, but not to $0$.

I add as well that


due to simple inversion of summation order, and so since

$$\frac{1}{[N/k]}\sum_{n=1}^{[N/k]}a_{kn}\approx \mathbb{E}_{n\in\mathbb{N}}[a_{kn}]$$

we get further intuition for the result.

  • 2
    $\begingroup$ I wrote up Terry's argument in more classical form. See below. $\endgroup$
    – GH from MO
    Commented Nov 7, 2020 at 1:39

2 Answers 2


This identity is true, though somewhat tricky to prove and the infinite series here might only converge conditionally rather than absolutely.

The key lemma is

Lemma 1 (Fourier representation of averages along homogeneous arithmetic progressions). Let $a_n$ be a bounded sequentially summable sequence. Then there exist complex numbers $c_\xi$ for each $\xi \in {\mathbb Q}/{\mathbb Z}$ such that $\sum_{\xi \in {\mathbb Q}/{\mathbb Z}} |c_\xi|^2 \ll 1$ and $$ {\mathbb E}_{n \in {\mathbb N}} a_{kn} = \sum_{q|k; 1 \leq b < q; (b,q)=1} c_{b/q}.$$ for each natural number $k$.

Proof We first use the Furstenberg correspondence principle to move things to a compact abelian group (specifically, the profinite integers $\hat {\mathbb Z}$). It is convenient to introduce a generalised limit functional $\tilde \lim_{N \to \infty} \colon \ell^\infty({\mathbb N}) \to {\mathbb C}$ that is a continuous linear functional extending the usual limit functional (this can be created by the Hahn-Banach theorem or by using an ultrafilter). On every cyclic group ${\mathbb Z}/q{\mathbb Z}$ we then have a complex bounded density measure $\mu_q$ defined by $$ \mu_q(\{b \hbox{ mod } q \}) := \frac{1}{q} \tilde \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N a_{b+nq}$$ for any integer $b$ (the particular choice of coset representative $b$ is not important). One can check that $\mu_q$ pushes forward to $\mu_{q'}$ under the quotient map from ${\mathbb Z}/q{\mathbb Z}$ to ${\mathbb Z}/q'{\mathbb Z}$ whenever $q'$ divides $q$, hence by the Kolmogorov extension theorem, there is a complex bounded density measure $\mu$ on the profinite integers $\hat {\mathbb Z}$ that pushes forward to all of the $\mu_q$, in particular $$ \mu( b + q \hat {\mathbb Z} ) = \frac{1}{q} \tilde \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N a_{b+nq}$$ for any residue class $b \hbox{ mod } q$. Specialising to $b=0$ and using the sequential summability hypothesis we conclude $$ \mu( q \hat {\mathbb Z} ) = \frac{1}{q} {\mathbb E}_{n \in {\mathbb N}} a_{qn}.$$ Now we use the Fourier transform to move to frequency space. The Radon-Nikodym derivative of $\mu_q$ with respect to Haar probability measure on ${\mathbb Z}/q{\mathbb Z}$ is bounded, hence the Radon-Nikodym derivative of $\mu$ with respect to Haar probability measure $\mathrm{Haar}_{\hat {\mathbb Z}}$ on the compact abelian group $\hat {\mathbb Z}$ is bounded. By Fourier expansion and Plancherel's theorem on $\hat {\mathbb Z}$ (which has Pontryagin dual ${\mathbb Q}/{\mathbb Z}$) we conclude the Fourier expansion $$ \frac{d\mu}{d\mathrm{Haar}_{\hat {\mathbb Z}}}(x) = \sum_{\xi \in {\mathbb Q}/{\mathbb Z}} c_\xi e^{2\pi i x \xi} $$ (in an $L^2$ sense) where $x \xi \in {\mathbb R}/{\mathbb Z}$ is defined in the obvious fashion and the Fourier coefficients $c_\xi$ are square-summable. In particular (by Parseval or a suitable form of Poisson summation) we have $$ \mu( q \hat {\mathbb Z} ) = \frac{1}{q} \sum_{b \in {\mathbb Z}/q{\mathbb Z}} c_{b/q}$$ and thus we have a compact formula for the average values of the $a_{kn}$ in terms of the Fourier coefficients: $$ {\mathbb E}_{n \in {\mathbb N}} a_{kn} = \sum_{b \in {\mathbb Z}/k{\mathbb Z}} c_{b/k}.$$ Reducing the fractions to lowest terms we conclude that $$ {\mathbb E}_{n \in {\mathbb N}} a_{kn} = \sum_{q|k; 1 \leq b < q; (b,q)=1} c_{b/q}$$ as desired. $\Box$

Remark 2 One can avoid the use of generalised limits (and thus the axiom of choice or some slightly weaker version thereof) by establishing a truncated version of this lemma in which one only considers those natural numbers $k$ dividing some large modulus $Q$, and replaces the averages ${\mathbb E}_{n \in {\mathbb N}}$ by ${\mathbb E}_{n \in [N]}$ for some $N$ much larger than $Q$. Then one has a similar formula with errors that go to zero in the limit $N \to \infty$ (for $Q$ fixed). One can then either recover the full strength of Lemma 1 by any number of standard compactness arguments (e.g., Tychonoff, Banach-Alaoglu, Hahn-Banach, Arzela-Ascoli, or ultrafilters) or else just use the truncated version in the arguments below and manage all the error terms that appear. In particular it is possible to solve the problem without use of the axiom of choice. I leave these variations of the argument to the interested reader. $\diamond$

Remark 3 The Fourier coefficients $c_{b/q}$ can be given explicitly by the formula $$ c_{b/q} = \tilde \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N a_n e(-nb/q)$$ (the minus sign in the exponential $e(\theta) := e^{2\pi i \theta}$ is an arbitrary convention and may be omitted if desired). The desired representation then follows from the Fourier inversion formula in ${\mathbb Z}/k{\mathbb Z}$, and the square-summability follows from the large sieve (e.g., equation (20) from this paper of Montgomery; many other references exist for this). $\diamond$

Returning to the problem, we use the above lemma to write $$ \sum_{k=1}^N \frac{\lambda(k) {\mathbb E}_{n \in {\mathbb N}} a_{kn}}{k} = \sum_{k=1}^N \frac{\lambda(k) \sum_{q|k; 1 \leq b < q; (b,q)=1} c_{b/q}}{k}$$ $$ = \sum_{q \leq N} \sum_{1 \leq b < q: (b,q)=1} c_{b/q} \sum_{l \leq N/q} \frac{\lambda(ql)}{ql}.$$ Note the cancellation present in the inner sum. To exploit this cancellation, let $\varepsilon>0$ be a small parameter. For $N$ large enough, we have from dominated convergence that $$ \sum_{\varepsilon N \leq q \leq N} \sum_{1 \leq b < q: (b,q)=1} |c_{b/q}|^2 \leq \varepsilon$$ and $$ \sum_{q \leq \varepsilon N} \sum_{1 \leq b < q: (b,q)=1} |c_{b/q}|^2 \ll 1$$ so by Cauchy-Schwarz one can bound the preceding expression in magnitude by $$ \ll \left(\sum_{q \leq \varepsilon N} \sum_{1 \leq b < q: (b,q)=1} \left|\sum_{l \leq N/q} \frac{\lambda(ql)}{ql}\right|^2 + \varepsilon \sum_{\varepsilon N \leq q \leq N} \sum_{1 \leq b < q: (b,q)=1} \left|\sum_{l \leq N/q} \frac{\lambda(ql)}{ql}\right|^2\right)^{1/2}.$$ There are at most $q$ values of $b$ for each $q$, so this can be bounded by $$ \ll \left(\sum_{q \leq \varepsilon N} \frac{1}{q} \left|\sum_{l \leq N/q} \frac{\lambda(l)}{l}\right|^2 + \varepsilon \sum_{\varepsilon N \leq q \leq N} \frac{1}{q} \left|\sum_{l \leq N/q} \frac{\lambda(l)}{l}\right|^2\right)^{1/2}.$$ From the prime number theorem one has $$ \sum_{l \leq N/q} \frac{\lambda(l)}{l} \ll \log^{-10}(2+N/q)$$ (say). From this and some calculation one can bound the preceding expression by $$ (\log^{-19}(1/\varepsilon) + \varepsilon)^{1/2}$$ which goes to zero as $\varepsilon \to 0$, giving the claim.

  • 3
    $\begingroup$ +1, nice answer! I think it might make things clearer (and less scary to the more novice reader) to separate into a lemma the statement that sequential summability implies the existence of $(c_n)_n$ with ${\mathbb E}_{n \in {\mathbb N}} a_{kn} = \sum_{q|k; 1 \leq b < q; (b,q)=1} c_{b/q}$ for each $k$. $\endgroup$ Commented Nov 6, 2020 at 14:14
  • 4
    $\begingroup$ @GHfromMO Yes, this presumably follows from some version of the large sieve inequality (in particular now that I look at it the classical papers of Montgomery and Montgomery-Vaughan are likely to contain very similar inequalities to the one you write). Here I followed the path that ended up working for the Erdos discrepancy problem, but I am sure other proofs are available also. $\endgroup$
    – Terry Tao
    Commented Nov 6, 2020 at 15:43
  • 3
    $\begingroup$ You are welcome to write up the argument by yourself (possibly in a simplified form, e.g., using the large sieve inequality as suggested above) and cite this MO answer as its origin. $\endgroup$
    – Terry Tao
    Commented Nov 6, 2020 at 17:23
  • 4
    $\begingroup$ @MiloMoses: This website is not for disseminating or verifying one's results, nor is it for personal communication. Your question has been answered: further corollaries should be explained elsewhere, while further questions should be asked as a new entry. With all that said, I congratulate to you on the original question and the activity it generated. $\endgroup$
    – GH from MO
    Commented Nov 8, 2020 at 7:49
  • 3
    $\begingroup$ @GHfromMO Thank you. I have now deleted my added answer and my out of place comments. $\endgroup$
    – Milo Moses
    Commented Nov 8, 2020 at 16:37

Here is a more classical (more streamlined) version of Terry's nice argument. It avoids any reference to generalized limits (hence the axiom of choice).

We shall only use that $a_n$ is sequentially summable and satisfies the weak mean square bound $$\liminf_{N\to\infty}\frac{1}{N}\sum_{n\leq N}|a_n|^2<\infty.$$ By assumption, the limits $$f(k):=\lim_{N\to\infty}\frac{1}{N}\sum_{n\leq N}a_{kn}$$ exist, and we want to show that $$\sum_{k=1}^\infty\frac{\lambda(k)f(k)}{k}=0.\tag{$\ast$}$$ Lemma. The multiplicative convolution $g:=\mu\ast f$ satisfies $$\sum_{q=1}^\infty\frac{|g(q)|^2}{\varphi(q)}<\infty.$$ Proof. For the exponential sums $$S_N(x):=\sum_{n\leq N} a_n e(nx),$$ we observe that $$\sum_{q\mid k}\sideset{}{^*}\sum_{b\bmod q}S_N(b/q)=\sum_{c\bmod k}S_N(c/k)=k\sum_{\substack{n\leq N\\k\mid n}}a_n=k\sum_{m\leq N/k}a_{km}.$$ Dividing by $N$ and letting $N\to\infty$, the right hand side tends to $f(k)$. Therefore, $$f(k)=\lim_{N\to\infty}\frac{1}{N}\sum_{q\mid k}\sideset{}{^*}\sum_{b\bmod q}S_N(b/q).$$ It follows that $$g(q)=\lim_{N\to\infty}\frac{1}{N}\sideset{}{^*}\sum_{b\bmod q}S_N(b/q).$$ In particular, the limit on the right hand side exists. Using the Cauchy-Schwarz inequality and the large sieve inequality, we infer that $$\sum_{q\leq Q}\frac{|g(q)|^2}{\varphi(q)}\leq\liminf_{N\to\infty}\frac{1}{N^2}\sum_{q\leq Q}\sideset{}{^*}\sum_{b\bmod q}|S_N(b/q)|^2\leq\liminf_{N\to\infty}\frac{1}{N}\sum_{n\leq N}|a_n|^2<\infty.$$ Letting $Q$ tend to infinity, the inequality in the lemma follows. $\Box$

For $g$ as in the Lemma, we have $f=1\ast g$, hence also $$\sum_{k\leq K}\frac{\lambda(k)f(k)}{k}=\sum_{k\leq K}\frac{\lambda(k)}{k}\sum_{q\mid k}g(q)=\sum_{q\leq K}g(q)\sum_{\substack{k\leq K\\q\mid k}}\frac{\lambda(k)}{k} =\sum_{q\leq K}\frac{g(q)\lambda(q)}{q}\sum_{\ell\leq K/q}\frac{\lambda(\ell)}{\ell}.$$ In particular, $$\left|\sum_{k\leq K}\frac{\lambda(k)f(k)}{k}\right|\leq \sum_{q\leq K}\frac{|g(q)|}{q}\left|\sum_{\ell\leq K/q}\frac{\lambda(\ell)}{\ell}\right|.$$ Let us fix a large $L>0$. We cut the $q$-sum into two parts $q\leq K/L$ and $q>K/L$, and we apply Cauchy-Schwarz to both parts: $$\left|\sum_{k\leq K}\frac{\lambda(k)f(k)}{k}\right|^2\ll \left(\sum_{q\leq K/L}\frac{|g(q)|^2}{\varphi(q)}\right)\left(\sum_{q\leq K/L}\frac{\varphi(q)}{q^2}\left|\sum_{\ell\leq K/q}\frac{\lambda(\ell)}{\ell}\right|^2\right) +\left(\sum_{K/L<q\leq K}\frac{|g(q)|^2}{\varphi(q)}\right)\left(\sum_{K/L<q\leq K}\frac{\varphi(q)}{q^2}\left|\sum_{\ell\leq K/q}\frac{\lambda(\ell)}{\ell}\right|^2\right).$$ Now we let $K\to\infty$, and apply the Lemma. On the right hand side, the first $q$-sum is $O(1)$, the third $q$-sum is $o_L(1)$, and the fourth $q$-sum is $O_L(1)$. As a result, $$\limsup_{K\to\infty}\left|\sum_{k\leq K}\frac{\lambda(k)f(k)}{k}\right|^2 \ll\limsup_{K\to\infty}\sum_{q\leq K/L}\frac{\varphi(q)}{q^2}\left|\sum_{\ell\leq K/q}\frac{\lambda(\ell)}{\ell}\right|^2.$$ By the Prime Number Theorem, the $\ell$-sum is $\ll 1/\log(K/q)$, where of course $K/q\geq L$. By applying a dyadic decomposition for $q$, we conclude that $$\limsup_{K\to\infty}\left|\sum_{k\leq K}\frac{\lambda(k)f(k)}{k}\right|^2 \ll\frac{1}{\log L}.$$ Letting $L\to\infty$, we see that the left hand side is zero. We have proved $(\ast)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.