Polynomials with roots modulo every integer

Given a polynomial with integer coefficients, we calculate the density of the set of primes modulo which the polynomial has a root. We also give a simple criterion to decide whether or not the polynomial has a root modulo every non-zero integer.

     

Diophantine m-tuples for linear polynomials II. Equal degrees

In this paper we prove the best possible upper bounds for the number of elements in a set of polynomials with integer coefficients all having the same degree, such that the product of any two of them plus a linear polynomial is a square of a polynomial with integer coefficients. Moreover, we prove that there does not exist a set of more than 12 polynomials with integer coefficients and with the property from above. This significantly improves a recent result of the first two authors with Tichy [A. Dujella, C. Fuchs, R.F. Tichy, Diophantine m-tuples for linear polynomials, Period. Math. Hungar. 45 (2002) 21-33].     

Solving polynomial systems in integers

The paper describes a method for determining integer solutions of a homogeneous polynomial system with integer coefficients which has finitely many solutions in the projective space over the field of complex numbers under the assumption that these solutions have a certain property.     

On asymptotic distribution on the a-adic integers

We show that the values of a polynomial with a-adic coefficients at integer and rational prime arguments are asymptotically distributed on the a-adic integers and that the integer parts of certain sequences known to be uniformly distributed modulo one, are uniformly distributed on the a-adic integers.     

Description of 2-integer continuous knapsack polyhedra

In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems.     

On testing the divisibility of lacunary polynomials by cyclotomic polynomials

An algorithm is described that determines whether a given polynomial with integer coefficients has a cyclotomic factor. The algorithm is intended to be used for sparse polynomials given as a sequence of coefficient-exponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.

     

Certain Diophantine Properties of the Mahler Measure

It is proved that a polynomial in several Mahler measures with positive rational coefficients is equal to an integer if and only if all these Mahler measures are integers. An estimate for the distance between a metric Mahler measure and an integer is obtained. Finally, it is proved that the ratio of two distinct Mahler measures of algebraic units is irrational.     

On Galois spectra of polynomials with integral parameters

We prove that there exists a polynomial F(x, t) with rational coefficients, whose degree with respect to x is equal to 4, such that for every integer a, the Galois group of the decomposition field of the polynomial F(x, a) is not the dihedral group, but any other transitive subgroup of the group S₄ can be represented as the Galois group of the decomposition field of the polynomial F(x, a) for a certain integer a. Bibliography: 1 title. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 321, 2005, pp. 275–280.     

A fraction-free unit-circle zero location test for a polynomial with any singularity profile

This paper presents a fraction-free (FF) version of the Bistritz test to determine the zero location (ZL) of a polynomial with respect to the unit circle. The test has the property that when it is invoked on a polynomial with Gaussian or real integer coefficients, it is an efficient integer algorithm completed without fractions over the respective integral domain. The test is not restricted to integers but remains integer preserving (IP) in all possible encounters of abnormalities and singularities. We define a symmetric subresultant polynomial sequence (SSPS) for the Sylvester matrix of two symmetric polynomials. We then show that the sequence of polynomials produced by the FF test coincides with the SSPS of its first two polynomials when the test is normal and the SSPS is strongly nonsingular, or else its polynomials match the non-singular subresultant polynomial and pass over intermediate gaps of singular subresultants in an IP and efficient manner. This relationship (interesting in its own right) is used to show that the test is IP and normally attains integers of minimal size.     

Lattice Paths and Positive Trigonometric Sums

A trigonometric polynomial generalization to the positivity of an alternating sum of binomial coefficients is given. The proof uses lattice paths, and identifies the trigonometric sum as a polynomial with positive integer coefficients. Some special cases of the q -analogue conjectured by Bressoud are established, and new conjectures are given. January 22, 1997. Date revised: July 9, 1997.     

The large sieve inequality for integer polynomial amplitudes

We obtain a close to optimal version of the large sieve inequality with amplitudes given by the values of a polynomial with integer coefficients of degree ?2.     

纽结与多项式

In this paper, we deal with some corresponding relations between knots and polynomials by using the basic properties of knot polynomials （such as, some special values of knot polynomials, the Arf invariant and derivative of knot polynomials）. We give necessary and sufficient conditions that a Laurent polynomial with integer coefficients, whose breadth is less than five, is the Jones polynomial of a certain knot.     

