VC-Dimension of Hyperplanes Over Finite Fields

Abstract Let $$\mathbb {F}_q^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mi>d</mml:mi> </mml:msubsup> </mml:math> be the d -dimensional vector space over the finite field with q elements. For a subset $$E\subseteq \mathbb {F}_q^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>E</mml:mi> <mml:mo>⊆</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mi>d</mml:mi> </mml:msubsup> </mml:mrow> </mml:math> and a fixed nonzero $$t\in \mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>∈</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:mrow> </mml:math> , let $$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>H</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:msub> <mml:mi>h</mml:mi> <mml:mi>y</mml:mi> </mml:msub> <mml:mo>:</mml:mo> <mml:mi>y</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$h_y:E\rightarrow \{0,1\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>h</mml:mi> <mml:mi>y</mml:mi> </mml:msub> <mml:mo>:</mml:mo> <mml:mi>E</mml:mi> <mml:mo>→</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is the indicator function of the set $$\{x\in E: x\cdot y=t\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>x</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> <mml:mo>:</mml:mo> <mml:mi>x</mml:mi> <mml:mo>·</mml:mo> <mml:mi>y</mml:mi> <mml:mo>=</mml:mo> <mml:mi>t</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . Two of the authors, with Maxwell Sun, showed in the case $$d=3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> that if $$|E|\ge Cq^{\frac{11}{4}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>E</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mi>C</mml:mi> <mml:msup> <mml:mi>q</mml:mi> <mml:mfrac> <mml:mn>11</mml:mn> <mml:mn>4</mml:mn> </mml:mfrac> </mml:msup> </mml:mrow> </mml:math> and q is sufficiently large, then the VC-dimension of $$\mathcal {H}_t(E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>H</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of $$\mathcal {H}_t(E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>H</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is d whenever $$E\subseteq \mathbb {F}_q^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>E</mml:mi> <mml:mo>⊆</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mi>d</mml:mi> </mml:msubsup> </mml:mrow> </mml:math> with $$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>E</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>d</mml:mi> </mml:msub> <mml:msup> <mml:mi>q</mml:mi> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> .