Estimates on the number of Fq–rational solutions of variants of diagonal equations over finite fields

In this paper we study the set of

-rational solutions of equations defined by polynomials evaluated in power-sum polynomials with coefficients in

. This is done by means of applying a methodology which relies on the study of the geometry of the set of common zeros of symmetric polynomials over the algebraic closure of

. We provide improved estimates and existence results of

-rational solutions to the following equations: deformed diagonal equations, generalized Markoff-Hurwitz-type equations and Carlitz's equations. We extend these techniques to more general variants of diagonal equations over finite fields.     

Fast computation of a rational point of a variety over a finite field

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

     

On the number of curves of genus 2 over a finite field

In this paper we compute the number of curves of genus 2 defined over a finite field k of odd characteristic up to isomorphisms defined over k; the even characteristic case is treated in an ongoing work (G. Cardona, E. Nart, J. Pujolàs, Curves of genus 2 over field of even characteristic, 2003, submitted for publication). To this end, we first give a parametrization of all points in , the moduli variety that classifies genus 2 curves up to isomorphism, defined over an arbitrary perfect field (of zero or odd characteristic) and corresponding to curves with non-trivial reduced group of automorphisms; we also give an explicit representative defined over that field for each of these points. Then, we use cohomological methods to compute the number of k-isomorphism classes for each point in .     

Sequences of consecutive smooth polynomials over a finite field

Given , we show that there are infinitely many sequences of consecutive -smooth polynomials over a finite field. The number of polynomials in each sequence is approximately .

     

Solving sparse linear systems of equations over finite fields using bit-flipping algorithm

Let _Fq${\mathbb{F}}_q$ be the finite field with q   elements. We give an algorithm for solving sparse linear systems of equations over _Fq${\mathbb{F}}_q$ when the coefficient matrix of the system has a specific structure, here called relatively connected. This algorithm is based on a well-known decoding algorithm for low-density parity-check codes called bit-flipping algorithm. We modify and extend this hard decision decoding algorithm. The complexity of this algorithm is linear in terms of the number of columns n and the number of nonzero coefficients ω of the matrix per iteration. The maximum number of iterations is bounded above by m, the number of equations.     

Continued fractions for hyperquadratic power series over a finite field

An irrational power series over a finite field of characteristic p is called hyperquadratic if it satisfies an algebraic equation of the form x=(Ax^r+B)/(Cx^r+D), where r is a power of p and the coefficients belong to . These algebraic power series are analogues of quadratic real numbers. This analogy makes their continued fraction expansions specific as in the classical case, but more sophisticated. Here we present a general result on the way some of these expansions are generated. We apply it to describe several families of expansions having a regular pattern.     

A simplified proof for the limit of a tower over a cubic finite field

Recently Bezerra, Garcia and Stichtenoth constructed an explicit tower F=(Fn)_n?0 of function fields over a finite field Fq³, whose limit λ(F)=limn→∞N(Fn)/g(Fn) attains the Zink bound λ(F)?2(q²−1)/(q+2). Their proof is rather long and very technical. In this paper we replace the complex calculations in their work by structural arguments, thus giving a much simpler and shorter proof for the limit of the Bezerra, Garcia and Stichtenoth tower.     

Periodicity and solutions of some rational difference equations systems

In this paper we are interested in a technique for solving some nonlinear rational systems of difference equations of third order, in three-dimensional case. Moreover, we study the periodicity of solutions for such systems. Finally, some numerical examples are presented.     

Recursively enumerable sets of polynomials over a finite field

We prove that a relation over is recursively enumerable if and only if it is Diophantine over . We do this by first constructing a model of in , where n is represented by Zⁿ. In a second step, we show that it suffices to eliminate a bounded universal quantifier. Then finally, the hardest part of the proof is to show that we can eliminate this quantifier.     

On the complexity of matrix reduction over finite fields

In this paper we study the complexity of matrix elimination over finite fields in terms of row operations, or equivalently in terms of the distance in the Cayley graph of generated by the elementary matrices. We present an algorithm called striped matrix elimination which is asymptotically faster than traditional Gauss–Jordan elimination. The new algorithm achieves a complexity of row operations, and operations in total, thanks to being able to eliminate many matrix positions with a single row operation. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices. Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from , with n and q small. Finally we consider an extension from finite fields to finite semifields of the matrix reduction problem. We give a conjecture on the behaviour of a natural analogue of GL_n for semifields and prove this for a certain class of semifields.     

关于有限域上一类方程解的个数

Let Fq be a finite field with q = pf elements,where p is an odd prime.Let N(a1x12 + ···+anxn2 = bx1 ···xs) denote the number of solutions(x1,...,xn) of the equation a1x12 +···+ anxn2 = bx1 ···xs in Fnq,where n 5,s n,and ai ∈ F*q,b ∈ F*q.In this paper,we solve the problem which the present authors mentioned in an earlier paper,and obtain a reduction formula for the number of solutions of equation a1x21 + ··· + anxn2 = bx1 ···xs,where n 5,3 ≤ s n,under a certain restriction on coefficients.We also obtain an explicit formula for the number of solutions of equation a1x21 + ··· + anxn2 = bx1 ···xn-1 in Fqn under a restriction on n and q.