# Generator matrices of codes

I need a little help please.

The Klein curve $X\subset \mathbb{P}^{2}$ given by homogeneous equation: $x^{3}y+y^{3}z+z^{3}x=0$.

1. Show that the space $L(m(z))$ is generated by elements of the form $\left \{x^{i}y^{j}|2i+3j\leq 3m, i-2j \leq m \right \}$. My first question: How to prove this?

2. From this generator system, select a basis of $L(m(z))$ and write out generator matrices of codes$(X,P,m(z))_{L}$ for $m=2,3,5$ where $P=X(F_{8})\setminus \left \{ Q_{1},Q_{2} \right \}$ $\left ( Q_{1}=(1:0:0);Q_{2}=(0:1:0) \right )$

I have found basis for $m=2,3,5$ . For instance, for $m=2$ I got a basis $\left \{ 1,x,x^{2},y,yx,y^{2} \right \}$. And my second question: What is its generator matrix?

Thanks a lot!

Added: 24 rational points that i have founded:

$P_{\infty }= (0,1,0);P_{1}=(1,0,0);P_{2}=(0,0,1)$;

$P_{3}=(1,\alpha^{4} ,\alpha^{2});P_{4}= (\alpha^{4},1,\alpha^{2});P_{5}=(\alpha^{2} \alpha^{4},1)$;

$P_{6}=(1,\alpha^{5},\alpha^{5});P_{7}=(\alpha^{5},1 ,\alpha^{5}) P_{8}= (\alpha^{5},\alpha^{5},1)$;

$P_{9}=(\alpha,\alpha^{2},1);P_{10}=(1,\alpha,\alpha^{2});P_{11}=(\alpha^{2},1 ,\alpha)$;

$P_{12}= (\alpha^{3},1,\alpha^{3}); P_{13}=(\alpha^{3},\alpha^{3},1);P_{14}=(1,\alpha^{3},\alpha^{3});$

$P_{15}=(1,1 ,\alpha); P_{16}=(\alpha,1,1);P_{17}=(1,\alpha,1);$

$P_{18}=(\alpha^{5},\alpha ,1); P_{19}=(1,\alpha^{5},\alpha);P_{20}=(\alpha,1,\alpha^{5});$

$P_{21}=(\alpha^{4},\alpha^{3} ,1); P_{22}=(1,\alpha^{4},\alpha^{3});P_{23}=(\alpha^{3},1,\alpha^{4});$

-
Are you sure that the homogeneous coordinates shouldn't be $X,Y,Z$? The sections of a divisor are functions on the curve (certainly in coding theory you need functions to be evaluated at the rational points of the curve!), but homogeneous coordinates are not well-defined functions! – Jyrki Lahtonen Apr 7 '12 at 16:31

As you are interested in $F_8$, we can assume that we are working over fields of characteristic two.

The notation of the question seems to be a bit inconsistent?! For $x$ and $y$ to be functions on (an affine part of) the curve, they need to be ratios of forms of same degree - more often than not $x=X/Z$ and $y=Y/Z$. I assume that the equation of the curve is actually given in terms of the homogeneous coordinates: $$X^3Y+Y^3Z+Z^3X=0.$$ Sorry about mangling your question in this way, but I honestly cannot understand it otherwise.

Dehomogenization (divide by $Z^4$) turns this into $$F(x,y)=x^3y+y^3+x=0.\tag{*}$$ The curve intersects the line at infinity $Z=0$ at the points $Q_1=(1:0:0)$ and $Q_2=(0:1:0)$. Here $Q_1$ is in the affine piece $X=1$, so it is the origin $u=v=0$ in the coordinate system $u=Y/X, v=Z/X$. That dehomogenization looks like $$P(u,v)=u+u^3v+v^3=0.$$ The partial derivative $\partial P/\partial u =1+u^2v$ is non-zero at $Q_1$, so $v$ is a local parameter at $Q_1$. From a study of the terms of $P(u,v)$ we see that $u$ must have a zero of multiplicity three at $Q_1$. Therefore $x=1/v$ has a simple pole at $Q_1$ and $y=u/v$ has a zero of multiplicity $2$ there. Thus we can conclude that the monomial $\nu_{Q_1}(x^iy^j)=2j-i$. In other words, if $i-2j>0$, then $x^iy^j$ has a pole of order $i-2j$ at $Q_1$, and otherwise it does not have a pole there.

Similarly $Q_2$ is the origin of the affine piece $R(s,t)=s^3+t+st^3=0$, where $s=X/Y$ and $t=Z/Y$. Here $\partial R/\partial t(Q_2)\neq0$, so $s$ is a local parameter at $Q_2$, and $t$ has a zero of order $3$. So $x=s/t$ has a double pole at $Q_2$, and $y=1/t$ a pole of order three there. Thus the monomial $x^iy^j$ has a pole of order $2i+3j$ at $Q_2$.

