Skip to main content
2 of 3
formatting, added tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

$\delta$-equidistributed polynomials over finite fields

I'm trying to show that a polynomial over finite (prime) field is "close enough" to being equidistributed over its range. A polynomial $p(\cdot)$ from $\mathbb{F}^n$ to $\mathbb{F}$ is $\delta$-equidistributed is $\forall c\in \mathbb{F}, |\{x\in \mathbb{F}^n : p(x)=c\}|=(1\pm \delta)|\mathbb{F}|$.

I found a paper by Green and Tao that deals with it. They define the notion of rank of a polynomial: $\operatorname{rank}_{d−1}(P)$ is the smallest integer $k$ such that there exist degree $d−1$ polynomials $q_1(X), ..., q_k(x)$, and a function $B : \mathbb{F}^k → \mathbb{F}$, s.t. $p(X) = B(q_1(X), ..., q_k(X))$.

From theorem 1.7 in the paper, it follows that if a polynomial has high degree, it is equidistributed. However, I couldn't figure out the exact parameter/relationship between the equidistribution parameter $\delta$ and the rank needed to achieve that.

So my question is how high the rank should be (as a function of $\delta$) for a polynomial to be equidistributed?

GWB
  • 301
  • 1
  • 3