Diophantine geometry over groups V1: Quantifier elimination I

This paper is the first part (out of two) of the fifth paper in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the two papers on quantifier elimination we use the iterative procedure that validates the correctness of anAE sentence defined over a free group, presented in the fourth paper, to show that the Boolean algebra ofAE sets defined over a free group is invariant under projections, and hence show that every elementary set defined over a free group is in the Boolean algebra ofAE sets. The procedures we use for quantifier elimination, presented in this paper and its successor, enable us to answer affirmatively some of Tarski's questions on the elementary theory of a free group in the sixth paper of this sequence. Partially supported by an Israel Academy of Sciences Fellowship.     

Diophantine geometry over groups V2: quantifier elimination II

This paper is the sixth in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the two papers on quantifier elimination we use the iterative procedure that validates the correctness of an AE sentence defined over a free group, presented in the fourth paper, to show that the Boolean algebra of AE sets defined over a free group is invariant under projections, hence, show that every elementary set defined over a free group is in the Boolean algebra of AE sets. The procedures we use for quantifier elimination, presented in this paper, enable us to answer affirmatively some of Tarski’s questions on the elementary theory of a free group in the last paper of this sequence. Received (resubmission): January 2004 Revision: November 2005 Accepted: March 2006 Partially supported by an Israel Academy of Sciences Fellowship.     

Diophantine geometry over groups III: Rigid and solid solutions

This paper is the third in a series on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the third paper we analyze exceptional families of solutions to a parametric system of equations. The structure of the exceptional solutions, and the global bound on the number of families of exceptional solutions we obtain, play an essential role in our approach towards quantifier elimination in the elementary theory of a free group presented in the next papers of this series. The argument used for proving the global bound is a key in proving the termination of the quantifier elimination procedure presented in the sixth paper of the series. Partially supported by an Israel Academy of Sciences Fellowship.     

Diophantine geometry over groups VI: the elementary theory of a free group

This paper is the sixth in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the sixth paper we use the quantifier elimination procedure presented in the two parts of the fifth paper in the sequence, to answer some of A. Tarski’s problems on the elementary theory of a free group, and to classify finitely generated (f.g.) groups that are elementarily equivalent to a non-abelian f.g. free group. Received (resubmission): January 2004 Revision: January 2006 Accepted: January 2006 Partially supported by an Israel Academy of Sciences fellowship.     

Diophanting geometry over groups II: Completions,closures and formal solutions

This paper is the second in a series on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the second paper we generalize Merzlyakov’s theorem on the existence of a formal solution associated with a positive sentence [Me]. We first construct a formal solution to a generalAE sentence which is known to be true over some variety, and then develop tools that enable us to analyze the collection of all such formal solutions. Partially supported by an Israel Academy of Sciences Fellowship.     

Elementary theories of completely simple semigroups

The connections between first-order formulas over a completely simple semigroupC and corresponding formulas over its structure groupH are found in this paper. For the case of finite sandwich-matrix the criterion of decidability of the elementary theoryT(C) is established in terms of the elementary theory ofH in the enriched signature (Theorem 1). For the general case the criterion is established in terms of two-sorted algebraic systems (Theorem 2). Sufficient conditions in terms ofH for decidability and for undecidability ofT(C) are outlined. Corollaries and examples are presented, among them an example of a completely simple semigroup with a finite structure group and with undecidable elementary theory (Theorem 3).     

Equations and algebraic geometry over profinite groups

The notion of an equation over a profinite group is defined, as well as the concepts of an algebraic set and of a coordinate group. We show how to represent the coordinate group as a projective limit of coordinate groups of finite groups. It is proved that if the set π(G) of prime divisors of the profinite period of a group G is infinite, then such a group is not Noetherian, even with respect to one-variable equations. For the case of Abelian groups, the finiteness of a set π(G) gives rise to equational Noetherianness. The concept of a standard linear pro-p-group is introduced, and we prove that such is always equationally Noetherian. As a consequence, it is stated that free nilpotent pro-p-groups and free metabelian pro-p-groups are equationally Noetherian. In addition, two examples of equationally non-Noetherian pro-p-groups are constructed. The concepts of a universal formula and of a universal theory over a profinite group are defined. For equationally Noetherian profinite groups, coordinate groups of irreducible algebraic sets are described using the language of universal theories and the notion of discriminability.     

On the Loewy Length and the Noetherian Dimension of Artinian Modules

The problem of computing the automorphism groups of an elementary Abelian Hadamard difference set or equivalently of a bent function seems to have attracted not much interest so far. We describe some series of such sets and compute their automorphism group. For some of these sets the construction is based on the nonvanishing of the degree 1-cohomology of certain Chevalley groups in characteristic two. We also classify bent functions f such that Aut(f) together with the translations from the underlying vector space induce a rank 3 group of automorphisms of the associated symmetric design. Finally, we discuss computational aspects associated with such questions.     

Indivisible plexes in latin squares

In this paper, we present two constructions of divisible difference sets based on skew Hadamard difference sets. A special class of Hadamard difference sets, which can be derived from a skew Hadamard difference set and a Paley type regular partial difference set respectively in two groups of orders v ₁ and v ₂ with |v ₁ − v ₂| = 2, is contained in these constructions. Some result on inequivalence of skew Hadamard difference sets is also given in the paper. As a consequence of Delsarte’s theorem, the dual set of skew Hadamard difference set is also a skew Hadamard difference set in an abelian group. We show that there are seven pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁵ or 3⁷, and also at least four pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁹. Furthermore, the skew Hadamard difference sets deduced by Ree-Tits slice symplectic spreads are the dual sets of each other when q ≤ 3¹¹.      

On functional specification of latin squares

