Source author record

I. Hal Sudborough

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Information Theory math.IT

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Equivalence Relations for Computing Permutation Polynomials

We present a new technique for computing permutation polynomials based on equivalence relations. The equivalence relations are defined by expanded normalization operations and new functions that map permutation polynomials (PPs) to other PPs. Our expanded normalization applies to almost all PPs, including when the characteristic of the finite field divides the degree of the polynomial. The equivalence relations make it possible to reduce the size of the space, when doing an exhaustive search. As a result, we have been able to compute almost all permutation polynomials of degree $d$ at most 10 over $GF(q)$ , where $q$ is at most 97. We have also been able to compute nPPs of degrees 11 and 12 in a few cases. The techniques apply to arbitrary $q$ and $d$ . In addition, the equivalence relations allow the set all PPs for a given degree and a given field $GF(q)$ to be succinctly described by their representative nPPs. We give several tables at the end of the paper listing the representative nPPs (\ie the equivalence classes) for several values of $q$ and $d$ . We also give several new lower bounds for $M(n,D)$ , the maximum number of permutations on $n$ symbols with pairwise Hamming distance $D$ , mostly derived from our results on PPs.

preprint2016arXiv

Constructing Permutation Arrays from Groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1,q) and PGL(2,q) with Frobenius maps to obtain new, improved lower bounds for M(n,d). We give new randomized algorithms. We give better lower bounds for M(n,d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for M(n,n-2) for all n=2 (mod 3) such that n+1 is a prime power.

preprint2006arXiv

Short Proofs for Cut-and-Paste Sorting of Permutations

We consider the problem of determining the maximum number of moves required to sort a permutation of $[n]$ using cut-and-paste operations, in which a segment is cut out and then pasted into the remaining string, possibly reversed. We give short proofs that every permutation of $[n]$ can be transformed to the identity in at most $\flr{2n/3}$ such moves and that some permutations require at least $\flr{n/2}$ moves.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.