# Geometric vs Algebraic Nullity for Hyperpaths

Joshua Cooper  Grant Fickes

###### Abstract

We consider the question of how the eigenvarieties of a hypergraph relate to
the algebraic multiplicities of their corresponding eigenvalues. Specifically,
we (1) fully describe the irreducible components of the zero-eigenvariety of a
loose $3$-hyperpath (its “nullvariety”), (2) use recent results of Bao-Fan-
Wang-Zhu to compute the corresponding algebraic multiplicity of zero (its
“nullity”), and then (3) for this special class of hypergraphs, verify a
conjecture of Hu-Ye about the relationship between the geometric
(multi-)dimension of the nullvariety and the nullity.

##  1 Introduction

We begin with two questions:

  1. 1.

What is the combinatorial meaning of the multiplicity of the zero eigenvalue
of a (hyper)graph?

  2. 2.

What is the relationship between the various notions of “multiplicity” for an
eigenvalue?

One may combine these two questions by asking, “What is the combinatorial
meaning of each notion of the multiplicity of the zero eigenvalue of
(hyper)graphs?” For the Laplacian matrix $L(G)=D(G)-A(G)$ of a graph, in the
1970s, Fiedler showed that the multiplicity – in both the algebraic and
geometric senses – of the zero eigenvalue is equal to the number of components
of $G$. Thus it is natural to ask this same question about the seemingly
simpler adjacency matrix $A(G)$, and indeed considerable attention has been
given to Question 1 (e.g., [4, 6, 7, 11, 13]). Because $A(G)$ is real
symmetric and therefore diagonalizable, the answer to Question 2 is simple for
a graph, however: they agree.

In contrast, these questions are nearly untouched for hypergraphs. The first
question has been investigated for some special graphs – for example, [1]
implicitly provides an algorithm for computing the algebraic multiplicity of
zero as an eigenvalue of a hyperpath. In a related vein, [2] analyzes which
eigenvectors corresponding to the zero eigenvalue of a subgraph of $G$ are
also such “null eigenvectors” for $G$. The second question is also almost
entirely unexplored for hypergraphs, and Sturmfels observed (see [8]) that the
relatively straightforward linear eigenspaces of matrices become complicated
“eigenvarieties” when one passes to adjacency tensors/hypermatrices to study
hypergraphs. Hu and Ye [8] take up this matter in earnest and pose a
conjecture about the relationship between the (multi-)dimension of such
varieties and their multiplicities as roots of a hypermatrix’s characteristic
polynomial; these are natural choices for analogizing “geometric” and
“algebraic” multiplicity, respectively, and the conjecture is an attempt to
generalize the fact that the geometric multiplicity of a matrix eigenvalue is
bounded above by its algebraic multiplicity. Another notable contribution [5]
by Fan-Bao-Huang investigated properties of the eigenvariety associated with
the spectral radius of a hypergraph (and, more generally, certain
hypermatrices/tensors).

The aforementioned Hu-Ye Conjecture can be stated as follows; definitions
follow below. Let $\operatorname{am}(\lambda)$ be the algebraic multiplicity
of $\lambda$ as an eigenvalue of the hypermatrix $M$. Let
$V_{\lambda}^{1},\ldots,V_{\lambda}^{\kappa}$ denote the irreducible
components of $V_{\lambda}$, the eigenvariety correponding to $\lambda$.

######  Conjecture 1.1 ([8]).

For any order-$k$ hypermatrix $M$, define

$\operatorname{gm}(\lambda):=\sum_{j=1}^{\kappa}\dim(V_{\lambda}^{j})(k-1)^{\dim(V_{\lambda}^{j})-1}$

Then $\operatorname{gm}(\lambda)\leq\operatorname{am}(\lambda)$.

Here we verify this for the zero eigenvalue of a simple class of $3$-uniform
hypergraphs – sometimes called “loose paths” or “linear hyperpaths” – by
obtaining an explicit description of the irreducible components of their
nullvarieties, using this to obtain a generating function that encodes said
irreducible components’ dimensions, using results from [1] to obtain an
explicit expression for the multiplicity of zero as a root of their
characteristic polynomials, and comparing the resulting quantities to confirm
the conjecture in this special case.

We briefly define the multilinear algebra and spectral hypergraph theory
terminology and notation used throughout the paper. More detailed information
and references can be found in [3, 5]. An order-$k$ hypermatrix111Variously
known as a “tensor” in some literature. $M$ over a ring $R$ is a
$k$-dimensional array of values $M_{i_{1}\cdots i_{k}}\in R$ (usually
$R=\mathbb{C}$), which we often identify with the function
$M:(i_{1},\ldots,i_{k})\mapsto M_{i_{1}\cdots i_{k}}$. A hypermatrix is
cubical if the $i_{j}$, $j=1,\ldots,k$, all belong to the same index set
$\mathcal{I}$, in which case we say that its dimension is $|\mathcal{I}|$, and
a cubical hypermatrix is symmetric if, for every permutation $\sigma$ of
$\mathcal{I}$ and $\mathbf{i}=(i_{1},\ldots,i_{k})\in\mathcal{I}^{k}$,
$M_{\mathbf{i}}=M_{\sigma(\mathbf{i})}$, where
$\sigma(\mathbf{i})=(\sigma(i_{1}),\ldots,\sigma(i_{k}))$. An order-$k$
cubical hypermatrix $M$ of dimension $n$ over $R$ gives rise to a homogeneous
$k$-form $Mx^{k}$, where $x=(x_{1},\ldots,x_{n})$, given by
$\sum_{\mathbf{i}\in[n]^{k}}M_{\mathbf{i}}x^{\mathbf{i}}$, where
$x^{\mathbf{i}}$ denotes $\prod_{j=1}^{k}x_{i_{j}}$ if
$\mathbf{i}=(i_{1},\ldots,i_{k})$. The symmetric hyperdeterminant $\det(M)$ of
a symmetric hypermatrix $M$ over
$R=\mathbb{C}[\\{x_{\mathbf{i}}\\}_{\mathbf{i}\in[n]^{k}}]$ is the unique
monic irreducible polynomial over $R$ which vanishes if and only if
$\nabla(Mx^{k})=\mathbf{0}$ for some nonzero vector $x\in\mathbb{C}^{n}$. The
identity hypermatrix $I$ of rank $k$ and order $n$ is the function so that
$I(i_{1},\ldots,i_{k})=1$ if $i_{1}=\cdots=i_{k}$ and $0$ otherwise. Write
$\lambda M$ for the hypermatrix whose $\mathbf{i}$ entry is $\lambda
M_{\mathbf{i}}$ for each valid multi-index $\mathbf{i}$. Then the
characteristic polynomial of $M$ is $\phi_{M}(\lambda):=\det(\lambda
I-M)\in\mathbb{C}[\lambda]$. The (homogeneous) spectrum of $M$ is the multiset
of roots of $\phi_{M}(\lambda)$; the elements $\lambda$ of the adjacency
spectrum of $M$ are referred to as eigenvalues of $M$, and any nonzero $x$ so
that $\nabla[(M-\lambda I)x^{k}]=0$ is a corresponding eigenvector. The set of
all eigenvectors corresponding to an eigenvalue $\lambda$ of a hypermatrix $M$
of dimension $n$ is its $\lambda$-eigenvariety $\mathcal{V}_{\lambda}$. Then
$\mathcal{V}_{\lambda}$ is an affine algebraic variety in $\mathbb{C}^{n}$;
indeed, since the equations defining eigenvectors are homogeneous,
$\mathcal{V}_{\lambda}$ can also be viewed as a projective variety, although
we adhere to the affine perspective presently. The multiplicity of $\lambda$
as a root of $\phi_{M}(\lambda)$ is its algebraic muliplicity, and the
dimension of the variety $\mathcal{V}_{\lambda}$ is its geometric
multiplicity. Since the $0$-eigenvariety of a matrix $M$ – i.e., a hypermatrix
of order $k=2$ – is its nullspace, we refer to the $0$-eigenvariety as the
nullvariety of $M$. We also refer to the algebraic multiplicity of $0$ as the
nullity of $M$.

A (uniform) hypergraph $\mathcal{H}$ of rank $k$ is a pair $(V,E)$, where
$E\subset\binom{V}{k}$. The adjacency hypermatrix of a hypergraph
$\mathcal{H}$ is the symmetric hypermatrix
$A(\mathcal{H}):V^{k}\rightarrow\mathbb{C}$ so that
$A(\mathcal{H})_{v_{1}\cdots v_{k}}$ is $1/(k-1)!$ if
$\\{v_{1},\ldots,v_{k}\\}\in E(\mathcal{H})$ and $0$ otherwise. The $k$-form
$p(x_{1},\ldots,x_{k})=A(\mathcal{H})x^{k}$ is sometimes known as the
Lagrangian polynomial of $\mathcal{H}$; the coordinate $\partial p/\partial
x_{i}$ of $\nabla A(\mathcal{H})x^{k}$ is ($k$ times) the Langrangian
polynomial of the link of vertex $v_{i}$ in $\mathcal{H}$, i.e., the
hypergraph whose edges are $\\{e\setminus\\{x_{i}\\}|v_{i}\in e\in
E(\mathcal{H})\\}$. We will often abuse notation slightly and refer to the
multilinear algebraic properties of $A(\mathcal{H})$ by describing them as
properties of $\mathcal{H}$ instead. For example, the (adjacency) spectrum of
a hypergraph $\mathcal{H}$ is the spectrum of $A(\mathcal{H})$, the
nullvariety of $\mathcal{H}$ is the nullvariety of $A(\mathcal{H})$, and
$\phi_{\mathcal{H}}(\lambda):=\phi_{A(\mathcal{H})}(\lambda)$. A loose
hyperpath $P_{n}^{k}$ is the $k$-uniform hypergraph on $n$ edges
$\\{e_{1},\ldots,e_{n}\\}$ so that, for $i\neq j$, $|e_{i}\cap e_{j}|$ is $1$
if $|i-j|=1$ and $0$ otherwise. We label the vertex set $V(P_{n}^{k})$ with
$\\{v_{1},\ldots,v_{(k-1)n+1}\\}$ so that
$e_{j}=\\{v_{(k-1)(j-1)+1},\ldots,v_{(k-1)j+1}\\}$ for $j\in[n]$.

Throughout, we also write $\mathcal{V}(S)$ for the affine variety over
$\mathbb{C}$ defined as the zero locus of the set of polynomials $S$, and
$\mathcal{V}(p)$ for $\mathcal{V}(\\{p\\})$. We write $\langle S\rangle$ for
the ideal generated by a set of polynomials $S$, and call $S$ irredundant if
$\langle S^{\prime}\rangle\neq\langle S\rangle$ when $S^{\prime}\subsetneq S$
is any proper subset. Also, given $p\in\mathbb{C}[x_{1},\ldots,x_{m}]$ and a
vector $\mathbf{c}\in\mathbb{C}^{m}$, we will sometimes say “$\mathbf{c}$
satisfies $p$” if $p(\mathbf{c})=0$.

In the next section, we enumerate the irreducible components of the
nullvariety of $P_{n}^{3}$ and capture their count and the quantity
$\operatorname{gm}(0)$ as a generating function. The following section repeats
this exercise, but for the nullity $\operatorname{am}(0)$ of $P_{n}^{3}$ – in
fact, more generally $P_{n}^{k}$ for $k\geq 3$. The last section compares
these two functions of $n$, verifying the Hu-Ye Conjecture for the zero
eigenvalue of $P_{n}^{3}$.

##  2 Null Variety for Rank-$3$ Loose Hyperpaths

We examine the “geometric multiplicity” of the zero eigenvalue for a
hypergraph $\mathcal{H}$, or more accurately, the multiset of dimensions of
irreducible components of the corresponding nullvariety. Our strategy will be
as follows. First, we describe the ideal whose zero locus is the nullvariety,
generated by the Lagrangian polynomials of the links of all vertices. Each of
the degree-one vertices contributes a polynomial to the ideal which is a
simple product of variables. Thus, the vanishing of these monomials reduces to
the vanishing of each of their constituent variables, one at a time.
Considering the set of possible vanishing monomials – which correspond to
vertices/coordinates where portions of the nullvariety are zero – results in
substantial simplification of the set of polynomials in the ideal. Thus,
taking the union of all such vanishing set possibilities gives a decomposition
of the nullvariety into simpler subvarieties. We then analyze these
subvarieties to show that they are irreducible. Next, it is necessary to
identify which such irreducible subvarieties are maximal in order to obtain an
irredundant list of irreducible components. Finally, we describe the multiset
of these components’ dimensions by counting the number of polynomials
determining them, leading to an expression for $\operatorname{gm}(0)$. As a
warm-up, and for completeness, we start with the one-edge and two-edge
hyperpaths.

###  2.1 Small Cases

######  Proposition 2.1.

The $3$-uniform hyperedge $\mathcal{H}=P_{1}^{3}$ has three irreducible
components of dimension $1$, and $\operatorname{gm}(0)=3$.

###### Proof.

Let the vertices of $\mathcal{H}$ be $v_{1},v_{2},v_{3}$. Given a null vector
$x$, if the adjacency tensor of $\mathcal{H}$ is $A=A(\mathcal{H})$, then the
$i$-th component of $Ax^{2}$ is given by $\sum_{\\{i,j,k\\}\in
E(\mathcal{H})}x_{j}x_{k}=x_{1}x_{2}x_{3}/x_{i}$. Since $x$ is a null vector,
we have $x_{1}x_{2}=x_{1}x_{3}=x_{2}x_{3}=0$, and we consider the variety
$V_{0}\subset\mathbb{C}^{3}$ in three-dimensional affine space defined by
these equations. If $p,q$ are polynomials, then
$\mathcal{V}(p,q)=\mathcal{V}(p)\cap\mathcal{V}(q)$ and
$\mathcal{V}(pq)=\mathcal{V}(p)\cup\mathcal{V}(q)$. Therefore, we have the
following.

$\displaystyle\mathcal{V}(x_{1}x_{2},x_{1}x_{3},x_{2}x_{3})$
$\displaystyle=\mathcal{V}(x_{1}x_{2})\cap\mathcal{V}(x_{1}x_{3})\cap\mathcal{V}(x_{2}x_{3})$
$\displaystyle=\left[\mathcal{V}(x_{1})\cup\mathcal{V}(x_{2})\right]\cap\left[\mathcal{V}(x_{1})\cup\mathcal{V}(x_{3})\right]\cap\left[\mathcal{V}(x_{2})\cup\mathcal{V}(x_{3})\right]$

This is equal to the union over all choices of
$\mathcal{V}(x_{i})\cap\mathcal{V}(x_{j})\cap\mathcal{V}(x_{k})=\mathcal{V}(x_{i},x_{j},x_{k})$
where $i\in\\{1,2\\}$, $j\in\\{1,3\\}$, and $k\in\\{2,3\\}$. Thus, maximal
subvarieties of $V_{0}$ correspond to minimal sets $\\{i,j,k\\}$ given these
conditions, i.e.,

