THE DIMENSIONS OF LU(3,q) CODES 1 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 bipartitegraphs. Recently,P.SinandQ.Xiangdeterminedthedimensionsofthesecodesinthecasethat 9 q is a power of an odd prime. They also obtained a lower bound for the dimension of an LU(3,q) code 0 whenqisapowerof2. InthispaperweprovethatthislowerboundistheexactdimensionoftheLU(3,q) 0 code. Theproofinvolvesthegeometryofsymplecticgeneralized quadrangles,therepresentationtheoryof 2 Sp(4,q), and thering of polynomials. l u J 1. Introduction 4 1 Let P∗ andL∗ be two sets in bijection with F3, where q is any prime power. In [4],an element q (a,b,c) P∗ is defined to be incident with an element [x,y,z] L∗ if and only if y = ax+b ] ∈ ∈ O 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 C matrices are called LU(3,q) codes in [4]. . h Let V be a 4 dimensional vector space over the field F of q elements. We assume that V has q t ′ ′ a a nonsingular alternating bilinear form (v,v ), that is, (v,v ) is linear in both components and m (v,v) = 0 for all v. Let Sp(4,q) be the symplectic group of linear automorphisms preserving this [ form. We pick a symplectic basis e0, e1, e2, e3 of V, with (ei,e3−i)=1 for i=0,1. WedenotebyP,theprojectivespaceP(V),thespaceofonedimensionalsubspacesofV. These 5 one dimensional subspaces are called the points of P. A subspace of V is called totally isotropic, v ′ ′ 5 if (v,v )=0 whenever v and v are both in the subspace. We let L be the set of totally isotropic 1 2-dimensional subspaces of V, considered as lines in P. The pair (P,L), with the natural relation 0 of incidence between the points and lines is the symplectic generalized quadrangle W(q). In this 0 paper the term line will always mean an element of L. One can see that given any line ℓ and a . 2 point p not on that line there is a unique line that passes through p and intersects ℓ. 0 Fix a point p0 = e0 P and a line ℓ0 = e0,e1 L. For a point p P, we define p⊥ to be 8 the set of points onahll tihe∈lines that pass throuhgh p.iT∈hus, p⊥ = (a:b:∈c:0) a,b,c F where 0 0 { | ∈ q} : (a : b : c : d) are the homogeneous coordinates of a point. Let P1 be the set of points not in p⊥0 v and L1 be the set of lines which do not intersect ℓ0. Hence other incidence systems of interest are i X (P1,L1), (P,L1) and (P1,L). Let M(P,L) be the incidence matrix whose rows are indexed by P, r andthe columns by L. Similarly, we getthe incidence matrix M(P1,L1), which canbe thoughtas a a submatrix of M(P,L). It was proven in [8, appendix] that the incidence systems (P∗,L∗) and (P1,L1) areequivalent. Hence,M(P1,L1) andits transposeareparity checkmatricesfor LU(3,q) codes. The 2-ranks of M(P,L) and M(P1,L1) for q a power of an odd prime, were proven to be (q3+2q2+q+2)/2 and(q3+2q2 3q+2)/2 in [1, theorem9.4]and [8, theorem1.1]respectively. − The formulas for the case where q is a power of 2 are quite different. It was proven in [7, 2t 2t theorem 1] that the 2-rank of M(P,L) is 1+ (1+√17)/2 + (1 √17)/2 . − In this paper we prove the following theorhem. The formiula inhthe theoremiwas conjectured in [8] based on the computer calculations of J.-L. Kim. Theorem 1. Assume q =2t for some positive integer t. The 2-rank of M(P1,L1) is 2t 2t 1+√17 1 √17 1+ + − 2t+1. 2 ! 2 ! − Hence we get the following corollary. 1ThisworkwassupportedbyChatYinHoscholarshipofDepartmentofMathematics atUniversityofFlorida. 1 Corollary 2. The dimension of the LU(3,q) code for q a power of 2 is 2t 2t 1+√17 1 √17 23t+2t+1 1 − . − − 2 ! − 2 ! The dimensionofthe LU(3,q)code forq apowerofanoddprimewasproventobe (q3 2q2+ − 3q 2)/2 in [8, Corollary 1.2]. − For the rest of the section we can assume that q is an arbitrary prime power. We denote by F2[P] the space of F2 valued functions on P. We can think of elements of F2[P] as q3+q2+q+1 component vectors whose entries are indexed by the points of P so that for any function f, the value of eachentry is the value off atthe correspondingpoint. The characteristic function χ for a point p P is the function whose value is 1 at p, and zero at any other point. p Thus, χ is the q3+q2+∈q+1 component vector whose entry that corresponds to p is 1, and all p the other entries are zero. The characteristic functions for all the points in P form a basis for F2[P]. For any line ℓ L, the characteristic function χℓ is the function given by the sum of the q+1 characteristic fu∈nctions of the points of ℓ. The subspace of F2[P] spanned by all the χℓ is the F2 code of (P,L), denoted by C(P,L). We can think of it as the column space of M(P,L). Most of the time we will not make a distinction between the lines and the characteristic functions of the lines. For example, we will say, let C(P,L1) be the subspace of F2[P] spanned by the lines of L1. Let C(P1,L1) denote the code of (P1,L1) viewed as a subspace of F2[P1], and let C(P1,L) be the larger subspace of F2[P1] spanned by the restrictions to P1 of the characteristic functions of all lines of L. We consider the natural projection map πP1 : F2[P] → F2[P1] given by the restriction of functions to P1. We denote its kernel by kerπP1. LetZ C(P,L1)beasetofcharacteristicfunctionsoflinesinL1whichmapsbijectivelyunder ⊂ πP1 to a basis of C(P1,L1). Let X be the set of characteristic functions of the q+1 lines passing throughp0, andlet X0 =X ℓ0. Furthermore,we pick q lines that intersectℓ0 atq distinct points \ except p0, and call the set of these lines as Y. These sets X,Y, and Z are disjoint, also note that X kerπ . ⊂ P1 The following lemma and corollary were proven in [8]. Lemma 3. X0 Y Z is linearly independent over F2. ∪ ∪ Hence, |X0∪Y|=2q, while |Z|=dimF2C(P1,L1). Corollary 4. Let q be an arbitrary prime power. Then dimF LU(3,q) q3 dimF C(P,L)+2q. 2 ≥ − 2 The proof of Theorem 1 follows from Lemma 3 and the dimension of C(P,L). In section 2 we prove that X0 Y L1 spans C(P,L). Then we show in section 3 that the span of X0 Y L1 ∪ ∪ ∪ ∪ and X0 Y Z are the same. ∪ ∪ 2. The Grid Of Lines Unless otherwise is stated we assume that q =2t for the rest of the paper. ′ Lemma 5. Let ℓ and ℓ be two lines passing through p∈ℓ0. Then χℓ+χℓ′ ∈C(P,L1). Proof. ThepointsofthequadrangleW(q)areregularasitisdefinedin[6,section1.3,p.4]. When q is even this quadrangle is known to be self-dual [6, 3.2.1]. Hence, the lines of W(q) are regular ′ for the case of even q. Thus one can show that there is a grid of lines between ℓ and ℓ . This means there are two sets of lines ∆ and Λ such that each set has q elements, each line in ∆ inter- sects ℓ p and distinct lines of ∆ intersects ℓ p in distinct points. Similarly, each line in Λ \{ ′} \{′} intersects ℓ p and distinct lines of Λ intersects ℓ p in distinct points. Moreover,every line \{ } \{ } of ∆ intersects every line of Λ. 2 ′ ℓ t d d d t d d d t d d d ℓ d t t t p We add characteristic functions of these lines and get χγ =χℓ+χℓ′ ∈C(P,L1). γ∈∆∪Λ X Lemma 6. For any choice of Y, ℓ L ℓ0 and 1 are in the span of X0 Y L1. ∈ \{ } ∪ ∪ Proof. It is enough to show that any line ℓ in L (X L1) is in the span of X0 Y L1. It is \ ∪ ′ ∪ ∪ immediate that ℓ intersects ℓ0 at a point p other than p0. Let ℓ be the line in Y that intersect ℓ0 at p. Then, by the previous result χℓ+χℓ′ is in the span of L1. Thus (χℓ+χℓ′)+χℓ′ =χℓ is in the span of Y L1. Thus any line in L ℓ0 can be written as a linear combination of the lines ∪ \{ } in X0 Y L1. ∪ ∪ In order to prove the second part of the lemma, we pick a line in L1, say ℓ∗. Since ℓ∗ does not intersectℓ0,allthelinesthatintersectℓ∗ arein X0,Y,L1 . Henceweaddalltheselines,including h i ℓ∗, to get 1. Lemma 7. ℓ0 is contained in the span of X0 Y L1. ∪ ∪ Proof. χℓ0 =1+ χℓ ∈hX0,Y,L1i. ℓ∩ℓ0X6=∅,ℓ6=ℓ0 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 LetkdenotethefieldF . Considerthespace,k[V],ofk-valuedfunctionsonV,wheretheelements q of this space are vectors with q4 components 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 find the value of f(x0,x1,x2,x3) R at ∈ v = (a0,a1,a2,a3) V we just substitute xi with ai for all i. Thus, there is an homomorphism ∈ fromRtok[V]thatmapseverypolynomialtoafunction. Onecanprovethatthishomomorphism isinfactanisomorphismbetweenR/I andk[V],whereI istheidealgeneratedby (xq0 x0),(xq1 x1),(xq2 x2),(xq3 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 1 and 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∗. 3 Letk[V 0 ]bethespaceobtainedbyrestrictingfunctionsofk[V]toV 0 ,andk[V 0 ]k× be the subsp\a{ce}of k[V 0 ]fixed by k×. In other words,k[V 0 ]k× is th\e{sp}ace of func\t{ion}s f \{ } \{ } ink[V 0 ]suchthatf(λv)=f(v)foreveryv V 0 ,andλ k×. Thus,foreachp= v P \{ } ∈ \{ } ∈ h i∈ 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 func\ti{on}f k[P] can be extended to a function f¯ k[V 0 ]k× by defining the value of f¯(v) to be the sam∈e as f(p), where p is the point so that v∈ p.\T{hu}s, there is a one to one correspondence between k[P] and k[V 0 ]k×, and k[P] can be e∈mbedded into k[V]k×. \{ } Sincek[V] R/I,thereisaspaceR whichisisomorphictok[P],andthatcanbeembeddedin P to(R/I)k×. E≃lementsofR areclassesofpolynomials. LetR∗ R∗ be the setofrepresentatives P P ⊆ of elements of R . For any element g +I of R the unique representative g∗ in R∗ will be a P P P homogeneous polynomial whose terms have degrees which are multiples of (q 1). In this case, the set of monomials of the form xm0 0xm1 1xm2 2xm3 3 in RP∗ where m0+m1+m2−+m3 is a multiple of (q 1) will map to a basis of R . Since these monomials are in R∗, each m q 1. − P P i ≤ − Forapointp P,letδ∗ bethepolynomialinR∗ thatcorrespondstothecharacteristicfunction ∈ p P χ of p in k[P]. So, p 1 if v =p, δ∗(v)= h i p 0 if v =p. (cid:26) h i6 For aline ℓ L, letδ∗ be the polynomialinR∗ thatcorrespondsto the characteristicfunction ∈ ℓ P χ of ℓ in k[P]. So, ℓ 1 if v ℓ, δ∗(v)= h i∈ ℓ 0 if v ℓ. (cid:26) h i6∈ Example: Let ℓ0 =h(1:0:0:0),(0:1:0:0)i, then δℓ∗0 =(1+x2q−1)(1+x3q−1) 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 . Hence, P by applying the elements of Sp(4,q) to δ∗ , we can obtain all q3 +q2 +q +1 polynomials cor- ℓ0 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+( 3 a x )q−1)(1+( 3 b x )q−1)+I, where a ,b k such that the 2-dimensional sub- i=0 i i i=0 i i i i ∈ space of V given by a0x0+a1x1+a2x2+a3x3 =0 and b0x0+b1x1+b2x2+b3x3 =0 is a line in L. ThPerefore for c+I C,Pc∗ is a homogeneous polynomial whose terms have degrees 0,q 1 or ∈ − 2(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 first introduced in [2]. Definition: We call a polynomial f R∗ digitizable if it is possible to find square free homo- geneous polynomials, fi, called digits of∈f, so that f = f0f12f222...ft2−t−11. In this case, we denote f as [f0,f1,...ft−1], and call this notation the 2-adic t-tuple of f. Example: Every monomial m = xm0xm1xm2xm3 in R∗ is digitizable. Since each m q 1, 0 1 2 3 i ≤ − we can find n 0,1 such that; i,j ∈{ } mi =ni,0+2ni,1+22ni,2+...+2t−1ni,t−1 for all i. The 2-adic t-tuple for m is [f0,f1,...,ft−1] where fi =xn00,ixn11,ixn22,ixn33,i for all i. Example: For q = 8, f = x30x1x63 + x0x31x22x43 is digitizable with digits f0 = x0x1,f1 = x0x3+x1x2,f2 =x3. Note that, f = [x0x1,x0x3+x1x2,x3] = [x0x1,x0x3,x3]+[x0x1,x1x2,x3] Let β := [f0,f1,...,ft−1]+I fi 1,x0,x1,x2,x3,x0x1,x0x2,x1x3,x2x3,x0x3+x1x2 { | ∈{ }} 4 Lemma 8. The code C(P,L) lies in the span of β. Proof. This just a special case of the theorem 5.2 in [2] with m=2 and r=2. 3.2. The kernel: k[P1] is the space of k valued functions on P1. Let RP1 be the space of classes of polynomials that corresponds to k[P1]. As before we use RP∗1 to denote the set of unique representatives of elements of R . P1 In this section we will find the dimension of C(P,L) kerπ , where π : R R is the ∩ P1 P1 P → P1 projection map. Elements of kerπ are the classes of polynomials whose values at the points P1 of P1 are zero. Any element of the form (1+x3q−1)f +I is in the kernel. On the other hand, f +I = (xq−1+1)f +I for any class f +I kerπ . This is because for any point p, the value of (x3q−1+31)f is zero if p P1, and f(p) oth∈erwise.P1 ∈ Lemma 9. Any element of kerπ can be written in the form (1+xq−1)h+I where h is in R∗ P1 3 P and h does not contain indeterminate x3. Proof. Let(x3q−1+1)f+I,f ∈Rp∗beanelementofkerπP1. Sincexq3 =x3,wegetx3q−1(xi0xj1xk2xl3)+ I = xi0xj1xk2xl3 + I, for l 1 . Thus, any term of f + I that contains x3 is invariant under multiplicationby x3q−1. He≥nce, the terms with x3 will disappear inthe expansion(x3q−1f+f)+I. So, we can find a polynomial h without indeterminate x3 and (x3q−1+1)f +I =(x3q−1+1)h+I. For the rest of the section we fix an element r+I of kerπ C(P,L). Let r∗ be its unique representative in RP∗. Since r∗+I is in the kernel, r∗ =(1+x3qP−11∩)h(x0,x1,x2) for some h∈RP∗ . Since r∗+I is alsoinC(P,L), itisinthe spanofβ, andits termshavedegrees0,q 1or2(q 1). − − Lemma 10. The degree of the digits of any non-constant monomial of h is 1. Proof. Let m be a non-constant monomial of h. Then m = [g0,g1,...,gt−1] for some g = xn0,ixn1,ixn2,i, where n 0,1 . Let deg(g ) = k for each i. Hence xq−1m = i 0 1 2 j,i i i 3 ∈ { } [x3g0,x3g1,...,x3gt−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 =0, 1, or 2 for each i. i Sincer∗+I is inC(P,L), andxq−1mis amonomialofr∗,the degreeofxq−1m isq 1or2(q 1). 3 3 Since m is nonconstant, deg(m)=q 1.Hence, k0+2k1+...2t−1kt−1 =2t 1. Sin−ce 2t 1−is an odd number, k0 =1. Then we get k1−+2k2+...+2t−2kt−1 =2t−1 1 and−so k1 =1. W−e repeat − this process until we get k =1 for all i. i Lemma11. hisinthespanoftheset [1,1,...,1] [g0,...,gt−1] gi x1,x2 , for 0 i t . { }∪{ | ∈{ } ≤ ≤ } Proof. It is enough to show that h does not contain the variable x0. Supposeoneofthemonomials,say[g0,...,gt−1],ofhhasx0 init. Sogi =x0 forsomei. Then, x3q−1[g0,g1,...,x0,...,gt−1] = [g0x3,g1x3,...,x0x3,...,gt−1x3] is a monomial in r∗. We know that r∗ is a linear combination of the elements of β, so, the coefficient of [g0x3,g1x3,...,x0x3+ x1x2,...,gt−1x3] is non zero. Hence, r∗ contains the monomial [g0x3,g1x3,...,x1x2,...,gt−1x3] also. Note that the degree of x3 in this monomial is different from 0 or q 1. However this is impossible since r∗ =x3q−1h+h, the degree of x3 in any monomial of r∗ is e−ither 0 or q 1. − Corollary 12. dim(kerπ C(P,L))=q+1. P1 ∩ Proof. Since X kerπ C(P,L), and elements of X are linearly independent, dim(kerπ ⊆ P1 ∩ RP1 ∩ C) q+1. ≥Anyelementofkerπ C(P,L)isoftheform(1+xq−1)h+I ,where,bythepreviouslemma, RP1∩ 3 h lies in space of dimension at most q+1. Thus, dim(kerπ C(P,L))=q+1. P1 ∩ 5 Following lemma was proven in [8], the proof works the same for the even case also. Lemma13. kerπP1∩C(P,L1)has dimension q−1andhav′ingasbasis thesetoffunctionsχℓ−χℓ′ where ℓ=ℓ0 is an arbitrary but fixed line through p0 and ℓ varies over the q 1 lines through p0 6 − different from ℓ0 and ℓ. ′ Proof. By lemma 5 applied to p0, we see that if ℓ and ℓ are any two lines through p0 other than ℓ0, the function χℓ −χℓ′ lies in C(P,L1). It is also in kerπP1. Thus, we can find q −1 linearly independent functions of this kind as described in the statement. Then the dimension of kerπP1 ∩C(P,L1) is greater than or equal to q−1. On the other hand, since none of the lines in L1 has a common point with ℓ0, C(P,L1) is in the kernel of the restriction map to ℓ0, while the image of the restriction of kerπP1 ∩C(P,L) to ℓ0 has dimension 2, spanned by the images of χℓ0 and χp0. Thus, kerπP1 ∩C(P,L1) has codimension at least 2 in kerπP1 ∩C(P,L), which has dimension q+1, by Corollary 12. Hence, dim(kerπP1 ∩C(P,L1))≤q−1. Corollary 14. The spans of Z X0 and L1 X0 are 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 πP1(α)=πP1(α ). Hence, α−α ∈kerπP1 ∩C(P,L1). By the previous lemma kerπP1 ∩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 spansC(P,L)asavectorspace. So,dim(C(P,L)) dim(C(P1,L1))+2q and this implies∪dimL∪U(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.I also would like to thank to Qing Xiang for his comments on the proof of lemma 8. 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 Trans. Inform. Theory,vol. IT-8, Jan. 1962,pp.21-28. [4]J.-L.Kim,U.Peled,I.Pereplitsa,V.Pless,andS.Friedland,Explicit construction of LDPC codes with no 4-cycles, IEEE Trans. Inform. Theory, vol. 50, 2004, pp. 2378-2388. [5]F.Lazebnik andV.A.Ustimenko, Explicit construction of graphs with arbitrarily large girth and of size, Discrete Applied Math., vol. 60, 1997, pp. 275-284. [6]S.E.Payne,J.A.Thas,Finite Generalized Quadrangles, PittmanAdvancedPublishing Pro- gram, Boston, London, Melbourne, 1984. [7] 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. 6 [8] P. Sin, Q. Xiang, On the dimensions of certain LDPC codes based on q-regular bipartite graphs, IEEE Trans. Inform. Theory, vol. 52 (8), 2006, pp. 3735-3737. DepartmentofMathematics, UniversityOfFlorida,Gainesville,FL,32611,USA E-mail Address: [email protected]fl.edu 7