1
$\begingroup$

Define $s(J)=\sum_{j\in J}j$ and $[n]=\{1,...,n\}$. I'm trying to get some reasonable upper bound on $$\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}.$$

Actually, I want an upper bound on $$\sum_{i=k}^{2k}\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}$$ for a fixed $k<\frac{n}{2}$.

The best I could get was $$\sum_{i=k}^{2k}\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}\leq \sum_{i=0}^{n}\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}=\prod_{i=1}^n \left(1+\frac{1}{2^i}\right).$$

I'd appreciate if someone could find anything better than that, preferentially depending on $k$.

Edit: Using $$\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}\leq \sum_{J\subset [n], |J|=i}\frac{1}{2^{\frac{i(i+1)}{2}}}$$ wasn't enough for me either.

$\endgroup$
8
  • $\begingroup$ Is $[n]=\{1,2,\dots,n\}$? $\endgroup$
    – Kenta S
    Commented May 8, 2021 at 16:37
  • $\begingroup$ @KentaS Yes, sorry. I'll edit that. $\endgroup$
    – JPMarciano
    Commented May 8, 2021 at 16:40
  • $\begingroup$ This can be written as the coefficient of $x^i$ in $$\prod_{k=1}^{n} \left(1+2^{-k}x\right)$$ Not sure if that helps. $\endgroup$ Commented May 8, 2021 at 16:41
  • 2
    $\begingroup$ If we write $$s(n,i)$$ for the sum in the question, then we have clumsy bounds: $$ \frac{1}{2^{i(i+1)/2}} \leq s(n,i) \leq \binom{n}{i} \frac{1}{2^{i(i+1)/2}}. $$ Given that $\binom{n}{i}$ is negligible compared to $2^{i^2}$ as long as $i \gg \sqrt{n}$, I guess that we have an asymptotic formula of the form $$\log s(n,i) \approx a_0 + a_1 i + a_2 i^2 $$ for some constants $a_0, a_1, a_2$. I numerically tested this with $n = 25$ and the result seems to fit into a quadratic polynomial in $i$ fairly well. $\endgroup$ Commented May 8, 2021 at 16:59
  • 1
    $\begingroup$ For your double sum and product equality, the outer sum should be $\sum_{i=0}^n$ and the product should be $\prod_{i=1}^n$. $\endgroup$
    – RobPratt
    Commented May 8, 2021 at 19:51

1 Answer 1

1
$\begingroup$

Here is another crude bound: Your sum

$$ S(n,j) := \sum_{\substack{J \subseteq [n] \\ |J| = j}} \prod_{k \in J} \frac{1}{2^k} $$

can be bounded from above by

$$ S(n, j) \leq \frac{1}{2^{j(j+1)/2}} \prod_{k=1}^{j} \frac{1}{1 - 2^{-k}}. \tag{*} $$

To derive this, we may write

\begin{align*} S(n,j) &= \sum_{0<k_1<\dots<k_j\leq n} \frac{1}{2^{k_1 + \dots + k_j}} \\ &= \frac{1}{2^{j(j+1)/2}} \sum_{0 \leq r_1 \leq \dots \leq r_j \leq n-j} \frac{1}{2^{r_1 + \dots + r_j}} \tag{$k_i = i + r_i$} \\ &= \frac{1}{2^{j(j+1)/2}} \sum_{\lambda} \frac{1}{2^{|\lambda|}}, \end{align*}

where the sum runs over all partitions $\lambda = (\lambda_1, \dots, \lambda_l)$ for which the length $l$ is at most $n-j$ and each part $\lambda_i$ is at most $j$. Also, $|\lambda| = \lambda_1 + \dots + \lambda_l $ denotes the size of $\lambda$. Then by relaxing the restriction on the length $l$, we obtain the desired bound $\text{(*)}$.

This bound seems useful if $j \ll n$. Indeed, a loose bound

$$ \left| \prod_{k=1}^{j} \frac{1}{1 - 2^{-k}} - \sum_{\lambda} \frac{1}{2^{|\lambda|}} \right| \leq \frac{C n^j}{2^{n-j} - 1} \tag{2} $$

for the constant $C = \prod_{k=1}^{\infty} (1 - 2^{-k})^{-1} \approx 3.46275$ is already enough to prove that the relative error between $S(n,j)$ and the upper bound in $\text{(*)}$ decays exponentially fast along the limit as $n\to\infty$ and $j=\mathcal{O}(\log n)$.


Addendum. Proof of $\text{(2)}$: We have

$$ \prod_{k=1}^{j} \frac{1}{1 - 2^{-k}} - \sum_{\lambda} \frac{1}{2^{|\lambda|}} = \sum_{\mu} \frac{1}{2^{|\mu|}}, $$

where the sum in the right-hand side runs over all partitions $\mu$ for which the length is $>n-j$ and each part is $\leq j$. Now for each $l = 1, \dots, j$, the contribution from all such partitions $\mu$ with $\mu_{n-j} = l$ is

\begin{align*} \sum_{\mu \,:\, \mu_{n-j} = l} \frac{1}{2^{|\mu|}} &= \sum_{\substack{j \geq \mu_1 \geq \mu_2 \geq \dots \\ \mu_{n-j} = l}} \frac{1}{2^{\mu_1 + \mu_2 + \dots}} \\ &= \Biggl( \sum_{j \geq \mu_1 \geq \dots \geq \mu_{n-j-1} \geq l} \frac{1}{2^{\mu_1 + \dots + \mu_{n-j-1} + l}} \Biggr) \Biggl(\sum_{l \geq \mu_{n-j+1} \geq \dots} \frac{1}{2^{\mu_{n-j+1} + \dots}}\Biggr). \end{align*}

Now the first sum in the last step can be bounded from above by

$$ \frac{\#\{ (\mu_1,\dots,\mu_{n-j+1}) : j \geq \mu_1 \geq \dots \geq \mu_{n-j-1} \geq l \}}{2^{(n-j)l}} \leq \frac{n^j}{2^{(n-j)l}}, $$

and the second sum satisfies

$$ \sum_{l \geq \mu_{n-j+1} \geq \dots} \frac{1}{2^{\mu_{n-j+1} + \dots}} = \prod_{k=1}^{l} \frac{1}{1 - 2^{-k}} \leq C. $$

Therefore

$$ \sum_{\mu} \frac{1}{2^{|\mu|}} \leq \sum_{l=1}^{j} \frac{Cn^j}{2^{(n-j)l}} \leq \sum_{l=1}^{\infty} \frac{Cn^j}{2^{(n-j)l}} = \frac{Cn^j}{2^{n-j}-1}. $$

$\endgroup$

You must log in to answer this question.

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