$\left[\mathcal{V}(x_{1})\cup\mathcal{V}(x_{2})\right]\cap\left[\mathcal{V}(x_{1})\cup\mathcal{V}(x_{3})\right]\cap\left[\mathcal{V}(x_{2})\cup\mathcal{V}(x_{3})\right]=\mathcal{V}(x_{1},x_{2})\cup\mathcal{V}(x_{1},x_{3})\cup\mathcal{V}(x_{2},x_{3}).$

Since $\mathcal{V}(x_{i},x_{j})$ is the $x_{k}$-axis, $V_{0}$ is the union of
three lines. ∎

######  Proposition 2.2.

If $\mathcal{H}=P_{2}^{3}$, then $V_{0}$ has one component of dimension $1$
and another of dimension $3$, so that $\operatorname{gm}(0)=13$.

###### Proof.

Let the vertices of $\mathcal{H}$ be $v_{1},v_{2},v_{3},v_{4},v_{5}$. Let $x$
be a null vector. The equations defining $V_{0}\subset\mathbb{C}^{5}$ are
$x_{1}x_{3}=x_{2}x_{3}=x_{1}x_{2}+x_{4}x_{5}=x_{3}x_{4}=x_{3}x_{5}$. Decompose
this system as follows:

$V_{0}=\mathcal{V}(x_{1}x_{3},x_{2}x_{3},x_{3}x_{4},x_{3}x_{5})\cap\mathcal{V}(x_{1}x_{2}+x_{4}x_{5}).$

In the first conjunct, we have intersections of unions, namely

$\mathcal{V}(x_{1}x_{3},x_{2}x_{3},x_{3}x_{4},x_{3}x_{5})=\left[\mathcal{V}(x_{1})\cup\mathcal{V}(x_{3})\right]\cap\left[\mathcal{V}(x_{2})\cup\mathcal{V}(x_{3})\right]\cap\left[\mathcal{V}(x_{3})\cup\mathcal{V}(x_{4})\right]\cap\left[\mathcal{V}(x_{3})\cup\mathcal{V}(x_{5})\right].$

Expand the expression on the right to obtain the union over all choices of
$\mathcal{V}(x_{i})\cap\mathcal{V}(x_{j})\cap\mathcal{V}(x_{k})\cap\mathcal{V}(x_{\ell})=\mathcal{V}(x_{i},x_{j},x_{k},x_{\ell})$
where $i\in\\{1,3\\}$, $j\in\\{2,3\\}$, $k\in\\{3,4\\}$, and
$\ell\in\\{3,5\\}$. The union
$\bigcup_{\\{i,j,k,\ell\\}}\mathcal{V}(x_{i},x_{j},x_{k},x_{\ell})$ is the
union over the minimal sets $\\{i,j,k,\ell\\}$ of this form, i.e.,

$\displaystyle\left[\mathcal{V}(x_{1})\cup\mathcal{V}(x_{3})\right]\cap\left[\mathcal{V}(x_{2})\cup\mathcal{V}(x_{3})\right]$
$\displaystyle\cap\left[\mathcal{V}(x_{3})\cup\mathcal{V}(x_{4})\right]\cap\left[\mathcal{V}(x_{3})\cup\mathcal{V}(x_{5})\right]$
$\displaystyle=$
$\displaystyle\mathcal{V}(x_{3})\cup\mathcal{V}(x_{1},x_{2},x_{4},x_{5}).$

The second variety has dimension four, while the first variety is the $x_{3}$
axis. It remains to intersect each such set with
$\mathcal{V}(x_{1}x_{2}+x_{3}x_{4})$. Note that
$\mathcal{V}(x_{1},x_{2},x_{4},x_{5})\subseteq\mathcal{V}(x_{1}x_{2}+x_{4}x_{5})$,
so that intersection yields $\mathcal{V}(x_{1},x_{2},x_{4},x_{5})$. The
intersection of $\mathcal{V}(x_{1}x_{2}+x_{4}x_{5})$ and $\mathcal{V}(x_{3})$
gives $\mathcal{V}(x_{1}x_{2}+x_{4}x_{5},x_{3})$, which is a three-dimensional
variety. Thus,

$V_{0}=\mathcal{V}(x_{1},x_{2},x_{4},x_{5})\cup\mathcal{V}(x_{1}x_{2}+x_{4}x_{5},x_{3}),$

which is the union of a one-dimensional and a three-dimensional irreducible
component. ∎

###  2.2 General $3$-uniform case

We now generalize the above approach to all $3$-uniform loose hyperpaths.
Define $p_{k}$ to be $x_{k-2}x_{k-1}+x_{k+1}x_{k+2}$ for some integer $k$. For
integer $n\geq 1$, define $A^{\prime}_{n}:=\\{2k+1:1\leq k\leq n-1\\}$, and
let $A_{n}=A_{n}^{\prime}\setminus\\{3,2n-1\\}$. Define $\mathcal{F}_{n}$ be
the collection of “Fibonacci subsets” of $A^{\prime}_{n}$, i.e., sets
containing at least one of each two consecutive elements:

$\mathcal{F}_{n}=\\{S\subset A^{\prime}_{n}:\forall k\in[n-2],(2k+1\in
S)\vee(2k+3\in S)\\}$

Let $S$ be any element of $\mathcal{F}_{n}$. We say that a set of polynomials
$B\subset\\{x_{i}:i\in[2n+1]\\}\cup\\{p_{i}:i\in A^{\prime}_{n}\\}$ is
$S$-admissible if it can be obtained in the following manner. Define $U_{i}$,
$i=1,2,3,4$, in the following way.

  1. 1.

$U_{1}=\\{x_{i}:i\in S\\}$

  2. 2.

$U_{2}=\begin{cases}\\{x_{1},x_{2}\\}&\mbox{if }x_{3}\notin U_{1},x_{5}\in
U_{1}\\\ \\{x_{1}\\}\mbox{ or }\\{x_{2}\\}&\mbox{if
}\\{x_{3},x_{5}\\}\subseteq U_{1}\\\ \\{p_{3}\\}&\mbox{if }x_{3}\in
U_{1},x_{5}\notin U_{1}\end{cases}$

  3. 3.

$U_{3}=\begin{cases}\\{x_{2n},x_{2n+1}\\}&\mbox{if }x_{2n-1}\notin
U_{1},x_{2n-3}\in U_{1}\\\ \\{x_{2n}\\}\mbox{ or }\\{x_{2n+1}\\}&\mbox{if
}\\{x_{2n-3},x_{2n-1}\\}\subseteq U_{1}\\\ \\{p_{2n-1}\\}&\mbox{if
}x_{2n-1}\in U_{1},x_{2n-3}\notin U_{1}\end{cases}$

  4. 4.

$U_{4}=\bigcup_{a\in A}\begin{cases}\emptyset&\mbox{if
}\\{x_{a-2},x_{a+2}\\}\subseteq U_{1}\\\ \\{x_{a+1}\\}&\mbox{if }x_{a-2}\in
U_{1},x_{a+2}\notin U_{1}\\\ \\{x_{a-1}\\}&\mbox{if }x_{a-2}\notin
U_{1},x_{a+2}\in U_{1}\\\ \\{p_{a}\\}&\mbox{if
}\\{x_{a-2},x_{a+2}\\}\subseteq\\{x_{j}:j\in A_{n}^{\prime}\\}\setminus
U_{1}\\\ \end{cases}$

Note that the only choices that do not depend only on $S$ arise from cases of
$U_{2}$ and $U_{3}$. If we let $\mathcal{U}_{i}$ denote the collection of all
allowable $U_{i}$, $i=2,3$, then $\mathcal{T}_{S}=\\{U_{1}\cup U_{2}\cup
U_{3}\cup U_{4}:U_{2}\in\mathcal{U}_{2},U_{3}\in\mathcal{U}_{3}\\}$ is the
collection of $S$-admissible sets. We also remark that for each
$B\in\mathcal{T}_{S}$, $B\subseteq\mathbb{C}[x_{1},\dotsc,x_{2n+1}]$. Define
$I_{B}$ as the ideal in $\mathbb{C}[x_{1},\dotsc,x_{2n+1}]$ generated by the
polynomials in $B$. Furthermore, let $\mathcal{I}_{n}$ denote the collection
of all such ideals generated by $S$-admissible sets in $\mathcal{F}_{n}$,
i.e.,

$\mathcal{I}_{n}=\\{I_{B}:B\in\mathcal{T}_{S}\text{ for some
}S\in\mathcal{F}_{n}\\}.$

Before proceeding, we note the following useful fact.

######  Proposition 2.3 (Prop. 5.20 in [9]).

If $V$ and $W$ are irreducible affine varieties over an algebraically closed
field, then $V\times W$ is as well.

In fact, the way we will often use Proposition 2.3 is: if
$I\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ and
$J\subset\mathbb{C}[y_{1},\ldots,y_{m}]$ are prime ideals and
$I^{\prime},J^{\prime}$ are the ideals they generate in
$\mathbb{C}[x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]$, respectively, then
$I^{\prime}+J^{\prime}$ is also a prime ideal, and
$\mathcal{V}(I^{\prime}+J^{\prime})=\mathcal{V}(I)\times\mathcal{V}(J)$. The
following lemma establishes that the ideals in $\mathcal{I}_{n}$ are prime.

######  Lemma 2.4.

For $n\geq 3$ and each $I_{B}\in\mathcal{I}_{n}$, $I_{B}$ is a prime ideal in
$\mathbb{C}[x_{1},\dotsc,x_{2n+1}]$, and $B$ is an irredundant set of
generators for it.

###### Proof.

First, since polynomial rings over $\mathbb{C}$ are UFDs, primality is
equivalent to irreducibility throughout. Note that the generators of $I_{B}$
are a finite collection of variables and polynomials of the form $p_{k}$ for
some odd integer(s) $k$. Let $\mathcal{X}=\\{x_{i}:x_{i}\in I_{B}\\}$ and
$\mathcal{X}^{\prime}=\\{x_{1},\dotsc,x_{2n+1}\\}\setminus\mathcal{X}$.
Furthermore, let $\mathcal{K}=\\{p_{k}:p_{k}\in I_{B}\\}$. By Proposition 2.3,
it suffices to show the primality of the ideal generated by $\mathcal{K}$ in
the ring $\mathbb{C}[\mathcal{X}^{\prime}]$, since the variables appearing in
$\mathcal{K}$ are disjoint from those of $\mathcal{X}$. The base case
$|\mathcal{K}|=1$ holds if and only if the polynomial in $\mathcal{K}$ is
irreducible. Let $i\in\mathbb{Z}$ so that $p_{i}\in\mathcal{K}$. It is easy to
see that $p_{i}=x_{i-2}x_{i-1}+x_{i+1}x_{i+2}$ is irreducible. Fix an integer
$k\geq 1$ and suppose that the result holds for all $\mathcal{K}^{\prime}$
with $|\mathcal{K}^{\prime}|=k$. Let $|\mathcal{K}|=k+1$ and let $p_{i}$ be
any element of $\mathcal{K}$. By the induction hypothesis,
$\mathcal{K}\setminus\\{p_{i}\\}$ generates a prime ideal. From here we split
into the following two cases.

Case $1$: The variables of $p_{i}$ are disjoint from those of
$\mathcal{K}\setminus\\{p_{i}\\}$. As noted above, $p_{i}$ generates a prime
ideal in $\mathbb{C}[x_{i-2},x_{i-1},x_{i+1},x_{i+2}]$, so it also generates a
prime ideal in $\mathbb{C}[\mathcal{X}]$. Moreover, the induction hypothesis
gives that $\mathcal{K}\setminus\\{p_{i}\\}$ generates a prime ideal in
$\mathbb{C}[\mathcal{X}^{\prime}\setminus\\{x_{i-2},x_{i-1},x_{i+1},x_{i+2}\\}]$,
further implying that $\mathcal{K}\setminus\\{p_{i}\\}$ generates a prime
ideal in $\mathbb{C}[\mathcal{X}]$ by Proposition 2.3.

Case $2$: Some variables of $p_{i}$ also occur as variables of polynomials in
$\mathcal{K}\setminus\\{p_{i}\\}$. Since $i$ is odd, $i-1$ and $i+1$ are even.
Moreover, the variables $x_{i-1}$ (and $x_{i+1}$) appear in no other
polynomial of $\mathcal{K}$, since $p_{i},p_{i-2}\in\mathcal{K}$
(respectively, $p_{i}$ and $p_{i+2}$) implies both $i$ and $i-2$
(respectively, $i$ and $i+2$) are outside the set $B$ used to generate the
original ideal $I_{B}$, contradicting that $B$ is generated by a Fibonacci
subset of $A_{n}^{\prime}$. Therefore, the only overlap in variables comes
from $x_{i-2}$ and $x_{i+2}$.

Let $X$ be the collection of variables in $p_{i}$ that also appear in
polynomials of $\mathcal{K}\setminus\\{p_{i}\\}$. Define
$Y:=\\{x_{i-2},x_{i-1},x_{i+1},x_{i+2}\\}\setminus X$, and let $Z$ be the
collection of variables in polynomials of $\mathcal{K}$ except the variables
contained in $X$. Define a collection of new variables
$X^{\prime}:=\\{x_{m}^{\prime}:x_{m}\in X\\}$. Let the polynomial
$p_{i}^{\prime}$ be $p_{i}$ evaluated at the variables of $X^{\prime}$ and
$Y$, where each input variable matches the index of the existing variable. Let
$I$ be the ideal generated by $\mathcal{K}\setminus\\{p_{i}\\}$. The induction
hypothesis gives that $I$ is prime. The ideal $\langle p_{i}^{\prime}\rangle$
is prime because $p_{i}^{\prime}$ is irreducible. Proposition 2.3 gives the
primality of the ideal generated by $I+\langle p_{i}^{\prime}\rangle$. Let
$\sigma:\mathbb{C}[X\cup Z]\times\mathbb{C}[X^{\prime}\cup
Y]\to\mathbb{C}[X\cup Y\cup Z]$ be the quotient homomorphism $\sigma:f\mapsto
f+\langle\\{x_{i}-x_{i}^{\prime}:x_{i}\in X\\}\rangle$. Clearly, $\sigma$ is
surjective, so Proposition $3.34$b in [9] (that surjective homomorphisms
preserve primality) completes the proof of primality.

The second claim, that $B$ is irredundant, is straightforward to check from
the conditions defining $U_{i}$, $i=1,\ldots,4$: with respect to the variable
ordering

$x_{1}\prec x_{3}\prec\cdots\prec x_{2n+1}\prec x_{2}\prec
x_{4}\prec\cdots\prec x_{2n},$

the set $B$ is triangular (its $\prec$-main variables are distinct), so form a
basis of $I_{B}=\langle B\rangle$. ∎

If we let $\mathcal{W}_{n}$ denote the collection of affine varieties
generated by ideals of $\mathcal{I}_{n}$, i.e.,
$\mathcal{W}_{n}:=\bigcup_{I\in\mathcal{I}_{n}}\mathcal{V}(I)$, then the
previous lemma implies that all varieties in $\mathcal{W}_{n}$ are
irreducible. However, some of these varieties may not be inclusion-maximal, so
they are not irreducible components, a matter we address presently.

