The VC-dimension and point configurations in $\mathbb{R}^d$
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912651279335424 |
|---|---|
| author | Iosevich, Alex Magyar, Akos McDonald, Alex McDonald, Brian |
| author_facet | Iosevich, Alex Magyar, Akos McDonald, Alex McDonald, Brian |
| contents | Given a set $X$ and a collection ${\mathcal H}$ of functions from $X$ to $\{0,1\}$, the VC-dimension measures the complexity of the hypothesis class $\mathcal{H}$ in the context of PAC learning. In recent years, this has been connected to geometric configuration problems in vector spaces over finite fields. In particular, it is easy to show that the VC-dimension of the set of spheres of a given radius in $\mathbb{F}_q^d$ is equal to $d+1$, since this is how many points generically determine a sphere. It is known that for $E\subseteq \mathbb{F}_q^d$, $|E|\geq q^{d-\frac{1}{d-1}}$, the set of spheres centered at points in $E$, and intersected with the set $E$, has VC-dimension either $d$ or $d+1$.
In this paper, we study a similar question over Euclidean space. We find an explicit dimensional threshold $s_d<d$ so that whenever $E\subseteq \mathbb{R}^d$, $d\geq 3$, and the Hausdorff dimension of $E$ is at least $s_d$, it follows that there exists an interval $I$ such that for any $t\in I$, the VC-dimension of the set of spheres of radius $t$ centered at points in $E$, and intersected with $E$, is at least $3$. In the process of proving this theorem, we also provide the first explicit dimensional threshold for a set $E\subseteq \mathbb{R}^3$ to contain a $4$-cycle, i.e. $x_1,x_2,x_3,x_4\in E$ satisfying $$ |x_1-x_2|=|x_2-x_3|=|x_3-x_4|=|x_4-x_1| $$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13984 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The VC-dimension and point configurations in $\mathbb{R}^d$ Iosevich, Alex Magyar, Akos McDonald, Alex McDonald, Brian Classical Analysis and ODEs 28A78, 28A80, 42B10 Given a set $X$ and a collection ${\mathcal H}$ of functions from $X$ to $\{0,1\}$, the VC-dimension measures the complexity of the hypothesis class $\mathcal{H}$ in the context of PAC learning. In recent years, this has been connected to geometric configuration problems in vector spaces over finite fields. In particular, it is easy to show that the VC-dimension of the set of spheres of a given radius in $\mathbb{F}_q^d$ is equal to $d+1$, since this is how many points generically determine a sphere. It is known that for $E\subseteq \mathbb{F}_q^d$, $|E|\geq q^{d-\frac{1}{d-1}}$, the set of spheres centered at points in $E$, and intersected with the set $E$, has VC-dimension either $d$ or $d+1$. In this paper, we study a similar question over Euclidean space. We find an explicit dimensional threshold $s_d<d$ so that whenever $E\subseteq \mathbb{R}^d$, $d\geq 3$, and the Hausdorff dimension of $E$ is at least $s_d$, it follows that there exists an interval $I$ such that for any $t\in I$, the VC-dimension of the set of spheres of radius $t$ centered at points in $E$, and intersected with $E$, is at least $3$. In the process of proving this theorem, we also provide the first explicit dimensional threshold for a set $E\subseteq \mathbb{R}^3$ to contain a $4$-cycle, i.e. $x_1,x_2,x_3,x_4\in E$ satisfying $$ |x_1-x_2|=|x_2-x_3|=|x_3-x_4|=|x_4-x_1| $$ |
| title | The VC-dimension and point configurations in $\mathbb{R}^d$ |
| topic | Classical Analysis and ODEs 28A78, 28A80, 42B10 |
| url | https://arxiv.org/abs/2510.13984 |