Please do submit them, Fred. For f_3, I have an image in my head of a light source at the origin of a three-dimensional coordinate system. Thin grid-lines permeate the space, showing all the points where two of the three coordinates are integers. An octohedral screen, centered at the origin, marks off the part of the space where the sum of the absolute values of the coordinates is less than n. On the screen can be seen the shadows cast by the grid-lines in the light of the lamp at the origin. The surface of the octohedron is divided into f_3(n) regions by these shadow lines. On Wed, Aug 18, 2010 at 7:35 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun