# A polynomial resultant approach to algebraic construction of extremal graphs

Tao Zhang${}^{\text{a,}}$, Zixiang Xu${}^{\text{b}}$ and Gennian
Ge${}^{\text{b,}}$
${}^{\text{a}}$ School of Mathematics and Information Science, Guangzhou
University, Guangzhou 510006, China.
${}^{\text{b}}$ School of Mathematical Sciences, Capital Normal University,
Beijing 100048, China.
Research supported by the National Natural Science Foundation of China under
Grant No. 11801109.Research supported by the National Natural Science
Foundation of China under Grant No. 11971325, National Key Research and
Development Program of China under Grant Nos. 2020YFA0712100 and
2018YFA0704703, and Beijing Scholars Program.

###### Abstract

The Turán problem asks for the largest number of edges ex$(n,H)$ in an
$n$-vertex graph not containing a fixed forbidden subgraph $H$, which is one
of the most important problems in extremal graph theory. However the order of
magnitude of ex$(n,H)$ for bipartite graphs is known only in a handful of
cases. In particular, giving explicit constructions of extremal graphs is very
challenging in this field. In this paper, we develop a polynomail resultant
approach to algebraic construction of explicit extremal graphs, which can
efficiently decide whether a specified structure exists. A key insight in our
approach is the multipolynomial resultant, which is a fundamental tool of
computational algebraic geometry. Our main results include the matched lowers
bounds for Turán number of $1$-subdivision of $K_{3,t_{1}}$ and linear Turán
number of Berge theta hyerpgraph $\Theta_{3,t_{2}}^{B}$ with $t_{1}=25$ and
$t_{2}=217$. Moreover, the constant $t_{1}$ improves the random algebraic
construction of Bukh and Conlon [Rational exponents in extremal graph theory,
J. Eur. Math. Soc. 20 (2018), 1747-1757] and makes progress on the known
estimation for the smallest value of $t_{1}$ concerning a problem posed by
Conlon, Janzer and Lee [More on the extremal number of subdivisions,
Combinatorica, to appear], while the constant $t_{2}$ improves a result of He
and Tait [Hypergraphs with few berge paths of fixed length between vertices,
SIAM J. Discrete Math., 33(3), 1472-1481].

Key words and phrases: Turán number, resultant, algebraic construction,
subdivision, Berge theta hypergraph.

AMS subject classifications: 05C35, 05C65.

##  1 Introduction

Given a graph $H$, the Turán number $\text{ex}(n,H)$ is the maximum number of
edges in an $n$-vertex graph that does not contain $H$ as a subgraph. The
estimation of $\text{ex}(n,H)$ for various graphs $H$ is one of the most
important problems in extremal graph theory. For general graph $H,$ the famous
Erdős-Stone-Simonovits Theorem [13, 14] gives that

$\displaystyle\text{ex}(n,H)=(1-\frac{1}{\chi(H)-1}+o(1))\binom{n}{2},$

where $\chi(H)$ is the chromatic number of $H$. This theorem asymptotically
solves the problem when $\chi(H)\geq 3$. However, finding good bounds for
$\text{ex}(n,H)$ for bipartite graphs $H$ is in general very difficult. The
order of magnitude of $\text{ex}(n,H)$ is not known even in some very basic
cases such as when $H$ is the even cycle $C_{8}$, complete bipartite graph
$K_{4,4}$ or the hypercube $Q_{3}$. In general, complete bipartite graphs and
even cycles are two of the most important classes of bipartite graphs. A well-
known theorem of Kövári, Sós and Turán [19] showed that
$\text{ex}(n,K_{s,t})=O(n^{2-1/s})$ for any integers $t\geq s$. In 1974, Bondy
and Simonovits [3] gave a general upper bound
$\text{ex}(n,C_{2\ell})=O(n^{1+\frac{1}{\ell}})$.

Showing matched lower bounds for Turán number of a specified bipartite graph
is one of the most challenging problems in extremal graph theory. Usually
there are three types of constructions as follows:

  1. 1.

Probabilistic method with alterations, which are quite general and easy to
apply, but usually do not give tight bounds. For example, for a given
bipartite graph $H$ with $a$ vertices and $b$ edges, the standard
probabilistic argument will give
$\text{ex}(n,H)=\Omega(n^{\frac{2b-a}{b-1}}).$ In particular, when $H=K_{s,t}$
with $s\leq t$, this method gives
$\text{ex}(n,K_{s,t})=\Omega(n^{2-\frac{s+t-2}{st-1}})$, which do not match
the upper bound $\text{ex}(n,K_{s,t})=O(n^{2-\frac{1}{s}})$.

  2. 2.

Explicit constructions, which often give tight bounds but appear to be
somewhat magical and only work in certain special situations. For example, one
can view the vertices as the points in vector space over finite field, and two
vertices are adjacent if they satisfy a system of equations in finite field.
Using the above idea, when $s=2,3,$ matching lower bounds for
$\text{ex}(n,K_{s,t})$ were found in [5, 12]. For general values of $s$, Alon
Kollár, Rónyai and Szabó [1, 18] constructed the so-called projective norm
graphs, which yields $\text{ex}(n,K_{s,t})=\Omega(n^{2-\frac{1}{s}})$ when
$t\geqslant(s-1)!+1$. Moreover, using the relation with finite geometry,
Benson [2] and Singleton [25] constructed extremal graphs for $C_{6}$ and
$C_{10}$ in 1966. Several alternative constructions can be found in [10, 21,
23, 27].

  3. 3.

Random algebraic method, which combines the advantages of both the flexibility
of randomized constructions and the rigidity of algebraic constructions,
originally was proposed by Bukh [6]. Usually the vertex set is the vector
space over finite field and the edge set is determined by a number of random
polynomials. This method has been applied to complete bipartite graphs [6],
theta graphs [9] and several other types of hypergraphs [17, 22]. Moreover,
Bukh and Conlon [7] successfully proved the so-called rational Turán exponent
conjecture via this method. It is worth noticing that, the random algebraic
method usually requires some parameters to be very large due to Lang-Weil
bound [20]. Bukh and Tait [8] and the authors [28] studied how these Turán
numbers depend on such large parameters of the forbidden graphs and
hypergraphs.

Our original motivation for this paper can be stated as follows.

Motivation: If we have used the random algebraic construction of Bukh to
obtain tight lower bounds for Turán number of some given graph $H$, can we
give an explicit construction of extremal graph for $H$? Furthermore, as we
have mentioned above, the random algebraic method usually requires some
parameters to be very large, can we obtain a better constant dependence?

As far as we know, there have been two such explicit constructions with
similar motivation in recent years. Verstraëte and Williford [26] gave an
explicit construction of $\theta_{4,3}$-free graph with
$\Omega(n^{\frac{5}{4}})$ edges, which significantly improves the constant
compared with the result of Conlon [9]. Pohoata and Zakharov [24] introduced a
high uniformity generalization of the so-called (projective) norm graphs of
Alon, Kollár, Rónyai and Szabó [1, 18], and showed that
$\text{ex}_{r}(n,K_{s_{1},s_{2},\ldots,s_{r}}^{(r)})=\Omega(n^{r-\frac{1}{s_{1}s_{2}\cdots
s_{r-1}}})$ holds for all integers $s_{1},\ldots,s_{r}\geq 2$ such that
$s_{r}\geq((r-1)(s_{1}\cdots s_{r-1}-1))!+1.$ This improves upon the result of
Ma, Yuan and Zhang [22].

In this paper, we mainly focus on two forbidden structures. The first is the
1-subdivision of complete bipartite graphs. Recall that the $1$-subdivision of
a graph $H$, denoted by $H^{\prime}$, is the graph obtained by replacing the
edges of $H$ by internally disjoint paths of length $2$. In [11], Conlon,
Janzer and Lee showed that
$\text{ex}(n,K_{s,t}^{\prime})=O(n^{\frac{3}{2}-\frac{1}{2s}})$ for $2\leq
s\leq t$. Combining the random algebraic construction in [7], they also showed
the upper bound is tight when $t$ is sufficiently large compared to $s$. In
the same paper, they asked the following problem:

######  Problem 1.1.

For any integer $s\geq 2$, estimate the smallest $t$ such that
$\textup{ex}(n,K_{s,t}^{\prime})=\Omega(n^{\frac{3}{2}-\frac{1}{2s}})$.

The case $s=2$ amounts to estimating the extremal number of the theta graph
$\theta_{4,t}$. As we have mentioned, Verstraëte and Williford [26] gave an
algebraic construction which yields
$\text{ex}(n,\theta_{4,3})=\Omega(n^{\frac{5}{4}})$. In this paper, we
consider the next case $s=3$, and prove the following result.

######  Theorem 1.2.

$\textup{ex}(n,K_{3,25}^{\prime})=\Theta(n^{\frac{4}{3}})$.

The previously known smallest value of $t$ from random algebraic method in [7]
is $s^{O(s^{2})}.$ In particular, when $s=3,$ their construction works for
$t\approx 10^{56}.$

Secondly, we consider the linear Turán number of Berge theta hypergraph
$\Theta_{\ell,t}^{B}.$ Define the _$r$ -uniform Berge theta hypergraph_
$\Theta_{\ell,t}^{B}$ to be a set of distinct vertices
$x,y,v_{1}^{1},\cdots,v_{\ell-1}^{1},\cdots,v_{1}^{t},$
$\cdots,v_{\ell-1}^{t}$ and a set of distinct edges $e_{1}^{1},\cdots,$
$e_{\ell}^{1},\cdots,e_{1}^{t},\cdots,e_{\ell}^{t}$ such that
$\\{x,v_{1}^{i}\\}\subset e_{1}^{i},$ $\\{v_{j-1}^{i},v_{j}^{i}\\}\subset
e_{j}^{i}$ and $\\{v_{\ell-1}^{i},y\\}\subset e_{\ell}^{i}$ for $1\leq i\leq
t$ and $2\leq j\leq\ell-1.$ By contrast with the simple graph cases, only a
few results are known for hypergraph Turán problems. A hypergraph is called
_linear_ if every two hyperedges have at most one vertex in common. Given a
family of $r$-uniform hypergraphs $\mathcal{F}$, the _linear Turán number_ of
$\mathcal{F}$, denoted $\text{ex}_{r}^{lin}(n,\mathcal{F})$, is the maximum
number of hyperedges in an $\mathcal{F}$-free $r$-uniform linear hypergraph on
$n$ vertices. It is easy to see that
$\text{ex}_{r}^{lin}(n,\mathcal{F})\leq\text{ex}_{r}(n,\mathcal{F})$.

Recently, He and Tait [17] gave the following upper bound

$\displaystyle\textup{ex}_{r}(n,\Theta_{\ell,t}^{B})\leq
c_{r,\ell,t}n^{1+\frac{1}{\ell}},$

where $c_{r,\ell,t}$ is a constant depending on $r,\ell,t$. They also showed
that

$\displaystyle\textup{ex}_{r}(n,\Theta_{\ell,t}^{B})=\Omega_{\ell,r}(n^{1+\frac{1}{\ell}}),$

where $t$ is extremely large.

It is therefore still quite natural to ask whether for $\ell\geq 3$, there
exist improved constructions that could show that $t(\ell)$ can be chosen to
be a reasonable quantity. When $\ell=3,$ we prove the following result via an
explicit construction.

######  Theorem 1.3.

$\textup{ex}_{3}^{lin}(n,\Theta_{3,217}^{B})=\Theta(n^{\frac{4}{3}})$.

Table 1 lists some comparisons between random algebraic constructions and
explicit constructions. This paper is organized as follows. In Section 2, we
will give some basics about the resultant of polynomials, which are the main
techniques employed in this paper. In Section 3, we give a proof of Theorem
1.2. We prove Theorem 1.3 in Section 4. Section 5 concludes our paper. Most of
the computations have been done by MAGMA [4].

Forbidden (hyper-)graph $H$ | Constant dependence
---|---
| Random algebraic construction | Explicit construction
$\text{ex}(n,K_{s,t})=\Omega(n^{2-\frac{1}{s}})$ | $t\geq s^{4s}$ | $t\geq(s-1)!+1$
$\text{ex}(n,\Theta_{\ell,t})=\Omega(n^{1+\frac{1}{\ell}})$ | $t=\ell^{O(\ell^{2})}$ | $\ell=4,t\geq 3$
$\text{ex}_{r}(n,K_{s_{1},\ldots,s_{r}}^{(r)})=\Omega(n^{r-\frac{1}{s_{1}\cdots s_{r-1}}})$ | $s_{r}\geq(\prod\limits_{i=1}^{r-1}s_{i})^{O(\prod\limits_{i=1}^{r-1}s_{i})}$ | $s_{r}\geq((r-1)(s_{1}\cdots s_{r-1}-1))!+1$
$\text{ex}(n,sub(K_{s,t}))=\Omega(n^{\frac{3}{2}-\frac{1}{2s}})$ | $t=s^{O(s^{2})}$ |  $\bm{s=3}$, $\bm{t\geq 25}$
$\text{ex}_{r}^{lin}(n,\Theta_{\ell,t}^{B})=\Omega(n^{1+\frac{1}{\ell}})$ | $t=\ell^{O(\ell^{2})}$ | $\bm{\ell=3,t\geq 217}$
Table 1: Constant dependence in random algebraic constructions and explicit
constructions

##  2 Main technique employed

Let $q$ be a prime power, and $\mathbb{F}_{q}$ be the finite field of order
$q$. Let $G$ be a graph with vertex set $\mathbb{F}_{q}^{t}$ and two vertices
$u,v\in\mathbb{F}_{q}^{t}$ are joined if $f_{i}(u,v)=0$ for $i=1,\dots,s$,
where $f_{i}\in\mathbb{F}_{q}[x_{1},\dots,x_{2t}]$. In order to show that $G$
does not contain certain structure, we first fix several vertices, then count
the number of certain substructures between these vertices (for example,
consider theta graph $\theta_{k,t}$, we need to show that there are at most
$t-1$ paths of length $k$ between any two fixed vertices, and for complete
bipartite graph $K_{s,t}$, we need to show that there are at most $t-1$ common
neighbours between any $s$ vertices). From these conditions, we can get a
series of equations

$F_{1}(x_{1},\dots,x_{m})=\cdots=F_{m}(x_{1},\dots,x_{m})=0,$

(in general, there should be $m$ equations with $m$ variables), where $F_{j}$
($j=1,\dots,m$) come from $f_{i}$ ($i=1,\dots,s$). If the construction works,
then there are finitely many solutions for above equations, i.e., $\dim(W)=0$,
where

$W=\\{x\in\mathbb{F}_{q}^{m}:\ F_{1}(x)=\cdots=F_{m}(x)=0\\}.$

The following lemma says that the size of $W$ is bounded by the product of
degrees of $F_{i}$.

######  Theorem 2.1 (Bézout’s theorem).

Let $F_{i}\in\mathbb{F}_{q}[x_{1},\dots,x_{m}]$ for $i=1,\dots,m$. If the
variety $W=\\{x\in\mathbb{F}_{q}^{m}:\ F_{1}(x)=\cdots=F_{m}(x)=0\\}$ has
$\dim(W)=0$, then

$|W|\leq\prod_{i=1}^{m}\deg(F_{i}).$

In general, Bézout’s theorem does not give the best bound for the size of $W$.
On the other hand, it is not easy to compute the dimension of $W$. But for
some specific cases, we can determine the size of $W$ by eliminate variables
directly.

When the forbidden graph is simple, for example, $\theta_{4,t}$ in Theorem
2.5, we get Eqs. (1)-(3), the degrees of polynomials are 2, 3 and 3. Hence
this case can be done by manual calculation. But when the forbidden graph is a
bit complicated, say $\Theta_{3,t}^{B}$ in Section 4, we get Eqs. (66)-(73),
and the degrees of these polynomials are 2, 2, 2, 3, 3 and 3. After
eliminating 5 variables, the final polynomial has degree 40 (see Eq. (74)),
this is almost impossible to get it by manual computation. Similarly for the
case $K_{3,t}^{\prime}$. Hence we introduce the polynomial resultant method,
which can settle such cases by computer.

The polynomial resultant method has been used in [16] for Ramsey problems. For
the convenience of readers, we recall some basics about the resultant of
polynomials. Let $\mathbb{F}$ be a field, and $\mathbb{F}[x]$ be the
polynomial ring with coefficients in $\mathbb{F}$.

######  Definition 2.2.

Let $f(x),g(x)\in\mathbb{F}[x]$ with $f(x)=a_{m}x^{m}+\cdots+a_{1}x+a_{0}$ and
$g(x)=b_{n}x^{n}+\cdots+b_{1}x+b_{0}$, then the resultant of $f$ and $g$ is
defined by the determinant of the following $(m+n)\times(m+n)$ matrix,

$\begin{array}[]{c@{\hspace{-5pt}}l}\left(\begin{array}[]{cccccccc}a_{0}&&&&b_{0}&&&\\\
a_{1}&a_{0}&&&b_{1}&b_{0}&&\\\ a_{2}&a_{1}&\ddots&&b_{2}&b_{1}&\ddots&\\\
\vdots&a_{2}&\ddots&a_{0}&\vdots&b_{2}&\ddots&b_{0}\\\
a_{m}&\vdots&\ddots&a_{1}&b_{n}&\vdots&\ddots&b_{1}\\\
&a_{m}&\ddots&a_{2}&&b_{n}&\ddots&b_{2}\\\ &&\ddots&\vdots&&&\ddots&\vdots\\\
&&&a_{m}&&&&b_{n}\\\ \end{array}\right)\\\\[-5.0pt]
\begin{array}[]{cc}\underbrace{\rule{88.20354pt}{0.0pt}}_{n}&\underbrace{\rule{88.20354pt}{0.0pt}}_{m}\end{array}&\end{array},$

which is denoted by $R(f,g)$.

The resultant of two polynomials has the following property.

######  Lemma 2.3.

[15, Theorem 3.18] If $\text{gcd}(f(x),g(x))=h(x)$, where
$\text{deg}(h(x))\geq 1$, then $R(f,g)=0$. In particular, if $f$ and $g$ have
a common root in $\mathbb{F}$, then $R(f,g)=0$.

When we consider multivariable polynomials, we can define the resultant
similarly, and the above lemma still holds when we fix one variable. For any
$f,g\in\mathbb{F}[x_{1},\dots,x_{n}]$, let $R(f,g;x_{i})$ denote the resultant
of $f$ and $g$ with respect to $x_{i}$, then we have
$R(f,g;x_{i})\in\mathbb{F}[x_{1},\dots,x_{i-1},x_{i+1},x_{n}]$.

######  Example 2.4.

We consider the following equations

$\displaystyle f=xy-1=0,$ $\displaystyle g=x^{2}+y^{2}-4=0.$

Regarding $f$ and $g$ as polynomials in $x$ whose coefficients are polynomials
in $y$, then we can compute to get that

$R(f,g;x)=\text{det}\left(\begin{array}[]{ccc}y&0&1\\\ -1&y&0\\\
0&-1&y^{2}-4\\\ \end{array}\right)=y^{4}-4y^{2}+1.$

By Lemma 2.3, it follows that $y^{4}-4y^{2}+1$ vanishes at any common
solutions of $f=g=0$. Hence, by solving $y^{4}-4y^{2}+1=0$, we can find the
$y$-coordinates of the solutions.

As an example, we give a new proof for the result stated in the following
theorem, which was proved by Verstraëte and Williford [26]. A theta graph
$\theta_{k,t}$ is a graph made of $t$ internally disjoint paths of length $k$
connecting two endpoints.

######  Theorem 2.5.

[26] $\textup{ex}(n,\theta_{4,3})=\Omega(n^{\frac{5}{4}})$.

###### Proof.

Let $q$ be an odd prime power. The graph $G_{q}$ is defined on the vertex set
$V=\mathbb{F}_{q}^{4}$ such that $u=(u_{1},u_{2},u_{3},u_{4})\in V$ is joined
to $v=(v_{1},v_{2},v_{3},v_{4})\in V$ if and only if $u\neq v$ and

$\displaystyle u_{2}+v_{2}=u_{1}v_{1},$ $\displaystyle
u_{3}+v_{4}=u_{1}v_{1}^{2},$ $\displaystyle u_{4}+v_{3}=u_{1}^{2}v_{1}.$

From above equations, it is easy to see that if $r,s\in V$ are distinct and
have a common neighbour, then $r_{1}\neq s_{1}$. It can be computed to get
that $G_{q}$ has $n:=q^{4}$ vertices and $\Omega(n^{\frac{5}{4}})$ edges.

Suppose that $G_{q}$ contains a $\theta_{4,3}$ with edges
$\\{au,uv,vw,wb,ax,xy,yz,zb,ad,de,ef,fb\\}$. We first consider the octagon
with edge set $\\{au,uv,vw,wb,ax,xy,yz,zb\\}$. By the definition of $G_{q}$,
we have

$\displaystyle a_{2}+u_{2}=a_{1}u_{1},$ $\displaystyle
a_{3}+u_{4}=a_{1}u_{1}^{2},$ $\displaystyle a_{4}+u_{3}=a_{1}^{2}u_{1},$
$\displaystyle u_{2}+v_{2}=v_{1}u_{1},$ $\displaystyle
v_{3}+u_{4}=v_{1}u_{1}^{2},$ $\displaystyle v_{4}+u_{3}=v_{1}^{2}u_{1},$
$\displaystyle w_{2}+v_{2}=w_{1}v_{1},$ $\displaystyle
v_{3}+w_{4}=v_{1}w_{1}^{2},$ $\displaystyle v_{4}+w_{3}=v_{1}^{2}w_{1},$
$\displaystyle w_{2}+b_{2}=w_{1}b_{1},$ $\displaystyle
b_{3}+w_{4}=b_{1}w_{1}^{2},$ $\displaystyle b_{4}+w_{3}=b_{1}^{2}w_{1},$
$\displaystyle z_{2}+b_{2}=z_{1}b_{1},$ $\displaystyle
b_{3}+z_{4}=b_{1}z_{1}^{2},$ $\displaystyle b_{4}+z_{3}=b_{1}^{2}z_{1},$
$\displaystyle z_{2}+y_{2}=y_{1}z_{1},$ $\displaystyle
y_{3}+z_{4}=y_{1}z_{1}^{2},$ $\displaystyle y_{4}+z_{3}=y_{1}^{2}z_{1},$
$\displaystyle x_{2}+y_{2}=y_{1}x_{1},$ $\displaystyle
y_{3}+x_{4}=y_{1}x_{1}^{2},$ $\displaystyle y_{4}+x_{3}=y_{1}^{2}x_{1},$
$\displaystyle x_{2}+a_{2}=x_{1}a_{1},$ $\displaystyle
a_{3}+x_{4}=a_{1}x_{1}^{2},$ $\displaystyle a_{4}+x_{3}=a_{1}^{2}x_{1}.$

From the left eight equations (the middle eight equations, the right eight
equations, resp.), we can get the following equations.

$\displaystyle
f_{1}:=a_{1}u_{1}-u_{1}v_{1}+v_{1}w_{1}-w_{1}b_{1}+b_{1}z_{1}-z_{1}y_{1}+y_{1}x_{1}-x_{1}a_{1}=0,$
(1) $\displaystyle
f_{2}:=a_{1}u_{1}^{2}-u_{1}^{2}v_{1}+v_{1}w_{1}^{2}-w_{1}^{2}b_{1}+b_{1}z_{1}^{2}-z_{1}^{2}y_{1}+y_{1}x_{1}^{2}-x_{1}^{2}a_{1}=0,$
(2) $\displaystyle
f_{3}:=a_{1}^{2}u_{1}-u_{1}v_{1}^{2}+v_{1}^{2}w_{1}-w_{1}b_{1}^{2}+b_{1}^{2}z_{1}-z_{1}y_{1}^{2}+y_{1}^{2}x_{1}-x_{1}a_{1}^{2}=0.$
(3)

Regarding $f_{i}$ as polynomials with variable $u_{1}$, we can compute to get
that

$\displaystyle R(f_{1},f_{2};u_{1})=g_{1}(a_{1}-v_{1}),$ $\displaystyle
R(f_{1},f_{3};u_{1})=g_{2}(a_{1}-v_{1}),$

where

$\displaystyle g_{1}=$ $\displaystyle-
a_{1}b_{1}w_{1}^{2}+2a_{1}b_{1}w_{1}x_{1}-2a_{1}b_{1}x_{1}z_{1}+a_{1}b_{1}z_{1}^{2}+a_{1}v_{1}w_{1}^{2}-2a_{1}v_{1}w_{1}x_{1}+a_{1}v_{1}x_{1}^{2}-a_{1}x_{1}^{2}y_{1}+$
$\displaystyle
2a_{1}x_{1}y_{1}z_{1}-a_{1}y_{1}z_{1}^{2}+b_{1}^{2}w_{1}^{2}-2b_{1}^{2}w_{1}z_{1}+b_{1}^{2}z_{1}^{2}-b_{1}v_{1}w_{1}^{2}+2b_{1}v_{1}w_{1}z_{1}-b_{1}v_{1}z_{1}^{2}-2b_{1}w_{1}x_{1}y_{1}+$
$\displaystyle
2b_{1}w_{1}y_{1}z_{1}+2b_{1}x_{1}y_{1}z_{1}-2b_{1}y_{1}z_{1}^{2}+2v_{1}w_{1}x_{1}y_{1}-2v_{1}w_{1}y_{1}z_{1}-v_{1}x_{1}^{2}y_{1}+v_{1}y_{1}z_{1}^{2}+x_{1}^{2}y_{1}^{2}-$
$\displaystyle 2x_{1}y_{1}^{2}z_{1}+y_{1}^{2}z_{1}^{2},$ $\displaystyle
g_{2}=$ $\displaystyle
a_{1}b_{1}w_{1}-a_{1}b_{1}z_{1}-a_{1}v_{1}w_{1}+a_{1}v_{1}x_{1}-a_{1}x_{1}y_{1}+a_{1}y_{1}z_{1}-b_{1}^{2}w_{1}+b_{1}^{2}z_{1}+b_{1}v_{1}w_{1}-b_{1}v_{1}z_{1}-$
$\displaystyle v_{1}x_{1}y_{1}+v_{1}y_{1}z_{1}+x_{1}y_{1}^{2}-y_{1}^{2}z_{1}.$

Since $a$ and $v$ have a common neighbour, then $a_{1}\neq v_{1}$. Hence
$g_{1}=g_{2}=0$. We can regard $g_{1}$ and $g_{2}$ as polynomials with
variable $x_{1}$, then we have

$\displaystyle
R(g_{1},g_{2};x_{1})=(b_{1}-y_{1})(w_{1}-z_{1})^{2}(v_{1}-y_{1})(v_{1}-b_{1})(a_{1}-y_{1})(a_{1}-b_{1})(a_{1}-v_{1}+b_{1}-y_{1}).$

Note that $b$ and $y$ ($w$ and $z$, $v$ and $b$, $a$ and $y$, resp.) have a
common neighbour, then we have $a_{1}=b_{1}$ or $v_{1}=y_{1}$ or
$a_{1}+b_{1}=v_{1}+y_{1}$.

If $a_{1}=b_{1}$, substitute this equation into $f_{1}$ and $f_{2}$, then we
can compute to get that
$R(f_{1},f_{2};u_{1})=(z_{1}-x_{1})(v_{1}-y_{1})(a_{1}-y_{1})(a_{1}-v_{1})$.
Since $x$ and $z$ ($a$ and $y$, $a$ and $v$, resp.) have a common neighbour,
then we must have $v_{1}=y_{1}$. Substituting $a_{1}=b_{1}$ and $v_{1}=y_{1}$
into $f_{1}$ and $f_{3}$, then we get
$R(f_{1},f_{3};u_{1})=(z_{1}-x_{1})(w_{1}-z_{1})(a_{1}-v_{1})^{3}=0$, which
contradicts to the fact that $z$ and $x$ ($w$ and $z$, $a$ and $v$, resp.)
have a common neighbour. Hence $a_{1}\neq b_{1}$. Similarly, $v_{1}\neq
y_{1}$.

Therefore, we have

$\displaystyle a_{1}+b_{1}=v_{1}+y_{1}.$

By the symmetry of octagon, we also have

$\displaystyle u_{1}+z_{1}=x_{1}+w_{1}.$ (4)

Since there are three octagons $\\{au,uv,vw,wb,ax,xy,yz,zb\\}$,
$\\{au,uv,vw,wb,ad,de,ef,fb\\}$, $\\{ax,xy,yz,zb,ad,de,ef,fb\\}$ in
$\theta_{4,3}$, we have $a_{1}+b_{1}=v_{1}+y_{1}=v_{1}+e_{1}=y_{1}+e_{1}$.
Hence $v_{1}=y_{1}=e_{1}$ and $a_{1}+b_{1}=2v_{1}$. Substituting these
equations into $f_{1}$, we have $(a_{1}-v_{1})(u_{1}+w_{1}-x_{1}-z_{1})=0.$
Since $a,v$ have a common neighbour, then $a_{1}\neq v_{1}$. Hence we have
$u_{1}+w_{1}=x_{1}+z_{1}$. Combining with Eq. (4), we get that $u_{1}=x_{1}$,
which contradicts to the fact that $u,x$ have a common neighbour $a$. ∎

##  3 Construction of $K_{3,25}^{\prime}$-free graphs

In this section, we construct a $K_{3,25}^{\prime}$-free graph with $n$
vertices and $\Omega(n^{\frac{4}{3}})$ edges. Let $\mathbb{F}_{p}$ be a finite
field, where $p$ is an odd prime with $p\equiv 5\pmod{6}$ and $p>11$. Let

$S=\\{x:x\in\\{1,2,\dots,\frac{p-5}{6}\\}\text{ and }x\equiv
1\pmod{3}\\}\subseteq\mathbb{F}_{p}.$

Then we have the following lemma.

######  Lemma 3.1.

For any $x,y,z,t\in S$, we have $x+y\neq 0$, $x+y+z+t\neq 0$, $x+5y\neq 0$,
and $x^{2}+xy+y^{2}\neq 0$.

###### Proof.

Since $x,y,z,t\in\mathbb{F}_{p}$ and
$x,y,z,t\in\\{1,2,\dots,\frac{p-5}{6}\\}$, then we have $x+y\neq 0$,
$x+y+z+t\neq 0$, $x+5y\neq 0$. Note that $p\equiv 5\pmod{6}$, then $-3$ is a
non-quadratic residue module $p$. Hence,
$x^{2}+xy+y^{2}=(x+\frac{y}{2})^{2}+3(\frac{y}{2})^{2}\neq 0$. ∎

Now we can give our construction.

######  Construction 3.2.

The graph $G_{p}$ is defined with vertex set
$V:=S\times\mathbb{F}_{p}\times\mathbb{F}_{p}$, where
$x=(x_{1},x_{2},x_{3})\in V$ is joined to $y=(y_{1},y_{2},y_{3})\in V$ if
$x\neq y$ and

$\displaystyle x_{2}+y_{3}=x_{1}y_{1}^{2},$ $\displaystyle
x_{3}+y_{2}=x_{1}^{2}y_{1}.$

For any vertex $x=(x_{1},x_{2},x_{3})\in V$, from above two equations, any
choice of $y_{1}\in S$ can uniquely determine $y_{2}$ and $y_{3}$. Note that
$x$ should be different from $y$, then each vertex has degree at least
$\frac{p-5}{18}-1=\frac{p-23}{18}$. Hence $G_{p}$ has
$n:=\lceil\frac{p-5}{18}\rceil p^{2}$ vertices and at least $\frac{1}{18\times
18\times 2}(p-23)(p-5)p^{2}=\Omega(n^{\frac{4}{3}})$ edges. In the following
of this section, we will prove that $G_{p}$ is $K_{3,25}^{\prime}$-free. We
begin with the following simple lemma.

######  Lemma 3.3.

If $x,y\in V$ are distinct and have a common neighbour, then $x_{1}\neq
y_{1}$, $x_{2}\neq y_{2}$ and $x_{3}\neq y_{3}$.

###### Proof.

Suppose $x,y$ have a common neighbour $u$, then

$\displaystyle x_{2}+u_{3}=x_{1}u_{1}^{2},$ (5) $\displaystyle
x_{3}+u_{2}=x_{1}^{2}u_{1},$ (6) $\displaystyle y_{2}+u_{3}=y_{1}u_{1}^{2},$
(7) $\displaystyle y_{3}+u_{2}=y_{1}^{2}u_{1}.$ (8)

Now we divide our discussion into three cases.

Case 1: $x_{1}=y_{1}.$

For this case, from Eqs. (5) and (7), we have $x_{2}=y_{2}$. Similarly, from
Eqs. (6) and (8), we have $x_{3}=y_{3}$. Hence $x=y$, which is a
contradiction.

Case 2: $x_{2}=y_{2}.$

For this case, from Eqs. (5) and (7), we have $(x_{1}-y_{1})u_{1}^{2}=0$. Then
$x_{1}=y_{1}$, this has been done in Case 1.

Case 3: $x_{3}=y_{3}.$

For this case, from Eqs. (6) and (8), we have $u_{1}(x_{1}^{2}-y_{1}^{2})=0$.
Hence either $x_{1}=y_{1}$ or $x_{1}+y_{1}=0$. If $x_{1}=y_{1}$, this has been
done in Case 1. If $x_{1}+y_{1}=0$, this contradicts to Lemma 3.1. ∎

For any given $a,b,c\in V$ with $a,b,c$ being pairwise distinct, we estimate
the number of sequences $(x,y,z,w)\in V^{4}$ with $x,y,z,w$ being pairwise
distinct, such that $ax,xw,by,yw,cz,zw$ are edges in $G_{p}$. We will prove
that there are at most $24$ different such sequences. By the definition of
graph $G_{p}$, we have

$\displaystyle a_{2}+x_{3}=a_{1}x_{1}^{2},$ $\displaystyle
a_{3}+x_{2}=a_{1}^{2}x_{1},$ $\displaystyle w_{2}+x_{3}=w_{1}x_{1}^{2},$
$\displaystyle w_{3}+x_{2}=w_{1}^{2}x_{1},$ $\displaystyle
b_{2}+y_{3}=b_{1}y_{1}^{2},$ $\displaystyle b_{3}+y_{2}=b_{1}^{2}y_{1},$
$\displaystyle w_{2}+y_{3}=w_{1}y_{1}^{2},$ $\displaystyle
w_{3}+y_{2}=w_{1}^{2}y_{1},$ $\displaystyle c_{2}+z_{3}=c_{1}z_{1}^{2},$
$\displaystyle c_{3}+z_{2}=c_{1}^{2}z_{1},$ $\displaystyle
w_{2}+z_{3}=w_{1}z_{1}^{2},$ $\displaystyle w_{3}+z_{2}=w_{1}^{2}z_{1}.$

Cancelling $x_{2},x_{3},y_{2},y_{3},z_{2},z_{3}$ from the above equations, we
can get the following equations

$\displaystyle f_{1}:=a_{2}-w_{2}-x_{1}^{2}(a_{1}-w_{1})=0,$ (9)
$\displaystyle f_{2}:=a_{3}-w_{3}-x_{1}(a_{1}^{2}-w_{1}^{2})=0,$ (10)
$\displaystyle f_{3}:=b_{2}-w_{2}-y_{1}^{2}(b_{1}-w_{1})=0,$ (11)
$\displaystyle f_{4}:=b_{3}-w_{3}-y_{1}(b_{1}^{2}-w_{1}^{2})=0,$ (12)
$\displaystyle f_{5}:=c_{2}-w_{2}-z_{1}^{2}(c_{1}-w_{1})=0,$ (13)
$\displaystyle f_{6}:=c_{3}-w_{3}-z_{1}(c_{1}^{2}-w_{1}^{2})=0.$ (14)

In the following of this section, we divide our discussions into three
subsections.

###  3.1 $a_{1}=b_{1}$ or $a_{1}=c_{1}$ or $b_{1}=c_{1}$

We begin with the following lemma.

######  Lemma 3.4.

  1. (1)

If $a_{1}=b_{1}$, then $a_{2}\neq b_{2}$ and $a_{3}\neq b_{3}$.

  2. (2)

If $a_{1}=c_{1}$, then $a_{2}\neq c_{2}$ and $a_{3}\neq c_{3}$.

  3. (3)

If $b_{1}=c_{1}$, then $b_{2}\neq c_{2}$ and $b_{3}\neq c_{3}$.

###### Proof.

We will only prove the first statement, the proofs of the other two are
similar.

If $a_{2}=b_{2}$, then by Eqs. (9) and (11), we have $x_{1}^{2}=y_{1}^{2}$,
hence either $x_{1}=y_{1}$ or $x_{1}=-y_{1}$, which contradicts to Lemmas 3.1
and 3.3.

