Dyadic cubes
Encyclopedia
In mathematics
, the dyadic cubes are a collection of cubes in ℝn of different sizes or scales such that the set of cubes of each scale partition
ℝn and each cube in one scale may be written as a union of cubes of a smaller scale. These are frequently used in mathematics (particularly harmonic analysis
) as a way of discretizing objects in order to make computations or analysis easier. For example, to study an arbitrary subset of A of Euclidean space, one may instead replace it by a union of dyadic cubes of a particular size that cover the set. One can consider this set as a pixelized version of the original set, and as smaller cubes are used one gets a clearer image of the set A. Most notable appearances of dyadic cubes include the Whitney extension theorem
and the Calderón–Zygmund lemma.
and let Δ be the union of all the Δk.
The most important features of these cubes are the following:
We use the word "partition" somewhat loosely: for although their union is all of ℝn, the cubes in Δk can overlap at their boundaries. These overlaps, however, have zero Lebesgue measure, and so in most applications this slightly weaker form of partition is no hindrance.
It may also seem odd that larger k corresponds to smaller cubes. One can think of k as the degree of magnification. In practice, however, letting Δk be the set of cubes of sidelength 2k or 2−k is a matter of preference or convenience.
Let Δk be the dyadic cubes of scale k as above. Define
This is the set of dyadic cubes in Δk translated by the vector α. For each such α, let Δα be the union of the Δkα over k.
where f is a locally integrable function
and |B(x, r)| denotes the measure of the ball B(x, r). The Hardy–Littlewood maximal inequality states that for an integrable function f,
for λ>0 where Cn is some constant depending only on dimension.
This theorem is typically proven using the Vitali Covering Lemma
. However, one can avoid using this lemma by proving the above inequality first for the dyadic maximal functions
The proof is similar to the proof of the original theorem, however the properties of the dyadic cubes rid us of the need to use the Vitali covering lemma. We may then deduce the original inequality by using the one-third trick.
then
where C>0is a universal constant independent of the choice of x and r.
If X supports such a measure, then there exist collections of sets Δk such that they (and their union Δ) satisfy the following:
These conditions are very similar to the properties for the usual Euclidean cubes described earlier. The last condition says that the area near the boundary of a "cube" Q in Δ is small, which is a property taken for granted in the Euclidean case although is very important for extending results from harmonic analysis
to the metric space setting.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the dyadic cubes are a collection of cubes in ℝn of different sizes or scales such that the set of cubes of each scale partition
Partition
-Computing:* Partition , the division of a database* Disk partitioning, the division of a hard disk drive* Logical partition , a subset of a computer's resources, virtualized as a separate computer-Mathematics:...
ℝn and each cube in one scale may be written as a union of cubes of a smaller scale. These are frequently used in mathematics (particularly harmonic analysis
Harmonic analysis
Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
) as a way of discretizing objects in order to make computations or analysis easier. For example, to study an arbitrary subset of A of Euclidean space, one may instead replace it by a union of dyadic cubes of a particular size that cover the set. One can consider this set as a pixelized version of the original set, and as smaller cubes are used one gets a clearer image of the set A. Most notable appearances of dyadic cubes include the Whitney extension theorem
Whitney extension theorem
In mathematics, in particular in mathematical analysis, the Whitney extension theorem is a partial converse to Taylor's theorem. Roughly speaking, the theorem asserts that if A is a closed subset of a Euclidean space, then it is possible to extend a given function off A in such a way as to have...
and the Calderón–Zygmund lemma.
Dyadic cubes in Euclidean space
In Euclidean space, dyadic cubes may be constructed as follows: for each integer k = 0, ±1, ±2, ..., let Δk be the set of cubes in ℝn of sidelength 2−k and corners in the set and let Δ be the union of all the Δk.The most important features of these cubes are the following:
- For each integer k, Δk partitions ℝn.
- All cubes in Δk have the same sidelength, namely 2−k.
- If the interiorsInterior (topology)In mathematics, specifically in topology, the interior of a set S of points of a topological space consists of all points of S that do not belong to the boundary of S. A point that is in the interior of S is an interior point of S....
of two cubes Q and R in Δk have nonempty intersection, then either Q is contained in R or R is contained in Q. - Each Q in Δk may be written as a union of 2n cubes in Δk+1 with disjoint interiors.
We use the word "partition" somewhat loosely: for although their union is all of ℝn, the cubes in Δk can overlap at their boundaries. These overlaps, however, have zero Lebesgue measure, and so in most applications this slightly weaker form of partition is no hindrance.
It may also seem odd that larger k corresponds to smaller cubes. One can think of k as the degree of magnification. In practice, however, letting Δk be the set of cubes of sidelength 2k or 2−k is a matter of preference or convenience.
The one-third trick
One disadvantage to dyadic cubes in Euclidean space is that they rely too much on the specific position of the cubes. For example, for the dyadic cubes Δ described above, it is not possible to contain an arbitrary ball inside some Q in Δ (consider, for example, the unit ball centered at zero). Alternatively, there may be such a cube that contains the ball, but the sizes of the ball and cube are very different. Because of this caveat, it is sometimes to work with two or more collections of dyadic cubes simultaneously.Definition
The following is known as the one-third trick:Let Δk be the dyadic cubes of scale k as above. Define
This is the set of dyadic cubes in Δk translated by the vector α. For each such α, let Δα be the union of the Δkα over k.
- There is a universal constant C > 0 such that for any ball ball B with radius r < 1/3, there is α in {0,1/3}n and a cube Q in Δα containing B whose diameter is no more than Cr.
- More generally, if B is a ball with any radius r > 0, there is α in {0, 1/3, 4/3, 42/3, ...}n and a cube Q in Δα containing B whose diameter is no more than Cr.
An example application
The appeal of the one-third trick is that one can first prove dyadic versions of a theorem and then deduce "non-dyadic" theorems from those. For example, recall the Hardy-Littlewood Maximal functionwhere f is a locally integrable function
Locally integrable function
In mathematics, a locally integrable function is a function which is integrable on any compact set of its domain of definition. Their importance lies on the fact that we do not care about their behavior at infinity.- Formal definition :...
and |B(x, r)| denotes the measure of the ball B(x, r). The Hardy–Littlewood maximal inequality states that for an integrable function f,
for λ>0 where Cn is some constant depending only on dimension.
This theorem is typically proven using the Vitali Covering Lemma
Vitali covering lemma
In mathematics, the Vitali covering lemma is a combinatorial and geometric result commonly used in measure theory of Euclidean spaces. This lemma is an intermediate step, of independent interest, in the proof of the Vitali covering theorem. The covering theorem is credited to the Italian...
. However, one can avoid using this lemma by proving the above inequality first for the dyadic maximal functions
The proof is similar to the proof of the original theorem, however the properties of the dyadic cubes rid us of the need to use the Vitali covering lemma. We may then deduce the original inequality by using the one-third trick.
Dyadic cubes in metric spaces
Analogues of dyadic cubes may be constructed in some metric spaces . In particular, let X be a metric space with metric d that supports a doubling measure µ, that is, a measure such that if x in X, r > 0, andthen
where C>0is a universal constant independent of the choice of x and r.
If X supports such a measure, then there exist collections of sets Δk such that they (and their union Δ) satisfy the following:
- For each integer k, Δk partitions X in the sense that
-
- All sets Q Δk have roughly the same size. More specifically, each such Q has a center zQ such that
-
where c1, c2, and δ are positive constants depending only on the doubling constant C of the measure µ and independent of Q.
-
- Each Q in Δk is contained in a unique set R in Δk−1.
- There are constants constant C3, η > 0 depending only on µ such that for all k and t > 0,
-
These conditions are very similar to the properties for the usual Euclidean cubes described earlier. The last condition says that the area near the boundary of a "cube" Q in Δ is small, which is a property taken for granted in the Euclidean case although is very important for extending results from harmonic analysis
Harmonic analysis
Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms...
to the metric space setting.