14
$\begingroup$

Update: Initially the question was posted for $a = 1$. Now it has been generalized for any real $a > 0$

What is known about the distribution of the sum of the binomial coefficients over multiple of squares? My experimental data seems to suggest that for a given positive real $a > 0$ $$ s_{n,a} = \sum_{1\leq \lfloor ak^2 \rfloor\leq n}{n\choose \lfloor ak^2 \rfloor}= {n\choose \lfloor 1^2 a \rfloor} + {n\choose \lfloor 2^2 a \rfloor} + \cdots + {n\choose \lfloor r^2 a \rfloor} \approx \frac{2^n}{\sqrt{2an}} $$

Clearly the sum will be dominated by the term closest to the central binomial coefficient which in this case is the square nearest to $n/2$. What I found interesting is the shape of the histogram of the distribution of the ratios of the actual sum to its asymptotic estimate i.e. $\dfrac{s_n \sqrt{2an}}{2^n}$ are similar for all $a$ and look like an acr-sine distribution as mentioned in the comments.

Histogram of distribution for $a = 1$

enter image description here

Question 1: Why does it have an arc-sine like distribution?

Question 2 Where does the spikes occur? E.g. for $a = 1$, the spikes occur roughly at $1 \pm 1/6$.

Related question: What is the sum of the binomial coefficients $n \choose p$ over prime numbers?

$\endgroup$
  • $\begingroup$ As you say, it is probably about the distance between a square and $n/2$. Normalize it so $x=((n/2)-m^2)/m$ where $m^2$ is the largest square below $n/2$. Then $x is between 0 and 2. $\endgroup$ – Empy2 Jul 9 '19 at 10:56
  • 4
    $\begingroup$ Let $t_n = s_n \sqrt{2n}/2^n$. If you plot $t_n$ against $\sqrt{n}$ you get approximately a sine wave with period $\sqrt{2}$, oscillating between roughly $5/6$ and $7/6$. That suggests that what you're observing is an arcsine distribution (en.wikipedia.org/wiki/Arcsine_distribution) on the interval $[1-\delta, 1+\delta]$ where $\delta \approx 1/6$. I have no idea how one would prove this though. $\endgroup$ – Michael Lugo Jul 9 '19 at 14:02
  • $\begingroup$ I finally got where the sum ends up (at the last square less than n), and that actual plot is an histogram (in n). Could have been made clearer in the post... $\endgroup$ – Olivier Jul 10 '19 at 8:59
  • 1
    $\begingroup$ @MichaelLugo An arcsine distribution implies that the asymptotic value is the least likely value of $s_n$. In other words can we say that the true value of $s_n$ tends to be as far as possible from its asymptotic estimate ???? $\endgroup$ – Nilotpal Kanti Sinha Jul 14 '19 at 7:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.