If $a_{3}=b_{3}$, then by Eqs. (10) and (12), we have $x_{1}=y_{1}$, which
contradicts to Lemma 3.1. ∎

Without loss of generality, we assume that $a_{1}=b_{1}$. Then Eqs. (9)-(14)
become

$\displaystyle f_{1}:=a_{2}-w_{2}-x_{1}^{2}(a_{1}-w_{1})=0,$ $\displaystyle
f_{2}:=a_{3}-w_{3}-x_{1}(a_{1}^{2}-w_{1}^{2})=0,$ $\displaystyle
f_{3}:=b_{2}-w_{2}-y_{1}^{2}(a_{1}-w_{1})=0,$ $\displaystyle
f_{4}:=b_{3}-w_{3}-y_{1}(a_{1}^{2}-w_{1}^{2})=0,$ $\displaystyle
f_{5}:=c_{2}-w_{2}-z_{1}^{2}(c_{1}-w_{1})=0,$ $\displaystyle
f_{6}:=c_{3}-w_{3}-z_{1}(c_{1}^{2}-w_{1}^{2})=0.$

Now we regard $f_{i}$ ($i=1,2,\dots,6$) as polynomials with variables
$x_{1},y_{1},z_{1},w_{1},w_{2},w_{3}$. By the MAGMA Program 1 in the Appendix
A, we can get that

$\displaystyle R(f_{1},f_{2};x_{1})=g_{1}\cdot(a_{1}-w_{1}),$ $\displaystyle
R(f_{3},f_{4};y_{1})=g_{2}\cdot(a_{1}-w_{1}),$ $\displaystyle
R(f_{5},f_{6};z_{1})=g_{3}\cdot(c_{1}-w_{1}).$

By Lemma 3.3, we have $a_{1}\neq w_{1}$ and $c_{1}\neq w_{1}$. Then
$g_{1}=g_{2}=g_{3}=0$ and

$\displaystyle R(g_{1},g_{2};w_{2})=g_{4}\cdot(a_{1}-w_{1})(a_{1}+w_{1})^{2},$
$\displaystyle R(g_{1},g_{3};w_{2})=g_{5}.$

By Lemmas 3.1 and 3.3, $a_{1}+w_{1}\neq 0$ and $a_{1}-w_{1}\neq 0$, then
$g_{4}=g_{5}=0$. Let $h=R(g_{4},g_{5};w_{3})$, then $h$ is a polynomial of
$w_{1}$ with degree $8$. We can write $h$ as $h=\sum_{i=0}^{8}h_{i}w_{1}^{i}$.
Then we can compute to get that

$\displaystyle h_{8}=-(a_{2}-b_{2})^{2}(a_{1}-c_{1}).$

By Lemma 3.4, $a_{2}\neq b_{2}$. If $a_{1}\neq c_{1}$, then there are at most
8 solutions for $w_{1}$. For any fixed $w_{1}$, $g_{4}$ is a polynomial of
$w_{3}$ with degree 1. We write $g_{4}$ as $g_{4}=s_{1}w_{3}+s_{0}$, where
$s_{1}=a_{3}-b_{3}\neq 0$. Hence there is at most $1$ solution for $w_{3}$. If
$w_{1}$ and $w_{3}$ are given, then all the remaining variables are uniquely
determined. Hence there are at most $8\ (=8\times 1)$ different sequences of
$(x,y,z,w)$ for this case.

If $a_{1}=c_{1}$, then we can compute to get that
$g_{5}=g_{6}\cdot(a_{1}-w_{1})(a_{1}+w_{1})^{2}$. Let
$h^{\prime}=R(g_{4},g_{6};w_{3})$, then $h^{\prime}$ is a polynomial of
$w_{1}$ with degree $3$. We can write $h^{\prime}$ as
$h^{\prime}=\sum_{i=0}^{3}k_{i}w_{1}^{i}$. Regarding $k_{i}$ ($i=0,1,2,3$) as
polynomials with variable $a_{2}$, then by the MAGMA Program 2 in the Appendix
A, we have

$\displaystyle
R(k_{0},k_{3};a_{2})=4(b_{3}-c_{3})^{2}(a_{3}-c_{3})(a_{3}-b_{3}).$

By Lemma 3.4, $R(k_{0},k_{3};a_{2})\neq 0$, then $k_{0}$ and $k_{3}$ cannot be
both zero. Hence there are at most 3 solutions for $w_{1}$. Similarly as
above, for any fixed $w_{1}$, there is at most $1$ solution for $w_{3}$. If
$w_{1}$ and $w_{3}$ are given, then all the remaining variables are uniquely
determined. Hence there are at most $3\ (=3\times 1)$ different sequences of
$(x,y,z,w)$ for this case.

Therefore, if $a_{1}=b_{1}$ or $a_{1}=c_{1}$ or $b_{1}=c_{1}$, then there are
at most $8$ different sequences of $(x,y,z,w)$.

###  3.2 $a_{1}\neq b_{1}$, $a_{1}\neq c_{1}$, $b_{1}\neq c_{1}$ and
$a_{2}=b_{2}$ or $a_{2}=c_{2}$ or $b_{2}=c_{2}$

Without loss of generality, we assume that $a_{2}=b_{2}$. Then Eqs. (9)-(14)
become

$\displaystyle f_{1}:=a_{2}-w_{2}-x_{1}^{2}(a_{1}-w_{1})=0,$ $\displaystyle
f_{2}:=a_{3}-w_{3}-x_{1}(a_{1}^{2}-w_{1}^{2})=0,$ $\displaystyle
f_{3}:=a_{2}-w_{2}-y_{1}^{2}(b_{1}-w_{1})=0,$ $\displaystyle
f_{4}:=b_{3}-w_{3}-y_{1}(b_{1}^{2}-w_{1}^{2})=0,$ $\displaystyle
f_{5}:=c_{2}-w_{2}-z_{1}^{2}(c_{1}-w_{1})=0,$ $\displaystyle
f_{6}:=c_{3}-w_{3}-z_{1}(c_{1}^{2}-w_{1}^{2})=0.$

Now we regard $f_{i}$ ($i=1,2,\dots,6$) as polynomials with variables
$x_{1},y_{1},z_{1},w_{1},w_{2},w_{3}$. By the MAGMA Program 3 in the Appendix
A, we can get that

$\displaystyle R(f_{1},f_{2};x_{1})=g_{1}\cdot(a_{1}-w_{1}),$ $\displaystyle
R(f_{3},f_{4};y_{1})=g_{2}\cdot(b_{1}-w_{1}),$ $\displaystyle
R(f_{5},f_{6};z_{1})=g_{3}\cdot(c_{1}-w_{1}).$

Note that $a$ and $w$ ($b$ and $w$, $c$ and $w$, resp.) have a common
neighbour, by Lemma 3.3, we have $a_{1}\neq w_{1}$ ($b_{1}\neq w_{1}$,
$c_{1}\neq w_{1}$, resp.). Then $g_{1}=g_{2}=g_{3}=0$ and

$\displaystyle R(g_{1},g_{2};w_{2})=g_{4},$ $\displaystyle
R(g_{1},g_{3};w_{2})=g_{5},$ $\displaystyle
R(g_{4},g_{5};w_{3})=h\cdot(a_{1}-w_{1})^{2}(a_{1}+w_{1})^{4},$

where $h$ is a polynomial of $w_{1}$ with degree $10$. By Lemmas 3.1 and 3.3,
$a_{1}\neq w_{1}$ and $a_{1}+w_{1}\neq 0$, then $h=0$. We can write $h$ as
$h=\sum_{i=0}^{10}h_{i}w_{1}^{i}$, where

$\displaystyle h_{10}=(a_{2}-c_{2})^{2}(a_{1}-b_{1})^{2}.$

If $a_{2}\neq c_{2}$, then $h_{10}\neq 0$. Hence there are at most 10
solutions for $w_{1}$. For any fixed $w_{1}$, $g_{4}$ and $g_{5}$ are
polynomials of $w_{3}$ with degree 2. We write $g_{4}$ and $g_{5}$ as
$g_{4}=\sum_{i=0}^{2}s_{i}w_{3}^{i}$ and $g_{5}=\sum_{i=0}^{2}t_{i}w_{3}^{i}$,
then $s_{2}=s_{2}^{\prime}\cdot(a_{1}-b_{1})$ and
$t_{2}=t_{2}^{\prime}\cdot(a_{1}-c_{1})$. We can compute to get that
$s_{2}^{\prime}-t_{2}^{\prime}=(b_{1}-c_{1})(a_{1}+b_{1}+c_{1}+w_{1})$. By
Lemmas 3.1 and 3.3, we have $s_{2}^{\prime}-t_{2}^{\prime}\neq 0$. Hence there
is at least one of $s_{2},t_{2}$ not being 0, then there are at most $2$
solutions for $w_{3}$. If $w_{1}$ and $w_{3}$ are given, then all the
remaining variables are uniquely determined. Hence there are at most $20\
(=10\times 2)$ different sequences of $(x,y,z,w)$ for this case.

If $a_{2}=c_{2}$, then $h_{i}=0$ for $i=6,7,8,9,10$. We can regard $h_{4}$ and
$h_{5}$ as polynomials with variable $a_{1}$. Then by the MAGMA Program 4 in
the Appendix A, we have

$\displaystyle
R(h_{4},h_{5};a_{1})=80(b_{1}-c_{1})^{2}(a_{3}-b_{3})^{4}(a_{3}-c_{3})^{4}(b_{3}-c_{3})^{4}.$

If $R(h_{4},h_{5};a_{1})\neq 0$, then at least one of $h_{4},h_{5}$ is not 0.
Hence there are at most 5 solutions for $w_{1}$. For any fixed $w_{1}$,
through a similar discussion as above, there are at most $2$ solutions for
$w_{3}$. If $w_{1}$ and $w_{3}$ are given, then all the remaining variables
are uniquely determined. Hence there are at most $10\ (=5\times 2)$ different
sequences of $(x,y,z,w)$ for this case.

If $R(h_{4},h_{5};a_{1})=0$, without loss of generality, we assume that
$a_{3}=b_{3}$. Then by the MAGMA Program 5 in the Appendix A, we have

$\displaystyle g_{4}=(a_{3}-w_{3})^{2}(a_{1}-b_{1})\cdot g_{4}^{\prime},$

where
$g_{4}^{\prime}=-w_{1}^{2}+(a_{1}+b_{1})w_{1}+a_{1}^{2}+a_{1}b_{1}+b_{1}^{2}$.
By Eq. (10), if $a_{3}=w_{3}$, then $a_{1}^{2}=w_{1}^{2}$, which is a
contradiction. Hence $a_{3}\neq w_{3}$ and $a_{1}\neq b_{1}$, then there are
at most 2 solutions for $w_{1}$. For any fixed $w_{1}$, $g_{5}$ is a
polynomial of $w_{3}$ with degree 2. We write $g_{5}$ as
$g_{5}=\sum_{i=0}^{2}t_{i}w_{3}^{i}$, then
$t_{2}=t_{2}^{\prime}\cdot(a_{1}-c_{1})$. We can compute to get that
$g_{4}^{\prime}-t_{2}^{\prime}=(b_{1}-c_{1})(a_{1}+b_{1}+c_{1}+w_{1})$. By
Lemmas 3.1 and 3.3, we have $g_{4}^{\prime}-t_{2}^{\prime}\neq 0$. Hence there
are at most $2$ solutions for $w_{3}$. If $w_{1}$ and $w_{3}$ are given, then
all the remaining variables are uniquely determined. Hence there are at most
$4\ (=2\times 2)$ different sequences of $(x,y,z,w)$ for this case.

Therefore, if $a_{1}\neq b_{1}$, $a_{1}\neq c_{1}$, $b_{1}\neq c_{1}$ and
$a_{2}=b_{2}$ or $a_{2}=c_{2}$ or $b_{2}=c_{2}$, then there are at most $20$
different sequences of $(x,y,z,w)$.

###  3.3 $a_{1}\neq b_{1}$, $a_{1}\neq c_{1}$, $b_{1}\neq c_{1}$, $a_{2}\neq
b_{2}$, $a_{2}\neq c_{2}$ and $b_{2}\neq c_{2}$

For this case, we begin with the following lemmas.

######  Lemma 3.5.

If $G_{p}$ contains a copy of $\theta_{3,3}$, which consists of the set of
edges $\\{da,db,dc,ax,by,cz,\\\ wx,wy,wz\\}$, then
$a_{1}y_{1}-a_{1}z_{1}-b_{1}x_{1}+b_{1}z_{1}+c_{1}x_{1}-c_{1}y_{1}=0$.

###### Proof.

We first consider the edges $da,ax,xw,wy,yb,bd$, which form a hexagon. By the
definition of $G_{p}$, we have

$\displaystyle d_{3}+a_{2}=d_{1}^{2}a_{1},$ $\displaystyle
a_{3}+d_{2}=a_{1}^{2}d_{1},$ (15) $\displaystyle a_{2}+x_{3}=a_{1}x_{1}^{2},$
$\displaystyle x_{2}+a_{3}=x_{1}a_{1}^{2},$ (16) $\displaystyle
x_{3}+w_{2}=x_{1}^{2}w_{1},$ $\displaystyle w_{3}+x_{2}=w_{1}^{2}x_{1},$ (17)
$\displaystyle w_{2}+y_{3}=w_{1}y_{1}^{2},$ $\displaystyle
y_{2}+w_{3}=y_{1}w_{1}^{2},$ (18) $\displaystyle y_{3}+b_{2}=y_{1}^{2}b_{1},$
$\displaystyle b_{3}+y_{2}=b_{1}^{2}y_{1},$ (19) $\displaystyle
b_{2}+d_{3}=b_{1}d_{1}^{2},$ $\displaystyle d_{2}+b_{3}=d_{1}b_{1}^{2}.$ (20)

Then we can compute to get that

$\displaystyle
f_{1}:=d_{1}^{2}a_{1}-a_{1}x_{1}^{2}+x_{1}^{2}w_{1}-w_{1}y_{1}^{2}+y_{1}^{2}b_{1}-b_{1}d_{1}^{2}=0,$
$\displaystyle
f_{2}:=d_{1}a_{1}^{2}-a_{1}^{2}x_{1}+x_{1}w_{1}^{2}-w_{1}^{2}y_{1}+y_{1}b_{1}^{2}-b_{1}^{2}d_{1}=0,$

where $f_{1}$ is from the left six equations of (15)-(20) and $f_{2}$ is from
the right six equations of (15)-(20). Regarding $f_{1},f_{2}$ as polynomials
with variables $a_{1},u_{1},v_{1},b_{1},x_{1},w_{1}$, we can compute to get
that

$\displaystyle R(f_{1},f_{2};b_{1})=$
$\displaystyle(a_{1}-w_{1})(x_{1}-y_{1})(d_{1}-y_{1})(d_{1}-x_{1})(d_{1}^{2}a_{1}+d_{1}^{2}w_{1}-d_{1}a_{1}x_{1}-d_{1}a_{1}y_{1}+$
$\displaystyle
d_{1}x_{1}w_{1}+d_{1}w_{1}y_{1}-a_{1}x_{1}^{2}-a_{1}x_{1}y_{1}-a_{1}y_{1}^{2}+x_{1}^{2}w_{1}+x_{1}w_{1}y_{1}-w_{1}y_{1}^{2}).$

By Lemma 3.3 and $f_{1}=f_{2}=0$, we have

$\displaystyle
d_{1}^{2}a_{1}+d_{1}^{2}w_{1}-d_{1}a_{1}x_{1}-d_{1}a_{1}y_{1}+d_{1}x_{1}w_{1}+d_{1}w_{1}y_{1}-a_{1}x_{1}^{2}-a_{1}x_{1}y_{1}-$
$\displaystyle
a_{1}y_{1}^{2}+x_{1}^{2}w_{1}+x_{1}w_{1}y_{1}-w_{1}y_{1}^{2}=0.$

Similarly, the edges $da,ax,xw,wz,zc,cd$ also form a hexagon, we have

$\displaystyle
d_{1}^{2}a_{1}+d_{1}^{2}w_{1}-d_{1}a_{1}x_{1}-d_{1}a_{1}z_{1}+d_{1}x_{1}w_{1}+d_{1}w_{1}z_{1}-a_{1}x_{1}^{2}-a_{1}x_{1}z_{1}-$
$\displaystyle
a_{1}z_{1}^{2}+x_{1}^{2}w_{1}+x_{1}w_{1}z_{1}-w_{1}z_{1}^{2}=0.$

From the above two equations, we get

$\displaystyle(d_{1}+x_{1})(w_{1}-a_{1})y_{1}-(w_{1}+a_{1})y_{1}^{2}=(d_{1}+x_{1})(w_{1}-a_{1})z_{1}-(w_{1}+a_{1})z_{1}^{2}.$

Then we can compute to get that

$\displaystyle\frac{d_{1}+x_{1}}{w_{1}+a_{1}}=\frac{y_{1}+z_{1}}{w_{1}-a_{1}}.$

By the symmetry of $\theta_{3,3}$, we have

$\displaystyle\frac{w_{1}+a_{1}}{d_{1}+x_{1}}=\frac{b_{1}+c_{1}}{d_{1}-x_{1}}.$

From the above two equations, we can get

$\displaystyle g_{1}=(y_{1}+z_{1})(b_{1}+c_{1})-(w_{1}-a_{1})(d_{1}-x_{1})=0.$

By the symmetry of $\theta_{3,3}$ again, we also have

$\displaystyle g_{2}=(x_{1}+z_{1})(a_{1}+c_{1})-(w_{1}-b_{1})(d_{1}-y_{1})=0,$
$\displaystyle g_{3}=(x_{1}+y_{1})(a_{1}+b_{1})-(w_{1}-c_{1})(d_{1}-z_{1})=0.$

Now we regard $g_{i}$ ($i=1,2,3$) as polynomials with variables $d_{1},w_{1}$.
By the MAGMA Program 6 in the Appendix A, we can get that

$\displaystyle R(g_{1},g_{2};d_{1})=h_{1}\cdot(a_{1}+b_{1}+c_{1}-w_{1}),$
$\displaystyle R(g_{1},g_{3};d_{1})=h_{2}\cdot(a_{1}+b_{1}+c_{1}-w_{1}).$

