2
$\begingroup$

For $v, w \in \{0,1\}^n$, denote $v w = (v_1 w_1, \ldots, v_n w_n)$ and $|v|=\sum_{i} v_i$.

Let $v_1, v_2 \in \{0,1\}^n$ and \begin{align*} f(x_1, x_2) = \sum_{d=0}^{|v_1 v_2|} \frac{1}{2^{|v_1|+|v_2|-|v_1 v_2|}} {|v_1| - |v_1 v_2| \choose x_1 - d} {|v_2| - |v_1 v_2| \choose x_2 - d}. \end{align*}

How to find the asymptotic formulas for $f(x_1, x_2)$ ($|v_1|, |v_2| \to \infty$)?

Is it possible to prove that there is a constant $\epsilon$, $0<\epsilon<1$, such that \begin{align} \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} f(x_1, x_2) < 1 - \epsilon? \end{align}

These questions relate to the question.

Any help would be greatly appreciated!

$\endgroup$
  • $\begingroup$ What limit do you want to consider? All binomial coefficients vanish when $x_1>\lvert \nu_1\rvert$ or $x_2>\lvert \nu_2\rvert$. So $f$ is asymptotic to $0$ as $x_i\to\infty$. $\endgroup$ – Philipp Lampe Aug 6 '18 at 14:20
  • $\begingroup$ @Philipp Lampe, thank you very much for your comments. I want to consider the limit $|v_1|, |v_2| \to \infty$. I have edited the post. $\endgroup$ – Jianrong Li Aug 6 '18 at 14:24
  • $\begingroup$ I guess this is related to mathoverflow.net/questions/307584/… $\endgroup$ – Max Alekseyev Aug 6 '18 at 15:34
  • $\begingroup$ @Max Alekseyev, yes, this is a related question. I will put a link of that question in this post. $\endgroup$ – Jianrong Li Aug 6 '18 at 15:49
3
$\begingroup$

Put $a=|v_1|$, $b=|v_2|$, $c=|v_1v_2|$. Then we have $$ \sum_{i=0}^a\sum_{j=0}^b\sum_{k=0}^c\binom{a-c}{i-k}\binom{b-c}{j-k}= \sum_{k=0}^c\left(\sum_{i=0}^a\binom{a-c}{i-k}\right)\left(\sum_{j=0}^b\binom{b-c}{j-k}\right). $$ As $i$ runs from $0$ to $a$, $i-k$ runs from $-k$ to $a-k$. Since $0\leq k\leq c$, this range covers the interval from 0 to $a-c$, thus $\sum_{i=0}^a\binom{a-c}{i-k} = \sum_{i=0}^{a-c}\binom{a-c}{i}=2^{a-c}$. Hence $$ 2^{a+b-c}\sum_{i=0}^a\sum_{j=0}^b f(i,j) = \sum_{k=0}^c 2^{a-c}\cdot 2^{b-c} = (c+1)2^{a+b-2c}, $$ that is, $$ \sum_{i=0}^a\sum_{j=0}^b f(i,j) = \frac{c+1}{2^c}. $$ Hence the answer to the last question is yes if and only if $|v_1v_2|>1$. A pointwise estimate for $f$ is more difficult, as it depends on the relative size of $a$, $b$ and $c$.

$\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.