VC-Dimension of Hyperplanes Over Finite Fields

Abstract

Abstract Let $$\mathbb {F}_q^d$$

F q d

be the d-dimensional vector space over the finite field with q elements. For a subset

$$E\subseteq \mathbb {F}_q^d$$

E ⊆

F q d

and a fixed nonzero

$$t\in \mathbb {F}_q$$

t ∈

F q

, let

$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$

H t

( E )

=

{

h y

: y ∈ E }

, where

$$h_y:E\rightarrow \{0,1\}$$

h y

: E →

{ 0 , 1 }

is the indicator function of the set

$$\{x\in E: x\cdot y=t\}$$

{ x ∈ E : x · y = t }

. Two of the authors, with Maxwell Sun, showed in the case

$$d=3$$

d = 3

that if

$$|E|\ge Cq^{\frac{11}{4}}$$

| E |

≥ C

q

11 4

and q is sufficiently large, then the VC-dimension of

$$\mathcal {H}_t(E)$$

H t

( E )

is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of

$$\mathcal {H}_t(E)$$

H t

( E )

is d whenever

$$E\subseteq \mathbb {F}_q^d$$

E ⊆

F q d

with

$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$

| E |

≥

C d

q

d -

1

d - 1

.