This paper studies functional methods for specification of Latin squares over the sets of n-dimensional Boolean vectors, n-dimensional vectors over an arbitrary finite prime field and over an arbitrary finite Abelian group. In conclusion, a method for constructing classes of nongroup Latin squares is presented.     

On the lower central series of the free nilpotent groups of finite rank

In their article, “On the derived subgroup of the free nilpotent groups of finite rank” R. D. Blyth, P. Moravec, and R. F. Morse describe the structure of the derived subgroup of a free nilpotent group of finite rank n as a direct product of a nonabelian group and a free abelian group, each with a minimal generating set of cardinality that is a given function of n. They apply this result to computing the nonabelian tensor squares of the free nilpotent groups of finite rank. We generalize their main result to investigate the structure of the other terms of the lower central series of a free nilpotent group of finite rank, each again described as a direct product of a nonabelian group and a free abelian group. In order to compute the ranks of the free abelian components and the size of minimal generating sets for the nonabelian components we introduce what we call weight partitions.     

An automated modelling approach for dynamic performance evaluation of mechatronic multibody systems

An automated modelling approach of mechatronic multibody systems is presented in this paper. The proposed approach uses some object-oriented GUI modules to automatically generate the dynamic equations for different domains, solve them with numerical methods to obtain approximate solutions, and then evaluate the dynamic performances of the systems. By systematically defining an elementary linear graph and its general rules, the modules of mechanical parts and kinematic pairs can be modelled independently of special systems by the extensible elementary linear graph (EELG) method, and the member's dynamic equations can be derived by topology matrices operation. Some major advantages of this procedure are as follows: the combinations of mechanical components could be dealt with as an integrated member and directly assembled with other modules, the topology structure of individual members are described by elementary cutset and circuit matrices derived from the elementary linear graph, rotation vector is used to express angular variables for analysing rotation and translation with same linear graph; the function vertices, opening edges, and self-closed edges are first introduced to elementary linear graph of kinematic pairs modelling, multiport for special mechanical members and different ports for various energy domains are defined, and relation equations linking the ports are given for interdisciplinary domains, so that the modules could have the characteristics of reapplication and extensibility. For two typical cases, the approach carried out on a Modelica/Dymola software platform is proved feasible by comparing the results using the EELG method with those of the conventional approach.     

ν-perfect groups

Let F_∞ be a free group on a countable set {x₁, x₂, …} and ν be a variety of groups, defined by the set of outer commutators V, in the free generators x_i's.The paper is devoted to give the complete structure of a ν-covering of ν-perfect groups. Fur thermore necessary and sufficient conditions for the universality of a ν-central extension by a group and its ν-covering group will be presented.     

Occurrence problem for free solvable groups

We study the problem on the existence of an algorithm verifying whether systems of linear equations over a group ring of a free metabelian group are solvable. The occurrence problem for free solvable groups of derived length 3is proved undecidable. We give an example of a group with undecidable word problem which is finitely presented in a variety of solvable groups and is defined by the relations from the last commutator subgroup. Translated fromAlgebra i Logika, Vol. 34, No. 2, pp. 211-232, March-April, 1995.     

Free Subgroups of Groups with Nontrivial Floyd Boundary

Abstract

We prove that when a countable group admits a nontrivial Floyd-type boundary, then every nonelementary and metrically proper subgroup contains a noncommutative free subgroup. This generalizes the corresponding well-known results for hyperbolic groups and groups with infinitely many ends. It also shows that no finitely generated amenable group admits a nontrivial boundary of this type. This improves on a theorem by Floyd (Floyd, W. J. (1980). Group completions and limit sets of Kleinian groups. Invent. Math. 57: 205–218) as well as giving an elementary proof of a conjecture stated in that same paper. We also show that if the Floyd boundary of a finitely generated group is nontrivial, then it is a boundary in the sense of Furstenberg and the group acts on it as a convergence group.     

When series of computable functions with varying domains are computable

In this paper we study the behavior of computable series of computable partial functions with varying domains (but each domain containing all computable points), and prove that the sum of the series exists and is computable exactly on the intersection of the domains when a certain computable Cauchyness criterion is met. In our point‐free approach, we name points via nested sequences of basic open sets, and thus our functions from a topological space into the reals are generated by functions from basic open sets to basic open sets. The construction of a function that produces the sum of a series requires working with an infinite array of pairs of basic open sets, and reconciling the varying domains. We introduce a general technique for using such an array to produce a set function that generates a well‐defined point function and apply the technique to a series to establish our main result. Finally, we use the main finding to construct a computable, and thus continuous, function whose domain is of Lebesgue measure zero and which is nonextendible to a continuous function whose domain properly includes the original domain. (We had established existence of such functions with domains of measure less than ε for any , in an earlier paper.)     

Elementary Abelian <Emphasis Type="Italic">p</Emphasis>-groups of rank greater than or equal to 4<Emphasis Type="Italic">p</Emphasis>−2 are not CI-groups

In this paper we prove that an elementary Abelian p-group of rank 4p−2 is not a CI⁽²⁾-group, i.e. there exists a 2-closed transitive permutation group containing two non-conjugate regular elementary Abelian p-subgroups of rank 4p−2, see Hirasaka and Muzychuk (J. Comb. Theory Ser. A 94(2), 339–362, 2001). It was shown in Hirasaka and Muzychuk (loc cit) and Muzychuk (Discrete Math. 264(1–3), 167–185, 2003) that this is related to the problem of determining whether an elementary Abelian p-group of rank n is a CI-group. As a strengthening of this result we prove that an elementary Abelian p-group E of rank greater or equal to 4p−2 is not a CI-group, i.e. there exist two isomorphic Cayley digraphs over E whose corresponding connection sets are not conjugate in Aut E. This research was supported by a fellowship from the Pacific Institute for the Mathematical Sciences.