Search

A well-known conjecture of Babai states that if G is a finite simple group and X is a generating set of G, then the diameter of the Cayley graph Cay ( G , X ) is bounded above by ( log ⁡ | G | ) c for some absolute constant c. The goal of this paper is to prove such a bound for the diameter of Cay ( G , X ) whenever G = S L ( n , p ) and X is a generating set of G which contains a transvection. A natural analogue of this result is also proved for G = S L ( n , K ) , where K can be any field.

Let X be a projective K3 surface over C . We prove that its Cox ring has a generating set whose degrees are either classes of smooth rational curves, sums of at most three elements of the Hilbert basis of the nef cone, or of the form 2 ( f + f ′ ) , where f , f ′ are classes of smooth elliptic curves with f ⋅ f ′ = 2 . This result and techniques using Koszul's type exact sequences are then applied to determine a generating set for the Cox ring of all Mori dream K3 surfaces of Picard number three which is minimal in most cases. A presentation for the Cox ring is given in some special cases with few generators.

We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP -complete for every n ≥ 2 . It is known that { n V : n ≥ 1 } is an infinite family of infinite, finitely presented, simple groups. We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP -complete.

For each family of finite classical groups, and their associated simple quotients, we provide an explicit presentation on a specific generating set of size at most 8. Since there exist efficient algorithms to construct this generating set in any copy of the group, our presentations can be used to verify claimed isomorphisms between representations of the classical group. The presentations are available in Magma .

To any toric ideal I A , encoded by an integer matrix A, we associate a matroid structure called the bouquet graph of A and introduce another toric ideal called the bouquet ideal of A. We show how these objects capture the essential combinatorial and algebraic information about I A . Passing from the toric ideal to its bouquet ideal via the graph theoretic properties of the bouquet graph allows us to classify several cases. For example, on the one end of the spectrum, there are ideals that we call stable, for which bouquets capture the complexity of various generating sets as well as the minimal free resolution. On the other end of the spectrum lie toric ideals whose various bases (e.g., minimal generating sets, Grobner, Graver bases) coincide. Apart from allowing for classification-type results, bouquets provide a new way to construct families of examples of toric ideals with various interesting properties, such as robustness, genericity, and unimodularity. The new bouquet framework can be used to provide a characterization of toric ideals whose Graver basis, the universal Grobner basis, any reduced Grobner basis and any minimal generating set coincide.

Consider a finite dimensional vector space V over a finite field F q . We give a minimal generating set for the ring of invariants F q [ V ⊕ V ⁎ ] GL ( V ) , and show that this ring is a Gorenstein ring but is not a complete intersection. These results confirm a conjecture of Bonnafe and Kemper [3, Conjecture 3.1] .

We present Las Vegas algorithms for constructive recognition and constructive membership testing of the Ree groups G 2 2 ( q ) = Ree ( q ) , where q = 3 2 m + 1 for some m > 0 , in their natural representations of degree 7. The input is a generating set X ⊂ GL ( 7 , q ) . The constructive recognition algorithm is polynomial time given a discrete logarithm oracle. The constructive membership testing consists of a pre-processing step, that only needs to be executed once for a given X, and a main step. The latter is polynomial time, and the former is polynomial time given a discrete logarithm oracle. Implementations of the algorithms are available for the computer algebra system Magma .

Let F〈X〉 be the free unitary associative algebra over a field F on a free generating set X. An unitary subalgebra R of F〈X〉 is called a T-subalgebra if R is closed under all endomorphisms of F〈X〉. A T-subalgebra R⁎ in F〈X〉 is limit if every larger T-subalgebra W⫌R⁎ is finitely generated (as a T-subalgebra) but R⁎ itself is not. It follows easily from Zorn's lemma that if a T-subalgebra R is not finitely generated then it is contained in some limit T-subalgebra R⁎. In this sense limit T-subalgebras form a “border” between those T-subalgebras which are finitely generated and those which are not. In the present article we give the first example of a limit T-subalgebra in F〈X〉, where F is an infinite field of characteristic p>2 and |X|≥4. Note that, by Shchigolev's result, over a field F of characteristic 0 every T-subalgebra in F〈X〉 is finitely generated; hence, over such a field limit T-subalgebras in F〈X〉 do not exist.

