Tricki

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

### 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 for some fixed non-zero and some exponents . The integrand here exhibits three distinct modes of "bad" behavior: a singularity as , a singularity as , and a slow decay as . Rather than deal with all these modes at once, one can decompose the domain 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 into

• I. The region where ;

• II. The region where ;

• III. The region where .

In region I, the dominant mode of behavior is the singularity as . The term is comparable in magnitude here to the quantity , which is independent of 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 .

In region II, the dominant mode of behavior is the singularity as . The term is comparable in magnitude here to the quantity , and can be pulled out of the integral also, leaving one with the tractable integral .

In region III, the dominant mode of behavior is the decay as . Here, and are comparable in magnitude to each other, so the integral can be simplified (up to multiplicative constants) as . The additional restriction is not significantly helping us here (this is intuitively obvious after drawing a picture), and we can estimate this contribution by the tractable integral .

(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

where, say, . Remembering that and one expects the sum to be something (a bit) worse than and (a lot) better than close to the 'dangerous' endpoint . Thus a good guess would be for some . We will try to prove such an estimate by using the Divide and Conquer trick in order to 'decouple' the two terms and , in the sum.

In order to decide where to break the sum, the following observation is quite important. Whenever we have that . This means that in the region we can just use the bound without losing anything but a multiplicative constant. Thus we write

For the first term in the sum above we have that

where we have also used the Bounding the sum by an integral trick. Observe that this gives automatically a lower bound for our sum , the latter being a sum of positive terms. We expect to be the main term of the sum. In order to estimate the second term we can use a dyadic decomposition and write

For the inner sum we use the Base times height trick where the base is the number of terms in the sum, and the height is essentially . Hence we get

Of course the first term dominates when so

Observe that the same calculation can be carried out by just write the power series of 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

for some arbitrary and .

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