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