Skip to main content
1 of 9
Anurag
  • 1.2k
  • 1
  • 20
  • 29

Enumerating certain types of permutation polynomials.

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism) all the permutation polynomials $f(x)$ on $GF(q^3)$ satisfying the following conditions:

  1. $f(x) = af(x)$ for all $a \in GF(q)$,
  2. $Tr(x f(x)) = 0$.

I know that for for $q = 3$ there are $5$ isomorphism classes and in total there are $3852$ such polynomials. For $q = 4$, there are $18534400$ of them. This is from computer computations.

It is not hard to see that such polynomials correspond to perfect matchings in the incidence graph of the projective plane $PG(2,q)$. By [1] a $k$-regular bipartite graph of size $2n$ has at least $$\left( \frac{(k-1)^{(k-1)}}{k^{(k-2)}} \right)^n$$ perfect matchings. Therefore there is a lower bound of $\frac{q^{qn}}{(q+1)^{n(q-1)}}$ where $n = 1 + q + q^2$.

To the finite field experts: is there a way of theoretically classifying such polynomials? Can we give some bounds on the total number? Any suggestions on what approach might work?

[1] http://homepages.cwi.nl/~lex/files/countpms2.pdf

Anurag
  • 1.2k
  • 1
  • 20
  • 29