An extension of a result of Zaharescu on irreducible polynomials

It is well known that if f(x) is a monic irreducible polynomial of degree d with coefficients in a complete valued field (K, ‖), then any monic polynomial of degree d over K which is sufficiently close to f(x) with respect to ‖ is also irreducible over K. In 2004, Zaharescu proved a similar result applicable to separable, irreducible polynomials over valued fields which are not necessarily complete. In this paper, the authors extend Zaharescu’s result to all irreducible polynomials without assuming separability.     

Hyperelliptic jacobians with real multiplication

Let K be a field of characteristic p≠2, and let f(x) be a sextic polynomial irreducible over K with no repeated roots, whose Galois group is isomorphic to A₅. If the jacobian J(C) of the hyperelliptic curve C:y²=f(x) admits real multiplication over the ground field from an order of a real quadratic field D, then either its endomorphism algebra is isomorphic to D, or p>0 and J(C) is a supersingular abelian variety. The supersingular outcome cannot occur when p splits in D.     

Polynomials and primitive roots in finite fields

The primitive elements of a finite field are those elements of the field that generate the multiplicative group of k. If f(x) is a polynomial over k of small degree compared to the size of k, then f(x) represents at least one primitive element of k. Also f(x) represents an lth power at a primitive element of k, if l is also small. As a consequence of this, the following results holds.Theorem. Let g(x) be a square-free polynomial with integer coefficients. For all but finitely many prime numbers p, there is an integer a such that g(a) is equivalent to a primitive element modulo p.Theorem. Let l be a fixed prime number and f(x) be a square-free polynomial with integer coefficients with a non-zero constant term. For all but finitely many primes p, there exist integers a and b such that a is a primitive element and f(a) ≡ b¹ modulo p.     

On the irreducibility of a class of polynomials,III

This work is a continuation and extension of our earlier articles on irreducible polynomials. We investigate the irreducibility of polynomials of the form g(f(x)) over an arbitrary but fixed totally real algebraic number field $\text{L}$, where g(x) and f(x) are monic polynomials with integer coefficients in $\text{L}$, g is irreducible over $\text{L}$ and its splitting field is a totally imaginary quadratic extension of a totally real number field. A consequence of our main result is as follows. If g is fixed then, apart from certain exceptions f of bounded degree, g(f(x)) is irreducible over $\text{L}$ for all f having distinct roots in a given totally real number field.     

Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals

This paper studies the representation of a positive polynomial f(x) on a noncompact semialgebraic set S={x∈Rⁿ:g₁(x)≥0,…,g_s(x)≥0} modulo its KKT (Karush-Kuhn-Tucker) ideal. Under the assumption that the minimum value of f(x) on S is attained at some KKT point, we show that f(x) can be represented as sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)>0 on S; furthermore, when the KKT ideal is radical, we argue that f(x) can be represented as a sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)≥0 on S. This is a generalization of results in [J. Nie, J. Demmel, B. Sturmfels, Minimizing polynomials via sum of squares over the gradient ideal, Mathematical Programming (in press)], which discusses the SOS representations of nonnegative polynomials over gradient ideals.     

Integer Polynomials with Roots mod p for all Primes p

Let f(X) be an integer polynomial which is a product of two irreducible factors. Assume that f(X) has a root mod p for all primes p. If the splitting field of f(X) over the rationals is a cyclic extension of the stem fields, then the Galois group of f(X) over the rationals is soluble and of bounded Fitting length. Moreover, the fixed groups of the stem extensions are in, some sense, unique.     

Spectrally arbitrary ray patterns

An n×n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a matrix in the pattern class of A such that its characteristic polynomial is f(x). In this article the authors extend the nilpotent-Jacobi method for sign patterns to ray patterns, establishing a means to show that an irreducible ray pattern and all its superpatterns are spectrally arbitrary. They use this method to establish that a particular family of n×n irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. They then show that every n×n irreducible, spectrally arbitrary ray pattern has at least 3n-1 nonzeros.     

A New Computational Approach to Ideal Theory in Number Fields

Let K be the number field determined by a monic irreducible polynomial f(x) with integer coefficients. In previous papers we parameterized the prime ideals of K in terms of certain invariants attached to Newton polygons of higher order of f(x). In this paper we show how to carry out the basic operations on fractional ideals of K in terms of these constructive representations of the prime ideals. From a computational perspective, these results facilitate the manipulation of fractional ideals of K avoiding two heavy tasks: the construction of the maximal order of K and the factorization of the discriminant of f(x). The main computational ingredient is the Montes algorithm, which is an extremely fast procedure to construct the prime ideals.     

Reducibility of polynomials a0(x) + a1 (x)y + a2 (x) y2 modulo p

Let f=a₀(x)+a₁(x)y+a₂(x)y² ? \Bbb Z[x,y]f=a_0(x)+a_1(x)y+a_2(x)y^2\in {\Bbb Z}[x,y] be an absolutely irreducible polynomial of degree m in x. We show that the reduction f mod p will also be absolutely irreducible if p 3 c_m·H(f)^e_mp\ge c_m\cdot H(f)^{e_m} where H (f) is the height of f and e₁ = 4,e₂ = 6, e₃ = 6 [2/3]{2}\over{3} and e_m = 2 m for m S 4. We also show that the exponents e_m are best possible for m 1 3m\ne 3 if a plausible number theoretic conjecture is true.     

Fast construction of irreducible polynomials over finite fields

