On the distribution of reducible polynomials

Let ℛ _n (t) denote the set of all reducible polynomials p(X) over ℤ with degree n ≥ 2 and height ≤ t. We determine the true order of magnitude of the cardinality |ℛ _n (t)| of the set ℛ _n (t) by showing that, as t → ∞, t ² log t ≪ |ℛ₂(t)| ≪ t ² log t and t ⁿ ≪ |ℛ _n (t)| ≪ t _n for every fixed n ≥ 3. Further, for 1 < n/2 < k < n fixed let ℛ _k,n (t) ⊂ ℛ _n (t) such that p(X) ∈ ℛ _k,n (t) if and only if p(X) has an irreducible factor in ℤ[X] of degree k. Then, as t → ∞, we always have t ^k+1 ≪ |ℛ _k,n (t)| ≪ t ^k+1 and hence |ℛ _n−1,n (t)| ≫ |ℛ _n (t)| so that ℛ _n−1,n (t) is the dominating subclass of ℛ _n (t) since we can show that |ℛ _n (t)∖ℛ _n−1,n (t)| ≪ t ⁿ⁻¹(log t)².On the contrary, if R _n ^s (t) is the total number of all polynomials in ℛ _n (t) which split completely into linear factors over ℤ, then t ²(log t) ⁿ⁻¹ ≪ R _n ^s (t) ≪ t ² (log t) ⁿ⁻¹ (t → ∞) for every fixed n ≥ 2.      

On the reducible quintic complete base polynomials

Let B(x)=xm+bm−1xm−1+?+b₀∈Z[x]. If every element in Z[x]/(B(x)Z[x]) has a polynomial representative with coefficients in S={0,1,2,…,|b₀|−1} then B(x) is called a complete base polynomial. We prove that if B(x) is a completely reducible quintic polynomial with five distinct integer roots less than −1, then B is a complete base polynomial. This is the best possible result regarding the completely reducible polynomials so far. Meanwhile, we provide a Mathematica program for determining whether an input polynomial B(x) is a complete base polynomial or not. The program enables us to experiment with various polynomial examples, to decide if the potential result points in the desired direction and to formulate credible conjectures.     

Elements with bounded height in number fields

We give a constructive proof of the fact that there exist only finitely many elements with bounded height in number fields. This provides an eficient method to enumerate all those elements. Such a method is helpful to compute bases on elliptic curves.     

On bounded polynomials in several variables

Mathematische Zeitschrift -     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

Counting reducible and singular bivariate polynomials

Among the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the “relatively irreducible” ones which are irreducible but factor over an extension field, and the singular ones, which have a root at which both partial derivatives vanish.     

The asymptotic number of integral cubic polynomials with bounded heights and discriminants

Let P denote a cubic integral polynomial, and let D(P) and H(P) denote the discriminant and height of P, respectively. Let N(Q,X) be the number of cubic integral polynomials P such that H(P) ≤ Q and |D(P)| ≤ X. We obtain an asymptotic formula of N(Q,X) for Q ^14/5 ? X ? Q ⁴ and Q → +∞. Using this result, for 0 ≤ η ≤ 9/10, we find the asymptotic value of $$ \sum\limits_{{\begin{array}{*{20}{c}} {H(P)\leq Q} \\ {1\leq \left| {D(P)} \right|\ll {Q^{{4-\eta }}}} \\ \end{array}}} {{{{\left| {D(P)} \right|}}^{{-{1 \left/ {2} \right.}}}}}, $$ where the sum is taken over irreducible integral polynomials and Q → +∞. This improves upon a result of Davenport, who dealt with the case η = 0.     

On the number of polynomials of small house

