Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can every function $\psi ~\colon \mathbb{F_{p}^n} \to \mathbb{F_{p}}$ be regarded as a polynomial function for some polynomial in $\mathbb{F_{p}[x_1, \ldots,x_n]}$?

I believe this is true, but am having trouble proving it.

share|cite|improve this question
up vote 16 down vote accepted

For each point $y=(y_1,...,y_n)$ in $\mathbb{F}_p^n$, the polynomial

$$\prod_{i=1}^n\prod_{z_i=0\atop z_i\neq y_i}^{p-1}(x_i-z_i)$$

is non-zero at $y$ and zero everywhere else, so these polynomials form a basis of the function space.

share|cite|improve this answer
Note that this shows more generally that you can interpolate a function defined on any finite subset of $F^n$ with polynomials in $F[x_1, ... x_n]$. The crucial observation from here is that $\mathbb{F}_p^n$ is, well, a finite subset of itself. – Qiaochu Yuan Mar 6 '11 at 22:11

The answer is yes. Suppose that the elements of $F_p$ are given by $\{{a_1,\dots,a_p\}}$. First, let us note that the function $f(x) =1$ if $x=a_i$, and $f(x)=0$ otherwise is a polynomial, given by (up to a constant) $f(x) = (x-a_1)\dots \widehat{(x-a_i)} \dots (x-a_p)$.

Let us denote this function by $f_i$. For an $n$-tuple $(a_{i_1},\dots,a_{i_n})$ let $f_{i_1,\dots,i_n}(x_1,\dots,x_n) = f_{i_1}(x_1) \cdot f_{i_2}(x_2) \cdot \dots \cdot f_{i_n}(x_n)$.

Now, given a function $f:F_p^n \to F_p$, we may write it as:

$f(x_1,\dots,x_n) = \sum_{ (a_{i_1},\dots,a_{i_n}) \in F_p^n } f_{i_1,\dots,i_n}(x) f(a_{i_1},\dots,a_{i_n})$ which is a finite sum of polynomials, and therefore, a polnomial.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.