3
$\begingroup$

I am looking for a proof, disproof or counter example of the following claim.

Let $C = \{k_1, k_2, \ldots, \}$ be a strictly increasing infinite sequence of positive integers which have a certain characteristic $C$. For example $C$ can be the set of all natural numbers, or all odd numbers or all even numbers or all primes or all numbers not divisible by 4 etc.

Let $N(x)$ be the numbers of positive integers $\le x$ that have this characteristic $C$ i.e. $N(x) = \sum_{k_i \le x} 1$. For example the number of integers less than $x$ have the characteristic of being even or prime is $x/2$ and $\pi(x)$ respectively.

Conjecture: If $(\frac{k_1}{k_n}, \frac{k_2}{k_n}, \ldots, \frac{k_{n-1}}{k_n},1)$ approach uniform distribution in $(0,1)$ as $n \to \infty$ then,

$$ \sum_{k_i \le n}{n\choose k_i} \sim \frac{2^n}{n}N(n). $$

The progress on the case of primes is present in this MSE post.

Edit: The additional constraint on uniform distribution has been added in light of @Paul SInclair's comment and @bof's counter example for non-uniformly distributed $k_i/k_n$

$\endgroup$
9
  • 1
    $\begingroup$ Let $C$ consist of all positive integers less than $2$, then $S_n = n$ and $N(n) = 1$, so $S_n/N(n)$ is not asymptotically equivalent to $2^n/n$. Can you try to give a more precise statement of the conjecture. The role of the "characteristic" (in my example "being less than 2") is not clear to me. $\endgroup$
    – Christoph
    Feb 24, 2019 at 12:43
  • 1
    $\begingroup$ I have a feeling that something like this might be a counterexample: let $C$ be the set of all numbers with an odd number of digits (in base $10$). $\endgroup$
    – bof
    Feb 24, 2019 at 14:09
  • 1
    $\begingroup$ For $C=k\mathbb{Z}$ with positive $k$ (well-known), $C=\mathcal{P}$ primes (work in progress), the asymptotic is true. But, there are going to be counterexamples by making $C$ stay far away from the central binomial coefficient. $\endgroup$ Feb 24, 2019 at 14:19
  • 1
    $\begingroup$ Now, I am not sure on $C=\mathcal{P}$. For $C=\mathcal{P}$, the asymptotic is true for "almost all" $n$. It may be true for primes, but currently there is a technical barrier. $\endgroup$ Feb 26, 2019 at 4:37
  • 1
    $\begingroup$ @i707107 Just an FYI, even the primes satisfy this uniform distribution condition i.e. the ratios $\frac{p_1}{p_n}, \frac{p_2}{p_n}, \ldots \frac{p_{n-1}}{p_n},1$ are uniformly distributed in 0,1. $\endgroup$ Feb 27, 2019 at 23:14

3 Answers 3

3
$\begingroup$

I think this is a counterexample.

Let $C$ be the set of all positive integers whose base $10$ representation has an odd number of digits. Let $$f(n)=\frac n{N(n)2^n}\sum_{k\in C}\binom nk.$$ The conjecture is that $\lim_{n\to\infty}f(n)=1$. In fact, $$\lim_{n\to\infty}f\left(10^{2n}\right)=0$$ and $$\lim_{n\to\infty}f\left(10^{2n+1}\right)=1.1.$$

$\endgroup$
1
  • $\begingroup$ This shows that we need stronger conditions on $C$ for the conjecture to hold. I think a sufficient but not necessary condition is that the sequence of numbers $k_1/k_n, k_2/k_n, k_3/k_n, \ldots$ approach uniform distribution in $(0,1)$. $\endgroup$ Feb 25, 2019 at 11:17
1
$\begingroup$

A general reason for this to hold is just that $\sum_{k\le n}{n\choose k} = 2^n$. There are $n+1$ terms in this sum. For large $n$, if you add up some $N < n$ of the terms, uniformly distributed, it is reasonable to expect that you will get approximately $\frac N{n+1}$ of the total value, i.e., $\frac N{n+1}2^n \sim \frac Nn2^n$

Of course, this heuristic argument hinges on the summed values being proportionate to the fraction of terms chosen. For sets that are approximately uniformly distributed for large $n$, this is likely to hold. But bof has provided an example where they are not uniformly distributed, and thus it fails.

$\endgroup$
1
  • $\begingroup$ As demonstrated by @bof we need stronger condition on $C$ for the conjecture to hold. $\endgroup$ Feb 25, 2019 at 11:13
1
$\begingroup$

This method is also present in my other answer to the linked question about binomial coefficients over primes.

Let $T_n\sim B(n,1/2)$ be the binomial distribution. Then by Hoeffding's inequality,

$$ P(T_n \notin [\frac n2-\sqrt{n\log\log n}, \frac n2 + \sqrt{n\log\log n}]) \leq \frac 2{(\log n)^2}.$$

Now, let $k_1, \ldots, k_m$ denote the enumeration of integers $1,\ldots, n$ outside $[\frac n2-\sqrt{n\log\log n}, \frac n2+\sqrt{n\log\log n}]$ in increasing order, and the last number is $n$. Then we have for any $0\leq a<b\leq 1$, $$ \frac{ \# \{ a\leq \frac kn \leq b | k\notin [\frac n2-\sqrt{n\log\log n}, \frac n2+\sqrt{n\log\log n}]\}}{n+O(\sqrt{n\log\log n})}=\frac{(b-a)n+O(\sqrt{n\log\log n})}{n +O(\sqrt{n\log\log n})}\rightarrow b-a \ \mathrm{as} \ n\rightarrow\infty. $$ Therefore the sequence $k_1/k_m,k_2/k_m,\ldots, k_{m-1}/k_m, 1$ approach uniform distribution in $(0,1)$. However, the asymptotic for the sum of binomial coefficients over the set $k_1, \ldots, k_m$ is at most $$ \lesssim \frac{2^{n+1}}{(\log n)^2}. $$ This is much less than the conjectured asymptotic of $\sim 2^n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .