Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The minimum size of complete caps in (Z/nZ)2. | The minimum size of complete caps in Z nZ 2 Jack Huizenga Department of Mathematics University of Chicago Chicago IL 60637 USA huizenga@ Submitted Oct 19 2005 Accepted Jul 12 2006 Published Jul 28 2006 Mathematics Subject Classification 51E22 Abstract A line in Z nZ 2 is any translate of a cyclic subgroup of order n. A subset X c Z nZ 2 is a cap if no three of its points are collinear and X is complete if it is not properly contained in another cap. We determine bounds on T n the minimum size of a complete cap in Z nZ 2. The other natural extremal question of determining the maximum size of a cap in Z nZ 2 is considered in 8 . These questions are closely related to well-studied questions in finite affine and projective geometry. If p is the smallest prime divisor of n we prove that max 4 p2p I T n max 4 p 1 . We conclude the paper with a large number of open problems in this area. 1 Introduction A k-cap in AG n q affine n-space over F is a subset X c AG n q of size k no three of whose points are collinear. When a k-cap is not contained in any k 1 -cap it is said to be complete. The same definitions may be made for PG n q projective n-space over F . There are two very natural extremal questions in the study of caps. First what is the maximum size of a cap in AG n q or PG n q This question is of great importance in coding theory and relates to the existence of certain q-ary codes. A nice survey of this question is provided in 4 . On the other hand we could try to determine the minimum number of points in a complete cap. This question was originally posed by B. Segre 16 17 in the late 1950 s in the special case of finite projective planes of order q. Most work in this field has concerned the two-dimensional case so we will restrict our attention to n 2. An essentially trivial lower bound for the minimum number of points in a complete cap in PG 2 q is given THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R58 1 by y 2q and the best known lower bound to date
