On explicit factors of cyclotomic polynomials over finite fields

We study the explicit factorization of 2 ⁿ r-th cyclotomic polynomials over finite field \mathbbF_q{\mathbb{F}_q} where q, r are odd with (r, q) = 1. We show that all irreducible factors of 2 ⁿ r-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of 2 ⁿ 5-th cyclotomic polynomials over finite fields and construct several classes of irreducible polynomials of degree 2 ^n–2 with fewer than 5 terms.     

A Poisson * Negative Binomial Convolution Law for Random Polynomials over Finite Fields

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ⁿ 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⁻¹. 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     

On Value Sets of Polynomials over a Finite Field

We study value sets of polynomials over a finite field, and value sets associated to pairs of such polynomials. For example, we show that the value sets (counting multiplicities) of two polynomials of degree at mostdare identical or have at mostq−(q−1)/dvalues in common whereqis the number of elements in the finite field. This generalizes a theorem of D. Wan concerning the size of a single value set. We generalize our result to pairs of value sets obtained by restricting the domain to certain subsets of the field. These results are preceded by results concerning symmetric expressions (of low degree) of the value set of a polynomial. K. S. Williams, D. Wan, and others have considered such expressions in the context of symmetric polynomials, but we consider (multivariable) polynomials invariant under certain important subgroups of the full symmetry group.     

Groups Satisfying the Two-Prime Hypothesis with a Composition Factor Isomorphic to PSL<Subscript>2</Subscript>(<Emphasis Type="Italic">q</Emphasis>) for <Emphasis Type="Italic">q</Emphasis> ⩾ 7

Let G be a finite group and write cd(G) for the degree set of the complex irreducible characters of G. The group G is said to satisfy the two-prime hypothesis if for any distinct degrees a, b 2 cd(G), the total number of (not necessarily different) primes of the greatest common divisor gcd(a, b) is at most 2. We prove an upper bound on the number of irreducible character degrees of a nonsolvable group that has a composition factor isomorphic to PSL₂(q) for q ? 7.     

On the Distribution of the Degrees of Prime Element Factors in Additive Arithmetical Semigroups

 Results of Arnold Knopfmacher about the distribution of the degrees of irreducible factors in the canonical decomposition of monic polynomials in ? _q [X] are generalized to additive arithmetical semigroups (G,∂) satisfying a weak condition called axiom ?     

Uniqueness and zeros of <Emphasis Type="Italic">q</Emphasis>-shift difference polynomials

In this paper, we consider the zero distributions of q-shift difference polynomials of meromorphic functions with zero order, and obtain two theorems that extend the classical Hayman results on the zeros of differential polynomials to q-shift difference polynomials. We also investigate the uniqueness problem of q-shift difference polynomials that share a common value.     

Enumeration of inequivalent irreducible Goppa codes

We consider irreducible Goppa codes over F_q of length qⁿ defined by polynomials of degree r, where q is a prime power and n,r are arbitrary positive integers. We obtain an upper bound on the number of such codes.     

On the Distribution of the Degrees of Prime Element Factors in Additive Arithmetical Semigroups

 Results of Arnold Knopfmacher about the distribution of the degrees of irreducible factors in the canonical decomposition of monic polynomials in ? _q [X] are generalized to additive arithmetical semigroups (G,∂) satisfying a weak condition called axiom ? (Received 25 August 1998; in revised form 7 June 1999)     

Counting the number of distinct real roots of certain polynomials by Bezoutian and the Galois groups over the rational number field

In this article, we count the number of distinct real roots of certain polynomials in terms of Bezoutian form. As an application, we construct certain irreducible polynomials over the rational number field which have given number of real roots and by the result of Oz Ben-Shimol [On Galois groups of prime degree polynomials with complex roots, Algebra Disc. Math. 2 (2009), pp. 99–107], we obtain an algorithm to construct irreducible polynomials of prime degree p whose Galois groups are isomorphic to S _p or A _p .     

Isomorphism criterion for monomial graphs

Let q be a prime power, ??_q be the field of q elements, and k, m be positive integers. A bipartite graph G = G_q(k, m) is defined as follows. The vertex set of G is a union of two copies P and L of two‐dimensional vector spaces over ??_q, with two vertices (p₁, p₂) ∈ P and [ l₁, l₂] ∈ L being adjacent if and only if p₂ + l₂ = pl. We prove that graphs G_q(k, m) and G_q′(k′, m′) are isomorphic if and only if q = q′ and {gcd (k, q ? 1), gcd (m, q ? 1)} = {gcd (k′, q ? 1),gcd (m′, q ? 1)} as multisets. The proof is based on counting the number of complete bipartite INFgraphs in the graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 322–328, 2005     

Total variation asymptotics for independent process approximations of logarithmic multisets and selections

Many natural unlabeled combinatorial structures, such as random partitions of the integer n, or random monic polynomials over a finite field of degree n, or unlabeled mapping patterns on n points may be described as multisets. In the usual statistical language, a multiset is an unordered sample in which number of items is variable, but the sum is a fixed value n. For these structures, the process counting the number of components of various sizes is equal in distribution to a process of independent, but not identically distributed random variables, conditioned on the value of a weighted sum. By restricting to the first b coordinates, it is possible to compare the combinatorial process directly to the independent process, and to estimate the total variation distance d_b(n) between these distributions. For a broad class of examples similar to the Ewens sampling formula we give asymptotics for d_b(n) which are valid for b=o(n/log n). The polynomial and random mapping pattern examples are covered by this result, but not the example of partitions. Similar results for selections, which are multisets with no repeated parts, such as square free polynomials, are also derived. The proofs of these results use large deviations bounds and singularity analysis of generating functions. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 51–80, 1997     

