Divide and conquer

a repository of mathematical know-how

Divide and conquer

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]

When an mathematical object that exhibits many distinct features, each of which makes it more difficult to control that object effectively, try decomposing the object into better-behaved (and non-interacting) components, each of which only has one of the features dominating.  Then control each of the components separately, and "sum up" to control the original object.

Note that in many cases, the components may be "messier" than the original object (because of the presence of cutoffs, mollifiers, truncations, etc.).  Nevertheless, these messier components may be easier to control, especially if one is only seeking upper bounds or approximations rather than exact computations, particularly if one is prepared to lose multiplicative constants in the final bound.

[PREREQUISITES]

Undergraduate calculus

[EXAMPLE]

The divide-and-conquer strategy is particularly good for estimating "linear" expressions, such as an integral over a domain.  One can divide up the domain into several components where the integrand is exhibiting different behavior, and bound the contribution of each component separately.

For instance, suppose one wants to compute the convolution integral $\int_{\R^n} \frac{1}{|y|^\alpha |x-y|^\beta}\ dy$ for some fixed non-zero $x \in \R^n$ and some exponents $\alpha, \beta > 0$.  The integrand here exhibits three distinct modes of "bad" behavior: a singularity as $y \to 0$, a singularity as $y \to x$, and a slow decay as $y \to \infty$.  Rather than deal with all these modes at once, one can decompose the domain $\R^n$ into three regions where one only sees one of these modes at a time.  There are a number of ways to do this, but here is one way: decompose $\R^n$ into

* I. The region where $|y| < |x|/2$;
* II.  The region where $|y-x| < |x|/2$;
* III.  The region where $|y|, |y-x| \geq |x|/2$.

In region I, the dominant mode of behavior is the singularity as $y \to 0$.  The $\frac{1}{|x-y|^{\beta}}$ term is comparable in magnitude here to the quantity $\frac{1}{|x|^\beta}$, which is independent of $y$ and can thus be pulled out of the integral (here we are using the trick "[[bound the integrand by something simpler]]"), leaving us with the (tractable) task of computing the integral $\int_{|y| < |x|/2} \frac{1}{|y|^\beta}\ dy$.

In region II, the dominant mode of behavior is the singularity as $y \to x$.  The $\frac{1}{|y|^\alpha}$ term is comparable in magnitude here to the quantity $\frac{1}{|x|^\alpha}$, and can be pulled out of the integral also, leaving one with the tractable integral $\int_{|y-x| < |x|/2} \frac{1}{|x-y|^\beta}\ dy$.

In region III, the dominant mode of behavior is the decay as $y \to \infty$.  Here, $|y|$ and $|x-y|$ are comparable in magnitude to each other, so the integral can be simplified (up to multiplicative constants) as $\int_{|y|, |y-x| \geq |x|/2} \frac{1}{|y|^{\alpha + \beta}}\ dy$.  The additional restriction $|y-x| \geq |x|/2$ is not significantly helping us here (this is intuitively obvious after drawing a picture), and we can estimate this contribution by the tractable integral $\int_{|y| \geq |x|/2} \frac{1}{|y|^{\alpha + \beta}}\ dy$.

(Should this example be worked out more fully?)

[EXAMPLE] The [[Divide and Conquer]] has been described in the context of [[Estimating Integrals]] but of course it can be equally useful in [[Estimating Sums]]. Let us exhibit that with a simple example. Suppose we need to estimate the series

[math] S(t)\sim \sum_{n=1} ^\infty \frac{\log n}{n} t^n [/math]

where, say, $0<t<1$. Remembering that $\log\frac{1}{1-t}=\sum_{n=1}^\infty \frac{t^k}{k}$ and $\frac{1}{1-t}=\sum_{n=1}^\infty t^k$ one expects the sum $S(t)$ to be something (a bit) worse than $\log\frac{1}{1-t}$ and (a lot) better than $\frac{1}{1-t}$ close to the 'dangerous' endpoint $t=1$. Thus a good guess would be $S(t)\sim(\log\frac{1}{1-t})^\lambda$ for some $\lambda>1$. We will try to prove such an estimate by using the [[Divide and Conquer]] trick in order to 'decouple' the two terms $\frac{\log n}{n}$ and $t^n$, in the sum.

