4
$\begingroup$

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?

$\endgroup$
4
  • $\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, 2016 at 4:46
  • $\begingroup$ Thanks. Yes that's what I mean. I updated the definition in the main text. $\endgroup$
    – Han
    Mar 29, 2016 at 4:55
  • $\begingroup$ when $n$ is fixed and $d \to \infty$ the number of roots $\to$ ? $\endgroup$
    – reuns
    Mar 29, 2016 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, 2016 at 5:32

0

Reset to default

You must log in to answer this question.