Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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) –  Cosmin Pohoata Mar 9 '12 at 2:41
    
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...) –  Cosmin Pohoata Mar 9 '12 at 2:47
    
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. –  Marina Iliopoulou Mar 9 '12 at 3:14

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.

share|improve this answer
    
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. –  Brendan Murphy Jul 30 '13 at 21:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.