Dear Jozsef,

Yes, in principle this argument should work, but I have been having difficulties over the last few months trying to make it rigorous.  Ultimately it comes down to the technical differences between the following two claims:

Claim I:  Up to logs, N points in R^3 determine at least N^{2/3} distances.

Claim II: Up to logs, N points in R^3 determine at most N^4/k^3 k-rich rigid motions for each k.  (Or, essentially equivalently: there are O(N^4) pairs of congruent triangles.)

Claim II implies Claim I, but not conversely.   A typical situation here is that of a bipartite set of points A u B, where there are very few distances between two points in A, or between two points in B, but a lot of distinct distances from A to B.  With the right tweaking of parameters, one can arrange things so that Claim I holds but Claim II fails for this set of points.

Anyway, the cell decomposition argument tells us, morally at least, that if we can prove Claim II for each cell (or more precisely, for a pair of cells), then we should be able to prove Claim II in general.

The problem is that I don't know how to prove Claim II unconditionally; I can only do so under the assumption that Claim I fails (i.e. I need to exploit the fact that there are only O(N^{2/3}) distances in order to get the right sort of upper and lower bounds on things like the number of pairs of congruent line segments, or the number of pairs of congruent triangles; the most annoying enemy is this bipartite thing where there are lots of pairs of congruent line segments but very few pairs of congruent triangles).    And Claim I does not descend well to a single cell the way that Claim II does.   This sounds like a mere technical problem, but it has been frustrating me for the last few months and I don't know how to get around it.

Best,

Terry

On Wed, Apr 6, 2011 at 9:09 AM, zolimozi <solymosi@...> wrote:

 

Dear Terry,

I hope that we can handle the non-homogeneous case as well. Here is a rough plan. We want to bound the k-rich transformations and we have a good bound for small (<< k)transformations. Let us partition the pointset P into r^3 cells by a polynomial, Q, with degree not much larger than r. (r is very small) If T is a rigid motion that T(P)\cap P = S has cardinality at least k then partition S into Dr^3 cells, where D is a large number. If we apply the inverse of T to the partitioning polynomial of P, (T^{-1}(Q)), then it will intersect a small fraction of the Dr^3 cells, so most of the in-cell pointsets of S move from one to another cell in P by the transformation T. So, we have X k-rich transformations, each defines about r^3 transformations which are |S|/Dr^3 -rich from one cell of P to another one. There are no more than (r^3)^2*(|P|/r^3)^4/(k/Dr^3)^3 such transformations (by the induction) Therefore

(r^3)^2*(|P|/r^3)^4/(k/Dr^3)^3 > r^3*X

X<cN^4/k^3 as we wanted.

I hope it works.

Best wishes,
Jozsef

--- In erdos@yahoogroups.com, Terence Tao <tao@...> wrote:
>
> Dear all,
>
> I think that (in principle, at least), we can prove the following
> somewhat wimpy partial result towards 3D erdos by putting together all
> our techniques:
>
> Claim. Let N points in R^3 be distributed homogeneously (by which I
> mean (a) that these points are contained in a ball of radius
> O(N^{1/3}), and (b) any unit ball contains O(1) points (and thus for
> any r >= 1, any ball of radius r contains O(r^3) points). Then there
> exists a ball of radius 1 < r < N^{1/3} such that the points in that
> ball determine \gtrapprox r^2 distances.
>
> The basic idea here is that we already know that the main obstructions
> to 3D Erdos are the rich rigid motions (either orientation preserving
> or orientation reversing). But we can use Jozsef's argument to pass
> to a pair of cells to reduce the richness. In the homogeneous case,
> the cells are basically just balls or cubes, and when one passes to (a
> pair of) cells one is basically in a miniature version of the original
> problem.
>
> There are a number of technical issues in order to make the argument
> rigorous (in particular, collinearity is going to be an issue again; I
> was able to get around it in my previous arguments, but those
> arguments aren't quite compatible with induction on scale at present),
> but I think this is a feasible claim from the methods we have.
>
> Of course, we would like to have something better than this, with
> weaker hypotheses and stronger conclusions...
>
> Best,
>
> Terry
>
> --
> Terence Tao, Department of Mathematics, UCLA
> http://www.math.ucla.edu/~tao

> Email: tao@... / teorth@...
>

--
Terence Tao, Department of Mathematics, UCLA
http://www.math.ucla.edu/~tao

Email: tao@... / teorth@...