AFAICT your exercise #1 asks us to identify the space of functions that have a pole of order at most $3m$ at $Q_2$, a pole of order at most $m$ at $Q_1$, and no other poles. The affine curve on the $xy$-plane determined by $(*)$ seems to be non-singular. If $\partial F/\partial x=x^2y+1$ vanishes at some point, we must have $y=1/x^2$ there. But $$F(x,1/x^2)=x+x^{-6}+x=x^{-6}$$ never vanishes on an affine point of the curve, so we have the claimed non-singularity. From this it follows that for a function to have no poles on the affine $xy$-part of the curve, it must be a polynomial on $x$ and $y$. The claim of your question #1 follows from this, our pole number calculations, and the answer (once we figure it out) to your other question.

In order to write down a generator matrix for the resulting Goppa code, we need an enumeration of the $F_8$-rational points of the Klein curve. Presumably you have been given this in class, but I had to dig for it. You may need to translate my numbering of points to match with that of your source.

Let us first find the points $(x,y)\in X(F_8)\setminus\{Q_1,Q_2\}$ with $x\neq0$. We need an auxiliary variable $w=x^2y$. Multiplying $(*)$ by $x^6$ gives $$x^9y+x^6y^3+x^7=0\Leftrightarrow x^7(1+w)=w^3.$$ This implies that we must have $$x^7=\frac{w^3}{1+w}.$$ Here we have phenomenal luck! Any non-zero element of $F_8$ satisfies the equation $x^7=1$, so the above equation implies $w^3=1+w$. Let $\alpha$ be a root of $\alpha^3=\alpha+1$. It is well known that such an element $\alpha$ is a primitive element of $F_8$. The solutions of $w^3=1+w$ are then $w=\alpha$ and its conjugates $w=\alpha^2$ and $w=\alpha^4=\alpha+\alpha^2$. If you have trouble with the arithmetic of $F_8$, please take a look at my other answer. Here we can pick any non-zero value for $x$, and then solve for $y=w/x^2$ for any of the three possible values of $w$. With $w=\alpha$ we get seven $F_8$-rational points: $$P_i=(\alpha^i,\alpha^{1-2i}),\qquad\text{for i=1,2,\ldots,7.}$$ With $w=\alpha^2$ we get seven other $F_8$-rational points: $$P_{7+i}=(\alpha^i,\alpha^{2-2i}),\qquad\text{for i=1,2,\ldots,7.}$$ And with $w=\alpha^4$ we get seven more: $$P_{14+i}=(\alpha^i,\alpha^{4-2i}),\qquad\text{for i=1,2,\ldots,7.}$$

Finally we observe that if $x=0$, then $(*)$ implies that $y=0$ also, and we have our last point $P_{22}=(0,0)$. Thus the curve has 22 $F_8$-rational points in the affine $xy$-plane.

Remember that we can reduce the exponents of $\alpha$ modulo 7. Below I will list the values of the functions $1,x,y$ at the 22 points on the three rows of the following matrix. You get the values of the other monomial with the obvious operations. $$\pmatrix{1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\cr \alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&1&0\cr \alpha^6&\alpha^4&\alpha^2&1&\alpha^5&\alpha^3&\alpha&1&\alpha^5&\alpha^3&\alpha&\alpha^6&\alpha^4&\alpha^2&\alpha^2&1&\alpha^5&\alpha^3&\alpha&\alpha^6&\alpha^4&0\cr}$$

Hopefully you can make some sense out of this. Too bad I don't have your textbook so that I could help you more.

-
:First of all thank you very much! I gonna to read your detailed answer closely and think I still have many questions. Our textbook is [ "Algebraic Geometric Codes: Basic Notions" By Tsfasman, G. Vlăduț][1] And this is example 4.4.51(Klein quartic) on page 245 [1]: books.google.com/… – Lilly Apr 8 '12 at 0:01
@Lilly, that link only shows me the front cover. Our library may have it. Will check later. – Jyrki Lahtonen Apr 8 '12 at 5:14
Oh, sorry! [that's correct link:][1] [1]: books.google.com/… – Lilly Apr 8 '12 at 11:50
@Lilly, the most likely explanation of my difficulties in viewing that is that as a rule my Adblocker blocks most things from Google. I am trying to find a balance there, but I will not freely give information to market research. – Jyrki Lahtonen Apr 8 '12 at 14:11
@ Jyrki Lahtonen, Never mind, thanks for helping me! But i have a couple new questions according your answer. Is this generator matrix? I mean the matrix that appears at the end of your answer? How do you build it? Also, 24 rational points that i have found they little different, I added them to my question my main question is still: how can I to write out generator matrix according basis $\left \{ 1,x,x^{2},y,yx,y^{2} \right \}$ and these 22 rational points ? Can you please to explain me? Thanks. – Lilly Apr 8 '12 at 16:18