Remainder Terms of Congruence Sums in Positive Density Sets

analytic-number-theoryarithmetic-progressionnt.number-theoryprime numberssieve-theory

Let $\mathcal{A} \subset \mathbb{N}$ be an infinite sequence with positive density, in the sense that
$$
\tag{1}
\lim_{x\to\infty} \frac{|\mathcal{A} \cap x|}{x} = c > 0,
$$

and define the remainder term $r_p(x)$ by
$$
r_p(x) = \sum_{\substack{n\leq x\\ n\in \mathcal{A}\\ p\mid n}} 1 – \frac{|\mathcal{A}\cap x|}{p}.
$$

What can be said about $r_p(x)$ on average, assuming only the hypothesis (1)? In particular, can one obtain an estimate of the form
$$
\tag{2}
\sum_{p\leq Q} |r_p(x)| \ll \frac{x}{\log x}
$$

in a large range of $Q$, potentially as large as $Q \leq x$? It seems to me that the positive density of the sequence $\mathcal{A}$ should preclude the possibility that $\mathcal{A}$ "misses" many primes, in the sense that $r_p(x)$ is large for many $p$. However, perhaps there is a way to construct such a sequence via a clever use of the Chinese Remainder Theorem. Any comments/references are most appreciated.

Edit. The estimate (2) is false in general, as one need only consider the case when $\mathcal{A}$ is an arithmetic progression. As a concrete example, if $\mathcal{A} = \left\{4n+1: n\geq 0\right\}$ and $p=2$, then
$$
|r_2(x)| = \frac{|\mathcal{A}|}{2} = \frac{x}{8}+O(1),
$$

since the sum is empty. For a general arithmetic progression $a\mod{q}$, this kind of thing happens for at most finitely many primes (the divisors of the modulus $q$). For the application I have in mind, I really only need something like
$$
\sum_{y < p\leq Q} |r_p(x)| \ll \frac{x}{\log x},
$$

where $y$ is a parameter that grows with $x$, and so a finite number of large $r_p(x)$ is acceptable. This also allows for sets $\mathcal{A}$ where the density of integers divisible by a prime $p$ is only asymptotically $\frac{1}{p}$. For instance, if $\mathcal{A}$ is the set of squarefree numbers, then one expects
$$
\sum_{\substack{n\leq x\\p\mid n}} \mu^2(n) \sim \frac{|\mathcal{A}\cap x|}{p+1}.
$$

Best Answer

Let $\mathcal A$ be the set of all $n\in \mathbb N$ with a prime factor $p>\sqrt{n}$. First, the number of elements $a\in \mathcal A$ with $a\leq x$ is $\gg x$. Indeed, this large prime factor is unique for any $a$, for a given $p\leq x$ there are $\left[\frac{\min(x,p^2)}{p}\right]$ integers $a\leq x$ with $p>\sqrt{a}$ and $p\mid a$. Therefore, $$ |\mathcal A\cap [1,x]|=\sum_{p\leq x}\left[\frac{\min(x,p^2)}{p}\right]=\sum_{\sqrt{x}<p\leq x}\frac{x}{p}+\sum_{p\leq \sqrt{x}}p+O(\pi(x))= $$ $$ =x(\ln 2+o(1))\gg x $$ On the other hand, for any $\sqrt{x}<p\leq x$ all the numbers between $\sqrt{x}$ and $x$, which are divisible by $p$, lie in $\mathcal A$. Therefore, $$ r_p(x)=\sum_{p\mid n, n\in \mathcal A} 1-\frac{x(\ln 2+o(1))}{p}\geq $$ $$ \geq \left[\frac{x}{p}\right]-\left[\frac{\sqrt{x}}{p}\right]-\frac{x(\ln 2+o(1))}{p}= $$ $$ =\frac{x(1-\ln 2)+o(x)}{p}. $$ Summing over all $\sqrt{x}\leq y<p\leq x$, we get $$ \sum_{y<p\leq x}|r_p(x)|\geq x(1-\ln 2+o(1))\sum_{y<p\leq x}\frac{1}{p}. $$ For $y=x^{1-\varepsilon}$ we would get $\gg x$. Also, a trivial upper bound for $r_p(x)$ is $\frac{x}{p}$, so for $y\geq \sqrt{x}$ there is no hope for an upper bound of non-trivial order.

Related Question