Homogenous polynomial over finite field having only trivial zero Is there a way to construct homogenous polynomials of small degree over a certain finite field having only trivial zero?
For instance, the polynomial 
$f (a, b, c) = a^3 + b^3 + c^3 - 3abc - 3a^2b - 3b^2c - 3c^2a$ 
has only a trivial zero over $\mathbb{F}_{13}^3$ (I found this by trial and error). Is there a nice way to show that this polynomial has indeed the forementioned property? Can we find other polynomials over $\mathbb{F}_{13}$ with this property?
 A: If you can find a matrix $M$ of integers such that 
$$ \det (aI + b M + c M^2)   $$ is your polynomial, you have a method. For example, with
$$ M \; = \;  
 \left(  \begin{array}{rrr}
  0  &  1  &  0 \\
  0   &  0  &  1 \\
  1  &  0   &  0  
\end{array} 
  \right)  ,
  $$
we get
$$  aI + b M + c M^2 =
 \left(  \begin{array}{rrr}
  a  &  b  &  c \\
  c   &  a  &  b \\
  b  &  c   &  a  
\end{array} 
  \right)  .   $$
In this case 
$$ \det ( aI + b M + c M^2) = a^3 + b^3 + c^3 - 3 a b c.   $$
As a result, you can see at a glance that this is singular when $a=b=c,$ but it is also singular when $a+b+c = 0.$ So the determinant is $0$ in those two cases. In your case, if you find an appropriate matrix $M,$ which is the low-budget version of Jyrki's comment, you can do Gauss-Jordan elimination in the field of 13 elements to find out when  $ aI + b M + c M^2$ is singular, which will (as you say) be only when $$ a \equiv b \equiv c \equiv 0 \pmod {13}.  $$ 
I will see if I can come up with a matrix $M$ for your problem. I think Jyrki would know an elegant method for doing that, but I will do trial and error. 
EEDDIITTTT: if absolutely necessary, one may use a matrix where the determinant does not come out the same but is equivalent to your polynomial mod 13; so a $-3$ coefficient in your polynomial could become $-16,$ for instance. This variant is limited to one prime at a time...
EEDDDIIIIITT, Thursday, 6 March. It did not turn out as cleanly as I had expected, but it did have an identity matrix and (the negation of) a companion matrix, so everything still holds. In this case we find 
$$f (a, b, c) = a^3 + b^3 + c^3 - 3abc - 3a^2b - 3b^2c - 3c^2a = \det (a X + b Y + c I),$$
with
 $$ Y \; = \;  
 \left(  \begin{array}{rrr}
  0  &  -1  &  0 \\
  0   &  0  &  -1 \\
  1  &  -3   &  0  
\end{array} 
  \right)  ,
  $$
also $X = I + Y - Y^2,$ so
 $$ X \; = \;  
 \left(  \begin{array}{rrr}
  1  &  -1  &  -1 \\
  1   &  -2  &  -1 \\
  1  &  -2   &  -2  
\end{array} 
  \right)  .
  $$
All we need for the multiplication property to hold is to be able to express $Y^2, XY,YX, X^2$ as sums of $X,Y,I$ with integer coefficients. Note first that $Y^3 = 3 Y + I.$ Then we get
$$ Y^2 = Y - X + I,  $$
$$  XY = YX = -Y - X,  $$
$$  X^2 = - Y - 2 X + I.  $$
Done. Everything works. So, there is a middle ground. The identity matrix and a companion matrix, then some polynomial in the companion matrix. Live and learn. 
A: Supplementing Will's answer with the following suggestion for $M$. The key is to observe that the element $3$ is a cubic root of unity in the field $\Bbb{F}_{13}$. But there are no ninth roots of unity in that prime field, as $9\nmid (13-1)$. Therefore the polynomial $x^3-3\in\Bbb{F}_{13}[x]$ is irreducible (all its zeros are clearly of multiplicative order nine). Therefore we can use the companion matrix of $x^3-3$ as $M$ in Will's answer. IOW, pick
$$
M=\left(\begin{array}{ccc}0&0&3\\1&0&0\\0&1&0\end{array}\right).
$$
This gives
$$
a+b M+ c M^2=\left(\begin{array}{ccc}a&3c&3b\\b&a&3c\\c&b&a\end{array}\right),
$$
and also
$$
\det(a+b M+ c M^2)=a^3 + 3 b^3 - 9 a b c + 9 c^3.
$$
As $M$ generates the field $\Bbb{F}_{13^3}$, we know that $a+bM+cM^2$ is invertible for all non-trivial choices $a,b,c\in\Bbb{F}_{13}$.

