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$ – Per Alexandersson Jul 18 '19 at 6:44

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)

| cite | improve this answer | |

Your Answer

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

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