Premium
A Poisson * Negative Binomial Convolution Law for Random Polynomials over Finite Fields
Author(s) -
Hwang HsienKuei
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199808)13:1<17::aid-rsa2>3.0.co;2-v
Subject(s) - mathematics , monic polynomial , poisson distribution , polynomial , convolution (computer science) , distribution (mathematics) , hypergeometric distribution , combinatorics , asymptotic distribution , binomial (polynomial) , factorization , discrete mathematics , pure mathematics , mathematical analysis , statistics , algorithm , machine learning , estimator , artificial neural network , computer science
Let F q [ X ] denote a polynomial ring over a finite field F q with q elements. Let n be the set of monic polynomials over F q of degree n . Assuming that each of the q n possible monic polynomials in n is equally likely, we give a complete characterization of the limiting behavior of P (Ω n = m ) as n →∞ by a uniform asymptotic formula valid for m ≥1 and n − m →∞, where Ω n represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in n . The distribution of Ω n is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q −1 . Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P (Ω n = m ) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Rényi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17–47, 1998