  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.