Note that $a_{1},b_{1},c_{1},w_{1}\in S$, then
$w_{1}\in\\{1,2,\dots,\frac{p-5}{6}\\}$, $w_{1}\equiv 1\pmod{3}$,
$a_{1}+b_{1}+c_{1}\in\\{3,\dots,\frac{p-5}{2}\\}$ and $a_{1}+b_{1}+c_{1}\equiv
0\pmod{3}$. Hence $a_{1}+b_{1}+c_{1}-w_{1}\neq 0$. Then $h_{1}=h_{2}=0$, we
can compute to get that
$R(h_{1},h_{2};w_{1})=(y_{1}+z_{1})(a_{1}y_{1}-a_{1}z_{1}-b_{1}x_{1}+b_{1}z_{1}+c_{1}x_{1}-c_{1}y_{1})=0$.
Hence $a_{1}y_{1}-a_{1}z_{1}-b_{1}x_{1}+b_{1}z_{1}+c_{1}x_{1}-c_{1}y_{1}=0$. ∎

######  Remark 3.6.

In the above proof, we do not need the condition $d_{1}\in S$ for $d\in V$.
Hence, if $d_{1}\in\mathbb{F}_{p}^{*}\backslash S$, then Lemma 3.5 still
holds.

By Lemma 3.3, if $d,a,b,c,x,y,z,w$ form a copy of $\theta_{3,3}$ with edge set
$\\{da,db,dc,ax,by,cz,wx,\\\ wy,wz\\}$, then $a_{3}\neq b_{3}$.

######  Claim 3.7.

If $a_{1}y_{1}-a_{1}z_{1}-b_{1}x_{1}+b_{1}z_{1}+c_{1}x_{1}-c_{1}y_{1}=0$ and
$a_{3}\neq b_{3}$, then there are at most $24$ different sequences of
$(x,y,z,w)$.

###### Proof.

Let
$f_{7}=a_{1}y_{1}-a_{1}z_{1}-b_{1}x_{1}+b_{1}z_{1}+c_{1}x_{1}-c_{1}y_{1}=0$,
then we regard $f_{7}$ and $f_{i}$ ($i=1,2,\dots,6$) in Eqs. (9)-(14) as
polynomials with variables $x_{1},y_{1},z_{1},w_{1},w_{2},w_{3}$. Let
$g_{1}=f_{1}-f_{3}$, $g_{2}=f_{1}-f_{5}$ and $g_{3}=f_{2}-f_{4}$. By the MAGMA
Program 7 in the Appendix A, we can get that

$\displaystyle R(g_{1},g_{2};w_{1})=g_{5},$ $\displaystyle
R(g_{1},g_{3};w_{1})=g_{6}\cdot(x_{1}-y_{1}),$ $\displaystyle
R(f_{7},g_{5};x_{1})=h_{1}\cdot(y_{1}-z_{1}),$ $\displaystyle
R(f_{7},g_{6};x_{1})=h_{2},$ $\displaystyle
R(h_{1},h_{2};z_{1})=(b_{1}-c_{1})^{3}(a_{1}-b_{1})^{6}(a_{1}y_{1}^{2}-b_{1}y_{1}^{2}-a_{2}+b_{2})^{2}\cdot
s,$

where $s$ is a polynomial of $y_{1}$ with degree $8$.

If $a_{1}y_{1}^{2}-b_{1}y_{1}^{2}-a_{2}+b_{2}=0$, by Eqs. (9) and (11), we
have

$\displaystyle 0$ $\displaystyle=f_{1}-f_{3}$
$\displaystyle=a_{2}-b_{2}-x_{1}^{2}(a_{1}-w_{1})+y_{1}^{2}(b_{1}-w_{1})$
$\displaystyle=a_{2}-b_{2}-(x_{1}^{2}-y_{1}^{2})(a_{1}-w_{1})+y_{1}^{2}(b_{1}-a_{1}).$

Then we have $(x_{1}^{2}-y_{1}^{2})(a_{1}-w_{1})=0$, which is a contradiction.
Hence $a_{1}y_{1}^{2}-b_{1}y_{1}^{2}-a_{2}+b_{2}\neq 0$.

We write $s=\sum_{i=0}^{8}s_{i}y_{1}^{i}$, then we can compute to get that
$s_{8}=s_{8}^{\prime}\cdot(b_{1}-c_{1})^{3}(a_{1}-c_{1})^{4}(a_{1}-b_{1})^{4}$
and
$s_{7}=s_{7}^{\prime}\cdot(b_{1}-c_{1})^{3}(a_{3}-b_{3})(a_{1}-c_{1})^{3}(a_{1}-b_{1})^{3}$.
We regard $s_{8}^{\prime}$ and $s_{7}^{\prime}$ as polynomials of $a_{1}$,
then by Lemma 3.1, we have
$R(s_{7}^{\prime},s_{8}^{\prime};a_{1})=(b_{1}+c_{1})(b_{1}+5c_{1})(b_{1}^{2}+b_{1}c_{1}+c_{1}^{2})\neq
0$. Hence there are at most $8$ solutions for $y_{1}$. For any given $y_{1}$,
$h_{1}$ is a polynomial of $z_{1}$ with degree 3. We write $h_{1}$ as
$h_{1}=\sum_{i=0}^{3}s_{i}z_{1}^{i}$, then
$s_{3}=(a_{1}-c_{1})(a_{1}-b_{1})^{2}\neq 0$. Hence, there are at most 3
solutions for $z_{1}$. If $y_{1}$ and $z_{1}$ are given, then all the
remaining variables are uniquely determined. Hence there are at most $24\
(=8\times 3)$ different sequences of $(x,y,z,w)$ for this case. ∎

Now we regard $f_{i}$ ($i=1,2,\dots,6$) in Eqs. (9)-(14) as polynomials with
variables $x_{1},y_{1},z_{1},w_{1},\\\ w_{2},w_{3}$. By the MAGMA Program 8 in
the Appendix A, we can get that

$\displaystyle R(f_{1},f_{2};x_{1})=g_{1}\cdot(a_{1}-w_{1}),$ $\displaystyle
R(f_{3},f_{4};y_{1})=g_{2}\cdot(b_{1}-w_{1}),$ $\displaystyle
R(f_{5},f_{6};z_{1})=g_{3}\cdot(c_{1}-w_{1}).$

By Lemma 3.3, we have $a_{1}\neq w_{1}$ and $c_{1}\neq w_{1}$. Then we can
compute to get that

$\displaystyle R(g_{1},g_{2};w_{2})=g_{4},$ $\displaystyle
R(g_{1},g_{3};w_{2})=g_{5},$ $\displaystyle
R(g_{4},g_{5};w_{3})=h\cdot(a_{1}-w_{1})^{2}(a_{1}+w_{1})^{4},$

where $h$ is a polynomial of $w_{1}$ with degree $10$. By Lemma 3.1,
$a_{1}+w_{1}\neq 0$, then $h=0$. We can write $h$ as
$h=\sum_{i=0}^{10}h_{i}w_{1}^{i}$.

If at least one of $h_{i}$ is not 0, then there are at most 10 solutions for
$w_{1}$. For any fixed $w_{1}$, $g_{4}$ and $g_{5}$ are polynomials of $w_{3}$
with degree 2. We write $g_{4}$ and $g_{5}$ as
$g_{4}=\sum_{i=0}^{2}s_{i}w_{3}^{i}$ and $g_{5}=\sum_{i=0}^{2}t_{i}w_{3}^{i}$,
then $s_{2}=s_{2}^{\prime}\cdot(a_{1}-b_{1})$ and
$t_{2}=t_{2}^{\prime}\cdot(a_{1}-c_{1})$. We can compute to get that
$s_{2}^{\prime}-t_{2}^{\prime}=(b_{1}-c_{1})(a_{1}+b_{1}+c_{1}+w_{1})$. By
Lemmas 3.1 and 3.3, we have $s_{2}^{\prime}-t_{2}^{\prime}\neq 0$. Hence there
is at least one of $s_{2},t_{2}$ not being 0, then there are at most $2$
solutions for $w_{3}$. If $w_{1}$ and $w_{3}$ are given, then all the
remaining variables are uniquely determined. Hence there are at most $20\
(=10\times 2)$ different sequences of $(x,y,z,w)$ for this case.

If $h_{i}=0$ for $0\leq i\leq 10$. We regard $h_{i}$ as polynomials with
variables $b_{2},c_{2},c_{3}$. We can compute to get that

$\displaystyle
h_{10}=(a_{1}b_{2}-a_{1}c_{2}-a_{2}b_{1}+a_{2}c_{1}+b_{1}c_{2}-b_{2}c_{1})^{2}.$

Let
$h_{10}^{\prime}=a_{1}b_{2}-a_{1}c_{2}-a_{2}b_{1}+a_{2}c_{1}+b_{1}c_{2}-b_{2}c_{1}.$
By the MAGMA Program 8 in the Appendix A, we can get that

$\displaystyle R(h_{10}^{\prime},h_{8};c_{2})=(a_{2}-b_{2})(a_{1}-b_{1})\cdot
k_{1},$ $\displaystyle
R(h_{10}^{\prime},h_{6};c_{2})=(a_{2}-b_{2})(a_{1}-b_{1})\cdot k_{2},$
$\displaystyle
R(k_{1},k_{2};c_{3})=(b_{1}-c_{1})^{4}(a_{1}-c_{1})^{4}(a_{1}-b_{1})^{4}\cdot
r_{1}^{2},$ $\displaystyle
R(k_{1},k_{2};b_{2})=(b_{1}-c_{1})^{2}(a_{1}-c_{1})^{2}(a_{1}-b_{1})\cdot
r_{2}^{2},$

where

$\displaystyle
r_{1}=a_{1}^{3}a_{2}-a_{1}^{3}b_{2}+a_{1}^{2}a_{2}b_{1}-a_{1}^{2}b_{1}b_{2}-a_{1}a_{2}b_{1}^{2}+a_{1}b_{1}^{2}b_{2}-a_{2}b_{1}^{3}-a_{3}^{2}+2a_{3}b_{3}+b_{1}^{3}b_{2}-b_{3}^{2},$
(21) $\displaystyle
r_{2}=a_{1}^{2}b_{3}-a_{1}^{2}c_{3}-a_{3}b_{1}^{2}+a_{3}c_{1}^{2}+b_{1}^{2}c_{3}-b_{3}c_{1}^{2}.$
(22)

We can also compute to get that

$\displaystyle R(h_{10}^{\prime},h_{8};b_{2})=(a_{2}-c_{2})(a_{1}-c_{1})\cdot
k_{3},$ $\displaystyle
R(h_{10}^{\prime},h_{6};b_{2})=(a_{2}-c_{2})(a_{1}-c_{1})\cdot k_{4},$
$\displaystyle
R(k_{3},k_{4};c_{3})=(b_{1}-c_{1})^{4}(a_{1}-c_{1})^{2}(a_{1}-b_{1})^{4}\cdot
r_{3}^{2},$

where

$\displaystyle r_{3}=$ $\displaystyle
a_{1}^{4}a_{2}-a_{1}^{4}c_{2}-2a_{1}^{2}a_{2}b_{1}^{2}+2a_{1}^{2}b_{1}^{2}c_{2}-a_{1}a_{3}^{2}+2a_{1}a_{3}b_{3}-a_{1}b_{3}^{2}+a_{2}b_{1}^{4}+a_{3}^{2}c_{1}-$
$\displaystyle 2a_{3}b_{3}c_{1}-b_{1}^{4}c_{2}+b_{3}^{2}c_{1}.$ (23)

Now we define $d_{1}:=\frac{a_{3}-b_{3}}{a_{1}^{2}-b_{1}^{2}}$,
$d_{2}:=a_{1}^{2}(\frac{a_{3}-b_{3}}{a_{1}^{2}-b_{1}^{2}})-a_{3}$, and
$d_{3}:=a_{1}(\frac{a_{3}-b_{3}}{a_{1}^{2}-b_{1}^{2}})^{2}-a_{2}$. Then by
$r_{1}=r_{2}=r_{3}=0$ (see Eqs. (21), (22) and (23)), it can be computed to
get that

$\displaystyle a_{2}+d_{3}=a_{1}d_{1}^{2},$ $\displaystyle
a_{3}+d_{2}=a_{1}^{2}d_{1},$ $\displaystyle b_{2}+d_{3}=b_{1}d_{1}^{2},$
$\displaystyle b_{3}+d_{2}=b_{1}^{2}d_{1},$ $\displaystyle
c_{2}+d_{3}=c_{1}d_{1}^{2},$ $\displaystyle c_{3}+d_{2}=c_{1}^{2}d_{1}.$

Then the vertex $d=(d_{1},d_{2},d_{3})$ is a common neighbour of $a,b,c$.
Hence the vertex $d,a,b,c,x,\\\ y,z,w$ form a $\theta_{3,3}$, by Lemma 3.5 and
Claim 3.7, there are at most $24$ different sequences of $(x,y,z,w)$ for this
case.

######  Remark 3.8.

Note that $d_{1}$ may not be in the set $S$, and then $d\not\in V$, but by
Remark 3.6, we still have the same result. Actually, we do not need the
notation $\theta_{3,3}$. If the point $d=(d_{1},d_{2},d_{3})$ satisfies the
above equations with $a,b,c$, then we have the statements of Lemma 3.5.

Therefore, if $a_{1}\neq b_{1}$, $a_{1}\neq c_{1}$, $b_{1}\neq c_{1}$,
$a_{2}\neq b_{2}$, $a_{2}\neq c_{2}$ and $b_{2}\neq c_{2}$, then there are at
most $24$ different sequences of $(x,y,z,w)$.

###  3.4 Proof of Theorem 1.2

From the previous discussions, for any given $a,b,c\in V$, there are at most
$24$ different sequences of $(x,y,z,w)$ such that $ax,xw,by,yw,cz,zw$ are
edges in $G_{p}$. Hence $G_{p}$ is $K_{3,25}^{\prime}$-free.

##  4 Construction of $\Theta_{3,217}^{B}$-free linear hypergraphs

In this section, we describe an algebraic construction of $3$-uniform linear
hypergraph with no copy of $\Theta_{3,217}^{B}$ having $n$ vertices and
$\Omega(n^{\frac{4}{3}})$ edges.

Let $p$ be a sufficiently large prime number, $\mathbb{F}_{p}$ be the finite
field of order $p$. Let

$\displaystyle T_{1}=\\{2,3,\dots,\frac{p-1}{2}\\},$ $\displaystyle
T_{2}=\\{\frac{p+3}{2},\dots,p-1\\},$ $\displaystyle
T_{3}=\mathbb{F}_{p}\backslash\\{-x^{2}:x\in\mathbb{F}_{p}\\},$ $\displaystyle
T_{4}=\\{x:x\in\mathbb{F}_{p},x^{2}-4x+1=0\\}\cup\\{x:x\in\mathbb{F}_{p},3x-1=0\\}\cup\\{x:x\in\mathbb{F}_{p},3x-2=0\\},$
$\displaystyle
T_{5}=\\{x:x\in\mathbb{F}_{p},x^{5}-\frac{12757}{10872}x^{4}+\frac{1123}{3624}x^{3}+\frac{289}{1359}x^{2}-\frac{49}{453}x-\frac{2}{151}=0\\}.$

Since $p$ is a sufficiently large prime, then the above definition of $T_{i}$
is well-defined. Note that $T_{1}\cup
T_{2}\cup\\{0,1,\frac{p+1}{2}\\}=\mathbb{F}_{p}$ and $|T_{3}|=\frac{p-1}{2}$.
Then there exists $i\in\\{1,2\\}$ such that $|T_{i}\cap
T_{3}|\geq\frac{p-7}{4}$. Without loss of generality, we assume that
$|T_{1}\cap T_{3}|\geq\frac{p-7}{4}$. Let $S_{1}=(T_{1}\cap
T_{3})\backslash(T_{4}\cup T_{5})$, $S_{2}=\mathbb{F}_{p}\backslash\\{0,1\\}$.
Since $|T_{4}|\leq 4$ and $|T_{5}|\leq 5$, then $|S_{1}|\geq\frac{p-43}{4}$.

Now we are ready to construct a $3$-partite $3$-uniform linear hypergraph as
follows. For $1\leq i\leq 3$, let $V_{i}=S_{1}\times S_{2}\times
S_{2}\times\\{i\\}$. The union $V_{1}\cup V_{2}\cup V_{3}$ will be the vertex
set of our hypergraph. Given $x_{1},x_{2},x_{3}\in S_{1}$ and
$a\in\mathbb{F}_{p}^{*}$, let

$\displaystyle
e(x_{1},x_{2},x_{3},a)=\\{(x_{1},x_{2}x_{3}+a,x_{2}^{2}x_{3}+a,1),(x_{2},x_{3}x_{1}+a,x_{3}^{2}x_{1}+a,2),(x_{3},x_{1}x_{2}+a,x_{1}^{2}x_{2}+a,3)\\}.$

######  Definition 4.1.

We define $\mathcal{H}$ to be the $3$-uniform hypergraph with vertex set

$\displaystyle V(\mathcal{H})=\\{(b,c,d,i):b\in S_{1},c,d\in S_{2},1\leq i\leq
3\\}$

and edge set

$\displaystyle
E(\mathcal{H})=\\{e(x_{1},x_{2},x_{3},a):e(x_{1},x_{2},x_{3},a)\subseteq
V(\mathcal{H})\\}.$

######  Proposition 4.2.

$\mathcal{H}$ is a linear hypergraph.

###### Proof.

Let $x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\in S_{1}$ and
$a,b\in\mathbb{F}_{p}^{*}$. Assume $|e(x_{1},x_{2},x_{3},a)\cap
e(y_{1},y_{2},y_{3},b)|=2$, without loss of generality, suppose that the first
two vertices are the same. Then we have

$\displaystyle x_{1}=y_{1},$ (24) $\displaystyle x_{2}x_{3}+a=y_{2}y_{3}+b,$
(25) $\displaystyle x_{2}^{2}x_{3}+a=y_{2}^{2}y_{3}+b,$ (26) $\displaystyle
x_{2}=y_{2},$ (27) $\displaystyle x_{3}x_{1}+a=y_{3}y_{1}+b,$ (28)
$\displaystyle x_{3}^{2}x_{1}+a=y_{3}^{2}y_{1}+b.$ (29)

Substituting $x_{2}=y_{2}$ (Eq. (27)) into Eqs. (25) and (26), then computing
Eq. (25)-Eq. (26), we have

$(x_{2}-x_{2}^{2})x_{3}=(x_{2}-x_{2}^{2})y_{3}.$

Note that $x_{2}\neq 0,1$, we get that $x_{3}=y_{3}$, and then $a=b$. Hence
$e(x_{1},x_{2},x_{3},a)=e(y_{1},y_{2},y_{3},b)$. Therefore $\mathcal{H}$ is
linear. ∎

