---

Claim. K. F. Roth, Remark concerning integer sequences, Acta Arith. 9 (1964), no. 3, 257--260, cited as [Ro64] on the problem page. For a set $\mathcal N$ of distinct positive integers not exceeding $N$ with density $\eta=\lvert\mathcal N\rvert/N$, let $V_q(m)$ be the sum over the residue classes $h$ modulo $q$ of the squared difference between the number of elements of $\mathcal N$ up to $m$ in the class $h$ and its expected value $\eta m/q$. The Theorem (p. 257) states that for every $Q$

$$\sum_{q\le Q}\frac1q\sum_{m\le N}V_q(m)+Q\sum_{q\le Q}V_q(N)\gg\eta(1-\eta)Q^2N$$

with an absolute implied constant, and its corollary (4), with $Q=\lfloor N^{1/2}\rfloor$, gives $m_0\le N$ and $q_0\le N^{1/2}$ with $q_0^{-1}V_{q_0}(m_0)\gg\eta(1-\eta)N^{1/2}$: some arithmetic progression of common difference at most $N^{1/2}$ inside $[1,N]$ has discrepancy $\gg(\eta(1-\eta))^{1/2}N^{1/4}$. The proof compares upper and lower estimates for the integral of $\sum_{q\le Q}\lvert F(q\alpha)S(\alpha)\rvert^2$, with $S$ the exponential sum of the indicator minus its mean and $F$ a partial geometric sum. The source is carded at roth_1964_remark_concerning_integer_sequences.

Covers. A lower bound on $h(d)$ in Problem 177: no coloring $f:\mathbb N\to\{-1,1\}$ has $\max_{P_d}\lvert\sum_{n\in P_d}f(n)\rvert=O(d^p)$ for any $p<1/2$. Applied to the set of $n\le N$ with $f(n)=1$, whose density is bounded away from $0$ and $1$ when the discrepancy on the progressions of difference $1$ is $o(N)$, the corollary gives a progression with difference $d\le N^{1/2}$ and discrepancy $\gg N^{1/4}\ge d^{1/2}$ up to constants; the site's commentary records the consequence as $h(d)\gg d^{1/2}$, and that inference from Roth's theorem is the site's, not the paper's. The result settles nothing about the order of $h(d)$ beyond this bound.

Depends on. No page of this wiki.

Acceptance. Refereed: the paper is a journal publication in Acta Arithmetica, volume 9, issue 3 (1964), the refereed evidence; the issue carries no month or day, so this page is dated to the first day of that year. The site's curator credits the bound $h(d)\gg d^{1/2}$ to [Ro64] in the problem's commentary, but the site labels the problem OPEN, so that credit is not reviewed evidence. The proof is not checked by this corpus, and nothing is independently reviewed by this project.