We study the finite 2-groups with a fixed number of real conjugacy classes. The order of such groups can be arbitrarily large but we show that it can be bounded if the orders of the elements in a generating set are also fixed. If the number k of real classes is odd we show that the group order can be bounded in terms of k and the nilpotency class although we conjecture that a bound in terms only of k exists. We confirm this conjecture when k = 7 .

Let L n , k be the Steinberg summand of the ideal generated by the k-th power of the top Dickson class of H ⁎ ( B ( Z / 2 ) n ; Z / 2 ) . The module L n , k is the mod 2 cohomology of the Steinberg summand of a Thom spectrum over the classifying space B ( Z / 2 ) n . In this paper, using the Kameko map (Kameko, 1990 [6] ) and short exact sequences induced by the cofibration sequences constructed by Takayasu (1999) [15] , we construct a minimal generating set for L n , k as a module over the mod 2 Steenrod algebra. This generalises the result of Masateru Inoue (2002) [5] for the cases k = 0 , 1 .

Denote by C n , d the nilpotency degree of a relatively free algebra generated by d elements and satisfying the identity x n = 0 . Under assumption that the characteristic p of the base field is greater than n / 2 , it is shown that C n , d n log 2 ( 3 d + 2 ) + 1 and C n , d 4 ⋅ 2 n 2 d . In particular, it is established that the nilpotency degree C n , d has a polynomial growth in case the number of generators d is fixed and p > n 2 . For p ≠ 2 the nilpotency degree C 4 , d is described with deviation 3 for all d . As an application, a finite generating set for the algebra R GL ( n ) of GL ( n ) -invariants of d matrices is established in terms of C n , d . Several conjectures are formulated.

Let k be a field. For each pair of positive integers ( n , N ) , we resolve Q = R / ( x N , y N , z N ) as a module over the ring R = k [ x , y , z ] / ( x n + y n + z n ) . Write N in the form N = a n + r for integers a and r, with r between 0 and n − 1 . If n does not divide N and the characteristic of k is fixed, then the value of a determines whether Q has finite or infinite projective dimension. If Q has infinite projective dimension, then value of r, together with the parity of a, determines the periodic part of the infinite resolution. When Q has infinite projective dimension we give an explicit presentation for the module of first syzygies of Q. This presentation is quite complicated. We also give an explicit presentation for the module of second syzygies for Q. This presentation is remarkably uncomplicated. We use linkage to find an explicit generating set for the grade three Gorenstein ideal ( x N , y N , z N ) : ( x n + y n + z n ) in the polynomial ring k [ x , y , z ] . The question “Does Q have finite projective dimension?” is intimately connected to the question “Does k [ X , Y , Z ] / ( X a , Y a , Z a ) have the Weak Lefschetz Property?”. The second question is connected to the enumeration of plane partitions. When the field k has positive characteristic, we investigate three questions about the Frobenius powers F t ( Q ) of Q. When does there exist a pair ( n , N ) so that Q has infinite projective dimension and F ( Q ) has finite projective dimension? Is the tail of the resolution of the Frobenius power F t ( Q ) eventually a periodic function of t (up to shift)? In particular, we exhibit a situation where the tail of the resolution of F t ( Q ) , after shifting, is periodic as a function of t, with an arbitrarily large period. Can one use socle degrees to predict that the tail of the resolution of F t ( Q ) is a shift of the tail of the resolution of Q?

"The first author is supported by an EPSRC Doctoral Training Grant" We study finite groups for which every minimal generating set has the same cardinality. A group has the basis property if it and every subgroup satisfies this condition on minimal generating sets. We classify all finite groups with the basis property. Postprint

For a prime p > 3 , we compute a finite generating set for the SL 2 ( F p ) -invariants of the third symmetric power representation. The proof relies on the construction of an infinite SAGBI basis and uses the Hilbert series calculation of Hughes and Kemper.

