Hypercubic billiard word: Difference between revisions

(186 intermediate revisions by 5 users not shown)

Line 1:

~~#redirect~~ [[~~Rank~~-~~3_scale_theorems#Definition~~:~~_Billiard_scale~~]]

'''Hypercubic billiard words''', '''cutting sequences''', or '''cutting words'''<ref name="vuillon">Vuillon, L. (2003). Balanced words. Bulletin of the Belgian Mathematical Society-Simon Stevin, 10(5), 787-805.</ref> can be visualized by considering a point particle (a "billiard ball") bouncing off walls in a closed cubic room. The ratio between the numbers of the step sizes (associated with the direction of the billiard ball) may be rational (resulting in a periodic scale) or irrational (resulting in an aperiodic scale).

Regarded as scales, they are called '''billiard scales''', which are one possible generalization of [[MOS]] scales to [[arity|larger alphabets]].

In the binary case with irrational slope, billiard scales correspond to '''Sturmian words''', which are aperiodic "MOS" (i.e. [[strict variety]] 2) scales.

== Mathematical overview ==

In the periodic case, let ''w'' be a word representing a periodic scale with signature ''a''1'''X'''1 ... ''a''''d''{{nbhsp}}'''X'''''d'' (i.e. ''w'' is a scale word with ''a''''i''-many '''X'''''i'' steps) and let {{nowrap|'''a''' {{=}} (''a''1, ..., ''a''''d'')}}, which we call the ''velocity''.

