Adv Syst Sci Appl 2023; 03:153–163 Published online at https://ijassa.ipu.ru. Butler Group Direct Decomposition Classification With Applications to Parallel Algorithms Ekaterina Blagoveshchenskaya*, Ilya Mikulik Emperor Alexander I St. Petersburg State Transport University, St. Petersburg, Russia Abstract: The graphical approach to the classification problem of Butler group direct decompositions is used to preserve the indecomposability property of some rigid subgroups in all possible direct decompositions of the group itself. The group class under consideration as well as torsion-free abelian groups as a whole admits non-isomorphic direct decompositions. The proof of decomposition existence with predicted properties is one of the investigation streams. Until now the related results concerned only the ranks of indecomposable summands. Now the way of controlling the other properties of group decompositions is suggested. All the results in this direction are closely connected with the algorithm parallelization. The special feature of the results presented is that they give the method of constructing certain dependence graphs as the subgraphs of the algorithm graph to be given in a parallel form preserving the corresponding fragments. Such dependence subgraphs can define the data relations in parallel computations, which reflect various conditions of parallelism. Keywords: Butler groups, direct decompositions, parallel algorithms 1. INTRODUCTION We consider a class of torsion-free abelian groups which is a subclass of the so-called almost completely decomposable groups. The latter belong to the wider class of Butler groups which are epimorphic images of finite rank completely decomposable groups, see [1, Theorem 2.4.19]. Recall the main notions. The monographs [1] - [4] serve as the main references and we adopt their standard notations throughout this paper. Any torsion-free abelian group the can be considered as a subgroup of a direct sum of copies of the rationals Q. If the minimal possible number of the summands is finite then it is called the rank of X , which is denoted by rkX (in comparison, there exist abelian groups of infinite ranks). A cd-group (completely decomposable group) is a direct sum of rank-one groups (subgroups of the rationals). An acd-group X (almost completely decomposable group) is a torsion-free abelian group of finite rank, that contains a completely decomposable group V with finite X/V . If in addition X/V is a cyclic group then X is called a crq-group (i.e. an acd-group with cyclic regulator quotient). Any acd-group X has a distinguished completely decomposable fully invariant subgroup R(X). This group R(X) is called the regulator of X , and [X : R(X)] is the regulator index of X . Its regulator exponent is the exponent e =: exp X/R(X) of the regulator quotient X/R(X). In general, for an abelian group generated by a system of elements we use the symbol ⟨. . . ⟩. As usual, V ⊂ X means that V is a subgroup of X and V∗ = {g ∈ X : there is n ∈ ∗Corresponding author: blagoveschenskaya@pgups.ru, kblag2002@yahoo.com 154 EKATERINA BLAGOVESHCHENSKAYA, ILYA MIKULIK N with ng ∈ V } denotes the purification of V in X . The type of an element g ∈ X denoted by tpX g can be determined as the isomorphism class of the rational group τ , which is isomorphic to ⟨g⟩∗ in X and contains the group of integers Z. Then we may say that the element g is of type τ , Z ⊂ τ ⊂ Q. Furthermore, tpX g coincides with the group type, tpX , if X is a homogeneous group. We will write τ(p) = ∞ or pτ = τ if 1/pn belongs to τ for any natural number n (p is a prime). Following standard definitions also X∗(τ) = ∑ σ>τ X(σ) and X♯(τ) is the purification of X∗(τ) in X . A type τ is critical, a member of the set Tcr(X) of critical types of X , if X(τ)/X♯(τ) ̸= 0, see [1, p. 37, Definition 2.4.6 ]. Any direct sum of rank-one groups of a fixed type τ is called (τ−) homogeneous cd-group, i.e. completely decomposable group, whose elements are of type τ . We are concentrated on the so-called block-rigid crq-groups X of ring type and their direct decompositions. This means that Tcr(X) is an antichain and consists only of idempotent types (i.e. the ones which are types of idempotent rational groups, or in other words, can be represented by characteristics, consisting only of 0′s and ∞′s, see [1, p. 13], [3, Section 85]). The regulator A = R(X) decomposes uniquely A = ⊕ τ∈Tcr(X) Aτ into its τ - homogeneous components Aτ = A(τ) = X(τ), which are pure in X (that is na ∈ Aτ with natural n and a ∈ X implies a ∈ Aτ ). If τ ̸∈ Tcr(X)) then Aτ = 0. If rkAτ = 1 for all τ ∈ Tcr(X), then A and X are called rigid groups. Torsion-free abelian groups admit non-isomorphic direct decompositions. Traditionally, direct decomposition classification is based on the near-isomorphism equivalence, which preserves their properties in detail. Here we introduce a very natural weaker equivalence with the one goal to preserve only the main properties of abelian group direct decompositions. 2. DIRECT DECOMPOSITION THEORY OF CRQ-GROUPS: BASIC RESULTS Near-isomorphism is an equivalence, which is weaker than isomorphism and traditionally used for classification of groups of this class, see [1, Definition 9.1.2, Theorem 9.1.4, 5], [2, Theorem 7.16]: Definition 2.1: Let G and H be torsion-free abelian groups of finite rank. Then G and H are called nearly isomorphic (in symbols G ∼=nr H) if and only if for any prime q there are monomorphisms ηq : G −→ H and ξq : H −→ G such that H/ηq(G) and G/ξq(H) are finite groups and |H/ηq(G)| and q as well as |G/ξq(H)| and q are relatively prime. This equivalence preserves decomposability properties of torsion-free abelian groups of finite rank: Theorem 2.1 (12.9 (b), p. 144, [2]): Let X and Y be nearly isomorphic torsion-free abelian groups of finite rank and X = X1 ⊕X2. Then there exists a decomposition Y = Y1 ⊕ Y2 with Y1 ∼=nr X1 and Y2 ∼=nr X2. We concentrate on a block-rigid crq-group X of ring type with the regulator A = R(X) and cyclic regulator quotient X/A with e = exp X/A = |X/A|. The completely decomposable group A is a direct sum of its τ -homogeneous components Aτ = A(τ) with Aτ ∼= nττ (a direct sum of nτ copies of τ , Z ⊂ τ ⊂ Q), that is A = ⊕ τ∈Tcr(A) A(τ), and n = rkX = rkA = ∑ τ∈Tcr(A) nτ . Choose a generator b+ A of X/A, then eb = ∑ τ∈T vτ , vτ ∈ Aτ , and mτ = mτ (X) = |vτ | = |vτ + eA|, (2.1) Clearly e = lcmτ∈Tcr(X) mτ . It is shown in [5, Lemma 2.2] that mτ (X) do not depend on the choice of element b and serve as invariants of group X . Moreover, they are the same for nearly isomorphic groups: Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) BUTLER GROUP DIRECT DECOMPOSITION CLASSIFICATION 155 Theorem 2.2 (Near–Isomorphism Criterion, Theorem 2.4, [5]): Let X and Y be block-rigid crq-groups. Then X ∼=nr Y if and only if R(X) ∼= R(Y ) and mτ (X) = mτ (Y ) for all types τ . We always put mτ (X) = 1 if τ /∈ Tcr(X)). It is easy to see that for any prime divisor p of e there exist at least two members of Tcr(X), say τ and σ, such that gcd(mτ ,mσ) is divisible by p (if only one mτ is divisible by p then p|aτ which contradicts the purity of Aτ in A = R(X)). We list the additional restrictions on the groups X under consideration: S1. e is a square-free natural number; S2. for any prime divisor p of e there exist exactly two invariants, say mτ and mσ, which are divisible by p; S3. mτ (X) ̸= 1 for any τ ∈ Tcr(X). A special decomposition, called the main decomposition in [1, Theorem 13.1.6] and [5, Theorem 3.5], always exists for almost completely decomposable groups, according to Main Decomposition Theorem (see [1, Theorem 9.2.7]). For the groups under consideration it is described in Theorem 2.3 (Main Decomposition, Theorem 3.5, [5]): Let X be a block–rigid crq-group. Then there exists a decomposition X = X0 ⊕ A′ such that A′ is completely decomposable, X0 is a rigid crq-group and τ ∈ Tcr(X0) if and only if mτ (X0) = mτ (X) > 1. The group X0 is unique up to near isomorphism and A′ is unique up to isomorphism. Such a main decomposition is not unique but uniquely determined up to near isomorphism. The rigid summand X0 from any main decomposition is called a main summand of X . Since direct decompositions into indecomposable summands are of great importance the special role belongs to the following Theorem 2.4 (Indecomposability Criterion, Theorem 3.7, [5]): Let X be a block–rigid crq–group. Then X is directly indecomposable if and only if X is rigid, and there is no non–trivial partition Tcr(X) = T1 ∪ T2 such that gcd(mσ(X),mτ (X)) = 1 whenever σ ∈ T1 and τ ∈ T2. The next theorem describes all the decompositions of a block-rigid crq-group into direct sum of indecomposable summands up to near isomorphism. Theorem 2.5 (Decomposability Criterion, Theorem 3.3, [5]): Let X be a block-rigid crq-group. If X = X1 ⊕X2 ⊕ . . .⊕Xt ⊕Xt+1 with completely decomposable Xt+1 (rkXt+1 ⩾ 0) and rigid indecomposable crq-groups Xi with mτi = mτ (Xi), i = 1, . . . , t, then, for all types τ , mτ (X) = ∏t i=1 mτi is a factorization such that: D1. the integers mτi and mσj are relatively prime whenever i ̸= j; D2. |{i : mτi > 1}| ≤ rk(X(τ)); D3. for any i = 1, . . . , t there is no non–trivial partition Tcr(Xi) = T i 1 ∪ T i 2 such that gcd(mσi,mτi) = 1 whenever σ ∈ T i 1 and τ ∈ T i 2. Conversely, if mτ (X) = ∏t i=1mτ i is a factorization of the mτ (X) such that the decomposability conditions D1, D2 and D3 are satisfied, then there is a decomposition X = X1 ⊕X2 ⊕ · · · ⊕Xt ⊕Xt+1 such that Xi are rigid indecomposable crq-groups, Tcr(Xi) = {ρ : mρi > 1} and mτ (Xi) = mτi for i = 1, . . . , t, and Xt+1 is a completely decomposable group (may be it is 0). Remark 2.1: I. If the condition D3 is excluded, the theorem remains true, but the rigid direct summands of X are not necessarily indecomposable. Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) 156 EKATERINA BLAGOVESHCHENSKAYA, ILYA MIKULIK II. Let X = X1 ⊕X2 ⊕ · · · ⊕Xv be a decomposition into indecomposable summands with Tcr(X1) ∩ Tcr(X2) = {τ1, . . . , τs} ≠ ∅. Then there exists a decomposition X ∼= X1,2 ⊕ τ1 ⊕ . . .⊕ τs ⊕X3 ⊕ . . .⊕Xv with the indecomposable group X1,2 satisfying the conditions: Tcr(X1,2) = Tcr(X1) ∪ Tcr(X2), rkX1,2 ∼= rkX1 + rkX2 − s, mτ (X1,2) = mτ (X1)mτ (X2). III. Let X = X1 ⊕X2 and X = X ′ 1 ⊕X ′ 2 be two decompositions with indecomposable summands X1, X ′ 1 and let Tcr(X1) ∩ Tcr(X ′ 1) = {τ1, . . . , τs} ≠ ∅. Then there exists a decomposition X = X1,2 ⊕X ′′ 2 having the indecomposable summand X1,2, which satisfies the conditions: Tcr(X1,2) = Tcr(X1) ∪ Tcr(X ′ 1), rkX1,2 ∼= rkX1 + rkX ′ 1 − s, mτ (X1,2) = mτ (X1)mτ (X ′ 1). IV. Let A = R(X) = ⊕ τ∈Tcr(X) Aτ and let X = X1 ⊕X2 ⊕ · · · ⊕Xv be a decompo- sition into indecomposable summands. If p | gcd(mτ (Xi),mσ(Xi)) ̸= 1 for some i and rk(Aτ ) = 1 then σ ∈ Tcr(Xi) with p | exp(Xi/R(Xi)) . 3. CLASSIFICATION OF BLOCK-RIGID CRQ-GROUPS: GENERAL APPROACH Let X be a block-rigid crq-group of ring type having the regulator A = R(X) and the cyclic regulator quotient X/A with e = exp X/A = |X/A|. Denote by P = P(X) the set of all prime divisors of e = expX/A of a crq-group X . The completely decomposable group A is a direct sum of its τ -homogeneous components Aτ = A(τ) with Aτ ∼= nττ (a direct sum of nτ copies of τ , Z ⊂ τ ⊂ Q), that is A = ⊕ τ∈Tcr(A) A(τ), and n = rkX = rkA =∑ τ∈Tcr(A) nτ . For any acd-group X (not only for that with a cyclic regulator quotient) its regulator A is a fully invariant subgroup. Then for any group decomposition X = X1 ⊕X2 there exists the corresponding regulator decomposition A = A1 ⊕ A2 such that X/A ∼= X1/A1 ⊕X2/A2. Then e = e1e2 with ei = exp Xi/Ai, i = 1, 2. Let us introduce the definition of the new very natural equivalence on the class of acd-groups which is stronger than quasi-isomorphism but weaker than near isomorphism and preserves only the regulators and regulator quotients of groups and their direct decompositions. Definition 3.1: Let X and Y be acd-groups. Then X and Y are called factor-identical groups (in symbols X ∼=fi Y ) if R(X) ∼= R(Y ) and X/R(X) ∼= Y/R(Y ). Definition 3.2: Let X and Y be acd-groups. Then X and Y are called strongly factor-identical groups (in symbols X ∼=sfi Y ) if and only if X ∼=fi Y and for any decomposition X = X1 ⊕X2 ⊕ . . .⊕Xt into indecomposable summands there also exists a decomposition Y = Y1 ⊕ Y2 ⊕ . . .⊕ Yt with indecomposable summands such that Xi ∼=fi Yi for any i = 1, . . . , t. Remark 3.1: I. Let X and Y be nearly isomorphic acd-groups. Then X and Y are strongly factor-identical. II. Let X and Y be factor-identical indecomposable acd-groups. Then X and Y are strongly factor-identical. III. Let X and Y be factor-identical indecomposable acd-groups of rank 2. Then X and Y are strongly factor-identical, moreover, X ∼=nr Y . Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) BUTLER GROUP DIRECT DECOMPOSITION CLASSIFICATION 157 IV. Let X and Y be factor-identical acd-groups and X = X1 ⊕X2, Y = Y1 ⊕ Y2 with X1 ∼=fi Y1 . Then X2 ∼=fi Y2. V. Let X and Y be strongly factor-identical acd-groups and X = X1 ⊕X2, Y = Y1 ⊕ Y2 with X1 ∼=sfi Y1 . Then X2 ∼=sfi Y2. We are interested in crq-groups X and Y which are strongly factor-identical but not nearly isomorphic. Without loss of generality assume that a completely decomposable group A serves as the regulator for the both groups and X/A ∼= Y/A with e = exp X/A = exp Y/A. For a crq-group X define the set of its near-isomorphism invariants: MX = {mτ (X), τ ∈ Tcr(A)}. For any prime divisor p of e denote Tp(X) = {τ ∈ Tcr(A) : p | mτ (X)}, (3.2) by the condition, |Tp(X)| = 2. Definition 3.3: Let X be a crq-group. A subset M ′ of MX is called a type-connected set if and only if for any non-trivial partition M ′ = M ′ 1 ∪M ′ 2 with disjoint M ′ 1 and M ′ 2 there exist mτ (X) ∈ M ′ 1 and mσ(X) ∈ M ′ 2 which are not relatively prime. If any mτ (X) ∈ (MX \M ′) is not p-divisible for a prime p ∈ P , then a type-connected set M ′ is called a cover for the factor p in X and it is denoted by M ′(p). In general, this type- connected set is not uniquely determined. In particular, the two members mτ (X), mσ(X) of the set MX , which are divisible by p, form the minimal cover for p, exactly, {mτ (X),mσ(X)} is the minimal cover for p if and only if Tp(X) = {τ, σ}, see (3.2). For a prime p ∈ P define T X p , the set of all the primes such that for each q ∈ T X p there exists a cover M ′(p, q) for the factors p and q simultaneously. If M ′(p, q) is not empty, it is not uniquely determined in general. We have the set union P = ⋃ p∈P T X p (3.3) as there exists the minimal cover for each p. The members of the same set T X p are equivalent in accordance with the equivalence relation introduced on the set P as being members of the same Tp. Indeed, this relation is trivially reflexive because p ∈ T X p . It is obviously symmetric which means that q ∈ T X p implies p ∈ T X q . The transitivity follows the fact that p ∈ T X q , q ∈ T X r imply r ∈ T X q by symmetry, therefore, p and r belong to the same set T X q . Then (3.3) is a union of pairwise disjoint or completely coinciding subsets. Fix a set PX of primes from P such that P = ⋃ p∈PX T X p (3.4) consists of only pairwise disjoint sets. For a crq-group X denote MX p = {mτ (X) : there exists q ∈ T X p such that q | mτ (X)}. Clearly, MX = ⋃ p∈PX MX p (3.5) Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) 158 EKATERINA BLAGOVESHCHENSKAYA, ILYA MIKULIK is a uniquely determined union of pairwise disjoint type-connected subsets MX p , which will be called a canonical decomposition of the set of the near-isomorphism invariants of a crq- group X . Note that MX p is the maximal cover for each q ∈ T X p , therefore, any two members of different sets Mp X are relatively prime. We also need RX p = {τ : mτ (X) ∈ Mp X}. Denote eXp = lcm{mτ (X) : τ ∈ RX p }. Clearly, e = ∏ p∈PX eXp (3.6) with gcd(eXp , e X q ) = 1, and Tcr(X) = ⋃ p∈PX RX p with RX p ∩RX q = ∅ if p /∈ T X q (or p ̸= q if we take the numbers from the set PX). We also have that any q ∈ T X p divides eXp . 4. DIRECT DECOMPOSITION CLASSIFICATION OF BLOCK-RIGID FACTOR- IDENTICAL CRQ-GROUPS Since factor-identical crq-groups X and Y have isomorphic regulators we assume that a ring type block-rigid completely decomposable group A serves as the regulator for the both groups. Furthemore, according to the Definition 3.1 we have that e = |X/A| = |Y/A| and P is the set of all prime divisors of e. We start with rigid crq-groups X . Theorem 4.1: Let X and Y be factor-identical rigid crq-groups. Then X and Y are strongly factor-identical if and only if T X p = T Y p and RX p = RY p for any p ∈ P . Proof As X is a rigid crq-group, it follows from Theorem 2.4 that their exists the only one decomposition X = ⊕ p∈PX Xp into indecomposable summands Xp which satisfy the conditions RX p = Tcr(X p) and ep = expXp/R(Xp) = lcm{mτ (X) : τ ∈ RX p }. Note that Xp is allowed to be a rank-one group isomorphic to some τ ∈ Tcr(X) with mτ (X p) = 1 and ep = 1. Let Y = ⊕ p∈PY Y p be a decomposition into indecomposable summands. Evidently, crq- groups X and Y are strongly factor-identical if and only if the corresponding indecomposable summands of their main decompositions are factor-identical (after a suitable reordering if necessary). It takes place if and only if R(Xp) ∼= R(Y p) and X/R(Xp) ∼= Y/R(Y p) for any p. Since the regulators of Xp and Y p are rigid completely decomposable groups and the factor-groups over the regulators are cyclic groups with square-free orders ep, these conditions are equivalent to the following, RX p = RY p and T X p = T Y p for any p ∈ P as required. For a block-rigid crq-group we define the set P ′(X) = {q ∈ P : q|mτ (X) if and only if rkAτ ⩾ 2} (4.7) which satisfies the condition: if q ∈ P ′(X) and Tq(X) = {τ, σ} then rkAτ ⩾ 2 and rkAσ ⩾ 2, see (3.2). Denote P ′′(X) = P \ P ′(X), then P = P ′(X) ∪ P ′′(X), (4.8) Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) BUTLER GROUP DIRECT DECOMPOSITION CLASSIFICATION 159 with P ′′(X) = {q ∈ P : rkAσ < 2 or rkAσ < 2 with Tq(X) = {τ, σ}}. (4.9) Introduce the subset P 0(X) of P ′′(X): P 0(X) = {q ∈ P : rkAσ = 1 and rkAσ = 1 with Tq(X) = {τ, σ}}. (4.10) Note that P 0(X) = P and consists of all prime divisors of |X/R(X)| if X is a rigid crq- group. We also introduce the subset T ′(X) of Tcr(X) which consists of all the types τ satisfying rkAτ = 1. We use the so-called primary factor representation X = ∑ p∈P Xp (4.11) for uniquely determined fully invariant crq-groups Xp having the same regulator A and the regulator quotients Xp/A ∼= Z/pZ. For any subset P̃ ⊂ P define a fully invariant subgroup of X as XP̃ = ∑ p∈P̃ Xp, (4.12) then X = XP ′(X) +XP ′′(X). Theorem 4.2 (Criterion of strong factor-identity for crq-groups): Let X and Y be factor-identical block-rigid crq-groups with P ′ = P ′(X). Then X and Y are strongly factor-identical if and only if the following conditions hold: (1) P ′ = P ′(Y ); (2) XP ′ ∼=nr YP ′; (3) XP ′′ ∼=sfi YP ′′ . Proof Without loss of generality we assume that the groups X and Y have the same regulator A = R(X) = R(Y ) and the same regulator exponent e = |X/A| = |Y/A|, see Definition 3.1. If X is indecomposable then it is rigid which means X = XP 0(X) and the theorem is trivial. In general we apply the decomposability criterion for crq-groups, see Theorem 2.5. Assume that X and Y are strongly factor-identical. It is immediate from (4.11) that Xp = Xp 0 ⊕ A′p is the only one possible decomposition up to near isomorphism, which is the main decomposition, whose main summand Xp 0 is an indecomposable crq-group of rank 2 with Tcr(X p 0 ) = Tp(X) = {τ, σ} and expXp 0/R(Xp 0 ) = p. I. If p ∈ P ′(X) then X = V p 0 ⊕ V p with V p 0 ∼=nr X p 0 . It corresponds to the following factorizations of the invariants mτ (X) = mτ (V p 0 )mτ (V p): 1. Tcr(V p 0 ) = {τ, σ} and mτ (V p 0 ) = mσ(V p 0 ) = p; 2. Tcr(V p) = Tcr(X), mτ (V p) = mτ (X) p , mσ(V p) = mσ(X) p and mρ(V p) = mρ(X) if ρ /∈ Tp(X). This means that for any p ∈ P ′(X) the main summand Xp 0 of Xp is nearly isomorphic to an indecomposable summand of X . Then Y has an indecomposable summand of rank 2, which is also nearly isomorphic to Xp 0 for the prime p ∈ P , see Remark 3.1(III). Therefore, Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) 160 EKATERINA BLAGOVESHCHENSKAYA, ILYA MIKULIK p ∈ P ′(Y ), and, by symmetry, we conclude that P ′ = P ′(X) = P ′(Y ) with XP ′ ∼=nr YP ′ by Theorem 2.2. Then P ′′(X) = P ′′(Y ). Denote P ′′ = P ′′(X) = P ′′(Y ). II. Let XP ′′ = Z ⊕G with indecomposable Z, see (4.9, 4.12). Clearly, Z is a rigid crq-group and Z/R(Z) ∼= ( ⊕ τ∈Tcr(Z) Aτ ) X ∗ / ⊕ τ∈Tcr(Z) Aτ by Remark 2.1(III). There exists a decomposition X = W0 ⊕W with W0 ∼=cr Z by Theorem 2.5. It corresponds to the following factorizations of the invariants mτ (X) = mτ (W0)mτ (W ): 1. Tcr(W0) = Tcr(Z) and mτ (W0) = mτ (Z) by Theorem 2.2; 2. Tcr(W ) = Tcr(X) \ (T ′(X) ∩ Tcr(Z)), mρ(W ) = mρ(X) mρ(Z) for any ρ ∈ Tcr(W ). (traditionally we set mτ (Z) = 1 if τ ∈ Tcr(X) \ Tcr(Z)). Since X and Y are supposed to be strongly factor-identical, Y has an indecomposable summand, say V0, which is factor-identical to Z. Let Y = V0 ⊕ V . We conclude from Remark 3.1(II,V) that W ∼=sfi V with P ′′(W ) = P ′′(V ) = P ′′(X) \ P 0(Z), and the induction on the number of indecomposable summands leads to the conclusion that XP ′′ ∼=sfi YP ′′ . Conversely, assume that P ′(X) = P ′(Y ). This implies P ′′(X) = P ′′(Y ). For P ′ = P ′(X) and P ′′ = P ′′(X) we have XP ′ ∼=nr YP ′ and XP ′′ ∼=sfi YP ′′ by the condition. Let X = X1 ⊕X2 with indecomposable X1. Then XP ′ = X ′ 1 ⊕X ′ 2 and XP ′′ = X ′′ 1 ⊕ X ′′ 2 with X ′ i = XP ′ ∩Xi, X ′′ i = XP ′′ ∩Xi, i = 1, 2, as XP ′ and XP ′′ are fully invariant in X . Denote e1 = expX ′ 1/R(X ′ 1) and e2 = expX ′′ 1 /R(X ′′ 1 ) with Tcr(X1) = Tcr(X ′ 1) ∪ Tcr(X ′′ 1 ) and e1e2 = |X1/R(X1)|. It follows from e1 | expXP ′/A and e2 | expXP ′′/A that gcd(e1, e2) = 1. There exist direct summands Y ′ 1 and Y ′′ 1 of Y such that X ′ 1 ∼=nr Y ′ 1 and X ′′ 1 ∼=sfi Y ′′ 1 by the condition, and we apply Remark 2.1(III) to get that Y = Y1 ⊕ Y2 with indecomposable Y1 ∼=sfi X1 satisfying expY ′ 1/R(Y ′ 1) = e1e2. We apply the same approach to the groups X2 and Y2 by Remark 3.1(V), which is actually an induction on the number of indecomposable summands leading to the required conclusion X ∼=sfi Y . Now we need to obtain the coditions for crq-groups to be strongly factor-identical if their regulator homogeneous components satisfy the condition: if gcd(mτ ,mσ) ̸= 1 then Aτ or Aσ is a rank-one group (in particular, rk(Aτ ⊕ Aσ) = 2) . It takes place if P(X) = P ′′(X), and we fix this condition. Let P ∗(X) = P ′′(X) \ P 0(X), then X = XP 0(X) +XP ∗(X), see (4.12). Denote P 0 = P 0(X), P ∗ = P ∗(X), V = XP 0 and W = XP ∗ , see (4.12). We have that XP ′′ = V +W and consider the canonical decomposition of the the near-isomorphism invariant set of the rigid crq-group V : MV = ⋃ p∈PV MV p into pair-wise disjoint subsets with PV ⊂ P 0, see (3.5). Applying (3.6) to the group V we have that eVp = lcm{mτ (V ) : τ ∈ RV p ⊂ Tcr(V ) ⊂ Tcr(X)} with RV p = {τ : mτ (V ) ∈ Mp V }. We also introduce the numbers e′ X p = lcm{mτ (X) : τ ∈ RV p }. Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) BUTLER GROUP DIRECT DECOMPOSITION CLASSIFICATION 161 It is important that e = |X/A| = ∏ p∈PV e′Xp by the condition P(X) = P ′′(X). Denote M ′ X = {mτ (X) : gcd(mτ (X), e′ X p ) ̸= 1} and R′X p = {τ ∈ Tcr(X) : gcd(mτ (X), e′Xp ) ̸= 1} = {τ ∈ Tcr(X) : mτ (X) ∈ M ′ X}. Let X ′ p = ( ⊕ τ∈R′X p Aτ ) X ∗ . By construction, the sets of types R′X p = Tcr(X ′ p) are not supposed to be pair-wise disjoint and Tcr(X) = ⋃ p∈PV R′X p . Therefore, X = ∑ p∈PV X ′ p. Denote T X′ p = {q ∈ P : q|e′Xp }, we see that P = ⋃ p∈PV T X′ p . Recall that the set PV can be chosen differently as a subset of P , see (3.4). In fact, each number q determines one of the sets {T X′ p : p ∈ PV }, exactly, that one, which contains this prime number q. Without loss of generality, instead of PV we take the set QX which can have prime divisors of e′Xp eVp , that is QX ⊂ P(X) = P ′′(X). Then we write P = ⋃ p∈QX T X′ p and X = ∑ p∈QX X ′ p with Tcr(X) = ⋃ p∈QX R′X p . Theorem 4.3 (Criterion of strong factor-identity for special crq-groups): Let X and Y be factor-identical block-rigid crq-groups with the regulator A and P ′′ = P(X) = P(Y ) such that X = XP ′′ and Y = YP ′′ . Then X and Y are strongly factor-identical if and only if there exists a subset Q of P ′′ such that the groups X ′ p and Y ′ p are factor-identical for any p ∈ Q. Proof Each group X ′ p has the only one decomposition, which is its main decomposition X ′ p = X ′ 0p ⊕ A′ p into the rigid indecomposable group X ′ 0p, having the critical typeset Tcr(X ′ 0p) = Tcr(X ′ p), and a completely decomposable group A′ p. Then X ′ p ∼=fi Y ′ p implies X ′ 0p ∼=fi Y ′ 0p, that is X ′ p and Y ′ p are strongly factor-identical for any p ∈ Q by the condition, see Theorem 4.1. The necessity of this condition follows from the fact that, by construction, the groups X and Y have direct decompositions with indecomposable summands nearly isomorphic to X ′ 0p and Y ′ 0p accordingly, see Theorem 2.5. The sufficiency is obtained on the basis of the same direct decompositions by Remark 2.1(II, III). 5. ALGORITHMS OF BUTLER GROUP DIRECT DECOMPOSITIONS AS A PARALLEL PROGRAMMING MODEL Let us recall some links between crq-group direct decomposition theory and the theory of graphs from [6] - [7]. We need a graph Γ, which is an r-colorable graph, that is each vertex can be assigned one of the r colors so that no two adjacent vertices are of the same color, see [8, 14.1]. As for the crq-group X associated with graph Γ, it will be characterized by some restriction on the invariants mτ = mτ (X). Recall that for any prime divisor p of e there exist two members of Tcr(A), say τ and σ, such that gcd(mτ ,mσ) is divisible by p (if only one mτ is divisible by p then p|aτ which contradicts the purity of τaτ in A). We constructed a crq-group X of rank n satisfying the special previously listed conditions (S1, S2, S3). Recall the following Definition 5.1 (Definition 3.9, [5]): Let X be a block–rigid crq–group. The frame of X is a graph F (X) whose vertices are the Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) 162 EKATERINA BLAGOVESHCHENSKAYA, ILYA MIKULIK elements of Tcr(X) and two vertices σ and τ are joined by the edges designated by ”p” for each prime divisor p of gcd(mσ(X),mτ (X)). Note that if X is rigid then the frame vertex number coincides with rkX and it an indecomposable group if and only if its frame is connected, see Theorem 2.4. Passing to the graphical illustration of the main decomposition of X by graph Γ, we denote r = |Tcr(X)| and arrange the elements of its critical typeset in an arbitrary way, Tcr(X) = {τ1, . . . , τr}. Then A = Aτ1 ⊕ Aτ2 ⊕ . . .⊕ Aτr . Let us distribute n vertices of Γ on the r radiuses τ1, . . . , τr of some concentric circles so that the circle of the smallest radius would be filled with the vertices of the frame F (X), and each radius τi would contain ni = rkAτi vertices, i = 1, . . . , r. Recall that all the prime divisors p of e are naturally assigned to the edges of the frame, and, therefore, F (X) is located on the circle of the smallest radius, see Definition 5.1. By construction, any two adjacent (connected by an edge) vertices of graph Γ never share the same radius. Thus, graph Γ is an r-colorable graph (with only vertices of different colors connected by edges). The graph Γ is the union of the frame F (X) and the set of isolated vertices. We call Γ the main graph of group X since its main decomposition X = Y ⊕ A′ can be easily reconstructed from Γ up to near isomorphism by visualization Y as F (X) (condition S3.) and identifying completely decomposable A′ with the set of all isolated vertices of Γ. The Decomposability criterion (Theorem 2.5) states that all the other decompositions X = X1 ⊕X2 ⊕ . . .⊕Xt ⊕Xt+1 up to near-isomorphism can be seen as the special transformations of graph Γ, which will be called ”admissible transformations”. They can be obtained by moving the edges so that the edge p of the new graph Γ′ would join (another) pair of vertices, but at the same radiuses as those in Γ and under the important restriction that no pair of vertices of the same connected component share the same radius (see Theorem 2.2). Then the vertex number of each component coincides with the rank of the corresponding indecomposable summand. Moreover, the connected components are the frames of rigid indecomposable crq-groups X1, X2, . . . , Xt, whose critical types and, therefore, the regulators are determined by their vertex radiuses, while the prime divisors of e = expX/A are interpreted as the edges allowing us to calculate the invariants mτ (Xi), i = 1, . . . , t, as their partial products. Meantime, the isolated vertices correspond to completely decomposable group Xt+1. Thus, admissible transformations of Γ lead to the new set of connected components forming a graph with the same number of vertices of each color and the same number of edges connecting the vertices of any two different colors as those in Γ. The graphical approach to direct decompositions of the considered groups opens some new prospects in parallel programming modeling. The main graph of an almost completely decomposable group after the choosing homogeneous component numeration becomes an oriented graph of a sequential algorithm. The group direct decompositions are in the correspondence with the set of possible parallel decompositions of the algorithm into a number of threads. We can apply them to modify the Parallel Random Access Machine (PRAM) using the parallel programming with hints, called semi-implicit parallelism, see [9]- [10]. More exactly, the special choice of the group homogeneous component ranks preserves the fixed graph fragments associated with the so-called maximal stable subgroups. We call the subgroups X ′ 0p with p ∈ Q the maximal stable subgroups of X as each of them is a maximal indecomposable subgroup always serving up to near isomorphism as a fully invariant subgroup of one of the indecomposable summands for any possible direct decomposition of X . Then the Theorem 4.3 says that crq-groups X and Y with the same regulator A and P ′′ = P(X) = P(Y ) are strongly factor-identical if only if the sets of their maximal stable subgroups consist of the factor-identical groups. Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) BUTLER GROUP DIRECT DECOMPOSITION CLASSIFICATION 163 This meets the programmer’s instruction to save these parts, which correspond to the maximal stable subgroups, for the separated execution. It is a way of creating a universal parallel programming for solving the tasks, which are of the same kind but differ in the particular segments. Note, that it is also the way to save the cores involved for the other processes during the time of the special segment fulfillment. Thus, the direct decomposition graph of an acd-group with some predicted properties can be applied to the parallel programming solution of the tasks with the special segments needing the particular attention of the programmer. It can be also used as one of the first steps within the general approach to the task solution under consideration. ACKNOWLEDGEMENTS The research was supported by the Russian Science Foundation (project No. 22-21- 00267). REFERENCES 1. Mader, A. (2000). Almost completely decomposable groups. Amsterdam, Netherlands: Gordon and Breach. 2. Arnold, D. (1982). Finite Rank Torsion Free Abelian Groups and Rings. Berlin, Germany: Springer Verlag. 3. Fuchs, L. (1970). Infinite Abelian Groups. Cambridge, MA: Academic Press. 4. Blagoveshchenskaya, E. (2009). Almost Completely Decomposable Abelian Groups and their Endomorphism Rings. St. Petersburg, Russia: Mathematics in Polytechnical University. 5. Blagoveshchenskaya, E., & Mader, A. (1994). Decompositions of almost completely decomposable abelian groups, Contemporary Mathematics, 171, 21–36. 6. Blagoveshchenskaya, E., & Kunetz, D. (2018). Direct decomposition theory of torsion- free abelian groups of finite rank: graph method, Lobachevskii Journal of Mathematics, 39, 29—34. 7. Blagoveshchenskaya, E., Zuev, D., & Kunetz, D. (2016). Torsion-free abelian groups, graphs and algorithms, Proc. of International conference ”Mathematics and Informatics”, Moscow, Russia. 8. Bondy, J.A. & Murty, U.S.R. (1976). Graph theory with applications. Amsterdam, Netherlands: Elsevier. 9. Ding, C. (2011). Parallel programming by hints. Proc. of the ACM international conference on object oriented programming systems languages and applications, Cascais , Portugal, 13–14, https://doi.org/10.1145/2048147.2048154 10. Helm, D., et al. (2020). A programming model for semi-implicit parallelization of static analyses. Proc. of the 29th ACM SIGSOFT International Simposium on software testing and analyses, Los Angeles, CA, 428–439, https://doi.org/10.1145/3395363.3397367 Copyright © 2023 ASSA. Adv Syst Sci Appl (2023) Introduction Direct decomposition theory of crq-groups: basic results Classification of block-rigid crq-groups: general approach Direct decomposition classification of block-rigid factor-identical crq-groups Algorithms of Butler group direct decompositions as a parallel programming model