In order to decide where to break the sum, the following observation is quite important. Whenever $t>1-\frac{1}{n}$ we have that $t^n>(1-\frac{1}{n})^n\simeq 1$. This means that in the region $t>1-\frac{1}{n}\iff n < \frac{1}{1-t}$ we can just use the bound $t^n<1$ without losing anything but a multiplicative constant. Thus we write

[math] \sum_{n=1} ^\infty \frac{\log n}{n} t^n =\sum_{1\leq n < \frac{1}{1-t}} \frac{\log n}{n} t^n +\sum_{n\geq \frac{1}{1-t}} \frac{\log n}{n} t^n .[/math]

For the first term in the sum above we have that

[math]\sum_{1\leq n < \frac{1}{1-t}} \frac{\log n}{n} t^n \simeq \sum_{1\leq n < \frac{1}{1-t}} \frac{\log n}{n}\simeq \int _1 ^{\frac{1}{1-t}}\frac{\log x}{x}  \simeq \bigg(\log \frac{1}{1-t}\bigg)^2,[/math]

where we have also used the [[Bounding the sum by an integral]] trick. Observe that this gives automatically a lower bound for our sum $S(t)$, the latter being a sum of ''positive'' terms. We expect $(\log\frac{1}{1-t})^2$ to be the main term of the sum. In order to estimate the second term we can use a [[dyadic decomposition]] and write

[math] \sum_{n\geq \frac{1}{1-t}} \frac{\log n}{n} t^n = \sum_{k=0} ^\infty \sum_{\frac{2^k}{1-t} \leq n < \frac{2^{k+1}}{1-t}} \frac{\log n}{n} t^n \simeq 
\sum_{k=0} ^\infty  \frac{\log \frac{2^k}{1-t}}{\frac{2^k}{1-t}} \sum_{\frac{2^k}{1-t} \leq n < \frac{2^{k+1}}{1-t}}  \big(1-\frac{2^k}{n}\big)^n . [/math]

For the inner sum we use the [[Bound your integral by its base times its height|Base times height]] trick where the base is the number of terms in the sum, $\frac{2^k}{1-t}$ and the height is essentially $e^{-2^k}$. Hence we get

[math] \sum_{n\geq \frac{1}{1-t}} \frac{\log n}{n} t^n \simeq \sum _{m=1} ^\infty e^{-m}\log\frac{m}{1-t} \lesssim 1 + \log\frac{1}{1-t}.[/math]

Of course the first term $(\log\frac{1}{1-t})^2$ dominates when $t\rightarrow 1$ so

[math] \sum_{n=1} ^\infty \frac{\log n}{n} t^n \simeq \bigg(\log\frac{1}{1-t}\bigg)^2 [/math]

Observe that the same calculation can be carried out by just write the power series of $\log{1}{1-t}$ and then using the [[Square and rearrange]] trick to reach to the same conclusion, and in fact, in a much more elegant way. However this requires that one already knows the result and just wants to prove it. A second and more important advantage of the [[Divide and Conquer]] trick is that it is much more flexible. Thus one could for example apply the same steps in order to estimate a series of the form

[math]\sum_{n=1} ^\infty \frac{(\log n)^\epsilon}{n}t^n ,[/math]

for some arbitrary $\epsilon>0$ and $0<t<1$.
[GENERAL DISCUSSION]

A particularly useful special case of the divide-and-conquer strategy is [[dyadic decomposition]].

(Need some non-integration examples of divide-and-conquer strategies, e.g. in combinatorics.  Suggestions?)

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.

Divide and conquer

Recent articles

Active forum topics

Recent comments