Let G be a non-cyclic finite group that can be generated by two elements. A subset S of G is said to be a pairwise generating set for G if every distinct pair of elements in S generates G. The maximal size of a pairwise generating set for G is denoted by ω(G). The minimal number of proper subgroups of G whose union is G is denoted by σ(G). This is an upper bound for ω(G). In this paper we give lower bounds for ω(G) and upper bounds for σ(G) whenever G is a sporadic simple group.

We discuss conditions under which a soluble-by-finite linear group has a unipotent derived subgroup. We hope our positive results will be helpful for computer calculations with finitely generated soluble linear groups.

Let g ˜ be an affine Lie algebra of the type A l ( 1 ) . We find a combinatorial basis of Feigin–Stoyanovsky's type subspace W ( Λ ) given in terms of difference and initial conditions. Linear independence of the generating set is proved inductively by using coefficients of intertwining operators. A basis of the standard g ˜ -module L ( Λ ) is obtained as an “inductive limit” of the basis of W ( Λ ) .

The paper develops algorithmic methods to enumerate all normal subgroups of a finitely presented group such that the factor groups are either isomorphic to PSL ( 2 , p n ) or to PGL ( 2 , p n ) . The case of two generators is treated in detail. A range of examples starting with the free group on two generators and ending with groups having only finitely many normal subgroups of this type is discussed.

Spanning sets for vertex operator algebras satisfying difference-zero and difference-one conditions have been extensively studied in the recent years. In this paper, we extend these results. More specifically, we show that for a suitably chosen generating set, any N -graded Mobius vertex algebra is spanned by monomials satisfying a difference-N ordering condition.

The trace algebra C n d over a field of characteristic 0 is generated by all traces of products of d generic n × n matrices, n , d ⩾ 2 . Minimal sets of generators of C n d are known for n = 2 and n = 3 for any d as well as for n = 4 and n = 5 and d = 2 . The defining relations between the generators are found for n = 2 and any d and for n = 3 , d = 2 only. Starting with the generating set of C 3 d given by Abeasis and Pittaluga in 1989, we have shown that the minimal degree of the set of defining relations of C 3 d is equal to 7 for any d ⩾ 3 . We have determined all relations of minimal degree. For d = 3 we have also found the defining relations of degree 8. The proofs are based on methods of representation theory of the general linear group and easy computer calculations with standard functions of Maple.

Let $R$ be a ring generated by $l$ elements with stable range $r$. Assume that the group $EL_d(R)$ has Kazhdan constant $\epsilon_0>0$ for some $d > r $. We prove that there exist $\epsilon(\epsilon_0,l) >0$ and $k \in N$, s.t. for every $n \geq d$, $EL_n(R)$ has a generating set of order $k$ and a Kazhdan constant larger than $\epsilon$. As a consequence, we obtain for $SL_n(Z)$ where $n \geq 3$, a Kazhdan constant which is independent of $n$ w.r.t generating set of a fixed size., Comment: To appear in J. of Alg

Let $\Gamma$ be the fundamental group of a manifold modeled on three dimensional Sol geometry. We prove that $\Gamma$ has a finite index subgroup $G$ which has a rational growth series with respect to a natural generating set. We do this by enumerating $G$ by a regular language. However, in contrast to most earlier proofs of this sort our regular language is not a language of words in the generating set, but rather reflects a different geometric structure in $G$., Comment: 30 pages; author's name changed to agree with published version; to appear in Journal of Algebra

Over a field of characteristic 0, the algebra of invariants of several n×n matrices under simultaneous conjugation by GLn is generated by traces of products of generic matrices. Teranishi, 1986, found a minimal system of eleven generators of the algebra of invariants of two 3×3 matrices. Nakamoto, 2002, obtained an explicit, but very complicated, defining relation for a similar system of generators over Z. In this paper we have found another natural set of eleven generators of this algebra of invariants over a field of characteristic 0 and have given the defining relation with respect to this set. Our defining relation is much simpler than that of Nakamoto. The proof is based on easy computer calculations with standard functions of Maple but the explicit form of the relation has been found with methods of representation theory of general linear groups.

