# Testing MediaPipe Holistic for Linguistic Analysis
of Nonmanual Markers in Sign Languages

###### Abstract

Advances in Deep Learning have made possible reliable landmark tracking of
human bodies and faces that can be used for a variety of tasks. We test a
recent Computer Vision solution, MediaPipe Holistic (MPH), to find out if its
tracking of the facial features is reliable enough for a linguistic analysis
of data from sign languages, and compare it to an older solution (OpenFace,
OF). We use an existing data set of sentences in Kazakh-Russian Sign Language
and a newly created small data set of videos with head tilts and eyebrow
movements. We find that MPH does not perform well enough for linguistic
analysis of eyebrow movement – but in a different way from OF, which is also
performing poorly without correction. We reiterate a previous proposal to
train additional correction models to overcome these limitations.

Keywords: nonmanual markers, MediaPipe Holistic, OpenFace

Testing MediaPipe Holistic for Linguistic Analysis
of Nonmanual Markers in Sign Languages

Anna Kuznetsova1, Vadim Kimmelman2
---
1University of Trento, 2University of Bergen
1Amsterdam, Netherlands, 2Bergen, Norway
<EMAIL_ADDRESS><EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

Recent advances in Deep Learning have substantially improved the quality of
Computer Vision (CV) solutions, making possible reliable tracking of human
bodies and faces in video recordings and video stream. One popular CV package,
OpenPose (Cao et al., 2018), has been used in a large variety of applications
including Automatic Sign Language Recognition, Translation and Generation
(SLRTG) (Adeyanju et al., 2021). Another package, OpenFace (Baltrusaitis et
al., 2018; Zadeh et al., 2017), was created as an extension of OpenPose with
the task of emotion recognition; it has the additional functionality of
tracking the head rotation (along the three axes) and 3D reconstruction of the
head model from 2D video data. More recently, another solution has been
published, namely MediaPipe (Lugaresi et al., 2019), including MediaPipe
Holistic which tracks the body, the hands, and a large number of facial
landmarks in 2D video data.

It is clear that CV solutions can be used for research purposes, including in
linguistics, and especially in the fields of gesture studies and sign language
linguistics (Börstell, 2023; Trujillo et al., 2019). CV solutions have been
used most frequently and successfully for the tasks of SLRTG (Morgan et al.,
2022).

Additionally, since it is now possible to automatically track the body, hands,
and faces of signers and gesturers, researchers can use these tools to perform
measurements of the motion and position of the subjects in video recordings
(Börstell, 2023; Trujillo et al., 2019). This has the potential to solve
several important practical problems: 1) Automatic tracking is much less time
consuming than manual annotation and 2) Automatic tracking can be more
reliable than manual annotation. However, this potential is somewhat
hypothetical. It is not clear whether the CV solutions are reliable/precise
enough to enable linguistic analysis.

This is especially pertinent for the issue of analyzing facial expressions
which play an important role in sign language production and comprehension
(Pfau and Quer, 2010) but are produced by small articulators (e.g. eyebrows)
which can be difficult to track precisely (Kimmelman et al., 2020).

In this paper, we specifically test MediaPipe Holistic (MPH) and compare it
with OpenFace (OF) for the task of tracking eyebrow position in sign language
recordings. Our previous research (Kuznetsova et al., 2021, 2022) has shown
that OF can be used to analyze eyebrow position and head tilt used to mark
questions in a sign language; however, it was only possible to use OF after
training an additional correction model to counteract distortions introduced
by head tilts. In this study, we use the same data set to see if MPH, being a
more recent solution developed by a large company, still suffers from the same
distortions. We also record an additional small data set to specifically test
the effects of head tilts on eyebrow position estimation.

## 2\. Methods

We analyzed two data sets: a data set of utterances in Kazakh-Russian Sign
Language (KRSL) produced by 9 signers (Kuznetsova et al., 2021), which is a
part of the K-RSL dataset Imashev et al. (2020), and a newly recorded data set
of head tilts and eyebrow raises produced by a single subject, both analyzed
with OF and MPH.

### 2.1. Data Set 1: KRSL

The KRSL data set contains video recordings of 9 signers of KRSL producing 10
sentences in three conditions (as a statement, a polar question, and a content
question). In a previous study (Kuznetsova et al., 2021), we analyzed this
data set with OpenFace and found out that polar questions are accompanied by
eyebrow raise on the whole sentence and two downward head movements, content
questions are marked with backward head tilt and eyebrow raise on the question
sign, and statements are unmarked. This is similar to how questions are marked
in some other sign languages, see Cecchetto (2012).

Another important finding, however, was that OF 3D reconstruction does not
actually work for the purposes of linguistic analysis of the data directly.
Specifically, we observed that the eyebrow position relative to the eye was
strongly affected by the head tilt (Figure 1). This led to a distortion of the
eyebrow position assessment which almost fully obfuscated the pattern
described above.

Figure 1: Head models based on OF outputs demonstrating distortion due to head
pitch.

We proposed a solution which, briefly, consisted of training a model using
manually selected sentences without eyebrow movement which would predict
eyebrow position based on head rotation. This model thus predicts the
distortion of the eyebrow position due to head tilts. When applied to
sentences with eyebrow movement this model corrects for this distortion. The
resulting assessment of the eyebrow position is in agreement with the actual
data. Figure 2 in Section 3 shows the corrected and uncorrected outputs of OF.

For the current study, we simply applied MPH to the same data set and analyzed
the outputs for the same sentence types. Since MPH’s face model has a much
larger number of landmarks, a direct comparison is not possible. However, it
is possible to compare the results using either single landmarks or by
averaging over multiple landmarks in the MPH outputs.

### 2.2. Data Set 2: Head and Eyebrow Movements

As we discuss below, the MPH analysis of the KRSL data set looked promising as
it showed the differences between sentence types in general agreement with the
corrected results from OF. This indicated that MPH did not suffer from
distortions in the context of head tilts. We decided to further test this
directly by recording videos with and without eyebrow raise and different head
movements.

Specifically, we recorded a single person producing head pitches (up and down)
with raised and with neutral eyebrow position.111We also recorded head yaws
and rolls with neutral eyebrow position, and head pitches with variable
eyebrow position. However, we do not further analyse these files in this
report. We applied MPH (to assess eyebrow location) and OF (to assess eyebrow
location and head pitch) to this data set.

### 2.3. Data Preparation and Analysis

In order to assess the effect of head tilts on eyebrow raise, we used the
following methods. For the KRSL data set, we simply reconstructed the eyebrow
movement patterns to replicate the findings from the previous study and
graphically compared the results. The eyebrow distance was calculated using
inner and outer eyebrow points and two inner points of the eyes – we drew a
line through the eye points and calculated the distance from eyebrow points to
this line.

For the new data set, first, we calculated the standard deviation of the mean
eyebrow distance (separately for inner and outer eyebrow landmarks) by
comparing each measure of distance to the distance in the initial frame of the
recording with no tilt. If the solution works perfectly, then the distance
with and without tilts should be the same, and the deviation should be
minimal. For comparison of different camera distances (close, middle, far) we
scaled the eyebrow distances and rotation angles between 0 and 1 in each
camera distance group. To test whether the differences are statistically
significant, we conducted t-tests to compare the deviation in each video
(separately for inner and outer eyebrow points) to zero, and to compare the OF
and MPH deviations to each other.

Second, we explored the data graphically in two ways. (1) We created
visualizations of the distortions introduced by different types of head tilts
by visualizing the model of the eyebrows, eyes and nose in 3D space at three
different time points (first frame, middle of the head pitch, peak of the head
pitch). The face models were rotated to the neutral position by reverting the
head rotation angles and centred around the upper nose point. (2) We created
visualizations of the scaled eyebrow distance measures for the different video
recordings in order to compare the videos with and without eyebrow raise in
the context of the pitches upward and downward.

Data preparation, analysis and visualization were conducted in Python and R (R
Core Team, 2022; Wickham et al., 2019). The video and data files and scripts
to reproduce the results, as well as the full set of visualizations, can be
found here.

## 3\. Results

### 3.1. KRSL

The results of applying MPH to the KRSL data set can be seen in Figure 2. The
top panel shows the results of MPH application to the data. It is clear that
it more closely resembles the results of OF with a correction model (middle
panel) than OF without correction (lower panel). Specifically, the MPH outputs
also clearly show eyebrow raise on the question sign in content questions, and
eyebrow raise on the whole sentence in polar questions. Note however some
issues: (1) the differences between sentence types are diminished in
comparison to the middle panel, (2) there is a strong difference between inner
and outer eyebrow distances.

Figure 2: Eyebrow marking for different types of sentences in the KRSL data
set. Top panel: MPH. Middle panel: OF corrected. Lower panel: OF non-
corrected. Colors represent sentence types (orange: polar question, green:
content question, purple: statement). N: noun, V: verb. Left column: inner
eyebrow distance, right column: outer eyebrow distance. X-axis is frame number
normalized to 70.

Despite the differences between MPH and OF corrected, since the overall
pattern is similar, the application of MPH looks promising. If it were
possible to use MPH to directly measure eyebrow position, also in the presence
of head tilts, without additional correction, this would be a very practical
solution for sign language linguistics. However, we decided to further test
whether head tilts introduce distortion in eyebrow position estimation
directly in the new data set.

### 3.2. Head and Eyebrow Movements

#### 3.2.1. Deviations Due to Head Movement

As described in Section 2, we used video recordings of a single subject
performing head movements with and without eyebrow raise, filmed from three
different distances. We analyzed these videos with OF to estimate eyebrow
position and head tilt, and with MPH to estimate eyebrow position.

We analyzed the estimated eyebrow distance in videos without eyebrow raise by
comparing the eyebrow distance throughout the video with the eyebrow distance
in the initial part which contained no head rotation. We calculated average
deviation for inner eyebrow points and outer eyebrow points in MPH and OF, see
the results in Table 1.

Type | MPH inner | OF inner | MPH outer | OF outer
---|---|---|---|---
close pitch down | 0.103 | 0.079 | 0.19 | 0.066
close pitch up | 0.117 | 0.224 | 0.097 | 0.265
far pitch down | 0.1 | 0.053 | 0.098 | 0.054
far pitch up | 0.109 | 0.2 | 0.08 | 0.209
middle pitch down | 0.097 | 0.062 | 0.161 | 0.054
middle pitch up | 0.096 | 0.211 | 0.064 | 0.26
Table 1: Deviation of eyebrow distance, no eyebrow raise, with different head
pitches at different distances, with OF and MPH. The higher deviation between
in pairwise comparison of MPH to OF is in red. The range of possible
deviations is (0,1).

We have conducted t-tests comparing the deviations in each case to each other
(between OF and MPH), and to zero. In each case, the difference is highly
statistically significant. Please see the code in the repository linked above.

This table shows several puzzling patterns. First, it is clear that MPH is
still susceptible to bias in eyebrow position estimation in the presence of
head tilts. Second, while MPH performs considerably better than OF for the
upward head pitch, OF actually outperforms MPH for downward head pitch.
Finally, MPH performs worse for outer eyebrow estimation than for inner
eyebrow estimation, which is not the case for OF.

We also analyzed the videos with eyebrows raised the same way as the videos
with no eyebrow raise. Note that in these videos the eyebrows are raised
throughout and there is no eyebrow movement, while the head is moving. The
results are reported in Table 2. While there are still significant differences
between MPH and OF (and all the deviations are significantly different from
zero), the differences are not the same as in Table 1.

Type | MPH inner | OF inner | MPH outer | OF outer
---|---|---|---|---
close pitch down | 0.146 | 0.079 | 0.211 | 0.178
close pitch up | 0.322 | 0.24 | 0.374 | 0.261
far pitch down | 0.131 | 0.074 | 0.138 | 0.102
far pitch up | 0.268 | 0.096 | 0.201 | 0.097
middle pitch down | 0.118 | 0.098 | 0.097 | 0.13
middle pitch up | 0.273 | 0.128 | 0.244 | 0.145
Table 2: Deviation of eyebrow distance, with eyebrow raise, with different
head pitches at different distances, with OF and MPH. The higher deviation
between in pairwise comparison of MPH to OF is in red. The range of possible
deviations is (0,1).

Here, in all but one case (middle pitch down), the deviations for MPH are much
higher than for OF, so it performs much worse than OF. Note that it is very
surprising to find that the results are different when using the videos with
or without eyebrow movement. It is also surprising to see MPH perform so badly
in this condition. In the next section, we confirm this pattern by visual
inspection.

#### 3.2.2. Visualizing the Deviations

Another way to see that MPH is susceptible to distortion due to head rotation
is to look at visualizations of the head model (only eyebrows, eyes and nose
landmarks included) produced from MPH outputs, see Figure 3. This figure shows
the head visualized in the beginning of a video (no pitch), in the middle of
head movement, and in the peak of the head movement (upper panel: head pitch
up, lower panel: head pitch down).

Figure 3: Head models based on MPH output, for close pitch up and close pitch
down videos. Grey line: no pitch; red line: middle of pitch motion; yellow
line: maximal pitch.

