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

About 4 years old · traced to

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

Γ(r)={xr:x∈Fq×}⊆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)=VCdim⁡Fq(Γ(r))log⁡2q,α‾(r)=lim inf⁡q→∞α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, VCdim⁡Fq(Γ(r))=(1+or(1))log⁡2q\operatorname{VCdim}_{\mathbb{F}_q}(\Gamma^{(r)})=(1+o_r(1))\log_2q as q→∞q\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.

References

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.