The maximum VC-dimension conjecture for bounded-index power subgroups

Let rr be a positive integer of bounded index, meaning r1r\ll 1, and let

Γ(r)={xr:xFq×}Fq×\Gamma^{(r)}=\{x^r:x\in\mathbb{F}_q^\times\}\subseteq\mathbb{F}_q^\times

be the subgroup of rrth powers in the finite field Fq\mathbb{F}_q. Define

αq(r)=VCdimFq(Γ(r))log2q,α(r)=lim infqαq(r).\alpha_q^{(r)}=\frac{\operatorname{VCdim}_{\mathbb{F}_q}(\Gamma^{(r)})}{\log_2q},\qquad \underline{\alpha}^{(r)}=\liminf_{q\to\infty}\alpha_q^{(r)}.

Maximum VC-dimension conjecture for power subgroups. One has

α(r)=1.\underline{\alpha}^{(r)}=1.

Consequently, VCdimFq(Γ(r))=(1+or(1))log2q\operatorname{VCdim}_{\mathbb{F}_q}(\Gamma^{(r)})=(1+o_r(1))\log_2q as qq\to\infty. This is stated as the bounded-index generalization of the quadratic-residue expectation; the supplied text says that analogous partial progress is proved, but does not give a resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Brian McDonald, Anurag Sahay and Emmett L. Wyman, “The VC-dimension of quadratic residues in finite fields”, arXiv:2210.03789 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.