Re: [math-fun] 3-coloring the rationals
James Propp <jamespropp@gmail.com>
There's a unique way to 3-color the rationals in [0,1] using the colors red, blue, and green so that 0 is red, 1 is blue, and the fractions a/b, c/d, and (a+c)/(b+d) all have distinct colors whenever ad-bc=1.
Puzzle (no spoilers till Sunday please!): What color is 355/113?
Argh: 355/113 isn't in [0,1]; replace it by 113/355.
Either way, it's blue. Odd/odd is blue. Even/odd is red. Odd/even is green. Even/even can be reduced to one of the above. I have no idea how to prove that this coloring is unique, however. Do you have a proof? I noticed, years ago, that the rationals have these three parities, so that was the first thing I tried. I agree with RCS that this is unambiguous over the whole of the rationals. I don't understand why you think there's any ambiguity with negatives. Just as negative integers have the same parity as if they were positive, so do negative rationals. Extra credit: Is there any color or pairs of colors that form a group under multiplication? Is there any color or any pair of colors that forms a group under addition? Can this coloring be extended in any natural way to any irrationals? You mention 355/113, which is best known as one of the convergents to pi. Are there any irrational numbers whose convergents are all the same color? (Pi isn't one.) If so, it might make sense to regard the number as having that color. Especially if it wouldn't break any group of rationals with that color.
Hi, Keith. On Sunday, April 17, 2016, Keith F. Lynch <kfl@keithlynch.net <javascript:_e(%7B%7D,'cvml','kfl@keithlynch.net');>> wrote:
Argh: 355/113 isn't in [0,1]; replace it by 113/355.
Either way, it's blue.
Odd/odd is blue. Even/odd is red. Odd/even is green. Even/even can be reduced to one of the above. I have no idea how to prove that this coloring is unique, however. Do you have a proof?
There are two issues: existence and uniqueness. For existence, one colors the rationals as Keith says. One must then show that if a/b and c/d are fractions with ad-bc=1, the fraction a/b, the fraction c/d, and their mediant (a+c)/(b+d) must have different colors; simple consideration of cases suffices. For uniqueness, one may cite the theory of Farey fractions and the Stern-Brocot tree. Every rational can be obtained by an iterative process of inserting mediants, starting from 0/1 and 1/1. This means that at each stage one has no choice (that is to say, that one has 1 choice).
I noticed, years ago, that the rationals have these three parities, so that was the first thing I tried.
Is there a standard term for this tripartition? Note that it can be described as the sign of the 2-adic valuation.
I agree with RCS that this is unambiguous over the whole of the rationals. I don't understand why you think there's any ambiguity with negatives. Just as negative integers have the same parity as if they were positive, so do negative rationals.
Your notion of "parity" is unambiguous, and indeed natural, but my question was about 3-colorings. I may be mistaken, but I think the uniqueness proof fails if one tri-colors all the rationals. If you disagree, please show me how to deduce the color of -1. Just to be clear: I agree completely that the natural 3-coloring assigns -r the same color as r, for all r. But I think there's another coloring that satisfies the conditions I stated: -r is blue if r is green and vice versa.
Extra credit: Is there any color or pairs of colors that form a group under multiplication? Is there any color or any pair of colors that forms a group under addition?
Yes and yes.
Can this coloring be extended in any natural way to any irrationals? You mention 355/113, which is best known as one of the convergents to pi. Are there any irrational numbers whose convergents are all the same color? (Pi isn't one.)
Maybe all but finitely many convergents to pi are the same color? If so, it might make sense to regard pi as having that color. My guess is that (a) pi shows no signs of having this property, and (b) we have no idea for how to approach the question. Maybe some quadratic irrational has the property in question, or maybe not; that might be my fall-asleep problem for tonight. (Is that what Charles Dodgson meant by a "pillow problem"?) Jim Propp
This statement is true for rationals between 0 and 1. You cannot obtain rationals greater than 1 if you only consider the half of the s-b tree between 0/1 and 1/1. For rationals greater than 1, it still works if you throw (1/0) into the mix (i.e., treat it as a rational) and color it green. But if you don't consider (1/0) to be a rational, then you could break the pattern by coloring both (0/1) and (1/0) the same color, e.g. red. And you could then choose any color for (1/1), but if you force it to blue, then you get the same color for any a/b and b/a, as opposed to red/green reversal if you allow (1/0) as a rational. Tom James Propp writes:
For uniqueness, one may cite the theory of Farey fractions and the Stern-Brocot tree. Every rational can be obtained by an iterative process of inserting mediants, starting from 0/1 and 1/1. This means that at each stage one has no choice (that is to say, that one has 1 choice).
Actually, I can make a stronger statement: If you don't consider (1/0) to be a rational (for the purposes of the coloring restrictions), then you can assign *any* color to the integers > 1 to obtain an alternate coloring of the rationals > 1, since none of them would be subject to any color restrictions. Tom Tom Karzes writes:
This statement is true for rationals between 0 and 1. You cannot obtain rationals greater than 1 if you only consider the half of the s-b tree between 0/1 and 1/1.
For rationals greater than 1, it still works if you throw (1/0) into the mix (i.e., treat it as a rational) and color it green. But if you don't consider (1/0) to be a rational, then you could break the pattern by coloring both (0/1) and (1/0) the same color, e.g. red. And you could then choose any color for (1/1), but if you force it to blue, then you get the same color for any a/b and b/a, as opposed to red/green reversal if you allow (1/0) as a rational.
Tom
James Propp writes:
For uniqueness, one may cite the theory of Farey fractions and the Stern-Brocot tree. Every rational can be obtained by an iterative process of inserting mediants, starting from 0/1 and 1/1. This means that at each stage one has no choice (that is to say, that one has 1 choice).
This seems too strong to me (though maybe I am misinterpreting Tom's claim). For instance, the colors of 1/1, 2/1, and 3/2 would have to be distinct. So there would be some restrictions even if the coloring isn't uniquely determined. My guess is that, in the absence of 1/0, each interval [n,n+1] would introduce a new bit's worth of freedom. Jim Propp On Sunday, April 17, 2016, Tom Karzes <karzes@sonic.net> wrote:
Actually, I can make a stronger statement: If you don't consider (1/0) to be a rational (for the purposes of the coloring restrictions), then you can assign *any* color to the integers > 1 to obtain an alternate coloring of the rationals > 1, since none of them would be subject to any color restrictions.
Tom
Tom Karzes writes:
This statement is true for rationals between 0 and 1. You cannot obtain rationals greater than 1 if you only consider the half of the s-b tree between 0/1 and 1/1.
For rationals greater than 1, it still works if you throw (1/0) into the mix (i.e., treat it as a rational) and color it green. But if you don't consider (1/0) to be a rational, then you could break the pattern by coloring both (0/1) and (1/0) the same color, e.g. red. And you could then choose any color for (1/1), but if you force it to blue, then you get the same color for any a/b and b/a, as opposed to red/green reversal if you allow (1/0) as a rational.
Tom
James Propp writes:
For uniqueness, one may cite the theory of Farey fractions and the Stern-Brocot tree. Every rational can be obtained by an iterative process of inserting mediants, starting from 0/1 and 1/1. This means that at each stage one has no choice (that is to say, that one has 1 choice).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, my wording was ambiguous. When I said "none of them", I was referring to the integers > 1, not the rationals > 1. I'm not claiming that all rationals greater than 1 are completely unconstrained, but only that the integers are. Then, in the case where the "parents" of a given rational have the same color, that rational has a choice among the two remaining colors. For instance, suppose all of the integers were colored blue, i.e. 1/1, 2/1, 3/1, etc. Then 3/2 couldn't be blue, but it could be either red or green. If 1/0 were treated as a rational, then the rationals greater than 1 would be fully constrained, with all colors being uniquely determined by the colors of 0/1 and 1/0. Tom James Propp writes:
This seems too strong to me (though maybe I am misinterpreting Tom's claim). For instance, the colors of 1/1, 2/1, and 3/2 would have to be distinct. So there would be some restrictions even if the coloring isn't uniquely determined.
My guess is that, in the absence of 1/0, each interval [n,n+1] would introduce a new bit's worth of freedom.
Jim Propp
On Sunday, April 17, 2016, Tom Karzes <karzes@sonic.net> wrote:
Actually, I can make a stronger statement: If you don't consider (1/0) to be a rational (for the purposes of the coloring restrictions), then you can assign *any* color to the integers > 1 to obtain an alternate coloring of the rationals > 1, since none of them would be subject to any color restrictions.
Tom
Tom Karzes writes:
This statement is true for rationals between 0 and 1. You cannot obtain rationals greater than 1 if you only consider the half of the s-b tree between 0/1 and 1/1.
For rationals greater than 1, it still works if you throw (1/0) into the mix (i.e., treat it as a rational) and color it green. But if you don't consider (1/0) to be a rational, then you could break the pattern by coloring both (0/1) and (1/0) the same color, e.g. red. And you could then choose any color for (1/1), but if you force it to blue, then you get the same color for any a/b and b/a, as opposed to red/green reversal if you allow (1/0) as a rational.
Tom
James Propp writes:
For uniqueness, one may cite the theory of Farey fractions and the Stern-Brocot tree. Every rational can be obtained by an iterative process of inserting mediants, starting from 0/1 and 1/1. This means that at each stage one has no choice (that is to say, that one has 1 choice).
I agree completely. Inasmuch as coloring the rationals can be thought of as coloring the Ford circles, maybe a good follow-up question involves 4-coloring the circles of an integral Apollonian gasket. The same sort of rigidity/uniqueness should prevail, but I have no idea whether there'd be a simple way to characterize the color-classes based on the respective centers and/or curvatures of the circles; the details would probably depend on which integral Apollonian gasket was chosen. Jim Propp On Monday, April 18, 2016, Tom Karzes <karzes@sonic.net> wrote:
Sorry, my wording was ambiguous. When I said "none of them", I was referring to the integers > 1, not the rationals > 1.
I'm not claiming that all rationals greater than 1 are completely unconstrained, but only that the integers are. Then, in the case where the "parents" of a given rational have the same color, that rational has a choice among the two remaining colors.
For instance, suppose all of the integers were colored blue, i.e. 1/1, 2/1, 3/1, etc. Then 3/2 couldn't be blue, but it could be either red or green.
If 1/0 were treated as a rational, then the rationals greater than 1 would be fully constrained, with all colors being uniquely determined by the colors of 0/1 and 1/0.
Tom
James Propp writes:
This seems too strong to me (though maybe I am misinterpreting Tom's claim). For instance, the colors of 1/1, 2/1, and 3/2 would have to be distinct. So there would be some restrictions even if the coloring isn't uniquely determined.
My guess is that, in the absence of 1/0, each interval [n,n+1] would introduce a new bit's worth of freedom.
Jim Propp
On Sunday, April 17, 2016, Tom Karzes <karzes@sonic.net <javascript:;>> wrote:
Actually, I can make a stronger statement: If you don't consider (1/0) to be a rational (for the purposes of the coloring restrictions), then you can assign *any* color to the integers > 1 to obtain an alternate coloring of the rationals > 1, since none of them would be subject to any color restrictions.
Tom
Tom Karzes writes:
This statement is true for rationals between 0 and 1. You cannot obtain rationals greater than 1 if you only consider the half of the s-b tree between 0/1 and 1/1.
For rationals greater than 1, it still works if you throw (1/0) into the mix (i.e., treat it as a rational) and color it green. But if you don't consider (1/0) to be a rational, then you could break the pattern by coloring both (0/1) and (1/0) the same color, e.g. red. And you could then choose any color for (1/1), but if you force it to blue, then you get the same color for any a/b and b/a, as opposed to red/green reversal if you allow (1/0) as a rational.
Tom
James Propp writes:
For uniqueness, one may cite the theory of Farey fractions and the Stern-Brocot tree. Every rational can be obtained by an iterative process of inserting mediants, starting from 0/1 and 1/1. This means that at each stage one has no choice (that is to say, that one has 1 choice).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
James Propp -
Keith F. Lynch -
Tom Karzes