5
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Commented Jan 26, 2022 at 12:21
  • 2
    $\begingroup$ Great answer. I actually happened to stumble across this sequence today doing some related searches. $\endgroup$ Commented Jan 26, 2022 at 19:58

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.