Why I’d like to see this solved

I am aware that quite a number of people have been captivated by the problem I posed. So here is the motivation for it, with some additional remarks and commennts. First, to repeat the problem:

Problem: Let n be a positive integer. Show that there exist subsets A1, A2, … An of {1,2,…n} with the properties

  • |Ai| = φ(i) for i = 1,2,…,n;
  • if lcm(i,j) ≤ n, then Ai and Aj are pairwise disjoint, where lcm denotes the least common multiple.

This arises in the “graphs on groups” project. The enhanced power graph of a finite group G is the graph whose vertices are the elements of G, two vertices joined if they generate a cyclic group. Now it is easy to see that any complete subgraph of the enhanced power graph of G is contained in a cyclic subgroup of G. So the first part of the following theorem is clear.

Theorem:

  • The clique number of the enhanced power graph of G is equal to the largest order of an element of G.
  • If the answer to the problem is affirmative, then the chromatic number of the enhanced power graph is also equal to the largest order of an element of G; in other words, this graph is weakly perfect.

We prove the second part by making use to a supposed solution to the problem. We let n be the largest order of an element of G, and use the elements 1,2,…n as colours. We will assign the elements of the set Ai as colours for the elements of order i. If two elements of the same order i are joined, they generate the same cyclic group; this cyclic group has φ(i) generators, and so we have enough colours to give them all different colours. Elements of order i in a different cyclic subgroup are not joined to these ones, and so we can re-use the same colours for them. Now, if two elements of different orders i and j are joined, they lie in a cyclic group whose order is the least common multiplie of i and j; this lcm is at most n, so the colour sets Ai are disjoint. Thus we have a proper colouring with n colours. (The chromatic number cannot be smaller since there is a clique of size n.)

We have proved a little more. For any value of n for which the problem has a positive solution, the enhanced power graph of a group whose largest element order is that value of n is weakly perfect. So you will have to go quite far to look for a counterexample.

You might wonder whether we could get the conclusion of the theorem more easily. After all, for most groups, the set of element orders is not the first n natural numbers. Indeed, we could ask:

Problem: Determine the finite groups in which the set of element orders is {1,2,…,n} for some n; in particular, determine the n which can occur.

There can only be finitely many such values of n. This can be seen by considering the Gruenberg–Kegel graph, whose vertices are the prime divisors of the group order, two vertices p and q joined if the group contains an element of order pq. Now it is known that the GK graph of a finite group has at most six connected components. But for a group satisfying our conditions, any prime in the interval (n/2,n] is an isolated vertex of the graph. Modern strengthenings of Bertrand’s postulate show that the number of primes in this interval grows with n.

Indeed, the hypothesis of this question determines the GK graph: the vertices are the primes up to n, two vertices joined if their product does not exceed n.

One could also ask this question for infinite torsion groups. I don’t know what happens for these.

However, this may not help us very much. Of several approaches I tried to solve the problem, the one I found most promising included the observation that there is no difficulty about choosing the sets Ai for i > n/2; for the only sets Aj we have to avoid correspond to divisors j of i, and there are enough points available to do this. (Similarly, the sets Ai for i < √n are not a problem; they must be pairwise disjoint, but there are enough points for all of them. It is the block in the middle where the problem lies.)

So omitting some primes greater than n/2 will not make the problem easier.

We see, incidentally, that groups with the property that the maximal order of an element coincides with the exponent (so that the orders are just the divisors of n) will not be a problem. Indeed, for any finite group G, there is an integer k such that Gk has this property. But I can’t find a way to exploit this observation.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics and tagged , , . Bookmark the permalink.

3 Responses to Why I’d like to see this solved

  1. kyubivulpes says:

    Consider the set F_n of all irreducible fraction 0<p/q<=1,1<=p,q{1,…,n} then we take A_i=f(D_i).
    The map f is simple, we map all fraction such that (m-1)/n<p/q<=m/n to m. If f(p/q) =f(p'/q') =m then |p/q-p'/q'|<m/n-(m-1)/n=1/n (*)
    1. The restriction of f to D_i is injective: if f(k/i) =f(l/i), then by (*) we have |(k-l) /i|k-l=0 because i<j, then there exist fraction k/i, l/j such that f(k/i) =f(l/j) =m, by (*) we have |k/i-l/j|<j and k/i, l/j is irreducible, 0<|k/i-l/j|n. So for all i, j such that lcm(i, j) <=n, A_i, A_j disjoint.

  2. kyubivulpes says:

    Consider the set F_n of all irreducible fraction 0<p/q<=1,1{1,…,n} then we take A_i=f(D_i).
    The map f is simple, we map all fraction such that (m-1)/n<p/q<=m/n to m. If f(p/q) =f(p'/q') =m then |p/q-p'/q'|k-l=0. So |A_i|=|D_i|=phi(i)
    2. If m in both A_i,A_j then there exist fraction k/i, l/j such that f(k/i) =f(l/j) =m, by (*) we have |k/i-l/j|<1/n, because i,j is different and k/i, l/j is irreducible, we have 0<|k/i-l/j|n. So for all i, j such that lcm(i, j) <=n, A_i, A_j disjoint.

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.