Table of bounds on three dimensional linear codes or (n,r) arcs in PG(2,q)
Linear codes and (n,r) arcs
Let V be the n-dimensional vector space over a finite field F with q elements.
The weight of a vector v is the number of non-zero coordinates of v.
A linear [n,k,d]-code C over F is a k-dimensional subspace
of V all of whose non-zero vectors have weight at least d.
Let
v1,v2, .... ,vk be a basis for C and for i=1,2, .... ,n
define vectors ui of V, by the rule
(ui)j=(vj)i.
In other words, the j-th co-ordinate of ui is the i-th coordinate of
vj. For all a in F the vector Σ 1 ≤ j ≤ k ajvj has at
most n-d zero coordinates and so, for i=1,2, .... ,n,
Σ 1 ≤ j ≤ k aj (vj)i=0
has at most n-d solutions. Hence
Σ 1 ≤ j ≤ k aj (ui)j=0
has at most n-d solutions, or in other words there are at most n-d of the
n vectors u_i on the hyperplane defined by the equation
Σ 1 ≤ j ≤ k aj Xj=0 .
The matrix whose rows are the vectors vj, or equivalently whose columns
are the vectors ui, is called a generator matrix of the code
C. An (n,r)-arc in PG(k-1,q) is a set of n points K
with the property that every hyperplane is incident with at most r points of
K and there is some hyperplane incident with exactly r points of
K. Hence an (n,n-d)-arc in PG(k-1,q) is
equivalent to a linear [n,k,d]-code for which any two
columns of the generator matrix are linearly independent, in other words with dual minimum distance at least three.
The Griesmer bound
For a linear [n,k,d]-code the Griesmer bound, [Theorem 5.2.6, J. H. van Lint, An Introduction to Coding Theory, Third edition, Springer-Verlag, 1998] states that
n ≥ Σ 0 ≤ i ≤ k-1 ⌈ d ⁄ q i ⌉,
where ⌈ x ⌉ indicates the upper integer part of x.
A linear [n,3,n-r]-code gives
an (n,r)-arc in PG(2,q) and so the Griesmer bound tells us, assuming d=n-r ≤ q2 (or equivalently fixing r ≤ q+1),
n ≥ n-r+ ⌈ n-r ⁄ q ⌉ +1.
Hence, we have the upper bound n ≤ (r-1)q+r and equality in the Griesmer bound if and only if n >(r-2)q+r.
Question: For a fixed n-d, is there always a three-dimensional linear [n,3,d] code meeting the Griesmer bound (or at least close to the Griesmer bound, may be constant or log(q) away) ?
If we are prepared to accept codes whose dual minimum distance is three then this will answer the more general question for k-dimensional linear codes with small minimum distance (less than q2). However we may wish to add a condition on the dual minimum distance for higher dimensional codes.
Table of known bounds for small q
The table indicates the largest set of points in PG(2,q) with at most r points incident with any line.
Alternatively, the longest linear [n,3,d]-code for a fixed n-d.
If you know of any improvement to this table, then please e-mail the address below.
I have not finished updating all the links but if there is a value in the table that you wish to know about then please e-mail the address below.
*** Amendment of the table December 2009 - First change in the table since April 2008 with the discovery of a (79,6)-arc in PG(2,17) and a (126,8)-arc in PG(2,19) by Axel Kohnert. Click on the links below for data. ***
*** Amendment of the table January 2010 - Rumen Daskalov and Elena Metodieva construct a (95,7)-arc and a (183,12)-arc in PG(2,17) and a (243,14)-arc and a (264,15)-arc in PG(2,19). Click on the links below for data. ***
*** Amendment of the table June 2010 - Aaron Gulliver constructs a (78,8)-arc in PG(2,11). Click on the link below for data. ***
*** Amendment of the table July 2011 - Axel Kohnert and Johannes Zwanzger construct a (265,15)-arc in PG(2,19). Click on the link below for data. ***
*** Amendment of the table July 2011 - Rumen Daskalov constructs a (286,16)-arc in PG(2,19). Click on the link below for data. ***
*** Amendment of the table January 2012 - Gary Cook proves that there are no (34,4)-arcs, nor (33,4)-arcs in PG(2,11). Click on the link below for data. ***
*** Amendment of the table November 2012 - Daniele Bartoli, Stefano Marcugini and Fernanda Pambianco prove that there are no (29,3)-arcs in PG(2,16). See this article published in Designs, Codes and Cryptography, for details ***
*** Amendment of the table April 2013 - Noboru Hamada, Tatsuya Maruta and Yusuke Oya prove that there are no (34,3)-arcs in PG(2,17). Click on the link below for the proof. ***
*** Amendment of the table September 2017 - Thanks to Rumen Daskalov who has provided examples for all the lower bounds in PG(2,13), PG(2,17) and PG(2,19). Click on the links below for the examples. ***
*** Amendment of the table June 2018 - A double blocking set in PG(2,19) of size 3q-1, whose complement is a (325,18)-arc. Well done Tamás Heger and Bence Csajbók !! First improvement in more than 5 years. ***
*** Amendment of the table June 2018 - A (167,11)-arc in PG(2,17), a (184,12)-arc in PG(2,17), a (244,14)-arc in PG(2,19) and a (267,15)-arc in PG(2,19) discovered by Michael Braun. Click on the link for the preprint.
*** Amendment of the table August 2018 - A (87,6) arc in PG(2,19) discovered by Michael Braun.
*** Amendment of the table November 2019 - A (144,10) arc in PG(2,16) discovered by Michael Braun. Click on the corresponding link.
Back
Simeon Ball
simeon@ma4.upc.edu
12 November 2019