# Must bounded sequences be well-distributed to most *composite* moduli?

Let $$\{a_n\}_{n=1}^N$$, $$|a_n|\leq 1$$. Let $$Q=\sqrt{N}$$. Then $$a_n$$ is well-distributed modulo most prime $$p\leq Q$$, in the following sense: $$\sum_{p\leq Q} \frac{1}{p} \left(\frac{1}{N/p} \sum_{\substack{n\leq N\\ p|n}} a_n - \frac{1}{N} \sum_{n\leq N} a_n\right)^2 = O(1).\;\;\;\;\;\;\;\;\;\;\;\;\;\;(+)$$ This is just a weak form of the large sieve.

Can one give a similar statement with the sum ranging over all composite numbers? Say, is the inequality false with the outer sum ranging over $$q\leq Q=N^{1/10}$$, $$q$$ squarefree? Even if it is false, can one prove that, for $$S_\epsilon = \left\{q\leq Q, \text{Q squarefree}: \left| \frac{1}{N/q} \sum_{\substack{n\leq N: q|n}} a_n - \frac{1}{N} \sum_{n\leq N} a_n\right| < \epsilon\right\},$$ we have $$\sum_{q\in S_\epsilon} 1/q \gg_\epsilon \log Q$$ for $$\epsilon$$ arbitrarily small?

Some remarks:

• if we attempt to apply the duality principle to (+) with $$q$$ squarefree instead of $$p$$ prime, we obtain something that does not look true. However, the condition $$|a_n|\leq 1$$ is lost, so this is not even a sketch of a disproof.
• The duality principle does prove a statement like (+) for $$q$$ composite, but it isn't quite what we are asking for; see Théorème 5 in Bombieri's Le grand crible..., ignoring all non-zero moduli $$a$$. At the same time, that statement does give a lower bound on $$\sum_{q\in S_\epsilon} 1/q$$ better than $$\sum_{q\in S_\epsilon} 1/q \geq \sum_{p\in S_\epsilon} 1/p \gg \log \log Q$$ (which is what one gets easily from (+)). See the sketch in the (non-)self-answer below.
• Notes: (a) in (+), $=O(1)$ can be replaced by $\leq 2$. (b) As shown in Lemma 4.6 of vol I of P.D.T.A. Elliott's Probabilistic Number Theory), the statement (with $=O(1)$, not $\leq 2$) is true even for $Q=N$; it is basically the dual of the Turán–Kubilius inequality. (I do not really care about (a) or (b) right now - this is just a side note.) Commented Sep 5 at 2:46
• Something like what @WillSawin just posted and deleted should work (in the negative direction) - I was just thinking along the same lines, but I am on top of a Mayan ruin and my girlfriend is telling me to put away my phone. Commented Sep 5 at 17:39
• I undeleted it after fixing a problem (my first version of it didn't give a good bound for $\sum_{q \in S_\epsilon} 1/q$, but this version does.) Commented Sep 5 at 17:48

The answer to both questions is negative. I will now try to be careful about constants.

Let $$\omega(n)$$ be the number of prime factors of $$n$$, let $$a_n = \begin{cases} 1 & \omega(n) < \log \log N \\ -1 & \omega(n) > \log \log N \end{cases}.$$

By Erdős–Kac, $$\frac{1}{N} \sum_{n \leq N} a_n = o(1)$$.

On the other hand, by Erdős–Kac applied to $$n/q$$, $$\frac{1}{N/q} \sum_{n \leq N \colon q\mid n} a_n = o(1) + 2 \int_0^{ \frac{\omega(q)}{\sqrt{\log \log N}}} \frac{1}{\sqrt{2\pi}}e^{ -x^2/2} dx$$

So the difference $$\frac{1}{N/q} \sum_{n \leq N \colon q\mid n} a_n - \frac{1}{N} \sum_{n\leq N }a_n$$ is at least $$\epsilon$$ as long as $$\frac{\omega(q)}{\sqrt{\log \log N}} > \sqrt{2} \operatorname{erf}^{-1} (\epsilon) = \sqrt{\frac{\pi}{2}} \epsilon + O(\epsilon^2)$$

So it is possible for the discrepancy to be larger than $$\epsilon$$ for all $$q$$ with more than $$(1+o(1) )\sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N}$$ prime factors.

On the other hand, Harald's argument shows the discrepancy is smaller than $$\epsilon$$ for a proportion at least $$\gamma$$ of those $$q$$ with less than $$(1+o(1)) \frac{1-\gamma}{2} \epsilon \sqrt{\log \log N}$$ prime factors. But $$\epsilon$$ small we save the factor of $$2$$ as it comes from a crude geometric series bound and so we get $$(1-\gamma) \epsilon \sqrt{\log \log N}$$.

For a set $$B$$, if we let $$G_B$$ be the expectation of $$\gcd(n,m)-1$$ for $$n$$ and $$m$$ logarithmically random samples of $$B$$, then Tao's variant of Bergelson-Richter states that the discrepancy is at most $$\epsilon$$ for a proportion $$(1-\gamma)$$ of the $$q\in B$$ as long as $$G_B \leq \epsilon^2(1-\gamma)^2$$.

