Remoteness

After the last bit of bureaucratic nonsense, what a relief to turn to mathematics again. Maximilien Gadouleau and I have just submitted a paper about a concept for finite metric spaces somewhat related to domination, which we call remoteness. It is on the arXiv here.

One of the most important contexts for finite metric spaces is coding theory. You send a message through a noisy channel, and some errors occur during transmission; the more errors, the further the received message is from the transmitted one, in some notion of distance. (I will assume, for simplicity, that the distance between transmitted and received message is the number of errors made.)

Let then C be a code, a subset of the metric space X of all possible messages. We restrict the transmissions to elements of C. Now two important parameters of C are

  • the packing radius, the largest number r such that the balls of radius r centred at the codewords are pairwise disjoint; and
  • the covering radius, the smallest number R such that the balls of radius R centred at the codewords cover the whole space X.

If we use nearest-neighbour decoding, assuming that the transmitted word is the codeword nearest to the received message, then the packing radius is the largest number of errors such that nearest-neighbour decoding surely gets the right result; while the covering radius is the largest number of errors for which nearest-neighbour decoding does not surely get the wrong result.

The covering radius can be defined as maxx∈X minc∈C d(x,c), where d is the distance function. Max suggested that we consider a related parameter, which he called remoteness, defined to be minx∈X maxc∈C d(x,c). This is the smallest radius of a ball containing the whole code C (its centre is not required to be a codeword).

We are particularly interested in working out this concept in the context of the symmetric group Sn; the distance between permutations g and h is the number of points in {1,…,n} on which they disagree, that is, n−fix(gh-1), where fix(x) is the number of fixed points of the permutation x. In view of the relation between covering radius and remoteness, this paper is the sequel to one I wrote with Ian Wanless about covering radius of sets of permutations.

There is lots of stuff here, involving Latin squares and rectangles and various other things. But the part that I want to discuss here concerns the case where C is a group, and in particular is a transitive group. So I will call it G from now on.

The analysis depends on a result which I think deserves to be better known than it is. Let G be a transitive permutation group on {1,…,n}. By the Orbit-Counting Lemma, the average number of fixed points of elements of G is 1. In other words, the average distance of elements of G from the identity permutation is n−1. But, in fact, this is true if the identity is replaced by any permutation whatever; that is, the average value of fix(gx-1), as g runs over G, is 1, for any permutation x. (This is the coset form of the orbit-counting lemma, since it says that the average number of fixed points of the elements in any coset of a transitive group is equal to 1.)

From this we immediately get a dichotomy.

For a transitive permutation group of degree n, one of the following is true:

  • the covering radius and the remoteness are both n−1;
  • the covering radius is smaller than n−1, and the remoteness is n.

For the average distance from a permutation x to G is n−1; so either all distances are n−1, or some are n and some are smaller than n−1. The first case in the displayed statement occurs if and only if there is a permutation x for which the first of these alternatives holds.

This means that, unlike covering radius, where there are some interesting open problems about its precise value, for remoteness there are only two options. We have some results, but cannot resolve the question completely, so there is a decision problem here for anyone who wants to try it. (Note that the condition “remoteness n” is closed upwards.)

The two possibilities can be characterised as follows. An orbital is an orbit of G on ordered pairs; it is non-diagonal if the components of the ordered pairs are unequal. If G is transitive, then there is a bijection between the orbitals of G and the orbits of the stabiliser of a point.

Now a permutation x lies at distance n−1 from all elements of G if and only if it maps each non-diagonal pair to one in a different orbital. Some low-hanging fruit follow from this: for example:

  • If there is an orbit of a point stabiliser of size at least n/2, then the remoteness is n. For the corresponding orbital cannot be disjoint from its image under any permutation. In particular, this is true if G is doubly transitive.
  • If G is a normal subgroup of a doubly transitive group H but is not itself doubly transitive, then the remoteness is n−1. For H/G permutes the non-diagonal orbitals transitively; by Jordan’s theorem there is an element fixing none of them.
  • If G is contained in the automorphism group of a self-complementary graph or a self-converse tournament (for example, a Paley graph or tournament), then the remoteness is n−1. For a permutation mapping the graph to its complement, or the tournament to its converse, does what is required.
  • The condition “remoteness n−1″ is in NP. For we can compute the orbitals in polynomial time, and if the permutation x is given, check that it maps each pair to one in a different orbital.

We obtained various other results too, for example:

  • If G has odd order, then its remoteness is n−1.
  • If G has even order and acts regularly, then the remoteness is n if and only if the Sylow 2-subgroups are cyclic. (This uses the truth of the Hall–Paige conjecture, which is rumoured to be now proved, using CFSG.)
  • If G is dihedral of order 2n, then the remoteness is n−1 if and only if n is congruent to 1 or 5 (mod 6).

So there is where we got to. Can you give a necessary and sufficient condition for a transitive group to have remoteness n−1? Or at least give an efficient decision algorithm?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, mathematics, open problems, symmetric group and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s