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. ***

*** Observation: There have been no improvements on the values in the table for more than four years.

q

r=n-d
34 578911 13161719

2
4 6 6 8 10 10 12 14 18 18 20

3
9 11 15 15 17 21 23 28 28 ... 33 31 ... 39

4
16 22 28 28 32 38 ... 40 52 48 ... 52 52 ... 58

5
29 33 37 43 ... 45 49 ... 53 65 61 ... 69 68 ... 77

6
36 42 48 56 64 ... 66 78... 82 79 ... 86 86 ... 96

7
49 55 67 79 93 ... 97 95 ... 103 105 ... 115

8
65 78 92 120 114 ... 120 126 ... 134

9
89 ... 90 105 129 ... 130 137 147 ... 153

10
100 ... 102 118 ... 119 142 ... 148 154 172

11
132 ... 133 159 ... 164 166 ... 171 191

12
145 ... 147 180 ... 181 183 ... 189 204 ... 210

13
195 ... 199 205 ... 207 225 ... 230

14
210 ... 214 221 ... 225 243 ... 250

15
231 239 ... 243 265 ... 270

16
256 ... 261 286 ... 290

17
305 ... 310

18
324 ... 330

Back

Simeon Ball
simeon@ma4.upc.edu
4 September 2017