Tao checks that for $$B$$ the set of $$q \leq N$$ with at most $$k$$ prime factors we have $$G_B \leq e^{ e^2 k^2 / \log \log N}+o(1)$$ so to get $$G_B \leq \epsilon^2$$ we need $$k \leq (1+o(1)) \frac{1-\gamma }{e} \sqrt{\log \log N}$$.

So it looks to me like there is a factor of $$e$$ loss between the duality estimate and the large sieve estimate here and a $$\sqrt{\frac{\pi}{2}}$$ loss between the large sieve estimate and the construction.

Finally, Tao checks that for a set $$B$$ of numbers $$\leq N$$, most members of $$B$$ must have a number of prime factors at most $$\sqrt{G_B} \log \log N$$, so to prove that a proportion at least $$\gamma$$ of $$q\in B$$ have discrepancy at most $$\epsilon$$ by the duality method we require most $$q\in B$$ to have number of prime factors at most $$\epsilon(1-\gamma) \sqrt{\log \log N}$$. So maybe this upper bound is equivalent to the claim that there is no set of numbers where the duality method does better than the large sieve method?

• Nice. (I had a piecewise linear function of $\omega(n)$ in my head, but this is simpler.) Your last $>$ should be a $\leq$, right? Commented Sep 5 at 19:30
• @HAHelfgott Thanks! No, what I was trying to express is that the Erdős–Kac argument does not give a good enough bound on the number of large values of $q$ with a small number of prime factors. Of course there are other arguments that estimate that. Commented Sep 5 at 19:43
• Ah. Should I give a sketch of the bound for $k=\sqrt{\log \log N}$ below? It still has a wonky step at the beginning, but it can most likely be made rigorous. Commented Sep 5 at 23:02
• @HAHelfgott It seems that combining the arguments carefully would give that the sum is at most $\epsilon$ for almost all $q$ with at most $C_1 (\epsilon) \sqrt{\log \log N}$ prime factors but can sometimes fail to be at most $\epsilon$ for all $q$ with more than $C_2(\epsilon) \sqrt{\log \log N}$ prime factors for constants $C_1$ and $C_2$ going to $0$ with $\epsilon$. This would be a pretty sharp result and seems worth writing down. Commented Sep 6 at 1:36
• I’ll try to post something soon. (I’m still in Guatemala and my laptop is now refusing to turn on.) Commented Sep 8 at 3:35

This question is related to the results in

Bergelson, Vitaly; Richter, Florian K., Dynamical generalizations of the prime number theorem and disjointness of additive and multiplicative semigroup actions, Duke Math. J. 171, No. 15, 3133-3200 (2022). ZBL1514.37018.

Given a finite set $$B$$ of natural numbers, they introduce the quantity $${\mathbb E}_{n \in B}^{\log} {\mathbb E}_{m \in B}^{\log} \Phi(n,m) \tag{1}$$ where $$\Phi(n,m) := \mathrm{gcd}(n,m)-1$$ and $${\mathbb E}_{n \in B}^{\log}$$ denotes the logarithmic averaging operator $${\mathbb E}_{n \in B}^{\log} f(n) := \frac{\sum_{n \in B} f(n)/n}{\sum_{n \in B} 1/n}.$$ In Proposition 2.1 of that paper, they establish the Turan-Kubilius type inequality $$|{\mathbb E}_{n \in [N]} a_n - {\mathbb E}_{q \in B}^{\log} {\mathbb E}_{n \in [N]: q|n} a_{n}| \leq ({\mathbb E}_{n \in B}^{\log} {\mathbb E}_{m \in B}^{\log} \Phi(n,m))^{1/2} + o(1)$$ in the limit as $$N \to \infty$$ for $$1$$-bounded sequences $$a_n$$ (one can be more precise about the $$o(1)$$ term if desired). In fact their proof shows the stronger bound $${\mathbb E}_{q \in B}^{\log} |{\mathbb E}_{n \in [N]} a_n - {\mathbb E}_{n \in [N]: q|n} a_{n}| \leq ({\mathbb E}_{n \in B}^{\log} {\mathbb E}_{m \in B}^{\log} \Phi(n,m))^{1/2} + o(1);$$ this is not quite the dual of Lemma 2.4 of that paper, but can be proven by a similar method (insert some arbitrary bounded coefficients in the $$q$$ summation, which is a summation over $$m$$ in the notation of that paper). This gives the type of bound you seek as long as the quantity (1) is small.

In that paper it was noted that examples of sets of $$B$$ with small (1) include the sets of numbers with at most $$k$$ prime factors, for a fixed $$k$$. In a recent paper of mine, I worked out what the maximal size of $$B$$ could be while still keeping (1) small (this also answered a question of Erdős and Graham); see Proposition 2.2 of my paper. The optimal example is essentially the same as the one worked out by you and Will, namely the numbers with at most $$o(\sqrt{\log\log n})$$ prime factors. (One has to be more careful with this construction if one wants a single set $$B$$ which works at all scales $$N$$, rather than working with a single large scale $$N$$ and permitting $$B$$ to vary with $$N$$, but this is a technical detail.)