For a group G with order 2 automorphism ι, we consider irreducible representations (π, V ) of G such that ιπ ∼= π, where π is the contragredient representation of π. This isomorphism gives rise to a nondegenerate bilinear form on V which is (π, ιπ)-invariant, unique up to scalar, and consequently is either symmetric or skew-symmetric. For such a representation π, we study the question of when this form is symmetric and when it is skew-symmetric. We begin with recalling a method of Prasad [13] in the case that ι is trivial, and G is a finite group of Lie type. We apply a theorem of Klyachko to obtain results for all representations of many of the groups SL(n,Fq), improving the results of Prasad, which were for generic representations. In Section 3, we start by generalizing Lemma 1 to the case of any order 2 automorphism ι in Lemma 2. We are able to apply this to get another proof of a theorem of Gow [5] for the group GL(n,Fq) and ι the transposeinverse automorphism, and in Section 4 we are also able to apply Lemma 2 to distinguished representations and Gelfand pairs. In Section 5 we find a generating set for a finite group G given that we know certain information about the representations of G satisfying ιπ ∼= π. Finally, in Section 6, we turn to the case of a locally compact totally disconnected group. We adapt the methods of Section 2, along with approximation by compact open subgroups, to obtain an equivalent result of Theorem 4 of Gow for GL(n, F ), where F is a nonarchimedean local field.

We introduce “endomorphic presentations,” or L-presentations: group presentations whose relations are iterated under a set of substitutions on the generating set, and show that a broad class of groups acting on rooted trees admit explicitly constructible finite L-presentations, generalising results by Igor Lysionok and Said Sidki.

The diameter of a finite group $G$ with respect to a generating set $A$ is the smallest non-negative integer $n$ such that every element of $G$ can be written as a product of at most $n$ elements of $A \cup A^{-1}$. We denote this invariant by $\diam_A(G)$. It can be interpreted as the diameter of the Cayley graph induced by $A$ on $G$ and arises, for instance, in the context of efficient communication networks. In this paper we study the diameters of a finite abelian group $G$ with respect to its various generating sets $A$. We determine the maximum possible value of $\diam_A(G)$ and classify all generating sets for which this maximum value is attained. Also, we determine the maximum possible cardinality of $A$ subject to the condition that $\diam_A(G)$ is "not too small". Connections with caps, sum-free sets, and quasi-perfect codes are discussed.

Let (G,X) be a pair consisting of a group G and a generating set X of G. Let K be a commutative ring and let M be a KG-module. In this work, I try to answer the following question: “Is it possible to find a K-algebra L such that M is a LG-module and such that the elements of X act as reflections of M?” If X is a set of involutions and if a presentation of G is known, then I can answer the above question.

The irreducible Brauer characters ofSLn(q) are investigated for primeslnot dividingq. They are described in terms of a set of ordinary characters ofSLn(q) whose reductions modulolare a generating set of the additive group of generalized Brauer characters and the decomposition numbers of this set. These decomposition numbers are described by combinatorial means in terms of the decomposition numbers ofGLn(q). The latter have been investigated in great detail the last 15 years and are known completely forn ≤ 10.

LetFbe a field, and letAbe a finite-dimensionalF-algebra. Writed = dimF A, and letebe the largest degree of the minimal polynomial for anya ∈ A. Define the function f(d, e) = e 2d/(e − 1) + 1/4 + e/2 − 2 . We prove that, ifSis any finite generating set forAas anF-algebra, the words inSof length less thanf(d, e) spanAas anF-vector space. In the special case ofn-by-nmatrices, this bound becomes f(n 2 , n) = n 2n 2 /(n − 1) + 1/4 + n/2 − 2 ∈ O(n 3/2 ) . This is a substantial improvement over previous bounds, which have all beenO(n2). We also prove that, for particular setsSof matrices, the bound can be sharpened to one that is linear inn. As an application of these results, we reprove a theorem of Small, Stafford, and Warfield about semiprime affineF-algebras.

