Mixing
Roots of lacunary polynomials over a finite field
Clash Royale CLAN TAG#URR8PPP
up vote
12
down vote
favorite
If $P$ is a polynomial over the field $mathbb F_q$ of degree at most $q-2$ with $k$ nonzero coefficients, then $P$ has at most $(1-1/k)(q-1)$ distinct nonzero roots.
Does this fact have any standard name / reference / proof / refinements / extensions?
reference-request polynomials finite-fields
asked Aug 17 at 14:31
Seva
12k13497
add a comment |Â
up vote
12
down vote
favorite
If $P$ is a polynomial over the field $mathbb F_q$ of degree at most $q-2$ with $k$ nonzero coefficients, then $P$ has at most $(1-1/k)(q-1)$ distinct nonzero roots.
Does this fact have any standard name / reference / proof / refinements / extensions?
reference-request polynomials finite-fields
asked Aug 17 at 14:31
Seva
12k13497
4
What is $p$? Do you mean $(q-1)$ instead of $(p-1)$?
– Noam D. Elkies
Aug 17 at 14:43
add a comment |Â
up vote
12
down vote
favorite
up vote
12
down vote
favorite
If $P$ is a polynomial over the field $mathbb F_q$ of degree at most $q-2$ with $k$ nonzero coefficients, then $P$ has at most $(1-1/k)(q-1)$ distinct nonzero roots.
Does this fact have any standard name / reference / proof / refinements / extensions?
reference-request polynomials finite-fields
asked Aug 17 at 14:31
Seva
12k13497
If $P$ is a polynomial over the field $mathbb F_q$ of degree at most $q-2$ with $k$ nonzero coefficients, then $P$ has at most $(1-1/k)(q-1)$ distinct nonzero roots.
Does this fact have any standard name / reference / proof / refinements / extensions?
reference-request polynomials finite-fields
asked Aug 17 at 14:31
Seva
12k13497
edited Aug 17 at 14:45
asked Aug 17 at 14:31
Seva
12k13497
asked Aug 17 at 14:31
Seva
12k13497
asked Aug 17 at 14:31
Seva
12k13497
12k13497
4
What is $p$? Do you mean $(q-1)$ instead of $(p-1)$?
– Noam D. Elkies
Aug 17 at 14:43
add a comment |Â
4
What is $p$? Do you mean $(q-1)$ instead of $(p-1)$?
– Noam D. Elkies
Aug 17 at 14:43
4
4
What is $p$? Do you mean $(q-1)$ instead of $(p-1)$?
– Noam D. Elkies
Aug 17 at 14:43
What is $p$? Do you mean $(q-1)$ instead of $(p-1)$?
– Noam D. Elkies
Aug 17 at 14:43
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
13
down vote
Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $mathbbF_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^q-1-1$. This is why the following argument looks natural and I expect something similar to appear in other extensions of this result.
Denote $P(x)=sum_i=1^k c_i x^a_i$, $0=a_1<a_2<a_3<dots<a_kleqslant q-2<a_k+1:=q-1$. Choose $iin 1,2,dots,k$ such that $a_i+1-a_igeqslant (q-1)/k$ and reduce the polynomial $Q(x)=x^q-1-a_i+1P(x)$ modulo $x^q-1-1$. The remainder $R(x)$ has the same non-zero roots as $P$, but $deg R(x)leqslant max (q-1+a_i-a_i+1,a_k-a_i+1)=q-1+a_i-a_i+1leqslant (q-1)(1-frac1k)$.
This method allows to get something for the polynomials in many variables. Say, if a non-zero polynomial $P(x_1,dots,x_n)$ has degree at most $q-2$ in each variable and has at most $M$ non-zero-coefficients, we may estimate the number of points $a=(a_1,dots,a_n)in (mathbbF_q^*)^n$ for which $P(a)=0$. Namely, choose some ``forbidden'' set $Omegain 0,1,dots,q-2^n$ and look for a monomial $x_1^c_1dots x_n^c_n$ for which all monomials of the reduced polynomial $x_1^c_1dots x_n^c_nP(x_1,dots,x_n)$ (reduced modulo the ideal $langle x_1^q-1-1,dots,x_n^q-1-1rangle$, that does not change the zeroes in $(mathbbF_q^*)^n$) do not belong to $Omega$. If we choose random exponents $c_1,dots,c_n$, each specific monomial belongs to $Omega$ after multiplying by $x_1^c_1dots x_n^c_n$ and reduction with probability $|Omega|/(q-1)^n$. Thus if $Mcdot |Omega|<(q-1)^n$, we may avoid $Omega$ by suitable multiplication and reduction. For certain choices of $Omega$ this gives some upper bounds on the number of zeroes by De Millo -- Lipton -- Schwartz -- Zippel -- Alon -- Füredi -- $dots$ theory.
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
13
down vote
Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $mathbbF_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^q-1-1$. This is why the following argument looks natural and I expect something similar to appear in other extensions of this result.
Denote $P(x)=sum_i=1^k c_i x^a_i$, $0=a_1<a_2<a_3<dots<a_kleqslant q-2<a_k+1:=q-1$. Choose $iin 1,2,dots,k$ such that $a_i+1-a_igeqslant (q-1)/k$ and reduce the polynomial $Q(x)=x^q-1-a_i+1P(x)$ modulo $x^q-1-1$. The remainder $R(x)$ has the same non-zero roots as $P$, but $deg R(x)leqslant max (q-1+a_i-a_i+1,a_k-a_i+1)=q-1+a_i-a_i+1leqslant (q-1)(1-frac1k)$.
This method allows to get something for the polynomials in many variables. Say, if a non-zero polynomial $P(x_1,dots,x_n)$ has degree at most $q-2$ in each variable and has at most $M$ non-zero-coefficients, we may estimate the number of points $a=(a_1,dots,a_n)in (mathbbF_q^*)^n$ for which $P(a)=0$. Namely, choose some ``forbidden'' set $Omegain 0,1,dots,q-2^n$ and look for a monomial $x_1^c_1dots x_n^c_n$ for which all monomials of the reduced polynomial $x_1^c_1dots x_n^c_nP(x_1,dots,x_n)$ (reduced modulo the ideal $langle x_1^q-1-1,dots,x_n^q-1-1rangle$, that does not change the zeroes in $(mathbbF_q^*)^n$) do not belong to $Omega$. If we choose random exponents $c_1,dots,c_n$, each specific monomial belongs to $Omega$ after multiplying by $x_1^c_1dots x_n^c_n$ and reduction with probability $|Omega|/(q-1)^n$. Thus if $Mcdot |Omega|<(q-1)^n$, we may avoid $Omega$ by suitable multiplication and reduction. For certain choices of $Omega$ this gives some upper bounds on the number of zeroes by De Millo -- Lipton -- Schwartz -- Zippel -- Alon -- Füredi -- $dots$ theory.
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
add a comment |Â
up vote
13
down vote
Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $mathbbF_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^q-1-1$. This is why the following argument looks natural and I expect something similar to appear in other extensions of this result.
Denote $P(x)=sum_i=1^k c_i x^a_i$, $0=a_1<a_2<a_3<dots<a_kleqslant q-2<a_k+1:=q-1$. Choose $iin 1,2,dots,k$ such that $a_i+1-a_igeqslant (q-1)/k$ and reduce the polynomial $Q(x)=x^q-1-a_i+1P(x)$ modulo $x^q-1-1$. The remainder $R(x)$ has the same non-zero roots as $P$, but $deg R(x)leqslant max (q-1+a_i-a_i+1,a_k-a_i+1)=q-1+a_i-a_i+1leqslant (q-1)(1-frac1k)$.
This method allows to get something for the polynomials in many variables. Say, if a non-zero polynomial $P(x_1,dots,x_n)$ has degree at most $q-2$ in each variable and has at most $M$ non-zero-coefficients, we may estimate the number of points $a=(a_1,dots,a_n)in (mathbbF_q^*)^n$ for which $P(a)=0$. Namely, choose some ``forbidden'' set $Omegain 0,1,dots,q-2^n$ and look for a monomial $x_1^c_1dots x_n^c_n$ for which all monomials of the reduced polynomial $x_1^c_1dots x_n^c_nP(x_1,dots,x_n)$ (reduced modulo the ideal $langle x_1^q-1-1,dots,x_n^q-1-1rangle$, that does not change the zeroes in $(mathbbF_q^*)^n$) do not belong to $Omega$. If we choose random exponents $c_1,dots,c_n$, each specific monomial belongs to $Omega$ after multiplying by $x_1^c_1dots x_n^c_n$ and reduction with probability $|Omega|/(q-1)^n$. Thus if $Mcdot |Omega|<(q-1)^n$, we may avoid $Omega$ by suitable multiplication and reduction. For certain choices of $Omega$ this gives some upper bounds on the number of zeroes by De Millo -- Lipton -- Schwartz -- Zippel -- Alon -- Füredi -- $dots$ theory.
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
add a comment |Â
up vote
13
down vote
up vote
13
down vote
Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $mathbbF_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^q-1-1$. This is why the following argument looks natural and I expect something similar to appear in other extensions of this result.
Denote $P(x)=sum_i=1^k c_i x^a_i$, $0=a_1<a_2<a_3<dots<a_kleqslant q-2<a_k+1:=q-1$. Choose $iin 1,2,dots,k$ such that $a_i+1-a_igeqslant (q-1)/k$ and reduce the polynomial $Q(x)=x^q-1-a_i+1P(x)$ modulo $x^q-1-1$. The remainder $R(x)$ has the same non-zero roots as $P$, but $deg R(x)leqslant max (q-1+a_i-a_i+1,a_k-a_i+1)=q-1+a_i-a_i+1leqslant (q-1)(1-frac1k)$.
This method allows to get something for the polynomials in many variables. Say, if a non-zero polynomial $P(x_1,dots,x_n)$ has degree at most $q-2$ in each variable and has at most $M$ non-zero-coefficients, we may estimate the number of points $a=(a_1,dots,a_n)in (mathbbF_q^*)^n$ for which $P(a)=0$. Namely, choose some ``forbidden'' set $Omegain 0,1,dots,q-2^n$ and look for a monomial $x_1^c_1dots x_n^c_n$ for which all monomials of the reduced polynomial $x_1^c_1dots x_n^c_nP(x_1,dots,x_n)$ (reduced modulo the ideal $langle x_1^q-1-1,dots,x_n^q-1-1rangle$, that does not change the zeroes in $(mathbbF_q^*)^n$) do not belong to $Omega$. If we choose random exponents $c_1,dots,c_n$, each specific monomial belongs to $Omega$ after multiplying by $x_1^c_1dots x_n^c_n$ and reduction with probability $|Omega|/(q-1)^n$. Thus if $Mcdot |Omega|<(q-1)^n$, we may avoid $Omega$ by suitable multiplication and reduction. For certain choices of $Omega$ this gives some upper bounds on the number of zeroes by De Millo -- Lipton -- Schwartz -- Zippel -- Alon -- Füredi -- $dots$ theory.
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $mathbbF_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^q-1-1$. This is why the following argument looks natural and I expect something similar to appear in other extensions of this result.
Denote $P(x)=sum_i=1^k c_i x^a_i$, $0=a_1<a_2<a_3<dots<a_kleqslant q-2<a_k+1:=q-1$. Choose $iin 1,2,dots,k$ such that $a_i+1-a_igeqslant (q-1)/k$ and reduce the polynomial $Q(x)=x^q-1-a_i+1P(x)$ modulo $x^q-1-1$. The remainder $R(x)$ has the same non-zero roots as $P$, but $deg R(x)leqslant max (q-1+a_i-a_i+1,a_k-a_i+1)=q-1+a_i-a_i+1leqslant (q-1)(1-frac1k)$.
This method allows to get something for the polynomials in many variables. Say, if a non-zero polynomial $P(x_1,dots,x_n)$ has degree at most $q-2$ in each variable and has at most $M$ non-zero-coefficients, we may estimate the number of points $a=(a_1,dots,a_n)in (mathbbF_q^*)^n$ for which $P(a)=0$. Namely, choose some ``forbidden'' set $Omegain 0,1,dots,q-2^n$ and look for a monomial $x_1^c_1dots x_n^c_n$ for which all monomials of the reduced polynomial $x_1^c_1dots x_n^c_nP(x_1,dots,x_n)$ (reduced modulo the ideal $langle x_1^q-1-1,dots,x_n^q-1-1rangle$, that does not change the zeroes in $(mathbbF_q^*)^n$) do not belong to $Omega$. If we choose random exponents $c_1,dots,c_n$, each specific monomial belongs to $Omega$ after multiplying by $x_1^c_1dots x_n^c_n$ and reduction with probability $|Omega|/(q-1)^n$. Thus if $Mcdot |Omega|<(q-1)^n$, we may avoid $Omega$ by suitable multiplication and reduction. For certain choices of $Omega$ this gives some upper bounds on the number of zeroes by De Millo -- Lipton -- Schwartz -- Zippel -- Alon -- Füredi -- $dots$ theory.
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
edited Aug 20 at 7:30
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
answered Aug 17 at 16:19
Fedor Petrov
44.6k5106211
44.6k5106211
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f308537%2froots-of-lacunary-polynomials-over-a-finite-field%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
4
What is $p$? Do you mean $(q-1)$ instead of $(p-1)$?
– Noam D. Elkies
Aug 17 at 14:43