[math-fun] A question about infinite words
The following question has arisen from my research on one-dimensional packing; I'm wondering if someone can help me prove it. Say we have an infinite word W = (w_1, w_2, w_3, ...) consisting of letters from some finite alphabet each of which occurs infinitely often in W. Suppose further that the finite alphabet consists of two kinds of letters which I'll call "consonants" and "vowels". We are also given a rational number r, and our infinite word satisfies a "proportionality property" (P): (P) If w_i = w_j (with i < j), then the number of vowels in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) divided by the number of consonants in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) equals r. Then I would like to be able to conclude that the consonant-vowel pattern of W is eventually periodic. Example: W = (a, b, c, e, d, c, a, b, c, a, b, c, e, d, c, a, b, c, a, b, c, a, b, c, e, d, c, ....) where a and e are vowels and b, c, and d are consonants. (If the pattern isn't clear, write the word schematically as XY XXY XXXY XXXXY ... where X = (a, b, c) and Y = (e, d, c).) Let r = 1/2. With i = 1 and j = 7, we see that the number of vowels in positions 1 through 6 divided by the number of consonants in positions 1 through 6 equals 2/4, or 1/2. More generally, given any two positions i and j that both have the same letter in W, if we look at all the letters that occur in positions i through j-1, we see that the number of vowels divided by the number of consonants is 1/2, so property (P) is satisfied. And if we look at the consonant-vowel pattern, it's just vowel-consonant-consonant over and over again, repeating periodically. My gut tells me that this is at the level of a hard IMO problem, and that it has a pretty solution. But that's no consolation to me, given that I don't see how to solve it. A solution to this puzzle would advance me towards a seemingly unrelated goal in the theory of sphere-packing. Jim
Is the following a counterexample? Take the Thue sequence, and replace each 1 by (a, b), and each 0 by (c, e). a and e are vowels, b and c are consonants, and r = 1. Andy On Sun, Jan 29, 2017 at 7:30 PM, James Propp <jamespropp@gmail.com> wrote:
The following question has arisen from my research on one-dimensional packing; I'm wondering if someone can help me prove it.
Say we have an infinite word W = (w_1, w_2, w_3, ...) consisting of letters from some finite alphabet each of which occurs infinitely often in W. Suppose further that the finite alphabet consists of two kinds of letters which I'll call "consonants" and "vowels". We are also given a rational number r, and our infinite word satisfies a "proportionality property" (P):
(P) If w_i = w_j (with i < j), then the number of vowels in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) divided by the number of consonants in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) equals r.
Then I would like to be able to conclude that the consonant-vowel pattern of W is eventually periodic.
Example: W = (a, b, c, e, d, c, a, b, c, a, b, c, e, d, c, a, b, c, a, b, c, a, b, c, e, d, c, ....) where a and e are vowels and b, c, and d are consonants. (If the pattern isn't clear, write the word schematically as XY XXY XXXY XXXXY ... where X = (a, b, c) and Y = (e, d, c).) Let r = 1/2. With i = 1 and j = 7, we see that the number of vowels in positions 1 through 6 divided by the number of consonants in positions 1 through 6 equals 2/4, or 1/2. More generally, given any two positions i and j that both have the same letter in W, if we look at all the letters that occur in positions i through j-1, we see that the number of vowels divided by the number of consonants is 1/2, so property (P) is satisfied. And if we look at the consonant-vowel pattern, it's just vowel-consonant-consonant over and over again, repeating periodically.
My gut tells me that this is at the level of a hard IMO problem, and that it has a pretty solution. But that's no consolation to me, given that I don't see how to solve it.
A solution to this puzzle would advance me towards a seemingly unrelated goal in the theory of sphere-packing.
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Wow, you're right! (I didn't think of trying to build a counterexample that way, though of course I should have, having written a whole essay on the PTM sequence mere weeks ago...) Thanks, Andy. Jim PS: This counterexample doesn't disprove the conjecture about packings I'm hoping to establish, but it does mean I'll have to find a new way to try to prove it. On Sunday, January 29, 2017, Andy Latto <andy.latto@pobox.com> wrote:
Is the following a counterexample?
Take the Thue sequence, and replace each 1 by (a, b), and each 0 by (c, e). a and e are vowels, b and c are consonants, and r = 1.
Andy
On Sun, Jan 29, 2017 at 7:30 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
The following question has arisen from my research on one-dimensional packing; I'm wondering if someone can help me prove it.
Say we have an infinite word W = (w_1, w_2, w_3, ...) consisting of letters from some finite alphabet each of which occurs infinitely often in W. Suppose further that the finite alphabet consists of two kinds of letters which I'll call "consonants" and "vowels". We are also given a rational number r, and our infinite word satisfies a "proportionality property" (P):
(P) If w_i = w_j (with i < j), then the number of vowels in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) divided by the number of consonants in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) equals r.
Then I would like to be able to conclude that the consonant-vowel pattern of W is eventually periodic.
Example: W = (a, b, c, e, d, c, a, b, c, a, b, c, e, d, c, a, b, c, a, b, c, a, b, c, e, d, c, ....) where a and e are vowels and b, c, and d are consonants. (If the pattern isn't clear, write the word schematically as XY XXY XXXY XXXXY ... where X = (a, b, c) and Y = (e, d, c).) Let r = 1/2. With i = 1 and j = 7, we see that the number of vowels in positions 1 through 6 divided by the number of consonants in positions 1 through 6 equals 2/4, or 1/2. More generally, given any two positions i and j that both have the same letter in W, if we look at all the letters that occur in positions i through j-1, we see that the number of vowels divided by the number of consonants is 1/2, so property (P) is satisfied. And if we look at the consonant-vowel pattern, it's just vowel-consonant-consonant over and over again, repeating periodically.
My gut tells me that this is at the level of a hard IMO problem, and that it has a pretty solution. But that's no consolation to me, given that I don't see how to solve it.
A solution to this puzzle would advance me towards a seemingly unrelated goal in the theory of sphere-packing.
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com <javascript:;>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Looks like you can't do it over an alphabet of 2 letters (use breadth-first search) but you can do it over an alphabet of 3 letters. Take the Thue-Morse word, replace each 0 by 010102 and 1 by 010202 and let {a} be the vowels and {1,2} be consonants and r = 1/2. Another construction: take the Thue-Morse word 01101001... and insert a 2 between each letter to get 2021212021202021 ... and let {2} be vowel and {0,1} be consonants. Jeff On 1/29/17 7:56 PM, Andy Latto wrote:
Is the following a counterexample?
Take the Thue sequence, and replace each 1 by (a, b), and each 0 by (c, e). a and e are vowels, b and c are consonants, and r = 1.
Andy
On Sun, Jan 29, 2017 at 7:30 PM, James Propp <jamespropp@gmail.com> wrote:
The following question has arisen from my research on one-dimensional packing; I'm wondering if someone can help me prove it.
Say we have an infinite word W = (w_1, w_2, w_3, ...) consisting of letters from some finite alphabet each of which occurs infinitely often in W. Suppose further that the finite alphabet consists of two kinds of letters which I'll call "consonants" and "vowels". We are also given a rational number r, and our infinite word satisfies a "proportionality property" (P):
(P) If w_i = w_j (with i < j), then the number of vowels in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) divided by the number of consonants in (w_i, w_{i+1}, ..., w_{j-1}) (counted with multiplicity) equals r.
Then I would like to be able to conclude that the consonant-vowel pattern of W is eventually periodic.
Example: W = (a, b, c, e, d, c, a, b, c, a, b, c, e, d, c, a, b, c, a, b, c, a, b, c, e, d, c, ....) where a and e are vowels and b, c, and d are consonants. (If the pattern isn't clear, write the word schematically as XY XXY XXXY XXXXY ... where X = (a, b, c) and Y = (e, d, c).) Let r = 1/2. With i = 1 and j = 7, we see that the number of vowels in positions 1 through 6 divided by the number of consonants in positions 1 through 6 equals 2/4, or 1/2. More generally, given any two positions i and j that both have the same letter in W, if we look at all the letters that occur in positions i through j-1, we see that the number of vowels divided by the number of consonants is 1/2, so property (P) is satisfied. And if we look at the consonant-vowel pattern, it's just vowel-consonant-consonant over and over again, repeating periodically.
My gut tells me that this is at the level of a hard IMO problem, and that it has a pretty solution. But that's no consolation to me, given that I don't see how to solve it.
A solution to this puzzle would advance me towards a seemingly unrelated goal in the theory of sphere-packing.
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Jeff Shallit wrote: Another construction: take the Thue-Morse word 01101001... and insert
a 2 between each letter to get 2021212021202021 ... and let {2} be vowel and {0,1} be consonants.
But then the consonant-vowel pattern is just period-2 alternation between consonants and vowels. So this isn't a counterexample. Jim
Oops, sorry, didn't read your requirements carefully enough! On 1/30/17 10:03 AM, James Propp wrote:
Jeff Shallit wrote:
Another construction: take the Thue-Morse word 01101001... and insert a 2 between each letter to get 2021212021202021 ... and let {2} be vowel and {0,1} be consonants.
But then the consonant-vowel pattern is just period-2 alternation between consonants and vowels. So this isn't a counterexample.
Jim
participants (3)
-
Andy Latto -
James Propp -
Jeffrey Shallit