VC-Dimension of Hyperplanes over Finite Fields

2023/07/19 by Ascoli, Ruben, Betti, Livia, Cheigh, Justin +8 · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.10425

Abstract

Let \mathbbF_q^d be the d-dimensional vector space over the finite field with q elements. For a subset E⊆ \mathbbF_q^d and a fixed nonzero t∈ \mathbbF_q, let H_t(E)=\h_y: y∈ E\, where h_y is the indicator function of the set \x∈ E: x⋅ y=t\. Two of the authors, with Maxwell Sun, showed in the case d=3 that if |E|≥ Cq^(11)/(4) and q is sufficiently large, then the VC-dimension of H_t(E) is 3. In this paper, we generalize the result to arbitrary dimension and improve the exponent in the case d=3.

Cited by

• VC-dimension of Salem sets over finite fields
• Joint upper Banach density, VC dimensions and Euclidean point configurations
• The VC-dimension and point configurations in ℝ^d

Related

• The VC-dimension and point configurations in \Bbb F_q²
• VC-Dimension and Distance Chains in \mathbbF_q^d
• The VC-dimension and point configurations in ℝ^d
• Pinned distance sets, Wolff's exponent in finite fields and improved sum-product estimates
• VC-dimension of Salem sets over finite fields