Incidence bounds and applications over finite fields

2016/01/03 by Nguyễn Duy Phương, Phuong, Nguyen Duy, Thang Pham +7 · 1 citation
Computer Science · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1601.00290

openalex publication_date 2016/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we introduce a unified approach to deal with incidence problems between points and varieties over finite fields. More precisely, we prove that the number of incidences I(P, V) between a set P of points and a set V of varieties of a certain form satisfies \vert I(P,V)-(|P||V|)/(q^k)\vert≤ q^dk/2√(|P||V|). This result is a generalization of the results of Vinh (2011), Bennett et al. (2014), and Cilleruelo et al. (2015). As applications of our incidence bounds, we obtain results on the pinned value problem and the Beck type theorem for points and spheres. Using the approach introduced, we also obtain a result on the number of distinct distances between points and lines in \mathbbF_q², which is the finite field analogous of a recent result of Sharir et al. (2015).

Citations

• Further improvements to incidence and Beck-type bounds over prime finite fields
• Distinct distances between points and lines

Cited by

• Incidence theorems for multivariate polynomials over finite fields

Related

• A point-variety incidence theorem over finite fields, and its applications
• Incidences between points and generalized spheres over finite fields and\n related problems
• Explicit incidence bounds over general finite fields
• Elementary methods for incidence problems in finite fields
• A point-sphere incidence bound in odd dimensions and applications