*

|  Muon Ionization Cooling Experiment |

---|---|---

Beam-based detector alignment in the MICE muon beam line
François Drielsma\dagger\dagger$\dagger$University of Geneva

> The Muon Ionization Cooling Experiment (MICE) will perform a detailed study
> of ionization cooling to evaluate the feasibility of the technique. To carry
> out this program, MICE requires all of its detectors to reconstruct space
> points in a globally consistent fashion. The beam-based alignment constants
> were found to be more accurate than the survey for the scintillating-fibre
> trackers lodged inside the bores of the superconducting magnets. This
> alignment algorithm can achieve unbiased measurements of the trackers
> rotation angles with a resolution of 6 mrad/$\sqrt{N}$ and of their position
> with a resolution of 20 mm/$\sqrt{N}$, with $N$ the number of selected
> tracks.

##  1 Introduction

Intense muon sources are required for a future Neutrino Factory or Muon
Collider [1, 2]. At production, muons occupy a large phase-space volume
(emittance), which makes them difficult to accelerate and store. Therefore,
the emittance of the muon beams must be reduced, i.e the muons must be
“cooled”, to maximise the muon flux delivered to the accelerator. Conventional
cooling techniques applied to muon beams [3] would leave too few muons to be
accelerated since the muon lifetime is short ($\tau_{\mu}\sim 2.2\,\mu$s).
Simulations indicate that the ionization-cooling effect builds quickly enough
[4] to deliver the flux and emittance required by the Neutrino Factory and the
Muon Collider [5, 6]. The MICE collaboration will study ionization cooling in
detail to demonstrate the feasibility of the technique [7].

###  1.1 The Muon Ionization Cooling Experiment

A schematic of the MICE Muon Beam (MMB) and the MICE experiment is shown in
figure 1 and described in detail in [8, 9]. The MMB operates on the ISIS
proton synchrotron [10] at the Rutherford Appleton Laboratory. A titanium
target [11] samples the ISIS proton beam, producing pions. The pions are
transported by the upstream quadrupoles, Q1–3, and are momentum-selected at
the first dipole, D1. The high field present in the Decay Solenoid (DS)
contains the pions to allow them to decay into muons. The second dipole, D2,
is used to momentum-select a ‘muon’ beam with high purity or a ‘pion’ beam
containing a mix of muons, pions and electrons. The resultant beam is
transported through two quadrupole triplets, Q4–6 and Q7–9, time-of-flight
counters [12], TOF0 and TOF1, and Cherenkov detectors, Ckov [13], to the
cooling cell. The beam emittance is inflated as it passes through the
variable-thickness brass and tungsten ‘diffuser’ and is measured in the
upstream spectrometer solenoid using a scintillating-fibre tracker. The beam
then passes through low-$Z$ absorbers and RF cavities prior to being sampled
in the downstream tracker. Upon exiting the cooling cell, the beam is incident
upon the final time-of-flight detector, TOF2 [14], a pre-shower detector, KL
[15], and the Electron-Muon Ranger, EMR [16].

Figure 1: (a) Cross-sectional and (b) side views of the MICE Muon Beam Line
(MMB) and the MICE experiment. The two scintillating fibre trackers are
embedded inside the spectrometer solenoids.

The particle identification system consists of the TOF0, TOF1 and TOF2, Ckov,
KL and EMR detectors, which can conceptually be split into two: TOF0–1 and
Ckov identifying particle species prior to the cooling cell and TOF2, KL and
EMR identifying species after the cooling cell. In combination with time-of-
flight information, the EMR is used to distinguish between muons that have
successfully traversed the full cooling cell from those that have decayed en-
route. This aids in the measurement of beam transmission through the cooling
cell, as well as reducing the uncertainty on the emittance measurement.

MICE is a single-particle experiment. The emittance reduction is measured by
measuring $(x,y,p_{x},p_{y},p_{z})$ of each muon before and after going
through the absorber. A sufficient amount of tracks are accumulated during
data taking and a sample is assembled during the analysis process to measure
the RMS emittance reduction. The single-particle nature of the experiment
requires reliable global track matching throughout, i.e. the ability to
associate a trace measured in the upstream tracker with one in the downstream
tracker but also with the PID detectors. The detectors must reconstruct space
points in a globally consistent fashion to guarantee reliable and efficient
track matching.

###  1.2 Surveys

The baseline for the beam-based alignment is the surveys of the detectors in
the hall using laser telemetry. Surveys were performed regularly throughout
the MICE Step IV commissioning phase and data taking period. The TOF1 time-of-
flight hodoscope was moved periodically to access the upstream end of the
superconducting solenoids and resurveyed systematically. The downstream PID
detectors module, composed of TOF2, the KL and the EMR, was also repositioned
on occasion. The focus coil module was moved in and out of the beam line to
change absorbers. Each of these events was followed by a complete resurvey.

The PID detectors are each equipped with at least four survey monuments and
are surveyed directly [17, 18, 19, 20]. The two scintillating fibre trackers,
nested in the superconducting solenoids, can not be accessed directly. The
upstream and downstream flanges of each solenoid are surveyed and the end
plate of the trackers are surveyed with respect to the flanges [21]. The
estimated position of the trackers within the bores are inferred from these
measurements. A laser theodolite is used to locate the monuments with respect
to the datum point situated under the second dipole magnet, D2. The surveyed
positions of the detectors for the 2017/01 ISIS user cycle are summarized in
table 1.1. Figure 3 shows a picture of TOF2 and the location of its survey
monuments.

|  $x_{M}$ [mm] |  $y_{M}$ [mm] |  $z_{M}$ [mm] |  $\alpha_{M}$ [mrad] |  $\beta_{M}$ [mrad] |  $\gamma_{M}$ [mrad]
---|---|---|---|---|---|---
TOF0 | 1.919 | 1.565 | 5287.247 | 6.030 | 5.252 | 3.718
TOF1 | -3.738 | -0.913 | 12929.563 | -5.083 | 0.033 | 2.768
TKU | 0.761 | 2.732 | 14515.055 | 2.669 | -0.041 | 0.000
TKD | -1.027 | 8.943 | 19398.921 | -6.435 | 1.283 | 0.000
TOF2 | 13.518 | -10.981 | 21139.375 | 10.735 | 6.699 | -1.406
KL | 16.616 | -12.855 | 21221.649 | 8.717 | 7.994 | -9.841
EMR | 35.647 | 7.827 | 21937.889 | -2.527 | 6.857 | -0.118
Table 1.1: Survey of the detectors in the MICE hall with respect to the datum
point at D2 during the 2017/01 ISIS user cycle. The bold figures are the ones
sensitive to the beam-based detector alignment.

Figure 2: Picture of the TOF2 time-of-flight hodoscope and its four survey
monuments labelled TOF2.1–2.4.

Figure 3: Disposition of the downstream tracker stations along with the CMM
measurements of their position with respect to the reference axis.

Before being placed inside the magnets, each tracker was surveyed
independently using a coordinate-measuring machine (CMM). This ensures that
the position of the five stations is well known within each tracker with
respect to the end plate. Figure 3 shows the disposition of the stations in
the downstream scintillating fibre tracker and their position as measured by
the CMM. The reference position is the axis that joins the centre of station 1
to the centre of station 5. The positions of stations 1 to 3 are measured with
respect to that axis. The beam can be used to check the tracker station
alignment.

Special care is taken during the installation of the trackers within the
magnet bores. The installation platform is adjustable to enable the tracker to
be aligned with the bore of the solenoid. The tracker sits on four adjustable
feet, two at each end. The adjustable feet are used to align the tracker with
the magnetic axis of the solenoid. Once this has been done, the location
bracket is fitted. The location bracket locks the tracker in its $z$ and
azimuthal positions.

##  2 Analysis method

The beam based alignment was initially designed as a consistency check of the
detector surveys. The tracking detectors (i.e. the two scintillating fibre
trackers and the EMR) are used to extract a straight track fit, propagate the
track into other adjacent detectors and compare the predicted position with
the measured position. Reliable surveys should yield mean residuals of zero.

It was found that, although the EMR tracks match when propagated to other
downstream PID detectors, the tracker tracks do not. A data driven analysis
was developed to extract the position and rotations of the two trackers in to
the global coordinate system. As the space points reconstructed by PID
detectors are globally consistent with their surveyed position, the TOF1 to
TOF2 detectors are chosen to construct a reference axis with respect to which
to align the trackers.

This section defines the nomenclature used for the alignment constants and
describes the measurements required to perform the beam-based alignment.

###  2.1 Module placement

Each detector is defined as a module in the MICE geometry. A module describes
where the elements that compose the detector are placed with respect to the
detector centre, i.e. in local coordinates. The placement of the module in
global coordinates is entirely defined by the location of its centre
$(x_{\mathrm{M}},y_{\mathrm{M}},z_{\mathrm{M}})$ and a set of Tait-Bryan
angles $(\alpha,\beta,\gamma)$. The rotation about $x$, $\alpha$, is called
pitch, about $y$, $\beta$, is called yaw and about $z$, $\gamma$, is called
roll. For a set of local coordinates $(x,y,z)$, the global coordinates are
reconstructed as

$\begin{pmatrix}\xi\\\ \upsilon\\\
\zeta\end{pmatrix}=\mathcal{R}\begin{pmatrix}x\\\ y\\\
z\end{pmatrix}+\begin{pmatrix}x_{\mathrm{M}}\\\ y_{\mathrm{M}}\\\
z_{\mathrm{M}}\end{pmatrix}\,,$ (2.1.1)

with $\mathcal{R}$ the module rotation matrix. In the small angle
approximation, which is an excellent working hypothesis considering the
surveys, $\sin\theta\sim\theta$ and $\cos\theta\sim 1$, which yields a matrix
of the form:

$\mathcal{R}=R_{x}R_{y}R_{z}=\begin{pmatrix}1&0&0\\\ 0&1&-\alpha\\\
0&\alpha&1\end{pmatrix}\begin{pmatrix}1&0&\beta\\\ 0&1&0\\\
-\beta&0&1\end{pmatrix}\begin{pmatrix}1&-\gamma&0\\\ \gamma&1&0\\\
0&0&1\end{pmatrix}=\begin{pmatrix}1&-\gamma&\beta\\\
\gamma+\alpha\beta&1&-\alpha\\\
-\beta+\alpha\gamma&\alpha-\beta\gamma&1\end{pmatrix}\,.$ (2.1.2)

This matrix is obtained in the MAUS (MICE Analysis User Software) conventions
of performing the rotation about $z$ first, then $y$, then $x$. Getting rid of
the second order ($\sim\theta^{2}$) corrections, the matrix simplifies to

$\mathcal{R}=\begin{pmatrix}1&-\gamma&\beta\\\ \gamma&1&-\alpha\\\
-\beta&\alpha&1\end{pmatrix}\,.$ (2.1.3)

Using this expression of the rotation matrix, equation 2.1.1 can be rewritten
as

$\begin{pmatrix}\xi\\\ \upsilon\\\ \zeta\end{pmatrix}=\begin{pmatrix}x-\gamma
y+\beta z+x_{\mathrm{M}}\\\ y+\gamma x-\alpha z+y_{\mathrm{M}}\\\ z-\beta
x+\alpha y+z_{\mathrm{M}}\end{pmatrix}\,.$ (2.1.4)

For each detector, there are six potential unknowns:
$(x_{\mathrm{M}},y_{\mathrm{M}},z_{\mathrm{M}},\alpha,\beta,\gamma)$. Some
simplifications can be made to lower the amount of unknowns. The $z_{M}$
coordinate of each detector and the
$(x_{\mathrm{M}},y_{\mathrm{M}},\alpha,\beta,\gamma)$ coordinates of the PID
detectors are known to great accuracy from the survey. The scintillating fibre
trackers are challenging to survey due to their embedding in the two
spectrometer solenoids. The beam-based detector alignment is critical to find
the $(x_{\mathrm{M}},y_{\mathrm{M}},\alpha,\beta,\gamma)$ constants for each
tracker.

###  2.2 Sought after measurements

The location of the TOFs is known to great accuracy and are used as the
reference for the tracker alignment. The line that joins the centre of TOF1
with the centre of TOF2 is chosen to be the reference axis. A deviation from
this axis is considered as a misalignment of the trackers.

Multiple scattering in the beam line does not allow to do the alignment on
single particle basis but works for a larger sample of particles. The mean
residual angles and positions of tracker $t=u,d$ with respect to the TOF12
axis are an essential and powerful tool to infer the correction factors
$(x_{T},y_{T},\alpha_{T},\beta_{T},\gamma_{T})$.

Each TOF provides a single space point in the global coordinate system
$(\xi_{i},\upsilon_{i},\zeta_{i})$ with $i$ the ID of the TOF. This position
is assumed to be the true position with a large uncertainty due to the limited
granularity of the detector ($\sigma_{x}\sim\sigma_{y}\sim 17$ mm). The
gradients of the track between the two TOFs are reconstructed as:

$\psi^{\prime}_{12}=\frac{\psi_{2}-\psi_{1}}{\zeta_{2}-\zeta_{1}},\,\psi=\xi,\upsilon.$
(2.2.1)

