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. For positive integers N , q , a {\displaystyle N,q,a} define the expression Q ( N ; q , a ) {\displaystyle Q(N;q,a)} to be the number of perfect squares in the arithmetic progression q n + a {\displaystyle qn+a} , for n = 0 , 1 , … , N − 1 {\displaystyle n=0,1,\ldots ,N-1} , and define Q ( N ) {\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 Q ( N ) = O ( N ) {\displaystyle Q(N)=O({\sqrt {N}})} and in its stronger form that, if N > 6 {\displaystyle N>6} , Q ( N ) = Q ( N ; 24 , 1 ) {\displaystyle Q(N)=Q(N;24,1)} . This progression begins with 1 , 25 , 49 , 73 , 97 , 121 , . . . {\displaystyle 1,25,49,73,97,121,...} and its square terms correspond to indices that are generalized pentagonal numbers. For N = 5 {\displaystyle N=5} , the arithmetic progression 120 n + 49 {\displaystyle 120n+49} contains four squares ( 49 , 169 , 289 , 529 ) {\displaystyle (49,169,289,529)} , so Q ( 5 ) = 4 {\displaystyle Q(5)=4} , whereas 24 n + 1 {\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 Q ( 4 ) = 3 {\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 N {\displaystyle N} , the number of squares must be o ( N ) {\displaystyle o(N)} (little-o notation). This was proven by Endre Szemerédi as a consequence of Szemerédi's theorem on arithmetic progressions. Following Szemerédi's result, the upper bound for Q ( N ) {\displaystyle Q(N)} was progressively improved. Bombieri, Granville, and Pintz established a bound of O ( N 2 3 + o ( 1 ) ) {\displaystyle O\!\left(N^{{\tfrac {2}{3}}+o(1)}\right)} . This was later refined by Bombieri and Zannier to O ( N 3 5 + o ( 1 ) ) {\displaystyle O\!\left(N^{{\tfrac {3}{5}}+o(1)}\right)} . Enrique Gonzalez-Jimenez and Xavier Xarles verified in 2014 that the Strong Rudin's Conjecture holds for all 6 ≤ N ≤ 52 {\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 N {\displaystyle N} where Q ( N ) {\displaystyle Q(N)} is expected to increase (specifically when N = G P k + 1 ≥ 8 {\displaystyle N=GP_{k}+1\geq 8} , where G P k {\displaystyle GP_{k}} is the k {\displaystyle k} -th generalized pentagonal number), the arithmetic progression 24 n + 1 {\displaystyle 24n+1} is the only one, up to equivalence, that achieves the maximum number of squares.
References