3
$\begingroup$

Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality $p \le {a \choose b}$. Is there a closed form solution (can be approximate as well/doesn't have to be exact) for that combinatorial optimization problem?

$\endgroup$
  • 1
    $\begingroup$ How is this not a pure mathematics question? See here for a related meta discussion. Your question should exhibit some indication as to whether it is more relevant to computer scientists than to mathematicians, and why you expect the former to provide a better answer. $\endgroup$ – Raphael Sep 5 '13 at 14:10
6
$\begingroup$

G. Bach noticed that the best choice for $b$ is $\lfloor a/2 \rfloor$, and furthermore this choice gives the maximal binomial coefficient. The easiest way to see this is to consider the ratio of two adjacent binomial coefficients: $$ \frac{\binom{a}{b}}{\binom{a}{b+1}} = \frac{b+1}{a-b}.$$ Therefore $\binom{a}{b} \leq \binom{a}{b+1}$ iff $b+1 \leq a-b$ iff $2b+1 \leq a$, and we get the desired result.

The binomial theorem states that $$ \sum_{b=0}^a \binom{a}{b} = 2^a, $$ hence $$ \frac{2^a}{a+1} \leq \binom{a}{\lfloor a/2 \rfloor} \leq 2^a. $$ (The correct order of magnitude, $\Theta(2^a/\sqrt{a})$, can be found using Stirling's approximation.) Therefore the optimal $a$ satisfies the following inequalities: $$ \frac{2^{a-1}}{a} < p \leq 2^a. $$ Therefore $a \geq \log_2 p$. On the other hand, when $p \geq 4$, $a \geq 2$, and so $a - \log_2 a \geq a/2$ (since $a-\log_2 a$ is monotone and $2 - \log_2 2 = 2/2$). Therefore for $p \geq 4$, $$ 2p\log_2 (2p) > 2\frac{2^{a-1}}{a} (a - \log_2 a) > 2^{a-1}.$$ We conclude that $$ \log_2 p \leq a < \log_2 p + 1 + \log_2 \log_2 (2p). $$ Therefore the binary search that G. Bach mentions takes only $O(\log\log\log p)$ steps.

If all we want is an asymptotic expression, then since $\binom{a}{\lfloor a/2 \rfloor} = \Theta(2^a/\sqrt{a})$, approximately we have $2^a/\sqrt{a} = Cp$, and so $a = \log_2 p + \Theta(\log_2\log_2 p)$. More terms can be obtained by taking more terms in Stirling's approximation. For example, we can find a constant $A$ such that $a = \log_2 p + A\log_2\log_2 p + o(\log_2\log_2 p)$.

$\endgroup$
  • $\begingroup$ Could you expand on that last paragraph, specifically the transformations to get from 2^a / sqrt(a) = Cp to the asymptotic statement? I never know how to solve for a variable if it's both in the exponent and in an additive/multiplicative term. Is that just using Stirling's approximation as well or is there some clever transformation involved? $\endgroup$ – G. Bach Sep 5 '13 at 6:06
  • $\begingroup$ The idea is that if $x = \Theta(y\log y)$ then $y = \Theta(x\log x)$. You can prove that using inequalities of the sort I get for $\log_2 p$ above, but it's somewhat tedious. Or you could say that $\log y \approx \log x$ and therefore one expects that $y = \Theta(x/\log y) = \Theta(x/\log x)$, though of course this reasoning isn't formal. $\endgroup$ – Yuval Filmus Sep 5 '13 at 6:52
  • $\begingroup$ Hm I'm just thinking, shouldn't the search take $\mathcal{O}(\log \log p)$ steps since we only apply the logarithm in the inequation once for the binary search? $\endgroup$ – G. Bach Sep 5 '13 at 17:09
  • $\begingroup$ The range is of length $\Theta(\log\log p)$ and so binary search takes $O(\log\log\log p)$ steps. $\endgroup$ – Yuval Filmus Sep 5 '13 at 18:16
4
$\begingroup$

For any $a$ we have

$\text{max}\,\{\binom{a}{b}\} = \binom{a}{\lceil a/2 \rceil}$

since the binomial grows towards "the middle" and afterwards declines again (a proof for that is not difficult and probably easy to look up if need be).

So what you want is the minimal $a$ such that $p \leq \binom{a}{\lceil a/2 \rceil}$. Let's expand that term:

\begin{align} p &\leq \binom{a}{\lceil a/2 \rceil} = \frac{\prod_{i = \lceil a/2 \rceil}^{a}i}{\lfloor a/2 \rfloor!} \qquad (*) \iff \\ p \cdot \lfloor a/2 \rfloor! &\leq \prod_{i = \lceil a/2 \rceil}^{a}i \end{align}

If that is any help, the product on the right hand side is also called the "falling factorial" and usually denoted as

\begin{align} \prod_{i = \lceil a/2 \rceil}^{a}i = (a)_{\lfloor a/2 \rfloor} \end{align}

where the "index" is the number of factors in the factorial.

Now this is where it gets a bit tricky, since this doesn't really give us a polynomial in $a$; the exponents of the factorial on the left hand side and the falling factorial on the right hand side - if we rewrite them as "polynomials" - depend on $a$ instead of being constants, so we can't just use some algorithm to find the roots of those polynomials. What we can do, however, is do a sort of binary search. We can use the inequation $(*)$ and do a search over $a$; start out with $a = 1$, check whether the inequation holds; after each iteration, go $a := a \cdot 2$ until $(*)$ holds; call that first $a$ for which it holds $a_{max}$. Then do a binary search over $[\frac{a_{max}}{2}; a_{max}]$ to find the smallest $a$ for which $(*)$ holds.

No idea whether there's a closed form or what the complexity of the above would be, though.

$\endgroup$
  • $\begingroup$ Thanks G. Bach, your clear explanation was also very helpful. $\endgroup$ – systemsfault Sep 5 '13 at 22:22

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.