Improved Lower Bounds for Permutation Arrays Using Permutation Rational Functions

Abstract

We consider rational functions of the form $V(x)/U(x)$, where both $V(x)$ and $U(x)$ are polynomials over the finite field ${\mathbb{F}}_q$. Polynomials that permute the elements of a field, called {\it permutation polynomials ($PPs$)}, have been the subject of research for decades. Let ${\mathcal{P}}^1({\mathbb{F}}_q)$ denote ${\mathbb{Z}}_q\cup \{\infty \}$. If the rational function, $V(x)/U(x)$, permutes the elements of ${\mathcal{P}}^1({\mathbb{F}}_q)$, it is called a {\em permutation rational function (PRf)}. Let $N_d(q)$ denote the number of PPs of degree $d$ over ${\mathbb{F}}_q$, and let $N_{v,u}(q)$ denote the number of PRfs with a numerator of degree $v$ and a denominator of degree $u$. It follows that $N_{d,0}(q)=N_d(q)$, so PRFs are a generalization of PPs. The number of monic degree 3 PRfs is known [11]. We develop efficient computational techniques for $N_{v,u}(q)$, and use them to show $N_{4,3}(q)=(q+1)q^2(q-1{)}^2/3$, for all prime powers $q\le 307$, $N_{5,4}(q)>(q+1)q^3(q-1{)}^2/2$, for all prime powers $q\le 97$, and $N_{4,4}(p)=(p+1)p^2(p-1{)}^3/3$, for all primes $p\le 47$. We conjecture that these formulas are, in fact, true for all prime powers $q$. Let $M(n,D)$ denote the maximum number of permutations on $n$ symbols with pairwise Hamming distance $D$. Computing improved lower bounds for $M(n,D)$ is the subject of much current research with applications in error correcting codes. Using PRfs, we obtain significantly improved lower bounds on $M(q,q-d)$ and $M(q+1,q-d)$, for $d\in \{5,7,9\}$.