Equidistribution of Sidon Sums in Residue Classes II

In the last post, we introduced what we are trying to achieve in this post. However, we will write this note in a way that is independent of the last one.

A set of positive integers $A\subset \mathbb N$ is called a Sidon Set if the equation $a+b=c+d$ does not have any non-trivial solutions in $A$. A Sidon subset $A\subset [n]:=\{1,2,\dots , n\}$ is called dense (or extremal) if $\left\lvert A\right\rvert = \max \left\lvert S\right\rvert$ where the maximum is taken over all Sidon subsets of $[n]$. If $A\subset [n]$ is a dense Sidon set with $|A|=n^{1/2}-L$, then $-n^{\frac 14}\le L\ll n^{\frac{21}{80}}$ (see this and this for a proof).

It is well known that dense Sidon sets are surprisingly symmetric in profound ways. For example, it is known that they are uniformly distributed in intervals and well distributed in residue classes. In a previous work, Ding asked whether the sums of elements of a dense Sidon set over residue classes are also equidistributed. We will prove a stronger result here.

Take a dense Sidon set $A\subset [N]:=\{1,2,\dots, N\}$ with $|A| = N^{1/2}-L^\prime$ and $L=\max\{0,L^\prime\}\le N^{\frac{21}{80}}$. For a fixed $k\in \mathbb N$ and some $m\in \mathbb N$, define

\begin{align*} &S^{(k)} := \sum_{a\in A} a^k\\ &S_b^{(k)} := \sum_{\substack{a\in A\\}} a^k\cdot \mathbf{1}_{\{a\,\equiv\, b\,\pmod m\}} \end{align*}

for each $b\in \{0, 1, 2,\dots , m-1\}$.

For $f:\mathbb Z\to\mathbb C$ supported on $[N]$, we define the Fourier transform

$$\widehat f(\beta):=\sum_{n\in\mathbb Z} f(n)e(\beta n)$$

and for $X\in\{0,1,\dots,N\}$, consider the one-sided Dirichlet kernel

$$D_X(\theta):=\sum_{n=1}^{X} e(\theta n)$$

where $e(t) := e^{2\pi it}$. Additionally, we let $\mathbb T := \mathbb R / \mathbb Z$ equipped with the Haar measure.

We will use the following results in our proof.

Theorem A [Ortega-Prendiville] : We have

$$\left\|\widehat{\mathbf 1_A} - \frac{|A|}{N}\,\widehat{\mathbf 1_{[N]}}\right\|_{\infty} \ll\ \sqrt N\, \left(\left|\frac{|A|}{\sqrt N}-1\right| + N^{-\frac 14}\right)^{\frac 12}$$

for a Sidon set $S\subset [N]$.

Theorem B [Balasubramanian-Dutta, Ding] : Let $A=\left\{a_1,\dots ,a_{|A|}\right\}\subset [n]$ be a Sidon set so that $|A|=n^{1/2}-L^\prime$. Then,

$$\sum_{a\in A} a^k = \frac {1}{k +1} \cdot n^{\frac{2k +1}{2}} + \mathcal O \left( n^{\frac{8k +3}{8}} \right) + \mathcal O\left( L^{1/2}\cdot n^{\frac{4k +1}{4}}\right)$$

for $L\le n^{\frac {21}{80}}$.

Similar results can also be proven for Sidon sets in $\mathbb Z_m$ (see this for example).

Theorem C [Folklore] : We have $\|D_n\|_1 \asymp \log n$.

The main result we prove in this note is the following.

Theorem : Fix any $k\in \mathbb N_{\ge 1}$. For an $m=o\left(N^{\frac{19}{160}}\,(\log N)^{-1}\right)$, we have

$$S_b^{(k)}\ =\ \frac{1}{m(k+1)}\,N^{k+\frac 12} \ +\ \mathcal O_k\left(\frac{N^{k+\frac 38}}{m}+\frac{N^{k+\frac 14}\, \sqrt L}{m} \,+\, mN^{k-\frac 12} \,+\, N^{k+\frac{61}{160}}\,\log N\right)$$

for all $b\in \{0, 1, 2,\dots , m-1\}$.

The following proposition lies in the heart of our proof.

Proposition 1 : For $0\le X\le N$, define

$$F_r(X) := \sum_{\substack{a\in A\\ a\le X}} e\left(\frac{ra}{m}\right)$$

for a dense Sidon set $A\subset [N]$ and any integer $m>1$. Then, we have

