Infoscience

Journal article

Incidences between points and generalized spheres over finite fields and related problems

Let F-q be a finite field of q elements, where q is a large odd prime power and Q = a(1)x(1)(c1) + ..... + a(d)x(d)(cd) is an element of F-q[x(1) ,...,x(d)], where 2 <= c(i) <= N, gcd(c(i), q) = 1, and a(i) is an element of F-q for all 1 <= i <= d. A Q-sphere is a set of the form {x is an element of F-q(d) vertical bar Q(x - b) = r}, where b epsilon F-q(d) r is an element of F-q. We prove bounds on the number of incidences between a point set P and a Q-sphere set S, denoted by I(P, S), as the following: vertical bar I(P,S)-vertical bar P parallel to S vertical bar/q vertical bar <= q(d/2) root vertical bar P parallel to S vertical bar. We also give a version of this estimate over finite cyclic rings Z/qZ, where q is an odd integer. As a consequence of the above bounds, we give an estimate for the pinned distance problem and a bound on the number of incidences between a random point set and a random Q-sphere set in F-q(d). We also study the finite field analogues of some combinatorial geometry problems, namely, the number of generalized isosceles triangles, and the existence of a large subset without repeated generalized distances.

Fulltext

Related material