Skip to main content
6 of 8
deleted 522 characters in body
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

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?

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563