Level sets of the polynomial function $𝑥^2+𝑦^2−𝑥+𝑦−𝑎𝑥𝑦$ over $\mathbb{F}_𝑝$

Question

Let 𝑝 be an odd prime and assume $𝑥^2+ax+1$ is irreducible over the field $\mathbb{F}_p$. The polynomial function

$$\Psi:\mathbb{F}_p^2⟶\mathbb{F}_p,\quad (x,y)\mapsto 𝑥^2+𝑦^2−x+y-axy$$

is surjective, as proved here: Image of a polynomial function $x^2+y^2-x+y-axy$ over $\mathbb{F}_p$.

I would like to compute a set of representatives of the classes of the kernel of $\Psi$ (i.e., the relation $\ker(\Psi)=\{(x,y,t,w)\in \mathbb{F}_p^4, \, \Psi(𝑥,𝑦)=\Psi(t,w)\})$. So basically I would like to have an explicit set of $p-1$ elements of $\mathbb{F}_p^2$ that take on all the nonzero values in $\mathbb{F}_p$ when you apply $\Psi$. (Finding a solution to $\Psi(x,y)=0$ is obvious.)

Is there a way to do this in general, regardless of the value of $p$?

Answer 1

Here is a solution for $\frac{p-1}{2}$ of the level sets. Let $\varphi=x^2+y^2-x+y-axy$, and assume that $a\not=\pm 2$.

Following the suggestion in https://mathoverflow.net/q/356936 we first apply the change of variables given by $x= z+(a/2)y$ to obtain $$\varphi=z^2-z-b(y^2+(1+a/2)^{-1}y),$$ where $b=a^2/4-1$. Then letting $u=z-1/2$, $v=y+(2+a)^{-1}$, and $c=\frac{-1}{4}\left(\frac{1-a/2}{1+a/2}\right)$ we have $$\varphi=u^2-bv^2+c.$$

To compute the level sets you need to compute the fibres $\varphi^{-1}(d)$ for an image point $d$. If $d-c$ is a quadratic residue, then $d-c=e^2$ and so letting $s=u/e$ and $t=v/e$ we obtain: $$s^2-bt^2=1.$$

Having all solutions $(s,t)$ determines the solutions $(u,v)$, in turn the solutions $(y,z)$, and in turn the solutions $(x,y)$.

So it suffices to find the solutions to $s^2-bt^2=1.$ But such solutions are explicitly determined in:

Tekcan, Ahmet, The number of rational points on conics $C_{p,k}:x^2−ky^2=1$ over finite fields $\mathbb{F}_p$. Int. J. Math. Sci. 1 (2007), no. 2, 150–153.

MathSciNet Summary:

"Let $p$ be a prime number, $\mathbb{F}_p$ be a finite field, and let $k\in \mathbb{F}_p^*$. In this paper, we consider the number of rational points on conics $C_{p,k}: x^2−ky^2=1$ over $\mathbb{F}_p$. We prove that the order of $C_{p,k}$ over $\mathbb{F}_p$ is $p−1$ if $k$ is a quadratic residue mod $p$ and is $p+1$ if $k$ is not a quadratic residue mod $p$....''

I am not sure what happens when $d-c$ is a non-residue (I haven't tried), but since $\varphi$ is onto and $(p-1)/2$ of the non-zero values are quadratic residues, this gets you roughly half way.