cycle misses some periodic cycles

[jeanluct]

Consider the braid (same as in issue #48):

#!matlab

>> b = braid([4  3 -1  4  1  4  2 -3 -4  3 -2 -1  4  2  4 -3]);
>> b.cyclemat('plot')
Error using braidlab.braid/cycle (line 147)
Failed to achieve convergence after 1000 iterations.  Try to increase MAXIT.

Error in braidlab.braid/cyclemat (line 53)
[pn,it] = cycle(b,varargin{:});

However, looking at the plot, the braid clearly has period 4.

I think what happens is that two of the iterates actually have identical p/n patterns, so the code keeps failing to converge with period one every 4 iterations.

[jeanluct]

From Jean-Luc Thiffeault on 2014-06-23 14:28:14+00:00

Mention this bug in help message in dc1d429.

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-25 13:13:14+00:00

Something Toby says in his Dynnikov manual strikes me as relevant: "Convergence by cycle iterates until the approximate growth rates of successive iterates are very close to a periodic cycle of length less than the number of punctures."

So far I haven't found single example where the period is larger than the number of punctures. Why is that? This would help greatly in looking for cycles.

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-25 16:26:04+00:00

http://www.mathworks.com/help/signal/ref/seqperiod.html

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-26 11:11:25+00:00

Fix cycle convergence detection. Resolves issue #52.

→ <<cset 8124dc9b05df>>

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-26 11:18:13+00:00

D'oh! Fails the testsuite.

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-26 11:49:20+00:00

The problem is the following. Let

#!matlab

>> b1 = braid([1 2]);
>> b2 = braid([1 2 3]);
>> b3 = tensor(b1,b2)

b3 =  < 1  2  4  5  6 >

b1 has a cycle of period 3; b2 has a cycle of period 4. Therefore, since b3 is simply the two braids next to each other, it must have period 12! This is indeed the case. So the conjecture that the period is bounded by n is completely false.

For now (bddebf3) choose maxperiod = maxit/nconvereq, which is the maximum we could detect anyways.

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-26 11:59:31+00:00

Ok, so the problem is that of finding the partition of n with the largest lcm.

Google: Find out the largest LCM of the partitions of n

Seems like a hard problem.

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-26 12:02:30+00:00

Maybe best to just make a list with Mathematica:

#!Mathematica

In[1] := Table[Max[LCM @@ # & /@ IntegerPartitions[n]], {n, 30}]

Out[1] := {1, 2, 3, 4, 6, 6, 12, 15, 20, 30, 30, 60, 60, 84, 105, 140, 210,
210, 420, 420, 420, 420, 840, 840, 1260, 1260, 1540, 2310, 2520, 4620}

[jeanluct]

From Jean-Luc Thiffeault on 2014-09-26 12:40:26+00:00

Hardcode some max periods in cycle (print warning). Finally resolves issue #52.

→ <<cset 008dbccccc67>>