# Improved Bounds onmr(2,q) q=19,25,27

Authors: Rumen Daskalov; Elena Metodieva
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

An (n,r)-arc is a set of n points of a projective plane such that some r, but no r+1 of them, are collinear. The maximum size of an (n,r)-arc in PG(2, q) is denoted by mr(2, q). In this paper, a new (286, 16)-arc in PG(2,19), a new (341, 15)-arc, and a (388, 17)-arc in PG(2,25) are constructed, as well as a (394, 16)-arc, a (501, 20)-arc, and a (532, 21)-arc in PG(2,27). Tables with lower and upper bounds on mr(2, 25) and mr(2, 27) are presented as well. The results are obtained by nonexhaustive local computer search.


---

## Body

## 1. Introduction

LetGF(q) denote the Galois field of q elements, and let V(3,q) be the vector space of row vectors of length three with entries in GF(q). Let PG(2,q) be the corresponding projective plane. The points(x1,x2,x3) of PG(2,q) are the 1-dimensional subspaces of V(3,q). Subspaces of dimension two are called lines. The number of points in PG(2,q) is q2+q+1 and so is the number of lines. There are q+1 points on every line and q+1 lines through every point.Definition 1.
An(n,r)-arc is a set of n points of a projective plane such that some r, but no r+1 of them, are collinear.The maximum size of a(k,r)-arc in PG(2,q) is denoted by mr(2,q).Definition 2.
An(l,t)-blocking set S in PG(2,q)  is a set of l points such that every line of  PG(2,q)  intersects S in at least t points, and there is a line intersecting S in exactly t points.Note that an(n,r)-arc is the complement of a (q2+q+1-n,q+1-r)-blocking set in a projective plane and conversely.Definition 3.
LetM be a set of points in any plane. An i-secant is a line meeting M in exactly i points. A 0-secant is also called skew line. Define τi as the number of i-secants to a set M.In terms ofτi, the definitions of an (n,r)-arc and an (l,t)-blocking set become the following:an(n,r)-arc is a set of n points of a projective plane for which τi≥0 for i<r, τr>0 and τi=0  when  i>r;an(l,t)-blocking set is a set of l points of a projective plane for which τi=0 for i<t,  τt>0 and  τi≥0  when  i>t.In 1947, Bose [1] proved that
(1)m2(2,q)={q+1forqodd,q+2orqeven.From the result of Barlotti [2], it follows that for q odd and(2)r=(q+1)2,r=(q+3)2,
there exists an
(3)((r-1)q+1,r)-arc.For background onPG(2,q), see Hirschfeld [3].A survey of(n,r)-arcs with the best known results was presented in [4]. After this publication, many improvements were obtained in [5–7]. Summarizing these improvements, Ball and Hirschfeld [8] presented a new table with bounds on mr(2,q) for q≤19. As we can see from these tables, the exact values of mr(2,q) are known only for q≤9   (see Table 1).Table 1
Values ofmr(2,q).
r
q
3
4
5
7
8
9
2
4
6
6
8
10
10
3
9
11
15
15
17
4
16
22
28
28
5
29
33
37
6
36
42
48
7
49
55
8
65Some new improvements were made in recent years. A (79,6) arc in PG(2,17) and a (126,8) arc in PG(2,19) are given in [9]. A (95,7)-arc,  and a (183,12)-arc, a (205,13)-arc in PG(2,17) and a (243,14)-arc and a (264,15)-arc in PG(2,19) have been presented in [10]. In 2010, Gulliver constructed an optimal (78,8) arc in PG(2,11) (see [11]). A table for mr(2,q),q≤19, is maintained by Ball [11].To obtain good(n,r)-arcs, we apply local search techniques. The neighborhood structure is a simple one. Given an arc, then its neighborhood consists of all arcs that can be obtained from the given arc by adding new points or deleting some points. The choice of a start solution is based on some heuristic observations. The cost function is chosen to favour as local optima arcs with a small number of r-secants. The computation times are in order of several minutes up to few hours on a PC. Similar techniques are employed for the construction of (l,t)-blocking sets.Sum and product tables for the fields PG(2,25) and PG(2,27) are taken from [12]. In order to present the results in more concise form, the points in PG(2,25) and PG(2,27) are in lexicographic order, and each point is associated with its number. For example, some of the points in PG(2,25) and their numbers are given in Table 2.Table 2
Some points in PG(2, 25).
Number
Point
1
(
0,0
,
1
)
2
(
0,1
,
0
)
3
(
0,1
,
1
)
4
(
0,1
,
2
)
5
(
0,1
,
3
)
6
(
0,1
,
4
)
7
(
0,1
,
5
)
8
(
0,1
,
6
)
9
(
0,1
,
7
)
⋯
⋯
⋯
⋯
⋯
⋯
303
(
1,11,1
)
304
(
1,11,2
)
305
(
1,11,3
)
306
(
1,11,4
)
307
(
1,11,5
)
308
(
1,11,6
)
309
(
1,11,7
)
310
(
1,11,8
)
⋯
⋯
643
(
1,24,16
)
644
(
1,24,17
)
645
(
1,24,18
)
646
(
1,24,19
)
647
(
1,24,20
)
648
(
1,24,21
)
649
(
1,24,22
)
650
(
1,24,23
)
651
(
1,24,24
)In Table3, some of the lines and their numbers are presented.Table 3
Some lines in PG(2, 25).
Number
a
,
b
,
c
Line—ax+by+cz=0
1
0, 0, 1
626 627 628 629 630 631 632 633 634 635 636 637 638
639 640 641 642 643 644 645 646 647 648 649 650 651
110
1, 3, 8
31 66 69 84 87 167 176 187 211 260 265 299 303 322
325 394 411 432 467 488 503 518 580 587 606 628
310
1, 11, 8
5 38 66 89 112 140 153 181 204 227 255 293 321 344
367 395 408 436 459 482 510 548 576 599 622 650
444
1, 16, 17
8 30 93 112 121 144 160 175 196 201 216 253 301
339 357 408 423 448 480 532 537 539 578 594 606 648
651
1, 24, 24
59 61 63 65 67 122 124 126 128 130 132 142 193
195 197 199 201 203 265 267 269 271 273 275 291 651In [9], a (285,16)-arc in PG(2,19), a (339,15)-arc and a (387,17)-arc in PG(2,25), and a (393,16)-arc, a (499,20)-arc, and a (531,21)-arc in PG(2,27) are presented. In this paper, we improve these results by constructing six new large arcs.


## 2. A New Arc in PG(2, 19)

Theorem 4.
There exists a(286,16)-arc in  PG(2,19).Proof.
The set of points having numbers1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 24 28 33 37 44 46 52 57 62 67 68 70 71 79 90 96 103 106 109 112 116 121 128 129 134 136 137 145 155 159 162 166 181 184 185 188 194 195 203 204 221 223 225 233 242 247 250 254 261 262 267 272 280 285 287 294 299 301 311 313 316 318 329 337 338 339 340 346 350 356 360 363 372 375 379forms a (95,4)-blocking set in PG(2, 19).
The complement of this blocking set is a(286,16)-arc in PG(2, 19) with secant distribution
(4)τ0=14,τ1=1,τ13=10,τ14=60,τ15=147,τ16=159.
In the next sections, we construct new large(n,r)-arcs in PG(2, 25) and PG(2, 27). These arcs were presented at ACCT 2012, Pomorie, Bulgaria [13].


## 3. New Arcs in PG(2, 25)

Theorem 5.
There exist a(341,15)-arc and a (388,17)-arc in  PG(2,25).Proof.
(1) The set of points having numbers6 9 10 15 16 17 20 22 23 25 26 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 56 60 63 65 66 68 69 71 74 77 78 79 80 81 85 87 89 92 95 97 99 102 103 104 105 107 108 110 113 121 122 124 126 129 130 131 134 135 136 138 146 148 149 150 154 155 157 160 164 165 169 170 172 174 176 178 181 182 187 188 189 192 195 196 197 200 202 207 210 211 212 214 215 217 219 220 223 224 228 229 230 231 232 239 241 243 245 246 247 248 252 257 258 259 263 266 268 270 271 272 275 276 279 280 284 287 290 291 292 293 294 296 300 307 309 310 313 315 319 320 321 322 324 325 328 331 333 334 335 336 340 344 348 349 350 351 352 353 356 358 359 364 365 368 369 370 376 377 379 380 382 384 386 387 390 392 397 398 400 403 406 407 409 410 411 416 422 423 424 425 427 428 431 432 436 437 440 441 442 443 444 447 452 454 455 458 459 461 464 468 470 473 475 476 479 480 486 488 489 490 491 493 494 495 498 508 510 511 512 513 516 517 518 521 523 524 526 528 531 533 536 537 538 539 542 545 546 551 552 559 560 562 564 566 567 568 570 575 576 578 579 580 581 583 584 587 590 592 594 600 601 602 607 608 611 613 615 619 621 622 623 626 629 630 632 633 635 637 641 642 643 647 649 651forms a (310,11)-blocking set in PG(2,25) with secant distribution
(5)τ11=229,τ12=247,τ13=122,τ14=28,τ15=1,τ23=7,τ24=8,τ25=3,τ26=6.
The complement of this blocking set is a (341,15)-arc in PG(2,25).
(2) The set of points having numbers1 3 6 12 13 14 17 18 20 21 24 27 28 31 35 38 40 46 49 52 60 62 64 67 70 71 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 133 137 138 139 142 145 149 157 158 160 164 166 168 172 174 176 182 183 185 190 194 197 199 201 205 206 211 213 214 215 216 219 220 221 223 225 227 229 230 231 233 238 246 247 255 256 259 262 263 266 267 268 269 271 275 278 281 286 289 291 293 295 298 302 303 304 305 306 310 311 313 324 325 328 331 334 337 340 342 344 350 354 355 358 361 364 373 375 376 379 380 382 384 386 392 397 400 403 406 411 414 416 418 420 423 429 430 432 434 437 447 448 450 454 455 458 459 461 470 473 476 478 481 484 487 490 492 494 500 502 503 504 505 506 509 510 523 524 532 533 535 541 543 547 549 551 553 554 559 562 563 565 566 567 568 571 575 577 578 579 580 582 588 596 601 603 604 609 611 613 614 615 618 619 620 621 623 632 633 635 640 644 647 649 651 forms a (263,9)-blocking set in PG(2,25) with secant distribution
(6)τ9=220,τ10=226,τ11=96,τ12=58,τ13=16,τ14=17,τ15=4,τ16=2,τ25=4,τ26=8.
The complement of this blocking set is a (388,17)-arc in PG(2,25).


## 4. New Arcs in PG(2, 27)

Theorem 6.
There exist a(394,16)-arc, a (501,20)-arc, and a (532,21)-arc in  PG(2,27).Proof.
(1) The set of points having numbers1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 29 57 58 59 62 67 69 71 72 73 75 77 78 79 82 83 84 85 86 88 89 90 93 94 96 97 102 103 108 109 110 113 114 116 118 119 120 121 124 126 128 129 130 133 135 138 139 141 145 149 150 151 152 153 158 160 161 162 163 164 165 166 173 174 176 178 179 180 182 184 185 187 188 189 196 198 201 202 203 205 207 208 210 211 213 214 215 216 219 220 223 225 227 229 231 232 233 236 237 239 243 244 245 249 253 255 256 258 260 261 262 264 265 266 267 268 271 273 274 275 276 277 278 279 280 281 288 289 290 294 295 299 300 301 303 304 306 307 311 313 315 316 321 322 323 324 326 331 333 335 337 338 339 340 343 344 345 348 350 351 352 353 356 358 359 360 364 365 368 369 370 372 374 375 376 377 383 385 386 387 389 390 394 395 396 398 400 401 403 405 408 409 410 411 413 415 417 418 421 424 426 427 429 432 438 442 443 444 445 446 447 450 452 453 454 457 458 460 464 465 467 469 470 473 474 475 478 479 483 485 486 487 491 492 493 494 495 496 497 499 500 503 506 507 509 512 515 518 521 524 528 529 530 531 532 533 536 537 538 540 541 546 547 549 550 552 555 556 557 559 562 563 564 567 568 570 571 572 574 575 576 579 581 582 585 589 592 593 595 596 597 598 599 602 605 606 608 609 613 614 616 618 620 622 623 624 625 627 628 630 631 632 634 636 639 641 642 646 649 650 651 652 653 654 656 658 661 662 664 665 669 671 674 675 678 679 686 687 688 689 692 694 695 696 697 698 699 701 704 705 706 708 709 711 712 713 714 719 721 722 724 725 726 731 734 735 736 737 738 739 741 743 744 746 751 752 755 757 forms a (394,16)-arc in PG(2,27) with secant distribution
(7)τ1=12,τ2=15,τ14=156,τ15=378,τ16=196.
(2) The set of points having numbers1 2 13 17 19 21 23 24 40 42 46 48 51 54 55 59 61 62 63 67 70 75 81 86 88 89 90 94 97 102 108 110 122 124 125 127 131 132 134 135 140 141 142 143 144 145 146 148 155 156 167 170 174 175 178 183 184 189 191 203 205 206 207 208 212 213 214 215 216 219 220 221 224 228 229 232 237 238 243 248 249 251 253 254 256 260 263 264 266 281 282 285 288 290 292 295 298 300 301 310 313 314 318 320 324 327 328 330 331 333 334 336 343 346 348 353 357 361 362 365 370 371 375 377 381 382 390 392 396 400 403 404 410 412 413 414 417 419 421 422 423 427 428 430 431 432 438 442 445 447 449 453 455 460 461 462 463 474 475 476 477 482 484 486 487 491 493 494 495 500 503 509 512 519 523 524 525 528 531 533 535 538 541 542 546 547 549 550 551 552 559 560 562 564 570 571 582 583 584 590 594 595 596 600 604 607 609 611 615 617 622 623 628 630 635 638 640 644 645 647 650 663 665 666 667 671 672 673 676 681 685 686 687 694 695 697 699 707 710 714 716 717 720 724 727 728 730 732 733 740 743 747 749 754 755 706 forms a (256,8)-blocking set in PG(2,27) with secant distribution
(8)τ8=252,τ9=236,τ10=152,τ11=73,τ12=21,τ13=10,τ14=2,τ15=1,τ28=10.
The complement of this blocking set is a (501,20)-arc in PG(2,27).
(3) The set of points having numbers1 2 13 16 17 21 23 27 29 30 31 39 41 42 46 51 55 59 61 62 63 67 70 75 81 86 88 89 90 94 97 102 108 110 111 112 114 122 124 127 132 134 135 137 139 140 141 143 145 146 148 155 156 165 166 167 170 174 175 178 183 184 189 191 192 193 195 203 205 208 213 215 216 219 220 221 224 228 229 232 237 238 243 245 247 248 249 251 253 254 256 263 264 281 282 285 288 290 292 295 298 300 301 313 314 320 324 330 331 333 334 336 343 346 348 357 361 362 370 371 375 381 382 392 394 396 403 404 408 410 413 417 419 423 427 430 431 438 442 445 447 449 453 455 460 461 462 474 476 477 482 484 487 493 495 500 503 509 512 524 525 528 531 533 535 538 541 546 547 549 550 552 559 562 564 570 571 583 584 590 594 600 604 607 609 611 615 617 622 628 630 635 638 644 647 650 651 663 665 666 671 673 676 681 685 686 694 695 699 705 707 710 714 716 720 724 727 728 732 733 743 745 747 754 755 forms a (225,7)-blocking set in PG(2,27) with secant distribution
(9)τ7=308,τ8=208,τ9=130,τ10=53,τ11=46,τ12=3,τ14=1,τ28=8.
The complement of this blocking set is a (532,21)-arc in PG(2,27).There exists a projective[n,3,d]q code if and only if thereexists an (n,n-d)-arc in PG(2,q) (see [14]). So, there exist projective [286,3,270]19, [341,3,326]25 Griesmer's codes and projective codes, having parameters [388,3,371]25, [394,3,378]27, [501,3,481]27, and [532,3,511]27.


## 5. New Upper Bounds onmr(2,25) and mr(2,27)

Whenq is a prime, there are good upper bounds on mr(2,q) obtained by Ball [15] (see also [4]) and Daskalov [16].Theorem 7.
LetK be an (n,r)-arc in PG(2,q), where q is prime.(1)
Ifr≤(q+1)/2, then mr(2,q)≤(r-1)q+1.(2)
Ifr≥(q+3)/2, then mr(2,q)≤(r-1)q+r-(q+1)/2.Theorem 8.
LetK be an (n,r)-arc in PG(2,q) with r>(q+3)/2 and prime q≤29. Then,
(10)mr(2,q)≤(r-1)q+r-(q+3)2.From Theorem7 and Barlotti's constructions, it follows that, for prime q,
(11)mr(2,q)=(r-1)q+1,wherer=(q+1)2,r=(q+3)2.But whenq is an odd prime power, these bounds are not valid. For example, a (48,6)-arc in PG(2,9) was constructed by Mason [17]. So, when q is an odd prime power, in order to obtain good upper bounds on mr(2,q), we have to combine some bounds given in [8]—consider the following (12), (13), (14), (15) and (16).Let𝒜 be an (n,r)-arc and P a point of 𝒜. Each line incident with P contains at most (r-1) points of 𝒜∖P, and the next trivial upper bound follows
(12)n≤(r-1)(q+1)+1=(r-1)q+r.If(r,q)≠(2t,2h) and 2<r<q, then (Barlotti, [18])
(13)n≤(r-1)q+r-2.Corollary  2.2 in [8]. An (n,r)-arc 𝒜 in a projective plane of order q which has no skew line satisfies
(14)n≤(r-1)q+⌊r2q⌋,
and if q divides r, then
(15)n<(r-1)q+⌊r2q⌋.It follows from [19] that an (n,r)-arc 𝒜 in PG(2,q) which has a skew line satisfies
(16)n≤(r-1)q+(r,q).Corollary 2.2 in combination with (16) can always be used to provide an upper bound on mr(2,q).In [9], upper bounds on mr(2,25), based on the trivial bound (12), are given. Now, we will improve these bounds, using (13), (14), (15), and (16) (see Table 4).Table 4
Upper bounds onmr(2,25).
r
(
r
-
1
)
q
+
r
-
2
(
r
-
1
)
q
+
⌊
r
2
/
q
⌋
(
r
-
1
)
q
+
(
r
,
q
)
Upper bounds
(13)
(14) or (15)
(16)
2
26
25
26
26
3
51
50
51
51
4
77
75
76
76
5
103
100
105
103
6
129
126
126
126
7
155
151
151
151
8
181
177
176
177
9
207
203
201
203
10
233
228
230
230
11
259
254
251
254
12
285
280
276
280
13
311
306
301
306
14
337
332
326
332
15
363
358
355
358
16
389
385
376
385
17
415
411
401
411
18
441
437
426
437
19
467
464
451
464
20
493
480
480
480
21
519
517
501
517
22
545
544
526
544
23
571
571
551
571
24
597
598
576
597Combining these upper bounds with the lower bounds from [9] and the new arcs, presented in Sections 3 and 4, we obtain the next bounds on mr(2,25) (see Table 5).Table 5
Bounds onmr(2,25).
r
2
26
3
38–51
4
64–76
5
85–103
6
126
7
135–151
8
168–177
9
189–203
10
210–230
11
231–254
12
266–280
13
301–306
14
326–332
15
341–358
16
362–385
17
388–411
18
414–437
19
447–464
20
480
21
501–517
22
527–544
23
558–571
24
577–597In PG(2,27), we have Tables6 and 7.Table 6
Upper bounds onmr(2,27).
r
(
r
-
1
)
q
+
r
-
2
(
r
-
1
)
q
+
⌊
r
2
/
q
⌋
(
r
-
1
)
q
+
(
r
,
q
)
Upper bounds
(13)
(14) or (15)
(16)
2
28
28
28
28
3
55
54
57
55
4
83
81
82
82
5
111
108
109
109
6
139
136
138
138
7
167
163
163
163
8
195
191
190
191
9
223
219
225
223
10
251
246
244
246
11
279
274
271
274
12
307
302
300
302
13
335
330
325
330
14
363
358
352
358
15
391
386
381
386
16
419
414
406
414
17
447
442
433
442
18
475
471
468
471
19
503
499
487
499
20
531
527
514
527
21
559
556
543
556
22
587
584
568
584
23
615
613
595
613
24
643
642
624
642
25
671
671
649
671
26
699
700
676
699Table 7
Bounds onmr(2,27).
r
2
28
3
42–55
4
66–82
5
88–109
6
116–138
7
142–163
8
169–191
9
198–223
10
223–246
11
253–274
12
281–302
13
315–330
14
352–358
15
379–386
16
394–414
17
419–442
18
468–471
19
483–499
20
501–527
21
532–556
22
558–584
23
586–613
24
624–642
25
652–671



---

*Source: 628952-2013-03-13.xml*