Eugene M. Luks

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (34)

Group Isomorphism with Fixed Subnormal Chains

2015-01-01

Eugene M. Luks

In recent work, Rosenbaum and Wagner showed that isomorphism of explicitly listed $p$-groups of order $n$ could be tested in $n^{\frac{1}{2}\log_p n + O(p)}$ time, roughly a square root of … In recent work, Rosenbaum and Wagner showed that isomorphism of explicitly listed $p$-groups of order $n$ could be tested in $n^{\frac{1}{2}\log_p n + O(p)}$ time, roughly a square root of the classical bound. The $O(p)$ term is entirely due to an $n^{O(p)}$ cost of testing for isomorphisms that match fixed composition series in the two groups. We focus here on the fixed-composition-series subproblem and exhibit a polynomial-time algorithm that is valid for general groups. A subsequent paper will construct canonical forms within the same time bound.

Chat View PDF

Polynomial-time normalizers

2011-12-09

Eugene M. Luks , Takunari Miyazaki

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all … special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all of whose nonabelian composition factors lie in S-d; in particular, Gamma(d) includes all solvable groups. Motivated by applications to graph-isomorphism testing, there has been extensive study of the complexity of computation for permutation groups in this class. In particular, the problems of finding set stabilizers, intersections and centralizers have all been shown to be polynomial-time computable. A notable open issue for the class Gamma(d) has been the question of whether normalizers can be found in polynomial time. We resolve this question in the affirmative. We prove that, given permutation groups G, H \textless= Sym(Omega) such that G is an element of Gamma(d), the normalizer of H in G can be found in polynomial time. Among other new procedures, our method includes a key subroutine to solve the problem of finding stabilizers of subspaces in linear representations of permutation groups in Gamma(d).

Chat View PDF

Generalizing Boolean Satisfiability III: Implementation

2005-04-01

H. E. Dixon , Matthew L. Ginsberg , Daniel Hofer +2 more

This is the third of three papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying … This is the third of three papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal has been to define a representation in which this structure is apparent and can be exploited to improve computational performance. The first paper surveyed existing work that (knowingly or not) exploited problem structure to improve the performance of satisfiability engines, and the second paper showed that this structure could be understood in terms of groups of permutations acting on individual clauses in any particular Boolean theory. We conclude the series by discussing the techniques needed to implement our ideas, and by reporting on their performance on a variety of problem instances.

Chat View PDF

Generalizing Boolean Satisfiability II: Theory

2004-12-01

H. E. Dixon , Matthew L. Ginsberg , Eugene M. Luks +1 more

This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental … This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing that existing ideas in this area exploit a single, recurring structure in that multiple database axioms can be obtained by operating on a single axiom using a subgroup of the group of permutations on the literals in the problem. We argue that the group structure precisely captures the general structure at which earlier approaches hinted, and give numerous examples of its use. We go on to extend the Davis-Putnam-Logemann-Loveland inference procedure to this broader setting, and show that earlier computational improvements are either subsumed or left intact by the new method. The third paper in this series discusses ZAPs implementation and presents experimental performance results.

Chat View PDF

Generalized Derivations of Lie Algebras

2000-06-01

G. Leger , Eugene M. Luks

Sylow Subgroups in Parallel

1999-04-01

William M. Kantor , Eugene M. Luks , Peter D Mark

Chat View PDF

Fast Management of Permutation Groups I

1997-10-01

László Babai , Eugene M. Luks , Ákos Seress

We present new algorithms for permutation group manipulation. Our methods result in an improvement of nearly an order of magnitude in the worst-case analysis for the fundamental problems of finding … We present new algorithms for permutation group manipulation. Our methods result in an improvement of nearly an order of magnitude in the worst-case analysis for the fundamental problems of finding strong generating sets and testing membership. The normal structure of the group is brought into play even for such elementary issues. An essential element is the recognition of large alternating composition factors of the given group and subsequent extension of the permutation domain to display the natural action of these alternating groups. Further new features include a novel fast handling of alternating groups and the sifting of defining relations in order to link these and other analyzed factors with the rest of the group. The analysis of the algorithm depends on the classification of finite simple groups. In a sequel to this paper, using an enhancement of the present method, we shall achieve a further order of magnitude improvement.

