100 problems

For a number of years now I have kept an open problem on my webpage. The 100th problem has just been posted there. It is the following, which will be familiar to readers of this blog.

Let H be a subgroup of the finite group G. Say that the pair (G,H) is good if G can be generated by a set of representatives of the right cosets of H in G.

  • If coreG(H)=1 then G is good. Prove this without using the Classification of Finite Simple Groups.
  • What can be said about the function f, where f(n) is the largest m such that if the index of H in G is n and coreG(H) can be generated by m elements, then (G,H) is good?

Older problems are kept in a file here, with notes about whether any progress has been made. I have just gone through the file. About half of the problems have been solved, in whole or part. Of the unsolved ones (as far as I know), here are a few of my favourites:

Problem 1: In 1956, Rudin defined a permutation of the integers which maps 3x to 2x, 3x+1 to 4x+1, and 3x-1 to 4x-1 for all x. Problem: Determine the cycle structure of this permutation. (This is the “original Collatz problem” predating the famous “3x+1 problem”.)

Problem 17: It is known that the average number of ways in which a positive integer in the range [1,…,n] can be written as a sum of consecutive primes tends to the limit loge2 as n tends to infinity. Is it true that the limiting distribution of the number of representations of this form is Poisson with parameter loge2?

Problem 36: How large is the largest antichain of subgroups of the symmetric group Sn? More precisely, estimate an/sn, where an is the size of the largest antichain and sn the total number of subgroups.

Problem 44: Consider the following decision problem.

Let p1, …, pm be partial permutations
of a finite set A (that is, bijections between subsets). Suppose that

  • p1 is the identity map on A, and
  • for any i,j, there is at most one k such that pk extends pi o pj.

Does there exist a finite set B containing A, and permutations fi of B extending pi for i=1,…,m, such that, if pk extends pi o pj, then fi o fj = fk?

What is the computational complexity of this problem? How is this affected if we insist that B=A?

Problem 64:
Let n be a multiple of 8. Is there a finite group G with a homomorphism onto the symmetric group Sn such that no involution in G maps onto a fixed-point-free involution of Sn? If so, what is the smallest such group? (For n even but not divisible by 8, one or other of the double covers of Sn has this property.)

Problem 73: Let a be an algebraic integer. Show that there exists a natural number n such that a + n is a root of the chromatic polynomial of a graph.

Problem 83: Let p be an odd prime, and k an integer at least 3. A k-AP decomposition mod p is an arithmetic progression a1, . . . ak consisting of integers not congruent to 0 or 1 mod p such that the group of units of Zp is the direct product by the cyclic groups generated by the terms of the progression. (Donald Preece and I found many examples of 3-AP decompositions but no 4-AP decompositions.)

Problem 89: Which finite groups G have the property that the number of isomorphisms between pairs of subgroups of G is equal to the number of endomorphisms of G? (Every abelian group has this property; no non-abelian group is known to do so.)

Problem 98: Anatoly Vershik and I, in Ann. Pure Appl. Logic 143 (2006), 70–78, gave a “random” construction of isometries of the Urysohn space such that every orbit is dense. The closure A of the group generated by such an isometry is abelian and transitive, and so gives the Urysohn space an abelian group structure. Can we make the choice such that A has no non-trivial proper closed subgroup? (This is inspired by a question of Stanislav Shkalin.)


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, open problems, the Web. 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