Steven Senger: Rich lines or planes in vector spaces over finite fields

This is just a little note. I visited my advisor, Alex Iosevich a few weeks ago. He has some undergraduates doing research, and they remarked that they could prove some result if they could show that a large subset of the three-dimensional vector space over a finite field must have some plane with a lot of points. It turns out that this statement, as well as a related statement in a two-dimensional vector space is not true in general. Here are the precise statements.

$\dpi{100} $There exists set $E\subset \mathbb{F}_q^3$ such that $|E|\gtrsim q^\frac{3}{2}$, and no plane contains $\gtrsim q$ points of the set $E$.$
Flat things and curved things share very little in common. So we consider a “sphere” in a vector space over a finite field. $\dpi{100} $ A ``sphere'' in of radius $r$ in $\mathbb{F}_q^d$ will be defined to be the set of points satisfying the equation $x_1^2+x_2^2+\dots +x_d^2=r.$ Note that we do not take a square root of the sum.$
The trick is to consider a special type of field, and consider a unit sphere in that field. $\dpi{100} $ Let $q=p^4$. Now, consider the sphere of radius one centered at the origin in the 3-dimensional vector space over the finite field of order $p^3$. The sphere has about $p^6= q^{3/2}$ points on it, and no plane will have more than about $p^3=q^{3/4}$ points.$

The statement in two dimensions is similar.
$\dpi{100} $There exists a set $E\subset\mathbb{F}_q^2$ such that $|E|\gtrsim q^\frac{3}{2}$, and no line contains more than $\gtrsim q^\frac{1}{2}$ points of the set $E$.$
Again, the proof involves curved things, but here, we use a slightly different approach.
$\dpi{100} $Let our set be the union of $q^{1/2}$ circles of different radii, centered at the origin. No line can hit any circle more than twice, so each line has fewer than $2q^{1/2}$ points from our set. Each circle has about $q$ points on it, for a grand total of $q^{3/2}$ points in our set.$

Clearly, there is plenty of room for more investigation here. I wonder how these statements would change if we were curious about the population of spheres and circles as opposed to lines and planes. It should be no surprise to anyone that knows me that this begins to look like the Erdős single distance problem.

2 comments:

AnonymousOctober 20, 2012 at 10:54 AM
Dvir and Lovett have a paper on "subspace evasive sets" where they prove that in F_q^3 there is a set S of size q^{3/2} such that any affine plane intersects S in at most 16 (!) points. This is theorem 1 of http://arxiv.org/pdf/1110.5696v1.pdf with n=3, epsilon=1/2, and k=2. Your construction is a lot simpler than theirs though...

Steven Senger

Monday, July 30, 2012

Rich lines or planes in vector spaces over finite fields

2 comments:

About Me