The Tarski Theorems and Elementary Equivalence of Group Rings

The Tarski theorems, proved by Myasnikov and Kharlampovich and inde-pendently by Sela say that all nonabelian free groups satisfy the same first-order or elementary theory. Kharlampovich and Myasnikov also prove that the elementary theory of free groups is decidable. For a group ring they have proved that the first-order theory (in the language of ring theory) is not decidable and have studied equations over group rings, especially for torsion-free hyperbolic groups. In this note we examine and survey extensions of Tarksi-like results to the collection of group rings and examine relationships between the universal and elementary theories of the corresponding groups and rings and the corresponding universal theory of the formed group ring. To accomplish this we introduce different first-order languages with equality whose model classes are respectively groups, rings and group rings. We prove that if R[G] is elementarily equivalent to S[H] then simultaneously the group G is elementarily equivalent to the group H and the ring R is elementarily equivalent to the ring S with respect to the appropriate languages. Further if G is universally equivalent to a nonabelian free group F and R is universally equivalent to the integers Z then R[G] is universally equivalent to Z[F] again with respect to an ap-propriate language.

The Class of Orderable Groups Is a Quasi-Variety with Undecidable Theory

Let G be a group. G is right-orderable provided it admits a total order ≤ satisfying hg1 ≤ hg2 whenever g1 ≤ g2. G is orderable provided it admits a total order ≤ satisfying both: hg1 ≤ hg2 whenever g1 ≤ g2 and g1h ≤ g2h whenever g1 ≤ g2. A classical result shows that free groups are orderable. In this paper, we prove that left-orderable groups and orderable groups are quasivarieties of groups both with undecidable theory. For orderable groups, we find an explicit set of universal axioms.

The Tarski Problems and Their Solutions

Around 1945, Alfred Tarski proposed several questions concerning the elementary theory of non-abelian free groups. These remained open for 60 years until they were proved by O. Kharlampovich and A. Myasnikov and independently by Z. Sela. The proofs, by both sets of authors, were monumental and involved the development of several new areas of infinite group theory. In this paper we explain precisely the Tarski problems and what has been actually proved. We then discuss the history of the solution as well as the components of the proof. We then provide the basic strategy for the proof. We finish this paper with a brief discussion of elementary free groups.

Cryptographic Protocols Based on Nielsen Transformations

We introduce in this paper cryptographic protocols which use combinatorial group theory. Based on a combinatorial distribution of shares we present secret sharing schemes and cryptosystems using Nielsen transformations. Nielsen transformations are a linear technique to study free groups and general infinite groups. In addition the group of all automorphisms of a free group F, denoted by AUT (F), is generated by a regular Nielsen transformation between two basis of F, and each regular Nielsen transformation between two basis of F defines an automorphism of F.

Secure Passwords Using Combinatorial Group Theory

Password security is a crucial component of modern internet security. In this paper, we present a provably secure method for password verification using combinatorial group theory. This method relies on the group randomizer system, a subset of the MAGNUS computer algebra system and corrects most of the present problems with challenge response systems, the most common types of password verification. Theoretical security of the considered method depends on several results in asymptotic group theory. We mention further that this method has applications for many other password situations including container security.

Test Elements, Generic Elements and Almost Primitivity in Free Products

In [5, 6] the relationships between test words, generic elements, almost primitivity and tame almost primitivity were examined in free groups. In this paper we extend the concepts and connections to general free products and in particular to free products of cyclic groups.