######  Lemma 2.5.

Let $I_{V}$ denote the ideal in $\mathcal{I}_{n}$ which generates the variety
$V$. Furthermore, let $\Theta_{V}$ denote the collection of all maximal sets
of consecutive odd-indexed $x_{i}\in I_{V}$ whose indices are contained in
$A_{n}^{\prime}$. Then, the variety $V\in\mathcal{W}_{n}$ is inclusion-maximal
if and only if $\Theta_{V}$ does not contain a set with odd cardinality $m\geq
3$.

###### Proof.

Suppose first that there exists an odd $m\geq 3$ so that
$X:=\\{x_{a},x_{a+2},\ldots,x_{a+2(m-1)}\\}\in\Theta_{V}$. Let $B$ be the
generating set for $I_{V}$ which corresponds to an $S$-admissible set for some
$S\in\mathcal{F}_{n}$. If $a>3$, then the maximality of $X$ implies
$x_{a-2}\notin I_{V}$, giving that $x_{a-1}\in I_{V}$ by condition (4) in the
definition of $S$-admissible. On the other hand, if $a=3$, then condition (2)
gives the presence of either $x_{1}$ or $x_{2}$ in $I_{V}$. In either case,
there exists $q_{1}\in\mathbb{N}$ so that $x_{q_{1}}\in
I_{V}\cap\\{x_{a-2},x_{a-1}\\}$. Similarly, there exists $q_{2}$ so that
$x_{q_{2}}\in I_{V}\cap\\{x_{a+2m-1},x_{a+2m}\\}$. Now, define
$X^{\prime}:=\\{x_{q_{1}},x_{q_{2}}\\}\cup\\{x_{a+2},x_{a+6},\dotsc,x_{a+2(m-2)}\\}$,
which is well-defined since $|X|$ is odd, and, let
$P^{\prime}=\\{p_{a},p_{a+4},\dotsc,p_{a+2(m-1)}\\}$. Note that
$|X^{\prime}|=|P^{\prime}|+1$, so that $|B|>|(B\setminus X^{\prime})\cup
P^{\prime}|$. Inspection shows that $(B\setminus X^{\prime})\cup P^{\prime}$
is an $S$-admissible set for some $S\in\mathcal{F}_{n}$. Moreover, if every
polynomial in $B$ yields $0$ when evaluated at a tuple
$(c_{1},c_{2},\dotsc,c_{2n+1})\in\mathbb{C}^{2n+1}$, then
$(c_{1},c_{2},\dotsc,c_{2n+1})$ is also a common zero of all polynomials in
$(B\setminus X^{\prime})\cup P^{\prime}$, since all polynomials of
$P^{\prime}$ evaluate to zero if those of
$X\cup\\{x_{q_{1}},x_{q_{2}}\\}\subseteq B$ do as well. Then $V$ is not
maximal.

It remains to establish the converse. If $n\leq 3$, it is straightforward to
check that the varieties in $\mathcal{W}_{n}$ are maximal. Suppose now that
$n\geq 4$ and that $V\in\mathcal{W}_{n}$ is not maximal, so there exists
$V^{\prime}\in\mathcal{W}_{n}$ with $V\subsetneq V^{\prime}$. Let $B$ and
$B^{\prime}$ be the admissible sets which generate $I_{V}$ and
$I_{V^{\prime}}$ respectively, meaning $B$ and $B^{\prime}$ also generate $V$
and $V^{\prime}$. Since $V\subset V^{\prime}$, if values for
$x_{1},\dotsc,x_{2n+1}$ are chosen so that all polynomials in $B$ are zero,
then all the polynomials in $B^{\prime}$ are also zero for the same choice of
values for $x_{1},\dotsc,x_{2n+1}$. By the definition of admissible sets, $B$
and $B^{\prime}$ are each minimal generating sets of their respective ideals,
and additionally $B\cap B^{\prime}\notin\\{B,B^{\prime}\\}$, i.e., neither is
a subset of the other.

Next, we establish the following claim regarding the inclusion of single-
variable monomials between $B$ and $B^{\prime}$. Let $i\in[2n-1]$.

######  Claim 2.6.

If $x_{i}\notin B$, then $x_{i}\notin B^{\prime}$.

###### Proof of claim.

Suppose $i\in[2n-1]$ and $x_{i}\notin B$. Let
$\mathbf{c}=(c_{1},\ldots,c_{2n+1})\in V$. If $c_{i}\neq 0$, then $x_{i}\notin
B^{\prime}$, as otherwise $\mathbf{c}\not\in V^{\prime}$, contradicting that
$V\subset V^{\prime}$. Suppose now that $c_{i}=0$. The following cases
construct another point $\mathbf{c}^{\prime}$ so that $\mathbf{c}^{\prime}\in
V$ with $c^{\prime}_{i}\neq 0$, again obtaining a contradiction to $V\subset
V^{\prime}$.

Case $1$: $i\in\\{1,2,2n,2n+1\\}$. Without loss of generality, suppose $i=1$,
and note that the only polynomials of any admissible set in which $x_{1}$
occurs are $x_{1}$ and $p_{3}$, and, in this case, $x_{1}\not\in B$. If
$p_{3}\in B$, define $\mathbf{c}^{\prime}$ so that $c^{\prime}_{i}=c_{i}$ for
$i\not\in\\{1,2\\}$, but $c^{\prime}_{1}=1$ and $c^{\prime}_{2}=-x_{4}x_{3}$.
The choice of $c^{\prime}_{2}$ gives $p_{3}(\mathbf{c^{\prime}})=0$. Since
$p_{3}\in B$ implies $x_{2}\notin B$, $\mathbf{c}^{\prime}\in V$. If
$p_{3}\notin B$, define $\mathbf{c}^{\prime}$ so that $c^{\prime}_{j}=c_{j}$
for $j\neq 1$, but $c^{\prime}_{1}=1$. All polynomials of $B$ are satisfied by
$\mathbf{c}^{\prime}$.

Case $2$: $3\leq i\leq 2n-1$ and $i$ odd. Note that the only possible
polynomials containing $x_{i}$ are $p_{i-2}$, $p_{i+2}$, and $x_{i}$. By
assumption, $x_{i}\notin B$, leaving only $p_{i-2}$ and $p_{i+2}$. Define
$\mathbf{c}^{\prime}$ so that $c^{\prime}_{j}=c_{j}$ for
$j\not\in\\{i-1,i,i+1\\}$ and $c_{i}^{\prime}=1$. If $p_{i-2}\in B$ (resp.
$p_{i+2}\in B$), define $c_{i-1}^{\prime}=-x_{i-4}x_{i-3}$ (resp.
$c_{i+1}^{\prime}=-x_{i+4}x_{i+3}$), so that $p_{i-2}(\mathbf{c}^{\prime})=0$
(resp. $p_{i+2}(\mathbf{c}^{\prime})=0$). The existence of $p_{i-2}\in B$
(resp. $p_{i+2}$) implies $x_{i-1}\notin B$ (resp. $x_{i+1}\notin B$).
Clearly, $p_{i}$ is the only other polynomial containing either $x_{i-1}$ or
$x_{i+1}$, but $x_{i}\notin B$ implies $x_{i-2},x_{i+2}\in B$, further giving
that $p_{i}\notin B$. Therefore, all polynomials of $B$ are satisfied by
$\mathbf{c}^{\prime}$.

Case $3$: $3\leq i\leq 2n-1$ and $i$ even. Note that the only possible
polynomials containing $x_{i}$ are $p_{i-1}$, $p_{i+1}$, and $x_{i}$. By
assumption, $x_{i}\notin B$, leaving only $p_{i-1}$ and $p_{i+1}$. If
$x_{i-1},x_{i+1}\in B$, then $p_{i-1},p_{i+1}\notin B$, so defining
$c_{j}^{\prime}=c_{j}$ for $j\neq i$ and $c_{i}^{\prime}=1$ yields a
$\mathbf{c}^{\prime}$ satisfying all polynomials of $B$. Suppose now that not
both of $x_{i-1}$ and $x_{i+1}$ are in $B$. Condition (1) gives that at least
one of $x_{i-1}$ and $x_{i+1}$ are in $B$, so $B$ cannot contain both of
$p_{i-1}$ and $p_{i+1}$. Without loss of generality, suppose $p_{i-1}\in B$,
giving that $x_{i+1}\notin B$. In this case, define $\mathbf{c}^{\prime}$ so
that $c^{\prime}_{j}=c_{j}$ for $j\not\in\\{i,i+1,i+2\\}$, $c_{i}^{\prime}=1$,
and $c_{i+1}^{\prime}=-c_{i-3}c_{i-2}$. Then $p_{i-1}(\mathbf{c}^{\prime})=0$,
so the only other polynomial containing $x_{i+1}$ is $p_{i+3}$. If
$c_{i+1}^{\prime}=0$, then we already have $\mathbf{c}^{\prime}\in V$. Suppose
now that $c_{i+1}^{\prime}\neq 0$. If $p_{i+3}\notin B$, then take
$c_{i+2}^{\prime}=c_{i+2}$, and $\mathbf{c}^{\prime}\in V$. Otherwise, take
$c_{i+2}^{\prime}=-c_{i+4}c_{i+5}/c_{i+1}^{\prime}$. In this case,
$x_{i+3},p_{i+3}\in B$ gives that $x_{i+2}\notin B$. Furthermore, $x_{i+3}\in
B$ also implies $p_{i+1}\notin B$, meaning $p_{i+3}$ is the only polynomial of
$B$ containing $x_{i+2}$. Therefore, in this case, $\mathbf{c}^{\prime}\in V$.
∎

We will often use the above claim in contrapositive form, i.e., if $x_{i}\in
B^{\prime}$, then $x_{i}\in B$.

Suppose the polynomial $p_{a}$ is an element of $B^{\prime}\setminus B$. Thus,
$x_{a-2}\in B\setminus B^{\prime}$ or $x_{a-1}\in B\setminus B^{\prime}$ by
condition (4). The same conclusion can be drawn of $x_{a+1}$ or $x_{a+2}$.
Without loss of generality, there are three cases: $x_{a-2},x_{a+2}\in
B\setminus B^{\prime}$ and $x_{a-1},x_{a+1}\not\in B\setminus B^{\prime}$,
$x_{a-1},x_{a+1}\in B\setminus B^{\prime}$, and $x_{a-1},x_{a+2}\in B\setminus
B^{\prime}$. Suppose, by way of contradiction, that $\Theta_{V}$ does not
contain a set of odd cardinality greater than $1$.

Case $1$: $\\{x_{a-2},x_{a+2}\\}\subset B\setminus B^{\prime}$ and
$x_{a-1},x_{a+1}\not\in B\setminus B^{\prime}$. Since $B^{\prime}$ is an
admissible set, then $x_{a}\in B^{\prime}$, further implying $x_{a}\in B$ by
the above claim. Let $M_{a}$ be the element of $\Theta_{V}$ containing
$x_{a}$. By assumption, $|M_{a}|$ is even. If $M_{a}^{L}$ denotes the subset
of variables in $M_{a}$ with indices less than $a$ and $M_{a}^{R}$ denotes the
subset of variables in $M_{a}$ with indices greater than $a$, then exactly one
of $|M_{a}^{L}|$ and $|M_{a}^{R}|$ is odd. Without loss of generality, suppose
$|M_{a}^{R}|$ is odd, and let $x_{a+2q}$ be the variable of largest index in
$M_{a}$. Clearly $q\geq 1$.

Since $x_{a+2m}\in B$ for all $0\leq m\leq q$, we have that $x_{a+2m+1}\notin
B$ for each $0\leq m\leq q-1$ by condition (4). The above claim gives that
$x_{a+2m+1}\notin B^{\prime}$ for each $0\leq m\leq q-1$. Therefore,
$x_{a+2},x_{a+3}\not\in B^{\prime}$, so $p_{a+4}\in B^{\prime}$ by condition
(4), so $x_{a+6}\not\in B^{\prime}$. Repeating this argument,
$B^{\prime}\setminus B$ contains polynomials $p_{i}$ for
$i\in\\{a,a+4,a+8,\dotsc,a+2(q-1)\\}$, since $|M_{a}^{R}|$ odd implies $q$
odd. Furthermore, $x_{a-2},x_{a+2},x_{a+6},\dotsc,x_{a+2q}\notin B^{\prime}$.
If $a+2(q+1)\leq 2n-1$, then $x_{a+2q}$ being the variable with maximum index
in $M_{a}$ implies $x_{a+2(q+1)}\notin B$. The above claim gives
$x_{a+2(q+1)}\notin B^{\prime}$, and this together with $x_{a+2q}\notin
B^{\prime}$ contradicts condition (1). Therefore, $a+2q=2n+1$. Since
$x_{a+2(q-1)},x_{a+2q}\in B$, then exactly one of $x_{2n}$ and $x_{2n+1}$ are
not in $B$. Without loss of generality, suppose $x_{2n}\notin B$. By the above
claim, we have that $x_{2n}\notin B^{\prime}$. This together with
$x_{a+2q}\notin B^{\prime}$ contradicts condition (3), completing the case.

Case $2$: $\\{x_{a-1},x_{a+1}\\}\subseteq B\setminus B^{\prime}$. By the
definition of an admissible set, we have $x_{a}\notin B$ (as otherwise implies
$x_{a-2}\notin B$ and $x_{a+2}\notin B$, giving that $p_{a}\in B$, a
contradiction). The absence of $x_{a}$ in $B$ further implies that
$x_{a}\notin B^{\prime}$ by the above claim. If $3<a<2n-1$, then
$\\{x_{a-2},x_{a+2}\\}\subseteq B$. If $a=3$ or $a=2n-1$, suppose without loss
of generality that $a=3$, in which case $x_{a+2}\in B$. For any $a$, there
exists $x_{j}$ with $j\in\\{a+2,a-2\\}$ so that $3\leq j\leq 2n-1$ and
$x_{j}\in B$. The presence of $p_{a}\in B^{\prime}$ requires $x_{j}\notin
B^{\prime}$. This together with $x_{a}\notin B^{\prime}$ contradicts the
definition of an admissible set.

Case $3$: Without loss of generality, $\\{x_{a-1},x_{a+2}\\}\subseteq
B\setminus B^{\prime}$. Suppose that $3<a<2n-1$. Since $B^{\prime}$ is an
admissible set, $x_{a+2}\notin B^{\prime}$ implies $x_{a}\in B^{\prime}$, so
$x_{a}\in B$ by the above claim. Furthermore, $\\{x_{a},x_{a-1}\\}\subset B$
implies $x_{a-2}\notin B$, giving that $x_{a-2}\notin B^{\prime}$, again by
the above claim. Let $M_{a}$ be the element of $\Theta_{V}$ containing
$x_{a}$. We have that $x_{a}$ is the variable with smallest index in $M_{a}$,
since $x_{a-2}\notin B$. Let $x_{a+2q}$ be the variable with largest index in
$M_{a}$. Since $|M_{a}|$ is even, we have that $q\geq 1$ is odd. Therefore,
applying the argument from case $1$ completes this case as well.

