27:
813:
642:
693:
1130:
530:
983:
134:
902:
1177:
858:
469:
369:
323:
267:
214:
1268:
682:
1213:
1456:
1040:
808:{\displaystyle \left\lfloor {\frac {{\binom {n}{2}}-{\frac {6n}{13}}}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .}
380:
1494:
1424:
1002:
77:
1612:
1366:
637:{\displaystyle \left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .}
1617:
925:
1534:
1313:
1218:
645:
1607:
1132:
3-point lines which matches the lower bound established by Burr, GrĂĽnbaum and Sloane. Thus, for sufficiently large
865:
1485:
1141:
822:
517:
433:
333:
274:
231:
178:
55:
862:
are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of
1224:
1281:
Orchard-planting problem has also been considered over finite fields. In this version of the problem, the
905:
520:
1309:
1622:
653:
1271:
1189:
31:
1389:
20:
1447:
1184:
This is slightly better than the bound that would directly follow from their tight lower bound of
1561:
1543:
1521:
1503:
1473:
1406:
1380:
990:
563:
1580:
1362:
39:
1584:
1553:
1513:
1465:
1451:
1433:
1398:
1275:
1017:
59:
1325:
63:
51:
26:
1532:
Padmanabhan, R.; Shukla, Alok (2020), "Orchards in elliptic curves over finite fields",
1601:
1565:
1410:
1354:
1321:
71:
1525:
1024:
published a paper in which they prove that for all point sets of sufficient size,
1489:
1384:
1376:
1021:
1006:
994:
986:
1557:
1517:
218:
to be the maximum number of 3-point lines attainable with a configuration of
1589:
1270:
proved in the same paper and solving a 1951 problem posed independently by
1125:{\displaystyle {\frac {n(n-3)}{6}}+1={\frac {1}{6}}n^{2}-{\frac {1}{2}}n+1}
1477:
1438:
1402:
1469:
1548:
1508:
1454:(1984), "Arrangements of lines with a large number of triangles",
25:
1285:
points lie in a projective plane defined over a finite field. (
375:
165:. One can also ask the question if these are not allowed.
978:{\displaystyle {\tfrac {1}{6}}n^{2}-{\tfrac {1}{2}}n+1}
1229:
1194:
955:
930:
873:
658:
279:
1227:
1192:
1144:
1043:
928:
868:
825:
696:
656:
533:
436:
336:
277:
234:
181:
80:
516:
Since no two lines may share two distinct points, a
1262:
1207:
1171:
1124:
998:
977:
896:
852:
807:
676:
636:
463:
363:
317:
261:
208:
128:
16:Geometry; how many 3-point lines can n points form
1286:
584:
571:
555:
542:
129:{\displaystyle t_{k}>{\frac {cn^{2}}{k^{3}}},}
1457:Proceedings of the American Mathematical Society
151:-point lines. Their construction contains some
70:-point lines there can be. Hallard T. Croft and
1492:(2013), "On sets defining few ordinary lines",
523:for the number of 3-point lines determined by
66:. There are also investigations into how many
30:An arrangement of nine points (related to the
1010:
720:
707:
8:
1418:Csima, J.; Sawyer, E. (1993), "There exist 6
897:{\displaystyle \approx {\tfrac {1}{8}}n^{2}}
1318:Extremal Problems in Combinatorial Geometry
687:
373:are given in the following table (sequence
1547:
1507:
1437:
1228:
1226:
1193:
1191:
1172:{\displaystyle t_{3}^{\text{orchard}}(n)}
1154:
1149:
1143:
1103:
1094:
1080:
1044:
1042:
954:
945:
929:
927:
888:
872:
867:
853:{\displaystyle t_{3}^{\text{orchard}}(n)}
835:
830:
824:
782:
768:
762:
729:
719:
706:
704:
701:
695:
657:
655:
609:
602:
583:
570:
568:
562:
561:
554:
541:
539:
532:
464:{\displaystyle t_{3}^{\text{orchard}}(n)}
446:
441:
435:
364:{\displaystyle t_{3}^{\text{orchard}}(n)}
346:
341:
335:
318:{\displaystyle {\tfrac {1}{6}}n^{2}-O(n)}
294:
278:
276:
262:{\displaystyle t_{3}^{\text{orchard}}(n)}
244:
239:
233:
209:{\displaystyle t_{3}^{\text{orchard}}(n)}
191:
186:
180:
115:
104:
94:
85:
79:
50:) asks for the maximum number of 3-point
1337:
385:
1298:
1359:Research Problems in Discrete Geometry
690:), this upper bound can be lowered to
1263:{\displaystyle {\tfrac {n(n-2)}{6}},}
7:
1535:Finite Fields and Their Applications
1005:. An elementary construction using
222:points. For an arbitrary number of
1495:Discrete and Computational Geometry
1425:Discrete and Computational Geometry
711:
575:
546:
14:
1001:), using a construction based on
677:{\displaystyle {\tfrac {6n}{13}}}
1013:achieving the same lower bound.
1003:Weierstrass's elliptic functions
1387:(1974), "The Orchard problem",
1316:, et al, in the chapter titled
1208:{\displaystyle {\tfrac {n}{2}}}
1247:
1235:
1166:
1160:
1062:
1050:
847:
841:
458:
452:
358:
352:
312:
306:
256:
250:
203:
197:
1:
1306:The Handbook of Combinatorics
1287:Padmanabhan & Shukla 2020
1353:Brass, P.; Moser, W. O. J.;
140:is the number of points and
34:) forming ten 3-point lines.
1011:Füredi & Palásti (1984)
646:the number of 2-point lines
1639:
1585:"Orchard-Planting Problem"
912:points on the cubic curve
18:
1558:10.1016/j.ffa.2020.101756
1518:10.1007/s00454-013-9518-9
1613:Euclidean plane geometry
922:. This was improved to
328:The first few values of
58:of a specific number of
44:orchard-planting problem
19:Not to be confused with
688:Csima & Sawyer 1993
1422:/13 ordinary points",
1338:Green & Tao (2013)
1264:
1209:
1173:
1126:
979:
898:
854:
809:
678:
638:
512:Upper and lower bounds
465:
365:
319:
263:
210:
130:
35:
1618:Mathematical problems
1265:
1210:
1174:
1136:, the exact value of
1127:
1037:, there are at most
980:
899:
855:
810:
679:
644:Using the fact that
639:
466:
366:
320:
264:
211:
131:
48:tree-planting problem
29:
1272:Gabriel Andrew Dirac
1225:
1190:
1142:
1041:
926:
866:
823:
694:
654:
531:
434:
334:
275:
232:
179:
155:-point lines, where
78:
32:Pappus configuration
1390:Geometriae Dedicata
1361:, Springer-Verlag,
1159:
1016:In September 2013,
840:
451:
351:
249:
196:
1581:Weisstein, Eric W.
1439:10.1007/BF02189318
1403:10.1007/BF00147569
1260:
1255:
1217:for the number of
1205:
1203:
1169:
1145:
1122:
975:
964:
939:
894:
882:
850:
826:
805:
674:
672:
634:
461:
437:
361:
337:
315:
288:
259:
235:
206:
182:
126:
36:
1608:Discrete geometry
1254:
1202:
1157:
1111:
1088:
1069:
963:
938:
881:
838:
817:Lower bounds for
795:
777:
748:
742:
718:
671:
625:
582:
553:
509:
508:
449:
349:
287:
271:was shown to be
247:
194:
147:is the number of
121:
40:discrete geometry
1630:
1594:
1593:
1568:
1551:
1528:
1511:
1480:
1442:
1441:
1413:
1385:Sloane, N. J. A.
1371:
1340:
1335:
1329:
1303:
1284:
1276:Theodore Motzkin
1269:
1267:
1266:
1261:
1256:
1250:
1230:
1216:
1214:
1212:
1211:
1206:
1204:
1195:
1180:
1178:
1176:
1175:
1170:
1158:
1155:
1153:
1135:
1131:
1129:
1128:
1123:
1112:
1104:
1099:
1098:
1089:
1081:
1070:
1065:
1045:
1036:
984:
982:
981:
976:
965:
956:
950:
949:
940:
931:
921:
911:
903:
901:
900:
895:
893:
892:
883:
874:
861:
859:
857:
856:
851:
839:
836:
834:
814:
812:
811:
806:
801:
797:
796:
791:
783:
778:
773:
772:
763:
753:
749:
744:
743:
738:
730:
725:
724:
723:
710:
702:
685:
683:
681:
680:
675:
673:
667:
659:
643:
641:
640:
635:
630:
626:
621:
614:
613:
603:
594:
590:
589:
588:
587:
574:
567:
566:
560:
559:
558:
545:
526:
472:
470:
468:
467:
462:
450:
447:
445:
391:
386:
378:
372:
370:
368:
367:
362:
350:
347:
345:
324:
322:
321:
316:
299:
298:
289:
280:
270:
268:
266:
265:
260:
248:
245:
243:
225:
221:
217:
215:
213:
212:
207:
195:
192:
190:
169:Integer sequence
164:
154:
150:
146:
139:
135:
133:
132:
127:
122:
120:
119:
110:
109:
108:
95:
90:
89:
69:
54:attainable by a
21:Euclid's orchard
1638:
1637:
1633:
1632:
1631:
1629:
1628:
1627:
1598:
1597:
1579:
1578:
1575:
1531:
1484:
1470:10.2307/2045427
1446:
1417:
1375:
1369:
1352:
1349:
1344:
1343:
1336:
1332:
1326:George B. Purdy
1304:
1300:
1295:
1282:
1231:
1223:
1222:
1188:
1187:
1185:
1140:
1139:
1137:
1133:
1090:
1046:
1039:
1038:
1035:
1025:
941:
924:
923:
913:
909:
884:
864:
863:
821:
820:
818:
784:
764:
761:
757:
731:
705:
703:
697:
692:
691:
660:
652:
651:
649:
605:
604:
598:
569:
540:
538:
534:
529:
528:
524:
514:
432:
431:
429:
389:
374:
332:
331:
329:
290:
273:
272:
230:
229:
227:
223:
219:
177:
176:
174:
171:
156:
152:
148:
145:
141:
137:
111:
100:
96:
81:
76:
75:
67:
42:, the original
24:
17:
12:
11:
5:
1636:
1634:
1626:
1625:
1620:
1615:
1610:
1600:
1599:
1596:
1595:
1574:
1573:External links
1571:
1570:
1569:
1529:
1502:(2): 409–468,
1482:
1464:(4): 561–566,
1444:
1432:(2): 187–202,
1415:
1397:(4): 397–424,
1373:
1367:
1348:
1345:
1342:
1341:
1330:
1297:
1296:
1294:
1291:
1259:
1253:
1249:
1246:
1243:
1240:
1237:
1234:
1201:
1198:
1168:
1165:
1162:
1152:
1148:
1121:
1118:
1115:
1110:
1107:
1102:
1097:
1093:
1087:
1084:
1079:
1076:
1073:
1068:
1064:
1061:
1058:
1055:
1052:
1049:
1033:
993:, and
974:
971:
968:
962:
959:
953:
948:
944:
937:
934:
891:
887:
880:
877:
871:
849:
846:
843:
833:
829:
804:
800:
794:
790:
787:
781:
776:
771:
767:
760:
756:
752:
747:
741:
737:
734:
728:
722:
717:
714:
709:
700:
670:
666:
663:
633:
629:
624:
620:
617:
612:
608:
601:
597:
593:
586:
581:
578:
573:
565:
557:
552:
549:
544:
537:
513:
510:
507:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
460:
457:
454:
444:
440:
426:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
360:
357:
354:
344:
340:
314:
311:
308:
305:
302:
297:
293:
286:
283:
258:
255:
252:
242:
238:
205:
202:
199:
189:
185:
170:
167:
143:
125:
118:
114:
107:
103:
99:
93:
88:
84:
15:
13:
10:
9:
6:
4:
3:
2:
1635:
1624:
1621:
1619:
1616:
1614:
1611:
1609:
1606:
1605:
1603:
1592:
1591:
1586:
1582:
1577:
1576:
1572:
1567:
1563:
1559:
1555:
1550:
1545:
1542:(2): 101756,
1541:
1537:
1536:
1530:
1527:
1523:
1519:
1515:
1510:
1505:
1501:
1497:
1496:
1491:
1487:
1483:
1479:
1475:
1471:
1467:
1463:
1459:
1458:
1453:
1449:
1445:
1440:
1435:
1431:
1427:
1426:
1421:
1416:
1412:
1408:
1404:
1400:
1396:
1392:
1391:
1386:
1382:
1378:
1374:
1370:
1368:0-387-23815-8
1364:
1360:
1356:
1351:
1350:
1346:
1339:
1334:
1331:
1327:
1323:
1319:
1315:
1311:
1310:László Lovász
1307:
1302:
1299:
1292:
1290:
1288:
1279:
1277:
1273:
1257:
1251:
1244:
1241:
1238:
1232:
1220:
1219:2-point lines
1199:
1196:
1182:
1163:
1150:
1146:
1119:
1116:
1113:
1108:
1105:
1100:
1095:
1091:
1085:
1082:
1077:
1074:
1071:
1066:
1059:
1056:
1053:
1047:
1032:
1028:
1023:
1019:
1014:
1012:
1009:was found by
1008:
1004:
1000:
996:
992:
988:
972:
969:
966:
960:
957:
951:
946:
942:
935:
932:
920:
916:
908:, who placed
907:
904:was given by
889:
885:
878:
875:
869:
844:
831:
827:
815:
802:
798:
792:
788:
785:
779:
774:
769:
765:
758:
754:
750:
745:
739:
735:
732:
726:
715:
712:
698:
689:
668:
664:
661:
647:
631:
627:
622:
618:
615:
610:
606:
599:
595:
591:
579:
576:
550:
547:
535:
522:
519:
511:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
455:
442:
438:
428:
427:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
388:
387:
384:
382:
377:
355:
342:
338:
326:
309:
303:
300:
295:
291:
284:
281:
253:
240:
236:
200:
187:
183:
168:
166:
163:
159:
123:
116:
112:
105:
101:
97:
91:
86:
82:
73:
65:
61:
57:
56:configuration
53:
49:
45:
41:
33:
28:
22:
1623:Dot patterns
1588:
1539:
1533:
1499:
1493:
1490:Tao, Terence
1461:
1455:
1429:
1423:
1419:
1394:
1388:
1381:GrĂĽnbaum, B.
1358:
1333:
1317:
1308:, edited by
1305:
1301:
1280:
1183:
1030:
1026:
1015:
1007:hypocycloids
918:
914:
816:
648:is at least
515:
327:
172:
161:
157:
47:
43:
37:
1452:Palásti, I.
1377:Burr, S. A.
1022:Terence Tao
985:in 1974 by
521:upper-bound
1602:Categories
1549:2003.07172
1486:Green, Ben
1448:FĂĽredi, Z.
1347:References
1322:Paul Erdős
1314:Ron Graham
1181:is known.
527:points is
72:Paul Erdős
1590:MathWorld
1566:212725631
1509:1208.4714
1411:120906839
1242:−
1101:−
1057:−
1018:Ben Green
952:−
906:Sylvester
870:≈
780:−
727:−
616:−
325:in 1974.
301:−
1526:15813230
1357:(2005),
1355:Pach, J.
991:GrĂĽnbaum
799:⌋
759:⌊
751:⌋
699:⌊
628:⌋
600:⌊
592:⌋
536:⌊
226:points,
46:(or the
1478:2045427
1215:
1186:
1179:
1156:orchard
1138:
997: (
860:
837:orchard
819:
684:
650:
518:trivial
471:
448:orchard
430:
379:in the
376:A003035
371:
348:orchard
330:
269:
246:orchard
228:
216:
193:orchard
175:
173:Define
74:proved
62:in the
1564:
1524:
1476:
1409:
1365:
995:Sloane
989:,
136:where
60:points
1562:S2CID
1544:arXiv
1522:S2CID
1504:arXiv
1474:JSTOR
1407:S2CID
1293:Notes
1029:>
160:>
64:plane
52:lines
1363:ISBN
1324:and
1274:and
1020:and
999:1974
987:Burr
381:OEIS
92:>
1554:doi
1514:doi
1466:doi
1434:doi
1399:doi
1320:by
1312:,
1289:).
505:26
502:22
499:19
496:16
493:12
490:10
424:14
421:13
418:12
415:11
412:10
383:).
38:In
1604::
1587:,
1583:,
1560:,
1552:,
1540:68
1538:,
1520:,
1512:,
1500:50
1498:,
1488:;
1472:,
1462:92
1460:,
1450:;
1428:,
1405:,
1393:,
1383:;
1379:;
1278:.
1221::
917:=
793:78
786:25
740:13
669:13
487:7
484:6
481:4
478:2
475:1
409:9
406:8
403:7
400:6
397:5
394:4
1556::
1546::
1516::
1506::
1481:.
1468::
1443:.
1436::
1430:9
1420:n
1414:.
1401::
1395:2
1372:.
1328:.
1283:n
1258:,
1252:6
1248:)
1245:2
1239:n
1236:(
1233:n
1200:2
1197:n
1167:)
1164:n
1161:(
1151:3
1147:t
1134:n
1120:1
1117:+
1114:n
1109:2
1106:1
1096:2
1092:n
1086:6
1083:1
1078:=
1075:1
1072:+
1067:6
1063:)
1060:3
1054:n
1051:(
1048:n
1034:0
1031:n
1027:n
973:1
970:+
967:n
961:2
958:1
947:2
943:n
936:6
933:1
919:x
915:y
910:n
890:2
886:n
879:8
876:1
848:)
845:n
842:(
832:3
828:t
803:.
789:n
775:6
770:2
766:n
755:=
746:3
736:n
733:6
721:)
716:2
713:n
708:(
686:(
665:n
662:6
632:.
623:6
619:n
611:2
607:n
596:=
585:)
580:2
577:3
572:(
564:/
556:)
551:2
548:n
543:(
525:n
459:)
456:n
453:(
443:3
439:t
390:n
359:)
356:n
353:(
343:3
339:t
313:)
310:n
307:(
304:O
296:2
292:n
285:6
282:1
257:)
254:n
251:(
241:3
237:t
224:n
220:n
204:)
201:n
198:(
188:3
184:t
162:k
158:m
153:m
149:k
144:k
142:t
138:n
124:,
117:3
113:k
106:2
102:n
98:c
87:k
83:t
68:k
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
