Raising all group elements to a common power
HUI-TING CHEN, CHING-LUEH CHANG
Department of Computer Science and Engineering
Yuan Ze University
No. 135, Yuandong Rd., Zhongli Dist., Taoyuan City Taiwan (R.O.C.)
TAIWAN
Abstract: - We give a deterministic O(|G|)-time algorithm that, given the multiplication table of a finite group (G, ·)
and nonzero p,q∈Z, finds all solutions (if any) to xp=gqfor all g∈G.
Key-Words: - inverting element, group, multiplication table and power.
Received: July 4, 2022. Revised: January 5, 2023. Accepted: February 4, 2023. Published: March 2, 2023.
1 Introduction
Many properties of a group-like structure can be discov-
ered from its multiplication table. Zumbrägel et al., [1]
, consider the problem of learning the multiplication ta-
ble of a groupoid (G, ·)by making the minimum num-
ber of queries, each for a product a·b, with a, b ∈G.
An interesting problem is to determine algebraic prop-
erties of a finite group Gfrom Ψ(G) = ∑g∈Go(g),
where o(g)denotes the order of g∈G, [2]–[5]. Jahani
et al., [6], find a pair of finite groups Gand Sof the
same order such that Ψ(G)<Ψ(S), with Gsolvable
and Ssimple.
Now we are interested in efficiently finding a given
power of all elements simultaneously. By convention,
the multiplication in Gcosts O(1) time. Let Gbe a
group with nelements. If we want to calculate the qth
power of each element, how long does it take? The
brute force method takes O(q)time to calculate the qth
power of an element. So the total time is O(nq).
Recursive doubling method reduces the time required
to calculate the qth power of an element to O(log q), so
the total time can be reduced to O(nlog q). Kavitha,
[7], presents an O(n)algorithm that determines if two
Abelian groups with nelements each are isomorphic.
Similar research can see, [8] and [9]. The main in-
gredient in this result is an O(|G|)-time algorithm that
finds the orders of all elements in any finite group G
given as input the multiplication table of G. Inspired by
Kavitha’s result, we give a deterministic O(|G|)-time
algorithm that, given the multiplication table of a finite
group (G, ·)and nonzero p,q∈Z, finds all solutions
(if any) to xp=gqfor all g∈G.
Primitive roots are elements of order |G|and have
been extensively studied. See, e.g., [10]. To find the
solutions to xp=gqfor each g∈G, it suffices to do
the following:
(1) Calculate gqfor each g∈G.
(2) Find a primitive root rand calculate r1,r2,. . .,r|G|.
When some rjmatches any value calculated in step
1, a solution for xp=gqis found.
Unlike in our result, however, the above procedure
takes ω(|G|)time.
2 Preliminaries
We refer to some basic definitions in algebra, [11].For
more detail, please see, [12] and [13].
Definition 1. A nonempty set Gendowed with a binary
operation ·,G·G→Gis called a groupoid. An element
e∈Gis an identity if and only if for all x∈G,x·e=
e·x=x. If yhas a unique inverse, it’s denoted y−1.
Definition 2. A groupoid (G, ·)is
•Abelian if x·y=y·xfor all x, y ∈G.
•associative if x·(y·z) = (x·y)·zfor all x, y, z ∈
G.
•a quasigroup if for all x, y ∈G, there are unique
elements a, b ∈Gsuch that x·a=yand b·x=y.
•a loop if (G, ·)is a quasigroup with an identity.
Definition 3. The order of a finite group (G, ·)refers to
the number of elements of G. The order of an element
ain a finite group (G, ·)refers to the least positive in-
teger hwhich satisfies ah=e, where eis the identity
of (G, ·).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.21
Hui-Ting Chen, Ching-Lueh Chang
E-ISSN: 2224-2880
167
Volume 22, 2023
Input: The multiplication table of a group (G, ·)and
q∈Z+
1: Compute g−1for all g∈G;
2: Compute the order of g, denoted order(g), for all
g∈G;
3: for all g∈Gdo
4: ans[g]← ⊥;
5: end for
6: for ℓ= 1,2,. . .,|G|do
7: g←the ℓth element of G;
8: if ans[g] = ⊥then
9: k←min{qmod order(g)}∪{i≥2|
(ans[gi−1]∈G)∧(ans[gi]∈G)};
10: Calculate g,g2,. . .,gk;
11: if k= (qmod order(g)) then
12: ans[g]←gk;
13: else
14: ans[g]←ans[gk]·(ans[gk−1])−1;
15: end if
16: for j= 2,3,. . .,k−1do
17: ans[gj]←ans[gj−1]·ans[g];
18: end for
19: end if
20: end for
Figure 1: Algorithm All Powers outputting gq, stored in
ans[g], for all g∈G
Definition 4. For any finite group (G, ·), we say (H, ·)
is a subgroup of (G, ·)if H⊆Gand for any x, y ∈H,
x·y∈H.
3 Raising powers
To begin with, we check that ans[gk]∈Gand ans[gk−1]∈
Gin line 14 of algorithm All Powers in Fig. 1; hence
line 14 tries neither to invert ⊥nor to multiply a group
element with ⊥.
Lemma 5. In line 14 of All Powers,ans[gk−1]∈Gand
ans[gk]∈G.
Proof. Clearly, k=qin line 14. So line 9 implies the
lemma.
Lemma 6. At any time, ans[a] = aqfor all a∈G
satisfying ans[a]=⊥.
Proof. Assume as induction hypothesis that the lemma
is true up to the (ℓ−1)th iteration of the for loop in
lines 6–20, where ℓ≥1. In the ℓth iteration:
• As gqmod order(q)=gq, line 12 maintains the lemma.
• Upon reaching line 14, ans[gk−1]∈Gand ans[gk]∈
Gby Lemma 5, implying ans[gk−1] = (gk−1)q
and ans[gk]=(gk)qby the induction hypothesis
(note that ans[gk−1]and ans[gk]are not yet modi-
fied in the current iteration). So line 14 calculates
ans[g]as gq.
• Upon reaching Line 17, we must have just run
line 12 or line 14, resulting in ans[g] = gqby the
analyses above. So lines 16–18 calculate ans[gj]
as (gj)qfor all 2≤j≤k−1.
In summary, the lemma remains true after the ℓth itera-
tion.
The base case that ℓ= 0 is trivial because ans[g] =
⊥for all g∈Gbefore the first iteration.
Lemma 7. After running All Powers,ans[g] = gqfor
all g∈G.
Proof. Lines 11–15 and Lemma 5 guarantee ans[g]=
⊥. So the loop in lines 6–20 ends up guaranteeing ans[g]=
⊥for all g∈G. Now apply Lemma 6.
Lemma 8. Each execution of lines 8–19 of All Powers
take O(k)time, where kis as in line 8.
Proof. Run line 9 by calculating gifor an increasing i≥
1until either (1) i=qmod order(g)or (2) ans[gi−1]=
⊥and ans[gi]=⊥. Because gi=gi−1·gfor all i, line 8
takes O(k)time. Similarly, line 9 also takes O(k)time.
Clearly, lines 11–15 and 16–18 take O(1) and O(h)
time, respectively (note that the inverse (ans[gk−1])−1
in line 14 has been found in line 1).
Lemma 9. Each execution of lines 9–18 of All Powers
turn Ω(k)entries of ans[·]from ⊥to non-⊥.
Proof. By the minimality of kin line 9, the sequence
{ans[gj]}k−1
j=1 does not contain two consecutive elements
that are non-⊥(when line 9 is executed). So ⊥appears
for at least ⌊(k−1)/2⌋times in {ans[gj]}k−1
j=1 . But af-
ter lines 11–19, ans[gj]=⊥for all j∈ {1,2, . . . , k −
1}. Note that as k < order(g)by line 9, g1,g2,. . .,
gk−1are distinct. In summary, lines 9–18 turn at least
⌊(k−1)/2⌋distinct entries of ans[·]from ⊥to non-⊥.
Unless k≤2,⌊(k−1)/2⌋= Ω(k). When k≤2, the
lemma still holds because lines 11–15 turn ans[g]from
⊥to non-⊥.
Lemma 10. All Powers take O(|G|)time.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.21
Hui-Ting Chen, Ching-Lueh Chang
E-ISSN: 2224-2880
168
Volume 22, 2023
Proof. Appendix A proves the easy, probably folklore,
result that line 1 takes O(|G|)time. Kavitha [7] gives an
O(|G|)-time algorithm for line 2. Clearly, once an en-
try of ans[·]becomes non-⊥, it remains non-⊥forever.
So by Lemmas 8–9, the running time is at most propor-
tional to the total number of entries of ans[·], which is
|G|.
Lemma 11. Given the multiplication table of a finite
group (G, ·)and a nonzero q∈Z, it takes O(|G|)time
to find gqand all qth roots (if any) of g, for all g∈G.
Proof. There are several cases:
•q≥2: By Lemmas 7 and 10, finding gqfor all
g∈Gtakes O(|G|)time. Create a list Lafor each
a∈G. For each g∈G, put ginto Lgq. Then the
qth roots of each a∈Gare just the elements of
La.
•q= 1: Trivial.
•q < 0: Find g−1for all g∈Gin O(|G|)time,
as in Appendix A. Replace qby −q≥1and each
g∈Gby g−1. Then proceed as if q > 0.
Below is our main result.
Theorem 12. Given the multiplication table of a finite
group (G, ·)and nonzero p,q∈Z, it takes O(|G|)time
to find all solutions (if any) to xp=gqfor all g∈G.
Proof. Use Lemma 11 twice to find gqand all pth roots
(if any) of g, for all g∈G.
4 Conclusion
If we want to find the power of a finite group G given
the multiplication table, we give the optimal algorithm
that takes O(|G|)time to find all solutions (if any) to
xp=gqfor all g∈G. And we use this method to
invert all elements in G.
A Inverting all elements
We begin by verifying that algorithm All Inverses in
Fig. 2 performs only reasonable operations. In partic-
ular, line 12 does not try to multiply a group element
with ⊥.
Lemma 13. In line 12 of All Inverses,inv[gh]∈G.
Proof. By lines 9 and 11, gh= 1 in line 12. So line 7
implies the lemma.
Input: The multiplication table of a group (G, ·)
1: for all g∈Gdo
2: inv[g]← ⊥;
3: end for
4: for ℓ= 1,2,. . .,|G|do
5: g←the ℓth element of G;
6: if inv[g] = ⊥then
7: h←min{i≥1|(gi= 1) ∨(inv[gi]∈G)};
8: Calculate g,g2,. . .,gh;
9: if gh= 1 then
10: inv[g]←gh−1;
11: else
12: inv[g]←gh−1·inv[gh];
13: end if
14: for j= 2,3,. . .,h−1do
15: inv[gj]←inv[gj−1]·inv[g];
16: end for
17: end if
18: end for
Figure 2: Algorithm All Inverses outputting g−1, stored
in inv[g], for all g∈G
Lemma 14. At any time, inv[a] = a−1for all a∈G
satisfying inv[a]=⊥.
Proof. Assume as induction hypothesis that the lemma
is true up to the (ℓ−1)th iteration of the for loop in
lines 4–18, where ℓ≥1. In the ℓth iteration:
• Line 10 clearly maintains the lemma.
• Upon reaching line 12, inv[gh]∈Gby Lemma 13,
implying inv[gh] = (gh)−1by the induction hy-
pothesis. So line 12 calculates inv[g]as g−1.
• Upon reaching Line 15, we must have just run
line 10 or line 12, resulting in inv[g] = g−1by the
analyses above. So lines 14–16 calculate inv[gj]
as (gj)−1for all 2≤j≤h−1.
In summary, the lemma remains true after the ℓth itera-
tion.
The base case that ℓ= 0 is trivial because inv[g] =
⊥for all g∈Gbefore the first iteration.
Lemma 15. After running All Inverses,inv[g] = g−1
for all g∈G.
Proof. Lines 9–13 and Lemma 13 guarantee inv[g]=
⊥. So the loop in lines 4–18 ends up guaranteeing inv[g]=
⊥for all g∈G. Now apply Lemma 14.
Lemma 16. Each execution of lines 7–16 of All Inverses
take O(h)time, where his as in line 7.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.21
Hui-Ting Chen, Ching-Lueh Chang
E-ISSN: 2224-2880
169
Volume 22, 2023
Proof. Run line 7 by calculating gifor an increasing
i≥1until either (1) gi= 1 or (2) inv[gi]=⊥. Because
gi=gi−1·gfor all i, line 7 takes O(h)time. Similarly,
line 8 also takes O(h)time. Clearly, lines 9–13 and 14–
16 take O(1) and O(h)time, respectively.
Lemma 17. Each execution of lines 7–16 of All Inverses
turn Ω(h)entries of inv[·]from ⊥to non-⊥.
Proof. By the minimality of hin line 7, inv[gj] = ⊥
for 1≤j≤h−1(when line 7 is executed). But after
lines 9–16, inv[gj]=⊥for all j∈ {1,2, . . . , h−1}. So
lines 7–16 turn at least h−1entries of inv[·]from ⊥to
non-⊥. Unless h≤1,h−1 = Ω(h). When h≤1, the
lemma still holds because lines 9–13 turn inv[g]from ⊥
to non-⊥.
Lemma 18. All Inverses take O(|G|)time.
Proof. Clearly, once an entry of ans[·]is non-⊥, it re-
mains non-⊥forever. So by Lemmas 16–17, the run-
ning time is at most proportional to the total number of
entries of ans[·], which is |G|.
Lemmas 15 and 18 yield the following.
Theorem 19. Finding g−1for all g∈Gtakes O(|G|)
time.
References
[1] N. Suvorov and N. Kryuchkov, “Examples of some
quasigroups and loops admitting only discrete topol-
ogization,” Siberian Mathematical Journal, vol. 17,
no. 2, pp. 367–369, 1976.
[2] H. Amiri and S. Jafarian Amiri, “Sum of element
orders of maximal subgroups of the symmetric
group,” Communications in Algebra, vol. 40, no. 2,
pp. 770–778, 2012.
[3] H. Amiri and S. Jafarian Amiri, “Sum of element
orders on finite groups of the same order,” Jour-
nal of Algebra and its Applications, vol. 10, no. 02,
pp. 187–190, 2011.
[4] Y. Marefat, A. Iranmanesh, and A. Tehranian, “On
the sum of element orders of finite simple groups,”
Journal of Algebra and its Applications, vol. 12,
no. 07, p. 1 350 026, 2013.
[5] M. Tărnăuceanu and D. G. Fodor, “On the sum
of element orders of finite abelian groups,” arXiv
preprint arXiv:1805.11693, 2018.
[6] M. Jahani, Y. Marefat, H. Refaghat, and B. Vak-
ili Fasaghandisi, “The minimum sum of element
orders of finite groups,” International Journal of
Group Theory, vol. 10, no. 2, pp. 55–60, 2021.
[7] T.Kavitha, “Linear time algorithms for Abelian
group isomorphism and related problems,” Jour-
nal of Computer and System Sciences, vol. 73,
no. 6, pp. 986–996, 2007.
[8] C. D. Savage, An O(n2)algorithm for abelian
group isomorphism. Computer Studies [Program],
North Carolina State University, 1980.
[9] N. Vikas, “An o(n) algorithm for abelianp-group
isomorphism and an o(nlogn) algorithm for abelian
group isomorphism,” journal of computer and sys-
tem sciences, vol. 53, no. 1, pp. 1–9, 1996.
[10] V. Edemsky and W. CHENHUANG, “On the lin-
ear complexity of binary sequences derived from
generalized cyclotomic classes modulo (2n)(pm),”
WSEAS Transactions on Mathematics, vol. 18,
pp. 197–202, 2019.
[11] D. S. Dummit and R. M. Foote, Abstract alge-
bra. Prentice Hall Englewood Cliffs, NJ, 1991,
vol. 1999.
[12] M. Hall, The theory of groups. Courier Dover Pub-
lications, 2018.
[13] I. N. Herstein, Topics in algebra. John Wiley &
Sons, 2006.
Contribution of individual authors to
the creation of a scientific article
(ghostwriting policy)
Author Contributions:
Ching-Lueh Chang carried out the conceptualization and
is the supervisor.
Hui-Ting Chen did the data curation and has writing and
editing.
Sources of funding for research
presented in a scientific article or
scientific article itself
This work was Supported in part by the Ministry of
Science and Technology of Taiwan under grant 111-
2221-E-155-035-MY2.
Creative Commons Attribution License
4.0 (Attribution 4.0 International , CC
BY 4.0)
This article is published under the terms of the Creative
Commons Attribution License 4.0
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.21
Hui-Ting Chen, Ching-Lueh Chang
E-ISSN: 2224-2880
170
Volume 22, 2023
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