Since this considers all cases, this completes the proof that, if $V$ is not
maximal, then $B$ contains a maximal odd order collection of monomials with
consecutive indices in $A_{n}^{\prime}$. ∎

Let $\mathcal{J}_{n}$ denote the collection of all ideals in $\mathcal{I}_{n}$
which generate inclusion-maximal irreducible varieties. Furthermore, define
$\mathcal{T}_{n}$ to be the subcollection of
$\bigcup_{S\in\mathcal{F}_{n}}\mathcal{T}_{S}$ containing all admissible sets
which generate ideals in $\mathcal{J}_{n}$. Lastly, define
$\hat{\mathcal{F}}_{n}$ to be the subcollection of $\mathcal{F}_{n}$
containing all Fibonacci subsets of $A_{n}^{\prime}$ which give rise to at
least one admissible set in $\mathcal{T}_{n}$, i.e., subsets $S$ of
$A_{n}^{\prime}=\\{3,5,\ldots,2n-1\\}$ so that at least one of every two
consecutive elements of $A_{n}^{\prime}$ belong to $S$, and so that maximal
intervals of $A_{n}^{\prime}$ contained in $S$ are either a single element or
have even length.

######  Theorem 2.7.

If $\mathcal{H}=P_{n}^{3}$ for some $n\geq 3$, then the null variety $V_{0}$
of $\mathcal{H}$ can be written $\cup_{J\in\mathcal{J}_{n}}\mathcal{V}(J)$,
where $\mathcal{J}_{n}$ is as defined above and each $J\in\mathcal{J}_{n}$ is
an irreducible component of $V_{0}$.

###### Proof.

Recall that the hyperpath $\mathcal{H}$ has exactly $2n+1$ vertices, and we
label them with $\\{v_{1},\ldots,v_{2n+1}\\}$ so that the $j$-th edge is
$e_{j}=\\{v_{2(j-1)+1},\ldots,v_{2j+1}\\}$ for $j=1,\ldots,n$.

In constructing the equations that define $V_{0}$, there are $n-1$ vertices
giving rise to equations of the form $p_{k}=0$, while the other $n+2$ vertices
give equations of the form $x_{i}x_{j}=0$. We begin by considering the variety
defined by all polynomials of the second form. Let $x_{i_{k}}x_{j_{k}}$ for
$1\leq k\leq n+2$ be the $n+2$ polynomials of this form. Then

$\mathcal{V}\left(\\{x_{i_{k}}x_{j_{k}}\\}_{k=1}^{n+2}\right)=\bigcap_{k=1}^{n+2}\mathcal{V}(x_{i_{k}}x_{j_{k}})=\bigcap_{k=1}^{n+2}\left(\mathcal{V}(x_{i_{k}})\cup\mathcal{V}(x_{j_{k}})\right).$

Let $\ell_{k}\in\\{i_{k},j_{k}\\}$ for each $1\leq k\leq n+2$, so that

$\bigcap_{k=1}^{n+2}\left(\mathcal{V}(x_{i_{k}})\cup\mathcal{V}(x_{j_{k}})\right)=\bigcup_{\\{\ell_{k}\\}_{k=1}^{n+2}}\mathcal{V}(\\{x_{\ell_{k}}\\}_{k=1}^{n+2}).$

Let $L$ be the collection of all choices of $\\{\ell_{k}\\}$. To facilitate
analysis of the sets in $L$, we construct a graph $G$, where the vertices of
$G$ are labeled with the distinct $\ell_{k}$, and edges connect $\ell_{k}$ and
$\ell_{k^{\prime}}$ if and only if
$x_{\ell_{k}}x_{\ell_{k^{\prime}}}\in\\{x_{i_{k}}x_{j_{k}}\\}_{k=1}^{n+2}$.
Based on the structure of $\mathcal{H}$ and the vertex labeling given
originally, $G$ has the following form.

$\cdots$$1$$2$$3$$5$$2n+1$$2n$$2n-1$$2n-3$

An element of $L$ corresponds to a set of vertices in $G$ covering $E(G)$,
since the vertices of $G$ are labeled by variable indices, edges are given by
pairs of indices in a term of
$\bigcap_{k=1}^{2n+1}\left(\mathcal{V}(x_{i_{k}})\cup\mathcal{V}(x_{j_{k}})\right)$,
and
$\bigcap_{k=1}^{2n+1}\left(\mathcal{V}(x_{i_{k}})\cup\mathcal{V}(x_{j_{k}})\right)$
is the union of intersections over one term from each element of $L$.

A subset $S$ of vertices in $G$ which is an edge cover must, in particular,
cover the edges $\\{3,5\\},\\{5,7\\},\ldots,\\{2n-3,2n-1\\}$, so no two
consecutive elements of $A_{n}^{\prime}$ are absent from any such set. In
particular, $S\cap A_{n}^{\prime}\in\mathcal{F}_{n}$. Let
$\mathcal{X}_{S}=\\{x_{i}:i\in S\\}$. Since $3\not\in S$ implies $1,2\in S$ so
that $S$ covers the edges $\\{1,3\\}$ and $\\{2,3\\}$, if
$x_{3}\not\in\mathcal{X}_{S}$, then $x_{1},x_{2}\in\mathcal{X}_{S}$.
Similarly, if $x_{2n-1}\not\in\mathcal{X}_{S}$, then
$x_{2n},x_{2n+1}\in\mathcal{X}_{S}$. Note that, for any odd $a$, if

$[(x_{a-2}=0)\vee(x_{a-1}=0)]\wedge[(x_{a+1}=0)\vee(x_{a+2}=0)]$ (1)

then $p_{a}=0$. Then let $P$ be the set of $p_{a}$ so that (1) is not
satisfied, and define $B=\mathcal{X}_{S}\cup P$. Then, for each $i\in
A_{n}^{\prime}$:

  1. 1.

If $i\not\in S$ and $i-4\not\in S$, then $x_{i}\not\in B$, $x_{i-4}\not\in B$,
and $p_{i-2}\in B$.

  2. 2.

If $i\not\in S$ and $i+4\not\in S$, then $x_{i}\not\in B$, $x_{i+4}\not\in B$,
and $p_{i+2}\in B$.

  3. 3.

If $i\not\in S$ and $i-4\in S$, then $x_{i}\not\in B$, $x_{i-4}\in B$, and
$x_{i-1}\in B$.

  4. 4.

If $i\not\in S$ and $i+4\in S$, then $x_{i}\not\in B$, $x_{i+4}\in B$, and
$x_{i+3}\in B$.

  5. 5.

If $5\not\in S$ and $x_{1}\not\in B$, then $p_{3}\in B$.

  6. 6.

If $2n-3\not\in S$ and $x_{2n+1}\not\in B$, then $p_{2n-1}\in B$.

  7. 7.

If $5\in S$ and $x_{1}\notin B$, then $x_{2}\in B$.

  8. 8.

If $5\in S$ and $x_{2}\notin B$, then $x_{1}\in B$.

  9. 9.

If $2n-3\in S$ and $x_{2n}\notin B$, then $x_{2n+1}\in B$.

  10. 10.

If $2n-3\in S$ and $x_{2n+1}\notin B$, then $x_{2n}\in B$.

Let $\mathcal{B}$ be the set of all such $B$ generated by the above
conditions. Then, we have that the null variety of $\mathcal{H}$ is
$\cup_{B\in\mathcal{B}}\mathcal{V}(B)$, and it is easy to see that this is
exactly the same as the construction given by
$\bigcup_{I\in\mathcal{I}_{n}}\mathcal{V}(I)$. Since Lemma 2.4 gives that each
of these ideals are prime, the corresponding varieties are irreducible, giving
that $\bigcup_{I\in\mathcal{I}_{n}}\mathcal{V}(I)$ is a decomposition of
$V_{0}$ into irreducible varieties. Furthermore, Lemma 2.5 determines the
inclusion-maximal varieties under the inclusion relation, implying that
$\cup_{J\in\mathcal{J}_{n}}\mathcal{V}(J)$ is a decomposition of $V_{0}$ into
its irreducible components. ∎

######  Corollary 2.8.

For $n\geq 3$, the null variety $V_{0}$ of $P_{n}^{3}$ has dimension $2\lfloor
n/2\rfloor+1$.

As an illustration of Theorem 2.7, we list all the ideals that generate
irreducible components of $V_{0}$ for $P_{5}^{3}$:

$\begin{array}[]{ccc}\langle
x_{1},x_{2},x_{5},x_{9},p_{5},p_{9}\rangle&\langle
x_{1},x_{2},x_{4},x_{5},x_{7},x_{8},x_{10},x_{11}\rangle&\langle
x_{3},x_{7},x_{10},x_{11},p_{3},p_{7}\rangle\\\ \langle
x_{3},x_{6},x_{7},x_{9},x_{10},p_{3}\rangle&\langle
x_{3},x_{6},x_{7},x_{9},x_{11},p_{3}\rangle&\langle
x_{1},x_{3},x_{5},x_{6},x_{9},p_{9}\rangle\\\ \langle
x_{2},x_{3},x_{5},x_{6},x_{9},p_{9}\rangle&\langle
x_{1},x_{3},x_{5},x_{7},x_{9},x_{10}\rangle&\langle
x_{1},x_{3},x_{5},x_{7},x_{9},x_{11}\rangle\\\ \langle
x_{2},x_{3},x_{5},x_{7},x_{9},x_{10}\rangle&\langle
x_{2},x_{3},x_{5},x_{7},x_{9},x_{11}\rangle&\end{array}$

###  2.3 Enumeration of Components by Dimension

From here we work to determine the quantity of irreducible components of
$V_{0}$ of different dimensions for each $P_{n}^{3}$. Fix an $n$. Let
$B\in\mathcal{T}_{n}$, and let $S$ be such that $S\in\hat{\mathcal{F}}_{n}$
with $B$ an $S$-admissible set. Let $U_{1},U_{2},U_{3},U_{4}$ be given so that
$B=U_{1}\cup U_{2}\cup U_{3}\cup U_{4}$ as in the definition above. Noting
that $|U_{1}|=|S|$, $|U_{2}|=\begin{cases}2&\mbox{if }x_{3}\notin U_{1}\\\
1&\mbox{otherwise}\end{cases}$, $|U_{3}|=\begin{cases}2&\mbox{if
}x_{2n-1}\notin U_{1}\\\ 1&\mbox{otherwise}\end{cases}$, and $|U_{4}|=|\\{a\in
A_{n}:a-2\notin S\mbox{ or }a+2\notin S\\}|$, the following computation gives
an expression for $|B|$.

$\displaystyle|B|$ $\displaystyle=|S|+\begin{cases}2&\mbox{if }x_{3}\notin
U_{1}\\\ 1&\mbox{otherwise}\end{cases}+\begin{cases}2&\mbox{if }x_{2n-1}\notin
U_{1}\\\ 1&\mbox{otherwise}\end{cases}+|\\{a\in A_{n}:a-2\notin S\mbox{ or
}a+2\notin S\\}|$ $\displaystyle=|S|+1_{3\notin S}+1_{2n-1\notin
S}+|(A_{n}^{\prime}-2)\cap\overline{S}|+|(A_{n}^{\prime}+2)\cap\overline{S}|-|(A_{n}^{\prime}-2)\cap(A_{n}^{\prime}+2)\cap\overline{S}|$
$\displaystyle=|S|+1_{3\notin S}+1_{2n-1\notin
S}+|(A_{n}^{\prime}-2)\cap\overline{S}|+|(A_{n}^{\prime}+2)\cap\overline{S}|-|A_{n}\cap\overline{S}|$
$\displaystyle=|S|+1_{3\notin S}+1_{2n-1\notin
S}+|A_{n}^{\prime}|-|(S-2)\cap(S+2)|$ $\displaystyle=|S\cap
A|+n+1-|S\cap(S+4)|$

Additionally, let $\mu_{n}(S)$ denote $|\mathcal{T}_{S}\cap\mathcal{J}_{n}|$,
i.e., the number of irreducible components of $V_{0}$ generated by sets in
$\mathcal{T}_{S}$. It is clear that $\mu_{n}(S)\in\\{1,2,4\\}$. All
irreducible components generated by sets in $\mathcal{T}_{S}$ have dimension
$2n+1-|B|$ for some $B\in\mathcal{T}_{S}$, since the irreducible components
all reside in $\mathbb{C}[x_{1},\dotsc,x_{2n+1}]$, $|B_{1}|=|B_{2}|$ for all
$B_{1},B_{2}\in\mathcal{T}_{S}$, and the sets $B\in\mathcal{T}_{S}$ are
irredundant by Lemma 2.4. Consider the generating function

$\displaystyle g(y,z)$ $\displaystyle=\sum_{n\geq
0}\sum_{S\in\hat{\mathcal{F}}_{n}}y^{|B|}z^{n}.$

Note that $g(y,z)$ does not incorporate the multiplicity $\mu_{n}(S)$. We
first consider the expression given by the inner sum, namely

$g_{n}(y):=\sum_{S\in\hat{\mathcal{F}}_{n}}y^{|B|}$

for a given $n\in\mathbb{N}$. Computation gives the following results for
small values of $n$.

$\displaystyle g_{0}(y)$ $\displaystyle=y$ $\displaystyle g_{1}(y)$
$\displaystyle=y^{2}$ $\displaystyle g_{2}(y)$ $\displaystyle=2y^{3}$

$\displaystyle g_{3}(y)$ $\displaystyle=3y^{4}$ $\displaystyle g_{4}(y)$
$\displaystyle=3y^{6}+y^{4}$ $\displaystyle g_{5}(y)$
$\displaystyle=y^{8}+5y^{6}$

We develop a recurrence for $g_{n}(y)$ aided by two new sequences of
functions, $b_{n}(y)$ and $c_{n}(y)$, defined in the following way:

$\displaystyle b_{n}(y)$
$\displaystyle=\sum_{S\in\hat{\mathcal{F}}_{n},\\{2n-3,2n-1\\}\subseteq
S}y^{|B|}$ $\displaystyle c_{n}(y)$
$\displaystyle=\sum_{S\in\hat{\mathcal{F}}_{n},2n-3\notin S,2n-1\in S}y^{|B|}$

For clarity, we define $b_{0}=b_{1}=b_{2}=c_{0}=c_{1}=c_{2}=0$. Otherwise, we
have the following small values of the two new sequences.

$\displaystyle b_{3}(y)$ $\displaystyle=y^{4}$ $\displaystyle b_{4}(y)$
$\displaystyle=y^{6}$ $\displaystyle b_{5}(y)$ $\displaystyle=2y^{6}$

$\displaystyle c_{3}(y)$ $\displaystyle=y^{4}$ $\displaystyle c_{4}(y)$
$\displaystyle=y^{4}$ $\displaystyle c_{5}(y)$ $\displaystyle=2y^{6}$

