Lets say that we have two permutations $X$ and $Y$ of integers in $N \in [0..n-1]$ so that $x_k$ is the $k$:th element in $X$ and $y_k$ is the $k$:th element in $Y$.
Is there a function $f(x_k, y_k) = z_k, z_k \in Z$ such that $Z$ is a permutations of integers in $N$ and information is used from both $x_k$ and $y_k$ ?
And can you give me an example of this kind of a function?
This is related to me deep diving to mental poker papers and it seems that making up this kind of a function is not trivial.. For binary set $[0,1]$ only functions seem to be $f(x_k,y_k) \in [ x_k , y_k, 1-x_k, 1-y_k ]$ and thus not taking information from both arguments.
An example in mod $3$:
$X$ is $(1,2,0)$
$Y$ is $(0,1,2)$
for example function $f(x_k,y_k) = x^2_k-y_k x_k$ mod $3$ will produce
$Z$ is $(1,2,0)$ - that is a permutation
BUT if $Y$ is $(0,2,1)$ then $Z$ is $(1,0,0)$ and not a permutation.
Thus $x^2_k-y_k x_k$ mod $3$ is not a function I am looking for.
This is not possible. To see this, look at the number of pairs $(x,y)$ satisfying $f(x,y)=z$ for a fixed $z\in\{0,...,n-1\}$.
If for any $z$ the number of pairs is less than $n$, then if you choose two permutations $X$ and $Y$ at random, the average number of times that $f(x_i,y_i)=z$ is less than $1$, and so for some $X$ and $Y$ the result of applying $f$ is not $z$ anywhere, so this isn't a permutation.
Therefore we have exactly $n$ solutions for every $z$ (more than $n$ for some $z$ would imply less for some other $z'$). Also, if $f(x,y)=f(x',y')=z$ then we must have either $x=x'$ or $y=y'$, since otherwise we could find two permutations with $x_1=x,x_2=x',y_1=y,y_2=y'$, and then the result of applying $f$ would have two $z$s, so wouldn't be a permutation.
The only way to have $n$ pairs such that every two pairs match in either the first or second coordinate is if either all pairs match in the first coordinate, or all pairs match in the second coordinate. So you have solution pairs $(x,0)...(x,n-1)$ for some $x$ or $(0,y)...(n-1,y)$ for some $y$. Whichever of these you have, you can't have the opposite form for solutions to $f(x',y')=z'$, since the two solution sets would intersect.
Thus either you have for every $z$ there is an $x$ such that $f(a,b)=z$ if and only if $a=x$, or you have for every $z$ there is a $y$ such that $f(a,b)=z$ if and only if $b=y$. In the first case, $f$ only depends on the first permutation; in the other it only depends on the second.