Source author record

Mariana Pérez

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT math.CO math.AG math.PR

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the computation of rational solutions of underdetermined systems over a finite field

We design and analyze an algorithm for computing solutions with coefficients in a finite field $\mathbb{F}_q$ of underdetermined systems defined over $\mathbb{F}_q$ . The algorithm is based on reductions to zero-dimensional searches. The searches are performed on "vertical strips", namely parallel linear spaces of suitable dimension in a given direction. Our results show that, on average, less than three searches suffice to obtain a solution of the original system, with a probability of success which grows exponentially with the number of searches. The analysis of our algorithm relies on results on the probability that the solution set (over the algebraic closure of $\mathbb{F}_q$ ) of a random system with coefficients in $\mathbb{F}_q$ satisfies certain geometric and algebraic properties which is of independent interest.

preprint2022arXiv

The distribution of defective multivariate polynomial systems over a finite field

This paper deals with properties of the algebraic variety defined as the set of zeros of a "deficient" sequence of multivariate polynomials. We consider two types of varieties: ideal-theoretic complete intersections and absolutely irreducible varieties. For these types, we establish improved bounds on the dimension of the set of deficient systems of each type over an arbitrary field. On the other hand, we establish improved upper bounds on the number of systems of each type over a finite field.

preprint2020arXiv

Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field

We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field F_q of q elements when the highest-degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f which are relatively prime with g and for the average degree of gcd(g,f). The accuracy of our estimates is confirmed by practical experiments. We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.

preprint2016arXiv

On the computation of rational points of a hypersurface over a finite field

We design and analyze an algorithm for computing rational points of hypersurfaces defined over a finite field based on searches on "vertical strips", namely searches on parallel lines in a given direction. Our results show that, on average, less than two searches suffice to obtain a rational point. We also analyze the probability distribution of outputs, using the notion of Shannon entropy, and prove that the algorithm is somewhat close to any "ideal" equidistributed algorithm.

preprint2015arXiv

On the value set of small families of polynomials over a finite field, III

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})=μ_d\,q+\mathcal{O}(q^{1/2})$ , where $μ_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.

preprint2014arXiv

Explicit Estimates for the Number of Rational Points of Singular Complete Intersections over a Finite Field

Let $V\subset\mathbb{P}^n(\overline{F}_{\hskip-0.7mm q})$ be a complete intersection defined over a finite field $F_{\hskip-0.7mm q}$ of dimension $r$ and singular locus of dimension at most $0\le s\le r-2$ . We obtain an explicit version of the Hooley--Katz estimate $||V(F_{\hskip-0.7mm q})|-p_r|=\mathcal{O}(q^{(r+s+1)/2})$ , where $|V(F_{\hskip-0.7mm q})|$ denotes the number of $F_{\hskip-0.7mm q}$ -rational points of $V$ and $p_r:=|\mathbb{P}^r(F_{\hskip-0.7mm q})|$ . Our estimate improves all the previous estimates in several important cases. Our approach relies on tools of classical algebraic geometry. A crucial ingredient is a new effective version of the Bertini smoothness theorem, namely an explicit upper bound of the degree of a proper Zariski closed subset of $(\mathbb P^{n})^{s+1}(\overline{F}_{\hskip-0.7mm q})$ which contains all the singular linear sections of $V$ of codimension $s+1$ .

preprint2014arXiv

The distribution of factorization patterns on linear families of polynomials over a finite field

We obtain estimates on the number $|\mathcal{A}_{\boldsymbolλ}|$ of elements on a linear family $\mathcal{A}$ of monic polynomials of $\mathbb{F}_q[T]$ of degree $n$ having factorization pattern $\boldsymbolλ:=1^{λ_1}2^{λ_2}\cdots n^{λ_n}$ . We show that $|\mathcal{A}_{\boldsymbolλ}|= \mathcal{T}(\boldsymbolλ)\,q^{n-m}+\mathcal{O}(q^{n-m-{1}/{2}})$ , where $\mathcal{T}(\boldsymbolλ)$ is the proportion of elements of the symmetric group of $n$ elements with cycle pattern $\boldsymbolλ$ and $m$ is the codimension of $\mathcal{A}$ . Furthermore, if the family $\mathcal{A}$ under consideration is "sparse", then $|\mathcal{A}_{\boldsymbolλ}|= \mathcal{T}(\boldsymbolλ)\,q^{n-m}+\mathcal{O}(q^{n-m-{1}})$ . Our estimates hold for fields $\mathbb{F}_q$ of characteristic greater than 2. We provide explicit upper bounds for the constants underlying the $\mathcal{O}$ --notation in terms of $\boldsymbolλ$ and $\mathcal{A}$ with "good" behavior. Our approach reduces the question to estimate the number of $\mathbb{F}_q$ --rational points of certain families of complete intersections defined over $\mathbb{F}_q$ . Such complete intersections are defined by polynomials which are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning their singular locus, from which precise estimates on their number of $\mathbb{F}_q$ --rational points are established.

preprint2013arXiv

On the value set of small families of polynomials over a finite field, I

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})=μ_d.q+\mathcal{O}(1), where V(d,s,\bfs{a}) is such an average cardinality, μ_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.

preprint2013arXiv

On the value set of small families of polynomials over a finite field, II

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})=μ_d\,q+\mathcal{O}(q^{1/2}), where \mathcal{V}(d,s,\bfs{a}) is such an average cardinality, μ_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})=μ_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)=μ_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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Mariana Pérez

Research overview

Is this your work?

9 publications

On the computation of rational solutions of underdetermined systems over a finite field

The distribution of defective multivariate polynomial systems over a finite field

Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field

On the computation of rational points of a hypersurface over a finite field

On the value set of small families of polynomials over a finite field, III

Explicit Estimates for the Number of Rational Points of Singular Complete Intersections over a Finite Field

The distribution of factorization patterns on linear families of polynomials over a finite field

On the value set of small families of polynomials over a finite field, I

On the value set of small families of polynomials over a finite field, II

See the researcher in context

Building this map preview