$$\big|F_r(X)\big|\ll\ \frac{m}{\sqrt N} \,+\, N^{\frac{61}{160}}\log N$$

uniformly for $1\le r\le m-1$ and $0\le X\le N$.

The proof follows immediately from the following three lemmas.

Lemma 1 : We have

$$\sum_{n=1}^{X} f(n)\,e(\alpha n)\ =\ \int_{\mathbb T}\widehat f(\beta)\,D_X(\alpha-\beta)\,\mathrm d\beta$$

for every $\alpha\in\mathbb T$.

Proof : Follows from expanding the integral

\begin{align*} \int_{\mathbb T}\widehat f(\beta)\, D_X(\alpha-\beta)\, \mathrm d\beta &=\int_{\mathbb T}\left(\sum_{u}f(u)\,e(\beta u)\right)\left(\sum_{n=1}^X e((\alpha-\beta)n)\right)\mathrm d\beta\\ &=\sum_{u}\sum_{n=1}^X f(u)\, e(\alpha n)\int_{\mathbb T} e(\beta(u-n))\, \mathrm d\beta\\ &=\sum_{n=1}^X f(n)\, e(\alpha n) \end{align*}

using orthogonality. $\square$

Define

$$f(n):= \mathbf 1_A(n)-\frac{|A|}{N}\mathbf 1_{[N]}(n)$$

for $n\in\mathbb Z$. Then, $f$ is supported on $[N]$. Also,

$$\widehat f(\beta)=\widehat{\mathbf 1_A}(\beta)-\frac{|A|}{N}\widehat{\mathbf 1_{[N]}}(\beta)$$

and we define $U:=\|\widehat f\|_\infty$.

Lemma 2 : For each $r\in\{1,2,\dots,m-1\}$ and each $X\in\{0,1,\dots,N\}$, we have

$$\big|F_r(X)\big| \ll\ \frac{m}{\sqrt N} + U\log N$$

where the implied constant is absolute.

Proof : Put $\alpha:=\frac rm\in\mathbb T$. We have

\begin{align*} F_r(X)=\sum_{n=1}^X \mathbf 1_A(n)e(\alpha n) &= \frac{|A|}{N}\sum_{n=1}^X e(\alpha n) \,+\, \sum_{n=1}^X f(n)e(\alpha n)\\ &= \frac{|A|}{N}D_X(\alpha) \,+\, \sum_{n=1}^X f(n)\, e(\alpha n) \end{align*}

for $X\le N$. The last sum is

$$\sum_{n=1}^X f(n)e(\alpha n) = \int_{\mathbb T}\widehat f(\beta)\, D_X(\alpha-\beta)\, \mathrm d\beta$$

using Lemma 1. This implies

$$\left|\sum_{n=1}^X f(n)e(\alpha n)\right| \le\ U\int_{\mathbb T}\big|D_X(t)\big|dt \ll\ U\log N$$

using $\left|\widehat f(\beta)\right|\le U$ and Theorem C.

On the other hand, we have

$$\left|D_X\left(\frac rm\right)\right| = \left|\frac{\sin(\pi X \alpha)}{\sin(\pi \alpha)}\right| \le \frac{1}{|\sin(\pi \alpha)|}$$

for $\alpha=\frac rm$ with $1\le r\le m-1$. This implies

$$\left|\frac{|A|}{N}D_X(\alpha)\right|\ll \frac{|A|}{N}m \asymp \frac{m}{\sqrt N}$$

since $|\sin(\pi \alpha)|\ge \sin(\pi/m)\gg 1/m$. Combining the two bounds completes the proof. $\square$

Lemma 3 : For $|A|= \sqrt N-L'$ with $L:=\max\{0,L'\}\le N^{\frac{21}{80}}$, we have $U\ll N^{\frac{61}{160}}$.

Proof : We have

$$U\ll N^{1/2}\left(\left|1-\frac{|A|}{N^{1/2}}\right|+N^{-1/4}\right)^{1/2}$$

using Theorem A. Plugging $L\le N^{\frac{21}{80}}$ and using the fact that $A$ is dense, we have

$$U\ll\ \sqrt N \left(\frac{L}{\sqrt N}+N^{-\frac 14}\right)^{\frac 12} \ll\ \sqrt N\left(N^{-\frac{19}{80}}+N^{-\frac{1}{4}}\right)^{\frac 12}$$

hence completing the proof. $\square$

From Proposition 1, there are essentially two main steps to our main theorem. The first one is the next lemma, and the second one is given in the body of the proof. To begin with, define

