#  $L_{\infty}$ norm minimization for nowhere-zero integer eigenvectors of the
block graphs of Steiner triple systems and Johnson graphs

E.A. Bespalov, I.Yu. Mogilnykh, K.V. Vorob’ev  Evgeny Andreevich Bespalov
iii Sobolev Institute of Mathematics, Novosibirsk, Russia<EMAIL_ADDRESS>Ivan Yurevich Mogilnykh
iii Sobolev Institute of Mathematics, Novosibirsk, Russia<EMAIL_ADDRESS>Konstantin Vasil’evich Vorob’ev
iii Sobolev Institute of Mathematics, Novosibirsk, Russia
<EMAIL_ADDRESS>
Bespalov, E.A., Mogilnykh, I.Yu., Vorob’ev K.V.

© 2023 Bespalov, E.A., Mogilnykh, I.Yu., Vorob’ev K.V.

This work was funded by the Russian Science Foundation under grant 22-21-00135

Received January, 1, 2023, published March, 1, 2023.

> Abstract.  We study nowhere-zero integer eigenvectors of the block graphs of
> Steiner triple systems and the Johnson graphs. For the first eigenvalue we
> obtain the minimums of $L_{\infty}$-norm for several infinite series of
> Johnson graphs, including $J(n,3)$ as well as general upper and lower
> bounds. The minimization of $L_{\infty}$-norm for nowhere-zero integer
> eigenvectors with the second eigenvalue of the block graph of a Steiner
> triple system $S$ is equivalent to finding the minimum nowhere-zero flow for
> Steiner triple system $S$. For the all Assmuss-Mattson Steiner triple
> systems of order at least $99$ we prove that this minimum is bounded above
> by $4$.
>
> Keywords: Steiner triple system, flow, strongly regular graph, Johnson
> graph, Grassmann graph, eigenvalue

##  1\. Introduction

A vector is called nowhere-zero integer (shortly NZI vector) if all of its
elements are nonzero integers. The infinity norm $\|v\|_{\infty}$ of a vector
$v$ is defined as the maximum of the absolute values of its elements.

Let $W_{S}$ be the point-block incidence matrix of Steiner triple system $S$.
A nowhere-zero integer vector $u$: $W_{S}u=0$ is called a nowhere-zero
$(\|u\|_{\infty}+1)$-flow for Steiner triple system $S$ [1]. It is not hard to
see that the right nullspace of the incidence matrix $W_{S}$ coincides with
the second eigenspace of the block graph of $S$ (see Proposition 4 below).

The minimum of $L_{\infty}$ norm for flows of Steiner triple systems were
considered in works [1], [2], [4]. Akbari, Burgess, Danziger and Mendelsohn
[3] showed that the norm of a flow in Steiner triple system of order $n$ is
upper bounded by $O(n^{2})$.

On the other hand, studies show that for particular families of Steiner triple
systems, the actual minimum of norm of flow is much smaller than $O(n^{2})$
and this fact finds similarities in a conjecture of Tutte on existence of a
$5$-flow for the graphs [24]. Speaking more precisely, all Steiner triple
systems of order $15$ have $3$-flows [1]. Furthermore, it was proven that some
well-known recursive classes of Steiner triple systems, such as direct product
construction, $2v+7$-construction admit a $3$-flow, given a $3$-flow in the
original Steiner triple system [4]. As for the $2v+1$-construction, the
resulting Steiner triple systems has $3$, $4$ or $5$-flow [3]. In Section 5 we
establish that any Assmuss-Mattson [6] Steiner triple system obtained from a
Steiner triple system $S$ of order at least $49$ has a $5$-flow, regardless of
the flow in the original system $S$.

One might consider a more general definition of a flow for any given natural
matrix $W$, which is, for example, the inclusion matrix of subsets [1] or
subspaces [23]. A flow in these cases is the sum of eigenvectors of a Johnson
or Grassmann graph with specific eigenvalues. For example, let $W$ be the
inclusion matrix of $2$-subsets and $k$-subsets of $n$-element set. In [1] it
was shown that for $k=3$, there is a nowhere-zero integer vector $v$: $Wv=0$,
$\|v\|_{\infty}=2$, i.e. a generalized $3$-flow. Note that any such vector is
an eigenvector of the Johnson graph $J(n,3)$ with third eigenvalue. Relying on
the properties of higher order inclusion matrices, the authors of [1] extended
the result and showed that a $3$-flow exists for the inclusion matrix of
$2$-subsets and $k$-subsets for any $k\geq 3$.

The perspective of the continuing studies of flows in Steiner triple systems
and some other structures implies the following natural question.

Problem 1. Given a distance-regular graph $\Gamma$ of diameter $d$ and its
rational eigenvalue $\theta_{i}(\Gamma),$ $0\leq i\leq d$, find

$min\\{\|u\|_{\infty}{\it+1}:u\mbox{ is a nowhere-zero integer
}\theta_{i}(\Gamma)\mbox{-eigenvector of }\Gamma\\},$

which we denote as $m(i,\Gamma)$ in below.

From results of Akbari et al. there is always a solution for Problem 1.

######  Theorem 1.

[1], [2] Let $\Gamma$ be a distance-regular graph with a rational eigenvalue
$\theta_{i}(\Gamma)$, $0\leq i\leq d$. Then there is a NZI
$\theta_{i}(\Gamma)$-eigenvector of $\Gamma$.

###### Proof..

By [2, Theorem 3] there is a nowhere-zero real eigenvector for every
eigenvalue of any distance-regular graph. By [1, Lemma 3.3] the existence of a
nowhere-zero real vector, belonging to the null space of a rational matrix
implies the existence of nowhere-zero integer vector in the null space. By
taking the matrix to be $A_{\Gamma}-\theta_{i}I$, where $A_{\Gamma}$ is the
adjacency matrix of $\Gamma$, we obtain the required. ∎

Definitions, notation and basic theory are in Section 2. The results of
Section 3 are presented in a general context: for $q$-ary Steiner triple
systems and Grassmann graphs; the classic Steiner triple systems and Johnson
graph are treated as a particular case. Recently, $q$-ary Steiner triple
systems were shown to exist asymptotically [19], however there is only one
explicit example [9] of order $13$. We consider a description of the
eigenspaces of the block graph of $q$-ary Steiner triple system in terms of
the point-block incidence matrix of $STS$. In particular, for the first
eigenvalues, we see that eigenvectors of the Grassmann graph $J_{q}(n,3)$ are
in a natural one-to-one correspondence with that of the block graph of $q$-ary
Steiner triple system $S$ order $n$: the restriction of any eigenvector of
$J_{q}(n,3)$ to the blocks of $S$ is an eigenvector of the block graph of $S$.
This relation between the first eigenspaces of STSs and $J_{q}(n,k)$ is in
spirit of [25], where an extension of eigenvectors of Johnson graphs to that
of Hamming graphs was established. Despite this strong connection, in Section
4 we show that the minimums of the $L_{\infty}$ norm for nowhere-zero
eigenvectors for both graphs are different for $q=1$. We establish lower and
upper bounds on the optimum norms of NZI $\theta_{1}(J(n,k))$-eigenvectors of
the Johnson graphs $J(n,k)$ and obtain the exact minimums for infinite series
of Johnson graphs $J(n,k)$. In particular, we completely solve the problem for
$k=3$ and all $n>63$ (see Theorem 5). The bounds on the $L_{\infty}$ norm of
the NZI eigenvectors of the block graphs of STSs with the second eigenvalue
(which is equivalent to finding $i$-flow for STSs for small $i$) are given in
Section 5. We start Section 5.1 with reviewing the existing results for flows
in projective and Bose Steiner triple systems which utilize the aspects of
cyclicity and resolvability of these designs. In Section 5.2 we show that any
Steiner triple system constructed by Assmuss-Mattson approach [6] of order at
least $99$ has a $5$-flow. The results of this section are described in terms
of flows of Steiner triple systems rather than eigenvectors of their block
graphs.

In Section 6 we discuss completely regular codes in the block graphs of
Steiner triple system. These objects are in the scope of current study, as the
minimum possible value of $L_{\infty}$ norm for nowhere-zero integer
eigenvectors is attained on a vector arising from a specific completely
regular code (see Proposition 2). From perspective of Cameron-Liebler line
classes [10], the completely regular codes in the block graphs of Steiner
triple system with the covering radius $1$ and the first eigenvalue are of
interest as they provide one of different variations [13], [17] of such
objects. The block graph of projective (Hamming) Steiner triple system of
order $2^{r}-1$ is isomorphic to the Grassmann graph $J_{2}(r,2)$ and all such
completely regular codes are exactly Cameron-Liebler line classes in
$PG(n-1,2)$. We conjecture that these codes comprise only the following
classic examples of Cameron-Liebler line classes: a point, hyperplane and
nonincident point-hyperplane pair (see Problem 2 in Section 6) and show that
there are no other codes for STSs of orders $13$ and $15$. These codes in the
block graphs of Steiner triple systems and affine Steiner triple systems in
particular, were considered in [18], where these objects and the above
mentioned conjecture were treated from the perspective of small support
eigenvectors of the block graphs.

##  2\. Definitions and notations

###  2.1. Johnson, Grassmann graphs, $q$-ary Steiner triple systems and their
block graphs

A regular graph of diameter $d$ is called distance-regular if there is an
array of integers

$\\{\beta_{0},\ldots,\beta_{d-1};\gamma_{1},\ldots,\gamma_{d}\\},$

such that for any vertices $x$ and $y$ at distance $i$, $i\in\\{0,\ldots,d\\}$
there are exactly $\beta_{i}$ neighbors of $y$ at distance $i+1$ from $x$ and
$\gamma_{i}$ neighbors of $y$ at distance $i-1$ from $x$. The array of
integers $\\{\beta_{0},\ldots,\beta_{d-1};\gamma_{1},\ldots,\gamma_{d}\\}$ is
called the intersection array of the distance-regular graph $\Gamma$. We say
that a nonzero vector $v$ is $\theta(\Gamma)$-eigenvector if
$A_{\Gamma}v=\theta(\Gamma)v$, where $A_{\Gamma}$ is the adjacency matrix of
$\Gamma$. In this case $\theta$ is called an eigenvalue of $\Gamma$. It is
well known that any distance-regular graph of diameter $d$ has exactly $d+1$
distinct eigenvalues, which we index in descending order:
$\theta_{0}(\Gamma)>\theta_{1}(\Gamma)>\ldots>\theta_{d}(\Gamma)$, note that
$\theta_{0}(\Gamma)$ is the valency of the graph.

The vertices of the Grassmann graph $J_{q}(n,k)$ are $k$-subspaces of the
finite vector space $\mathbb{F}_{q}^{n}$ over the field $\mathbb{F}_{q}$ and
the edges are pairs of subspaces meeting in $(k-1)$-subspace. We also include
a limit case of $q=1$ as we define the Johnson graph $J(n,k)$ (also denoted by
$J_{1}(n,k)$) to be the graph with the vertex set being $k$-subsets of
$\\{1,\ldots,n\\}$ and edges being pairs of subsets meeting in $(k-1)$ set.
Let $[^{n}_{k}]_{q}$ be the Gaussian binomial coefficient and $[^{n}_{k}]_{1}$
be the ordinary binomial coefficient. The $k+1$ eigenvalues of $J_{q}(n,k)$,
$q\geq 1$ are as follows:

$\theta_{i}(J_{q}(n,k))=q^{k+1}[^{k-i}_{1}]_{q}[^{n-k-i}_{1}]_{q}-[^{i}_{1}]_{q},0\leq
i\leq k.$

By a $q$-ary Steiner triple system (briefly, STS) $S$ we mean a collection of
$3$-subspaces (called blocks) of $\mathbb{F}_{q}^{n}$ such that any
$2$-subspace of $\mathbb{F}_{q}^{n}$ is in exactly one subspace in $S$. By
letting $q=1$ we include Steiner triple system in the traditional sense in the
definition above, i.e. a collection of $3$-subsets of $\\{1,\ldots,n\\}$
(called blocks or triples) such that any $2$-subset is in exactly one block. A
$1$-subspace of $\mathbb{F}_{q}^{n}$ ($1$-subset of $\\{1,\ldots,n\\}$) is
called a point of $S$. By the order of $S$, we mean the dimension $n$ of the
ambient space $F_{q}^{n}$ (the number of points for $q=1$).

The incidence matrix of a $q$-ary Steiner triple system $S$ is the matrix
$W_{S}$, whose rows are indexed by the points of $S$ and the columns are
indexed by its blocks:

$(W_{S})_{i,T}=\begin{cases}1,&i\subseteq T\\\
0,&\text{otherwise}\end{cases}.$

Similarly, we define the point-block incidence matrix $W$ of $J_{q}(n,k)$ with
rows indexed by the points ($1$-subspaces) and columns are indexed by the
$k$-subspaces of $\mathbb{F}_{q}^{n}$. The block intersection graph of
$q$-ary, $q\geq 1$, STS $S$ denoted by $\Gamma_{S}$, has the blocks of $S$ as
vertices and blocks having a nonempty intersection as edges. It is well-known
that this graph is strongly-regular [5] and has the following eigenvalues:

$\theta_{1}(\Gamma_{S})=\frac{[^{n}_{1}]_{q}-1}{[^{3}_{1}]_{q}-1}-[^{3}_{1}]_{q}-1,$
$\theta_{2}(\Gamma_{S})=-[^{3}_{1}]_{q}.$

The blocks of any $q$-ary STS, $q\geq 1$, of order $n$ could be treated as a
set of vertices of $J_{q}(n,3)$. So the block intersection graph can be viewed
as the subgraph induced by the blocks of STS in the distance-$2$ graph of
$J_{q}(n,3)$. A Steiner triple system is called resolvable if its blocks are
parted into parallel classes, i.e. collections of pairwise nonintersecting
blocks with the size of each class equal to $\frac{n}{3}$.

###  2.2. Completely regular codes

Given $C\subseteq V(\Gamma)$, a distance partition with respect to $C$ is
$C_{0}=C,\ldots,C_{\rho}$:

$C_{i}=\\{x:d(x,C)=i\\}.$

The maximum of all $i$’s is denoted by $\rho$ and is called the covering
radius of $C$. A subset $C\subseteq V(\Gamma)$ is called a completely regular
code if there are numbers $\alpha_{0},\ldots,\alpha_{\rho}$,
$\beta_{0},\ldots,\beta_{\rho-1}$, $\gamma_{1},\ldots,\gamma_{\rho}$ such that
any vertex of $C_{i}$ is adjacent to exactly $\alpha_{i}$, $\beta_{i}$,
$\gamma_{i}$ vertices of $C_{i},C_{i+1}$ and $C_{i-1}$ respectively, for
$i=0,\dots\rho$ and $\gamma_{0}=\beta_{\rho+1}=0.$ The array
$\\{\beta_{0},\ldots,\beta_{\rho-1};\gamma_{1},\ldots,\gamma_{\rho}\\}$ is
called the intersection array of the completely regular code $C$. For a
completely regular code C consider the following tridiagonal
$(\rho+1)\times(\rho+1)$ matrix

$\left(\begin{array}[]{cccccc}\alpha_{0}&\beta_{0}&0&0&\ldots&0\\\
\gamma_{1}&\alpha_{1}&\beta_{1}&0&\ldots&0\\\ .&.&.&.&.&.\\\ .&.&.&.&.&.\\\
0&.&0&\gamma_{\rho-1}&\alpha_{\rho-1}&\beta_{\rho-1}\\\
0&.&0&0&\gamma_{\rho}&\alpha_{\rho}\end{array}\right),$

which we call the intersection matrix of the completely regular code $C$.

The eigenvalues of this matrix are called the eigenvalues  of the completely
regular code $C$. It is well-known that the eigenvalues of a completely
regular code in a regular graph are necessarily eigenvalues of the graph,
which is known as Lloyd’s theorem.

Given a set of vertices $C$ in a graph $\Gamma$ we denote by $\chi_{C}$ its
characteristic vector in the vertex set of the graph.

######  Proposition 1.

(Folklore) Let $C$ be a completely regular code with $\rho=1$, eigenvalue
$\theta_{i}(\Gamma)$ and intersection array $\\{\beta_{0};\gamma_{1}\\}$ in a
distance-regular graph $\Gamma$. Then the vector
$\beta_{0}\chi_{C}-\gamma_{1}\chi_{V(\Gamma)\setminus C}$ is a
$\theta_{i}$-eigenvector of $\Gamma$. Moreover, any $\theta_{i}$-eigenvector
(up to multiplicity) with only two values can be obtained in this manner.

