On relational complexity and base size of finite primitive groups

Veronica Kelsey; Colva Mary Roney-Dougal

doi:10.2140/pjm.2022.318.89

On relational complexity and base size of finite primitive groups

Veronica Kelsey^*, Colva Mary Roney-Dougal

^*Corresponding author for this work

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

Abstract

In this paper we show that if G is a primitive subgroup of S_n that is not large base, then any irredundant base for G has size at most 5 log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and is best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5 log n+1, and the maximal size of a minimal base and the height are both at most 5 log n. Furthermore, we deduce that a base for G of size at most 5 log n can be computed in polynomial time.

Original language	English
Pages (from-to)	89–108
Journal	Pacific Journal of Mathematics
Volume	318
Issue number	1
DOIs	https://doi.org/10.2140/pjm.2022.318.89
Publication status	Published - 1 Aug 2022

Keywords

Permutation group
Base size
Relational complexity
Computational complexity

Access to Document

10.2140/pjm.2022.318.89

Kelsey-2022-On-relational-complexity-PJM-v318-n1-p05-p
Copyright © 2022 Mathematical Sciences Publishers. 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 final published version of the work, which was originally published at https://doi.org/10.2140/pjm.2022.318.89.
Final published version, 374 KB

Cite this

@article{f533ebe0c47346f9bdb52ff149da25b5,

title = "On relational complexity and base size of finite primitive groups",

abstract = "In this paper we show that if G is a primitive subgroup of Sn that is not large base, then any irredundant base for G has size at most 5 log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and is best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5 log n+1, and the maximal size of a minimal base and the height are both at most 5 log n. Furthermore, we deduce that a base for G of size at most 5 log n can be computed in polynomial time.",

keywords = "Permutation group, Base size, Relational complexity, Computational complexity",

author = "Veronica Kelsey and Roney-Dougal, {Colva Mary}",

year = "2022",

month = aug,

day = "1",

doi = "10.2140/pjm.2022.318.89",

language = "English",

volume = "318",

pages = "89–108",

journal = "Pacific Journal of Mathematics",

issn = "0030-8730",

publisher = "University of California, Berkeley",

number = "1",

}

TY - JOUR

T1 - On relational complexity and base size of finite primitive groups

AU - Kelsey, Veronica

AU - Roney-Dougal, Colva Mary

PY - 2022/8/1

Y1 - 2022/8/1

N2 - In this paper we show that if G is a primitive subgroup of Sn that is not large base, then any irredundant base for G has size at most 5 log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and is best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5 log n+1, and the maximal size of a minimal base and the height are both at most 5 log n. Furthermore, we deduce that a base for G of size at most 5 log n can be computed in polynomial time.

AB - In this paper we show that if G is a primitive subgroup of Sn that is not large base, then any irredundant base for G has size at most 5 log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and is best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5 log n+1, and the maximal size of a minimal base and the height are both at most 5 log n. Furthermore, we deduce that a base for G of size at most 5 log n can be computed in polynomial time.

KW - Permutation group

KW - Base size

KW - Relational complexity

KW - Computational complexity

U2 - 10.2140/pjm.2022.318.89

DO - 10.2140/pjm.2022.318.89

M3 - Article

SN - 0030-8730

VL - 318

SP - 89

EP - 108

JO - Pacific Journal of Mathematics

JF - Pacific Journal of Mathematics

IS - 1

ER -

On relational complexity and base size of finite primitive groups

Abstract

Keywords

Access to Document

Fingerprint

Cite this