$$T_{r,k}:=\sum_{a\in A} a^k\, e\left(\frac{ra}{m}\right)$$

for $r\in\{0,1,\dots,m-1\}$.

Lemma 4 : We have

$$\big|T_{r,k}\big|\le\ 2N^k\cdot \max_{0\le X\le N}\big|F_r(X)\big|$$

for each $1\le r\le m-1$.

Proof : Write

$$T_{r,k}=\sum_{n=1}^N n^k\ \mathbf 1_A(n)\,e(\alpha n)$$

and allow $F_r(0):=0$. We have

$$T_{r,k}=\ N^k F_r(N) - \sum_{n=1}^{N-1}F_r(n)\big((n+1)^k-n^k\big)$$

using Abel summation. Define

$$M_r:=\max_{0\le X\le N} \big|F_r(X)\big|$$

to get

$$\big|T_{r,k}\big| \le\ N^kM_r+\sum_{n=1}^{N-1}M_r\big((n+1)^k-n^k\big) \le\ 2N^kM_r$$

hence completing the proof. $\square$

Equipped with all this, we finally present our promised proof.

Proof of Theorem : Begin by noticing

$$\mathbf 1_{{a\equiv b \pmod m}} = \frac1m\sum_{r=0}^{m-1} e\left(\frac{(a-b)r}{m}\right)$$

for integers $a,b$ and $m$. This gives

\begin{align*} S_b^{(k)} &=\sum_{a\in A} a^k \mathbf 1_{{a\equiv b\pmod m}}\\ &=\frac1m\sum_{r=0}^{m-1} e\left(-\frac{br}{m}\right)\sum_{a\in A} a^k e\left(\frac{ar}{m}\right)\\ &=\frac1m\sum_{r=0}^{m-1} e\left(-\frac{br}{m}\right)\, T_{r,k}\\ &=\frac1mT_{0,k} \,+\, \frac1m\sum_{r=1}^{m-1}e\left(-\frac{br}{m}\right)T_{r,k}\\ &=\frac1m\sum_{a\in A}a^k \,+\, \mathcal R_b \end{align*}

where

$$\mathcal R_b:=\frac1m\sum_{r=1}^{m-1}e\left(-\frac{br}{m}\right)T_{r,k}$$

so that

$$\big|\mathcal R_b\big| \le \frac1m\sum_{r=1}^{m-1} \big|T_{r,k}\big| \le \max_{1\le r\le m-1}|T_{r,k}| \ll\ 2N^k\left(\frac{m}{\sqrt N}+N^{\frac{61}{160}}\log N\right)$$

using Lemma 4 and Proposition 1. This proves

$$S_b^{(k)} =\ \frac1m\sum_{a\in A} a^k \,+\, \mathcal O_k\left(mN^{k-\frac12}+N^{k+\frac{61}{160}}\log N\right)$$

from which Theorem B completes the proof. $\square$

-----------

Now, it is not difficult to see that for a fixed non-principal character $\chi$, one has

$$\sum_{a\in A} \chi(a)\ =\ \sum_{b=0}^{q-1}\chi(b)\,r_b$$

where $r_b := \left|\left\{a\in A :\ a\equiv b\,\pmod q\right\}\right|$. This gives

$$\sum_{a\in A}\chi(a)=\sum_{b=0}^{q-1}\chi(b)\left(r_b-\frac{|A|}{q}\right)$$

implying

$$\left|\sum_{a\in A}\chi(a)\right|\ \ll\ N^{\frac{61}{160}}\ =\ o\left(\sqrt{N}\right)$$

using Theorem A. This now makes us wonder about how dense Sidon sets are expected to behave against cancellations. While I do not have any ideas to contribute to this discussion, I would like to take this opportunity to make the following conjecture.

Conjecture 1 : Let $A\subset [n]$ be a dense Sidon set. Then, we have

$$\sum_{a\in A} \mu(a) = o(\sqrt n)$$

where $\mu$ is the Möbius function.

In fact, Conjecture 1 is probably true more generally with $\mu$ replaced by some suitable function that admits sufficient cancellations. The tools developed in the discussed paper (from which Theorem A is taken) are most certainly not strong enough to handle this question.

In case Conjecture 1 is not true, I would like to know if the following weaker statement is true.

Conjecture 2 : Let $\mathrm D_n$ be the collection of all dense Sidon subsets of $[n]$. Then, we have

$$\sum_{A\in \mathrm D_n}\sum_{a\in A} \mu(a) = o\left(\left\lvert \mathrm D_n\right\rvert \sqrt n\right)$$