The current study of the completely regular codes from the point of view of
Problem 1 is inspired by the following statement.

######  Proposition 2.

Let $\Gamma$ be a distance-regular graph. Then $m(i,\Gamma)\geq 2$,
$m(i,\Gamma)=2$ if and only if there is a completely regular code with
$\rho=1$, intersection array $\\{\beta_{0};\beta_{0}\\}$ and eigenvalue
$\theta_{i}(\Gamma)$ in $\Gamma$.

###### Proof..

We obviously have $m(i,\Gamma)\geq 2$ and $m(i,\Gamma)$ attains the lower
bound $2$ if and only if there is an $\theta_{i}(\Gamma)$-eigenvector with
values $+1$ and $-1$ only. From Proposition 1 we obtain the required. ∎

For the completely regular codes with $\rho=1$ and the second eigenvalue, we
see that they are equivalent to 1-subdesigns of Steiner triple system.

######  Proposition 3.

Let $S$ be a Steiner triple system of order $n$. A set $S^{\prime}\subset S$
is a completely regular code with $\rho=1$ and eigenvalue
$\theta_{2}(\Gamma_{S})$ if and only if $S^{\prime}$ is a 1-design.

###### Proof..

Let $S^{\prime}$ be a subset of blocks of $S$. The set $S^{\prime}$ is
$1$-$(n,3,\lambda)$-design if and only if the vector
$W_{S}((\frac{n-1}{2}-\lambda)\chi_{S^{\prime}}-\lambda\chi_{S\setminus
S^{\prime}})$ is all-zero, where $W_{S}$ is the point-block incidence matrix
of STS $S$. This follows from the fact that any point of $S$ belongs to
$\frac{n-1}{2}$ and $\lambda$ blocks of $S$ and $S^{\prime}$. In view of
Proposition 4.1 below this is equivalent to
$(\frac{n-1}{2}-\lambda)\chi_{S^{\prime}}-\lambda\chi_{S\setminus S^{\prime}}$
being a $\theta_{2}(\Gamma_{S})$-eigenvector. As any two-valued eigenvector of
the graph corresponds to a completely regular code with $\rho=1$, see
Proposition 1, we obtain the required.

∎

##  3\. A description of the eigenspaces of the block graphs of STS and the
first eigenspace of $J_{q}(n,k)$

Firstly, we consider the following auxiliary fact.

######  Theorem 2.

[7, Theorem 1] Let $\overline{\Gamma}$ be a biregular bipartite graph with
valencies $c$ and $c^{\prime}$ and the halved graphs $\Gamma$ and
$\Gamma^{\prime}$ and let $I$ denote the incidence matrix of two parts of
$\overline{\Gamma}$. Let any pair of vertices of $V(\Gamma)$ at distance $2$
in $\overline{\Gamma}$ have exactly $m$ common neighbors and any pair of
vertices of $V(\Gamma^{\prime})$ at distance $2$ in $\overline{\Gamma}$ have
exactly $m^{\prime}$ common neighbors. The following holds

1\. Let $u$ be a $\theta$-eigenvector of $\Gamma$, $\theta\neq-\frac{c}{m}$.
Then the vector $Iu$ is a
$\frac{c-c^{\prime}+m\theta}{m^{\prime}}$-eigenvector of $\Gamma^{\prime}$.

2\. Given a vector $u$, $Iu$ is all-zero vector if and only if $u$ is
$-\frac{c}{m}$-eigenvector of $\Gamma^{\prime}$.

Example 1. Consider the biregular graph whose parts are the blocks and the
points of a $q$-ary STS $S$ with adjacency being point-block inclusion. The
halved graphs are the block graph $\Gamma_{S}$ (as $\Gamma$ in Theorem 2) and
the complete graph $K_{[^{n}_{1}]_{q}}$ (as $\Gamma^{\prime}$ in Theorem 2) on
the points of $S$, $I$ is the point-block incidence matrix $W_{S}$ of the
design $S$. It is not hard to see that parameters in Theorem 2 are
$m=m^{\prime}=1$, $c=[^{3}_{1}]$,
$c^{\prime}=\frac{[^{n}_{1}]_{q}-1}{[^{3}_{1}]_{q}-1}$.

We obtain the following relation between the null-spaces of the incidence
matrix of Steiner triple system and the second eigenspace.

######  Proposition 4.

Let $S$ be a $q$-ary STS $S$, $q\geq 1$ with the point-block intersection
matrix $W_{S}$. Then

1\. A vector u fulfills $W_{S}u$=0 if and only if $u$ is a
$\theta_{2}(\Gamma_{S})$-eigenvector of $\Gamma_{S}$.

2\. A vector $v$ is a $(\|v\|_{\infty}+1)$-flow for $S$ if and only if $v$ is
a nowhere-zero integer $\theta_{2}(\Gamma_{S})$-eigenvector of the block graph
$\Gamma_{S}$ of the Steiner triple system $S$.

###### Proof..

We apply Theorem 2.2 for the graph in Example 1. ∎

###  3.1. The first eigenspaces of the block graphs of STSs, Grassmann and
Johnson graphs

In the theorem below by $W$ we denote the incidence matrix of all
$1$-subspaces of $\mathbb{F}_{q}^{n}$ ($1$-subsets of $\\{1,\ldots,n\\}$ for
$q=1$) vs $k$-subspaces $\mathbb{F}_{q}^{n}$ ($1$-subsets of
$\\{1,\ldots,n\\}$ for $q=1$). A vector is a restriction of a vector $v$ to a
set $S$ if the vector is obtained deleting all the elements of $v$ having
indices outside of $S$. This operation in coding theory is also known as
puncturing. Contrary, when we say that a vector is an extention of $v$ if it
is obtained by appending some extra elements to $v$.

######  Theorem 3.

Let $U$ be the set of all real-valued vectors of the vertices of the graph
$J_{q}(n,1)$, $q\geq 1$ with the sum of values is zero. Then

1\. $U$ is the set of all $\theta_{1}(J_{q}(n,1))$-eigenvectors of
$J_{q}(n,1)$.

2\. [14][20] $W^{T}(U)$ is the set of all
$\theta_{1}(J_{q}(n,k))$-eigenvectors of $J_{q}(n,k)$.

3\. If $S$ is a $q$-ary Steiner triple system of order $n$, then
$W_{S}^{T}(U)$ is the set of all $\theta_{1}(\Gamma_{S})$-eigenvectors of its
block graph $\Gamma_{S}$.

4\. The restriction of each $\theta_{1}(J_{q}(n,3))$-eigenvector of
$J_{q}(n,3)$ to the blocks of $S$ is $\theta_{1}(\Gamma_{S})$-eigenvector of
its block graph $\Gamma_{S}$ and each $\theta_{1}(\Gamma_{S})$-eigenvectors of
its block graph $\Gamma_{S}$ is extended to a unique
$\theta_{1}(J_{q}(n,3))$-eigenvector of $J_{q}(n,3)$.

5\. If $S$ is a $q$-ary Steiner triple system of order $n$, then
$m(1,\Gamma_{S})\leq m(1,J_{q}(n,[^{3}_{1}]_{q}))$.

###### Proof..

1\. The graph $J_{q}(n,1)$ is the complete graph $K_{[^{n}_{1}]_{q}}$. Since
$\theta_{1}(J_{q}(n,1))=-1$, we see a $(-1)$-eigenvector $u$ of
$K_{[^{n}_{1}]_{q}}$ is such that $\sum\limits_{x\in
K_{[^{n}_{1}]_{q}}}u_{x}=0$ and vice versa.

2\. For the Johnson graphs $J(n,k)$ this property was established by Delsarte
[14]. For Grassmann graphs the proof could be found in [20]. We note that the
result follows by consecutively applying Theorem 2 to the pairs of the graphs
$J_{q}(n,i)$ and $J_{q}(n,i+1)$ for $i=0,\ldots,k-1$. The graph are the halved
graphs of the bipartite graph, with adjacency being incidence of $i$-subspaces
into $i+1$-subspace of $\mathbb{F}_{q}^{n}$ (which is $\overline{\Gamma}$ in
Theorem 2).

3\. In view of Theorem 2 consider the bipartite graph $\overline{\Gamma}$
where adjacency is the containment relation for the vertices of $J_{q}(n,1)$
and $J_{q}(n,k)$ which are subspaces (or subsets for q=1). The graph is the
same as in Example 1 but conversely to it, the complete graph
$K_{[^{n}_{1}]_{q}}$ is denoted by $\Gamma$ and the block intersection graph
of $S$ is denoted by $\Gamma^{\prime}$. The values mentioned in Theorem 2 are
$c=\frac{[^{n}_{1}]_{q}-1}{[^{3}_{1}]_{q}-1}$, $c^{\prime}=[^{3}_{1}]$,
$m=m^{\prime}=1$. By Theorem 2, we see that any vector of $W_{S}^{T}(U)$ is a
$c-c^{\prime}+\theta_{1}(J_{q}(n,1))=\frac{[^{n}_{1}]_{q}-1}{[^{3}_{1}]_{q}-1}-[^{3}_{1}]_{q}-1=\theta_{1}(\Gamma_{S})$-eigenvector
of the block graph $\Gamma_{S}$.

On the other hand, we apply Theorem 2 to $\overline{\Gamma}$ with interchanged
the roles of $\Gamma$ and $\Gamma^{\prime}$. We see that any
$\theta_{1}(\Gamma_{S})$-eigenvector $v$ implies that $W_{S}v$ is a
$\theta_{1}(J_{q}(n,1))$-eigenvector of the graph $J_{q}(n,1)$. Therefore,
$W_{S}^{T}$ establishes an isomorphism between the first eigenspaces of
$J_{q}(n,1)$ and $\Gamma_{S}$.

4\. From the second and third statements of the theorem, we see that
$W_{S}^{T}$ ($W_{J_{q}(n,3)}^{T}$ respectively) settles an isomorphism between
the first eigenspaces of the complete graph and the block graph (the graph
$J_{q}(n,k)$ respectively). Each STS $S$ could be treated as vertices of
$J_{q}(n,3)$ and the rows of the block-point incidence matrix $W_{S}^{T}$ for
$q$-ary STS $S$ form a subset of the rows of the block-point incidence matrix
$W_{J_{q}(n,3)}^{T}$ for $J_{q}(n,3)$, which implies the required.

5\. From the fourth statement of the current theorem we see that the
restriction of a $\theta_{1}(J_{q}(n,3))$-eigenvector $v$ of $J_{q}(n,3)$ to
the blocks of $S$ is an $\theta_{1}(\Gamma_{S})$-eigenvector $v^{\prime}$ of
$S$. Obviously the norm is not increased upon reduction, i.e.:
$\|v\|_{\infty}\geq\|v^{\prime}\|_{\infty}$.

∎

Remark 1. When $q$ is $1$ (i.e. for STS in traditional sense and Johnson
graphs) the bound in Theorem 3.5 is not sharp for as we show in the next
Section that for STS $S$ of order $n$ $m(1,\Gamma_{S})\leq 5$ whereas
$m(1,J(n,3))\geq 6$.

##  4\. Minimum of $L_{\infty}$ norm on nowhere-zero integer eigenvector for
the block graphs of STSs and Johnson graphs

In the rest of the paper, we set $q=1$ and consider Steiner triple systems in
the classical sense.

###  4.1. Minimum of $L_{\infty}$ norm of nowhere-zero integer eigenvectors
with the first eigenvalue for Johnson graphs

In this subsection we denote by $(n,k)$ the greatest common divisor of $n$ and
$k$.

######  Lemma 1.

Any $\theta_{1}(J(n,k))$-eigenvector of $J(n,k)$ is equal to $W^{T}u$, where
$u$ is a real-valued eigenvector of $J(n,1)$,
$\sum\limits_{i=1,\ldots,n}u_{i}=0$. If $W^{T}u$ is an integer
$\theta_{1}(n,k)$-eigenvector of $J(n,k)$, then $u$ is such that $u_{i}$ and
$u_{j}$ have the same fractional parts for all $1\leq i,j\leq n$. Moreover,
the fractional parts equal $\frac{r}{s}$, where $r$ and $s$ are some non-
negative integers such that $0\leq r<s$, $(r,s)=1$ and $s$ is a divisor of
$(n,k)$.

###### Proof..

By Theorem 3 we see that any $\theta_{1}(J(n,k))$-eigenvector of $J(n,k)$ is
equal to $W^{T}u$, where $u$ is such that $\sum\limits_{i=1,\ldots,n}u_{i}=0$.
Let us prove that $u_{i}$ and $u_{j}$ have the same fractional parts for any
$i\neq j$. Consider some pairwise distinct positions
$i_{1}=i,i_{2}\ldots,i_{k}$, which are different from $j$. By hypothesis of
the theorem we have $u_{i}+u_{i_{2}}+\ldots+u_{i_{k}}$ and
$u_{j}+u_{i_{2}}+\ldots+u_{i_{k}}$ are integers. Hence, $u_{i}-u_{j}$ is an
integer and $u_{i}$ and $u_{j}$ have the same fractional parts. Denote this
fractional part by $\alpha$. Consider some $k$ elements of $u$:
$u_{i_{1}}\ldots,u_{i_{k}}$. We have that the sum $u_{i_{1}}+\ldots+u_{i_{k}}$
is integer (since $W^{T}u$ is an integer vector). On the other hand, this sum
has the same fractional part as $k\alpha$. Hence, $\alpha$ is rational and can
be represented as $\frac{r}{s}$, where $r$ and $s$ are non-negative integers,
$0\leq r<s$. Also we have $\frac{kr}{s}$ is integer, hence, $s$ is a divisor
of $k$. Since $\sum\limits_{i=1}^{n}u_{i}=0$, $\frac{nr}{s}$ is integer and,
hence, $s$ is a divis or of $n$. Therefore, $s$ is a divisor of $(n,k)$. ∎

######  Proposition 5.

If $n\geq 2k$ then we have $m(1,J(n,k))\leq\frac{n-k}{(n,k)}+1$.

###### Proof..

For this statement we take the vector

$u^{T}=(\frac{1}{(n,k)},\ldots,\frac{1}{(n,k)},-\frac{n-1}{(n,k)}),$

of length $n$, where $\frac{1}{(n,k)}$ is repeated $n-1$ times. The vector
$W^{T}u$ has two different values $\frac{k}{(n,k)}$ and $-\frac{n-k}{(n,k)}$.
Since $n\geq 2k$, we have $\|W^{T}u\|_{\infty}=\frac{n-k}{(n,k)}$. ∎

Note that in Proposition 5 the bound tends to infinity when $n$ is growing as
a function of $k$. However, for a ”small” $n$, for example $n=2k$, it can be
sharp. In the following statements we provide further upper bounds for odd and
even cases of $k$.

######  Proposition 6.

Let $k$ be odd. Then

1\. If $n$ is even then $m(1,J(n,k))\leq k+1$.

2\. If $n$ is odd then $m(1,J(n,k))\leq 2k+1$.

###### Proof..

The vector $W^{T}u$ is an $\theta_{1}(J(n,k))$-eigenvector of $J(n,k)$ if
$\sum\limits_{i=1,\ldots,n}u_{i}=0$.

1) For the first statement we take the vector

$u^{T}=(1,\ldots,1,-1,\ldots,-1),$

of length $n$ with $\frac{n}{2}$ positions with value $1$ and $\frac{n}{2}$
positions with value $-1$.

2) For the second statement we take the vector

$u^{T}=(k+1,-1,\ldots,-1,1,\ldots,1),$

of length $n$ with $\frac{n-k-2}{2}$ positions with value $1$, $\frac{n+k}{2}$
positions with value $-1$, where $u_{1}=k+1$. ∎

######  Proposition 7.

Let $k$ be even and $\gamma$ be the smallest positive integer number that does
not divide $k$. We have the following.

1\. If $n$ is divisible by $\gamma$ then
$m(1,J(n,k))\leq(\lfloor\frac{\gamma}{2}\rfloor+1)k+1$.

2\. If $n$ is not divisible by $\gamma$ then
$m(1,J(n,k))\leq(\lfloor\frac{\gamma}{2}\rfloor+1)(2k+\beta-1)+1$, where
$\beta$ is the remainder of division of $n-(k+1)$ by $\gamma$.