Note that, for each $S$ a Fibonacci subset of $A_{n}^{\prime}$, at least one
of $2n-3$ and $2n-1$ are included in $S$, so there are three options for
$\\{2n-1,2n-3\\}\cap S$. All three can be expressed in terms of $b_{n}$,
$c_{n}$, and $g_{n}$. A straightforward (if laborious) case analysis provides
the following recurrences for the three sequences of functions. Note that
these recurrences are valid only for $n\geq 5$.

$\displaystyle g_{n}(y)$
$\displaystyle=2y^{2}g_{n-2}(y)+y^{4}b_{n-3}(y)+y^{2}(y^{2}-1)c_{n-2}(y)$ (2)
$\displaystyle b_{n}(y)$ $\displaystyle=y^{2}g_{n-2}(y)-y^{2}c_{n-2}(y)$
$\displaystyle c_{n}(y)$ $\displaystyle=y^{2}b_{n-2}(y)+y^{2}c_{n-2}(y)$

Recall that $g(y,z)$ is the generating function for $g_{n}(y)$. Analogously,
let $b(y,z)=\sum_{n\geq 0}b_{n}(y)z^{n}$ and $c(y,z)=\sum_{n\geq
0}c_{n}(y)z^{n}$. The following computations work towards closed forms for
$b$, $c$, and $g$.

$\displaystyle g$ $\displaystyle=\sum_{n=0}^{4}g_{n}z^{n}+2y^{2}\sum_{n\geq
5}g_{n-2}z^{n}+y^{4}\sum_{n\geq 5}b_{n-3}z^{n}+y^{2}(y^{2}-1)\sum_{n\geq
5}c_{n-2}z^{n}$
$\displaystyle=\sum_{n=0}^{4}g_{n}z^{n}+2y^{2}z^{2}(g-\sum_{n=0}^{2}g_{n}z^{n})+y^{4}z^{3}b+y^{2}(y^{2}-1)z^{2}c$
$\displaystyle g$
$\displaystyle=\frac{3y^{6}z^{4}-4y^{5}z^{4}+y^{4}z^{4}+y^{4}z^{3}+y^{2}z+y+y^{4}z^{3}b+y^{2}(y^{2}-1)z^{2}c}{1-2y^{2}z^{2}}$
$\displaystyle b$ $\displaystyle=\sum_{n=0}^{4}b_{n}z^{n}+y^{2}\sum_{n\geq
5}g_{n-2}z^{n}-y^{2}\sum_{n\geq
5}c_{n-2}z^{n}=\sum_{n=0}^{4}b_{n}z^{n}+y^{2}z^{2}(g-\sum_{n=0}^{2}g_{n}z^{n})-y^{2}z^{2}c$
$\displaystyle=y^{6}z^{4}-2y^{5}z^{4}-y^{3}z^{2}+y^{2}z^{2}g-y^{2}z^{2}c$
$\displaystyle c$ $\displaystyle=\sum_{n=0}^{4}c_{n}z^{n}+y^{2}\sum_{n\geq
5}b_{n-2}z^{n}+y^{2}\sum_{n\geq
5}c_{n-2}z^{n}=\sum_{n=0}^{4}c_{n}z^{n}+y^{2}z^{2}b+y^{2}z^{2}c$
$\displaystyle c$
$\displaystyle=\frac{y^{4}z^{4}+y^{4}z^{3}+y^{2}z^{2}b}{1-y^{2}z^{2}}$

Solving the system for $g$ gives the following.

$g=-\frac{{\left(y^{8}-2\,y^{7}+y^{6}\right)}z^{6}-{\left(y^{8}-2\,y^{7}\right)}z^{5}-{\left(2\,y^{6}-3\,y^{5}+y^{4}\right)}z^{4}+{\left(y^{5}-y^{4}\right)}z^{3}-y^{2}z-y}{y^{4}z^{4}-y^{4}z^{3}-2\,y^{2}z^{2}+1}$

Recall that the exponent on $y$ in $g(y,z)$ is the co-dimension of the
irreducible component of $V_{0}$ for $P_{n}^{3}$. Since we are interested in
the dimension of these components, we make the following transformation. The
dimension of each component is $2n+1$ minus its co-dimension. Thus, the
function we want is given by $h(y,z)=y\cdot g(1/y,y^{2}z)$, expressible as
follows (computations throughout performed by SageMath [12]).

$\displaystyle
h=\frac{-y^{7}z^{6}+2y^{6}z^{6}-y^{5}z^{6}+y^{5}z^{4}-2y^{4}z^{5}-3y^{4}z^{4}+y^{3}z^{5}+2y^{3}z^{4}+y^{3}z^{3}-y^{2}z^{3}+yz+1}{y^{4}z^{4}-y^{2}z^{3}-2y^{2}z^{2}+1}$

To help later with verifying Conjecture 1.1, differentiating with respect to
$y$ gives the following expression and then plugging in $y=2$, because

$H(z):=\left.\frac{\partial}{\partial y}h(y,z)\right|_{y=2}=\sum_{n\geq
0}\sum_{S\in\hat{\mathcal{F}}_{n}}(\dim\mathcal{V}(B))2^{\dim\mathcal{V}(B)-1}z^{n}.$

The generating function obtained in this way encodes a lower bound on
$\operatorname{gm}(0)$ of the conjecture, but four times this function is an
upper bound. We get the following expression when substituting $y=2$:

$\displaystyle\frac{-1280z^{10}+384z^{9}+1136z^{8}+192z^{7}-224z^{6}-132z^{5}-20z^{4}+20z^{3}+8z^{2}+z}{256z^{8}-128z^{7}-240z^{6}+64z^{5}+96z^{4}-8z^{3}-16z^{2}+1}$
$\displaystyle\hskip
72.26999pt=z+8z^{2}+36z^{3}+116z^{4}+412z^{5}+1088z^{6}+\cdots$

The smallest-magnitude root of the denominator lies in the interval
$(0.37,0.371)$. This implies that the coefficients of $H(z)$ have growth rate
in the interval $(2.69,2.71)$. We upper-bound the coefficients
$\\{\eta_{n}\\}_{n\geq 0}$ of $H(z)$. Recall that Corollary 2.8 gives that the
maximum dimension of an irreducible component of $V_{0}$ for $P_{n}^{3}$ is
$2\lfloor n/2\rfloor+1$. Since we counted at most one component for each
Fibonacci subset of $A_{n}^{\prime}$, there are at most $F_{n}$ (the $n$-th
Fibonacci number) terms which contribute to $\eta_{n}$. Therefore, $\eta_{n}$
is bounded above in the following way, given that $\phi=(1+\sqrt{5})/2$:

$\eta_{n}\leq\frac{\phi^{n}-(-\phi)^{-n}}{\sqrt{5}}\cdot(n+1)\cdot 2^{n}$

###  2.4 Incorporating Multiplicity

Recall that $\mu_{n}(S)\in\\{1,2,4\\}$ for $S\in\hat{\mathcal{F}}_{n}$, but
the above sums ignore this factor. Note that $\mu_{n}(S)>1$ when either pair
$\\{3,5\\}$ or $\\{2n-3,2n-1\\}$ are subsets of $S$. The sequence $b_{n}$
given above accounts for the subcollection of $\hat{\mathcal{F}}_{n}$
containing both $2n-3$ and $2n-1$, so $b$ is the generating function where the
$y^{m}z^{n}$ coefficient counts the number of irreducible components of
codimension $m$ from a hyperpath of length $n$ generated from a given $S$
containing both $2n-3$ and $2n-1$. By the symmetry of these Fibonacci subsets,
the coefficients of $b$ also count the same quantity, where now the Fibonacci
set $S$ contains both $3$ and $5$. So, $2b$ counts the $\\{3,5\\}\subseteq S$
and $\\{2n-3,2n-1\\}\not\subseteq S$ components once, the
$\\{2n-3,2n-1\\}\subseteq S$ and $\\{3,5\\}\not\subseteq S$ components once,
and the $\\{3,5,2n-3,2n-1\\}\subseteq S$ components twice. It only remains to
count the $\\{3,5,2n-3,2n-1\\}\subseteq S$ components one additional time.

We now define $g_{n}^{\prime}$, $b_{n}^{\prime}$, and $c_{n}^{\prime}$ to have
the same conditions on the presence of $2n-3$ and $2n-1$ in $S$ as was given
for $g_{n}$, $b_{n}$, and $c_{n}$ above, but now we require that $3$ and $5$
be in $S$, i.e.,

$g^{\prime}_{n}(y):=\sum_{\begin{subarray}{c}S\in\hat{\mathcal{F}}_{n}\\\
3,5\in S\end{subarray}}y^{|B|}$

and analogously for $b^{\prime}_{n}$ and $c^{\prime}_{n}$. We define all three
sequences for $n\geq 0$, although some initial values are zero. These modified
sequences satisfy the exact same recurrences as displayed in (2) for $n\geq
5$.

Let $g^{\prime}$, $b^{\prime}$, and $c^{\prime}$ be the generating functions
with respect to the variable $z$ for the three sequences defined. Then, the
generating function $b^{\prime}$ counts exactly the
$\\{3,5,2n-3,2n-1\\}\subseteq S$ components once. Computation gives the
following rational expression for $g^{\prime}$ and $b^{\prime}$:

$\displaystyle g^{\prime}$
$\displaystyle=\frac{y^{6}z^{4}+y^{4}z^{3}}{y^{4}z^{4}-y^{4}z^{3}-2\,y^{2}z^{2}+1}$
$\displaystyle b^{\prime}$
$\displaystyle=-\frac{y^{6}z^{5}-y^{4}z^{3}}{y^{4}z^{4}-y^{4}z^{3}-2\,y^{2}z^{2}+1}$

Note that the generating function for $g^{\prime}$ counts the same irreducible
components as $b$ from above. Therefore, the generating function of
$\operatorname{gm}(0)$, which incorporates multiplicity (aside from some
initial terms), is given by $G=g+2g^{\prime}+b^{\prime}$, and is given by the
following rational function.

$\displaystyle G$
$\displaystyle=\left(-y^{8}z^{6}+y^{8}z^{5}+2y^{7}z^{6}-2y^{7}z^{5}-y^{6}z^{6}-y^{6}z^{5}+4y^{6}z^{4}-3y^{5}z^{4}-y^{5}z^{3}+y^{4}z^{4}\right.$
$\displaystyle\hskip
72.26999pt\left.+\,4y^{4}z^{3}+y^{2}z+y\right)/(y^{4}z^{4}-y^{4}z^{3}-2y^{2}z^{2}+1)$

Similarly to the previous subsection, we compute $h^{\prime}=y\cdot
G(1/y,y^{2}z)$, which is the generating function for the number of irreducible
components of dimension given by the exponent on $y$ in $V_{0}$ for
$P_{n}^{3}$, if $n$ is the exponent on $z$.

$\displaystyle h^{\prime}$
$\displaystyle=\left(-y^{7}z^{6}+2y^{6}z^{6}-y^{5}z^{6}-y^{5}z^{5}+y^{5}z^{4}-2y^{4}z^{5}-3y^{4}z^{4}+y^{3}z^{5}\right.$
$\displaystyle\hskip
72.26999pt\left.+\,4y^{3}z^{4}+4y^{3}z^{3}-y^{2}z^{3}+yz+1\right)/(y^{4}z^{4}-y^{2}z^{3}-2y^{2}z^{2}+1).$

Computing $\left.\frac{\partial}{\partial y}h^{\prime}(y,z)\right|_{y=2}$
yields the following generating function:

$\displaystyle\frac{-1280z^{10}+128z^{9}+1200z^{8}+352z^{7}-336z^{6}-308z^{5}+4z^{4}+56z^{3}+8z^{2}+z}{256z^{8}-128z^{7}-240z^{6}+64z^{5}+96z^{4}-8z^{3}-16z^{2}+1}$
$\displaystyle=z+8z^{2}+72z^{3}+140z^{4}+812z^{5}+1648z^{6}+7280z^{7}$
$\displaystyle\qquad+18064z^{8}+60928z^{9}+176576z^{10}+\cdots$

Here the linear and quadratic coefficients are incorrect, however, because
incorporation of multiplicity only adjusts for $n\geq 3$. Modifying this
expression via Propositions 2.1 and 2.2, we obtain

$\displaystyle H^{\prime}(z)$
$\displaystyle=\frac{-256z^{8}+192z^{7}+272z^{6}-156z^{5}-92z^{4}+24z^{3}+13z^{2}+3z}{256z^{8}-128z^{7}-240z^{6}+64z^{5}+96z^{4}-8z^{3}-16z^{2}+1}$
$\displaystyle=3z+13z^{2}+72z^{3}+140z^{4}+812z^{5}+1648z^{6}+7280z^{7}$
$\displaystyle\qquad+18064z^{8}+60928z^{9}+176576z^{10}+\cdots$

##  3 Algebraic Multiplicity of Zero

Let $D_{n,k}$ be the algebraic multiplicity of zero in the characteristic
polynomial of $\phi_{P_{n}^{k}}(\lambda)$ (the $k$-uniform linear hyperpath
with $n$ edges). We are given the following by the paper of Bao, Fan, Wang,
and Zhu.

######  Theorem 3.1 ([1]).

For $n\geq 2$,

$\phi_{P_{n}^{k}}(\lambda)=\lambda^{(k-2)(k-1)^{n(k-1)}}\prod_{s=0}^{n}\left(\lambda-\frac{f^{s-1}(1)}{\lambda^{k-1}}\right)^{\nu_{n,k}(s)}\phi_{P_{n-1}^{k}}(\lambda)^{(k-1)^{k-1}},$

where

$\nu_{n,k}(s)=\begin{cases}k^{s(k-2)}((k-1)^{k-1}-k^{k-2})(k-1)^{(n-s-1)(k-1)}&\mbox{if
}s\in[0,n-1],\\\ k^{s(k-2)}&\mbox{if }s=n,\\\ \end{cases}$

and

$f^{i}(x)=\begin{cases}0&\mbox{if }i=-1,\\\ 1&\mbox{if }i=0,\\\
f(x)=\frac{1}{1-x\lambda^{-k}}=\frac{\lambda^{k}}{\lambda^{k}-x}&\mbox{if
}i=1,\\\ f^{i-1}(f(x))&\mbox{if }i>1.\end{cases}$

We use these facts to prove the following. We start by proving the following
lemma concerning the degree of the zero root in $f(x)$.

######  Lemma 3.2.

Let $k\geq 2$ be given. Let $d_{s}$ be the degree of the zero root in the
rational function $f^{s}(1)$. If $s\geq 1$, then $d_{s}=0$ if $s$ is even and
$d_{s}=k$ if $s$ is odd.

###### Proof.

We proceed by induction on $s$, with the base cases given by $s=1$ and $s=2$.
The definition of $f^{s}(x)$ includes that
$f(1)=\frac{\lambda^{k}}{\lambda^{k}-1}$, giving that $d_{1}=k$. For $s=2$,
then,

