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:

  1. 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.)

  • 2
    $\begingroup$ Isn't $x$ growing but $a$ fixed? On the other hand, the question seems trivial unless you want to the implied constants in $o()$ and $\ll$ to be INDEPENDENT of $a,$ and it certainly seems that the paper does not prove this, for the reason you give. $\endgroup$
    – Igor Rivin
    Mar 30, 2012 at 20:22
  • $\begingroup$ I can't imagine that Erdos whould have posed the problem with $a$ and $b$ fixed, surely he would have been able to prove that himself. However, that must be what Uchiyama is claiming. $\endgroup$
    – Mark Lewko
    Mar 30, 2012 at 20:38
  • 1
    $\begingroup$ What about a lower bound to $A(x;a,b)$? Is anything known? $\endgroup$
    – kodlu
    Mar 9, 2014 at 23:09
  • 1
    $\begingroup$ Obviously, Uchiyama did not understand the true question of Erdös, which is trivial if $a$ is fixed. But if he saw the problem formulated as in this post, he is excusable. Saying that the implied constant is absolute, or something like this, would have help. As it is formulated, we are induced to believe that it may depend on $a,b$: because of your title first, "squares" (plural) in "an arithmetic progression" (singular), as if the arithmetic progression, hence $a$ and $b$, where fixed. $\endgroup$
    – Joël
    Oct 12, 2017 at 15:29
  • 1
    $\begingroup$ Also because of your notation as well $A(x;a,b)$ and not $A(x,a,b)$, as if $a$ and $b$ were parameters (fixed) and not variables. $\endgroup$
    – Joël
    Oct 12, 2017 at 15:30

1 Answer 1


The conjecture of Rudin is about the maximum of $A(x; a,b)$, taken over all values of $a$ and $b$. Not with just keeping $a$ and $b$ fixed and letting $x$ get large. So, like you said, if $a$ is not $o(x)$, the proof of Uchida doesn't go through.

The latest news on this problem (as far as I know) can be found here: E. Bombieri, U. Zannier, A Note on squares in arithmetic progressions, II, Rend. Mat. Acc. Lincei, s. 9, v. 13:69-75 (2002) (link: Wayback Machine).

  • 4
    $\begingroup$ The difference between Uchiyama and Uchida is a mountain versus a rice field. $\endgroup$
    – S. Carnahan
    Mar 31, 2012 at 2:46
  • $\begingroup$ Just to recap: I was aware that both Rudin's and Erdos' problems required uniformity in $a$ and $b$. My question was basically "I don't understand how Uchiyama's argument gives uniformity in $a$." The answer turns out to be: "it doesn't." The statement (in french) of Erdos' problem can be found in bolyai.math-inst.hu/~p_erdos/1963-14.pdf (problem 16). It seems to not be completely clear on the uniformity issue (although its hard to imagine that it never occurred to the author or referee that Erdos was asking for a uniform estimate). $\endgroup$
    – Mark Lewko
    Mar 31, 2012 at 3:05
  • 1
    $\begingroup$ The order of quantifiers in Erdos's statement seems clear enough; since it refers to "une progression" rather than "la progression", it asks for uniformity over progressions. $\endgroup$
    – Terry Tao
    Mar 31, 2012 at 3:29
  • $\begingroup$ @Mark Yeah, sorry for this anticlimactic ending. Thanks for accepting my answer though. My first one! Yay! $\endgroup$
    – Woett
    Apr 1, 2012 at 0:04
  • 1
    $\begingroup$ @Woett This is 10 years later, but you wrote "Uchida" in your answer rather than "Uchiyama". "Da" (or rather, "Ta" 田) is Japanese for "rice field", whereas "Yama" (山) is Japanese for "mountain"! $\endgroup$ Nov 18, 2022 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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