Bounds on affine caps,

coauthor Jürgen Bierbrauer

Journal of Combinatorial Designs, 10 (2002), 111-115.



A cap in affine space AG(k,q) is a set A of k-tuples in GF(q) such that whenever a1,a2,a3 are different elements of A and li in GF(q),li not 0, i=1,2,3 such that l1+l2+l3=0 we have a1l1+a2l2+a3l3 is not 0.

Denote by Ck(q) the maximum cardinality of a cap in AG(k,q), and ck(q)=Ck(q)/qk. Clearly ck(2)=1. Henceforth we assume q› 2. The values Ck(q) for k‹ 4 are well-known. Aside of these only a small number of values are known: C4(3)=20 and C5(3)=45.

Clearly Ck(q)‹= qCk-1(q), hence ck(q)‹= ck-1(q). Our main results may be seen as lower bounds on ck-1(q)-ck(q). Meshulam proves an upper bound on the size of subsets of abelian groups of odd order, which do not contain 3-term arithmetic progressions. A more careful analysis of Meshulam's method in the case of caps shows that it can be generalized to cover also the characteristic 2 case. Moreover stronger bounds can be obtained.

Download the preprint as pdf.

| home | List of publications |