$f^{2}(1)=f(f(1))=f\left(\frac{\lambda^{k}}{\lambda^{k}-1}\right)=\frac{\lambda^{k}-1}{\lambda^{k}-2}.$

Now suppose that the result holds for some $s\geq 1$. Consider the value of
$d_{s+1}$. Since composition of functions is associative,
$f^{s+1}(1)=f^{s}(f(1))=f(f^{s}(1))$. Let $q^{s}(x)$ denote the denominator of
$f^{s}(x)$. Since $f(x)=\frac{\lambda^{k}}{\lambda^{k}-x}$, we can think of
$f^{s+1}(1)$ as $\lambda^{k}q^{s}(1)$ divided by $\lambda^{k}q^{s}(1)$ minus
the numerator of $f^{s}(1)$.

If $f^{s}(1)$ is rational in $\lambda$ with $d_{s}=0$, then the denominator of
$f^{s+1}(1)$ will not be divisible by $\lambda$, but the degree of $\lambda$
in the numerator is $k$. Thus $d_{s+1}=k$. On the other hand, if $d_{s}=k$,
then $f^{s}(1)$ is rational in $\lambda$ with the power of $\lambda$ in the
numerator equal to $k$. Then, $f^{s+1}(1)$ will have $k$ factors of $\lambda$
in the numerator after multiplying through by $q^{s}(1)$, but the denominator
is the difference of two polynomials both of which have $\lambda$ occurring
$k$ times as a factor. Factor out the term $\lambda^{k}$ from the denominator
and cancel it within $f^{s+1}(1)$. This leaves zero factors of $\lambda$ in
the numerator. In the denominator, we have zero factors of $\lambda$ if and
only if the constant term in $q^{s}(1)$ differs from the coefficient of
$\lambda^{k}$ in the numerator of $f^{s}(1)$. This inequality of coefficients
is established by the following inductive argument, which need only handle the
case of $s$ odd. In fact, we include in the inductive hypothesis as well that
the numerator and denominator have no nonzero coefficients of terms of the
form $\lambda^{j}$ with $0<j<k$.

By definition, $f(1)=\frac{\lambda^{k}}{\lambda^{k}-1}$, so the constant term
in the denominator (namely, $-1$) and the coefficient of $\lambda^{k}$
(namely, $1$) in the numerator differ, giving the base case. Suppose now that
the result holds for some odd $i\geq 1$. Let $f^{s}(1)$ have numerator
$\alpha(\lambda)+\alpha_{1}\lambda^{k}$ and denominator
$\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}$, where $\alpha$ and $\beta$
are both polynomials of degree greater than $k$, and
$\alpha_{1}\neq\beta_{2}$. Then, we have the following.

$\displaystyle f^{s+2}(1)$ $\displaystyle=f\circ
f\left(\frac{\alpha(\lambda)+\alpha_{1}\lambda^{k}}{\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}}\right)$
$\displaystyle=f\left(\frac{\lambda^{k}}{\lambda^{k}-\frac{\alpha(\lambda)+\alpha_{1}\lambda^{k}}{\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}}}\right)$
$\displaystyle=f\left(\frac{\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}}{\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}-\alpha(\lambda)\lambda^{-k}-\alpha_{1}}\right)$
$\displaystyle=\frac{\lambda^{k}}{\lambda^{k}-\left(\frac{\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}}{\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}-\alpha(\lambda)\lambda^{-k}-\alpha_{1}}\right)}$
$\displaystyle=\frac{\lambda^{k}(\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}-\alpha(\lambda)\lambda^{-k}-\alpha_{1})}{\lambda^{k}(\beta(\lambda)+\beta_{1}\lambda^{k}+\beta_{2}-\alpha(\lambda)\lambda^{-k}+\alpha_{1})-\beta(\lambda)-\beta_{1}\lambda^{k}-\beta_{2}}$

From this, we see that the coefficient of $\lambda^{k}$ in the numerator is
$\beta_{2}-\alpha_{1}$, and the constant term in the denominator is
$-\beta_{2}$. Since $\alpha_{1}=1$ and $\beta_{2}=-1$ in $f(1)$, we have that
the constant term in the denominator flips back and forth between $-1$ and $1$
as the powers of $f$ increase by two. On the other hand,
$\beta_{2}-\alpha_{1}$ takes values of the form $(-1)^{(s-1)/2}\cdot(s-1)/2$
for odd $s\geq 1$. Then the two desired coefficients are never equal,
completing the proof. ∎

######  Corollary 3.3.

The multiplicity of the zero root of $\lambda^{k}-f^{s}(1)$ is the same as the
multiplicity of zero in $f^{s}(1)$.

###### Proof.

The even case is trivial, because both multiplicities are zero. In the odd
case, the ratio of the coefficient of $\lambda^{k}$ in the numerator of
$f^{s}(1)$ divided by the constant coefficient in the denominator has absolute
value less than $1$ except when $s=1$. However, in that case
$\lambda^{k}-f(1)=\lambda^{k}-\frac{\lambda^{k}}{\lambda^{k}-1}=\frac{\lambda^{2k}-2\lambda^{k}}{\lambda^{k}-1}$.
∎

We now use the preceding lemma and corollary to fully describe the nullity of
$P_{n}^{k}$.

######  Theorem 3.4.

Let $k\geq 1$ and $n\geq 1$. Additionally, let $u=(k-1)^{k-1}$ and
$v=k^{k-2}$. If $D_{n,k}$ denotes the multiplicity of $\lambda$ in the
$k$-uniform hyperpath characteristic polynomial $\phi_{P_{n}^{k}}(\lambda)$,
then

$D_{n,k}=\frac{u^{n}\left([nk-n+1]u^{2}+[nk-2n+2]uv-[k+n-1]v^{2}\right)+k(-v)^{n+2}}{(u+v)^{2}}_{.}$

###### Proof.

We first separate the $n=1$ case. Cooper and Dutle [3] showed that
$D_{1,k}=k(k-1)^{k-1}-k^{k-1}=k(u-v)$. Plugging $n=1$ into the suggested
formula gives the same expression, verifying the result for the base case.
Suppose now that $n\geq 2$. From Theorem 3.1, we have

$\phi_{P_{n}^{k}}(\lambda)=\lambda^{(k-2)(k-1)^{n(k-1)}}\prod_{s=0}^{n}\left(\lambda-\frac{f^{s-1}(1)}{\lambda^{k-1}}\right)^{\nu_{n,k}(s)}\phi_{P_{n-1}^{k}}(\lambda)^{(k-1)^{k-1}},$
(3)

so we develop a recurrence that gives $D_{n,k}$ knowing $D_{n-1,k}$. From the
preceding formula, we see

$D_{n,k}=(k-2)u^{n}+u\cdot D_{n-1,k}+F_{n,k},$

where we define $F_{n,k}$ to be the multiplicity of the zero root in the
simplified rational function
$\prod_{s=0}^{n}\left(\lambda-\frac{f^{s-1}(1)}{\lambda^{k-1}}\right)^{\nu_{n,k}(s)}$
(taking the parameter to be negative if there are excess powers of $\lambda$
in the denominator). As above, let $d_{s}$ be the multiplicity of the zero
root in $f^{s}(1)$. By Lemma 3.2, we have that $d_{s-1}$ is zero when $s-1$ is
even, and $d_{s-1}=k$ when $s-1$ is odd. Since the $s$-th term of the product
in (3) is $[\lambda^{-(k-1)}(\lambda^{k}-f^{s-1}(1))]^{\nu_{n,k}(s)}$, and
Corollary 3.3 gives that the degree of the zero root in $f^{s-1}(1)$ and
$\lambda^{k}-f^{s-1}(1)$ are the same, we have

$F_{n,k}=-(k-1)\sum_{s=0}^{n}\nu_{n,k}(s)+\sum_{s=0}^{n}\nu_{n,k}(s)\cdot
d_{s-1}.$

We start by considering the value of the first term above. We have the
following.

$\displaystyle\sum_{s=0}^{n}\nu_{n,k}(s)$
$\displaystyle=\nu_{n,k}(n)+\sum_{s=0}^{n-1}\nu_{n,k}(s)$
$\displaystyle=v^{n}+\sum_{s=0}^{n-1}v^{s}(u-v)u^{n-s-1}$
$\displaystyle=v^{n}+(u-v)u^{n-1}\frac{1-\left(\frac{v}{u}\right)^{n}}{1-\frac{v}{u}}$
$\displaystyle=u^{n}$

When considering the second summand in the expression for $F_{n,k}$, we split
into cases initially based on the parity of $n$. Starting with $n$ odd, we
have the following simplification of $\sum_{s=0}^{n}\nu_{n,k}(s)\cdot
d_{s-1}$:

$\displaystyle\sum_{s=0}^{n}\nu_{n,k}(s)\cdot d_{s-1}$
$\displaystyle=\sum_{s=0}^{(n-1)/2}\nu_{n,k}(2s)\cdot k$
$\displaystyle=k\cdot\sum_{s=0}^{(n-1)/2}v^{2s}(u-v)u^{n-1-2s}$
$\displaystyle=k(u-v)u^{n-1}\frac{1-\left(\frac{v^{2}}{u^{2}}\right)^{(n+1)/2}}{1-\frac{v^{2}}{u^{2}}}$
$\displaystyle=\left(\frac{k}{u+v}\right)(u^{n+1}-v^{n+1})$

On the other hand, if $n$ is even, we have the following.

$\displaystyle\sum_{s=0}^{n}\nu_{n,k}(s)\cdot d_{s-1}$
$\displaystyle=\sum_{s=0}^{n/2}\nu_{n,k}(2s)\cdot k$ $\displaystyle=k\cdot
v^{n}+k\cdot\sum_{s=0}^{(n-2)/2}v^{2s}(u-v)u^{n-1-2s}$ $\displaystyle=k\cdot
v^{n}+k(u-v)u^{n-1}\frac{1-\left(\frac{v^{2}}{u^{2}}\right)^{(n)/2}}{1-\frac{v^{2}}{u^{2}}}$
$\displaystyle=\left(\frac{k}{u+v}\right)(u^{n+1}+v^{n+1})$

Thus, for general $n$, we have

$\sum_{s=0}^{n}\nu_{n,k}(s)\cdot
d_{s-1}=\left(\frac{k}{u+v}\right)(u^{n+1}-(-v)^{n+1}).$

This gives the following closed form for $F_{n,k}$.

$F_{n,k}=-(k-1)u^{n}+\left(\frac{k}{u+v}\right)(u^{n+1}-(-v)^{n+1})$

Substituting this back into the original expression for $D_{n,k}$, we have the
following simplification.

$\displaystyle D_{n,k}$ $\displaystyle=(k-2)u^{n}+u\cdot D_{n-1,k}+F_{n,k}$
$\displaystyle=(k-2)u^{n}+uD_{n-1,k}-(k-1)u^{n}+\left(\frac{k}{u+v}\right)(u^{n+1}-(-v)^{n+1})$
$\displaystyle=uD_{n-1,k}+\frac{u^{n}[(k-1)u-v]-k(-v)^{n+1}}{u+v}$

For $n=1$, we noted earlier that $D_{1,k}=k(u-v)$. We continue with the
following, completing the proof.

$\displaystyle D_{n,k}$
$\displaystyle=ku^{n-1}(u-v)+\frac{u^{n}[(k-1)u-v]-k(-v)^{n+1}}{u+v}+\sum_{i=1}^{n-2}u^{i}\frac{u^{n-i}[(k-1)u-v]-k(-v)^{n-i+1}}{u+v}$
$\displaystyle=ku^{n-1}(u-v)+\sum_{i=0}^{n-2}u^{i}\frac{u^{n-i}[(k-1)u-v]-k(-v)^{n-i+1}}{u+v}$
$\displaystyle=ku^{n-1}(u-v)+\sum_{i=0}^{n-2}\frac{u^{n}[(k-1)u-v]}{u+v}-\sum_{i=0}^{n-2}\frac{ku^{i}(-v)^{n+1-i}}{u+v}$
$\displaystyle=ku^{n-1}(u-v)+\frac{u^{n}(n-1)[(k-1)u-v]}{u+v}-\frac{k(-v)^{n+1}}{u+v}\cdot\frac{1-\left(\frac{u}{-v}\right)^{n-1}}{1-\frac{u}{-v}}$
$\displaystyle=\frac{u^{n}([nk-n+1]u^{2}+[nk-2n+2]uv-[k+n-1]v^{2})+k(-v)^{n+2}}{(u+v)^{2}}.$

∎

The next result applies the above theorem to obtain an asymptotic expression
for $D_{n,k}$.

######  Corollary 3.5.

Let $k\geq 3$ be fixed and $n\geq 1$. Then
$\lim_{n\to\infty}\frac{D_{n,k}}{n(k-1)^{n(k-1)+1}}=1$. In particular, the
fraction of eigenvalues of $P_{n}^{k}$ which are zero approaches $1/(k-1)$ as
$n\rightarrow\infty$.

###### Proof.

We have the following expression for $D_{n,k}$, where $u=(k-1)^{k-1}$ and
$v=k^{k-2}$:

$D_{n,k}=\frac{u^{n}\left([nk-n+1]u^{2}+[nk-2n+2]uv-[k+n-1]v^{2}\right)+k(-v)^{n+2}}{(u+v)^{2}}$

Noting that $k\geq 2$, we first show that $u>v$. We have the following
computation.

$\frac{u}{v}=\frac{(k-1)^{k-1}}{k^{k-2}}=\frac{k^{2}}{k-1}\left(1-\frac{1}{k}\right)^{k}\geq\frac{k^{2}}{k-1}\cdot\frac{1}{4}=\frac{k^{2}}{4k-4}.$

Note that for $k\geq 2$, the function $\left(\frac{k-1}{k}\right)^{k}$ is
increasing, so its value for any $k\geq 2$ is bounded below by its value when
$k=2$, namely, $1/4$. Furthermore, the rightmost expression is greater than
one if and only if $k^{2}\geq 4k-4$, which is true because $(k-2)^{2}\geq 0$.
Therefore, $u>v$, so $u$ dominates $v$ asymptotically. Then the rational
expression is asymptotically the same as a ratio of two polynomials just in
the variable $u$, from which it follows that

$\lim_{n\to\infty}\frac{D_{n,k}}{[n(k-1)+1]u^{n}}=1.$

Since $k$ is constant, this gives the desired result. The second claim in the
proof follows because (see [10]) the total number of eigenvalues (counted with
algebraic multiplicity) is $N(k-1)^{N}$, where $N$ is the number of vertices;
in this case, $N=n(k-1)+1$ and, as $n\rightarrow\infty$,

$\frac{n(k-1)^{n(k-1)+1}}{(n(k-1)+1)(k-1)^{n(k-1)+1}}\sim\frac{n(k-1)^{n(k-1)+1}}{n(k-1)^{n(k-1)+2}}=\frac{1}{k-1}.$

∎

From this, we observe the following lower bound for $D_{n,3}$ when $n\geq 12$.

