Korean J. Math. Vol. 32 No. 1 (2024) pp.43-57
DOI: https://doi.org/10.11568/kjm.2024.32.1.43

VC-dimension and distance chains in $\mathbb{F}_q^d$

Main Article Content

Ruben Ascoli
Livia Betti
Justin Cheigh
Alex Iosevich
Ryan Jeong
Xuyan Liu
Brian McDonald
Wyatt Milgrim
Steven J. Miller
Francisco Romero Acosta
Santiago Velazquez Iannuzzelli


Given a domain $X$ and a collection $\mathcal{H}$ of functions $h:X\to \{0,1\}$, the Vapnik-Chervonenkis (VC) dimension of $\mathcal{H}$ measures its complexity in an appropriate sense. In particular, the fundamental theorem of statistical learning says that a hypothesis class with finite VC-dimension is PAC learnable. Recent work by Fitzpatrick, Wyman, the fourth and seventh named authors studied the VC-dimension of a natural family of functions $\mathcal{H}_t^{'2}(E): \mathbb{F}_q^2\to \{0,1\}$, corresponding to indicator functions of circles centered at points in a subset $E\subseteq \mathbb{F}_q^2$. They showed that when $|E|$ is large enough, the VC-dimension of $\mathcal{H}_t^{'2}(E)$ is the same as in the case that $E = \mathbb F_q^2$. We study a related hypothesis class, $\mathcal{H}_t^d(E)$, corresponding to intersections of spheres in $\mathbb{F}_q^d$, and ask how large $E\subseteq \mathbb{F}_q^d$ needs to be to ensure the maximum possible VC-dimension. We resolve this problem in all dimensions, proving that whenever $|E|\geq C_dq^{d-1/(d-1)}$ for $d\geq 3$, the VC-dimension of $\mathcal{H}_t^d(E)$ is as large as possible. We get a slightly stronger result if $d=3$: this result holds as long as $|E|\geq C_3 q^{7/3}$. Furthermore, when $d=2$ the result holds when $|E|\geq C_2 q^{7/4}$.

Article Details

Supporting Agencies

NSF grant DMS1947438 and Williams College University of Michigan NSF grant HDR TRIPODS - 1934962 and NSF grant DMS2154232


[1] M. Bennett, J. Chapman, D. Covert, D. Hart, A. Iosevich, J. Pakianathan, Long paths in the distance graph over large subsets of vector spaces over finite fields, Korean Math. Soc. 53 (1) (2016), 115–126. https://doi.org/10.4134/JKMS.2016.53.1.115 Google Scholar

[2] M. Bennett, D. Hart, A. Iosevich, J. Pakianathan, M. Rudnev, Group actions and geometric combinatorics in Fdq , Forum Math. 29 (1) (2017), 91–110. https://doi.org/10.1515/forum-2015-0251 Google Scholar

[3] D. Fitzpatrick, A. Iosevich, B. McDonald, E. Wyman, The VC-dimension and point configurations in F2q, Discrete Comput. Geom. (2023). https://doi.org/10.1007/s00454-023-00570-5 Google Scholar

[4] D. Hart, A. Iosevich, D. Koh, S. Senger, I. Uriarte-Tuero, Distance graphs in vector spaces over finite fields, Recent advances in harmonic analysis and applications (2013), 139–160. https://doi.org/10.1007/978-1-4614-4565-4_14 Google Scholar

[5] A. Iosevich, G. Jardine, B. McDonald, Cycles of arbitrary length in distance graphs on Fdq, Tr. Mat. Inst. Steklova 314 (1) (2021) 27–43. https://doi.org/10.1134/S0081543821040027 Google Scholar

[6] A. Iosevich, B. McDonald, M. Sun, Dot products in F3q and the Vapnik-Chervonenkis dimension, Discrete Math. 346 (1) (2023), Paper No. 113096. https://doi.org/10.1016/j.disc.2022.113096 Google Scholar

[7] A. Iosevich, H. Parshall, Embedding distance graphs in finite field vector spaces, J. Korean Math. Soc. 56 (6) (2019), 1515–1528. https://doi.org/10.4134/JKMS.j180776 Google Scholar

[8] A. Iosevich, M. Rudnev, Erdos distance problem in vector spaces over finite fields, Trans. Amer. Math. Soc 359 (12) (2007), 6127–6142. https://doi.org/10.48550/arXiv.math/0509005 Google Scholar

[9] M. Kearns, U. Vazirani, An introduction to computational learning theory, MIT press, 1994. https://doi.org/10.7551/mitpress/3897.001.0001 Google Scholar

[10] H. Minkowski, Grundlagen fu ̈r eine Theorie quadratischen Formen mit ganzahligen Koeffizienten, Gesammelte Abhandlungen (1911), 3–145. https://doi.org/10.1007/978-3-540-34720-0_18 Google Scholar

[11] S. Shalev-Shwartz, S. Ben-David, Understanding machine learning: From theory to algorithms, Cambridge university press, 2014. https://doi.org/10.1017/CBO9781107298019 Google Scholar