On sizes of complete arcs in

New upper bounds on the smallest size t 2 ( 2 , q ) of a complete arc in the projective plane P G ( 2 , q ) are obtained for 853 ≤ q ≤ 5107 and q ∈ T 1 ∪ T 2 , where T 1 = { 173 , 181 , 193 , 229 , 243 , 257 , 271 , 277 , 293 , 343 , 373 , 409 , 443 , 449 , 457 , 461 , 463 , 467 , 479 , 487 , 491 , 499 , 529 , 563 , 569 , 571 , 577 , 587 , 593 , 599 , 601 , 607 , 613 , 617 , 619 , 631 , 641 , 661 , 673 , 677 , 683 , 691 , 709 } , and T 2 = { 5119 , 5147 , 5153 , 5209 , 5231 , 5237 , 5261 , 5279 , 5281 , 5303 , 5347 , 5641 , 5843 , 6011 , 8192 } . From these new bounds it follows that for q ≤ 2593 and q = 2693 , 2753 , the relation t 2 ( 2 , q ) < 4.5 q holds. Also, for q ≤ 5107 we have t 2 ( 2 , q ) < 4.79 q . It is shown that for 23 ≤ q ≤ 5107 and q ∈ T 2 ∪ { 2 14 , 2 15 , 2 18 } , the inequality t 2 ( 2 , q ) < q ln 0.75 q is true. Moreover, the results obtained allow us to conjecture that this estimate holds for all q ≥ 23 . The new upper bounds are obtained by finding new small complete arcs with the help of a computer search using randomized greedy algorithms. Also new constructions of complete arcs are proposed. These constructions form families of k -arcs in P G ( 2 , q ) containing arcs of all sizes k in a region k min ≤ k ≤ k max , where k min is of order 1 3 q or 1 4 q while k max has order 1 2 q . The completeness of the arcs obtained by the new constructions is proved for q ≤ 2063 . There is reason to suppose that the arcs are complete for all q > 2063 . New sizes of complete arcs in P G ( 2 , q ) are presented for 169 ≤ q ≤ 349 and q = 1013 , 2003 .