International Journal of Algebra and Computation

Let K be a field of any characteristic. We prove that a free metabelian Lie algebra M₃ of rank 3 over K admits wild automorphisms. Moreover, the subgroup IAutM₃ of all automorphisms identical modulo the derived subalgebra cannot be generated by any finite set of IA-automorphisms together with the sets of all inner and all tame IA-automorphisms. In the case if K is finite the group AutM₃ cannot be generated by any finite set of automorphisms together with the sets of all tame, all inner automorphisms and all one-row automorphisms. We present an infinite set of wild IA-automorphisms of M₃ which generates a free subgroup F_∞ modulo normal subgroup generated by all tame, all inner and all one-row automorphisms of M₃.

We present a practical algorithm to construct the subgroup of the general linear group that preserves a system of bilinear or sesquilinear forms on a vector space defined over a finite field. Components include efficient algorithms to construct the Jacobson radical and the group of units of a matrix algebra.

Let A be a cyclic group of order pⁿ, where p is a prime, and B be a finite abelian group or a finite p-group which is determined by its endomorphism semigroup in the class of all groups. It is proved that under these assumptions the wreath product A Wr B is determined by its endomorphism semigroup in the class of all groups. It is deduced from this result that if A, B, A₀,…, A_n are finite abelian groups and A₀,…, A_n are p-groups, p prime, then the wreath products A Wr B and A_nWr (…(Wr (A₁Wr A₀))…) are determined by their endomorphism semigroups in the class of all groups.

In this paper, we study the irreducible decompositions of the degeneracy loci of matrices which are defined by rank conditions on upper left submatrices. By introducing the concepts of standard and essential rank functions, we give an explicit classification of these degeneracy loci. Based on standard rank functions, we design an algorithm to write a degeneracy locus as a union of its irreducible components. This gives an answer to a problem raised by Sturmfels.

Let L be a free restricted Lie algebra and R a restricted ideal of L. Denote by u(L) the restricted enveloping algebra of L and by ω(L) the associative ideal of u(L) generated by L. The purpose of this paper is to identify the subalgebra R ∩ ωⁿ(L)ω(R) in terms of R only. This problem is the analogue of the Fox problem for free groups.

We consider the subgroup lpG_k,1 of length preserving elements of the Thompson–Higman group G_k,1 and we show that all elements of G_k,1 have a unique lpG_k,1 · F_k,1 factorization. This applies to the Thompson–Higman group T_k,1 as well. We show that lpG_k,1 is a "diagonal" direct limit of finite symmetric groups, and that lpT_k,1 is a k^∞ Prüfer group. We find an infinite generating set of lpG_k,1 which is related to reversible boolean circuits.

We further investigate connections between the Thompson–Higman groups, circuits, and complexity. We show that elements of F_k,1 cannot be one-way functions. We show that describing an element of G_k,1 by a generalized bijective circuit is equivalent to describing the element by a word over a certain infinite generating set of G_k,1; word length over these generators is equivalent to generalized bijective circuit size.

We give some coNP-completeness results for G_k,1 (e.g., the word problem when elements are given by circuits), and -completeness results (e.g., finding the lpG_k,1 · F_k,1 factorization of an element of G_k,1 given by a circuit).

We prove that for every distributive 〈∨,0〉-semilattice S, there are a meet-semilattice P with zero and a map μ: P × P → S such that μ(x,z) ≤ μ(x,y) ∨ μ(y,z) and x ≤ y implies that μ(x,y) = 0, for all x, y, z ∈ P, together with the following conditions:.

(P1) μ(v,u) = 0 implies that u = v, for all u ≤ v in P.

(P2) For all u ≤ v in P and all a, b ∈ S, if μ(v,u) ≤ a ∨ b, then there are a positive integer n and a decomposition u = x₀ ≤ x₁ ≤ ⋯ ≤ x_n = v such that either μ(x_{i + 1}, x_i) ≤ a or μ(x_i+1, x_i) ≤ b, for each i < n.

(P3) The subset {μ(x,0) | x ∈ P} generates the semilattice S.

Furthermore, every finite, bounded subset of P has a join, and P is bounded in case S is bounded. Furthermore, the construction is functorial on lattice-indexed diagrams of finite distributive 〈∨,0,1〉-semilattices.

The dual symmetric inverse monoid is the inverse monoid of all isomorphisms between quotients of an n-set. We give a monoid presentation of and, along the way, establish criteria for a monoid to be inverse when it is generated by completely regular elements.

We give an efficient algorithm to randomly generate finitely generated subgroups of a given size, in a finite rank free group. Here, the size of a subgroup is the number of vertices of its representation by a reduced graph such as can be obtained by the method of Stallings foldings. Our algorithm randomly generates a subgroup of a given size n, according to the uniform distribution over size n subgroups. In the process, we give estimates of the number of size n subgroups, of the average rank of size n subgroups, and of the proportion of such subgroups that have finite index. Our algorithm has average case complexity in the RAM model and in the bitcost model.