{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:02:33Z","timestamp":1746331353357,"version":"3.40.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T00:00:00Z","timestamp":1741996800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T00:00:00Z","timestamp":1741996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS2154232"],"award-info":[{"award-number":["DMS2154232"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,4]]},"abstract":"Abstract<\/jats:title>\n Let \n \n $$\\mathbb {F}_q^d$$<\/jats:tex-math>\n \n \n F<\/mml:mi>\n q<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be the d<\/jats:italic>-dimensional vector space over the finite field with q<\/jats:italic> elements. For a subset \n \n $$E\\subseteq \\mathbb {F}_q^d$$<\/jats:tex-math>\n \n \n E<\/mml:mi>\n \u2286<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and a fixed nonzero \n \n $$t\\in \\mathbb {F}_q$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n \u2208<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, let \n \n $$\\mathcal {H}_t(E)=\\{h_y: y\\in E\\}$$<\/jats:tex-math>\n \n \n \n H<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n {<\/mml:mo>\n \n h<\/mml:mi>\n y<\/mml:mi>\n <\/mml:msub>\n :<\/mml:mo>\n y<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, where \n \n $$h_y:E\\rightarrow \\{0,1\\}$$<\/jats:tex-math>\n \n \n \n h<\/mml:mi>\n y<\/mml:mi>\n <\/mml:msub>\n :<\/mml:mo>\n E<\/mml:mi>\n \u2192<\/mml:mo>\n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is the indicator function of the set \n \n $$\\{x\\in E: x\\cdot y=t\\}$$<\/jats:tex-math>\n \n \n {<\/mml:mo>\n x<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n :<\/mml:mo>\n x<\/mml:mi>\n \u00b7<\/mml:mo>\n y<\/mml:mi>\n =<\/mml:mo>\n t<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Two of the authors, with Maxwell Sun, showed in the case \n \n $$d=3$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> that if \n \n $$|E|\\ge Cq^{\\frac{11}{4}}$$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n E<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n C<\/mml:mi>\n \n q<\/mml:mi>\n \n 11<\/mml:mn>\n 4<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and q<\/jats:italic> is sufficiently large, then the VC-dimension of \n \n $$\\mathcal {H}_t(E)$$<\/jats:tex-math>\n \n \n \n H<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of \n \n $$\\mathcal {H}_t(E)$$<\/jats:tex-math>\n \n \n \n H<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is d<\/jats:italic> whenever \n \n $$E\\subseteq \\mathbb {F}_q^d$$<\/jats:tex-math>\n \n \n E<\/mml:mi>\n \u2286<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> with \n \n $$|E|\\ge C_d q^{d-\\frac{1}{d-1}}$$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n E<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n C<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n \n q<\/mml:mi>\n \n d<\/mml:mi>\n -<\/mml:mo>\n \n 1<\/mml:mn>\n \n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00373-025-02909-6","type":"journal-article","created":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T11:35:13Z","timestamp":1742038513000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["VC-Dimension of Hyperplanes Over Finite Fields"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2906-0807","authenticated-orcid":false,"given":"Ruben","family":"Ascoli","sequence":"first","affiliation":[]},{"given":"Livia","family":"Betti","sequence":"additional","affiliation":[]},{"given":"Justin","family":"Cheigh","sequence":"additional","affiliation":[]},{"given":"Alex","family":"Iosevich","sequence":"additional","affiliation":[]},{"given":"Ryan","family":"Jeong","sequence":"additional","affiliation":[]},{"given":"Xuyan","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Brian","family":"McDonald","sequence":"additional","affiliation":[]},{"given":"Wyatt","family":"Milgrim","sequence":"additional","affiliation":[]},{"given":"Steven J.","family":"Miller","sequence":"additional","affiliation":[]},{"given":"Francisco","family":"Romero Acosta","sequence":"additional","affiliation":[]},{"given":"Santiago","family":"Velazquez Iannuzzelli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"issue":"1","key":"2909_CR1","first-page":"43","volume":"32","author":"R Ascoli","year":"2024","unstructured":"Ascoli, R., Betti, L., Cheigh, J., Iosevich, A., Jeong, R., Liu, X., McDonald, B., Milgrim, W., Miller, S.J., Romero Acosta, F., Velazquez Iannuzzeli, S.: VC-dimension and distance chains in $$\\mathbb{F} _q^d$$. Korean J. Math. 32(1), 43\u201357 (2024)","journal-title":"Korean J. Math."},{"key":"2909_CR2","doi-asserted-by":"crossref","unstructured":"Ben-David, S., Shalev-Shwartz, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press (2014)","DOI":"10.1017\/CBO9781107298019"},{"key":"2909_CR3","doi-asserted-by":"crossref","unstructured":"Bennett, M., Chapman, J., Covert, D., Hart, D., Iosevich, A., Pakianathan, J.: Long paths in the distance graph over large subsets of vector spaces over finite fields, J. Korean Math. Soc. 53, (2016)","DOI":"10.4134\/JKMS.2016.53.1.115"},{"key":"2909_CR4","unstructured":"Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer Science and Business Media (2006)"},{"issue":"1","key":"2909_CR5","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.disc.2017.08.037","volume":"341","author":"A Bruner","year":"2018","unstructured":"Bruner, A., Sharir, M.: Distinct distances between a collinear set and an arbitrary set of points. Discret. Math. 341(1), 261\u2013265 (2018)","journal-title":"Discret. Math."},{"issue":"1","key":"2909_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.015","volume":"31","author":"D Covert","year":"2010","unstructured":"Covert, D., Iosevich, A., Koh, D., Rudnev, M.: Generalized incidence theorems, homogeneous forms and sum-product estimates in finite fields. Eur. J. Combin. 31(1), 306319 (2010)","journal-title":"Eur. J. Combin."},{"issue":"3","key":"2909_CR7","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1023\/A:1004802524095","volume":"38","author":"G Elekes","year":"1999","unstructured":"Elekes, G.: A note on the number of distinct distances. Period. Math. Hung. 38(3), 173\u2013177 (1999)","journal-title":"Period. Math. Hung."},{"issue":"1","key":"2909_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcta.1999.2976","volume":"89","author":"G Elekes","year":"2000","unstructured":"Elekes, G., R\u00f3nyai, L.: A combinatorial problem on polynomials and rational functions. J. Combin. Theory Ser. A 89(1), 1\u201320 (2000)","journal-title":"J. Combin. Theory Ser. A"},{"key":"2909_CR9","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1080\/00029890.1946.11991674","volume":"53","author":"P Erd\u0151s","year":"1946","unstructured":"Erd\u0151s, P.: On sets of distances of n points. Am. Math. Monthly 53, 248\u2013250 (1946)","journal-title":"Am. Math. Monthly"},{"key":"2909_CR10","doi-asserted-by":"crossref","unstructured":"Fitzpatrick, D., Iosevich, A., McDonald, B., Wyman, E.: The VC-dimension and point configurations in $$\\mathbb{F}_q^2$$. Discrete Comput. Geom. (2023)","DOI":"10.1007\/s00454-023-00570-5"},{"issue":"1","key":"2909_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.4007\/annals.2015.181.1.2","volume":"181","author":"L Guth","year":"2015","unstructured":"Guth, L., Katz, N.: On the Erd\u0151s distinct distances problem in the plane. Ann. Math. 181(1), 155\u2013190 (2015)","journal-title":"Ann. Math."},{"issue":"6","key":"2909_CR12","first-page":"1515","volume":"56","author":"A Iosevich","year":"2019","unstructured":"Iosevich, A., Parshall, H.: Embedding distance graphs in finite field vector spaces. J. Korean Math. Soc. 56(6), 1515\u20131528 (2019)","journal-title":"J. Korean Math. Soc."},{"issue":"12","key":"2909_CR13","doi-asserted-by":"publisher","first-page":"6127","DOI":"10.1090\/S0002-9947-07-04265-1","volume":"359","author":"A Iosevich","year":"2007","unstructured":"Iosevich, A., Rudnev, M.: Erd\u0151s distance problem in vector spaces over finite fields. Trans. Am. Math. Soc. 359(12), 6127\u20136142 (2007)","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"2909_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1134\/S0081543821040027","volume":"314","author":"A Iosevich","year":"2021","unstructured":"Iosevich, A., Jardine, G., McDonald, B.: Cycles of arbitrary length in distance graphs on $$\\mathbb{F} _q^d$$. Proc. Steklov Inst. Math. 314(1), 27\u201343 (2021)","journal-title":"Proc. Steklov Inst. Math."},{"issue":"1","key":"2909_CR15","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.disc.2022.113096","volume":"346","author":"A Iosevich","year":"2023","unstructured":"Iosevich, A., McDonald, B., Sun, M.: Dot products in $$\\mathbb{F} _q^3$$ and the Vapnik\u2013Chervonenkis dimension. Discrete Math. 346(1), 9 (2023)","journal-title":"Discrete Math."},{"issue":"1","key":"2909_CR16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.14321\/realanalexch.36.1.0079","volume":"36","author":"P Maga","year":"2010","unstructured":"Maga, P.: Full dimensional sets without given patterns. Real Anal. Exchange 36(1), 79\u201390 (2010)","journal-title":"Real Anal. Exchange"},{"key":"2909_CR17","first-page":"13","volume":"21","author":"A McDonald","year":"2021","unstructured":"McDonald, A., McDonald, B., Passant, J., Sahay, A.: Distinct distances from points on a circle to a generic set. Integers 21, 13 (2021)","journal-title":"Integers"},{"key":"2909_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2024.114192","volume":"348","author":"B McDonald","year":"2025","unstructured":"McDonald, B., Sahay, A., Wyman, W.: The VC-dimension of quadratic residues in finite fields. Discrete Math. 348, 114192 (2025)","journal-title":"Discrete Math."},{"issue":"1","key":"2909_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1017\/S0963548316000225","volume":"26","author":"J Pach","year":"2017","unstructured":"Pach, J., de Zeeuw, F.: Distinct distances on algebraic curves in the plane. Comb. Probab. Comput. 26(1), 99\u2013117 (2017)","journal-title":"Comb. Probab. Comput."},{"key":"2909_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.dam.2024.02.012","volume":"349","author":"T Pham","year":"2024","unstructured":"Pham, T.: Parallelograms and the VC-dimension of the distance sets. Discrete Appl. Math. 349, 195\u2013200 (2024)","journal-title":"Discrete Appl. Math."},{"key":"2909_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.dam.2025.01.030","volume":"365","author":"T Pham","year":"2025","unstructured":"Pham, T., Senger, S., Tait, M., Thu-Huyen, N.: VC-dimension and pseudo-random graphs. Discrete Appl. Math. 365, 231\u2013246 (2025)","journal-title":"Discrete Appl. Math."},{"key":"2909_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcta.2017.02.006","volume":"150","author":"M Sharir","year":"2017","unstructured":"Sharir, M., Zahl, J.: Cutting algebraic curves into pseudo-segments and applications. J. Combin. Theory Ser. A 150, 1\u201335 (2017)","journal-title":"J. Combin. Theory Ser. A"},{"key":"2909_CR23","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"A Ya","year":"1971","unstructured":"Ya, A., Chervonenkis Vapnik, V.N.: Distinct distances between a collinear set and an arbitrary set of points. Theory Prob. Appl. 16, 264 (1971)","journal-title":"Theory Prob. Appl."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02909-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02909-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02909-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T06:17:07Z","timestamp":1746253027000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02909-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,15]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["2909"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02909-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,3,15]]},"assertion":[{"value":"19 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"47"}}