4
$\begingroup$

The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: t_1,t_2 \in \mathbb{F}_p \}$ be the $2$-dimensional vector space over $\mathbb{F}_p$. Denote by $\text{Sym}(\mathcal{V})$ the group of bijections on $\mathcal{V}$. Then any element of $\text{Sym}(\mathcal{V})$ is defined by a pair $ \langle f_1(x_1,x_2),f_2(x_1,x_2) \rangle $ of functions on $\mathcal{V}$. Since $\mathbb{F}_p$ is a finite field, we can assume that $f_1$ and $f_2$ are polynomials (of degree at most $p-1$ in each variable). Now, suppose we are given an arbitrary pair $$ \langle g_1(x_1,x_2),g_2(x_1,x_2) \rangle, $$ where $g_1,g_2 \in \mathbb{F}_p[x_1,x_2]$. Can we determine if the map $$ (x_1,x_2) \mapsto (g_1(x_1,x_2),g_2(x_1,x_2)) $$ induces:

  • a permutation on $\mathcal{V}$?
  • a $p^2$-cycle on $\mathcal{V}$?

Update: There are plenty of types of pairs which are obvious bijections. For example, so called "triangular": $\alpha= \langle x_1+f_1,x_2+f_2(x_1) \rangle$, where $f_1 \in \mathbb{F}_p$ and $f_2(x_1) \in \mathbb{F}_p[x_1]$. Here, $\alpha$ is a $p^2$-cycle if and only if $f_1 \neq 0$ and $\text{deg}f_2 = p-1$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ When you say every function can be represented as a pair of polynomials of degree $p-1$, you mean in each variable. The degree of a polynomial in two variables is something else. Since your question is a finite one, the answer is clearly yes, so you must mean something else. Do you want a computationally efficient algorithm (perhaps polynomial in $\log p$)? Do you want an explicit criterion in terms of the coefficients of the $g_i$? Can the $g_i$ have any degree, even bigger than $p-1$? $\endgroup$
    – Felipe Voloch
    Jul 30, 2014 at 21:18
  • $\begingroup$ Thanks, @FelipeVoloch. It's definitely should be "in each variable", my fault, sorry (I fixed it). I was thinking about an explicit criterion in terms of the coefficients and degrees. But I suspect that there is no one (at least for the general case of $n$ dimensions). Maybe there are some sufficient conditions? $\endgroup$
    – user35603
    Jul 30, 2014 at 22:03

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.