It can be clearly seen that, with upward pitch, the head model is squished
vertically, so the estimation of eyebrow distance is lowered. With downward
pitch, the head model is stretched vertically, and the estimation of eyebrow
distance is raised. This is the opposite pattern of distortion from OF (see
Figure 1 above), but it is still a very clearly present distortion.

Finally, yet another way to see the distortion is to visualize (standardized)
eyebrow distance estimation for videos with and without eyebrow movement and
with upward or downward pitch. Consider Figure 4 which shows inner eyebrow
distance in the close condition. An interesting pattern emerges: with downward
pitch, both raised and non-raised eyebrows are distorted approximately to the
same extent. With upward pitch, however, there is a very strong distortion of
raised eyebrows, but the distortion for non-raised eyebrows is much smaller.

Figure 4: MPH eyebrow distance estimation for inner eyebrows in the close
condition; head pitch up or down; with or without raised eyebrows. The
distance and frame numbers are standardized.

To see that this pattern is not due to differences in head pitch itself,
consider Figure 5 which shows eyebrow distance (as dots) and head pitch (as
lines) in the videos with head pitch up with and without eyebrow movement. It
can seen that, in both videos, the pitch is similar, but it affects the
eyebrow distance estimation differently. The same pattern (the difference
between videos with and without eyebrow raise for head pitch up) can be seen
also at middle and far distances, although the pattern becomes less
pronounced.

Figure 5: MPH eyebrow distance (colored dots) and head pitch (black lines)
estimation for inner eyebrows in the close condition; head pitch up with or
without raised eyebrows. The distances and frame numbers are standardized.

Compare also to Figure 6 showing the OF estimation of eyebrow distance in the
same two videos. The pattern here is completely different. First, there is no
difference between the videos with and without eyebrow raise: both are
distorted to the same extent. Second, the distortion of the eyebrow distance
is in the opposite direction from MPH, as mentioned above.

Figure 6: OF eyebrow distance (colored dots) and head pitch (black lines)
estimation for inner eyebrows in the close condition; head pitch up with or
without raised eyebrows. The distances and frame numbers are standardized.

We conclude that both calculating deviations and graphical exploration
demonstrate that MPH outputs and the measure of eyebrow distance that we
derive from them are substantially distorted in the presence of head pitch.
The distortion is complex and different from OF, but it is still very clearly
present.

Finally, when graphically exploring the videos at middle and far distance, we
also observed that MPH loses many data points with extreme upward head pitch
(see Figure 7). This means that MPH does not reliably track the face in the
presence of such head movements. This is especially relevant given that most
sign language recordings are at a distance comparable to the far case in our
study.

Figure 7: MPH eyebrow distance estimation for inner eyebrows in the middle
condition; head pitch up or down; with or without raised eyebrows. The
distance and frame numbers are standardized.

## 4\. Discussion

The main question of this study is whether MPH can track facial landmarks
reliably enough and without distortions in the reconstructed 3D model so that
its outputs can be used for linguistic analysis of nonmanual markers in sign
languages. The answer to this question is a clear “no”.

We find clear evidence that the 3D model of the head that MPH outputs is
distorted in the presence of head movements (specifically, head pitches). The
distortion is so strong that it completely obscures very pronounced eyebrow
position differences. In Figure 5, we can see for example that, with a head
pitch up, raised eyebrows at the peak of the pitch can be perceived as being
at the same distance as the non-raised eyebrows.

What is even more troubling is that the distortions are not describable by a
simple trend. The distortion introduced by the pitch up movement is clearly
stronger than the one introduced by pitch down. The distortion is also
stronger for outer than inner eyebrows. Finally, the distortion of the pitch
up movement is for some reason much stronger for raised than for non-raised
eyebrows. In this respect, MPH works even worse than uncorrected OF because
the distortions are more complex and thus might be more difficult to correct.

With this result, a puzzle remains: why does the analysis of the KRSL data set
with MPH look better than the uncorrected OF output? We think that this is a
coincidence based on the co-occurrence pattern of the head and eyebrow
movement in this specific data set.

Specifically, for polar questions, the head pitches down while the eyebrows
are raised, and for content questions, the head pitches up while the eyebrows
are raised. For OF, the downward pitch leads to a decrease in eyebrow
distance, and so polar questions with eyebrow raise become indistinguishable
from statements without eyebrow raise. For MPH, the distortion goes in the
opposite direction, as downward pitch leads to an increase in eyebrow
distance, and so in the MPH output polar questions are different from
statements. For pitch up in content questions, the effects are mirrored, and
here we could expect MPH to obscure eyebrow raise, but because MPH is on
average better in the presence of pitch up, the raise on the question sign is
still visible (but mostly for outer eyebrows). In other words, while MPH
happens to output a reasonable picture for the KRSL data set we analyzed, it
is pure coincidence and does not indicate that MPH can be used directly for
other data sets.

Finally, we hope that the procedure of correcting the outputs that we proposed
for OF in our previous work (Kuznetsova et al., 2021, 2022) can also be
applied to the outputs of MPH. However, as discussed above, the distortions
that MPH introduces are more complex and less linear than those in OF, and
thus corrective models might not perform as well. We plan to further test this
in future.

## 5\. Bibliographical References

##

  * Adeyanju et al. (2021) I.A. Adeyanju, O.O. Bello, and M.A. Adegboye. 2021.  Machine learning methods for sign language recognition: A critical review and analysis.  _Intelligent Systems with Applications_ , 12:200056.
  * Baltrusaitis et al. (2018) Tadas Baltrusaitis, Amir Zadeh, Yao Chong Lim, and Louis-Philippe Morency. 2018\.  Openface 2.0: Facial behavior analysis toolkit.  In _2018 13th IEEE International Conference on Automatic Face & Gesture Recognition (FG 2018)_, pages 59–66. IEEE.
  * Börstell (2023) Carl Börstell. 2023.  Extracting sign language articulation from videos with MediaPipe.  In _NoDaLiDa 2023_.
  * Cao et al. (2018) Zhe Cao, Gines Hidalgo, Tomas Simon, Shih-En Wei, and Yaser Sheikh. 2018.  OpenPose: realtime multi-person 2d pose estimation using part affinity fields.  In _arXiv preprint arXiv:1812.08008_.
  * Cecchetto (2012) Carlo Cecchetto. 2012.  Sentence types.  In Roland Pfau, Markus Steinbach, and Bencie Woll, editors, _Sign language: An international handbook_ , pages 292–315. De Gruyter Mouton.
  * Imashev et al. (2020) Alfarabi Imashev, Medet Mukushev, Vadim Kimmelman, and Anara Sandygulova. 2020.  A dataset for linguistic understanding, visual evaluation, and recognition of sign languages: The k-RSL.  In _Proceedings of the 24th Conference on Computational Natural Language Learning_ , pages 631–640, Online. Association for Computational Linguistics.
  * Kimmelman et al. (2020) Vadim Kimmelman, Alfarabi Imashev, Medet Mukushev, and Anara Sandygulova. 2020.  Eyebrow position in grammatical and emotional expressions in kazakh-russian sign language: A quantitative study.  _PLOS ONE_ , 15(6):e0233731.
  * Kuznetsova et al. (2021) Anna Kuznetsova, Alfarabi Imashev, Medet Mukushev, Anara Sandygulova, and Vadim Kimmelman. 2021.  Using Computer Vision to Analyze Non-manual Marking of Questions in KRSL.  In _Proceedings of the 1st International Workshop on Automatic Translation for Signed and Spoken Languages (AT4SSL)_ , pages 49–59, Virtual. Association for Machine Translation in the Americas.
  * Kuznetsova et al. (2022) Anna Kuznetsova, Alfarabi Imashev, Medet Mukushev, Anara Sandygulova, and Vadim Kimmelman. 2022.  Functional Data Analysis of Non-manual Marking of Questions in Kazakh-Russian Sign Language.  In _Proceedings of the LREC2022 10th Workshop on the Representation and Processing of Sign Languages: Multilingual Sign Language Resources_ , pages 124–131, Marseille, France. European Language Resources Association (ELRA).
  * Lugaresi et al. (2019) Camillo Lugaresi, Jiuqiang Tang, Hadon Nash, Chris McClanahan, Esha Uboweja, Michael Hays, Fan Zhang, Chuo-Ling Chang, Ming Guang Yong, Juhyun Lee, Wan-Teh Chang, Wei Hua, Manfred Georg, and Matthias Grundmann. 2019.  MediaPipe: A framework for building perception pipelines.
  * Morgan et al. (2022) Hope E. Morgan, Onno Crasborn, Maria Kopf, Marc Schulder, and Thomas Hanke. 2022\.  Facilitating the spread of new sign language technologies across europe.  In _Proceedings of the LREC2022 10th Workshop on the Representation and Processing of Sign Languages: Multilingual Sign Language Resources_ , pages 144–147. European Language Resources Association (ELRA).
  * Pfau and Quer (2010) Roland Pfau and Josep Quer. 2010.  Nonmanuals: their prosodic and grammatical roles.  In Diane Brentari, editor, _Sign Languages_ , pages 381–402. Cambridge University Press.
  * R Core Team (2022) R Core Team. 2022.  _R: A Language and Environment for Statistical Computing_.  R Foundation for Statistical Computing.
  * Trujillo et al. (2019) James P. Trujillo, Julija Vaitonyte, Irina Simanova, and Asli Özyürek. 2019.  Toward the markerless and automatic analysis of kinematic features: A toolkit for gesture and movement research.  _Behavior Research Methods_ , 51(2):769–777.
  * Wickham et al. (2019) Hadley Wickham, Mara Averick, Jennifer Bryan, Winston Chang, Lucy D’Agostino McGowan, Romain François, Garrett Grolemund, Alex Hayes, Lionel Henry, Jim Hester, Max Kuhn, Thomas Lin Pedersen, Evan Miller, Stephan Milton Bache, Kirill Müller, Jeroen Ooms, David Robinson, Dana Paige Seidel, Vitalie Spinu, Kohske Takahashi, Davis Vaughan, Claus Wilke, Kara Woo, and Hiroaki Yutani. 2019.  Welcome to the tidyverse.  _Journal of Open Source Software_ , 4(43):1686.
  * Zadeh et al. (2017) Amir Zadeh, Tadas Baltrušaitis, and Louis-Philippe Morency. 2017.  Convolutional experts constrained local model for facial landmark detection.  _ArXiv e-prints_ , arXiv:1611.08657.


#  The Doorways Problem and Sturmian Words

Jason Siefken  Northwestern University, Evanston, IL 60208 USA
<EMAIL_ADDRESS>
###### Abstract.

The doorways problem considers adjacent parallel hallways of unit width each
with a single doorway (aligned with integer lattice points) of unit width. It
then asks, what are the properties of lines that pass through each doorway?
Configurations of doorways closely correspond to Sturmian words, and so
properties of these configurations may be lifted to properties of Sturmian
words. This paper classifies the slopes of _lines of sight_ , lines that pass
through each doorway, for both the case of a finite number of parallel
hallways and an infinite number and their consequences for Sturmian words. We
then produce a metric on configurations with an infinite number of hallways
that preserves the property of admitting a line of sight under limits. Pulling
back this metric to $\mathbb{R}$, we produce the Baire metric under which the
irrational numbers form a complete metric space. Pulling back this metric to
the set of all Sturmian sequences, we show that the set of all Sturmian
sequences is complete with this metric (unlike with the standard metric).

##  1\. The Doorways Problem

Imagine a series of $n+1$ infinitely long parallel walls spaced one unit
apart, creating $n$ hallways. Further imagine that each wall has infinitely
many doors of unit width, but that only one door per wall is open.

Standing to one side of the hallways, you could imagine certain arrangements
of open doors you could see through and certain arrangements you could not.
This is precisely stated in the following definitions.

######  Definition 1 (Hallway).

An _$n$ -hallway_ is the set $H_{n}\subset\mathbb{R}^{2}$ defined by

$H_{n}=\bigcup_{i\in\\{0,\ldots,n\\}}\\{i\\}\times(\mathbb{R}\backslash
D_{i})$

where $D_{i}=(d_{i},d_{i}+1)$ is an open interval of width one and left point
$d_{i}\in\mathbb{Z}$. The set $D_{i}$ is called the $i$th _doorway_.

######  Definition 2 (Line of Sight).

Given an $n$-hallway $H_{n}$, we can _see through_ $H_{n}$ if there exists
some line $\ell_{\alpha\beta}=\\{(x,\alpha x+\beta):x\in\mathbb{R}\\}$ with
slope $\alpha$ and $y$-intercept $\beta$ so that $\ell_{\alpha\beta}\cap
H_{n}=\emptyset$. If $\ell_{\alpha\beta}\cap H_{n}=\emptyset$, we call
$\ell_{\alpha\beta}$ a _line of sight_ and we say $H_{n}$ _admits_ the line of
sight $\ell_{\alpha\beta}$. If $\ell_{\alpha\beta}$ is a line of sight and
$\alpha\in\mathbb{Q}$, we call $\ell_{\alpha\beta}$ a _rational line of
sight_.

Note that Definition 2 captures the idea that “no light is blocked” by a
hallway. This could be equivalently phrased as _an $n$-hallway $H_{n}$ with
doorways $D_{i}$ admits the line of sight $\ell_{\alpha\beta}$ if
$\ell_{\alpha\beta}\cap(\\{i\\}\times D_{i})\neq\emptyset$ for all $i$_, which
would capture the idea that “light passed through every doorway.” However,
upon the introduction of infinite hallways, the “no light is blocked”
definition will be more useful.

