New upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane

摘要

In the projective planes PG(2, _q), more than 1230 new small complete arcs are obtained for _q ≤ 13627 and _q ∈ G where G is a set of 38 values in the range 13687,..., 45893; also,2~(18) ∈ G. This implies new upper bounds on the smallest size t_2(2, q) of a complete arc in PG(2, q). From the new bounds it follows that, Also, as q grows, the positive difference √q ln~(0.73) q-t?_2(2, q) has a tendency to increase whereas the ratio t?_2(2, q)/(√q ln~(0.73) q) tends to decrease. Here t?_2(2, q) is the smallest known size of a complete arc in PG(_2,q). These properties allow us to conjecture that the estimate t_2(2,q) < √q ln~(0.73) q holds for all q≥ 109. The new upper bounds are obtained by finding new small complete arcs in PG(2,q) with the help of a computer search using randomized greedy algorithms. Finally, new forms of the upper bound on t_2(2,q) are proposed.