Let $F:=\{f\in\mathbb{F}_q[X_1,\ldots,X_n]: \textrm{deg}(f)\leq d\}$ be the set containing all $n$-variate polynomials of degree less than or equal to $d$ over finite field $\mathbb{F}_q$ of prime power $q$. Suppose that $f$ is chosen uniformly at random from $F$ and let $N(f)$ be the number of distinct roots of $f$ in $\mathbb{F}_q$, namely $N(f)=\#\{(x_1,\ldots,x_n)\in\mathbb{F}_q^n:f(x_1,\ldots,x_n)=0\}$. I am interested in (the upper bound of) the $m$-th moment $\mathbb{E}[(N(f))^m]$ for $m\geq 1$.

By Schwartz–Zippel lemma, there is an upper bound $\mathbb{E}[(N(f))^m]\leq (dq^{n-1})^m$. Is this the best possible upper bound?

  • $\begingroup$ What do you mean by "the number of distinct roots of $f$ in $\mathbb{F}_q$" when $n>1$? Do you mean the number of points in $\mathbb{F}_q^n$ at which $f$ vanishes? $\endgroup$ – Daniel McLaury Mar 29 '16 at 4:46
  • $\begingroup$ Thanks. Yes that's what I mean. I updated the definition in the main text. $\endgroup$ – Han Mar 29 '16 at 4:55
  • $\begingroup$ when $n$ is fixed and $d \to \infty$ the number of roots $\to$ ? $\endgroup$ – reuns Mar 29 '16 at 5:13
  • 1
    $\begingroup$ For $n=1$ and $d\to\infty$, there are at most $q$ distinct roots where the function can be expressed as $f(x)=(x^q-x)g(x)$. In fact I am more interested in the cases $q>> n,m,d$, but still thanks. $\endgroup$ – Han Mar 29 '16 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.