Let ( A , Σ) be an Artin system of one of the types A l , B l , D l . For X ⊆ Σ, we denote by A X the subgroup of A generated by X . Such a group is called a parabolic subgroup of ( A , Σ). Let A X be a parabolic subgroup with connected associated Coxeter graph. We exhibit a generating set of the centralizer of A X in A . Moreover, we prove that there exists X ′ ⊆ Σ such that A X ′ is conjugate to A X and such that the centralizer of A X ′ in A is generated by the centers of all the parabolic subgroups containing A X ′ .

Using the trivial observation that one can get polynomial identities on R from the ones of Mk(R) we derive from the Amitsur-Levitzki theorem a subset of the identities on n × n matrices, obtained recently by Szigeti, Tuza, and Revesz starting from directed Eulerian graphs, which generate the same T-ideal of the free algebra. After that we show that by this method we get a generating set of the T-ideal of identities on the 2 × 2 matrix ring over a field of characteristic 0. We reformulate a problem on algebras satisfying a standard identity in terms of Eulerian identities and use this equivalence in both directions. We apply a result of Braun to Eulerian identities on 3 × 3 matrices, and we give a simpler example which answers the question investigated by Braun. Finally we give an upper estimation on the minimal degree of the standard identity which is satisfied by the matrix algebra over an algebra satisfying some standard identity.

In Section 5 of our paper there are some errors related to degrees of generalized pp-extensions. We provide here a correct version of definition and results adapted to this definition.

This note gives necessary and sufficient conditions for the existence of cogenerating sets in fairly general categories admitting a certain generating set. In particular, the locally ℵ0-representale categories in the sense of Gabriel and Ulmer and all quasi-varieties of Unitary universal algebras are included. If these categories have enough injectives they also have to contain a cogenerating set. Further relations between injectivity and cogenerating sets are studied and some known results are derived as easy corollaries.

A major drawback of applying condensation in computational representation theory is the so-called generation problem, i.e. given a set of elements for the group algebra we generally do not know whether the corresponding condensed elements generate the condensed algebra. In this note we present two new methods to bridge this gap. Firstly we introduce generating sets which are in practice often small enough to be of computational use. Secondly we give a criterion which allows us to verify that a subset of the condensed algebra is in fact a generating set.

Thin Gaussian groups are a natural generalization of spherical Artin groups, namely groups of fractions of monoids in which the existence of least common multiples is kept as an hypothesis, but the relations between the generators are not supposed to necessarily be of Coxeter type. Here we completely describe the center of thin Gaussian groups by constructing a minimal generating set for the quasi-center. We deduce that every thin Gaussian group is an iterated crossed product of thin Gaussian groups with a cyclic center.

Let S be a semigroup generated by periodic elements and k be an infinite field. Suppose that the semigroup algebra kS has 1. The authors prove interesting properties of kS and S assuming that U(kS) satisfies a group identity (kS is called a GI-ring for short). In particular, S is locally finite and kS satisfies a polynomial identity. Thus Hartley's conjecture is confirmed for such semigroup algebras. If, furthermore, S is generated by a finite number of periodic elements, then they give necessary and sufficient conditions on S for kS to be a GI-ring. The authors obtain this result by proving first that if A is a semiprime GI-algebra over an infinite commutative domain D, such that A is generated as a D-algebra by U(A) and no element of D is a zero divisor in A, then A is a reduced ring. The latter fact is also used to give shorter proofs of some known results on group rings which are GI-rings.

The trace algebra C n d is generated by all traces of products of d generic n × n matrices. Minimal generating sets of C n d and their defining relations are known for n 3 and n = 3 , d = 2 . This paper states a minimal generating set and their defining relations for n = d = 3 . Furthermore the computations yield a description of C 33 as a free module over the ring generated by a homogeneous system of parameters.

Solomon's descent algebra is generated by sums of descent classes corresponding to certain hook shapes. This particularly implies that the ring of class functions of any finite symmetric group S n is generated by the irreducible characters corresponding to certain hook partitions of n . As another consequence, a second generating set of Solomon's descent algebra (and of the ring of class functions of S n ) is obtained related to the major index of permutations.