###### Proof..

By the hypothesis of the proposition, $n-(\beta+k+1)=q\gamma$ for some
positive integers $q$ and $\beta$. Let us describe a vector $u$, which is an
eigenvector of the graph $J(n,1)$. Divide the first $n-(\beta+k+1)$ positions
into $\gamma$ blocks. If $\gamma$ is odd then each block consists from
$\lfloor\frac{\gamma}{2}\rfloor$ positions with value
$\lfloor\frac{\gamma}{2}\rfloor+1$ and $\lfloor\frac{\gamma}{2}\rfloor+1$
positions with value $-\lfloor\frac{\gamma}{2}\rfloor$. If $\gamma$ is even
then each block consists from $\lfloor\frac{\gamma}{2}\rfloor-1$ positions
with value $\lfloor\frac{\gamma}{2}\rfloor+1$ and
$\lfloor\frac{\gamma}{2}\rfloor+1$ positions with value
$-\lfloor\frac{\gamma}{2}\rfloor+1$. Note that we describe all $\gamma$
positions in each block and the sum of the values in each block equals $0$. We
define the values for the remaining $k+\beta+1$ positions of $u$. We set one
element to be equal to $-(k+\beta)(\lfloor\frac{\gamma}{2}\rfloor+1)$ and the
other $(k+\beta)$ elements to be $(\lfloor\frac{\gamma}{2}\rfloor+1)$. The sum
of values in all positions equals $0$ and sum of values in any $k$ positions
is integer.

Let us prove that the sum of values in any $k$ positions is not $0$. If one of
the elements in these positions is
$-(\beta+k)(\lfloor\frac{\gamma}{2}\rfloor+1)$ then the sum is less than $0$
because the absolute values of all other elements is not greater than
$\lfloor\frac{\gamma}{2}\rfloor+1$.

Consider the case $\gamma$ is even i.e. $\gamma=2l$. Take $x$,
$x\in\\{0,1,\ldots,k\\}$ positions with values $l+1$ and $k-x$ positions with
values $-l+1$. The sum of the values in these positions equals
$lx+x-kl+k+lx-x=2lx-k(l-1)$ which is $0$ if and only if

$2lx=k(l-1).$

Let $l$ be odd. From the equality above we see that $k$ is divisible by odd
$l$ and by $2$ from the condition of the Proposition, so $k$ is divisible by
$\gamma=2l$, which contradicts the definition of $\gamma$. If $l$ is even,
then $l-1$ is odd. Hence, again from the equality above we see that $k$ should
be divisible by $\gamma=2l$, a contradiction.

Consider the case when $\gamma$ is odd, i.e. $\gamma=2l+1$. Take $x$
positions, $x\in\\{0,1,\ldots,k\\}$ with value $l+1$ and $k-x$ positions with
value $-l$. The sum of the values in these positions equals $lx+x-kl+lx$. If
this sum equals $0$ then $x(2l+1)=kl$. Since $k$ is not divisible by
$\gamma=2l+1$, then this sum is equal to $0$.

Therefore, $W^{T}u$ is NZI. If $n$ is divisible by $\gamma$, then
$\|W^{T}u\|_{\infty}=(\lfloor\frac{\gamma}{2}\rfloor+1)k$. If $n$ is not
divisible by $\gamma$, then
$\|W^{T}u\|_{\infty}=(\lfloor\frac{\gamma}{2}\rfloor+1)(2k+\beta-1)$. ∎

In the following Lemmas we study the structural properties of NZI vector as we
are working towards lower bounds on $m(1,J(n,k))$.

######  Lemma 2.

Let $u$ be a real-valued vector indexed by the vertices of the graph $J(n,1)$
and $\sum\limits_{i=1,\ldots,n}u_{i}=0$ that has at least $k$ positions with
value that equals $a+\frac{r}{s}$ and at least $k$ positions with value that
equals $-b+\frac{r}{s}$ for some non-negative integers $a,b,r$ and $s$, where
$b\neq 0,0\leq r<s,(n,s)=1\text{ and }s\text{ is divisor of }(n,k),$. If
$W^{T}u$ is a NZI $\theta_{1}(J(n,k))$-eigenvector of $J(n,k)$ then the number
$\frac{k(bs-r)}{s(a+b)}$ is not integer.

###### Proof..

Take $x$, $0\leq x\leq k$, positions of $u$ with value $a+\frac{r}{s}$ and
$k-x$ positions with the value $-b+\frac{r}{s}$. The sum of these values
equals $x(a+b)+\frac{kr}{s}-bk$. This sum equals $0$ if and only if
$x=\frac{(bs-r)k}{s(a+b)}$ is an integer. ∎

######  Lemma 3.

Let $u$ be a real-valued vector indexed by the vertices of the graph $J(n,1)$,
$\sum\limits_{i=1,\ldots,n}u_{i}=0$ such that $W^{T}u$ is NZI and
$\|W^{T}u\|_{\infty}+1=m(1,J(n,k))$. Let $n>j^{2}+2kj+3k-j-\frac{j^{2}}{k}$,
where $j=2k$ if $k$ is odd and
$j=(\lfloor\frac{\gamma}{2}\rfloor+1)(2k+\gamma)$ if $k$ is even, $\gamma$ be
the smallest positive integer number that is not a divisor of $k$. Then $u$
has at least $k$ positions with the same positive value and at least $k$
positions with the same negative value.

###### Proof..

If vector $u$ has $k$ positions with value $0$ then an element of $W^{T}u$ is
zero. Hence, at least $n-k+1$ positions of $u$ has nonzero values. By
Propositions 6 and 7 we have that $\|W^{T}u\|_{\infty}\leq j$, where $j=2k$ if
$k$ is odd and $j=(\lfloor\frac{\gamma}{2}\rfloor+1)(2k+\gamma)$ if $k$ is
even. Here $\gamma$ is the smallest positive integer number that does not
divide $k$. Also denote by $x$ the number of positions with positive values
and by $y$ the number of positions with negative values.

Let us denote $m=\frac{j}{k}$. By Lemma 1 the values of the vector $u$ in all
positions have the same fractional part. If $u$ does not have $k$ positions
with the same value then there are not more than $k-1$ positions with integer
part $i$ for any nonnegative $i$. So there are not more than $(\lfloor
m\rfloor+1)(k-1)$ positions with integer part not more than $\lfloor
m\rfloor$. So, if $x>(m+2)(k-1)\geq\lfloor m\rfloor(k-1)$ then there are at
least $k$ positions with the same positive value or there are $k$ positions
with values that are more than $\lfloor m\rfloor+1>m$. In the latter case we
have $\|W^{T}u\|_{\infty}>mk=j$, a contradiction. Analogously, if
$y>(m+2)(k-1)$ then there are at least $k$ positions with the same negative
value or we have a contradiction with the minimality of norm. If
$n-k+1>2(m+2)(k-1)$ then $x$ or $y$ is more than $(m+2)(k-1)$. Without loss of
generality, we assume that $x>(m+2)(k-1)$. If $y$ is also more than
$(m+2)(k-1)$, then the Lemma holds, so we consider the case

(1) $y\leq(m+2)(k-1)$

in more details below.

In view of Lemma 1, we have that the positive values of $u$ are not less than
$\frac{1}{k}$. This, combined with inequality (1) implies that the sum of all
positive values in $u$ is such that

(2)
$\sum\limits_{i=1,\ldots,n,u_{i}>0}u_{i}\geq\frac{x}{k}\geq\frac{n-k+1-y}{k}\geq\frac{n-k+1-(m+2)(k-1)}{k}.$

If $y<k$ we consider the sum of $y$ positions with negative values and $k-y$
positions with the smallest positive values in the vector $u$. Since
$\sum\limits_{i=1,\ldots,n}u_{i}=0$ the absolute value of this sum equals the
sum of $x-k+y$ positions with the largest positive values. Since each positive
value in $u$ is at least $\frac{1}{k}$, this sum is not less than
$\frac{x-k+y}{k}\geq\frac{(n-k+1-y)-k+y}{k}=\frac{n-2k+1}{k}$. Hence, because
$n>j^{2}+2kj+3k-j-\frac{j^{2}}{k}>jk+2k+1$, which we have by the hypothesis of
the Lemma, we obtain $\|W^{T}u\|_{\infty}>j$, which is a contradiction.

If $y\geq k$ we consider the $k$ minimum negative values of $u$. The sum of
these values is not greater than average negative value $k$ times. Because
$\sum\limits_{i=1,\ldots,k}u_{i}=0$, the absolutes of average negative and
average positive coincide. So, from (2) the average amoung all negative is
less then or equal to $-\frac{(n-k+1-y)}{ky}$ and there are pairwise distinct
$i_{1},\ldots,i_{k}$:

(3) $\sum\limits_{l=1,\ldots,k}u_{i_{l}}\leq-\frac{(n-k+1-y)}{y}.$

We show that we have $n>(j+1)y+k-1$. By the hypothesis of the Lemma

$n>j^{2}+2kj+3k-j-\frac{j^{2}}{k}=j(j+2k-1-\frac{j}{k})+3k=j(mk+2k-1-m)+3k=$
$j(mk+2k-2-m)+mk+3k>j(mk+2k-2-m)+(mk+2k-2-m)+k=$ $(j+1)(m+2)(k-1)+k$

From (1) we have that

$(j+1)(m+2)(k-1)+k\geq(j+1)y+k>y(j+1)+k-1,$

so we have that $n>(j+1)y+k-1$ and therefore from
$\sum\limits_{l=1,\ldots,k}u_{i_{l}}\leq-\frac{(n-k+1-y)}{y}<-j$, which
contradicts $\|Wu\|_{\infty}\leq j$.

∎

We introduce extra notations.

$\begin{split}T(k)=j^{2}+2kj+3k-j-\frac{j^{2}}{k},\text{ where
}j=(\lfloor\frac{\gamma}{2}\rfloor+1)(2k+\gamma)\text{ if }\gamma\text{ is
even and }j=2k\\\ \text{ if }\gamma\text{ is odd },\gamma\text{ is the
smallest positive integer number that is not a divisor of }k.\end{split}$

$\begin{split}B(n,k)=\\{(a,b,r,s):\frac{(bs-r)k}{s(a+b)}\text{ is not integer
},\text{ where }a,b,r,s\\\ \text{ are non-negative integers },b,\neq 0,0\leq
r<s,(s,r)=1,s\text{ is a divisor of }(n,k)\\}.\end{split}$

$\begin{split}N(n,k)=\min\\{\max\\{k(a+\frac{r}{s}),k(b-\frac{r}{s})\\}:(a,b,r,s)\in
B(n,k)\\}.\end{split}$ $\begin{split}M(n,k)=\\{(a,b,r,s)\in
B(n,k):\max\\{k(a+\frac{r}{s}),k(b-\frac{r}{s})\\}=N(n,k)\\}\end{split}$

######  Theorem 4.

If $n>T(k)$, then $m(1,J(n,k))\geq N(n,k)+1$.

###### Proof..

In view of Theorem 3 consider the vector $u$,
$\sum\limits_{i=1,\ldots,n}u_{i}=0$ such that $W^{T}u$ is a NZI
$\theta_{1}(J(n,k))$-eigenvector of $J(n,k)$ such that
$\|W^{T}u\|_{\infty}+1=m(1,J(n,k))$. By Lemma 3 we have that there are $k$
positions of $u$ with values $a+\frac{r}{s}$ and $k$ positions with values
$-b+\frac{r}{s}$ for some $b\neq 0,(r,s)=1,0\leq r<s,s\text{ is divisor of
}(n,k)$. By Lemma 2 we have that $\frac{(bs-r)k}{s(a+b)}$ is not integer.
Therefore, $(a,b,r,s)\in B(n,k)$. On the other hand, $\|W^{T}u\|_{\infty}$ is
not less than $\max\\{k(a+\frac{r}{s}),k(b-\frac{r}{s})\\}$, hence,
$\|W^{T}u\|_{\infty}\geq N(n,k)$. ∎

######  Corollary 1.

Let $(a,b,r,s)$ be in $M(n,k)$. If $n>T(k)$ and $\frac{(bs-r)n}{s(a+b)}$ is
integer, then $m(1,J(n,k))=N(n,k)+1$.

###### Proof..

Take the vector $u$ such that it has $\frac{(bs-r)n}{s(a+b)}$ positions with
value $(a+\frac{r}{s})$ and $\frac{(as+r)n}{s(a+b)}$ positions with value
$(b-\frac{r}{s})$. The norm of the vector $W^{T}u$ equals
$\max\\{k(a+\frac{r}{s}),k(-b+\frac{r}{s})\\}=N(n,k)$. In the other hand, by
Theorem 4 we have $m(1,J(n,k))\geq N(n,k)+1$, hence, $m(1,J(n,k))=N(n,k)+1$ ∎

######  Corollary 2.

Let $\gamma$ be the smallest positive integer that does not divide $k$. If
$n>T(k)$ and $(n,k)=1$ and $n$ is divisible by $\gamma$, then

1\. If $\gamma=2$ then $m(1,J(n,k))=k+1$.

2\. If $\gamma>2$ then $m(1,J(n,k))=(\lfloor\frac{\gamma}{2}\rfloor+1)k+1$.

###### Proof..

Let $u$ be the real-valued vector of the vertices of the graph $J(n,1)$ with
the sum of values is zero, such that $\|W^{T}u\|_{\infty}+1=m(1,J(n,k))$. By
Proposition 7 we have
$\|W^{T}u\|_{\infty}\leq(\lfloor\frac{\gamma}{2}\rfloor+1)k+1$ (if $\gamma=2$
then $\|W^{T}u\|_{\infty}\leq k+1$ by Proposition 6). Since $(n,k)=1$ the
fractional part of value in any position of $u$ equals $0$. Let $(a,b,0,1)\in
M(n,k)$. We have that $\frac{bk}{a+b}$ is not integer and $(a+b)$ is not
divisor of $k$. So, $a+b\geq\gamma$, and if $a+b=\gamma$, then $(a,b)=1$. On
the other hand, if $a+b=\gamma$, then
$\max\\{a,b\\}\geq(\lfloor\frac{\gamma}{2}\rfloor+1)$ (if $\gamma=2$ then
$\max\\{a,b\\}=1$). If $a+b>\gamma$ then $\max\\{a,b\\}$ also not less than
$\lfloor\frac{\gamma}{2}\rfloor+1$ ($1$ in the case $\gamma=2$). Therefore,
$N(n,k)\geq(\lfloor\frac{\gamma}{2}\rfloor+1)k$ ($k$ if $\gamma=2$) and,
hence, $m(1,J(n,k))=(\lfloor\frac{\gamma}{2}\rfloor+1)k+1$ ($k+1$ if
$\gamma=2$). ∎

######  Proposition 8.

If $n$ is even, $k$ is odd and $n>T(k)$, then $m(1,J(n,k))=k+1$.

###### Proof..

Let $u$ be the real-valued vector such that $W^{T}u$ is NZI eigenvector of
$J(n,k)$ with norm $\|W^{T}u\|_{\infty}+1=m(1,J(n,k))$. By Proposition 6 we
have $\|W^{T}u\|_{\infty}\leq k$. In the other hand, let $(a,b,r,s)\in
M(n,k)$. Then $a\geq 1$ or $b\geq 2$ (otherwise $a+b=1$, and $(a,b,r,s)$ does
not belong to $B(n,k)$). Therefore, $N(n,k)$ more than $ka$ and more than
$k(b-1)$ and, hence, $N(n,k)\geq k$. By Corollary 1 we have $m(1,J(n,k))\geq
N(n,k)+1=k+1$ and, hence, $m(1,J(n,k))=k+1$. ∎

######  Theorem 5.

If $n>T(3)=63$, then we have that

$m(1,J(n,3))=\begin{cases}4,{}n\text{ is even}\\\ 6,{}n\text{ is odd and
}n=0,6\mbox{ mod }9\\\ 7,{}\text{otherwise}.\end{cases}$

###### Proof..

Let $u$ be the real-valued vector such that $W^{T}u$ is NZI eigenvector of
$J(n,k)$ with norm $\|W^{T}u\|_{\infty}+1=m(1,J(n,k))$.

The case of even $n$ is a special case of Proposition 8.

In what follows $n$ is odd. By Proposition 6 we have $\|W^{T}u\|_{\infty}\leq
6$.