Polynomial Identities and Nonidentities of Split Jordan Pairs

We show that split Jordan pairs over rings without 2-torsion can be distinguished by polynomial identities with integer coefficients. In particular, this holds for simple finite-dimensional Jordan pairs over algebraically closed fields of characteristic not 2. We also generalize results of Drensky and Racine and of Rached and Racine on polynomial identities of, respectively, Jordan algebras and Jordan triple systems.     

On the distribution of the coefficients of normal forms for Frobenius expansions

Frobenius expansions are representations of integers to an algebraic base which are sometimes useful for efficient (hyper)elliptic curve cryptography. The normal form of a Frobenius expansion is the polynomial with integer coefficients obtained by reducing a Frobenius expansion modulo the characteristic polynomial of Frobenius. We consider the distribution of the coefficients of reductions of Frobenius expansions and non-adjacent forms of Frobenius expansions (NAFs) to normal form. We give asymptotic bounds on the coefficients which improve on naive bounds, for both genus one and genus two. We also discuss the non-uniformity of the distribution of the coefficients (assuming a uniform distribution for Frobenius expansions).     

On some classes of polynomials with nonnegative coefficients and a given factor

For a given real polynomial f without positive roots we study polynomials g of lowest degree such that the product gf has positive (nonnegative, respectively) coefficients. We show that for quadratic f with negative linear coefficient every such g must have positive coefficients and exhibit an easy procedure for the determination of g. If f has only integer coefficients we show that g with integer coefficients can be found. Furthermore, for some classes of polynomials f we give upper (lower, respectively) bounds for the degrees of g.     

Complete solution of the polynomial version of a problem of Diophantus

In this paper, we prove that if {a,b,c,d} is a set of four non-zero polynomials with integer coefficients, not all constant, such that the product of any two of its distinct elements plus 1 is a square of a polynomial with integer coefficients, then

(a+b−c−d)2=4(ab+1)(cd+1).     

Further results on Hilbert’s Tenth Problem

Hilbert's Tenth Problem(HTP) asks for an algorithm to test whether an arbitrary polynomial Diophantine equation with integer coefficients has solutions over the ring Z of integers.This was finally solved negatively by Matiyasevich in 1970.In this paper we obtain some further results on HTP over Z.We prove that there is no algorithm to determine for any P(z_1,...,z_9) ∈ Z[z_1,...,z_9] whether the equation P(z_1,...,z_9)=0 has integral solutions with z_9≥0.Consequently,there is no algorithm to test whether an arbitrary polynomial Diophantine equation P(z_1,...,z_(11))=0(with integer coefficients) in 11 unknowns has integral solutions,which provides the best record on the original HTP over Z.We also prove that there is no algorithm to test for any P(z_1,...,z_(17))∈Z[z_1,...,z_(17)] whether P(z_1,...,z_(17))=0 has integral solutions,and that there is a polynomial Q(z_1,...,z_(20))∈Z[z_1,...,z_(20)] such that {Q(z_1~2,...,z_(20)~2):z_1,...,z_(20)∈Z}∩ {0,1,2,...} coincides with the set of all primes.     

An explicit form for Kerov's character polynomials

Kerov considered the normalized characters of irreducible representations of the symmetric group, evaluated on a cycle, as a polynomial in free cumulants. Biane has proved that this polynomial has integer coefficients, and made various conjectures. Recently, Sniady has proved Biane's conjectured explicit form for the first family of nontrivial terms in this polynomial. In this paper, we give an explicit expression for all terms in Kerov's character polynomials. Our method is through Lagrange inversion.

     

Schönemann–Eisenstein–Dumas-Type Irreducibility Conditions that Use Arbitrarily Many Prime Numbers

The famous irreducibility criteria of Schönemann–Eisenstein and Dumas rely on information on the divisibility of the coefficients of a polynomial by a single prime number. In this paper, we will use some results and ideas of Dumas to provide several irreducibility criteria of Schönemann–Eisenstein–Dumas-type for polynomials with integer coefficients, criteria that are given by some divisibility conditions for their coefficients with respect to arbitrarily many prime numbers. A special attention will be paid to those irreducibility criteria that require information on the divisibility of the coefficients by two distinct prime numbers.