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

Question

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.

Answer 1

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.

Answer 2

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?

Answer 3

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}$).

Answer 4

Not in Mayan glyphs but it should do.