Another way of looking at the end game is that the matrix $a+bM+cM^2$ is the matrix representing multiplication by $a+bx+cx^2$ in the quotient ring $\Bbb{F}_{13}[x]/\langle x^3-3\rangle$. As that quotient ring is a field by virtue of $x^3-3$ being irreducible, that multiplication is invertible when non-zero.
A: It is quite likely that the original cubic polynomial is the same, under a linear invertible change of variables with rational integer coefficients, to the one in the Corollary on the final page of Nowlan 1926. 
The behavior as far as represented primes $\pm 1 \pmod 9$ and primes giving only trivial zeroes $2,4,5,7 \pmod 9$ (as your 13: i am calling this "anisotropic") is identical, and the polynomials are quite similar. There are people on this site who could determine this by using  the number field in question, I imagine Jyrki could do that, so I left him an additional note. For me, I am doing some trial and error. 
EEEEDDDDIIITTT: It worked. The polynomial given by the OP is equivalent, by an invertible  linear change of variables with rational integer coefficients, to Nowlan's 1926 polynomial.
As a result, we have Nowlan's Corollary on the final page: for (positive) primes $p \equiv 2,4,5,7 \pmod 9,$ the OP's polynomial can only be divisible by $p$ if all three of his $a,b,c$ are divisible by $p.$ Meanwhile, for prime $q=3$ or $q \equiv \pm 1 \pmod 9,$ we can find rational integers $a,b,c$ such that $f(a,b,c) = p.$  Finally, if the polynomial integrally represents two numbers, it represents their product. So, we can tell exactly what numbers are integrally represented by the polynomial: for every prime factor $p \equiv 2,4,5,7 \pmod 9,$ the exponent must be divisible by $3.$ Those are the only restrictions. 
Meanwhile given Nowlan's 
$$ g(u,v,w) = u^3 + 6 u^2 w - 3 u v^2 + 3 uvw +9 u w^2 - v^3 + 3 v w^2 + w^3,  $$
we find
$$ g(a+c, -a-b, -a) = a^3 + b^3 + c^3 -3abc -3 a^2 b - 3 b^2 c - 3 c^2 a = f(a,b,c)  $$
We can invert this with
$$  f(-w, w-v,u+v) = g(u,v,w). $$
So There.
jagy@phobeusjunior:~$ gp
Reading GPRC: /etc/gprc ...Done.

                                               GP/PARI CALCULATOR Version 2.5.0 (released)
                                           i686 running linux (ix86/GMP kernel) 32-bit version
                                     compiled: Nov 17 2011, gcc-4.6.2 (Ubuntu/Linaro 4.6.2-2ubuntu1) 
                                              (readline v6.2 enabled, extended help enabled)

                                                  Copyright (C) 2000-2011 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500509
? 
? u = a+c
%1 = a + c
? 
? v = -a - b
%2 = -a - b
? 
? w = -a 
%3 = -a
? 
? p = u^3 - v^3 + w^3 + 3 * u * v * w - 3 * u * v^2 + 3 * v * w^2 + 9 * u * w^2 + 6 * u^2 * w 
%4 = a^3 - 3*b*a^2 + (-3*c^2 - 3*b*c)*a + (c^3 - 3*b^2*c + b^3)
? 


A: My answer addresses this question from a different point of view.
The following result has essentially been established in the previous answers.
Let $k$ be any finite field field of cardinality $q$ and let $F$ be cubic extension of $k$.
Then the norm form $h(x,y,x) = N_{F/k}(x \alpha + y \beta + z \gamma)$, where $\alpha, \beta, \gamma$ is any
vector space basis of $F/k$, is an anisotropic homogeneous form of degree 3 in the variables $x,y,z$ with coefficients in $k$.
Let $L = \alpha x + \beta y + \gamma z$.  This is a linear form with coefficients in $F$ and $h(x,y,z)$ is the product of the three conjugates of $L$ under the Galois action of $F/k$.
The claim now is that every ternary anisotropic form of degree $3$ with coefficients in a finite field is necessarily a norm form as above.
Here is a proof. There are a few subtle points where it is easy to make an error, so I am giving more details than one might expect.
Let $h \in k[x,y,z]$ be an anisotropic homogeneous form of degree 3.
Then $h$ is irreducible over $k$ because otherwise $h$ would have a linear factor over $k$ which would obviously have a nontrivial zero.
First suppose that $h$ is absolutely irreducible, which means that $h$ is irreducible over the algebraic closure of $k$.
Then $h$ defines an algebraic curve of degree 3 having genus 0 or 1.  (If the absolutely irreducible curve has degree $n$, then the genus is
$\le \frac{(n-1)(n-2)}{2}$.)
First suppose that the genus is 1.  Then $h$ is a nonsingular curve and the Weil estimate states that the number $N$ of projective zeros of $h$ over $k$ satisfies
$|N - (q+1)| \le 2\sqrt{q}$.  It is easy to check that we cannot have $N=0$.
Therefore $N\ge 1$ and $h$ is not anisotropic over $k$.
Now suppose that the genus is 0.  Then $h$ has a singular point defined over the algebraic closure of $k$.  There can be at most one singular point because each singular point subtracts at least one from the genus and the genus is non-negative. It follows that the singular point must be defined over $k$ (because if not, the Galois action would produce another singular point), and thus again $h$ is not anisotropic over $k$.
Therefore $h$ is not absolutely irreducible.  Since $h$ has degree 3, $h$ must have a linear factor defined over some finite extension.  Considering the Galois action again, and remembering that $h$ has no linear factor defined over $k$, it follows that $h$ is a product of 3 conjugate linear factors defined over a cubic extension of $k$.  This means that $h$ must be a norm form as defined above.
Therefore any anisotropic cubic form in 3 variables defined over a finite field must be a norm form.  The previous answers discuss how to make this explicit from a computational view.
