6
$\begingroup$

The original version of the so-called "joints problem" consists of the following:

Let $L$ be a set of lines in $\mathbb{R}^{3}$. Determine the maximum number of "joints" determined by these lines, where by joint we understand a point of $\mathbb{R}^{3}$ lying on three lines from the set $L$ but which do not all lie in the same plane (i.e. they are non-coplanar).

The conjectured answer by Sharir was that this number of joints is $\leq C |L|^{\frac{3}{2}}$, for some positive constant $C$; this was proven by Guth and Katz using a rather simple polynomial mathod which easily generalies to $\mathbb{R}^{d}$ in which case the upper bound becomes $C |L|^{\frac{d}{d-1}}$. (references can be found very easily on google; for example, see http://www.dagstuhl.de/Materials/Files/09/09111/09111.SharirMicha.Other.pdf)

Now, it seems to me that this polynomial method does not generalize to finite fields; so, my question is, can we get some upper bound in this case? My thoughts for now are to use the graph $G$ having as vertices the lines and to connected them if the lines intersect. Then the number of joints is the number of triangles of $G$ minus $\frac{1}{2}\left(\binom{|L|}{2} - k\right)$, where $k$ is the number of distinct planes determined by the $|L|$ lines... but I feel that I'll be getting really weak bounds if I majorize this (using graph theoretic stuff about the number of triangles and Beck's theorem or related things for $k$).

So, any other ideas or knowledge about the finite field case in literature? Thanks.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

I think that Quilodrán's solution to the joints problem in $\mathbb{R}^n$ can be applied to the finite field case, to get the same bounds. This is the paper, "The joints problem in $\mathbb{R}^n$": Abstract: arXiv:0906.0555v3; PDF link.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I just found the paper after posting the question and I was considering this right before seeing the post. Now I am really interested in in the graph theoretic approach (given that the bound is the same) $\endgroup$
    – Cosmin Pohoata
    Commented Mar 9, 2012 at 2:41
  • $\begingroup$ Actually I'm now sure if the proof works since as in the proof that I know, it uses that a non-zero polynomial over the reals has a non-zero partial of degree strickly less than the degree of the polynomial (fact which is not true over finite fields...) $\endgroup$
    – Cosmin Pohoata
    Commented Mar 9, 2012 at 2:47
  • 1
    $\begingroup$ There is the notion of the Hasse derivative, see this paper for example: arxiv.org/pdf/0901.2529.pdf - I think that everything can be generalised using that. $\endgroup$
    – Marina Iliopoulou
    Commented Mar 9, 2012 at 3:14
3
$\begingroup$

I know I'm digging up an old thread, but I figured out how to extend Kaplan, Sharir and Shustin's proof (similar to Quilodran's proof) to finite fields last summer, then later realized that Dvir indicates the proof in a set of lecture notes.

Anyway, the trick is this: if $Q$ is a polynomial over $\mathbb{F}_q[x_1,...,x_n]$ whose gradient vanishes identically, then $Q$ is the $p$th power of some other polynomial $Q_1$ (where $q$ is a power of $p$). Since $Q_1$ is zero if and only if $Q_1^p$ is zero, if we're assuming that $Q$ is the minimum degree polynomial that vanishes on the set of lines forming our joints, we get a contradiction.

Dvir mentions how to do this in his lecture notes: http://www.cs.princeton.edu/~zdvir/teaching/incidence12/6.%20The%20polynomial%20method.pdf

I couldn't get Hasse derivatives to work, but it might be possible. I forgot what the trouble was with them.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It's also possible to generalize the "flat point" methods from Guth and Katz's original paper (and from Elekes, Kaplan, and Sharir's paper) to $\mathbb{F}_{p^r}$ by choosing from a smaller set of monomials. If you exclude monomials that would bring down a multiple of $p$ when you take two derivatives, then the usual proof goes through. I think following Guth's notes, you could then show that if $L$ is a set of $N$ lines such that no $\sqrt{N}$ lie in a plane, then the number of $k$-rich points of $L$ is $O(N^{3/2}/k^{3/2})$, though I haven't written out the details. $\endgroup$
    – Brendan Murphy
    Commented Jul 30, 2013 at 21:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .