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$.
No comments:
Post a Comment