👁 Logo

Forum Inbox Favourites Tags

Forum

A problem of Erdős and Sárközy.

van Doorn has sent the following argument which shows\[\lvert A\rvert \leq (0.108\cdots+o(1))N.\]The condition implies, in particular, that $a^2+1$ is divisible by $p^2$ for some prime $p$ for all $a\in A$. Furthermore, $a^2+1\equiv 0\pmod{p^2}$ has either $2$ or $0$ solutions, according to whether $p\equiv 1\pmod{4}$ or $p\equiv 3\pmod{4}$. It follows that every $a\in A$ belongs to one of $2$ residue classes for some prime $p\equiv 1\pmod{4}$, and hence, as $N\to \infty$,\[\frac{\lvert A\rvert}{N}\leq 2\sum_{p\equiv 1\pmod{4}}\frac{1}{p^2}\approx 0.108.\]Weisenberg has noted that this proof in fact gives the slightly better constant of $\approx 0.105$ (see the comments section).

This was solved for all sufficiently large $N$ by Sawhney in this note. In fact, Sawhney proves something slightly stronger, that there exists some constant $c>0$ such that if $\lvert A\rvert \geq (\frac{1}{25}-c)N$ and $N$ is large then $A$ is contained in either $\{ n\equiv 7\pmod{25}\}$ or $\{n\equiv 18\pmod{25}\}$.

See also [844].

View the LaTeX source

This page was last edited 06 December 2025. View history

External data from the database - you can help update this
Formalised statement? Yes

Likes this problem	None
Interested in collaborating	None
Currently working on this problem	None
This problem looks difficult	None
This problem looks tractable	TerenceTao, BorisAlexeev
The results on this problem could be formalisable	None
I am working on formalising the results on this problem	None