Parallelograms and the VC-dimension of the distance sets

Abstract

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.

9 pages