Let q tend to infinity through prime powers, and let obreakS_q denote the set of squares in the finite field obreakF_q, viewed as a subset of its additive group. Write alpha_q=fracoperatornameVCdim_F_q(S_q)log_2 q,qquad underlinealpha=liminf_q→∞alpha_q. Maximum VC-dimension conjecture. One has underlinealpha=1. Equivalently, obreak operatornameVCdim_F_q(S_q)=(1+o(1))log_2q as q→∞; in particular, the squares have asymptotically the maximum possible VC-dimension. The paper presents this as a natural expectation motivated by the multiplicative structure of the squares and the pseudorandomness of their interaction with addition; the conjecture is not resolved in the supplied text.

The maximum VC-dimension conjecture for quadratic residues

Let $q$ tend to infinity through prime powers, and let $obreak\mathcal{S}_q$ denote the set of squares in the finite field $obreak\mathbb{F}_q$ , viewed as a subset of its additive group. Write

\alpha_q=\frac{\operatorname{VCdim}_{\mathbb{F}_q}(\mathcal{S}_q)}{\log_2 q},\qquad \underline{\alpha}=\liminf_{q\to\infty}\alpha_q.

Maximum VC-dimension conjecture. One has

\underline{\alpha}=1.

Equivalently, $obreak\operatorname{VCdim}_{\mathbb{F}_q}(\mathcal{S}_q)=(1+o(1))\log_2q$ as $q\to\infty$ ; in particular, the squares have asymptotically the maximum possible VC-dimension. The paper presents this as a natural expectation motivated by the multiplicative structure of the squares and the pseudorandomness of their interaction with addition; the conjecture is not resolved in the supplied text.

On October 7, 2022, the paper formulated the conjecture that the squares in a large finite field have essentially the largest possible complexity when tested by additive patterns. In symbols, it predicts $\underline{\alpha}=1$ , equivalently $\operatorname{VCdim}_{\mathbb{F}_q}(\mathcal{S}_q)=(1+o(1))\log_2 q$ .

Known results

The 2022 paper proves only $\underline{\alpha}\geqslant\tfrac12$ ; hence $\operatorname{VCdim}_{\mathbb{F}_q}(\mathcal{S}_q)\geqslant(\tfrac12-\epsilon)\log_2 q$ for every $\epsilon>0$ and sufficiently large $q$ .
For primes $5\leqslant q\leqslant300$ , computations found $\lfloor\log_2q\rfloor-1$ for about $57\%$ of primes and the maximum $\lfloor\log_2q\rfloor$ for the rest.
The lower bound $\operatorname{VCdim}(\mathcal{S}_q)\geqslant\lfloor\log_2q\rfloor-1$ was computationally verified for primes through $512$ .

Later related paper (date not stated)

A later arXiv paper places the question within the McDonald–Sahay–Wyman conjecture for multiplicative subgroups, but reports no proof, counterexample, or improvement for quadratic residues.

Current status (as of September 2026): the conjecture is open; only the asymptotic lower bound $\underline{\alpha}\geqslant\tfrac12$ and supporting computations are recorded, with no public resolution found.

The maximum VC-dimension conjecture for quadratic residues

Primary source

Progress summary

Solutions 0