This thread is following the question posted here and seeks to find a generalization to the test function used in the previous question i.e. $f_a(x_1, \dotsc,x_n)=(x_1+a)\dotsb(x_n+a)$

At first, I propose this conjecture:
$\forall$ $n>0 \in \mathbb N$, $ \exists$ $p>0 \in \mathbb N$ such that for any set of integers $(x_1,...,x_n)$ and $1\leq x_i \leq n$:

$(x_1,\dotsc,x_n)$ is a permutation of $(1,\dotsc,n)$ if and only if:

I checked this conjecture for $n=1,\dotsc,17$
The minimum values of $p$ are: $(1,1,2,2,2,4,5,5,5,5,5,7,7,7,7,7,7)$
Here the test function is $f_p(x_1, \dotsc,x_n)=x_1^p+\dotsb +x_n^p$

The question is then: assuming $f_p(x_1, \dotsc,x_n)$ is a symmetric function of n variables with a parameter $p$, what kind of properties must $f$ have in order to be a test function i.e. to be able to say if $(x_1,...,x_n)$ is a permutation of $(1,...,n)$?
New examples ?

  • $\begingroup$ I wonder what sets $S$ of integer partitions of $n$ has the property that if one knows the values of $s_\lambda(x)$ for $\lambda \in S$, then one can deduce 'permutability' of the vector $x$. Here, $s_\lambda$ are the Schur functions. $\endgroup$ Jul 18, 2019 at 6:44

1 Answer 1


Your conjecture is true: If $p$ is big enough then $(n-1)\cdot (n-1)^p<n^p$ and therefore $\lfloor \frac{x_1^p+\cdots+x_n^p}{n^p}\rfloor$ denotes the number of $i$ with $x_i=n$, hence from $x_1^p+\cdots + x_n^p=1^p+\cdots +n^p$ we see that this number is one as desired. Next, if also $(n-2)\cdot(n-2)^p<(n-1)^p$, then $\lfloor \frac{x_1^p+\cdots+x_n^p-n^p}{(n-1)^p}\rfloor$ denotes the number of $i$ with $x_i=n-1$, and so on. So all we need is $p$ such that $k^{p+1}<(k+1)^p$ for $1\le k\le n-1$. Divide by $k^p$ and take logarithms to see that it is sufficient to take $$p>\max_{1\le k<n}\frac{\ln k}{\ln(1+\frac1k)}\sim n\ln n.$$ (This gives $p=50$ instead of $p=7$ for $n=17$, but who cares)

  • $\begingroup$ Just one small question: if all $x_i$ are equal to $n-1$, we have $x_1^p + \dots + x_n^p= n \cdot (n-1)^p$. Hence I think the inequality $(n-1)\cdot (n-1)^p < n^p$ is formally not sufficient for the first step, I think for that we might need $n \cdot (n-1)^p < n^p$. $\endgroup$
    – Jakob W.
    Mar 20, 2021 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.