Tricki

## Turn sets into functions

### Quick description

Let be a set. Then there is a one-to-one correspondence between subsets of and functions from to , which takes the subset to its characteristic function (or indicator function) , which is defined by if and otherwise. It can often be very fruitful to regard as a function from to a bigger set such as the closed interval , or , or , or to a set with more structure such as the field with two elements. The basic idea is to prove more general theorems about functions and to derive from them theorems about sets. A great advantage of doing this is that it allows one to import methods from other areas such as analysis and linear algebra.

This page could do with several more examples. (Even examples of reformulated problems, without accompanying accounts of the solutions, would be better than nothing.)

### Prerequisites

A basic familiarity with the first half of a typical undergraduate course in mathematics.

### Example 1

Let be an even positive integer and let be the collection of all subsets of of size . Let and let be a subset of such that for every . Then the size of is bounded above by a constant that depends on only.

Here is a way of looking at this fact. If you choose a typical pair of subsets of of size then their intersection will be very likely to have size about . If you want to find many sets of size with larger intersections than this, then you can choose subsets of a smaller set such as (which has exponentially many subsets of size , any two of which intersect in at least ). But if you want intersections that are smaller than the expected size, then you are in trouble: the number of sets you can choose does not even tend to infinity with .

This rather surprising fact (if you are not familiar with it) has an unforgettably beautiful proof: one that is not only short but also one that tells you exactly what is really going on. The idea is to associate with each set in a vector. The idea is to do this in such a way that if has size then the inner product of the corresponding vectors is zero. This one does by taking not the characteristic function of a set but rather the function defined by if and otherwise.

We now make this vector a unit vector in a Hilbert space by taking as inner product the bilinear form . Clearly, for every set . If and are two sets of size , then is on , on , and everywhere else. It is easy to prove that , so we find that . Thus, the inner product ranges from (if and are disjoint) to (if and are equal). Also, and this is what matters to us, if , then , and conversely.

We are thus led to ask a more general question: how many unit vectors can one find in a Hilbert space, subject to the constraint that the inner product of any two of them is less than , for some fixed positive ?

To answer this question we use another trick: averaging: if every inner product is at most then the average inner product is certainly at most . If we call the vectors , then one way of writing this is .

Now this will give us an upper bound for if we can show that it is not possible for the left-hand side to be too large and negative. It is not immediately obvious how to prove this, but the following simple observation does it: the closely related sum is equal to and is therefore non-negative. Moreover, what we have added to get to this sum from the one that we are interested in is , which equals (since the are unit vectors). Therefore, . From this it follows that , which implies that .

This inequality turns out to be sharp: if you arrange unit vectors as vertices of a simplex of dimension , then the inner product of any two vectors is . For example, if , then this is true because the cosine of is In general, one can prove it by making the simple observation that the sum of these unit vectors is 0, and the inner products are all the same (both following from the symmetry of a simplex), so that all the inequalities in the above argument are sharp.

Since we have bounded in terms of only, the number of sets one can choose in the first problem is bounded above by a constant that depends on only, as claimed.

### Example 2

One basic example of this in the passage from measures (which are functions on a -algebra of sets) to integrals (which are functionals on a space of functions). See the discussion of Lebesgue integral and the for explanations of this.

### Example 3

One particularly powerful tool which is available for functions (and hence, by this trick, for sets), is Fourier analysis. When applied to sets, this technique is sometimes known as the Hardy-Littlewood circle method, especially in number theory.

For instance, if one wants to count the number of ways a positive integer can be expressed as the sum of three numbers in some set (e.g. the set of primes), one can turn the set into a function and write thus quantity as

One can recognize this as a discrete convolution evaluated at . Using Fourier analysis, one can rewrite this expression as

where is the Fourier transform of . So the task is now a Fourier-analytic one, namely to compute the exponential sum . This is by no means a non-trivial task, but it is still a simpler one than the original problem (basically because it only involves one instance the complicated set , while the original problem involved three such instances).

### General discussion

It is also possible to partially invert this trick and turn functions back into sets, see "Control level sets" for more discussion.