Chat View PDF

Short Presentations for Finite Groups

1997-08-01

László Babai , Albert J. Goodman , William M. Kantor +2 more

Some Algorithms for Nilpotent Permutation Groups

1997-04-01

Eugene M. Luks , Ferenc Rákóczi , Charles R. Wright

Computing the fitting subgroup and solvable radical of small-base permutation groups in nearly linear time

1997-02-11

Eugene M. Luks , Ákos Seress

Fast Monte Carlo Algorithms for Permutation Groups

1995-04-01

László Babai , Gene Cooperman , Leonard H. Finkelstein +2 more

Permutation groups and polynomial-time computation

1993-09-01

Eugene M. Luks

Chat View PDF

Computing composition series in primitive groups

1993-09-01

László Babai , Eugene M. Luks , Ákos Seress

Computing in solvable matrix groups

1992-01-01

Eugene M. Luks

The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for … The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for membership-testing, which subsumes the discrete-log problem. However, assuming that the primes in mod G mod (other than the field characteristic) are polynomially-bounded, membership-testing and many other computational problems are in polynomial time. These problems include finding stabilizers of vectors and of subspaces and finding centralizers and intersections of subgroups. An application to solvable permutation groups puts the problem of finding normalizers of subgroups into polynomial time. Some of the results carry over directly to finite matrix groups over algebraic number fields; thus, testing solvability is in polynomial time, as is testing membership and finding Sylow subgroups.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>

Chat View PDF

Parallel algorithms for solvable permutation groups

1988-08-01

Eugene M. Luks , Pierre McKenzie

An O ( n 3 log n ) deterministic and an O ( n 3 ) Las Vegs isomorphism test for trivalent graphs

1987-07-01

Zvi Galil , Christoph M. Hoffmann , Eugene M. Luks +2 more

This paper describes an O ( n 3 log n ) deterministic algorithm and an O ( n 3 ) Las Vegas algorithm for testing whether two given trivalent graphs … This paper describes an O ( n 3 log n ) deterministic algorithm and an O ( n 3 ) Las Vegas algorithm for testing whether two given trivalent graphs on n vertices are isomorphic. In fact, the algorithms construct the set of all isomorphisms between two such graphs, presenting, in particular, generators for the group of all automorphisms of a trivalent graph. The algorithms are based upon the original polynomial-time solution to these problems by Luks but they introduce numerous speedups. These include improved permutation-group algorithms that exploit the structure of the underlying 2-groups. A remarkable property of the Las Vegas algorithm is that it computes the set of all isomorphisms between two trivalent graphs for the cost of computing only those isomorphisms that map a specified edge to a specified edge.

Chat View PDF

Computing the composition factors of a permutation group in polynomial time

1987-03-01

Eugene M. Luks

Chat View PDF

Isomorphism of graphs of bounded valence can be tested in polynomial time

1982-08-01

Eugene M. Luks

Polynomial-time algorithms for permutation groups

1980-10-01

Merrick L. Furst , John E. Hopcroft , Eugene M. Luks

A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is … A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this proceaure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms.

Chat View PDF

Derivation towers of Lie algebras

1979-11-01

Eugene M. Luks

A Characteristically Nilpotent Lie Algebra Can be a Derived Algebra

1976-04-01

Eugene M. Luks

An example is constructed of a Lie algebra whose derived algebra has only nilpotent derivations, thus answering a question of Dixmier and Lister. An example is constructed of a Lie algebra whose derived algebra has only nilpotent derivations, thus answering a question of Dixmier and Lister.

Chat View PDF

A characteristically nilpotent Lie algebra can be a derived algebra

1976-01-01

Eugene M. Luks

Chat View PDF

Correction and comment concerning “on derivations and holomorphs of nilpotent Lie algebras”

1975-12-01

G. Leger , Eugene M. Luks

