Suma de cuadrados de multiplicidades de diferencias

Question

Es difícil llegar con un buen título. Deje $A$ ser un conjunto de $n$ enteros, decir $A=\{a_1,\ldots,a_n\}$$a_1<\cdots<a_n$. Vamos a considerar todas las diferencias positivas $a_j-a_i$ (necesariamente $i<j$). Hay $n \choose 2$ pares de $(a_i,a_j)$$i<j$, pero, por supuesto, algunas diferencias pueden ser repetidos, o en otras palabras, tienen la "multiplicidad" mayor que 1.

Para un determinado $A$, una manera de ilustrar las diferencias y sus multiplicidades es con una "tabla de diferencias". Aquí está una tabla de $A=\{0,1,3,5,6\}$, y otro para $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|          -

Podemos ver que si $A=\{0,1,3,5,6\}$, entonces las diferencias $1,2,3,5$ cada uno tiene multiplicidad 2, y las diferencias $4,6$ cada uno tiene multiplicidad 1. También vemos que si $A=\{1,4,7,10,13\}$, entonces las diferencias $3,6,9,12$ han multiplicidades $4,3,2,1$ respectivamente.

Mi pregunta es: ¿Qué es un estrecho límite superior de la suma de los cuadrados de las multiplicidades? Suponemos que la respuesta es $1^2+2^2+3^2+\cdots+(n-1)^2$, que se produce si $A$ se compone de $n$ enteros en progresión aritmética (como en el segundo ejemplo anterior).

Al principio, pensé que esto sería una fácil consecuencia de los siguientes "lema": El más grande de la multiplicidad debe ser en la mayoría de las $n-1$, la segunda más grande de la multiplicidad debe ser en la mayoría de las $n-2$, la tercera más grande de la multiplicidad debe ser en la mayoría de las $n-3$, y así sucesivamente. Sin embargo, que "lema" es falso! En el primer ejemplo anterior (en el que $n=5$), los cuatro mayores multiplicidades se $2,2,2,2$, los cuales son no acotada arriba por $4,3,2,1$ respectivamente.

Tenga en cuenta que mi conjetura obligado crece como $n^3/3$. Estoy bastante seguro de que puedo encontrar un límite superior que crece como $2n^3/3$, pero la brecha entre esos límites es desconcertante para mí.

Answer 1

Podemos demostrar por inducción que su obligación es la mejor.

Supongamos que tenemos $n$ números y las diferencias se han multiplicidades $m_1\ge m_2\ge \cdots \ge m_t$. Si ahora añadimos un nuevo número más grande, crea $n$ diferencias. Si pudiéramos elegir libremente las diferencias (sin restricciones basados en los otros números), podríamos elegir a $n$ de la $m_i$ a un incremento de una sola vez, o puede agregar $m_{t+1}=1,m_{t+2}=1,\ldots$ según sea necesario por las diferencias que no coinciden.

Desde $m_i>m_j\Rightarrow (m_i+1)^2+m_j^2>m_i^2+(m_j+1)^2$, sin restricciones en las diferencias que se maximice la suma de los cuadrados incrementando el $n$ mayores diferencias disponible. Comenzando con $n=2, m_1=1$, el máximo de $n=3$ es alcanzado por $m_1\leftarrow 2,m_2=1$, y así sucesivamente. Si asumimos que para $n=k$ el máximo es de $m_1=(k-1),m_2=(k-2),\ldots,m_{k-1}=1$, $k+1$ números y el máximo es de $m_1\leftarrow k,m_2\leftarrow (k-1),\ldots, m_{k-1}\leftarrow 2, m_k=1$. Así que por inducción este patrón da un obligado para todos los $n$. Y, como usted ha señalado, esta obligado puede lograrse mediante la elección de números en una progresión aritmética.

Esta línea de pensamiento también se confirma @Gerry comentario en su Lema. Comenzando con un número y la adición de nuevos números más grandes, lo mejor que podemos hacer para la parte superior, $M$ multiplicidades es el incremento de algún subconjunto de ellos cada vez que se agrega un número hasta que hayamos $M$ números, entonces el incremento de cada uno de ellos por cada número que se agrega después de que. Esta restricción es así, que se suman a la mayoría de las $Mn-M(M+1)/2$, pero el $M$th más grande puede ser de hasta el $n-(M+1)/2$.

Answer 2

Pensando en ello hoy en día (todos las respuestas y comentarios que sin duda ayudó a), creo que hay un relativamente corto inductivo prueba de que no se molesta con cualquier lemas.

Mi enlazado es cierto para $n=2$. Cuando estamos en la transición a partir de un conjunto $A=\{a_1<\cdots<a_n\}$ a un conjunto $A'=\{a_1<\cdots<a_n<a_{n+1}\}$, entonces como Zander menciona, presentamos $n$ diferencias $a_{n+1}-a_1,\ldots,a_{n+1}-a_n$ que son distintos el uno del otro, por lo $n$ de las multiplicidades aumentar en 1 (posiblemente incluyendo algunos de multiplicidades que fueron 0).

Cuando se aumenta una multiplicidad de$m$$m+1$, se aumenta la suma de los cuadrados de las multiplicidades por $2m+1$. Por lo tanto, el incremento total de la suma de los cuadrados de las multiplicidades que tiene la forma de $\sum(2m_i+1)$, donde se $n$ términos en la suma, y el $m_i$ son algunas de las multiplicidades con respecto a $A$ (y algunos $m_i$ puede ser 0).

Por lo que la suma de los cuadrados de las multiplicidades aumenta por $2(\sum m_i) + n$. Esto puede estar acotada arriba por $2S+n$ donde $S$ es la suma de todas las multiplicidades con respecto a $A$. Pero $S = {n \choose 2}$, por lo que nos han demostrado que la suma de los cuadrados de multiplicidades ha aumentado en la mayoría de las $2{n \choose 2}+n = (n^2-n)+n = n^2$.