{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T04:47:25Z","timestamp":1778906845056,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P 34180"],"award-info":[{"award-number":["P 34180"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Johannes Kepler University Linz"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,12]]},"abstract":"Abstract<\/jats:title>An arc in $$\\mathbb F_q^2$$<\/jats:tex-math>\n \n F<\/mml:mi>\n q<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a set $$P \\subset \\mathbb F_q^2$$<\/jats:tex-math>\n \n P<\/mml:mi>\n \u2282<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that no three points of P<\/jats:italic> are collinear. We use the method of hypergraph containers to prove several counting results for arcs. Let $${\\mathcal {A}}(q)$$<\/jats:tex-math>\n \n A<\/mml:mi>\n (<\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denote the family of all arcs in $$\\mathbb F_q^2$$<\/jats:tex-math>\n \n F<\/mml:mi>\n q<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our main result is the bound $$\\begin{aligned} |{\\mathcal {A}}(q)| \\le 2^{(1+o(1))q}. \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n |<\/mml:mo>\n A<\/mml:mi>\n \n (<\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n |<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n 2<\/mml:mn>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n )<\/mml:mo>\n q<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula>This matches, up to the factor hidden in the o<\/jats:italic>(1) notation, the trivial lower bound that comes from considering all subsets of an arc of size q<\/jats:italic>. We also give upper bounds for the number of arcs of a fixed (large) size. Let $$k \\ge q^{2\/3}(\\log q)^3$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n \n q<\/mml:mi>\n \n 2<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and let $${\\mathcal {A}}(q,k)$$<\/jats:tex-math>\n \n A<\/mml:mi>\n (<\/mml:mo>\n q<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denote the family of all arcs in $$\\mathbb F_q^2$$<\/jats:tex-math>\n \n F<\/mml:mi>\n q<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with cardinality k<\/jats:italic>. We prove that $$\\begin{aligned} |{\\mathcal {A}}(q,k)| \\le \\left( {\\begin{array}{c}(1+o(1))q\\\\ k\\end{array}}\\right) . \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n |<\/mml:mo>\n A<\/mml:mi>\n \n (<\/mml:mo>\n q<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n |<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n \n \n \n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n )<\/mml:mo>\n q<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula>This result improves a bound of Roche-Newton and Warren [12]. A nearly matching lower bound $$\\begin{aligned} |{\\mathcal {A}}(q,k)| \\ge \\left( {\\begin{array}{c}q\\\\ k\\end{array}}\\right) \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n |<\/mml:mo>\n A<\/mml:mi>\n \n (<\/mml:mo>\n q<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n |<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n \n \n \n \n q<\/mml:mi>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula>follows by considering all subsets of size k<\/jats:italic> of an arc of size q<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00454-023-00622-w","type":"journal-article","created":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T20:01:53Z","timestamp":1704744113000},"page":"1630-1646","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Counting Arcs in $${\\mathbb {F}}_q^2$$"],"prefix":"10.1007","volume":"72","author":[{"given":"Krishnendu","family":"Bhowmick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1640-3707","authenticated-orcid":false,"given":"Oliver","family":"Roche-Newton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,8]]},"reference":[{"key":"622_CR1","unstructured":"Balogh, J., Liu, H., Sharifzadeh, M.: The number of subsets of integers with no $$k$$-term arithmetic progression. Int. Math. Res. Not. IMRN, no. 20, 6168\u20136186"},{"issue":"3","key":"622_CR2","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1090\/S0894-0347-2014-00816-X","volume":"28","author":"J Balogh","year":"2015","unstructured":"Balogh, J., Morris, R., Samotij, W.: Independent sets in hypergraphs. J. Am. Math. Soc. 28(3), 669\u2013709 (2015)","journal-title":"J. Am. Math. Soc."},{"key":"622_CR3","doi-asserted-by":"crossref","unstructured":"Balogh, J., Morris, R., Samotij, W.: The method of hypergraph containers. In: Proceedings of the International Congress of Mathematicians-Rio de Janeiro 2018. Vol. IV. Invited lectures, pp. 3059\u20133092 (2018)","DOI":"10.1142\/9789813272880_0172"},{"key":"622_CR4","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1112\/jlms\/jdq086","volume":"83","author":"J Balogh","year":"2011","unstructured":"Balogh, J., Samotij, W.: The number of $$K_{s, t}$$-free graphs. J. Lond. Math. Soc. 83, 368\u2013388 (2011)","journal-title":"J. Lond. Math. Soc."},{"key":"622_CR5","unstructured":"Balogh, J., Solymosi, J.: On the number of points in general position in the plane. Discrete Anal., Paper No. 16, 20 pp"},{"key":"622_CR6","first-page":"107","volume":"8","author":"RC Bose","year":"1947","unstructured":"Bose, R.C.: Mathematical theory of the symmetrical factorial design. Sankhya 8, 107\u2013166 (1947)","journal-title":"Sankhya"},{"key":"622_CR7","unstructured":"Chen, Y., Liu, X., Nie, J., Zeng, J.: Random Tur\u00e1n and counting results for general position sets over finite fields. arXiv:2309.07744"},{"key":"622_CR8","first-page":"222","volume":"94","author":"HE Dudeney","year":"1917","unstructured":"Dudeney, H.E.: 317. A puzzle with pawns. Amusements Math. 94, 222 (1917)","journal-title":"Amusements Math."},{"key":"622_CR9","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/0097-3165(75)90043-6","volume":"18","author":"RR Hall","year":"1975","unstructured":"Hall, R.R., Jackson, T.H., Sudbery, A., Wild, K.: Some advances in the no-three-in-line problem. J. Comb. Theory Ser. A 18, 336\u2013341 (1975)","journal-title":"J. Comb. Theory Ser. A"},{"key":"622_CR10","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1016\/j.aim.2016.05.001","volume":"298","author":"R Morris","year":"2016","unstructured":"Morris, R., Saxton, D.: The number of $$C_{2l}$$-free graphs. Adv. Math. 298, 534\u2013580 (2016)","journal-title":"Adv. Math."},{"issue":"4","key":"622_CR11","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1002\/rsa.21042","volume":"60","author":"C Pohoata","year":"2022","unstructured":"Pohoata, C., Roche-Newton, O.: Four-term progression free sets with three-term progressions in all large subsets. Random Struct. Algorithms 60(4), 749\u2013770 (2022)","journal-title":"Random Struct. Algorithms"},{"key":"622_CR12","doi-asserted-by":"crossref","unstructured":"Roche-Newton, O., Warren, A.: Arcs in $${\\mathbb{F}}_q^2$$. Eur. J. Comb. 103, Paper No. 103512, 15 pp (2022)","DOI":"10.1016\/j.ejc.2022.103512"},{"issue":"2","key":"622_CR13","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1112\/jlms\/s1-26.3.198","volume":"26","author":"KF Roth","year":"1951","unstructured":"Roth, K.F.: On a problem of Heilbronn. J. Lond. Math. Soc. 26(2), 198\u2013204 (1951)","journal-title":"J. Lond. Math. Soc."},{"issue":"3","key":"622_CR14","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1007\/s00222-014-0562-8","volume":"201","author":"D Saxton","year":"2015","unstructured":"Saxton, D., Thomason, A.: Hypergraph containers. Invent. Math. 201(3), 925\u2013992 (2015)","journal-title":"Invent. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00622-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00622-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00622-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T22:02:14Z","timestamp":1731794534000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00622-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,8]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["622"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00622-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,8]]},"assertion":[{"value":"3 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}