Suppose that ɛ is a positive number, and letd be a sufficiently large positive integer. We consider a set of monic polynomials of degreed with integer coefficients and roots lying in the disk of radiusd ^ɛ/d. We prove that the number of such polynomials is less than exp(d ^2/3+ɛ). Partially supported by the Lithuanian State Science and Studies Foundation. Vilnius University, Naugarduko 24, 2600 Vilnius, Lithuania. Published in Lietuvos Matematikos Rinkinys, Vol. 39, No. 2, pp. 214–219, April–June, 1999.     

Irreducible polynomials which are locally reducible everywhere

For any positive integer , there exist polynomials of degree which are irreducible over and reducible over for all primes if and only if is composite. In fact, this result holds over arbitrary global fields.

     

On the number of zeros of certain harmonic polynomials

Using techinques of complex dynamics we prove the conjecture of Sheil-Small and Wilmshurst that the harmonic polynomial , 1$">, has at most complex zeros.

     

On the distribution of points in projective space of bounded height

In this paper we consider the uniform distribution of points in compact metric spaces. We assume that there exists a probability measure on the Borel subsets of the space which is invariant under a suitable group of isometries. In this setting we prove the analogue of Weyl's criterion and the Erdös-Turán inequality by using orthogonal polynomials associated with the space and the measure. In particular, we discuss the special case of projective space over completions of number fields in some detail. An invariant measure in these projective spaces is introduced, and the explicit formulas for the orthogonal polynomials in this case are given. Finally, using the analogous Erdös-Turán inequality, we prove that the set of all projective points over the number field with bounded Arakelov height is uniformly distributed with respect to the invariant measure as the bound increases.

     

On sequences of Dirichlet polynomials uniformly bounded on half planes

Given and a sequence of Dirichlet polynomials estimates for the coefficientsa _n are proved if {_n} is uniformly bounded on a region containing a half plane. Thereby a result is obtained which is an analogue of a known result for polynomials, that is for theA-transforms of the geometric sequence; moreover a Jentzsch type theorem for {_n(z)} is derived.     

On the number of zero-patterns of a sequence of polynomials

Let be a sequence of polynomials of degree in variables over a field . The zero-pattern of at is the set of those ( ) for which . Let denote the number of zero-patterns of as ranges over . We prove that for and

for . For , these bounds are optimal within a factor of . The bound () improves the bound proved by J. Heintz (1983) using the dimension theory of affine varieties. Over the field of real numbers, bounds stronger than Heintz's but slightly weaker than () follow from results of J. Milnor (1964), H.E.  Warren (1968), and others; their proofs use techniques from real algebraic geometry. In contrast, our half-page proof is a simple application of the elementary ``linear algebra bound'.

Heintz applied his bound to estimate the complexity of his quantifier elimination algorithm for algebraically closed fields. We give several additional applications. The first two establish the existence of certain combinatorial objects. Our first application, motivated by the ``branching program' model in the theory of computing, asserts that over any field , most graphs with vertices have projective dimension (the implied constant is absolute). This result was previously known over the reals (Pudlák-Rödl). The second application concerns a lower bound in the span program model for computing Boolean functions. The third application, motivated by a paper by N. Alon, gives nearly tight Ramsey bounds for matrices whose entries are defined by zero-patterns of a sequence of polynomials. We conclude the paper with a number of open problems.

     

On the number of monic integer polynomials with given signature

In this paper, we show that the number of monic integer polynomials of degree \(d \ge 1\) and height at most H which have no real roots is between \(c_1H^{d-1/2}\) and \(c_2 H^{d-1/2}\), where the constants \(c_2>c_1>0\) depend only on d. (Of course, this situation may only occur for d even.) Furthermore, for each integer s satisfying \(0 \le s < d/2\) we show that the number of monic integer polynomials of degree d and height at most H which have precisely 2s non-real roots is asymptotic to \(\lambda (d,s)H^{d}\) as \(H \rightarrow \infty \). The constants \(\lambda (d,s)\) are all positive and come from a recent paper of Bertók, Hajdu, and Peth?. They considered a similar question for general (not necessarily monic) integer polynomials and posed this as an open question.