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$
4
  • $\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$ Oct 2, 2014 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$ Oct 2, 2014 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$ Oct 2, 2014 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$ Oct 2, 2014 at 19:27

2 Answers 2

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$
9
  • $\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, 2014 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, 2014 at 20:23
  • $\begingroup$ You are right! I have corrected this. $\endgroup$ Oct 2, 2014 at 20:25
  • $\begingroup$ I am sorry, but I am not familiar with the notion of middle coefficient? $\endgroup$
    – user45183
    Oct 2, 2014 at 23:36
  • $\begingroup$ @Zeno44 Just note that the q-binomial coefficients are symmetric polynomials in q. $\endgroup$
    – Wolfgang
    Oct 3, 2014 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 agree to our terms of service and acknowledge you have read our privacy policy.