Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathbb {F}_q^d$</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mi>d</mi> </msubsup> </math></EquationSource> </InlineEquation> be the d-dimensional vector space over the finite field with q elements. For a subset <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">$E\subseteq \mathbb {F}_q^d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo>⊆</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mi>d</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation> and a fixed nonzero <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$t\in \mathbb {F}_q$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>∈</mo> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, let <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="163" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {H}_t(E)=\{h_y: y\in E\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="script">H</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">{</mo> <msub> <mi>h</mi> <mi>y</mi> </msub> <mo>:</mo> <mi>y</mi> <mo>∈</mo> <mi>E</mi> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="116" /> </InlineMediaObject> <EquationSource Format="TEX">$h_y:E\rightarrow \{0,1\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>h</mi> <mi>y</mi> </msub> <mo>:</mo> <mi>E</mi> <mo stretchy="false">→</mo> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the indicator function of the set <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="140" /> </InlineMediaObject> <EquationSource Format="TEX">$\{x\in E: x\cdot y=t\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mi>x</mi> <mo>∈</mo> <mi>E</mi> <mo>:</mo> <mi>x</mi> <mo>·</mo> <mi>y</mi> <mo>=</mo> <mi>t</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. Two of the authors, with Maxwell Sun, showed in the case <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$d=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> that if <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq8.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">$|E|\ge Cq^{\frac{11}{4}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi>E</mi> <mo stretchy="false">|</mo> </mrow> <mo>≥</mo> <mi>C</mi> <msup> <mi>q</mi> <mfrac> <mn>11</mn> <mn>4</mn> </mfrac> </msup> </mrow> </math></EquationSource> </InlineEquation> and q is sufficiently large, then the VC-dimension of <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {H}_t(E)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="script">H</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {H}_t(E)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="script">H</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is d whenever <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq11.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">$E\subseteq \mathbb {F}_q^d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo>⊆</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mi>d</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2909_Article_IEq12.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="110" /> </InlineMediaObject> <EquationSource Format="TEX">$|E|\ge C_d q^{d-\frac{1}{d-1}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi>E</mi> <mo stretchy="false">|</mo> </mrow> <mo>≥</mo> <msub> <mi>C</mi> <mi>d</mi> </msub> <msup> <mi>q</mi> <mrow> <mi>d</mi> <mo>-</mo> <mfrac> <mn>1</mn> <mrow> <mi>d</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>.

VC-Dimension of Hyperplanes Over Finite Fields

期刊论文
出版模式：

开放获取
发表日期：

2025年3月15日

查看全文

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

摘要

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 \subseteq F_{q}^{d}$ and a fixed nonzero $t\in \mathbb {F}_q$ $t \in F_{q}$ , let $\mathcal {H}_t(E)=\{h_y: y\in E\}$ $H_{t} (E) = {h_{y} : y \in E}$ , where $h_y:E\rightarrow \{0,1\}$ $h_{y} : E \to {0, 1}$ is the indicator function of the set $\{x\in E: x\cdot y=t\}$ ${x \in E : x \cdot 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 | \geq C q^{\frac{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 \subseteq F_{q}^{d}$ with $|E|\ge C_d q^{d-\frac{1}{d-1}}$ $| E | \geq C_{d} q^{d - \frac{1}{d - 1}}$ .