论文标题
有限组的空间有效表示
Space Efficient Representations of Finite Groups
论文作者
论文摘要
组的Cayley表表示使用$ \ Mathcal {o}（n^2）$单词$单词$ n $，并及时回答乘法查询$ \ MATHCAL {O}（O}（1）$。询问是否有一个$ o（n^2）$空间表示的组的$ \ mathcal {o}（1）$查询时间很有趣。我们表明，对于任何$δ$，$ \ frac {1} {\ log n} \leδ\ le 1 $，有一个$ \ nathcal {o}（\ frac {n^{1 +δ{1 +δ}}Δ）$ n $ n $ n $ n $ n $ n $ \ n $的$ \ mathcal pime}的$ n $ ntime $ ntime的$ n $} $ query}; 我们还表明，对于z组，简单组和几个按半程产品定义的组类，有线性空间表示，最多可对数查询时间。 Farzan和Munro（ISSAC'06）定义了一个组表示模型，并为具有持续查询时间的Abelian团体提供了简洁的数据结构。他们询问他们的结果是否可以扩展到较大的小组类。我们在其模型中为哈密顿群体和其他一些具有持续查询时间的组构建数据结构。
The Cayley table representation of a group uses $\mathcal{O}(n^2)$ words for a group of order $n$ and answers multiplication queries in time $\mathcal{O}(1)$. It is interesting to ask if there is a $o(n^2)$ space representation of groups that still has $\mathcal{O}(1)$ query-time. We show that for any $δ$, $\frac{1}{\log n} \le δ\le 1$, there is an $\mathcal{O}(\frac{n^{1 +δ}}δ)$ space representation for groups of order $n$ with $\mathcal{O}(\frac{1}δ)$ query-time. We also show that for Z-groups, simple groups and several group classes defined in terms of semidirect product, there are linear space representations with at most logarithmic query-time. Farzan and Munro (ISSAC'06) defined a model for group representation and gave a succinct data structure for abelian groups with constant query-time. They asked if their result can be extended to categorically larger group classes. We construct data structures in their model for Hamiltonian groups and some other classes of groups with constant query-time.