The examples on p. 44 of metabelian Lie algebras L 1 and L 2 are isomorphic over certain base fields contrary to the claim in the paper. More specifically, the … The examples on p. 44 of metabelian Lie algebras L 1 and L 2 are isomorphic over certain base fields contrary to the claim in the paper. More specifically, the error lies in the incorrect statement that the rank of ad x for any x in L 1 is either zero or is at least 3. This statement does hold over Q , but if τ is a scalar satisfying τ 2 − τ − 1 = 0 then ad ( x 1 + τx 2 + τ 2 x 3 + x 4 + τ 2 x 5 has rank 2.

Chat View PDF

An urn model and the prediction of order statistics

1975-01-01

Kennetn S. Kaminsky , Eugene M. Luks , Paul Nelson

Balls are randomly selected from an urn Which contains 2 red and b blade balls. Red balls are retained and blade balls are replaced.It is shown that the probability that … Balls are randomly selected from an urn Which contains 2 red and b blade balls. Red balls are retained and blade balls are replaced.It is shown that the probability that fewer than a blade balls are selected before r red ones are removed. n>1, r<a, can be expressed in terms cf a distribution function used to construct prediction intervals tor order statistics from an exponential population. An F distribution approximation and Limiting values are obtained for these Probabilities.

Cohomology of Nilradicals of Borel Subalgebras

1974-08-01

G. Leger , Eugene M. Luks

Let 31 be the maximal nilpotent ideal in a Borel subalgebra of a complex simple Lie algebra.The cohomology groups H\% 91).H (3¡, 3Í*) and the 31-invariant symmetric bilinear forms on … Let 31 be the maximal nilpotent ideal in a Borel subalgebra of a complex simple Lie algebra.The cohomology groups H\% 91).H (3¡, 3Í*) and the 31-invariant symmetric bilinear forms on 3! are determined.The main result is the computation of H (31,31). Introduction.In his well-known paper [2] Professor Kostant has given an algebraic description of the cohomology group /i*(S, V) where ffl is the maximal nilpotent ideal of a parabolic subalgebra of a complex simple Lie algebra g and V is an Sl-module obtained by restriction to ÏÏ1 of an irreducible g-module.In the course of lectures on this and related matters Professor Kostant pointed out the problem of computing the cohomology group //*(ï!, ffl) and stated (indeed it is written in the introduction to [2]) that he knew //KSt, 3c) where 3c is the maximal nilpotent ideal of a Borel subalgebra of g.As a result of other work on derivations of Lie algebras we had also obtained H 01, 31) and we describe this set easily as a consequence of our Theorem 2.4 and Kostant's [2, Theorem 5.14].The principal goal of this paper is the computation of f/2(3l, 31).In the course of this we determine f/1(3l, 31*) and the 31-invariant symmetric bilinear forms on 31.To facilitate the use of our results we give a description of these groups in such a way that they may be read from the root system.In [4], F.Williams also determines Hl(3l, 31) and f/KSt, 31*) by different methods which involve extending Kostant's Laplacian.Throughout this paper g will denote a complex simple Lie algebra with fixed Cartan subalgebra % We shall assume a fixed linear ordering of the roots with aj» • • • » a¡ denoting the simple roots where / is the rank of g, i.e. / = dim b,.We shall denote the set of roots by A and the positive roots by A+.If a = 2. ,na.* Zsl z z is in A we put |a| = 2j .n¿;|<*| is called the level of a. 1= I 3a; 3l'= I 9., Thus g = 31 © §

Chat View PDF

Normalizers of Linear Lie Algebras

1974-01-01

Eugene M. Luks

Let V be a finite dimensional vector space over an arbitrary field. For a Lie subalgebra L of gl(V) the “normalizer tower” of L is the sequence {Ni (L)}i=0,1,…, where … Let V be a finite dimensional vector space over an arbitrary field. For a Lie subalgebra L of gl(V) the “normalizer tower” of L is the sequence {Ni (L)}i=0,1,…, where N 0(L)=L N i+1(L)= the normalizer of Ni (L) in gl(V). The minimal n such that N n+1(L)=N n (L) is called the height of the tower. Bounds for the tower height are discussed for certain classes of algebras. In particular, it is shown that if L is one-dimensional then its tower has height at most 3. In characteristic 0, the relatively few one-dimensional linear Lie algebras whose towers achieve this upper bound are determined.

