Robert M. Beals
Robert M. Beals has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Alice C. Niemeyer
RWTH Aachen University Germany
2 shared publications - Charles R. Leedham-Green
School of Mathematical Sciences, Queen Mary and Westfield College, London E1 4NS, United Kingdom
2 shared publications - Cheryl E. Praeger
The University of Western Australia
2 shared publications - Joseph L. Wetherell
Center for Communications Research
2 shared publications - Michael E. Zieve
Center for Communications Research, 805 Bunn Drive, Princeton, New Jersey 08540
2 shared publications - Ákos Seress
The University of Western Australia
2 shared publications
Latest Publications
- Open Access
Finding Blocks of Imprimitivity When There is a Small-Base Action on Blocks
Given a transitive permutation group G of degree n , we seek to determine whether or not G is primitive, and to find a system of blocks of imprimitivity in the case that G is imprimitive. An algorithm of Atkinson solves this problem in time O(n^2) , while a previous algorithm of ours runs in time O(n log^3|G|) , which is advantageous in the small-base case. A simpler algorithm of Schonert and Seress has the same asymptotic O(n log^3|G|) performance. In this paper we extend the small-base algorithms to work with imprimitive groups G which, while not small-base in the action on n points, possess a small-base action on a block system. Using a recent upper bound by Kelsey and Roney-Dougal on the size of a nonredundant base of a primitive group of a given degree, we obtain a time of O(n log^5 n) except in the case that G has a primitive action (either on the n points or on a block system) for which the socle is isomorphic to Alt(m)^d for some m at least 5 and d at least 1. A key component of our improvement is a new variant of sifting, which is a workhorse of permutation group algorithms.
Open AccessFinding Blocks of Imprimitivity When There is a Small-Base Action on Blocks
Given a transitive permutation group G of degree n , we seek to determine whether or not G is primitive, and to find a system of blocks of imprimitivity in the case that G is imprimitive. An algorithm of Atkinson solves this problem in time O(n^2) , while a previous algorithm of ours runs in time O(n log^3|G|) , which is advantageous in the small-base case. A simpler algorithm of Schonert and Seress has the same asymptotic O(n log^3|G|) performance. In this paper we extend the small-base algorithms to work with imprimitive groups G which, while not small-base in the action on n points, possess a small-base action on a block system. Using a recent upper bound by Kelsey and Roney-Dougal on the size of a nonredundant base of a primitive group of a given degree, we obtain a time of O(n log^5 n) except in the case that G has a primitive action (either on the n points or on a block system) for which the socle is isomorphic to Alt(m)^d for some m at least 5 and d at least 1. A key component of our improvement is a new variant of sifting, which is a workhorse of permutation group algorithms.
- 1 November 2009
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 174 (1) , 93-117
Polynomials with a common composite
- 1 November 2009
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 174 (1) , 93-117
Polynomials with a common composite
- Open Access
Polynomials with a common composite
Let f and g be nonconstant polynomials over an arbitrary field K. In this paper we study the intersection of the polynomial rings K[f] and K[g], and in particular we ask whether this intersection is larger than K. We completely resolve this question when K has characteristic zero, and in positive characteristic we present various results, examples, and algorithms.
Open AccessPolynomials with a common composite
Let f and g be nonconstant polynomials over an arbitrary field K. In this paper we study the intersection of the polynomial rings K[f] and K[g], and in particular we ask whether this intersection is larger than K. We completely resolve this question when K has characteristic zero, and in positive characteristic we present various results, examples, and algorithms.
- 1 October 2005
- Published by Elsevier in Journal of Algebra
- Vol. 292 (1) , 4-46
Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules
- 1 October 2005
- Published by Elsevier in Journal of Algebra
- Vol. 292 (1) , 4-46
Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules
- 1 September 2002
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 11 (5) , 447-464
Permutations with Restricted Cycle Structure and an Algorithmic Application
Let q be an integer with q [ges ] 2. We give a new proof of a result of Erdös and Turán determining the proportion of elements of the finite symmetric group Sn having no cycle of length a multiple of q. We then extend our methods to the more difficult case of obtaining the proportion of such elements in the finite alternating group An. In both cases, we derive an asymptotic formula with error term for the above mentioned proportion, which contains an unexpected occurrence of the Gamma-function.We apply these results to estimate the proportion of elements of order 2f in Sn, and of order 3f in An and Sn, where gcd(2, f) = 1, and gcd(3, f) = 1, respectively, and log f is polylogarithmic in n. We also give estimates for the probability that the fth power of such elements is a transposition or a 3-cycle, respectively. An algorithmic application of these results to computing in An or Sn, given as a black-box group with an order oracle, is discussed.
- 1 September 2002
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 11 (5) , 447-464
Permutations with Restricted Cycle Structure and an Algorithmic Application
Let q be an integer with q [ges ] 2. We give a new proof of a result of Erdös and Turán determining the proportion of elements of the finite symmetric group Sn having no cycle of length a multiple of q. We then extend our methods to the more difficult case of obtaining the proportion of such elements in the finite alternating group An. In both cases, we derive an asymptotic formula with error term for the above mentioned proportion, which contains an unexpected occurrence of the Gamma-function.We apply these results to estimate the proportion of elements of order 2f in Sn, and of order 3f in An and Sn, where gcd(2, f) = 1, and gcd(3, f) = 1, respectively, and log f is polylogarithmic in n. We also give estimates for the probability that the fth power of such elements is a transposition or a 3-cycle, respectively. An algorithmic application of these results to computing in An or Sn, given as a black-box group with an order oracle, is discussed.