International Journal of Algebra and Computation

Value semigroups of non-irreducible singular algebraic curves and their fractional ideals are submonoids of ${\mathbb{Z}}^n$ that are closed under infimums, have a conductor and fulfill a special compatibility property on their elements. Monoids of ${\mathbb{N}}^n$ fulfilling these three conditions are known in the literature as good semigroups and there are examples of good semigroups that are not realizable as the value semigroup of an algebraic curve. In this paper, we consider good semigroups independently from their algebraic counterpart, in a purely combinatorial setting. We define the concept of good system of generators, and we show that minimal good systems of generators are unique. Moreover, we give a constructive way to compute the canonical ideal and the Arf closure of a good subsemigroup when $n=2$.

The question of describing the automorphisms of $End(A)$ for a free algebra $A$ in a certain variety was considered by different authors since 2002. In this paper, we consider this question for the class of all relatively free groups having only cyclic centralizers of non-trivial elements. We prove that each automorphism of the endomorphism semigroup $End(F)$ of groups $F$ from this class is uniquely determined by its action on the subgroup of inner automorphisms $Inn(F)$. The obtained general result includes the following cases: absolutely free groups, free Burnside groups of odd period $n\ge 665$, free groups of infinitely based varieties of Adian (the cardinality of the set of such varieties is continuum), and so on.

We use results from the theory of algebras with polynomial identities (PI-algebras) to study the witness complexity of matrix identities. A matrix identity of $d\times d$ matrices over a field $𝔽$is a non-commutative polynomial (f(x₁, …, x_n)) over $𝔽$, such that $f$ vanishes on every $d\times d$ matrix assignment to its variables. For every field $𝔽$of characteristic 0, every $d>2$ and every finite basis of $d\times d$ matrix identities over $𝔽$, we show there exists a family of matrix identities ${(f_n)}_{n\in \mathbb{N}}$, such that each $f_n$ has $2n$ variables and requires at least $\mathrm{\Omega }(n^{2d})$ many generators to generate, where the generators are substitution instances of elements from the basis. The lower bound argument uses fundamental results from PI-algebras together with a generalization of the arguments in [P. Hrubeš, How much commutativity is needed to prove polynomial identities? Electronic colloquium on computational complexity, ECCC, Report No.: TR11-088, June 2011].

We apply this result in algebraic proof complexity, focusing on proof systems for polynomial identities (PI proofs) which operate with algebraic circuits and whose axioms are the polynomial-ring axioms [P. Hrubeš and I. Tzameret, The proof complexity of polynomial identities, in Proc. 24th Annual IEEE Conf. Computational Complexity, CCC 2009, 15–18 July 2009, Paris, France (2009), pp. 41–51; Short proofs for the determinant identities, SIAM J. Comput. 44(2) (2015) 340–383], and their subsystems. We identify a decrease in strength hierarchy of subsystems of PI proofs, in which the $d$th level is a sound and complete proof system for proving $d\times d$ matrix identities (over a given field). For each level $d>2$ in the hierarchy, we establish an $\mathrm{\Omega }(n^{2d})$ lower bound on the number of proof-steps needed to prove certain identities.

Finally, we present several concrete open problems about non-commutative algebraic circuits and speed-ups in proof complexity, whose solution would establish stronger size lower bounds on PI proofs of matrix identities, and beyond.

We will determine the ring structure of the Hochschild cohomology $H{H}^{\ast }(\mathbb{Z}S{D}_{8\ell })$ of the integral group ring of the semidihedral group $S{D}_{8\ell }$ of order $8\ell$ for arbitrary integer $\ell \ge 2$ by giving the precise description of the integral cohomology ring $H^{\ast }(S{D}_{8\ell },\mathbb{Z})$ and by using a method similar to [T. Hayami, Hochschild cohomology ring of the integral group ring of the semidihedral $2$-group, Algebra Colloq. 18 (2011) 241–258].

Let $F$ be a finite field with the characteristic $p>2$ and let $G$ be the unitary Grassmann algebra generated by an infinite dimensional vector space $V$ over $F$. In this paper, we determine a basis for ${\mathbb{Z}}_2$-graded polynomial identities for any ${\mathbb{Z}}_2$-grading such that its underlying vector space is homogeneous.

L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives and bases in the free group on two generators, the Bridson–Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk’s group can be generated by L systems. To complement the result on primitives in rank 2 free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L languages of intermediate growth.

Irreducible Artin groups of finite type can be parametrized via their associated Coxeter diagrams into six sporadic examples and four infinite families, each of which is further parametrized by the natural numbers. Within each of these four infinite families, we investigate the relationship between elementary equivalence and isomorphism. For three out of the four families, we show that two groups in the same family are equivalent if and only if they are isomorphic; a positive, but weaker, result is also attained for the fourth family. In particular, we show that two braid groups are elementarily equivalent if and only if they are isomorphic. The ${(\forall \exists )}^1$ fragment suffices to distinguish the elementary theories of the groups in question.

As a consequence of our work, we prove that there are infinitely many elementary equivalence classes of irreducible Artin groups of finite type. We also show that mapping class groups of closed surfaces — a geometric analogue of braid groups — are elementarily equivalent if and only if they are isomorphic.

In this paper, we give a description of the generators of the prime level congruence subgroups of braid groups. Also, we give a new presentation of the symplectic group over a finite field, and we calculate the symmetric quotients of the prime level congruence subgroups of braid groups. Finally, we find a finite generating set for the level-3 congruence subgroup of the braid group on three strands.