2
$\begingroup$

Let $q$ be a prime number and $n$ an integer.

Is there some number theoretic condition involving the numbers $q,n$ that can tell me when is the polynomial $$x^2+xy+y^2\in\mathbb{F}_{q^n}[x,y]$$

doesn't have roots other than ones with $x=y$.

$\endgroup$
  • $\begingroup$ Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$... $\endgroup$ – Dirk Jan 23 at 9:32
  • $\begingroup$ Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = \left( \frac{-1 \pm \sqrt{-3}}{2} \right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $\mathbb{F}_{q^{n}}\left[x,y\right]$ has no roots if and only if $q \neq 2$ and $\mathbb{F}_{q^{n}}$ has no square roots of $-3$. $\endgroup$ – Adam Higgins Jan 23 at 9:33
2
$\begingroup$

$\textbf{EDIT:}$ As @JyrkiLahtonen pointed out in the comments, there is a much simpler argument here. $\mathbb{F}_{q^{n}}$ contains a primitive third root of unity if and only if $3$ divides $q^{n} - 1$. This is because the multiplicative group of a field of size $q^{n}$ is always cyclic of order $q^{n} - 1$, and a cyclic group contains an element of prime order $p$ for every prime dividing its size. Thus $x^{2} + xy + y^{2}$ has non-zero solutions in $\mathbb{F}_{q^{n}}$ whenever $q^{n} \equiv 1 \ (\text{mod} \ 3)$. Thus if $q \equiv 1 \ (\text{mod} \ 3)$ then our equation has non-zero solutions, else $q \equiv 2 \ (\text{mod} \ 3)$ and then $q^{n} \equiv 1 \ (\text{mod} \ 3)$ if and only if $n$ is even. Giving the complete solution that this equation has no non-zero solutions only when $q \equiv 2 \ (\text{mod} \ 3)$ and $n$ is odd.

I'm gonna leave my original attempt up in case it is at all enlightening for anyone.


Following on from my answer in the comments. Ignoring the solution $x=y=0$ which you have for every $q$, and suppose also for now that $q \neq 2$. Then by the quadratic formula $x^{2} + xy + y^{2} = 0$ only when

$$ x = \left( \frac{-1 \pm \sqrt{-3}}{2} \right) y, $$

and so are interested when the field $\mathbb{F}_{q^{n}}$ contains square roots of $-3$. Let us first consider the case $n=1$. I'm not sure how much elementary number theory you know, but the problem of whether or not the finite field of a prime number of elements contains the square root of a number is given the Legendre symbol. That is for $q$ a prime number, and $a$ an integer, then

$$ \left( \frac{a}{q} \right) = \left\{ \begin{array}{l l} 1, & \text{if} \ a \not\equiv 0 \ (\text{mod} \ q) \ \text{is a quadratic residue in} \ \mathbb{F}_{q} \\ -1, & \text{if} \ a \not\equiv 0 \ (\text{mod} \ q) \ \text{is not a quadratic residue in} \ \mathbb{F}_{q} \\ 0, & \text{if} \ a \equiv 0 \ (\text{mod} \ q) \end{array}\right. $$

where the phrase "quadratic residue" exactly means that it is the square of something in that field. Thus this problem is reduced this figuring out the value of $\left( \frac{-3}{q} \right)$. This symbol has the following properties.

$$ \left( \frac{1}{q} \right) = 1 \ \text{for all primes} \ q, $$ $$ \left( \frac{ab}{q} \right) = \left( \frac{a}{q} \right) \left( \frac{b}{q} \right) \ \text{for all integers} \ a,b \ \text{and primes} \ q, $$
$$ \left( \frac{a + kq}{q} \right) = \left(\frac{a}{q}\right) \ \text{for all integers} \ a,k \ \text{and primes} \ q. $$

We also have quadratic reciprocity. That is, if $p,q$ are two distinct odd primes then

$$ \left( \frac{p}{q} \right)\left( \frac{q}{p} \right) = (-1)^{\frac{(p-1)(q-1)}{4}} $$

Using these properties we can see that (so long as $q \neq 3$)

$$ \left( \frac{-3}{q} \right) = \left( \frac{-1}{q} \right)\left( \frac{3}{q} \right) = (-1)^{\frac{q-1}{2}}\left( \frac{-1}{q} \right)\left( \frac{q}{3} \right) $$

Now using these (and maybe Euler's Criterion , one works out that

$$ \left( \frac{-1}{q} \right) = \left\{ \begin{array}{l l} 1, & \text{if} \ q \equiv 1 \ (\text{mod} \ 4) \\ -1,& \text{if} \ q \equiv 3 \ (\text{mod} \ 4) \end{array}\right. $$

and

$$ \left( \frac{3}{q} \right) = \left\{ \begin{array}{l l} 1, & \text{if} \ q \equiv 1,11 \ (\text{mod} \ 12) \\ -1,& \text{if} \ q \equiv 5,7 \ (\text{mod} \ 12) \end{array}\right. $$

This allows us to calculate that

$$ \left( \frac{-3}{q} \right) = \left\{ \begin{array}{l l} 1, & \text{if} \ q \equiv 1,7 \ (\text{mod} \ 12) \\ -1,& \text{if} \ q \equiv 5,11 \ (\text{mod} \ 12) \end{array}\right. $$

This answers your question when $n=1$. When $n = 2$ we need to use a little bit of algebra. Again suppose that $q \neq 2$, and suppose we have a case where $\mathbb{F}_{q}$ does not have a square root of $-3$, then $x^{2} + 3$ is irreducible in $\mathbb{F}_{q}[x]$, and so can be used to generated the field extension $\mathbb{F}_{q^{2}}$ over $\mathbb{F}_{q}$, thus since all finite fields of the same order are isomorphic $\mathbb{F}_{q^{2}}$ must always contain a square root of $-3$. Thus any field extension of $\mathbb{F}_{q^{2}}$ contains a square root of $-3$ and thus $\mathbb{F}_{q^{n}}$ contains a square root of $-3$ whenever $n$ is even.

I know this isn't a complete answer, but I hope it goes some way to showing the sorts of things you need to think about when tackling this question. See if you can use these ideas to tackle the case when $n$ is not even, or when $q = 2, 3$.

$\endgroup$
  • 2
    $\begingroup$ This is the right idea. It might be simpler to explain that $\Bbb{F}_{q^n}$ contains $\sqrt{-3}$ if and only if it contains a third primitive root of unity $\omega=(-1+\sqrt{-3})/2$ if and only if $3\mid q^n-1$ (by cyclicity of $\Bbb{F}_{q^n}^*$). $\endgroup$ – Jyrki Lahtonen Jan 23 at 10:23
  • 1
    $\begingroup$ Yes. The group $\Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three. $\endgroup$ – Jyrki Lahtonen Jan 23 at 10:27
  • 1
    $\begingroup$ Of course, $\Bbb{F}_q[\sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $\omega$ is in there whenever either $q\equiv1\pmod3$ or $n$ is even. $\endgroup$ – Jyrki Lahtonen Jan 23 at 10:28
  • 1
    $\begingroup$ Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $\mathbb{F}_{q^{n}}^{\times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group. $\endgroup$ – Adam Higgins Jan 23 at 10:29
  • 1
    $\begingroup$ @AdamHiggins But when $q=2$ we cannot use the quadratic formula ? $\endgroup$ – user621824 Jan 23 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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