January 01, 1970
Let \(S\subset \{1,2,\ldots,n\}\) be a Sidon set with \(|S|=n^{1/2}+O(n^{1/2-\delta})\) for some fixed \(\delta>0\). This article provides the following expected asymptotic formula \[\sum_{\substack{a\in S\\ a\equiv r\,(\mathrm{mod}\,m)}} a^\ell =\frac{1}{m(\ell+1)}n^{\ell+1/2} +o\left(n^{\ell+1/2}\right),\] where \(m\geq 1\), \(0\leq r<m\), and \(\ell\geq 0\) are three integers. This removes the additional hypothesis in a previous residue-class asymptotic formula by the author. The proof uses the Fourier uniformity of extremal Sidon sets due to Ortega and Prendiville.
A set \(S\subset \mathbb{Z}\) is called a Sidon set if all sums \(a+b\), with \((a,b)\in S^2\) considered as unordered pairs, are distinct. Let \(S_n\) be the largest cardinality of a Sidon subset of \([1,n]\). Throughout the paper, \([1,n]\) denotes the integer interval \(\{1,2,\ldots,n\}\). We use \(X\ll Y\) and \(X=O(Y)\) interchangeably; the dependence of implied constants is stated in the relevant results and proofs. The classical upper bound of Erdős and Turán [1], together with Singer’s construction [2] and prime-gap estimates of Baker, Harman and Pintz [3], gives the standard near-square-root size estimate \[\label{eq:maximal-sidon-size} S_n=n^{1/2}+O\left(n^{21/80}\right).\tag{1}\]
Uniform distribution questions for dense Sidon sets have a long history. Lindström [4] proved well distribution in residue classes, and Kolountzakis [5] obtained quantitative refinements for dense sets of integers with distinct sums. Cilleruelo’s work on gaps in dense Sidon sets [6] is another important input in this circle of ideas; in particular, it is used by Ortega and Prendiville in the improved Fourier-uniformity estimate recalled below.
In [7], the author proved that if \(S\subset[1,n]\) is a Sidon set with \(|S|=S_n\), then for every \(\varepsilon>0\), \[\sum_{a\in S}a =\frac{1}{2}n^{3/2} +O\left(n^{111/80+\varepsilon}\right).\] The same paper also considered sums in residue classes. For fixed \(m\geq 1\) and \(0\leq r<m\), it was shown conditionally that \[\sum_{\substack{a\in S\\ a\equiv r\,(\mathrm{mod}\,m)}}a \sim \frac{1}{2m}n^{3/2}.\] The condition imposed there was a lower bound for \(|S\cap[1,k]|\) throughout a long terminal range of \(k\). As observed by Balasubramanian and Dutta [8], this condition is rarely compatible with the expected distribution of a dense Sidon set. The final remark of [7] explicitly asks whether the residue-class asymptotic remains true after removing this additional condition. One purpose of the present note is to answer this question unconditionally, in fact for all fixed power sums.
The author’s subsequent paper [9] developed these weighted summation questions further. It proved, for \[S=\{a_1<a_2<\cdots<a_t\}\subset[1,n],\] that for every positive integer \(\ell\), \[\sum_{i=1}^t a_i^\ell =\frac{t}{\ell+1}n^\ell +O\left(n^{\ell+3/8}\right)\] whenever \[t\geq n^{1/2}-n^{1/4}.\] In particular, for \(|S|=S_n\), this gives \[\sum_{a\in S}a =\frac{1}{2}n^{3/2} +O\left(n^{221/160}\right),\] which slightly improves the error term in [7]. The same paper also proved the almost-all estimate \[\sum_{a\in S}a =\frac{1}{2}n^{3/2} +O\left(n^{11/8}\log n\right)\] for all \(n\leq N\), with at most \[O\left(\frac{N}{(\log N)^{7/19}}\right)\] exceptions, and established asymptotic formulae for the more general weighted sums \[\sum_{i=1}^t i^s a_i^\ell.\] One of the results below, Theorem [2](#thm:rank-weighted-local){reference-type=“ref” reference=“thm:rank-weighted-local”}, gives a residue-class and local analogue of these weighted sums.
Balasubramanian and Dutta [8] later introduced a direct formula for the \(m\)-th element of a dense finite Sidon set. As consequences of their formula, they recovered some results of [7], [9] by a different argument and improved the almost-all error term from [9], using a large-prime-gap estimate of Heath-Brown [10]: for every \(\varepsilon>0\), \[\sum_{a\in S}a =\frac{1}{2}n^{3/2} +O\left(n^{11/8}\right)\] for all \(n\leq N\), with at most \[O\left(N^{4/5+\varepsilon}\right)\] exceptions. Their observation about the conditional residue-class theorem in [7] is one motivation for the present note. We use the same prime-gap device below to sharpen the residue-class error term for almost all values of \(n\).
We revisit the residue-class problem using a different input: Fourier uniformity of extremal Sidon sets, due to Ortega and Prendiville [11]. This gives a short unconditional proof of the residue-class power-sum asymptotic. In fact, the same argument gives a more transparent local statement: a dense Sidon set has the expected density on every finite arithmetic progression.
For a Sidon set \(S\subset[1,n]\), put \[\label{eq:def-phi} \Phi(S,n)= n^{1/2} \left( \left|1-\frac{|S|}{n^{1/2}}\right| +n^{-1/4} \right)^{1/2}.\tag{2}\] The new results are the following asymptotic formulae.
Theorem 1. Let \(\ell\geq 0\) be fixed, and let \(S\subset[1,n]\) be a Sidon set. Then, for every finite arithmetic progression \(P\subset[1,n]\), \[\label{eq:main-asymptotic} \sum_{a\in S\cap P} a^\ell =\frac{|S|}{n}\sum_{a\in P}a^\ell +O\left(n^\ell\Phi(S,n)\log(2n)\right).\qquad{(1)}\] The implied constant depends only on \(\ell\).
Corollary 1. Let \(m\geq 1\), \(0\leq r<m\), and \(\ell\geq 0\) be fixed integers. Let \(S\subset[1,n]\) be a Sidon set. Then, uniformly for all intervals of integers \(I\subset[1,n]\), \[\label{eq:local-residue} \sum_{\substack{a\in S\cap I\\ a\equiv r\,(\mathrm{mod}\,m)}} a^\ell = \frac{|S|}{n} \sum_{\substack{a\in I\\ a\equiv r\,(\mathrm{mod}\,m)}} a^\ell +O\left(n^\ell\Phi(S,n)\log(2n)\right).\qquad{(2)}\] The implied constant depends only on \(\ell\) and \(m\).
For the maximal cases below, we recall the standard estimate \[S_n=n^{1/2}+O\left(n^{21/80}\right),\] already stated in 1 . This is the only additional input needed to pass from the general residue-class formula to maximal Sidon sets. The next corollary contains the unconditional maximal-Sidon-set form of the residue-class result asked for in the final remark of [7].
Corollary 2. Let \(m\geq 1\), \(0\leq r<m\), and \(\ell\geq 0\) be fixed integers. Let \(S\subset[1,n]\) be a Sidon set. Then \[\label{eq:residue-effective} \sum_{\substack{a\in S\\ a\equiv r\,(\mathrm{mod}\,m)}} a^\ell =\frac{|S|}{m(\ell+1)}n^\ell +O\left(n^\ell\Phi(S,n)\log(2n)\right).\qquad{(3)}\] The implied constant depends only on \(\ell\) and \(m\). In particular, if \(S\) is maximal, that is, \(|S|=S_n\), then \[\sum_{\substack{a\in S\\ a\equiv r\,(\mathrm{mod}\,m)}} a =\frac{1}{2m}n^{3/2} +O\left(n^{221/160}\log n\right),\] where the implied constant depends only on \(m\).
In particular, if \(|S|\sim n^{1/2}\) and \(\Phi(S,n)\log(2n)=o(n^{1/2})\), then the expected asymptotic formula in each fixed residue class follows. Under the hypothesis \(|S|\geq n^{1/2}-n^{1/4}\), the same corollary gives the error term \(O(n^{\ell+3/8}\log n)\), with the implied constant depending only on \(\ell\) and \(m\).
The next theorem is a rank-weighted generalization of Theorem [1](#thm:main){reference-type=“ref” reference=“thm:main”}, giving the same local distribution principle after weighting \(a_i\in S\) by \(i^s a_i^\ell\).
Theorem 2. Let \(m\geq 1\), \(0\leq r<m\), and \(s,\ell\geq 0\) be fixed integers. Let \[S=\{a_1<a_2<\cdots<a_t\}\subset[1,n]\] be a Sidon set. Then, uniformly for all intervals of integers \(I\subset[1,n]\), \[\label{eq:rank-local} \sum_{\substack{1\leq i\leq t\\ a_i\in I\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell = \frac{t^{s+1}}{n^{s+1}} \sum_{\substack{a\in I\\ a\equiv r\,(\mathrm{mod}\,m)}}a^{s+\ell} +O\left(t^s n^\ell\Phi(S,n)\log(2n)\right).\qquad{(4)}\] The implied constant depends only on \(s\), \(\ell\), and \(m\). In particular, \[\label{eq:rank-residue} \sum_{\substack{1\leq i\leq t\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell = \frac{t^{s+1}}{m(s+\ell+1)}n^\ell +O\left(t^s n^\ell\Phi(S,n)\log(2n)\right).\qquad{(5)}\]
Corollary 3. Let \(m\geq 1\), \(0\leq r<m\), and \(s,\ell\geq 0\) be fixed integers. Let \[S=\{a_1<a_2<\cdots<a_t\}\subset[1,n]\] be a Sidon set with \(t=S_n\). Then \[\label{eq:maximal-rank-residue} \sum_{\substack{1\leq i\leq t\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell =\frac{1}{m(s+\ell+1)}n^{\ell+(s+1)/2} +O\left(n^{\ell+s/2+61/160}\log n\right).\qquad{(6)}\] The implied constant depends only on \(s\), \(\ell\), and \(m\).
The following almost-all theorem follows by combining Theorem [2](#thm:rank-weighted-local){reference-type=“ref” reference=“thm:rank-weighted-local”} with the prime-gap input used by Balasubramanian and Dutta [8].
Theorem 3. Let \(N\geq 2\) and \(\varepsilon>0\). For all but \(O(N^{4/5+\varepsilon})\) integers \(n\leq N\), the following assertion holds: for any fixed integers \(m\geq 1\), \(0\leq r<m\), and \(s,\ell\geq 0\), if \[S=\{a_1<a_2<\cdots<a_t\}\subset[1,n]\] is a Sidon set with \(t=S_n\), then \[\label{eq:almost-all-rank-residue} \sum_{\substack{1\leq i\leq t\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell =\frac{1}{m(s+\ell+1)}n^{\ell+(s+1)/2} +O\left(n^{\ell+s/2+3/8}\log n\right).\qquad{(7)}\] The implied constant in the formula depends only on \(s\), \(\ell\), and \(m\); the exceptional-set constant may also depend on \(\varepsilon\). In particular, for \(s=0\) and \(\ell=1\), \[\sum_{\substack{a\in S\\ a\equiv r\,(\mathrm{mod}\,m)}} a =\frac{1}{2m}n^{3/2} +O\left(n^{11/8}\log n\right),\] where the implied constant depends only on \(m\).
Acknowledgement and AI Disclosure. The author would like to thank the support from the CSC program. This paper records an attempt of the author’s research on interacting with OpenAI Codex. I first suggested OpenAI Codex to study the proofs of my former articles [7], [9]. Then I asked OpenAI Codex to give an unconditional proof of the second asymptotic formula of Corollary [2](#cor:residue-effective){reference-type=“ref” reference=“cor:residue-effective”}. OpenAI Codex quickly recognized that the Fourier uniformity of extremal Sidon sets due to Ortega and Prendiville [11] could be applied here. Inspiring by this, I suggested further OpenAI Codex to extend its results to the more general power and rank-weighted sums introduced in [9]. It then led to a slightly more general Theorem [2](#thm:rank-weighted-local){reference-type=“ref” reference=“thm:rank-weighted-local”}. Next, I suggested OpenAI Codex to study the article of Balasubramanian and Dutta [8], and asked it to obtain an almost-all result involving the improvements of error terms of the asymptotic formulae. OpenAI Codex gave me the correct result which was now recorded as Theorem [3](#thm:maximal-almost-all){reference-type=“ref” reference=“thm:maximal-almost-all”}.
As a summary, I think the proofs of the main results are not too difficult, given the knowledge of the Fourier uniformity results from Ortega and Prendiville (see Lemma [1](#lem:fourier){reference-type=“ref” reference=“lem:fourier”} and Lemma [2](#lem:progression-l1){reference-type=“ref” reference=“lem:progression-l1”} below). However, starting from the problem itself, finding suitable and useful results, and then connecting them with the problems do not seem very obvious.
The author takes full responsibility for all proofs and claims in the article.
We use the following consequence of Ortega and Prendiville’s improved Fourier uniformity theorem for extremal Sidon sets [11]. We write \(\mathbb{T}=\mathbb{R}/\mathbb{Z}\), identifying it with \([0,1)\) in integrals. For a set \(A\subset\mathbb{Z}\), let \(1_A\) denote its indicator function. For a function \(G:\mathbb{T}\to\mathbb{C}\), put \(\|G\|_\infty=\sup_{\alpha\in\mathbb{T}}|G(\alpha)|\). For a finitely supported function \(f:\mathbb{Z}\to\mathbb{C}\), write \[\widehat f(\alpha)=\sum_{x\in\mathbb{Z}}f(x)\mathrm{e}^{2\pi i\alpha x} \qquad (\alpha\in\mathbb{T}).\]
Lemma 1. Let \(S\subset[1,n]\) be a Sidon set. Then \[\left\| \widehat{1_S} -\frac{|S|}{n}\widehat{1_{[1,n]}} \right\|_\infty \ll \Phi(S,n).\]
Proof. Ortega and Prendiville proved [11] that \[\label{eq:op-improved-fourier} \left\| \widehat{1_S} -\frac{|S|}{n}\widehat{1_{[1,n]}} \right\|_\infty \ll n^{1/2} \left( \left|1-\frac{|S|}{n^{1/2}}\right| +n^{-1/4} \right)^{1/2}.\tag{3}\] This is precisely the claimed bound. ◻
Lemma 2. Let \(P\subset[1,n]\) be a finite arithmetic progression. Then \[\int_{\mathbb{T}}|\widehat{1_P}(\alpha)|\,d\alpha\ll \log(2n).\]
Proof. If \(P\) is empty or consists of one point, the estimate is immediate. Otherwise, the result follows from the standard progression estimate of Ortega and Prendiville [11], since \(|P|\leq n\). ◻
Lemma 3. Let \(S\subset[1,n]\) be a Sidon set. Then, uniformly for every finite arithmetic progression \(P\subset[1,n]\), \[|S\cap P|=\frac{|S|}{n}|P|+O\left(\Phi(S,n)\log(2n)\right).\] The implied constant is absolute.
Proof. Put \[h=1_S-\frac{|S|}{n}1_{[1,n]}.\] Then \[|S\cap P|-\frac{|S|}{n}|P| = \sum_{x\in P}h(x) = \sum_{x\in\mathbb{Z}}1_P(x)h(x).\] For finitely supported functions on \(\mathbb{Z}\), Fourier orthogonality gives \[\sum_{x\in\mathbb{Z}}1_P(x)h(x) = \int_{\mathbb{T}}\widehat{1_P}(\alpha)\widehat h(-\alpha)\,d\alpha.\] Since \(\widehat h=\widehat{1_S}-\frac{|S|}{n}\widehat{1_{[1,n]}}\), we obtain \[\sum_{x\in\mathbb{Z}}1_P(x)h(x) = \int_{\mathbb{T}}\widehat{1_P}(\alpha) \left( \widehat{1_S} -\frac{|S|}{n}\widehat{1_{[1,n]}} \right)(-\alpha)\,d\alpha.\] Combining Lemma [2](#lem:progression-l1){reference-type=“ref” reference=“lem:progression-l1”} with Lemma [1](#lem:fourier){reference-type=“ref” reference=“lem:fourier”} gives \[|S\cap P|-\frac{|S|}{n}|P| \ll \Phi(S,n)\log(2n).\] The bound is uniform in \(P\), as required. ◻
Proof of . Theorem 1] Let \[E=\Phi(S,n)\log(2n).\] Let \(P\subset[1,n]\) be a finite arithmetic progression. For \(1\leq k\leq n\), put \[P(k)=P\cap[1,k],\qquad A_P(k)=|S\cap P(k)|,\qquad R_P(k)=|P(k)|.\] Since \(P(k)\) is again a finite arithmetic progression, Lemma [3](#lem:progression-discrepancy){reference-type=“ref” reference=“lem:progression-discrepancy”} gives, uniformly in \(k\), \[A_P(k)=\frac{|S|}{n}R_P(k)+O(E).\] For \(\ell\geq 1\), Abel summation gives \[\begin{align} \sum_{a\in S\cap P}a^\ell&=\sum_{k=1}^{n}\big(A_P(k)-A_P(k-1)\big)k^\ell\\ &=n^\ell A_P(n) -\sum_{k=1}^{n-1}A_P(k)\left((k+1)^\ell-k^\ell\right). \end{align}\] Substituting the estimate for \(A_P(k)\) into Abel summation, we get \[\label{eq:weighted-reduction} \begin{align} \sum_{a\in S\cap P}a^\ell &= \frac{|S|}{n} \left( n^\ell R_P(n) -\sum_{k=1}^{n-1}R_P(k)\left((k+1)^\ell-k^\ell\right) \right) +O(n^\ell E) \\ &= \frac{|S|}{n} \sum_{a\in P}a^\ell +O(n^\ell E). \end{align}\tag{4}\] This proves ?? for \(\ell\geq 1\), with the implied constant depending only on \(\ell\). The case \(\ell=0\) is exactly Lemma [3](#lem:progression-discrepancy){reference-type=“ref” reference=“lem:progression-discrepancy”}. ◻
Proof of . Corollary 1] For an interval \(I\subset[1,n]\), the set \[\{a\in I:a\equiv r\,(\mathrm{mod}\,m)\}\] is a finite arithmetic progression. Applying Theorem [1](#thm:main){reference-type=“ref” reference=“thm:main”} to this progression gives the claim. ◻
Proof of . Corollary 2] Apply Theorem [1](#thm:main){reference-type=“ref” reference=“thm:main”} to \[P=\{a\in[1,n]:a\equiv r\,(\mathrm{mod}\,m)\}.\] The elementary estimate for sums of powers in a fixed residue class is \[\label{eq:residue-power-reference} \sum_{\substack{1\leq a\leq n\\ a\equiv r\,(\mathrm{mod}\,m)}}a^\ell =\frac{1}{m(\ell+1)}n^{\ell+1}+O(n^\ell).\tag{5}\] Multiplying by \(|S|/n\), the extra error is \(O(|S|n^{\ell-1})\), which is absorbed by \(O(n^\ell\Phi(S,n)\log(2n))\), since \(|S|\leq n\) and \(\Phi(S,n)\gg n^{3/8}\). Together with 5 , this proves ?? for \(\ell\geq 1\). The case \(\ell=0\) follows similarly from \(|P|=n/m+O(1)\). If \(|S|=S_n\), then 1 gives \(|S|=n^{1/2}+O(n^{21/80})\). Then \[\Phi(S,n) \ll n^{1/2}\left(n^{-19/80}+n^{-1/4}\right)^{1/2} \ll n^{61/160}.\] Taking \(\ell=1\) in ?? and replacing \(|S|\) in the main term therefore gives the stated maximal special case. ◻
Proof of . Theorem 2] Put \[E=\Phi(S,n)\log(2n)\] and \[P=\{a\in I:a\equiv r\,(\mathrm{mod}\,m)\}.\] The set \(P\) is a finite arithmetic progression. For \(a_i\in S\), the index \(i\) is the initial counting function of \(S\) at \(a_i\). Hence Lemma [3](#lem:progression-discrepancy){reference-type=“ref” reference=“lem:progression-discrepancy”}, applied to the interval \([1,a_i]\), gives \[\label{eq:index-approx} i=\frac{t}{n}a_i+O(E).\tag{6}\] If \(s=0\), the local formula is exactly Corollary [1](#cor:local-residue){reference-type=“ref” reference=“cor:local-residue”}. Assume now that \(s\geq 1\). Put \(y_i=t a_i/n\). Since \(0\leq i,y_i\leq t\), we have \[i^s-y_i^s=(i-y_i)\sum_{j=0}^{s-1}i^{s-1-j}y_i^j.\] Together with 6 , this gives \[\label{eq:rank-power-approx} i^s=\left(\frac{t}{n}a_i\right)^s+O_s(t^{s-1}E).\tag{7}\] Therefore \[\label{eq:rank-weighted-reduction} \sum_{\substack{1\leq i\leq t\\ a_i\in I\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell = \frac{t^s}{n^s} \sum_{a\in S\cap P}a^{s+\ell} +O_s(t^s n^\ell E).\tag{8}\] Applying Corollary [1](#cor:local-residue){reference-type=“ref” reference=“cor:local-residue”} with \(\ell\) replaced by \(s+\ell\), we get \[\label{eq:rank-local-power-input} \sum_{a\in S\cap P}a^{s+\ell} = \frac{t}{n}\sum_{a\in P}a^{s+\ell} +O_{s,\ell,m}(n^{s+\ell}E).\tag{9}\] Combining 8 and 9 proves ?? .
Taking \(I=[1,n]\) and using \[\label{eq:rank-residue-power-reference} \sum_{\substack{1\leq a\leq n\\ a\equiv r\,(\mathrm{mod}\,m)}}a^{s+\ell} =\frac{1}{m(s+\ell+1)}n^{s+\ell+1}+O_{s,\ell,m}(n^{s+\ell})\tag{10}\] gives ?? . The extra term obtained after multiplication by \(t^{s+1}/n^{s+1}\) is \(O(t^{s+1}n^{\ell-1})\), which is absorbed by the stated error term. ◻
Proof of . Corollary 3] By 1 , if \(t=S_n\), then \[\Phi(S,n) \ll n^{1/2}\left(n^{-19/80}+n^{-1/4}\right)^{1/2} \ll n^{61/160}.\] Substituting this bound into Theorem [2](#thm:rank-weighted-local){reference-type=“ref” reference=“thm:rank-weighted-local”}, with \(I=[1,n]\), gives \[\label{eq:maximal-rank-before-t-replacement} \sum_{\substack{1\leq i\leq t\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell = \frac{t^{s+1}}{m(s+\ell+1)}n^\ell +O\left(n^{\ell+s/2+61/160}\log n\right).\tag{11}\] Finally, \[\label{eq:maximal-t-power} t^{s+1}=n^{(s+1)/2}+O_s\left(n^{s/2+21/80}\right),\tag{12}\] again by 1 . This replacement error is absorbed by the error term in 11 . Combining 11 and 12 gives ?? . ◻
Lemma 4. Let \(N\geq 2\) and \(\varepsilon>0\). For all but \(O(N^{4/5+\varepsilon})\) integers \(n\leq N\), one has \[S_n=n^{1/2}+O\left(n^{1/4}\right).\] The exceptional-set constant depends on \(\varepsilon\), and the implied constant in the displayed estimate is absolute.
Proof. The upper bound \(S_n\leq n^{1/2}+O(n^{1/4})\) is the classical theorem of Erdős and Turán. We prove the corresponding lower bound for almost all \(n\), following the prime-gap argument used by Balasubramanian and Dutta [8].
Let \(p_j\) be the \(j\)-th prime and put \(g_j=p_{j+1}-p_j\). Heath-Brown’s theorem [10] gives, for every \(\varepsilon>0\), \[\label{eq:heath-brown-large-gaps} \sum_{\substack{p_j\leq x\\ g_j\geq p_j^{1/2}}}g_j \ll x^{3/5+\varepsilon},\tag{13}\] with the implied constant depending on \(\varepsilon\). If \[p_j^2-1\leq n<p_{j+1}^2-1\] and \(g_j<p_j^{1/2}\), Singer’s construction gives \(S_n\geq p_j\), and also \[n^{1/2}-p_j< p_{j+1}-p_j=g_j<p_j^{1/2}\ll n^{1/4}.\] Thus \(S_n\geq n^{1/2}-O(n^{1/4})\) for all such \(n\).
It remains to count the \(n\leq N\) lying in intervals belonging to a bad gap \(g_j\geq p_j^{1/2}\). Their number is at most \[\sum_{\substack{p_j\leq \sqrt{N+1}\\ g_j\geq p_j^{1/2}}} \left(p_{j+1}^2-p_j^2\right) \ll \sqrt N \sum_{\substack{p_j\leq \sqrt{N+1}\\ g_j\geq p_j^{1/2}}}g_j \ll N^{4/5+\varepsilon},\] where Bertrand’s postulate is used in the middle estimate and 13 is used in the final estimate. The final implied constant depends on \(\varepsilon\). This proves the lemma. ◻
Proof of . Theorem 3] For all \(n\leq N\) outside the exceptional set in Lemma [4](#lem:almost-all-size){reference-type=“ref” reference=“lem:almost-all-size”}, a maximal Sidon set satisfies \[\left|1-\frac{|S|}{n^{1/2}}\right| \ll n^{-1/4}.\] Hence \(\Phi(S,n)\ll n^{3/8}\). Applying Theorem [2](#thm:rank-weighted-local){reference-type=“ref” reference=“thm:rank-weighted-local”}, with \(I=[1,n]\), gives \[\label{eq:almost-all-rank-before-t-replacement} \sum_{\substack{1\leq i\leq t\\ a_i\equiv r\,(\mathrm{mod}\,m)}} i^s a_i^\ell = \frac{t^{s+1}}{m(s+\ell+1)}n^\ell +O\left(n^{\ell+s/2+3/8}\log n\right).\tag{14}\] Since \(t=n^{1/2}+O(n^{1/4})\), we may replace \(t^{s+1}\) by \(n^{(s+1)/2}\) in the main term. The error introduced by this replacement is \(O_s(n^{\ell+s/2+1/4})\), and is absorbed by the error term in 14 . This proves ?? , and the last display in the statement is the case \(s=0\) and \(\ell=1\). ◻
Remark 4. The proof gives more than the displayed asymptotic formula. It shows that both the residue-class power-sum problem and its rank-weighted analogue are controlled by a uniform estimate for the discrepancy of \(S\) on finite arithmetic progressions. Any improvement in the Fourier-uniformity exponent for extremal Sidon sets would immediately improve the error term in Theorem [1](#thm:main){reference-type=“ref” reference=“thm:main”} and Theorem [2](#thm:rank-weighted-local){reference-type=“ref” reference=“thm:rank-weighted-local”}; the almost-all improvement in Theorem [3](#thm:maximal-almost-all){reference-type=“ref” reference=“thm:maximal-almost-all”} instead comes from improving the size defect of maximal Sidon sets for almost all \(n\).