On 8/9/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
Called earlier "interleavings of arithmetic progressions", billiard sequences can be viewed equivalently as generated by discrete approximation to a line in m-dimensional space; by a weightless ball bouncing against the walls of an m-dimensional hypercube; or by a point translated continuously through a suitably partitioned m-dimensional torus T^m.
In each case, we ask for function f_m(n) counting the number of m-symbol words of length n occurring as factors of possible billiard sequences. Allan Wechsler posed the case m = 3. I have now had a look at m = 4, for which I find f_4(n) = 1, 4, 16, 64, 244, 856, 2776, 8356, 23032, 59200, 142624, 324484, 696256, 1422436, 2779900, when n = 0,...,14. [OK, now do your worst, Michael!] Setting n = 14 in the expression log(f(n)/f(n-1)) / log(n/(n-1)) gives 9.04, suggesting to the credulous optimist that perhaps f_4(n) = O(n^9).
4-D billiards update --- for n = 0,...,16, f_4(n) = 1, 4, 16, 64, 244, 856, 2776, 8356, 23032, 59200, 142624, 324484, 696256, 1422436, 2779900, 5219452, 9455596 [In 14.6 hours, Magma running on elderly G4 Mac Powerbook.] The final values of log(f(n)/f(n-1)) / log(n/(n-1)) now read ... 8.62473, 8.77451, 8.92534, 9.04146, 9.13106, 9.20714 --- a little too monotonic even for my powers of extrapolation to persuade to approach 9 ...
... A (notionally slightly weaker) version of this projection constraint involves projecting instead onto planes, yielding instead m_C_2 2-symbol sequences, one on each pair of the m symbols. If a candidate is already known to be valid, it may be reconstructed from just m-1 of these binary projections --- say, just those involving symbols (1,2),...,(1,m). But it is already known that there are O(n^3) of the latter, from which it follows immediately that f_m(n) <= O(n^(3m-3)). The numerical results suggest that degree 3(m-1) is actually sharp!
The numerical results suggest that degree 3(m-1) is actually bo11ox. Cleaned up, I find instead f_m(n) < O(n^k) with exponent bound k = 3 m_C_2 + m-1 = (3m+2)(m-1)/2, e.g. k = 11 for m = 3. The first term arises from the m_C_2 2-symbol projections; the second from the number (n+m-1)_C_n = O(n^(m-1)) of ways to assign frequencies to m symbols in a length-n word. Hardly impressive, but it does at least establish that the m-dimensional word counts are polynomial. Since nobody else has done so, I propose to submit f_3(n) and f_4(n) to OEIS. Fred Lunnon