1\. Suppose the elements of $u$ are integers. By Lemma 3 there are at least
$3$ elements of $u$ equal to $a$ and at least $3$ elements equal to $-b$. If
$a\geq 2$ or $b\geq 2$ then $\|W^{T}u\|_{\infty}\geq 6$. Otherwise $a=1$ and
$b=1$. Since $n$ is odd and $\sum\limits_{i=1}^{n}u_{i}=0$, there is an
element of $u$ with even value $c$. This value cannot be $0,2,-2$, otherwise
we have three elements in $u$ with zero sum. Hence, $c\geq 4$ or $c\leq-4$. In
both cases, $\|W^{T}u\|_{\infty}\geq 6$.

2\. Suppose the elements of $u$ have nonzero fractional parts. By Lemma 1 this
fractional part is $\frac{1}{3}$ or $\frac{2}{3}$ and we necessarily have that
$n$ is divisible by $3$. Without loss of generality, we can assume that this
fractional part equals $\frac{2}{3}$ (otherwise we take the vector $-u$). By
Lemma 3 the vector $u$ has $3$ elements with some positive value
$a+\frac{2}{3}$ and $3$ elements with some negative value $-b+\frac{2}{3}$. If
$a=0$, then $b$ cannot be $1$ or $2$, otherwise there are three elements of
$u$ with the sum equals $0$. If $b\geq 3$, then $\|W^{T}u\|_{\infty}\geq 7$.
If $a\geq 2$, then $\|W^{T}u\|_{\infty}\geq 8$. So, $a=1$, hence,
$\|W^{T}u\|_{\infty}\geq 5$. Also we have $b=1$ or $b=2$, otherwise
$\|W^{T}u\|_{\infty}\geq 7$.

2a. Let $n$ be $3\mod 9$. We also recall that $n$ is $n$ odd and there are at
least $3$ elements in $u$ equal $\frac{5}{3}$ and at least $3$ elements equal
$-b+\frac{2}{3}$, where $b$ is $1$ or $2$. We show that
$\|W^{T}u\|_{\infty}\geq 6$.

Consider case $b=1$. Since $\sum_{i=1}^{n}u_{i}=0$ and $n$ is odd, there is an
element $\frac{c}{3}$ of $u$ for some even $c$. If $c\geq 8$ or $c\leq-16$
then $\|W^{T}u\|_{\infty}\geq 6$. If $c=2,-4,-10$ then there are three
elements in $u$ having zero sum.

Consider case $b=2$. If all elements of $u$ are $\frac{5}{3}$ or
$-\frac{4}{3}$ then $n$ is divisible by $9$, which is not the case. So there
is at least one element of $u$ that differs from $\frac{5}{3}$ or
$-\frac{4}{3}$. If there is element that is not less than $\frac{8}{3}$ or
element that is not more than $-\frac{10}{3}$ or two elements that equals
$-\frac{7}{3}$ then $\|W^{T}u\|_{\infty}\geq 6$. If in vector $u$ there is an
element $-\frac{1}{3}$ or two elements equals $\frac{2}{3}$ or two elements
with values $\frac{2}{3}$ and $-\frac{7}{3}$ then there are three elements in
$u$ with zero sum. It remains to consider case when one element of $u$ equals
$\frac{c}{3}$, where $c$ is $2$ or $-7$, any other element is $\frac{5}{3}$ or
$-\frac{4}{3}$. Denote by $x$ the number of elements $\frac{5}{3}$ and by $y$
the number of elements $-\frac{4}{3}$ in $u$. Then the sum of all elements
equals $\frac{5x-4y+c}{3}$, where $x+y=n-1$. Since
$\sum\limits_{i=1}^{n}u_{i}=0$ we have $x=\frac{4n-4-c}{9}$, i.e.
$x=\frac{4n-6}{9}$ or $x=\frac{4n+3}{9}$. In both case $n=6\mod 9$. Hence, in
all cases $\|W^{T}u\|_{\infty}\geq 6$ for $n=3\mod 9$.

2b. If $n=0\mbox{ mod }9$ take the vector

$u^{T}=(\frac{5}{3},\ldots,\frac{5}{3},-\frac{4}{3},\ldots,-\frac{4}{3}),$

of length $n$, where $\frac{5}{3}$ is repeated $\frac{4n}{9}$ times. Hence,
$\|W^{T}u\|_{\infty}=5$.

2c. If $n=6\mbox{ mod }9$ take vector

$u^{T}=(\frac{2}{3},\frac{5}{3},\ldots,\frac{5}{3},-\frac{4}{3},\ldots,-\frac{4}{3}),$

of length $n$, where $\frac{5}{3}$ is repeated $\frac{4n-6}{9}$ times,
$-\frac{4}{3}$ is repeated $\frac{5n-3}{9}$ times and $u_{1}=\frac{2}{3}$.
Hence, $\|W^{T}u\|_{\infty}=5$.

∎

###  4.2. Minimum of $L_{\infty}$ norm of nowhere-zero integer eigenvectors
with the first eigenvalue for block graphs of STSs

######  Theorem 6.

Let $S$ be a Steiner triple system of order $n$, $n>7$. If $n=1\mbox{ mod }4$
then $m(1,\Gamma_{S})\leq 4$ and if $n=3\mbox{ mod }4$ then
$m(1,\Gamma_{S})\leq 5$.

###### Proof..

Let $n$ be such that $n=1\mbox{ mod }4$. Suppose $S$ is a STS with all triples
containing point $1$ being $\\{1,2,3\\},\ldots,\\{1,n-1,n\\}$. We set vector
$u$ as follows: $u_{1}=0$, $u_{i}=1$ for $2\leq i\leq\frac{n+1}{2}$ and
$u_{i}=-1$ for $\frac{n+3}{2}\leq i\leq n$. The vector $W_{S}^{T}u$ is a
$\theta_{1}(J(n,3))$-eigenvector of $\Gamma_{S}$ by Theorem 3. The elements of
$W_{S}^{T}u$ are $u_{i}+u_{j}+u_{k}$ if $\\{i,j,k\\}$ is a triple of $S$. If
$\\{i,j,k\\}$ contains $1$, then by the choice of u, we see that
$(W_{S}^{T})_{i,j,k}$ is either $2$ or $-2$. Otherwise, $u_{i}+u_{j}+u_{k}$ is
the sum of three numbers with absolute value $1$, therefore
$\|W_{S}^{T}u\|_{\infty}=3$.

Let $n$ be such that $n=3\mbox{ mod }4$. Without restriction of generality,
$\\{1,2,3\\}$ is a triple in $S$. Set the vector $u$ as follows: $u_{1}=-1$,
$u_{2}=2$, $u_{3}=-3$. We will arrange the remaining $\frac{n-5}{2}$ values
$-1$ and $\frac{n-1}{2}$ values $1$ in the remaining $n$ positions of $u$
according to the structure of STS $S$.

We consider an auxiliary graph on the vertices, which are points
$\\{4,\ldots,n\\}$. The edges are pairs obtained from the all triples of $S$
containing $2$ or $3$, excluding $\\{1,2,3\\}$, by removing the points $2$ and
$3$. The edges are labeled ”2” or ”3” which is the point that completes the
edge, i.e. pair of points, to a triple of $S$. From the definition of Steiner
triple system, we see that the graph is the union of even length cycles that
partition $\\{4,\ldots,n\\}$, where labels, i.e. 2 and 3, for any two incident
edges are different.

For a vector $u$ we set its remaining elements (with indices of the vertices
of the auxiliary graph) to $1$ and $-1$ as follows. We distinguish one cycle
$i_{1},\ldots,i_{2l}$. Choose a path $i_{1}$, $i_{2}$, $i_{3}$ in the cycle
and set values $u_{i_{1}}=u_{i_{2}}=u_{i_{3}}=1$. The remaining values of $u$
in this cycle are alternating $-1$ and $1$: $u_{i_{4}}=-1$, $u_{i_{5}}=1$,
$u_{i_{6}}=-1$,…, $u_{i_{2l}}=-1$. For any other cycle $j_{1},\ldots,j_{2m}$
we set the values of $u$ in the alternating way:
$u_{j_{2s+1}}=-u_{j_{2(s+1)}}=1$, for $s=0,\ldots,m-1$. By the choice of
values of $u$ on the points $\\{4,\ldots,n\\}$, for any two adjacent vertices
$a$, $b$ in the auxiliary graph we have that $u_{a}+u_{b}=0$ or $2$.

Since $\sum\limits_{i=1,\ldots,n}u_{i}=0$, $u$ is (-1)-eigenvector of $K_{n}$.
Now consider the vector $W^{T}u$, which is a $\theta_{1}(J(n,3))$-eigenvector
of $J(n,3)$ by Theorem 3. For a triple $\\{i,j,k\\}$ of $S$ such that
$\\{i,j,k\\}\cap\\{2,3\\}=\emptyset$, we see that $u_{i}+u_{j}+u_{k}$ is a sum
of elements with absolute values $1$ (note that $u_{1}=1$ and
$|u_{i}|=1,i=4\ldots,n$). So $u_{i}+u_{j}+u_{k}$ is nonzero with absolute
value less or equal to $3$. Let $\\{i,j,k\\}$ be a triple of $S$, such that
$k=2$ or $3$ and $i,j\geq 4$. Since $u_{2}=2$, $u_{3}=-3$ and $u_{i}+u_{j}$ is
either $0$ or $2$, the sum $u_{k}+u_{i}+u_{j}$ is nonzero with absolute value
less or equal to $4$. For the last remaining case of triple $\\{1,2,3\\}$ in
$S$ we have $u_{1}+u_{2}+u_{3}=-2$. We see that $\|W_{S}^{T}u\|_{\infty}=4$.

∎

##  5\. Nowhere zero flows for families of classic Steiner triple system

Throughout this section, we use terms of flows in Steiner triple systems in
the sense of work [1] rather than terms of eigevectors.

###  5.1. Flows for some classic STSs

######  Lemma 4.

[3, Lemma 1.4] Let $S$ be a resolvable STS of order $n$. If $n=1\mbox{ mod
}4$, $S$ has a $2$-flow, otherwise it has a $3$-flow.

###### Proof..

If $n=1\mbox{ mod }4$, we split the $\frac{n-1}{2}$ parallel classes into two
equal sized subsets and set $v_{T}=1$ if $T$ belongs to any parallel class
from the first subset and $-1$ otherwise. It is easy to see that $v$ is
$2$-flow for $S$.

If $n=3\mbox{ mod }4$, we part the $\frac{n-1}{2}$ parallel classes into three
subsets sets of sizes $\frac{n-7}{4}$ , $\frac{n-3}{4}$ and $2$ and set the
elements of vector $v$ to be $2$, $-2$ and $1$ if the triple belongs to
parallel classes in these sets respectively. It is easy to see that $v$ is
$3$-flow for $S$.

∎

######  Proposition 9.

1\. Let $S$ be the Steiner triple system formed by the supports of weight
three codewords of the Hamming code of length $2^{r}-1$, $r\geq 4$. Then we
have that $m(2,\Gamma_{S})=3$.

2\. Let $S$ be the original Bose Steiner triple system of order $3p$
constructed from the latin square of $Z_{p}$, where $p$ is an odd prime. Then
$S$ had $3$ or $2$-flow.

###### Proof..

1\. If $r$ is even, then the Hamming STS of order $2^{r}-1$ is known to be
resolvable, i.e. its blocks are parted into $\frac{2^{r}-2}{2}$ parallel
classes [8]. In this case, following Lemma 4, we see that $3$-flow exists.

When $r$ is odd, then it is easy to see that $2^{r}$ is $2$ modulo 6 by
induction on $r$. Any Hamming STS is cyclic, i.e. it has an automorphism of
order being equal to the order of $S$. By [4, Theorem 3.6] if the order of a
STS $S$ is $1$ modulo $6$ and $S$ is cyclic, then a $3$-flow for $S$ exists.

Suppose a $2$-flow $v$ for Hamming STS $S$ exists, so $W_{S}v=0$ and the
elements of the $v$ are $+1$ and $-1$. This contradicts the fact that any row
of $W_{S}$ has exactly $\frac{n-1}{2}=\frac{2^{r}-1-1}{2}$ of ones, which is
odd.

2\. Steiner triple systems constructed by Bose method of order $9p$ were
recently shown to be resolvable by Colbourn and Lusi [11]. The result follows
from Lemma 4. ∎

###  5.2. Flows for Assmuss-Mattson construction

Let us consider the Assmus-Mattson construction [6]. Given a Steiner triple
system $S$ of order $n$ with pointset $\\{1,\ldots,n\\}$ we denote by
$\bar{i}$ the number $i+n$. For a function $\tau:S\rightarrow\\{0,1\\}$, we
define the Assmuss-Mattson Steiner triple system of order $2n+1$ with point
set $\\{1,2,\dots,n,\bar{1},\bar{2},\dots,\bar{n},2n+1\\}$:

${\bar{S}}=\bigcup_{\\{i,j,k\\}\in
S,\,\tau(\\{i,j,k\\})=0}{P(\\{i,j,k\\})}\cup$ $\bigcup_{\\{i,j,k\\}\in
S,\tau(\\{i,j,k\\})=1}{P^{\prime}(\\{i,j,k\\})}\cup$
$\bigcup_{i=1,\dots,n}{\\{i,\bar{i},2n+1\\}},$

where

$P(\\{i,j,k\\})=\\{\\{i,j,k\\},\\{i,\bar{j},\bar{k}\\},\\{\bar{i},j,\bar{k}\\},\\{\bar{i},\bar{j},k\\}\\},$

if $\tau(\\{i,j,k\\})=0$ and

$P(\\{i,j,k\\})=\\{\\{\bar{i},j,k\\},\\{\bar{i},\bar{j},\bar{k}\\},\\{i,j,\bar{k}\\},\\{i,\bar{j},k\\}\\}.$

$\tau(\\{i,j,k\\})=1$ otherwise.

Our goal is to construct a zero-sum $5$-flow in $S^{\prime}=S^{2n+1,\tau}$,
i.e. to find such an NZI vector $v$ that $\sum\limits_{T\in S^{\prime},i\in
T}{v_{T}}=0$ for any
$i\in\\{1,2,\dots,n,\bar{1},\bar{2},\dots,\bar{n},2n+1\\}$.

For our following arguments we need several auxiliary statements.

Let $a_{1},a_{2},a_{3}$ be pairwise distinct elements from $\\{1,\dots,n\\}$.
We define a real-valued vector $g$ indexed by $P(\\{a_{1},a_{2},a_{3}\\})$
depending on $\tau(\\{a_{1},a_{2},a_{3}\\})$. If
$\tau(\\{a_{1},a_{2},a_{3}\\})=0$, define the elements of $g$ (indexed by
triples in $P$) in the following way:

$g_{\\{a_{1},a_{2},a_{3}\\}}=g_{\\{a_{1},\bar{a}_{2},\bar{a}_{3}\\}}=1,g_{\\{\bar{a}_{1},\bar{a}_{2},a_{3}\\}}=g_{\\{\bar{a}_{1},a_{2},\bar{a}_{3}\\}}=-1.$

If $\tau(\\{a_{1},a_{2},a_{3}\\})=1$ define

$g_{\\{\bar{a}_{1},a_{2},a_{3}\\}}=g_{\\{\bar{a}_{1},\bar{a}_{2},\bar{a}_{3}\\}}=-1,g_{\\{a_{1},a_{2},\bar{a}_{3}\\}}=g_{\\{a_{1},\bar{a}_{2},a_{3}\\}}=1.$

Consider the properties of the introduced vector $g$.

######  Proposition 10.

The following holds for vector $g$:

(4) $\sum_{T^{\prime}\in P(\\{a_{1},a_{2},a_{3}\\}),a_{1}\in
T^{\prime}}{g_{T^{\prime}}}=2,$

(5) $\sum_{T^{\prime}\in P(\\{a_{1},a_{2},a_{3}\\}),\bar{a}_{1}\in
T^{\prime}}{g_{T^{\prime}}}=-2,$

(6) $\sum_{T^{\prime}\in P(\\{a_{1},a_{2},a_{3}\\}),s\in
T^{\prime}}{g_{T^{\prime}}}=0\mbox{ for
}s\in\\{a_{2},a_{3},\bar{a}_{2},\bar{a}_{3}\\}.$