The doorways problem in general asks what types of $n$-hallways can be seen
through, and what are the properties of lines of sight. This question is
closely related to rotation sequences, balanced sequences, and Sturmian
sequences [2, 4], and it is from this context that the following motivating
question arises.

######  Question 3.

For an $n$-hallway $H_{n}$ that can be seen through, is there always a line of
sight $\ell_{\alpha\beta}$ with slope $\alpha=\frac{p}{q}$ where $q\leq n$?

###  1.1. Connection to Sturmians

Sturmian sequences and Sturmian words have many equivalent definitions in
terms of rotation sequences, billiard sequences, balanced words, complexity,
and invariant measures [2, 3, 4]. For the sake of brevity, we provide only two
equivalent definitions.

######  Definition 4 (Complexity).

For a sequence $x\in\\{0,1\\}^{\mathbb{N}}$, the _complexity function_ is

$L_{n}(x)=\\#\\{\text{distinct subwords of }x\text{ of length }n\\}.$

######  Definition 5 (Periodic and Eventually Periodic).

For a sequence $x\in\\{0,1\\}^{\mathbb{N}}$, let $(x)_{i}$ be the $i$th
coordinate of $x$. The sequence $x\in\\{0,1\\}^{\mathbb{N}}$ is called
_periodic_ if there exists $m>0$ so that $(x)_{i}=(x)_{i+m}$ for all $i$ and
is called _aperiodic_ otherwise. The sequence is called _eventually periodic_
if there exists $m>0$ and some $I$ so that $(x)_{i}=(x)_{i+m}$ for all $i>I$.

######  Definition 6 (Sturmian Sequence).

Let $x\in\\{0,1\\}^{\mathbb{N}}$. The sequence $x$ is a _Sturmian sequence_ if
it is periodic and satisfies $L_{n}(x)\leq n+1$ for all $n$ or if it satisfies
$L_{n}(x)=n+1$ for all $n$. A _Sturmian word_ is a subword of a Sturmian
sequence.

A sequence $x\in\\{0,1\\}^{\mathbb{N}}$ satisfying $L_{n}(x)=n+1$ is always
aperiodic and never eventually periodic. Thus, an eventually periodic Sturmian
sequence must be periodic. Hedlund and Morse [5] proved that for any
$x\in\\{0,1\\}^{\mathbb{N}}$, $x$ is eventually periodic if and only if there
exists an $n$ such that $L_{n}(x)<n+1$. Viewed this way, aperiodic Sturmian
sequences are the aperiodic sequences of the lowest possible complexity.

######  Definition 7 (Rotation Sequence).

For a pair $(\alpha,\beta)\in[0,1]\times\mathbb{R}$, the rotation sequences
$s=\mathbf{R}_{\left\lfloor{\cdot}\right\rfloor}(\alpha,\beta)\in\\{0,1\\}^{\mathbb{N}}$
and
$s^{\prime}=\mathbf{R}_{\left\lceil{\cdot}\right\rceil}(\alpha,\beta)\in\\{0,1\\}^{\mathbb{N}}$
are the sequences whose $i$th coordinates are given by

$(s)_{i}=\left\lfloor{(i+1)\alpha+\beta}\right\rfloor-\left\lfloor{i\alpha+\beta}\right\rfloor$

and

$(s^{\prime})_{i}=\left\lceil{(i+1)\alpha+\beta}\right\rceil-\left\lceil{i\alpha+\beta}\right\rceil,$

where $\left\lfloor{\cdot}\right\rfloor$ and $\left\lceil{\cdot}\right\rceil$
are the floor and ceiling functions, respectively. A sequence
$x\in\\{0,1\\}^{\mathbb{N}}$ is called a _rotation sequence_ if
$x=\mathbf{R}_{\left\lfloor{\cdot}\right\rfloor}(\alpha,\beta)$ or
$x=\mathbf{R}_{\left\lceil{\cdot}\right\rceil}(\alpha,\beta)$ for some
$(\alpha,\beta)\in[0,1]\times\mathbb{R}$.

As shown in [2, 4], a sequence $x\in\\{0,1\\}^{\mathbb{N}}$ is Sturmian if and
only if it is a rotation sequence. Further, every Sturmian word appears as the
starting word of a rotation sequence (equivalently Sturmian sequence).

Given an $n$-hallway $H_{n}$ with doorways $D_{i}=(d_{i},d_{i}+1)$, there is a
natural correspondence between $H_{n}$ and elements in $\mathbb{Z}^{n}$.
Namely, associate $H_{n}$ with the $n$-word
$(d_{1}-d_{0},d_{2}-d_{1},\ldots,d_{n}-d_{n-1})$ given by the differences
between positions of consecutive doorways. Let
$\Phi:\\{\text{hallways}\\}\to\\{\text{words}\\}$ denote this correspondence.

The question of whether a hallway admits a line of sight only depends on the
relative placement of each doorway and is therefore translation invariant.
Thus $H_{n}$ admits a line of sight if and only if every hallway in
$\\{H_{n}^{\prime}:\Phi(H_{n}^{\prime})=\Phi(H_{n})\\}$ admits a line of
sight.

Fix an $n$-hallway $H_{n}$ with initial doorway $D_{0}=(0,1)$ and suppose
$\Phi(H_{n})$ is a Sturmian word. Further suppose $\Phi(H_{n})$ appears as the
initial word for the rotation sequence
$s=\mathbf{R}_{\left\lfloor{\cdot}\right\rfloor}(\alpha,\beta)$ and that
$(i\alpha+\beta)\notin\mathbb{Z}$ for $0\leq i\leq n$. We can now conclude
that

$D_{i}=(\left\lfloor{i\alpha+\beta}\right\rfloor,\left\lfloor{i\alpha+\beta}\right\rfloor+1)$

and $H_{n}$ admits the line of sight $\ell_{\alpha\beta}$. The converse of
this statement also holds, and with the technical assumptions minimized, we
get Theorem 8.

######  Theorem 8.

Let $\Psi_{a}:\\{a,a+1\\}^{n}\to\\{0,1\\}^{n}$ be the map that sends $a\mapsto
0$ and $(a+1)\mapsto 1$. The $n$-hallway $H_{n}$ admits a line of sight if and
only if $\Phi(H_{n})\in\\{a,a+1\\}^{n}$ for some $a$ and
$\Psi_{a}\circ\Phi(H_{n})$ is a Sturmian word.

We will not prove Theorem 8 in the context of Sturmian sequences, however,
studying the hallway problem directly we will arrive at equivalent results.
Theorem 8 also gives context as to why Question 3 might be interesting.

Consider the following: given a finite Sturmian word $w$, is $w$ always
contained in a periodic Sturmian word? If so, what is the minimum period of
such a word? Translating from hallways to rotation sequences to Sturmian
sequences, Question 3 asks, “Is a finite Sturmian word $w$ always contained in
a periodic Sturmian sequence with period bounded by the length of $w$?”

Studying $n$-hallways will provide a geometric way to answer this question.
Further, the extension of $n$-hallways to infinite hallways will allow us to
arrive at several results without the subtleties of working with Sturmian
sequences or rotation sequences directly. In particular, the distinction
between _aperiodic_ and _not eventually periodic_ and the need to include both
$\left\lfloor{\cdot}\right\rfloor$ and $\left\lceil{\cdot}\right\rceil$ (as in
the definition of rotation sequences) is avoided.

##  2\. Answering the Question

As discussed earlier, the question of whether an $n$-hallway admits a line of
sight is translation invariant. Thus, we will assume that all $n$-hallways
satisfy $D_{0}=(0,1)$. Now, we will tackle the question of whether or not
there exists lines of sight.

######  Definition 9.

Let $\mathrm{proj}_{\gamma}:\mathbb{R}^{2}\to\mathbb{R}$ be _parallel
projection onto the $y$-axis_ along a line of slope $\gamma$. That is,

$\mathrm{proj}_{\gamma}(x,y)=y-\gamma x.$

######  Proposition 10.

If $H_{n}$ is an $n$-hallway that admits a line of sight, then there is an
interval of slopes corresponding to lines of sight for $H_{n}$.

Proof. Fix $H_{n}$, an $n$-hallway, and let $\ell_{\alpha\beta}$ be a line of
sight. We now have $\mathrm{proj}_{\alpha}(\ell_{\alpha\beta})=\\{\beta\\}$.

Let $D_{i}=(d_{i},d_{i}+1)$ be the $i$th doorway of $H_{n}$, and let

$D=\bigcap_{0\leq i\leq n}\mathrm{proj}_{\alpha}(\\{i\\}\times D_{i}).$

Since $\ell_{\alpha\beta}$ is a line of sight, $\beta\in D\neq\emptyset$.
Since $D$ is a finite intersection of open intervals, $D=(d_{l},d_{r})$ is an
open interval. It directly follows that the “tube”
$T=\mathrm{proj}_{\alpha}^{-1}(D)\cap([0,n]\times\mathbb{R})$ safely passes
through every doorway in $H_{n}$, and as a consequence any line contained in
$T$ will be a line of sight. See Figure 1 for an example.

$T$slope $\alpha$$\ell$ Figure 1.  A hallway with four doorways and the
slope-$\alpha$ tube
$T=\mathrm{proj}_{\alpha}^{-1}(D)\cap([0,4]\times\mathbb{R})$ along with a
line of sight $\ell$ having slope greater than $\alpha$.

Since the width of $T$ is $n$ and the height of $T$ is $d_{r}-d_{l}>0$, we
know there must be lines of sight for every slope in the interval
$(\alpha-\frac{d_{r}-d_{l}}{n},\alpha+\frac{d_{r}-d_{l}}{n})$.

######  Corollary 11.

If $H_{n}$ is an $n$-hallway that admits a line of sight, then $H_{n}$ admits
a rational line of sight.

Since every interval of real numbers contains a rational number, Corollary 11
follows immediately.

The proof of Proposition 10 gives some insight into what types of hallways
admit lines of sight. In particular, a hallway admits a line of sight if and
only if $D^{\alpha}=\bigcap\mathrm{proj}_{\alpha}(\\{i\\}\times D_{i})$ is
non-empty for some $\alpha$.

Suppose $\alpha\in[0,1)$, and consider $1$-hallways. Recall that we always
assume $D_{0}=(0,1)$ is the first doorway. Now, if $\ell_{\alpha\beta}$ is a
line of sight for a $1$-hallway $H_{1}$, because $0\leq\alpha<1$, there are
only two possibilities for $D_{1}$. Namely, $D_{1}=(0,1)$ or $D_{1}=(1,2)$.
Since we are assuming $\ell_{\alpha\beta}$ is a line of sight for $H_{1}$, we
can completely determine what $D_{1}$ is by the following procedure: Let
$s_{1}=\mathrm{proj}_{\alpha}(1,1)$. If $\beta$, the $y$-intercept of
$\ell_{\alpha\beta}$, satisfies $\beta<s_{1}$, then $D_{1}=(0,1)$. If
$\beta>s_{1}$ then $D_{1}=(1,2)$. See Figure 2 for an illustration.

$(0,-1)$$(0,0)$$(0,1)$$(0,2)$$(1,-1)$$(1,0)$$(1,1)$$(1,2)$$s_{1}$slope
$\alpha$

$s_{1}$$s_{2}$$s_{2}^{\prime}$

Figure 2.  For a slope of $\alpha$, $s_{1}$ and $s_{2}$ divide $(0,1)$ into
regions based on the doorways $D_{1}$ and $D_{2}$.

Inductively, we may determine all possible hallways corresponding to lines of
sight with a particular slope. For illustration, consider $2$-hallways and
assume we have a line of sight $\ell_{\alpha\beta}$. If $D_{1}=(0,1)$, we know
$D_{2}=(0,1)$ or $(1,2)$. To find out which, let
$s_{2}=\mathrm{proj}_{\alpha}(2,1)$. If $\beta<s_{2}$, $D_{2}=(0,1)$, and if
$\beta>s_{2}$, $D_{2}=(1,2)$. Similarly, if $D_{1}=(1,2)$, the options for
$D_{2}$ are $(1,2)$ or $(2,3)$. Now letting
$s_{2}^{\prime}=\mathrm{proj}_{\alpha}(2,2)$, $\beta<s_{2}^{\prime}$ implies
$D_{2}=(1,2)$ and $\beta>s_{2}^{\prime}$ implies $D_{2}=(2,3)$.

If we continue this process, we will notice that we always consider
$s=\mathrm{proj}_{\alpha}(x_{0},y_{0})$ as a bifurcation point. That is, $s$
allows us to decide which doorway must be open if we presuppose a certain line
of sight.

######  Definition 12.

Let $Y_{\alpha,n}=(0,1)\backslash\left(\bigcup_{i\leq
n}\mathrm{proj}_{\alpha}(\\{i\\}\times\mathbb{Z})\right)$ and let
$\mathcal{Y}_{\alpha,n}$ be the partition of $Y_{\alpha,n}$ consisting of its
connected components.

