Sum of correlations of $k$ integers whose sum is fixed

Question

Fix integers $k,N \geq 2$. Suppose that $n_1, \ldots, n_k$ are $k$ positive integers such that $n_1 + \cdots + n_k = N$. Can we get a good upper bound for the sum $$ \sum_{a=1}^{k-1} \sum_{b = 1}^{k - a} n_b n_{b + a}? $$ The trivial upper bound is $N^2$. Can we do better? Thanks.

Answer 1

The sum counts every pair of $n_i$ exactly once, making it identical to the second elementary symmetric polynomial $e_2(n_1,\ldots,n_k)$, which is exactly half of $$(\sum_{i=1}^k n_i)^2 - \sum_{i=1}^k n_i^2 = N^2 - \sum_{i=1}^k n_i^2.$$ To get an upper bound we simply need to minimize the $\ell^2$-norm of $(n_1,\ldots,n_k)$, and this is achieved by taking all $n_i$ as close as possible to equal (so $n_i \approx N/k$).

A smooth upper bound would be $\tfrac12(1 - \tfrac1k)N^2$, and the exact bound can easily be computed from the appropriate combination of $\lfloor N/k\rfloor$ and $\lceil N/k \rceil$.