I'll also remark that the quantity (1) can also be rewritten in sum-of-squares form as $$\sum_{d>1} \phi(d) ({\mathbb E}_{n \in B}^{\log} 1_{d|n})^2,$$ which is a more tractable form of the expression when trying to compute it; see equation (1.10) of my paper. Not unsurprisingly, similar expressions also show up in the theory of the large sieve (and the Selberg sieve).

p.s. the asymptotic formula for counting the number of numbers up to $$N$$ with exactly $$k$$ prime factors is sometimes referred to as the Sathé-Selberg formula, see

Sathe, L. G., On a problem of Hardy on the distribution of integers having a given number of prime factors. II, J. Indian Math. Soc., New Ser. 17, 83-141 (1953). ZBL0051.28008.

and

Selberg, Atle, Note on a paper by L. G. Sathe, J. Indian Math. Soc., N. Ser. 18, 83-87 (1954). ZBL0057.28502.

• Nice. Is what Will and I have just worked out a special case of theirs? Commented Sep 9 at 16:31
• PS. Just eyeballed your paper quickly - is the point that one can pass to the dual and then solve the problem using one of your bounds in that paper? That doesn't seem quite as straightforward as the arguments here (in fact it's what I was trying to avoid) but I am guessing it should work. Commented Sep 9 at 16:35
• As I wrote, the positive result basically follows by applying an improved version of their Proposition 2.1 (as indicated above) to the construction in Proposition 2.2 of my own paper. As for negative results, my own paper has a negative result (Theorem 1.4(ii)) on controlling (1) for any larger set than the one under discussion, but because Proposition 2.1 of Bergelson-Richter is not necessarily sharp, this does not directly imply Will's counterexample (though it is certainly closely related, for instance the Hardy-Ramanujan law is an important guiding principle in both proofs). Commented Sep 9 at 16:38
• Basically, yes. Bergelson-Richter reduce the problem of getting well-distribution results to moduli in a set B to the problem of controlling the quantity (1). My paper controls the quantity (1) for the set you are discussing here, and shows that this is essentially the largest set for which (1) remains under control. Will shows the stronger statement that the set under consideration is also basically the largest set for which the original equidistribution statement is true. Commented Sep 9 at 16:40
• This may be related to a similar gap between the positive and negative results in Theorem 1.4 of my paper: for small $\varepsilon$ it is just a constant factor gap (a ratio of $2e$, to be precise) but for large $\varepsilon$ the gap is exponential. I would be interested in seeing if this gap can be narrowed. Commented Sep 9 at 16:45

Here is an inequality one can in fact prove by the duality principle (Théorème 5 in Bombieri's Le grand crible, ignoring terms with $$a\ne 0$$):

$$\sum_{q\leq Q} \frac{\mu^2(q)}{q} \left(\frac{1}{N} \sum_{d|q} \mu(d) d \sum_{\substack{n\leq N\\d|n}} a_n\right)^2 \leq 2.$$

It is straightforward to use this inequality to prove that $$\frac{1}{N/q} \sum_{n\leq N: q|n} a_n - \frac{1}{N} \sum_{n\leq N} a_n$$ is small for most $$q$$ having a bounded number of small prime factors -- meaning $$\sum_{q\in S_\epsilon} 1/q \gg_k (\log \log Q)^k$$ for every $$k\geq 1$$. One can probably push this argument up to $$k = \sqrt{\log \log N}$$ or so.

Can one go farther, possibly by other means?

Update: (a) as Will Sawin showed, one cannot go farther, (b) as my new answer shows, yes, one can go up to $$k$$ in the order of $$\sqrt{\log \log N}$$ (or rather $$\epsilon \sqrt{\log \log N}$$).

• Both upper and lower bounds (expressed in terms of the number of prime factors) being of order $\epsilon \sqrt{\log \log N}$ is remarkable. Commented Sep 9 at 0:38
• @WillSawin Sure, let’s write it up more formally and send it off when we both have the time. (Or do you mean something else?) Commented Sep 9 at 1:16
• That wasn't what I meant to suggest but it works for me. Commented Sep 9 at 11:10
• @WillSawin Whichever way. It's true that it has turned out to be very easy. But why would it be remarkable that the upper and lower bounds are of the same order? Commented Sep 9 at 12:10
• Just because in general there's a lot of ways that slackness can be introduced into an argument and it can be hard to find an explicit example that exhibits the worst-case scenario, the upper and lower bounds seem to take different perspectives on the problem, we have two parameters and the dependence on each one is sharp, and the comparison is "qualitative" in that it identifies explicit sets of moduli where the difference must usually be small / can always be large instead of just counting the size of the bad set. Commented Sep 9 at 12:42

Not in Mayan glyphs but it should do.