Hypercubic billiard word: Difference between revisions

Inthar (talk | contribs)
Inthar (talk | contribs)
Line 17: Line 17:
* A (circular) scale word is a rank-2 billiard scale iff it is a MOS scale.
* A (circular) scale word is a rank-2 billiard scale iff it is a MOS scale.
* Not all billiard scales are Fokker blocks; [[blackdye]] can be checked to be a billiard scale by using the initial position (1, 1/√5, 1/√3), but it is not a Fokker block.
* Not all billiard scales are Fokker blocks; [[blackdye]] can be checked to be a billiard scale by using the initial position (1, 1/√5, 1/√3), but it is not a Fokker block.
* A billiard scale becomes a billiard scale of lower rank when one removes all instances of some subset of its step sizes. However, the converse is false.
* A billiard scale becomes a billiard scale over fewer letters when one removes all instances of some subset of its step sizes. However, the converse is false.
** That’s because projecting we just remove some of the αs from the list, leaving all remaining ones intact.
** That’s because projecting we just remove some of the αs from the list, leaving all remaining ones intact.
* Not all billiard words of arity higher than 2 are [[balance|balanced]]. (In binary scales, the term "(1-)balanced" becomes one characterization of the [[MOS]] property.) Ternary billiard scales that are 1-balanced are [[MV3]].<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref>
* Not all billiard words over more than 2 letters are [[balance|balanced]]. (In binary scales, the term "(1-)balanced" becomes one characterization of the [[MOS]] property.) Ternary billiard scales that are 1-balanced are [[MV3]].<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref>
* There exist ternary billiard scales of length up to 29 that do not have a well-formed [[generator sequence]].
* There exist ternary billiard scales of length up to 29 that do not have a well-formed [[generator sequence]].
* A ''d''-ary billiard scale has [[balance]] at most (''d'' &minus; 1).<ref name="vuillon"/> However, scales of arity &ge; 3 satisfying this bound need not be billiard scales.
* A ''d''-ary billiard scale has [[balance]] at most (''d'' &minus; 1).<ref name="vuillon"/> However, scales on at least 3 letters satisfying this bound need not be billiard scales.
* An aperiodic ''d''-ary billiard scale has maximum variety at most 2<sup>''d''&minus;1</sup>.<ref name="andrieu">Mélodie Andrieu, Léo Vivion. Minimal Complexities for Infinite Words Written with d Letters. Combinatorics on Words - 14th International Conference, WORDS, Jun 2023, Umeå, Sweden. pp.3–13.</ref> Hence this bound must hold for periodic ''d''-ary billiard scales as well.
* An aperiodic ''d''-ary billiard scale has maximum variety at most 2<sup>''d''&minus;1</sup>.<ref name="andrieu">Mélodie Andrieu, Léo Vivion. Minimal Complexities for Infinite Words Written with d Letters. Combinatorics on Words - 14th International Conference, WORDS, Jun 2023, Umeå, Sweden. pp.3–13.</ref> Hence this bound must hold for periodic ''d''-ary billiard scales as well.


=== Determining whether a scale word is a billiard scale ===
=== Determining whether a scale word is a billiard scale ===
The following discussion documents a naive algorithm for answering whether a circular word ''s'' of arity ''d'' with velocity '''a''' = ∑<sub>''i''</sub> ''a''<sub>''i''</sub> '''e'''<sub>''i''</sub> ∈ ℤ<sup>''d''</sup> (representing the signature ''a''<sub>1</sub>''x''<sub>1</sub>...''a''<sub>''d''</sub>''x''<sub>''d''</sub>) is a billiard word:
The following discussion documents a naive algorithm for answering whether a circular word ''s'' over ''d'' letters with velocity '''a''' = ∑<sub>''i''</sub> ''a''<sub>''i''</sub> '''e'''<sub>''i''</sub> ∈ ℤ<sup>''d''</sup> (representing the signature ''a''<sub>1</sub>''x''<sub>1</sub>...''a''<sub>''d''</sub>''x''<sub>''d''</sub>) is a billiard word:


Consider the ''d''-dimensional prism ''P'' = ∏<sup>''d''</sup><sub>''i''=1</sub> [0, ''a''<sub>''i''</sub>]. Since the pattern in which the billiard line ''L'' = ''L''(''t'') = '''a'''''t'' + ''b'' hits integer coordinate hyperplanes (i.e. sets ''x''<sub>''i''</sub> = ''n'' for ''n'' ∈ ℤ) is periodic with period 1 in ''t'', we may first regard ''P'' as a ''d''-torus and ''L'' : ℝ → ''P'' as a periodic function with period 1.  Because ''s'' is a billiard word, ''L'' ''cannot'' meet any point '''q''' = (''q''<sub>1</sub>, ..., ''q''<sub>''d''</sub>) ∈ ℝ<sup>''d''</sup> where two coordinates, ''q''<sub>''i''</sub> and ''q''<sub>''j''</sub>, ''i'' < ''j'', are integers. Thus for two distinct integers ''i'' < ''j'' in {1, ..., ''d''}, any choice of two integers ''m''<sub>''i''</sub> ∈ {0, ..., ''a''<sub>''i''</sub>} and ''n''<sub>''j''</sub> ∈ {0, ..., ''b''<sub>''j''</sub>} corresponds to the affine hyperplane (which we call a ''constraint hyperplane'')
Consider the ''d''-dimensional prism ''P'' = ∏<sup>''d''</sup><sub>''i''=1</sub> [0, ''a''<sub>''i''</sub>]. Since the pattern in which the billiard line ''L'' = ''L''(''t'') = '''a'''''t'' + ''b'' hits integer coordinate hyperplanes (i.e. sets ''x''<sub>''i''</sub> = ''n'' for ''n'' ∈ ℤ) is periodic with period 1 in ''t'', we may first regard ''P'' as a ''d''-torus and ''L'' : ℝ → ''P'' as a periodic function with period 1.  Because ''s'' is a billiard word, ''L'' ''cannot'' meet any point '''q''' = (''q''<sub>1</sub>, ..., ''q''<sub>''d''</sub>) ∈ ℝ<sup>''d''</sup> where two coordinates, ''q''<sub>''i''</sub> and ''q''<sub>''j''</sub>, ''i'' < ''j'', are integers. Thus for two distinct integers ''i'' < ''j'' in {1, ..., ''d''}, any choice of two integers ''m''<sub>''i''</sub> ∈ {0, ..., ''a''<sub>''i''</sub>} and ''n''<sub>''j''</sub> ∈ {0, ..., ''b''<sub>''j''</sub>} corresponds to the affine hyperplane (which we call a ''constraint hyperplane'')