BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Guillermo Matera

Guillermo Matera appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.AGmath.NTmath.COmath.PRSymbolic Computation

Catalog footprint

What is connected

18works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

18 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the bit complexity of polynomial system solving

We exhibit a probabilistic algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence. Its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size. Our algorithm solves the input system modulo a prime number p and applies p-adic lifting. For this purpose, we establish a number of results on the bit length of a "lucky" prime p, namely one for which the reduction of the input system modulo p preserves certain fundamental geometric and algebraic properties of the original system. These results rely on the analysis of Chow forms associated to the set of solutions of the input system and effective arithmetic Nullstellensätze.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Explicit estimates for polynomial systems defining irreducible smooth complete intersections

This paper deals with properties of the algebraic variety defined as the set of zeros of a "typical" sequence of polynomials. We consider various types of "nice" varieties: set-theoretic and ideal-theoretic complete intersections, absolutely irreducible ones, and nonsingular ones. For these types, we present a nonzero "obstruction" polynomial of explicitly bounded degree in the coefficients of the sequence that vanishes if its variety is not of the type. Over finite fields, this yields bounds on the number of such sequences. We also show that most sequences (of at least two polynomials) define a degenerate variety, namely an absolutely irreducible nonsingular hypersurface in some linear projective subspace.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Number of rational points of symmetric complete intersections over a finite field and applications

We study the set of common F_q-rational zeros of systems of multivariate symmetric polynomials with coefficients in a finite field F_q. We establish certain properties on these polynomials which imply that the corresponding set of zeros over the algebraic closure of F_q is a complete intersection with "good" behavior at infinity, whose singular locus has a codimension at least two or three. These results are used to estimate the number of F_q-rational points of the corresponding complete intersections. Finally, we illustrate the interest of these estimates through their application to certain classical combinatorial problems over finite fields.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Degeneracy loci and polynomial equation solving

Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(p\times s)$-matrix of coordinate functions of $C[V]$, where $s\ge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:=\{x\in V:\mathrm{rk} F(x)=p\}$. We associate with $(V,F)$ a descending chain of degeneracy loci of E (the generic polar varieties of $V$ represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded error probabilistic pseudo-polynomial time algorithm which we are going to design and which solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Polar varieties, Bertini's theorems and number of points of singular complete intersections over a finite field

Let P^n denote the n-dimensional projective space defined over the algebraic closure of a finite field F_q, let V contained P^n be a complete intersection defined over F_q of dimension r and singular locus of dimension at most s, and let π:V-->P^{s+1} be a "generic" linear mapping. We obtain an effective version of the Bertini smoothness theorem concerning π, namely an explicit upper bound of the degree of a proper Zariski closed subset of P^{s+1} which contains all the points defining singular fibers of π. For this purpose we make essential use of the concept of polar variety associated to the set of exceptional points of π. As a consequence of our effective Bertini theorem we obtain results of existence of smooth rational points of V, namely conditions on q which imply that V has a smooth q-rational point. Finally, for s=r-2 and s=r-3 we obtain estimates on the number of q-rational points of V, and we discuss how these estimates can be used in order to determine the average value set of "small" families of univariate polynomials with coefficients in F_q.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Singularities of symmetric hypersurfaces and an application to Reed-Solomon codes

We determine conditions on q for the nonexistence of deep holes of the standard Reed-Solomon code of dimension k over F_q generated by polynomials of degree k+d. Our conditions rely on the existence of q-rational points with nonzero, pairwise-distinct coordinates of a certain family of hypersurfaces defined over F_q. We show that the hypersurfaces under consideration 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 these hypersurfaces, from which the existence of q-rational points is established.

0 citations0 reviewsNo code linkedOpen access