| Related sites for http://www.maths.qmw.ac.uk/~pjc/pgprob.html |
| Trinomials_with_Interesting_Galois_Groups Parametrisation of trinomials with Galois groups contained in the simple group G168. | | The_World_of_Groups Part of the World Wide Algebra project. Open problems in combinatorial group theory, a list of personal web pages, conferences and seminars, and useful links. | | Caribbean_African_Ancestry_Project A population genetic study with goal of identifying ethnic groups that contributed to the Caribbean population. Features research background, photos and information on methodology. | | Accumet_Materials High temperature labware, made of refractory materials. | | Agilent_Educator\'s_Corner Offers a variety of general purpose test and measurement equipment for engineering education labs. | | All_World_Scientifics__Wine_Testing_Supplies A full-line scientific supplier offering laboratory equipment with a focus on wine testing. | | Alpkem_Technicon_AutoAnalyzer_Instruments A source for instrumentation used in soil, water, and air analysis. International distributor and manufacturer of peristaltic pump tubing. | | APS_Labware Specializes in design, manufacturing and service organisation of platinum alloy products, including crucibles and evaporating dishes. | | Arrington_Research Eye movement measurement and analysis software and hardware systems. Eye tracking: ViewPoint Eye Tracker software and hardware. | | Astell_Scientific Manufacturers of autoclaves and sterilizers for laboratory and medical applications. | | Asylum_Research Supplier of innovative instrumentation for nano-science and technology. The focus of the site is on Atomic Force Microscopy instruments and supplies. | | ASYS_Hitech Manufactures microplate readers, washers, dispensers and shaker/incubators for microplate applications. Includes company profile, product specifications, and documentation downloads. | | Atago_Co_,_Ltd_ Manufactures refractometers and polarimeters for use in the food and beverage industry, research labs, industrial facilities, universities and clinics. | | Automated_Fusion_Technology Sample preparation for (XRF) and (ICP-AE) spectrometric analysis and platinum ware. | | Axyos Australian manufacturer of laboratory and scientific equipment to ISO 9001 specifications. Product line includes a range of cell culture and incubation products. | | Bellingham_and_Stanley_Ltd Manufactures refractometers and polarimeters. | | Big-Dipper_Technochem_Institute Offers chemical analyzers, and meters for moisture, humidity, pH and conductivity, in China. | | Biochrom Manufacturer of amino acid analysers, UV/visible spectrophotometers, microplate readers, low volume liquid dispensers and gel electrophoresis equipment. Product information, company profile, news and | | Bioscreen_C_MBR_homepage A proven precision incubator and a culture growth monitoring instrument (OD reader) for up to 200 samples. Also the source for consumables and information regarding the instrument. | | Boeckeler_Instruments Manufacturer of precision video measuring devices for the industrial, biomedical, and presentation markets. | | Brookhaven_Instruments Instruments for particle sizing, laser light scattering, zeta potential and polymer and particle characterisation. Also sells microspheres and certified standard particles. | | Brüel_and_Kjaer Manufactures transducers, instruments and software for sound, acceleration, and vibration measurement and analysis. | | Burkard Manufacturer of a range of instruments, equipment and systems, standard and novel developments for entomological, environmental and agricultural research. | | Caldon,_Inc Specializes in advanced measurements based on the movement of sound waves through fluids. | | The_CAL2k_Calorimeter_System The CAL2k Calorimeter System is the most advanced calorimeter system available today. The system was designed and manufactured by DDS. | | Caloris_Group_S_A_ Furnaces for heat treatment, dental laboratories, and calcination of organic materials, as well as ovens, incubators, thermostatic baths, hospital furniture, electro-thermal Soxhlet heating mantles, a | | CE_Elantech Elemental analysis instrumentation. | | Chemplex_Industries Specializing in x-ray spectrochemical sample preparation equipment, supplies and accessories. | | Climatic_Test_Systems Climatic, testing, humidity, temperature, environmental testing, test equipment, testing chambers | | Constellation_Technology_Corporation analytical instruments, instruments, scientific instruments, nuclear instruments, radiation detection, multichannel analyzer, spectrometers, | | Contherm_Scientific_Equipment_Manufacturer Manufacturer of ovens, incubators, environmental chambers, water baths, tissue culture and plant growth chambers for industrial and scientific research. | | Copley_Scientific_Ltd_ Catalogue of equipment for the cosmetic and pharmaceutical research and QC/QA lab. | | Costech_Analytical_Technologies Supplier of consumables and elemental analyzers for CHNS-O. | | CSC_Scientific_Company_Inc_ Manufacturer and distributor of laboratory equipment. Areas of concentration: Moisture Analysis, Surace Tension Analysis, Titration Analysis, Particle Size Analysis. | | Darwin_Chambers_Company Manufacturer of incubators, thermal cycling chambers, environmental chambers, and stability chambers. | | Data_Support_CO__Inc_ Rapid moisture/solids analysis, a line of new and reconditioned microwaves and infrared moisture/fat analyzers. | | Day-Impex Stainless steel dewar flasks and containers. . | | DB_Robinson_Group_of_Companies Manufacturer of specialized laboratory equipment for the petroleum and petrochemical industries. | | DC_Scientific_Glass_Inc_ A full-service scientific glassblowing and glassware repair facility offering products and services worldwide in petroleum testing, environmental testing, heating mantles, thermometers, and distillat | | Demondo Digiflume digital drainage burette, an electronic volume measurement for petrophysical, rock-mechanics and core-analysis experiments |
|
Permutation Group Problems Problems on Permutation Groups  These are research problems containing notes and references to solutionsif they exist. There is also a list of old problemsfrom my homepage; if you are interestedin exercises on permutation groups, there are many in mybook, and you can find somefurther exercises on the web. You may also be interested in the Permutation GroupsResources Page, or the page devoted toproblems from the paperP. J. Cameron, Permutations, pp. 205-239 in Paul Erdős and his Mathematics,Vol. II (ed. G. Halász, L. Lovász, M. Simonovits andV. T. Sós), Bolyai Society Mathematical Studies 11, Springer,Berlin, 2002.Problem 1.Is there a function F(m,p) (where the first argument is aninteger and the second a prime) such that, if G is a finitepermutation group which is a p-group with m orbits,each of size at least pF(m,p), thenG contains a fixed-point-free element? (This is a very old problem;for p=2, it is implicitly due to Isbell in 1959.)Problem 2.Let G be a permutation group on an infinite set X. There is agraded algebra A[G] associated with G as follows:the nthhomogeneous component Vn is the set of allG-invariant functions fromthe set of n-element subsets of X to the complex numbers;multiplication is defined by the rule that, if f in Vn, g in Vm,and K is an (n+m)-element set then(fg)(K) = sum f(L)g(K-L): L subseteq K, |L| = n.The constant function e in V1 with value 1 is not a zero-divisor. We say that G is entire if A[G]is an integral domain, andstrongly entire if A[G]/eA[G] is anintegral domain. It isconjectured that G is (strongly) entire if and only if it has nofinite orbits on X. In the absence of a proof of this conjecture,can one show the following:If the permutation groups G1 on X1 andG2 on X2are (strongly) entire, then G1 × G2 (in its intransitive action on X1 union X2)is (strongly) entire.Note: Maurice Pouzet has proved that, if G hasno finite orbits, then G is entire. This appears inTheor. Inform. Appl. 42 (2008), 83-103.Problem 3.Let S be the symmetric group on the infinite set X.Consider the product action of S2 on X2, and let an be the number of orbits on subsets of size n.The problem is to find a formula for, or an efficient means ofcalculating, an.The number an has various other interpretations: It is the number of zero-one matrices with n ones,with no zero rows or columns, up to row and column permutation. It is the number of bipartite graphs with n edges,no isolated vertices, and a distinguished bipartite block, up toisomorphism.The initial terms in the sequence can be foundhere.Problem 4. This problem is due to Dragan Marusicand Mikhail Klin. It appears in theresearch problems from the 15thBritish Combinatorial Conference.A permutation group G is 2-closed ifany permutation which preserves the orbits of G onordered pairs belongs to G.Problem: is there a 2-closed transitive permutation group containing no non-identity semiregular subgroup?(Not every transitive permutation group contains anon-identity semiregular subgroup; the smallest counterexample hasdegree 12.)Note: Michael Giudici has some partial results on this problem,including the statement that every minimal normal subgroup of anycounterexample to the conjecture is intransitive. See: P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marusic and L. A. Nowitz,Transitive permutation groups without semiregular subgroups, J. London Math. Soc. (2) 66 (2002), 325-333. M. Giudici, Quasiprimitive groups with no fixed point free elements of prime order, J. London Math. Soc. (2) 67 (2003), 73-84.Problem 5.A base for a permutation group Gis a sequence of points whose pointwise stabiliseris the identity; it is irredundant if no point in the sequence isfixed by the stabiliser of its predecessors. The group G is said tobe an IBIS group if any two irredundant bases have the same numberof elements. If this condition holds, then the irredundant bases are thebases of a matroid (and conversely). It is too much to ask for aclassification of IBIS groups (since, for example, any semiregulargroup is IBIS); but can one classify the matroids which can arise?Note added 22 November 2001: The matroids include all those representableover finite fields (with each element replaced by q parallel elements,where q is the field order). See Problem 18 below for further details.Problem 6. McIver and Neumann, Quart. J. Math. (2) 38 (1987), 473-488, showed that a subgroup of the symmetricgroup Sn can be generated by at most n/2 elements,provided that n is at least 4. Problem: Give an efficientalgorithm to find such a generating set, preferably an "on-line" algorithm(one which, given a small generating set for H and a permutationg, finds efficiently a small generating set for the group generatedby H and g).Problem 7. Martin Liebeck and Aner Shalev have shown that there isan absolute constant c such that an almost simple primitive finitepermutation group, which is not a symmetric or alternating group actingon subsets or partitions, or a classical group acting on subspaces orcomplementary pairs of subspaces in its natural module, has a base ofsize c. Does this assertion hold with c = 5 (if we allow finitely many more exceptions)?Note added 13/7/2007: It has now been proved by Burness et al.that the assertion holds for c = 6, with a singleexception, the Mathieu group M24.Problem 8.Let G be a transitive permutation group on a set X.For each orbit Oi of G on X2,we associate a basis matrix Ai, whose xy entry is equal to 1 if (x,y) is in Oi,or 0 otherwise. The matrices Ai span an algebra, whichis the centraliser algebra of the permutation group G.A subalgebra of the centraliser algebra which contains the identity matrixand is spanned by symmetriczero-one matrices is the Bose-Mesner algebra of anassociation scheme on the set X, and G actsas a group of automorphisms of this association scheme. There is alwaysat least one such subalgebra, namely the span of I and J-I, where J is the all-one matrix. We call this subalgebraor association scheme trivial.Problem: For which transitive permutation groups is it true thatthe only association scheme invariant under G is the trivial one?This class of groups includes the 2-homogeneous groups. Any such groupmust be primitive, and (if not 2-homogeneous) is either of diagonal typeor almost simple. Examples which are not 2-homogeneous do exist. Some can be found in table3.5.1 of I. A. Faradzev, M. H. Klin and M. E. Muzichuk, "Cellular rings andgroups of automorphisms of graphs", pp. 1-152 in Investigations inAlgebraic Theory of Combinatorial Objects (ed. I. A. Faradzev, A. A.Ivanov, M. H. Klin and A. J. Woldar), Kluwer, Dordrecht, 1994. The smallest isthe group PSL(3,3) acting on the cosets of PO(3,3); this group hasdegree 234. (I am grateful to Leonard Soicher for this reference).No such group of diagonal type is known, and the problem of deciding whetherany such group exists remains open. There are none having two or threesimple factors in their socle. See: P. P. Alejandro, R. A. Bailey, and P. J. Cameron,Association schemes and permutation groups,Discrete Math. 266 (2003), 47-67. P. J. Cameron, Coherent configurations, association schemes, and permutation groups, pp. 55-71 in Groups, Combinatorics and Geometry (ed. A. A. Ivanov, M. W. Liebeck and J. Saxl), World Scientific, Singapore, 2003.Problem 9. A derangement problem.Let d(k,n) be the proportion of derangements inthe symmetric group Sn in its action on k-sets.Then d(k,n) tends to a limit a(k) as n tends toinfinity. (So, for example, a(1)=e-1 - this is the usual"derangement problem".) Does a(k) tend monotonically to 1 as ktends to infinity?Problem 10. It is known that, for any finite group G, ifx(G,n) is the number of (unlabelled) graphs on n verticeswhose automorphism group contains G, and y(G,n) the numberwhose automorphism group is precisely G, then the ratioy(G,n)/x(G,n) tends to a limit as n tends to infinity.Problem: Does this result hold for trivalent graphs? What aboutother special classes of graphs such as strongly regular graphs? Problem 11.The Parker vector of a finite permutation group G is then-tuple whose kth component is the number of orbits of Gon the set of k-cycles occurring in elements of G.If G has the same Parker vector as a Frobenius group(resp. a 2-transitive group), is it a Frobenius group (resp.a 2-transitive group)?Problem 12.Is the following true? If P is a 2-group which is not elementary abelian, then some non-identity element of the centre of P is a square.The answer to this question is negative. The smallest counterexampleshave order 128, and there are two of them. This was found by AlexanderHulpke and Andreas Caranti. Alexander provided the following example in GAP:gap> g:=SmallGroup(128,36);gap> z:=Centre(g);Group([ f6, f7 ])gap> r:=List(ConjugacyClasses(g),Representative);;gap> s:=Filtered(r,i->Order(i)>2);;gap> List(s,Order);[ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ]gap> Set(List(s,i->i^2));[ f4,f5,f4*f7,f5*f6,f3*f4*f5,f3*f4*f5*f6,f3*f4*f5*f7,f3*f4*f5*f6*f7 ]gap> List(last,i->i in z);[ false, false, false, false, false, false, false, false ]If not, is the following weaker statement true? If P is a 2-group which is not elementary abelian, and Q is a core-free subgroup of P, then there is an element lying in no conjugate of Q which is a square.Avinoam Mann also suggested the above group as a possible counterexample to thesecond question. However, Steve Linton and John Murray both checked thatthere is no core-free subgroup Q for which it is a counterexample. Sothe question is still open.Solution (13 September 2004):The answer to the second question is alsonegative. Pablo Spiga found that the group of order 128 with generators(1,2,7,3)(4,8)(5,11)(6,9)(10,14)(12,16,13,15),(1,4,7,5)(2,8)(3,11)(6,13,14,12)(9,15)(10,16), and(1,6)(2,9,3,10)(4,12,5,13)(7,14)(8,15)(11,16)is a counterexample. Indeed, in this group the set of elements withfixed points coincides with the set of squares. This group isSmallGroup(128,836) in the GAP library. The motivating question, whether a vertex-transitive trivalent graphnecessarily has a semiregular automorphism of order greater than 2, iscurrently still open. (But see Problem 23.)Problem 13.It is known that, if G is a permutation group in which everynon-identity element fixes exactly k points, then either Ghas a fixed set of size k, or G is one of a finitelist of groups (for given k). The problem is to find a good upperbound (in terms of k) for the orders of the groups in this finitelist.For example, when k=2, the groups are the tetrahedral, octahedraland icosahedral groups, acting on the vertices, edges and faces of thecorresponding polyhedra. (Every rotation has an axis, so has just twofixed points in this action.) So the correct bound is 60.(This is a theorem of Iwahori, J. Fac. Sci., Univ. Tokyo11 (1964), 47-64.)An upper bound in terms of k has been found by C. Franchi,On permutation groups of finite type,European J. Combinatorics 22 (2001), 821-837.Problem 14.Let G be a finite group, a an automorphism of G,and X the semidirect product of G by the group generatedby a. Suppose that every element of X not in Ghas prime order p.It follows that the centraliser of a in G is a p-group.Let its order be pm.A theorem of Kegel (Math. Z. 75 (1961), 373-376) shows thatG is nilpotent. Then a theorem of Khukhro (Mat. Zametki38 (1985), 652-657) shows that G has a normal subgroupwhose nilpotency class and index are bounded by functions of pand m.Is it true that the nilpotency class of G is bounded by a functionof p and m?This question has been settled in the affirmative by Andrei Jaikin, using a theoremof E. Khukhro, On locally nilpotent groups admitting asplitting automorphism of prime order, Mat. sb. 130 (1986),120-127.Problem 15.Let Sn and Pn be the respectivelythe symmetric group (the set of all permutations) and the set of allpartitions on the set [1..n]. There is a functionF from Sn to Pn whichreplaces every permutation by the partition corresponding to itscycle decomposition. (a) Is there an efficient method to decide whether a set of partitionsis the image under F of a subgroup of Sn?(b) If G and H are subgroups of Sn suchthat F(G)=F(H), then G and Hhave the same order. Are they necessarily isomorphic?Note added 19 May 2000: The answer to (b) is negative. Eamonn O'Brienhas shown that there are two pairs of groups of order 64 (numbers19 and 111, and 94 and 249, in the lists in MAGMA and GAP), which acttransivitely on 16 points, such that the two groups in each pair giverise to the same sets of cycle partitions. You can finda GAP program to verify this.See P. J. Cameron, Partitions and permutations, Discrete Math.291 (2005), 45-54.Problem 16.Let G be a subgroup of the symmetric group Sn.For i = 0, ..., n, let pi be theprobability that a random element of G has exactly ifixed points, and let Fi be the number of orbitsof G on i-tuples of distinct points. These two sequencesdetermine each other. In fact, N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. Leavitt, D. T. Oseand D. A. Jackson,Communications in Algebra 21 (1993), 3259-3275, showedthat, if P(x) = Sum pi xiand F(x) = Sum Fi xi/i! , thenF(x) = P(x+1).Now consider the linear analogue. Let G be a subgroup of the general linear group GL(n,q). For i = 0, ..., n, letpi be the probability that the fixed points of a randomelement form precisely an i-dimensional subspace, andlet Fi be the number of orbits of G onlinearly independent i-tuples. Again the two sequences determineeach other.Problem: Express the relation between these two sequences in termsof generating functions.Note: This problem is now solved (2 August 2000). It is just acase of finding the right definitions of the q-analogues!See: P. J. Cameron and S. Majid, Braided line and counting fixed points ofGL(d,Fq),Communications in Algebra 31 (2003), 2003-2013. P. J. Cameron, Fixed points and cycles, pp. 49-60 in Finite Geometries: Proceedings of the Fourth Isle of Thorns Conference (ed. A. Blokhuis, J. W. P. Hirschfeld, D. Jungnickel and J. A. Thas), Kluwer, Boston, 2001.Problem 17. (An old problem revisited)Let G be a permutation group on the infinite set X.Assume that G is oligomoprhic, that is, G hasonly finitely many (say fn) orbits on the set ofn-element subsets of X. Dugald Macpherson, Proc.London Math. Soc. (3) 46 (1983), 471-486, showed that,if G is primitive on X (preserves nonon-trivial equivalence relation) but not highly set-transitive((that is, fn > 1 for some n), then thesequence (fn) grows exponentially, that is,limsup (fn)1/n > 1. These twoassumptions apply throughout this problem, though analogous problemscan be posed with primitivity relaxed. Is it true that lim (fn)1/n existsfor any group G? What is the smallest possible value of the limsup? (Macpherson's lowerbound of 21/5 has been improved by F. Merola to about 1.324. The smallest known value is 2.) What is the smallest limit point of the set of values of the limsup?Further information on such sequences is available in mysurvey article.Problem 18.A base for a permutation group is a sequence of points whose stabiliseris the identity; it is irredundant if no point is fixed by thestabiliser of its predecessors. Cameron and Fon-Der-Flaass, Europ. J.Combinatorics 16 (1995), 537-544, called a permutation groupan IBIS group if all irredundant bases have the same number ofelements; they showed that the irredundant bases of an IBIS group are thebases of a matroid.Problem: What is the relation between the Tutte polynomial of thematroid and the cycle index of the permutation group? It is known that sometimes the first determines the second and sometimesvice versa. Perhaps there is a gadget which generalises both!See P. J. Cameron,Cycle index, weight enumerator and Tutte polynomial, Electronic J. Combinatorics9(1) (2002), #N2 (10pp).Problem 19.How large is the largest antichain of subgroups of the symmetric groupSn? More precisely, estimatean/sn, where an isthe size of the largest antichain and sn the totalnumber of subgroups.Problem 20.Let L(G) be the subgroup lattice of the finite group G.Is the following true or false? Suppose that the Boolean latticeB(n) of subsets of an n-element set is embeddableas a meet-semilattice of L(G), and suppose that n is maximal with this property. Then there is an embedding of B(n)as meet-semilattice, such that the least element of B(n) is a normal subgroup of G.Note: The quaternion group Q8 shows that wecannot make the least element of B(n) correspond to theidentity in general.Problem 21.Let Z(G) denote the cycle index of the permutation groupG, and let Fn*(G) be the number oforbits of G on the set of all n-tuples of its permutationdomain.Let G and H be permutation groups acting on sets X andY respectively. We consider G×H as a permutationgroup on X×Y. We have Z(G×H) =Z(G)oZ(H), wheresiosj =(slcm(i,j))gcd(i,j), and theoperation is extended multiplicatively and additively; Fn*(G×H) =Fn*(G)Fn*(H).The second assertion is trivially proved directly. The challenge is to deduceit from the first; this will probably require methods of dealing with thesevery strange operations on polynomials.Solution: Solved by Daniele Gewurz. Seea paper by Daniele Gewurz, Francesca Merola and me inDiscrete Mathematics 308 (2008), 386-394; doi:10.1016/j.disc.2006.11.054Problem 22.Let G be a Frobenius group with Frobenius kernel N and Frobenius complement H having orders n and hrespectively. Number the elements of N as x1,...,xn. Now letXij be the n × n matrixwith (k,l) entry equal to the cardinality of the intersection ofxi-1Hxk and xj-1Hxl.Note that Xii = hI while, for i andj distinct, Xij is a zero-one matrix.Is it true thatSumk XikXkj = nXij+h(h-1)J,where J is the all-one matrix?Solution: This problem is now solved in the affirmative (but I have lost the solution . . .)Problem 23.Since Problem 20 in the list of old problemshas a negative solution, the following problem (due to John Sheehan and me,BCC problem 17.12) is open again.Is it true that a vertex-transitive trivalent graph has a semiregularautomorphism (one with all cycles of the same size) of order greaterthan 2?Note: This has now been settled affirmatively: seeP. J. Cameron, J. Sheehan and P. Spiga,Europ. J. Combinatorics 27 (2006), 924-930; doi:10.1080/00927870701404812,and a stronger result has been given byCai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.Problem 24.Let G be a permutation group of degree n. The base sizeof G is the smallest number b(G) of points whosestabiliser is the identity; the separation number of G is thesmallest size of a set S of points such that, for any two distinctpoints x,y, there exists s in S such that xand y lie in distinct orbits of the stabiliser of s.Clearly b(G) <= s(G). Is it truethat, if G is primitive but not 2-transitive, thens(G) <= b(G) log n? See Combinatorics Study Group notes on this problem(PDF file).Problem 25.Let F be the set of sequences F of positive integers whose nth term is the number of orbits on n-tuples of distinct elementsof an infinite permutation group.Is F closed under pointwise multiplication?I conjecture that the answer is "no". Specifically, let F be thesequence (1,2,4,10,26,...) whose nth term is the number of solutions of g2=1 in the symmetric group of degree n. Thissequence belongs to F, but I conjecture that the sequence (1,4,16,100,676...)whose terms are the squares of the terms in this sequence is not in F.Remark: The set of sequences counting orbits of permutation groups onall n-tuples is closed under pointwise multiplication. Moreover, theset of sequences counting orbits on n-tuples of distinct elements forgroups with the property that the stabiliser of a finite set fixes noadditional points is closed under pointwise multiplication.Further remark: The answer in general is "no": if G is thestabiliser of a point in the symmetric group, the sequence begins 2, 3, 4, ...,but a group with 4 orbits on points must have at least 12 orbits on orderedpairs of distinct points. It is harder for transitive groups(where a possible counterexample is given in the question), and still more sofor primitive groups.Problem 26.I conjectured in 1972 that there is a function f with the followingproperty: Let G be a finite primitive permutation group, with rankr; let s be the subrank of G, the maximum rankof a point stabiliser on any of its orbits. Then either G has a base of size 2; or r <= f(s).Perhaps the time has come to revisit this conjecture.The most extreme example I know is an extension of a 2n-dimensionalvector space over GF(2) by a dihedral group of order2(2n+1); this has rank 2n and subrank2n-1+1. So perhaps the conjecture holds with a linearfunction f.Problem 27.Let S be a set of elements of the symmetric group Sn.It is not always true that every element in the group generated by Scan be written as a word in S of length bounded by a polynomial inn. (Take S to be a singleton whose element has maximum possibleorder in Sn.)Problem: If the group generated by S contains a fixed-point-freeelement, can we always find one which is a word of polynomially bounded length?My homepage|Permutation Groups ResourcesPeter J. Cameronp.j.cameron(at)qmul.ac.uk11 September 2007Permutation Groups Pages at Queen Mary:Resources|Lecture Notes|Problems|The Book|Problems from "Permutations"Maths Research Centre |
|