It is easy to see that the number of vertices of $\mathcal{H}$ is
$n:=3|S_{1}|(p-2)^{2}$, and there are at least
$|S_{1}|^{3}(p-13)=\Omega(n^{\frac{4}{3}})$ edges in $\mathcal{H}$. In the
following of this section, we will prove that $\mathcal{H}$ is
$\Theta_{3,217}^{B}$-free.

We call a _Berge $3$-path_ $v_{1},e_{1},v_{2},e_{2},v_{3},e_{3},v_{4}$ of type
$(i_{1},i_{2},i_{3},i_{4})$ if $v_{j}\in V_{i_{j}}$ for $1\leq j\leq 4$, and a
_Berge $4$-cycle_ $v_{1},e_{1},v_{2},e_{2},v_{3},e_{3},v_{4},e_{4},v_{1}$ of
type $(i_{1},i_{2},i_{3},i_{4})$ if $v_{j}\in V_{i_{j}}$ for $1\leq j\leq 4$.

By symmetry, without loss of generality, we only need to consider three types
of Berge $3$-paths: $(1,2,1,2)$-type, $(1,2,3,1)$-type and $(1,2,3,2)$-type.
Indeed, we will upper bound the number of Berge 3-paths of the above three
types for any given endpoints. In the following, we divide our discussions
into three subsections according to the types.

###  4.1 $(1,2,1,2)$-type Berge $3$-paths

We begin with the following lemma.

######  Lemma 4.3.

There is no $(1,2,1,2)$-type Berge $4$-cycle in $\mathcal{H}$.

###### Proof.

Assume to the contrary, suppose
$(u_{1},v_{1},w_{1},1),e(x_{1},x_{2},x_{3},a_{1}),(u_{2},v_{2},w_{2},2),e(y_{1},y_{2},y_{3},a_{2}),\\\
(u_{3},v_{3},w_{3},1),e(z_{1},z_{2},z_{3},a_{3}),(u_{4},v_{4},w_{4},2),e(t_{1},t_{2},t_{3},a_{4}),(u_{1},v_{1},w_{1},1)$
form a copy of Berge $4$-cycle. Then by the definition of hypergraph
$\mathcal{H}$, we have

$\displaystyle u_{1}=x_{1}=t_{1},$ (30) $\displaystyle
v_{1}=x_{2}x_{3}+a_{1}=t_{2}t_{3}+a_{4},$ (31) $\displaystyle
w_{1}=x_{2}^{2}x_{3}+a_{1}=t_{2}^{2}t_{3}+a_{4},$ (32) $\displaystyle
u_{2}=x_{2}=y_{2},$ (33) $\displaystyle
v_{2}=x_{3}x_{1}+a_{1}=y_{3}y_{1}+a_{2},$ (34) $\displaystyle
w_{2}=x_{3}^{2}x_{1}+a_{1}=y_{3}^{2}y_{1}+a_{2},$ (35) $\displaystyle
u_{3}=y_{1}=z_{1},$ (36) $\displaystyle
v_{3}=y_{2}y_{3}+a_{2}=z_{2}z_{3}+a_{3},$ (37) $\displaystyle
w_{3}=y_{2}^{2}y_{3}+a_{2}=z_{2}^{2}z_{3}+a_{3},$ (38) $\displaystyle
u_{4}=z_{2}=t_{2},$ (39) $\displaystyle
v_{4}=z_{3}z_{1}+a_{3}=t_{3}t_{1}+a_{4},$ (40) $\displaystyle
w_{4}=z_{3}^{2}z_{1}+a_{3}=t_{3}^{2}t_{1}+a_{4}.$ (41)

We can compute to get the following equations.

$\displaystyle
f_{1}:=x_{2}x_{3}-x_{3}x_{1}+t_{3}x_{1}-z_{2}t_{3}+z_{2}z_{3}-z_{3}y_{1}+y_{3}y_{1}-x_{2}y_{3}=0,$
$\displaystyle f_{2}:=x_{2}x_{3}-x_{2}^{2}x_{3}-z_{2}t_{3}+z_{2}^{2}t_{3}=0,$
$\displaystyle f_{3}:=x_{3}x_{1}-x_{3}^{2}x_{1}-y_{3}y_{1}+y_{3}^{2}y_{1}=0,$
$\displaystyle f_{4}:=z_{3}y_{1}-z_{3}^{2}y_{1}-t_{3}x_{1}+t_{3}^{2}x_{1}=0,$
$\displaystyle f_{5}:=x_{2}y_{3}-x_{2}^{2}y_{3}-z_{2}z_{3}+z_{2}^{2}z_{3}=0,$

where $f_{1}$ is from Eqs. (30), (31), (33), (34), (36), (37), (39) and (40),
$f_{2}$ is from Eqs. (31), (32) and (39), $f_{3}$ is from Eqs. (34) and (35),
$f_{4}$ is from Eqs. (30), (36) (40) and (41), and $f_{5}$ is from Eqs. (33),
(37) and (38).

Regarding $f_{i}$ as polynomials with variables
$x_{1},x_{2},x_{3},y_{1},y_{3},z_{2},z_{3},t_{3}$, we can compute to get the
following polynomials.

$\displaystyle g_{1}=R(f_{3},f_{4};x_{1}),$ $\displaystyle
g_{2}=R(f_{2},f_{5};x_{2}),$ $\displaystyle h=R(g_{1},g_{2};x_{3}).$

By the MAGMA Program 9 in the Appendix B, the polynomial $h$ can be factorized
as

$\displaystyle
h=t_{3}^{2}z_{3}^{2}z_{2}^{4}y_{3}^{2}y_{1}^{2}(z_{3}-t_{3})^{2}(z_{2}-1)^{4}(y_{3}-z_{3})^{2}.$

Since $h$ is obtained from $f_{i}$, then $h$ must be $0$. Hence we have
$z_{2}=1$ or $z_{3}=t_{3}$ or $y_{3}=z_{3}$.

If $z_{2}=1$, then $u_{4}=1$, which contradicts to the fact that
$(u_{4},v_{4},w_{4},2)\in V_{2}$ by the definition of $S_{1}$.

If $z_{3}=t_{3}$, then from Eqs. (40) and (41), we have
$z_{1}(z_{3}-z_{3}^{2})=t_{1}(z_{3}-z_{3}^{2})$. Note that
$z_{3}-z_{3}^{2}\neq 0$, then $z_{1}=t_{1}$, and so $a_{3}=a_{4}$. This leads
to $e(z_{1},z_{2},z_{3},a_{3})=e(t_{1},t_{2},t_{3},a_{4})$, which is a
contradiction.

If $y_{3}=z_{3}$, then from Eqs. (37) and (38), we have
$y_{2}-y_{2}^{2}=z_{2}-z_{2}^{2}\neq 0$. Since $x_{2}=y_{2}$ and
$z_{2}=t_{2}$, then $x_{2}-x_{2}^{2}=t_{2}-t_{2}^{2}$. From Eqs. (31) and
(32), we have $x_{3}=t_{3}$. Substituting the equations $x_{3}=t_{3}$ and
$y_{3}=z_{3}$ to $f_{1}$, we get that

$\displaystyle(x_{2}-z_{2})(x_{3}-y_{3})=0.$

If $x_{3}=y_{3}$, then we have $z_{3}=t_{3}$, which is impossible. If
$x_{2}=z_{2}$, then $x_{2}=t_{2}$, and so $a_{1}=a_{4}$, this leads to
$e(x_{1},x_{2},x_{3},a_{1})=e(t_{1},t_{2},t_{3},a_{4})$, which is a
contradiction. Hence there is no $(1,2,1,2)$-type Berge $4$-cycle in
$\mathcal{H}$. ∎

Now we consider $(1,2,1,2)$-type Berge $3$-path. For any given
$(b_{1},c_{1},d_{1},1)\in V_{1},(b_{2},c_{2},d_{2},2)\in V_{2}$, suppose there
exist $(u_{1},v_{1},w_{1},2)\in V_{2},(u_{2},v_{2},w_{2},1)\in V_{1}$ and
$e(x_{1},x_{2},x_{3},a_{1}),e(y_{1},y_{2},y_{3},a_{2}),\\\
e(z_{1},z_{2},z_{3},a_{3})$ such that
$(b_{1},c_{1},d_{1},1),e(x_{1},x_{2},x_{3},a_{1}),(u_{1},v_{1},w_{1},2),e(y_{1},y_{2},y_{3},a_{2}),(u_{2},v_{2},w_{2},1),\\\
e(z_{1},z_{2},z_{3},a_{3}),(b_{2},c_{2},d_{2},2)$ form a copy of Berge
$3$-path.

Then by the definition of hypergraph $\mathcal{H}$, we have

$\displaystyle b_{1}=x_{1},$ (42) $\displaystyle c_{1}=x_{2}x_{3}+a_{1},$ (43)
$\displaystyle d_{1}=x_{2}^{2}x_{3}+a_{1},$ (44) $\displaystyle
u_{1}=x_{2}=y_{2},$ (45) $\displaystyle
v_{1}=x_{3}x_{1}+a_{1}=y_{3}y_{1}+a_{2},$ (46) $\displaystyle
w_{1}=x_{3}^{2}x_{1}+a_{1}=y_{3}^{2}y_{1}+a_{2},$ (47) $\displaystyle
b_{2}=z_{2},$ (48) $\displaystyle c_{2}=z_{3}z_{1}+a_{3},$ (49) $\displaystyle
d_{2}=z_{3}^{2}z_{1}+a_{3},$ (50) $\displaystyle u_{2}=y_{1}=z_{1},$ (51)
$\displaystyle v_{2}=y_{2}y_{3}+a_{2}=z_{2}z_{3}+a_{3},$ (52) $\displaystyle
w_{2}=y_{2}^{2}y_{3}+a_{2}=z_{2}^{2}z_{3}+a_{3}.$ (53)

Then we have the following equations.

$\displaystyle f_{1}:=x_{2}x_{3}+a_{1}-c_{1}=0,$ $\displaystyle
f_{2}:=x_{2}^{2}x_{3}+a_{1}-d_{1}=0,$ $\displaystyle
f_{3}:=z_{3}y_{1}+a_{3}-c_{2}=0,$ $\displaystyle
f_{4}:=z_{3}^{2}y_{1}+a_{3}-d_{2}=0,$ $\displaystyle
f_{5}:=x_{3}b_{1}+a_{1}-y_{3}y_{1}-a_{2}=0,$ $\displaystyle
f_{6}:=x_{3}^{2}b_{1}+a_{1}-y_{3}^{2}y_{1}-a_{2}=0,$ $\displaystyle
f_{7}:=x_{2}y_{3}+a_{2}-b_{2}z_{3}-a_{3}=0,$ $\displaystyle
f_{8}:=x_{2}^{2}y_{3}+a_{2}-b_{2}^{2}z_{3}-a_{3}=0,$

where $f_{1}$ is from Eq. (43), $f_{2}$ is from Eq. (44), $f_{3}$ is from Eqs.
(49) and (51), $f_{4}$ is from Eqs. (50) and (51), $f_{5}$ is from Eqs. (42)
and (46), $f_{6}$ is from Eqs. (42) and (47), $f_{7}$ is from Eqs. (45), (48)
and (52), $f_{8}$ is from Eqs. (45), (48) and (53).

######  Lemma 4.4.

  * (1)

$b_{i},c_{i},d_{i},u_{i},v_{i},w_{i},x_{j},y_{j},z_{j}\not\in\\{0,1\\}$ for
$1\leq i\leq 2$ and $1\leq j\leq 3$,

  * (2)

$c_{1}\neq d_{1}$, $x_{2}\neq b_{2}$, $c_{2}\neq d_{2}$,

  * (3)

$x_{2}+b_{2}\neq 1$, $x_{2}^{2}-x_{2}+c_{1}-d_{1}\neq 0$, $b_{1}+b_{2}^{2}\neq
0$.

###### Proof.

All the statements are immediately from the definition of $\mathcal{H}$. We
will only prove $x_{2}^{2}-x_{2}+c_{1}-d_{1}\neq 0$. If
$x_{2}^{2}-x_{2}+c_{1}-d_{1}=0$, then by the equations $f_{1}$ and $f_{2}$, we
have $c_{1}-d_{1}=(x_{2}-x_{2}^{2})x_{3}$, then $x_{3}=1$, which is a
contradiction. ∎

######  Remark 4.5.

When we consider the resultant of two polynomials, we can divide those nonzero
factors first.

Now we regard $f_{i}$ as polynomials with variables
$x_{2},x_{3},y_{1},y_{3},z_{3},a_{1},a_{2},a_{3}$. We can compute to get the
following polynomials.

$\displaystyle g_{1}=R(f_{1},f_{2};a_{1}),$ $\displaystyle
g_{2}=R(f_{5},f_{6};a_{1}),$ $\displaystyle g_{3}=R(f_{1},f_{5};a_{1}),$
$\displaystyle g_{4}=R(f_{3},f_{4};a_{3}),$ $\displaystyle
g_{5}=R(f_{7},f_{8};a_{3}),$ $\displaystyle g_{6}=R(f_{3},f_{7};a_{3}),$
$\displaystyle g_{7}=R(g_{3},g_{6};a_{2}),$ $\displaystyle
g_{8}=R(g_{1},g_{2};x_{3}),$ $\displaystyle g_{9}=R(g_{1},g_{7};x_{3}),$
$\displaystyle g_{10}=R(g_{4},g_{5};z_{3}),$ $\displaystyle
g_{11}=R(g_{5},g_{9};z_{3}),$ $\displaystyle g_{12}=R(g_{8},g_{10};y_{1}),$
$\displaystyle g_{13}=R(g_{8},g_{11};y_{1}).$

By the MAGMA Program 10 in the Appendix B, the polynomials $g_{12}$ and
$g_{13}$ can be factorized as

$\displaystyle g_{12}=y_{3}x_{2}(x_{2}-1)g_{14},$ $\displaystyle
g_{13}=y_{3}x_{2}(x_{2}-1)g_{15}.$

Finally, we can get that

$\displaystyle
R(g_{14},g_{15};y_{3})=b_{1}x_{2}^{2}(c_{1}-d_{1})(x_{2}-1)^{2}(x_{2}-b_{2})(x_{2}+b_{2}-1)(x_{2}^{2}-x_{2}+c_{1}-d_{1})g_{16},$

where $g_{16}$ is a polynomial of $x_{2}$ with degree $4$.

By Lemma 4.4, we have
$b_{1}x_{2}^{2}(c_{1}-d_{1})(x_{2}-1)^{2}(x_{2}-b_{2})(x_{2}+b_{2}-1)(x_{2}^{2}-x_{2}+c_{1}-d_{1})\neq
0$. Since $g_{16}$ is obtained from $f_{i}$, then $g_{16}=0$. Write $g_{16}$
as $g_{16}=h_{4}x_{2}^{4}+h_{3}x_{2}^{3}+h_{2}x_{2}^{2}+h_{1}x_{2}+h_{0}$. We
claim that $h_{4},h_{3},h_{2},h_{1},h_{0}$ cannot be all $0$. Assume to the
contrary, we regard $h_{i}$ as polynomials with variables
$b_{1},c_{1},d_{1},b_{2},c_{2},d_{2}$. $h_{0}$ can be factorized as follows.

$\displaystyle h_{0}=$
$\displaystyle(-b_{1}c_{1}^{2}+2b_{1}c_{1}d_{1}-b_{1}c_{1}b_{2}^{2}+b_{1}c_{1}b_{2}-b_{1}d_{1}^{2}+b_{1}d_{1}b_{2}^{2}-b_{1}d_{1}b_{2}-b_{2}^{4}c_{2}+b_{2}^{4}d_{2}+2b_{2}^{3}c_{2}-2b_{2}^{3}d_{2}-$
$\displaystyle b_{2}^{2}c_{2}+b_{2}^{2}d_{2})\cdot h_{5}.$

Claim
$g_{17}:=-b_{1}c_{1}^{2}+2b_{1}c_{1}d_{1}-b_{1}c_{1}b_{2}^{2}+b_{1}c_{1}b_{2}-b_{1}d_{1}^{2}+b_{1}d_{1}b_{2}^{2}-b_{1}d_{1}b_{2}-b_{2}^{4}c_{2}+b_{2}^{4}d_{2}+2b_{2}^{3}c_{2}-2b_{2}^{3}d_{2}-b_{2}^{2}c_{2}+b_{2}^{2}d_{2}\neq
0.$

###### Proof of the claim.

If $g_{17}=0$, by the MAGMA Program 11 in the Appendix B, we have

$\displaystyle R(g_{17},h_{1};d_{2})=$ $\displaystyle
b_{2}^{3}(b_{2}-1)^{3}(c_{1}-d_{1})b_{1}(b_{1}c_{1}-b_{1}d_{1}-c_{1}b_{2}^{2}+d_{1}b_{2}+b_{2}^{2}c_{2}-b_{2}c_{2}),$
$\displaystyle R(g_{17},h_{1};c_{2})=$ $\displaystyle
b_{2}^{4}(b_{2}-1)^{4}(c_{1}-d_{1})b_{1}(b_{1}c_{1}^{2}-2b_{1}c_{1}d_{1}+b_{1}d_{1}^{2}+c_{1}b_{2}^{4}-c_{1}b_{2}^{3}-d_{1}b_{2}^{3}+d_{1}b_{2}^{2}-b_{2}^{4}d_{2}$
$\displaystyle+2b_{2}^{3}d_{2}-b_{2}^{2}d_{2}).$

Hence

$\displaystyle
b_{1}c_{1}-b_{1}d_{1}-c_{1}b_{2}^{2}+d_{1}b_{2}+b_{2}^{2}c_{2}-b_{2}c_{2}=0,$
$\displaystyle
b_{1}c_{1}^{2}-2b_{1}c_{1}d_{1}+b_{1}d_{1}^{2}+c_{1}b_{2}^{4}-c_{1}b_{2}^{3}-d_{1}b_{2}^{3}+d_{1}b_{2}^{2}-b_{2}^{4}d_{2}+2b_{2}^{3}d_{2}-b_{2}^{2}d_{2}=0.$

