Return to Answer

The answer to both questions is negative.

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\leq N$ with more than $(1+o(1) )\sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N}$ prime factors.

The number of $q\leq N$ where the discrepancy is small is apparently $ e^{ (1+o(1) )\frac{1}{2} \sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N } \log \log \log N}$.

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?

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?

The answer to both questions is negative.

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\leq N$ with more than $(1+o(1) )\sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N}$ prime factors.

The number of $q\leq N$ where the discrepancy is small is apparently $ e^{ (1+o(1) )\frac{1}{2} \sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N } \log \log \log N}$.

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.

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?