Sparse bivariate polynomial factorization

Motivated by Sasaki’s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is efficient, especially for sparse bivariate polynomials.     

On the polynomial representation for the number of partitions with fixed length

In this paper, it is shown that the number of partitions of a nonnegative integer with parts can be described by a set of polynomials of degree in , where denotes the least common multiple of the integers and denotes the quotient of when divided by . In addition, the sets of the polynomials are obtained and shown explicitly for and .

     

On the number of distinct roots of a lacunary polynomial over finite fields

We obtain new upper bounds on the number of distinct roots of lacunary polynomials over finite fields. Our focus will be on polynomials for which there is a large gap between consecutive exponents in the monomial expansion.     

Polyhedra related to integer-convex polynomial systems

This paper deals with the reformulation of a polynomial integer program. For deducing a linear integer relaxation of such a program a class of polyhedra that are associated with nonlinear functions is introduced. A characterization of the family of polynomials for which our approach leads to an equivalent linear integer program is given. Finally the family of so-called integer-convex polynomials is defined, and polyhedra related to such a polynomial are investigated. Supported by DFG-Forschergruppe FOR-468 Received: April, 2004     

Factorable polynomial matrices

It is shown that any regular polynomial matrix over the field of complex numbers that has at most one elementary divisor of degree 3 and whose remaining elementary divisors are of degree no greater than 2 can be factored into linear regular factors. Translated fromMatematicheskie Zametki, Vol. 68, No. 4, pp. 593–607, October, 2000.     

The digit generating function of a polynomial

The average frequency of 1 occurring as the kth digit in the binary expansion of squares, cubes, and generally the values of a polynomial is studied. In particular, it turns out that the generating function of these frequencies is rational for the important special cases of powers, linear and quadratic polynomials. For higher degree polynomials, the behaviour seems to be much more chaotic in general, which is exhibited by two examples of cubic polynomials.     

On solving composite power polynomial equations

It is well known that a system of power polynomial equations can be reduced to a single-variable polynomial equation by exploiting the so-called Newton's identities. In this work, by further exploring Newton's identities, we discover a binomial decomposition rule for composite elementary symmetric polynomials. Utilizing this decomposition rule, we solve three types of systems of composite power polynomial equations by converting each type to single-variable polynomial equations that can be solved easily. For each type of system, we discuss potential applications and characterize the number of nontrivial solutions (up to permutations) and the complexity of our proposed algorithmic solution.

     

Finding a complete set of solutions or proving unsolvability for certain classes of matrix polynomial equations with commuting coefficients

Two classes of matrix polynomial equations with commuting coefficients are examined. It is shown that the equations in one class have complete sets of solutions, whereas the equations in the other class are unsolvable. A method is given for finding the solution set of an equation in the former class.     

Orthogonal polynomial expansions for the matrix exponential

Many different algorithms have been suggested for computing the matrix exponential. In this paper, we put forward the idea of expanding in either Chebyshev, Legendre or Laguerre orthogonal polynomials. In order for these expansions to converge quickly, we cluster the eigenvalues into diagonal blocks and accelerate using shifting and scaling.     

On the calculation of the Kauffman bracket polynomial

In this paper, we present a new algorithm to evaluate the Kauffman bracket polynomial. The algorithm uses cyclic permutations to count the number of states obtained by the application of ‘A’ and ‘B’ type smoothings to the each crossing of the knot. We show that our algorithm can be implemented easily by computer programming.     

On polynomial symbols for subdivision schemes

Given a dilation matrix A :ℤ^d→ℤ^d, and G a complete set of coset representatives of 2π(A ^−Tℤ^d/ℤ^d), we consider polynomial solutions M to the equation ∑ _g∈G M(ξ+g)=1 with the constraints that M≥0 and M(0)=1. We prove that the full class of such functions can be generated using polynomial convolution kernels. Trigonometric polynomials of this type play an important role as symbols for interpolatory subdivision schemes. For isotropic dilation matrices, we use the method introduced to construct symbols for interpolatory subdivision schemes satisfying Strang–Fix conditions of arbitrary order. Research partially supported by the Danish Technical Science Foundation, Grant No. 9701481, and by the Danish SNF-PDE network.     

