Coding theory and its neighbourhood  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
49662
Type K
Principal investigator Szőnyi, Tamás
Title in Hungarian Kódelmélet és környéke
Title in English Coding theory and its neighbourhood
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science (Eötvös Loránd University)
Participants Gács, András
Sziklai, Péter
Weiner, Zsuzsanna
Starting date 2005-01-01
Closing date 2009-06-30
Funding (in million HUF) 7.508
FTE (full time equivalent) 2.41
state closed project





 

Final report

 
Results in Hungarian
Kódelméletben hasznos véges projektív terek speciális egyenes-,illetve hipersíkmetszetű ponthalmazainak vizsgálata. Egyes cikkeinknek közvetlen kódelméleti alkalmazása van (itt ezeket soroljuk),mások geometriai ill. algebrai szálakkal kapcsolódnak oda. A polinomos módszer alkalmazásával bebizonyítottuk,hogy PG(2,q) egy olyan ponthalmaza, melyet minden egyenes adott r mod p pontban metsz, legalább (r-1)q+(p-1)r pontú kell legyen, ahol p a karakterisztika, r|q. Következésképp egy 3 dimenziós kód,melynek hossza és súlyai is oszthatók r-rel és minimális távolsága legalább 3, legalább (r-1)q+(p-1)r hosszú kell legyen. Ball,Blokhuis és Mazzocca híres, maximális ívek nemlétezéséről szóló tétele is egyszerűen kijön a tételből. Meghatároztuk két fontos poset, D^{k,n} és B_{m,n} automorfizmus-csoportját.A kérdéskör az insertion-deletion kódokhoz kapcsolódik. A B_{m,n} struktúra automorfizmus-csoportja korábban is ismert volt, de a hosszú bizonyítást 1 oldalasra redukáltuk. Megfogalmaztunk egy sejtést algebrai síkgörbék pontjainak számáról: n-edfokú, lineáris komponens nélküli görbének legfeljebb (n-1)q+1 pontja lehet; (n-1)q+n/2-t sikerült igazolni. Ilyen görbék hatékony kódokat adnak. Bebizonyítottuk, hogy ha egy lineáris [n,k,d]_q kód kiterjeszthető nem feltétlenül lineáris [n+1,k,d+1]_q kóddá, akkor a kiterjesztést lineáris módon is meg lehet csinálni.Eredményünk kiterjesztéséből pedig az következhetne,hogy az MDS sejtés lineáris és tetszőleges kódokra ekvivalens.
Results in English
In coding theory, it is useful to study point sets of finite projective spaces with special intersection multiplicities with respect to lines and hyperplanes. Some of our papers have immediate application in coding theory (here we list those), the others are linked by its geometrical or algebraical concept. Using polynomial method, we proved that point sets of PG(n,q) intersecting each hyperplane in r mod p points have at least (r-1)q+(p-1)r points, where p is the characteristic and r|q. Hence a linear code whose length and weight are divisible by r and whose dual minimum distance is at least 3, has length at least (r-1)q+(p-1)r. Now the famous Ball-Blokhuis-Mazzocca theorem on the non-existence of maximal arcs becomes a corollary of this result. We determined the automorphism group of two important posets D^{k,n} and B_{m,n}. It was already known for B_{m,n}, but we shortened its long proof to 1 page. This topic is related to insertion-deletion codes. We conjecture that an algebraic plane curve of degree n without linear components can have at most (n-1)q+1 points, we showed that it is at most (n-1)q+n/2. Such curves give efficient codes. We proved that if a linear [n,k,d]_q code can be extended to a not necessarily linear[n+1,k,d+1]_q code then it can be done also in a linear way. From an extension of our results it would follow that the MDS-conjecture is equivalent for linear and arbirtary codes.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=49662
Decision
Yes





 

