Extra logarithmic factors

a repository of mathematical know-how

Extra logarithmic factors

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[QUICK DESCRIPTION]

Many proofs in many areas of mathematics, but especially in parts of number theory and combinatorics, give rise to bounds that have logarithmic terms. This article is about why that should be, and gives some examples of proofs where they arise. So far it has just one example. It would be good to have many more, demonstrating many different reasons for the appearance of log factors.

[EXAMPLE]

An ''aligned rectangle'' is a rectangle in $\mathbb{R}^2$ with its sides parallel to the $x$ and $y$ axes. Suppose you have a collection of $n$ aligned rectangles. What is the maximum value of $m$ for which it is always possible to find either $m$ disjoint rectangles in the collection or a point in $\mathbb{R}^2$ that is contained in $m$ rectangles from the collection? For convenience we shall assume throughout the discussion that all rectangles are closed.

A simple example shows that $m$ cannot be greater than $\sqrt n$: one simply takes $\sqrt n$ sets of aligned rectangles and makes sure that two aligned rectangles in the same set intersect, while two aligned rectangles in different sets are disjoint.

Now let us match this lower bound with an upper bound that is the same---apart from a logarithmic factor.

First, if $R$ is an aligned rectangle, let us define $x_0(R)$ and $x_1(R)$ to be the minimum and maximum $x$ coordinates of points in $R$, respectively. Similarly, let $y_0(R)$ and $y_1(R)$ be the minimum and maximum $y$ coordinates. (Thus, if $R$ is closed, then it equals $[x_0(R),x_1(R)]\times[y_0(R),y_1(R)]$. Now, given any collection of $n$ aligned rectangles, let $X$ be the set of all real numbers that are equal to $x_0(R)$ or $x_1(R)$ for some $R$ in the collection, and let $Y$ be the same thing for $y$ coordinates. Then the sizes of $X$ and $Y$ are both at most $2n$.

Now whether or not two rectangles $R$ and $R'$ intersect depends solely on the ordering of the four numbers $x_0(R)$, $x_1(R)$, $x_0(R')$ and $x_1(R')$ and the ordering of the four numbers $y_0(R)$, $y_1(R)$, $y_0(R')$ and $y_1(R')$. Therefore, we can replace the sets $X$ and $Y$ by $\{1,2,\dots,m_1\}$ and $\{1,2,\dots,m_2\}$ for two integers $m_1$ and $m_2$ that are both at most $2n$.

What all this amounts to is that we can assume, without loss of generality, that the coordinates of the vertices of all rectangles in the collection are integers between $1$ and $2n$.

Now it turns out to be a lot easier to prove the result if all the rectangles have about the same size and shape. Here is an argument that shows that gives a lower bound of $c\sqrt n$ for aligned squares.<comment thread="1264" /> Let us form a graph whose vertices are the aligned squares, with an edge joining two vertices if those squares intersect. (If you are unfamiliar with graph theory terminology, then you can find it in Wikipedia's [[w:Glossary_of_graph_theory|graph theory glossary]].) If the maximum degree of any vertex in this graph is $\sqrt n$, then we can pick a sequence of vertices $S_1,S_2,\dots,S_k$, with no vertex joined to any previous one, provided that $(k-1)\sqrt n<n$, so certainly if $k=\sqrt n$. So in this case we have a collection of $\sqrt n$ disjoint squares. But now suppose that there is a vertex of degree greater than $\sqrt n$. This will be a square $S$ that overlaps with over $\sqrt n$ other squares. Now each of those other squares must contain a vertex of the original square (this is the step that fails when the rectangles have different shapes), so a least one vertex of $S$ must be contained in at least $\sqrt n/4$ rectangles, which completes the proof.

What can we do if we have rectangles? We can use the widely applicable trick of [[Make everything roughly the same size|making everything roughly the same size]]. The widths of the rectangles lie between $1$ and $2n$, as do their heights. Let us partition the set $\{1,2,\dots,2n\}$ into sets of the form $\{r:2^{k-1}\leq r<2^k\}$. There are at most $\log_2(2n)+1$ of these sets, so we can find two of them, $U$ and $V$ say, and a set $\mathcal{R}$ of at least $n/(\log_2(2n)+1)^2$ aligned rectangles taken from the original collection, such that the width of every rectangle in $\mathcal{R}$ lies in $U$ and the height lies in $V$.

This implies that the ratios of the widths and heights of any two rectangles in $\mathcal{R}$ are at most 2. We now repeat the argument above for squares, except that this time when we have a rectangle $R$ of degree at least $\sqrt N$ (where $N$ is the size of $\mathcal{R}$), we cannot argue that all rectangles that intersect $R$ must contain a vertex of $R$. However, we ''can'' argue that any rectangle in $\mathcal{R}$ that intersects $R$ contains either a vertex of $R$ or the midpoint of an edge or the centre of $R$. This makes nine possibilities, so we can obtain a lower bound of $c\sqrt N$. Since $N$ is of the form $cn/(\log n)^2$, this gives a lower bound of the form $c\sqrt n/\log n$ for the original problem.

This demonstrates one way in which stray logarithmic factors can arise: through an application of the [[Make everything roughly the same size|make-everything-roughly-the-same-size]] trick.

It is often possible to be more careful and remove a logarithmic factor of this kind by avoiding the use of that trick and thinking hard about how to relate objects of different sizes. However, closing the gap between the above estimates is still an open problem.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Extra logarithmic factors

Recent articles

Active forum topics

Recent comments