1. The VC-Dimension and Point Configurations in Fq2.
- Author
-
Fitzpatrick, David, Iosevich, Alex, McDonald, Brian, and Wyman, Emmett
- Subjects
- *
FINITE fields , *VECTOR spaces , *STATISTICAL sampling - Abstract
Let X be a set and H a collection of functions from X to { 0 , 1 } . We say that H shatters a finite set C ⊂ X if the restriction of H yields every possible function from C to { 0 , 1 } . The VC-dimension of H is the largest number d such that there exists a set of size d shattered by H , and no set of size d + 1 is shattered by H . Vapnik and Chervonenkis introduced this idea in the early 70s in the context of learning theory, and this idea has also had a significant impact on other areas of mathematics. In this paper we study the VC-dimension of a class of functions H defined on F q d , the d-dimensional vector space over the finite field with q elements. Define H t d = { h y (x) : y ∈ F q d } , where for x ∈ F q d , h y (x) = 1 if ‖ x - y ‖ = t , and 0 otherwise, where here, and throughout, ‖ x ‖ = x 1 2 + x 2 2 + ⋯ + x d 2 . Here t ∈ F q , t ≠ 0 . Define H t d (E) the same way with respect to E ⊂ F q d . The learning task here is to find a sphere of radius t centered at some point y ∈ E unknown to the learner. The learning process consists of taking random samples of elements of E of sufficiently large size. We are going to prove that when d = 2 , and | E | ⩾ C q 15 / 8 , the VC-dimension of H t 2 (E) is equal to 3. This leads to an intricate configuration problem which is interesting in its own right and requires a new approach. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF