Direct factors of polynomial rings over finite fields

Let G_q denote the multiplicative semigroup of all monic polynomials in one indeterminate over a finite field F_q with q elements. By a direct factor of G_q is understood a subset B₁ of G_q such that, for some subset B₂ of G_q, every polynomial w G_q has a unique factorization in the form w = b₁b₂ for b_i B_i. An asymptotic formula B₁^#(n) c₁qⁿ as n → ∞ is derived for the total number B₁^#(n) of polynomials of degree n in an arbitrary direct factor B₁ of G_q, c₁ a constant depending on B₁.     

On Diophantine sets over polynomial rings

We prove that the recursively enumerable relations over a polynomial ring , where is the ring of integers in a totally real number field, are exactly the Diophantine relations over .

     

Quadratic forms over polynomial rings over global fields

It is proved that a quadratic space over the polynomial extension of a global field K is extended from K if it is extended from K_v for every completion K_v of K.     

Unimodular polynomial matrices over finite fields

Journal of Algebraic Combinatorics - We consider some combinatorial problems on matrix polynomials over finite fields. Using results from control theory, we give a proof of a result of Lieb, Jordan...     

Classification of multivariate skew polynomial rings over finite fields via affine transformations of variables

In this work, free multivariate skew polynomial rings are considered, together with their quotients over ideals of skew polynomials that vanish at every point (which includes minimal multivariate skew polynomial rings). We provide a full classification of such multivariate skew polynomial rings (free or not) over finite fields. To that end, we first show that all ring morphisms from the field to the ring of square matrices are diagonalizable, and that the corresponding derivations are all inner derivations. Secondly, we show that all such multivariate skew polynomial rings over finite fields are isomorphic as algebras to a multivariate skew polynomial ring whose ring morphism from the field to the ring of square matrices is diagonal, and whose derivation is the zero derivation. Furthermore, we prove that two such representations only differ in a permutation on the field automorphisms appearing in the corresponding diagonal. The algebra isomorphisms are given by affine transformations of variables and preserve evaluations and degrees. In addition, ours proofs show that the simplified form of multivariate skew polynomial rings can be found computationally and explicitly.     

The rank of sparse random matrices over finite fields

Let M be a random (n×n)-matrix over GF[q] such that for each entry M_ij in M and for each nonzero field element α the probability Pr[M_ij=α] is p/(q−1), where p=(log n−c)/n and c is an arbitrary but fixed positive constant. The probability for a matrix entry to be zero is 1−p. It is shown that the expected rank of M is n−𝒪(1). Furthermore, there is a constant A such that the probability that the rank is less than n−k is less than A/q^k. It is also shown that if c grows depending on n and is unbounded as n goes to infinity, then the expected difference between the rank of M and n is unbounded. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 407–419, 1997     

On the polynomial Ramanujan sums over finite fields

The polynomial Ramanujan sum was first introduced by Carlitz (Duke Math J 14:1105–1120, 1947), and a generalized version by Cohen (Duke Math J 16:85–90, 1949). In this paper, we study the arithmetical and analytic properties of these sums, deriving various fundamental identities, such as Hölder formula, reciprocity formula, orthogonality relation, and Davenport–Hasse type formula. In particular, we show that the special Dirichlet series involving the polynomial Ramanujan sums are, indeed, the entire functions on the whole complex plane, and we also give a square mean values estimation. The main results of this paper are new appearance to us, which indicate the particularity of the polynomial Ramanujan sums.     

Nonsingularity of least common multiple matrices on gcd-closed sets

Let n be a positive integer. Let S={x₁,…,x_n} be a set of n distinct positive integers. The least common multiple (LCM) matrix on S, denoted by [S], is defined to be the n×n matrix whose (i,j)-entry is the least common multiple [x_i,x_j] of x_i and x_j. The set S is said to be gcd-closed if for any x_i,x_j∈S,(x_i,x_j)∈S. For an integer m>1, let ω(m) denote the number of distinct prime factors of m. Define ω(1)=0. In 1997, Qi Sun conjectured that if S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. In this paper, we settle completely Sun's conjecture. We show the following result: (i). If S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. Namely, Sun's conjecture is true; (ii). For each integer r?3, there exists a gcd-closed set S satisfying max_x∈S{ω(x)}=r, such that the LCM matrix [S] is singular.     

Hensel lifting and bivariate polynomial factorisation over finite fields

This paper presents an average time analysis of a Hensel lifting based factorisation algorithm for bivariate polynomials over finite fields. It is shown that the average running time is almost linear in the input size. This explains why the Hensel lifting technique is fast in practice for most polynomials.

     

Minimal sets in finite rings

We describe how to calculate the (, )-minimal sets in any finite ring.     

A remark on polynomial function over finite commutative rings with identity

In the present paper, the degree of polynomial functions on a finite commutative ringR with identity is investigated. An upper bound for the degree is given (Theorem 3) with the help of a reduction formula for powers (Theorem 1).