###### Proof..

The proof is obtained by direct calculations. ∎

Clearly, by direct permutation of points $a_{1}$, $a_{2}$ and $a_{3}$ one may
apply Proposition 10 for $a_{2}$ or $a_{3}$.

######  Lemma 5.

Let $S$ be $STS(n)$, where $n\geq 49$. Then there is a function
$h:S\rightarrow\\{1,\ldots,n\\}$ such that

  1. (1)

for any $\\{i,j,k\\}\in S$, $h(\\{i,j,k\\})\in\\{i,j,k\\}$,

  2. (2)

for any $i\in\\{1,\ldots,n\\}$, $|\\{T\in S:h(T)=i\\}|\geq 4$.

###### Proof..

Consider the set $A$ of all functions satisfying the first condition from
Lemma. Each function maps any triple $T\in S$ to a point in $T$. Therefore,
$|A|=3^{\frac{n(n-1)}{6}}$. The next step is counting the number of functions
from $A$ not satisfying the second condition of Lemma for a fixed point
$i_{0}$. Clearly, for any such function $f$, $|\\{T\in S:h(T)=i_{0}\\}|$
equals $0$, $1$, $2$ or $3$. We conclude that the number of such functions is
equal to

$R=2^{\frac{n-1}{2}}3^{\frac{n(n-1)}{6}-\frac{n-1}{2}}+{\frac{n-1}{2}\choose
1}2^{\frac{n-1}{2}-1}3^{\frac{n(n-1)}{6}-\frac{n-1}{2}}+$
${\frac{n-1}{2}\choose
2}2^{\frac{n-1}{2}-2}3^{\frac{n(n-1)}{6}-\frac{n-1}{2}}+{\frac{n-1}{2}\choose
3}2^{\frac{n-1}{2}-3}3^{\frac{n(n-1)}{6}-\frac{n-1}{2}}.$

Consequently, the number of functions in $A$ not satisfying the second
condition from Lemma (in at least one point) is not greater than $nR$. As a
result, we have that the number of functions from $A$ satisfying both
conditions is at least $3^{\frac{n(n-1)}{6}}-nR$ which is equal to

$2^{\frac{n-1}{2}}3^{\frac{n(n-1)}{6}-\frac{n-1}{2}}\bigl{(}(\frac{3}{2})^{\frac{n-1}{2}}-\frac{1}{384}n^{4}-\frac{1}{128}n^{3}-\frac{71}{384}n^{2}-\frac{103}{128}n\bigr{)}.$

This expression is strictly positive for $n\geq 49$ and the proof is finished.
∎

######  Theorem 7.

Let $\overline{S}$ be a Assmuss-Mattson Steiner triple system of order $N$,
$N\geq 99$. Then $\overline{S}$ admits a zero-sum $5$-flow.

###### Proof..

Let $\overline{S}$ of order $N=2n+1$ be obtained from STS $S$ of order $n$,
$n\geq 49$ by Assmuss-Mattson construction.

We start from the all-zero vector $v$, indexed by the triples of ${\bar{S}}$
and update it with the course of the proof. At the end of the proof, $v$ will
be $5$-flow for STS ${\bar{S}}$. Consider the set $B=\\{T\in S:1\in T\\}$ and
$T_{0}\in S\setminus B$. Without loss of generality we have that
$B=\\{\\{1,2,3\\},\\{1,4,5\\},\\{1,6,7\\},\dots,\\{1,n-1,n\\}\\}$ and
$T_{0}=\\{2,4,6\\}$. The triples of ${\bar{S}}$ are parted into the following
three sets of triples: $P(T_{0})\cup\bigcup\limits_{T^{\prime}\in
B}P(T^{\prime})$, $\bigcup\limits_{T^{\prime}\in S\setminus(T_{0}\cup
B)}P(T^{\prime})$ and $\bigcup\limits_{i=1,\ldots,n}\\{i,\bar{i},2n+1\\},$ .
We consequently define the vector $v$ on these sets.

Let us consider an auxiliary vector $w$ indexed by triples from
$B\cup\\{T_{0}\\}$. For $i$, $1\leq i\leq\frac{n-1}{2}$, and even
$\frac{n-1}{2}$, we define $w_{\\{2,4,6\\}}=-2$ and

$w_{\\{1,2i,2i+1\\}}=\begin{cases}1,&1\leq i\leq\frac{n-1}{4}+1\\\
-1,&\text{otherwise.}\end{cases}$

And for $i$, $1\leq i\leq\frac{n-1}{2}$, and odd $\frac{n-1}{2}$, we define
$w_{\\{2,4,6\\}}=-2$ and

$w_{\\{1,2i,2i+1\\}}=\begin{cases}1,&1\leq i\leq\frac{n-3}{4}\\\
-1,&\frac{n+1}{4}\leq i\leq\frac{n-3}{2}\\\ 2,&i=\frac{n-1}{2}.\end{cases}$

The choice of $w$ implies:

(7) $\sum_{T\in B_{0}\cup T}w_{T}=0.$

Let us now define the elements of $v$ on the triples arising from
$B\cup\\{T_{0}\\}$ in Assmuss-Mattson recursive approach. For $T\in
B\cup\\{T_{0}\\}$, put $v_{T^{\prime}}=w_{T}$ for all $T^{\prime}\in P(T)$.

Let us define $\alpha_{i}=\sum\limits_{T^{\prime}\in
P(T_{0})\cup\bigcup\limits_{T\in B}P(T)}{v_{T}}$ for
$i\in\\{1,\dots,n,\bar{1},\dots,\bar{n}\\}$. From the definition of $P(T)$ we
see that for any $i\in T$ the points $i$ or $\bar{i}$ are in exactly two
triples of $P(T)$. We see that

$\alpha_{i}=\alpha_{\bar{i}}=\sum\limits_{T^{\prime}\in
P(T_{0})\cup\bigcup\limits_{T\in B}P(T)}{v_{T}}$

for the vector $v$. Moreover, we see that the absolute values of the elements
of vector $w$ are 1 or 2, so we have that $|v_{T}|=1$ or $2$ for $v_{T}$ in
the sum above , so for all $i\in\\{1,\ldots,n\\}$ we have that

(8) $\alpha_{i}\in\\{\pm 2,\pm 4\\}.$

The equality (7) gives the following (note that so far, some values of $v$ are
still zeros):

(9) $\sum_{i\in\\{1,\ldots,n\\}}\alpha_{i}=0.$

By Lemma 5 there is a function $h$ defined on $S$ such that for any
$\\{i,j,k\\}\in S$, $h(\\{i,j,k\\})\in\\{i,j,k\\}$, and for any $i\in[n]$,
$|\\{T\in S:h(T)=i\\}|\geq 4$. Take any point $j\in[n]\setminus\\{1\\}$.
Clearly, $B\cup T_{0}$ covers every point at most twice. Consequently,

$|M_{j}|\geq 2,$

where $M_{j}=\\{T\in S\setminus(B\cup T_{0}):h(T)=j\\}$. The next step is to
apply Proposition 10 in order to define $v$ on $P(T)$ and $P^{\prime}(T)$ for
$T\in M_{j}$. If the size of $M_{j}$ is even then we divide $M_{j}$ into two
sets $M^{1}_{j}$ and $M^{2}_{j}$ of equal cardinality. After that we define
values of $v$ as follows. For a triple $T$ in $M_{j}^{1}$, judging by the
value of $\tau$, we set the values $v_{T^{\prime}}$ to be +1 and -1 for all
triples in $T^{\prime}\in P(T)$ as the values of vector $g$ in Proposition 10
with $a_{1}=j$. For a triple $T$ in $M_{j}^{2}$ we set the values
$v_{T^{\prime}}$ to be +1 and -1 for all triples in $T^{\prime}\in P(T)$ as
the values of vector $-g$ in Proposition 10 with $a_{1}=j$.

Due to definition of $v_{T^{\prime}}$ from $g(T^{\prime})$ we have:

$\sum_{T^{\prime}\in P(T):j\in T^{\prime},T\in
M_{j}}v_{T^{\prime}}=\sum_{T^{\prime}\in P(T):j\in T^{\prime},T\in
M_{j}^{1}}g_{T^{\prime}}-\sum_{T^{\prime}\in P(T):j\in T,T\in
M_{j}^{2}}g_{T^{\prime}}=$ $\\\ \sum_{T\in M_{j}^{1}}\sum_{T^{\prime}\in
P(T):j\in T^{\prime}}g(T^{\prime})-\sum_{T\in M_{j}^{2},}\sum_{T^{\prime}\in
P(T):j\in T^{\prime}}g(T^{\prime});$

Taking into account (4) and because $|M_{j}^{1}|=|M^{2}_{j}|$, we see that

$\sum_{T\in M_{j}^{1}}\sum_{T^{\prime}\in P(T):j\in
T^{\prime}}g(T^{\prime})-\sum_{T\in M_{j}^{2},}\sum_{T^{\prime}\in P(T):j\in
T^{\prime}}g(T^{\prime})=\sum_{T\in M_{j}^{1}}2-\sum_{T\in M_{j}^{2}}2=0.$

The same holds for the point $\bar{j}$ as we use (5) to obtain the following:

$\sum_{T^{\prime}\in P(T):\bar{j}\in T^{\prime},T\in M_{j}}v_{T^{\prime}}=\\\
\sum_{T\in M_{j}^{1}}\sum_{T^{\prime}\in P(T):\bar{j}\in
T^{\prime}}g(T^{\prime})-\sum_{T\in M_{j}^{2},}\sum_{T^{\prime}\in
P(T):\bar{j}\in T^{\prime}}g(T^{\prime})=$ $\sum_{T\in M_{j}^{1}}-2+\sum_{T\in
M_{j}^{2}}2=0.$

Thus, we have:

(10) $\sum_{T^{\prime}:T^{\prime}\in P(T),T\in M_{j},j\in
T^{\prime}}v_{T^{\prime}}=\sum_{T^{\prime}:T^{\prime}\in P(T),T\in
M_{j},\bar{j}\in T^{\prime}}v_{T^{\prime}}=0.$

Moreover, according to (6) we see that for the ”projection” of any point
different from $j$ is zero. For any $s\in T\cup\\{\bar{i}:i\in
T\\}\setminus\\{j,\bar{j}\\}$ we have that:

(11) $\sum_{T^{\prime}:T^{\prime}\in P(T),T\in M_{j},\bar{s}\in
T^{\prime}}v_{T^{\prime}}=\sum_{T^{\prime}:T^{\prime}\in P(T),T\in
M_{j},\bar{s}\in T^{\prime}}g_{T^{\prime}}=0.$

In the case of odd size of the set $M_{j}$, we divide $M_{j}$ into three non-
intersecting subsets $M_{j}^{1}$, $M_{j}^{2}$ and $M_{j}^{3}$ respectively of
sizes $\frac{|M_{j}|+1}{2}$, $\frac{|M_{j}|-3}{2}$ and $1$. We repeat the
procedure (as for the case when $M_{j}$ was of even size) for the first two
sets with vectors $g$ and $-g$ correspondingly. For the last one-element set
we do the same but with the vector $-2g$. Similarly to the case of even size
of $M_{j}$, we have equalities (10) and (11). We repeat the arguments for sets
$M_{t}$ for all remaining $t\in\\{1,\ldots,n\\}\setminus\\{1,j\\}$.

So far we have defined the elements of v indexed by all triples in
${\bar{S}}\setminus\\{\\{i,\bar{i},2n+1\\},i=1,\ldots,n\\}$ and they are
nonzeros. Moreover, from (10), (11) and (8) for any $i\in\\{1,\ldots,n\\}$

(12)
$\sum_{T^{\prime}\in{\bar{S}}\setminus\\{\\{i,\bar{i},2n+1\\},i=1,\ldots,n\\},i\in{\bar{S}}}v_{T^{\prime}}=\sum_{T^{\prime}\in{\bar{S}}\setminus\\{\\{i,\bar{i},2n+1\\},i=1,\ldots,n\\},\bar{i}\in{\bar{S}}}v_{T^{\prime}}=\alpha_{i}\in\\{\pm
2,\pm 4\\}.$

The last step that finishes the proof is to define $v$ on the set of triples

$\bigcup\limits_{i=1,2,\dots,n}{\\{i,\bar{i},2n+1\\}}$

in the following way:

(13) $v_{\\{i,\bar{i},2n+1\\}}=-\alpha_{i}\text{ for }i\in\\{1,\ldots,n\\}.$

From (9) we see that

(14)
$\sum\limits_{\\{i,\bar{i},2n+1\\},l=1,\ldots,n}v_{\\{i,\bar{i},2n+1\\}}=\sum\limits_{i=1,\ldots,n}\alpha_{i}=0.$

Summing up the above we have the following.

1\. All values of $v$ are nonzeros with absolute values not greater than $4$.

2\. From (12) and (13), for any $i\in\\{1,\ldots,n\\}$
$\sum\limits_{T^{\prime}\in{\bar{S}},i\in
T^{\prime}}v_{T^{\prime}}=\sum\limits_{T^{\prime}\in{\bar{S}},{\bar{i}}\in
T^{\prime}}v_{T^{\prime}}=0$.

3\. From (14), $\sum\limits_{T^{\prime}\in{\bar{S}},2n+1\in
T^{\prime}}v_{T^{\prime}}=0$.

In other words, $v$ is a $5$-flow for ${\bar{S}}$. ∎

##  6\. Completely regular codes in the block graphs of STSs

Let $S$ be a Steiner triple system in the classical sense of order $n$. The
following are examples of completely regular codes in the block graph of $S$.

Covering radius $\rho=1$ and eigenvalue $\theta_{1}(\Gamma)$:

Construction 1. $\\{B\in S:i\in B\\}$, where $i$ is any fixed point
$\\{1,\ldots,n\\}$.

Construction 2. Any Steiner subsystem of $S$ having order $\frac{n-1}{2}$.

Construction 3. $\\{B\in S:i\in B\\}\cup S^{\prime}$, where $S^{\prime}$ is
any Steiner subsystem of $S$ having order $\frac{n-1}{2}$, such that $i$ is a
point of $S$ but not a point of $S^{\prime}$.

Covering radius $\rho=1$ and eigenvalue $\theta_{2}(\Gamma)$:

Construction 4 (see Proposition 3). Any $1$-subdesign of $S$.

Covering radius $\rho=2$:

Construction 5. Any Steiner subsystem of $S$ of order less then
$\frac{n-1}{2}$.

Remark 2. Actually, Construction 5 lists all completely regular codes in the
block graphs with $\rho=2$. This can be shown, for example, using the
technique from [22, Theorem 4 and Lemma 2] that utilizes the fact that all
such codes naturally arise from subsets of the vertices of the clique graph of
the block graph. This is beyond the scope of the current study, so we skip the
details here.

The block graph of projective (Hamming) Steiner triple system of order
$2^{r}-1$ is isomorphic to the Grassmann graph $J_{2}(r,2)$. The completely
regular codes with $\rho=1$ and the first eigenvalue in these graphs are known
as Cameron-Liebler line classes. These objects were characterized in [16] as
follows: these are Constructions 1-3 or their opposite codes. Judging by this
fact for the most ”symmetric” Steiner triple system, we propose the following:

Problem 2. Find any other completely regular codes with $\rho=1$ and the first
eigenvalue in the block graphs of Steiner triple systems of order $n,n\geq 13$
or prove that no such codes exist.

All Steiner triple systems of orders $13$ and $15$ are enumerated and there
are $2$ and $80$ isomorphism classes of such Steiner triple systems
respectively [12].

######  Theorem 8.

Let $S$ be a Steiner triple system of order $13$ or $15$. Then all completely
regular codes with $\rho=1$ in $\Gamma_{S}$ and eigenvalue
$\theta_{1}(\Gamma_{S})$ are codes from Constructions 1-3.

###### Proof..

For a given Steiner triple system of order $n$, the number of codes from
Construction 2 equals the number of Steiner subsystems of order
$\frac{n-1}{2}$. Using a well-known result of [15] the number of such
subsystems equals the $2^{n-r}-1$, where $r$ is the binary rank of Steiner
triple system. We recall that the rank is the dimension of the subspace,
spanned by the characteristic vectors of triples in the point set. We see that
there are exactly $(2^{n-r}-1)$ and $(2^{n-r}-1)\frac{n+1}{2}$ codes given by
Constructions 2 and 3 respectively.