$D_{n,3}\geq\frac{4^{n}}{7}(5n+3)$

##  4 Conjecture Verification

######  Theorem 4.1.

Let $V_{0}^{1},\dotsc,V_{0}^{\kappa}$ denote the irreducible components of
$V_{0}$ for $P_{n}^{3}$. For $n\geq 1$,
$D_{n,3}\geq\sum_{i=1}^{\kappa}\dim(V_{0}^{i})(2)^{\dim(V_{0}^{i})-1}$.

###### Proof.

Recall the following bounds on $D_{n,3}$ and $\eta_{n}$, where $\eta_{n}$ is
the $z^{n}$ coefficient of the generating function $H(z)$ found in Section 2.

$\displaystyle D_{n,3}$ $\displaystyle\geq\frac{4^{n}}{7}(5n+3)$
$\displaystyle\eta_{n}$
$\displaystyle\leq\frac{\phi^{n}-(-\phi)^{-n}}{\sqrt{5}}\cdot(n+1)\cdot 2^{n}$

It is easy to check that $4(\phi^{n}+1)\leq 2^{n}$ for any $n\geq 7$.
Furthermore,

$2^{n}\leq\frac{4\sqrt{5}}{7}\cdot 2^{n}\leq\frac{\sqrt{5}}{7}\cdot
2^{n}\cdot\frac{5n+3}{n+1}$ $4(\phi^{n}+1)\geq 4(\phi^{n}-(-\phi)^{-n})$

Combining the inequalities shows that $D_{n,3}\geq 4\eta_{n}$ for $n\geq 12$:

$\displaystyle 4(\phi^{n}-(-\phi)^{-n})$
$\displaystyle\leq\frac{\sqrt{5}}{7}\cdot 2^{n}\cdot\frac{5n+3}{n+1}$
$\displaystyle 4\cdot\frac{\phi^{n}-(-\phi)^{-n}}{\sqrt{5}}\cdot(n+1)$
$\displaystyle\leq\frac{2^{n}}{7}\cdot(5n+3)$ $\displaystyle
4\cdot\frac{\phi^{n}-(-\phi)^{-n}}{\sqrt{5}}\cdot(n+1)\cdot 2^{n}$
$\displaystyle\leq\frac{4^{n}}{7}\cdot(5n+3)$

Therefore, this gives us that the conjecture holds for $n\geq 12$, since
$\operatorname{gm}(0)\leq 4\eta_{n}$. The following table computes values for
$n<12$ exactly, completing the proof.

n | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$
---|---|---|---|---|---|---|---|---|---|---|---
$D_{n,3}$ | $3$ | $35$ | $151$ | $891$ | $3983$ | $19795$ | $88071$ | $407531$ | $1792063$ | $7993155$ | $34740791$
$\operatorname{gm}(0)$ | $3$ | $13$ | $72$ | $140$ | $812$ | $1648$ | $7280$ | $18064$ | $60928$ | $176576$ | $509376$

∎

##  5 Conclusion

We have shown how to compute the multiplicities of the zero eigenvalue of
linear hyperpaths of rank $3$ and the dimensions of the irreducible components
of the corresponding nullvarieties. This enables us to compute
$\operatorname{gm}(0)$ and $\operatorname{am}(0)$ so that they can be compared
in order to verify the Hu-Ye conjecture in this special case. The above
analysis can be extended by straightforward generalization to higher rank
hyperpaths. Furthermore, some of the issues encountered in carrying out this
analysis invite new questions:

  1. 1.

In general, linear hypertrees have many of the properties taken advantage of
above for hyperpaths. Therefore, we ask: can these methods be used to answer
Conjecture 1.1 for this much more general class of hypergraphs?

  2. 2.

The set of vertices/coordinates where hypergraphs’ nullvectors are zero is
combinatorially interesting and plays an integral role in our classification
of irreducible components. For example, it is not hard to see that these
vertex sets are transversals of the hypergraph’s edge set when it is any
hypertree. What is possible to say in general about these sets and their
relation to the nullvariety’s components?

  3. 3.

We have made no attempt to understand eigenvarieties corresponding to nonzero
eigenvalues $\lambda$, nor have we attempted to compute their algebraic
multiplicities. Doing so would require answering: what are the rest of the
root multiplicities of the characteristic polynomials of linear hyperpaths,
and how does the structure of non-zero eigenvarieties differ from the
nullvariety?

  4. 4.

Is Conjecture 1.1 tight? The quantity proposed for
$\operatorname{gm}(\lambda)$ is perhaps not the maximum function of the
multiset of eigenvariety component dimensions which still provides a lower
bound on $\operatorname{am}(\lambda)$.

##  6 Acknowledgement

The authors wish to thank Fan Chung for so much of the inspiration that paved
the road to this subject, and to the organizers of the December 2019 TSIMF
conference for creating the occasion to honor her and continue her work.

## References

  * [1] Yan-Hong Bao, Yi-Zheng Fan, Yi Wang, and Ming Zhu.  A combinatorial method for computing characteristic polynomials of starlike hypergraphs.  J. Algebraic Combin., 51(4):589–616, 2020.
  * [2] Gregory J. Clark and Joshua N. Cooper.  On the adjacency spectra of hypertrees.  Electron. J. Combin., 25(2):Paper No. 2.48, 8, 2018.
  * [3] Joshua Cooper and Aaron Dutle.  Spectra of uniform hypergraphs.  Linear Algebra Appl., 436(9):3268–3292, 2012.
  * [4] Dragoš M. Cvetković and Ivan M. Gutman.  The algebraic multiplicity of the number zero in the spectrum of a bipartite graph.  Mat. Vesnik, 9(24):141–150, 1972.
  * [5] Yi-Zheng Fan, Yan-Hong Bao, and Tao Huang.  Eigenvariety of nonnegative symmetric weakly irreducible tensors associated with spectral radius and its application to hypergraphs.  Linear Algebra Appl., 564:72–94, 2019.
  * [6] Stanley Fiorini, Ivan Gutman, and Irene Sciriha.  Trees with maximum nullity.  Linear Algebra Appl., 397:245–251, 2005.
  * [7] Ivan Gutman and Bojana Borovićanin.  Nullity of graphs: an updated survey.  Zb. Rad. (Beogr.), 14(22)(Selected topics on applications of graph spectra):137–154, 2011.
  * [8] Shenglong Hu and Ke Ye.  Multiplicities of tensor eigenvalues.  Commun. Math. Sci., 14(4):1049–1071, 2016.
  * [9] James S. Milne.  Algebraic geometry (v6.02), 2017.  Available at www.jmilne.org/math/.
  * [10] Liqun Qi.  Eigenvalues of a real supersymmetric tensor.  J. Symbolic Comput., 40(6):1302–1324, 2005.
  * [11] Irene Sciriha.  A characterization of singular graphs.  Electron. J. Linear Algebra, 16:451–462, 2007.
  * [12] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.2), 2021.  https://www.sagemath.org.
  * [13] Long Wang and Xianya Geng.  Proof of a conjecture on the nullity of a graph.  Journal of Graph Theory, 95(4):586–593, 2020.

Joshua Cooper, Department of Mathematics, University of South Carolina,
Columbia, SC 29208 USA

E-mail address, Joshua Cooper<EMAIL_ADDRESS>
Grant Fickes, Department of Mathematics, University of South Carolina,
Columbia, SC 29208 USA

E-mail address, Grant Fickes<EMAIL_ADDRESS>


# BiometricBlender: Ultra-high dimensional,
multi-class synthetic data generator to imitate
biometric feature space

Marcell Stippinger  Dávid Hanák  Marcell T. Kurbucz  Gergely Hanczár  Olivér
M. Törteli  Zoltán Somogyvári  Wigner Research Centre for Physics, Department
of Computational Sciences, 29-33 Konkoly-Thege Miklós Street, H-1121 Budapest,
Hungary  Cursor Insight, 20-22 Wenlock Road, N1 7GU London, United Kingdom
Department of Statistics, Corvinus University of Budapest, 8 Fővám Square,
H-1093, Hungary

###### Abstract

The lack of freely available (real-life or synthetic) high or ultra-high
dimensional, multi-class datasets may hamper the rapidly growing research on
feature screening, especially in the field of biometrics, where the usage of
such datasets is common. This paper reports a Python package called
BiometricBlender, which is an ultra-high dimensional, multi-class synthetic
data generator to benchmark a wide range of feature screening methods. During
the data generation process, the overall usefulness and the intercorrelations
of blended features can be controlled by the user, thus the synthetic feature
space is able to imitate the key properties of a real biometric dataset.

###### keywords:

Dataset generator , Biometrics , Feature screening , Ultra-high dimensionality
, Multi-class classification

††journal: SoftwareX

## Code and Software Metadata

Nr. |  Metadata description |  Metadata contents
---|---|---
C1, S1 |  Current code version |  1.1.0
C2, S2 |  Permanent link to code/repository used for this code version |  https://github.com/cursorinsight/biometricblender/tree/paper
C3 |  Code Ocean compute capsule |  Not applicable
C4, S3 |  Legal Code License |  MIT License111More information at: https://mit-license.org (retrieved: 2 December 2021).
C5 |  Code versioning system used |  Git
C6 |  Software code languages, tools, and services used |  Python
C7,S4–S5 |  Compilation and installation requirements, operating environments & dependencies |  Python 3.7.1+, h5py 2.10+, numpy 1.18+, scipy 1.6+, scikit-learn 0.24+; OS agnostic (Linux, OS X, MS Windows)
C8, S6 |  Link to developer documentation and user manual |  https://github.com/cursorinsight/biometricblender/blob/paper/README.md
C9, S7 |  Support email for questions |<EMAIL_ADDRESS>
Table 1: Code and software metadata

##  1 Motivation and significance

Analyzing ultra-high dimensional data that include hundreds of thousands of
features is becoming an increasingly common problem in many fields of modern
scientific research [1]. Since these datasets typically contain only a
relatively few relevant, non-redundant predictors, a screening step that
removes irrelevant features prior to the main analysis is often employed for
reaching a better prediction accuracy and much faster computation [2].

While numerous screening methods have been published in recent years (e.g.,
[3, 4, 5, 6, 7, 8, 9]), only a few high or ultra-high dimensional datasets are
available publicly that can be employed for benchmarking purposes.
Furthermore, these public datasets (see, e.g, high dimensional datasets
related to classification tasks on the UC Irvine Machine Learning
Repository222Available at: https://archive.ics.uci.edu (retrieved: 2 December
2021).) typically do not contain ground truth side information on the
usefulness of the features. Besides, most of them have binary response
variables, so they cannot be used to benchmark methods developed for solving
multiple-class screening problems. While in biometrics such problems are
typically encountered, it is difficult to imitate the properties of these
kinds of feature spaces by using available data generators (e.g., the Madelon
dataset [10] and the associated data generation algorithm implemented by the
make_classification function of the scikit-learn Python package [11]).

To remedy this shortcoming, this paper reports a Python package called
BiometricBlender, which is an ultra-high dimensional, multi-class synthetic
data generator to benchmark a wide range of feature screening methods. During
the data generation process, the overall usefulness and the intercorrelations
of features can be controlled by the user. Accordingly, the key properties of
a biometric dataset can be imitated by the blended synthetic feature space.
This dataset provides an alternative to real biometric datasets, which are
typically not freely available. Therefore, it enables the publishing of
results achieved on such data.

The paper is organized as follows. Section 2 contains the detailed description
of the data generator software. As an illustrative example, Section 3 presents
a synthetic feature space generated to imitate a real-life signature
verification dataset. Finally, Section 4 summarizes the impact of the software
and provides the conclusions.

##  2 Software description

This section describes the full generator pipeline of BiometricBlender in
detail. The output of the pipeline is a high dimensional, multi-class $S\times
F^{visible}$ feature matrix
$\mathbf{V}^{visible}=\left[v^{visible}_{ij}\right]$, where:

  * •

$F^{visible}$ is the desired number of observable, _visible_ features;

  * •

$\mathcal{F}^{visible}=\left\\{f^{visible}_{j}|1\leq j\leq
F^{visible}\right\\}$ is the set of visible features;

  * •

$C=|\mathcal{C}|$ is the number of classes;

  * •

$S_{\mathcal{C}}$ is the number of samples per class333Note that, for
simplicity, scalar $S_{\mathcal{C}}$ was used. Further development could
provide a more realistic feature space by employing classes with different
sample sizes.; and

  * •

$S=|\mathcal{S}|=C\cdot S_{\mathcal{C}}$ is the total number of samples.

Visible features are derived from a set of _hidden_ features, which are
significantly fewer than their visible counterparts. In this context:

  * •

$F^{hidden}\ll F^{visible}$ is the desired number of hidden features;

  * •

$\mathcal{F}^{hidden}=\left\\{f^{hidden}_{j}|1\leq j\leq F^{hidden}\right\\}$
is the set of hidden features;

  * •

$\mathcal{F}^{true}$ is the set of hidden features which are created to be
significant and distinguishing, and

  * •

$\mathcal{F}^{fake}$ is the set of hidden features which are just pure noise,
and do not contribute useful information to the classification of samples.
Moreover:

$\displaystyle\mathcal{F}^{true}\cup\mathcal{F}^{fake}$
$\displaystyle=\mathcal{F}^{hidden},$
$\displaystyle\mathcal{F}^{true}\cap\mathcal{F}^{fake}$
$\displaystyle=\emptyset.$

With an analogy taken from genetics, hidden features are the _genotypes_ ,
visible features are the _phenotypes_ of samples. “True feature” genes have an
effect on the behavior being observed, while “fake feature” genes do not.

If hidden features were directly observable and ideally distributed, sample
classification would be a trivial task. The blender components in the second
half of the pipeline (see below) ensure that this information is more
concealed in the visible features. The full pipeline performs the following
steps:

  1. 1.

A suitable distribution type and a set of distribution parameters are selected
per $c_{k}\in\mathcal{C}$ class and $f^{hidden}_{j}\in\mathcal{F}^{hidden}$
hidden feature;

  2. 2.

$F^{hidden}$ hidden feature values are drawn from these distributions per
sample:

$\forall
s_{i}\in\mathcal{S},f^{hidden}_{j}\in\mathcal{F}^{hidden}:v^{hidden}_{ij}=v(s_{i},f^{hidden}_{j});$

  3. 3.

Hidden features are combined with each other through polynomial, linear and/or
logarithmic combinations to produce $F^{visible}$ visible features per sample;

  4. 4.

A certain amount of random noise is added to the visible feature values.

###  2.1 Software Architecture

Figure 1 shows an overview of the pipeline, with the data flow between the
components. The number in parentheses after the name of each component
indicates which of the above steps the given component participates in. Each
component has a number of parameters that control the usefulness and signal-
to-noise ratio of the individual features. The components and their parameters
are described in Sections 2.1.1 to 2.1.5.

Figure 1:  Main components of the generator pipeline of BiometricBlender

####  2.1.1 Location Factory

