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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.