ID: 2210.03789

The VC-dimension of quadratic residues in finite fields

October 7, 2022

View on ArXiv
Brian McDonald, Anurag Sahay, Emmett L. Wyman
Mathematics
Combinatorics
Number Theory

We study the Vapnik-Chervonenkis (VC) dimension of the set of quadratic residues (i.e. squares) in finite fields, $\mathbb F_q$, when considered as a subset of the additive group. We conjecture that as $q \to \infty$, the squares have the maximum possible VC-dimension, viz. $(1+o(1))\log_2 q$. We prove, using the Weil bound for multiplicative character sums, that the VC-dimension is $\geq (\frac{1}{2} + o(1))\log_2 q$. We also provide numerical evidence for our conjectures. The results generalize to multiplicative subgroups $\Gamma \subseteq \mathbb F_q^\times$ of bounded index.

Similar papers 1

Ilya D. Shkredov
Number Theory
Combinatorics

In our paper, we apply additive-combinatorial methods to study the distribution of the set of squares $\mathcal{R}$ in the prime field. We obtain the best upper bound on the number of gaps in $\mathcal{R}$ at the moment and generalize this result for sets with small doubling.

VC-Dimension of Hyperplanes over Finite Fields

July 19, 2023

85% Match
Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J. Miller, ... , Iannuzzelli Santiago Velazquez
Combinatorics

Let $\mathbb{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$ and a fixed nonzero $t\in \mathbb{F}_q$, let $\mathcal{H}_t(E)=\{h_y: y\in E\}$, where $h_y$ is the indicator function of the set $\{x\in E: x\cdot y=t\}$. Two of the authors, with Maxwell Sun, showed in the case $d=3$ that if $|E|\geq Cq^{\frac{11}{4}}$ and $q$ is sufficiently large, then the VC-dimension of $\mathcal{H}_t(E)$ is 3. In th...

Find SimilarView on arXiv

The VC-dimension and point configurations in ${\Bbb F}_q^2$

August 30, 2021

85% Match
D. Fitzpatrick, A. Iosevich, ... , Wyman E.
Combinatorics
Classical Analysis and ODEs

Let $X$ be a set and ${\mathcal H}$ a collection of functions from $X$ to $\{0,1\}$. We say that ${\mathcal H}$ shatters a finite set $C \subset X$ if the restriction of ${\mathcal H}$ yields every possible function from $C$ to $\{0,1\}$. The VC-dimension of ${\mathcal H}$ is the largest number $d$ such that there exists a set of size $d$ shattered by ${\mathcal H}$, and no set of size $d+1$ is shattered by ${\mathcal H}$. Vapnik and Chervonenkis introduced this idea in the e...

Find SimilarView on arXiv

On squares in special sets of finite fields

February 21, 2016

84% Match
Mikhail Gabdullin
Number Theory

We consider the linear vector space formed by the elements of the finite fields $\mathbb{F}_q$ with $q=p^r$ over $\mathbb{F}_p$. Let $\{a_1,\ldots,a_r\}$ be a basis of this space. Then the elements $x$ of $\mathbb{F}_q$ have a unique representation in the form $\sum_{j=1}^r c_ja_j$ with $c_j\in\mathbb{F}_p$. Let $D_1,\ldots,D_r$ be subsets of $\mathbb{F}_p$. We consider the set $W=W(D_1,\ldots,D_r)$ of elements of $\mathbb{F}_q$ such that $c_j \in D_j$ for all $j=1,\ldots,r$....

Find SimilarView on arXiv

An improved point-line incidence bound over arbitrary finite fields via the VC-dimension theory

March 1, 2023

84% Match
Alex Iosevich, Thang Pham, ... , Tait Michael
Combinatorics
Number Theory

The main purpose of this paper is to prove that the point-line incidence bound due to Vinh (2011) over arbitrary finite fields can be improved in certain ranges by using tools from the VC-dimension theory. As consequences, a number of applications will be discussed in detail.

Find SimilarView on arXiv

Character sums over affine spaces and applications

July 9, 2020

84% Match
Lucas Reis
Number Theory

Given a finite field $\mathbb F_q$, a positive integer $n$ and an $\mathbb F_q$-affine space $\mathcal A\subseteq \mathbb F_{q^n}$, we provide a new bound on the sum $\sum_{a\in \mathcal A}\chi(a)$, where $\chi$ a multiplicative character of $\mathbb F_{q^n}$. We focus on the applicability of our estimate to results regarding the existence of special primitive elements in $\mathbb F_{q^n}$. In particular, we obtain substantial improvements on previous works.

Find SimilarView on arXiv

Dot products in ${\Bbb F}_q^3$ and the Vapnik-Chervonenkis dimension

March 6, 2022

84% Match
A. Iosevich, B. McDonald, M. Sun
Combinatorics
Classical Analysis and ODEs

Given a set $E \subset {\Bbb F}_q^3$, where ${\Bbb F}_q$ is the field with $q$ elements. Consider a set of "classifiers" ${\mathcal H}^3_t(E)=\{h_y: y \in E\}$, where $h_y(x)=1$ if $x \cdot y=t$, $x \in E$, and $0$ otherwise. We are going to prove that if $|E| \ge Cq^{\frac{11}{4}}$, with a sufficiently large constant $C>0$, then the Vapnik-Chervonenkis dimension of ${\mathcal H}^3_t(E)$ is equal to $3$. In particular, this means that for sufficiently large subsets of ${\Bbb ...

Find SimilarView on arXiv

Counting Additive Decompositions of Quadratic Residues in Finite Fields

March 11, 2014

84% Match
Simon R. Blackburn, Sergei V. Konyagin, Igor E. Shparlinski
Number Theory
Combinatorics

We say that a set $S$ is additively decomposed into two sets $A$ and $B$ if $S = \{a+b : a\in A, \ b \in B\}$. A. S\'ark\"ozy has recently conjectured that the set $Q$ of quadratic residues modulo a prime $p$ does not have nontrivial decompositions. Although various partial results towards this conjecture have been obtained, it is still open. Here we obtain a nontrivial upper bound on the number of such decompositions.

Find SimilarView on arXiv

Parallelograms and the VC-dimension of the distance sets

April 19, 2023

83% Match
Thang Pham
Combinatorics
Number Theory

In this paper, we study the distribution of parallelograms and rhombi in a given set in the plane over arbitrary finite fields $\mathbb{F}_q^2$. As an application, we improve a recent result due to Fitzpatrick, Iosevich, McDonald, and Wyman (2021) on the Vapnik-Chervonenkis dimension of the induced distance graph. Our proofs are based on the discrete Fourier analysis.

Find SimilarView on arXiv

VC-Dimension and Distance Chains in $\mathbb{F}_q^d$

October 6, 2022

83% Match
Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J. Miller, ... , Iannuzzelli Santiago Velazquez
Combinatorics
Classical Analysis and ODEs

Given a domain $X$ and a collection $\mathcal{H}$ of functions $h:X\to \{0,1\}$, the Vapnik-Chervonenkis (VC) dimension of $\mathcal{H}$ measures its complexity in an appropriate sense. In particular, the fundamental theorem of statistical learning says that a hypothesis class with finite VC-dimension is PAC learnable. Recent work by Fitzpatrick, Wyman, the fourth and seventh named authors studied the VC-dimension of a natural family of functions $\mathcal{H}_t^{'2}(E): \math...

Find SimilarView on arXiv