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 t2(2, q) of a complete arc in PG(2, q). From the new bounds it follows that t2(2, q) < 4.5√q for q ≤ 2647 and q = 2659, 2663, 2683, 2693, 2753, 2801. Also, t2(2, q) < 4.8√q for q ≤ 5419 and q = 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5521. Moreover, t2(2, q) < 5√q for q ≤ 9497 and q = 9539, 9587, 9613, 9623, 9649, 9689, 9923, 9973. Finally, t2(2, q) < 5.15√q for q ≤ 13627 and q = 13687, 13697, 13711, 14009. Using the new arcs it is shown that t2(2, q) <√q ln^0.73 (q) for 109 ≤ q ≤ 13627 and q ∈ G. Also, as q grows, the positive difference √q ln^0.73 (q)−t2(2, q) has a tendency to increase whereas the ratio t2(2, q)/(√q ln^0.73 (q)) tends to decrease. Here t2(2, q) is the smallest known size of a complete arc in PG(2, q). These properties allow us to conjecture that the estimate t2(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 t2(2, q) are proposed.