Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It's hard to come up with a good title. Let $A$ be a set of $n$ integers, say $A=\{a_1,\ldots,a_n\}$ with $a_1<\cdots<a_n$. We consider all the positive differences $a_j-a_i$ (necessarily $i<j$). There are $n \choose 2$ pairs $(a_i,a_j)$ with $i<j$, but of course, some differences can be repeated, or in other words, have "multiplicity" greater than 1.

For a given $A$, one way to illustrate the differences and their multiplicities is with a "table of differences". Here is one such table for $A=\{0,1,3,5,6\}$, and another for $A=\{1,4,7,10,13\}$.

-| 0 1 3 5 6     - | 1 4 7 10 13
-+----------     --+------------
0| - 1 3 5 6     1 | - 3 6 9  12
1|   - 2 4 5     4 |   - 3 6  9
3|     - 2 3     7 |     - 3  6
5|       - 1     10|       -  3
6|         -     13|          -

We see that if $A=\{0,1,3,5,6\}$, then the differences $1,2,3,5$ each have multiplicity 2, and the differences $4,6$ each have multiplicity 1. We also see that if $A=\{1,4,7,10,13\}$, then the differences $3,6,9,12$ have multiplicities $4,3,2,1$ respectively.

My question is: What is a tight upper bound on the sum of the squares of the multiplicities? I conjecture that the answer is $1^2+2^2+3^2+\cdots+(n-1)^2$, which occurs if $A$ consists of $n$ integers in arithmetic progression (as in the second example above).

At first, I thought this would be an easy consequence of the following "lemma": The largest multiplicity must be at most $n-1$, the second largest multiplicity must be at most $n-2$, the third largest multiplicity must be at most $n-3$, and so on. However, that "lemma" is false! In the first example above (in which $n=5$), the four largest multiplicities are $2,2,2,2$, which are not bounded above by $4,3,2,1$ respectively.

Note that my conjectured bound grows like $n^3/3$. I'm pretty sure I can find an upper bound that grows like $2n^3/3$, but the gap between those bounds is perplexing me.

share|improve this question
2  
Your lemma might be true if you modify it to say the largest multiplicity is at most $n-1$, the two largest multiplicities sum to at most $n-1+n-2=2n-3$, the three largest sum to at most $(n-1)+(n-2)+(n-3)=3n-6$, etc. –  Gerry Myerson Jun 21 '12 at 1:07

2 Answers 2

We can show by induction that your bound is the best.

Suppose we have $n$ numbers and the differences have multiplicities $m_1\ge m_2\ge \cdots \ge m_t$. If we now add a new largest number, it creates $n$ distinct differences. If we could freely choose the differences (without constraints based on the other numbers), we could choose up to $n$ of the $m_i$ to increment exactly once, or can add $m_{t+1}=1,m_{t+2}=1,\ldots$ as necessary for differences that do not match.

Since $m_i>m_j\Rightarrow (m_i+1)^2+m_j^2>m_i^2+(m_j+1)^2$ then without constraints on the differences we maximize our sum of squares by incrementing the $n$ largest differences available. Starting with $n=2, m_1=1$, the maximum for $n=3$ is achieved by $m_1\leftarrow 2,m_2=1$, and so on. If we assume that for $n=k$ the maximum is $m_1=(k-1),m_2=(k-2),\ldots,m_{k-1}=1$, then for $k+1$ numbers the maximum is $m_1\leftarrow k,m_2\leftarrow (k-1),\ldots, m_{k-1}\leftarrow 2, m_k=1$. So by induction this pattern gives a bound for all $n$. And, as you pointed out, this bound can be achieved by choosing numbers in an arithmetic sequence.

This line of thought also confirms @Gerry's comment on your Lemma. Starting with one number and adding new largest numbers, the best we can do for the top $M$ multiplicities is to increment some subset of them each time we add a number until we have $M$ numbers, then increment every one of them for each number added after that. This constraint is thus that they add to at most $Mn-M(M+1)/2$, but the $M$th largest can be up to $n-(M+1)/2$.

share|improve this answer
up vote 0 down vote accepted

Thinking about it today (everybody's answers and comments certainly helped), I believe there is a relatively short inductive proof that doesn't bother with any lemmas.

My bound is certainly true for $n=2$. When we transition from a set $A=\{a_1<\cdots<a_n\}$ to a set $A'=\{a_1<\cdots<a_n<a_{n+1}\}$, then as Zander mentions, we introduce $n$ differences $a_{n+1}-a_1,\ldots,a_{n+1}-a_n$ that are distinct from each other, so $n$ of the multiplicities increase by 1 (possibly including some multiplicities that were 0).

When we increase a multiplicity from $m$ to $m+1$, we increase the sum of the squares of the multiplicities by $2m+1$. Therefore the total increase of the sum of the squares of the multiplicities has the form $\sum(2m_i+1)$, where there are $n$ terms in the sum, and the $m_i$ are some of the multiplicities with respect to $A$ (and some $m_i$ may be 0).

So the sum of the squares of the multiplicities increases by $2(\sum m_i) + n$. This can be bounded above by $2S+n$, where $S$ is the sum of all multiplicities with respect to $A$. But $S = {n \choose 2}$, so we have shown that the sum of squares of multiplicities has increased by at most $2{n \choose 2}+n = (n^2-n)+n = n^2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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