# Remainder terms of congruence sums in sets of positive density

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

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} $$=x(\ln 2+o(1))\gg x$$ On the other hand, for any $$\sqrt{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, we get $$\sum_{y 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.
• I also think one can replace $p>\sqrt{n}$ with $p>n^\varepsilon$ for any $\varepsilon>0$ and obtain a similar lower bound for all $y\geq x^\varepsilon$. Jan 26, 2022 at 12:21