VC-Dimension of Salem sets over finite fields

Moustapha Diallo, Brian McDonald · 2025

Read VC-Dimension of Salem sets over finite fields by Moustapha Diallo, Brian McDonald (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08963.txt.

Description

Moustapha Diallo and Brian McDonald connect a learning theory measure, VC-dimension, to the geometry of structured point sets over finite fields. For a family of shapes such as spheres or hyperplanes, lower-bounding the VC-dimension of the classes they define on a set amounts to building intricate geometric configurations inside that set.

The sets in question are Salem sets, which balance randomness and structure in a precise Fourier sense. The authors show that many techniques developed for distance problems over finite fields extend to a far broader setting that does not depend on the special geometry of circles and spheres. Their unified framework handles highly structured sets like algebraic curves and random sets within the same argument. The work ties the Erdős distance problem and its Falconer cousin to modern questions about the complexity of geometric hypothesis classes.

Catalog record

CREATORMoustapha Diallo, Brian McDonald
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08963

Browse the full library · About the Tower of Babel