As the next proposition shows, $\mathcal{Y}_{\alpha,n}$ exactly classifies
which sequence of doors must be open for a given line of sight. In this
respect, $\mathcal{Y}_{\alpha,n}$ can be seen as generating an equivalence
relation on intercepts of lines of sight with slope $\alpha$.

######  Proposition 13.

Fix $\alpha\in[0,1)$ and suppose $\ell_{\alpha\beta}$ is a line of sight for
the $n$-hallway $H_{n}$ and $\ell_{\alpha\beta^{\prime}}$ is a line of sight
for the $n$-hallway $H_{n}^{\prime}$. Then, $\beta,\beta^{\prime}\in Y$ for
some $Y\in\mathcal{Y}_{\alpha,n}$ if and only if $H_{n}=H_{n}^{\prime}$.

Proof. Notice that $H_{n}=H_{n}^{\prime}$ if and only if the sequences of
doorways for $H_{n}$ and $H_{n}^{\prime}$ are the same.

Suppose $H_{n}=H_{n}^{\prime}$ and that $\ell_{\alpha\beta}$ and
$\ell_{\alpha\beta^{\prime}}$ are lines of sight for $H_{n}$ and
$H_{n}^{\prime}$, respectively. By construction
$Y=(\mathrm{proj}_{\alpha}H_{n})^{c}=(\mathrm{proj}_{\alpha}H_{n}^{\prime})^{c}\in\mathcal{Y}_{\alpha,n}$,
and we must have $\beta,\beta^{\prime}\in Y$.

Now suppose that $\beta,\beta^{\prime}\in Y$ for some
$Y\in\mathcal{Y}_{\alpha,n}$. We will proceed by induction.

The base case is clear. $H_{1}=H_{1}^{\prime}$, since $\mathcal{Y}_{\alpha,1}$
precisely partitions the $y$-intercepts for lines of sight through
$(D_{0},D_{1})=\Big{(}(0,1),(0,1)\Big{)}$ and
$(D_{0},D_{1})=\Big{(}(0,1),(1,2)\Big{)}$.

Assume the proposition holds for $n-1$. This means that $D_{i}=D_{i}^{\prime}$
for $i<n$. Fix $a$ so that $D_{n-1}=D_{n-1}^{\prime}=(a,a+1)$. Since
$\alpha\in[0,1)$, there can only be two possibilities for $D_{n}$ or
$D_{n}^{\prime}$. Namely, $(a,a+1)$ or $(a+1,a+2)$. Let
$s=\mathrm{proj}_{\alpha}(n,a+1)$ and suppose $\ell_{\alpha\gamma}$ is a line
of sight for $H_{n}$. If $\gamma<s$, $D_{n}=(a,a+1)$ and if $\gamma>s$,
$D_{n}=(a+1,a+2)$.

We complete the proof by noticing that $s$ lies on the boundary of a partition
element of $\mathcal{Y}_{\alpha,n}$ (or completely outside the interval
$(0,1)$). Thus, if $\beta,\beta^{\prime}\in Y$, we have
$\beta,\beta^{\prime}>s$ or $\beta,\beta^{\prime}<s$, and so
$D_{n}=D_{n}^{\prime}$.

Propositions like Proposition 13 can be extended to handle lines of sights
with slopes in $\mathbb{R}$ without too much trouble, so we will mainly focus
on lines of sights with slopes in $[0,1)$ to make our arguments simpler.

######  Corollary 14.

For a fixed line $\ell_{\alpha\beta}$, there is at most one $n$-hallway such
that $\ell_{\alpha\beta}$ is a line of sight.

Proof. This follows directly from an application of Proposition 13 with
$\beta=\beta^{\prime}$.

######  Proposition 15.

For a fixed $\alpha$, the number of elements in the partition
$\mathcal{Y}_{\alpha,n}$ is at most $n+1$.

Proof. First, notice that since
$\mathrm{proj}_{\alpha}(x,y)-\mathrm{proj}_{\alpha}(x,y^{\prime})=y-y^{\prime}$,
for a fixed $i$, $(0,1)\cap\mathrm{proj}_{\alpha}(\\{i\\}\times\mathbb{Z})$
contains at most one point. This follows from the fact that integers are one
unit apart and $(0,1)$ is an open interval of width one.

Now, we may proceed by induction. Clearly $\mathcal{Y}_{\alpha,0}=\\{(0,1)\\}$
consists of one interval. Suppose $\mathcal{Y}_{\alpha,n-1}$ consists of no
more than $n$ intervals. $\mathcal{Y}_{\alpha,n}$ can be obtained from
$\mathcal{Y}_{\alpha,n-1}$ by slicing the partition elements of
$\mathcal{Y}_{\alpha,n-1}$ by the points in
$(0,1)\cap\mathrm{proj}_{\alpha}(\\{n\\}\times\mathbb{Z})$. But, there is at
most one point in $(0,1)\cap\mathrm{proj}_{\alpha}(\\{n\\}\times\mathbb{Z})$
and so at most one interval in $\mathcal{Y}_{\alpha,n-1}$ could be sliced into
two intervals. Thus the number of elements in $\mathcal{Y}_{\alpha,n}$ cannot
exceed $n+1$.

######  Corollary 16.

For a fixed $\alpha$, the number of distinct $n$-hallways having $D_{0}=(0,1)$
and admitting a line of sight of slope $\alpha$ is at most $n+1$.

Proof. From Proposition 13, $\mathcal{Y}_{\alpha,n}$ is in one-to-one
correspondence with $n$-hallways having lines of sight of slope $\alpha$.
Applying Proposition 15 shows $|\mathcal{Y}_{\alpha,n}|\leq n+1$, which
completes the proof.

Recalling the correspondence between $n$-hallways and finite words, Corollary
16 can be applied to show that rotation sequences satisfy the complexity
conditions required of Sturmian sequences. We might also ask the total number
of $n$-hallways admitting lines of slope of any $\alpha\in[0,1)$.

######  Theorem 17 (Mignosi [6]).

Let $C(n)$ be the number of distinct $n$-hallways with $D_{0}=(0,1)$ and
admitting a line of sight with slope in $[0,1)$. Then,

$C(n)=1+\sum_{i=1}^{n}(n+1-i)\phi(i)$

where $\phi(i)$ is Euler’s totient function, which counts the number of
integers in $\\{1,\ldots,i\\}$ that are relatively prime to $i$.

In [6], Mignosi uses combinatoric properties to count subwords of Sturmian
sequences, In [1], Berstel and Pocchiola use geometric arguments to arrive at
the same conclusion.

Let’s get a slightly better idea of what the set of all $n$-hallways looks
like.

######  Definition 18.

Let $S_{n}\subset[0,1]\times(0,1)$ be the set of pairs $(\alpha,\beta)$ such
that $\ell_{\alpha\beta}$ is a line of sight for some $n$-hallway. Let
$\mathcal{P}_{n}$ be the partition of $S_{n}$ where $(\alpha,\beta)$ and
$(\alpha^{\prime},\beta^{\prime})$ are in the same partition element if
$\ell_{\alpha\beta}$ and $\ell_{\alpha^{\prime}\beta^{\prime}}$ are lines of
sight for the same $n$-hallway.

Corollary 14 ensures that $\mathcal{P}_{n}$ is well defined. Drawing
$\mathcal{P}_{n}$ as a subset of $\mathbb{R}^{2}$, we see that the vertical
fiber of $\mathcal{P}_{n}$ with $x$-coordinate $\alpha$ is precisely
$\mathcal{Y}_{\alpha,n}$.

Looking at $\mathcal{Y}_{\alpha,n}$ as a function of $\alpha$, we wee that
$\mathcal{Y}_{\alpha,n}$ must be split at the point

$f_{i}(\alpha)=\mathrm{proj}_{\alpha}(\\{i\\}\times\mathbb{Z})=\mathrm{proj}_{\alpha}(i,0)\
\mathrm{mod}\ 1=-\alpha i\ \mathrm{mod}\ 1$

for every $i\in\\{0,\ldots,n\\}$. In other words, $\mathcal{P}_{n}$ looks like
$[0,1]\times(0,1)$ cut by the lines (mod 1) of slope $-i$ for
$i\in\\{0,\ldots,n\\}$. See Figure 3.

$\alpha$$t$$\frac{1}{2}$$\frac{1}{3}$$\frac{2}{3}$$0$$1$$1$$\frac{1}{2}$
Figure 3.  The partition $\mathcal{P}_{5}$.

Using this description of $\mathcal{P}_{n}$, we can answer our question about
rational lines of sight.

######  Theorem 19.

Given an $n$-hallway $H_{n}$ admitting a line of sight, there is a rational
line of sight $\ell_{\alpha\beta}$ with $\alpha=\frac{p}{q}$ and $q\leq n$.

Proof. Fix an $n$-hallway $H_{n}$ admitting a line of sight at let
$P\in\mathcal{P}_{n}$ be the corresponding partition element. That is, for
every $(\alpha,\beta)\in P$, $\ell_{\alpha\beta}$ is a line of sight for
$H_{n}$.

Our proof would be complete if we could show that $P$ contained a point
$(\alpha,\beta)$ where $\alpha=\frac{p}{q}$ with $q\leq n$. To this end,
consider the corners of $P$, when $P$ is interpreted as a polygon. Since
$\mathcal{P}_{n}$ is formed by cutting $[0,1]\times(0,1)$ by lines of slope
$-1,\ldots,-n$, the edges of $P$ are segments of lines of the same slope and
so the corners are intersections of such lines.

We will now compute the intersection of two lines of the form $y=-ax\
\mathrm{mod}\ 1$. Notice that any connected segment of the graph of such a
line is identical to the graph of the line $y=-ax+b$ restricted to
$[0,1]\times(0,1)$ for some $1\leq b\leq a$.

Let $L_{-a,b}(x)=-ax+b$ be a line with slope $-a$ and $y$-intercept $b$. Then,
the intersection of the graphs of $L_{-a,b}$ and $L_{-a^{\prime},b^{\prime}}$
occurs at

$x=\frac{b^{\prime}-b}{a^{\prime}-a}\qquad\text{and}\qquad
L_{-a,b}(x)=\frac{a^{\prime}b-ab^{\prime}}{a^{\prime}-a}.$

Now, if $a,a^{\prime}\in\\{0,\ldots,n\\}$, $|a^{\prime}-a|\leq n$. This shows
that the $x$-coordinate of every corner of $P$ is of the form $\frac{p}{q}$
with $q\leq n$.

To complete the proof, notice that either $P$ is one of the two extreme
cases—the triangles with corners $(0,0)$, $(1,1)$, $(1/n,0)$ or $(1,0)$,
$(1,1)$, $(1/n,1)$—or $P$ has a corner directly above or below its interior
(see Figure 3). If $P$ is the left extremal triangle, then there is a line of
sight $\ell_{0\beta}$ for some $\beta$ and if $P$ is the right extremal
triangle, there is a line of sight $\ell_{1\beta}$ for some $\beta$.

Finally, if $P$ has a corner with coordinates $(\alpha,b)$ above or below its
interior, then there must be some point $(\alpha,\beta)\in P$. Thus
$\ell_{\alpha\beta}$ is a line of sight and as shown, $\alpha=\frac{p}{q}$
with $q\leq n$.

##  3\. Infinite Hallways

Diagrams like Figure 3 show that if an $n$-hallway admits a line of sight
$\ell_{\alpha\beta}$, then it admits lines of sign $\ell_{\gamma\delta}$ for a
host of real numbers $\gamma$ and $\delta$. However, things become a bit more
restricted when we pass to infinite hallways.

An infinite hallway is defined analogously to a finite hallway and can be
thought of as the union of finite hallways that get longer and longer. It
would now seem natural to say that an infinite hallway $H^{\infty}$ has a line
of sight if and only if $\ell_{\alpha\beta}\cap H^{\infty}=\emptyset$ for some
$\alpha$ and $\beta$. However, this definition rules out a very desirable
property.

_Desirable Property_ :

> If $H^{\infty}$ is an infinite hallway admitting a line of sight, then there
> exists a doorway $D_{-1}=(d_{-1},d_{-1}+1)$ such that the infinite hallway
> $\\{-1\\}\times(\mathbb{R}\backslash D_{-1})\cup H^{\infty}$ admits a line
> of sight.

That is, if a hallway admits a line of sight, we should be able to add a
doorway to it and have it still admit a line of sight. In the finite hallway
case, this is always true and there are always infinitely many lines of sight.
However, for infinite hallways, there may be a unique line of sight and the
naïve formulation of infinite hallways does not always allow a door to be
added while preserving visibility. For example, consider the infinite hallway
$H^{\infty}$ whose $i$th doorway is
$D_{i}=(\left\lfloor{n\pi}\right\rfloor,\left\lfloor{n\pi}\right\rfloor+1)$
for $i\geq 1$ and where $D_{0}$ is undefined. As will be shown in Theorem 27,
$\ell_{\pi 0}$ is the only line such that $\ell_{\pi 0}\cap
H^{\infty}=\emptyset$. However, $\ell_{\pi 0}$ contains the point $(0,0)$ on
the integer lattice and so there is no acceptable choice of $D_{0}$ if we
would like $H^{\infty}$ to admit a line of sight (since every doorway excludes
every lattice point).