Let
$t_{1}=b_{1},t_{2}=b_{2},t_{3}=\frac{c_{1}-d_{1}}{b_{2}-b_{2}^{2}},a_{4}=\frac{d_{1}-b_{2}c_{1}}{1-b_{2}}$.
Then it is easy to get that $(b_{1},c_{1},d_{1},1),(b_{2},c_{2},d_{2},2)\in
e(t_{1},t_{2},t_{3},a_{4})$. Hence there exists a $(1,2,1,2)$-type Berge
$4$-cycle in $\mathcal{H}$, which contradicts to Lemma 4.3. This completes the
proof. ∎

Now we can compute to get that

$\displaystyle
R(h_{1},h_{5};c_{1})=b_{2}^{6}b_{1}^{3}(c_{2}-d_{2})^{2}(b_{2}-1)^{6}(b_{1}+b_{2}^{2})^{2}.$

By Lemma 4.4, we have $R(h_{1},h_{5};c_{1})\neq 0$, which is a contradiction.
Hence $h_{4},h_{3},h_{2},h_{1},h_{0}$ cannot be all $0$. Note that
$g_{16}=h_{4}x_{2}^{4}+h_{3}x_{2}^{3}+h_{2}x_{2}^{2}+h_{1}x_{2}+h_{0}$, then
there are at most $4$ solutions for $x_{2}$.

Now for any fixed $x_{2}$, we consider the polynomial $g_{15}$, which is a
polynomial of $y_{3}$ with degree $2$. We write $g_{15}$ as
$g_{15}=\sum_{i=0}^{2}l_{i}y_{3}^{i}$, where
$l_{2}=b_{2}x_{2}^{3}(x_{2}-1)(x_{2}-b_{2})\neq 0$. Hence there are at most
$2$ solution for $y_{3}$ when $x_{2}$ is given. If $x_{2}$ and $y_{3}$ are
given, then all the remaining variables are uniquely determined.

Hence, for any given $(b_{1},c_{1},d_{1},1)\in V_{1},(b_{2},c_{2},d_{2},2)\in
V_{2}$, there are at most $4\times 2=8$ Berge $3$-paths of $(1,2,1,2)$-type
with $(b_{1},c_{1},d_{1},1),(b_{2},c_{2},d_{2},2)$ being its end core
vertices.

###  4.2 $(1,2,3,1)$-type Berge $3$-paths

For any given $(b_{1},c_{1},d_{1},1),(b_{2},c_{2},d_{2},1)\in V_{1}$, suppose
there exist $(u_{1},v_{1},w_{1},2)\in V_{2},(u_{2},v_{2},w_{2},3)\in V_{3}$
and
$e(x_{1},x_{2},x_{3},a_{1}),e(y_{1},y_{2},y_{3},a_{2}),e(z_{1},z_{2},z_{3},a_{3})$
such that $(b_{1},c_{1},d_{1},1),e(x_{1},x_{2},x_{3},a_{1}),\\\
(u_{1},v_{1},w_{1},2),e(y_{1},y_{2},y_{3},a_{2}),(u_{2},v_{2},w_{2},3),e(z_{1},z_{2},z_{3},a_{3}),(b_{2},c_{2},d_{2},1)$
form a copy of Berge $3$-path.

Then by the definition of hypergraph $\mathcal{H}$, we have

$\displaystyle b_{1}=x_{1},$ (54) $\displaystyle c_{1}=x_{2}x_{3}+a_{1},$ (55)
$\displaystyle d_{1}=x_{2}^{2}x_{3}+a_{1},$ (56) $\displaystyle
u_{1}=x_{2}=y_{2},$ (57) $\displaystyle
v_{1}=x_{3}x_{1}+a_{1}=y_{3}y_{1}+a_{2},$ (58) $\displaystyle
w_{1}=x_{3}^{2}x_{1}+a_{1}=y_{3}^{2}y_{1}+a_{2},$ (59) $\displaystyle
b_{2}=z_{1},$ (60) $\displaystyle c_{2}=z_{2}y_{3}+a_{3},$ (61) $\displaystyle
d_{2}=z_{2}^{2}y_{3}+a_{3},$ (62) $\displaystyle u_{2}=y_{3}=z_{3},$ (63)
$\displaystyle v_{2}=y_{1}y_{2}+a_{2}=z_{1}z_{2}+a_{3},$ (64) $\displaystyle
w_{2}=y_{1}^{2}y_{2}+a_{2}=z_{1}^{2}z_{2}+a_{3}.$ (65)

Then we can get the following equations.

$\displaystyle f_{1}:=x_{2}x_{3}+a_{1}-c_{1}=0,$ (66) $\displaystyle
f_{2}:=x_{2}^{2}x_{3}+a_{1}-d_{1}=0,$ (67) $\displaystyle
f_{3}:=z_{2}y_{3}+a_{3}-c_{2}=0,$ (68) $\displaystyle
f_{4}:=z_{2}^{2}y_{3}+a_{3}-d_{2}=0,$ (69) $\displaystyle
f_{5}:=x_{3}b_{1}+a_{1}-y_{3}y_{1}-a_{2}=0,$ (70) $\displaystyle
f_{6}:=x_{3}^{2}b_{1}+a_{1}-y_{3}^{2}y_{1}-a_{2}=0,$ (71) $\displaystyle
f_{7}:=y_{1}x_{2}+a_{2}-b_{2}z_{2}-a_{3}=0,$ (72) $\displaystyle
f_{8}:=y_{1}^{2}x_{2}+a_{2}-b_{2}^{2}z_{2}-a_{3}=0,$ (73)

where $f_{1}$ is from Eq. (55), $f_{2}$ is from Eq. (56), $f_{3}$ is from Eq.
(61), $f_{4}$ is from Eq. (62), $f_{5}$ is from Eqs. (54) and (58), $f_{6}$ is
from Eqs. (54) and (59), $f_{7}$ is from Eqs. (57), (60) and (64), $f_{8}$ is
from Eqs. (57), (60) and (65).

######  Lemma 4.6.

  * (1)

$b_{i},c_{i},d_{i},u_{i},v_{i},w_{i},x_{j},y_{j},z_{j}\not\in\\{0,1\\}$ for
$1\leq i\leq 2$ and $1\leq j\leq 3$,

  * (2)

$c_{1}\neq d_{1}$, $c_{2}\neq d_{2}$, $b_{1}+b_{2}\neq 1$,

  * (3)

$b_{1}^{2}-4b_{1}+1\neq 0$, $2b_{2}\neq 1$, $3b_{2}\neq 1$,

  * (4)

$b_{2}^{5}-\frac{12757}{10872}b_{2}^{4}+\frac{1123}{3624}b_{2}^{3}+\frac{289}{1359}b_{2}^{2}-\frac{49}{453}b_{2}-\frac{2}{151}\neq
0$.

###### Proof.

All the statements are immediately from the definition of $\mathcal{H}$. ∎

Now we regard $f_{i}$ as polynomials with variables
$x_{2},x_{3},y_{1},y_{3},z_{2},a_{1},a_{2},a_{3}$. We can get the following
polynomials.

$\displaystyle g_{1}=R(f_{1},f_{2};a_{1}),$ $\displaystyle
g_{2}=R(f_{5},f_{6};a_{1}),$ $\displaystyle g_{3}=R(f_{1},f_{5};a_{1}),$
$\displaystyle g_{4}=R(f_{3},f_{4};a_{3}),$ $\displaystyle
g_{5}=R(f_{7},f_{8};a_{3}),$ $\displaystyle g_{6}=R(f_{3},f_{7};a_{3}),$
$\displaystyle g_{7}=R(g_{3},g_{6};a_{2}),$ $\displaystyle
g_{8}=R(g_{1},g_{2};x_{3}),$ $\displaystyle g_{9}=R(g_{1},g_{7};x_{3}),$
$\displaystyle g_{10}=R(g_{4},g_{5};z_{2}),$ $\displaystyle
g_{11}=R(g_{5},g_{9};z_{2}),$ $\displaystyle g_{12}=R(g_{10},g_{11};y_{3}),$
$\displaystyle g_{13}=R(g_{8},g_{11};y_{3}).$

By the MAGMA Program 12 in the Appendix B, the polynomials $g_{12}$ and
$g_{13}$ can be factorized as

$\displaystyle g_{12}=b_{2}y_{1}x_{2}\cdot g_{14},$ $\displaystyle
g_{13}=y_{1}x_{2}^{2}(x_{2}-1)^{2}\cdot g_{15}.$

Finally, we can compute to get that

$\displaystyle
g_{16}:=R(g_{14},g_{15};y_{1})=b_{2}^{5}(b_{2}-1)^{8}x_{2}^{9}(x_{2}-1)\cdot
g_{17}^{2}g_{18},$ (74)

where
$g_{17}=x_{2}^{3}+x_{2}^{2}c_{1}+x_{2}^{2}b_{2}^{2}-2x_{2}^{2}b_{2}-x_{2}^{2}c_{2}-x_{2}^{2}-x_{2}d_{1}-x_{2}b_{2}^{3}+2x_{2}b_{2}+x_{2}c_{2}-b_{1}c_{1}+b_{1}d_{1}+b_{2}^{3}-b_{2}^{2}$
and $g_{18}$ is a polynomial of $x_{2}$ with degree $24$. We write $g_{18}$ as
$g_{18}=\sum_{i=0}^{24}h_{i}x_{2}^{i}$. We claim that $h_{i}$ $(0\leq i\leq
24)$ cannot be all $0$, otherwise, we can take 6 coefficients such as

$\displaystyle h_{0}=b_{2}^{2}(b_{2}-1)^{2}(c_{1}-d_{1})^{10}b_{1}^{5}\cdot
k_{0},$ $\displaystyle h_{1}=b_{2}(b_{2}-1)(c_{1}-d_{1})^{9}b_{1}^{5}\cdot
k_{1},$ $\displaystyle h_{2}=(c_{1}-d_{1})^{8}b_{1}^{4}\cdot k_{2},$
$\displaystyle h_{3}=(c_{1}-d_{1})^{7}b_{1}^{4}\cdot k_{3},$ $\displaystyle
h_{4}=(c_{1}-d_{1})^{6}b_{1}^{3}\cdot k_{4},$ $\displaystyle
h_{24}=(c_{2}-d_{2})b_{2}^{4}(b_{2}-1)^{2}\cdot k_{5}.$

Now we regard $k_{i}$ $(i=0,1,2,3,4,5)$ as the polynomials with variables
$b_{1},b_{2},c_{1},c_{2},d_{1},d_{2}$. Then we can get the following
polynomials.

$\displaystyle R(k_{0},k_{1};d_{1})=(c_{2}-d_{2})b_{2}^{2}(b_{2}-1)^{2}\cdot
k_{6},$ $\displaystyle R(k_{0},k_{5};d_{1})=k_{7},$ $\displaystyle
R(k_{0},k_{2};d_{1})=(c_{2}-d_{2})b_{2}^{3}(b_{2}-1)^{3}b_{1}\cdot k_{8},$
$\displaystyle R(k_{0},k_{3};d_{1})=(c_{2}-d_{2})b_{2}^{2}(b_{2}-1)^{3}\cdot
k_{9},$ $\displaystyle
R(k_{0},k_{4};d_{1})=(c_{2}-d_{2})b_{2}^{3}(b_{2}-1)^{3}b_{1}\cdot k_{10},$
$\displaystyle R(k_{6},k_{7};d_{2})=(c_{1}-c_{2})\cdot k_{11},$ $\displaystyle
R(k_{6},k_{8};d_{2})=(c_{1}-c_{2})b_{1}^{2}(b_{1}-1)^{2}(b_{1}-b_{2})(b_{1}+b_{2}-1)\cdot
k_{12},$ $\displaystyle
R(k_{6},k_{9};d_{2})=(c_{1}-c_{2})b_{1}^{4}(b_{1}-1)^{3}(b_{1}-b_{2})(b_{1}+b_{2}-1)\cdot
k_{13},$ $\displaystyle
R(k_{6},k_{10};d_{2})=(c_{1}-c_{2})b_{1}^{4}(b_{1}-1)^{4}(b_{1}-b_{2})(b_{1}+b_{2}-1)\cdot
k_{14}.$

Claim: $b_{1}\neq b_{2}$ and $c_{1}\neq c_{2}$.

###### Proof of the Claim.

If $b_{1}=b_{2}$. Then we substitute this equation into $k_{0}$ to get a
polynomial $k_{15}$, and substitute it into $k_{1}$ to get a polynomial
$k_{16}$. Then $k_{15}$ and $k_{16}$ can be factorized as

$\displaystyle k_{15}=b_{2}(b_{2}-1)\cdot k_{17},$ $\displaystyle
k_{16}=b_{2}(b_{2}-1)\cdot k_{18}.$

We can compute to get that
$R(k_{17},k_{18};c_{1})=(c_{2}-d_{2})(b_{2}-\frac{1}{3})(d_{1}-d_{2})$, hence
$d_{1}=d_{2}$. Similarly, we can get that $c_{1}=c_{2}$. Therefore
$(b_{1},c_{1},d_{1},1)=(b_{2},c_{2},d_{2},1)$, which is a contradiction.

Similarly, we can prove that $c_{1}\neq c_{2}$. This completes the proof of
our claim. ∎

Now we can compute to get that

$\displaystyle k_{19}=R(k_{11},k_{12};c_{1}),$ $\displaystyle
R(k_{12},k_{13};c_{1})=b_{1}^{2}(b_{1}-b_{2})^{2}(b_{1}^{2}-4b_{1}+1)^{2}\cdot
k_{20},$ $\displaystyle
R(k_{12},k_{14};c_{1})=b_{1}^{3}(b_{1}-b_{2})^{3}(b_{1}^{2}-4b_{1}+1)^{3}\cdot
k_{21},$ $\displaystyle k_{22}=R(k_{19},k_{20};b_{1}),$ $\displaystyle
k_{23}=R(k_{19},k_{21};b_{1}),$

where the polynomials $k_{i}\ (i=22,23)$ can be factorized as

$\displaystyle k_{22}=$ $\displaystyle
b_{2}^{89}(b_{2}-1)^{20}(b_{2}-\frac{2}{3})^{17}(b_{2}-\frac{1}{3})^{10}(b_{2}^{5}-\frac{12757}{10872}b_{2}^{4}+\frac{1123}{3624}b_{2}^{3}+\frac{289}{1359}b_{2}^{2}-\frac{49}{453}b_{2}-\frac{2}{151})^{4}\cdot
k_{24},$ $\displaystyle k_{23}=$ $\displaystyle
b_{2}^{91}(b_{2}-1)^{30}(b_{2}-\frac{2}{3})^{26}(b_{2}-\frac{1}{3})^{15}(b_{2}^{5}-\frac{12757}{10872}b_{2}^{4}+\frac{1123}{3624}b_{2}^{3}+\frac{289}{1359}b_{2}^{2}-\frac{49}{453}b_{2}-\frac{2}{151})^{6}\cdot
k_{25}.$

Finally, we have $R(k_{24},k_{25};b_{2})\neq 0$, which is a contradiction.
Hence, from Eq. (74), there are at most 24+3=27 solutions for $x_{2}$.

Now for any fixed $x_{2}$, $g_{15}$ is a polynomial of $y_{1}$ with degree
$4$. We write $g_{15}$ as $g_{15}=\sum_{i=0}^{4}l_{i}y_{1}^{i}$, then
$l_{4}=b_{2}(b_{2}-1)x_{2}^{4}(x_{2}-1)^{2}\neq 0$. Hence there are at most
$4$ solutions for $y_{1}$. If $x_{2}$ and $y_{1}$ are given, then all the
remaining variables are uniquely determined.

Hence, for any given $(b_{1},c_{1},d_{1},1),(b_{2},c_{2},d_{2},1)\in V_{1}$,
there are at most $27\times 4=108$ Berge $3$-paths of $(1,2,3,1)$-type with
$(b_{1},c_{1},d_{1},1),(b_{2},c_{2},d_{2},1)$ being its end core vertices.

###  4.3 $(1,2,3,2)$-type Berge $3$-paths

For any given $(b_{1},c_{1},d_{1},1)\in V_{1},(b_{2},c_{2},d_{2},2)\in V_{2}$,
suppose there exist $(u_{1},v_{1},w_{1},2)\in V_{2},\\\
(u_{2},v_{2},w_{2},3)\in V_{3}$ and
$e(x_{1},x_{2},x_{3},a_{1}),e(y_{1},y_{2},y_{3},a_{2}),e(z_{1},z_{2},z_{3},a_{3})$
such that $(b_{1},c_{1},d_{1},1),\\\
e(x_{1},x_{2},x_{3},a_{1}),(u_{1},v_{1},w_{1},2),e(y_{1},y_{2},y_{3},a_{2}),(u_{2},v_{2},w_{2},3),e(z_{1},z_{2},z_{3},a_{3}),(b_{2},c_{2},d_{2},2)$
form a copy of Berge $3$-path.

Then by the definition of hypergraph $\mathcal{H}$, we have

$\displaystyle b_{1}=x_{1},$ (75) $\displaystyle c_{1}=x_{2}x_{3}+a_{1},$ (76)
$\displaystyle d_{1}=x_{2}^{2}x_{3}+a_{1},$ (77) $\displaystyle
u_{1}=x_{2}=y_{2},$ (78) $\displaystyle
v_{1}=x_{3}x_{1}+a_{1}=y_{3}y_{1}+a_{2},$ (79) $\displaystyle
w_{1}=x_{3}^{2}x_{1}+a_{1}=y_{3}^{2}y_{1}+a_{2},$ (80) $\displaystyle
b_{2}=z_{2},$ (81) $\displaystyle c_{2}=z_{3}z_{1}+a_{3},$ (82) $\displaystyle
d_{2}=z_{3}^{2}z_{1}+a_{3},$ (83) $\displaystyle u_{2}=y_{3}=z_{3},$ (84)
$\displaystyle v_{2}=y_{1}y_{2}+a_{2}=z_{1}z_{2}+a_{3},$ (85) $\displaystyle
w_{2}=y_{1}^{2}y_{2}+a_{2}=z_{1}^{2}z_{2}+a_{3}.$ (86)

Then we can get the following equations.

$\displaystyle f_{1}:=x_{2}x_{3}+a_{1}-c_{1}=0,$ $\displaystyle
f_{2}:=x_{2}^{2}x_{3}+a_{1}-d_{1}=0,$ $\displaystyle
f_{3}:=y_{3}z_{1}+a_{3}-c_{2}=0,$ $\displaystyle
f_{4}:=y_{3}^{2}z_{1}+a_{3}-d_{2}=0,$ $\displaystyle
f_{5}:=x_{3}b_{1}+a_{1}-y_{3}y_{1}-a_{2}=0,$ $\displaystyle
f_{6}:=x_{3}^{2}b_{1}+a_{1}-y_{3}^{2}y_{1}-a_{2}=0,$ $\displaystyle
f_{7}:=y_{1}x_{2}+a_{2}-z_{1}b_{2}-a_{3}=0,$ $\displaystyle
f_{8}:=y_{1}^{2}x_{2}+a_{2}-z_{1}^{2}b_{2}-a_{3}=0,$