The Number of Permutation Polynomials of a Given Degree Over a Finite Field

We relate the number of permutation polynomials in F_q[x] of degree d≤q−2 to the solutions (x₁,x₂,…,x_q) of a system of linear equations over F_q, with the added restriction that x_i≠0 and x_i≠x_j whenever i≠j. Using this we find an expression for the number of permutation polynomials of degree p−2 in F_p[x] in terms of the permanent of a Vandermonde matrix whose entries are the primitive pth roots of unity. This leads to nontrivial bounds for the number of such permutation polynomials. We provide numerical examples to illustrate our method and indicate how our results can be generalised to polynomials of other degrees.     

Necklaces,symmetries and self-reciprocal polynomials

The connection between a certain class of necklaces and self-reciprocal polynomials over finite fields is shown. For n?2, self-reciprocal polynomials of degree 2n arising from monic irreducible polynomials of degree n are shown to be either irreducible or the product or two irreducible factors which are necessarily reciprocal polynomials. Using DeBruijn's method we count the number of necklaces in this class and hence obtain a formula for the number of irreducible self-reciprocal polynomials showing that they exist for every even degree. Thus every extension of a finite field of even degree can be obtained by adjoining a root of an irreducible self-reciprocal polynomial.     

The Distribution of Reciprocal Pairs Modulo Polynomials over a Finite Field

Given a finite field F_q of order q, a fixed polynomial g in –F_q[X] of positive degree, and two elements u and v in the ring of polynomials in R = F_q [X]/gF_q[X], the question arises: How many pairs (a, 6) are there in R × R so that ab ? 1 mod g and so that a is close to u while b is close to v ? The answer is, about as many as one would expect. That is, there are no favored regions in R × R where inverse pairs cluster. The error term is quite sharp in most cases, being comparable to what would happen with random distribution of pairs. The proof uses Kloosterman sums and counting arguments. The exceptional cases involve fields of characteristic 2 and composite values of g. Even then the error term obtained is nontrivial. There is no computational evidence that inverses are in fact less evenly distributed in this case, however.     

Recurrent Methods for Constructing Irreducible Polynomials over GF(2s)

The paper is devoted to some results concerning the constructive theory of the synthesis of irreducible polynomials over Galois fields GF(q), q=2^s. New methods for the construction of irreducible polynomials of higher degree over GF(q) from a given one are worked out. The complexity of calculations does not exceed O(n³) single operations, where n denotes the degree of the given irreducible polynomial. Furthermore, a recurrent method for constructing irreducible (including self-reciprocal) polynomials over finite fields of even characteristic is proposed.     

On the reducibility of some composite polynomials over finite fields

Let g(x)?=?x ⁿ ?+?a _n-1 x ^n-1?+?. . .?+?a ₀ be an irreducible polynomial over ${\mathbb{F}_q}$ . Varshamov proved that for a?=?1 the composite polynomial g(x ^p ?ax?b) is irreducible over ${\mathbb{F}_q}$ if and only if ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})\neq 0}$ . In this paper, we explicitly determine the factorization of the composite polynomial for the case a?=?1 and ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})= 0}$ and for the case a?≠ 0, 1. A recursive construction of irreducible polynomials basing on this composition and a construction with the form ${g(x^{r^kp}-x^{r^k})}$ are also presented. Moreover, Cohen’s method of composing irreducible polynomials and linear fractions are considered, and we show a large number of irreducible polynomials can be obtained from a given irreducible polynomial of degree n provided that gcd(n, q ³ ? q)?=?1.     

The two-prime hypothesis: groups whose nonabelian composition factors are not isomorphic to $${{\mathrm{PSL}}}_2(q)$$

Let G be a finite group, and write \({\mathrm {cd}}(G)\) for the degree set of the complex irreducible characters of G. The group G is said to satisfy the two-prime hypothesis if, for any distinct degrees \(a, b \in {\mathrm {cd}}(G)\), the total number of (not necessarily different) primes of the greatest common divisor \(\gcd (a, b)\) is at most 2. In this paper, we give an upper bound on the number of irreducible character degrees of nonsolvable groups satisfying the two-prime hypothesis and without composition factors isomorphic to \({{\mathrm{PSL}}}_2(q)\) for any prime power q.     

The parity of the number of irreducible factors for some pentanomials

It is well known that the Stickelberger–Swan theorem is very important for determining the reducibility of polynomials over a binary field. Using this theorem the parity of the number of irreducible factors for some kinds of polynomials over a binary field, for instance, trinomials, tetranomials, self-reciprocal polynomials and so on was determined. We discuss this problem for Type II pentanomials, namely x^m+xⁿ⁺²+xⁿ⁺¹+xⁿ+1F₂[x] for even m. Such pentanomials can be used for the efficient implementation of multiplication in finite fields of characteristic two. Based on the computation of the discriminant of these pentanomials with integer coefficients, we will characterize the parity of the number of irreducible factors over F₂ and establish necessary conditions for the existence of this kind of irreducible pentanomials.Our results have been obtained in an experimental way by computing a significant number of values with Mathematica and extracting the relevant properties.     

The Clebsch-Gordan coefficients for the quantum group SμU(2) and q-Hahn polynomials

The tensor product of two unitary irreducible representations of the quantum group S_μU(2) is decomposed in a direct sum of unitary irreducible representations with explicit realizations. The Clebsch-Gordan coefficients yield the orthogonality relations for q-Hahn and dual q-Hahn polynomials.