We will solve this issue by introducing infinitesimals.

######  Definition 20 (Infinitesimals).

Let $\epsilon$ represent a positive infinitesimal. Formally, let
$\mathbb{R}^{\epsilon}=\\{a+b\epsilon:a,b\in\mathbb{R}\\}$ be the two-
dimensional vector space with basis $\\{1,\epsilon\\}$ over the field
$\mathbb{R}$ endowed with the following total order:

$a+b\epsilon<c+d\epsilon\qquad\text{if}\qquad a<c\qquad\text{or}\qquad
a=c\text{ and }b<d$

and

$a+b\epsilon=c+d\epsilon\qquad\text{if}\qquad a=c\text{ and }b=d.$

A number $r=a+b\epsilon\in\mathbb{R}^{\epsilon}$ is called _real_ if $b=0$.

This all amounts to saying that $\epsilon$ satisfies $0<\epsilon<a$ for all
positive real numbers $a$ and that addition of infinitesimals and
multiplication of infinitesimals by real numbers makes sense. We define open
and closed intervals in the usual way: the open interval
$(a,b)\subseteq\mathbb{R}^{\epsilon}$ is defined as
$(a,b)=\\{r\in\mathbb{R}^{\epsilon}:a<r<b\\}$ and the closed interval
$[a,b]\subset\mathbb{R}^{\epsilon}$ is defined as
$[a,b]=\\{r\in\mathbb{R}^{\epsilon}:a\leq r\leq b\\}$ and in general we endow
$\mathbb{R}^{\epsilon}$ with the order topology.

Now we will precisely define what it means to be an infinite hallway,
systematically replacing $\mathbb{R}$ (in the finite case) with
$\mathbb{R}^{\epsilon}$ (in the infinite case).

######  Definition 21 (Infinite Hallway).

Let $D_{i}=(d_{i},d_{i}+1)\subset\mathbb{R}^{\epsilon}$ for
$d_{i}\in\mathbb{Z}$ be a sequence of open unit intervals and define the
corresponding infinite hallway $H^{\infty}$ as

$H^{\infty}=\bigcup_{i\in\mathbb{Z}}\\{i\\}\times(\mathbb{R}^{\epsilon}\backslash
D_{i}).$

We will notate the restriction of $H^{\infty}$ to the first $n$ hallways it
contains by

$H_{n}^{\infty}=H^{\infty}\cap([0,n]\times\mathbb{R}^{\epsilon}).$

######  Definition 22 (Infinite Lines).

For $\alpha,\beta\in\mathbb{R}$, define the _infinite line_
$\ell_{\alpha\beta}^{\epsilon}\subset\mathbb{R}\times\mathbb{R}^{\epsilon}$ by

$\ell_{\alpha\beta}^{\epsilon}=\\{(x,\alpha(x+t\epsilon)+\beta):x,t\in\mathbb{R}\\}.$

Given a subset $X\subset\mathbb{R}\times\mathbb{R}^{\epsilon}$, for any
$t\in\mathbb{R}^{\epsilon}$, we define $X+t=\\{(a,b+t):(a,b)\in X\\}$. In this
notation, we can alternatively define
$\ell^{\epsilon}_{\alpha\beta}=\bigcup_{t\in\mathbb{R}}\ell_{\alpha\beta}+t\epsilon$.

Infinite lines are “fattened up” lines. As such, we need to slightly modify
how we define a line of sight. Whereas, $\ell_{\alpha\beta}\cap H=\emptyset$
captures the idea “no light is blocked,” we would like to capture the idea
“not all light is blocked.”

######  Notation 23.

Given a line or infinite line $\ell_{\alpha\beta}^{*}$ and a hallway or
infinite hallway $H^{*}$, the _visibility operator_ $\vee$ is defined as

$\ell_{\alpha\beta}^{*}\vee H^{*}=\text{real part of
}(\mathrm{proj}_{\alpha}\ell_{\alpha\beta}^{*})\cap(\mathrm{proj}_{\alpha}H^{*})^{c}.$

######  Definition 24 (Infinite Line of Sight).

The infinite line $\ell_{\alpha\beta}^{\epsilon}$ is a _line of sight for the
infinite hallway $H^{\infty}$_ if $\ell_{\alpha\beta}^{\epsilon}\vee
H^{\infty}\neq\emptyset$.

Notice that infinite lines of sight are still defined by real parameters, they
are just infinitesimally “fattened up.” To see this, consider the following
example. Let $H^{\infty}$ be the infinite hallway with doorways
$D_{i}=(i,i+1)$. $H^{\infty}$ has infinite lines of sight
$\ell_{1\beta}^{\epsilon}$ for every $\beta\in[0,1]$. In particular,
$\ell_{10}^{\epsilon}$ and $\ell_{11}^{\epsilon}$ are infinite lines of sight,
but we would not consider the real lines $\ell_{10}$ and $\ell_{11}$ to be
lines of sight.

From now on we will refer to infinite lines of sight simply as lines of sight
and use the term _real line of sight_ if we need to draw a careful distinction
between infinite and non-infinite lines of sight.

######  Proposition 25.

If $H^{\infty}$ is an infinite hallway with line of sight
$\ell_{\alpha\beta}^{\epsilon}$, then either
$(\ell_{\alpha\beta}+\epsilon)\cap H^{\infty}\neq\emptyset$ or
$(\ell_{\alpha\beta}-\epsilon)\cap H^{\infty}\neq\emptyset$.

Proof. Observe that if $\ell^{\epsilon}_{\alpha\beta}\vee
H^{\infty}\neq\emptyset$, then for some $r\in\mathbb{R}$ we have
$(\ell_{\alpha\beta}+r\epsilon)\cap H^{\infty}=\emptyset$. If $r\geq 0$, then
we must have $(\ell_{\alpha\beta}+\epsilon)\cap H^{\infty}\neq\emptyset$ and
if $r\leq 0$ we must have $(\ell_{\alpha\beta}-\epsilon)\cap
H^{\infty}\neq\emptyset$.

Next we will show that the using infinite lines of sight gives us our desired
property. In fact, it gives us something slightly stronger.

######  Proposition 26.

Suppose $\hat{H}^{\infty}$ is an infinite hallway missing its first door and
admitting a line of sight $\ell_{\alpha\beta}^{\epsilon}$. If $D_{i}$ for
$i\geq 1$ are the doorways for $\hat{H}^{\infty}$, then there exists a doorway
$D_{0}$ such that the infinite hallway $H^{\infty}$ with doorways $D_{i}$ for
$i\geq 0$ admits the line of sight $\ell_{\alpha\beta}^{\epsilon}$.

Proof. Suppose $D_{i}$ for $i\geq 1$ and $\hat{H}^{\infty}$ are as in the
statement of the proposition. Given a definition for $D_{0}$, let $H^{\infty}$
be the infinite hallway with doorways $D_{i}$ for $i\geq 0$. Let
$z=\left\lfloor{\beta}\right\rfloor$. From Proposition 25 we know either
$(\ell_{\alpha\beta}+\epsilon)\cap\hat{H}^{\infty}=\emptyset$ or
$(\ell_{\alpha\beta}-\epsilon)\cap\hat{H}^{\infty}=\emptyset$.

Suppose $(\ell_{\alpha\beta}+\epsilon)\cap\hat{H}^{\infty}=\emptyset$. In this
case, define $D_{0}=(z,z+1)$. We now have
$z+1>\mathrm{proj}_{\alpha}(\ell_{\alpha\beta}+\epsilon)=\beta+\epsilon>z$,
and so $(\ell_{\alpha\beta}+\epsilon)\cap H^{\infty}=\emptyset$. It
immediately follows that $\ell_{\alpha\beta}^{\epsilon}$ is a line of sight
for $H^{\infty}$.

If $(\ell_{\alpha\beta}-\epsilon)\cap\hat{H}^{\infty}=\emptyset$, a similar
argument shows that if $D_{0}=(z-1,z)$, then $H^{\infty}$ admits the line of
sight $\ell^{\epsilon}_{\alpha\beta}$.

######  Theorem 27.

Let $H^{\infty}$ be an infinite hallway. If $\ell_{\alpha\beta}^{\epsilon}$
and $\ell_{\gamma\delta}^{\epsilon}$ are both lines of sight for $H^{\infty}$,
then $\alpha=\gamma$. In other words, all lines of sight for $H^{\infty}$ have
the same slope.

Proof. Let $H^{\infty}$ be an infinite hallway with doorways
$D_{i}=(d_{i},d_{i}+1)$ and suppose $\ell_{\alpha\beta}^{\epsilon}$ is a line
of sight for $H^{\infty}_{n}$. Let $\bar{D}_{i}=[d_{i},d_{i}+1]$ and notice
that $\ell_{\alpha\beta}$ must pass through $\bar{D}_{0}$ and $\bar{D}_{n}$.
From this, we conclude

$\frac{d_{0}-(d_{n}+1)}{n}=\frac{d_{0}-d_{n}}{n}-\frac{1}{n}\leq\alpha\leq\frac{d_{0}-d_{n}}{n}+\frac{1}{n}=\frac{d_{0}+1-d_{n}}{n},$

since a line with any slope outside of that range would not pass through
$\bar{D}_{0}$ and $\bar{D}_{n}$.

Now, if $\ell_{\alpha\beta}^{\epsilon}$ is a line of sight for $H^{\infty}$,
it is a line of sight for every $H^{\infty}_{n}$. Thus for any $r>0$ and
$n>1/r$,

$\alpha-r\leq\frac{d_{0}-d_{n}}{n}\leq\alpha+r$

and so $\lim_{n\to\infty}(d_{0}-d_{n})/n=\alpha$ exists. Since
$\lim_{n\to\infty}(d_{0}-d_{n})/n$ exists and is unique, there can only be one
slope for lines of sight for $H^{\infty}$.

######  Definition 28 (Periodic Hallways).

An infinite hallway $H^{\infty}$ with doors $D_{i}=(d_{i},d_{i}+1)$ is called
_periodic with period $m>0$_ if there exists some $k$ such that

$D_{i+m}=D_{i}+k=(d_{i}+k,d_{i}+k+1).$

If there exists an $m$ such that $H^{\infty}$ is periodic with period $m$,
$H^{\infty}$ is called _periodic_ , otherwise $H^{\infty}$ is called
_aperiodic_.

If $H^{\infty}$ is periodic, the _minimum period_ is the smallest $m$ such
that $H^{\infty}$ is periodic with period $m$.

######  Theorem 29.

An infinite hallway $H^{\infty}$ which admits a line of sight is periodic if
and only if it admits a rational line of sight.

Proof. Suppose $H^{\infty}$ is an aperiodic infinite hallway with doorways
$D_{i}=(d_{i},d_{i}+1)$ and line of sight $\ell_{\alpha\beta}^{\epsilon}$.

If $H^{\infty}$ is periodic, then there is some $m$ such that
$d_{km}=d_{0}+k(d_{m}-d_{0})$. Now,

$\alpha=\lim_{n\to\infty}\frac{d_{0}-d_{n}}{n}=\lim_{k\to\infty}\frac{d_{0}-d_{km}}{km}=\lim_{k\to\infty}\frac{d_{0}-(d_{0}+k(d_{m}-d_{0}))}{km}=\frac{r}{m}$

where $r=d_{m}-d_{0}$ and so $\alpha\in\mathbb{Q}$.

Conversely, suppose $\alpha=\tfrac{p}{q}\in\mathbb{Q}$. Now,
$\beta+n\tfrac{p}{q}+\epsilon\in(d_{n},d_{n}+1)$ or
$\beta+n\tfrac{p}{q}-\epsilon\in(d_{n},d_{n}+1)$, and so in particular,
$d_{n}$ is the unique integer such that

$\beta+n\tfrac{p}{q}-1<d_{n}<\beta+n\tfrac{p}{q}.$

Letting $k=n+q$, we additionally have

$\beta+n\tfrac{p}{q}+p-1<d_{k}=d_{n+q}<\beta+n\tfrac{p}{q}+p,$

and so $d_{n+q}$ is the unique integer such that
$\beta+n\tfrac{p}{q}-1<d_{n+q}-p<\beta+n\tfrac{p}{q}$, which shows
$H^{\infty}$ is periodic with period $q$.

The proof of Theorem 29 actually gives us an additional result.

######  Theorem 30.

An infinite hallway $H^{\infty}$ admitting a line of sight has period $m$ if
and only if it admits a rational line of sight with slope $p/m$ for some
$p\in\mathbb{Z}$.

######  Corollary 31.

Suppose $H^{\infty}$ is an infinite periodic hallway with minimal period $m$.
If $\ell_{\tfrac{p}{m}\beta}^{\epsilon}$ is a line of sight for $H^{\infty}$,
then $p/m$ is in lowest terms.

Proof. We will prove the contrapositive. Suppose $H^{\infty}$ is an infinite
hallway admitting a line of sight $\ell_{\tfrac{p}{m}\beta}^{\epsilon}$. If
$p/m$ is not in lowest terms, then $p/m=p^{\prime}/m^{\prime}$ where
$0<m^{\prime}<m$. Since $m^{\prime}$ is a period for $H^{\infty}$, we know $m$
is not a minimal period.