where $\mu$ is the Möbius function.

On the other hand, the question at the heart of Conjecture 1 (and 2) is whether dense Sidon sets are multiplicatively independent. This invites us to ask another question of a similar flavour.

Conjecture 3 : Let $A\subset [n]$ be a dense Sidon set. Then, we have

$$\pi(A) \asymp \frac{\sqrt n}{\log n}$$

where $\pi(A)$ is the number of primes in $A$.

Whether order can be replaced with asymptote (with a suitable constant) in Conjecture 3 is an interesting question, but also one that probably asks a bit too much. An upper bound of $\pi(A)(\log n) \ll \sqrt n$ follows from an application of the Selberg sieve. From what I understand, the other direction might be very difficult to achieve. For example, I do not know whether it is easy to even show $\pi(A)>100$ for sufficiently large $n$.

Equidistribution of Sidon Sums in Residue Classes

A set of positive integers $A\subset \mathbb N$ is called a Sidon Set if the equation $a+b=c+d$ does not have any non-trivial solutions in $A$. A Sidon subset $A\subset [n]:=\{1,2,\dots , n\}$ is called dense (or extremal) if $\left\lvert A\right\rvert = \max \left\lvert S\right\rvert$ where the maximum is taken over all Sidon subsets of $[n]$. If $A\subset [n]$ is a dense Sidon set with $|A|=n^{1/2}-L$, then $-n^{\frac 14}\le L\ll n^{\frac{21}{80}}$ (see this and this for a proof).

It is well known that dense Sidon sets are surprisingly symmetric in profound ways. For example, it is known that they are uniformly distributed in intervals and well distributed in residue classes. In a previous work, Ding asked whether the sums of elements of a dense Sidon set over residue classes are also equidistributed. We will prove a stronger result here.

Take a dense Sidon set $A\subset [n]:=\{1,2,\dots, n\}$ with $t:=|A| = n^{1/2}-L^\prime$ and $L=\max\{0,L^\prime\}\le n^{\frac{21}{80}}$. For a fixed $k\in \mathbb N$ and some $m\in \mathbb N$, define

$$S_b^{(k)}(A;m) := \sum_{\substack{a\in A\\a\,\equiv\, b\,\pmod m}} a^k$$

for each $b\in \{0, 1, 2,\dots , m-1\}$.

We will use the following result in our proof.

Theorem A [Balasubramanian-Dutta, Ding] : Let $A=\left\{a_1,\dots ,a_{|A|}\right\}\subset [n]$ be a Sidon set so that $|A|=n^{1/2}-L^\prime$. Then,

$$\sum_{a\in A} a^k = \frac {1}{k +1} \cdot n^{\frac{2k +1}{2}} + \mathcal O \left( n^{\frac{8k +3}{8}} \right) + \mathcal O\left( L^{1/2}\cdot n^{\frac{4k +1}{4}}\right)$$

for $L\le n^{\frac {21}{80}}$.

Similar results can also be proven for Sidon sets in $\mathbb Z_m$ (see this for example).

The main result we prove in this note is the following.

Theorem : For fixed $k,m\in \mathbb N$, we have

$$S_b^{(k)}(A;m)\ =\ \frac{1}{m(k+1)}\,n^{k+\frac 12} \,+\, \mathcal O_{k,m}\left(n^{k+\frac 38}+n^{k+\frac 14}\,\sqrt{L}\right)$$

for all $b\in \{0, 1, 2,\dots , m-1\}$.

Proof of Theorem : The proof will require a lemma that will be proven after the body of the proof.

Let $\omega:=e^{2\pi i/m}$. We have

$$\mathbf 1_{\{x\equiv b \pmod m\}} := \frac1m\sum_{r=0}^{m-1}\omega^{r(x-b)}$$

for any integers $x,b$. Also, we have

$$\Delta_r^{(k)}:=\ \sum_{a\in A} a^k\,\omega^{ra}$$

for $r\in \{0,1,\dots,m-1\}$. This gives

$$S_b^{(k)}(A;m) =\sum_{a\in A}a^k\mathbf 1_{a\equiv b\pmod m} =\frac1m\sum_{r=0}^{m-1}\omega^{-rb}\Delta_r^{(k)}$$

implying

$$S_b^{(k)}(A;m)-\frac1m\sum_{a\in A}a^k \ =\ \frac1m\sum_{r=1}^{m-1}\omega^{-rb}\Delta_r^{(k)}$$

