3
$\begingroup$

I think that there is a typo in the paper referred to in the title of the question, available here. While discussing Roth's proof of AP discrepancy, on page 2, the author states that

Roth [20] established the existence of such irregularities of distribution. Indeed, more generally he showed that if $A$ is a subset of the [positive] integers up to $N$ with $|A| = ρN$, then there exists an absolute positive constant $c$ such that $$ \sup_{\stackrel{k \leq \sqrt{N}}{a\pmod k}} \left| \sum_{\stackrel{n \in A}{n \equiv a \pmod k}} 1-\frac{\rho N}{q} \right| \geq c \sqrt{\rho(1-\rho)}N^{1/4} $$ In other words, the only subsets of $[1, N ]$ that are evenly distributed in all arithmetic progressions with moduli below $\sqrt{N}$ are essentially the empty set (with $\rho=1$) or the whole set (with $\rho=1$).

Shouldn't the $k$'s in this inequality should be replaced by $q$'s?

$\endgroup$
  • 4
    $\begingroup$ Yes. Or the $q$ should be replaced by $k$. $\endgroup$ – Thomas Bloom Dec 16 '18 at 9:21
  • $\begingroup$ @ThomasBloom, I will accept this if you want to type it as an answer. Thanks. $\endgroup$ – kodlu Dec 16 '18 at 23:00
3
$\begingroup$

I actually think there is a more significant flaw. A counterexample to the centered inequality is $\rho = \frac{1}{2}$ and $A = \{1,2,\dots,\frac{N}{2}\}$. Indeed, we always have $\sum_{n \in A, n \equiv a \pmod{q}} 1 -\frac{N/2}{q} = O(1)$.

What he actually meant to say is what he ended up saying in words: "evenly distributed in all arithmetic progressions with moduli below $\sqrt{N}$". The correct inequality would be something like $$\sup_{\substack{q \le \sqrt{N} \\ a \pmod{q}} \\ 1 \le m_1 < m_2 \le N} \left| \sum_{\substack{n \in A \\ n \equiv a \pmod{q} \\ m_1 < n \le m_2}} 1 - \frac{\rho (m_2-m_1)}{q}\right| \ge c\sqrt{\rho(1-\rho)}N^{1/4}.$$

And indeed, the cited paper says this same thing (note that, by the triangle inequality, we can remove the $m_1$ in the above at the cost of changing $c$ to $\frac{c}{2}$).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.