# Squares in an Arithmetic Progession

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, Erdos posed the problem of showing that $A(x;a,b) = o(x)$. This was proven by Szemeredi around 1974 (amusingly the paper is only a few sentences).

Here is Szemeredi'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 Szemeredi'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 Szemeredi's theorem. I recently I ran across the paper "On the Number of Squares in an Arithmetic Progression" by Saburo Uchiyama (Proc. Japan Acad. Volume 52, Number 8 (1976), 431-433.) The complete paper is freely available here. The paper claims to give a simple and self-contained solution to Erdos' question (that $A(x;a,b) = o(x)$). In fact, the proof given is so short that I will repost it in its entirety:

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

-
Picture link is broken – Felipe Voloch Mar 30 '12 at 20:01
Should be fixed, let me know if it isn't. – Mark Lewko Mar 30 '12 at 20:13
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. – Igor Rivin Mar 30 '12 at 20:22
Picture is up now. BTW, you are clearly correct. – Felipe Voloch Mar 30 '12 at 20:22
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. – Mark Lewko Mar 30 '12 at 20:38

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: http://www.lincei.it/pubblicazioni/rendicontiFMN/rol/pdf/M2002.02.01.pdf
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). – Mark Lewko Mar 31 '12 at 3:05
The text passage discusses a mathematical conjecture and proof related to the number of squares in an arithmetic progression. It mentions a proof by Szemeredi and a paper by Uchiyama that claims to provide a simpler solution to a related problem. The author expresses skepticism about a specific claim in Uchiyama's paper.
no_question

the passage does not contain a direct mathematical question or calculation. it describes a mathematical problem and some proofs, but does not pose a question for the reader to solve.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Squares in an Arithmetic Progession

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, Erdos posed the problem of showing that $A(x;a,b) = o(x)$. This was proven by Szemeredi around 1974 (amusingly the paper is only a few sentences).

Here is Szemeredi'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 Szemeredi'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 Szemeredi's theorem. I recently I ran across the paper "On the Number of Squares in an Arithmetic Progression" by Saburo Uchiyama (Proc. Japan Acad. Volume 52, Number 8 (1976), 431-433.) The complete paper is freely available here. The paper claims to give a simple and self-contained solution to Erdos' question (that $A(x;a,b) = o(x)$). In fact, the proof given is so short that I will repost it in its entirety:

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

-
Picture link is broken – Felipe Voloch Mar 30 '12 at 20:01
Should be fixed, let me know if it isn't. – Mark Lewko Mar 30 '12 at 20:13
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. – Igor Rivin Mar 30 '12 at 20:22
Picture is up now. BTW, you are clearly correct. – Felipe Voloch Mar 30 '12 at 20:22
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. – Mark Lewko Mar 30 '12 at 20:38

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: http://www.lincei.it/pubblicazioni/rendicontiFMN/rol/pdf/M2002.02.01.pdf
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). – Mark Lewko Mar 31 '12 at 3:05
user
The text passage discusses a mathematical conjecture and proof related to the number of squares in an arithmetic progression. It mentions a proof by Szemeredi and a paper by Uchiyama that claims to provide a simpler solution to a related problem. The author expresses skepticism about a specific claim in Uchiyama's paper.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question or calculation. It describes a mathematical problem and some proofs, but does not pose a question for the reader to solve.