On random polynomials over finite fields
On random polynomials over finite fields
复制标题
DOI：
10.1017/s0305004100071620
复制
发表时间：
1993-09
影响因子：
0.8
通讯作者：
R. Arratia;A. Barbour;S. Tavaré
中科院分区：
文献类型：
--
作者：
R. Arratia;A. Barbour;S. Tavaré
摘要我们考虑q元有限域上的n次随机一元多项式，选择所有qn种可能性相等，分解为一元不可约因子。更一般地说，放松限制，q是一个素数的权力，我们认为，多集建设的可能性的总数量的重量n是qn。我们建立了各种近似的联合分布的因素，通过给上界的总变异距离更简单的离散分布。例如，特定因子的计数近似独立且呈几何分布，所有大小为1，2，.，B（其中B = O（n/log n））的因子的计数近似为独立负二项随机变量。作为另一示例，大因子的联合分布接近于随机排列中的大循环的联合分布。我们展示了这些离散近似如何隐含布朗运动泛函中心极限定理和Poisson-Dirichiet极限定理，以及适当的误差估计。我们还给出了泊松近似，误差界，为分布的因素的总数。
Abstract We consider random monic polynomials of degree n over a finite field of q elements, chosen with all qn possibilities equally likely, factored into monic irreducible factors. More generally, relaxing the restriction that q be a prime power, we consider that multiset construction in which the total number of possibilities of weight n is qn. We establish various approximations for the joint distribution of factors, by giving upper bounds on the total variation distance to simpler discrete distributions. For example, the counts for particular factors are approximately independent and geometrically distributed, and the counts for all factors of sizes 1, 2, …, b, where b = O(n/log n), are approximated by independent negative binomial random variables. As another example, the joint distribution of the large factors is close to the joint distribution of the large cycles in a random permutation. We show how these discrete approximations imply a Brownian motion functional central limit theorem and a Poisson-Dirichiet limit theorem, together with appropriate error estimates. We also give Poisson approximations, with error bounds, for the distribution of the total number of factors.