Tricki
a repository of mathematical know-how

Divide and conquer

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 1

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 2

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

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

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

 \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 .

For the first term in the sum above we have that

\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,

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

 \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 .

For the inner sum we use the 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

 \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}.

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

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

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

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

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?)

Comments

which parent for this child?

Divide and Conquer is currently a child of Estimating Integrals. However it seems that it should be a general principle that applies to many different situations. Thus it could be for example a child of Techniques for obtaining estimates which it is in a sense (it's a grandchild). However, if someone goes to the techniques for obtaining estimates and their problem has nothing to do with integrals, he/she might never end up seeing this article as its way is via Estimating Integrals. I understand that this is potentially a general problem for many different articles. They belong to many different places. Is it possible to have a more parallel structure here? That is, instead of a folder structure have a label structure (a bit like how gmail uses labels instead of folders so different things can of course belong to the same label). Of course this might already be the case without me knowing it. But in this case I guess the article divide and conquer that I'm using as an example should be linked from Techniques for obtaining estimates as well. I have another question. If I edit the article and add an extra 'parent', can a link automatically be created in the parent article? Otherwise how can one track the child from this new parent?

Parent/child links

There was an inconclusive forum discussion about this issue (under the topic of "Linking to front pages"). If I understand the current situation correctly, at the moment if you add a parent to an article, you have to manually edit that parent article and add the link.