[math-fun] Thue-Morse sequence
Nice! Re #1, #2, #3: At the risk of restating the obvious: https://en.wikipedia.org/wiki/Firing_squad_synchronization_problem --rwg Date: 2017-01-10 17:30 From: Fred Lunnon <fred.lunnon@gmail.com> That crap Fig. 10 graphic is bugging me, so I have uploaded up a folder of colour graphics related to number walls to https://www.dropbox.com/sh/mkpkoqy8r6ybmpd/AAAaHPx8wnEdSvc3UMMp0uzCa including a cleaner view of the ternary Pagoda wall filed at pagodab.gif , colour-coded 0, 1, 2 -> blue, magenta, cyan. Note how zero/blue pixels are isolated, apart from the first two (constant) rows; a segment from further along the sequence appears on the third row. "Ternary" means computing the wall entries (Hankel determinants) modulo 3 ; so the walls over the integers also have only isolated zeros --- as also apparently do those modulo a lot of other primes congruent to -1 (mod 4). WFL On 1/10/17, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Section 3 of the attached link might be relevant --- it turns out that the properties of T-M are much easier to establish via inspection of an equivalent 4-symbol sequence:
https://www.dropbox.com/s/1etnzbciqhbmy2j/csp08_submission_23.pdf
And while I am on the subject, the main topic of that paper is a little-known analogue of T-M christened the "Pagoda" sequence, arising as follows. The ternary T-M property of square-freedom is a special case of the more restrictive property of minimal linear complexity, that is nowhere satisfying _any_ linear recurrence of order r (for more than 2r consecutive terms).
This constraint turns out impossible to satisfy for a ternary sequence; but if relaxed to allow just 2r+1 consecutive terms (linear deficiency = 2), it results in an apparently unique (up to some fairly trivial transformations) object with a rather beautiful, fractal-like number wall. [Sadly the publisher required greyscale graphics, though these walls look much nicer in colour.]
The paper finishes with an improbable 2-D tiling-based proof that Pagoda satisfies deficiency = 2 , by which stage it has to be admitted that the going has become a little heavy ...
[Correction: the ambitious graphic on p.14 is missing its bottom two rows, especially confusing since it was (deliberately) rotated anticlockwise to emphasise the symmetry: as a result, the initial "22" below has been omitted. Along with an initial invisible white (= 0) and black (= 1) line running up the left-hand side from the bottom, not to mention the eye-watering pixel scale, it was not a success.
The Pagoda sequence should actually commence: 22010211 22011201 22010211 02211201 22010211 22011201 02210211 02211201 ... ]
Fred Lunnon
On 1/8/17, James Propp <jamespropp@gmail.com> wrote:
Do any of you have any favorite private facts about the Thue-Morse sequence, or any favorite links to existing content on this subject?
(I already know about the Numberphile video "The Fairest Sharing Sequence Ever".)
I'd especially like a link to an image or animation graphically depicting the self-similarity of the Thue-Morse sequence. (I have my own ideas for a GIF that would depict this, but I prefer not to create things that already exist.)
I'd also be interested in knowing whether any well-known (or not so well-known) poems use an abbabaab rhyme scheme, or whether there is any interesting music based on the Thue-Morse sequence.
(Yes, this is all for my next Mathematical Enchantments piece.)
Thanks,
Jim Propp
Yes indeed --- I just uploaded the whole directory, and some stuff about FSSP has crept in there. Tho' it's not completely irrelevant: FSSP proves to be an essential component in constructing a fast algorithm to compute number walls modulo (very small) primes! Still, I think I've done enough hijacking Jim's thread already ... WFL On 1/11/17, Bill Gosper <billgosper@gmail.com> wrote:
Nice! Re #1, #2, #3: At the risk of restating the obvious: https://en.wikipedia.org/wiki/Firing_squad_synchronization_problem --rwg
Date: 2017-01-10 17:30 From: Fred Lunnon <fred.lunnon@gmail.com>
That crap Fig. 10 graphic is bugging me, so I have uploaded up a folder of colour graphics related to number walls to https://www.dropbox.com/sh/mkpkoqy8r6ybmpd/AAAaHPx8wnEdSvc3UMMp0uzCa including a cleaner view of the ternary Pagoda wall filed at pagodab.gif , colour-coded 0, 1, 2 -> blue, magenta, cyan. Note how zero/blue pixels are isolated, apart from the first two (constant) rows; a segment from further along the sequence appears on the third row.
"Ternary" means computing the wall entries (Hankel determinants) modulo 3 ; so the walls over the integers also have only isolated zeros --- as also apparently do those modulo a lot of other primes congruent to -1 (mod 4).
WFL
On 1/10/17, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Section 3 of the attached link might be relevant --- it turns out that the properties of T-M are much easier to establish via inspection of an equivalent 4-symbol sequence:
https://www.dropbox.com/s/1etnzbciqhbmy2j/csp08_submission_23.pdf
And while I am on the subject, the main topic of that paper is a little-known analogue of T-M christened the "Pagoda" sequence, arising as follows. The ternary T-M property of square-freedom is a special case of the more restrictive property of minimal linear complexity, that is nowhere satisfying _any_ linear recurrence of order r (for more than 2r consecutive terms).
This constraint turns out impossible to satisfy for a ternary sequence; but if relaxed to allow just 2r+1 consecutive terms (linear deficiency = 2), it results in an apparently unique (up to some fairly trivial transformations) object with a rather beautiful, fractal-like number wall. [Sadly the publisher required greyscale graphics, though these walls look much nicer in colour.]
The paper finishes with an improbable 2-D tiling-based proof that Pagoda satisfies deficiency = 2 , by which stage it has to be admitted that the going has become a little heavy ...
[Correction: the ambitious graphic on p.14 is missing its bottom two rows, especially confusing since it was (deliberately) rotated anticlockwise to emphasise the symmetry: as a result, the initial "22" below has been omitted. Along with an initial invisible white (= 0) and black (= 1) line running up the left-hand side from the bottom, not to mention the eye-watering pixel scale, it was not a success.
The Pagoda sequence should actually commence: 22010211 22011201 22010211 02211201 22010211 22011201 02210211 02211201 ... ]
Fred Lunnon
On 1/8/17, James Propp <jamespropp@gmail.com> wrote:
Do any of you have any favorite private facts about the Thue-Morse sequence, or any favorite links to existing content on this subject?
(I already know about the Numberphile video "The Fairest Sharing Sequence Ever".)
I'd especially like a link to an image or animation graphically depicting the self-similarity of the Thue-Morse sequence. (I have my own ideas for a GIF that would depict this, but I prefer not to create things that already exist.)
I'd also be interested in knowing whether any well-known (or not so well-known) poems use an abbabaab rhyme scheme, or whether there is any interesting music based on the Thue-Morse sequence.
(Yes, this is all for my next Mathematical Enchantments piece.)
Thanks,
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Bill Gosper -
Fred Lunnon