- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Gap sequences for Thue-Morse
by Bill Gosper 26 Feb '17

26 Feb '17

Date: 2017-02-25 07:59 From: Jeffrey Shallit <shallit(a)uwaterloo.ca> To: <math-fun(a)mailman.xmission.com>, Fred Lunnon <fred.lunnon(a)gmail.com> Reply-To: shallit(a)cs.uwaterloo.ca, math-fun <math-fun(a)mailman.xmission.com> Some history: Thue actually *defined* his squarefree sequence 210201... by counting the number of 1's appearing between consecutive occurrences of 0 in (what we now call) the Thue-Morse sequence t. From the fact that t is overlapfree, a very very simple argument shows that the resulting sequence is squarefree. (For example, it appears in my book, A Second Course in Formal Language Theory.) The same argument applies to counting the number of 0's between consecutive 1's. So in some sense, you are doing it backwards. It is easiest to start from the overlapfreeness of Thue-Morse, and from this derive the squarefreeness of the resulting sequence. In any event, both the squarefree property of 210201... and 012021... is easily proved ab initio using the "logical approach" I have described in a number of papers (see my home page). For this, you need to find an automaton generating these sequences, and this is pretty easy, too. The first sequence is generated by iterating the morphism 2 -> 210 1 -> 20 0 -> 1 and the second is generated by iterating the morphism 0 -> 012 1 -> 02 2 -> 1 Both of these are pretty easy to prove by induction. <End JS> There's some sort of equivalence between the gaps method and direct conversion of Thue-Morse. E.g., starting with 0, the 5th iteration of your second morphism produces In[576]:= NestList[StringReplace[#, {"0" -> "012", "1" -> "02", "2" -> "1"}] &, "0", 5] Out[576]= {"0", "012", "012021", "012021012102", "012021012102012021020121", "012021012102012021020121012021012102012101202102"} But here is a piece of Thue-Morse base 4: In[577]:= "112122112212112122121122112122112212112211212212"; Shifting right one bit, In[580]:= IntegerString[FromDigits[%577, 4]/2, 4] Out[580]= "23031023103023031030231023031023103023102303103" Changing 2 to 1 and 3 to 2, In[581]:= StringReplace[%, {"2" -> "1", "3" -> "2"}] Out[581]= "12021012102012021020121012021012102012101202102" is your 5th iterate, modulo a dropped leading 0. --rwg On 2/24/17 9:38 PM, Fred Lunnon wrote: > A month ago I mentioned the sequence of gaps between consecutive occurrences > of 1 in the Thue-Morse sequence, which rather prettily appeared identical to > the well-known classical example of a `square-free' ternary sequence: > > [S_n] = 0 1 2 0 2 1 0 1 2 1 0 2 0 1 2 1 ... , > > in turn related to Thue-Morse = (sum of binary digits of n ) mod 2 , > > [T_n] = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ... , > > via S_n = 1 + T_n - T_{n-1} . > > At the time I assumed there existed some obvious, easily-discovered > explanation of the identity. While that may well be the case, I haven't > succeeded in discovering any: it is doubtful whether my present proof, > hewn from granite over several days of tantalising head-scratching, > could be compressed to less than a page while remaining intelligible. > > So is it obvious --- even if it isn't obviously obvious? WFL [25/02/17] > > > On 1/22/17, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: >> For case w = 1 , the resulting gap sequence is apparently the standard >> square-free ternary sequence >> S_n = 1 + T_n - T_{n-1} , >> with T_n denoting Thue-Morse sequence. >> >> This is indeed an "automatic sequence" in the sense of Allouche & >> Shallit's >> book of that title (2003), and generated by the width-4 iterated morphism >> 0 -> 03, 1 -> 02, 2 -> 21, 3 -> 20 >> followed by terminal symbol-to-symbol encoding 3 -> 1 . If I have >> understood >> JS correctly, it follows that both other cases w = 01, 010 are also >> automatic >> sequences, and so generated in a similar fashion. >> >> How wide are their morphisms? An ominous feature of the recursions I >> found earlier is the division by 3 rather than 2 involved in computing >> n" , suggesting that the width must be at least 6 ; if the same morphism >> also serves case w = 0 (and 1), the width goes up to at least 12 . >> >> WFL >> >>>> >>>> On 1/21/17, Jeffrey Shallit <shallit(a)uwaterloo.ca> wrote: >>>>> I just want to point out that there is a technology that can answer >>>>> questions like this purely mechanically, by a machine computation. >>>>> Given any particular w, or even for all w of a given length, the gaps >>>>> between occurrences are specified by a finite automaton, which can be >>>>> computed "automatically". We can also produce a so-called "linear >>>>> representation" that specifies gap positions and/or their first >>>>> differences. See the papers on my home page, particularly >>>>> E. Charlier, N. Rampersad, J. Shallit, Enumeration and decidable >>>>> properties of automatic sequences, Int. J. Found. Comput. Sci., 23 >>>>> (2012), 1035-1066. >>>>> >>>>> Jeffrey Shallit >>>>> https://cs.uwaterloo.ca/~shallit/papers.html >>>>> >>>>> >>>>> On 1/21/17 9:26 AM, Fred Lunnon wrote: >>>>>> As an indirect result of contemplating Jim Propp's Mathematical >>>>>> Enchantments >>>>>> >>>>>> https://mathenchant.wordpress.com/2017/01/16/avoiding-chazakah-with-the-pro… >>>>>> I became distracted (the way one does) into examining the sequence of >>>>>> gaps >>>>>> between repetitions of a given word w in the Thue-Morse sequence. >>>>>> >>>>>> Obviously the gap sequence will vary according to w . But it turns >>>>>> out that every such sequence is related by linear transformation and >>>>>> index shift to one of just three particular cases: w = 0, 01, 010 >>>>>> --- see for example sect. 4 of >>>>>> Lubomira Balkova, Edita Pelantov a, Wolfgang Steiner >>>>>> "Return words in the Thue-Morse and other sequences" >>>>>> >>>>>> https://hal.archives-ouvertes.fr/file/index/docid/90970/filename/BPS.pdf >>>>>> >>>>>> Initial segments, compressed into infinite words --- >>>>>> Thue-Morse: >>>>>> 01101001 10010110 10010110 01101001 10010110 01101001 01101001 >>>>>> 10010110 ... >>>>>> Gaps w = 0 : >>>>>> 21020121 01202102 01202101 21020121 01202101 21020120 21020121 >>>>>> 01202102 ... >>>>>> Gaps w = 01 : >>>>>> 11201102 11202110 11201102 11011202 11201102 11202110 11202112 >>>>>> 01102110 ... >>>>>> Gaps w = 010 (halved): >>>>>> 21032301 21030123 21032301 23210301 21032301 21030123 21030121 >>>>>> 03230123 ... >>>>>> >>>>>> From case w = 0 , the gap sequence for w = 1 follows by >>>>>> transposing >>>>>> 0 with 2 : which may be considered linear S_n -> 2 - S_n , or else >>>>>> the >>>>>> limit of shifts n -> n + 2^k for k = 0,1,2,... Either way, the >>>>>> result >>>>>> commences >>>>>> 0 1 2 0 2 1 0 1 2 1 0 2 0 1 2 1 ... >>>>>> 'Ang abaht --- >>>>>> < = > < > = < = > = < > < = > = ... >>>>>> --- haven't we seen something very like this somewhere else recently? >>>>>> >>>>>> So it would be reasonable to expect the other two cases to have some >>>>>> simple relation to Thue-Morse as well. Yeah, right --- the most >>>>>> concise >>>>>> (conjectural) recurrences I have been able to come up with for S_n >>>>>> so >>>>>> far are the following horrors. >>>>>> >>>>>> Given index n > 0 , >>>>>> for 0 < n <= 8 , set explicitly S_1,...,S_8 = >>>>>> 1, 1, 2, 0, 1, 1, 0, 2 for w = 01 , >>>>>> 2, 1, 0, 3, 2, 3, 0, 1 for w = 010 ; >>>>>> define k, n', n" via >>>>>> 4 n' < n <= 8 n' = 2^k ; >>>>>> n" = (n' - (-1)^k)/3 for w = 01 , >>>>>> (n' + 2(-1)^k)/3 for w = 010 ; >>>>>> then for n > 8 , S_n = >>>>>> S_(n - 4*n') for 4 n' < n <= 6 n' , >>>>>> S_(n - 3*n' + n") for 6 n' < n <= 7 n' , >>>>>> S_(n - 5*n' + n") for 7 n' < n <= 8 n' . >>>>>> >>>>>> Fred Lunnon >>>>>> >>>>>> _______________________________________________

1 0

Re: [math-fun] 7 earth-size planets identified in orbit around a dwarf star
by Keith F. Lynch 25 Feb '17

25 Feb '17

Dan Asimov <asimov(a)msri.org> wrote: > Not just one, but seven Earth-size planets that could potentially > harbor life have been identified orbiting a tiny star not too far > away, offering the first realistic opportunity to search for > biological signs of alien life outside of the solar system. They're almost certainly tidally locked. It's an interesting question whether winds would keep the permanent dark side warm enough that the atmosphere, or at least any water vapor in it, wouldn't all freeze out there, making life impossible. As Stephen Baxter pointed out in his novel _Proxima_, set on a similar planet around Proxima Centauri, dwarf stars are projected to last trillions of years, not mere billions like our sun. (Interestingly, he just made up that planet, but it has since been discovered, like Jonathan Swift's two small moons of Mars.) Most stars that can be seen without a telescope have a very high intrinsic brightness, which means they last only millions of years, almost certainly not long enough for advanced life to evolve on planets around them. Getting back to math, Wikipedia says "The orbits of planets b-g are nearly in resonance, having ... nearest-neighbor period ratios (proceeding outward) of about 8/5, 5/3, 3/2, 3/2 and 4/3 ...." I'm sure everyone here recognizes the signifance of first three ratios.

5 4

Re: [math-fun] Gap sequences for Thue-Morse
by Fred Lunnon 25 Feb '17

25 Feb '17

For case w = 1 , the resulting gap sequence is apparently the standard square-free ternary sequence S_n = 1 + T_n - T_{n-1} , with T_n denoting Thue-Morse sequence. This is indeed an "automatic sequence" in the sense of Allouche & Shallit's book of that title (2003), and generated by the width-4 iterated morphism 0 -> 03, 1 -> 02, 2 -> 21, 3 -> 20 followed by terminal symbol-to-symbol encoding 3 -> 1 . If I have understood JS correctly, it follows that both other cases w = 01, 010 are also automatic sequences, and so generated in a similar fashion. How wide are their morphisms? An ominous feature of the recursions I found earlier is the division by 3 rather than 2 involved in computing n" , suggesting that the width must be at least 6 ; if the same morphism also serves case w = 0 (and 1), the width goes up to at least 12 . WFL >> >> On 1/21/17, Jeffrey Shallit <shallit(a)uwaterloo.ca> wrote: >>> I just want to point out that there is a technology that can answer >>> questions like this purely mechanically, by a machine computation. >>> Given any particular w, or even for all w of a given length, the gaps >>> between occurrences are specified by a finite automaton, which can be >>> computed "automatically". We can also produce a so-called "linear >>> representation" that specifies gap positions and/or their first >>> differences. See the papers on my home page, particularly >>> E. Charlier, N. Rampersad, J. Shallit, Enumeration and decidable >>> properties of automatic sequences, Int. J. Found. Comput. Sci., 23 >>> (2012), 1035-1066. >>> >>> Jeffrey Shallit >>> https://cs.uwaterloo.ca/~shallit/papers.html >>> >>> >>> On 1/21/17 9:26 AM, Fred Lunnon wrote: >>>> As an indirect result of contemplating Jim Propp's Mathematical >>>> Enchantments >>>> >>>> https://mathenchant.wordpress.com/2017/01/16/avoiding-chazakah-with-the-pro… >>>> I became distracted (the way one does) into examining the sequence of >>>> gaps >>>> between repetitions of a given word w in the Thue-Morse sequence. >>>> >>>> Obviously the gap sequence will vary according to w . But it turns >>>> out that every such sequence is related by linear transformation and >>>> index shift to one of just three particular cases: w = 0, 01, 010 >>>> --- see for example sect. 4 of >>>> Lubomira Balkova, Edita Pelantov a, Wolfgang Steiner >>>> "Return words in the Thue-Morse and other sequences" >>>> >>>> https://hal.archives-ouvertes.fr/file/index/docid/90970/filename/BPS.pdf >>>> >>>> Initial segments, compressed into infinite words --- >>>> Thue-Morse: >>>> 01101001 10010110 10010110 01101001 10010110 01101001 01101001 >>>> 10010110 ... >>>> Gaps w = 0 : >>>> 21020121 01202102 01202101 21020121 01202101 21020120 21020121 >>>> 01202102 ... >>>> Gaps w = 01 : >>>> 11201102 11202110 11201102 11011202 11201102 11202110 11202112 >>>> 01102110 ... >>>> Gaps w = 010 (halved): >>>> 21032301 21030123 21032301 23210301 21032301 21030123 21030121 >>>> 03230123 ... >>>> >>>> From case w = 0 , the gap sequence for w = 1 follows by >>>> transposing >>>> 0 with 2 : which may be considered linear S_n -> 2 - S_n , or else >>>> the >>>> limit of shifts n -> n + 2^k for k = 0,1,2,... Either way, the >>>> result >>>> commences >>>> 0 1 2 0 2 1 0 1 2 1 0 2 0 1 2 1 ... >>>> 'Ang abaht --- >>>> < = > < > = < = > = < > < = > = ... >>>> --- haven't we seen something very like this somewhere else recently? >>>> >>>> So it would be reasonable to expect the other two cases to have some >>>> simple relation to Thue-Morse as well. Yeah, right --- the most >>>> concise >>>> (conjectural) recurrences I have been able to come up with for S_n so >>>> far are the following horrors. >>>> >>>> Given index n > 0 , >>>> for 0 < n <= 8 , set explicitly S_1,...,S_8 = >>>> 1, 1, 2, 0, 1, 1, 0, 2 for w = 01 , >>>> 2, 1, 0, 3, 2, 3, 0, 1 for w = 010 ; >>>> define k, n', n" via >>>> 4 n' < n <= 8 n' = 2^k ; >>>> n" = (n' - (-1)^k)/3 for w = 01 , >>>> (n' + 2(-1)^k)/3 for w = 010 ; >>>> then for n > 8 , S_n = >>>> S_(n - 4*n') for 4 n' < n <= 6 n' , >>>> S_(n - 3*n' + n") for 6 n' < n <= 7 n' , >>>> S_(n - 5*n' + n") for 7 n' < n <= 8 n' . >>>> >>>> Fred Lunnon >>>> >>>> _______________________________________________ >>>> math-fun mailing list >>>> math-fun(a)mailman.xmission.com >>>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>>> >>> >> >

2 7

[math-fun] Triangular # code golf
by Bill Gosper 22 Feb '17

22 Feb '17

I challenged young Rohan to find the shortest Mathematica definition for triangular number. We couldn't beat the obvious: StringLength@"(#+1)#/2&" 9 But then he said, OK, do it in 9 w/o using #. He stumped me! --rwg

1 0

[math-fun] 7 earth-size planets identified in orbit around a dwarf star
by Dan Asimov 22 Feb '17

22 Feb '17

7 Earth-Size Planets Identified in Orbit Around a Dwarf Star Not just one, but seven Earth-size planets that could potentially harbor life have been identified orbiting a tiny star not too far away, offering the first realistic opportunity to search for biological signs of alien life outside of the solar system. The planets orbit a dwarf star named Trappist-1, about 40 light years, or about 235 trillion miles, from Earth. That is quite close, and by happy accident, the orientation of the orbits of the seven planets allows them to be studied in great detail. One or more of the exoplanets — planets around stars other than the sun — in this new system could be at the right temperature to be awash in oceans of water, astronomers said, based on the distance of the planets from the dwarf star. “This is the first time so many planets of this kind are found around the same star,” said Michael Gillon, an astronomer at the University of Liege in Belgium and the leader of an international team that has been observing They could even discover convincing evidence of aliens. “I think that we have made a crucial step toward finding if there is life out there,” said Amaury H.M.J. Triaud, an astronomer at the University of Cambridge in England and another member of the research team. “Here, if life managed to thrive and releases gases similar to that we have on Earth, then we will know.” The findings appear Wednesday in the journal Nature. Telescopes on the ground now and the Hubble Space Telescope in orbit will be able to discern some of the molecules in the planetary atmospheres. The James Webb Telescope, scheduled to launch next year, will peer at the infrared wavelengths of light, ideal for studying the dimmer longer wavelength light coming from Trappist-1. Comparisons among the different conditions of the seven will also be revealing. “The Trappist-1 planets make the search for life in the galaxy imminent,” said Sara Seager, an astronomer at the Massachusetts Institute of Technology who was not a member of the research team. “For the first time ever, we don’t have to speculate. We just have to wait and then make very careful observations and see what is in the atmospheres of the Trappist planets.” More at https://www.nytimes.com/2017/02/22/science/trappist-1-exoplanets-nasa.html <https://www.nytimes.com/2017/02/22/science/trappist-1-exoplanets-nasa.html>. —Dan

1 0

Re: [math-fun] discrete curve shortening flow
by Dan Asimov 20 Feb '17

20 Feb '17

Sure, but my point was, How do you *define* the analogue of integral of squared curvature for a polygon? The curvature itself has an obvious integral, in the limit, for a sequence of curves approaching a polygon — the exterior angle — so that's a natural thing to use. For the integral squared curvature, by contrast we'd have to make some choice of how to interpret that, in order to obtain its analogue for a polygon. —Dan P.S. I've recently worked on a related question: Given a homotopy class of unit vector field on a square torus, which vector fields in that class minimize the integral squared curvature of the trajectories over the torus (or if you prefer over the unit square). The solutions to this are not C^1 vector fields, but they are differentiable. On Feb 20, 2017 4:27 AM Veit Elser <ve10(a)cornell.edu> wrote: ----- > On Feb 19, 2017, at 11:25 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: > > Thing is, the discrete approximation to a polygon's "integral curvature" (w.r.t. arclength) at a vertex is independent of which sequence of smooth curves is used to approach the polygon near the vertex. (The integral is [see below].)* > > But for the integral of *squared* curvature, that is not the case. Of course, but I thought he was interested in flows that make polygons round. The energy you cook up to define the flow then should *not* be a topological invariant (i.e. independent of shape). > > On Feb. 19, 2017, at 8:55 PM, Veit Elser <ve10(a)cornell.edu> wrote: > ----- > If you’re mostly interested in discrete approximations to continuous curves, I would use the integral of the squared curvature as the energy. When applied to 2D surfaces it is called the “Willmore energy”, and topological spheres always flow to the round sphere. I suspect the same happens to curves, although the curve will expand while it becomes round (the energy is not scale invariant in 1D as it is in 2D). There has been quite a lot of research on finding good approximations of curvature for triangulated surfaces. Brakke’s Surface Evolver does a nice job for 2D surfaces and I believe it also can be used for curves. > >> On Feb 18, 2017, at 9:09 PM, Mike Speciner <ms(a)alum.mit.edu> wrote: > ----- >> If one considers a polygon as a discrete approximation to a continuous closed curve, then each vertex has influence over a whole section of the curve. So it is not unreasonable to be less local when assigning a direction and 'curvature' at the vertex, dependent on the neighboring vertices. Whether there's a natural way to do this (and perhaps determine a 'best" continuous curve being approximated) might be an interesting question. -----

1 0

Re: [math-fun] discrete curve shortening flow
by Dan Asimov 20 Feb '17

20 Feb '17

Thing is, the discrete approximation to a polygon's "integral curvature" (w.r.t. arclength) at a vertex is independent of which sequence of smooth curves is used to approach the polygon near the vertex. (The integral is [see below].)* But for the integral of *squared* curvature, that is not the case. On Feb. 19, 2017, at 8:55 PM, Veit Elser <ve10(a)cornell.edu> wrote: ----- If you’re mostly interested in discrete approximations to continuous curves, I would use the integral of the squared curvature as the energy. When applied to 2D surfaces it is called the “Willmore energy”, and topological spheres always flow to the round sphere. I suspect the same happens to curves, although the curve will expand while it becomes round (the energy is not scale invariant in 1D as it is in 2D). There has been quite a lot of research on finding good approximations of curvature for triangulated surfaces. Brakke’s Surface Evolver does a nice job for 2D surfaces and I believe it also can be used for curves. > On Feb 18, 2017, at 9:09 PM, Mike Speciner <ms(a)alum.mit.edu> wrote: ----- > If one considers a polygon as a discrete approximation to a continuous closed curve, then each vertex has influence over a whole section of the curve. So it is not unreasonable to be less local when assigning a direction and 'curvature' at the vertex, dependent on the neighboring vertices. Whether there's a natural way to do this (and perhaps determine a 'best" continuous curve being approximated) might be an interesting question. ----- ----- —Dan —————————————————————————— * It's the exterior angle.

2 1

Re: [math-fun] discrete curve shortening flow
by Mike Speciner 19 Feb '17

19 Feb '17

If one considers a polygon as a discrete approximation to a continuous closed curve, then each vertex has influence over a whole section of the curve. So it is not unreasonable to be less local when assigning a direction and 'curvature' at the vertex, dependent on the neighboring vertices. Whether there's a natural way to do this (and perhaps determine a 'best" continuous curve being approximated) might be an interesting question. Not that I disagree with your notion of fairness. --ms On 18-Feb-17 20:23, Warren D Smith wrote: > Your rectangle example seems damning. > ANY vector "curvature" > which always has the direction of the angle-bisector, > is going to be killed by your rectangle example. > > And I really do not think it is fair to use any other direction! -- > Unless you abandon all pretense this has anything to do with > "motion of the boundary in the 'inward normal direction' > (which is a locally-defined notion) > with velocity proportional to 'curvature' > (which is a locally-defined notion)." > > So that's kind of cute, actually. I mean, the thing works for smooth > curves, but depends upon smoothness, and it works for simplices, > which are not smooth, but that is seen to be special. > >

2 1

[math-fun] Catalan's remains mysterious
by Bill Gosper 19 Feb '17

19 Feb '17

Date: 2017-02-19 00:30 From: Joerg Arndt <arndt(a)jjj.de> To: math-fun <math-fun(a)mailman.xmission.com> Reply-To: math-fun <math-fun(a)mailman.xmission.com> Just put a 1 into the upper parameters to cancel that lower hidden 1: (arcsin(z))^2 = z^2 * F([1, 1, 1], [3/2, 2], z^2) At least that's what my notes say (fxtbook, p.700). Best regards, jj Sorry, I was too cryptic. I was simply asking where this is in DLMF. It "belongs" in http://dlmf.nist.gov/15.4, but that bogus 1 disqualifies it. Look how trivial it is as a product matrix: 2 2 k z 1 ------- - 1 + 2 k k 0 1 But it doesn't have the obligatory k+1 in the 1,1 denominator. So it gets shunned. --rwg * Bill Gosper <billgosper(a)gmail.com> [Feb 19. 2017 08:50]: > I just fixed an egregious paste-o in gosper.org/pathi.pdf giving a second, > spurious value for > ζ(2,¼) instead of the intended ζ(2,¾), leading to an absurd "closed form" > for Catalan's constant. > --rwg > (I also wasted > ½ an hr trying to figure out why the new pdf didn't > replace the old one at > gosper.org. Eventually it did.) > > DLMF question: Due to the braindead hidden 1 in ₂F₁ notation, it can't > express arcsin². So > where in DLMF is the ₃F₂?

1 0

[math-fun] Catalan's remains mysterious
by Bill Gosper 19 Feb '17

19 Feb '17

I just fixed an egregious paste-o in gosper.org/pathi.pdf giving a second, spurious value for ζ(2,¼) instead of the intended ζ(2,¾), leading to an absurd "closed form" for Catalan's constant. --rwg (I also wasted > ½ an hr trying to figure out why the new pdf didn't replace the old one at gosper.org. Eventually it did.) DLMF question: Due to the braindead hidden 1 in ₂F₁ notation, it can't express arcsin². So where in DLMF is the ₃F₂?

2 1