Let $\ f:Z/n\rightarrow Z/n\ $ be a function such that $\ \sum_{i\in Z/n}\,f(i)=0.\ $ Is it true that $\ f\ $ can be represented as a sum of two permutations of Z/nZ?
-
$\begingroup$ Z/n should be Z/nZ. $\endgroup$– user64289Dec 24, 2014 at 23:03
-
1$\begingroup$ Both notations are equivalent well understood/known, and easily recognized. Denominator $\ n\ $ stands for a shortcut of $\ (n)\ $ which is the principal ideal. $\endgroup$– Włodzimierz HolsztyńskiDec 24, 2014 at 23:08
-
$\begingroup$ @user64289 -- look into the code of your question, and edit it to your heart desire. $\endgroup$– Włodzimierz HolsztyńskiDec 24, 2014 at 23:36
-
$\begingroup$ You may run a program for small values of $\ n$. $\endgroup$– Włodzimierz HolsztyńskiDec 25, 2014 at 0:37
2 Answers
This is a result of my former undergraduate adviser Marshall Hall. See http://www.ams.org/journals/proc/1952-003-04/S0002-9939-1952-0050579-7/S0002-9939-1952-0050579-7.pdf. (Hall states the result in terms of differences $f-g$, but if $g$ is a permutation then so is $-g$, so $f-g=f+(-g)$ is a sum of two permutations.)
You can find some information about what sequences can appear as differences of permutations in this paper of Bebeacua, Mansour, Postnikov, and Severini: http://math.mit.edu/~apost/papers/xray.pdf
EDIT: This does not really address the question posted, which is completely answered by Professor Stanley's response, but I still think the above paper may be relevant to people interested in what kinds of sequences appear as differences of permutations (and shows that there are still interesting things to explore here).