We conclude that for a given Steiner triple system, the number of codes from
Constructions 1, 2, 3 are as follows:

(15) $n+(2^{n-r}-1)(\frac{n+3}{2}).$

We use integer based computer search for completely regular codes with
$\rho=1$, described in [21]. Given the intersection array, a computer linear
programming solver outputs the number of completely regular codes having this
intersection array. For all considered Steiner triple systems of orders $n=13$
and $15$ of any given rank $r$, the solver output the number of completely
regular codes with eigenvalue $\theta_{1}(\Gamma_{S})$ being equal to (15),
thus we have the required. ∎

## References

  * [1] S. Akbari, G.B. Khosrovshahi, A. Mofidi, Zero-sum flows in Designs, Jour. of Comb. Designs,  19:5 (2011), 355–364.
  * [2] S. Akbari, E. Ghorbani, A. Mahmoodi, Nowhere-zero eigenvectors of graphs, Linear and Multilinear Algebra, 61:2 (2013), 273–279.
  * [3] S. Akbari, A.C. Burgess, P. Danziger, E. Mendelsohn, Zero-sum flows for triple systems, Disc. Math., 340:3 (2017), 416–425.
  * [4] S. Akbari, H.R. Maimani, L.P. Majd, I.M. Wanless, Zero-sum flows for Steiner triple systems, Disc. Math., 343:11 (2020), 112074.
  * [5] I.S.o. Aliev, E. Seiden, Steiner Triple Systems and Strongly Regular Graphs, Journal of combinatorial theory, 6:1 (1969), 33–39.
  * [6] E.F. Assmuss, Jr., H.F. Mattson, On the Number of Inequivalent Steiner Triple Systems, J. of Combin. Th.,  1:3 (1966), 301–305.
  * [7] S.V. Avgustinovich, I.Yu. Mogilnykh, Induced perfect colorings, Siberian Electronic Mathematical Reports,  8:1 (2011), 310–316.
  * [8] R. Baker, Partitioning the planes of AG2m(2) into 2-designs, Disc. Math.,  15:3 (1976), 205–211.
  * [9] M. Braun, T. Etzion, P.R.J. Ostergard, A. Vardy, A. Wassermann, Existence of q-analogs of Steiner systems, Forum of Mathematics Pi,  4 (2016), E7.
  * [10] P.J. Cameron, R.A. Liebler, Tactical decompositions and orbits of projective groups, Linear Algebra Appl., 46 (1982), 91–102.
  * [11] C. Colbourn, D. Lusi, Constructing resolutions for an infinite family of Bose triple system, Abstracts of Southeastern International Conference on Combinatorics, Graph Theory and Computing, March 8-12, (2021), http://www.math.fau.edu/combinatorics2021/lusid020921.pdf.
  * [12] F.N. Cole, L.D. Cummings, and H.S. White, Complete enumeration of triple systems in 15 elements, Proc. Nat. Acad. Sci. U.S.A.,  3  (1917), 197–199.
  * [13] J. D’haeseleer, F. Ihringer, J. Mannaert, L. Storme, Cameron-Liebler k-sets in AG(n,q), Electron. J. Combin.,  28:4 (2021), P4.11.
  * [14] P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips Res. Rep. Suppl.,  10 (1973), 1–97.
  * [15] J. Doyen, X. Hubaut, M. Vandensavel, Ranks of incidence matrices of Steiner triple systems, Mathematische Zeitschrift,  163 (1978), 251–259.
  * [16] K. Drudge, Extremal sets in projective and polar spaces, Ph.D. Thesis, University of Western Ontario (1998).
  * [17] Y. Filmus, F. Ihringer, Boolean degree 1 functions on some classic association schemes, Journal of Combinatorial Theory A,  162 (2019), 241–270.
  * [18] S. Goryainov, D. Panasenko, On eigenfunctions of block graphs of Steiner systems based on AG(n,3), The abstracts of 7th Algebraic Graph Theory and its Applications (2022), 17.
  * [19] P. Keevash, A. Sah, M. Sawhney, The existence of subspace designs, (2022), arXiv:2212.00870.
  * [20] C. Maldonado, D. Penazzi, Lattices and Norton algebras of Johnson, Grassmann and Hamming graphs, arxiv.org:1204.1947 (2012).
  * [21] I.Yu. Mogilnykh, Completely regular codes in Johnson and Grassmann graphs with small covering radii, Electron. J. Comb.,  29:2, 22 (2022), P2.57.
  * [22] I.Yu. Mogilnykh, K.V. Vorob’ev, On completely regular codes with minimum eigenvalue in geometric graphs, Disc. Math.,  346:7 (2023), 113357.
  * [23] G. Sarkis, S. Shahriari, Zero-sum flows of the linear lattice, Finite Fields and Their Applications,  31 (2015), 108–120.
  * [24] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math.,  6 (1954), 80–91.
  * [25] K.V. Vorob’ev, Embedding of eigenfunctions of the Johnson graph into eigenfunctions of the Hamming graph, Journal of Applied and Industrial Mathematics,  8 (2014), 136–142.


Since Duplicator plays with their winning strategy, we know that $b_{k+1}' = b_i' \cdot b_j'$.

It follows that that $a_l' = a_{k+1}' \cdot \mathtt{a}$, yet we have assumed $b_l' \neq b_{k+1}' \cdot \mathtt{a}$.
Consequently, Duplicator has lost which is a contradiction, since Duplicator plays with a known winning strategy.

Let $\vec a' = (a_1' , a_2', \dots, a_{k+3}', \mathtt{a}, \emptyword)$ where $a_i' \sqsubseteq \mathtt{a}^q$ for all $i \in [k+3]$ and $\vec b' = (b_1', b_2', \dots, b_{k+3}', \mathtt{a}, \emptyword)$ where $b_i' \sqsubseteq \mathtt{a}^p$ for all $i \in [k+3]$ be the resulting tuples of the look-up game $\mathcal{G}_l$.
Then, for any $r \leq k$, we have that $\mathtt{a}^q = a_r \cdot x$ if and only if $\mathtt{a}^p = b_r \cdot x$, where $x \in \{ \emptyword, \mathtt{a}, \mathtt{aa} \}$.

Let $\vec a' = (a_1' , a_2', \dots, a_{k+3}', \mathtt{a}, \emptyword)$ and $\vec b' = (b_1', b_2', \dots, b_{k+3}', \mathtt{a}, \emptyword)$ be the resulting tuples of the look-up game $\mathcal{G}_l$.
Without loss of generality, assume that $\mathtt{a}^q = a_r \cdot x$ and $\mathtt{a}^p \neq b_r \cdot x$ for some $r \leq k$ and $x \in \{ \emptyword, \mathtt{a}, \mathtt{aa} \}$.

In round $k+1$, assume that Spoiler chooses $\mathfrak{C}_q$ and $a_{k+1} \df x$.
Duplicator must respond with $\mathfrak{D}_p$ and $b_{k+1} \df x$ since $x$ is either a constant or the concatenation of two constants.
In round $k+1$, assume that Spoiler chooses $\mathfrak{C}_q$ and $a_{k+2} \df \mathtt{a}^q$.
It follows that $a_{k+2} = a_r \cdot a_{k+1}$ and therefore Duplicator must choose some $b_{k+2} = b_r \cdot b_{k+1}$.
We therefore know that $b_{k+2} \neq \mathtt{a}^p$.
In round $k+3$, let Spoiler choose $\mathfrak{B}_p$ and $b_{k+3} \df b_{k+2} \cdot \mathtt{a}$.
Since Spoiler cannot choose any factor of $\mathtt{a}^q$ of the form $a_{k+2} \cdot \mathtt{a}$, Spoiler has won.
This is a contradiction, as we have assumed that Duplicator plays with their winning strategy.

So far, we have that for any $r \leq k-3$ if $\mathtt{a}^q = a_r \cdot x$ then $\mathtt{a}^p = b_r \cdot x$, where $x \in \{ \emptyword, \mathtt{a}, \mathtt{aa} \}$.
However, the other direction immediately follows by simply considering the same proof with the roles switched.

Duplicator's strategy.
We now work towards a full strategy for Duplicator in the $k$-round game over $\mathfrak{A}_q$ and $\mathfrak{B}_p$.
For each round $r \in [k]$ of $\mathcal{G}_l$, if Duplicator responds in $\mathcal{G}_l$ with $\mathtt{a}^n$ for some $n \in \mathbb{N}_+$, then we know that Spoiler's choice in $\mathcal{G}$ is of the form $u_1 \cdot w^m \cdot u_2$, where $u_1, u_2 \sqsubset w$ , and $m \in \mathbb{N}_+$.
Duplicator then responds in $\mathcal{G}$ with $u_1 \cdot w^n \cdot u_2$.
From <ref>, we know that this response is uniquely defined.
See <ref> for an informal illustration of Duplicator's strategy.

vertex=[rectangle,fill=white!35,minimum size=12pt,inner sep=3pt,outer sep=1.5pt]
vertex2=[rectangle,fill=white!35,draw=gray,rounded corners=.1cm]
[vertex2] (7) at (-4,0) Spoiler's Choices;
[vertex2] (8) at (4.4,0) Duplicator's Responses;

[-latex] (7) to[bend left=30] (-3,1);
[-latex] (8) to[bend left=30] (3,-1);

[dotted] (0,1) ellipse (3cm and 0.6cm);
[dotted] (0,-1) ellipse (3cm and 0.6cm);

[vertex] (1) at (-1.6, 1) $u_1 \cdot w^n \cdot u_2$;
[vertex] (2) at (1.6, 1) $\mathtt{a}^n$;

[vertex] (3) at (1.6,-1) $\mathtt{a}^m$;
[vertex] (4) at (-1.6,-1) $u_1 \cdot w^m \cdot u_2$;

[-latex,dashed] (1) edge node [above]  (2);
[-latex] (2) edge node [right] $\mathcal{G}_l$ (3);
[-latex,dashed] (3) edge node [below]  (4);
[-latex] (1) edge node [left] $\mathcal{G}$ (4);

Duplicator's strategy when Spoiler chooses some $u_1 \cdot w^n \cdot u_2$ where $n \geq 1$.

In the case where Duplicator responds with $\emptyword$ in the look-up game $\mathcal{G}_l$, it follows that Spoiler's choice was some $u \in \Sigma^*$, where $\expo_w (u) = 0$.
Thus, Duplicator simply responds with the same $u \in \Sigma^*$.

Before showing that this strategy is a winning strategy for Duplicator, we first show that each choice for Duplicator (as defined above) is indeed a factor of the structure that Duplicator plays in a given round.
The case where Spoiler chooses some $u$ where $\expo_w(u) = 0$ is obvious, therefore we only look at the case where $\expo_w(u) \geq 1$.
Without loss of generality, assume that some round $r \leq k$, Spoiler chooses $\mathfrak{A}_q$ and $u_1 \cdot w^n \cdot u_2$ where $n \in \mathbb{N}_+$.
It therefore follows that Duplicator's response is of the form $u \df u_1 \cdot w^m \cdot u_2$ where

* $m \in \mathbb{N}_+$,

* $u_1$ is a strict suffix of $w$, and

* $u_2$ is a strict prefix of $w$.

Working towards a contradiction, assume that $u$ is not a factor of $w^p$.
By the definition of Duplicator's strategy (using the look-up game), we know that $m > p$ cannot hold.
Likewise, we know that $m \leq p-2$ cannot hold since then $u_1 \cdot w^m \cdot u_2$ is a factor of $w^p$.
Therefore, if $u$ is not a factor of $w^p$, then $p-2 < m \leq p$.
It follows from <ref> that $q-n = p-m$.
However, then $u_1 \cdot w^n \cdot u_2$ is not a factor of $w^q$ if $u_1 \cdot w^m \cdot u_2$ is not a factor of $w^p$, and therefore our assumption that $u$ is not a factor of $w^p$ cannot hold.

We now show that the given strategy for Duplicator is indeed a winning strategy.