We call ''w'' a '''rank-'''''d'' '''billiard scale''' if there exists a vector {{nowrap|'''b''' ∈ ℝ''d''}} such that the line {{nowrap|'''a'''''t'' + '''b'''}} has intersections with coordinate level planes {{nowrap|''x''''i'' {{=}} ''k'' ∈ ℤ}} that spell out the scale as you move in the positive ''t'' direction along that line.

This definition is equivalent to the definition given in terms of a billiard ball in a cubic room: We first fire off the billiard ball in the velocity {{nowrap|'''a''' {{=}} (''a''1, ..., ''a''''d'')}} given by the scale signature. For integer ''a''''i'', the particle's trajectory will be periodic, and for almost any starting point, the particle will only collide with one wall at a time. The pattern of which walls the particle collides with then spells out a billiard scale of the given signature, though for [[arity]] higher than 2, this can yield rotationally inequivalent scales depending on the starting point.

Identifying opposite sides of the cubic room, thereby producing a ''d''-torus, yields an equivalent and at times more compelling visualization: now the particle always travels with velocity '''a''', and every time a boundary is crossed and the corresponding scale step recorded, the particle reappears on the other side instead of bouncing. Considering the lines parallel to '''a''' that do not yield a billiard scale — namely those that have a point that has multiple integer coordinates — subdivides the ''d''-torus into finitely many regions each of which gives rise to a billiard scale.

== Properties ==

Proofs to be added

* A (circular) scale word is a rank-2 billiard scale iff it is a MOS scale.

* All [[distributionally even]] scales on any finite number of letters are billiard scales<ref name="sano"/>. The converse fails, because not all billiard scales are Fokker blocks (DE implies the scale is a Fokker block); [[blackdye]] can be checked to be a billiard scale by using the initial position <math>\left(1, \frac{1}{\sqrt{5}}, \frac{1}{\sqrt{3}}\right)</math>, but it is not a Fokker block.

* A billiard scale becomes a billiard scale over fewer letters when one removes all instances of some subset of its step sizes. In particular, ternary billiard scales are ''deletion-MOS'' (DMOS): deleting any step size results in a MOS. However, the converse is false.

** That’s because projecting we just remove some of the αs from the list, leaving all remaining ones intact.

* Not all billiard words over more than 2 letters are [[balance|balanced]]. (In binary scales, the term "balanced" becomes one characterization of the [[MOS]] property.) Ternary billiard scales that are 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>

* Balanced ternary billiard scales with odd length are pairwise well-formed and have a well-formed [[generator sequence]] of two terms; see [[Ternary scale theorems]].

* There exist ternary billiard scales of length up to 29 that do not have a well-formed [[generator sequence]].

* A ''d''-ary billiard scale is {{nowrap|(''d'' − 1)}}-[[balance|block balanced]] and {{nowrap|(''d'' − 1)}}-[[balance|chain balanced]].<ref name="vuillon"/><ref name="sano">Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> However, scales on at least 3 letters satisfying the block balance bound need not be billiard scales.

* An aperiodic ''d''-ary billiard scale has maximum variety at most 2''d'' − 1.<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>

* If a ternary billiard scale has a well-formed generator sequence, the WFGS must use either two or three distinct generators, since ternary billiard scales are MV3 or MV4.

* A ''d''-ary billiard scale satisfies the two generalizations of balance listed on the article [[balanced word]].

== Determining whether a scale word is a billiard scale ==

The following discussion documents a naive algorithm for answering whether a circular word ''s'' over ''d'' letters with step signature ''a''1''x''1...''a''''d''''x''''d'' is a billiard word with velocity <math>\mathbf{a} = \sum_{i}a_{i}\mathbf{e}_{i} \in \mathbb{Z}^{d}</math>:

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

<math>H(m_i, n_j) = \operatorname{span}(\mathbf{a}, \mathbf{e}_1, ..., \hat{\mathbf{e}}_i, ..., \hat{\mathbf{e}}_j, ..., \mathbf{e}_r) + (m_i \mathbf{e}_i + n_j \mathbf{e}_j),</math>

where the circumflexes indicate that the ''i''th and ''j''th basis vectors are to be omitted. In particular, ''L'' and ''H''(''m''''i'', ''n''''j'') are disjoint for any {{nowrap|''i'' < ''j''}}, any {{nowrap|''m''''i'' ∈ {{(}}0, ..., ''a''''i'' − 1{{)}}}}, and any {{nowrap|''n''''j'' ∈ {{(}}0, ..., ''b''''j'' − 1{{)}}}}.

Now, using the identifications {{nowrap|'''e'''''i'' {{=}} 0}} for {{nowrap|''i'' ∈ {{(}}1, ..., ''d''{{)}}}} on ''P'' results in a smaller ''d''-torus ''C'' whose fundamental domain in ℝ''d'' is the unit cube <math>\overline{C} = \prod^{d}_{i = 1}[0, 1]</math>. The path ''L'' descends to {{nowrap|''L'' : ℝ → ''C''}} which is still periodic with period 1. The constraint hyperplanes also descend to ''C''. Now unwrap ''C'' into ''{{overline|C}}'', and regard ''L'' as a subset of ''{{overline|C}}'' that is partitioned into disjoint line segments that travel from one facet (i.e. a {{nowrap|(''d'' − 1)}}-dimensional face) of ''{{overline|C}}'' to another. The reader is warned that to find (the images of) all of the constraint hyperplanes in ''{{overline|C}}'', any constraint hyperplane that does not meet ''{{overline|C}}'' should be shifted by integer increments in coordinates so that the shifted hyperplane does meet ''{{overline|C}}''. The constraint hyperplanes partition ''{{overline|C}}'' into finitely many regions (as they do for ''P''), and any valid billiard path ''L'' in ''{{overline|C}}'' must meet len(''s'')-many of these regions before returning to its starting point.

Now we use the projection π, a linear map on ℝ''d'' whose kernel is generated by '''a''', to project ''{{overline|C}}'' to a {{nowrap|(''d'' − 1)}}-dimensional convex polytope π(''{{overline|C}}''). The constraint hyperplanes now become {{nowrap|(''d'' − 2)}}-dimensional hyperplanes that partition π(''{{overline|C}}'') into finitely many convex regions. The components of ''L'' now become points in π(''{{overline|C}}''), and each region in the partition has at most one point of π(''L''). When ''L'' hits an integer coordinate hyperplane {{nowrap|''x''''i'' {{=}} (some integer)}}, the corresponding point in π(''L'') now shifts by −π('''e'''''i''), since the corresponding point in ''{{overline|C}}'' must undergo a shift by −'''e'''''i'' upon ''L'' hitting the coordinate hyperplane. Since ''L'' hits len(''s'') coordinate hyperplanes before returning to its starting region, we choose some region with a point of π(''L'') in it and advance the point len(''s'') times, each point in the orbit corresponding to the coordinate of the hyperplane hit by ''L''. To find all billiard scales with signature '''a''', we simply iterate the procedure described in the previous sentence over all regions (all of which are convex polytopes) in the partition we obtained in π(''{{overline|C}}''); we may choose the centroid of the region as the starting point of π(''L'').

The preceding method is redundant in that for chiral scales, one need not generate both chiralities manually using this method. This fact is realized via the symmetry of the coordinate planes under reflection about the orthogonal complement of '''a''', which reverses the orientation of the billiard trajectory.

== Open questions ==

* Does the generating function for ternary deletion-MOS necklaces admit an elegant expression? What about billiard scales over a given number of letters?

* Is there a more clever algorithm for checking whether a scale on more than 2 letters is a billiard scale?

== See also ==

* List of [[ternary billiard words of length at most 31]]

* [[Code for billiard scales]]

== Bibliography ==

[[Category:Scale]]

[[Category:Combinatorics on words]]

[[Category:Math]]

[[Category:Pages with open problems]]

@@ Line 1: / Line 1: @@
-#redirect [[Rank-3_scale_theorems#Definition:_Billiard_scale]]
+'''Hypercubic billiard words''', '''cutting sequences''', or '''cutting words'''<ref name="vuillon">Vuillon, L. (2003). Balanced words. Bulletin of the Belgian Mathematical Society-Simon Stevin, 10(5), 787-805.</ref> can be visualized by considering a point particle (a "billiard ball") bouncing off walls in a closed cubic room. The ratio between the numbers of the step sizes (associated with the direction of the billiard ball) may be rational (resulting in a periodic scale) or irrational (resulting in an aperiodic scale).
+Regarded as scales, they are called '''billiard scales''', which are one possible generalization of [[MOS]] scales to [[arity|larger alphabets]].
+In the binary case with irrational slope, billiard scales correspond to '''Sturmian words''', which are aperiodic "MOS" (i.e. [[strict variety]] 2) scales.
+== Mathematical overview ==
+In the periodic case, let ''w'' be a word representing a periodic scale with signature ''a''<sub>1</sub>'''X'''<sub>1</sub> ... ''a''<sub>''d''{{nbhsp}}</sub>'''X'''<sub>''d''</sub> (i.e. ''w'' is a scale word with ''a''<sub>''i''</sub>-many '''X'''<sub>''i''</sub> steps) and let {{nowrap|'''a''' {{=}} (''a''<sub>1</sub>, ..., ''a''<sub>''d''</sub>)}}, which we call the ''velocity''.
+We call ''w'' a '''rank-'''''d'' '''billiard scale''' if there exists a vector {{nowrap|'''b''' ∈ ℝ<sup>''d''</sup>}} such that the line {{nowrap|'''a'''''t'' + '''b'''}} has intersections with coordinate level planes {{nowrap|''x''<sub>''i''</sub> {{=}} ''k'' ∈ ℤ}} that spell out the scale as you move in the positive ''t'' direction along that line.
+This definition is equivalent to the definition given in terms of a billiard ball in a cubic room: We first fire off the billiard ball in the velocity {{nowrap|'''a''' {{=}} (''a''<sub>1</sub>, ..., ''a''<sub>''d''</sub>)}} given by the scale signature. For integer ''a''<sub>''i''</sub>, the particle's trajectory will be periodic, and for almost any starting point, the particle will only collide with one wall at a time. The pattern of which walls the particle collides with then spells out a billiard scale of the given signature, though for [[arity]] higher than 2, this can yield rotationally inequivalent scales depending on the starting point.
+Identifying opposite sides of the cubic room, thereby producing a ''d''-torus, yields an equivalent and at times more compelling visualization: now the particle always travels with velocity '''a''', and every time a boundary is crossed and the corresponding scale step recorded, the particle reappears on the other side instead of bouncing. Considering the lines parallel to '''a''' that do not yield a billiard scale &mdash; namely those that have a point that has multiple integer coordinates &mdash; subdivides the ''d''-torus into finitely many regions each of which gives rise to a billiard scale.
+== Properties ==
+Proofs to be added
+* A (circular) scale word is a rank-2 billiard scale iff it is a MOS scale.
+* All [[distributionally even]] scales on any finite number of letters are billiard scales<ref name="sano"/>. The converse fails, because not all billiard scales are Fokker blocks (DE implies the scale is a Fokker block); [[blackdye]] can be checked to be a billiard scale by using the initial position <math>\left(1, \frac{1}{\sqrt{5}}, \frac{1}{\sqrt{3}}\right)</math>, but it is not a Fokker block.
+* A billiard scale becomes a billiard scale over fewer letters when one removes all instances of some subset of its step sizes. In particular, ternary billiard scales are ''deletion-MOS'' (DMOS): deleting any step size results in a MOS. However, the converse is false.
+** That’s because projecting we just remove some of the αs from the list, leaving all remaining ones intact.
+* Not all billiard words over more than 2 letters are [[balance|balanced]]. (In binary scales, the term "balanced" becomes one characterization of the [[MOS]] property.) Ternary billiard scales that are 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>
+* Balanced ternary billiard scales with odd length are pairwise well-formed and have a well-formed [[generator sequence]] of two terms; see [[Ternary scale theorems]].
+* There exist ternary billiard scales of length up to 29 that do not have a well-formed [[generator sequence]].
+* A ''d''-ary billiard scale is {{nowrap|(''d'' &minus; 1)}}-[[balance|block balanced]] and {{nowrap|(''d'' &minus; 1)}}-[[balance|chain balanced]].<ref name="vuillon"/><ref name="sano">Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> However, scales on at least 3 letters satisfying the block balance bound need not be billiard scales.
+* An aperiodic ''d''-ary billiard scale has maximum variety at most 2<sup style="white-space: nowrap;">''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>
+* If a ternary billiard scale has a well-formed generator sequence, the WFGS must use either two or three distinct generators, since ternary billiard scales are MV3 or MV4.
+* A ''d''-ary billiard scale satisfies the two generalizations of balance listed on the article [[balanced word]].
+== Determining whether a scale word is a billiard scale ==
+The following discussion documents a naive algorithm for answering whether a circular word ''s'' over ''d'' letters with step signature ''a''<sub>1</sub>''x''<sub>1</sub>...''a''<sub>''d''</sub>''x''<sub>''d''</sub> is a billiard word with velocity <math>\mathbf{a} = \sum_{i}a_{i}\mathbf{e}_{i} \in \mathbb{Z}^{d}</math>:
+Consider the ''d''-dimensional prism <math>P = \prod^{d}_{i = 1}\left[0, a_{i}\right].</math> Since the pattern in which the billiard line {{nowrap|''L'' {{=}} ''L''(''t'')}} {{nowrap|{{=}} '''a'''''t'' + ''b''}} hits integer coordinate hyperplanes (i.e. sets {{nowrap|''x''<sub>''i''</sub> {{=}} ''n''}} for {{nowrap|''n'' ∈ ℤ}}) is periodic with period 1 in ''t'', we may first regard ''P'' as a ''d''-torus and {{nowrap|''L'' : ℝ → ''P''}} as a periodic function with period 1.  Because ''s'' is a billiard word, ''L cannot'' meet any point {{nowrap|'''q''' {{=}} (''q''<sub>1</sub>, ..., ''q''<sub>''d''</sub>)}} ∈&nbsp;ℝ<sup>''d''</sup> where two coordinates, ''q''<sub>''i''</sub> and ''q''<sub>''j''</sub>, {{nowrap|''i'' &lt; ''j''}}, are integers. Thus for two distinct integers {{nowrap|''i'' &lt; ''j''}} in {1, ..., ''d''}, any choice of two integers {{nowrap|''m''<sub>''i''</sub> ∈ {{(}}0, ..., ''a''<sub>''i''</sub>{{)}}}} and {{nowrap|''n''<sub>''j''</sub> ∈ {{(}}0, ..., ''b''<sub>''j''</sub>{{)}}}} corresponds to the affine hyperplane (which we call a ''constraint hyperplane'')
+<math>H(m_i, n_j) = \operatorname{span}(\mathbf{a}, \mathbf{e}_1, ..., \hat{\mathbf{e}}_i, ..., \hat{\mathbf{e}}_j, ..., \mathbf{e}_r) + (m_i \mathbf{e}_i + n_j \mathbf{e}_j),</math>
+where the circumflexes indicate that the ''i''th and ''j''th basis vectors are to be omitted. In particular, ''L'' and ''H''(''m''<sub>''i''</sub>,&nbsp;''n''<sub>''j''</sub>) are disjoint for any {{nowrap|''i'' &lt; ''j''}}, any {{nowrap|''m''<sub>''i''</sub> ∈ {{(}}0, ..., ''a''<sub>''i''</sub> &minus; 1{{)}}}}, and any {{nowrap|''n''<sub>''j''</sub> ∈ {{(}}0, ..., ''b''<sub>''j''</sub> &minus; 1{{)}}}}.
+Now, using the identifications {{nowrap|'''e'''<sub>''i''</sub> {{=}} 0}} for {{nowrap|''i'' ∈ {{(}}1, ..., ''d''{{)}}}} on ''P'' results in a smaller ''d''-torus ''C'' whose fundamental domain in ℝ<sup>''d''</sup> is the unit cube <math>\overline{C} = \prod^{d}_{i = 1}[0, 1]</math>. The path ''L'' descends to {{nowrap|''L'' : ℝ → ''C''}} which is still periodic with period 1. The constraint hyperplanes also descend to ''C''. Now unwrap ''C'' into ''{{overline|C}}'', and regard ''L'' as a subset of ''{{overline|C}}'' that is partitioned into disjoint line segments that travel from one facet (i.e. a {{nowrap|(''d'' &minus; 1)}}-dimensional face) of ''{{overline|C}}'' to another. The reader is warned that to find (the images of) all of the constraint hyperplanes in ''{{overline|C}}'', any constraint hyperplane that does not meet ''{{overline|C}}'' should be shifted by integer increments in coordinates so that the shifted hyperplane does meet ''{{overline|C}}''. The constraint hyperplanes partition ''{{overline|C}}'' into finitely many regions (as they do for ''P''), and any valid billiard path ''L'' in ''{{overline|C}}'' must meet len(''s'')-many of these regions before returning to its starting point.
+Now we use the projection π, a linear map on ℝ<sup>''d''</sup> whose kernel is generated by '''a''', to project ''{{overline|C}}'' to a {{nowrap|(''d'' &minus; 1)}}-dimensional convex polytope π(''{{overline|C}}''). The constraint hyperplanes now become {{nowrap|(''d'' &minus; 2)}}-dimensional hyperplanes that partition π(''{{overline|C}}'') into finitely many convex regions. The components of ''L'' now become points in π(''{{overline|C}}''), and each region in the partition has at most one point of π(''L''). When ''L'' hits an integer coordinate hyperplane {{nowrap|''x''<sub>''i''</sub> {{=}} (some integer)}}, the corresponding point in π(''L'') now shifts by &minus;π('''e'''<sub>''i''</sub>), since the corresponding point in ''{{overline|C}}'' must undergo a shift by &minus;'''e'''<sub>''i''</sub> upon ''L'' hitting the coordinate hyperplane. Since ''L'' hits len(''s'') coordinate hyperplanes before returning to its starting region, we choose some region with a point of π(''L'') in it and advance the point len(''s'') times, each point in the orbit corresponding to the coordinate of the hyperplane hit by ''L''. To find all billiard scales with signature '''a''', we simply iterate the procedure described in the previous sentence over all regions (all of which are convex polytopes) in the partition we obtained in π(''{{overline|C}}''); we may choose the centroid of the region as the starting point of π(''L'').
+The preceding method is redundant in that for chiral scales, one need not generate both chiralities manually using this method. This fact is realized via the symmetry of the coordinate planes under reflection about the orthogonal complement of '''a''', which reverses the orientation of the billiard trajectory.
+== Open questions ==
+* Does the generating function for ternary deletion-MOS necklaces admit an elegant expression? What about billiard scales over a given number of letters?
+* Is there a more clever algorithm for checking whether a scale on more than 2 letters is a billiard scale?
+== See also ==
+* List of [[ternary billiard words of length at most 31]]
+* [[Code for billiard scales]]
+== Bibliography ==
+<references />
+[[Category:Scale]]
+[[Category:Combinatorics on words]]
+[[Category:Math]]
+[[Category:Pages with open problems]]