On trees with real-rooted independence polynomial

The independence polynomial of a graph $G$ is

$I(G,x)=\sum _{k\ge 0}{i}_k\left(G\right)x^k,$

where $i_k\left(G\right)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0\left(G\right)=1$). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu’s theorem), caterpillars (Wang and Zhu’s theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees.     

On the division of polynomial matrices

The main purpose of this paper is to determine two new algorithmsfor the division of the polynomial matrix B(s) R[s]^pxq by A(s) R[s]^pxp (a) based on the Laurent matrix expansion at s = =of the inverse of A(s), i.e. A(s)^–1, and (b) in a waysimilar to the one presented by Gantmacher (1959).     

On the total number of prime factors of an odd perfect number

We say is perfect if , where denotes the sum of the positive divisors of . No odd perfect numbers are known, but it is well known that if such a number exists, it must have prime factorization of the form , where , , ..., are distinct primes and . We prove that if or for all , , then . We also prove as our main result that , where . This improves a result of Sayers given in 1986.

     

On the number of invariant lines for polynomial systems

In this paper we will revise the mistakes in a previous paper of Zhang Xikang (Number of integral lines of polynomial systems of degree three and four, J. Nanjing Univ. Math. Biquarterly, Supplement, 1993, pp. 209-212) for the proof of the conjecture on the maximum number of invariant straight lines of cubic and quartic polynomial differential systems; and also prove the conjecture in a previous paper of the second author (Qualitative theory of polynomial differential systems, Shanghai Science-Technical Publishers, Shanghai, 1995, p. 474) for a certain special case of the degree polynomial systems. Furthermore, we will prove that cubic and quartic differential systems have invariant straight lines along at most six and nine different directions, respectively, and also show that the maximum number of the directions can be obtained.

     

The black-box Niederreiter algorithm and its implementation over the binary field

The most time-consuming part of the Niederreiter algorithm for factoring univariate polynomials over finite fields is the computation of elements of the nullspace of a certain matrix. This paper describes the so-called ``black-box' Niederreiter algorithm, in which these elements are found by using a method developed by Wiedemann. The main advantages over an approach based on Gaussian elimination are that the matrix does not have to be stored in memory and that the computational complexity of this approach is lower. The black-box Niederreiter algorithm for factoring polynomials over the binary field was implemented in the C programming language, and benchmarks for factoring high-degree polynomials over this field are presented. These benchmarks include timings for both a sequential implementation and a parallel implementation running on a small cluster of workstations. In addition, the Wan algorithm, which was recently introduced, is described, and connections between (implementation aspects of) Wan's and Niederreiter's algorithm are given.

     

On the large sieve in algebraic number fields

In the present note Bombieri's central theorem concerning the average distribution of the prime numbers in arithmetic progressions is generalized to arbitrary algebraic number fields.Translated from Matematicheskie Zametki, Vol. 2, No. 6, pp. 673–680, December, 1967.Finally, I express my profound gratitude to B. V. Levin for setting the problem and the help he rendered and to A. I. Vinogradov for valuable suggestions.     

Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method

In this paper, we describe many improvements to the number field sieve. Our main contribution consists of a new way to compute individual logarithms with the number field sieve without solving a very large linear system for each logarithm. We show that, with these improvements, the number field sieve outperforms the gaussian integer method in the hundred digit range. We also illustrate our results by successfully computing discrete logarithms with GNFS in a large prime field.

     

A relation between the LG polynomial and the Kauffman polynomial

We give an explicit formula for the fact given by Links and Gould that a one variable reduction of the LG polynomial coincides with a one variable reduction of the Kauffman polynomial. This implies that the crossing number of an adequate link may be obtained from the LG polynomial by using a result of Thistlethwaite. We also give some evaluations of the LG polynomial.