The extrapolated position of the TOF reference track in the centre of tracker
$t=u,d$ is

$\psi_{12}^{t}=\psi_{1}+\frac{\psi_{2}-\psi_{1}}{\zeta_{2}-\zeta_{1}}(\zeta_{T}-\zeta_{1})=(1-\chi_{T})\psi_{1}+\chi_{T}\psi_{2},\,\psi=\xi,\upsilon,$
(2.2.2)

with $\chi_{\mathrm{T}}=(\zeta_{T}-\zeta_{1})/(\zeta_{2}-\zeta_{1})$, the
fractional distance from TOF1 to the tracker centre.

Tracker $t=u,d$ samples the particle track in five different stations
$(x_{t}^{j},y_{t}^{j},z_{t}^{j})$, with $j=1,\dots,5,$. This allows for the
reconstruction of a straight track with gradients $x^{\prime}_{t}$ (resp.
$y^{\prime}_{t}$) in the $xz$ (resp. $yz$) projection and its position at the
centre, $(x_{t},y_{t},0)$. No assumption is made on the prior position of the
tracker and hence the coordinates and gradients are returned in local
coordinates, i.e. assuming a tracker perfectly aligned with the beam axis,
whose centre lies at $z=0$.

Using the rotation matrix in equation 2.1.4, the position of the track in the
global coordinate system at the level of the tracker centre reads

$\begin{pmatrix}\xi_{t}\\\ \upsilon_{t}\\\
\zeta_{t}\end{pmatrix}=\begin{pmatrix}x_{t}-\gamma_{\mathrm{T}}y_{t}+x_{T}\\\
y_{t}+\gamma_{\mathrm{T}}x_{t}+y_{T}\\\
\beta_{T}x_{t}+\alpha_{T}y_{t}+z_{T}\end{pmatrix}.$ (2.2.3)

A local increment of $(dx_{t},dy_{t},dz_{t})$ in a tracker translates to
global increments of

$\begin{pmatrix}d\xi_{t}\\\ d\upsilon_{t}\\\
d\zeta_{t}\end{pmatrix}=\begin{pmatrix}dx_{t}-\gamma_{T}dy_{t}+\beta_{T}dz_{t}\\\
dy_{t}+\gamma_{T}dx_{t}-\alpha_{T}dz_{t}\\\
dz_{t}-\beta_{T}dx_{t}+\alpha_{T}dy_{t}\end{pmatrix},$ (2.2.4)

which in turn correspond to global gradients of

$\begin{gathered}\xi^{\prime}_{t}=\frac{d\xi_{t}}{d\zeta_{t}}=\frac{dx_{t}-\gamma_{T}dy_{t}+\beta_{T}dz_{t}}{dz_{t}\left(1-\beta_{T}x^{\prime}_{t}+\alpha_{T}y^{\prime}_{t}\right)}\simeq
x^{\prime}_{t}-\gamma_{T}y^{\prime}_{t}+\beta_{T},\\\
\upsilon^{\prime}_{t}=\frac{d\upsilon_{t}}{d\zeta_{t}}=\frac{dy_{t}+\gamma_{T}dx_{t}-\alpha_{T}dz_{t}}{dz_{t}\left(1-\beta_{T}x^{\prime}_{t}+\alpha_{T}y^{\prime}_{t}\right)}\simeq
y^{\prime}_{t}+\gamma_{T}x^{\prime}_{t}-\alpha_{T}.\end{gathered}$ (2.2.5)

In global coordinates, on average, the track reconstructed between TOF1 and
TOF2 should agree with the track reconstructed in either tracker, i.e. the
mean residuals should be zero. For example, take the following residual
gradient:

$\displaystyle\langle\xi^{\prime}_{t}-\xi^{\prime}_{12}\rangle=0$
$\displaystyle\iff\langle
x^{\prime}_{t}-\gamma_{T}y^{\prime}_{t}+\beta_{T}-\xi^{\prime}_{12}\rangle=0$
$\displaystyle\iff\langle
x^{\prime}_{t}-\xi^{\prime}_{12}\rangle=\langle\gamma_{T}y^{\prime}_{t}-\beta_{T}\rangle$
$\displaystyle\iff\langle
x^{\prime}_{t}-\xi^{\prime}_{12}\rangle=\gamma_{T}\langle
y^{\prime}_{t}\rangle-\beta_{T}.$ (2.2.6)

with $\langle x\rangle$ the average of $x$. Equation 2.2.6 uses the linearity
of the mean, i.e. $\langle ax+by\rangle=a\langle x\rangle+b\langle y\rangle$,
$a$ and $b$ constants. $\langle x^{\prime}_{t}-\xi^{\prime}_{12}\rangle$ is
the mean residual between the local angle measured in the tracker,
$x^{\prime}_{t}$, and the global angle reconstructed between TOF1 and TOF2,
$\xi^{\prime}_{12}$. The value $\langle y^{\prime}_{t}\rangle$ is the mean
gradient is the $yz$ projection. Both of the aforementioned means can be
measured with a resolution progressing as $1/\sqrt{N}$.

Applying the same reasoning to the other three parameters yields the following
system of four equations equations with five unknowns:

$\left\\{\begin{array}[]{l}\langle
x^{\prime}_{t}-\xi^{\prime}_{12}\rangle=\gamma_{T}\langle
y^{\prime}_{t}\rangle-\beta_{T}\\\\[5.69046pt] \langle
y^{\prime}_{t}-\upsilon^{\prime}_{12}\rangle=-\gamma_{T}\langle
x^{\prime}_{t}\rangle+\alpha_{T}\\\\[5.69046pt] \langle
x_{t}-\xi_{12}^{t}\rangle=\gamma_{T}\langle y_{t}\rangle-x_{T}\\\\[5.69046pt]
\langle y_{t}-\upsilon_{12}^{t}\rangle=-\gamma_{T}\langle x_{t}\rangle-
y_{T}\end{array}\right..$ (2.2.7)

The roll dependant terms in the equations have but a small influence on the
measurement of the other parameters. The roll of the trackers is constrained –
by the supports they are mounted on – to values of order 1 mrad within the
magnet bores. The mean gradients and positions after selection are of order 1
mrad and 10 mm in the worst settings. The systematic error in angle on
$\alpha_{T}$ and $\beta_{T}$ from the roll, $\gamma_{T}$, is
$\mathcal{O}(10^{-3})$ mrad and in position on $x_{T}$ and $y_{T}$ is
$\mathcal{O}(10^{-2})$ mm. These values are one order of magnitude smaller
than the statistical error.

One way to disentangle the roll, $\gamma_{T}$, from the yaw, $\beta_{T}$, in
the first equation is to bin out $y^{\prime}_{t}$ and measure $\langle
x^{\prime}_{t}-\xi^{\prime}_{12}\rangle$ as a function of it. A first order
fit of the output distribution yields $\gamma_{T}$ as its gradient and
$-\beta_{T}$ as its $y$-intercept. The same deconvolution can be performed for
the other three equations and provides redundant measurements of the roll.

An attempt at measuring the roll, $\gamma_{T}$, using this method was
inconclusive. The statistical uncertainty for a single measurement was of
order 10 mrad, one order of magnitude larger than the expected roll itself.
The roll was ignored in this analysis due to its negligible influence on
global track reconstruction.

##  3 Sample selection

The method described in the previous section assumes that the mean residuals
can be measured with great accuracy and, more importantly, are unbiased. A
bias in one of the residual distributions inevitably introduces a bias in the
measurement of the alignment parameters. The method also assumes isotropic
scattering and inefficiencies in the detectors involved.

###  3.1 Sampling bias

The main source of bias is the Multiple Coulomb Scattering (MCS) in the
material between TOF1 and TOF2. The particles used in the alignment go through
15 planes of scintillating fibre in each tracker, the aluminium windows of the
spectrometer solenoids and focus coil absorber module and the helium contained
in the bore of the magnets. In the absence of MCS, particles go down a
straight path between the two detectors and are sampled in the two trackers in
a fully nonstochastic fashion.

MCS introduces straggling and an uncertainty on the exact path taken by a
particle between the two TOFs. Assume a perfectly Gaussian sample of particles
first measured at a given $z_{0}$. In one dimension, the true position is
distributed as $x_{0}\sim\mathcal{N}(\overline{x},\sigma_{x}^{2})$ and the
true gradient is distributed as
$x^{\prime}_{0}\sim\mathcal{N}(\overline{x^{\prime}},\sigma_{x^{\prime}}^{2})$.
With material at $z_{0}$, the true distributions at a more downstream position
$z_{1}$ are

$\begin{array}[]{l}x_{1}\sim\mathcal{N}\left(\overline{x}+\overline{x^{\prime}}z_{01},\,\sigma_{x}^{2}+\sigma_{x^{\prime}}^{2}z_{01}^{2}+\theta_{0,0}^{2}z_{01}^{2}\right),\\\\[5.69046pt]
x^{\prime}_{1}\sim\mathcal{N}\left(\overline{x^{\prime}},\,\sigma_{x^{\prime}}^{2}+\theta_{0,0}^{2}\right),\end{array}$
(3.1.1)

with $z_{01}=z_{1}-z_{0}$. An expression for the RMS scattering angle at
$z_{0}$, $\theta_{0,0}$, can be found in [22]:

$\theta_{0,0}=\frac{13.6\,\text{MeV}}{\beta
pc}\sqrt{dz_{0}/X_{0,0}}\left[1+0.038\ln(dz_{0}/X_{0,0})\right],$ (3.1.2)

with $\beta=v/c$ and $p$ respectively the particle velocity and momentum and
$dz_{0}/X_{0,0}$ the thickness of the material encountered at $z_{0}$ in
radiation lengths, $X_{0,0}$.

For each position $z_{i}$ where the sample encounters material, we account for
an RMS scattering angle $\theta_{0,i}$. This yields, at the final measurement
point $z_{n}$,

$\begin{array}[]{l}x_{n}\sim\mathcal{N}\left(\overline{x}+\overline{x^{\prime}}z_{0n},\,\sigma_{x}^{2}+\sigma_{x^{\prime}}^{2}z_{0n}^{2}+\sum_{i=0}^{n-1}\theta_{0,i}^{2}(z_{i+1}-z_{i})^{2}\right),\\\\[5.69046pt]
x^{\prime}_{n}\sim\mathcal{N}\left(\overline{x^{\prime}},\,\sigma_{x^{\prime}}^{2}+\sum_{i=0}^{n-1}\theta_{0,i}^{2}\right),\end{array}$
(3.1.3)

with $z_{0n}=z_{n}-z_{0}$. A non-zero mean gradient, $\overline{x^{\prime}}$,
moves the position distribution by $\overline{x^{\prime}}z_{0n}$, and a spread
in gradient translates in a growing spread in position. MCS smears both
distributions but preserves the mean. The RMS effective scattering angle,
$\theta_{0}$, and effective distance, $\Delta z$, are defined as

$\begin{array}[]{l}\theta_{0}=\sqrt{\sum_{i=0}^{n-1}\theta_{0,i}^{2}},\\\
\Delta
z=\sqrt{\frac{\sum_{i=0}^{n-1}\theta_{0,i}^{2}(z_{i+1}-z_{i})^{2}}{\sum_{i=0}^{n-1}\theta_{0,i}^{2}}}.\end{array}$
(3.1.4)

The residuals between the measured and extrapolated distributions are
distributed as

$\begin{array}[]{l}x_{n}-x_{0}^{n}=x_{n}-(x_{0}+x^{\prime}_{0}z_{0n}))\sim\mathcal{N}\left(0,\theta_{0}^{2}\Delta
z^{2}\right),\\\\[5.69046pt]
x^{\prime}_{n}-x^{\prime}_{0}\sim\mathcal{N}(0,\theta_{0}^{2}),\end{array}$
(3.1.5)

with $x_{0}^{n}$ the track at $z_{0}$ propagated to $z_{n}$. The only source
of uncertainty on these residuals is the MCS.

Assume that both distributions are measured at $z_{0}$ and $z_{n}$. $x_{0}$ is
measured correctly but $x_{n}$ has a non zero misalignment $\delta x_{n}$. The
mean residual between the two measurements reads

$\langle x_{n}-\delta x_{n}-x_{n0}\rangle=\langle
x_{n}-(x_{0}+x^{\prime}_{0}(z_{n}-z_{0}))\rangle-\delta x_{n}=-\delta
x_{n}.\\\ $ (3.1.6)

True distributions are inherently unbiased in the measurement of $\delta
x_{n}$. The problem comes from the sampling of the distribution. A tracker
station fiducial surface is circular and about 30 cm in diameter. A typical
sample in the MICE beam has a spread of $\sim 80\,$mm in the upstream tracker
and $\sim 200\,$mm in the downstream tracker. The sample is not contained
within the trackers and hence the sample mean is not the true mean.

With limits of the sampling defined as $[-x_{L},x_{L}]$, the sample mean of a
Gaussian distribution centred around $\overline{x}$ and with a spread
$\sigma_{x}$ reads:

$\displaystyle\hat{x}$ $\displaystyle=$
$\displaystyle\int_{-x_{L}}^{x_{L}}x\times\mathcal{N}\left(\overline{x},\,\sigma_{x}^{2}\right)\mathrm{d}x$
(3.1.7) $\displaystyle=$
$\displaystyle\int_{-x_{L}}^{x_{L}}\frac{x}{\sqrt{2\pi}\sigma_{x}}\exp\left[\frac{-1}{2}\frac{\left(x-\overline{x}\right)^{2}}{\sigma_{x}^{2}}\right]\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int_{\frac{-x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}}^{\frac{x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}}\frac{\sqrt{2}\sigma_{x}z+\overline{x}}{\sqrt{\pi}}e^{-z^{2}}\mathrm{d}z$
$\displaystyle=$
$\displaystyle\sqrt{\frac{2}{\pi}}\sigma_{x}\int_{\frac{-x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}}^{\frac{x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}}ze^{-z^{2}}\mathrm{d}z+\frac{\overline{x}}{2}\left(\operatorname{erf}\left[\frac{x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}\right]-\operatorname{erf}\left[\frac{-x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}\right]\right)$
$\displaystyle=$
$\displaystyle\frac{\overline{x}}{2}\left(\operatorname{erf}\left[\frac{x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}\right]-\operatorname{erf}\left[\frac{-x_{L}-\overline{x}}{\sqrt{2}\sigma_{x}}\right]\right)-\sqrt{\frac{2}{\pi}}\sigma_{x}\exp\left[-\frac{x_{L}^{2}+\overline{x}^{2}}{2\sigma_{x}^{2}}\right]\sinh\left[\frac{x_{L}\overline{x}}{\sigma_{x}^{2}}\right].$

The relative deviation of the sample mean, $\hat{x}$, in equation 3.1.7 from
the real distribution mean, $\overline{x}$, is drawn in figure 4 as a function
of the relative true mean and the relative true width. The sample mean
preserves the true mean as long as the beam is well contained within the
detector fiducial.

Figure 4: Fractional discrepancy between the sample mean, $\hat{x}$, and the
true mean, $\overline{x}$, as a function of the mean and width of the true
distribution in units of the range half-width, $x_{L}$.

At different limits, the formula behaves as expected:

$\displaystyle\begin{array}[]{l}\lim\limits_{\overline{x}\rightarrow
0}\hat{x}=0=\overline{x},\\\
\lim\limits_{\frac{x_{L}}{\sigma_{x}}\rightarrow+\infty}\hat{x}=\overline{x}\operatorname{erf}(+\infty)-\sqrt{\frac{2}{\pi}}\sigma_{x}\lim\limits_{z\rightarrow+\infty}\left[e^{-z^{2}}\sinh(z)\right]=\overline{x},\\\
\lim\limits_{\frac{x_{L}}{\sigma_{x}}\rightarrow
0}\hat{x}=\frac{\overline{x}}{2}\left(\operatorname{erf}\left[\frac{-\overline{x}}{\sqrt{2}\sigma_{x}}\right]-\operatorname{erf}\left[\frac{-\overline{x}}{\sqrt{2}\sigma_{x}}\right]\right)=0.\end{array}$
(3.1.11)

For a distribution centred at 0, the sample mean converges to the true mean. A
distribution contained within the detector, i.e. for which
$\sigma_{x}/x_{L}\ll 1$, has a sample mean identical to the true mean as well.
The sample mean of a broad distribution, i.e. for which $\sigma_{x}/x_{L}\gg
1$, is asymptotically zero and thus heavily biased.

Given a significantly off-centre mean of the distribution at $z_{n}$, the
distributions in equation 3.1.5 are asymmetrically sampled. Given a positive
mean, $\overline{x_{n}}$, a particle that scatters towards the positive $x$ is
more likely to scatter out of the detector’s fiducial volume. The probability
density function of the effective scattering angle for a particle that is
expected to hit $x_{n}$ at $z_{n}$ is

$f_{x_{n}}(\theta)=\frac{C_{n}}{\sqrt{2\pi}\theta_{0}}\exp\left[-\frac{1}{2}\frac{\theta^{2}}{\theta_{0}^{2}}\right]\bm{1}_{[-x_{L},x_{L}]}\left(x_{n}+\Delta
z\theta\right),$ (3.1.12)

  * •

$\Delta z$, the effective distance between the two measuring stations;

  * •

$\theta\simeq\frac{x_{0}^{n}-x_{n}}{\Delta z}$, the effective scattering
angle;

  * •

$\theta_{0}$, the RMS effective scattering angle as described in equation
3.1.2;

  * •

$\bm{1}_{[a,b]}(\cdot)$, the indicator function that takes value 1 for all
elements of $[a,b]$ and 0 otherwise;

  * •

$C_{n}$, the normalization constant so that
$\int_{-\infty}^{+\infty}f_{x_{n}}(\theta)\mathrm{d}\theta=1$.

The indicator function symbolizes that, for a scattering angle above
threshold, the particle scatters out of the fiducial and does not contribute
to the PDF. The normalisation constant simplifies to

$\displaystyle C_{n}$ $\displaystyle=$ $\displaystyle
2\left(\operatorname{erf}\left[\frac{x_{L}-x_{n}}{\sqrt{2}\theta_{0}\Delta
z}\right]+\operatorname{erf}\left[\frac{x_{L}+x_{n}}{\sqrt{2}\theta_{0}\Delta
z}\right]\right)^{-1}$ (3.1.13) $\displaystyle\simeq$ $\displaystyle
2\left(\tanh\left[\frac{x_{L}-x_{n}}{\sqrt{2}\theta_{0}\Delta
z}\right]+\tanh\left[\frac{x_{L}+x_{n}}{\sqrt{2}\theta_{0}\Delta
z}\right]\right)^{-1}$ $\displaystyle\simeq$ $\displaystyle
1+\cosh\left[\frac{\sqrt{2}x_{n}}{\theta_{0}\Delta
z}\right]/\sinh\left[\frac{\sqrt{2}x_{L}}{\theta_{0}\Delta z}\right],$

which converges to unity if $x_{L}/(\theta_{0}\Delta_{z})\rightarrow+\infty$
or $x_{n}\rightarrow 0$. The last form in equation 3.1.13 is obtained using
the approximation $\operatorname{erf}(z)\simeq\tanh(z)$.

The function in equation 3.1.12 is represented for different values of
$x_{n}/x_{L}$ in figure 6. At large $x_{n}$, the function,
$f_{x_{n}}(\theta)$, is highly asymmetric due to scraping out of the fiducial
volume. The choice of parameters is consistent with a simulated 280 MeV/$c$
beam travelling between the two trackers at Step IV. The effective RMS
scattering angle is $\theta_{0}\simeq 9$ mrad and the effective distance is
$\Delta z/x_{L}\simeq 17.5$.

Figure 5: Part of the total scattering angle distribution (black) that does
not scrape out for different extrapolated position at the nth station,
$x_{n}$.

Figure 6: Deformation of the total sampled scattering angle distribution
(black) for different true position mean, $\overline{x_{n}}$, at the nth
station.

The average over the fiducial distribution of $x_{n}$, $g(x_{n})$, reads

$\displaystyle f(\theta)$ $\displaystyle=$ $\displaystyle
C\int_{-\infty}^{+\infty}\frac{f_{x_{n}}(\theta)}{C_{n}}g(x_{n})\mathrm{d}x_{n}$
(3.1.14) $\displaystyle=$ $\displaystyle
C\int_{-\infty}^{+\infty}\mathcal{N}(0,\theta_{0}^{2})\bm{1}_{[-x_{L},x_{L}]}\left(x_{n}+\Delta
z\theta\right)\frac{1}{\sqrt{2\pi}\sigma_{x_{n}}}\exp\left[-\frac{1}{2}\frac{(x_{n}-\overline{x_{n}})^{2}}{\sigma_{x_{n}}^{2}}\right]\mathrm{d}x_{n}$
$\displaystyle=$ $\displaystyle\mathcal{N}(0,\theta_{0}^{2})\times
C\int_{-x_{L}-\theta\Delta z}^{x_{L}-\theta\Delta
z}\frac{1}{\sqrt{2\pi}\sigma_{x_{n}}}\exp\left[-\frac{1}{2}\frac{(x_{n}-\overline{x_{n}})^{2}}{\sigma_{x_{n}}^{2}}\right]\mathrm{d}x_{n}$
$\displaystyle=$
$\displaystyle\mathcal{N}(0,\theta_{0}^{2})\times\frac{C}{2}\left(\operatorname{erf}\left[\frac{x_{L}-\theta\Delta
z-\overline{x_{n}}}{\sqrt{2}\sigma_{x_{n}}}\right]+\operatorname{erf}\left[\frac{x_{L}+\theta\Delta
z+\overline{x_{n}}}{\sqrt{2}\sigma_{x_{n}}}\right]\right),$

with $C^{-1}=\int_{-\infty}^{+\infty}f(\theta)\mathrm{d}\theta$. This shows a
deviation from the non-biased scattering distribution
$\mathcal{N}(0,\theta_{0}^{2})$. In the limit
$x_{L}/\sigma_{x_{n}}\rightarrow+\infty$, the normal distribution is
recovered.

The function in equation 3.1.14 is represented for different values of
$\overline{x_{n}}/x_{L}$ in figure 6. For positive means, $\overline{x_{n}}$,
the scattering angle distribution, $f(\theta)$, is biased towards negative
values due to anisotropic scraping. At $\overline{x_{n}}=0$, the distribution
is sharper than the normal $\mathcal{N}(0,\theta_{0}^{2})$ and has tamed tails
but retains the same mean. The large values of scattering angles are under-
represented in the distribution due to inevitable transmission losses between
measurement stations. The choice of parameters is motivated by the same
requirements as for figure 6. The width of the distribution of $x_{n}$ is
chosen to be $\sigma_{x_{n}}/x_{L}=0.5$.

At different limits, the formula behaves as expected:

$\begin{array}[]{l}\lim\limits_{\overline{x_{n}}\rightarrow
0}f(\theta)=f(\theta)|_{\overline{x_{n}}=0}=f(-\theta)|_{\overline{x_{n}}=0}\,\forall\theta\rightarrow\langle
f(\theta)\rangle=\int_{0}^{+\infty}\theta\left[f(\theta)-f(-\theta)\right]\mathrm{d}\theta=0,\\\
\lim\limits_{x_{L}\rightarrow+\infty}f(\theta)=\mathcal{N}(0,\theta_{0}^{2})\rightarrow\langle
f(\theta)\rangle=0,\\\ \lim\limits_{\sigma_{x_{n}}\rightarrow
0}f(\theta)=f_{\overline{x_{n}}}(\theta)\rightarrow\langle
f(\theta)\rangle=-\sqrt{\frac{2}{\pi}}\theta_{0}\exp\left[-\frac{x_{L}^{2}+\overline{x_{n}^{2}}}{2\theta_{0}^{2}\Delta
z^{2}}\right]\sinh\left[\frac{x_{L}\overline{x_{n}}}{\theta_{0}^{2}\Delta
z^{2}}\right].\end{array}$ (3.1.15)

A perfectly centred beam with $\overline{x_{n}}=0$ produces an even
distribution in $\theta$. A detector large enough to contain the entire beam
also yields an unbiased scattering angle distribution. A pencil beam still
produces an angular distribution sensitive to the extrapolated position at the
nth sampling station as $\theta_{0}>0$.

Figure 7 represents the sample mean scattering angle, $\hat{\theta}$,
normalised by the true effective scattering angle, $\theta_{0}$, as a function
of the true position mean, $\overline{x_{n}}$, and width, $\sigma_{x_{n}}$.
The figure is represented for negative values of $\overline{x_{n}}$ to produce
log-friendly positive values of $\hat{\theta}/\theta_{0}$.

Figure 7: Sample mean of the scattering distribution with respect to the
relative mean and width of the true position distribution at nth station.

Provided that $\hat{\theta}\neq 0$ for most beam settings, equation 3.1.6 in
terms of sample means reads

$\langle x_{n}-\delta x_{n}-x_{n0}\rangle=\langle x_{n}-x_{n0}\rangle-\delta
x_{n}=\langle f(\theta)\rangle\Delta z-\delta_{n}=\hat{\theta}\Delta z-\delta
x_{n}.\\\ $ (3.1.16)

For common values of $\hat{\theta}>0.01\theta_{0}$ and $\theta_{0}=0.009$, the
offset is of order $0.1$ mrad, which is larger than a tenth of the expected
Tait-Bryan angles of the tracker modules. This constitutes a significant bias
on the measurement of the station offset, $\delta_{n}$, and must be tackled to
ensure a consistent measurement of the offset independent of the MICE beam
setting.

###  3.2 Criterion

The beam anisotropy is the main source of bias, as demonstrated in section
3.1. An isotropic particle sample is selected out to ensure a consistent
measurement of the alignment.

It is not possible to make a selection depending on the track position at TOF1
and TOF2. A sample that makes it to TOF2 is inevitably biased by requiring
that the particles made it to TOF2. In field-off data, 80% of the particles
scrape out before reaching TOF2. TOF1 does not provide measurements of the
track gradients and as such cannot be used standalone.

