Strange shape of the distribution of the sum of the binomial coefficients ${n\choose r^2}$over squares

This is a part of ongoing research with Nilotpal Kanti Sinha. The answer does not explain fully why we have such distribution, but it will help understanding the distribution of the values of $\frac{s_n{\sqrt{2an}}}{2^n}$. I used $S_{n,a}$ notation to include its dependence on $a$.

Theorem 1

Let $\beta_n=\beta_{n,a}=\frac n2 - a(\lfloor \sqrt{\frac n{2a}}\rfloor)^2$. Then $$ \frac{S_{n,a}\sqrt{2an}}{2^n}=\frac{2\sqrt a}{\sqrt{\pi}} \sum_{k\in\mathbb{Z}} \exp\left\{-2\left(\frac{\beta_n}{\sqrt n}+k\sqrt{2a}\right)^2\right\}+O\left(\frac{\log^3 n}{\sqrt n}\right). $$

Corollary 1

Let $x_n=x_{n,a}=\beta_n/(\sqrt{2an})$. Then $$ \frac{S_{n,a}\sqrt{2an}}{2^n}=1+\sum_{k=1}^{\infty}2 e^{-\frac{\pi^2}{4a} k^2} \cos2\pi k x_n+O\left(\frac{\log^3 n}{\sqrt n}\right). $$

The first harmonic gives a good approximation of the magnitude of the oscillation $1\pm 2e^{-\frac{\pi^2}{4a}}$.

Proof of Theorem 1

Lemma 1

Let $g(n)$ be a function satisfying $|g(n)|\leq 6\log n$. Then as $n\rightarrow\infty$, $$ \frac1{2^n}\binom n{\left\lfloor\frac n2 + g(n)\sqrt n\right\rfloor}=\frac2{\sqrt{2\pi n}} e^{-2(g(n))^2}\left(1+O\left(\frac{\log^3 n}{\sqrt n}\right)\right). $$

Lemma 2[Hoeffding's Inequality]

Let $h>0$ and $B_n=\{k\leq n \ | \ \left|k-\frac n2\right|\geq h\sqrt n\}$. Then $$ \frac1{2^n}\sum_{k\in B_n} \binom nk \leq 2e^{-2h^2}. $$

We apply Lemma 1 and Lemma 2 with $h=5\log n$. Let $g_0(n)=\frac{\beta_n}{\sqrt n}$ and $g_k(n)=\frac{\frac n2-\left\lfloor a\left(\left\lfloor \sqrt{\frac{n}{2a}}\right\rfloor +k\right)^2\right\rfloor}{\sqrt n}$ for $k\in\mathbb{Z}$ and $|k|\leq \frac6a \log n$. $$ \frac{S_{n,a}\sqrt{2an}}{2^n}=\sum_{|k|\leq \frac6a\log n} \frac{2\sqrt{a}}{\sqrt{\pi}} e^{-2(g_k(n))^2}\left(1+O\left(\frac{\log^3 n}{\sqrt n}\right)\right)+O\left(e^{-(\log n)^2} \right). $$ Since $g_k(n)=\frac{\beta_n}{\sqrt n }- k\sqrt{2a} + O\left(\frac{k^2}{\sqrt n}\right) = \frac{\beta_n}{\sqrt n}-k\sqrt{2a}+O\left(\frac{\log^2 n}{\sqrt n}\right)$, we have by the mean value theorem, $$ e^{-2(g_k(n))^2} = e^{-2\left(\frac{\beta_n}{\sqrt n} - k\sqrt{2a}\right)^2} + O\left(\frac{\log^2 n}{\sqrt n} ke^{-ak^2} \right). $$ Summing these over $k$ and applying Lemma 2 again gives \begin{align*} \frac{S_{n,a}\sqrt{2an}}{2^n}&=\sum_{|k|\leq \frac 6a\log n} \frac{2\sqrt a}{\sqrt{\pi}} \exp\left\{-2\left(\frac{\beta_n}{\sqrt n} -k\sqrt{2a}\right)^2\right\}+O\left( \frac{\log^3 n}{\sqrt n}\right)\\ &=\frac{2\sqrt a}{\sqrt{\pi}}\sum_{k\in\mathbb{Z}} \exp\left\{-2\left(\frac{\beta_n}{\sqrt n} +k\sqrt{2a}\right)^2\right\}+O\left( \frac{\log^3 n}{\sqrt n}\right). \end{align*} Hence, Theorem 1 follows.

Let $c>0$ and define $$ f(t)=e^{-\pi\left(\frac{x+t}c\right)^2}. $$ Then its Fourier transform $\hat{f}(\xi)$ is $$ \hat{f}(\xi)=\int_{-\infty}^{\infty} f(t)e^{-2\pi i t \xi} \ dt = ce^{2\pi i x\xi}e^{-\pi(c\xi)^2}. $$ Applying Poisson summation formula, we obtain for any $x\in\mathbb{R}$, $$ \sum_{k\in \mathbb{Z}} e^{-\pi\left(\frac{x+k}c\right)^2}=c\sum_{k\in\mathbb{Z}} e^{2\pi i xk}e^{-\pi(ck)^2}=c\left(1+\sum_{k=1}^{\infty} 2e^{-\pi(ck)^2} \cos 2\pi kx\right). $$ Putting $c=\frac{\sqrt{\pi}}{2\sqrt a}$, Corollary 1 follows.