3
$\begingroup$

Let $\Lambda :=\{\lambda_1, \dots, \lambda_n\}$ be a set of $n$ distinct real numbers.

For a given $p \in \mathbb N$, consider further the set

$$I_p := \{ \{i_1, i_2, \dots, i_p\} : i_j \in \{1, \dots,n\} \text{ for all } j=1, \dots, p\}.$$

It is not hard to see that $|I_p| = \binom{n+p-1}{p}$. For example, if $n=3$ and $p=2$, then

$$ I_2 = \{ \{1,1\}, \{1,2\}, \{1,3\}, \{2,2\}, \{2,3\}, \{3,3\} \}.$$

Now for a given $p \in \mathbb N$ we write down all $\binom{n+p-1}{p}$ sums $$\lambda_{i_1} + \lambda_{i_2} + \dots + \lambda_{i_p}. $$

Clearly it can happen that "different" sums have the same value, e.g. if

$$\Lambda = \{0,1,2\}$$

and $p=2$, then we get the sums $0, 1, 2, 2, 3, 4$ given by considering the elements of $I_2$.

My question is the following: Is there in general an upper bound on how many "different" sums there are that lead to one particular value?

Another interesting question would be the following: Given a fixed upper bound $N^*$, are there conditions on $\Lambda$ such that for all $p \in \mathbb N$, at most $N^*$ different $p$'th order sums yield the same value. For $N^* = 1$ one gets the condition that $\lambda_1, \dots, \lambda_n$ need to linearly independent over $\mathbb Q$.

$\endgroup$
  • $\begingroup$ If you let the $\lambda_i$ be linearly independent over $\mathbb{Q}$, you will obtain the upper bound. That is, just pretend the $\lambda_i$ are unknowns, with no relations. $\endgroup$ – Per Alexandersson Oct 2 '14 at 18:48
  • $\begingroup$ @PerAlexandersson I think you misunderstood the question. What was wanted was an upper bound on the number of elements of $I_p$ that can have the same sum. In your example that number is $1$, which is a lower bound. $\endgroup$ – Robert Israel Oct 2 '14 at 18:52
  • $\begingroup$ Taking a set symmetric about 0, one get n/2 choose p/2 as a bigger lower bound. Since any two choices for the same sum will differ by at least two members, no choice of p-1 members is repeated, so that provides a weak upper bound. $\endgroup$ – The Masked Avenger Oct 2 '14 at 19:10
  • $\begingroup$ Also, considering the first n whole numbers, there are np-p+1 possible sums, so that gives a lower bound not far from the weak upper bound. $\endgroup$ – The Masked Avenger Oct 2 '14 at 19:27
6
$\begingroup$

I answer the first question in Corollary 4.1 of my paper at http://math.mit.edu/~rstan/pubs/pubfiles/42.pdf. The maximum number of sums that have the same value is the middle coefficient of the $q$-binomial coefficient $\left[ n+p-1\atop p \right]$. This is achieved by taking $\Lambda=\{ 1,2,\dots,n\}$ and the sum to be $\lfloor \frac 12 p(n+1)\rfloor$. A more elementary proof follows from the work of Proctor and is given in my book Algebraic Combinatorics.

Addendum. For fixed $p$, it follows from http://math.mit.edu/~rstan/papers/qbc.pdf that the middle coefficient of $\left[ n+p-1\atop p\right]$ is asymptotic to $$ \frac{A(p-1,\lceil p/2\rceil)n^{p-1}}{(p-1)!p!} $$ as $n\to \infty$, where $A(p-1,\lceil p/2\rceil)$ denotes an Eulerian number.

$\endgroup$
  • $\begingroup$ I always thought Corollary 4.1 of your paper applied to an arbitrary set of real numbers (not just a set of positive reals). Am I mistaken? $\endgroup$ – Tony Huynh Oct 2 '14 at 20:18
  • $\begingroup$ Indeed, it seems like the general case can be deduced from the all $\lambda_i > 0$ case by adding a large positive constant $C$ to each $\lambda_i$. $\endgroup$ – Tony Huynh Oct 2 '14 at 20:23
  • $\begingroup$ You are right! I have corrected this. $\endgroup$ – Richard Stanley Oct 2 '14 at 20:25
  • $\begingroup$ I am sorry, but I am not familiar with the notion of middle coefficient? $\endgroup$ – user45183 Oct 2 '14 at 23:36
  • $\begingroup$ @Zeno44 Just note that the q-binomial coefficients are symmetric polynomials in q. $\endgroup$ – Wolfgang Oct 3 '14 at 6:43
1
$\begingroup$

A trivial upper bound is ${n+p-1} \choose p$. Somewhat less trivial is ${{n+p - 1} \choose p}/(p+1)$, which can be obtained as follows.
Suppose we put the elements in increasing order. Consider the "stars and bars" representation of $I_p$ (where if there are bars at positions $1 \le b_1 < b_2 < \ldots < b_{n-1} \le n+p-1$, there are $b_1 - 1$ of $\lambda_1$, $b_2 - b_1$ of $\lambda_2$, ..., $b_{n-1} - b_{n-2}$ of $\lambda_{n-1}$ and $n+p-1 - b_{n-1}$ of $\lambda_n$). Suppose we put bars in vacant positions one-by-one. Each of the $p+1$ possible positions for the last bar to be placed produces a different sum (each time you move it to the next available position to the right, you substitute a smaller $\lambda$ in place of a larger one and decrease the sum)). So the probability of getting a particular sum is at most $1/(p+1)$.

This bound is actually attained in your example with $n = 3$ and $p = 2$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.