Author Archives: wilson.mark.c

Asymptotics for generalized Riordan arrays

Mark C. Wilson, Discrete Mathematics and Theoretical Computer Science, volume AD (2005), 323-334 (Proceedings of the 2005 International Conference on Analysis of Algorithms, Barcelona).

Download author version

Abstract: The machinery of Riordan arrays has been used recently by several authors. We show how meromorphic singularity analysis can be used to provide uniform bivariate asymptotic expansions, in the central regime, for a generalization of these arrays. We show how to do this systematically, for various descriptions of the array. Several examples from recent literature are given.

Probability generating functions for Sattolo’s algorithm

Mark C. Wilson, Journal of the Iranian Statistical Society 3 (2004), 297-308 (special issue on probabilistic analysis of algorithms).

Download author version

Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger’s analysis by finding limit laws for the same two random variables.

The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results results by determining the “grand” probability generating functions of the random variables.

The focus throughout is on using standard methods that give a unified approach, and open the door to further study.

Asymptotics of multivariate sequences, part II: multiple points of the singular variety

Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.

Download author version

Abstract: Let $latex F(mathbf{z})=sum_mathbf{r} a_mathbf{r}mathbf{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $latex mathbb{C}^d$, and let $latex mathcal{V}$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $latex mathcal{V}$.

In the first article in this series, we treated the case of smooth points of $latex mathcal{V}$. In this article we deal with multiple points of $latex mathcal{V}$.

Asymptotics of multivariate sequences, part I: smooth points of the singular variety

Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory Series A 97 (2002), 129-161.

Download author version

Abstract: Given a multivariate generating function $latex F(z_1 , ldots , z_d) = sum a_{r_1 , ldots , r_d} z_1^{r_1} cdots z_d^{r_d}$, we determine asymptotics for the coefficients. Our approach is to use Cauchy’s integral formula near singular points of $latex F$, resulting in a tractable oscillating integral. This paper treats the case where the singular point of $latex F$ is a smooth point of a surface of poles. Companion papers will treat singular points of $latex F$ where the local geometry is more complicated, and for which other methods of analysis are not known.

Associative algebras satisfying a semigroup identity

D. M. Riley and Mark C. Wilson, Glasgow Mathematical Journal 41 (1999), 453-462.

Download author version

Abstract: Denote by $latex (R,cdot)$ the multiplicative semigroup of an associative algebra $latex R$ over an infinite field, and let $latex (R,circ)$ represent $latex R$ when viewed as a semigroup via the circle operation $latex xcirc y=x+y+xy$. In this paper we characterize the existence of an identity in these semigroups in terms of the Lie structure of $latex R$. Namely, we prove that the following conditions on $latex R$ are equivalent: the semigroup $latex (R,circ)$ satisfies an identity; the semigroup $latex (R,cdot)$ satisfies a reduced identity; and, the associated Lie algebra of $latex R$ satisfies the Engel condition. When $latex R$ is finitely generated these conditions are each equivalent to $latex R$ being upper Lie nilpotent.

Degree- and time-constrained broadcast networks

Michael J. Dinneen, Geoffrey Pritchard and Mark C. Wilson, Networks 39 (2002), 1–9.

Download author version

Abstract: We consider the problem of constructing networks with as many nodes as possible, subject to upper bounds on the degree and broadcast time. The paper includes the results of an extensive empirical study of broadcasting in small regular graphs using a stochastic search algorithm to approximate the broadcast time. Significant improvements on known results are obtained for cubic broadcast networks.

X-inner automorphisms of semicommutative quantum algebras

Jeffrey Bergen and Mark C. Wilson, Journal of Algebra 220, (1999), 152-173.

Download author version

Abstract: Many important quantum algebras such as quantum symplectic space, quantum euclidean space, quantum matrices, $latex q$-analogs of the Heisenberg algebra and the quantum Weyl algebra are semi-commutative. In addition, enveloping algebras $latex U(L_+)$ of even Lie color algebras are also semi-commutative. In this paper, we generalize work of Montgomery and examine the X-inner automorphisms of such algebras.

The theorems and examples in our paper show that for algebras $latex R$ of this type, the non-identity X-inner automorphisms of $latex R$ tend to have infinite order. Thus if $latex G$ is a finite group of automorphisms of $latex R$, then the action of $latex G$ will be X-outer and this immediately gives useful information about crossed products $latex R*_t G$.

Group algebras and enveloping algebras with nonmatrix and semigroup identities

D. M. Riley and Mark C. Wilson, Communications in Algebra 27 (1999), 3545-3556.

Download author version

Abstract: Let $latex K$ be a field of characteristic $latex p>0$. Denote by $latex omega(R)$ the augmentation ideal of either a group algebra $latex R=K[G]$ or a restricted enveloping algebra $latex R=u(L)$ over $latex K$. We first characterize those $latex R$ for which $latex omega(R)$ satisfies a polynomial identity not satisfied by the algebra of all $latex 2times 2$ matrices over $latex K$. Then, we examine those $latex R$ for which $latex omega(R)$ satisfies a semigroup identity (that is, a polynomial identity which can be written as the difference of two monomials).

Construction of time-relaxed minimal broadcast networks

Michael J. Dinneen, Jose A. Ventura, Mark C. Wilson and Golbon Zakeri, Parallel Processing Letters 9 (1999), 53-68.

Download author version

Abstract: In broadcasting, or one-to-all communication, a message originally held in one node of the network must be transmitted to all the other nodes. A minimal broadcast network is a communication network that can transmit a message originated at any node to all other nodes of the network in minimum time. In this paper, we present a compound method to construct sparse, time-relaxed, minimal broadcast networks ($latex t$-mbn), in which broadcasting can be accomplished in slightly more than the minimum time. The proposed method generates a new network by connecting a subset of nodes from several copies of a $latex t_1$-mbn using the structure of another $latex t_2$-mbn. The objective is to construct a network as sparse as possible satisfying the desired broadcasting time constraint. Computational results illustrate the effectiveness of the proposed method.

Associative rings satisfying the Engel condition

D.M. Riley and Mark C. Wilson, Proceedings of the American Mathematical Society 127 (1999), 973-976.

Download author version

Abstract: Let $latex C$ be a commutative ring, and let $latex R$ be an associative $latex C$-algebra generated by elements $latex {x_1,ldots,x_d}$. We show that if $latex R$ satisfies the Engel condition of degree $latex n$ then $latex R$ is nilpotent as a Lie algebra of class bounded by a function that depends only on $latex d$ and $latex n$. We deduce that the Engel condition in an arbitrary associative ring is inherited by its group of units, and implies a semigroup identity.