where $f_{1}$ is from Eq. (76), $f_{2}$ is from Eq. (77), $f_{3}$ is from Eqs.
(82) and (84), $f_{4}$ is from Eqs. (83) and (84), $f_{5}$ is from Eqs. (75)
and (79), $f_{6}$ is from Eqs. (75) and (80), $f_{7}$ is from Eqs. (78), (81)
and (85), $f_{8}$ is from Eqs. (78), (81) and (86).

######  Lemma 4.7.

  * (1)

$b_{i},c_{i},d_{i},u_{i},v_{i},w_{i},x_{j},y_{j},z_{j}\not\in\\{0,1\\}$ for
$1\leq i\leq 2$ and $1\leq j\leq 3$,

  * (2)

$c_{1}\neq d_{1}$, $c_{2}\neq d_{2}$, $x_{2}\neq b_{2}$,

  * (3)

$x_{2}^{2}-x_{2}+c_{1}-d_{1}\neq 0$.

###### Proof.

We will only prove $x_{2}\neq b_{2}$, others are immediately from the
definition of $\mathcal{H}$. If $x_{2}=b_{2}$, then $y_{2}=z_{2}$. By the
equations on $v_{2}$ and $w_{2}$, we have $y_{1}=z_{1}$, and then
$a_{2}=a_{3}$. This leads to
$e(y_{1},y_{2},y_{3},a_{2})=e(z_{1},z_{2},z_{3},a_{3})$, which is a
contradiction. ∎

Regarding $f_{i}$ as polynomials with variables
$x_{2},x_{3},y_{1},y_{3},z_{1},a_{1},a_{2},a_{3}$, we can compute to get that

$\displaystyle g_{1}=R(f_{1},f_{2};a_{1}),$ $\displaystyle
g_{2}=R(f_{5},f_{6};a_{1}),$ $\displaystyle g_{3}=R(f_{1},f_{5};a_{1}),$
$\displaystyle g_{4}=R(f_{3},f_{4};a_{3}),$ $\displaystyle
g_{5}=R(f_{7},f_{8};a_{3}),$ $\displaystyle g_{6}=R(f_{3},f_{7};a_{3}),$
$\displaystyle g_{7}=R(g_{3},g_{6};a_{2}),$ $\displaystyle
g_{8}=R(g_{1},g_{2};x_{3}),$ $\displaystyle g_{9}=R(g_{1},g_{7};x_{3}),$
$\displaystyle g_{10}=R(g_{4},g_{5};z_{1}),$ $\displaystyle
g_{11}=R(g_{4},g_{9};z_{1}),$ $\displaystyle g_{12}=R(g_{8},g_{10};y_{1}),$
$\displaystyle g_{13}=R(g_{8},g_{11};y_{1}).$

By the MAGMA Program 13 in the Appendix B, the polynomials $h_{12}$ and
$g_{13}$ can be factorized as

$\displaystyle g_{12}=y_{3}^{2}(y_{3}-1)^{2}x_{2}\cdot g_{14},$ $\displaystyle
g_{13}=y_{3}(y_{3}-1)x_{2}(x_{2}-1)\cdot g_{15}.$

Finally, we have

$\displaystyle R(g_{14},g_{15};y_{3})=x_{2}^{2}(x_{2}-1)^{2}\cdot g_{16},$

where $g_{16}$ is a polynomial of $x_{2}$ with degree $18$. We write $g_{16}$
as $g_{16}=\sum_{i=0}^{18}h_{i}x_{2}^{i}$. We can compute to get that

$\displaystyle h_{0}=(c_{1}-d_{1})^{10}b_{1}^{5}(b_{1}-1)\neq 0.$

Hence, there are at most $18$ solutions for $x_{2}$.

Now for any fixed $x_{2}$, $g_{14}$ is a polynomial of $y_{3}$ with degree
$2$. We write $g_{14}$ as $g_{14}=\sum_{i=0}^{2}l_{i}y_{3}^{i}$, then
$l_{2}=x_{2}^{2}(x_{2}-1)^{2}l_{2}^{\prime}$. We can regard $l_{i}$ as
polynomials with variables $x_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2}$. Then
by the MAGMA Program 14 in the Appendix B, we have

$\displaystyle
R(l_{0},l_{2}^{\prime};b_{1})=(c_{2}-d_{2})^{2}b_{2}(c_{1}-d_{1})^{2}x_{2}^{2}(x_{2}-1)^{4}(x_{2}-b_{2})(x_{2}^{2}-x_{2}+c_{1}-d_{1})^{2}\neq
0.$

Hence there are at most $2$ solutions for $y_{3}$. If $x_{2}$ and $y_{3}$ are
given, then all the remaining variables are uniquely determined.

Hence, for any given $(b_{1},c_{1},d_{1},1)\in V_{1},(b_{2},c_{2},d_{2},2)\in
V_{2}$, there are at most $18\times 2=36$ Berge $3$-paths of $(1,2,3,2)$-type
with $(b_{1},c_{1},d_{1},1),(b_{2},c_{2},d_{2},2)$ being its end core
vertices.

###  4.4 Proof of Theorem 1.3

If the given two vertices are in the same part, without loss of generality,
suppose $(b_{1},c_{1},d_{1},1),\\\ (b_{2},c_{2},d_{2},1)\in V_{1}$. Then there
are two types of Berge $3$-paths: $(1,2,3,1)$-type and $(1,3,2,1)$-type. From
the previous discussions, there are at most $108\times 2=216$ such Berge
$3$-paths in $\mathcal{H}$.

If the given two vertices are in different parts, without loss of generality,
suppose $(b_{1},c_{1},d_{1},1)\in V_{1},(b_{2},c_{2},d_{2},2)\in V_{2}$. Then
there are three types of Berge $3$-paths: $(1,2,1,2)$-type, $(1,2,3,2)$-type
and $(1,3,1,2)$-type. From the previous discussions, there are at most
$8+36\times 2=80$ such Berge $3$-paths in $\mathcal{H}$. Hence $\mathcal{H}$
is $\Theta_{3,217}^{B}$-free.

##  5 Conclusion

In this paper, we determine the asymptotics of Turán number of
$K_{3,25}^{\prime}$ and linear Turán number of Berge theta hyerpgraph
$\Theta_{3,217}^{B}$. Our main technique is the polynomial resultant. The
parameters 25 and 217 may not be the best possible, hence improving these
parameters will be interesting. As we have mentioned in Section 2, polynomial
resultant can settle some cases which are difficult to deal with by manual
computation. We believe that the polynomial resultant can be used to construct
more extremal graphs, it would be interesting to find more such examples.

## References

  * [1] N. Alon, L. Rónyai, and T. Szabó.  Norm-graphs: variations and applications.  J. Combin. Theory Ser. B, 76(2):280–290, 1999.
  * [2] C. T. Benson.  Minimal regular graphs of girths eight and twelve.  Canadian J. Math., 18:1091–1094, 1966.
  * [3] J. A. Bondy and M. Simonovits.  Cycles of even length in graphs.  J. Combin. Theory Ser. B, 16:97–105, 1974.
  * [4] W. Bosma, J. Cannon, and C. Playoust.  The Magma algebra system. I. The user language.  J. Symbolic Comput., 24(3-4):235–265, 1997.
  * [5] W. G. Brown.  On graphs that do not contain a thomsen graph.  Canadian mathematical bulletin , 9(3), 1966.
  * [6] B. Bukh.  Random algebraic construction of extremal graphs.  Bull. Lond. Math. Soc., 47(6):939–945, 2015.
  * [7] B. Bukh and D. Conlon.  Rational exponents in extremal graph theory.  J. Eur. Math. Soc. (JEMS), 20(7):1747–1757, 2018.
  * [8] B. Bukh and M. Tait.  Turán numbers of theta graphs.  Combin. Probab. Comput., 29(4):495–507, 2020.
  * [9] D. Conlon.  Graphs with few paths of prescribed length between any two vertices.  Bull. Lond. Math. Soc., 51(6):1015–1021, 2019.
  * [10] D. Conlon.  Extremal numbers of cycles revisited.  Amer. Math. Monthly, 128(5):464–466, 2021.
  * [11] D. Conlon, O. Janzer, and J. Lee.  More on the extremal number of subdivisions.  Combinatorica, to appear.
  * [12] P. Erdős, A. Rényi, and V. T. Sós.  On a problem of graph theory.  Studia Sci. Math. Hungar., 1:215–235, 1966.
  * [13] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar., 1:51–57, 1966.
  * [14] P. Erdős and A. H. Stone.  On the structure of linear graphs.  Bull. Amer. Math. Soc., 52:1087–1091, 1946.
  * [15] P. A. Fuhrmann.  A polynomial approach to linear algebra.  Universitext. Springer, New York, second edition, 2012.
  * [16] G. Ge, Y. Jing, Z. Xu, and T. Zhang.  Color isomorphic even cycles and a related Ramsey problem.  SIAM J. Discrete Math., 34(3):1999–2008, 2020.
  * [17] Z. He and M. Tait.  Hypergraphs with few Berge paths of fixed length between vertices.  SIAM J. Discrete Math., 33(3):1472–1481, 2019.
  * [18] J. Kollár, L. Rónyai, and T. Szabó.  Norm-graphs and bipartite Turán numbers.  Combinatorica, 16(3):399–406, 1996.
  * [19] T. Kövari, V. T. Sós, and P. Turán.  On a problem of K. Zarankiewicz.  Colloquium Math., 3:50–57, 1954.
  * [20] S. Lang and A. Weil.  Number of points of varieties in finite fields.  Amer. J. Math., 76:819–827, 1954.
  * [21] F. Lazebnik and V. A. Ustimenko.  Explicit construction of graphs with an arbitrary large girth and of large size.  volume 60, pages 275–284. 1995.  ARIDAM VI and VII (New Brunswick, NJ, 1991/1992).
  * [22] J. Ma, X. Yuan, and M. Zhang.  Some extremal results on complete degenerate hypergraphs.  J. Combin. Theory Ser. A, 154:598–609, 2018.
  * [23] K. E. Mellinger and D. Mubayi.  Constructions of bipartite graphs from finite geometries.  J. Graph Theory, 49(1):1–10, 2005.
  * [24] C. Pohoata and D. Zakharov.  Norm hypergraphs.  arXiv, arXiv:2101.00715, 2021.
  * [25] R. Singleton.  On minimal graphs of maximum even girth.  J. Combinatorial Theory, 1:306–332, 1966.
  * [26] J. Verstraëte and J. Williford.  Graphs without theta subgraphs.  J. Combin. Theory Ser. B, 134:76–87, 2019.
  * [27] R. Wenger.  Extremal graphs with no $C^{4}$’s, $C^{6}$’s, or $C^{10}$’s.  J. Combin. Theory Ser. B, 52(1):113–116, 1991.
  * [28] Z. Xu, T. Zhang, and G. Ge.  Some tight lower bounds for Turán problems via constructions of multi-hypergraphs.  European J. Combin., 89:103161, 11, 2020.

## Appendix A

######  Program 1.

