On 8/19/10, Allan Wechsler <acwacw@gmail.com> wrote:
I think I may have an insight here, but at the moment I don't have the patience to carry it through, so I'm hoping some other math-funster will run with it. First, the image I had in mind in my previous post was wrong. But more importantly:
Suppose we count billiard-ball itineraries with the restriction that the ball is launched from one corner of the n-dimensional table. This eliminates certain sequences that were legal under the old rules.
Let's consider n=2. ABB is the simplest example of a sequence that used to be legal, but can't be achieved by launching from a corner of the table. The new sequence is much simpler to calculate: it's just the number of positive lowest-term rationals whose numerator and denominator sum to less than n. It's in OEIS as A002088, and its difference sequence is Euler's totient function, A000010. Call these "strict" sequences, and the old style sequences "lax" sequences.
I conjecture that any lax sequence under the old rules can be decomposed into three parts: a reversed strict sequence, a joint consisting of either AB or BA, and another strict sequence. Furthermore, the two strict sequences must be "close" in some sense, with the ratio of A's to B's not being too different.
The corresponding strict sequence for n=3 is harder to calculate. I think the first few entries are 1, 3, 9, 15, 45, 93, but I could easily have blundered. This sequence is not in OEIS.
In standard Sturmian word (m = 2 symbol alphabet; billiards in 2-D) terminology, your "strict" words are called "special"; and it's quite true that every word splits in the way you describe, though the decomposition may fail to be unique. In the end, such matters boil down to the existence of an invertible, Sturmian-preserving "inflation" morphism M acting (in the first instance) on infinite words: M: A -> AB^(k+1), B -> AB^k; for finite words, there's a complication over untidy ends to be sorted out. Applying M^(-1) corresponds to an application of one stage of the Euclidean algorithm to the ratio of A's to B's, k being its (continued fraction) quotient. The trouble is, as I remarked earlier, none of this extends to m > 2: instead of the Euclidean algorithm there looms a plethora of alternative Integer Relation Finding and MDCF algorithms, which are either highly complicated, or else don't even converge; and a bunch of "physical" models (Arnaud-Rauzy, interval-exchange, billiards, etc) which no longer coincide. Fred Lunnon