For a large prime p , and a polynomial f over a finite field \mathbb F_p of p elements, we obtain a lower bound on the size of the multiplicative …
For a large prime p , and a polynomial f over a finite field \mathbb F_p of p elements, we obtain a lower bound on the size of the multiplicative subgroup of \mathbb F_p^* containing H \ \geq 1 consecutive values f(x), x = u+1, \ldots, u+H , uniformly over f \in \mathbb F_p[X] and an u \in \mathbb F_p .
For a large prime $p$, and a polynomial $f$ over a finite field $F_p$ of $p$ elements, we obtain a lower bound on the size of the multiplicative subgroup of …
For a large prime $p$, and a polynomial $f$ over a finite field $F_p$ of $p$ elements, we obtain a lower bound on the size of the multiplicative subgroup of $F_p^*$ containing $H\ge 1$ consecutive values $f(x)$, $x = u+1, \ldots, u+H$, uniformly over $f\in F_p[X]$ and an $u \in F_p$.
For a large prime $p$, and a polynomial $f$ over a finite field $F_p$ of $p$ elements, we obtain a lower bound on the size of the multiplicative subgroup of …
For a large prime $p$, and a polynomial $f$ over a finite field $F_p$ of $p$ elements, we obtain a lower bound on the size of the multiplicative subgroup of $F_p^*$ containing $H\ge 1$ consecutive values $f(x)$, $x = u+1, \ldots, u+H$, uniformly over $f\in F_p[X]$ and an $u \in F_p$.
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},..., a_{d-s} …
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},..., a_{d-s} are fixed. Our estimate holds without restrictions on the characteristic of Fq and asserts that V(d,s,\bfs{a})=\mu_d.q+\mathcal{O}(1), where V(d,s,\bfs{a}) is such an average cardinality, \mu_d:=\sum_{r=1}^d{(-1)^{r-1}}/{r!} and \bfs{a}:=(a_{d-1},.., d_{d-s}). We provide an explicit upper bound for the constant underlying the \mathcal{O}--notation in terms of d and s with "good" behavior. Our approach reduces the question to estimate the number of Fq--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over Fq. We show that the polynomials defining such complete intersections are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of the varieties under consideration, from which a suitable estimate on the number of Fq--rational points is established.
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},...,a_{d-s} are …
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},...,a_{d-s} are fixed. Our estimate asserts that \mathcal{V}(d,s,\bfs{a})=\mu_d\,q+\mathcal{O}(q^{1/2}), where \mathcal{V}(d,s,\bfs{a}) is such an average cardinality, \mu_d:=\sum_{r=1}^d{(-1)^{r-1}}/{r!} and \bfs{a}:=(a_{d-1},...,a_{d-s}). We also prove that \mathcal{V}_2(d,s,\bfs{a})=\mu_d^2\,q^2+\mathcal{O}(q^{3/2}), where that \mathcal{V}_2(d,s,\bfs{a}) is the average second moment on any family of monic polynomials of Fq[T] of degree d with s consecutive coefficients fixed as above. Finally, we show that \mathcal{V}_2(d,0)=\mu_d^2\,q^2+\mathcal{O}(q), where \mathcal{V}_2(d,0) denotes the average second moment of all monic polynomials in Fq[T] of degree d with f(0)=0. All our estimates hold for fields of characteristic p>2 and provide explicit upper bounds for the constants underlying the \mathcal{O}--notation in terms of d and s with "good" behavior. Our approach reduces the questions to estimate the number of Fq--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over Fq. A critical point for our results is an analysis of the singular locus of the varieties under consideration, which allows to obtain rather precise estimates on the corresponding number of Fq--rational points.
We obtain an estimate on the average cardinality $\mathcal{V}(d,s,\boldsymbol{a})$ of the value set of any family of monic polynomials in $\mathbb F_q[T]$ of degree $d$ for which $s$ consecutive coefficients …
We obtain an estimate on the average cardinality $\mathcal{V}(d,s,\boldsymbol{a})$ of the value set of any family of monic polynomials in $\mathbb F_q[T]$ of degree $d$ for which $s$ consecutive coefficients $\boldsymbol{a} = (a_{d-1},\dots, a_{d-s})$ ar
We provide upper bounds for the cardinality of the value set of a polynomial map in several variables over a finite field. These bounds generalize earlier bounds for univariate polynomials.
We provide upper bounds for the cardinality of the value set of a polynomial map in several variables over a finite field. These bounds generalize earlier bounds for univariate polynomials.
We provide upper bounds for the cardinality of the value set of a polynomial map in several variables over a finite field. These bounds generalize earlier bounds for univariate polynomials.
We provide upper bounds for the cardinality of the value set of a polynomial map in several variables over a finite field. These bounds generalize earlier bounds for univariate polynomials.
We estimate the average cardinality $\mathcal{V}(\mathcal{A})$ of the value set of a general family $\mathcal{A}$ of monic univariate polynomials of degree $d$ with coefficients in the finite field $\mathbb{F}_{\hskip-0.7mm q}$. …
We estimate the average cardinality $\mathcal{V}(\mathcal{A})$ of the value set of a general family $\mathcal{A}$ of monic univariate polynomials of degree $d$ with coefficients in the finite field $\mathbb{F}_{\hskip-0.7mm q}$. We establish conditions on the family $\mathcal{A}$ under which $\mathcal{V}(\mathcal{A})=\mu_d\,q+\mathcal{O}(q^{1/2})$, where $\mu_d:=\sum_{r=1}^d{(-1)^{r-1}}/{r!}$. The result holds without any restriction on the characteristic of $\mathbb{F}_{\hskip-0.7mm q}$ and provides an explicit expression for the constant underlying the $\mathcal{O}$--notation in terms of $d$. We reduce the question to estimating the number of $\mathbb{F}_{\hskip-0.7mm q}$--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over $\mathbb{F}_{\hskip-0.7mm q}$. For this purpose, we obtain an upper bound on the dimension of the singular locus of the complete intersections under consideration, which allows us to estimate the corresponding number of $\mathbb{F}_{\hskip-0.7mm q}$--rational points.
This chapter contains sections titled: Zeros of Polynomials Algebraic Extensions of a Field Galois Fields Primitive Elements The Characteristic of a Field Minimal Polynomial Order The Structure of Finite Fields …
This chapter contains sections titled: Zeros of Polynomials Algebraic Extensions of a Field Galois Fields Primitive Elements The Characteristic of a Field Minimal Polynomial Order The Structure of Finite Fields Existence of Galois Fields
This paper seeks to explain in the simplest terms possible a paper written by Umberto Zannier. Though Zannier says that his is “a simple elementary method,” there are still steps …
This paper seeks to explain in the simplest terms possible a paper written by Umberto Zannier. Though Zannier says that his is “a simple elementary method,” there are still steps in his paper that are quite subtle. The tools needed to follow his proof are in the hands of most Algebra students, though which tools to use and how to use them may not be obvious. This essay hopes to make the path from conception to conclusion as clear and easy as possible, with simple proofs and examples to show the way.
Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field~$\mathbb{F}_{q^n}$ considered as …
Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field~$\mathbb{F}_{q^n}$ considered as a linear space over a subfield $\mathbb{F}_q$. We apply this to the recently introduced algorithmic problem of identity testing of "hidden" polynomials $f$ and $g$ over a high degree extension of a finite field, given oracle access to $f(x)^e$ and $g(x)^e$
Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field [Formula: see …
Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field [Formula: see text] considered as a linear space over a subfield [Formula: see text]. We apply this to the recently introduced algorithmic problem of identity testing of “hidden” polynomials [Formula: see text] and [Formula: see text] over a high degree extension of a finite field, given oracle access to [Formula: see text] and [Formula: see text].
We define a sequence of polynomials Pd ∊ Z[x, y]. such that Pd is absolutely irreducible, of degree d, has low height, and has at least d2 + 2d + …
We define a sequence of polynomials Pd ∊ Z[x, y]. such that Pd is absolutely irreducible, of degree d, has low height, and has at least d2 + 2d + 3 integral solutions to Pd(X, y) = 0. We know of no other nontrivial family of polynomials of increasing degree with as many integral solutions in terms of their degree.