PreprintCC BY 4.0arXiv
On the maximum relational complexity of affine groups
Abstract
Let G be a group of permutations of a set Ω. The relational complexity RC(G) is the least integer r≥ 2 such that the G-orbit of every finite tuple is determined by the G-orbits of its r-subtuples; there is currently only a small collection of groups G for which RC(G) is known precisely. In this paper we study the relational complexity of finite affine groups acting naturally on a d-dimensional vector space over 𝔽q. We prove that every such group has relational complexity at most d+2 when q>2 and at most d+1 when q=2; we produce a complete classification of the primitive such groups for which these bounds are attained.
Related
BibTeX
@misc{valle2026maximum,
title = {{On the maximum relational complexity of affine groups}},
author = {Coen del Valle and Nick Gill and Pablo Spiga},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20077},
eprint = {2610.20077},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20077},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the maximum relational complexity of affine groups
AU - Coen del Valle
AU - Nick Gill
AU - Pablo Spiga
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20077
UR - https://arxiv.org/abs/2610.20077
AB - Let G be a group of permutations of a set Ω. The relational complexity RC(G) is the least integer r≥ 2 such that the G-orbit of every finite tuple is determined by the G-orbits of its r-subtuples; there is currently only a small collection of groups G for which RC(G) is known precisely. In this paper we study the relational complexity of finite affine groups acting naturally on a d-dimensional vector space over 𝔽_q. We prove that every such group has relational complexity at most d+2 when q>2 and at most d+1 when q=2; we produce a complete classification of the primitive such groups for which these bounds are attained.
ER -