1

Given $L$ a constant positive integer, and $1\leq k \leq L$.

My question are:

(1) What is the upper bound of

$$\binom{m_1}{2}\binom{m_2}{2}\cdots\binom{m_k}{2}\leq \cdots$$

among all partitions $(m_1,\cdots,m_k)$ of integer $n$, i.e. $m_1+\cdots+m_k=n$, $1\leq m_i\leq n$?

Note: I define $\binom{1}{2}$ as $0$.

(2) I would like to understand how $(m_1,\cdots,m_k)$ influences the value of this quantity. Is it possible to see when will (what makes) this quantity to be small or large?

happyle
  • 183
  • I see that $m_i$ can be $1$, is $\binom{1}{2} = 0$ ? – Daniel Cunha Aug 24 '23 at 12:18
  • @DanielCunha Yes! I will now add it to the post. – happyle Aug 24 '23 at 12:19
  • I would say it is maximal when all $m_i$ are (almost) of the same size – julio_es_sui_glace Aug 24 '23 at 12:37
  • 1
    You can write $\binom{m}{2}=m(m-1)/2$. You can ignore the $2$ in the denominators (or collect them into a single constant factor $1/2^k$). Then the problem becomes a polynomial in the $m_i$, and you can turn this discrete problem into a continuous one. I'll switch from $m_i$ to $x_i$ to denote this change. From there you can use Lagrange multipliers to prove that the maximum occurs when $x_1=x_2=\ldots = x_k=n/k$ (ignoring the $1\leqslant m_i$ constraint). –  Aug 24 '23 at 12:51
  • 1
    From here, as @julio_es_sui_glace said, the maximum will be as close as you can get to this point while obeying your constraints $1\leqslant m_i\leqslant n$ and $m_i$ are integers.

    Note that if $k>n$, there are no $m_i$ which satisfy your conditions, since $m_1+\ldots + m_k\geqslant 1+\ldots + 1 =k>n$.

     –  Aug 24 '23 at 12:54
  • @bangs The function is convex, but it is a maximization problem (not minimization), can we prove that the local maximum is global for the relaxed continuous problem? – Daniel Cunha Aug 24 '23 at 13:13
  • "Can we prove ...?" Yes, but how much work is it? I don't know. That's why I gave a comment and not an answer. Proving a global maximum in this case would probably be to return to the "closest" integer point to $x_1=\ldots = x_k=n/k$ and prove that, say, replacing $(x_1,x_2, \ldots, x_k)$ with $(x_1+1, x_2-1, \ldots, x_k)$ would result in a decrease to the objective function if it takes us farther away from the "closest" point. –  Aug 24 '23 at 13:24
  • Well, but if the problem is only to find an upper bound, it is enough to show that that local maximum is global for the relaxed continuous problem, it will be an upper bound for the discrete original problem. – Daniel Cunha Aug 24 '23 at 13:57
  • My mistake, the function is not convex, it seems that the Hessian matrix will have both positive and negative eigenvalues... – Daniel Cunha Aug 24 '23 at 14:20
  • 1
    Quick beginner guide for asking a well-received question + please avoid "no clue" questions + focus on one question per post + clarify whether you are looking for the least upper bound for a fixed $k$ (as the comments and answer seem to interpret), or over all $k\le L$ (as the beginning of your post seems to mean). – Anne Bauval Aug 24 '23 at 15:13

1 Answers1

1

I've got some partial results:

By definition: $\boxed{n = m_1 + ... + m_k}$ ; $\boxed{m_k \geq 1}$ ; $\boxed{n \geq k}$

$$f(m_1,...,m_k) = \binom{m_1}{2}\binom{m_2}{2}...\binom{m_k}{2}$$

$$\binom{m_i}{2} = \frac{[m_i-1]\,m_i}{2}$$

$$f(m_1,...,m_k) = \frac{[m_1\,m_2\,...\,m_k][m_1-1][m_2-1]...[m_k-1]}{2^k}$$

Let's first solve for the small cases:

If $k \leq n < 2\,k$, there is at least one $m_i=1$, so $f(m_1,...,m_k)=0$

If $n = 2\,k$, $m_1=m_2=...=m_k=2$ would yield the maximal value: $f(m_1,...,m_k)=1$

Now, let's assume $\boxed{m_k\geq 2}$, so that $f(m_1,...,m_k)$ is strictly positive.

If we would write this as an continuous maximization problem, we would get the following derivatives.

$\nabla f = \frac{1}{2^k}\begin{bmatrix} [m_2\,m_3\,...\,m_k][m_2-1][m_3-1]...[m_k-1]\,[2\,m_1-1]\\ [m_1\,m_3\,...\,m_k][m_1-1][m_3-1]...[m_k-1]\,[2\,m_2-1]\\ \vdots\\ [m_1\,m_2\,...\,m_{k-1}][m_1-1][m_2-1]...[m_{k-1}-1]\,[2\,m_k-1]\\ \end{bmatrix}$

$g(m_1,...,m_k) = m_1+...+m_k - n = 0$

$\nabla g = \begin{bmatrix} 1\\ 1\\ \vdots\\ 1 \end{bmatrix}$

From these derivatives, it can be shown that $m_1=m_2=...=m_k=\frac{n}{k}$ is a local maximum that can be achieved in the discrete original problem whenever $\boxed{n = d\,k}$, with $d\in\{1,2,...\}$.

For this particular cases, the local maximal value of $f$ would be:

$$\boxed{\frac{n^k\,[n-k]^k}{2^k\,k^{2k}}}$$

If we can now show that this is a global maximum for the relaxed continuous problem, then it will be an upper bound for the discrete original function!

Note that, if $m_1=m_2=...=m_k=\frac{n}{k}$ is the global solution of the optimization problem:

$$\text{maximize} \;\; m_1\,m_2\,...\,m_k$$ $$\text{subject to} \;\; m_1+m_2+...+m_k=n$$

Then, $m_1-1 = m_2-1 = ... = m_k-1 = \frac{n-k}{k}$ will solve:

$$\text{maximize} \;\; [m_1-1][m_2-1]...[m_k-1]$$ $$\text{subject to} \;\; [m_1-1] + [m_2-1] + ... + [m_k-1] = n-k$$

Since our function of interest is the product of these two (divided by $2^k$), this would mean that the presented local optimum is global!

So now the problem is reduced to prove that the product of $k$ positive values with fixed sum is maximal when all the factors are equal.

Daniel Cunha
  • 1,735