Graphs and Combinatorics Discrete Mathematics and Combinatorics

VC-Dimension of Hyperplanes Over Finite Fields

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
Springer Nature · 2025-03-15 · DOI 10.1007/s00373-025-02909-6

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 .

Read at publisher →