Incidences: Lower Bounds (part 5)

This is the fifth in my series of posts concerning lower bounds for incidence problems (see the previous post here). This is the last post of the series that takes place in the plane. However, before moving to higher dimensional bounds, I am taking a break from this series, and moving to other topics.

In this post we generalize Elekes’ lower bound construction for lines (e.g., see this previous post) so that it would apply to an infinite family of polynomial curves. This generalization provides another example of a phenomena that we mentioned before: Although it is widely believed that the number of incidences between n  points and n  constant-degree polynomial curves with no common components is O(n^{4/3})  , this is not the case when the number of curves is significantly larger than the number of points. I am not aware of any references for the following, and I originally heard them from Micha Sharir.

Sharir2
Micha Sharir.

Update (11/26/2014): Frank de Zeeuw pointed out that a brief mentioning of these bounds can be found in Elekes’ Sums versus products in Number Theory, Algebra and Erdös Geometry.

We begin by generalizing Elekes’ technique to parabolas. For any given values of m  and n  (i.e., the required sizes for the point set and of the parabola set, respectively) we set r=m^{1/2}/(3^{1/2}n^{1/6})  and s=(3n/m)^{1/2}  .

We define the point set as

{\cal P} = \left\{\ (i,j)\ | \ 1 \le i \le r \quad \text{ and } \quad 1 \le j \le 3r^2s \ \right\}.

We define the parabola set as

\Gamma = \left\{\ y=ax^2+bx+c \ | \ 1 \le a \le s,  \quad 1 \le b \le rs, \quad \text{ and } \quad 1 \le c\le r^2s \ \right\}.

Notice that we indeed have

|{\cal P}| = 3r^3s = 3\cdot \frac{m^{3/2}}{3^{3/2}n^{1/2}} \cdot (3n/m)^{1/2} = m,
|\Gamma|  = r^3s^3 = \frac{m^{3/2}}{3^{3/2}n^{1/2}} \cdot (3n/m)^{3/2} = n.

Consider a parabola \gamma  that is defined by the equation y=ax^2+bx+c  , for some constants a,b,c  that satisfy the constraints of \Gamma  . Notice that for any value of x  in \{1,\ldots,r\}  , there exists a corresponding value of y  in the range \{1,\ldots, 3r^2s\}  such that the point (x,y)  is incident to \gamma  . That is, every parabola of \Gamma  is incident to exactly r  points of \cal P  , and thus

I({\cal P},\Gamma) = r \cdot |\Gamma| =  \frac{m^{1/2}}{3^{1/2}n^{1/6}} \cdot n = 3^{-1/2}m^{1/2}n^{5/6}.

Notice that this bound is asymptotically larger than m^{2/3}n^{2/3}  when n  is asymptotically larger than m  . That is, we cannot expect an upper bound of O(m^{2/3}n^{2/3})  when the number of parabolas is asymptotically larger than the number of points.

Continue reading

Reinventing Discovery: The New Era of Networked Science

From this blog, it is starting to seem that I am a big fan of Michael Nielsen. A few months ago I praised Nielsen’s article about how to perform effective research. In this post I highly recommend his book “Reinventing Discovery: The New Era of Networked Science”. What can I say – I think that Nielsen is a brillian writer.

Michael_Nielsen
Michael Nielsen.

So what is this book about? In one sentence – it explores how the process of doing scientific research is changing due to the internet, and asks what else can be done to improve future research. If you are a mathematician, then you are probably familiar with several related topics such as the polymath project (which is maintained by Nielsen), arXiv, open access journals, etc.

While personally I am very interested in these topics and enjoy Nielsen’s ideas, from my brief description of the book it might sound as if non-scientists would not find any interest in it, neither would the many scientists who are not looking for academic discussions about the future of open access, etc. This is definitely not the case – I think that this book would be quite interesting to anyone who is somewhat interested in modern science, and I am already planning to get copies to a couple of non-scientist friends. The stories about new ways of doing science via the web are surprisingly fascinating. You learn about how a 25-year old schoolteacher without any related experience discovered a completely new type of astronomical object (now called quasar ionization echo), how the CDC uses Google to spot flu outbreaks, how computer gamers help to understand the structure of proteins, and various other new developments in how science is being done. I was not familiar with most of these stories and developments, and learned quite a bit about what is happening in other scientific fields.

If you are a mathematician (if not, then how did you get here?), while reading this book you might start to think about how the way that you write and publish papers is changing, how collaborations are changing, and where would the community go next.

The book also discusses the phenomenon of technical scientific blogging, and is unfortunately not very optimistic about it (although the reason is the opposite of the one that I was imagining). Oh well… stop reading this and go read the book!