We present a randomized algorithm that on inputting a finite field K with q elements and a positive integer d outputs a degree d irreducible polynomial in K[x]. The running time is d ^1+?(d)×(log q)^5+?(q) elementary operations. The function ? in this expression is a real positive function belonging to the class o(1), especially, the complexity is quasi-linear in the degree d. Once given such an irreducible polynomial of degree d, we can compute random irreducible polynomials of degree d at the expense of d ^1+?(d) × (log q)^1+?(q) elementary operations only.     

Polynomials with PSL(2, 7) as Galois group

We describe a technique for determining the set-transitivity of the Galois group of a polynomial over the rationals. As an application we give a short proof that the polynomial P₇(x) = x⁷ ? 154x + 99 has the simple group PSL(2, 7) of order 168 as its Galois group over the rationals. A similar method is used to prove that the associated splitting field is not that of the polynomial x⁷ ? 7x + 3 given by Trinks [9].     

On multipliers of polynomial addition sets

Let G be a group of order v, and f(x) be a nonzero integral polynomial. A (v, k, f(x))-polynomial addition set in G is a subset D of G with k distinct elements such that f(Σ_d?Dd) = λΣ_g?Gg for some integer λ. We discuss the multipliers of polynomial addition sets. The structure of some polynomial addition sets is studied, and in particular, we give a complete characterization of the case where G is cyclic and f(x) is irreducible.     

A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length

A Boolean function f: {?1, +1} ⁿ → {?1, +1} is called the sign function of an integer-valued polynomial p(x) if f(x) = sgn(p(x)) for all x ∈ {?1, +1} ⁿ . In this case, the polynomial p(x) is called a perceptron for the Boolean function f. The weight of a perceptron is the sum of absolute values of the coefficients of p. We prove that, for a given function, a small change in the degree of a perceptron can strongly affect the value of the required weight. More precisely, for each d = 1, 2, ..., n ? 1, we explicitly construct a function f: {?1, +1} ⁿ → {?1, +1} that requires a weight of the form exp{Θ(n)} when it is represented by a degree d perceptron, and that can be represented by a degree d + 1 perceptron with weight equal to only O(n ²). The lower bound exp{Θ(n)} for the degree d also holds for the size of the depth 2 Boolean circuit with a majority function at the top and arbitrary gates of input degree d at the bottom. This gap in the weight values is exponentially larger than those that have been previously found. A similar result is proved for the perceptron length, i.e., for the number of monomials contained in it.     

On the irreducibility of a certain class of Laguerre polynomials

R. Gow has investigated the problem of determining classical polynomials with Galois group A_m, the alternating group on m letters, in the case that m is even (odd m being previously handled in work of I. Schur). He showed that the generalized Laguerre polynomial L_m^(m)(x), defined below, has Galois group A_m provided m>2 is even and L_m^(m)(x) is irreducible (and obtained irreducibility in some cases). In this paper, we establish that L_m^(m)(x) is irreducible for almost all m (and, hence, has Galois group A_m for almost all even m).     

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.     

Endomorphisms of superelliptic jacobians

Let K be a field of characteristic zero, n ≥ 5 an integer, f(x) an irreducible polynomial over K of degree n, whose Galois group contains a doubly transitive simple non-abelian group. Let p be an odd prime, the ring of integers in the pth cyclotomic field, C _{f, p} : y ^p  =  f(x) the corresponding superelliptic curve and J(C _{f, p} ) its jacobian. Assuming that either n  =  p + 1 or p does not divide n(n  −  1), we prove that the ring of all endomorphisms of J(C _{f, p} ) coincides with . The same is true if n  =  4, the Galois group of f(x) is the full symmetric group S ₄ and K contains a primitive pth root of unity. An erratum to this article can be found at     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

On some arithmetic properties of Mahler functions

Mahler functions are power series f(x) with complex coefficients for which there exist a natural number n and an integer ? ≥ 2 such that f(x), f(x^?),..., \(f({x^{{\ell ^{n - 1}}}}),f({x^{{\ell ^n}}})\) are linearly dependent over ?(x). The study of the transcendence of their values at algebraic points was initiated by Mahler around the’ 30s and then developed by many authors. This paper is concerned with some arithmetic aspects of these functions. In particular, if f(x) satisfies f(x) = p(x)f(x^?) with p(x) a polynomial with integer coefficients, we show how the behaviour of f(x) mirrors on the polynomial p(x). We also prove some general results on Mahler functions in analogy with G-functions and E-functions.     

On a certain family of generalized Laguerre polynomials

Following the work of Schur and Coleman, we prove the generalized Laguerre polynomial is irreducible over the rationals for all n?1 and has Galois group A_n if n+1 is an odd square, and S_n otherwise. We also show that for certain negative integer values of α and certain congruence classes of n modulo 8, the splitting field of L_n^(α)(x) can be embedded in a double cover.     

Factorization of Q(h(T)(x)) over a finite field where Q(x) is irreducible and h(T)(x) is linear—I

Let GF(q) be the finite field of order q, let Q(x) be an irreducible polynomial in GF(q)(x), and let h(T)(x) be a linear polynomial in GF(q)[x], where T:x→x^q. We use properties of the linear operator h(T) to give conditions for Q(h(T)(x)) to have a root of arbitrary degree k over GF(q), and we describe how to count the irreducible factors of Q(h(T)(x)) of degree k over GF(q). In addition we compare our results with those Ore which count the number of irreducible factors belonging to a linear polynomial having index k.