представление чисел скалярным произведением перестановок

[Руст]

Рассмотрим такую сумму

$$S(n,\pi,k)=\sum_{i=1}^ni^k(i-\pi(i)).$$

Мы выяснили, что

$$0\le S(n,\pi,k)\le 2\sum_{i=1}^n i^{k+1}-(n+1)\sum_{i=1}^n i^k=T(n,k)=O(\frac{kn^{k+2}}{(k+2)(k+1)}).$$

При $k=1$ начиная с некоторого n принимается все значения $0\le S(n,\pi,1)\le \frac{(n-1)n(n+1)}{6}.$
Как я понял сейчас выдвигается гипотеза, что при k=2 принимается все значения $0\le S(n,\pi,2)\le \frac{(n-1)n(n+1)^2}{6}.$
Эта гипотеза так же легко опровергается. Пусть $\pi(n)=m$. Если $m=n$ то величина ограничена величиной $T(n-1,k)<T(n,k)$ (между ними много нереализуемых $T(n,2)-T(n-1,2)=\frac{n(n-1)(4n+1)}{6}$. При $m<n$ запишем $S(n,\pi,k)=n^km-m^kn+S(n-1,\pi',k)+S'<T(n,k)-O(n^k).$ Исключительных (непринимаемых) значений в интервале много (неограниченно). Я предполагаю даже, что они имеют положительную плотность при $k>1, n\to \infty$.

[maxal]

maxal в сообщении #89995 писал(а):

Докажите, что при $n\geq 4$ каждое целое число из отрезка $[f(n),g(n)]$ представляется скалярным произведением двух перестановок порядка $n$.

Это утверждение следует, например, из теоремы 2.5 и леммы 2.9 в статье
J. Sack, H. Úlfarsson, Refined inversion statistics on permutations.