The upstream tracker is chosen to make a selection as it is the most upstream
detector that measures the position and gradients of the track. The criterion
is based on the likelihood of the particle to scatter out of the fiducial
volume before it makes it to the centre of the downstream tracker. This
analysis requests a 90 % probability of containment, i.e. $\sim 2.15\,\sigma$
for a 2D Gaussian. For an effective distance $\Delta z$ between the two
trackers, the fiducial radius $R_{L}$ and an RMS effective scattering angle
$\theta_{0}$, the criterion is expressed as

$(\xi_{u}^{d}-x_{D})^{2}+(\upsilon_{u}^{d}-y_{D})^{2}<(R_{L}-2.15\theta_{0}\Delta_{z})^{2},$
(3.2.1)

with $(\xi_{u}^{d},\upsilon_{u}^{d})$ the global upstream track propagated to
TKD and $(x_{D},y_{D})$ the downstream tracker centre. This is equivalent to
selecting out a smaller circular fiducial surface at the centre of TKD. It
ensures containment upstream and downstream so that $\sigma_{x_{n}}/x_{L}\ll
1$, $\overline{x_{n}}/x_{L}\ll 1$ and $\hat{\theta}\simeq 0$ in equation
3.1.15.

Figure 8 shows a geometrical representation of the selection criterion. The
phase space of two particles, $P_{1}$ and $P_{2}$, are sampled at the upstream
tracker and their parameters
($\xi_{i}^{u},\upsilon_{i}^{u},\xi_{i}^{{}^{\prime}u},\upsilon_{i}^{{}^{\prime}u}$)
are extracted. Their expected position in the downstream tracker are
extrapolated as
$\psi_{i}^{d}=\psi_{i}^{u}+\psi_{i}^{{}^{\prime}u}(\zeta_{d}-\zeta_{u})$,
$\psi=\xi,\upsilon$. If the downstream point belongs to the blue fiducial
surface on the left-hand drawing, as for $P_{1}$, the particle is kept in the
final sample. The right-hand figure represents the $2.15\,\sigma$ ellipses of
the particles’ expected position due to scattering between the two trackers.
The ellipse is contained for the accepted particle, $P_{1}$, but is not for
the rejected particle, $P_{2}$. The inclusion of the green ellipse ensures at
least a 90% probability that the particle goes through the downstream tracker.

xy$R_{L}$$R_{L}-2.15\theta_{0}\Delta
z$$(\xi_{1}^{u},\upsilon_{1}^{u})$$(\xi_{1}^{d},\upsilon_{1}^{d})$$(\xi_{2}^{u},\upsilon_{2}^{u})$$(\xi_{2}^{d},\upsilon_{2}^{d})$

xy$R_{L}$$(\xi_{1}^{d},\upsilon_{1}^{d})$$(\xi_{2}^{d},\upsilon_{2}^{d})$

Figure 8: Left: Schematic of the total (white) and selected (blue) tracker
fiducial surface in the $xy$ plane. The movement of two example particles are
represented. Right: $2.15\,\sigma$ position ellipses for two example
particles.

The RMS effective scattering angle, $\theta_{0}$, and effective distance,
$\Delta z$, in equation 3.2.1 are functions of the momentum, $p$, the particle
species and the amount of material, $dz/X_{0}$. The practicalities of
evaluating these quantities and applying the criterion will be described in
section 4.2 for a Monte Carlo sample.

###  3.3 Outliers

The criterion limits the number of particles that scrape between TKU and TKD
as it selects a tight aperture in the downstream tracker. Due to the large
non-Gaussian tails of the scattering distribution and decays in flight, a non-
negligible fraction of particles get lost in transmission. A beam anisotropic
about the downstream tracker center scrapes preferentially on one end of the
tracker, introducing a bias. The lost particles must be accounted for in the
residual distributions.

Figure 9 shows a paraxial particle that is expected to be transmitted but has
a hard scatter at the level of the absorber ($z=0$). In this scenario, no
track is recorded in the downstream tracker. If the extrapolated transversal
position in TKD, $\psi_{u}^{d}$, $\psi=\xi,\upsilon$, is farther on one side
of the tracker centre, it is more likely to scatter out on the same side, as
it requires a smaller, more probable scattering angle. To account for those
particles, outliers are added to the residual distributions with signs chosen
with the following prescriptions