This component is responsible for determining the _location_ 444 _Location_
defines the translation of a distribution, e.g., it is the mean of normal
distributions, and the smallest value, i.e., the start of the range of values
for uniform distributions. of the distributions per class and hidden feature:
$\mathbf{L}=\left[l_{kj}=l(c_{k},f^{hidden}_{j})\right]$. Locations are
randomly chosen under an envelope. The envelope is either a _normal
distribution_ or a _uniform distribution_ , specified by the user. The
parameters of the Location Factory are:

  * •

Number of features (true and fake): $F^{true},F^{fake}$.

  * •

Number of classes: $C$.

  * •

Ordering extent $\left(\in\mathbb{Z}_{[0,C]}\right)$: controls whether the
$l_{kj}:k\in\mathbb{Z}_{[1,C]}$ sequence of locations of any particular
$f^{hidden}_{j}$ feature are randomly, partially or fully ordered, thus
controls the correlations between features. Its value specifies the average
number of locations in every ordered subsequence. This is relevant when not
just one but several features come into play: the more ordered locations are,
the less detail a new feature adds to the overall amount of information.

Example: _height_ and _foot size_ are ordered similarly, therefore knowing
both does not carry twice as much information as knowing only one of them.
_IQ_ , on the other hand, is ordered randomly relative to these two features,
so knowing both _IQ_ and _height_ doubles the amount of information.

  * •

Sharing extent $\left(\in\mathbb{Z}_{[0,C]}\right)$: controls how many classes
share the exact same location on average. With zero sharing extent, all
classes have separate, distinguishable locations. With sharing extent $C$,
applied to all fake features, all classes share a single location: $\forall
k\in\mathbb{Z}_{[1,C]}:l_{kj}=l_{j}$, rendering the feature completely
useless. A sharing extent in between creates distinguishable groups of
classes, within which groups the individual classes appear identical.

Example: The sharing extent of _SSN_ is zero since all SSNs are unique. The
sharing extent of _first names,_ on the other hand, is significantly higher.

  * •

Usefulness $\left(\in\mathbb{R}_{[0,1]}\right)$ intuitively controls how
spread out are the sampling distributions of _Feature Sampler_. The larger the
usefulness and the less spread out distributions are, the easier it is to
separate feature values generated around these locations. Rather than
specifying the usefulness of all hidden features manually, the Location
Factory expects a _usefulness scheme_ , with which it generates the usefulness
of all features. The scheme can be _linear_ , _exponential_ or _long-tailed_.
The usefulness of pure noise features is fixed at zero. Figure 2 shows
different usefulness parameter settings through the example of two hidden
features.

Example: When identifying people, the usefulness of Social Security Number
(SSN) is 1, because it never changes and it is unambiguous. The respiratory
rate has much lower, but still non-zero usefulness because while it cannot
identify individuals, it can separate some age groups, people doing certain
activities or people with some medical condition that affects breathing.

Figure 2:  An example of two hidden features A and B for 10 labels with
ordering extent 2 and sharing extent 2

####  2.1.2 Feature Sampler

This component takes the $l_{kj}$ locations and usefulness values of the
previous step and draws hidden feature values for the required number of
samples from _normal distribution_ around these locations. As an option, the
_uniform distribution_ is also available at the command line interface.

During sampling, the usefulness is converted to the _scale_ 555 _Scale_
defines the spread of a distribution, e.g., it is the standard deviation for
normal distributions, and the length of the range of values for uniform
distributions. of the sampling distributions:

  * •

for true features, the converted scale is multiplied by a number drawn from a
small uniform distribution around 1, in order to add some variance; and

  * •

for fake features, a fixed scale value is used.

For every class $c_{k}\in\mathcal{C}$, $S_{\mathcal{C}}$ samples are created,
resulting in a $S\times F^{hidden}$ matrix
$\mathbf{V}^{hidden}=\left[v^{hidden}_{ij}\right]$ of hidden feature values.
Due to the conversion of usefulness to scale, less useful features have larger
magnitudes. The magnitudes get normalized just before blending.

####  2.1.3 Polynomial Blender

This component takes all possible combinations of at least one, at most $d$
non-unique hidden features, and multiplies them together while preserving
their scales by taking the appropriate roots. For example, if feature values
are $x,y\mbox{ and }z$, and $d=2$, then the generated features are $x$, $y$,
$z$, $\sqrt{\mathstrut xy}$, $\sqrt{\mathstrut xz}$, $\sqrt{\mathstrut yz}$,
$\sqrt{\mathstrut x^{2}}$, $\sqrt{\mathstrut y^{2}}$ and $\sqrt{\mathstrut
z^{2}}$.666Note that by taking the roots we end up with some repeated values.

The output is an $\mathcal{F}^{trans}$ set of
$F^{trans}=|\mathcal{F}^{trans}|=\binom{F^{hidden}+d}{d}-1$ (non-unique)
transitional features.777$F^{trans}$ is equal to the number of combinations of
taking exactly $d$ items of $F^{hidden}+1$ items – all the hidden features
plus the constant 1 – at a time, with replacement; minus the sole case of
taking 1 $d$ times. The degenerate case of $d=1$ results in
$\mathcal{F}^{trans}=\mathcal{F}^{hidden}$.

####  2.1.4 Feature Blender

This component takes the transitional features, constructs a random,
${F^{visible}\times F^{trans}}$ dimensional sparse weight matrix
$\mathbf{W}=\left[w_{ij}\right]$, and produces $F^{visible}$ blended features
using those weights.

The number of blended transitional features per visible feature (i.e., the
number of non-zero items in each column of $\mathbf{W}$) is randomly chosen
from a discrete uniform distribution of small values. The weights themselves
are chosen from a _Dirichlet distribution_ , such that their sum per visible
feature is always 1: $\forall i:\sum_{j=1}^{F^{trans}}w_{ij}=1$. Thus the
overall magnitude of the features is preserved during blending.

The Feature Blender can operate in two modes:

  * •

in _linear_ mode, the visible features are weighted sums of the transitional
features:

$\mathbf{V}^{visible}=\left[v^{visible}_{ij}\right]=\mathbf{V}^{trans}\mathbf{W}^{\intercal}\text{\enspace
where \enspace}v^{visible}_{ij}=\sum_{t=1}^{F^{trans}}v^{trans}_{it}w_{jt};$

  * •

in _logarithmic_ mode, the visible features are products of the weighted
powers of the transitional features:

$\mathbf{V}^{visible}=\left[v^{visible}_{ij}\right]\text{\enspace where
\enspace}v^{visible}_{ij}=\prod_{t=1}^{F^{trans}}\left(v^{trans}_{it}\right)^{w_{jt}}.$

The linear mode results in feature distributions close to the Gaussian, while
logarithmic mode generates long-tailed feature distributions close to the
lognormal distribution.888The linear blending mode (optionally with the noise
blending, see below) conforms the generative model of the _Factor Analysis_
(FA), thus, in theory, the hidden features may be reconstructed up to a
multidimensional rotation and some noise. The logarithmic blending mode is
different but the FA still produced reasonable reconstructions.

####  2.1.5 Noise Blender

Finally, optional random noise is added to the visible features, taking the
following steps per feature:

  1. 1.

noise is drawn randomly from a normal distribution;

  2. 2.

an $\alpha$ relative usefulness is drawn randomly from a uniform distribution
between $0-1$;

  3. 3.

the feature and the random noise are blended with either linear or logarithmic
interpolation, with $\alpha,1-\alpha$ weights, respectively.

Thus, if $\alpha$ is 1, zero noise is added, and when $\alpha$ is 0, the
feature values are completely blocked out by the random noise.

###  2.2 Software Functionalities

The sole functionality of BiometricBlender is to generate an ultra-high
dimensional, multi-class dataset to benchmark a wide range of feature
screening methods. The output is generated as an HDF5 file.999Detailed
information about the HDF5 format can be found at:
https://hdfgroup.org/solutions/hdf5 (retrieved: 2 December 2021). Given a
fixed seed, the output is reproducible up to rounding errors.

##  3 Illustrative Examples

As an illustrative example, a synthetic dataset is generated to imitate the
private signature feature space of Cursor Insight.101010Cursor Insight won the
ICDAR competition on signature verification and writer identification in 2015
[12]. For further information, see:
https://cursorinsight.com/e-signatures.html (retrieved: 2 December 2021). Note
that, to demonstrate the potential in screening, the dataset generated here is
somewhat noisier than the imitated data.

The following custom command line parameters were set:

  * •

n-labels = 100;

  * •

n-samples-per-label = 16;

  * •

n-true-features = 40;

  * •

n-fake-features = 160;

  * •

average-consecutive-locations = 2;

  * •

average-shared-locations = 3;

  * •

n-features-out = 10 000;

  * •

blending-mode = ’logarithmic’.

The resulting dataset has 1 600 samples and 10 000 features. Note that in this
feature set one must adjust the parameters of the generative model to
approximate the statistics (e.g., eigenspectrum) of the output rather than
prescribing the statistics themselves. We tested it for classification in the
following ways. We trained the scikit-learn [11] (version: 0.24.2)
implementation of three basic classifiers on the original data and on the
reduced/decomposed version of the data. We characterized the best cross-
validated accuracy that can be attained for each classifier using a full grid
search over crucial parameters. These parameters were

  * •

weights = ’uniform’, ’distance’ for $k$-nearest neighbors ($k$NN);

  * •

C = 0.5, 1.0, 2.0; tol = 1e-4, 1e-3, 1e-2 for the support vector classifier
(SVC); and

  * •

n_estimators = 1000; min_samples_leaf = 1, 2, 4; max_depth = None, 8, 10;
min_impurity_decrease = 0.0, 0.01, 0.05 for the Random Forest Classifier (RF).

The reduction step allowed the classifiers to work on a more focused dataset.
We executed each reduction/decomposition algorithm to produce a reduced
feature space of 10, 25, 50, 100, 200, 400, and 800 features and reported the
best accuracy only, see Table 2. The Principal Component Analysis (PCA) kept
its default settings. To Factor Analysis (FA) we applied the varimax rotation.
The $k$-best SelectKBest method increasingly selected the best features using
the f_classif score. $\mathcal{F}^{true}$ used the true hidden features.

(a) Classification performance

Reduction | None | PCA | FA |  $k$-best | $\mathcal{F}^{true}$
---|---|---|---|---|---
Class. |  $k$NN | 0.131 | 0.218 | 0.214 | 0.641 | 0.632
SVC | 0.471 | 0.466 | 0.548 | 0.686 | 0.656
RF | 0.609 | 0.371 | 0.716 | 0.692 | 0.860

(b) Fit time of the classifier

Reduction | None | PCA | FA |  $k$-best
---|---|---|---|---
Class. |  $k$NN | 0.153s | 0.003s | 0.001s | 0.006s
SVC | 24s | 0.37s | 0.42s | 0.46s
RF | 300s | 22s | 21s | 29s

Table 2: Classification results on the 1 600$\times$10 000 dataset for three
basic classifiers and various reduction algorithms. _(a)_ Only the best
accuracy among all parameters is reported. _(b)_ Fit times are the wall time
after the reduction step and correspond to the accuracy shown above.

##  4 Impact and conclusion

The ultra-high dimensional, multi-class data generator called BiometricBlender
supports the rapidly growing research on feature screening in two ways. On the
one hand, it facilitates the benchmark of a wide range of feature screening
methods (see Table 2) by providing an alternative to real (typically non-free)
biometric datasets. On the other hand, it enables the publishing of results
achieved on such data. To this end, the overall usefulness and the
intercorrelations of blended features can be controlled by the user during
data generation. Thus, the synthetic feature space is able to imitate the key
properties of a real biometric dataset.

## Declaration of Competing Interest

We wish to draw the attention of the reader to the following facts, which may
be considered as potential conflicts of interest, and to significant financial
contributions to this work. The nature of potential conflict of interest is
described below: some of the authors work for Cursor Insight, an IT company
targeting human motion analysis, person classification and identification
based on large-scale biometric data in particular. In order to handle such
real-life, multi-class, ultra-high dimension datasets efficiently, we came up
with our own feature screening algorithm, because we found industry standard
solutions insufficient. We have then decided to share our solution with the
general public. The demand for a synthetic data generator arose when, in order
to prove the performance of our screening algorithm against standard
solutions, we started looking for publicly available reference datasets of
such dimensions, or generators of such, and found none.

## Acknowledgments

The authors would like to thank Erika Griechisch (Cursor Insight, London) and
András Telcs (Wigner Research Centre for Physics, Budapest) for their valuable
comments and advice. M.S., M.T.K., and Z.S. thank the support of Eötvös Loránd
Research Network. Z.S. was supported by the Hungarian National Research,
Development and Innovation Office, under grant number NKFIH K135837 and the
Hungarian National Brain Research Program 2017-1.2.1-NKP-2017-00002.

## References

  * [1] Y. Liu, X. Chen, Quantile screening for ultra-high-dimensional heterogeneous data conditional on some variables, Journal of Statistical Computation and Simulation 88 (2) (2018) 329–342.
  * [2] D. Qiu, J. Ahn, Grouped variable screening for ultra-high dimensional data for linear model, Computational Statistics & Data Analysis 144 (2020) 106894.
  * [3] Q. Mai, H. Zou, The Kolmogorov filter for variable screening in high-dimensional binary classification, Biometrika 100 (1) (2013) 229–234.
  * [4] Q. Mai, H. Zou, et al., The fused Kolmogorov filter: A nonparametric model-free screening method, The Annals of Statistics 43 (4) (2015) 1471–1497.
  * [5] X. Chen, X. Chen, H. Wang, Robust feature screening for ultra-high dimensional right censored data via distance correlation, Computational Statistics & Data Analysis 119 (2018) 118–138.
  * [6] X. Chen, Y. Zhang, Y. Liu, X. Chen, Model-free feature screening for ultra-high dimensional competing risks data, Statistics & Probability Letters 164 (2020) 108815.
  * [7] X. Chen, C. C. Liu, S. Xu, An efficient algorithm for joint feature screening in ultrahigh-dimensional cox’s model, Computational Statistics 36 (2) (2021) 885–910.
  * [8] Y. He, L. Zhang, J. Ji, X. Zhang, Robust feature screening for elliptical copula regression model, Journal of Multivariate Analysis 173 (2019) 568–582.
  * [9] Q. Hu, L. Lin, Feature screening in high dimensional regression with endogenous covariates, Computational Economics (2021) 1–21.
  * [10] I. Guyon, S. Gunn, A. Ben-Hur, G. Dror, Result analysis of the nips 2003 feature selection challenge, Advances in neural information processing systems 17 (2004).
  * [11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al., Scikit-learn: Machine learning in python, the Journal of machine Learning research 12 (2011) 2825–2830.
  * [12] M. I. Malik, S. Ahmed, A. Marcelli, U. Pal, M. Blumenstein, L. Alewijns, M. Liwicki, Icdar2015 competition on signature verification and writer identification for on-and off-line skilled forgeries (sigwicomp2015), in: 2015 13th International Conference on Document Analysis and Recognition (ICDAR), IEEE, 2015, pp. 1186–1190.