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 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.展开更多
Let <em>G</em> be a group. <em>G</em> is right-orderable provided it admits a total order ≤ satisfying <em>hg</em><sub>1</sub> <span style="white-space:normal;&...Let <em>G</em> be a group. <em>G</em> is right-orderable provided it admits a total order ≤ satisfying <em>hg</em><sub>1</sub> <span style="white-space:normal;">≤ <span style="white-space:normal;"><em>hg</em><sub>2 </sub></span></span>whenever <em style="white-space:normal;">g</em><sub style="white-space:normal;">1</sub><span style="white-space:normal;"> </span><span style="white-space:normal;">≤ <i>g</i><sub>2</sub></span>. <em>G</em> is orderable provided it admits a total order ≤ satisfying both: <em style="white-space:normal;">hg</em><sub style="white-space:normal;">1</sub><span style="white-space:normal;"> </span><span style="white-space:normal;">≤ <em>hg</em><sub>2</sub></span> whenever <span style="white-space:nowrap;"><em>g</em><sub>1</sub> ≤ <em>g</em><sub>2</sub></span> and <em style="white-space:normal;">g</em><sub style="white-space:normal;">1</sub><em style="white-space:normal;">h</em><span style="white-space:normal;"> ≤ </span><em style="white-space:normal;">g</em><sub style="white-space:normal;">2</sub><em style="white-space:normal;">h</em> whenever <em>g</em><sub>1</sub> ≤ <em>g</em><sub>2</sub>. 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.展开更多
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 indep...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.展开更多
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 transformation...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.展开更多
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 rand...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.展开更多
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 produ...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.展开更多
文摘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.
文摘Let <em>G</em> be a group. <em>G</em> is right-orderable provided it admits a total order ≤ satisfying <em>hg</em><sub>1</sub> <span style="white-space:normal;">≤ <span style="white-space:normal;"><em>hg</em><sub>2 </sub></span></span>whenever <em style="white-space:normal;">g</em><sub style="white-space:normal;">1</sub><span style="white-space:normal;"> </span><span style="white-space:normal;">≤ <i>g</i><sub>2</sub></span>. <em>G</em> is orderable provided it admits a total order ≤ satisfying both: <em style="white-space:normal;">hg</em><sub style="white-space:normal;">1</sub><span style="white-space:normal;"> </span><span style="white-space:normal;">≤ <em>hg</em><sub>2</sub></span> whenever <span style="white-space:nowrap;"><em>g</em><sub>1</sub> ≤ <em>g</em><sub>2</sub></span> and <em style="white-space:normal;">g</em><sub style="white-space:normal;">1</sub><em style="white-space:normal;">h</em><span style="white-space:normal;"> ≤ </span><em style="white-space:normal;">g</em><sub style="white-space:normal;">2</sub><em style="white-space:normal;">h</em> whenever <em>g</em><sub>1</sub> ≤ <em>g</em><sub>2</sub>. 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.
文摘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.
文摘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.
文摘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.
文摘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.