[seqfan] Re: SIAM Rev problem 89-19

[David Wilson]

That was back when the SIAM review was hardcopy and ran a problem section.
I originally posted the problem in sci.math. A SIAM editor got it from 
there and
played around with it, getting the strange non-repeating Maclaurin 
series that you
got.

You omitted the constant term in your Maclaurin series, which is 0. Had 
you included
it, you would have gotten

0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,..

which is A010060, the Thue-Morse sequence. If you let F(0) = a, F'(0) = 
b as in
the problem statement, you get the Maclaurin series by replacing each 0 
with a
and each 1 with b.

One solver gave a formula:

F(x) = ((a+b)/2) (1/(1-x)) + ((a-b)/2) PROD(k = 0..inf) (1-x^(2^k)).


Let S be a b-automatic set (subset of Z+ whose base-b representations 
form a regular language).
Let f_S be the indicator function for S on Z+, that is

For n in Z+, f_S(n) = 1 if n in S, 0 otherwise

Then the series

F_S(x) = SUM(k = 0..inf, f_S(k) x^k)

satisfies an equation of the form

SUM(k = 0..m, p_k(x) F(x^(b^k))

with finite m, where p_k is a polynomial.


So let S = A000069, the odious numbers. The indicator function of S is 
f_A000069 = A000060,
the Thue-Morse sequence. S happens to be a 2-automatic set, whose base-2 
representations
form the regular language 1(0*10*1)0*. Thus the series

F(x) = F_A000069(x) = SUM(k = 0..inf, f_A000069(k) x^k) = SUM(k = 
0..inf, A000060(k) x^k)

satisfies the equation

[1]  x*F(x) + (x+1) F(x^2) + (x^4-1) F(x^4) = 0

given in the problem.


A000069 is about the simplest example of a 2-automatic sequence S that 
is not periodic
(a periodic S would lead to an uninteresting rational function F_S). But 
there are many
other examples of b-automatic sets, such as A004215 (2-automatic with 
base-2 regular set
1(0+1)*111(00)*, or A051003 (10-automatic with base-10 regular set 
[0-9]*666[0-9]*).
Any such set S would have an F_S satisfying an equation similar to [1] 
(but in general much
bigger).


On 10/17/2011 6:15 PM, Richard Mathar wrote:
> In problem  89-19 of SIAM Review vol 31 no 4 (1989) on page 676
> a certain David W. Wilson orders:  "Find the MacLaurin series
> expansion of F(x) that satisfies the funcional equation
> (x^4-1)*F(x^4)+(x+1)*F(x^2)-x*F(x)=0, F(0)=a, F'(0)=b
> This problem arose in a study of the acceptance of binary numerical
> strings by finite automata."
> I did not find any "solution" page on this question in the journal.
> Are any of these series coefficients in the OEIS? Are they "interesting"?
> The one that starts linearly, F(0)=0, F'(0)=1 seems to
> have the Taylor coefficients 1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,...
> (leading 0 from the absolute term omitted).
>
> http://www.jstor.org/stable/2031547
> http://dx.doi.org/10.1137/1031135
>
> RJM
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>