Base Sizes and Regular Orbits for Coprime Affine Permutation Groups
Base Sizes and Regular Orbits for Coprime Affine Permutation Groups
复制标题
互质仿射排列群的基尺寸和规则轨道
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
K. Magaard
中科院分区：
文献类型：
--
作者：
D. Gluck;K. Magaard
设G是有限集合Ω上的置换群.Ω中的点列B=（ω1，...，ωB）称为基，如果它在G中的点态稳定子是单位元。基在置换群的计算算法中具有重要意义。对于非冗余基B，初等不等式2 <$B <$$><$G <$B <$成立;特别是<$B <$log <$G <$<$/log <$Ω <$<$。在G在Ω上是本原的情况下，Pyber [8，p. 207]已经证明，对于某个（大的）泛常数C，最小基尺寸小于Clog <$G <$/log <$Ω <$。
Let G be a permutation group on a finite set Ω. A sequence B=(ω1, …, ωb) of points in Ω is called a base if its pointwise stabilizer in G is the identity. Bases are of fundamental importance in computational algorithms for permutation groups. For both practical and theoretical reasons, one is interested in the minimal base size for (G, Ω), For a nonredundant base B, the elementary inequality 2∣B∣⩽∣G∣⩽∣Ω∣∣B∣ holds; in particular, ∣B∣⩾log∣G∣/log∣Ω∣. In the case when G is primitive on Ω, Pyber [8, p. 207] has conjectured that the minimal base size is less than Clog∣G∣/log∣Ω∣ for some (large) universal constant C.