Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T05:00:14.674Z Has data issue: false hasContentIssue false
  • English
  • Français

AN EXPLICIT INCIDENCE THEOREM IN 𝔽p

Part of: Discrete mathematics in relation to computer science Sequences and sets

Published online by Cambridge University Press:  13 December 2010

Harald Andrés Helfgott  and
Misha Rudnev
Harald Andrés Helfgott
Affiliation:
Department of Mathematics, University of Bristol, Bristol BS8 1TW, U.K. (email: [email protected])
Misha Rudnev
Affiliation:
Department of Mathematics, University of Bristol, Bristol BS8 1TW, U.K. (email: [email protected])
Get access

Abstract

Let P=A×A⊂𝔽p×𝔽p, p a prime. Assume that P=A×A has n elements, n<p. See P as a set of points in the plane over 𝔽p. We show that the pairs of points in P determine lines, where c is an absolute constant. We derive from this an incidence theorem: the number of incidences between a set of n points and a set of n lines in the projective plane over 𝔽p (n<p)is bounded by , where C is an absolute constant.

MSC classification

Secondary: 68R05: Combinatorics 11B75: Other combinatorial number theory
Type
Research Article
Information
Mathematika , Volume 57 , Issue 1 , January 2011 , pp. 135 - 145
Copyright
Copyright © University College London 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Beck, J., On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdos̈ in combinatorial geometry. Combinatorica 3 (1983), 281–297.Google Scholar
[2]Bourgain, J., Multilinear exponential sums in prime fields under optimal Entropy Condition on the Source. Geom. Funct. Anal. 18 (2009), 1477–1502.Google Scholar
[3]Bourgain, J. and Garaev, M. Z., On a variant of sum–product estimates and explicit exponential sum bounds in prime fields. Math. Proc. Cambridge Philos. Soc. 146(1) (2009), 1–21.Google Scholar
[4]Bourgain, J., Katz, N. and Tao, T., A sum–product estimate in finite fields and their applications. Geom. Funct. Anal. 14 (2004), 27–57.Google Scholar
[5]Fox, J. and Sudakov, B., Dependent random choice. Preprint, 2009, arXiv:math/0909.3271, 31pp.Google Scholar
[6]Garaev, M. Z., An explicit sum–product estimate in 𝔽p. Int. Math. Res. Not. (11) (2007), 1–11.Google Scholar
[7]Katz, N. H. and Shen, C.-Y., A slight improvement to Garaev’s sum product estimate. Proc. Amer. Math. Soc. 136 (2008), 2499–2504.CrossRefGoogle Scholar
[8]Konyagin, S. V., A sum–product estimate in fields of prime order. Preprint, 2003, arXiv:math/0304217, 9pp.Google Scholar
[9]Li, L., Slightly improved sum–product estimates in fields of prime order. Preprint, 2009, arXiv:math/0907.2051, 9pp.Google Scholar
[10]Ruzsa, I. Z., An application of graph theory to additive number theory. Sci. Ser. A 3 (1989), 97–109.Google Scholar
[11]Shen, C.-Y., Quantitative sum product estimates on different sets. Electron. J. Combin. 15(1) (2008), 7 Note 40.Google Scholar
[12]Szemerédi, E. and Trotter, W. T., Extremal problems in discrete geometry. Combinatorica 3 (1983), 381–392.CrossRefGoogle Scholar
[13]Tao, T. and Vu, V., Additive Combinatorics, Cambridge University Press (Cambridge, 2006), 530.Google Scholar
[14]Vinh, L. A., Szemerédi–Trotter type theorem and sum–product estimate in finite fields. European J. Combin. (2010) (to appear).Google Scholar