Let $P(x;a,b) := \{an+b, 0\leq n \leq x \} $ denote an arithmetic progression. Further let $A(x;a,b)$ denote the number of elements of $P(x;a,b)$ that are squares. It's an old conjecture of Rudin that $A(x;a,b) \ll x^{1/2}$. Less ambitiously, Erdős posed the problem of showing that $A(x;a,b) = o(x)$. This was proven by Szemerédi around 1974 (amusingly the paper is only a few sentences).
Here is Szemerédi's proof: If the theorem was false then we could find arbitrarily large arithmetic progressions composed of at least $\delta>0$ percent squares. Then invoking the 4 case of Szemerédi's (most well-known) theorem we have that there must be a length 4 arithmetic progression consisting of only squares. However, this contradicts an old theorem of Euler.
While this proof is slick, it is natural to want to avoid having to use anything as powerful as Szemerédi's theorem. I recently I ran across the paper "On the Number of Squares in an Arithmetic Progression" by Saburo Uchiyama (Proc. Japan Acad. 52, no. 8 (1976), 431-433). The complete paper is freely available at Project Euclid. The paper claims to give a simple and self-contained solution to Erdős' question (that $A(x;a,b) = o(x)$). In fact, the proof given is so short that I will repost it in its entirety:
- We shall first give another simple and elementary proof of (1). There is no loss in generality in assuming that $a > b$. Every non-negative integer belongs to one and only one arithmetic progression of the form $an+b$ ($n \geqq 0$), where $a$ is fixed and $0 \leqq b < a$. Hence we have $$ \sum_{b=0}^{a-1} A(x;a,b) = [\sqrt{ax + a - 1}]+1 \qquad (x > 0) $$ where $[t]$ denotes the greatest integer not exceeding the real number $t$; this implies that $$ A(x; a, b) \leqq \sqrt{ax + a - 1} + 1 \qquad (x > 0) $$ for any $a$ and $b$ with $a > b \geqq 0$, since we always have $A(x; a, b) \geqq 0$. This clearly proves (1).
We plainly have $A(x; a, b) = 0$ ($x > 0$), if $b$ is a quadratic non-residue ($\operatorname{mod} a$).
Now I don't follow the claim that "This clearly proves (1)." (where (1) is the claim that $A(x;a,b) = o(x)$). Certainly when $a=o(x)$ this gives the desired result, but why does this work when $a$ is large?
Since this is so short and simple (and I have never seen the argument cited anywhere) I am skeptical, however perhaps I am missing something obvious.
(Perhaps, it should be pointed out that there is a more recent approach to the problem that yields better quantitative bounds that goes through Falting's theorem due to Bombieri, Granville and Pintz. In fact, their analysis shows that the case when $a$ is large compared to $x$ is the 'hard case', which raises further suspicion of the above argument.)