Cohomology of nilradicals of Borel subalgebras

1974-01-01

G. Leger , Eugene M. Luks

Chat View PDF

Cohomology and weight systems for nilpotent Lie algebras

1974-01-01

G. Leger , Eugene M. Luks

1. This paper announces results concerning the cohomology groups H*(N, N) where A* is in a certain class of finite-dimensional nilpotent Lie algebras over a field k and T is … 1. This paper announces results concerning the cohomology groups H*(N, N) where A* is in a certain class of finite-dimensional nilpotent Lie algebras over a field k and T is an abelian Lie algebra faithfully represented as a maximal diagonalizable algebra of derivations of N; we shall refer to such an iV as a T-algebra. The additional hypotheses to be placed on the pair N, T are inspired by the case when J is a Cartan subalgebra and T+N=B is a Borel subalgebra of a complex semisimple Lie algebra. In that case Kostant has shown [2] that H%N, N)=0 for i^.2 and the authors applied this result in [3] to conclude that H*(B, B) = 0. (A similar argument shows H*(P9 P ) = 0 for P parabolic.) Here we are concerned with the relations between the vanishing ofH%N, N), especially for i=2 , and the structure of the algebras N. Let W denote the set of weights of T in N. If dirn(r)=dim(7\T/A)=m then the subset of W arising from the induced representation of T on N/N has precisely m elements, say {a1? • • • , am}. Every a e Wthen has a unique representation a = 2 ^a* with each c? a nonnegative integer and ct 0. For such an a we call the sum (in Z) 2 i the height of a and denote it by |a|. For a in W, denote by Aa the weight space for a in N. DEFINITION. A T-algebra is called positive if (i) dim(70=dim(A7iV), (ii) N is graded by the heights of the weights, i.e., if N(j) = Q)\al=j Na then [N(j)9N(k)]cN(j+k). REMARK. Condition (ii) is superfluous in characteristic 0. However, in characteristic p>0 it has such consequences as N=0 for r > ( / > l ) d i m ( r ) .

Chat View PDF

Cohomology Theorems for Borel-Like Solvable Lie Algebras in Arbitrary Characteristic

1972-12-01

G. Leger , Eugene M. Luks

This paper develops some techniques for the study of derivation algebras and cohomology groups of Lie algebras. We are especially concerned with solvable algebras over arbitrary fields with structural properties … This paper develops some techniques for the study of derivation algebras and cohomology groups of Lie algebras. We are especially concerned with solvable algebras over arbitrary fields with structural properties like those of the Borel subalgebras of complex semi-simple Lie algebras. In particular, these algebras are semi-direct sums of nilpotent ideals and abelian subalgebras which act on the ideals in a semi-simple fashion. We make strong use, in our discussion, of a cohomology theorem of Hochschild-Serre. This result is stated herein (§ 2) in a modified form which allows us to omit the original hypothesis that the base field have characteristic 0.

Chat View PDF

On a duality for metabelian Lie algebras

1972-05-01

G. Leger , Eugene M. Luks

On Nilpotent Groups of Algebra Automorphisms

1972-03-01

G. Leger , Eugene M. Luks

The main purpose of this paper is to derive conclusions about the structure of a nilpotent group of algebra automorphisms and, in the case of a Lie algebra, about the … The main purpose of this paper is to derive conclusions about the structure of a nilpotent group of algebra automorphisms and, in the case of a Lie algebra, about the influence of this nilpotence on the structure of the algebra. A motivation for this study is a well known theorem due to Kolchin: A unipotent linear group can be triangularized and is thus nilpotent. The converse is manifestly false, but we have (as an immediate consequence of Theorem 2.7):

Chat View PDF

On Derivations and Holomorphs of Nilpotent Lie Algebras

1971-12-01

G. Leger , Eugene M. Luks