Let $\vec a' = (a_1' , a_2', \dots, a_{k+5}')$ where $a_i' \sqsubseteq \mathtt{a}^q$ for all $i \in [k]$ and $\vec b' = (b_1', b_2', \dots, b_{k+5}')$ where $b_i' \sqsubseteq \mathtt{a}^p$ for all $i \in [k]$ be the resulting tuples of $\mathcal{G}_l$.
Since Duplicator plays $\mathcal{G}_l$ using their winning strategy, we have that $(\vec a', \vec b')$ forms a partial isomorphism.

Let $\vec a = (a_1, a_2, \dots, a_{k+|\Sigma|+1})$ where $a_i \in A$ for all $i \in [k]$, and let $\vec b = (b_1,b_2,\dots,b_{k+|\Sigma|+1})$ where $b_i \in B$ for all $i \in [k]$ be the resulting tuples from a $k$-round game over $\mathfrak{A}_q$ and $\mathfrak{B}_p$, where Duplicator plays the strategy given in this proof.

To show that $(\vec a, \vec b)$ is indeed a partial isomorphism, we shall show that the following conditions hold:

* For every $i \in [k+ |\Sigma|+1]$, and constant symbol $c \in \signature_\Sigma$, we have $a_i = c^{\mathfrak{A}_w}$ if and only if $b_i = c^{\mathfrak{B}_v}$,

* for every $i,j \in [k+ |\Sigma|+1]$, we have that $a_i = a_j$ if and only if $b_i = b_j$, and

* for every $i,j,k \in [k+ |\Sigma|+1]$, we have that $a_i = a_j \cdot a_k$ if and only if $b_i = b_j \cdot b_k$.

Due to the definition of Duplicator's strategy, we know that if Spoiler some constant $\mathtt{a} \in \Sigma$, then Duplicator responds with $\mathtt{a} \in \Sigma$.
If Spoiler chooses some $a_j$ such that $a_j = a_i$, then by the definition of Duplicator's strategy, Duplicator chooses $b_j$ such that $b_j = b_i$.
The case where Spoiler chooses $b_j$ follows analogously.

Therefore, it suffices to show that $a_i \cdot a_j = a_l$ if and only if $b_i \cdot b_j = b_l$ holds to prove that $(\vec a, \vec b)$ is a partial isomorphism.

Without loss of generality, assume that $a_i \cdot a_j = a_l$.
We now look at the following cases, and for each case show that $a_i \cdot a_j = a_l$ implies $b_i \cdot b_j = b_l$

* Case 1: $\expo_w(a_i) = 0$ and $\expo_w(a_j) = 0$,

* Case 2: $\expo_w(a_i) \geq 1$ and $\expo_w(a_j) \geq 1$,

* Case 3: $\expo_w(a_i) = 0$ and $\expo_w(a_j) \geq 1$, and

* Case 4: $\expo_w(a_i) \geq 1$ and $\expo_w(a_j) = 0$.

Case 1, $\expo_w(a_i) = 0$ and $\expo_w(a_j) = 0$:
First, note that from <ref>, we know that $\expo_w(a_l) \leq 1$ must hold.
Thus, we continue Case 1 under the assumption that $\expo_w(a_l) \leq 1$.
Furthermore, we know from the definition of Duplicator's strategy, that $a_i = b_i$ and $a_j = b_j$.

* If $\expo_w(a_l) = 0$, then it follows directly from Duplicator's strategy that $a_l = b_l$, and $a_i = b_i$ and $a_j = b_j$.
Thus, $b_l = b_i \cdot b_j$.

* If $\expo_w(a_l) = 1$, then we can write $a_l = w_1 \cdot w \cdot w_2$ where $w_1, w_2 \sqsubset w$.
From the look-up game, we know that $a_l' = \mathtt{a}$, and therefore $b_l' = \mathtt{a}$ must hold.
Thus, from Duplicator's strategy, we know $b_l = w_1 \cdot w \cdot w_2$.
Hence $b_l = b_i \cdot b_j$.

Case 2, $\expo_w(a_i) \geq 1$ and $\expo_w(a_j) \geq 1$:
For this case, we know that we can write:

* $a_i = u_i  \cdot w^{m_i} \cdot v_i$, where $u_i$ is a suffix of $w$ and $v_i$ is a prefix of $w$, and $m_i = \expo_w(a_i)$, and

* $a_j = u_j  \cdot w^{m_j} \cdot v_j$, where $u_j$ is a suffix of $w$ and $v_j$ is a prefix of $w$, and $m_j = \expo_w(a_j)$.

Due to the definition of Duplicator's strategy, we know that

* $b_i = u_i  \cdot w^{n_i} \cdot v_i$, where $n_i = \expo_w(b_i)$, and

* $b_j = u_j  \cdot w^{n_j} \cdot v_j$, where $n_j = \expo_w(b_j)$.

Since $a_l \sqsubseteq w^q$ and $b_l \sqsubseteq w^p$, we know from <ref> that $v_i \cdot u_j = w$ or $v_i \cdot u_j = \emptyword$.

\[ a_l = u_i \cdot w^{m_i} \cdot w^g \cdot w^{m_j} \cdot v_j, \]

where $g \in \{0, 1 \}$.
From the definition of Duplicator's strategy,
$ b_l = u_i \cdot w^n \cdot v_j $
for some $n \in \mathbb{N}$.

\begin{align*}
b_i \cdot b_j &= u_i \cdot w^{n_i} \cdot w^g \cdot w^{n_j} \cdot v_j, \\
b_i \cdot b_j &= u_i \cdot w^{n_i + n_j + g} \cdot v_j.
\end{align*}

Therefore, $b_l = b_i \cdot b_j$ if and only if $n = n_i + n_j + g$.

Recall that the result $(\vec a', \vec b')$ of the look-up game $\mathcal{G}_l$ forms a partial isomorphism.
From the look-up game $\mathcal{G}_l$, we know that

* $a_i' = \mathtt{a}^{m_i}$ and $b_i' = \mathtt{a}^{n_i}$,

* $a_j' = \mathtt{a}^{m_j}$ and $b_j' = \mathtt{a}^{n_j}$, and

* $a_l' = \mathtt{a}^{m_i + m_j + g}$ and $b_l' = \mathtt{a}^{n}$.

We consider two cases.

Case 2.1, $g = 0$:
Since $g = 0$, it follows that $a_l' = \mathtt{a}^{m_i + m_j}$, and hence $a_l' = a_i' \cdot a_j'$.
Furthermore, because $(\vec a', \vec b')$ forms a partial isomorphism and $a_l' = a_i' \cdot a_j'$, we have that $b_l' = b_i' \cdot b_j'$.
Hence, $b_l' = \mathtt{a}^{n_i} \cdot \mathtt{a}^{n_j}$, and consequently, $n = n_i+ n_j$.
It therefore follows that $b_l = b_i \cdot b_j$ holds.

Case 2.2, $g = 1$:
Since $g=1$, it follows that $a_l' = \mathtt{a} \cdot \mathtt{a}^{m_i + m_j}$, and thus $a_l' = \mathtt{a} \cdot a_i' \cdot a_j'$.
It follows from <ref> that $b_l' = \mathtt{a} \cdot b_i' \cdot b_j'$, which means that $n = n_i + n_j + 1$.
It therefore follows that $b_l = b_i \cdot b_j$ holds.

Case 3, $\expo_w(a_i) = 0$ and $\expo_w(a_j) \geq 1$:
Since $\expo_w(a_j) \geq 1$ and therefore $\expo(a_l) \geq 1$, we can write

* $a_j = u_j \cdot w^{\expo_w(a_j)} \cdot v_j$ where $u_j, v_j \sqsubset w$, and

* $a_l = u_l \cdot w^{\expo_w(a_l)} \cdot v_l$ where $u_l, v_l \sqsubset w$.

From the definition of Duplicator's strategy, we know that

* $b_i = a_i$,

* $b_j = u_j \cdot w^{\expo_w(b_j)} \cdot v_j$, and

* $b_l = u_l \cdot w^{\expo_w(b_l)} \cdot v_l$.

Since $a_l = a_i \cdot a_j$, we have that

\[ u_l \cdot w^{\expo_w(a_l)} \cdot v_l = a_i \cdot u_j \cdot w^{\expo_w(a_j)} \cdot v_j. \]

Notice that $\expo_w(a_i) = 0$ and $\expo_w(u_j) = 0$, and thus from <ref>, we know that $\expo_w(a_i \cdot u_j) \leq 1$.
If $\expo_w(a_i \cdot u_j) = 0$, then $a_l = a_i \cdot u_j \cdot w^{\expo_w(a_l)} \cdot v_l$, and therefore

\[ u_l \cdot w^{\expo_w(a_l)} \cdot v_l = a_i \cdot u_j \cdot w^{\expo_w(a_l)} \cdot v_l, \]

which implies that $a_i \cdot u_j = u_l$.

If $\expo_w(a_i \cdot u_j) = 1$, then from <ref>, we know that $a_i \cdot u_j = w' \cdot w \cdot w''$, where $w', w'' \sqsubset w$.

\[ (w' \cdot w \cdot w'') \cdot  w^{\expo_w(a_j)} \cdot v_l \sqsubseteq w^q , \]

it immediately follows that $w'' = \emptyword$ must hold, see <ref>.

Thus, either $a_i \cdot u_j = u_l$ or $a_i \cdot u_j = u_l \cdot w$.
Therefore, we can write:

\[ a_l = u_l \cdot w^g \cdot w^{\expo_w(a_j)} \cdot v_j, \]

where $g \in \{ 0, 1\}$.

We know that:

\[ b_i \cdot b_j = b_i \cdot u_j \cdot w^{\expo_w(b_j)} \cdot v_j. \]

Furthermore, $b_i = a_i$, and  $a_i \cdot u_j = u_l \cdot w^g$ where $g \in \{0,1\}$.

\begin{align*}
b_i \cdot b_j = &  u_l \cdot w^g \cdot w^{\expo_w(b_j)} \cdot v_j, \\
= &  u_l \cdot w^{\expo_w(b_j) + g} \cdot v_j,
\end{align*}

for some $g \in \{ 0, 1\}$.
Hence $b_l = b_i \cdot b_j$ if and only if $\expo_w(b_l) = \expo_w(b_i) + g$ for $g \in \{ 0, 1\}$.
From <ref> along with the analogous reasoning given in Case 2, we know that $\expo_w(b_l) = \expo_w(b_i) + g$ must hold.
Consequently, $b_l = b_i \cdot b_j$.

Case 4, $\expo_w(a_i) \geq 1$ and $\expo_w(a_j) = 0$:
This case is symmetric to Case 3.
We therefore omit a proof.

Concluding the proof.
We have shown that if $a_l = a_i \cdot a_j$, then $b_l = b_i \cdot b_j$ must hold.
Due to the arbitrary nature of the notation $\vec a$ and $\vec b$, it follows that if $b_l = b_i \cdot b_j$, then $a_l = a_i \cdot b_j$.
Thus, we have shown that $(\vec a, \vec b)$ is a partial isomorphism.
We have therefore given a winning strategy for Duplicator over $\mathfrak{A}_q$ and $\mathfrak{B}_p$ – two structures that represent $w^q$ and $w^p$ respectively, whenever $\mathtt{a}^q \equiv_{k+3} \mathtt{a}^p$.

§.§ Proof of Proposition <ref>

The proof follows almost directly from <ref>.
Let $w \in \Sigma^+$ and let $z \in \Sigma^+$ be the primitive root of $w$.
That is, $w = z^i$ for some $i \in \mathbb{N}_+$ and some primitive word $z \in \Sigma^+$.
It follows that for any $p \in \mathbb{N}_+$, we have that $w^p = z^{pi}$.
Therefore, if for any primitive word $z \in \Sigma^+$, and any $k \in \mathbb{N}$, there exists $p \in \mathbb{N}_+$ and $v \in \Sigma^*$ such that $v \neq z^{pi}$, where $z^{pi} \equiv_k v$, then we have proven the stated lemma.

To that end, we observe that the set $\{ i \cdot 2^n \mid n \in \mathbb{N}_+ \}$ is not semi-linear (recall Section <ref>, using the same reasoning as for $L_{\mathsf{pow}}$) and, hence, not definable in $\fc$.
Consequently, from <ref>, for any word $w \in \Sigma^+$ and any $k \in \mathbb{N}_+$, there exists $p \in \mathbb{N}_+$ and $v \in \Sigma^*$ such that $w^p \equiv_k v$ where $w^p \neq v$.

§ APPENDIX FOR SECTION <REF>

§.§ Proof of Lemma <ref>

We prove this lemma in two parts.

(1) if and only if (2).
First, we show that the only if direction holds by proving the contrapositive.
In other words, if $v$ and $w$ conjugate, then there does not exist $n_0, m_0 \in \mathbb{N}$ such that
$ \facts(w^{n_0}) \intersect \facts(v^{m_0}) = \facts(w^{n}) \intersect \facts(v^{m}) $
for all $n > n_0$ and all $m > m_0$.
To that end, assume that there exists $x,y \in \Sigma^*$ such that $w = x \cdot y$ and $v = y \cdot x$.
Then, for any $m \in \mathbb{N}$, we have that

\begin{align*}
w^m = & \underbrace{xy \cdot xy \cdot xy \cdots xy}_{m \text{ times}}, \text{ and } \\
v^m = & \underbrace{yx \cdot yx \cdot yx \cdots yx}_{m \text{ times}}.
\end{align*}

Thus $(xy)^{m-1} \in \facts(w^m) \intersect \facts(v^m)$ and $(xy)^{m-1} \notin \facts(w^{m-d}) \intersect \facts(v^{m-d})$ for any $d \geq 2$ where $d \leq m$.
Consequently, the only if direction holds.

Next, we work towards showing the if direction.
In order to prove this direction, we reformulate the statement.

\[ \langinf \df \{ u \in \Sigma^* \mid u \sqsubseteq w^\omega \text{ and }u \sqsubseteq v^\omega \}. \]

Clearly, if $\langinf$ is infinite, then there does not exist $n_0, m_0 \in \mathbb{N}$ such that $ \facts(w^{n_0}) \intersect \facts(v^{m_0}) = \facts(w^{n}) \intersect \facts(v^{m}) $ for all $n > n_0$ and all $m > m_0$.
We can therefore reformulate the contraposition of the if direction as: If $\langinf$ is infinite then $w$ and $v$ conjugate.
To that end, assume $\langinf$ is infinite.
Therefore, for every $n \in \mathbb{N}$, there exists $u \in \langinf$ such that $|u| \geq n$.
Invoking the periodicity lemma, we conclude that $w$ and $v$ are conjugate.

(2) if and only if (3).
Let us first consider the if direction.
Note that for any $n_1, n_2 \in \mathbb{N}$ where $n_1 < n_2$, and any word $w \in \Sigma^*$, we have that $w^{n_1} \sqsubseteq w^{n_2}$.
Therefore, $\facts(w^{n_1}) \subseteq \facts(w^{n_2})$.

Let $w, v \in \Sigma^+$ be two primitive words such that there exists $r \in \mathbb{N}$ where

\[r \geq \mathsf{max} \{ |w| \in \mathbb{N} \mid w \in \facts(w^n) \intersect \facts(v^m) \},\]

for all $n,m \in \mathbb{N}$.
We assume that $r \in \mathbb{N}$ is the smallest such value.
Thus, for some $n', m' \in \mathbb{N}$, we have that

\[ r = \mathsf{max} \{ |w| \in \mathbb{N} \mid w \in \facts(w^{n'}) \intersect \facts(v^{m'}) \}. \]

Furthermore, due to the fact that $\Sigma$ is a fixed and finite alphabet, the number of words of in $\Sigma^*$ with a length that is less than or equal to $r$ is finite.

We now define the language

\[  L_\mathsf{intersect} \df \{ u \in \Sigma^* \mid u \in \facts(w^n) \intersect \facts(v^m) \text{ for some } n,m \in \mathbb{N} \}. \]

Since the number of words in $\Sigma^*$ with a length  that is less than or equal to $r$ is finite, it follows that $L_\mathsf{intersect}$ is also finite.
Combining this with the fact that for any $n_1, n_2 \in \mathbb{N}$ where $n_1 < n_2$, and any word $w \in \Sigma^*$, we have that $\facts(w^{n_1}) \subseteq \facts(w^{n_2})$,
there must exist some $n_0, m_0 \in \mathbb{N}$  such that for all $n \geq n_0$ and all $m \geq m_0$, we have that

\[ \facts(w^{n_0}) \intersect \facts(v^{m_0}) = \facts(w^n) \intersect \facts(v^m). \]

Now let us consider the only if direction.
Assume that there exists $n_0, m_0 \in \mathbb{N}$ such that $\facts(w^{n_0}) \intersect \facts(v^{m_0}) = \facts(w^m) \intersect \facts(v^m)$ for all $n> n_0$ and $m > m_0$.
Let $r \df \mathsf{max} \{ \facts(w^{n_0}) \intersect \facts(v^{m_0})  \}$.
Since for any $n> n_0$ and $m>m_0$, there does not exist $u$ such that $|u| > r$ and $u \in  \facts(w^m) \intersect \facts(v^m)$, this concludes the proof.

§.§ Proof of Lemma <ref>

Let $w_1, w_2, w_3 \in \Sigma^*$, and let $u,v \in \Sigma^+$ be two distinct primitive words such that there exists $r \in \mathbb{N}$ where
$r \geq \mathsf{max} \{ |u| \in \mathbb{N} \mid u \in \facts(u^m) \intersect \facts(v^n) \} $
for all $m,n \geq 1$, see <ref>.
Let $f \colon \mathbb{N} \rightarrow \mathbb{N}$ be an injective function, and let $\varphi \in \fc$ such that

\[w_1 \cdot u^p \cdot w_2 \cdot v^{f(p)} \cdot w_3 \in \lang(\varphi),\]

for all $p \in \mathbb{N}$.

For every $k \in \mathbb{N}$, there exists $p,q \in \mathbb{N}$ such that $p \neq q$ and $w_1 \cdot u^p \cdot w_2 \equiv_k w_1 \cdot u^q \cdot w_2$.

For every $k \in \mathbb{N}$, there exists $p, q \in \mathbb{N}$ such that $\mathtt{a}^p \equiv_{k+3} \mathtt{a}^q$ and $p \neq q$, see <ref>.
Thus, immediately from <ref>, we know that for every $k \in \mathbb{N}$, there exists $p,q \in \mathbb{N}$ such that $p \neq q$ and $ u^p  \equiv_k u^q $.
Now note that there exists some $p_0 \in \mathbb{N}$ such that for all $p, q \geq p_0$, we have that $\facts(w_1) \intersect \facts(u^p) = \facts(w_1) \intersect \facts(u^q)$.
This simply follows from the fact that $w_1$ is a fixed word.
Thus, there exists some $r \in \mathbb{N}$ such that:

\[  r \geq \mathsf{max} \{ |w| \in \mathbb{N} \mid w \in \facts(w_1) \intersect \facts(u^p) \text{ for all } p \in \mathbb{N} \}. \]

Therefore, there exists $p_0, r_0 \in \mathbb{N}$ such that

\[  r_0 = \mathsf{max} \{ |w| \in \mathbb{N} \mid w \in \facts(w_1) \intersect \facts(u^p) \text{ for all } p \geq p_0 \}. \]

We know that for every $k \in \mathbb{N}$, that there exists $p, q \in \mathbb{N}$ such that $u^p \equiv_{k+ r_0 +2} u^q$, where $p \neq q$.
Trivially, $w_1 \equiv_{k + r_0 +2} w_1$ holds.
Thus, invoking <ref>, we know: For every $k \in \mathbb{N}$, there exists $p,q \in \mathbb{N}$ such that $w_1 \cdot u^p \equiv_k w_1 \cdot u^q$, where $p \neq q$.
Using the symmetric reasoning, for every $k \in \mathbb{N}$, there exists $p, q \in \mathbb{N}$ such that $w_1 \cdot u^p \cdot w_2 \equiv_k w_1 \cdot u^q \cdot w_2$, where $p \neq q$.

Note that from <ref>, we know that there exists $n_0, m_0 \in \mathbb{N}$ such that for all $n > n_0$ and $m > m_0$, we have that
$\facts(u^{n_0}) \intersect \facts(v^{m_0}) = \facts(u^n) \intersect \facts(v^m)$.
Furthermore, due to the fact that $w_1$, $w_2$, and $w_3$ are fixed words, there exists $n_1, m_1 \in \mathbb{N}$ such that for all $n > n_1$ and $m > m_1$, we have that

\[
\facts(w_1 \cdot u^{n_1} \cdot w_2) \intersect \facts(v^{m_1} \cdot w_3) = \facts(w_1 \cdot u^n \cdot w_2) \intersect \facts(v^m \cdot w_3).
\]

Let $r' \df \mathsf{max} \{ |w| \in \mathbb{N} \mid w \in \facts(w_1 \cdot u^{n_1} \cdot w_2) \intersect \facts(v^{m_1} \cdot w_3) \}$.

Trivially, we know that $v^{f(p)} \cdot w_3 \equiv_k v^{f(p)} \cdot w_3$ for all $k \in \mathbb{N}_+$.
Furthermore, we know that from <ref> that for every $k \in \mathbb{N}$, there exists $p,q \in \mathbb{N}$ such that $p \neq q$ and $w_1 \cdot u^p \cdot w_2 \equiv_k w_1 \cdot u^q \cdot w_2$.

Thus, for every $k \in \mathbb{N}$, we know that there exists $p,q \in \mathbb{N}$ such that $p \neq q$ and:

* $w_1 \cdot u^p \cdot w_2 \equiv_{k + r' + 2} \, w_1 \cdot u^q \cdot w_2$, and

* $v^{f(p)} \cdot w_3 \equiv_{k + r' + 2} \, v^{f(p)} \cdot w_3$.

We can then invoke <ref> to infer that for all $k \in \mathbb{N}_+$, we have some $p,q \in \mathbb{N}$ where $p \neq q$ and

\[ w_1 \cdot u^p \cdot w_2 \cdot v^{f(p)} \cdot w_3 \equiv_k w_1 \cdot u^q \cdot w_2 \cdot v^{f(p)} \cdot w_3. \]

Since, we have assumed that $w_1 \cdot u^p \cdot w_2 \cdot v^{f(p)} \cdot w_3 \in \lang(\varphi)$ for all $p \in \mathbb{N}$, it follows that $w_1 \cdot u^q \cdot w_2 \cdot v^{f(p)} \cdot w_3  \in \lang(\varphi)$.
Due to the fact that $f$ is injective, $f(q) \neq f(p)$ since $q \neq p$.

§.§ Proof of Lemma <ref>

We now show that each of the following languages are not expressible in $\fc$:

* $L_1 \df \{ \mathtt{a}^n \cdot (\mathtt{ba})^n  \mid n \in \mathbb{N} \}$,

* $L_2 \df \{ \mathtt{a}^i \cdot (\mathtt{ba})^j \mid 1 \leq i \leq j  \}$,

* $L_3 \df \{ \mathtt{b}^n \cdot \mathtt{a}^m \cdot \mathtt{b}^{n+m} \mid m,n \in \mathbb{N} \}$,

* $L_4 \df \{ \mathtt{b}^n \cdot \mathtt{a}^m \cdot \mathtt{b}^{n \cdot m} \mid m,n \in \mathbb{N} \}$, and

* $L_5 \df \{ (\mathtt{abaabb})^m \cdot (\mathtt{bbaaba})^m \mid m \in \mathbb{N} \}$, and

* $L_6 \df \{ \mathtt{a}^n \cdot \mathtt{b}^n \cdot (\mathtt{ab})^n \mid n \in \mathbb{N} \}$.

$L_1$ and $L_2$: The fact that $L_1, L_2 \notin \lang(\fc)$ follows from <ref> and <ref>

$L_3$: For $L_3$, consider the case where $n=0$.
We therefore get the language $\{ \mathtt{a}^m \cdot \mathtt{b}^{m} \mid m \in \mathbb{N} \}$.
From <ref>, we know that for every $k \in \mathbb{N}$, there exists $p, q \in \mathbb{N}$ such that $q \neq p$ and $\mathtt{a}^q \cdot \mathtt{b}^p \equiv_k \mathtt{a}^p \cdot \mathtt{b}^p$.
Thus, invoking <ref>, we conclude that $L_3 \notin \lang(\fc)$.

For $L_4$, let $n=1$. We therefore get the language $\{ \mathtt{b} \cdot \mathtt{a}^m \cdot \mathtt{b}^m \mid m \in \mathbb{N} \}$.
From <ref>, we know that for every $k \in \mathbb{N}$, there exists $p,q \in \mathbb{N}$ such that $p \neq q$ and $\mathtt{b}^p \equiv_{k+3} \mathtt{b}^q$.
It trivially holds that $\mathtt{b} \cdot \mathtt{a}^p \equiv_{k+3} \mathtt{b} \cdot \mathtt{a}^p$.
As $\facts(\mathtt{b}^m) \intersect \facts(\mathtt{b} \cdot \mathtt{a}^n) = \{ \emptyword, \mathtt{b} \}$ for any $n,m \in \mathbb{N}$, we can invoke <ref> with $r=1$ and conclude that $\mathtt{b} \cdot \mathtt{a}^p \cdot \mathtt{b}^p \equiv_{k} \mathtt{b} \cdot \mathtt{a}^p \cdot \mathtt{b}^q$.
Thus, we know from <ref> that $L_4 \notin \lang(\fc)$.

$L_5$: It is clear that $\mathtt{abaabb}$ and $\mathtt{bbaaba}$ are both co-primitive.
Thus, there exists some $r \in \mathbb{N}$ where $r \geq  \mathsf{max}\{ |u| \in \mathbb{N} \mid u \in \facts((\mathtt{abaabb})^m) \intersect \facts((\mathtt{bbaaba})^n) \}$ for all $m,n \geq 1$.
Therefore, we can invoke <ref> to conclude that $L_5 \notin \lang(\fc)$.

$L_6$: We know that for every $k \in \mathbb{N}$, there exists $p, q \in \mathbb{N}$ such that $\mathtt{a}^p \cdot \mathtt{b}^p \equiv_{k+2} \mathtt{a}^q \cdot \mathtt{a}^p$ and $p \neq q$.
Furthermore, it is trivial that $(\mathtt{ab})^p \equiv_{k+2} (\mathtt{ab})^p$ for all $k \in \mathbb{N}$.

Since for any $i,j,l \in \mathbb{N}_+$, it holds that $\facts(\mathtt{a}^i \cdot \mathtt{b}^j) \intersect \facts( (\mathtt{ab})^l ) = \{ \emptyword, \mathtt{a}, \mathtt{b}, \mathtt{ab} \}$, we can invoke <ref> with $r = 2$.
Thus, for every $k \in \mathbb{N}$, there exists $p, q \in \mathbb{N}_+$ with $p \neq q$, and
$ \mathtt{a}^q \cdot \mathtt{b}^p \cdot (\mathtt{ab})^p \equiv_k \mathtt{a}^p \cdot \mathtt{b}^p \cdot (\mathtt{ab})^p$.
Therefore, $L_6 \notin \lang(\fc)$.

§ APPENDIX FOR SECTION 5

§.§ Proof of Lemma <ref>

The proof of this result closely follows the proof of Theorem 6.2 from <cit.>.
We prove this result for completeness sake, as Theorem 6.2 from <cit.> does not directly deal with $\fc$ and $\fc[\reg]$.
In this proof, we only show that if $L \subseteq \Sigma^*$ is a bounded language, then $L \in \lang(\fc)$ if and only if $L \in \lang(\fcreg)$.
Immediately from the fact that $\fc$ has conjunction, disjunction, and negation, we are able to lift this to Boolean combinations of bounded languages.

The only if direction is trivial, and therefore this proof focuses on the if direction.
That is, if $L \in \lang(\fc[\reg])$, and $L$ is bounded, then $L \in \lang(\fc)$.
Let $\varphi \in \fc[\reg]$ such that $\lang(\varphi) = L$, where $L$ is bounded.
Most of the proof of this direction follows from the following claim:

If $\gamma$ is a regular expression that generates a bounded regular language, then there exists $\varphi \in \fc$ such that $\fun{\varphi}(w) = \fun{x \regconst \gamma}(w)$ for all $w \in \Sigma^*$.

From Theorem 1.1 from <cit.>, we know that the class of bounded regular languages are exactly the class of languages that contain all finite languages, all languages $w^*$ where $w \in \Sigma^*$, and is closed under finite union and finite concatenation.
We show that for any $w \in \Sigma^*$, the language $w^*$ can be defined in $\fc$.

As syntactic sugar, we shall use atomic formulas that contain arbitrary concatenation.
It is clear that this can be rewritten into an $\fc$ formula that only contains binary concatenation (for example, see <cit.>).
Now, consider

\[  \varphi_{w^*}(x) \df \exists x \colon \Bigl(  (x \logeq \emptyword) \lor \bigl( (x \logeq w \cdot z) \land (x \logeq z \cdot w)  \bigr) \Bigr). \]

Thus, for any interpretation $\mathcal{I} \df (\mathfrak{A}_w, \subs)$ such that $\mathcal{I} \models \varphi_{w^*}$, we have that either $\subs(x) = \emptyword$, or $\subs(x) = w \cdot u$ and $\subs(x) = u \cdot w$ for some $u \in \Sigma^*$.
Proposition 1.3.2 in Lothaire <cit.> states that if $vu = uv$ for $u,v \in \Sigma^*$, then there is some $z \in \Sigma^*$ and $k_1,k_2 \in \mathbb{N}$ such that $u = z^{k_1}$ and $v = z^{k_2}$.
Thus, if $\subs(x) = w \cdot u$ and $\subs(x) = u \cdot w$ for some $u \in \Sigma^*$, then $\subs(x) = w^k$ for some $k \in \mathbb{N}_+$.

Finite languages, finite union, and finite concatenation can easily be dealt with.
Thus, for any $\fc[\reg]$-formula of the form $x \regconst \gamma$, where $\gamma$ generates a bounded regular language, there exists $\varphi \in \fc$ such that $\fun{\varphi}(w) = \fun{x \regconst \gamma}(w)$ for all $w \in \Sigma^*$.

We now construct $\psi \in \fc$ such that $\lang(\psi) = \lang(\varphi)$.
Note that every set of factors of a bounded language is also bounded (for example, see Lemma 5.1.1 in Ginsburg <cit.>).
Thus, since $\lang(\varphi)$ is bounded, it follows that $\lang(\varphi) \subseteq B$, where $B \df w_1^* \cdots w_n^*$ for some $w_1, \dots, w_n \in \Sigma^*$.
Therefore, for any $w \in \Sigma^*$ and any $x \in \var(\varphi)$, if $\subs \in \fun{\varphi}(w)$, then $\subs(x) \in L_x$, where

\[ L_x \subseteq \{ u \in \Sigma^* \mid u \sqsubseteq v \text{ and } v \in B \} \]

is a bounded regular language.
Therefore, we can replace any atomic formulas of the form $(x \regconst \gamma)$, with $(x \regconst \gamma')$, where $\lang(\gamma') = \lang(\gamma) \intersect L_x$.
Furthermore, it follows that $\lang(\gamma')$ is a bounded regular language.
Then, we can invoke <ref> to replace $(x \regconst \gamma')$ with $\varphi_{\gamma'}(x) \in \fc$ without altering the semantics of the formula.

After carrying out this process of replacing all regular constraints, we have a formula $\psi \in \fc$ that is equivalent to $\varphi$.

§.§ Proof of Theorem <ref>

First, let $\varphi_w(\strucvar) \df \neg \exists z_1, z_2 \colon \Bigl( \neg (z_2 \logeq \emptyword) \land \bigl( (z_1 \logeq z_2 \cdot x) \lor (z_1 \logeq x \cdot z_2)  \bigr)  \Bigr)$.
It is clear that for every interpretation $(\mathfrak{A}_w, \subs)$, where $\mathfrak{A}_w$ is a $\signature_\Sigma$-structure that represents $w \in \Sigma^*$, and where $(\mathfrak{A}_w, \subs) \models \varphi_w(\strucvar)$, we have that $\subs(\strucvar) = w$.

Note that for this proof, we use arbitrary concatenation as a shorthand.
For example, $(x \logeq y_1 \cdot y_2 \cdot y_3)$ is shorthand for $(x \logeq y_1 \cdot z_1) \land (z_1 \logeq y_2 \cdot y_3)$ where $z_1$ is a new and unique variable.
Also note that all the languages given in <ref> are bounded languages, therefore $L_i \notin \lang(\fcreg)$ for $i \in [6]$.

Assume that some relation $R$ from $\mathsf{Num}_\mathtt{a}$, $\mathsf{Add}$, $\mathsf{Mult}$, $\mathsf{Scatt}$, $\mathsf{Perm}$, $\mathsf{Rev}$, $\mathsf{Shuff}$ is definable in $\fc[\reg]$, and let $\varphi_R \in \fc[\reg]$ define $R$.
Now, consider the following $\fc$-formulas:

\begin{align*}
\psi_1 & \df \exists \strucvar, x,y \colon \bigl( \varphi_w(\strucvar) \land (\strucvar \logeq x  y) \land (x \regconst \mathtt{a}^*) \land (y \regconst (\mathtt{ba})^*)  \land \varphi_{\mathsf{Num}_\mathtt{a}}(x,y)\bigr) , \\
\psi_2 & \df \exists \strucvar, x,y \colon \bigl( \varphi_w(\strucvar) \land  (\strucvar \logeq x  y) \land (x \regconst \mathtt{a}^*) \land (y \regconst (\mathtt{ba})^*) \land \varphi_\mathsf{Scatt}(x,y) \bigr), \\
\psi_3 & \df \exists \strucvar, x,y,z \colon \bigl( \varphi_w(\strucvar) \land  (\strucvar \logeq x  y  z) \land (x \regconst \mathtt{b}^*) \land (y \regconst \mathtt{a}^*) \land (z \regconst \mathtt{b}^*)  \land \varphi_\mathsf{Add}(x,y,z)  \bigr), \\
\psi_4 & \df \exists \strucvar, x,y,z \colon \bigl( \varphi_w(\strucvar) \land  (\strucvar \logeq x  y  z)  \land (x \regconst \mathtt{b}^*) \land (y \regconst \mathtt{a}^*) \land (z \regconst \mathtt{b}^*) \land \varphi_\mathsf{Mult}(x,y,z) \bigr), \\
\psi_5 &  \df \exists \strucvar, x,y \colon \bigl( \varphi_w(\strucvar) \land  (\strucvar \logeq x  y) \land (x \regconst (\mathtt{abaabb})^* ) \land (y \regconst (\mathtt{bbaaba})^*) \land \varphi_\mathsf{Perm}(x,y) \bigr), \\
\psi_5' & \df \exists \strucvar, x,y \colon \bigl( \varphi_w(\strucvar) \land  (\strucvar \logeq x  y) \land (x \regconst (\mathtt{abaabb})^* ) \land (y \regconst (\mathtt{bbaaba})^*) \land \varphi_\mathsf{Rev}(x,y) \bigr), \\
\psi_6 & \df \exists \strucvar, x, y, z \colon \bigl( \varphi_w(\strucvar) \land (\strucvar \logeq x y z) \land (x \regconst \mathtt{a}^+) \land (y \regconst \mathtt{b}^+) \land \mathsf{Shuff}(x,y,z)  \bigr).
\end{align*}

It follows that $\lang(\psi_i) = L_i$ for $i \in [6]$, where $L_i$ is defined in <ref>, and $\lang(\psi_5') = L_5$.
Thus the relations $\mathsf{Num}_\mathtt{a}$, $\mathsf{Add}$, $\mathsf{Mult}$, $\mathsf{Scatt}$, $\mathsf{Perm}$, $\mathsf{Rev}$, and $\mathsf{Shuff}$ are not definable in $\fc[\reg]$

Now, let $\Sigma \df \{ \mathtt{a}, \mathtt{b} \}$.
To conclude the proof, assume that for the morphism $h \colon \Sigma^* \rightarrow \Sigma^*$, where $h(\mathtt{a}) = \mathtt{b}$ and $h(\mathtt{b}) = \mathtt{b}$, the relation $\mathsf{Morph}_h$ is definable in $\fcreg$.
Then, let $\psi \df \exists \strucvar, x, y \colon \bigl( \varphi_w(\strucvar) \land (\strucvar \logeq x \cdot y) \land (x \regconst \mathtt{a}^*) \land \mathsf{Morph}_h(x,y) \bigr)$.
It is clear that $\lang(\psi) = \{ \mathtt{a}^n \mathtt{b}^n \mid n \in \mathbb{N} \}$, and $\lang(\psi) \notin \lang(\fcreg)$ (see <cit.> or <ref> along with <ref>).
Thus, $\mathsf{Morph}_h$ is not definable in $\fcreg$.