We're trying to find a number, like e^3, or probably easier, e^4 (from coth 2), that we can prove nonHurwitz. We are tantalized by the apparent breakdown of finite state when we subject the c.f. for coth 2 (with fractional terms 1/2,3/2,5/2,...) to a homographic function, vs the simple, repetitive behavior when we process coth 1/n (with terms n,3n,5n,...). In the latter case, finite state can be proven by simple matrix identities. E.g., the process of simply doubling (={{2,0},{0,1}}, representing (2#+0)/(0#+1)) coth 1 = 1,3,5,... produces exactly five outputs for every three inputs via the identity 2 0 1 + 6 k 1 3 + 6 k 1 ( ).( ) . ( ) . 0 1 1 0 1 0 5 + 6 k 1 2 + 12 k 1 1 + 3 k 1 ( ) = ( ) . ( ) . 1 0 1 0 1 0 1 1 1 1 2 + 3 k 1 2 0 ( ).( ).( ) . ( ) 1 0 1 0 1 0 0 1 I.e., input 6k+1,6k+3,6k+5 and output 12k+2,3k+1,1,1,3k+2 restoring the {{2,0},{0,1}} state, so twice 1,3,5,7,..., = 2,1,1,1,2,14,4,1,1,5,26,7,1,1,8,... . Left and right multiplying the equation by {{1,0},{0,2}} (= halving) produces the matrix proof of the reverse process: Five inputs produce three outputs, where we cancel the 2s in {{2,0},{0,2}} to get the identity matrix, which we erase. Every homographic function of a Hurwitz c.f. will produce one of these matrix equations. Here is the actual computation of 2 coth 1. In[356]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st,{{{2*#+1,1},{1,0}}&,0,{{2,0},{0,1}}},32]]] st takes a state vector containing the function for the nth input matrix, the current value of n, the (2x2) state matrix (initially, the function we wish to apply to the c.f.), and the output c.f. so far. For each output, it also Sows the current n. After 32 (input or output) steps, we have the current state vector and a list of how many inputs preceded each output: Out[356]= {{{2 #1+1,1},{1,0}}&,12,{{2,0},{0,1}}, 2,1,1,1,2,14,4,1,1,5,26,7,1,1,8,38,10,1,1,11} {1,0,0,0,2,1,0,0,0,2,1,0,0,0,2,1,0,0,0} We see that the state matrix has returned to {{2,1},{1,0}}, and the I/O behavior is repetitive: read one, output four, read two, output 1. The actual update function is Clear[st]; st[{f_, n_, M_?MatrixQ, cf___}] := Block[{xy = Divide @@ (M.{{1, 1}, {1, 0}}), t}, If[Floor@xy[[1]] == (t = Floor@xy[[2]]), Join[{f, Sow[n]}, {{{0, 1}, {1, -t}}.M, Sequence @@ {cf, t}}], xy = M.f[n]; {f, n + 1, xy/GCD @@ Join @@ xy, cf}]] Now let's allow fractional terms. To keep the state matrix canonical, we can scale the input matrices to be integers, e.g. {{1/2,1},{1,0}} -> {{1,2},{2,0}}. This will scale the state matrix determinant by -4 instead if -1, clearly blowing finite-state, but for the possibility of later scaling out common factors from the state matrix. The only change to the stepper is to replace Divide @@ (M.{{1, 1}, {1, 0}}) by Divide @@M, reflecting that we can no longer rely on the unread tail of the c.f. to exceed 1. This will typically introduce a one term latency which will mildly conceal state repetition. Let's compute 2 coth 1 as the identity function of 1*2,3/2,5*2,7/2,... instead of doubling 1,3,5,... as before. In[366]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st2,{{{2^(-1)^#*(2*#+1),1},{1,0}}&,0,{{1,0},{0,1}}},35]]] Out[366]= {{{2^(-1)^#1 (2 #1+1),1},{1,0}}&,14,{{27,2},{2,0}}, 2,1,1,1,2,14,4,1,1,5,26,7,1,1,8,38,10,1,1,11,50} {1,1,0,0,1,1,1,0,0,1,1,1,0,0,1,1,1,0,0,1} It's still finite state (modulo a term of latency, and a temporary determinant of -4). But now let's try something ridiculously simple: In[372]:= FromContinuedFraction[{{1/2}}] Out[372]= 1/4 (1+Sqrt[17]) In[373]:= ContinuedFraction[%] Out[373]= {1,{3,1,1}} I.e., let's extract the strictly periodic 1,3,1,1,3,1,1,... (why didn't it say {{1,3,1}}?) from 1/2,1/2,1/2,... . (And why won't it allow FromContinuedFraction[{{x}}]? Or {{1,1,0}}?) Anyway, here's the bad news: In[376]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st2,{{{1/2,1},{1,0}}&,0,{{1,0},{0,1}}},69]]] Out[376]= {{{1/2,1},{1,0}}&,52, {{6370761842645543,5705560984788822}, {5040360126932101,1330401715713442}}, 1,3,1,1,3,1,1,3,1,1,3,1,1,3,1,1,3} {4,5,0,4,3,0,6,3,0,4,5,0,4,5,0,4} It's not finite state! (Note the huge matrix.) The input and output are repetitive, but their timings are not. Instead we have a very interesting quinary pattern, which becomes ternary under the mapping {4,5,0}->a, {4,3,0}->b, {6,3,0}->c: In[377]:= TableForm[Partition[Partition[Differences[#[[2,1]]]&@ Reap[Nest[st2,{{{1/2,1},{1,0}}&,0,{{1,0},{0,1}}},1093]],3] /.{{4,5,0}->a,{4,3,0}->b,{6,3,0}->c},15]] Out[377]//TableForm= a b c a a b c a b c c a b c a a b c a a b c a b c c a b c a a b c a b c c a b c c a b c a a b c a b c c a b c c a b c a a b c a b c c a b c a a b c a a b c a b c c a b c a a b c a This means that obvious misbehavior of the matrix processing coth 2 does not guarantee misbehavior of its c.f., = (e^4+1)/(e^4-1). Yet this is anything but random. Is it fractal, or does it draw one under some interpretation? A less degenerate example is computing coth 1 from (2#+1)/(0#+1), where #:=0 + ContinuedFractionK[k, k, {k,∞}]=1/(e-1) : In[378]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st,{{{#,#+1},{1,0}}&,0,{{2,1},{0,1}}},69]]] Out[378]= {{{#1,#1+1},{1,0}}&,49, {{2206943012448662116158774811288656,2206950077348678728346652963751377}, {26920936494950091431033190362544,26369778840455766330813469539023}}, 2,6,10,14,18,22,26,30,34,38,42,46,50,54,58,62,66,70,74,78} {3,3,2,2,3,2,2,3,2,2,3,2,2,3,1,3,3,1,3} The output intervals are crazy, yet the terms are not. What is it about processing 1/2,3/2,5/2,... that assures crazy sizes, not just crazy intervals?: In[387]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st,{{{#+1/2,1},{1,0}}&,0,{{1,0},{0,1}}},666]]] Out[387]= {{{#1+1/2,1},{1,0}}&,155, {{326309420948894846183209753068665518244757108833, -1309845084617830597650227042950849295187806558}, {183300788310157256605231207606976793305330479468, 5656683762988769057687299987446265732036054360}}, 1,26,1,3,1,42,2,3,1,28,5,1,4,3,1,6,12,1,40,1,9,1,8,2,1,1,2,1,3,5,4,1,1,5,1,5, 8,1,2,1,1,2,16,1,3,2,6,4,4,14,3,2,1,2,3,1,2,1,18,4,1,1,1,32,1,4,2,6,6,4,2,1, 1,3,2,1,4,1,1,8,1,2,1,9,8,1,2,4,1,19,1,3,3,2,11,1,62,2,2,2,6,21,3,7,1,1,7,23, 1,19,1,4,1,1,1,1,5,2,13,2,7,25,6,2,3,36,3,1,9,2,379,2,5,1,1,3,1,1,1,36,26,1,22, 1,1,5,1,1,2,1,1,13,2,1,3,4,1,2,7,1,2,1,1,330,1,1,4,3,5,10,1,31,2,27,3,1,1,2,56, 3,3,4,153,1,1,1,1,2,2,1,1,1,18,2,4,3,1,10,1,8,3,20,2,14,4,1,50,5,1,2,1,16,3,3, 28,1,1,3,1,1,7,2,2,8,2,7,1,1,1,3,9,4,1,1,2,1,1,3,3,2,1,3,197,63,1,6,14,5,6,1,1,1, 2,6,11,3,7,7,2,3,13,1,1,1,4,1,1,2,2,1,1,2,2,14,1,4,3,1,17,4,1,2,1,11,1,5,1,11,2,2, 1,2,1,1,2,1,3,3,2,2,2,1,1,9,2,1,2,1,2,1,1,6,4,1,16,2,2,1,3,1,14,1,1,2,3,1,1,2,5,1, 104,3,6,1,1,1,10,2,39,1,2,1,8,4,2,1,13,1,2,17,575,1,1,4,87,1,9,1,8,1,1,2,6,6,1,2, 1,1,6,1,1,16,12,1,1,5,4,1,76,2,3,8,1,128,2,2,4,1,2,1,2,4,1,3,3,2,2,1,3,2,1,1,2,2,31, 4,2,1,4,1,4,1,2,2,2,2,5,3,2,1,3,3,355,1,1,9,2,2,1,1,3,19,72,11,2,2,2,1,23,1,2,31,2, 7,1,1,2,5,1,2,35,1,1,1,7,1,10,1,3,3,4,5,21,1,1,1,2,2,1,7,1,1,19,4,1,8,2,2,1,2,34,1, 59,4,1,2,4,28,1,1,1,1,1,3,3,4,1,13,45,1,11,1,5,1,9,1,3,1,3,3,1} {2,0,2,0,1,0,1,0,1,1,0,1,1,0,1,0,0,2,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0, 0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0, 1,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,0,2,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0, 1,1,0,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,2,0,0,0,1,0,1,0,0,0, 1,1,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,1,0,0, 1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0, 0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0, 0,0,0,1,0,2,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0, 0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,2,0,0,0,0,1,0,0,0, 1,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0, 0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0} 2 is getting rare. Are there finitely many? Are the 0 bursts bounded? If not, could that make a proof? We'd triumph by showing unbounded 1 bursts in the *output* sequence. Or even unbounded bursts < any fixed constant. And we only need to prove nonHurwitz for *any* (a e^4 + b)/(c e^4 + d), a,b,c,d rational. (Desi insults notwithstanding.) --rwg (Apologies: In[378] is confusing because ConfinuedFractionK uses {{0,num},{1,den}} style matrices, but st uses {{den,num},{0,1}}.) On Sun, Oct 7, 2012 at 2:12 PM, Bill Gosper <billgosper@gmail.com> wrote:
The quasiperiod for the continued fraction of e ~ 2.718 can be written as the three polynomials {1,2k,1}, "modulo rotation and translation", e.g. {2k-2,1,1}. It can also be "inflated" by a factor of 2 or 3 or ..., e.g {1,4k,1,1,4k+2,1} or {1,6k,1,1,6k+2,1,1,6k+4,1} or ... .
If I heard him right, Julian has proved that given the Hurwitz # x :={P0(k),P1(k),...}, there is an inflation factor Δ ≤ (ad-bc)^4 such that the quasiperiod of y:=(ax+b)/(cx+d) can be written by inflating x by Δ and then replacing each polynomial Pi with an even number of constant polynomials, followed by a polynomial with the same degree as Pi. In particular, linear terms cannot arise from nonlinear terms. The resulting CF of y may often be "deflated" to have a shorter quasiperiod than x. --rwg One use of this theorem is to detect the possibility or impossibility of finding a homographic transformation shortening a long quasiperiod.
For some reason, Julian disavows calling this a "structure theorem". It can probably be extended to cover exponential (e.g.) as well as polynomial terms.