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

Hbe a subgroup of the finite groupG. Say that the pair (G,H) isgoodifGcan be generated by a set of representatives of the right cosets ofHinG.

- If core
_{G}(H)=1 thenGis good. Prove this without using the Classification of Finite Simple Groups.- What can be said about the function
f, wheref(n) is the largestmsuch that if the index ofHinGisnand core_{G}(H) can be generated bymelements, 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 3xto 2x, 3x+1 to 4x+1, and 3x-1 to 4x-1 for allx.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 ofconsecutiveprimes tends to the limit log_{e}2 asntends to infinity. Is it true that the limiting distribution of the number of representations of this form is Poisson with parameter log_{e}2?

Problem 36:How large is the largest antichain of subgroups of the symmetric groupS? More precisely, estimate_{n}a/_{n}s, where_{n}ais the size of the largest antichain and_{n}sthe total number of subgroups._{n}

Problem 44:Consider the following decision problem.Let

p_{1}, …,pbe partial permutations_{m}

of a finite setA(that is, bijections between subsets). Suppose that

p_{1}is the identity map onA, and- for any
i,j, there is at most oneksuch thatpextends_{k}po_{i}p._{j}Does there exist a finite set

BcontainingA, and permutationsfof_{i}Bextendingpfor_{i}i=1,…,m, such that, ifpextends_{k}po_{i}p, then_{j}fo_{i}f=_{j}f?_{k}What is the computational complexity of this problem? How is this affected if we insist that

B=A?

Problem 64:

Letnbe a multiple of 8. Is there a finite groupGwith a homomorphism onto the symmetric groupSsuch that no involution in_{n}Gmaps onto a fixed-point-free involution ofS? If so, what is the smallest such group? (For_{n}neven but not divisible by 8, one or other of the double covers ofShas this property.)_{n}

Problem 73:Letabe an algebraic integer. Show that there exists a natural numbernsuch thata+nis a root of the chromatic polynomial of a graph.

Problem 83:Letpbe an odd prime, andkan integer at least 3. Ak-AP decompositionmodpis an arithmetic progressiona_{1}, . . .aconsisting of integers not congruent to 0 or 1 mod_{k}psuch that the group of units ofZ_{p}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 groupsGhave the property that the number of isomorphisms between pairs of subgroups ofGis equal to the number of endomorphisms ofG? (Every abelian group has this property; no non-abelian group is known to do so.)

Problem 98:Anatoly Vershik and I, inAnn. Pure Appl. Logic143(2006), 70–78, gave a “random” construction of isometries of the Urysohn space such that every orbit is dense. The closureAof 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 thatAhas no non-trivial proper closed subgroup? (This is inspired by a question of Stanislav Shkalin.)