Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Sets with integral distances in finite fields


Authors: Alex Iosevich, Igor E. Shparlinski and Maosheng Xiong
Journal: Trans. Amer. Math. Soc. 362 (2010), 2189-2204
MSC (2000): Primary 05B25, 11T23, 52C10
DOI: https://doi.org/10.1090/S0002-9947-09-05004-1
Published electronically: November 17, 2009
MathSciNet review: 2574892
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a positive integer $ n$, a finite field $ \mathbb{F}_q$ of $ q$ elements ($ q$ odd), and a non-degenerate quadratic form $ Q$ on $ \mathbb{F}_q^n$, in this paper we study the largest possible cardinality of subsets $ \mathcal{E} \subseteq \mathbb{F}_q^n$ with pairwise integral $ Q$-distances; that is, for any two vectors $ {\bf {x}}=(x_1, \ldots,x_n), {\bf {y}}=(y_1,\ldots,y_n) \in \mathcal{E}$, one has

$\displaystyle Q({\bf {x}}-{\bf {y}})=u^2$

for some $ u \in \mathbb{F}_q$.


References [Enhancements On Off] (What's this?)

  • 1. N. H. Anning and P. Erdős, Integral distances, Bull. Amer. Math. Soc., 51 (1945), 598-600. MR 0013511 (7:164a)
  • 2. S. Ball, The number of directions determined by a function over a function field, J. Comb. Theory, Ser. A., 104 (2003), no. 2, 341-350. MR 2019280 (2005c:05039)
  • 3. E. Bannai, O. Shimanukuro and H. Tanaka, Finite analogues of non-Euclidean graphs and Ramanujan graphs, European J. Combin., 25 (2004), 243-259. MR 2070545 (2005g:05066)
  • 4. A. Blokhuis, S. Ball, A. Brouwer, L. Storme and T. Szőnyi, On the number of slopes of the graph of a function defined on a finite field, J. Comb. Theory, Ser. A., 86 (1999), no. 1, 187-196. MR 1682973 (2000g:05039)
  • 5. J. Bourgain, N. Katz and T. Tao, A sum-product estimate in finite fields, and applications, Geom. Funct. Anal., 14 (2004), 27-57. MR 2053599 (2005d:11028)
  • 6. A. M. Childs, L. J. Schulman and U. V. Vazirani, Quantum algorithms for hidden nonlinear structures, Proc. 48th IEEE Symp. on Found. Comp. Sci., IEEE, 2007, 395-404.
  • 7. D. Covert, D. Hart, A. Iosevich, D. Koh and M. Rudnev, Generalized incidence theorems, homogeneous forms and sum-product estimates in finite fields, European J. Combinatorics (to appear).
  • 8. D. Hart, A. Iosevich, D. Koh, S. Senger and I. Uriarte-Tuero, Distance graphs in vector spaces over finite fields, coloring and pseudo-randomness, Preprint, 2008 (available from http://arxiv.org/abs/0804.3036).
  • 9. D. Hart, A. Iosevich, D. Koh and M. Rudnev, Averages over hyperplanes, sum-product theory in finite fields, and the Erdős-Falconer distance conjecture, Trans. Amer. Math. Soc. (to appear).
  • 10. A. Iosevich and M. Rudnev, A combinatorial approach to orthogonal exponentials, Intern. Math. Research Notices, 49, (2003), 1-12.
  • 11. A. Iosevich and M. Rudnev, Erdős distance problem in vector spaces over finite fields, Trans. Amer. Math. Soc., 359 (2007), 6127-6142. MR 2336319 (2008k:11130)
  • 12. H. Iwaniec and E. Kowalski, ``Analytic number theory'', Amer. Math. Soc., Providence, RI, 2004. MR 2061214 (2005h:11005)
  • 13. M. Kiermaier and S. Kurz, Maximal integral point sets in affine planes over finite fields, Discrete Mathematics 309 (2009), 4564-4575. MR 2519195
  • 14. S. Kurz, Integral point sets over finite fields, Australasian J. Combin. 43 (2009), 3-29. MR 2489406
  • 15. S. Lang, ``Algebra'', Revised 3rd Edition, Graduate Texts in Mathematics 211, Springer, 2002. MR 1878556 (2003e:00003)
  • 16. R. Lidl and H. Niederreiter, ``Finite fields'', Cambridge University Press, Cambridge, 1997. MR 1429394 (97i:11115)
  • 17. A. Medrano, P. Myers, H.M. Stark and A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math., 68 (1996), 221-238. MR 1418760 (97k:11172)
  • 18. A. Medrano, P. Myers, H.M. Stark and A. Terras, Finite Euclidean graphs over rings, Proc. Amer. Math. Soc., 126 (1998), 701-710. MR 1443395 (98j:11118)
  • 19. G. Mockenhaupt and T. Tao, Restriction and Kakeya phenomena for finite fields, Duke Math. J., 121 (2004), 35-74. MR 2031165 (2004m:11200)
  • 20. J. Solymosi, Note on integral distances, Discrete Comput. Geom., 30 (2003), 337-342. MR 2007970 (2004g:52029)
  • 21. T. Wolff, Decay of circular means of Fourier transforms of measures, Internat. Math. Res. Notices, 10 (1999), 547-567. MR 1692851 (2000k:42016)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05B25, 11T23, 52C10

Retrieve articles in all journals with MSC (2000): 05B25, 11T23, 52C10


Additional Information

Alex Iosevich
Affiliation: Department of Mathematics, University of Missouri, Columbia, Missouri 65211
Email: iosevich@math.missouri.edu

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
Email: igor@ics.mq.edu.au

Maosheng Xiong
Affiliation: Department of Mathematics, Eberly College of Science, Pennsylvania State University, State College, Pennsylvania 16802
Email: xiong@math.psu.edu

DOI: https://doi.org/10.1090/S0002-9947-09-05004-1
Keywords: Integral distances, Gauss sums
Received by editor(s): September 10, 2008
Published electronically: November 17, 2009
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society