The Partition Type Conjecture, a generalization of the Middle Levels Conjecture of combinatorics, states that for all positive integers n and r , with n > r >1, and every non-exceptional partition type τ of weight r of X n , there exists a constant weight Gray code which admits an orthogonal labeling by partitions of type τ . We prove results in combinatorics and finite semigroup theory, providing the completion of the proof that the Partition Type Conjecture is true for all types having more than one class of size greater than one (and leaving open only those cases which are equivalent to the Middle Levels Conjecture). The rank of a finite semigroup S is the cardinality of a minimum generating set for S ; if S is idempotent generated, the idempotent rank of S is the cardinality of a minimum idempotent generating set for S . A semigroup of transformations of X n ={1,…, n } is said to be S n -normal if S is closed under conjugation by the permutations of X n . The results here concerning the Partition Type Conjecture are used to determine a simple formula for the rank and idempotent rank of every S n -normal semigroup.

We show that Thompson's group F does not satisfy Cannon's almost convexity condition AC(n) for any integer n in the standard finite two generator presentation. To accomplish this, we construct a family of pairs of elements at distance n from the identity and distance 2 from each other, which are not connected by a path lying inside the n-ball of length less than k for increasingly large k. Our techniques rely upon Fordham's method for calculating the length of a word in F and upon an analysis of the generators' geometric actions on the tree pair diagrams representing elements of F., Comment: 19 pages, 7 figures

It is well known that the triviality problem for finitely presented groups is unsolvable; we ask the question of whether there exists a general procedure to produce a non-trivial element from a finite presentation of a non-trivial group. If not, then this would resolve an open problem by J. Wiegold: `Is every finitely generated perfect group the normal closure of one element?' We prove a weakened version of our question: there is no general procedure to pick a non-trivial generator from a finite presentation of a non-trivial group. We also show there is neither a general procedure to decompose a finite presentation of a non-trivial free product into two non-trivial finitely presented factors, nor one to construct an embedding from one finitely presented group into another in which it embeds. We apply our results to show that a construction by Stallings on splitting groups with more than one end can never be made algorithmic, nor can the process of splitting connect sums of non-simply connected closed 4-manifolds., Comment: 16 pages, revised version, minor corrections made, additional results on algorithms to construct embeddings and enumerate subgroups. v3: minor changes to typesetting and theorem numberings, minor corrections made

Let ( W , S ) be the finite Weyl group with S as its Coxeter generating set. For w ∈ W , let R ( w )={ s i ∈ S ∣ l ( ws i ) l ( w )} and L ( w )={ s i ∈ S ∣ l ( s i w ) l ( w )}, where we denote by l ( w ) the minimal length of an expression of w as a product of simple reflections. To any Weyl group one can associate a corresponding finite-dimensional algebra called 0-Hecke algebra H where K is any field. Norton [J. Austral. Math. Soc. Ser. A 27 (1979) 337–357] pointed out that the principal indecomposable modules and the irreducible modules over the 0-Hecke algebra H parametrized by a subset J of S . We denote by U( J ) and M( J ) respectively the principal indecomposable module and the irreducible module parametrized by J . For two subset J , L of S , let C JL = the number of times M( L ) is a composition factor of U( J ) . Norton [J. Austral. Math. Soc. Ser. A 27 (1979) 337–357] shown that C JL =| Y L ∩( Y J ) −1 | where Y L ={ w ∈ W ∣ R ( w )= L } and ( Y J ) −1 ={ w ∈ W ∣ L ( w )= J }. In this article, we describe explicitly C JL for the 0-Hecke algebra of type F 4 by applying the canonical expression of every element in the Weyl group of type F 4 . Thus we determine the Cartan matrix over the 0-Hecke algebra of type F 4 .

Julius Whiston showed that the size of an independent generating set in the symmetric group S n is at most n −1. We determine all sets meeting this bound. We also give some general remarks on the maximum size of an independent generating set of a group and its relationship to coset geometries for the group. In particular, we determine all coset geometries of maximum rank for the symmetric group S n for n >6.