RE: [math-fun] Density question
David WIlson asks: << Can someone give me an example of a set of density 1/2 on every interval of the real numbers?
If such a set must be measurable, then no such set exists. On the other hand, there do exist partitions of the reals into two dense homogeneous subsets that are related by a translation. --Dan A.
David Wilson wrote:
Can someone give me an example of a set of density 1/2 on every interval of the real numbers?
Take [0,1/2), and then for every point x in it, flip a coin. If the coin is heads, keep x as is. If the coin is tails, replace x with x+1/2. Then shift the resulting set by all the integers. -Thomas C
I asked:
Can someone give me an example of a set of density 1/2 on every interval of the real numbers?
To which Dan Asimov replied:
If such a set must be measurable, then no such set exists.
On the other hand, there do exist partitions of the reals into two dense homogeneous subsets that are related by a translation.
So as with the well-ordering of the reals, it exists but no constructive example exists?
Dan Asimov wrote:
<< Can someone give me an example of a set of density 1/2 on every interval of the real numbers?
If such a set must be measurable, then no such set exists.
On the other hand, there do exist partitions of the reals into two dense homogeneous subsets that are related by a translation.
Probably I should know why both of these are true, but right now it seems that I don't. Can you explain? --Michael Kleber ps: "all reals whose last digit is even" :-? -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
1. A point of density of a set is a point such that for small enough neighborhoods, the density of the set in that neighborhood is arbitrarily close to 1. I.e. every neighborhood smaller than delta has 99.99% of points in the set, etc. The Lebesgue density theorem asserts that almost every element of any measurable set is a point of density. I.e. for any measurable subset of R (or any other space) almost every point has neighborhoods with density approaching 1 or density approaching 0. This is a fundamental principle of measure theory, I think it is (or at least it should be) in the basic texts. It really comes from the way measure is defined. 2. You can take an irrational rotation of the circle R/Z like x -> x + sqrt(2). The orbits of this rotation are all isomorphic to Z --- i.e. points never return to themselves. Pick a point from each orbit, using the axiom of choice. Partition the orbit into the even images and the odd images of this point. The union of all odd points in all orbits is "half" the circle in the sense that its congruent by a translation to its complement. In fact you can take odd powers of the rotation arbitrarily close to the identity, so you can make the set match its complement by an arbitrarily small rotation. This example is covered by an example in R --- you could think of this as taking any action of Z^2 (or Z^k would also work) by translations on R with dense orbits, then partitioning the orbits into cosets of a subgroup of index 2 acting on a selected point. It's known that there's no definition or rule or humanly comprehensible procedure to actually make such a selection. Bill On Apr 18, 2005, at 9:24 PM, Michael Kleber wrote:
Dan Asimov wrote:
<< Can someone give me an example of a set of density 1/2 on every interval of the real numbers?
If such a set must be measurable, then no such set exists.
On the other hand, there do exist partitions of the reals into two dense homogeneous subsets that are related by a translation.
Probably I should know why both of these are true, but right now it seems that I don't. Can you explain?
--Michael Kleber
ps: "all reals whose last digit is even" :-?
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
When I am mulling over a problem and I wish to consult math-fun about it, I tend to dumb-down the question I ask to math-fun, in order to avoid voluminous background material. In this case, my ruminations were on the chromatic number of the plane. To start with, here is a little theorem: Theorem: If c is the chromatic number of the plane, each of the c colors applies to an uncountable number of points in the plane. Proof: Let c be the chromatic number of the plane, and let the plane be c-colored so that no two points at unit distance have the same color. Suppose only a countable set of points S(A) have color A. Choose finite c-color Moser graph M in the plane (Erdos et al proved it exists). Let V be the finite set of vectors between pairs of vertices of M, including the zero vector. Let S'(A) = {a+v: a in S(A), v in V}. Then, any translation of M having a vertex in S(A) has all vertices in S'(A). Since S'(A) is countable, some point P of the plane is not in S'(A). Translate M to M' with vertex P. P is not in S'(A), so no vertex of M' is in S(A), and M' has no vertex of color A. This means that M' is (c-1)-colored, but it is not (c-1)-colorable, so two adjacent vertices must have the same color, corresponding to two points of the plane at unit distance with the same color. This contradicts our coloring of the plane, and so S(A) must be uncountable, QED. In tesselation-style colorings of the plane, such as the 7-coloring used to show c <= 7, the uncountability of points in each color is evident. However, since no tesselation-style coloring has yet been found for c <= 6, I was drawn to consider other types of colorings. Specifically, I wondered if there might not be a c-coloring in which every region of the plane included points of all colors. It was at that point I went out of my depth. My gut feeling was that if such a c-coloring existed, the points of color c would be of positive measure in each region of the plane. But I didn't even know of two sets of positive measure on every interval of the reals, hence my question. I suppose my hope was to find some miraculous decision function that would allow me to decide which points in the plane were of what color, with each color being somewise equally and uniformly distributed over the plane and every pair of points at distance 1 of different colors. The hope seems pretty naive.
The question of chromatic number of the plane is really akin to the measure counterexamples, it's talking about counting things that are actually uncountable. It's really a question about algebraic number fields---the chromatic number of the plane is the sup over all finite extensions of Q of the chromatic number for that algebraic number field. (for any graph containing 0 and 1 whose vertices are not algebraic, they're in a transcendental extension which means you can substitute complex variables for a transcendence basis --- and vary them to be algebraic). There's some kind of weird transfinite induction `construction' of a tiling of the plane with c colors from tilings of all algebraic number fields with c colors, but it's highly non-constructive. What's known about the chromatic number of the plane? I'm curious whether enough is known to be able to prove there can't be a measurable best coloring. Bill On Apr 19, 2005, at 6:33 AM, David Wilson wrote:
When I am mulling over a problem and I wish to consult math-fun about it, I tend to dumb-down the question I ask to math-fun, in order to avoid voluminous background material. In this case, my ruminations were on the chromatic number of the plane.
To start with, here is a little theorem:
Theorem: If c is the chromatic number of the plane, each of the c colors applies to an uncountable number of points in the plane.
Proof: Let c be the chromatic number of the plane, and let the plane be c-colored so that no two points at unit distance have the same color. Suppose only a countable set of points S(A) have color A. Choose finite c-color Moser graph M in the plane (Erdos et al proved it exists). Let V be the finite set of vectors between pairs of vertices of M, including the zero vector.
Let S'(A) = {a+v: a in S(A), v in V}. Then, any translation of M having a vertex in S(A) has all vertices in S'(A). Since S'(A) is countable, some point P of the plane is not in S'(A). Translate M to M' with vertex P. P is not in S'(A), so no vertex of M' is in S(A), and M' has no vertex of color A. This means that M' is (c-1)-colored, but it is not (c-1)-colorable, so two adjacent vertices must have the same color, corresponding to two points of the plane at unit distance with the same color. This contradicts our coloring of the plane, and so S(A) must be uncountable, QED.
In tesselation-style colorings of the plane, such as the 7-coloring used to show c <= 7, the uncountability of points in each color is evident. However, since no tesselation-style coloring has yet been found for c <= 6, I was drawn to consider other types of colorings. Specifically, I wondered if there might not be a c-coloring in which every region of the plane included points of all colors.
It was at that point I went out of my depth. My gut feeling was that if such a c-coloring existed, the points of color c would be of positive measure in each region of the plane. But I didn't even know of two sets of positive measure on every interval of the reals, hence my question.
I suppose my hope was to find some miraculous decision function that would allow me to decide which points in the plane were of what color, with each color being somewise equally and uniformly distributed over the plane and every pair of points at distance 1 of different colors. The hope seems pretty naive.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is old news by now but re that question about density one half, (A) Dan's proof is fine but a more general statement has a proof which is almost two-liner and doesn't need anything as deep as Lebesgue density. A couple of people C. Gardner and Y. Peres pointed out the following: _____________________________________________________________________ I write A(int)B for intersection, and m(S) for outer measure of S. THEORM.There is no set S (measurable or not) in [0,1] with the property that m(S(int)[a,b]) = (b-a)/2 for all intervals [a,b] in[0,1]. FACT; Every open set in R is a countable union of DISJOINT open intervals. Proof of Theorem. Assume S exist. Then m(S)=1/2, so there is an open set O containing S with 1/2<m(O) < 2/3. Using FACT, O is union of disjoint intervals J (where J will stand for the interval and also its length), but by assumption m(S(int)J)= J/2 so by subadditivity of outer measure m(S)<Summation(J/2) < 1/3<1/2, contradiction. At 09:42 PM 4/18/2005, you wrote:
1. A point of density of a set is a point such that for small enough neighborhoods, the density of the set in that neighborhood is arbitrarily close to 1. I.e. every neighborhood smaller than delta has 99.99% of points in the set, etc. The Lebesgue density theorem asserts that almost every element of any measurable set is a point of density. I.e. for any measurable subset of R (or any other space) almost every point has neighborhoods with density approaching 1 or density approaching 0. This is a fundamental principle of measure theory, I think it is (or at least it should be) in the basic texts. It really comes from the way measure is defined.
2. You can take an irrational rotation of the circle R/Z like x -> x + sqrt(2). The orbits of this rotation are all isomorphic to Z --- i.e. points never return to themselves. Pick a point from each orbit, using the axiom of choice. Partition the orbit into the even images and the odd images of this point. The union of all odd points in all orbits is "half" the circle in the sense that its congruent by a translation to its complement. In fact you can take odd powers of the rotation arbitrarily close to the identity, so you can make the set match its complement by an arbitrarily small rotation. This example is covered by an example in R --- you could think of this as taking any action of Z^2 (or Z^k would also work) by translations on R with dense orbits, then partitioning the orbits into cosets of a subgroup of index 2 acting on a selected point.
It's known that there's no definition or rule or humanly comprehensible procedure to actually make such a selection. Bill On Apr 18, 2005, at 9:24 PM, Michael Kleber wrote:
Dan Asimov wrote:
<< Can someone give me an example of a set of density 1/2 on every interval of the real numbers?
If such a set must be measurable, then no such set exists.
On the other hand, there do exist partitions of the reals into two dense homogeneous subsets that are related by a translation.
Probably I should know why both of these are true, but right now it seems that I don't. Can you explain?
--Michael Kleber
ps: "all reals whose last digit is even" :-?
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Bill Thurston -
Daniel Asimov -
David Wilson -
Michael Kleber -
Sandra Gilbert -
Thomas Colthurst