4
$\begingroup$

Fix $d\in\mathbb{N}\setminus\{0\}$. For $j\in\mathbb{N}\setminus\{0\}$, let \begin{align*} [j] = \Big\{\alpha\in \mathbb{N}^d: \sum^d_{i=1}\alpha_i=j\Big\}. \end{align*} For $\alpha\in[j]$, define the multi-index factorial $\alpha! =\prod_{i=1}^d (\alpha_i !)$. What is a good bound for \begin{align*} \sum_{\alpha \in [j]} (\alpha !) \end{align*} in terms of $j$, when $d$ is fixed and $j$ is large?

$\endgroup$
3
  • $\begingroup$ You'll get different answers depending on j bigger than d or d bigger than j. Do you know which you need? Gerhard "Answer Depends On The Both" Paseman, 2020.01.25. $\endgroup$ Jan 26, 2020 at 2:49
  • $\begingroup$ Updated the question. Please consider fixed d while j is large. $\endgroup$ Jan 26, 2020 at 3:04
  • $\begingroup$ So I believe the argument in my post actually works when d^2 is less than j and gives an upper bound of (d-1)j(j!) on your sum when d is greater than 1. It would be nice to know for what pairs (d,j) we have that the subsums involving tuples with largest element (j-k) is greater than the subsum with tuples having largest element (j-k-1). Maybe you can find the general argument. Gerhard "Staying With Specialization For Now" Paseman, 2020.01.25. $\endgroup$ Jan 26, 2020 at 6:12

3 Answers 3

2
$\begingroup$

The logarithm of the sum in question is $\sim j\ln j$ if $d=o(j)$.

Indeed, assume that $j\ge d$ and, moreover, $d=o(j)$.

By Stirling's formula (see e.g. formula (26)), $$(2\pi n)^{1/2}(n/e)^n<n!<(2\pi(n+1))^{1/2}(n/e)^n \tag{1}$$ for integers $n\ge0$ (with $0^0:=1$).

Let $S$ denote the sum in question. Let $a:=\alpha$ and $a_i:=\alpha_i$.

Note that $S\ge j!$, whence, by (1),
$$\ln S\gtrsim j\ln j.\tag{2}$$

On the other hand, again by (1), the arithmetic-geometric-mean inequality, and the convexity of $u\ln u$ in $u\ge0$ (with $0\ln0:=0$), for any $a\in[j]$ $$a!<(2\pi)^{d/2}e^{-j}\prod_1^d(a_i+1)^{1/2}\exp\sum_1^d a_i\ln a_i \\ \le (j/d+1)^{d/2}\exp(j\ln j) =\exp(j\ln j+o(j\ln j)). $$ Also, the cardinality of $[j]$ is $\le j^d=\exp o(j\ln j)$ (actually, the cardinality of $[j]$ is $\binom{j+d-1}{d-1}$). So, $$\ln S\lesssim j\ln j. \tag{3}$$

Thus, by (2) and (3), $$\ln S\sim j\ln j,$$ as claimed.

$\endgroup$
2
$\begingroup$

Here is an approach that suggests (for $d$ smaller than $j$, say $d^2$ less than $j$) the sum is not larger than $dj(j!)$. Unfortunately, we are only bounding part of the sum by $d(j/2 - d)(j!)$. These are the parts which have an $\alpha_i$ term at least as large as $(j/2+d+1)$.

Note that there are $d$ terms whose product is $j!$: these are the $d$ tuples where all but one of the $\alpha_i$ are zero. Now let's set $k=0$, and look at a single tuple whose largest $\alpha_i$ is $(j-k)$. By replacing this $\alpha_i$ by $(j-k-1)$ and adding $1$ to one of the other $d-1$ places, we get $d-1$ distinct tuples whose largest term is $(j-k-1)$ and whose sum of (the products derived from each of) these $d-1$ tuples is at most $(k+d-1)/(j-k)$ times the single tuple, meaning the sum of all (products derived from) tuples with largest element $(j-k-1)$ is less than the sum of all (products derived from) tuples with largest element $(j-k)$. So when $2k$ is less than $j+1-d$, we get the sum of tuples with largest element $(j-k)$ is less than $d(j!)$. So we can bound a large part of the sum by $(j+1-d)d(j!)/2$. If we could extend this argument down to $k=j/d$, we would have the sum bounded above by $(j-j/d)d(j!)$.

Gerhard "Turning Multiplication Back Into Addition" Paseman, 2020.01.25.

$\endgroup$
1
  • $\begingroup$ Actually, the sums may be bounded by a unimodal sequence which would lead to each subsum of terms derived from tuples with largest a_i being j-k is still less than d(j!). So I think we can establish a bound of dj(j!) even in the case d is near j in size. Gerhard "Ever Hopeful For A Proof" Paseman, 2020.01.25. $\endgroup$ Jan 26, 2020 at 5:53
2
$\begingroup$

Let us also show for each natural $d$ $$S_{d,j}\sim j!d \tag{1}$$ (as $j\to\infty$), where $S_{d,j}$ is the sum in question.

The key here is the recursion $$S_{d,j}=\sum_{b=0}^j b!S_{d-1,j-b} \tag{2}$$ for $d=2,3,\dots$ and $j=0,1,\dots$, with the initial conditions $S_{d,0}=1$ and $S_{1,j}=j!$. The latter initial condition obviously implies (1) for $d=1$.

Proceed by induction on $d$. Take any $d=2,3,\dots$ and $j=0,1,\dots$. Then, by (2) and induction, for any fixed natural $B$ $$S_{d,j}=\sum_{b=0}^j (j-b)!S_{d-1,b} \\ =j!S_{d-1,0}+(j-1)!S_{d-1,1}+S_{d-1,j}+S_{d-1,j-1} \\ +\sum_{b=2}^B (j-b)!S_{d-1,b} +\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b} \\ =j!+O((j-1)!)+(d-1+o(1))j!+O((j-1)!) \\ +O((j-2)!) +\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b} \\ =(d+o(1))j!+\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b}. $$ Let now $B\ge1$ be large enough so that $S_{d-1,b}\le b!d$ for all $b>B$; such $B$ exists by induction. Then, noting that $(j-b)!b!$ is log-convex in $b\in\{0,\dots,B\}$, we see that for $j\ge3$ $$\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b}\le \sum_{b=B+1}^{j-2} (j-b)!b!\,d \\ \le \sum_{b=2}^{j-2} (j-b)!b!\,d\le(j-2-1)(j-2)!2!\,d=o(j!).$$ Now (1) follows by the multiline display.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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