using definition of $\Delta_0^{(k)}$. Hence,

$$\left|S_b^{(k)}(A;m)-\frac1m \sum_{a\in A} a^k\right| \le\ \max_{1\le r\le m-1}\left|\Delta_r^{(k)}\right|$$

and therefore, it suffices to bound $\left|\Delta_r^{(k)}\right|$ for a fixed $r\in\{1,\dots,m-1\}$.

Define

$$d(h):=\ \#\left\{(a,a')\in A\times A:\ a-a'=h\right\}\le 1$$

since $A$ is Sidon. Now, extend $f:\mathbb Z \to \mathbb C$ by

$$f(x):=\omega^{rx}\,\mathbf 1_A(x)$$

so that $f(x)=0$ for $x\notin[1,n]$. Let $H$ be an integer parameter with $1\le H\le n$. Define block sums

$$B(t):=\sum_{i=1}^H f(t+i)$$

for $t\in \mathbb Z$. Also, define the energy

$$E:=\sum_{t=-H}^{n-1} \big|B(t)\big|^2$$

and

$$G:=\left|\sum_{h=1}^{H-1}(H-h)\omega^{-rh}\right|, \qquad M:=\sum_{h=1}^{H-1}(H-h)\,\left(1-d(h)\right)$$

so that

$$E\le Ht + 2G + 2M$$

using triangle inequality and the lemma we prove below. Also, by a simple geometric series argument, we have $G\ll_m H$.

Define the window count

$$X_q:=\#\big(A\cap(q-H,q]\,\big)=\sum_{x=q-H+1}^{q}\mathbf 1_A(x)$$

for $q\in\{1,2,\dots,n+H\}$. Therefore,

$$\sum_{q=1}^{n+H} X_q = Ht$$

since each $a\in A$ belongs to exactly $H$ such windows, namely those with $q\in\{a,a+1,\dots,a+H-1\}$. Also,

\begin{align*} \sum_{q=1}^{n+H} X_q^2 &=\sum_{q}\ \sum_{x,y\,\in(q-H,q]}\mathbf 1_A(x)\mathbf 1_A(y)\\ &=\sum_{x,y\in A}\#\big\{q:\ x,y\in(q-H,q]\big\}\\ &=Ht + 2\sum_{h=1}^{H-1}(H-h)d(h)\\ &\ge \frac{1}{n+H} \left(\sum_{q=1}^{n+H} X_q\right)^2 =\frac{H^2t^2}{n+H} \end{align*}

since for fixed $x,y\in\mathbb Z$, the number of $q$ such that both $x$ and $y$ lie in $(q-H,q]$ equals $H-|x-y|$ if $|x-y|\le H-1$, and equals $0$ otherwise.

Combining all of these now yields

$$2\ \sum_{h=1}^{H-1}(H-h)d(h)\ \ge\ \frac{H^2t^2}{n+H}-Ht$$

implying

\begin{align*} M &=\frac{H(H-1)}2-\sum_{h=1}^{H-1}(H-h)d(h)\\ &\le \frac{H(H-1)}2-\frac12\left(\frac{H^2t^2}{n+H}-Ht\right)\\ &\le \frac12\left(Ht+H^2\left(1-\frac{t^2}{n+H}\right)\right)\\ &\ll\ Ht+\frac{H^3}{n}+\frac{H^2L}{n^{1/2}} \end{align*}

using $t=\sqrt n -L$.

On the other hand, we also have

$$E\ \ll_m\ Hn^{1/2}+\frac{H^3}{n}+\frac{H^2L_+}{n^{1/2}}$$

using the geometric bound mentioned before.

Now, define

\begin{align*} T_k: &=\sum_{t=-H}^{n-1} t^k\, B(t) =\sum_{t=-H}^{n-1} t^k\ \sum_{i=1}^H f(t+i)\\ &=\sum_{x=1}^n f(x)\ \sum_{u=1}^H (x-u)^k = \sum_{\ell=0}^k c_{k,\ell}(H)\,\Delta_r^{(\ell)} \end{align*}

where

$$\Delta_r^{(\ell)}:=\sum_{a\in A}a^\ell\omega^{ra}$$

and

$$c_{k,\ell}(H):=\binom{k}{\ell}(-1)^{k-\ell}\sum_{u=1}^H u^{k-\ell}$$

coming from the Binomial expansion of $(x-u)^k$. It will enough for us to use the crude bounds

$$\big|c_{k,\ell}(H)\big|\le\ \binom{k}{\ell}\sum_{u=1}^H u^{k-\ell}\ \ll_k\ H^{k-\ell+1}$$

