Re: [math-fun] Colourings of the plane
Corey Ziegler Hunts wants to know what's wrong with the 3-coloration: (rational, rational) -> red ; (irrational, irrational) -> indigo; <discordant> -> blood green. He claims the validity of this solution is equivalent to the nonexistence of a continuous function that complements rationality on some interval. --rwg
Dear all,
Can the plane be n-coloured, such that there are no mono- chromatic continuous curves of nonzero length?
For n = 4, there is the 'Millar colouring':
Colour a point (x,y):
* red if x and y are both rational; * green if x is irrational, y is rational; * yellow if x is rational, y is irrational; * blue if x and y are both irrational.
It is obvious that no monochromatic continuous curves can exist, as both the ordinate and abcissa are fixed (as if they varied by a nonzero amount, they would cross an infinity of rational and irrational points).
With a little effort, it is possible to define a 3-colouring with similar properties:
* red if x and y are both irrational; * red if x is a dyadic rational and y is irrational; * green if x is a non-dyadic rational and y is irrational; * blue if x is irrational and y is rational; * blue if x is a non-dyadic rational and y is rational; * green if x is a dyadic rational and y is rational;
(A dyadic rational has a terminating binary expansion; a non-dyadic rational has a recurring binary expansion; an irrational has an aperiodic binary expansion.)
It is clear that no red and blue curves exist, as they can only be horizontal lines, and are terminated by the infinity of green points on the lines. Also, no green lines exist, as dyadic and non-dyadic rationals are separated by an infinity of irrational numbers.
For 2-colourings, this is not so easy. The 'reduced Millar colouring', where a point is red if x and y are both either rational or irrational, and blue otherwise, does not satisfy the property. For example, the curve y = x is exclusively red.
A variant, the 'Elliott colouring' was proposed, with the following rules:
* red if x and y are both irrational; * blue if x is irrational, y is rational; * blue if x is a dyadic rational, y is irrational; * red if x is a dyadic rational, y is rational.
However, Appendix I shows how the reals can be continuously deformed to map the ordinary rationals to dyadic rationals, thereby rendering the Elliott colouring equivalent to the reduced Millar colouring.
So, I leave the n = 2 case as an 'exercise for the reader'.
Sincerely,
Adam P. Goucher
And Julian Ziegler Hunts points out that the function in Appendix I is Minkowsky's ? function: http://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function . --rwg On Sat, Jun 4, 2011 at 5:19 PM, Bill Gosper <billgosper@gmail.com> wrote:
Corey Ziegler Hunts wants to know what's wrong with the 3-coloration: (rational, rational) -> red ; (irrational, irrational) -> indigo; <discordant> -> blood green.
He claims the validity of this solution is equivalent to the nonexistence of a continuous function that complements rationality on some interval. --rwg
Dear all,
Can the plane be n-coloured, such that there are no mono- chromatic continuous curves of nonzero length?
For n = 4, there is the 'Millar colouring':
Colour a point (x,y):
* red if x and y are both rational; * green if x is irrational, y is rational; * yellow if x is rational, y is irrational; * blue if x and y are both irrational.
It is obvious that no monochromatic continuous curves can exist, as both the ordinate and abcissa are fixed (as if they varied by a nonzero amount, they would cross an infinity of rational and irrational points).
With a little effort, it is possible to define a 3-colouring with similar properties:
* red if x and y are both irrational; * red if x is a dyadic rational and y is irrational; * green if x is a non-dyadic rational and y is irrational; * blue if x is irrational and y is rational; * blue if x is a non-dyadic rational and y is rational; * green if x is a dyadic rational and y is rational;
(A dyadic rational has a terminating binary expansion; a non-dyadic rational has a recurring binary expansion; an irrational has an aperiodic binary expansion.)
It is clear that no red and blue curves exist, as they can only be horizontal lines, and are terminated by the infinity of green points on the lines. Also, no green lines exist, as dyadic and non-dyadic rationals are separated by an infinity of irrational numbers.
For 2-colourings, this is not so easy. The 'reduced Millar colouring', where a point is red if x and y are both either rational or irrational, and blue otherwise, does not satisfy the property. For example, the curve y = x is exclusively red.
A variant, the 'Elliott colouring' was proposed, with the following rules:
* red if x and y are both irrational; * blue if x is irrational, y is rational; * blue if x is a dyadic rational, y is irrational; * red if x is a dyadic rational, y is rational.
However, Appendix I shows how the reals can be continuously deformed to map the ordinary rationals to dyadic rationals, thereby rendering the Elliott colouring equivalent to the reduced Millar colouring.
So, I leave the n = 2 case as an 'exercise for the reader'.
Sincerely,
Adam P. Goucher
***** Appendix I *****
Consider the following sequences, which can be derived from the Stern-Brocot tree:
[0] [0,1/2] [0,1/3,1/2,2/3] [0,1/4,1/3,2/5,1/2,3/5,2/3,1/4] ...
For each rational in the interval [0,1), there is a constant k such that for all n > k, the rational appears in the nth sequence.
A similar sequence of sequences can be created for the dyadic rationals in the interval [0,1):
[0] [0,1/2] [0,1/4,1/2,3/4] [0,1/8,1/4,3/8,1/2,5/8,3/4,7/8] ...
This gives a natural bijection between the rationals in [0,1) to the dyadic rationals in [0,1), which can be extended to a bijection between all rationals and all dyadic rationals.
It also extends to a mapping from the reals to the reals, which operates as follows:
1. Express the real number, x, as its integer part followed by binary expansion:
x = n . a_1 a_2 a_3 a_4 a_5 ...
2. Let L_0 = n, H_0 = n+1.
3. Iterate for all natural numbers i: (a) If a_i = 0, let L_i = L_(i-1), H_i = mediant(L_(i-1),H_(i-1)) (b) If a_i = 1, let H_i = H_(i-1), L_i = mediant(L_(i-1),H_(i-1))
4. The sequences L_i and H_i converge to a real number, y, from below and above, respectively.
***** End of appendix I *****
And Julian Ziegler Hunts points out that the function in Appendix I is Minkowsky's ? function: http://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function . --rwg
Ahh, so it is [the inverse]! According to the article, John Conway also independently discovered this function.
Corey Ziegler Hunts wants to know what's wrong with the 3-coloration: (rational, rational) -> red ; (irrational, irrational) -> indigo; <discordant> -> blood green.
That works as well, since every continuous curve must cross a line of the form y = x + q (for rational q), or lie parallel to such a line, so must contain either red or indigo points. Sincerely, Adam P. Goucher
Hi, I have a fractal related question that's inspired by the recent escape-time KIFS fractals (Kaleidoscopic IFS). KIFS can be used to produce any regular symmetrical IFS that does not involve overlap of the first level transform domains (please forgive my possibly inaccurate terminology but I hope you get what I mean) such as the Menger Sponge or Sierpinski Tetrahedron but not IFS that have overlapping first level transform domains. My question is: Is it correct that *any* IFS fractal system (affine or not) (or indeed RIFS or LRIFS) can be written as a standard escape-time system using positional conditionals if said conditionals identify which of the first level transform domains the current (input) point belongs to *and* the first level transform domains do not overlap ? (Of course the situation for RIFS and LRIFS would be more complex requiring knowledge of which transforms are active at that depth in the IFS tree etc.) bye Dave
Nevermind, I realised the answer is quite obviously "yes" (provided that the full attractor is finite). On 5 Jun 2011, at 13:24, David Makin wrote:
Hi,
I have a fractal related question that's inspired by the recent escape-time KIFS fractals (Kaleidoscopic IFS).
KIFS can be used to produce any regular symmetrical IFS that does not involve overlap of the first level transform domains (please forgive my possibly inaccurate terminology but I hope you get what I mean) such as the Menger Sponge or Sierpinski Tetrahedron but not IFS that have overlapping first level transform domains.
My question is: Is it correct that *any* IFS fractal system (affine or not) (or indeed RIFS or LRIFS) can be written as a standard escape-time system using positional conditionals if said conditionals identify which of the first level transform domains the current (input) point belongs to *and* the first level transform domains do not overlap ? (Of course the situation for RIFS and LRIFS would be more complex requiring knowledge of which transforms are active at that depth in the IFS tree etc.)
bye Dave _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It was suggested that I explain terms in future, I apologise but since I was pointed here by a fellow fractal artist who is also a Mathematician by profession I assumed all members of the list would be familiar with more general fractal terminology - which with the level of math generally discussed on the list is just about the only terminology that I'm up to speed on :) IFS == Iterated Function System as used in the famous "Barnsley Fern" which uses 4 affine transforms but general IFS can use any type of transform essentially provided the overall result is (mostly) contractive (if using the chaos-game or contractive deterministic rendering methods) - reference: http://classes.yale.edu/fractals/ RIFS = Recurrent IFS, not sure of the definition bit I found it used in a number of places several years ago and the fractal types/algorithms involved matched changes I had made myself to enhance standard IFS. LRIFS - Language Restricted IFS - by far the most interesting and general form, with sufficiently sophisticated algorithms can produce equivalent results to general L-Systems (again see the Yale link) When an IFS is rendered every final point basically has a genetic code formed by the path through the tree of transforms used to get to that point (or *from* that point when rendering using the escape-time method) in the case of convergent rendering the *last* transform used gives the transform domain that the point belongs to, in the case of divergent, escape-time rendering then the first transform gives the transform domain for the point concerned. Kaleidoscopic IFS is produced using the standard escape-time method (as in "normal" Mandelbrot or Julia fractals) to render IFS fractals by deciding which transform to use on each iteration based on the position of the entry point - in this way for standard non-overlapping IFS (i.e. where the domains for no two different transforms intersect) the result can exactly match the standard IFS method (using a full tree) e.g. the Menger Sponge etc. When used with overlapping areas the results often produce kaleidoscopic effects especially when the transforms are varied to produce animations. On 5 Jun 2011, at 15:51, David Makin wrote:
Nevermind, I realised the answer is quite obviously "yes" (provided that the full attractor is finite).
On 5 Jun 2011, at 13:24, David Makin wrote:
Hi,
I have a fractal related question that's inspired by the recent escape-time KIFS fractals (Kaleidoscopic IFS).
KIFS can be used to produce any regular symmetrical IFS that does not involve overlap of the first level transform domains (please forgive my possibly inaccurate terminology but I hope you get what I mean) such as the Menger Sponge or Sierpinski Tetrahedron but not IFS that have overlapping first level transform domains.
My question is: Is it correct that *any* IFS fractal system (affine or not) (or indeed RIFS or LRIFS) can be written as a standard escape-time system using positional conditionals if said conditionals identify which of the first level transform domains the current (input) point belongs to *and* the first level transform domains do not overlap ? (Of course the situation for RIFS and LRIFS would be more complex requiring knowledge of which transforms are active at that depth in the IFS tree etc.)
bye Dave _______________________________________________ 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 (3)
-
Adam P. Goucher -
Bill Gosper -
David Makin