Disjoint direct product decompositions of permutation groups

Mun See Chang; Christopher Anthony Jefferson

doi:10.1016/j.jsc.2021.04.003

Disjoint direct product decompositions of permutation groups

Mun See Chang^*, Christopher Anthony Jefferson

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

9 Downloads (Pure)

Abstract

Let H ≤ S_n be an intransitive group with orbits Ω₁, Ω₂, ... , Ω_k. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω₁ x H|Ω₂ x ... x H|Ω_k. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Π_c∈P H|_c and we demonstrate its usefulness in some applications.

Original language	English
Pages (from-to)	1-16
Journal	Journal of Symbolic Computation
Volume	108
Early online date	29 Apr 2021
DOIs	https://doi.org/10.1016/j.jsc.2021.04.003
Publication status	Published - Jan 2022

Keywords

Permutation group
Computation
Direct product
Subdirect product
Decomposition
Computer algebra system

Access to Document

10.1016/j.jsc.2021.04.003

DDFD-Pure
Copyright © 2021 Elsevier Ltd. All rights reserved. This work has been made available online in accordance with publisher policies or with permission. Permission for further reuse of this content should be sought from the publisher or the rights holder. This is the author created accepted manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1016/j.jsc.2021.04.003.
Accepted author manuscript, 220 KBLicence: CC BY-NC-ND

RS Research Fellowship Renewal: RS Research Fellowship Renewal
Jefferson, C. A. (PI)
The Royal Society
1/10/18 → 31/03/22
Project: Fellowship

Cite this

@article{7d66cd3682b8478d899541425f750ab1,

title = "Disjoint direct product decompositions of permutation groups",

abstract = "Let H ≤ Sn be an intransitive group with orbits Ω1, Ω2, ... , Ωk. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω1 x H|Ω2 x ... x H|Ωk. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Πc∈P H|c and we demonstrate its usefulness in some applications.",

keywords = "Permutation group, Computation, Direct product, Subdirect product, Decomposition, Computer algebra system",

author = "Chang, {Mun See} and Jefferson, {Christopher Anthony}",

note = "Funding: The first author is supported by an Engineering and Physical Sciences Research Council grant (EP/P015638/1). The second author is supported by a Royal Society University Research Fellowship (URF\R\180015).",

year = "2022",

month = jan,

doi = "10.1016/j.jsc.2021.04.003",

language = "English",

volume = "108",

pages = "1--16",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - Disjoint direct product decompositions of permutation groups

AU - Chang, Mun See

AU - Jefferson, Christopher Anthony

N1 - Funding: The first author is supported by an Engineering and Physical Sciences Research Council grant (EP/P015638/1). The second author is supported by a Royal Society University Research Fellowship (URF\R\180015).

PY - 2022/1

Y1 - 2022/1

N2 - Let H ≤ Sn be an intransitive group with orbits Ω1, Ω2, ... , Ωk. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω1 x H|Ω2 x ... x H|Ωk. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Πc∈P H|c and we demonstrate its usefulness in some applications.

AB - Let H ≤ Sn be an intransitive group with orbits Ω1, Ω2, ... , Ωk. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω1 x H|Ω2 x ... x H|Ωk. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Πc∈P H|c and we demonstrate its usefulness in some applications.

KW - Permutation group

KW - Computation

KW - Direct product

KW - Subdirect product

KW - Decomposition

KW - Computer algebra system

U2 - 10.1016/j.jsc.2021.04.003

DO - 10.1016/j.jsc.2021.04.003

M3 - Article

SN - 0747-7171

VL - 108

SP - 1

EP - 16

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

ER -

Disjoint direct product decompositions of permutation groups

Abstract

Keywords

Access to Document

Fingerprint

Projects

RS Research Fellowship Renewal: RS Research Fellowship Renewal

Cite this