Sum of squares of multiplicities of differences

Question

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.

Answer 1

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$.

Answer 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$.