We now know quite a bit about the slopes of lines of sight for infinite
hallways. Let us introduce a lemma dealing with the intercepts.

######  Lemma 32.

Suppose $H^{\infty}$ is an infinite hallway with doorways $D_{i}$ and
admitting a line of sight $\ell_{\alpha\beta}^{\epsilon}$. Let
$P_{n}=(p^{n}_{i})_{i\in\mathbb{Z}}$ be an enumeration of the points in
$\mathrm{proj}_{\alpha}(\\{0,1,\ldots,n\\}\times\mathbb{Z})$ satisfying
$p^{n}_{i}<p^{n}_{i+1}$. Let $B_{n}=\\{[p^{n}_{i},p^{n}_{i+1}]:p^{n}_{i}\in
P^{n}\\}$ and let $D=\\{\gamma:\ell_{\alpha\gamma}^{\epsilon}\text{ is a line
of sight for }H^{\infty}\\}$. Then $D$ is a (possibly degenerate) interval
such that for all $n$, $D\subseteq B$ for some $B\in B_{n}$.

Proof. Suppose $\ell_{\alpha\beta}^{\epsilon}$ is a line of sight for an
infinite hallway $H^{\infty}$ with doorways $D_{i}=(d_{i},d_{i}+1)$. Let
$\bar{D}_{i}=[d_{i},d_{i+1}]$. If $\ell_{\alpha\gamma}^{\epsilon}$ is a line
of sight for $H^{\infty}$, then $\ell_{\alpha\gamma}^{\epsilon}$ must
intersect $\\{i\\}\times D_{i}$ for every $i$. By Proposition 25,
$\ell_{\alpha\gamma}+\epsilon$ or $\ell_{\alpha\gamma}-\epsilon$ must
intersect $\\{i\\}\times D_{i}$ for each $i$ and so $\ell_{\alpha\gamma}$
intersects $\\{i\\}\times\bar{D}_{i}$ for each $i$. Thus, we have the equality

$D=\bigcap_{i\geq
0}\mathrm{proj}_{\alpha}\left(\\{i\\}\times\bar{D}_{i}\right).$

Since $D$ can be written as an intersection of intervals, it is an interval.
Lastly, since $D_{i}\cap\mathbb{Z}=\emptyset$ for all $i$, we know that for
every $n$, $D\subset B$ for some $B\in B_{n}$.

From Lemma 32 we can get a bound on the size of $D$.

######  Theorem 33.

Let $H^{\infty}$ be an infinite hallway. If $H^{\infty}$ is periodic with
minimal period $m$ and $\ell_{\alpha\beta}^{\epsilon}$ and
$\ell_{\alpha\delta}^{\epsilon}$ are lines of sight for $H^{\infty}$, then
$|\beta-\delta|\leq 1/m$.

Proof. This follows quickly from Lemma 32. If $\ell^{\epsilon}_{\alpha\beta}$
is a line of sight for an infinite periodic hallway with minimal period $m$,
then $\alpha=p/m$ for some $p$. This means, for all $i,j\geq m$,

$\mathrm{proj}_{\alpha}(\\{0,1,\ldots,i\\}\times\mathbb{Z})=\mathrm{proj}_{\alpha}(\\{0,1,\ldots,j\\}\times\mathbb{Z}),$

and so $B_{i}=B_{j}$ where $B_{n}$ is defined as in the statement of Lemma 32.
Since $\alpha=p/m$ must be in lowest terms, a quick calculation shows every
interval in $B_{i}$ for $i\geq m$ has width no greater than $1/m$, which
completes the proof.

######  Theorem 34.

Let $H^{\infty}$ be an infinite hallway. If $H^{\infty}$ is aperiodic, then
there is at most one line of sight for $H^{\infty}$.

Proof. Suppose $H^{\infty}$ is an aperiodic infinite hallway with doorways
$D_{i}=(d_{i},d_{i}+1)$ and line of sight $\ell_{\alpha\beta}^{\epsilon}$.
Necessarily we have $\alpha\notin\mathbb{Q}$, and by Theorem 27 $\alpha$ is
unique.

Let $D=\\{\gamma:\ell_{\alpha\gamma}^{\epsilon}\text{ is a line of sight for
}H^{\infty}\\}$. Since $\beta\in D$, $D$ is a non-empty (but possibly
degenerate) interval. Further, for every $n$ we have that $D\subseteq B$ for
some $B\in B_{n}$ where $B_{n}$ is as in the statement of Lemma 32. But, since
$\alpha\notin\mathbb{Q}$, $\mathrm{proj}_{\alpha}(\mathbb{N}\times\mathbb{Z})$
is dense the diameter if every interval in $B_{n}$ tends towards zero as
$n\to\infty$. We conclude that $D=\\{\beta\\}$ must be a singleton and so
there is only one line of sight for $H^{\infty}$.

The converse to Theorem 34 is also true. If there is a unique line of sight
for an infinite hallway, it must be aperiodic.

###  3.1. Metrics on Hallways

The theorems in the preceding section, taken together, show a correspondence
between infinite hallways and a symbolic _shift space_. Consider the map
$\Phi:\\{\text{infinite hallways}\\}\to\mathbb{Z}^{\mathbb{N}}$ where the
$i$th coordinate of $\Phi(H)$ is $d_{i}-d_{i+1}$. $\Phi$ is an extension of
the identically-named map between $n$-hallways and $n$-words from earlier.
Under the assumption that the initial doorway of every infinite hallway is
$D_{0}=(0,1)$, $\Phi$ is a bijection between hallways and sequences.

Let $T:\mathbb{Z}^{\mathbb{N}}\to\mathbb{Z}^{\mathbb{N}}$ be the _shift_ map.
That is $T(a_{0},a_{1},a_{2},\ldots)=(a_{1},a_{2},\ldots)$ deletes the first
coordinate of a sequence. Let $\Omega$ be the image under $\Phi$ of all
infinite hallways admitting a line of sight. Now, $T(\Omega)\subset\Omega$ is
immediate, and Proposition 26 (the proposition that gives us our desirable
property) shows that $T(\Omega)=\Omega$. Thus, $\Omega$ is $T$-invariant. The
word closed is almost always used in conjunction with the word invariant, so
we might ask if $\Omega$ is also closed.

The shift space $(\mathbb{Z}^{\mathbb{N}},T)$ is typically endowed with the
product topology on $\mathbb{Z}^{\mathbb{N}}$ where $\mathbb{Z}$ has the
discrete topology. This is the same topology arising from the _standard metric
on sequences_ , $d$. Namely, if $x,y\in\mathbb{Z}^{\mathbb{N}}$, $d(x,y)=1/n$
where $n$ is the index of the first coordinate where $x$ and $y$ differ.

Using $\Phi$, the standard metric on sequences induces a metric on infinite
hallways.

######  Definition 35 (Standard Metric on Infinite Hallways).

Let $H,H^{\prime}$ be infinite hallways. The _standard metric_ on infinite
hallways, notated $d_{S}$, is defined as

$d(\Phi(H),\Phi(H^{\prime}))=d_{S}(H,H^{\prime})=\frac{1}{n}\quad\text{ where
}\quad n=\inf\\{k\in\mathbb{N}:H_{k}\neq H_{k}^{\prime}\\},$

with the convention $1/\infty=0$ and $1/0=\infty$.

Standard arguments now show that the set of all infinite hallways is complete
with respect to $d_{S}$.

Let $V:\\{\text{infinite hallways}\\}\to\\{0,1\\}$ be the _visibility
function_. That is, $V(H)=1$ if $H$ admits a line of sight and $0$ otherwise.
Now, suppose $H$ is an infinite hallway that admits a line of sight and let
$H^{\prime}$ be $H$ with a single doorway changed. Since $V(H)=1$ and
$V(H^{\prime})=0$, we cannot hope that $V$ is continuous. However, we might
hope that $V$ would be upper-semicontinuous. That is, we might hope that if
$H^{(n)}\to H$ is a convergent sequence of infinite hallways and
$V(H^{(n)})=1$, then $V(H)=1$. Alas, this is not so with the standard metric.

######  Proposition 36.

The visibility function $V$ is not upper-semicontinuous with respect to the
standard metric on infinite hallways, $d_{S}$.

Proof. Let $H^{(n)}$ be the periodic infinite hallway admitting a line of
sight with slope $1/n$ and with doorways $D_{0}^{(n)}=(0,1)$,
$D_{1}^{(n)}=(1,2)$, and
$D_{i}^{(n)}=(\left\lfloor{\tfrac{i-1}{n}}\right\rfloor+1,\left\lfloor{\tfrac{i-1}{n}}\right\rfloor+2)$.
Geometrically, $H^{(n)}$ has a jump of size 1 between $D_{0}$ and $D_{1}$,
then has $n$ identical doorways in a row before another jump of size 1.

Now, for all $m,n$, we have

$(0,1)=D_{0}^{(m)}=D_{0}^{(n)}\qquad\text{and}\qquad(1,2)=D_{1}^{(m)}=D_{1}^{(n)}$

and for every $n,m>k>1$ and $1\leq i\leq k$,

$(1,2)=D_{1}^{(n)}=D_{i}^{(m)}.$

From this description, we see $H^{(n)}\to H^{\infty}$ which has doorways
$D_{0}^{\infty}=(0,1)$ and $D_{i}^{\infty}=(1,2)$ for all $i\geq 1$. But
$V(H^{(n)})=1$ and $V(H^{\infty})=0$, so $V$ is not semi-continuous.

Since $\Omega=\Phi^{-1}\circ V^{-1}(1)$, Proposition 36 shows that $\Omega$ is
not closed with respect to the standard metric. Similarly, the set of all
Sturmian sequences is not closed under the standard metric (because, as in
Proposition 36, limits of periodic points may be aperiodic but eventually
periodic) and the property of being a rotation sequence is not closed under
limits.

All hope is not lost, though. There may be a different metric that $V$ is
upper-semicontinuous with respect to. The counterexample used in Proposition
36 relied on a sequence of periodic infinite hallways. In particular, the
lines of sight had slope converging to a rational number, so we might seek to
prevent hallways from doing this.

######  Definition 37 (Common Initial Segment).

Given two infinite hallways $H$ and $H^{\prime}$, their _common initial
segment_ is

$\operatorname{comm}(H,H^{\prime})=H_{1/d_{S}(H,H^{\prime})}=H_{1/d_{S}(H,H^{\prime})}^{\prime}.$

If $H=H^{\prime}$, we consider
$\operatorname{comm}(H,H^{\prime})=H=H^{\prime}$. Otherwise,
$\operatorname{comm}(H,H^{\prime})$ is always a finite hallway or empty.

######  Definition 38 (Unframed Hallway).

Given a hallway $H$ with $i$th doorway $(d_{i},d_{i}+1)$, the corresponding
_unframed hallway_ is the hallway $\bar{H}$ whose $i$th doorway is the closed
interval $[d_{i},d_{i}+1]$.

######  Definition 39 (Rational Metric on Infinite Hallways).

Let $H,H^{\prime}$ be infinite hallways. The _rational metric_ on infinite
hallways, notated $d_{R}$, is defined as follows.

If $H=H^{\prime}$, then $d_{R}(H,H^{\prime})=0$; if
$\operatorname{comm}(H,H^{\prime})$ admits a line of sight,

$d_{R}(H,H^{\prime})=\max\\{\tfrac{1}{q}:\ell_{\frac{p}{q}\beta}\text{ is a
line of sight for }\operatorname{comm}(\bar{H},\bar{H}^{\prime})\text{ for
some }\beta\in\mathbb{R},p\in\mathbb{Z}\\};$

and if $\operatorname{comm}(H,H^{\prime})$ admits no line of sight and $H\neq
H^{\prime}$, then $d_{R}(H,H^{\prime})=\infty$.

######  Proposition 40.

The rational metric, $d_{R}$, is a metric on infinite hallways.

Proof. By definition $d_{R}(H,H^{\prime})=0$ if $H=H^{\prime}$. Suppose $H\neq
H^{\prime}$ . If $\operatorname{comm}(H,H^{\prime})$ admits no line of sight,
$d_{R}(H,H^{\prime})=\infty>0$. If $\operatorname{comm}(H,H^{\prime})$ admits
a line of sight, because it is a finite hallway, it admits a rational line of
sight and so $d_{R}(H,H^{\prime})>0$. Further, since
$\operatorname{comm}(H,H^{\prime})=\operatorname{comm}(H^{\prime},H)$,
$d_{R}(H,H^{\prime})=d_{R}(H^{\prime},H)$ and so conditions (i) and (ii) are
satisfied.

Now we consider condition (iii). Let $H,H^{\prime},H^{\prime\prime}$ be
infinite hallways and notice that either

$\operatorname{comm}(H,H^{\prime\prime})\subseteq\operatorname{comm}(H,H^{\prime})\qquad\text{or}\qquad\operatorname{comm}(H^{\prime},H^{\prime\prime})\subseteq\operatorname{comm}(H,H^{\prime}).$

