Rudin's conjecture

Unsolved problem in mathematics

What is the upper bound for the number of squares in finite arithmetic progressions?

More unsolved problems in mathematics

Rudin's conjecture is a mathematical conjecture in additive combinatorics and elementary number theory about an upper bound for the number of squares in finite arithmetic progressions. The conjecture, which has applications in the theory of trigonometric series, was first stated by Walter Rudin in his 1960 paper Trigonometric series with gaps. ^{[1] [2] [3]}

For positive integers ${\displaystyle N,q,a}$ define the expression ${\displaystyle Q(N;q,a)}$ to be the number of perfect squares in the arithmetic progression ${\displaystyle qn+a}$, for ${\displaystyle n=0,1,\ldots ,N-1}$, and define ${\displaystyle Q(N)}$ to be the maximum of the set {Q(N; q, a) : q, a ≥ 1} . The conjecture asserts (in big O notation) that ${\displaystyle Q(N)=O({\sqrt {N}})}$ and in its stronger form that, if ${\displaystyle N>6}$, ${\displaystyle Q(N)=Q(N;24,1)}$. ^[3] This progression begins with ${\displaystyle 1,25,49,73,97,121,...}$ and its square terms correspond to indices that are generalized pentagonal numbers. For ${\displaystyle N=5}$, the arithmetic progression ${\displaystyle 120n+49}$ contains four squares ${\displaystyle (49,169,289,529)}$, so ${\displaystyle Q(5)=4}$, whereas ${\displaystyle 24n+1}$ only contains three squares in its first five terms.

Background and partial results

The problem of finding squares in arithmetic progressions is famously connected to Fermat, who proved that no four squares can be in a non-constant arithmetic progression. This result is equivalent to stating that ${\displaystyle Q(4)=3}$. The general question of bounding the number of squares led to a conjecture by Paul Erdős that for any arithmetic progression of length ${\displaystyle N}$, the number of squares must be ${\displaystyle o(N)}$ (little-o notation). This was proven by Endre Szemerédi as a consequence of Szemerédi's theorem on arithmetic progressions. ^[3]

Following Szemerédi's result, the upper bound for ${\displaystyle Q(N)}$ was progressively improved. Bombieri, Granville, and Pintz established a bound of ${\displaystyle O\!\left(N^{{\tfrac {2}{3}}+o(1)}\right)}$. ^[4] This was later refined by Bombieri and Zannier to ${\displaystyle O\!\left(N^{{\tfrac {3}{5}}+o(1)}\right)}$. ^[5]

Enrique Gonzalez-Jimenez and Xavier Xarles verified in 2014 that the Strong Rudin's Conjecture holds for all ${\displaystyle 6\leq N\leq 52}$. Based on this evidence, they proposed a "Super-Strong Rudin's Conjecture", which states that for specific values of ${\displaystyle N}$ where ${\displaystyle Q(N)}$ is expected to increase (specifically when ${\displaystyle N=GP_{k}+1\geq 8}$, where ${\displaystyle GP_{k}}$ is the ${\displaystyle k}$-th generalized pentagonal number), the arithmetic progression ${\displaystyle 24n+1}$ is the only one, up to equivalence, that achieves the maximum number of squares. ^[3]

References

1. Cilleruelo, Javier; Granville, Andrew (2007). "Lattice points on circles, squares in arithmetic progressions and sumsets of squares". In Granville, Andrew; Nathanson, Melvyn Bernard; Solymosi, József (eds.). Additive combinatorics. CRM Proceedings & Lecture Notes, vol. 43. American Mathematical Society. pp. 241–262. ISBN   978-0-8218-7039-6. arXiv.org preprint
2. Rudin, Walter (1960). "Trigonometric series with gaps". Journal of Mathematics and Mechanics. 9 (2): 203–227. JSTOR   24900534.
3. González-Jiménez, Enrique; Xarles, Xavier (2014). "On a conjecture of Rudin on squares in arithmetic progressions". LMS Journal of Computation and Mathematics. 17 (1): 58–76. arXiv: 1301.5122 . doi:10.1112/S1461157013000259.
4. Bombieri, Enrico; Granville, Andrew; Pintz, János (1992). "Squares in arithmetic progressions". Duke Mathematical Journal. 66 (3): 369–385. doi:10.1215/S0012-7094-92-06612-9.
5. Bombieri, Enrico; Zannier, Umberto (2002). "A note on squares in arithmetic progressions. II". Rendiconti Lincei - Matematica e Applicazioni. 13 (2): 69–75. MR   1949479.