MAGMA program for Subsection 3.1 (Case $a_{1}\neq c_{1}$):

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=b2-w2-(a1-w1)*y1^{2};$
$\displaystyle f4:=b3-w3-(a1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=c2-w2-(c1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(c1^{2}-w1^{2})*z1;$
$\displaystyle g1:=Resultant(f1,f2,x1)\text{ div }(a1-w1);$ $\displaystyle
g2:=Resultant(f3,f4,y1)\text{ div }(a1-w1);$ $\displaystyle
g3:=Resultant(f5,f6,z1)\text{ div }(c1-w1);$ $\displaystyle
g4:=Resultant(g1,g2,w2)\text{ div }((a1-w1)*(a1+w1)^{2});$ $\displaystyle
g5:=Resultant(g1,g3,w2);$ $\displaystyle h:=Resultant(g4,g5,w3);$
$\displaystyle h8:=Coefficient(h,w1,8);$ $\displaystyle
s1:=Coefficient(g4,w3,1);$ $\displaystyle Factorization(h8);$

######  Program 2.

MAGMA program for Subsection 3.1 (Case $a_{1}=c_{1}$):

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=b2-w2-(a1-w1)*y1^{2};$
$\displaystyle f4:=b3-w3-(a1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=c2-w2-(a1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(a1^{2}-w1^{2})*z1;$
$\displaystyle g1:=Resultant(f1,f2,x1)\text{ div }(a1-w1);$ $\displaystyle
g2:=Resultant(f3,f4,y1)\text{ div }(a1-w1);$ $\displaystyle
g3:=Resultant(f5,f6,z1)\text{ div }(a1-w1);$ $\displaystyle
g4:=Resultant(g1,g2,w2)\text{ div }((a1-w1)*(a1+w1)^{2});$ $\displaystyle
g6:=Resultant(g1,g3,w2)\text{ div }((a1-w1)*(a1+w1)^{2});$ $\displaystyle
h^{\prime}:=Resultant(g4,g6,w3);$ $\displaystyle
k3:=Coefficient(h^{\prime},w1,3);$ $\displaystyle
k0:=Coefficient(h^{\prime},w1,0);$ $\displaystyle k:=Resultant(k3,k0,a2);$
$\displaystyle Factorization(k);$

######  Program 3.

MAGMA program for Subsection 3.2 (Case $a_{2}\neq c_{2}$):

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=a2-w2-(b1-w1)*y1^{2};$
$\displaystyle f4:=b3-w3-(b1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=c2-w2-(c1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(c1^{2}-w1^{2})*z1;$
$\displaystyle g1:=Resultant(f1,f2,x1)\text{ div }(a1-w1);$ $\displaystyle
g2:=Resultant(f3,f4,y1)\text{ div }(b1-w1);$ $\displaystyle
g3:=Resultant(f5,f6,z1)\text{ div }(c1-w1);$ $\displaystyle
g4:=Resultant(g1,g2,w2);$ $\displaystyle g5:=Resultant(g1,g3,w2);$
$\displaystyle h:=Resultant(g4,g5,w3)\text{ div }((a1-w1)^{2}*(a1+w1)^{4});$
$\displaystyle h10:=Coefficient(h,w1,10);$ $\displaystyle
s2:=Coefficient(g4,w3,2)\text{ div }(a1-b1);$ $\displaystyle
t2:=Coefficient(g5,w3,2)\text{ div }(a1-c1);$ $\displaystyle
Factorization(h10);$ $\displaystyle Factorization(s2-t2);$

######  Program 4.

MAGMA program for Subsection 3.2 (Case $a_{2}=c_{2}$ and
$(a_{3}-b_{3})(b_{3}-c_{3})(a_{3}-c_{3})\neq 0$):

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=a2-w2-(b1-w1)*y1^{2};$
$\displaystyle f4:=b3-w3-(b1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=a2-w2-(c1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(c1^{2}-w1^{2})*z1;$
$\displaystyle g1:=Resultant(f1,f2,x1)\text{ div }(a1-w1);$ $\displaystyle
g2:=Resultant(f3,f4,y1)\text{ div }(b1-w1);$ $\displaystyle
g3:=Resultant(f5,f6,z1)\text{ div }(c1-w1);$ $\displaystyle
g4:=Resultant(g1,g2,w2);$ $\displaystyle g5:=Resultant(g1,g3,w2);$
$\displaystyle h:=Resultant(g4,g5,w3)\text{ div }((a1-w1)^{2}*(a1+w1)^{4});$
$\displaystyle h5:=Coefficient(h,w1,5);$ $\displaystyle
h4:=Coefficient(h,w1,4);$ $\displaystyle Factorization(Resultant(h4,h5,a1));$

######  Program 5.

MAGMA program for Subsection 3.2 (Case $a_{2}=c_{2}$ and $a_{3}=b_{3}$):

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=a2-w2-(b1-w1)*y1^{2};$
$\displaystyle f4:=a3-w3-(b1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=a2-w2-(c1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(c1^{2}-w1^{2})*z1;$
$\displaystyle g1:=Resultant(f1,f2,x1)\text{ div }(a1-w1);$ $\displaystyle
g2:=Resultant(f3,f4,y1)\text{ div }(b1-w1);$ $\displaystyle
g3:=Resultant(f5,f6,z1)\text{ div }(c1-w1);$ $\displaystyle
g4:=Resultant(g1,g2,w2)\text{ div }((a3-w3)^{2}*(a1-b1));$ $\displaystyle
g5:=Resultant(g1,g3,w2);$ $\displaystyle t2:=Coefficient(g5,w3,2)\text{ div
}(a1-c1);$ $\displaystyle Factorization(g4-t2);$

######  Program 6.

MAGMA program for Lemma 3.5:

$\displaystyle P<a,b,c,d,x,y,z,w>:=PolynomialRing(RationalField(),8);$
$\displaystyle g1:=(y+z)*(b+c)-(w-a)*(d-x);$ $\displaystyle
g2:=(x+z)*(a+c)-(w-b)*(d-y);$ $\displaystyle g3:=(x+y)*(a+b)-(w-c)*(d-z);$
$\displaystyle h1:=Resultant(g1,g2,d)\text{ div }(a+b+c-w);$ $\displaystyle
h2:=Resultant(g1,g3,d)\text{ div }(a+b+c-w);$ $\displaystyle
Factorization(Resultant(h1,h2,w));$

######  Program 7.

MAGMA program for Claim 3.7:

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=b2-w2-(b1-w1)*y1^{2};$
$\displaystyle f4:=b3-w3-(b1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=c2-w2-(c1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(c1^{2}-w1^{2})*z1;$
$\displaystyle f7:=(a1-b1)*(y1-z1)-(b1-c1)*(x1-y1);$ $\displaystyle
g1:=f1-f3;$ $\displaystyle g2:=f1-f5;$ $\displaystyle g3:=f2-f4;$
$\displaystyle g5:=Resultant(g1,g2,w1);$ $\displaystyle
g6:=Resultant(g1,g3,w1)\text{ div }(x1-y1);$ $\displaystyle
h1:=Resultant(f7,g5,x1)\text{ div }(y1-z1);$ $\displaystyle
h2:=Resultant(f7,g6,x1);$ $\displaystyle s:=Resultant(h1,h2,z1)\text{ div
}((b1-c1)^{3}*(a1-b1)^{6}*(a1*y1^{2}-a2-b1*y1^{2}+b2)^{2});$ $\displaystyle
s8:=Coefficient(s,y1,8)\text{ div }((b1-c1)^{3}*(a1-c1)^{4}*(a1-b1)^{4});$
$\displaystyle s7:=Coefficient(s,y1,7)\text{ div
}((b1-c1)^{3}*(a1-c1)^{3}*(a1-b1)^{3}*(a3-b3));$ $\displaystyle
Factorization(Resultant(s7,s8,a1));$

######  Program 8.

MAGMA program for Subsection 3.3:

$\displaystyle
P<a1,a2,a3,b1,b2,b3,c1,c2,c3,w1,w2,w3,x1,y1,z1>:=PolynomialRing(RationalField(),15);$
$\displaystyle f1:=a2-w2-(a1-w1)*x1^{2};$ $\displaystyle
f2:=a3-w3-(a1^{2}-w1^{2})*x1;$ $\displaystyle f3:=b2-w2-(b1-w1)*y1^{2};$
$\displaystyle f4:=b3-w3-(b1^{2}-w1^{2})*y1;$ $\displaystyle
f5:=c2-w2-(c1-w1)*z1^{2};$ $\displaystyle f6:=c3-w3-(c1^{2}-w1^{2})*z1;$
$\displaystyle g1:=Resultant(f1,f2,x1)\text{ div }(a1-w1);$ $\displaystyle
g2:=Resultant(f3,f4,y1)\text{ div }(b1-w1);$ $\displaystyle
g3:=Resultant(f5,f6,z1)\text{ div }(c1-w1);$ $\displaystyle
g4:=Resultant(g1,g2,w2);$ $\displaystyle g5:=Resultant(g1,g3,w2);$
$\displaystyle h:=Resultant(g4,g5,w3)\text{ div }((a1-w1)^{2}*(a1+w1)^{4});$
$\displaystyle h10:=a1*b2-a1*c2-a2*b1+a2*c1+b1*c2-b2*c1;$ $\displaystyle
h8:=Coefficient(h,w1,8);$ $\displaystyle h6:=Coefficient(h,w1,6);$
$\displaystyle k1:=Resultant(h10,h8,c2)\text{ div }((a2-b2)*(a1-b1));$
$\displaystyle k2:=Resultant(h10,h6,c2)\text{ div }((a2-b2)*(a1-b1));$
$\displaystyle Factorization(Resultant(k1,k2,c3));$ $\displaystyle
Factorization(Resultant(k1,k2,b2));$ $\displaystyle
k3:=Resultant(h10,h8,b2)\text{ div }((a2-c2)*(a1-c1));$ $\displaystyle
k4:=Resultant(h10,h6,b2)\text{ div }((a2-c2)*(a1-c1));$ $\displaystyle
Factorization(Resultant(k3,k4,c3));$

## Appendix B

######  Program 9.

MAGMA program for (1,2,1,2)-type: Lemma 3.3

$\displaystyle P<x1,x2,x3,y1,y3,z2,z3,t3>:=PolynomialRing(RationalField(),8);$
$\displaystyle f1:=x2*x3-x3*x1+t3*x1-z2*t3+z2*z3-z3*y1+y3*y1-x2*y3;$
$\displaystyle f2:=x2*x3-x2^{2}*x3-z2*t3+z2^{2}*t3;$ $\displaystyle
f3:=x3*x1-x3^{2}*x1-y3*y1+y3^{2}*y1;$ $\displaystyle
f4:=z3*y1-z3^{2}*y1-t3*x1+t3^{2}*x1;$ $\displaystyle
f5:=x2*y3-x2^{2}*y3-z2*z3+z2^{2}*z3;$ $\displaystyle g1:=Resultant(f3,f4,x1);$
$\displaystyle g2:=Resultant(f2,f5,x2);$ $\displaystyle
h:=Resultant(g1,g2,x3);$ $\displaystyle Factorization(h);$

######  Program 10.

MAGMA program for (1,2,1,2)-type: General

$\displaystyle
P<x2,x3,y1,y3,z3,a1,a2,a3,b1,c1,d1,b2,c2,d2>:=PolynomialRing(RationalField(),14);$
$\displaystyle f1:=x2*x3+a1-c1;$ $\displaystyle f2:=x2^{2}*x3+a1-d1;$
$\displaystyle f3:=z3*y1+a3-c2;$ $\displaystyle f4:=z3^{2}*y1+a3-d2;$
$\displaystyle f5:=x3*b1+a1-y3*y1-a2;$ $\displaystyle
f6:=x3^{2}*b1+a1-y3^{2}*y1-a2;$ $\displaystyle f7:=x2*y3+a2-b2*z3-a3;$
$\displaystyle f8:=x2^{2}*y3+a2-b2^{2}*z3-a3;$ $\displaystyle
g1:=Resultant(f2,f1,a1);$ $\displaystyle g2:=Resultant(f6,f5,a1);$
$\displaystyle g3:=Resultant(f5,f1,a1);$ $\displaystyle
g4:=Resultant(f3,f4,a3);$ $\displaystyle g5:=Resultant(f8,f7,a3);$
$\displaystyle g6:=Resultant(f7,f3,a3);$ $\displaystyle
g7:=Resultant(g6,g3,a2);$ $\displaystyle g8:=Resultant(g2,g1,x3);$
$\displaystyle g9:=Resultant(g7,g1,x3);$ $\displaystyle
g10:=Resultant(g4,g5,z3);$ $\displaystyle g11:=Resultant(g9,g5,z3);$
$\displaystyle g14:=Resultant(g8,g10,y1)div(y3*x2*(x2-1));$ $\displaystyle
g15:=Resultant(g8,g11,y1)div(y3*x2*(x2-1));$ $\displaystyle
g16:=Resultant(g14,g15,y3)div(b1*x2^{2}*(c1-d1)*(x2-1)^{2}*(x2-b2)*(x2+b2-1)$
$\displaystyle*(x2^{2}-x2+c1-d1));$ $\displaystyle h4:=Coefficient(g16,x2,4);$
$\displaystyle h3:=Coefficient(g16,x2,3);$ $\displaystyle
h2:=Coefficient(g16,x2,2);$ $\displaystyle h1:=Coefficient(g16,x2,1);$
$\displaystyle
h5:=Coefficient(g16,x2,0)div(-b1*c1^{2}+2*b1*c1*d1-b1*c1*b2^{2}+b1*c1*b2-b1*d1^{2}+$
$\displaystyle
b1*d1*b2^{2}-b1*d1*b2-b2^{4}*c2+b2^{4}*d2+2*b2^{3}*c2-2*b2^{3}*d2-b2^{2}*c2+b2^{2}*d2);$
$\displaystyle Factorization(Resultant(h1,h5,c1));$

######  Program 11.

MAGMA program for (1,2,1,2)-type: Claim

$\displaystyle
P<x2,x3,y1,y3,z3,a1,a2,a3,b1,c1,d1,b2,c2,d2>:=PolynomialRing(RationalField(),14);$
$\displaystyle f1:=x2*x3+a1-c1;$ $\displaystyle f2:=x2^{2}*x3+a1-d1;$
$\displaystyle f3:=z3*y1+a3-c2;$ $\displaystyle f4:=z3^{2}*y1+a3-d2;$
$\displaystyle f5:=x3*b1+a1-y3*y1-a2;$ $\displaystyle
f6:=x3^{2}*b1+a1-y3^{2}*y1-a2;$ $\displaystyle f7:=x2*y3+a2-b2*z3-a3;$
$\displaystyle f8:=x2^{2}*y3+a2-b2^{2}*z3-a3;$ $\displaystyle
g1:=Resultant(f2,f1,a1);$ $\displaystyle g2:=Resultant(f6,f5,a1);$
$\displaystyle g3:=Resultant(f5,f1,a1);$ $\displaystyle
g4:=Resultant(f3,f4,a3);$ $\displaystyle g5:=Resultant(f8,f7,a3);$
$\displaystyle g6:=Resultant(f7,f3,a3);$ $\displaystyle
g7:=Resultant(g6,g3,a2);$ $\displaystyle g8:=Resultant(g2,g1,x3);$
$\displaystyle g9:=Resultant(g7,g1,x3);$ $\displaystyle
g10:=Resultant(g4,g5,z3);$ $\displaystyle g11:=Resultant(g9,g5,z3);$
$\displaystyle g14:=Resultant(g8,g10,y1)div(y3*x2*(x2-1));$ $\displaystyle
g15:=Resultant(g8,g11,y1)div(y3*x2*(x2-1));$ $\displaystyle
g16:=Resultant(g14,g15,y3)div(b1*x2^{2}*(c1-d1)*(x2-1)^{2}*(x2-b2)*(x2+b2-1)$
$\displaystyle*(x2^{2}-x2+c1-d1));$ $\displaystyle h1:=Coefficient(g16,x2,1);$
$\displaystyle
g17:=-b1*c1^{2}+2*b1*c1*d1-b1*c1*b2^{2}+b1*c1*b2-b1*d1^{2}+b1*d1*b2^{2}-b1*d1*b2$
$\displaystyle-b2^{4}*c2+b2^{4}*d2+2*b2^{3}*c2-2*b2^{3}*d2-b2^{2}*c2+b2^{2}*d2;$
$\displaystyle Factorization(Resultant(g17,h1,d2));$ $\displaystyle
Factorization(Resultant(g17,h1,c2));$

######  Program 12.

MAGMA program for (1,2,3,1)-type

$\displaystyle
P<x2,x3,y1,y3,z2,a1,a2,a3,b1,c1,d1,b2,c2,d2>:=PolynomialRing(RationalField(),14);$
$\displaystyle f1:=x2*x3+a1-c1;$ $\displaystyle f2:=x2^{2}*x3+a1-d1;$
$\displaystyle f3:=z2*y3+a3-c2;$ $\displaystyle f4:=z2^{2}*y3+a3-d2;$
$\displaystyle f5:=x3*b1+a1-y3*y1-a2;$ $\displaystyle
f6:=x3^{2}*b1+a1-y3^{2}*y1-a2;$ $\displaystyle f7:=y1*x2+a2-b2*z2-a3;$
$\displaystyle f8:=y1^{2}*x2+a2-b2^{2}*z2-a3;$ $\displaystyle
g1:=Resultant(f2,f1,a1);$ $\displaystyle g2:=Resultant(f6,f5,a1);$
$\displaystyle g3:=Resultant(f5,f1,a1);$ $\displaystyle
g4:=Resultant(f3,f4,a3);$ $\displaystyle g5:=Resultant(f8,f7,a3);$
$\displaystyle g6:=Resultant(f7,f3,a3);$ $\displaystyle
g7:=Resultant(g6,g3,a2);$ $\displaystyle g8:=Resultant(g2,g1,x3);$
$\displaystyle g9:=Resultant(g7,g1,x3);$ $\displaystyle
g10:=Resultant(g5,g4,z2);$ $\displaystyle g11:=Resultant(g9,g5,z2);$
$\displaystyle g14:=Resultant(g10,g11,y3)div(b2*y1*x2);$ $\displaystyle
g15:=Resultant(g8,g11,y3)div(y1*x2^{2}*(x2-1)^{2});$ $\displaystyle
g18:=Resultant(g14,g15,y1)div(b2^{5}*(b2-1)^{8}*x2^{9}*(x2-1)*(x2^{3}+x2^{2}*c1+x2^{2}*b2^{2}-$
$\displaystyle
2*x2^{2}*b2-x2^{2}*c2-x2^{2}-x2*d1-x2*b2^{3}+2*x2*b2+x2*c2-b1*c1+b1*d1+b2^{3}-b2^{2})^{2});$
$\displaystyle
k0:=Coefficient(g18,x2,0)div(b2^{2}*(b2-1)^{2}*(c1-d1)^{10}*b1^{5});$
$\displaystyle k1:=Coefficient(g18,x2,1)div(b2*(b2-1)*(c1-d1)^{9}*b1^{5});$
$\displaystyle k2:=Coefficient(g18,x2,2)div((c1-d1)^{8}*b1^{4});$
$\displaystyle k3:=Coefficient(g18,x2,3)div((c1-d1)^{7}*b1^{4});$
$\displaystyle k4:=Coefficient(g18,x2,4)div((c1-d1)^{6}*b1^{3});$
$\displaystyle k5:=Coefficient(g18,x2,24)div((c2-d2)*b2^{4}*(b2-1)^{2});$
$\displaystyle k6:=Resultant(k0,k1,d1)div((c2-d2)*b2^{2}*(b2-1)^{2});$
$\displaystyle k7:=Resultant(k0,k5,d1);$

$\displaystyle k8:=Resultant(k0,k2,d1)div((c2-d2)*b2^{3}*(b2-1)^{3}*b1);$
$\displaystyle k9:=Resultant(k0,k3,d1)div((c2-d2)*b2^{2}*(b2-1)^{3});$
$\displaystyle k10:=Resultant(k0,k4,d1)div((c2-d2)*b2^{3}*(b2-1)^{3}*b1);$
$\displaystyle k11:=Resultant(k6,k7,d2)div(c1-c2);$ $\displaystyle
k12:=Resultant(k6,k8,d2)div((c1-c2)*b1^{2}*(b1-1)^{2}*(b1-b2)*(b1+b2-1));$
$\displaystyle
k13:=Resultant(k6,k9,d2)div((c1-c2)*b1^{4}*(b1-1)^{3}*(b1-b2)*(b1+b2-1));$
$\displaystyle
k14:=Resultant(k6,k10,d2)div((c1-c2)*b1^{4}*(b1-1)^{4}*(b1-b2)*(b1+b2-1));$
$\displaystyle k19:=Resultant(k11,k12,c1);$ $\displaystyle
k20:=Resultant(k12,k13,c1)div(b1^{2}*(b1-b2)^{2}*(b1^{2}-4*b1+1)^{2});$
$\displaystyle
k21:=Resultant(k12,k14,c1)div(b1^{3}*(b1-b2)^{3}*(b1^{2}-4*b1+1)^{3});$
$\displaystyle
k24:=Resultant(k19,k20,b1)div(b2^{89}*(b2-1)^{20}*(b2-2/3)^{17}*(b2-1/3)^{10}*$
$\displaystyle(b2^{5}-12757/10872*b2^{4}+1123/3624*b2^{3}+289/1359*b2^{2}-49/453*b2-2/151)^{4});$
$\displaystyle
k25:=Resultant(k19,k21,b1)div(b2^{91}*(b2-1)^{30}*(b2-2/3)^{26}*(b2-1/3)^{15}*$
$\displaystyle(b2^{5}-12757/10872*b2^{4}+1123/3624*b2^{3}+289/1359*b2^{2}-49/453*b2-2/151)^{6});$
$\displaystyle Resultant(k24,k25,b2);$

######  Program 13.

MAGMA program for (1,2,3,2)-type: Determine the number of solutions for $x2$

$\displaystyle
P<x2,x3,y1,y3,z1,a1,a2,a3,b1,c1,d1,b2,c2,d2>:=PolynomialRing(RationalField(),14);$
$\displaystyle f1:=x2*x3+a1-c1;$ $\displaystyle f2:=x2^{2}*x3+a1-d1;$
$\displaystyle f3:=y3*z1+a3-c2;$ $\displaystyle f4:=y3^{2}*z1+a3-d2;$
$\displaystyle f5:=x3*b1+a1-y3*y1-a2;$ $\displaystyle
f6:=x3^{2}*b1+a1-y3^{2}*y1-a2;$ $\displaystyle f7:=y1*x2+a2-z1*b2-a3;$
$\displaystyle f8:=y1^{2}*x2+a2-z1^{2}*b2-a3;$ $\displaystyle
g1:=Resultant(f2,f1,a1);$ $\displaystyle g2:=Resultant(f6,f5,a1);$
$\displaystyle g3:=Resultant(f5,f1,a1);$ $\displaystyle
g4:=Resultant(f3,f4,a3);$ $\displaystyle g5:=Resultant(f8,f7,a3);$
$\displaystyle g6:=Resultant(f7,f3,a3);$ $\displaystyle
g7:=Resultant(g6,g3,a2);$ $\displaystyle g8:=Resultant(g2,g1,x3);$
$\displaystyle g9:=Resultant(g7,g1,x3);$ $\displaystyle
g10:=Resultant(g5,g4,z1);$ $\displaystyle g11:=Resultant(g9,g4,z1);$
$\displaystyle g14:=Resultant(g8,g10,y1)div(y3^{2}*(y3-1)^{2}*x2);$
$\displaystyle g15:=Resultant(g8,g11,y1)div(y3*(y3-1)*x2*(x2-1));$
$\displaystyle g16:=Resultant(g14,g15,y3)div(x2^{2}*(x2-1)^{2});$
$\displaystyle Factorization(Coefficient(g16,x2,0));$

######  Program 14.

MAGMA program for (1,2,3,2)-type: Given $x2$, determine the number of
solutions for $y3$

$\displaystyle
P<x2,x3,y1,y3,z1,a1,a2,a3,b1,c1,d1,b2,c2,d2>:=PolynomialRing(RationalField(),14);$
$\displaystyle f1:=x2*x3+a1-c1;$ $\displaystyle f2:=x2^{2}*x3+a1-d1;$
$\displaystyle f3:=y3*z1+a3-c2;$ $\displaystyle f4:=y3^{2}*z1+a3-d2;$
$\displaystyle f5:=x3*b1+a1-y3*y1-a2;$ $\displaystyle
f6:=x3^{2}*b1+a1-y3^{2}*y1-a2;$ $\displaystyle f7:=y1*x2+a2-z1*b2-a3;$
$\displaystyle f8:=y1^{2}*x2+a2-z1^{2}*b2-a3;$ $\displaystyle
g1:=Resultant(f2,f1,a1);$ $\displaystyle g2:=Resultant(f6,f5,a1);$
$\displaystyle g4:=Resultant(f3,f4,a3);$ $\displaystyle
g5:=Resultant(f8,f7,a3);$ $\displaystyle g8:=Resultant(g2,g1,x3);$
$\displaystyle g10:=Resultant(g5,g4,z1);$ $\displaystyle
g14:=Resultant(g8,g10,y1)div(y3^{2}*(y3-1)^{2}*x2);$ $\displaystyle
l2:=Coefficient(g14,y3,2)div(x2^{2}*(x2-1)^{2});$ $\displaystyle
l0:=Coefficient(g14,y3,0);$ $\displaystyle
Factorization(Resultant(l2,l0,b1));$