Maximal sets of permutations constructed from projective planes

✍ Scribed by Peter Lorimer

• Publisher: Elsevier Science
• Year: 1979
• Tongue: English
• Weight: 406 KB
• Volume: 25
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(79)90081-5

✦ Synopsis

On the set of n2+ n + 1 points of a projective plane, a set of ta2 + n -I-1 permutations is constructed with the property that any two are a Hamming distance 2n + 1 apart. Another set is constructed in which every pak are a Hamming distance not greater than 2n + 1 apart. Both sets are maximal with respect to the stated property.

An equidistant permutation array, or EPA, is a set of permutations on a finite set, each pair of which have the same .:image at the same number of points; a maximal EPA is one which cannot be extended without spoiling this property. The first construction produces, from a projective plane of order n, a maximal EPA of n2 + n t-1 permutations on the n2 + n + 1 points of the plane, each pair of which have the same image at n2n points. In the notation of [I] this is a maximal A(n2+n+l, n2-n; n2+n+l). The second construction, also from a projective plane of order n, is of a maximal A(n2+n+l,a(n"-n); m) where the exact value of m will be described later. This permutation array contains yn permutations on the n2 + n + 1 points of the plane, each pair of which have the same image at not less than n: -n points.

If two permutations on a set with G members have the same image at A points they are said to be a Hamming distance a -A apart. Distance here will always mean Hamming distance. If x has the same image under two permutations it will be said that they coincide at x.