a r X i v :0802.0015v 3 [m a t h .C O ] 7 A p r 2008
THE DIMENSIONS OF LU(3,q)CODES
Ogul Arslan
Department Of Mathematics
University Of Florida
ABSTRACT:A family of LDPC codes,called LU (3,q )codes,has been constructed from q-regular bipartite graphs.Recently,P.Sin and Q.Xiang determined the dimensions of these codes in the case that q is a power of an odd prime.They also obtained a lower bound for the dimension of an LU (3,q )code when q is a power of 2.In this paper we prove that this lower bound is the exact dimension of the LU (3,q )code.The proof involves the geometry of symplectic generalized quadrangles,the representation theory of Sp (4,q ),and the ring of polynomials.
1.Introduction
Let P ?and L ?be two sets in bijection with F 3q ,where q is any prime power.In [4],an element (a,b,c )∈P ?is de?ned to be incident with an element [x,y,z ]∈L ?if and only if y =ax +b and z =ay +c .The binary incidence matrix with rows indexed by P ?and columns indexed by L ?is denoted by H (3,q ).The two binary codes having H (3,q )and its transpose as parity check matrices are called LU (3,q )codes in [4].
Let V be a 4dimensional vector space over the ?eld F q of q elements.We assume that V has
an alternating bilinear form (v,v ′),that is,(v,v ′
)is linear in both components and (v,v )=0for all v .Let Sp (4,q )be the symplectic group of linear automorphisms preserving this form.We pick a symplectic basis e 0,e 1,e 2,e 3of V .
We denote by P ,the projective space P (V ),the space of one dimensional subspaces of V .These one dimensional subspaces are called the points of P .A subspace of V is called totally isotropic ,
if (v,v ′)=0whenever v and v ′
are both in the subspace.We let L be the set of totally isotropic 2-dimensional subspaces of V ,called the lines in P .The pair (P,L ),with the natural relation of incidence between the lines and points is called the symplectic generalized quadrangle.We can see that given any line ?and a point p not on that line there is a unique line that passes through p and intersects ?.
We ?x a point p 0= e 0 ∈P and a line ?0= e 0,e 1 ∈L .For a point p ∈P ,we de?ne p ⊥to be the set of points on all the lines that passes through p .Thus,p ⊥0={(a :b :c :0)|a,b,c ∈F q }where (a :b :c :d )is the homogeneous coordinates of a point.Let P 1be the set of points not in p ⊥0and L 1be the set of lines which does not intersect ?0.We can also talk about the incidence systems (P 1,L 1),(P,L 1)and (P 1,L ).We denote by M (P,L )the incidence matrix whose rows indexed by P ,and the columns by L .Similarly,we get the incidence matrix M (P 1,L 1),which can be thought as a submatrix of M (P,L ).It was proven in [7,appendix]that the incidence systems (P ?,L ?)and (P 1,L 1)are equivalent.Hence,M (P 1,L 1)and its transpose are parity check matrices for LU (3,q )codes.
The 2-rank of M (P,L )and M (P 1,L 1)for q a power of an odd prime,were proven to be q 3
+2q 2+q +2
2
in [1,theorem 9.4]and [7,theorem1.1]respectively.The formulas for the case where q is a power of 2are quite di?erent.It was proven in [6,theorem 1]that the 2-rank of M (P,L )is 1+(1+√2)2t +(1?
√
2)2t .In this paper we prove the following theorem.Theorem 1.Assume q =2t for some positive integer t .The 2-rank of M (P 1,L 1)equals
1+(
1+
√
2)2t +(1?√2)2t ?2t +1.The above formula was conjectured in [7]based on the computer calculations of J.-L.Kim.
P.Sin and Q.Xiang proved in [7,appendix]that (P 1,L 1)and (P ?,L ?)are equivalent incidence systems.Hence,M (P 1,L 1)is a parity check matrix of the LU (3,q )code given by the transpose of H (3,q )and by theorem 1above we get the following corollary.
Corollary2.If q=2t,then the dimension of LU(3,q)is
23t+2t+1?1?(1+√
2
)2t?(1?
√
2
)2t.
The dimension of LU(3,q)code for q a power of an odd prime was proven to be q3?2q2+3q?2
p p 2p 1
p ?v 0
h 0
??
′
?0@@
@@@@@t t t t There are a,b,c,d ∈V so that p 1= a ,p 2= b ,p ?= c and p = e ,and (a,b )=(e,c )=1.
Since v 0= a,c and h 0= b,c ,the points on v 0\(?∪p ?)and h 0\(?′
∪p ?)are of the form c +βa and c +γb for some β,γ∈F ×q ,respectively.
For each point c +βa ∈v 0there is a unique line through it that intersect ?′
at a point b +αe ,for some α∈F ×q .
?
′
b +αe p 2= b p = e v 0
c +βa p ?= c p 1= a
h 0
??0@@
@@
@@@t t
t
t
t t
Since (,)was bilinear,and α,β∈F ×q ,0=(c +βa,b +αe )=(c,b +αe )+(βa,b +αe )0=(c,b )+(c,αe )+(βa,b )+(βa,αe )0=(c,b )+α(c,e )+β(a,b )+αβ(a,e )0=α(c,e )+β(a,b )0=α+β
Thus α=?βin F q .Then for β∈F ×q ,the line through c +βa that intersect ?′
is h β= c +βa,b ?βe .
?
′
b ?βe p 2= b p = e
v 0 c +βa p ?= c p 1= a
h βh 0?
t
t
t
t t
t
Similarly,we can show that for γ∈F ×q ,the line through c +γb that intersect ?is v γ= c +γb,a ?γe .
Note that,for all β,γ∈F ×q ,h βand v γare in L 1.Furthermore,for any β1,β2,γ1,γ2∈F ×
q we have h β1∩h β2=?,and v γ1∩v γ2=?,these lines can be thought as horizontal and vertical lines.
Now we pick two lines v γ′and h β′for some γ′,β′
∈F ×q .We want to show that these two lines
intersect.Note that,by the above calculations,h β′= c +β′a,b ?β′e and v γ′= c +γ′b,a ?γ′
e .?
′
p 2= b p = e
v 0
v γ′p ?p 1
?
h β′h 0
?
t t
t
t
t
t d
Now,pick the point s = (c +β′
a )+γ′
(b ?β′
e ) ∈h β′.Let t = (c +γ′
b )+α(a ?γ′
e ) be an arbitrary point on v γ′\?.Then,
(s,t )=((c +β′a )+γ′(b ?β′e ),(c +γ′b )+α(a ?γ′
e ))
=(c +β′a,c +γ′b )+α(c +β′a,a ?γ′e )+γ′(b ?β′e,c +γ′b )+γ′α(b ?β′e,a ?γ′
e )
=β′γ′(a,b )+αγ′(c,e )?γ′β′(e,c )+γ′
α(b,a )=0
Therefore,v γ′and h β′intersect at s ,and by quadrangle properties this is the only point of intersection.Hence,v γintersect h βfor each γ,β∈F ×q .So,we have a grid of lines,where each h βand v γare in L 1for each β,γ∈F q .?′
?
p
p 2p 1
p
?
t t
t t t t d d d d d d d d d d
Finally we add characteristic functions of these lines and get;
γ∈F q
χv γ+
β∈F q
χh β=χ??χ?′∈C (P,L 1).Lemma 6.For any choice of Y ,?∈L \{?0}and 1are in the span of X 0∪Y ∪L 1.
Proof.It is enough to show that any line,?,in L \(X ∪L 1)is in the span of X 0∪Y ∪L 1.It is
immediate that ?intersects ?0at a point p other than p 0.Let ?′
be the line in Y that intersect ?0at p .Then,by the previous result χ??χ?′is in the span of L 1.Thus (χ??χ?′)+χ?′=χ?is in the span of Y ∪L 1.Thus any line in L \{?0}can be written as a linear combination of the lines in X 0∪Y ∪L 1.
In order to prove the second part of the lemma,we pick a line in L 1,say ??.Since ??does not intersect ?0,all the lines that intersect ??are in X 0,Y,L 1 .Hence we add all these lines,including ??,to get 1.
Lemma 7.?0is contained in the span of X 0∪Y ∪L 1.Proof.
χ?0=1?
?∩?0=?,?=?0
χ?∈ X 0,Y,L 1 .
Thus any line?∈L is in the span of X0∪Y∪L1.It remains to show the span of X0∪Y∪L1 is the same as the span of X0∪Y∪Z.
In the next section we introduce a new way of representing the lines of P.
3.The Polynomial Approach
Let k denote the?eld F q.Consider the space,k[V],of k-valued functions on V,where the elements of this space are vectors with q4components on k.
Let R=k[x0,x1,x2,x3],be the ring of polynomials in four indeterminates.We can think of any polynomial in R as a function in k[V].In order to?nd the value of f(x0,x1,x2,x3)∈R at v=(a0,a1,a2,a3)∈V we just substitute x i with a i for all i.Thus,there is an homomorphism from R to k[V]that maps every polynomial to a function.We can prove that this homomorphism is in fact an isomorphism between R/I and k[V],where I is the ideal generated by{(x q0?x0),(x q1?x1),(x q2?x2),(x q3?x3)}.
For each f+I∈R/I,there is a unique polynomial representative f?∈R such that each indeterminate in f?is of degree less than or equal to q?1and f+I=f?+I.Let R?be the set of all such representatives.By a term of an element f+I of R/I we mean a monomial of its representative f?in R?.
Let k[V\{0}]be the space obtained by restricting functions of k[V]to V\{0},and k[V\{0}]k×be the subspace of k[V\{0}]?xed by k×.For any v∈V\{0},f∈k[V\{0}]k×andλ∈k×we have f(λv)=f(v).Thus,for each p= v ∈P the value of f on p\{0}will be constant.Hence f can be thought as a function on P.On the other hand,any function f∈k[P]can be extended to a functionˉf∈k[V\{0}]k×by de?ning the value ofˉf(v)to be the same as f(p),where p is the point so that v∈p.Thus,there is a one to one correspondence between k[P]and k[V\{0}]k×, and k[P]can be embedded in to k[V]k×.
Since k[V]?R/I,there is a space R P which is isomorphic to k[P],and that can be embedded in to(R/I)k×.Elements of R P are classes of polynomials.Let R?P?R?be the set of representatives of elements of R P.For any element g+I of R P the unique representative g?in R?P will be a homogeneous polynomial whose terms have degrees multiples of(q?1).In this case,the set of monomials of the form x m00x m11x m22x m33where m0+m1+m2+m3=n(q?1)in R?P will map to a basis of R P.Being in R?P,each m i≤q?1.
For a point p∈P,letδ?p be the polynomial in R?P that corresponds to the characteristic function χp of p in k[P].So;
δ?p(p i)= 1if p i=p,
0if p i=p.
For a line?∈L,letδ??be the polynomial in R?P that corresponds to the characteristic function χ?of?in k[P].So;
δ??(p)= 1if p∈?,
0if p∈?.
Example:Let?0= (1:0:0:0),(0:1:0:0) ,thenδ??0=(1+x q?1
2)(1+x q?1
3
)would be the
characteristic function for?0.
The symplectic group Sp(4,q)acts transitively on the characteristic functions of the lines of L,so it also acts transitively on the classes of characteristic functions of lines in R P.Hence,
by applying the elements of Sp(4,q)toδ??0,we can obtain all q3+q2+q+1polynomials cor-responding to the characteristic functions of lines of L.The code C(P,L)is spanned by the
classes of these polynomials.So C(P,L)is spanned by the classes of polynomials of the form (1+( 3i=0a i x i)q?1)(1+( 3i=0b i x i)q?1)+I,for some a i,b i∈k so that (a0:a1:a2:a3),(b0: b1:b2:b3) is a line in L.Therefore for c+I∈C,c?is a homogeneous polynomial whose terms have degrees0,q?1or2(q?1).We also note that the degree of any variable in c?must be less
than or equal to q ?1.
3.1.Another way of representing the polynomials in R ?:
The method of this section was ?rst introduced in [2].
De?nition:We call a polynomial f ∈R ?digitizable if it is possible to ?nd square free homo-geneous polynomials,f i ,called digits of f ,so that f =f 0f 21f 22
2...f 2t ?1
t ?1.In this case,we denote f as [f 0,f 1,...f t ?1],and call this notation the 2-adic t-tuple of f .
Example:Every monomial m =x m 00x m 11x m 22x m 3
3in R ?is digitizable.Since each m i ≤q ?1,we can ?nd n i,j ∈{0,1}such that;
m i =n i,0+2n i,1+22n i,2+...+2t ?1n i,t ?1
for all i.
The 2-adic t-tuple for m is [f 0,f 1,...,f t ?1]where f i =x n
0,i 0x n
1,i 1x n
2,i 2x n
3,i 3for all i.
Example:For q =8,f =x 30x 1x 63+x 0x 31x 22x 4
3is digitizable with digits f 0=x 0x 1,f 1=x 0x 3+x 1x 2,f 2=x 3.Note that,f =[x 0x 1,x 0x 3+x 1x 2,x 3]=[x 0x 1,x 0x 3,x 3]+[x 0x 1,x 1x 2,x 3].Let β:={[f 1,f 2,...,f t ]+I |f i ∈{1,x 0,x 1,x 2,x 3,x 0x 1,x 0x 2,x 1x 3,x 2x 3,x 0x 3+x 1x 2}}Lemma 8.The code C (P,L )lies in the span of β.
Proof.C (P,L )is spanned by the classes of polynomials of the form (1+a q ?1)(1+b q ?1)+I where a =a 0x 0+a 1x 1+a 2x 2+a 3x 3and b =b 0x 0+b 1x 1+b 2x 2+b 3x 3for some a i ,b i ∈k ,and ?= (a 0:a 1:a 2:a 3),(b 0:b 1:b 2:b 3) ∈L .
We will show every summand of the right hand side of the expansion
(1+a q ?1)(1+b q ?1)=a q ?1+b q ?1+a q ?1b q ?1+1
is in the span of β.
Note that,a q ?1=aa 2a 22...a 2t ?1
=[a ,a ,...,a ].a q ?1=[a ,a ,...,a ]=[a 0x 0+a 1x 1+a 2x 2+a 3x 3,a ,...,a ]
=[a 0x 0,a ,...,a ]+[a 1x 1,a ,...,a ]+[a 2x 2,a ,...,a ]+[a 3x 3,a ,...,a ]=a 0[x 0,a ,...,a ]+a 1[x 1,a ,...,a ]+a 2[x 2,a ,...,a ]+a 3[x 3,a ,...,a ]
Repeating this for the remaining q ?1digits we see that a q ?1is in the span of β.By the same argument b q ?1is in the span of βalso.
In order to show that a q ?1b q ?1=(ab )(ab )2(ab )22...(ab )2t ?1
=[ab ,ab ,...,ab ]is in the span of β,it is enough to show that if ab have terms c 1x 0x 3and c 2x 1x 2for some c 1,c 2∈k then c 1=c 2.The summand that has this kind of terms in ab =(a 0x 0+a 1x 1+a 2x 2+a 3x 3)(b 0x 0+b 1x 1+b 2x 2+b 3x 3)is (a 0b 3+b 0a 3)x 0x 3+(a 1b 2+a 2b 1)x 1x 2.Since ?was isotropic,(a 0b 3+b 0a 3)+(a 1b 2+a 2b 1)=0Thus,a 0b 3+b 0a 3=a 1b 2+a 2b 1.Therefore a q ?1b q ?1is in the span of β.
Since constant term 1in the expansion is also in the span of β,we conclude that (1+a q ?1)(1+b q ?1)is in the span of β.3.2.The kernel:
k [P 1]is the space of k valued functions on P 1.Let R P 1be the space of classes of polynomials
that corresponds to k [P 1].As before we use R ?
P 1to denote the set of unique representatives of elements of R P 1.
In this section we will ?nd the dimension of C (P,L )∩kerπP 1,where πP 1:R P →R P 1is the projection map.Elements of kerπP 1are the classes of polynomials whose values at the points
of P 1are zero.Any element of the form (1+x q ?1
3)f +I is in the kernel.On the other hand,
f +I =(x q ?1
3+1)f +I for any class f +I ∈kerπP 1.This is because for any point p ,the value of (x q ?13+1)f is zero if p ∈P 1,and f (p )otherwise.
Lemma 9.Any element of kerπP 1can be written in the form (1+x q ?13
)h +I where h is in R ?
P and h does not contain indeterminate x 3.
Proof.Let (x q ?13+1)f +I ,f ∈R ?
p be an element of kerπP 1.Since x q 3=x 3,we get x q ?13
(x i 0x j 1x k 2x l 3)+I =x i 0x j 1x k 2x l
3+I ,for l ≥1.Thus,any term of f +I that contain x 3is invariant under multiplication by x q ?13.Hence,the terms with x 3will disappear in the expansion (x q ?13f +f )+I.
So,we can ?nd a polynomial h without indeterminate x 3and (x q ?13+1)f +I =(x q ?1
3+1)h +I .
For the rest of the section we ?x an element r +I of kerπP 1∩C (P,L ).Let r ?be its unique
representative in R ?P .Since r ?+I is in the kernel,r ?=(1+x q ?13)h (x 0,x 1,x 2)for some h ∈R ?
P .
Since r ?
+I is also in C (P,L ),it is in the span of β,and its terms have degrees 0,q ?1or 2(q ?1).Lemma 10.The degree of the digits of any non-constant monomial,m ,of h is 1.
Proof.m =[g 0,g 1,...,g t ?1]for some g i =x n 0,i 0x n 1,i 1x n
2,i 2,where n j,i ∈{0,1}.Let deg (g i )=k i for
each i .Hence x q ?1
3m =[x 3g 0,x 3g 1,...,x 3g t ?1]is a t-tuple of a monomial of r ?.Since r ?+I is in the span of β,these digits cannot have degrees greater than 2.Thus,k i =0or 1for each i .
Since x q ?1
3
m is in C (P,L ),deg (x q ?13m )=0,q ?1or 2(q ?1).Since m is nonconstant,deg (m )=k 0+2k 1+...2t ?1k t ?1=2t
?1.Since 2t ?1is an odd number,k 0=1.Then we get k 1+2k 2+...+2t ?2k t ?1=2t ?1?1and so k 1=1.We repeat this process until we get k i =1for all i .Lemma 11.h is in the span of the set {[1,1,...,1]}∪{[g 0,...,g t ?1]|g i ∈{x 1,x 2},for 0≤i ≤t }.Proof.It is enough to show that h does not contain the variable x 0.
Suppose one of the monomials,say [g 0,...,g t ?1],of h has x 0in it.So g i =x 0for some i .Then,x q ?1
3[g 0,g 1,...,x 0,...,g t ?1]=[g 0x 3,g 1x 3,...,x 0x 3,...,g t ?1x 3]is in r ?.We know that r ?is a lin-ear combination of the elements of β,so,the coe?cient of [g 0x 3,g 1x 3,...,x 0x 3+x 1x 2,...,g t ?1x 3]is non zero.Hence,r ?contains the monomial [g 0x 3,g 1x 3,...,x 1x 2,...,g t ?1x 3]also.Note that the degree of x 3in this monomial is di?erent from 0or q ?1.However this is impossible since
r ?=x q ?1
3h +h ,the degree of x 3in any monomial of r ?is either 0or q ?1.Corollary 12.dim (kerπP 1∩C (P,L ))=q +1.
Proof.Since X ?kerπP 1∩C (P,L ),and elements of X are linearly independent,dim (kerπR P 1∩C )≥q +1.
Any element of kerπR P 1∩C (P,L )is of the form (1+x q ?1
3
)h +I ,where,by the previous lemma,h lies in space of dimension q +1.Thus,dim (kerπP 1∩C (P,L ))≤q +1.
Following lemma was proven in [7],the proof works the same for even case also.
Lemma 13.kerπP 1∩C (P,L 1)has dimension q ?1and basis the set of functions χ??χ?′where
?=?0is an arbitrary but ?xed line through p 0and ?′
varies over the q ?1lines through p 0di?erent from ?0and ?.
Proof.By lemma 5applied to p 0,we see that if ?and ?′
are any two lines through p 0other than ?0,the function χ??χ?′lies in C (P,L 1).It is also in kerπP 1.Thus,we can ?nd q ?1linearly independent functions of this kind as described in the statement.Then the dimension of kerπP 1∩C (P,L 1)is greater than or equal to q ?1.On the other hand,since none of the lines in L 1has a common point with ?0,C (P,L 1)is in the kernel of the restriction map to ?0,while the image of the restriction of kerπP 1∩C (P,L )to ?0has dimension 2,spanned by the images of χ?0and χp 0.Thus,kerπP 1∩C (P,L 1)has codimension at least 2in kerπP 1∩C (P,L ),which has dimension q +1,by Corollary 14.Hence,
dim (kerπP 1∩C (P,L 1))≤q ?1.
Corollary14.The span of Z∪X0and L1∪X0are the same.
Proof.Letαbe an element in the span of L1.Since Z maps to a basis of C(P1,L1),there is an
elementα′in the span of Z so thatπP
1(α)=πP
1
(α′).Hence,α?α′∈kerπP1∩C(P,L1).By the
previous lemma kerπP
1∩C(P,L1)is contained in the span of X0.Hence,we conclude thatαis contained in the span of X0∪Z.
Therefore,Z∪X0∪Y spans C(P,L)as a vector space.So,dim(C(P,L))≤dim(C(P1,L1))+2q and this implies dimLU(3,q)=q3?dim(C(P,L))+2q.
Acknowledgement:I am grateful to Peter Sin for his constant support and encouragement.
I would like to thank Stanley Payne for his interest and helpful remarks.
References:
[1]B.Bagchi,A.E.Brouwer,and H.A.Wilbrink,Notes on binary codes related to the O(5,q) generalized quadrangle for odd q,Gemonetriae Dedicata,vol.39,1991,pp.339-355.
[2]D.B.Chandler,P.Sin,Q.Xiang,Incidence modules for symplectic spaces in characteristic two,preprint,arXiv:math/0801.4392v1.
[3]R.G.Gallager,Low-density parity-check codes,IRE https://www.doczj.com/doc/ea17851446.html,rm.Theory,vol.IT-8,Jan. 1962,pp.21-28.
[4]J.-L.Kim,U.Peled,I.Pereplitsa,V.Pless,and S.Friedland,Explicit construction of LDPC codes with no4-cycles,IEEE https://www.doczj.com/doc/ea17851446.html,rm.Theory,vol.50,2004,pp.2378-2388.
[5]https://www.doczj.com/doc/ea17851446.html,zebnik and https://www.doczj.com/doc/ea17851446.html,timenko,Explicit construction of graphs with arbitrarily large girth and of size,Discrete Applied Math.,vol.60,1997,pp.275-284.
[6]N.S.N.Sastry,P.Sin,The code of a regular generalized quadrangle of even order,Group Representations:Cohomology,Group Actions and Topology,ser.Proc.Symposia in Pure Mathe-matics,vol.63,1998,pp.485-496.
[7]P.Sin,Q.Xiang,On the dimensions of certain LDPC codes based on q-regular bipartite graphs,IEEE https://www.doczj.com/doc/ea17851446.html,rm.Theory,vol.52(8),2006,pp.3735-3737.
Department of Mathematics,University Of Florida,Gainesville,FL,32611,USA E-mail Address:ogul@math.u?.edu