Density

From Polymath1Wiki
Jump to: navigation, search

Let X be a finite set. The usual definition of the density of a subset Y of X is |Y|/|X|, that is, the size of Y divided by the size of X. In particular, if [math]\mathcal{A}[/math] is a subset of [math][3]^n[/math] then its density is [math]3^{-n}|\mathcal{A}|.[/math]

One speaks loosely of a set [math]\mathcal{A}\subset[3]^n[/math] being dense if its density [math]\delta[/math] is bounded below by a positive constant that is independent of n. Strictly speaking, this definition applies to sequences of sets with n tending to infinity, but it is a very useful way of talking.

Sometimes it is helpful to consider other probability measures on [math][3]^n,[/math] such as equal-slices density. Then the words "density" and "dense" have obviously analogous uses.