[math-fun] Billiard word counts (was "Interleavings of three arithmetic progressions")
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). The program does its best to avoid inequality analysis by first projecting each candidate sequence onto the axis hyperplanes, yielding m new (m-1)-symbol sequences which are necessarily also billiard, and can be validated from a precomputed list for dimension m-1. If any of these fails, the candidate fails; and if only one candidate remains after n-th symbols are attached to a valid (n-1)-length sequence, there is still no need for inequality analysis --- the ball cannot avoid bouncing next against some wall pair! The projection criterion is surprisingly effective: without inequality analysis, when m = 3 it catches every dud word for n < 10; when m = 4, for n < 12. I find it frustrating that it can't be beefed up just a little more, since inequality analysis of those cases remaining slows the Maple program by a factor of 10. 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! Finally, a taste of the difficulty to be expected in beefing up projection to achieve sufficiency is provided by the following example: the one-way infinite (and easily made two-way?), ultimately period-6 ternary word 1121231123 (112123)^oo is not billiard (by inequality analysis on its length-10 prefix); though all three of its projections 11212112(11212)^oo, 1113113(1113)^oo, 22323(223223)^oo are binary billiard words (aka Sturmian). Extraordinarily long impasses are possible: the above's length-31 prefix 1121231123 1121231121 2311212311 2 may be followed by the foreign length-85 suffix 3121123121 1231213121 2131212131 2132112132 1121321132 1211321211 3212131211 3212113212 13121 yielding a non-billiard length-116 ternary word, all of whose projections are billiard words, but which cannot be further extended without invalidating some projection. Any prospect that the projection criterion might be strengthened via larger samples is quashed by these examples. Another apparently promising test is to check that the candidate, whose length-(n-1) prefix was drawn from a precomputed list, has length-(n-1) suffix also a member of the same list. Surprisingly, this test appears to reject no additional candidates besides those already caught by projection: is there a (not terribly exciting) theorem here? Fred Lunnon On 7/26/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
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
On 8/9/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
... Extraordinarily long impasses are possible: the above's length-31 prefix 1121231123 1121231121 2311212311 2 may be followed by the foreign length-85 suffix 3121123121 1231213121 2131212131 2132112132 1121321132 1211321211 3212131211 3212113212 13121 yielding a non-billiard length-116 ternary word, all of whose projections are billiard words, but which cannot be further extended without invalidating some projection.
Claim unjustified, I'm afraid --- the actual back-up required there is much shorter than implied above. A more well-organised expedition to establish the shortest impasses prefixed by the dud 1121231123 uncovers length-26, 26, 29: 1121231123 1213121321 211321, 1121231123 1213211321 211321, 1121231123 1213211321 213211321. So while a (nontrivial) "pseudo-billiard" word --- one whose projections are all billiard words --- has in general some infinite pseudo-billiard extension, it is also conceivable that it has (always) another which terminates at an impasse within some boundable length. This would provide a combinatorial nec. & suff. criterion for a billiard word, independent of inequality analysis --- though the example above suggests that the bound may not be terrribly practical. [An efficient combinatorial criterion based on morphism inversion, and related to the Euclidean HCF algorithm, already exists when m = 2; it leads further to the explicit formula for f_2(n).] An alternative possibility: for given m, does there exist a finite set of words (like the length-10 dud above), such that every pseudo-billiard word has some factor in this set? Fred Lunnon
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
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
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. On Thu, Aug 19, 2010 at 11:24 AM, Allan Wechsler <acwacw@gmail.com> wrote:
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
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
The counts of 3-D billiard words of length n with k = 1,2,3 descendants of length n+1, for n = 0,...,19 are respectively 0, 0, 0, 6, 24, 78, 186, 372, 876, 1632, 3024, 5310, 8496, 13344, 21186, 31878, 46752, 66936, 94800, 130194, when k = 1; 0, 0, 6, 18, 36, 78, 150, 306, 420, 792, 1338, 2082, 3228, 4830, 7050, 9954, 13920, 18738, 24666, 32610, when k = 2; 1, 3, 3, 3, 9, 15, 33, 63, 153, 219, 261, 351, 585, 879, 933, 1233, 1401, 1899, 2301, 3111, when k = 3; Allan's sequence is the sum of the last two; note that his 15 should read 21. Fred Lunnon 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.
21 is correct. Now I have less confidence in the later entries. On Fri, Aug 20, 2010 at 4:12 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
The counts of 3-D billiard words of length n with k = 1,2,3 descendants of length n+1, for n = 0,...,19 are respectively
0, 0, 0, 6, 24, 78, 186, 372, 876, 1632, 3024, 5310, 8496, 13344, 21186, 31878, 46752, 66936, 94800, 130194, when k = 1;
0, 0, 6, 18, 36, 78, 150, 306, 420, 792, 1338, 2082, 3228, 4830, 7050, 9954, 13920, 18738, 24666, 32610, when k = 2;
1, 3, 3, 3, 9, 15, 33, 63, 153, 219, 261, 351, 585, 879, 933, 1233, 1401, 1899, 2301, 3111, when k = 3;
Allan's sequence is the sum of the last two; note that his 15 should read 21.
Fred Lunnon
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
In my early attempts to compute hairy combinatorial sequences, it was always the last one which was wrong --- I never learnt not to push primitive hardware just past its limits. So it was puzzling to see that one wrong, yet the next two right. WFL On 8/20/10, Allan Wechsler <acwacw@gmail.com> wrote:
21 is correct. Now I have less confidence in the later entries.
On Fri, Aug 20, 2010 at 4:12 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
The counts of 3-D billiard words of length n with k = 1,2,3 descendants of length n+1, for n = 0,...,19 are respectively
0, 0, 0, 6, 24, 78, 186, 372, 876, 1632, 3024, 5310, 8496, 13344, 21186, 31878, 46752, 66936, 94800, 130194, when k = 1;
0, 0, 6, 18, 36, 78, 150, 306, 420, 792, 1338, 2082, 3228, 4830, 7050, 9954, 13920, 18738, 24666, 32610, when k = 2;
1, 3, 3, 3, 9, 15, 33, 63, 153, 219, 261, 351, 585, 879, 933, 1233, 1401, 1899, 2301, 3111, when k = 3;
Allan's sequence is the sum of the last two; note that his 15 should read 21.
Fred Lunnon
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 8/19/10, Allan Wechsler <acwacw@gmail.com> wrote:
Please do submit them, Fred. On Wed, Aug 18, 2010 at 7:35 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Since nobody else has done so, I propose to submit f_3(n) and f_4(n) to OEIS.
I have done so, including Michael's version 1 Mathematica and my final Magma programs. As suggested by the OEIS instructions, I also fed the first 10, and later all 31, computed values of f_3(n) to superseeker; and received the following replies (fixed spacing) --- << Superseeker finds ... 2 3 [-27 + 27 a(n) - 9 a(n) + a(n) , lgdegf] 2 3 4 5 [-243 + 405 a(n) - 270 a(n) + 90 a(n) - 15 a(n) + a(n) , lgdegf]
where "lgdegf" stands for "logarithmic derivative of exponential generating function" The polynomials are simply (a(n) - 3)^3 and (a(n) - 3)^5 respectively. It's possibly that superseeker has discovered something relatively important here --- unfortunately, I have no idea what that might be, can find no assistance in the documentation, and have failed to put any construction on the phrase which stands up to numerical confirmation. Can somebody please enlighten me? Fred Lunnon
* Fred lunnon <fred.lunnon@gmail.com> [Aug 20. 2010 08:19]:
On 8/19/10, Allan Wechsler <acwacw@gmail.com> wrote:
Please do submit them, Fred. On Wed, Aug 18, 2010 at 7:35 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Since nobody else has done so, I propose to submit f_3(n) and f_4(n) to OEIS.
I have done so, including Michael's version 1 Mathematica and my final Magma programs.
As suggested by the OEIS instructions, I also fed the first 10, and later all 31, computed values of f_3(n) to superseeker; and received the following replies (fixed spacing) ---
<< Superseeker finds ... 2 3 [-27 + 27 a(n) - 9 a(n) + a(n) , lgdegf]
2 3 4 5 [-243 + 405 a(n) - 270 a(n) + 90 a(n) - 15 a(n) + a(n) , lgdegf]
where "lgdegf" stands for "logarithmic derivative of exponential generating function" The polynomials are simply (a(n) - 3)^3 and (a(n) - 3)^5 respectively.
It's possibly that superseeker has discovered something relatively important here --- unfortunately, I have no idea what that might be, can find no assistance in the documentation, and have failed to put any construction on the phrase which stands up to numerical confirmation.
Can somebody please enlighten me? Fred Lunnon
Cannot find "lgdegf" in any of the (program files) refd from http://oeis.org/classic/transforms.html so I suggest to ask NJAS via email (I thought he was on math-fun).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Well, if NJAS is listening, he must have heard ... Perhaps some kind soul might forward this query to SeqFan for me? Having thought a little about it, I'm now inclined to dismiss this as nonsense: the sequence commences with powers of 3, and later grows like n^6; the superseeker expression suspiciously resembles an amalgam of the linear recurrences for 3^n and degree-5 polynomial ... WFL On 8/20/10, Joerg Arndt <arndt@jjj.de> wrote:
* Fred lunnon <fred.lunnon@gmail.com> [Aug 20. 2010 08:19]:
I have done so, including Michael's version 1 Mathematica and my final Magma programs [A180238, A180239].
As suggested by the OEIS instructions, I also fed the first 10, and later all 31, computed values of f_3(n) to superseeker; and received the following replies (fixed spacing) ---
<< Superseeker finds ... 2 3 [-27 + 27 a(n) - 9 a(n) + a(n) , lgdegf]
2 3 4 5 [-243 + 405 a(n) - 270 a(n) + 90 a(n) - 15 a(n) + a(n) , lgdegf]
where "lgdegf" stands for "logarithmic derivative of exponential generating function" The polynomials are simply (a(n) - 3)^3 and (a(n) - 3)^5 respectively.
It's possibly that superseeker has discovered something relatively important here --- unfortunately, I have no idea what that might be, can find no assistance in the documentation, and have failed to put any construction on the phrase which stands up to numerical confirmation.
Can somebody please enlighten me? Fred Lunnon
Cannot find "lgdegf" in any of the (program files) refd from http://oeis.org/classic/transforms.html so I suggest to ask NJAS via email (I thought he was on math-fun).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think lgdegf means that f'(x) / f(x) is the rational function EGF for the given terms. So if f(x) given by superseeker is (a(n) - 3)^3 then the EGF is 3 / (a(n) - 3)??? hm, now I'm not making sense even to myself. Maybe you're supposed to find the function a(n) that makes this identically zero and then take a'(n) / a(n)? No, that doesn't make sense either, since a(n) = 3 is an obvious solution. Oh, but the higher-order terms probably give solutions like a(n) = n * 3^n or something? And then a'(n) / a(n) could be an EGF, and maybe it is then a rational function since the 3^n will divide out? As you can tell, it's too late at night for me to think this through, but maybe my muttering here will at least enable someone else to figure out what I should have said if only I knew what I was talking about. --Josh On Fri, Aug 20, 2010 at 12:10 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Fred lunnon <fred.lunnon@gmail.com> [Aug 20. 2010 08:19]:
<< Superseeker finds ... 2 3 [-27 + 27 a(n) - 9 a(n) + a(n) , lgdegf]
2 3 4 5 [-243 + 405 a(n) - 270 a(n) + 90 a(n) - 15 a(n) + a(n) , lgdegf]
where "lgdegf" stands for "logarithmic derivative of exponential generating function" The polynomials are simply (a(n) - 3)^3 and (a(n) - 3)^5 respectively.
Re superseeker's mysterious report on 3-D billiard sequence --- I fed A180238 to gfun via Maple9 --- and strange to say, gfun replied straight away "FAIL". So as I suspected, it is nonsense; and there appear to be bugs both in the way superseeker is to utilising the gfun package, and its output of the results; while the documentation leaves something to be desired (like, some documentation)! However, the OEIS site has no machinery in evidence for reporting bugs; so it seems I'll just have to leave things there for now ... WFL On 8/19/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
... As suggested by the OEIS instructions, I also fed the first 10, and later all 31, computed values of f_3(n) to superseeker; and received the following replies (fixed spacing) ---
<< Superseeker finds ... 2 3 [-27 + 27 a(n) - 9 a(n) + a(n) , lgdegf]
2 3 4 5 [-243 + 405 a(n) - 270 a(n) + 90 a(n) - 15 a(n) + a(n) , lgdegf]
where "lgdegf" stands for "logarithmic derivative of exponential generating function" The polynomials are simply (a(n) - 3)^3 and (a(n) - 3)^5 respectively.
It's possibly that superseeker has discovered something relatively important here --- unfortunately, I have no idea what that might be, can find no assistance in the documentation, and have failed to put any construction on the phrase which stands up to numerical confirmation.
Can somebody please enlighten me? Fred Lunnon
On 8/21/10, N. J. A. Sloane <njas@research.att.com> wrote:
Yes, I am on the math-fun mailing list!
The lgdegf search does refer to log deriv of a generating function
If you go to the foot of any OEIS page, and click on Superseeker, you will see more about what Superseeker does, including all the source code
It uses the Maple gfun package to search for generating functions. See for example pictor.math.uqam.ca/~plouffe/articles/gfun.pdf
Neil
participants (4)
-
Allan Wechsler -
Fred lunnon -
Joerg Arndt -
Joshua Zucker