International Journal of Algebra and Computation

Generalizing Solomon's theorem, Gordon and Rodriguez-Villegas have proven recently that, in any group, the number of solutions to a system of coefficient-free equations is divisible by the order of this group whenever the rank of the matrix composed of the exponent sums of ith unknown in jth equation is less than the number of unknowns. We generalize this result in two directions: first, we consider equations with coefficients, and second, we consider not only systems of equations but also any first-order formulae in the group language (with constants). Our theorem implies some amusing facts; for example, the number of group elements whose squares lie in a given subgroup is divisible by the order of this subgroup.

Let 𝒫_X and 𝒮_X be the partition monoid and symmetric group on an infinite set X. We show that 𝒫_X may be generated by 𝒮_X together with two (but no fewer) additional partitions, and we classify the pairs α, β ∈ 𝒫_X for which 𝒫_X is generated by 𝒮_X ∪ {α, β}. We also show that 𝒫_X may be generated by the set ℰ_X of all idempotent partitions together with two (but no fewer) additional partitions. In fact, 𝒫_X is generated by ℰ_X ∪ {α, β} if and only if it is generated by ℰ_X ∪ 𝒮_X ∪ {α, β}. We also classify the pairs α, β ∈ 𝒫_X for which 𝒫_X is generated by ℰ_X ∪ {α, β}. Among other results, we show that any countable subset of 𝒫_X is contained in a 4-generated subsemigroup of 𝒫_X, and that the length function on 𝒫_X is bounded with respect to any generating set.

Conway hemirings are Conway semirings without a multiplicative unit. We also define iteration hemirings as Conway hemirings satisfying certain identities associated with the finite groups. Iteration hemirings are iteration semirings without a multiplicative unit. We provide an analysis of the relationship between Conway hemirings and (partial) Conway semirings and describe several free constructions. In the second part of the paper we define and study hemimodules of Conway and iteration hemirings, and show their applicability in the analysis of quantitative aspects of the infinitary behavior of weighted transition systems. These include discounted and average computations of weights investigated recently.

Conway and iteration hemimodules were introduced in the first part of the paper. Here, we define and study hemimodules of Conway and iteration hemirings and study their relation to (partial) Conway and iteration semiring-semimodule pairs. Moreover, we show their applicability in the analysis of quantitative aspects of the infinitary behavior of weighted transition systems. These include discounted and average computations of weights investigated recently.

In this paper, we study the conjugacy problem in polycyclic groups. Our main result is that we construct polycyclic groups G_n whose conjugacy problem is at least as hard as the subset sum problem with n indeterminates. As such, the uniform conjugacy problem over the groups G_n is NP-complete where the parameters of the problem are taken in terms of n and the length of the elements given on input.