Tricki
a repository of mathematical know-how

Make everything roughly the same size

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.

Rough idea of unwritten article

Often it is easier to deal with objects that are roughly the same size. If the range of sizes isn't too great, then we can achieve this by picking a large subset of the objects we have at hand, or partitioning them into not too many sets. For example, if the integers a_1,\dots,a_m all lie between 1 and n, we can partition them into at most \log_2n sets such that any two a_i in the same cell of the partition are within a factor of 2 of each other. This very simple trick is very useful, though it often comes at the expense of extra logarithmic factors in proofs.

It would definitely be good if someone could write this article, and even better if they can think of a good way of classifying the article—it is not altogether obvious how to do so, as the basic idea is used in many different contexts. But how would somebody who needed it stumble on it in the Tricki?

Comments

Dyadic pigeonhole principle

I wrote something on this (the "dyadic pigeonhole principle") at

http://www.math.ucla.edu/~tao/preprints/Expository/pigeonhole.dvi

I may try to convert this to the wiki format, but probably not soon.