3
$\begingroup$

Motivated by Question 315568 of mine, I'm interested in the set $$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$ It is easy to see that $$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,11,13,14\}.$$ By the Cauchy-Schwarz inequality, for any $\pi\in S_n$ we have $$\bigg(\sum_{k=1}^nk\pi(k)\bigg)^2\le\bigg(\sum_{k=1}^nk^2\bigg)\bigg(\sum_{k=1}^n\pi(k)^2\bigg)$$ and hence $$\sum_{k=1}^nk\pi(k)\le\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6.$$ If we let $\sigma(k)=n+1-\pi(k)$ for all $k=1,\ldots,n$, then $\sigma\in S_n$ and \begin{align}\sum_{k=1}^n k\pi(k)=&\sum_{k=1}^nk(n+1-\sigma(k))=(n+1)\sum_{k=1}^nk-\sum_{k=1}^nk\sigma(k) \\\ge&\frac{n(n+1)^2}2-\frac{n(n+1)(2n+1)}6=\frac{n(n+1)(n+2)}6. \end{align} Thus $$S(n)\subseteq T(n):=\left\{\frac{n(n+1)(n+2)}6,\ldots,\frac{n(n+1)(2n+1)}6\right\}.$$ My computation indicates that $S(n)=T(n)$ whenever $n\not=3$. Note that $|T(n)|=n(n^2-1)/6+1$.

Inspired by the above analysis, here I pose the following new conjecture in additive combinatorics.

Conjecture. Let $n$ be a positive integer and let $F$ be a field with $p(F)>n+1$, where $p(F)=p$ if the characteristic of $F$ is a prime $p$, and $p(F)=+\infty$ if the characteristic of $F$ is zero. Let $A$ be any finite subset of $F$ with $|A|\ge n+\delta_{n,3}$, where $\delta_{n,3}$ is $1$ or $0$ according as $n=3$ or not. Then, for the set $$S(A):=\bigg\{\sum_{k=1}^n ka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of}\ A\bigg\},$$ we have $$|S(A)|\ge\min\left\{p(F),\ (|A|-n)\frac{n(n+1)}2+\frac{n(n^2-1)}6+1\right\}.$$

QUESTION: Is my above conjecture true?

PS: I'll soon pose another question which extends the current one to the general case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.