2021/08/30 by Fitzpatrick, D., Iosevich, A., McDonald, B. +1 · 1 citation
#11L40 #14N10 #42B10 #68Q32 #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.13231
Let X be a set and \mathcal H a collection of functions from X to \0,1\. We say that \mathcal H shatters a finite set C ⊂ X if the restriction of \mathcal H yields every possible function from C to \0,1\. The VC-dimension of \mathcal H is the largest number d such that there exists a set of size d shattered by \mathcal H, and no set of size d+1 is shattered by \mathcal 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 \mathcal H defined on \Bbb Fqd, the d-dimensional vector space over the finite field with q elements. Define \mathcal Hdt=\hy(x): y ∈ \Bbb Fqd \, where for x ∈ \Bbb Fqd, hy(x)=1 if ||x-y||=t, and 0 otherwise, where here, and throughout, ||x||=x12+x22+…+xd2. Here t ∈ \Bbb Fq, t \not=0. Define \mathcal Htd(E) the same way with respect to E ⊂ \Bbb Fqd. 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| ≥ Cq(15)/(8), the VC-dimension of \mathcal H2t(E) is equal to 3. This leads to an intricate configuration problem which is interesting in its own right and requires a new approach.