The higher-residue conjecture for the VC-dimension of Cayley graphs

Fix an integer $r\geqslant 3$. For primes $N\equiv 1\pmod r$, let $S\subseteq(\mathbb{Z}/N\mathbb{Z})^\times$ be the multiplicative subgroup of $r$-th powers, and let $\Gamma=\operatorname{Cay}(\mathbb{Z}/N\mathbb{Z},S)$ be the Cayley graph with respect to the additive group of $\mathbb{Z}/N\mathbb{Z}$. The VC-dimension $\operatorname{VCdim}(\Gamma)$ is the maximum cardinality of a set shattered by the neighborhoods of $\Gamma$.

Higher-residue conjecture. As $N\to\infty$ through the primes congruent to $1$ modulo $r$,

$$\operatorname{VCdim}(\Gamma)=(1+o(1))\log_r N.$$

The conjecture is presented as an alternative to the cited McDonald–Sahay–Wyman prediction involving base $2$. The source also expects a natural generalization over finite fields, but that expectation is not itself included as a separate conjecture.