On 7/25/10, Michael Kleber <michael.kleber@gmail.com> wrote:
Data update: the sequence through n=30 is
1,3,9,27,75,189,447,951,1911,3621, 6513,11103,18267,29013,44691,67251,98547,140865,197679,272799, 370659,497403,658371,859863,1110453,1420527,1799373,2260161,2815401,3479235, 4269279
Looks more n^5ish than n^6ish, at a casual glance.
evalf(log(4269279/3479235)/log(30/29)); # 6.036081126 evalf(log(3479235/2815401)/log(29/28)); # 6.033051457 No way --- it's order n^6 !!
The last term took something like 11 hours to count, so I think it's time to give Mma a break.
--Michael
Sterling effort. I've been trying hard to upstage it by finding an explicit formula, but am beginning to understand that the 3-D case may well qualitatively harder than the 2-D. There is a literature about generalisations of Sturmian sequences from 2-D / 2-symbol alphabet to n-D, which connects them to MDCF's. This particular generalisation is called "billiard words" (or "billiards words") --- the "words" here being what we might call infinite sequences, and "factors" finite words occurring within them. One reference which surveys these is the 2003 preprint available on the web: Laurent Vuillon "Balanced Words". A detailed study (also available on the web) is NICOLAS BEDARIDE "CLASSIFICATION OF ROTATIONS ON THE TORUS T^2" The following may well be very relevant, but I can't get at them from home: Jean-Pierre Borel "How to build billiard words using decimations" RAIRO-Theor. Inf. Appl. Volume 44, Number 1, January-March 2010 59--77 Jean-Pierre Borel "A geometrical Characterization of factors of multidimensional Billiards words and some Applications" Theoretical Computer Science 380 (2007) 286--303 http://hal.archives-ouvertes.fr/hal-00465586/fr/ The particular difficulty afflicting billiards --- in comparison with, say, the more common Arnaud-Rauzy generalisation --- is their nonlinear complexity: apparently, the number of distinct factors of length n in any given trajectory of cubical billiards (Allan's original problem) is in general n^2 + n + 1 . Fred Lunnon