A linear Lie algebra is called toroidal if it is abelian and consists of semi-simple transformations. The maximum, t(L) , of the dimensions of the toroidal subalgebras of the derivation … A linear Lie algebra is called toroidal if it is abelian and consists of semi-simple transformations. The maximum, t(L) , of the dimensions of the toroidal subalgebras of the derivation algebra, Δ( L ), is an invariant of L . This paper is mainly concerned with the relation between the magnitude of t(L) for nilpotent L and the structures of L and Δ(L) .

Chat View PDF

Lie algebras with only inner derivations need not be complete

1970-06-01

Eugene M. Luks

On the Mean Duration of a Ball and Cell Game; A First Passage Problem

1966-04-01

Harry Dym , Eugene M. Luks

Chat View PDF

Common Coauthors

Coauthor	Papers Together
G. Leger	9
Ákos Seress	4
László Babai	4
William M. Kantor	2
H. E. Dixon	2
Matthew L. Ginsberg	2
Andrew J. Parkes	2
John E. Hopcroft	1
Zvi Galil	1
Merrick L. Furst	1
Gene Cooperman	1
Péter P. Pálfy	1
Albert J. Goodman	1
Takunari Miyazaki	1
Ferenc Rákóczi	1
Christoph M. Hoffmann	1
Charles R. Wright	1
Paul Nelson	1
Leonard H. Finkelstein	1
C. P. Schnorr	1
Peter D Mark	1
Andreas Weber⋆	1
Harry Dym	1
Kennetn S. Kaminsky	1
Pierre McKenzie	1
Daniel Hofer	1

Commonly Cited References

Polynomial-time algorithms for permutation groups

1980-10-01

Merrick L. Furst , John E. Hopcroft , Eugene M. Luks

Chat View PDF

Isomorphism of graphs of bounded valence can be tested in polynomial time

1982-08-01

Eugene M. Luks

Sylow's theorem in polynomial time

1985-06-01

William M. Kantor

Computational methods in the study of permutation groups††This research was supported in part by the National Science Foundation.

1970-01-01

Charles C. Sims

Cohomology Theorems for Borel-Like Solvable Lie Algebras in Arbitrary Characteristic

1972-12-01

G. Leger , Eugene M. Luks

Chat View PDF

SIMPLE GROUPS OF LIE TYPE

1975-03-01

I. G. Macdonald

By W. Carter Roger: pp. viii, 331. £7.50. John Wiley & Sons, December 1972.) By W. Carter Roger: pp. viii, 331. £7.50. John Wiley & Sons, December 1972.)

Permutation groups and polynomial-time computation

1993-09-01

Eugene M. Luks

Chat View PDF

Computing the composition factors of a permutation group in polynomial time

1987-03-01

Eugene M. Luks

Chat View PDF

A polynomial bound for the orders of primitive solvable groups

1982-07-01

Péter P. Pálfy

Polynomial-time versions of Sylow's theorem

1988-03-01

William M. Kantor , D. E. Taylor

Derivations of nilpotent Lie algebras

1957-02-01

J. Dixmier , William G. Lister

J. DIXMIER AND W. G. LISTER In a recent note Jacobson proved [l] that, over a field of characteristic 0, a Lie algebra with a nonsingular derivation is nilpotent. He … J. DIXMIER AND W. G. LISTER In a recent note Jacobson proved [l] that, over a field of characteristic 0, a Lie algebra with a nonsingular derivation is nilpotent. He also noted that the validity of the converse was an open question. The purpose of this note is to supply a strongly negative answer to that question and to point out some of the immediate problems which this answer raises. Suppose then that 4> is a field of characteristic 0 and that 2 is the 8 dimensional algebra over described in terms of a basis ei, e2, • ■ • , t?s by the following multiplication table: (1) [eu e2] = eB, (6) [e2, e4] = e6, (2) [eu e8] = e6, (7) [e2, e6] = — e7, (3) [eu e4] = e7, (8) [e3, e4] = — e6, (4) [eu et] = e8, (9) [e3, e6] = e7, (5) [eit e3] = e8, (10) [e4, e6] = — es. In addition [e 4. It is convenient to use a symmetry in the table above. Denote by A the linear transformation induced in 2 by the mapping

Chat View PDF

Finite Permutation Groups and Finite Simple Groups

1981-01-01

Peter J‎. Cameron

Some remarks on the computation of complements and normalizers in soluble groups

1990-01-01

Frank Celler , J. Neubüser , Charles R. Wright

Finite Permutation Groups

1964-01-01

Chat View PDF

Polynomial-time algorithms for finding elements of prime order and sylow subgroups

1985-12-01

William M. Kantor

Chat View PDF

Computing in solvable matrix groups

1992-01-01

Eugene M. Luks

Chat View PDF

Graphs and finite permutation groups

1967-01-01

Charles C. Sims

On the orders of primitive groups with restricted nonabelian composition factors

1982-11-01

László Babai , Peter J‎. Cameron , Péter P. Pálfy

Finite Permutation Groups.

1966-08-01

Franklin Haimo , Helmut Wielandt

Isomorphism of graphs which are pairwise k-separable

1983-01-01

Gary L. Miller

Parallel algorithms for solvable permutation groups

1988-08-01

Eugene M. Luks , Pierre McKenzie

Efficient representation of perm groups

1991-03-01

Donald E. Knuth

Characteristically nilpotent Lie algebras

1959-12-01

G. Leger , Shigeaki Tôgô

Groupes et algèbres de Lie

1971-01-01

Nicolás Bourbaki

Les Elements de mathematique de Nicolas Bourbaki ont pour objet une presentation rigoureuse, systematique et sans prerequis des mathematiques depuis leurs fondements. Ce premier volume du Livre sur les Groupes … Les Elements de mathematique de Nicolas Bourbaki ont pour objet une presentation rigoureuse, systematique et sans prerequis des mathematiques depuis leurs fondements. Ce premier volume du Livre sur les Groupes et algebre de Lie, neuvieme Livre du traite, est consacre aux concepts fondamentaux pour les algebres de Lie. Il comprend les paragraphes: - 1 Definition des algebres de Lie; 2 Algebre enveloppante d une algebre de Lie; 3 Representations; 4 Algebres de Lie nilpotentes; 5 Algebres de Lie resolubles; 6 Algebres de Lie semi-simples; 7 Le theoreme d Ado. Ce volume est une reimpression de l edition de 1971.

Chapter I, from Solvability of groups of odd order, Pacific J. Math, vol. 13, no. 3 (1963

1963-09-01

Walter Feit , John Thompson

Chat View PDF

Some group-theoretic algorithms

1978-01-01

Charles C. Sims

Computing intersections and normalizersin soluble groups

1990-05-01

S. P. Glasby , Michael C. Slattery

Some remarks on the computation of complements and normalizers in soluble groups

1990-01-01

Frank Celler , J. Neub�ser , Charles R. Wright

Finding Sylow normalizers in polynomial time

1990-12-01

William M. Kantor

Groupes et algèbres de Lie

2007-01-01

A Theory of Subinvariant Lie Algebras

1951-04-01

Eugene Schenkman

Generalizing Boolean Satisfiability I: Background and Survey of Existing Work

2004-02-01

H. E. Dixon , Matthew L. Ginsberg , Andrew J. Parkes

This is the first of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea … This is the first of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper is a survey of the work underlying ZAP, and discusses previous attempts to improve the performance of the Davis-Putnam-Logemann-Loveland algorithm by exploiting the structure of the problem being solved. We examine existing ideas including extensions of the Boolean language to allow cardinality constraints, pseudo-Boolean representations, symmetry, and a limited form of quantification. While this paper is intended as a survey, our research results are contained in the two subsequent articles, with the theoretical structure of ZAP described in the second paper in this series, and ZAP's implementation described in the third.

Chat View PDF

Lie Algebra Cohomology and the Generalized Borel-Weil Theorem

1961-09-01

Bertram Kostant

Graph isomorphism, general remarks

1979-04-01

Gary L. Miller

On the Order of Uniprimitive Permutation Groups

1981-05-01

László Babai

One of the central problems of 19th century group theory was the estimation of the order of a primitive permutation group G of degree n, where G X An. We … One of the central problems of 19th century group theory was the estimation of the order of a primitive permutation group G of degree n, where G X An. We prove I G I < exp (4V'/ n log2 n) for the case when G is not doubly transitive. This result is best possible apart from an O(log n) factor in the exponent. The best result previously known was I G I < el (H. Wielandt). A similar estimate for the doubly transitive case follows in a subsequent paper. For rank 3 groups with subdegree p < n/2 we obtain I GI < exp (4(n/p) log2 n). In the proof we develop some new combinatorial properties of coherent configurations. The results also have relevance to theoretical estimates on the computational complexity of graph isomorphism testing.

Fast Management of Permutation Groups I

1997-10-01

László Babai , Eugene M. Luks , Ákos Seress

Chat View PDF

Derivations of Lie algebras III

1963-12-01

G. Leger

On the length of subgroup chains in the symmetric group

1986-01-01

László Babai

We prove that for n≥2, the length of every subgroup chain in Sn is at most 2n-3. The proof rests on an upper bound for the order of primitive permutation … We prove that for n≥2, the length of every subgroup chain in Sn is at most 2n-3. The proof rests on an upper bound for the order of primitive permutation groups, due to Praeger and Saxl. The result has applications to worst case complexity estimates for permutation group algorithms.

Permutation group algorithms based on partitions, I: Theory and algorithms

1991-10-01

Jeffrey S. Leon

Generators and Relations for Discrete Groups

1972-01-01

H. S. M. Coxeter , W. O. J. Moser

The sylow 2-subgroups of the finite classical groups

1964-07-01

Roger Carter , Paul Fong

Sylow 𝑝-subgroups of the classical groups over finite fields with characteristic prime to 𝑝

1955-08-01

A. J. Weir

If S,, is a Sylow p-subgroup of the symmetric group of degree pn, then any group of order pn may be imbedded in Sn. We may express Sn as the … If S,, is a Sylow p-subgroup of the symmetric group of degree pn, then any group of order pn may be imbedded in Sn. We may express Sn as the complete product' C o C o ... o C of n cyclic groups of order p and the purpose of this paper is to show that any Sylow psubgroup of a classical group (see ?1) over the finite field GF(q) with q elements, where (q, p) = 1, is expressible as a direct product of basic subgroups En-C O C O ... o C (n factors), where Z is cyclic of order pr. (We assume always that p ;2.) Since C may be imbedded in S., we see that n is imbedded in Sn+r-l in a particularly simple way. The above r is defined by the equation q -1 =pt *where qI is the first power of q which is congruent to 1 mod p and * denotes some unspecified number prime to p. The case r = 1 is therefore of frequent occurrence, and then clearly SnSn Professor Philip Hall was my research supervisor in Cambridge (England) during the years 1949-1952 and it is a pleasure to acknowledge here my indebtedness to him for his generous encouragement.

Chat View PDF

Computing the structure of finite algebras

1990-03-01

Lajos Rónyai

Solvable and Nilpotent Subgroups of GL(n,qm)

1982-10-01

Thomas R. Wolf

Let V ≠ 0 be a vector space of dimension n over a finite field of order q m for a prime q . Of course, GL ( n, q … Let V ≠ 0 be a vector space of dimension n over a finite field of order q m for a prime q . Of course, GL ( n, q m ) denotes the group of -linear transformations of V . With few exceptions, GL ( n, q m ) is non-solvable. How large can a solvable subgroup of GL ( n, q m ) be? The order of a Sylow- q -subgroup Q of GL ( n, q m ) is easily computed. But Q cannot act irreducibly nor completely reducibly on V . Suppose that G is a solvable, completely reducible subgroup of GL ( n, q m ). Huppert ([ 9 ], Satz 13, Satz 14) bounds the order of a Sylow- q -subgroup of G , and Dixon ([ 5 ], Corollary 1) improves Huppert's bound. Here, we show that | G | ≦ q 3 nm = | V | 3 . In fact, we show that where

Chat View PDF

ENUMERATING FINITE GROUPS

1987-01-01

Annabelle McIver , Peter Neumann

Journal Article ENUMERATING FINITE GROUPS Get access ANNABELLE MCIVER, ANNABELLE MCIVER The Queen's CollegeOxford OX14AW Search for other works by this author on: Oxford Academic Google Scholar PETER M. NEUMANN … Journal Article ENUMERATING FINITE GROUPS Get access ANNABELLE MCIVER, ANNABELLE MCIVER The Queen's CollegeOxford OX14AW Search for other works by this author on: Oxford Academic Google Scholar PETER M. NEUMANN PETER M. NEUMANN The Queen's CollegeOxford OX14AW Search for other works by this author on: Oxford Academic Google Scholar The Quarterly Journal of Mathematics, Volume 38, Issue 4, December 1987, Pages 473–488, https://doi.org/10.1093/qmath/38.4.473 Published: 01 December 1987 Article history Received: 23 September 1986 Published: 01 December 1987

A nilpotent Lie algebra with nilpotent automorphism group

1970-01-01

Joan L. Dyer

Recent work of Stein, Knapp, Koranyi and others has been concerned with nilpotent Lie groups which admit expanding automorphisms, that is, semisimple automorphisms whose eigenvalues are all greater than one … Recent work of Stein, Knapp, Koranyi and others has been concerned with nilpotent Lie groups which admit expanding automorphisms, that is, semisimple automorphisms whose eigenvalues are all greater than one in absolute value (cf. [l], [3], [S]). It was an open question whether all nilpotent Lie groups admit expansions.We first present a result due to Louis Auslander (oral communication) which establishes the existence of a class of Lie groups which do admit expanding automorphisms ( §1).We then present an example of a nine dimensional Lie group which does not have an expanding automorphism ( §2).In our work it is more convenient to use Lie algebra language than Lie group language.As is well known, for connected simply connected nilpotent Lie groups the choice of group or algebra language is a matter of taste.I wish to take this opportunity to thank Louis Auslander for suggesting this problem to me.

Chat View PDF

Normalizers of Linear Lie Algebras

1974-01-01

Eugene M. Luks

Cohomology and deformations in graded Lie algebras

1966-01-01

Albert Nijenhuis , R. W. Richardson

Introduction.In an address to the Society in 1962, one of the authors gave an outline of the similarities between the deformations of complex-analytic structures on compact manifolds on one hand, … Introduction.In an address to the Society in 1962, one of the authors gave an outline of the similarities between the deformations of complex-analytic structures on compact manifolds on one hand, and the deformations of associative algebras on the other.The first theory had been stimulated in 1957 by a paper [7] by Nijenhuis-Frölicher and extensively developed in a series of papers by Kodaira-Spencer, Kodaira-Spencer-Nirenberg and Kuranishi; the second had just been initiated by Gerstenhaber [9].While fine details were not available at that time, it seemed that graded Lie algebras were the common core of both theories.In particular, in both cases, the set of deformed structures is represented by the set of solutions of a certain deformation equation in graded Lie algebras.This observation was further elaborated in a Research Announcement [16] of the authors, in which the concept of algebraic graded Lie algebra was carefully defined, and in which applications to deformations of Lie algebras and to representations, extensions and homomorphisms of algebras were indicated.The present paper gives a detailed discussion of the deformation equation in graded Lie algebras whose summands are finite-dimensional.The paper starts with a general discussion of graded Lie algebras including the case of characteristic 2, and leads to a general deformation theorem, which is the precise analogue of Kuranishi's local completeness theorem for complex analytic structures [13].(A more recent proof of this theorem [14] uses methods closely related to those indicated in [16].)The basic deformation theorems presented are 16.2, 18.1, 20.3, 22.1 and 23.4.The following is an outline in which a few of the more technical details have been deleted.We consider a graded Lie algebra (cf.3.1) £ = ©£LQ E n in which each E n is finite-dimensional, and with

Chat View PDF

Some Algorithms for Nilpotent Permutation Groups

1997-04-01

Eugene M. Luks , Ferenc Rákóczi , Charles R. Wright

On the maximal subgroups of the finite classical groups

1984-10-01

Michael Aschbacher