Small Complete Arcs in Projective Planes

In the late 1950s, B. Segre introduced the fundamental notion of arcs and complete arcs 48,49]. An arc in a nite projective plane is a set of points with no three on a line and it is complete if cannot be extended without violating this property. Given a projective plane , determining , the size of its smallest complete arc, has been a major open question in finite geometry for several decades. Assume that has order q, it was shown by Lunelli and Sce 41], more than 40 years ago, that . Apart from this bound, practically nothing was known about , except for the case is the Galois plane. For this case, the best upper bound, prior to this paper, was O(q ^3/4) obtained by Sznyi using the properties of the Galois field GF(q).In this paper, we prove that for any projective plane of order q, where c is a universal constant. Together with Lunelli-Sces lower bound, our result determines up to a polylogarithmic factor. Our proof uses a probabilistic method known as the dynamic random construction or Rödls nibble. The proof also gives a quick randomized algorithm which produces a small complete arc with high probability.The key ingredient of our proof is a new concentration result, which applies for non-Lipschitz functions and is of independent interest.* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.Part of this work was done at AT&T Bell Labs and Microsoft Research