and

$$\left|\Delta_r^{(\ell)}\right|\le\ \sum_{a\in A}a^\ell\le\ t\,n^\ell\ll\ n^{\ell+\frac 12}$$

for $\ell\le k-1$.

We now have

$$\Delta_r^{(k)}=\frac1H\left(T_k-\sum_{\ell=0}^{k-1}c_{k,\ell}(H)\, \Delta_r^{(\ell)}\right)$$

since $c_{k,k}(H)=H$. On the other hand,

$$|T_k|^2 =\left|\sum_{t=-H}^{n-1} t^k B(t)\right|^2 \le \left(\sum_{t=-H}^{n-1} t^{2k}\right)\left(\sum_{t=-H}^{n-1}\big|B(t)\big|^2\right) =\left(\sum_{t=-H}^{n-1} t^{2k}\right)\cdot E\ \ll_k\ n^{k+\frac 12}E^{\frac 12}$$

by Cauchy-Schwarz. Combining all of these, and plugging in our crude bounds, we get

$$\left|\Delta_r^{(k)}\right| \le\ \frac{|T_k|}{H} + \frac1H\sum_{\ell=0}^{k-1}\big|c_{k,\ell}(H)\big|\,\left|\Delta_r^{(\ell)}\right| \ll_k\ \frac{n^{k+\frac 12}}{H}E^{\frac 12} + \sum_{\ell=0}^{k-1} H^{k-\ell} n^{\ell+\frac 12}$$

implying

$$E^{\frac 12} \ll_m\ n^{\frac 58}+n^{\frac 12}\sqrt{L}$$

on making the explicit choice $H:=\left\lfloor n^{\frac 34}\right\rfloor$.

The first term becomes

$$\frac{n^{k+\frac 12}}{H}E^{\frac 12} = \mathcal O_m \left(n^{k+\frac 38}+n^{k+\frac 14}\sqrt{L}\right)$$

and the second term simplifies to

$$\sum_{\ell=0}^{k-1} H^{k-\ell}\, n^{\ell+\frac 12}\ \ll_k\ n^{k+\frac 14}$$

on putting $H:=\left\lfloor n^{\frac 34}\right\rfloor$.

Combining all of these yields

$$\left|\Delta_r^{(k)}\right|\ \ll_{k,m}\ n^{k+3/8}+n^{k+1/4}\sqrt{L_+ +1}$$

uniformly for $1\le r\le m-1$. This completes the proof using Theorem A. $\square$

Finally, we prove the lemma we used in the previous proof.

Lemma : We have

$$E =\ H t + 2\Re\sum_{h=1}^{H-1}(H-h)\,\omega^{-rh}\,d(h)$$

where $E$ is the energy defined above.

Proof : Expand

$$E=\sum_{t}\sum_{1\le i,j\le H} f(t+i)\overline{f(t+j)}$$

so that

$$f(t+i)\overline{f(t+j)}=\ \omega^{r(t+i)}\omega^{-r(t+j)}\, \mathbf 1_A(t+i)\mathbf 1_A(t+j) =\ \omega^{-rh}\, \mathbf 1_A(t+i)\mathbf 1_A(t+i+h)$$

letting $h=j-i$ so that $\overline{f(t+j)}=\omega^{-r(t+j)}\,\mathbf 1_A(t+j)$.

    

Summing over $t$ with $f\equiv 0$ outside $[1,n]$ gives

$$\sum_{t=-H}^{n-1}\mathbf 1_A(t+i)\mathbf 1_A(t+i+h)=d(h)$$

for $h\ge 0$ and similarly, $d(-h)$ for $h<0$. The weight $(H-|h|)$ counts the number of pairs $(i,j)$ with $j-i=h$. Collecting terms yields

$$E=\sum_{h=-(H-1)}^{H-1} \big(H-|h|\big)\, \omega^{-rh}\, d(h) =\ Ht + 2\Re\sum_{h=1}^{H-1}(H-h)\,\omega^{-rh}\, d(h)$$

because $d(0)=t$ and $d(-h)=d(h)$. This completes the proof. $\square$

Notice that the equidistribution proof we presented was completely elementary, and does not use any outside results. In the next post, we will show that using more advanced tools (namely the fact that dense Sidon sets are Fourier-pseudorandom), we can prove slightly better results. In particular, we will show that the main theorem of this post is true with a better error term, allowing us to replace the fixed $m$ with an $m$ that can vary upto a power of $n$.