To see this, let $n_{XY}=1/d_{S}(X,Y)$ be the number of doorways that hallways
$X$ and $Y$ agree for, and consider the three choices: (a)
$n_{HH^{\prime}}=n_{HH^{\prime\prime}}$, (b)
$n_{HH^{\prime}}>n_{HH^{\prime\prime}}$, or (c)
$n_{HH^{\prime}}<n_{HH^{\prime\prime}}$.

In case (a),
$\operatorname{comm}(H,H^{\prime\prime})=\operatorname{comm}(H,H^{\prime})$
and so
$\operatorname{comm}(H,H^{\prime\prime})\subseteq\operatorname{comm}(H,H^{\prime})$;
in case (b), we must have
$n_{H^{\prime}H^{\prime\prime}}=n_{HH^{\prime\prime}}<n_{HH^{\prime}}$ and so
$\operatorname{comm}(H^{\prime},H^{\prime\prime})\subseteq\operatorname{comm}(H,H^{\prime})$;
and, in case (c), we must have
$n_{H^{\prime}H^{\prime\prime}}=n_{HH^{\prime}}$ which means
$\operatorname{comm}(H^{\prime},H^{\prime\prime})=\operatorname{comm}(H,H^{\prime})$
and so
$\operatorname{comm}(H^{\prime},H^{\prime\prime})\subseteq\operatorname{comm}(H,H^{\prime})$.

Now, for finite hallways $X,Y$ where $X\subset Y$, the set of lines of sight
for $X$ is a superset of the set of lines of sight for $Y$. Thus, the above
set inclusions give us either

$d_{R}(H,H^{\prime\prime})\geq d_{R}(H,H^{\prime})\qquad\text{or}\qquad
d_{R}(H^{\prime},H^{\prime\prime})\geq d_{R}(H,H^{\prime}),$

and so certainly
$d_{R}(H,H^{\prime\prime})+d_{R}(H^{\prime},H^{\prime\prime})\geq
d_{R}(H,H^{\prime})$.

######  Notation 41.

Let $\mathcal{H}$ be the set of all infinite hallways; let $\mathcal{Q}$ be
the set of all infinite periodic hallways that admit lines of sight; let
$\bar{\mathcal{Q}}\subset\mathcal{H}$ be the closure of $\mathcal{Q}$ under
the metric $d_{R}$; and let
$\mathcal{Q}^{c}=\bar{\mathcal{Q}}\backslash\mathcal{Q}$.

It is not immediately obvious that $\mathcal{Q}^{c}$ contains anything at all,
but we will show that $\mathcal{Q}^{c}$ is precisely the set of all aperiodic
hallways admitting lines of sight. Not only that, but we will show that
$\mathcal{Q}^{c}$ is a closed set with respect to $d_{R}$, from which it will
follow that $V$, the visibility function, is upper-semicontinuous.

######  Proposition 42.

The set $\mathcal{Q}^{c}$ is closed with respect to $d_{R}$.

Proof. By definition $\bar{\mathcal{Q}}$ is closed with respect to $d_{R}$.
Thus, if we can show $\mathcal{Q}$ is open with respect to $d_{R}$, the proof
will be complete.

To that end, suppose $H\in\mathcal{Q}$ admits a line of sight
$\ell_{\frac{p}{q}\beta}^{\epsilon}$. We necessarily have that
$\ell_{\frac{p}{q}\beta}^{\epsilon}$ is a line of sight for $H_{k}$ for all
$k$. Thus, $d_{R}(H,H^{\prime})\geq 1/q$ for all $H^{\prime}\neq H$, and so
the singleton $\\{H\\}$ is open with respect to $d_{R}$ (it is the only
element in the $d_{R}$-ball of radius $1/(2q)$ with center $H$). We conclude
that $\mathcal{Q}$ is the union of open sets and is therefore open.

######  Lemma 43.

If $H$ is an infinite hallway that admits a unique line of sight
$\ell_{\alpha\beta}^{\epsilon}$, then the unframed infinite hallway $\bar{H}$
admits $\ell_{\alpha\beta}^{\epsilon}$ as its unique line of sight.

Proof. Let $H$ be an infinite hallway with unique line of sight
$\ell_{\alpha\beta}^{\epsilon}$ and $\bar{H}$ the corresponding unframed
infinite hallway. Notice that the proof of Theorem 27 applies equally well to
unframed infinite hallways, and so the slope of any line of sight for
$\bar{H}$ must be $\alpha$.

Let $(d_{i},d_{i}+1)$ be the $i$th doorway for $H$. Similarly to the proof of
Lemma 32,

