Large Galois groups with applications to Zariski density
Large Galois groups with applications to Zariski density
复制标题
大型伽罗瓦群及其在 Zariski 密度中的应用
DOI：
10.2140/gt.2011.15.1
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Igor Rivin
中科院分区：
文献类型：
--
作者：
Igor Rivin
我们引入了第一个可证明的有效算法来检验在有理数上的几乎简单半简单群的有限生成子群是否为Zariski-dense。我们将这个问题简化为计算伽罗瓦群之一，为此，我们描述了有效的算法来检查具有整数系数的多项式$p$的伽罗瓦群是否“泛型”（对于任意次多项式$n$意味着完全对称群$S_n,$，而对于次多项式$2n$意味着高八面体群$C_2 \wr S_n.$）。我们给出了有效的算法来验证多项式是否具有伽罗瓦群$S_n,$和倒多项式是否具有伽罗瓦群$C_2 \wr S_n.$。我们展示了这些算法如何给出有效的算法来检查$\mathop{SL}(n, \mathbb{Z})$或$\mathop{Sp}(2n, \mathbb{Z})$中的一组矩阵$\mathcal{G}$是否生成\emph{Zariski密集}子群。 在$\mathop{SL}(n, \mathbb{Z})$中这样做的
复杂性为$O(n^4 \log n \log \|\mathcal{G}\|)\log \epsilon$阶，在$\mathop{Sp}(2n, \mathbb{Z})$中复杂性为$O(n^8 \log n\log \|\mathcal{G}\|)\log \epsilon$阶。在一般的半简单群中，我们表明Zariski密度可以在$O(n^14 \log \|\mathcal{G}\|\log \epsilon),$阶的时间内得到确认或否认，其中$\epsilon$是错误“NO”答案的概率，而$\|\mathcal{G}\|$是输入复杂性的度量（生成矩阵的Frobenius范数的最大值）。这些算法在代数数域和其他半简单群上基本上不需要改变就可以工作。但是，为了清楚起见，我们将其限制在特殊的线性群和辛群以及有理系数的情况下。
We introduce the first provably efficient algorithm to check if a finitely generated subgroup of an almost simple semi-simple group over the rationals is Zariski-dense. We reduce this question to one of computing Galois groups, and to this end we describe efficient algorithms to check if the Galois group of a polynomial $p$ with integer coefficients is "generic" (which, for arbitrary polynomials of degree $n$ means the full symmetric group $S_n,$ while for reciprocal polynomials of degree $2n$ it means the hyperoctahedral group $C_2 \wr S_n.$). We give efficient algorithms to verify that a polynomial has Galois group $S_n,$ and that a reciprocal polynomial has Galois group $C_2 \wr S_n.$ We show how these algorithms give efficient algorithms to check if a set of matrices $\mathcal{G}$ in $\mathop{SL}(n, \mathbb{Z})$ or $\mathop{Sp}(2n, \mathbb{Z})$ generate a \emph{Zariski dense} subgroup.
The complexity of doing this in$\mathop{SL}(n, \mathbb{Z})$ is of order $O(n^4 \log n \log \|\mathcal{G}\|)\log \epsilon$ and in $\mathop{Sp}(2n, \mathbb{Z})$ the complexity is of order $O(n^8 \log n\log \|\mathcal{G}\|)\log \epsilon$ In general semisimple groups we show that Zariski density can be confirmed or denied in time of order $O(n^14 \log \|\mathcal{G}\|\log \epsilon),$ where $\epsilon$ is the probability of a wrong "NO" answer, while $\|\mathcal{G}\|$ is the measure of complexity of the input (the maximum of the Frobenius norms of the generating matrices). The algorithms work essentially without change over algebraic number fields, and in other semi-simple groups. However, we restrict to the case of the special linear and symplectic groups and rational coefficients in the interest of clarity.