Posted by Jason Polak on 02. July 2017 · 1 comment · Categories: paper

I’ve submitted paper! The results stem from a pretty simple question that can be understood with an first course in abstract algebra. This post will explain the question and give a teaser of some of the results.

Let $R$ be a ring. A polynomial $f\in R[x]$ induces a function $R\to R$ given by $a\mapsto f(a)$. It turns out that this function is sometimes bijective. When this happens, we say that $f$ is a permutation polynomial. There are some easy examples: $f(x) = x + a$ for $a\in R$ is always injective, and always bijective if $R$ is finite. But there are less trivial examples as well. For instance, the polynomial $f(x) = x^6 + x^4 + x^2 + x$ permutes $\Z/27$.

Permutation polynomials are perhaps most well-known when $R$ is a finite field. In this case, every function $R\to R$ can be represented by a polynomial. In particular, every permutation can so be represented. This result is not particularly deep. More interesting for finite fields is to determine which polynomials are permutation polynomials, and to find certain classes of them.

More interesting things happen when $R$ is a finite ring that is not a field. Then it is not necessarily true that all functions $R\to R$ can be represented by polynomials. Can all permutations be represented by polynomials? The answer is in fact no! So, it makes perfect sense to define a group ${\rm Pgr}(R)$ as the subgroup of the symmetric group on $R$ generated by all permutations represented by polynomials. Let’s call it the polypermutation group of $R$.

Under this notation, ${\rm Pgr}(R)$ is the symmetric group on $R$ when $R$ is a finite field. What about other rings? This is what brings us to the topic of my latest paper: The Polypermutation Group of an Associative Ring. This paper started out by asking the simple question:

What is ${\rm Pgr}(R)$ for some common finite rings?

In my paper I’ve concentrated on $\Z/p^k$ where $p$ is a prime. The general case of $\Z/n$ for an integer $n$ reduces to this case via the Chinese Remainder Theorem.

Upon my initial investigations I found that ${\rm Pgr}(\Z/p^k)$ is actually a little complicated. It turns out to be easier when $p \geq k$. In this case I wrote down an explicit formula for the cardinality of ${\rm Pgr}(\Z/p^k)$. I already mentioned that when $k = 1$ the result is classical and is $p!$ because then $\Z/p$ is a finite field. One of my results is:

Theorem (P-). Let $p$ be a prime and $k\geq 2$ be an integer with $p\geq k$. Then:
$$|{\rm Pgr}(\Z/p^k)|= p![(p-1)p^{(k^2 + k-4)/2}]^p.$$

Whoa, that’s complicated. But it’s not hard to see that this is going to be less than $(p^k)!$, showing that there are indeed some permutations that cannot be represented by polynomials in this case. In fact, one can be more precise in the case of $k=2$. In this case, one can compute the group ${\rm Pgr}(\Z/p^2)$ itself, though I’ll leave you to read the paper to find out what it is!

1 Comment

  1. Whoa indeed! This looks like a very interesting paper and I look forward to reading it. :)

Leave a Reply to James Bond Cancel reply

Your email address will not be published. Required fields are marked *