List of publications

 
T. Szőnyi, A. Cossidente, A. Gács, Cs.Mengyán, A. Siciliano and Zs. Weiner: On large minimal blocking sets in PG(2,q), J. Combin. Des. 13 (2005), no. 1, 25--41, 2005
P. Sziklai: Partial flocks of the quadratic cone, J. Combin. Th. Ser. A 113 (2006), 698-702., 2006
J. Eisfeld, L. Storme, P. Sziklai: On the spectrum of the sizes of maximal partial line spreads in PG(2n,q), n>=3., Des. Codes Cryptogr. 36 (2005), no. 1, 101--110, 2005
P. Ligeti, P. Sziklai: Automorphisms of subword-posets, Discrete Mathematics Vol. 305, (2005), 372-378., 2005
A. Gács: On regular semiovals in PG(2,q), Journal of Algebraic Combinatorics 23 (2006) 71-77., 2006
Zs.Weiner: Small point sets of PG(n,q) intersecting each k-space in 1 modulo q^{1/2} points, Innovations in Incidence Geometry, 1 (2005), 171--180, 2005
A. Blokhuis, L. Lovász, L. Storme, T. Szőnyi: On multiple blocking sets in Galois planes, Adv. Geom. 7 (2007), no. 1, 39-53,, 2007
S. Ball, A. Blokhuis, A. Gács, P. Sziklai, Zs. Weiner: On linear codes whose weights and length have a common divisor, Advances in Mathematics, 211 (2007) 94-104., 2007
Sz. L. Fancsali, P. Sziklai: About Maximal Partial 2-Spreads in PG(3 m - 1,q), nnovations in Incidence Geometry, 4 (2007), 70-80., 2007
P. Sziklai: Directions in AG(3,p) and their applications, Note di Matematica, Lecce, 26 (2006). 121-130, 2006
P. Sziklai: Flocks of cones of higher degree, J. Algebraic Combin., 25 (2007), 233-238., 2007
T. Alderson, A. Gács: On the maximality of linear codes, Designs, Codes and Cryptography, 53/1 (2009), 59-68., 2009
S. Ball, A. Gács: On the graph of a function over a prime field whose small powers have bounded degree, European Journal of Combinatorics, 30 (2009) 1575-1584., 2009
A. Gács, L. Lovász and T. Szőnyi: Directions in AG(2,p^2), Innovations in Incidence Geometry, 6/7 189-201 (2009)., 2009
A. Gács, T. Héger: On geometric constructions of (k,g)-graphs., Contributions to Discrete Mathematics, 3 (2008) 63-80., 2008
J. De Beule, A. Gács: Complete (q^2-1)-arcs of Q(4,q)., Finite Fields and Their Applications, 14 (2008) 14-21., 2008
S. Ball, A. Gács, P. Sziklai: On linear combinations of permutation polynomials that are permutation polynomials, Finite Fields and Their Applications, 14 (2008) 14-21., 2008
A. Gács, T. Szőnyi: Random constructions and density results, Designs, Codes and Cryptography, 47 (2007) 267-287., 2007
G. Korchmáros, T. Szőnyi: Affinely regular polygons in an affine plane, Contrib. Discrete Math. 3 (2008), no. 1, 20--38., 2008
S. Ferret, L. Storme, P. Sziklai, Zs. Weiner: A t mod p result on weighted multiple (n-k)-blocking sets in PG(n,q), Innov. Incidence Geom. 6(7) (2007/08), 169--188., 2008
P. Sziklai. M. Takáts: Vandermonde sets and super-Vandermonde sets, Finite Fields Appl., 14 (2008), 1056-1067, 2008
G. Kós, P. Ligeti, P. Sziklai: Reconstruction of matrices from submatrices, Math. Comp. 78 (2009), no. 267, 1733--1747., 2009
M. Lavrauw, L. Storme, P. Sziklai, G. Van de Voorde: An empty interval in the spectrum of small weight codewords in the code from points and k-spaces of PG(n,q), J. Combin. Theory Ser. A 116 (2009), no. 4, 996--1001., 2009
P. Sziklai: On small blocking sets and their linearity, J. Combin. Theory Ser. A 115 (2008), no. 7, 1167--1182., 2008




Back »