Zhibo Chen

Let $Z_n$ denote the ring of integers modulo $n$ ($> 1$). It is well known that any function $f:Z_n \rightarrow Z_n$ can be represented by a polynomial over $Z_n$ if and only if n is a prime. We show that the transposition ($(0 1)$) has a polynomial representation if and only if $n$ is a prime. We also discuss (for general $n$) how to determine if a function $f\colon Z_n \rightarrow Z_n$ can have a polynomial representation.

It is well known that in a symmetric group $S_n$, any permutation can be decomposed as a product of cycles and any cycle can be expressed as a product of transpositions. D′enes (1959) proved that the number of representations of an $n$-cycle as a product of a minimal number of transpositions is equal to $n^{n-2}$. In this talk we present a graph-theoretical method to determine whether an $n$-cycle can have a minimal representation by a given set of transpositions.