Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T09:07:26.639Z Has data issue: false hasContentIssue false

On random polynomials over finite fields

Published online by Cambridge University Press:  24 October 2008

Richard Arratia
Affiliation:
Department of Mathematics, University of Southern California, Los Angeles, CA 90089-1113, U.S.A.
A. D. Barbour
Affiliation:
Institut für Angewandte Mathematik, Universität Zurich, Rämistrasse 74, CH-8001 Zurich, Switzerland
Simon Tavaré
Affiliation:
Department of Mathematics, University of Southern California, Los Angeles, CA 90089-1113, U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1993