3
$\begingroup$

Let $N(x^{n}=a)$ denote the number of solution to $x^{n}=a$ in $\mathbb{F_{p}}$

Lemma: $N(x^{n}=a)=\sum_{\chi^{n}=\epsilon}\chi{(a)}$ where the sum is taken over all characters. In particular, $N(x^{2}=a)=1+(^{a}_{p})$, where $(^{a}_{p})$ is the Legendre symbol.

Question1: Why is it that $N(x^{n}+y^{n}=1)=\sum_{a+b=1}N(x^{n}=a)N(y^{n}=b)$?

Question2: By direct substitution, we should get that $N(x^{2}+y^{2}=1)=p+\sum_{a}(^{a}_{p})+\sum_{b}(^{b}_{p})+\sum_{a+b=1}(^{a}_{p})(^{b}_{p})$, but I am not able to get this because I don't know how to deal with the summation in two variables.

  • 0
    @MattE: Ah, I see Alon switched the $=$ and $)$ around. That is one permutation I failed to contemplate! I also mentally took the premise to mean what was intended rather than what was written...2012-03-03

1 Answers 1

4

Summation in two variables can be simplified when one of the variables is determined by the other one. Here we have $a+b=1$, so we can simply replace $b$ with $1-a$ in the inner expression and sum over all $a\in\mathbb{F}$. However doing this is not always necessary to derive formulas or solutions.

Now for question 1, note that any solution $(x,y)$ to $x^n+y^n=1$ will correspond to $u$ and $v$ such that their sum $u+v=1$; simply take $u=x^n$ and $v=y^n$. So we can take the set of all solutions and partition them into cells, each cell is labelled by $(u,v)$ such that $u+v=1$ and inside each cell are all the $x$ and $y\in\mathbb{F}$ such that $x^n=u$ and $y^n=v$. Since these $x$ and $y$ are independent of each other when $u$ and $v$ are fixed, we conclude tha the number of solutions inside the cell labelled $(u,v)$ is just the product of $N(x^n=u)$ and $N(y^n=v)$. Summing over the available indices gives

$N(x^n+y^n=1)=\sum_{u+v=1}N(x^n=u)N(y^n=v).$

For question 2, we use direct substitution:

$N(x^2+y^2=1)=\sum_{u+v=1}N(x^2=u)N(y^2=v)=\sum_{u+v=1}\left(1+\left(u\over p\right)\right)\left(1+\left(v \over p\right)\right)$

Multiply out the summand on the RHS and split into multiple summations. Note that if you are summing over $u+v=1$ but the summand only depends on $u$ (respectively, $v$), then we need only note that for any $u$ (resp. $v$) there is exactly one $v$ (resp. $u$) to make $(u,v)$ a solution to $u+v=1$, so we are effectively just summing over all $u\in\mathbb{F}$ in that case!

n.b. I replaced $a$ and $b$ with $u$ and $v$ here.

  • 0
    @anon, Thanks for the excellent reply.2012-03-03