$\psi_{u}^{d}>q_{D}\rightarrow\\\
\left\\{\begin{array}[]{l}\psi_{u}-\psi_{12}^{u}<0\\\
\psi^{\prime}_{u}-\psi_{12}^{\prime}<0\\\ \psi_{d}-\psi_{12}^{d}<0\\\
\psi_{d}-\psi_{12}^{\prime}>0\end{array}\right.,\qquad\psi_{u}^{d}<q_{D}\rightarrow\\\
\left\\{\begin{array}[]{l}\langle\psi_{u}-\psi_{12}^{u}\rangle>0\\\
\langle\psi^{\prime}_{u}-\psi_{12}^{\prime}\rangle>0\\\
\langle\psi_{d}-\psi_{12}^{d}\rangle>0\\\
\langle\psi_{d}-\psi_{12}^{\prime}\rangle<0\end{array}\right.,\qquad\psi=\xi,\upsilon,\,q=x,y.$
(3.3.1)

zx0TOF1TOF2TKUTKD•$(x_{D},y_{D})$•$(\xi_{u},\upsilon_{u})$•$(\xi_{12}^{u},\upsilon_{12}^{u})$•$(\xi_{d},\upsilon_{d})$•$(\xi_{12}^{d},\upsilon_{12}^{d})$
Figure 9: Paraxial track (red line) that undergoes a hard scatter at the level
of the absorber ($z=0$) and hits the magnet bore. The track interpolated
between the two time-of-flight stations is represented by the green line.

##  4 Alignment of a Monte Carlo sample

Two main beam line settings are used in order to produce the alignment
corrections. High momentum beams are preferred in order to reduce the RMS
scattering angle and maximize transmission. The Monte Carlo reproduces two
runs taken during the ISIS 2017/01 user cycle presented in table 4.1. The two
settings correspond to ‘pion’ beams of positive polarity to maximize
statistics. The number of particle triggers has been greatly enhanced in the
Monte Carlo in order to investigate the resolution of the alignment algorithm.

Run ID | Date | Beam type |  $\langle p_{u}\rangle$ [MeV/c] |  $\sigma_{p_{u}}$ [MeV/c] | TOF1 SPs | MC TOF1 SPs
---|---|---|---|---|---|---
9367 | 30/05/17 | $\pi^{+}$ | 285.00$\pm$0.03 | 11.53$\pm$0.02 | 186136 | 2056605
9370 | 30/05/17 | $\pi^{+}$ | 394.40$\pm$0.03 | 13.55$\pm$0.02 | 133253 | 767107
Table 4.1: Characteristics of runs 9367 and 9370. The mean and RMS upstream
momentum are reconstructed for the MC from the velocity of the muons between
TOF0 and TOF1. SP stands for space point.

The 9367 Monte Carlo sample is separated out into ten chunks and the 9370 into
five. The chunks are combined together at the calibration stage but are fitted
separately during the alignment stage in order to verify the consistency of
the algorithm.

The two beams exhibit different distributions in the beam line. The mean
position of the former lies in the negative $x$ and negative $y$ while the
latter lies in the positive quadrant. Any bias that could arise from the beam
characteristics is amplified by the use of these two settings. An agreement
between the two independent fits guarantees an unbiased measurement of the
alignment constants.

###  4.1 Trackers internal alignment

As a consistency check, the alignment of the tracker stations with respect to
each other is measured. As for the CMM measurements described in section 1.2,
the two end stations (1 and 5) are used as the reference for the alignment and
the positions of the other stations are measured with respect to them.

For each track recorded in tracker $t=u,d$, the reference axis gradients are
reconstructed as $q^{\prime}_{15}=(q_{5}-q_{1})/(z_{5}-z_{1})$, $q=x,y$, and
the $y$-intercept is the position recorded in station 1. The interpolated
position in station $i$ reads

$q_{15}^{i}=q_{1}+q^{\prime}_{15}(z_{i}-z_{1}).$ (4.1.1)

The mean residuals $\langle q_{15}^{i}-q_{i}\rangle$, $q=x,y$, are represented
in figure 10 from the most upstream to the most downstream station. As
expected from aligned stations, the mean residuals are all compatible with
zero with a resolution of order 1 $\mu$m. This technique can be used to align
the tracker stations using real data down to a precision two orders of
magnitude smaller than the tracker space point resolution.

Figure 10: Mean residuals between the interpolated track joining the two
outermost stations of each tracker and the position reconstructed in the
central three stations in $x$ (left) and $y$ (right).

###  4.2 Implementation of the criterion

Applying the criterion in equation 3.2.1 requires the determination of the
mean RMS effective scattering angle for a given particle, $\theta_{0}^{i}$. It
is function of the upstream particle momentum, $p_{u}$, its velocity,
$\beta_{u}$, and the amount of material traversed between the two trackers,
$dz/X_{0}$.

The time-of-flight between TOF0 and TOF1, $t_{01}$, provides a strong particle
identification variable. In the pion beams used for the alignment, three
species of particles ($\pi^{+},\mu^{+},e^{+}$) are present in the sample but
have distinguishable time-of-flight distributions as shown in figure 12.
Positrons are rejected from this analysis as they are ultrarelativistic and
their momentum cannot be reconstructed from the time-of-flight. Requiring
$t_{01}>26$ ns rids the sample of positrons.

Figure 11: Time-of-flight distribution of a pion beam between TOF0 and TOF1.

Figure 12: Normalised probability density functions of the muon and pion
components of the beam. MPV stands for most probable value.

The remainder of the distribution contains three components. The bulk of muons
and pions are contained in the left and right peaks, respectively. The muons
produced by pion decays in flight form a decreasing time-of-flight continuum
that reaches a probability maximum at the level of the muon peak. The decay
muons are discriminated by using background identification methods [23]. They
are subtracted from the distribution and the rest of it is fitted with a two-
peak Gaussian to extract the locations, $t_{\mu}$ and $t_{\pi}$, and widths,
$\sigma_{\mu}$ and $\sigma_{\pi}$, of the muon and pion peaks, respectively.
The background-subtracted peaks do not overlap. The intermediary time-of-
flight, $t_{c}$, of equal probability for the two peaks is located at

$\frac{t_{c}-t_{\mu}}{\sqrt{2}\sigma_{\mu}}=\frac{t_{\pi}-t_{c}}{\sqrt{2}\sigma_{\pi}}\iff
t_{c}=\frac{\sigma_{\mu}t_{\pi}+\sigma_{\pi}t_{\mu}}{\sigma_{\mu}+\sigma_{\pi}}.$
(4.2.1)

The pion PDF lies above $t_{c}$. The background is added to the remainder of
the distribution to form the muon PDF. The two normalised distributions are
represented stacked on top of each other in figure 12. For a given test
sample, the particle species is selected to be the most probable species.

Given the species $i$, the momentum is inferred from the time-of-flight
through

$p_{01}=\frac{m_{i}c}{\sqrt{\left(ct_{01}/s_{01}\right)^{2}-1}},$ (4.2.2)

with $s_{01}$ the distance between the space points in TOF0 and TOF1. The
momentum is adjusted for the loss in TOF1 by subtracting the Bethe-Bloch mean
energy loss going through the scintillating material. This yields the upstream
momentum, $p_{u}$. The upstream velocity is derived from the momentum through

$\beta_{u}=\frac{p_{u}}{\sqrt{p_{u}^{2}+m_{i}^{2}c^{2}}}.$ (4.2.3)

The value of path length in amount of radiation length, $dz/X_{0}$, is
obtained by fitting the theoretical scattering width in equation 3.2.1 to real
data. Figure 13 shows the value of the RMS scattering angle, $\theta_{0}$ as a
function of the momentum, $p_{12}$, in the $xz$ and $yz$ projections. These
fits yield a value of the path length of $dz/X_{0}=3.509\pm 0.039$ %, which
produces a simplified expression for the RMS scattering angle:

$\theta_{0}\simeq\frac{(2.223\,\text{MeV})}{\beta_{u}p_{u}c}.$ (4.2.4)

Figure 13: Theoretical fit to the RMS scattering angle in the $xz$ and $yz$
projections between the upstream and downstream trackers as a function of the
momentum and velocity reconstructed at the upstream tracker.

The last element to determine is the effective distance, $\Delta z$, i.e the
constant that relates the effective scattering angle $\theta_{0}$ to the
displacement in the downstream tracker, as defined in equation 3.1.4. To
measure the RMS scattering angle, $\theta_{0}$, the angular residuals between
the two trackers are measured as shown in figure 15. This yields a weighted
average of $\theta_{0}=8.74\pm 0.02$ mrad, consistent with this run setting
mean momentum. The RMS of the residuals between the position measured in the
centre of the downstream tracker and the location of the track extrapolated
from the upstream tracker provides a measurement of $\theta_{0}\Delta
z=22.77\pm 0.04$ mm, as shown in figure 15. The effective distance between the
two trackers is

$\Delta z=\frac{\theta_{0}\Delta_{z}}{\theta_{0}}=2604.26\pm
6.53\,\mathrm{mm},$ (4.2.5)

a few centimeters over half the physical distance between two tracker centres
of 4886.57 mm. Most of the scattering happens at the level of the absorber
windows equidistant from both trackers. Provided with the set of equations and
parameters determined in this section, the criterion is applied on a particle-
by-particle basis to produce the analysis sample.

Figure 14: Angular residuals between the gradients measured in TKD and TKU.

Figure 15: Residuals between the position measured in TKD and the TKU position
projected into TKD.

The effect of this selection on the beam profile in the centre of the trackers
is shown in figure 16. The criterion produces a very tight beam upstream that
ensures that the sample is mostly contained downstream.

Figure 16: Beam $(\xi_{t},\upsilon_{t})$ and
$(\xi^{\prime}_{t},\upsilon^{\prime}_{t})$, $t=u,d$, profiles in the upstream
(TKU) and downstream tracker (TKD) shown before (left) and after (right) the
application of the selection criterion.

###  4.3 Fitting algorithm

Provided with the unbiased sample produced as described in sections 3.2–3.3,
each track yields of a set of global gradients between TOF1 and TOF2,
$\xi^{\prime}_{12}$ and $\upsilon^{\prime}_{12}$, and global extrapolated
positions at the tracker centres, $\xi_{12}^{t}$ and $\upsilon_{12}^{t}$. It
also records the position of the track at the centre of the trackers in local
coordinates, $x_{t}$ and $y_{t}$, and its local gradients, $x^{\prime}_{t}$
and $y^{\prime}_{t}$.

The residual distributions necessary to measure the left hand side of
equations 2.2.7 are produced in order to measure the eight alignment
parameters. Figure 18 shows the gradient residuals between $y^{\prime}_{u}$
and $\upsilon^{\prime}_{12}$. The mean residual yields the the pitch of the
upstream tracker, $\alpha_{U}$. Particular care must be taken in the
evaluation of the mean, as the scattering distribution exhibits long tails and
the peak is not necessarily Gaussian as the the time-of-flight detectors have
a very coarse granularity. The interquartile mean, more robust than the
arithmetic mean, is used as figure-of-merit. The statistical uncertainty
carried by the measurement is $2\sigma_{W}/\sqrt{N}$, with $\sigma_{W}$ the
interquantile Winsorised RMS [24].

Figure 17: Residuals distribution between the pitch gradients measured locally
in TKU, $y^{\prime}_{u}$, and globally between TOF1 and TOF2,
$\upsilon^{\prime}_{12}$.

Figure 18: Evolution of the optimal value of the pitch angle in TKU,
$\alpha_{U}^{*}$, for different number of iterations of the fitting algorithm.

To ensure the best possible fit to the tracker parameters, the algorithm is
applied multiple times. The first estimate of
$x_{T},y_{T},\alpha_{T},\beta_{T}$ is used as an input to the sample selection
part of the algorithm. The process is repeated until the alignment constants
converge. Figure 18 shows the evolution of the optimal upstream tracker pitch,
$\alpha_{U}^{*}$, over five iterations.

Each of the fifteen chunks described earlier were processed independently with
the algorithm. Figure 19 compiles the alignment parameters measured for each
run. The measurements are in good agreement with one another and show no
significant discrepancy. The constant fit $\chi^{2}/\text{ndf}$ is close to
unity for each fit, which indicates that there are no significant additional
source of uncertainty. The optimal parameters are summarised in table 4.2,
compared to the true positions of the trackers in the Monte Carlo.

| TKU | TKD
---|---|---
| Truth | Best fit | Truth | Best fit
x [mm] | $-0.138$ | $-0.074\pm 0.063$ | $-3.207$ | $-3.160\pm 0.061$
y [mm] | $-0.689$ | $-0.641\pm 0.062$ | $3.043$ | $3.018\pm 0.061$
$\alpha$ [mrad] | $3.014$ | $2.999\pm 0.018$ | $1.919$ | $1.917\pm 0.017$
$\beta$ [mrad] | $1.311$ | $1.344\pm 0.018$ | $-0.568$ | $-0.585\pm 0.017$
Table 4.2: Summary table of the optimal alignment constants measured in the
Monte Carlo.

Figure 19: Consistency of the alignment algorithm across MC runs produced for
the 2017/01 ISIS user cycle.

###  4.4 Propagation

The fitted parameters are used to yield the global track coordinates at the
tracker $t=u,d$ centres, $(\xi_{t},\upsilon_{t},\zeta_{t})$, through equation
2.1.4 and the global gradients $\xi^{\prime}_{t},\upsilon^{\prime}_{t}$
through equation 2.2.5. A corrected global track is propagated in an adjacent
detector module $M$ at $\zeta_{m}$ through

$\psi_{t}^{m}=\psi_{t}+\psi^{\prime}_{t}(\zeta_{m}-\zeta_{t}),\,\psi=\xi,\upsilon.$
(4.4.1)

Provided exact corrections, a detector module $M$ that measures a global
position $(\xi_{m},\upsilon_{m},\zeta_{m})$ verifies

$\left\\{\begin{array}[]{l}\langle\psi_{m}-\psi_{t}^{m}\rangle=0\\\
\langle\psi^{\prime}_{m}-\psi^{\prime}_{t}\rangle=0\end{array}\right.,\,\psi=\xi,\upsilon.$
(4.4.2)

As a consistency check, the tracks are first propagated between the two
trackers. The selection described in section 3.2 is applied but no
compensation is added for lost tracks. The results are shown in figure 20. The
top left and right distributions show the residuals between the TKU and TKD
tracks at the centre of the downstream tracker and at the level of the
absorber, respectively. The bottom two histograms show the agreement between
the angles measured upstream and downstream. The azimuthal angle residuals
show consistency between the roll of the two trackers. The results are
compatible with what is expected from aligned trackers.

Figure 20: Tracker-to-tracker residual distributions in position (top) and
angle (bottom).

The upstream tracker tracks are extrapolated into TOF1 and the downstream
tracker tracks are propagated into the three downstream particle
identification detectors: TOF2, the KL and the EMR. The residual plots are
represented in figure 21. The values obtained show good agreement between the
tracks and the space points measured in other MICE detectors.

Figure 21: Tracker to particle identification detectors residual distributions
(TOF1, TOF2, KL and EMR).

Special care is taken when evaluating the central value of the residual
distributions. The two trackers and the Electron-Muon Ranger have a sufficient
spacial resolution to follow a near-Gaussian distribution. The residuals
involving these detectors are fitted with a standard multivariate normal of
mean $\bm{\mu}$ and width $\bm{\sigma}$ between the two half-maximum, i.e. in
the range $\bm{\mu}\pm 1.1775\,\bm{\sigma}$. The TOF hodoscopes and the KL do
not have a sufficient resolution to produce residuals that follow a Gaussian
distribution. A probability density function of the form

$h(x)=\frac{1}{4W}\left(\tanh\left[\frac{x-\mu+W}{\sigma}\right]-\tanh\left[\frac{x-\mu-W}{\sigma}\right]\right)$
(4.4.3)

is used in each projection to fit the residuals involving the low granularity
detectors. The constant $\mu$ represents the central value of the residual
distribution, $\sigma$ the residual width and $W$ the half-width of one of the
low-resolution detector pixel. The parameters obtained for each of the fits
are represented in table 4.3. The values found for $W$ are consistent with
pixels of 6 cm in TOF1 and TOF2 and of 4.4 cm in the KL.

Origin | Target | Variable |  $\mu$ [mm]/[mrad] |  $\sigma$ [mm]/[mrad] |  $W$ [mm]
---|---|---|---|---|---
TKU | TOF1 | $\xi$ | $0.258\pm 0.050$ | $6.937\pm 0.107$ | $30.30\pm 0.07$
$\upsilon$ | $0.3072\pm 0.049$ | $7.048\pm 0.110$ | $29.56\pm 0.07$
TKD | $\xi$ | $0.213\pm 0.150$ | $19.890\pm 0.254$ | –
$\upsilon$ | $0.180\pm 0.141$ | $19.850\pm 0.225$ | –
$\xi^{\prime}$ | $0.064\pm 0.063$ | $7.136\pm 0.119$ | –
$\upsilon^{\prime}$ | $0.017\pm 0.062$ | $7.423\pm 0.113$ | –
$\phi$ | $0.75\pm 2.78$ | $413.4\pm 4.4$ | –
TKD | TOF2 | $\xi$ | $-0.049\pm 0.047$ | $4.883\pm 0.105$ | $29.80\pm 0.06$
$\upsilon$ | $-0.002\pm 0.049$ | $5.125\pm 0.119$ | $29.67\pm 0.06$
KL | $\upsilon$ | $0.037\pm 0.042$ | $5.785\pm 0.093$ | $21.63\pm 0.06$
EMR | $\xi$ | $0.036\pm 0.081$ | $10.760\pm 0.124$ | –
$\upsilon$ | $0.036\pm 0.081$ | $11.020\pm 0.122$ | –
Table 4.3: Residual distributions fitting parameters.

##  5 Conclusions

The beam-based detector alignment analysis has shown that all of the detectors
in the MICE beam line reconstruct space points and tracks in a consistent
fashion. Due to the embedded nature of the scintillating fibre trackers, it is
necessary to use straight particle tracks to probe their position within the
superconducting magnets bore. The adjustment is achieved by using detectors
whose positions are well known from laser telemetry surveys as reference
points to measure the offsets in the two trackers.

The alignment algorithm was tested on two large, highly differentiated Monte
Carlo samples duplicating runs 9367 and 9370 taken during the 2017/01 ISIS
user cycle. The alignment constants measured are in excellent agreement with
the true tracker positions. The resolution on the alignment constants improves
as $2\sigma_{W}/\sqrt{N}$ with $\sigma_{W}\simeq 3$ mrad in angle and
$\sigma_{W}\simeq 10$ mm in position.

## References

  * [1] S. Choubey et al., “International Design Study for the Neutrino Factory, Interim Design Report,” tech. rep., 2011.  arXiv:hep-ex/1112.2853 [hep-ex].
  * [2] D. Neuffer, “Multi-TeV muon colliders,” AIP Conf. Proc. 156 (1987) 201.
  * [3] V. V. Parkhomchuk and A. N. Skrinskii, “Cooling Methods for Charged Particle Beams,” Rev. Accel. Sci. Tech. 1 no. 1, (2008) 237.
  * [4] D. Stratakis and R. Palmer, “Rectilinear six-dimensional ionization cooling channel for a muon collider: A theoretical and numerical study,” Phys. Rev. ST Accel. Beams 18 (2005) 031003.
  * [5] M. Apollonio et al., “Accelerator design concept for future neutrino facilities,” J. Instrum. 4 no. 7, (2009) P07001.
  * [6] R. Palmer et al., “Muon collider design,” Nucl. Phys. Proc. Suppl. 51A (1996) 61–84.
  * [7] G. Gregoire et al., “Proposal to the Rutherford Appleton Laboratory: an International Muon Ionization Cooling Experiment (MICE),” tech. rep., 2003.  MICE-NOTE-21.
  * [8] M. Bogomilov et al., “The MICE Muon Beam on ISIS and the beam-line instrumentation of the Muon Ionization Cooling Experiment,” J. Instrum. 7 (2012) P05009.
  * [9] M. Bogomilov et al., “Lattice design and expected performance of the Muon Ionization Cooling Experiment demonstration of ionization cooling,” Phys. Rev. Accel. Beams 20 (2017) 063501.
  * [10] K. Tilley, “Status of Design of Muon Beam Line for the Muon Ionization Cooling Experiment,” pp. 1461–1463.  Proc. 9th European Particle Accelerator Conf. (EPAC’04), 2004.  MOPP098.
  * [11] C. Boother et al., “The design, construction and performance of the MICE target,” J. Instrum. 8 no. 1, (2013) P03006.
  * [12] R. Bertoni et al., “The design and commissioning of the MICE upstream time-of-flight system,” Nucl. Inst. and Meth. in Phys. Res. A 615 no. 1, (2010) 14–26.
  * [13] L. Cremaldi et al., “A Cherenkov Radiation Detector with High Density Aerogels,” IEEE Trans. Nucl. Sci. 56 no. 1, (2009) 1475–1478.
  * [14] R. Bertoni et al., “The construction of the MICE TOF2 detector,” tech. rep., 2012.  MICE-NOTE-286.
  * [15] M. Rayner and M. Bonesini, “The MICE PID Detector System,” pp. 1164–1166.  Proc. 1st Int. Particle Accelerator Conf. (IPAC’10), 5, 2010.  MOPE079.
  * [16] D. Adams et al., “Electron-muon ranger: performance in the MICE muon beam,” J. Instrum. 10 no. 12, (2015) P12012.
  * [17] T. Millington and A. Hooper, “MICE hall TOF0 survey report,” tech. rep., 2016\.  MICE-NOTE-483.
  * [18] T. Millington and A. Hooper, “MICE hall TOF1 survey report,” tech. rep., 2016\.  MICE-NOTE-492.
  * [19] T. Millington and A. Hooper, “MICE hall TOF2 survey report,” tech. rep., 2016\.  MICE-NOTE-494.
  * [20] T. Millington and A. Hooper, “MICE hall EMR/KL survey report,” tech. rep., 2016\.  MICE-NOTE-490.
  * [21] T. Millington and A. Hooper, “MICE hall Solenoid1, Solenoid2 and Focus Coil survey report,” tech. rep., 2017.  MICE-NOTE-510.
  * [22] K. A. Olive et al., “Review of Particle Physics,” Chin. Phys. C38 (2014) 090001.
  * [23] M. Morháč et al., “Background elimination methods for multidimensional coincidence gamma-ray spectra,” Nucl. Instr. and Meth. in Phys. Res. A 401 no. 1, (1997) 113–132.
  * [24] J. W. Tukey and D. H. McLaughlin, “Less Vulnerable Confidence and Significance Procedures for Location Based on a Single Sample: Trimming/Winsorization 1,” Sankhya 25 no. 3, (1963) 331–352. http://www.jstor.org/stable/25049278.


# Nivat’s Conjecture and pattern complexity in algebraic subshifts111Research
supported by the Academy of Finland grant 296018.

Jarkko Kari  Department of Mathematics and Statistics, University of Turku
Etienne Moutot  Department of Mathematics and Statistics, University of Turku
LIP, ENS de Lyon – CNRS – UCBL – Université de Lyon

###### Abstract

We study Nivat’s conjecture on algebraic subshifts and prove that in some of
them every low complexity configuration is periodic. This is the case in the
Ledrappier subshift (the 3-dot system) and, more generally, in all two-
dimensional algebraic subshifts over ${\mathbb{F}_{p}}$ defined by a
polynomial without line polynomial factors in more than one direction. We also
find an algebraic subshift that is defined by a product of two line
polynomials that has this property (the 4-dot system) and another one that
does not.

##  1 Introduction and preliminaries

The European Association for Theoretical Computer Science, EATCS, celebrated
its 25th anniversary at ICALP 1997 in Bologna. The keynote address was given
by Maurice Nivat. His talk – titled “Towards a History of Automata: Why Were
They Introduced? What Are They Good for?” – suggested the following intriguing
problem that has become known as Nivat’s conjecture: If an infinite two-
dimensional grid has been colored in such a way that, for some
$n,m\in\mathbb{N}$, the number of distinct $n\times m$ patterns is at most
$nm$, is the coloring necessarily periodic in some direction? The conjecture
has attracted wide interest, but it has turned out to be difficult and remains
still unsolved today.

A number of partial results and related observations have been made.
Periodicity has been established if the number of $n\times m$ patterns is at
most $\alpha nm$ for progressively larger and larger constants $\alpha<1$:
First for $\alpha=1/144$ in [5], then for $\alpha=1/16$ in [11], and finally
for the best known constant $\alpha=1/2$ in [3]. It is also known that having
at most $2n$ patterns of size $2\times n$ and having at most $3n$ patterns of
size $3\times n$ imply periodicity [12, 4]. In [7] we introduced an algebraic
approach that leads to the following asymptotic result: A non-periodic
coloring of the grid can only have finitely many pairs $(n,m)$ such that the
number of distinct $n\times m$ patterns is at most $nm$. Of course Nivat’s
conjecture claims that there are no such pairs.

In this paper we continue with our algebraic approach and prove that Nivat’s
conjecture holds on colorings that come from certain algebraically defined
sets, including the Ledrappier subshift [9]. In fact we prove a stronger
statement that in these sets periodicity is implied if for any shape – not
necessarily a rectangle – the number of patterns of that shape is at most the
size of the shape. Even more: if a coloring has any non-trivial annihilator
over $\mathbb{Z}$ (terms explained below) then it is periodic.

To make the statement precise we recall some terminology. For a finite
alphabet $A$, colorings $c\in A^{\mathbb{Z}^{2}}$ of the two-dimensional grid
by elements of $A$ are called (two-dimensional) _configurations_. Typically we
use notation $c_{\mathbf{n}}$ for the color $c(\mathbf{n})\in A$ of cell
$\mathbf{n}\in\mathbb{Z}^{2}$. Basic operations on $A^{\mathbb{Z}^{2}}$ are
_translations_ : for any $\mathbf{t}\in\mathbb{Z}^{2}$ the translation
$\tau_{\mathbf{t}}:A^{\mathbb{Z}^{2}}\longrightarrow A^{\mathbb{Z}^{2}}$ by
$\mathbf{t}$ is defined by
$\tau_{\mathbf{t}}(c)_{\mathbf{n}}=c_{\mathbf{n}-\mathbf{t}}$, for all $c\in
A^{\mathbb{Z}^{2}}$ and all $\mathbf{n}\in\mathbb{Z}^{2}$. We call a
configuration $c$ _periodic_ if $\tau_{\mathbf{t}}(c)=c$ for some non-zero
$\mathbf{t}\in\mathbb{Z}^{2}$, and we call $\mathbf{t}$ a _vector of
periodicity_. If there are two linearly independent vectors of periodicity
then $c$ is _two-periodic_. In this case it is easy to see that there are
horizontal and vertical vectors of periodicity $(k,0)$ and $(0,k)$ for some
$k\neq 0$, and consequently a vector of periodicity in every rational
direction. We call $c$ _one-periodic_ if it is periodic but not two-periodic.

Colorings $p\in A^{D}$ of a finite shape $D\subset\mathbb{Z}^{d}$ are called
_$D$ -patterns_, or simply patterns. The set of $D$-patterns that appear in a
configuration $c$ is denoted by $P(c,D)$, that is,

$P(c,D)=\\{\tau_{\mathbf{t}}(c)_{|D}\ |\ \mathbf{t}\in\mathbb{Z}^{2}\ \\}.$

We say that $c$ has _low complexity_ with respect to shape $D$ if
$|P(c,D)|\leq|D|$, and we call $c$ a _low complexity configuration_ if it has
low complexity with respect to some finite $D$. Otherwise $c$ is a _high
complexity configuration_. Low complexity configurations come up naturally in
practical setups, e.g. in crystallography particles may attach to each other
only in very limited ways. Moreover, there are interesting mathematical
problems associated to them, including the famous Nivat’s conjecture discussed
above:

######  Conjecture (Maurice Nivat 1997).

Let $c\in A^{\mathbb{Z}^{2}}$ be a two-dimensional configuration. If $c$ has
low complexity with respect to some rectangle
$D=\\{1,\dots,n\\}\times\\{1,\dots,m\\}$ then $c$ is periodic.

The analogous claim in dimensions higher than two fails, as does an analogous
claim in two dimensions for many other shapes than rectangles [1].

To study the conjecture algebraically we replace the colors by integers, or
elements of some other integral domain $R$, and express the configuration $c$
as a formal power series $c(X,Y)$ over two variables $X$ and $Y$ in which the
coefficient of monomial $X^{i}Y^{j}$ is $c_{i,j}$, for all $i,j\in\mathbb{Z}$.
Note that the exponents of the variables range from $-\infty$ to $+\infty$. In
the following also polynomials may have negative powers of variables so all
polynomials considered are actually Laurent polynomials. Let us denote by
$R[X^{\pm 1},Y^{\pm 1}]$ and $R[[X^{\pm 1},Y^{\pm 1}]]$ the sets of such
polynomials and power series, respectively, with coefficients in domain $R$.
We call a power series $c\in R[[X^{\pm 1},Y^{\pm 1}]]$ _finitary_ if its
coefficients take only finitely many different values. Since we color the grid
using finitely many colors, configurations are identified with finitary power
series.

Multiplying configuration $c\in R[[X^{\pm 1},Y^{\pm 1}]]$ by a monomial
corresponds to translating it, and the periodicity of the configuration by
vector $\mathbf{t}=(n,m)$ is then equivalent to $(X^{n}Y^{m}-1)c=0$, the zero
power series. More generally, we say that polynomial $f\in R[X^{\pm 1},Y^{\pm
1}]$ _annihilates_ power series $c$ if the formal product $fc$ is the zero
power series. The set of polynomials that annihilates a power series is a
polynomial ideal, and is denoted by

$\text{Ann}_{R}(c)=\\{f\in R[X^{\pm 1},Y^{\pm 1}]\leavevmode\nobreak\
|\leavevmode\nobreak\ fc=0\\}.$

We observed in [7] that, in the case $R=\mathbb{Z}$, if a configuration has
low complexity with respect to some shape then it is annihilated by some non-
zero polynomial $f\neq 0$. The proof works unchanged for an arbitrary field
$R$.

######  Lemma 1 ([7]).

Let $R$ be a field or $R=\mathbb{Z}$. Let $c\in R[[X^{\pm 1},Y^{\pm 1}]]$ be a
low complexity configuration. Then $\text{Ann}_{R}(c)$ contains a non-zero
polynomial.

One of the main results of [7] states that, in the case $R=\mathbb{Z}$, if a
configuration $c$ is annihilated by a non-zero polynomial then it has
annihilators of particularly nice form:

######  Theorem 2 ([7]).

Let $c\in\mathbb{Z}[[X^{\pm 1},Y^{\pm 1}]]$ be a configuration (a finitary
power series) annihilated by some non-zero polynomial.
Then there exists non-zero
$(i_{1},j_{1}),\ldots,(i_{m},j_{m})\in\mathbb{Z}^{2}$ such that

$(X^{i_{1}}Y^{j_{1}}-1)\cdots(X^{i_{m}}Y^{j_{m}}-1)\in\text{Ann}_{\mathbb{Z}}(c).$

Unlike Lemma 1 this theorem does not generalize to all cases when $R$ is a
field.

For a polynomial $f=\sum a_{i,j}X^{i}Y^{j}$, we call
$\text{supp}(f)=\\{(i,j)\leavevmode\nobreak\ |\leavevmode\nobreak\ a_{i,j}\neq
0\\}$ its _support_. A _line polynomial_ is a polynomial with its terms
aligned all on the same line: $f$ is a line polynomial in direction
$\mathbf{u}\in\mathbb{Z}^{2}\setminus\\{\mathbf{0}\\}$ if and only if
$\text{supp}(f)$ contains at least two elements and for some
$\mathbf{n}\in\mathbb{Z}^{2}$ we have
$\text{supp}(f)\subseteq\\{\mathbf{n}+r\mathbf{u}\ |\ r\in\mathbb{Q}\\}$. Note
that the annihilator provided by Theorem 2 is a product of line polynomials. A
central feature of line polynomials is that any configuration that is
annihilated by a line polynomial is periodic in the direction of the line
polynomial [7].

If $R$ is a finite field and if $f\in R[X^{\pm 1},Y^{\pm 1}]$ is a non-zero
polynomial then we define the set

$X_{f}=\\{c\in R[[X^{\pm 1},Y^{\pm 1}]]\ |\ fc=0\\}$

of all configurations that $f$ annihilates and call it the _algebraic
subshift_ defined by $f$. It is a subshift of finite type (SFT, see [10] for
the symbolic dynamics terminology). We have that $c\in
X_{f}\Longleftrightarrow f\in\text{Ann}_{R}(c)\Longleftrightarrow fc=0$.

By Lemma 1 all low complexity configurations belong to algebraic subshifts
when the symbols are renamed as elements of a finite field. It is thus enough
to consider Nivat’s conjecture on elements of algebraic subshifts: if the
conjecture is false then there is a counter example configuration that belongs
to an algebraic subshift. This is the approach taken in this work. We consider
various algebraic subshifts and see whether low complexity implies periodicity
in these subshifts. When this is the case we say that the subshift has the
_generalized Nivat property_. We prove that an algebraic subshift $X_{f}$ has
the generalized Nivat property if the defining polynomial $f$ does not have
line polynomial factors in two different directions.

The paper is organized as follows. In Section 2 we consider as a particular
example the well known Ledrappier subshift, also known as the 3-dot system,
and prove that any low complexity configuration in the Ledrappier subshift is
periodic. In Section 3 we generalize this result to all algebraic subshifts
where the defining polynomial does not have line polynomial factors in more
than one direction. This includes, for example, the space-time diagrams of all
additive cellular automata over finite fields. In Section 4 we consider the
4-dot system defined by polynomial $(1+X)(1+Y)$ over ${\mathbb{F}_{2}}$ and
prove that it also has the generalized Nivat property although the defining
polynomial has horizontal and vertical line polynomial factors, while the
analogous system defined by $(1+X^{2})(1+Y^{2})$ does not have the property.

##  2 The Ledrappier Subshift

The Ledrappier subshift, or the 3-dot system, consists of the configurations
over the binary alphabet ${\mathbb{F}_{2}}$ that are annihilated by the
polynomial $1+X+Y\in{\mathbb{F}_{2}}[X^{\pm 1},Y^{\pm 1}]$.

######  Definition 1 ([9]).

The _Ledrappier subshift_ $L$ is the algebraic subshift $X_{f_{L}}$ over
${\mathbb{F}_{2}}$ defined by the annihilator $f_{L}=1+X+Y$.

In this work we relate the generalized Nivat property to the number of line
polynomial factors of the defining annihilator. It turns out that $f_{L}$ has
none.

A visual way of seeing if a polynomial has a line polynomial factor is to look
at the shape of the convex hull of its support: the convex hull has parallel
sides in the directions of its line polynomial factors. To be more precise, we
need some definitions of discrete geometry. The closed half plane in a
direction $\mathbf{v}\in\mathbb{Z}^{2}\setminus\\{\mathbf{0}\\}$ is the set
$\overline{H}_{\mathbf{v}}=\\{\mathbf{x}\in\mathbb{Z}^{2}|\
\mathbf{x}\cdot\mathbf{v}\geq 0\\}$, and the open half plane $H_{\mathbf{v}}$
is defined analogously to contain those $\mathbf{x}\in\mathbb{Z}^{2}$ that
satisfy $\mathbf{x}\cdot\mathbf{v}>0$. The boundary of the half plane is
$\overline{H}_{\mathbf{v}}\setminus H_{\mathbf{v}}$. We say that a finite set
$D\subseteq\mathbb{Z}^{2}$ has an _outer edge_ perpendicular to
$\mathbf{v}\in\mathbb{Z}^{2}\setminus\\{\mathbf{0}\\}$ if there is
$\mathbf{x}\in D$ such that $D\subseteq\mathbf{x}+\overline{H}_{\mathbf{v}}$
and there are at least two elements of $D$ on the boundary
$\mathbf{x}+(\overline{H}_{\mathbf{v}}\setminus H_{\mathbf{v}})$. See Fig. 1
for an illustration.

Figure 1: The set of black cells has an outer edge perpendicular to vector
$\mathbf{v}$.

######  Lemma 3.

Let $g,h$ be non-zero polynomials such that $\text{supp}(g)$ has an outer edge
perpendicular to $\mathbf{v}$. Then also $\text{supp}(gh)$ has an outer edge
perpendicular to $\mathbf{v}$.

###### Proof.

Let vector $\mathbf{u}\in\mathbb{Z}^{2}\setminus\\{\mathbf{0}\\}$ be
perpendicular to $\mathbf{v}$. By the hypotheses of the lemma there are
$\mathbf{x}\in\mathbb{Z}^{2}$ and a line polynomial $\alpha$ in the direction
$\mathbf{u}$ such that
$\text{supp}(g)\subseteq\mathbf{x}+\overline{H}_{\mathbf{v}}$ and
$\text{supp}(g-\alpha)\subseteq\mathbf{x}+H_{\mathbf{v}}$. Here $\alpha$
contains the terms of $g$ along the boundary of the half plane
$\mathbf{x}+H_{\mathbf{v}}$. Analogously, for any non-zero polynomial $h$
there exists $\mathbf{y}\in\mathbb{Z}^{2}$ and polynomial $\beta\neq 0$ that
is either a monomial or a line polynomial in the direction $\mathbf{u}$ such
that $\text{supp}(h)\subseteq\mathbf{y}+\overline{H}_{\mathbf{v}}$ and
$\text{supp}(h-\beta)\subseteq\mathbf{y}+H_{\mathbf{v}}$. But then
$\text{supp}(gh)\subseteq\mathbf{x}+\mathbf{y}+\overline{H}_{\mathbf{v}}$ and
$\text{supp}(gh-\alpha\beta)\subseteq\mathbf{x}+\mathbf{y}+H_{\mathbf{v}}$.
Because $\alpha\beta$ is a line polynomial in the direction $\mathbf{u}$, this
proves that the support of $gh$ has an outer edge perpendicular to
$\mathbf{v}$. ∎

######  Corollary 4.

If $f\neq 0$ has a line polynomial factor in the direction $\mathbf{u}$ then
$\text{supp}(f)$ has outer edges perpendicular to $\mathbf{v}$ and
$-\mathbf{v}$, where $\mathbf{v}$ is a vector perpendicular to $\mathbf{u}$.

###### Proof.

A line polynomial $g$ in the direction $\mathbf{u}$ has outer edges
perpendicular to $\mathbf{v}$ and $-\mathbf{v}$. The claim then follows
directly from Lemma 3. ∎

Because the convex hull of $\text{supp}(f_{L})$ is a triangle, it does not
have parallel outer edges and therefore no line polynomial factors.

######  Corollary 5.

Polynomial $f_{L}=1+X+Y$ has no line polynomial factors.

Remark. In fact, it is very easy to see that $f_{L}$ is an irreducible
polynomial, which directly implies Corollary 5.

Now we can prove that the Ledrappier subshift has the generalized Nivat
property.

######  Theorem 6.

Any low complexity $c\in X_{f_{L}}$ is periodic.

###### Proof.

In this proof we are going to need annihilators of $c$ over ${\mathbb{F}_{2}}$
and over $\mathbb{Z}$. We interpret $c$ as a configuration over $\mathbb{Z}$
using the renaming ${\mathbb{F}_{2}}\longrightarrow\mathbb{Z}$ that maps
$0_{\mathbb{F}_{2}}\mapsto 0_{\mathbb{Z}}$ and $1_{\mathbb{F}_{2}}\mapsto
1_{\mathbb{Z}}$. We write $\text{Ann}_{\mathbb{Z}}(c)$ for the annihilator
ideal of the configuration over $\mathbb{Z}$ obtained after this renaming. We
are going to prove the following stronger statement: if
$\text{Ann}_{\mathbb{Z}}(c)$ contains a non-zero polynomial then $c$ is
periodic. The result then follows from Lemma 1.

Let $c\in L$ be non-periodic. We first prove that
$\text{Ann}_{\mathbb{F}_{2}}(c)$ is the principal ideal generated by $f_{L}$,
that is, for every $g\in\text{Ann}_{\mathbb{F}_{2}}(c)$ there exists
$\alpha\in{\mathbb{F}_{2}}[X^{\pm 1},Y^{\pm 1}]$ such that $g=\alpha f_{L}$.
First, let $g\in\text{Ann}_{\mathbb{F}_{2}}(c)$ be a proper polynomial which
means that all exponents of variables are non-negative. Because $X=1+Y+f_{L}$
we can eliminate variable $X$: there exists a polynomial $\alpha(X,Y)$ and a
polynomial $\beta(Y)$ in variable $Y$ only such that
$g=\alpha(X,Y)f_{L}+\beta(Y)$. Because both $f_{L}$ and $g$ are annihilators
of $c$, $\beta(Y)\in\text{Ann}_{\mathbb{F}_{2}}(c)$ as well.

If $\beta\neq 0$ then it is either a single monomial (in which case $c=0$) or
a line polynomial annihilator of $c$. Any configuration with a line polynomial
annihilator is periodic in the direction of the polynomial. We conclude that
$\beta=0$ so that $g=\alpha f_{L}$, as claimed.

Consider then arbitrary $g\in\text{Ann}_{\mathbb{F}_{2}}(c)$ with possibly
some negative exponents. Because $g=X^{i}Y^{j}g^{\prime}$ for some
$i,j\in\mathbb{Z}$ and a proper polynomial
$g^{\prime}\in\text{Ann}_{\mathbb{F}_{2}}(c)$, we conclude that also in this
case $g$ is a multiple of $f_{L}$, and therefore we have that
$\text{Ann}_{\mathbb{F}_{2}}(c)$ is the principal ideal generated by $f_{L}$.

Now it remains to show that $\text{Ann}_{\mathbb{Z}}(c)$, the set of
annihilators over $\mathbb{Z}$, is trivial. Suppose by contrary that there is
a non-zero annihilator in $\text{Ann}_{\mathbb{Z}}(c)$. By Theorem 2 there
exists non-zero $(i_{1},j_{1}),\ldots,(i_{m},j_{m})\in\mathbb{Z}^{2}$ such
that
$(X^{i_{1}}Y^{j_{1}}-1)\cdots(X^{i_{m}}Y^{j_{m}}-1)\in\text{Ann}_{\mathbb{Z}}(c)$.
By performing computations modulo two instead, we have that
$(X^{i_{1}}Y^{j_{1}}-1)\cdots(X^{i_{m}}Y^{j_{m}}-1)\in\text{Ann}_{{\mathbb{F}_{2}}}(c)$.
But then this polynomial, which only has line polynomial factors, is a
multiple of $f_{L}$. All factors of line polynomials are line polynomials in
the same direction (or monomials) so that all irreducible factors of $f_{L}$
are line polynomials, contradicting Corollary 5. Here we used the fact that
every polynomial can be factored uniquely into its irreducible factors [2].

∎

##  3 Annihilators with Few Line Polynomial Factors

One of the key element in the proof of Theorem 6 is the fact that we can find
an annihilator with one variable eliminated from it. It turns out that this is
something we can do with other annihilators than $f_{L}$, and to do so we will
use some parts of elimination theory, so-called resultants. Everything needed
to understand this paper will be introduced but for more, Cox’s book [2] is a
good introduction.

###  3.1 Resultant

Usually resultant are defined for proper polynomials, so in order to stick
with usual definitions we define them likewise. We will still use them for
talking about Laurent polynomials, which is not a problem since from a Laurent
polynomial annihilator we can always obtain a proper one by multiplying it by
a suitable monomial.

Let $R$ be a field, e.g. $R={\mathbb{F}_{p}}$ for a prime $p$, and let
$K=R[Y]$ be the ring of polynomials with one variable $Y$. Then $K[X]=R[X,Y]$
is the ring of polynomials with two variables over $R$. Resultant can be
defined for polynomials with more than two variables, but two is all we need
here. Resultant can be defined formally as a determinant of some matrix with
coefficients in $K$, but for our purpose, all we need to know is that for any
$f,g\in R[X,Y]$, there exists a polynomial ${\text{Res}_{X}}(f,g)\in R[Y]$ in
variable $Y$ only with the following two properties:

######  Property 1.

The polynomials $f$ and $g$ have a common factor in $R[X,Y]$ if and only if
${\text{Res}_{X}}(f,g)=0$.

######  Property 2.

There exist $\alpha,\beta\in R[X,Y]$ such that

$\alpha f+\beta g={\text{Res}_{X}}(f,g).$

The second property exactly states that we can find a linear combination of
$f$ and $g$ that eliminates variable $X$.

######  Lemma 7.

Let $c$ be a power series over a field $R$. If $c$ is annihilated by two non-
zero polynomials $f$ and $g$ with no common factors then $c$ is two-periodic.

###### Proof.

Using Property 2, let $\alpha,\beta\in R[X,Y]$ be such that

$\alpha f+\beta g={\text{Res}_{X}}(f,g).$

Because $f$ and $g$ are both annihilators of $c$ so is
${\text{Res}_{X}}(f,g)$. Because $f$ and $g$ have no common factors, Property
1 tells us that ${\text{Res}_{X}}(f,g)\neq 0$. We found an annihilator which
is a line polynomial or a monomial (only with variable $Y$) so $c$ must be
periodic along $Y$.

Symmetrically, there also exist $\gamma,\delta\in R[X,Y]$ such that

$\gamma f+\delta g={\text{Res}_{Y}}(f,g).$

Again, ${\text{Res}_{Y}}(f,g)\neq 0$, so $c$ is also periodic along $X$. ∎

Remark. In [8] we analyzed the structure of annihilator ideals of
configurations over $\mathbb{Z}$, and an analogous result for the case of
$\mathbb{Z}$ follow from those considerations. We included here the simple
proof above for the sake of completeness, and in order to cover also the case
of arbitrary coefficient fields.

###  3.2 Main Result

Now we can easily generalize Theorem 6. We consider an algebraic subshift
$X_{f}$ over a finite field ${\mathbb{F}_{p}}$ defined by an annihilator
$f\in{\mathbb{F}_{p}}[X^{\pm 1},Y^{\pm 1}]$. A configuration
$c\in{\mathbb{F}_{p}}[[X^{\pm 1},Y^{\pm 1}]]$ will also be interpreted as a
configuration over $\mathbb{Z}$ by mapping the symbols by
$a_{{\mathbb{F}_{p}}}\mapsto a_{\mathbb{Z}}$ for all
$a\in\\{0,1,\dots,p-1\\}$. Then, as in the proof of Theorem 6, we can define
both $\text{Ann}_{\mathbb{F}_{p}}(c)$ and $\text{Ann}_{\mathbb{Z}}(c)$, and
use the fact that any $g\in\text{Ann}_{\mathbb{Z}}(c)$ is also in
$\text{Ann}_{\mathbb{F}_{p}}(c)$ when its coefficients are reduced modulo $p$.

######  Theorem 8.

Let $c\in X_{f}$ for a polynomial $f\in{\mathbb{F}_{p}}[X^{\pm 1},Y^{\pm 1}]$,
and suppose that $\text{Ann}_{\mathbb{Z}}(c)$ contains a non-zero polynomial.

  * •

If $f$ has no line polynomial factors then $c$ is two-periodic.

  * •

If all line polynomial factors of $f$ are in the same direction then $c$ is
periodic in this direction.

###### Proof.

By Theorem 2 there exists non-zero
$(i_{1},j_{1}),\ldots,(i_{m},j_{m})\in\mathbb{Z}^{2}$ such that
$(X^{i_{1}}Y^{j_{1}}-1)\cdots(X^{i_{m}}Y^{j_{m}}-1)\in\text{Ann}_{\mathbb{Z}}(c)$.
By performing computations modulo $p$ instead, we have that
$g(X,Y)=(X^{i_{1}}Y^{j_{1}}-1)\cdots(X^{i_{m}}Y^{j_{m}}-1)\in\text{Ann}_{{\mathbb{F}_{p}}}(c)$.

If $f$ has no line polynomial factors then $f$ and $g$ do not have any common
factors. By Lemma 7 then $c$ is two-periodic. This proves the first claim.

Suppose then that all line polynomial factors of $f$ are in the same
direction. Let $h$ be the greatest common divisor of $f$ and $g$ so that we
can write $f=f^{\prime}h$ and $g=g^{\prime}h$ where $f^{\prime}$ and
$g^{\prime}$ do not have common factors. Note that $h$ is a line polynomial:
as a factor of $g$ $h$ is a product of line polynomials, and as a factor of
$f$ these line polynomials are all in the same direction.

Because $c^{\prime}=hc$ is annihilated by both $f^{\prime}$ and $g^{\prime}$
it follows from Lemma 7 that $c^{\prime}$ is two-periodic. In particular,
there is a line polynomial $h^{\prime}$ in the direction of $h$ that
annihilates $c^{\prime}$. We have
$hh^{\prime}\in\text{Ann}_{{\mathbb{F}_{p}}}(c)$ so that $c$ is annihilated by
the line polynomial $hh^{\prime}$ and is therefore periodic in this direction.

∎

Using Lemma 1 we now immediately get that algebraic subshifts defined by an
annihilator with at most one line polynomial factor have the generalized Nivat
property.

######  Corollary 9.

Let $c\in X_{f}$ for a polynomial $f\in{\mathbb{F}_{p}}[X^{\pm 1},Y^{\pm 1}]$
whose line polynomial factors are all in the same direction. If $c$ has low
complexity then it is periodic.

Remark. Elements of the Ledrappier subshift are exactly the space-time
diagrams of the one-dimensional XOR cellular automaton. More generally, the
algebraic subshift $X_{f}$ defined by a polynomial of the form
$f(X,Y)=Y-g(X)\in{\mathbb{F}_{p}}[X^{\pm 1},Y^{\pm 1}]$ consists exactly of
the space-time diagrams of the one-dimensional additive cellular automaton
over ${\mathbb{F}_{p}}$ whose local rule is given by $g(X)$. See Section 9 of
[6] for a short discussion about additive cellular automata. If $g(X)$ has at
least two terms then the support of $f$ has triangular shape and therefore $f$
has no line polynomial factors. If $g(X)$ has one term then $f$ itself is a
line polynomial. In any case, Theorem 8 and Corollary 9 hold for the space-
time diagrams of all one-dimensional additive cellular automata over field
${\mathbb{F}_{p}}$.

##  4 Square Annihilators

After Corollary 9, it is natural to take a look at configurations annihilated
by polynomials with line polynomial factors in more directions. It turns out
that already products of two line polynomials include examples with and
without the generalized Nivat property. We first prove that the 4-dot system
defined by $(1+X)(1+Y)$ over ${\mathbb{F}_{2}}$ has the generalized Nivat
property and then we show that the system defined by $(1+X^{2})(1+Y^{2})$ does
not.

###  4.1 The 4-dot system

######  Definition 2.

The _4-dot system_ $S$ is the algebraic subshift $X_{f_{S}}$ over
${\mathbb{F}_{2}}$ defined by the annihilator $f_{S}=1+X+Y+XY=(1+X)(1+Y)$.

######  Theorem 10.

Every low complexity $c\in X_{f_{S}}$ is periodic.

###### Proof.

Similarly as before, we are going to prove the more general statement that if
$c$ has a non-trivial annihilator $p_{0}$ over $\mathbb{Z}$ then it is
periodic.

We first observe that $c=h+v$ for $h,v\in{\mathbb{F}_{2}}[[X^{\pm 1},Y^{\pm
1}]]$ that are $(1,0)$-periodic and $(0,1)$-periodic, respectively. Indeed, we
can take $h_{i,j}=c_{0,j}$ and $v_{i,j}=c_{i,0}+c_{0,0}$, for all
$i,j\in\mathbb{Z}$. Because $(1+X^{i})(1+Y^{j})$ is a multiple of $(1+X)(1+Y)$
over ${\mathbb{F}_{2}}$, polynomial $(1+X^{i})(1+Y^{j})$ annihilates $c$, for
all $i,j\in\mathbb{Z}$. This means that
$c_{i,j}=c_{0,j}+c_{i,0}+c_{0,0}=h_{i,j}+v_{i,j}$.

Using the periodicity of $h$ and $v$ we can write $h=\mathbbm{1}(X)s(Y)$ and
$v=t(X)\mathbbm{1}(Y)$, with $\mathbbm{1}(X)=\sum_{i\in\mathbb{Z}}X^{i}$ and
$s,t$ two formal series depending only one one variable. Let us define another
binary configuration $d$ by

$d(X,Y)=t(X)s(Y).$

In other words, $d$ is the configuration that has ones where both $h$ and $v$
have ones:

$d_{i,j}=\begin{cases}1\text{ if }h_{i,j}=v_{i,j}=1\\\ 0\text{
otherwise}\end{cases}.$

Interpreted in $\mathbb{Z}$, we have

$c=h+v-2d.$

This is the case since the two sides are identical modulo two and both sides
only contain values 0 and 1.

Consider next the polynomial

$p=p_{0}(X-1)(Y-1)$

over ${\mathbb{F}_{2}}$. Because $p_{0}$ annihilates $c$, and $X-1$ and $Y-1$
annihilate $h$ and $v$, respectively, we have that $pc=ph=pv=0$. Therefore
$pd=0$ as well, which can be written as

$p(X,Y)t(X)s(Y)=0,$

emphasizing the variable dependencies of the polynomials. We have the
following two cases:

_Case 1:_ Suppose that $p(X,Y)t(X)=0$. In $p(X,Y)$ we collect together terms
with the same power of variable $Y$, obtaining

$p(X,Y)=\sum_{j\in\mathbb{Z}}Y^{j}p_{j}(X)$

where at least some $p_{j}(X)$ is a non-zero polynomial. We have

$\sum_{j\in\mathbb{Z}}Y^{j}p_{j}(X)t(X)=0.$

This is an identity of formal power series so that $p_{j}(X)t(X)=0$ for all
$j\in\mathbb{Z}$. But then also $p_{j}(X)v=p_{j}(X)t(X)u(Y)=0$, so that $v$ is
annihilated by a non-zero horizontal line polynomial (or a non-zero monomial)
$p_{j}(X)$. We conclude that $v$ is horizontally periodic. But then also
$c=h+v$ is horizontally periodic as a sum of two horizontally periodic
configurations.

_Case 2:_ Suppose that $p(X,Y)t(X)\neq 0$. Now we collect in $p(X,Y)t(X)$
together variables with the same power of variable $X$, obtaining

$p(X,Y)t(X)=\sum_{i\in\mathbb{Z}}X^{i}q_{i}(Y),$

where at least some $q_{i}(Y)$ is a non-zero polynomial. Note that all
$q_{i}(Y)$ are polynomials because powers of the variable $Y$ only come from
the polynomial $p(X,Y)$. Because

$0=p(X,Y)d(X,Y)=p(X,Y)t(X)s(Y)=\sum_{i\in\mathbb{Z}}X^{i}q_{i}(Y)s(Y),$

we have that $q_{i}(Y)s(Y)=0$ for all $i\in\mathbb{Z}$. Analogously to case 1
above, this implies that $h$ is vertically periodic, and therefore also $c$ is
vertically periodic. ∎

###  4.2 An algebraic subshift without the generalized Nivat property

For some polynomials with two line polynomial factors, the associated subshift
does not have the generalized Nivat property. This is typically the case when
the annihilating polynomial allows the use of sublattices.

######  Theorem 11.

There exists a configuration $c$ over ${\mathbb{F}_{2}}$ annihilated by
$f_{T}=(1+X^{2})(1+Y^{2})$ which is not periodic but has low complexity.

###### Proof.

Let us take $c=h+v$, with

$h_{i,j}=\begin{cases}1\text{ if }j=0\text{ and }i\text{ even}\\\ 0\text{
otherwise}\end{cases}$ and $v_{i,j}=\begin{cases}1\text{ if }i=1\text{ and
}j\text{ even}\\\ 0\text{ otherwise}\end{cases}.$

Visually, $c$ is the superposition of a horizontal and a vertical line on two
disjoint sublattices, see Fig. 2. Clearly $h$ is one-periodic with periodicity
vector $(2,0)$ and $v$ is one-periodic with periodicity vector $(0,2)$. Their
sum $c$ is not periodic.

1111111111111111111111111111111111112222222222222222222222222222223333333333333333333333333333334444444444444444444444444

Figure 2: Sublattices of $c$ and shape $D$ superimposed. The horizontal line
is from $h$ and the vertical one from $v$.

The periodicity of $h$ and $v$ directly implies that $f_{T}$ annihilates $c$:
$h$ being $(2,0)$-periodic $(1+X^{2})h=0$ and, analogously, $v$ being
$(0,2)$-periodic $(1+Y^{2})v=0$. This means that
$f_{T}c=(1+X^{2})(1+Y^{2})h+(1+X^{2})(1+Y^{2})v=0$.

Figure 3: The shape $D$ of low complexity.

The last thing we have to check is that $c$ has low complexity, i.e, there is
a shape $D$ such that $P_{c}(D)\leq|D|$. It is sufficient to take $D$ to be
the scattered 3x3 square, as shown in Fig. 3. Patterns of shape $D$ in $c$
will only contain values from one of the four sublattices, depending on the
parity of its position. If $D$ is superimposed with sublattices 3 or 4, the
pattern is blank. With sublattice 1, it can only contain values from $h$, so
it can have four different values: blank, and the horizontal line crossing at
the top, the middle or the bottom. If it is on sublattice 2, then it has
values from $v$, and here again there are four different possibilities.
Counting the blank shape only once, we obtain $P_{c}(D)=1+3+3=7<9=|D|$.

∎

##  5 Conclusions

To prove Nivat’s conjecture it is enough to consider configurations of two-
dimensional algebraic subshifts over ${\mathbb{F}_{p}}$. We prove that
simplest subshifts do not contain a counter example to the conjecture, and
they even have the stronger property that any configuration that has low
complexity with respect to any finite shape is periodic. It remains open to
characterize which algebraic subshifts have this generalized Nivat property.
It remains also an interesting algorithmic problem to decide for a set of at
most $|D|$ allowed patterns of shape $D$, for some finite
$D\subseteq\mathbb{Z}^{2}$, whether there is a configuration all of whose
$D$-patterns are among the allowed patterns. We do not know if this emptyness
problem of low complexity subshifts of finite type is decidable in general,
but if the given patterns come from one of the algebraic subshifts studied in
this work then the emptyness problem is decidable by a standard argument
because any configuration with these patterns must be periodic. We also ask
whether the generalized Nivat property may fail for other reasons than having
the support of the defining polynomial in a proper sublattice of
$\mathbb{Z}^{2}$.

## References

  * [1] J. Cassaigne.  Subword complexity and periodicity in two or more dimensions.  In G. Rozenberg and W. Thomas, editors, Developments in Language Theory, pages 14–21. World Scientific, 1999.
  * [2] D. A. Cox, J. Little, and D. O’Shea.  Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra.  Springer, 4th edition, 2015.
  * [3] V. Cyr and B. Kra.  Nonexpansive $\mathbb{Z}^{2}$-subdynamics and Nivat’s conjecture.  Trans. Amer. Math. Soc., 367(9):6487–6537, 2015.
  * [4] V. Cyr and B. Kra.  Complexity of short rectangles and periodicity.  European Journal of Combinatorics, 52:146 – 173, 2016.
  * [5] C. Epifanio, M. Koskas, and F. Mignosi.  On a conjecture on bidimensional words.  Theor. Comput. Sci., 1-3(299), 2003.
  * [6] J. Kari.  Theory of cellular automata: A survey.  Theoretical Computer Science, 334(1):3 – 33, 2005.
  * [7] J. Kari and M. Szabados.  An Algebraic Geometric Approach to Nivat’s Conjecture.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pages 273–285, 2015.
  * [8] J. Kari and M. Szabados.  An Algebraic Geometric Approach to Nivat’s Conjecture.  preprint arXiv:1605.05929, May 2016.
  * [9] F. Ledrappier.  Un champ markovien peut être d’entropie nulle et mélangeant.  C. R. Acad. Sci. Paris Sér. A-B, 287(7):A561–A563, 1978.
  * [10] D. Lind and B. Marcus.  An Introduction to Symbolic Dynamics and Coding.  Cambridge University Press, 1995.
  * [11] A. Quas and L. Q. Zamboni.  Periodicity and local complexity.  Theor. Comput. Sci., 319(1-3):229–240, 2004.
  * [12] J. W. Sander and R. Tijdeman.  The rectangle complexity of functions on two-dimensional lattices.  Theor. Comput. Sci., 270(1-2):857–863, 2002.