$\\{\beta\\}=B=\bigcap_{n\in\mathbb{N}}(\mathrm{proj}_{\alpha}(\\{n\\}\times[d_{i},d_{i}+1]),$

is the complete set of intercepts for the infinite hallway $H$ and is also the
complete set of intercepts for the unframed infinite hallway $\bar{H}$. Thus
$\ell_{\alpha\beta}^{\epsilon}$ is unique.

######  Proposition 44.

Suppose $H$ is an aperiodic infinite hallway admitting a line of sight. Then
$H\in\mathcal{Q}^{c}$.

Proof. Since $H$ is an aperiodic infinite hallway, $H\notin\mathcal{Q}$. To
show $H\in\mathcal{Q}^{c}$, we must show that there is a sequence $H^{(i)}$ of
periodic infinite hallways such that $H^{(i)}\to H$ with respect to $d_{R}$.

Let $\ell_{\alpha\beta}^{\epsilon}$ be the unique line of sight for $H$ and
let $(d_{i},d_{i}+1)$ be the $i$th doorway of $H$. Without loss of generality,
assume $\alpha\in[0,1]$. By Theorem 29, $\alpha\notin\mathbb{Q}$. By Lemma 43,
the unframed infinite hallway $\bar{H}$ admits the unique line of sight
$\ell_{\alpha\beta}^{\epsilon}$.

Recall that $H_{n}$ is the restriction of $H$ to the first $n$ doorways. Fix
$q\in\mathbb{N}$. Now, since there are only a finite number of rationals of
the form $\frac{p}{q}\in[0,1]$, it must be the case that for large enough $n$,
$H_{n}$ admits no line of sight of the form $\ell_{\tfrac{p}{q}\delta}$, lest
$\alpha=\tfrac{p}{q}$. Similarly, for large enough $n$, $\bar{H}_{n}$ admits
no line of sight of the form $\ell_{\tfrac{p}{q}\delta}$.

To complete the proof, notice that since $H_{n}$ is a finite hallway that
admits a line of sight, it admits a rational line of sight
$\ell_{\gamma_{i}\delta_{i}}$. Thus, there exists a periodic infinite hallway
$H^{(n)}$ admitting the line of sight $\ell_{\gamma_{i}\delta_{i}}$ and
satisfying

$H_{n}\subseteq\operatorname{comm}(H^{(n)},H).$

Further, by construction $d_{R}(H^{(n)},H)\to 0$.

An immediate corollary of Proposition 44 is that $\mathcal{Q}^{c}$ is non-
empty. Next, we will show that every hallway in $\mathcal{Q}^{c}$ admits a
line of sight.

######  Lemma 45.

Let $H$ be an infinte hallway and $H_{n}$ be the restriction of $H$ to the
first $n$ doorways. If $H_{n}$ admits a line of sight for every $n$, then the
unframed hallway $\bar{H}$ admits a line of sight.

Proof. For a hallway $K$, let

$A(K)=\\{\alpha:\ell_{\alpha\beta}^{\epsilon}\text{ is a line of sight for
}K\text{ for some }\beta\\}.$

By assumption, $A(H_{n})\neq\emptyset$, and $A(H_{m})\subseteq A(H_{n})$ for
all $m>n$. Further notice that $A(H)=\bigcap_{n\in\mathbb{N}}A(H_{n}).$ Let
$\bar{H}_{n}$ be the unframed hallway corresponding to $H_{n}$. Since
$A(\bar{H}_{n})$ is closed and bounded and $\\{A(\bar{H}_{n})\\}$ satisfies
the finite intersection property,
$A(\bar{H})=\bigcap_{n\in\mathbb{N}}A(\bar{H}_{n})\neq\emptyset$, and so
$\bar{H}$ admits a line of sight.

######  Proposition 46.

If $H\in\mathcal{Q}^{c}$, then $H$ admits a line of sight.

Proof. Let $H\in\mathcal{Q}^{c}$ and suppose the sequence
$H^{(i)}\in\mathcal{Q}$ satisfies $H^{(i)}\to H$ with respect to $d_{R}$. Let
$D_{i}=(d_{i},d_{i}+1)$ be the $i$th doorway of $H$.

Let $|\\!\operatorname{comm}(H^{(n)},H)|$ denote the number of doorways in
$\operatorname{comm}(H^{(n)},H)$. Since $\operatorname{comm}(H^{(n)},H)$
admits a line of sight and is necessarily a finite hallway,
$\operatorname{comm}(H^{(n)},H)$ must admit a rational line of sight with
slope $p/q$ where $q\leq|\\!\operatorname{comm}(H^{(n)},H)|$. Since
$d_{R}(H^{(i)},H)\to 0$, we must have that
$|\\!\operatorname{comm}(H^{(n)},H)|\to\infty$.

Now, by Lemma 45, the unframed hallway $\bar{H}$ must admit a line of sight
$\ell_{\alpha\beta}^{\epsilon}$ since
$H_{k}\subseteq\operatorname{comm}(H^{(n)},H)$ for large enough $n$. Further,
$\alpha\notin\mathbb{Q}$ and so $\ell_{\alpha\beta}^{\epsilon}$ must be
unique.

If we can show that $\ell_{\alpha\beta}^{\epsilon}$ is a line of sight for
$H_{k}$, regardless of $k$, then $\ell_{\alpha\beta}^{\epsilon}$ will be a
line of sight for $H$. Suppose this is not the case, and let $k$ be the
smallest number such that $\ell_{\alpha\beta}^{\epsilon}$ is not a line of
sight for $H_{k}$. Trivially, $k\geq 1$, and since $H^{(n)}\to H$ with respect
to $d_{R}$ and $H_{k}\subseteq\operatorname{comm}(H^{(n)},H)$ for large enough
$n$, we must have that $\ell_{\alpha\beta}^{\epsilon}$ is a line of sight for
$\bar{H}_{k}$.

Since $\ell_{\alpha\beta}^{\epsilon}$ is a line of sight for $H_{k-1}$ but not
for $H_{k}$, we must have either $\alpha k+\beta=d_{k}$ or $\alpha
k+\beta=d_{k}+1$.

Assume $\alpha k+\beta=d_{k}$. Since $\ell_{\alpha\beta}^{\epsilon}$ is not a
line of sight for $H_{k}$, we have that $\ell_{\alpha\beta}+\epsilon$ is not a
line of sight for $H_{k}$. Since $\alpha k+\beta+\epsilon\in D_{k}$, this
means $\ell_{\alpha\beta}+\epsilon$ is not a line of sight for $H_{k-1}$. So,
by Proposition 25, $\ell_{\alpha\beta}-\epsilon$ must be a line of sight for
$H_{k-1}$. We conclude that for some $0\leq i<k$, we must have $\alpha
i+\beta=d_{i}+1$. Thus, $\alpha=\frac{d_{k}-d_{i}-1}{k-i}\in\mathbb{Q}$, which
is a contradiction.

Assuming $\alpha k+\beta=d_{k}+1$, the proof follows similarly.

######  Corollary 47.

If $H\in\bar{\mathcal{Q}}$ then $H$ admits a line of sight.

Proof. By definition $\bar{\mathcal{Q}}=\mathcal{Q}\cup\mathcal{Q}^{c}$. If
$H\in\mathcal{Q}$, then by definition it admits a line of sight and by
Proposition 46, if $H\in\mathcal{Q}^{c}$, $H$ admits a line of sight.

We are almost ready to prove the semi-continuity of $V$. But first, let us
completely characterize the set of hallways that admit lines of sight.

######  Theorem 48.

Let $\mathcal{V}=\\{H\in\mathcal{H}:V(H)=1\\}$ be the set of infinite hallways
that admit lines of sight. Then, $\bar{\mathcal{Q}}=\mathcal{V}$.

Proof. By Corollary 47, $\bar{\mathcal{Q}}\subseteq\mathcal{V}$. Now, suppose
$H\in\mathcal{V}$. If $H$ is a periodic hallway, then $H\in\mathcal{Q}$.

Suppose $H$ is an aperiodic hallway. Since $H$ admits a line of sight, so does
the finite hallway $H_{k}$. Thus $H_{k}$ admits a rational line of sight
$\ell_{\alpha_{k}\beta_{k}}$ where $\alpha_{k}=\frac{p_{k}}{q_{k}}$ by Theorem
29. Let $H^{(k)}$ be the infinite periodic hallway admitting the line of sight
$\ell_{\alpha_{k}\beta_{k}}^{\epsilon}$. We will now show $H^{(k)}\to H$ with
respect to $d_{R}$.

Since $H^{(k)}_{k}=H_{k}$, we have $H^{(k)}\to H$ with respect to $d_{S}$. Let
$\ell_{\frac{p_{k}}{q_{k}}\delta_{n}}$ be a line of sight for $\bar{H}_{k}$
such that $q_{k}$ is as small as possible. If $q_{k}\to\infty$, we are done.
Suppose $\\{q_{k}\\}$ is bounded and let $\bar{D}_{0}=[d_{0},d_{0}+1]$ and
$\bar{D}_{1}=[d_{1},d_{1}+1]$ be the first two doorways of $\bar{H}$. Since
$d_{1}-d_{0}-1\leq\frac{p_{k}}{q_{k}}\leq d_{1}+1-d_{0}$ and there are only
finitely many $q_{k}$, there exists $p/q\in\\{p_{k}/q_{k}:k\in\mathbb{N}\\}$
such that $p/q=p_{k}/q_{k}$ for infinitely many $k$. It follows that
$\mathrm{proj}_{p/q}\bar{H}_{k}$ is a non-empty closed interval for all $k$
and so $\mathrm{proj}_{p/q}\bar{H}$ is non-empty. Thus, $\bar{H}$ admits a
rational line of sight with slope $p/q$, which is a contradiction.

######  Theorem 49.

$V:\mathcal{H}\to\\{0,1\\}$ is upper-semicontinuous with respect to $d_{R}$.

Proof. Let $H^{(n)}\to H$ with respect to $d_{R}$ and suppose $V(H^{(n)})=1$.
By Theorem 48, $H^{(n)}\in\bar{\mathcal{Q}}$, and so by definition
$H\in\bar{\mathcal{Q}}$. Now, by Corollary 47, $V(H)=1$.

##  4\. Applications of $d_{R}$

Theorem 27 states that if an infinite hallway admits a line of sight, its
slope is unique. Thus, we may define a function
$s:\bar{\mathcal{Q}}\to\mathbb{R}$ by

$s(H)=\alpha\text{ where }\ell_{\alpha\beta}^{\epsilon}\text{ is a line of
sight for }H.$

Let $s^{-1}$ be the set-valued right-inverse to $s$. That is

$s^{-1}(\alpha)=\\{H:s(H)=\alpha\\},$

and we have the equality $s\circ s^{-1}=\mathrm{id}$. Now, any metric $d$ on
infinite hallways induces a metric $\tilde{d}$ on $\mathbb{R}$ via

$\tilde{d}(\alpha,\gamma)=d(s^{-1}(\alpha),s^{-1}(\gamma)).$

Two metrics $d_{X}$ and $d_{Y}$ are said to be _equivalent_ if their
convergent sequences are the same. That is, $d_{X}(x_{i},x)\to 0$ if and only
if $d_{Y}(x_{i},x)\to 0$ for all sequences $(x_{i})$.

######  Proposition 50.

The metric $\tilde{d}_{S}$ on $\mathbb{R}$ induced by the metric $d_{S}$ is
equivalent to the standard metric $d$ on $\mathbb{R}$ given by
$d(\alpha,\gamma)=|\alpha-\gamma|$.

Proof. We will first show that convergence in $d$ implies convergence in
$\tilde{d}_{S}$. Let $(x_{i})$ be a sequence and suppose
$d(x_{i},x)=|x_{i}-x|\to 0$. Fix $k>0$ and let $H_{k}$ be a finite hallway
with doorways $D_{i}$ admitting a line of sight $\ell_{x\beta}$ for some
$\beta$. Now, for any $y\in\mathbb{R}$, define

$D^{y}=\bigcap_{i\leq k}\mathrm{proj}_{y}(\\{i\\}\times D_{i})$

and note that $D^{y}=(l^{y},r^{y})$ is always an open interval or the empty
set. Further, $D^{x_{i}}\to D^{x}$ in the sense that $l^{x_{i}}\to l^{x}$ and
$r^{x_{i}}\to r^{x}$. Necessarily we have $\beta\in D^{x}$, but we also see
that since $D^{x_{i}}\to D^{x}$, for all large enough $i$, we have $\beta\in
D^{x_{i}}$. Thus, for large enough $i$, $\ell_{x_{i}\beta}$ and
$\ell_{x\beta}$ are lines of sight for $H_{k}$ and so
$\tilde{d}_{S}(x_{i},x)\leq 1/k$. But $k$ was arbitrary, so
$\tilde{d}_{S}(x_{i},x)\to 0$.

Now, suppose $\tilde{d}_{S}(x_{i},x)\to 0$. Fix $k>0$. Now for all
sufficiently large $i$, $\tilde{d}_{S}(x_{i},x)\leq 1/k$. Supposing $i$ is
sufficiently large, we necessarily have that for some $\beta,\beta_{i}$, there
exists a $k$-hallway, $H_{k}$, for which $\ell_{x\beta}$ and
$\ell_{x_{i}\beta_{i}}$ are both lines of sight. In particular,
$\ell_{x\beta}$ and $\ell_{x_{i}\beta_{i}}$ both pass through the $k$th
doorway of $H_{k}$ and so

$|(kx+\beta)-(kx_{i}+\beta_{i})|\leq 1.$

By the reverse triangle inequality we have

$k|x-x_{i}|-|\beta-\beta_{i}|\leq|(kx+\beta)-(kx_{i}+\beta_{i})|\leq 1.$

Since $\ell_{x\beta}$ and $\ell_{x_{i}\beta_{i}}$ both pass through the
initial doorway of $H_{k}$, we know $|\beta-\beta_{i}|\leq 1$ and so
$k|x-x_{i}|\leq 2$. Thus, $|x-x_{i}|\leq 2/k$ and so, since $k$ was arbitrary,
$|x-x_{i}|\to 0$.

The metric $\tilde{d}_{S}$ is equivalent to what we are used to in a metric on
$\mathbb{R}$, but the metric $\tilde{d}_{R}$ is much stranger.

######  Proposition 51.

The set $\mathbb{R}\backslash\mathbb{Q}$ of irrational numbers is closed with
respect to $\tilde{d}_{R}$.

Proof. Suppose $(x_{i})$ is a sequence of irrational real numbers and
$x\in\mathbb{Q}$. Further, suppose $\tilde{d}_{R}(x_{i},x)\to 0$. This implies
the existence of hallways $H^{(i)}\in s^{-1}(x_{i})$ so that $H^{(i)}\to H\in
s^{-1}(x)$ with respect to $d_{R}$. However, since $x\in\mathbb{Q}$, $H$ is a
periodic infinite hallway, and so by Proposition 42, $H^{(i)}\not\to H$, a
contradiction.

The set $\mathbb{R}\backslash\mathbb{Q}$ is clearly not closed under
$\tilde{d}_{S}$. We now have an unusual situation. The set $\mathbb{Q}$ is
dense in $\mathbb{R}$ (its closure is $\mathbb{R}$) under both $\tilde{d}_{S}$
and $\tilde{d}_{R}$, however $\mathbb{R}\backslash\mathbb{Q}$ is dense in
$\mathbb{R}$ under $\tilde{d}_{S}$, but not $\tilde{d}_{R}$. Stranger still,
according to the following proposition, $\tilde{d}_{R}$ does not change very
much.

######  Proposition 52.

The metrics $\tilde{d}_{R}$ and $\tilde{d}_{S}$ are equivalent when restricted
to the set $\mathbb{R}\backslash\mathbb{Q}$ of irrational numbers.

Proof. First note that convergence in $d_{R}$ implies convergence in $d_{S}$
since $d_{R}(H^{(i)},H)\to 0$ implies
$|\operatorname{comm}(H^{(i)},H)|\to\infty$. Thus convergence in
$\tilde{d}_{R}$ implies convergence in $\tilde{d}_{S}$.

Now, fix $\alpha\in\mathbb{R}\backslash\mathbb{Q}$ and $q\in\mathbb{N}$ and
choose $\kappa>0$ so that the interval

$B_{\kappa}(\alpha)=(\alpha-\kappa,\alpha+\kappa)\subset\mathbb{R}$

contains no rational points with denominator less than $q$. Since
$\tilde{d}_{S}$ is equivalent to the standard metric on $\mathbb{R}$, there
exists a $k$ so that $\tilde{d}_{S}(\alpha,\gamma)<1/k$ implies $\gamma\in
B_{\kappa}(\alpha)$.

Now, if $H$ is an infinite hallway admitting a line of sight of slope
$\alpha$, then $d_{S}(H,H^{\prime})<1/k$ implies $d_{R}(H,H^{\prime})\leq
1/q$. Since $q$ was arbitrary, if sequence of hallways converges to $H$ with
respect to $d_{S}$, the same sequence converges to $H$ with respect to
$d_{R}$. Thus, a sequence converging to $\alpha$ with respect to
$\tilde{d}_{S}$ converges to $\alpha$ with respect to $\tilde{d}_{R}$. This
holds on all of $\mathbb{R}$ so long as
$\alpha\in\mathbb{R}\backslash\mathbb{Q}$, and therefore it holds on all of
$\mathbb{R}\backslash\mathbb{Q}$.

We can also use $d_{R}$ to induce a metric on the set of sequences,
$\mathbb{Z}^{\mathbb{N}}$, and in particular, the set of Sturmian sequences.

######  Theorem 53.

For an infinite hallway $H$, $\Phi(H)$ is a Sturmian sequence if and only if
$H$ admits an infinite line of sight $\ell_{\alpha\beta}^{\epsilon}$ with
$\alpha\in[0,1]$.

Proof. Suppose $H$ is an infinite hallway with doorways $D_{i}$. Further,
suppose $\Phi(H)$ is a Sturmian sequence. Then
$\Phi(H)=\mathbf{R}_{\left\lfloor{\cdot}\right\rfloor}(\alpha,\beta)$ or
$\Phi(H)=\mathbf{R}_{\left\lceil{\cdot}\right\rceil}(\alpha,\beta)$ for some
$\alpha,\beta\in[0,1]\times\mathbb{R}$. If
$\Phi(H)=\mathbf{R}_{\left\lfloor{\cdot}\right\rfloor}(\alpha,\beta)$ then,
because we assume the initial doorway of $H$ is $D_{0}=(0,1)$, we have

$D_{i}=(\left\lfloor{i\alpha+\beta}\right\rfloor,\left\lfloor{i\alpha+\beta}\right\rfloor+1).$

Similarly, if
$\Phi(H)=\mathbf{R}_{\left\lceil{\cdot}\right\rceil}(\alpha,\beta)$,

$D_{i}=(\left\lceil{i\alpha+\beta}\right\rceil,\left\lceil{i\alpha+\beta}\right\rceil+1).$

In either case, $H$ admits the infinite line of sight
$\ell_{\alpha\gamma}^{\epsilon}$ where $\gamma=\beta\ \mathrm{mod}\ 1$.

Now suppose that $H$ admits the infinite line of sight
$\ell_{\alpha\beta}^{\epsilon}$. By Proposition 25,
$(\ell_{\alpha\beta}+\epsilon)\cap H=\emptyset$ or
$(\ell_{\alpha\beta}-\epsilon)\cap H=\emptyset$. Suppose
$(\ell_{\alpha\beta}+\epsilon)\cap H=\emptyset$. Then

$D_{i}=(\left\lfloor{i\alpha+\beta}\right\rfloor,\left\lfloor{i\alpha+\beta}\right\rfloor+1)$

and so $\Phi(H)=\mathbf{R}_{\left\lfloor{\cdot}\right\rfloor}(\alpha,\beta)$.
Alternatively, suppose $(\ell_{\alpha\beta}-\epsilon)\cap H=\emptyset$. Then

$D_{i}=(\left\lceil{i\alpha+\beta}\right\rceil,\left\lceil{i\alpha+\beta}\right\rceil+1)$

and so $\Phi(H)=\mathbf{R}_{\left\lceil{\cdot}\right\rceil}(\alpha,\beta)$. In
either case, $\Phi(H)$ is a rotation sequence and therefore a Sturmian
sequence.

Recall that $\Omega=\Phi(\\{H:V(H)=1\\})$. In light of Theorem 53,
$\mathcal{S}=\Omega\cap\\{0,1\\}^{\mathbb{N}}$ is the set of all Sturmian
sequences. $\mathcal{S}$ is $T$-invariant ($T(\mathcal{S})=\mathcal{S}$), but
it is not closed with respect to the standard metric. Let $\hat{d}_{R}$ be the
metric on sequences induced by $d_{R}$. Again, $\hat{d}_{R}$ induces the same
topology on $\mathcal{S}$ as $d$, the standard metric on sequences, however
under $\hat{d}_{R}$, $\mathcal{S}$ is closed, and the set of periodic Sturmian
sequences is dense.

## References

  * [1] J. Berstel and M. Pocchiola.  A geometric proof of the enumeration formula for Sturmian words.  Internat. J. Algebra Comput., 3(3):349–355, 1993.
  * [2] N. P. Fogg.  Substitutions in dynamics, arithmetics and combinatorics, volume 1794 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2002.  Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel.
  * [3] J.-M. Gambaudo, O. Lanford, III, and C. Tresser.  Dynamique symbolique des rotations.  C. R. Acad. Sci. Paris Sér. I Math., 299(16):823–826, 1984.
  * [4] M. Lothaire.  Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications.  A collective work by Jean Berstel, et al.
  * [5] G. A. H. Marston Morse.  Symbolic dynamics.  American Journal of Mathematics, 60(4):815–866, 1938.
  * [6] F. Mignosi.  On the number of factors of Sturmian words.  Theoret. Comput. Sci., 82(1, Algorithms Automat. Complexity Games):71–84, 1991.