# Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately
Large Fields

Ashish Dwivedi  Department of Computer Science and Engineering, The Ohio State
University. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS> Zeyu
Guo11footnotemark: 1 Ben Lee Volk Efi Arazi School of Computer Science,
Reichman University, Israel. Email<EMAIL_ADDRESS>The research leading
to these results has received funding from the Israel Science Foundation
(grant number 843/23).

###### Abstract

We construct explicit pseudorandom generators that fool $n$-variate
polynomials of degree at most $d$ over a finite field $\mathbb{F}_{q}$. The
seed length of our generators is $O(d\log n+\log q)$, over fields of size
exponential in $d$ and characteristic at least $d(d-1)+1$. Previous
constructions such as Bogdanov’s (STOC 2005) and Derksen and Viola’s (FOCS
2022) had either suboptimal seed length or required the field size to depend
on $n$.

Our approach follows Bogdanov’s paradigm while incorporating techniques from
Lecerf’s factorization algorithm (J. Symb. Comput. 2007) and insights from the
construction of Derksen and Viola regarding the role of indecomposability of
polynomials.

##  1 Introduction

The role of randomness in efficient computation is one of the central topics
in complexity theory: random bits are useful for designing algorithms, but
producing random bits comes at a cost and it is often desirable to reduce them
or eliminate them altogether. One of the simplest yet most profound insights
in this area is that efficient algorithms are, by definition, computationally
limited, and cannot perform arbitrary statistical tests over their random
bits. Therefore, one may hope to construct _pseudorandom_ distributions that
use less random bits but are able to “fool” some limited classes of tests,
that cannot distinguish between them and between truly random bits.

For the pseudorandom distributions to be useful, they need to be efficiently
computable themselves. This is usually modeled as a _pseudorandom generator_
(PRG, for short). A PRG for a class of $\mathcal{C}$ is an efficiently
computable function $G:S\to B$ such that for every function $f\in\mathcal{C}$,
the distributions $f(\mathbf{U}_{B})$ and $f(G(\mathbf{U}_{S}))$ are close in
statistical distance, where $\mathbf{U}_{A}$ denotes the uniform distribution
over the set $A$. Namely, the two experiments of applying $f(\cdot)$ to a
uniformly random element of $B$, and applying $f(G(\cdot))$ to a uniformly
random element of $S$, give roughly the same results. For this to be useful
and non-trivial, obviously the set $S$ needs to be significantly smaller than
$B$. The quantity $\log|S|$ is called the _seed length_ of the generator.

There has been a significant amount of work on constructing pseudorandom
generators for various types of restricted distinguishers. In its most general
form, where the distinguisher is allowed to be an arbitrary efficient (even
non-uniform) algorithm, constructing such PRGs would imply breakthrough lower
bounds in complexity theory. However, there are also unconditional
constructions of PRGs for distinguishers coming from certain smaller
complexity classes (see, for example, the surveys [Vad12, HH23]).

In this paper, we focus on pseudorandom generators in the algebraic setting.
Here, the restriction on the distinguishers is of algebraic nature: we seek to
fool distinguishers that are low-degree $n$-variate polynomials over finite
fields.

The problem of fooling low-degree polynomials is well-studied. The most basic
case is polynomials of degree one, i.e., fooling linear functions. Such
generators are also known as _$\varepsilon$ -biased sets_, and this problem
was traditionally studied over $\mathbb{F}_{2}$, although some of the
constructions can be generalized to larger fields. This concept was first
defined and considered by Naor and Naor [NN93], with various improved
constructions given by [AGHP92, EGL+98, BT13], culminating in a recent nearly-
optimal construction by Ta-Shma [Ta-17]. The seed length in those
constructions is $O(\log n+\log q+\log(1/\varepsilon))$, where $n$ denotes the
number of variables, $\varepsilon$ the error of the PRG, and $q$ the field
size.

While focusing on polynomials of degree one might seem a bit too restrictive,
$\varepsilon$-biased sets have found numerous applications throughout the
field of pseudorandomness and derandomization, and in the theory of
computation in general.

One example relevant to this work is that $\varepsilon$-biased sets are in
fact a basic building block in a construction of PRGs for higher-degree
polynomials, using a paradigm initiated by Bogdanov and Viola [BV10]. They
suggested constructing a generator for degree-$d$ polynomials by summing up
$\ell=\ell(d)$ independent copies of a generator for degree-one polynomials.
The paper [BV10] proved a conditional result when the number of summands is
$d$, assuming certain additive combinatorics conjectures. Lovett [Lov09]
showed how to prove an unconditional result at the cost of making the number
of summands $2^{d}$. Finally, Viola [Vio09] showed (unconditionally) that in
fact $d$ summands suffice. The seed length in his construction is $O(d\log
n+d2^{d}\log(q/\varepsilon))$. Indeed, even though the construction only sums
$d$ copies of a generator for degree-one polynomials, for the analysis to go
through, the error of this generator needs to be as small as
$\varepsilon^{2^{d}}$ (for the final error of the generator for degree-$d$
polynomials to be $\varepsilon$), which incurs a factor of $2^{d}$ in the
final seed length. Improving this generator and in particular obtaining
meaningful results for polynomials of degree greater than $\log n$ is an
extremely important open problem in complexity theory. One reason is that such
pseudorandom generators will yield pseudorandom generators for small constant-
depth circuits with parity gates, since Razborov [Raz87] and Smolensky [Smo93]
famously proved that functions computed by such circuits are approximated by
low-degree polynomials.

All the constructions mentioned above work for any field. There are, however,
better results when the field size $q$ is assumed to be large (typically, at
least polynomially large in $d$ and $1/\varepsilon$). This assumption is
useful since it allows one to use powerful tools from algebraic geometry, such
as Weil-type estimates [Wei49] on the number of points of varieties over
finite fields.

This line of work was initiated by Bogdanov [Bog05], who showed how to use
different pseudorandom objects called _hitting set generators_ for low-degree
polynomials in order to construct pseudorandom generators. Bogdanov’s work,
followed by the later improved constructions of hitting set generators [KS01,
Lu12, CT13, GX14], resulted in a PRG with seed length $O(d^{4}\log n+\log q)$
assuming $q\geq Cd^{6}/\varepsilon^{2}$ for a sufficiently large constant
$C$.111One should note that since $q$ is polynomially large in
$1/\varepsilon$, the seed length also implicitly depends on
$\log(1/\varepsilon)$ through the $\log q$ term. We expand more on Bogdanov’s
technique in Section Section 1.2, as it is very relevant to this work.

More recently, Derksen and Viola [DV22] introduced fundamentally new
techniques for this problem, with tools coming from invariant theory. One of
their key ideas is to construct a low-degree polynomial map on a few variables
that preserves the _indecomposability_ property of a polynomial $f$ when
composed with it (we refer to Section 2 for more on that). Using this new tool
in conjunction with other techniques, they are able to construct generators
with seed length $O(d\log(dn)+\log q)$, assuming $q\geq
Cd^{4}n^{\delta}/\varepsilon^{2}$ (for some large constant $C$ and small
constant $\delta$), or seed length $O(d\log n\log(d\log n)+\log q)$ for $q\geq
C(d\log n)^{4}/\varepsilon^{2}$. One should note, however, that the optimal
parameters in the construction of [DV22] are obtained after composing their
construction with Bogdanov’s original construction.

A related natural question is how small the seed length can potentially be.
Alon, Ben-Eliezer and Krivelevich [ABK08] considered this question and proved
a lower bound of $\Omega(d\log(n/d)+\log q+\log(1/\varepsilon))$ on the seed
length. Thus, we see that the explicit constructions of [DV22] come very close
to the optimal bound. However, unlike the result of Bogdanov [Bog05], in the
construction of Derksen and Viola [DV22] the minimum field size depends on the
number of variables $n$.

###  1.1 Our Results

In this paper, we provide an improved construction of PRGs for low-degree
polynomials, with an even shorter seed length, assuming the field size is
exponentially large in $d$ (but independent of $n$).

######  Theorem 1.1.

Let $\mathbb{F}_{q}$ be a finite field of characteristic at least $d(d-1)+1$
and size $q\geq C(d2^{d}/\varepsilon+d^{4}/\varepsilon^{2})$ (for some
sufficiently large absolute constant $C$). Then, there exists an explicit
pseudorandom generator that fools $n$-variate polynomials of degree at most
$d$ over $\mathbb{F}_{q}$ with error $\varepsilon$ and seed length $O(d\log
n+\log q)$.

For convenience, we summarize the comparison between 1.1 and the results of
Bogdanov [Bog05], Viola [Vio09] and Derksen and Viola [DV22] in the following
table. All the entries in this table are given up to some constant factors,
but for ease of readability, we omit $O(\cdot)$ notations.

| Seed Length | Field Size
---|---|---
[Vio09] | $d\log n+d\cdot 2^{d}\log(q/\varepsilon)$ | Every $q\geq 2$
[Bog05]+[GX14] | $d^{4}\log n+\log q$ | $d^{6}/\varepsilon^{2}$
[DV22] | $d\log(dn)+\log q$ | $d^{4}n^{0.001}/\varepsilon^{2}$
[DV22] | $d\log n\cdot\log(d\log n)+\log q$ | $(d\log n)^{4}/\varepsilon^{2}$
This paper: | $d\log n+\log q$ | $d2^{d}/\varepsilon+d^{4}/\varepsilon^{2}$

We also prove that, if we only want to fool polynomials of _prime_ degree up
to $d$, then the required field size in 1.1 can be improved to
$O(d^{4}/\varepsilon^{2})$, avoiding an exponential dependence on $d$.

######  Theorem 1.2.

Let $\mathbb{F}_{q}$ be a finite field of characteristic at least $d(d-1)+1$
and size $q\geq C(d^{4}/\varepsilon^{2})$ (for some sufficiently large
absolute constant $C$). Then, there exists an explicit pseudorandom generator
that fools $n$-variate polynomials of prime degree up to $d$ over
$\mathbb{F}_{q}$ with error $\varepsilon$ and seed length $O(d\log n+\log q)$.

###  1.2 Proof Techniques

We start by reviewing the proof of Bogdanov’s PRG. Bogdanov’s idea is to
consider restrictions of the polynomial $f$ we are trying to fool onto planes,
and to argue that “most” planes preserve the output distribution of the
polynomial. Since a plane is a two-dimensional subspace, after having selected
a good plane, we only need to sample two more field elements to select a
random element from the plane.

The question now is how to find a good plane. Here, Bogdanov uses results by
Kaltofen [Kal95], who proved an effective version of Hilbert’s irreducibility
theorem. Kaltofen demonstrated that, for every degree-$d$ irreducible
polynomial $f$, there exists a polynomial $P$ of degree roughly $d^{4}$, whose
variables correspond to the parameters of the plane, such that every point at
which $P$ is nonzero corresponds to a “good” plane for $f$—that is, a plane
that preserves the irreducibility of $f$. Therefore, we can use a hitting set
generator for polynomials of degree $d^{4}$ to find a good plane. This results
in a factor of $d^{4}$ in the final seed length.

Over fields of large characteristic (or characteristic zero), Lecerf [Lec06,
Lec07] obtained an improved upper bound of $O(d^{2})$ on the degree of such
polynomials, based on ideas of Ruppert [Rup86, Rup99] and Gao [Gao03].
However, Lecerf also presents an example where the degree of such a polynomial
must be at least $\Omega(d^{2})$, demonstrating that this approach alone may
not suffice to achieve an improvement within Bogdanov’s framework.

Derksen and Viola circumvent this problem by using a different approach based
on preserving the _indecomposability_ of polynomials: a polynomial
$f(x_{1},\ldots,x_{n})$ is indecomposable if it cannot be written as
$f=g(h(x_{1},\ldots,x_{n}))$ where $g$ is a univariate polynomial of degree at
least $2$. We refer to Section 2 for precise definitions.

To prove our result, we revisit Bogdanov’s approach, while noting that by
applying Lecerf’s results [Lec07] (rather than Kaltofen’s bounds [Kal95]) in a
more careful way, and assuming the field is sufficiently large, it is in fact
enough to use hitting sets generators only for polynomials of degree $O(d)$,
rather than $O(d^{2})$. This requires following the outline above but making
sure that at each step, we only need to hit polynomials of degree $O(d)$.

Following Lecerf’s notation and terminology, suppose $F(x_{1},\ldots,x_{n},y)$
is an irreducible polynomial. A point $\mathbf{a}=(a_{1},\ldots,a_{n})$ is
called a _Bertinian good_ point if the bivariate polynomial
$H(x,y)=F(a_{1}x,\ldots,a_{n}x,y)$ remains irreducible. Lecerf proves that
there exists a polynomial $\mathcal{A}(z_{1},\ldots,z_{n})$ of degree
$O(d^{2})$ such that if $\mathcal{A}(a_{1},\ldots,a_{n})\neq 0$ then
$\mathbf{a}$ is a Bertinian good point. This is achieved by transforming the
question of irreducibility into a question about the rank of a solution space
for a certain linear system that depends on $a_{1},\ldots,a_{n}$ (see Section
4). This transformation naturally leads to defining $\mathcal{A}$ as a certain
minor of the matrix representing that linear system. The minor has dimensions
$O(d)\times O(d)$, and each entry of the matrix is a polynomial of degree
$O(d)$, which results in a total bound of $O(d^{2})$ on the degree of its
determinant, $\mathcal{A}$.

We, however, observe that Lecerf’s results actually imply a much stronger
structure of this linear system: its solution space, over any field, is always
spanned by vectors whose entries are in $\\{0,1\\}$. In fact, Lecerf directly
characterizes the relationship between the irreducible factors of $F$ and the
vectors spanning the solution space, though this detail is irrelevant for the
moment.

Thus, in Lecerf’s argument, $a_{1},\ldots,a_{n}$ are chosen such that a
particular minor is nonzero, namely, a certain linear system has no non-
trivial solutions. But it is enough to select $a_{1},\ldots,a_{n}$ in a way
that only guarantees that this linear system has no non-trivial $0/1$
solutions!

Fixing any vector $u\in\\{0,1\\}^{d}$, the requirement that $u$ is not a
solution to the linear system turns out to be a condition expressible as $u$
being a nonzero of a polynomial of degree $O(d)$, rather than $O(d^{2})$. If
we pick $a_{1},\ldots,a_{n}$ from a hitting set generator with error $\delta$
smaller than $2^{-d}$, we can afford to take a union bound over all vectors in
$\\{0,1\\}^{d}$ and ensure that none of them is a solution to the linear
system while keeping the total error small. This is not a big price to pay in
terms of the seed length of the HSG, which is $O(d\log n+\log(1/\delta))$, so
requiring $\delta$ to be exponentially small in $d$ adds an insignificant
additive $O(d)$ term. Where we do pay the price for the small error is in the
field size, since the explicit construction of the HSG we use requires the
field size to be at least roughly $d/\delta$. Fortunately, however, the
dependence of the seed length of our generator on the field size $q$ is also
by an additive $O(\log q)$ term, which means that once more requiring $q$ to
be exponentially large in $d$ has no adverse effects even on the total seed
length of the PRG.

We briefly remark that, for technical reasons, Lecerf’s result also requires
the characteristic of the underlying field to be zero or at least $d(d-1)+1$.
We further elaborate on Lecerf’s techniques in Section 4.

We finally mention another technical point. Lecerf’s irreducibility
characterization [Lec07] assumes a technical condition on the polynomial,
which he called Hypothesis (H) (see Section 3). Such a “preprocessing” step,
which makes the polynomial monic in a certain distinguished variable, is
common to many factorization algorithms, and can usually be easily guaranteed
by applying a random linear transformation to the variables. However, doing
this in the naïve way would require the use of too many random bits. To solve
this problem, in Section 3 we show that this part can also be derandomized by
using a hitting set generator for polynomials of degree $O(d)$.

##  2 Preliminaries

We now define the basic objects studied in this paper and introduce the
fundamental mathematical concepts used.

#### Notations.

All logarithms are base $2$. Denote by $\mathbb{N}$ the set of natural numbers
$\\{0,1,2,\dots\\}$. For $n\in\mathbb{N}$, define $[n]=\\{1,2,\dots,n\\}$. For
a finite set $A$, denote by $\mathbf{U}_{A}$ the uniform distribution over
$A$.

We often use symbols in bold, e.g., $\mathbf{a}$ or $\mathbf{x}$, as the
shorthand for a vector $(a_{1},\dots,a_{n})$ or a sequence of variables
$x_{1},\dots,x_{n}$.

Denote by $\mathbb{F}_{q}$ the finite field of size $q$. The algebraic closure
of a field $\mathbb{F}$ is denoted by $\overline{\mathbb{F}}$. For a
commutative ring $A$ and variables $x_{1},\dots,x_{n}$, we denote by
$A[[x_{1},\dots,x_{n}]]$ or $A[[\mathbf{x}]]$ the _ring of formal power
series_ over $A$ in $x_{1},\dots,x_{n}$, i.e.,

$A[[\mathbf{x}]]=\left\\{\sum_{\mathbf{e}=(e_{1},\dots,e_{n})\in\mathbb{N}^{n}}a_{\mathbf{e}}x_{1}^{e_{1}}\cdots
x_{n}^{e_{n}}:a_{\mathbf{e}}\in A\right\\}.$

#### Pseudorandom Generators and Hitting Set Generators.

######  Definition 2.1 (Pseudorandom generator, PRG).

Let $\mathbb{F}_{q}$ be a finite field. A _pseudorandom generator (PRG)_ for
$n$-variate polynomials of degree at most $d$ over $\mathbb{F}_{q}$ with error
$\varepsilon$ is an efficiently computable map $G:S\to\mathbb{F}_{q}^{n}$ from
a finite set $S\neq\emptyset$ such that for every such polynomial $f$ of
degree at most $d$, the two distributions $f(G(\mathbf{U}_{S}))$ and
$f(\mathbf{U}_{\mathbb{F}_{q}^{n}})$ are $\varepsilon$-close in statistical
distance. That is,

$\frac{1}{2}\sum_{a\in\mathbb{F}_{q}}\left|\Pr_{\mathbf{x}\in\mathbb{F}_{q}^{n}}[f(\mathbf{x})=a]-\Pr_{\mathbf{y}\in
S}[f(G(\mathbf{y}))=a]\right|\leq\varepsilon.$

The quantity $\log|S|$ is called the _seed length_ of $G$.

A weaker object than a PRG is a _hitting set generator_. Here, we only require
that a nonzero polynomial is nonzero (with high probability) on the output of
the generator.

######  Definition 2.2 (Hitting set generator, HSG).

Let $\mathbb{F}$ be a field. A _hitting set generator (HSG)_ with density
$1-\delta$ for $n$-variate polynomials of degree at most $d$ over $\mathbb{F}$
is an efficiently computable map $H:S\to\mathbb{F}^{n}$ from a finite set
$S\neq\emptyset$ such that for every such nonzero polynomial $f$ of degree at
most $d$,

$\Pr_{\mathbf{y}\in S}[f(H(\mathbf{y}))=0]\leq\delta.$

The quantity $\log|S|$ is called the _seed length_ of $G$.

Building on the earlier work [KS01, Lu12] and algebraic-geometric codes,
Guruswami and Xing [GX14] constructed explicit HSGs for low-degree polynomials
with asymptotically optimal seed length and density.

######  Theorem 2.3 ([GX14]).

There exists an absolute constant $C$ such that for any $n,d,q,\delta$, such
that $q\geq Cd/\delta$, there exists an explicit HSG for $n$-variate
polynomials of degree at most $d$ over $\mathbb{F}_{q}$ with density
$1-\delta$ and seed length $O(d\log n+\log(1/\delta))$.

It should also be noted that for hitting set generators, the field
$\mathbb{F}$ does not have to be finite. This generality is used in the
statement of the following fact, that an HSG for a field $\mathbb{F}$ is also
a HSG for any extension field $\mathbb{K}$ of $\mathbb{F}$.

######  Fact 2.4 ([Bog05, DV22]).

Let $H:S\to\mathbb{F}$ be an HSG with density $1-\delta$ for polynomials of
degree at most $d$ over a field $\mathbb{F}$, and let $\mathbb{K}$ be an
extension of $\mathbb{F}$. Then $H$ is also an HSG with density $1-\delta$ for
polynomials of degree at most $d$ over $\mathbb{K}$.

###### Proof.

Let $\mathcal{B}$ be a basis of $\mathbb{K}$ over $\mathbb{F}$, and let $f$ be
a nonzero polynomial in $\mathbb{K}[x_{1},\ldots,x_{n}]$ of degree at most
$d$. By expressing every coefficient $c\in\mathbb{K}$ of a monomial in $f$ as
a linear combination $c=\sum_{b\in\mathcal{B}}a_{b}\cdot b$ with
$a_{b}\in\mathbb{F}$ for every $b\in\mathcal{B}$, we may write
$f=\sum_{b\in\mathcal{B}}f_{b}\cdot b$ such that
$f_{b}\in\mathbb{F}[x_{1},\ldots,x_{n}]$ is a polynomial of degree at most $d$
for every $b\in\mathcal{B}$, and at least one $f_{b}$ is nonzero. Thus, for
any $u\in S$, $f(H(u))=\sum_{b\in\mathcal{B}}f_{b}(u)\cdot b$ is nonzero
unless $f_{b}(H(u))=0$ for every $b$, which happens with probability at most
$\delta$ over the choice of $u\in S$. ∎

#### Indecomposable Polynomials.

The _indecomposability_ of a polynomial is crucially used in the analysis of
the PRG construction in [DV22] as well as in our analysis. We first define
this property.

######  Definition 2.5 (Indecomposability).

Let $f\in\mathbb{F}[\mathbf{x}]$ be a non-constant polynomial over a field
$\mathbb{F}$. It is said to be _decomposable_ over $\mathbb{F}$ if there exist
$h\in\mathbb{F}[\mathbf{x}]$ and a univariate polynomial $g\in\mathbb{F}[y]$
such that $\deg(g)\geq 2$ and $f=g(h)$. Otherwise, $f$ is said to be
_indecomposable_ over $\mathbb{F}$.

Obviously, if a polynomial $f\in\mathbb{F}_{q}[\mathbf{x}]$ over a finite
field $\mathbb{F}_{q}$ is indecomposable over $\overline{\mathbb{F}}_{q}$,
then it is also indecomposable over $\mathbb{F}_{q}$. The following lemma,
which is a special case of [BDN09, Theorem 4.2], states that the converse is
also true.

######  Lemma 2.6 ([BDN09, Theorem 4.2]).

A polynomial $f\in\mathbb{F}_{q}[\mathbf{x}]$ that is indecomposable over
$\mathbb{F}_{q}$ is also indecomposable over $\overline{\mathbb{F}}_{q}$.

In [DV22], Derksen and Viola proved the following result, which states that if
a polynomial is indecomposable, then its outputs are equidistributed.

######  Lemma 2.7 ([DV22, Lemma 12]).

There exists an absolute constant $C>0$ such that the following holds: Suppose
$f\in\mathbb{F}_{q}[\mathbf{x}]=\mathbb{F}_{q}[x_{1},\dots,x_{n}]$ is
indecomposable over $\mathbb{F}_{q}$. Then
$f(\mathbf{U}_{\mathbb{F}_{q}^{n}})$ is $\varepsilon$-close to
$\mathbf{U}_{\mathbb{F}_{q}}$, where $\varepsilon=Cd^{2}/\sqrt{q}$.

The proof of 2.7 is based on the observation that the indecomposability of $f$
precisely captures the property that for most $b\in\mathbb{F}_{q}$, the
variety $f^{-1}(b)$, defined by the constraint $f(\mathbf{x})=b$, is
_absolutely irreducible_. This condition of absolute irreducibility is
required by the _Weil bound_ [Wei49]. Consequently, one can apply the Weil
bound to show that for most $b$, the number of points in
$f^{-1}(b)\cap\mathbb{F}_{q}^{n}$ is close to $q^{n-1}$, thereby proving the
equidistribution of the output of $f$. For details, we refer the reader to
[DV22].

Finally, the following lemma connects indecomposability with irreducibility
over algebraically closed fields. It is explicitly stated in, e.g., [CN10].

######  Lemma 2.8 ([CN10, Lemma 7]).

Let $f\in\mathbb{F}[\mathbf{x}]$ be a non-constant polynomial over a field
$\mathbb{F}$. Then $f$ is indecomposable over $\overline{\mathbb{F}}$ iff
$f-t$ is irreducible over $\overline{\mathbb{F}(t)}$, where $t$ is a new
variable.

#### Resultants.

Let $f(x)=\sum_{i=0}^{d_{1}}a_{i}y^{i}$ and
$g(x)=\sum_{i=0}^{d_{2}}b_{i}y^{i}$ be two univariate polynomials in $y$ over
a field $\mathbb{F}$ and suppose that $d_{1}+d_{2}>0$. The _Sylvester Matrix_
of $f$ and $g$ is the $(d_{1}+d_{2})\times(d_{1}+d_{2})$ matrix

$\begin{pmatrix}a_{0}&&&&b_{0}&&&&\\\ a_{1}&a_{0}&&&b_{1}&b_{0}&&\\\
a_{2}&a_{1}&\ddots&&b_{2}&b_{1}&\ddots&&\\\
\vdots&&\ddots&a_{0}&\vdots&&\ddots&&b_{0}\\\
&\vdots&&a_{1}&b_{d_{2}}&\vdots&&&b_{1}\\\ a_{d_{1}}&&&&&b_{d_{2}}&&&\\\
&a_{d_{1}}&&\vdots&&&&\vdots&\\\ &&\ddots&&&&\ddots&&\\\
&&&a_{d_{1}}&&&&&b_{d_{2}}\end{pmatrix}_{\raisebox{2.0pt}{.}}$

The determinant of this matrix is called the _resultant_ of $f$ and $g$, and
is denoted $\mathrm{Res}\left(f,g\right)$. It holds that $f$ and $g$ have a
common factor if and only if $\mathrm{Res}\left(f,g\right)=0$ ([CLO07,
Proposition 3 in Chapter 3, Section 6]).

Thus, in the case where $g=\pdv{f}{y}$, it holds that
$\mathrm{Res}\left(f,g\right)\neq 0$ if and only if $f$ does not have a root
of multiplicity greater than one.

#### Hensel Lifting.

Hensel lifting is a general technique for “lifting” roots or factorizations of
a polynomial modulo an ideal $I$ of a ring $R$ to those modulo powers of $I$,
under some mild conditions. The use of Hensel’s lifting lemma is standard in
multivariate factorization algorithms, and it is available in various forms.
We state one standard form, which can be derived from [Eis95, Theorem 7.3] as
a special case. This form is particularly relevant to our discussion of
Lecerf’s techniques in Section 4.

######  Lemma 2.9 (Hensel’s lifting lemma).

Let $f\in\mathbb{F}[x_{1},\dots,x_{n},y]=\mathbb{F}[\mathbf{x},y]$ be a
nonzero polynomial over a field $\mathbb{F}$. Suppose
$\bar{\lambda}\in\mathbb{F}$ is a simple root of
$f(\mathbf{0},y)\in\mathbb{F}[y]$. Then there exists unique
$\lambda\in\mathbb{F}[[\mathbf{x}]]$ such that

  1. 1.

$f(\mathbf{x},\lambda)=0$, i.e., $\lambda$ is a root of $f$ as a univariate
polynomial in $y$ over $\mathbb{F}[\mathbf{x}]$, and

  2. 2.

$\lambda(\mathbf{0})=\bar{\lambda}$.

##  3 Hypothesis (H)

Lecerf’s papers [Lec06, Lec07] on multivariate polynomial factoring assume a
hypothesis about the polynomial $f$, which he calls Hypothesis (H). Such a
hypothesis can be satisfied with high probability by applying a random linear
transformation on the variables.

In this section, we discuss Lecerf’s Hypothesis (H) and show that, for our
purpose, the random linear transformation can be derandomized by using a HSG
for polynomials of degree $O(d)$. The fact that we are interested in the
irreducibility of $f-t$ for an indeterminate $t$, rather than that of $f$, is
crucial in keeping the degree linear in $d$.

Let $\mathbb{F}$ be a field. First, we define Hypothesis (H).

######  Definition 3.1 (Hypothesis (H) [Lec06, Lec07]).

Let $f\in\mathbb{F}[x_{1},\dots,x_{n},y]=\mathbb{F}[\mathbf{x},y]$ be a non-
constant polynomial. We say $f$ satisfies _Hypothesis (H)_ if

  1. 1.

$f$ is monic in $y$ and $\deg_{y}(f)=\deg(f)$,

  2. 2.

$\mathrm{Res}\left(f(\mathbf{0},y),\pdv{f}{y}(\mathbf{0},y)\right)\neq 0$.

We also need a family of invertible linear transformations defined as follows.

######  Definition 3.2.

For $\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{F}^{n}$, let $s_{\mathbf{a}}$ be
the $\mathbb{F}$-linear automorphism of $\mathbb{F}[\mathbf{x},y]$ that fixes
$y$ and sends $x_{i}$ to $x_{i}+a_{i}y$.

######  Lemma 3.3.

Let $f\in\mathbb{F}[\mathbf{x},y]$ be a nonzero polynomial of degree at most
$d$. Then there exists a nonzero polynomial $B\in\mathbb{F}[\mathbf{x}]$ of
degree at most $d$ such that for every $\mathbf{a}\in\mathbb{F}^{n}$
satisfying $B(\mathbf{a})\neq 0$, it holds that
$\deg_{y}(s_{\mathbf{a}}(f))=d$ and the coefficient of $y^{d}$ in
$s_{\mathbf{a}}(f)$ is in $\mathbb{F}^{\times}$.

###### Proof.

Let $f_{d}$ be the degree-$d$ homogeneous part of $f$, so that we can write
$f=f_{d}+g$ where $g=f-f_{d}$ has degree less than $d$. Write
$f_{d}=\sum_{i=0}^{d}c_{i}(\mathbf{x})y^{i}$, where each
$c_{i}\in\mathbb{F}[\mathbf{x}]$ is either zero or a homogeneous polynomial of
degree $d-i$.

Consider $\mathbf{a}\in\mathbb{F}^{n}$. Note that

$s_{\mathbf{a}}(f)=s_{\mathbf{a}}(f_{d})+s_{\mathbf{a}}(g)=\sum_{i=0}^{d}s_{\mathbf{a}}(c_{i}(\mathbf{x}))y^{i}+s_{\mathbf{a}}(g)=\sum_{i=0}^{d}c_{i}(\mathbf{x}+y\cdot\mathbf{a})y^{i}+g(\mathbf{x}+y\cdot\mathbf{a},y).$

As $\deg(g)\leq d$ and each $c_{i}$ is either zero or homogeneous of degree
$d-i$, we have that $\deg_{y}s_{\mathbf{a}}(f)\leq d$, and that the
coefficient of $y^{d}$ in $s_{\mathbf{a}}(f)$ is
$\sum_{i=0}^{d}c_{i}(\mathbf{a})\in\mathbb{F}$. So we may choose
$B=\sum_{i=0}^{d}c_{i}$, which is a nonzero polynomial of degree at most $d$.
∎

######  Lemma 3.4.

Assume $f\in\mathbb{F}[\mathbf{x},y]$ is a polynomial of degree $d\geq 1$ that
satisfies Item 1 of Hypothesis (H). Further assume that
$\mathrm{char}(\mathbb{F})$ is either zero or greater than $d$. Let
$c\in\mathbb{F}^{\times}$. Then $f+ct$ is a degree-$d$ polynomial satisfying
Hypothesis (H) as a polynomial over $\mathbb{F}(t)$.

###### Proof.

As $f$ satisfies Item 1 of Hypothesis (H) and has degree $d\geq 1$, so does
$f+ct$. So it suffices to verify Item 2. Write $f=\sum_{i=0}^{d}c_{i}y^{i}$,
where $c_{i}\in\mathbb{F}[\mathbf{x}]$ and $c_{d}=1$. Then
$\pdv{(f+ct)}{y}=\sum_{i=1}^{d}(i\cdot c_{i})y^{i-1}$, which has degree $d-1$
in $y$ since $d\cdot c_{d}=d\neq 0$ by the assumption about
$\mathrm{char}(\mathbb{F})$.

Let $\bar{c}_{i}=c_{i}(\mathbf{0})$ for $i=0,1,\dots,d$. Let
$h=\mathrm{Res}\left((f+ct)(\mathbf{0},y),\pdv{f+ct}{y}(\mathbf{0},y)\right)$.
Then $h$ is the determinant of the following $(2d-1)\times(2d-1)$ matrix:

$\begin{pmatrix}\bar{c}_{0}+ct&0&\cdots&0&\bar{c}_{1}&0&\cdots&0\\\
\bar{c}_{1}&\bar{c}_{0}+ct&\cdots&0&2\bar{c}_{2}&\bar{c}_{1}&\cdots&0\\\
\bar{c}_{2}&\bar{c}_{1}&\ddots&0&3\bar{c}_{3}&2\bar{c}_{2}&\ddots&0\\\
\vdots&\vdots&\ddots&\bar{c}_{0}+ct&\vdots&\vdots&\ddots&\bar{c}_{1}\\\
\bar{c}_{d}&\bar{c}_{d-1}&\cdots&\vdots&d\bar{c}_{d}&(d-1)\bar{c}_{d-1}&\cdots&\vdots\\\
0&\bar{c}_{d}&\ddots&\vdots&0&d\bar{c}_{d}&\ddots&\vdots\\\
\vdots&\vdots&\ddots&\bar{c}_{d-1}&\vdots&\vdots&\ddots&(d-1)\bar{c}_{d-1}\\\
0&0&\cdots&\bar{c}_{d}&0&0&\cdots&d\bar{c}_{d}\end{pmatrix}_{\raisebox{2.0pt}{.}}$

Observe that $\deg_{t}h\leq d-1$, and that the coefficient of $t^{d-1}$ in $h$
is $c^{d-1}(d\bar{c}_{d})^{d}=c^{d-1}d^{d}\neq 0$ since only those entries on
the diagonal contribute to this coefficient. This implies that $h\neq 0$,
i.e., $f+ct$ satisfies Item 2 of Hypothesis (H). ∎

######  Corollary 3.5.

Assume that $f\in\mathbb{F}[\mathbf{x},y]$ is a polynomial of degree $d\geq 1$
and that $\mathrm{char}(\mathbb{F})$ is either zero or greater than $d$. Then
there exists a nonzero polynomial $B\in\mathbb{F}[\mathbf{x}]$ of degree at
most $d$ such that for every $\mathbf{a}\in\mathbb{F}^{n}$ satisfying
$B(\mathbf{a})\neq 0$, $s_{\mathbf{a}}(f)-t$ equals a product $c\cdot g$ where
$c\in\mathbb{F}^{\times}$ and $g\in\mathbb{F}(t)[\mathbf{x},y]$ is a
degree-$d$ polynomial satisfying Hypothesis (H).

###### Proof.

Let $B$ be as in 3.3. Consider $\mathbf{a}\in\mathbb{F}^{n}$ satisfying
$B(\mathbf{a})\neq 0$. By 3.3, we may write
$s_{\mathbf{a}}(f)=c\cdot\tilde{g}$ where $c\in\mathbb{F}^{\times}$ and
$\tilde{g}$ satisfies Item 1 of Hypothesis (H). Then
$s_{\mathbf{a}}(f)-t=c\cdot\tilde{g}-t=c\cdot g$ where $g=\tilde{g}-c^{-1}t$.
By 3.4, $g$ is a degree-$d$ polynomial satisfying Hypothesis (H). ∎

Thus, by choosing good $\mathbf{a}\in\mathbb{F}$ via an explicit HSG for
polynomials of degree at most $d$ and performing the transformation $f\mapsto
s_{\mathbf{a}}(f)$, we may assume $f-t$ satisfies Hypothesis (H).

#### Satisfying Hypothesis (H) in Small Characteristics.

While our final result needs $\mathrm{char}(\mathbb{F})>d(d-1)$, the
assumption that $\mathrm{char}(\mathbb{F})$ is zero or large enough is not
crucial for the sake of satisfying Hypothesis (H). We now sketch how to modify
the proof of 3.4 when $0<\mathrm{char}(\mathbb{F})\leq d$.

Let $p=\mathrm{char}(\mathbb{F})>0$. For our purpose, we may assume
$\mathbb{F}$ is a perfect field and $f$ is indecomposable over $\mathbb{F}$.
This implies that $f\not\in\mathbb{F}[x_{1}^{p},\dots,x_{n}^{p},y^{p}]$. Then
it is not hard to show that there exists an integer $e>0$ coprime to $p$ such
that for random $\mathbf{a}\in\mathbb{F}^{n}$, with high probability, not only
is the coefficient of $y^{d}$ in $s_{\mathbf{a}}(f)$ nonzero, but so is the
coefficient of $y^{e}$. Choose the largest $e$ that has this property. After
replacing $f$ by $s_{\mathbf{a}}(f)$, the polynomial $\pdv{f+ct}{y}$ in the
proof of 3.4 would have degree $e-1$ instead of $d-1$ in $y$. Then
$\deg_{t}(h)=e-1$ and the coefficient of $t^{e-1}$ in $h$ is
$c^{e-1}(e\bar{c}_{e})^{d}$, which is nonzero iff
$\bar{c}_{e}=c_{e}(\mathbf{0})$ is nonzero. The latter condition can be
guaranteed with high probability by performing the substitutions $x_{i}\mapsto
x_{i}+b_{i}$ for random $\mathbf{b}=(b_{1},\dots,b_{n})\in\mathbb{F}^{n}$.
Finally, it is not difficult to show that the choices of $\mathbf{a}$ and
$\mathbf{b}$ can be derandomized by using an explicit HSG for polynomials of
degree $O(d)$.

##  4 Lecerf’s Techniques

We describe Lecerf’s techniques in this section. For simplicity, our
discussion is restricted to the special case where the base field is
algebraically closed.

Let $\mathbb{K}$ be an algebraically closed field, and let
$f\in\mathbb{K}[\mathbf{x},y]$ be a polynomial of degree $d\geq 1$ satisfying
Hypothesis (H). Define $\bar{f}:=f(\mathbf{0},y)\in\mathbb{K}[y]$. As
$\mathbb{K}$ is algebraically closed and
$\mathrm{Res}\left(f(\mathbf{0},y),\pdv{f}{y}(\mathbf{0},y)\right)\neq 0$, the
univariate polynomial $\bar{f}$ factorizes into distinct linear factors

$\bar{f}=\prod_{i=1}^{d}(y-\bar{\lambda}_{i})$

where $\bar{\lambda}_{i}\in\mathbb{K}$ for $i\in[d]$. By Hensel’s lifting
lemma, the above factorization of $\bar{f}$ over $\mathbb{K}$ lifts to a
factorization of $f$ into distinct linear factors

$f=\prod_{i=1}^{d}(y-\lambda_{i}),$

where $\lambda_{i}\in\mathbb{K}[[\mathbf{x}]]$ and
$\lambda_{i}(\mathbf{0})=\bar{\lambda}_{i}$ for $i\in[d]$.

Now we introduce new variables $\mathbf{z}=(z_{1},\dots,z_{n})$ and $x$, and
define $g:=f(z_{1}x,\dots,z_{n}x,y)\in\mathbb{K}[\mathbf{z},x,y]$. Then $g$
factorizes into linear factors

$g=\prod_{i=1}^{d}(y-\lambda_{i}(z_{1}x,\dots,z_{n}x))$

where each $\lambda_{i}(z_{1}x,\dots,z_{n}x)$ lives in
$\mathbb{K}[\mathbf{z}][[x]]$. For $i\in[d]$, let $g_{i}$ be the factor
$y-\lambda_{i}(z_{1}x,\dots,z_{n}x)$ of $g$, and let $\hat{g}_{i}$ be its
cofactor $\prod_{j\in[d]\setminus\\{i\\}}g_{j}$. So
$g_{i},\hat{g}_{i}\in\mathbb{K}[\mathbf{z}][[x]][y]$.

For $h\in A[[x]][y]$ over a commutative ring $A$ and $(j,k)\in\mathbb{N}^{2}$,
denote by $\mathrm{coeff}\left(h,x^{j}y^{k}\right)\in A$ the coefficient of
$x^{j}y^{k}$ in $h$. We are now ready to define the linear system
$D_{\mathbf{z},\sigma}$ used in [Lec06, Lec07].

######  Definition 4.1 (Linear system $D_{\mathbf{z},\sigma}$ [Lec06, Lec07]).

Let $\sigma\in\mathbb{N}$. Define $D_{\mathbf{z},\sigma}$ to be the following
linear system over $\mathbb{K}(\mathbf{z})$ in the unknowns
$\ell_{1},\dots,\ell_{d}$:

$D_{\mathbf{z},\sigma}\begin{dcases}\sum_{i=1}^{d}\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{y},x^{j}y^{k}\right)\cdot\ell_{i}=0,\quad
k\leq d-1,~{}d\leq j+k\leq\sigma-1,\\\
\sum_{i=1}^{d}\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{x},x^{j}y^{k}\right)\cdot\ell_{i}=0,\quad
k\leq d-1,~{}j\leq\sigma-2,~{}d\leq j+k\leq\sigma-1.\end{dcases}$

We have the following easy lemma.

######  Lemma 4.2.

For $(j,k)\in\mathbb{N}^{2}$,
$\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{x},x^{j}y^{k}\right),\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{y},x^{j}y^{k}\right)\in\mathbb{K}[\mathbf{z}]$
are polynomials of degree at most $j+1$ and $j$ respectively.

###### Proof.

Consider arbitrary $i\in[d]$ and $(j,k)\in\mathbb{N}^{2}$. As
$g_{i}=y-\lambda_{i}(z_{1}x,\dots,z_{n}x)$ and $j\geq 0$, only terms of degree
at most $j$ in $z_{1},\dots,z_{n}$ contribute to the coefficient of
$x^{j}y^{k}$ in $g_{i}$. Then, as the operator $\pdv{}{x}$ is linear and sends
$x^{u}y^{v}$ to $ux^{u-1}y^{v}$ for all $u,v\in\mathbb{N}$, one can see that
only terms of degree at most $j+1$ in $z_{1},\dots,z_{n}$ contribute to the
coefficient of $x^{j}y^{k}$ in $\pdv{g_{i}}{x}$. Also, $\pdv{g_{i}}{y}=1$ by
definition.

For a collection of polynomials
$h_{1},\dots,h_{s}\in\mathbb{K}[\mathbf{z}][[x]][y]$ and
$h=\prod_{i=1}^{s}h_{i}$, we have

$\mathrm{coeff}\left(h,x^{j}y^{k}\right)=\sum_{\begin{subarray}{c}j_{1},\dots,j_{s},k_{1},\dots,k_{s}\in\mathbb{N}\\\
\sum_{i}j_{i}=j,\sum_{i}k_{i}=k\end{subarray}}\prod_{i=1}^{s}\mathrm{coeff}\left(h_{i},x^{j_{i}}y^{k_{i}}\right).$
(1)

We already know
$\deg\left(\mathrm{coeff}\left(g_{i},x^{j}y^{k}\right)\right)\leq j$,
$\deg\left(\mathrm{coeff}\left(\pdv{g_{i}}{x},x^{j}y^{k}\right)\right)\leq
j+1$, and
$\deg\left(\mathrm{coeff}\left(\pdv{g_{i}}{y},x^{j}y^{k}\right)\right)=0$ for
$i\in[d]$ and $(j,k)\in\mathbb{N}^{2}$ by the above discussion. Choosing
$(h_{1},\dots,h_{s})$ to be $(g_{1},\dots,g_{i-1},g_{i+1},\dots
g_{d},\pdv{g_{i}}{x})$ and $(g_{1},\dots,g_{i-1},g_{i+1},\dots
g_{d},\pdv{g_{i}}{y})$ respectively and applying (1) proves the claim. ∎

For $\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{K}^{n}$, we can assign
$a_{1}\dots,a_{n}$ to $z_{1},\dots,z_{n}$ respectively in the polynomials
$\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{x},x^{j}y^{k}\right),\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{y},x^{j}y^{k}\right)\in\mathbb{K}[\mathbf{z}]$.
This yields a linear system over $\mathbb{K}$, called the _specialization_ of
$D_{\mathbf{z},\sigma}$ at $\mathbf{a}$ and denoted by
$D_{\mathbf{a},\sigma}$.

######  Definition 4.3 (Specialization).

For $\sigma\in\mathbb{N}$ and
$\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{K}^{n}$, define
$D_{\mathbf{a},\sigma}$ to be the following linear system over $\mathbb{K}$ in
the unknowns $\ell_{1},\dots,\ell_{d}$:

$D_{\mathbf{a},\sigma}\begin{dcases}\sum_{i=1}^{d}\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{y},x^{j}y^{k}\right)(\mathbf{a})\cdot\ell_{i}=0,\quad
k\leq d-1,~{}d\leq j+k\leq\sigma-1,\\\
\sum_{i=1}^{d}\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{x},x^{j}y^{k}\right)(\mathbf{a})\cdot\ell_{i}=0,\quad
k\leq d-1,~{}j\leq\sigma-2,~{}d\leq j+k\leq\sigma-1.\end{dcases}$

For $S\subseteq[d]$, define
$\delta_{S}=(\delta_{S,1},\dots,\delta_{S,d})\in\mathbb{K}^{d}$ by

$\delta_{S,i}=\begin{cases}1&i\in S,\\\ 0&i\not\in S.\end{cases}$

For every factor $\tilde{f}$ of $f$, we may associate a set $S\subseteq[d]$
such that $\tilde{f}=\prod_{i\in S}(y-\lambda_{i})$, i.e., $S$ is the set of
indices $i\in[d]$ such that $y-\lambda_{i}$ divides $\tilde{f}$. Then
irreducible factors $f_{1},\dots,f_{r}$ of $f$ over $\mathbb{K}$ are then
associated with sets $S_{1},\dots,S_{r}\subseteq[d]$, which form a partition
of $[d]$. In [Lec06, Lec07], Lecerf proved that, when $\sigma$ is large
enough, the solution space of $D_{\mathbf{z},\sigma}$ is exactly spanned by
the vectors $\delta_{S_{1}},\dots,\delta_{S_{r}}$, and a similar statement
holds for the specializations $D_{\mathbf{a},\sigma}$. We state Lecerf’s
results formally as the following theorem.

######  Theorem 4.4 ([Lec06, Lec07]).

Assume $\mathrm{char}(\mathbb{K})$ is zero or greater than $d(d-1)$. Let
$\sigma\geq 2d$. Let $f\in\mathbb{K}[\mathbf{x},y]$ be a polynomial of degree
$d\geq 1$ satisfying Hypothesis (H). Then:

  1. 1.

Suppose $f=\prod_{i=1}^{r}f_{i}$ is the factorization of $f$ into its
irreducible factors over $\mathbb{K}$. For $i\in[r]$, let $S_{i}$ be the set
of indices $j\in[d]$ such that $y-\lambda_{j}$ divides $f_{i}$. Then
$\delta_{S_{1}},\dots,\delta_{S_{r}}$ form a basis of the solution space of
$D_{\mathbf{z},\sigma}$.

  2. 2.

Let $\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{K}^{n}$ and
$f_{\mathbf{a}}=f(a_{1}x,\dots,a_{n}x,y)\in\mathbb{K}[x,y]$. Suppose
$f_{\mathbf{a}}=\prod_{i=1}^{s}f_{\mathbf{a},i}$ is the factorization of
$f_{\mathbf{a}}$ into its irreducible factors over $\mathbb{K}$. For
$i\in[s]$, let $S_{\mathbf{a},i}$ be the set of indices $j\in[d]$ such that
$y-\lambda_{j}(a_{1}x,\dots,a_{n}x)$ divides $f_{\mathbf{a},i}$. Then
$\delta_{S_{\mathbf{a},1}},\dots,\delta_{S_{\mathbf{a},s}}$ form a basis of
the solution space of $D_{\mathbf{a},\sigma}$.

The first item of 4.4 is explicitly stated as [Lec07, Lemma 1]. The second
item follows from [Lec06, Theorem 1 and Lemma 4]. For a detailed analysis of
the linear systems $D_{\mathbf{z},\sigma}$ and $D_{\mathbf{a},\sigma}$, and
for a conceptual interpretation of these linear systems in terms of the
closedness condition of differential 1-forms, we refer the reader to [Lec06,
Lec07], as well as to the earlier paper of Gao [Gao03].

#### Bertinian Good/Bad Points.

The classical Bertini irreducibility theorem [Sha94] states, among other
things, that over an algebraically closed field $\mathbb{K}$, the intersection
of an irreducible variety with a plane in general position is still
irreducible. This motivates the following definition:

######  Definition 4.5 (Bertinian good/bad points [Lec07]).

Let $f\in\mathbb{K}[\mathbf{x},y]$ be a non-constant polynomial satisfying
Hypothesis (H). We say $\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{K}^{n}$ is a
_Bertinian good point_ for $f$ if for every irreducible factor $\tilde{f}$ of
$f$ over $\mathbb{K}$, the bivariate polynomial
$\tilde{f}_{\mathbf{a}}=\tilde{f}(a_{1}x,\dots,a_{n}x,y)$ is also irreducible
over $\mathbb{K}$. We say $\mathbf{a}=(a_{1},\dots,a_{n})\in\mathbb{K}^{n}$ is
a _Bertinian bad point_ for $f$ if it is not a Bertinian good point for $f$.

Lecerf [Lec07, Theorem 6] proved that given $f$, there exists a nonzero
polynomial $Q\in\mathbb{K}[z_{1},\dots,z_{n}]$ of degree at most $(d-1)(2d-1)$
that vanishes at all Bertinian bad points for $f$, where $d=\deg(f)$. Let $M$
be the matrix representing the linear system $D_{\mathbf{z},\sigma}$. Lecerf’s
proof can be sketched as follows: By 4.4, the solution space of
$D_{\mathbf{a},\sigma}$ contains that of $D_{\mathbf{z},\sigma}$, and
$\mathbf{a}$ is Bertinian good as long as the two are equal. Thus, we may
choose $Q$ to be the determinant of the largest nonsingular submatrix of $M$.
This is because for such $Q$, if $Q$ does not vanish at $\mathbf{a}$, then
$D_{\mathbf{z},\sigma}$ and $D_{\mathbf{a},\sigma}$ have the same rank, and
hence their solution spaces must be equal. The bound $(d-1)(2d-1)$ on the
degree of $Q$ follows from 4.2.

In [Lec07], Lecerf also demonstrated that the degree bound $(d-1)(2d-1)$ is
asymptotically tight by providing an example for which a degree of
$\Omega(d^{2})$ of the polynomial $Q$ is necessary. However, our next lemma
states that, perhaps surprisingly, the degree bound can be improved to $2d-1$
if we allow the use of the zero loci of _multiple_ polynomials to cover the
Bertinian bad points for $f$. For simplicity, we state the lemma in the
special case where $f$ is irreducible, which suffices for our purpose.

######  Lemma 4.6.

Assume $\mathrm{char}(\mathbb{K})$ is zero or greater than $d(d-1)$. Let
$f\in\mathbb{K}[\mathbf{x},y]$ be a irreducible polynomial over $\mathbb{K}$
of degree $d\geq 1$ satisfying Hypothesis (H). Let $m=2^{d-1}-1$. Then there
exist nonzero polynomials
$Q_{1},\dots,Q_{m}\in\mathbb{K}[\mathbf{z}]=\mathbb{K}[z_{1},\dots,z_{n}]$ of
degree at most $2d-1$ such that for every Bertinian bad point
$\mathbf{a}\in\mathbb{K}^{n}$ for $f$, at least one polynomial $Q_{i}$
vanishes at $\mathbf{a}$.

###### Proof.

Let $\sigma=2d$. Let $N$ be the number of equations in
$D_{\mathbf{z},\sigma}$. Let $M$ be the $N\times d$ matrix over
$\mathbb{F}(\mathbf{z})$ representing the linear system
$D_{\mathbf{z},\sigma}$. Note that by 4.1, the entries of $M$ are of the form
$\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{x},x^{j}y^{k}\right)$ with
$j\leq\sigma-2$ or
$\mathrm{coeff}\left(\hat{g}_{i}\pdv{g_{i}}{y},x^{j}y^{k}\right)$ with
$j\leq\sigma-1$. By 4.2 and the fact that $\sigma=2d$, the entries of $M$ are
polynomials in $\mathbb{K}[\mathbf{z}]$ of degree at most $2d-1$.

There are exactly $m=2^{d-1}-1$ proper subsets of $[d]$ containing $1$. Let
$S_{1},\dots,S_{m}$ be an enumeration of them. Consider $i\in[m]$. As $f$ is
irreducible, by 4.4, $\delta_{S_{i}}$ is not in the solution space of
$D_{\mathbf{z},\sigma}$. So we can fix a row
$\mathbf{r}_{i}=(r_{i,1},\dots,r_{i,d})$ of $M$ such that the inner product of
$\mathbf{r}_{i}$ and $\delta_{S_{i}}$ is nonzero, i.e.,
$\sum_{j=1}^{d}r_{i,j}\delta_{S_{i},j}\neq 0$. Let
$Q_{i}=\sum_{j=1}^{d}r_{i,j}\delta_{S_{i},j}$, which is a nonzero polynomial
in $\mathbb{K}[\mathbf{z}]$ of degree at most $2d-1$. Choose $Q_{i}$ in this
way for each $i=1,\dots,m$.

Now let $\mathbf{a}$ be a Bertinian bad point for $f$. Then
$f_{\mathbf{a}}=f(a_{1}x,\dots,a_{n}x,y)$ factorizes into more than one
irreducible factor over $\mathbb{K}$. Let $\tilde{f}_{\mathbf{a}}$ be the
irreducible factor of $f_{\mathbf{a}}$ divisible by
$y-\lambda_{1}(a_{1}x,\dots,a_{n}x)$. Let $S$ be the set of $j\in[d]$ such
that $\tilde{f}_{\mathbf{a}}$ is divisible by
$y-\lambda_{j}(a_{1}x,\dots,a_{n}x)$. Then $S$ is a proper subset of $[d]$
containing $1$. So $S=S_{i}$ for some $i\in[m]$. By 4.4, $\delta_{S_{i}}$ is
in the solution space of $D_{\mathbf{a},\sigma}$. As $D_{\mathbf{a},\sigma}$
is the specialization of $D_{\mathbf{z},\sigma}$ at $\mathbf{a}$, the vector
$(r_{i,1}(\mathbf{a}),\dots,r_{i,d}(\mathbf{a}))$ is a row of the matrix
representing $D_{\mathbf{a},\sigma}$. So
$\sum_{j=1}^{d}r_{i,j}(\mathbf{a})\delta_{S_{i},j}=0$, i.e.,
$Q_{i}(\mathbf{a})=0$. ∎

#### The Number of Low-Degree Polynomials Needed.

It is an intriguing mathematical question to us how many low-degree
polynomials are needed to cover the Bertinian bad points for $f$. We now
formalize this question.

######  Definition 4.7.

Let $\mathbb{K}$ be an algebraically closed field. For positive integers $d$
and $D$, define $N(d,D,\mathbb{K})$ to be the smallest $N\in\mathbb{N}$ such
that the following holds: Let $f\in\mathbb{K}[\mathbf{x},y]$ be an irreducible
polynomial of degree at most $d$ over $\mathbb{K}$ satisfying Hypothesis (H).
Then there exist $N$ nonzero polynomials in $\mathbb{K}[\mathbf{z}]$ of degree
at most $D$ such that the union of the zero loci of these polynomials contains
all Bertinian bad points for $f$ in $\mathbb{K}^{n}$.

If such $N$ does not exist, define $N(d,D,\mathbb{K})=\infty$.

In our application, it suffices to consider polynomials of the special form
$f+c\cdot t$, where $c\in\mathbb{F}^{\times}$, $f\in\mathbb{F}[\mathbf{x},y]$
and $\mathbb{K}=\overline{\mathbb{F}(t)}$. Moreover, by performing a variable
substitution $t\mapsto-c^{-1}t$, we may assume $c=-1$. This motivates us to
introduce the following variant of 4.7:

######  Definition 4.8.

Let $\mathbb{F}$ be a field. For positive integers $d$ and $D$, define
$N^{*}(d,D,\mathbb{F})$ to be the smallest $N\in\mathbb{N}$ such that the
following holds: Let $f\in\mathbb{F}[\mathbf{x},y]$ be a polynomial of degree
at most $d$ such that $f-t$ is an irreducible polynomial over
$\overline{\mathbb{F}(t)}$ satisfying Hypothesis (H). Then there exist $N$
nonzero polynomials in $\overline{\mathbb{F}(t)}[\mathbf{z}]$ of degree at
most $D$ such that the union of the zero loci of these polynomials contains
all Bertinian bad points for $f-t$ in $\overline{\mathbb{F}}^{n}$.

If such $N$ does not exist, define $N^{*}(d,D,\mathbb{F})=\infty$.

Lecerf’s result [Lec07, Theorem 6] can be interpreted as the statement that
when $\mathrm{char}(\mathbb{K})$ is zero or greater than $d(d-1)$, it holds
that

$N(d,D,\mathbb{K})=1\text{ for }D\geq(d-1)(2d-1).$

Our 4.6 states that under the same condition, we have

$N(d,D,\mathbb{K})\leq 2^{d-1}-1\text{ for }D\geq 2d-1.$

In [Lec07], Lecerf gave an example showing that the degree bound $O(d^{2})$
for the smallest $D$ satisfying $N(d,D,\mathbb{K})=1$ is asymptotically
tight.222See the example before Theorem 6 in [Lec07]. As one can always
combine the $N(d,D,\mathbb{K})$ polynomials of degree at most $D$ into a
single polynomial of degree at most $N(d,D,\mathbb{K})\cdot D$ by taking their
product, this implies $N(d,D,\mathbb{K})\cdot D=\Omega(d^{2})$, i.e.,
$N(d,D,\mathbb{K})=\Omega(d^{2}/D)$.

######  Question 4.9.

Give improved upper bounds (or lower bounds) on $N(d,D,\mathbb{K})$ and
$N^{*}(d,D,\mathbb{F})$, at least when the characteristic of $\mathbb{K}$ or
$\mathbb{F}$ is zero or large enough.

By definition, $N^{*}(d,D,\mathbb{F})\leq N(d,D,\overline{\mathbb{F}(t)})$. A
subexponential upper bound on $N^{*}(d,D,\mathbb{F})$ for $D=O(d)$ will
improve the required field size in 1.1.

Finally, it might be possible to exploit some extra structure to derive better
bounds on $N^{*}(d,D,\mathbb{F})$ than those obtained for $N(d,D,\mathbb{K})$.
For example, if we modify the definition of $N^{*}(d,D,\mathbb{F})$ by only
considering those polynomials $f$ of _prime_ degree, then
$N^{*}(d,2d-1,\mathbb{F})\leq 1$. This is because if $f_{\mathbf{a}}-t$ is
reducible over $\overline{\mathbb{F}(t)}$, then $f_{\mathbf{a}}$ is
decomposable over $\overline{\mathbb{F}}$ by 2.8. But as $\deg(f)$ is prime,
$f_{\mathbf{a}}$ must be of the form $g(h)$ with $\deg(g)=\deg(f)$ and $\deg
h=1$. This in turn implies that $f_{\mathbf{a}}-t$ factorizes into $\deg(f)$
linear factors over $\overline{\mathbb{F}_{q}(t)}$. In 5.4, we use this idea
to show that the required field size can be improved to
$O(d^{4}/\varepsilon^{2})$ if we only want to fool polynomials whose degrees
are prime and at most $d$.

##  5 Proofs of the Main Theorems

In this section, we present our PRG construction and prove the main theorems.

Let $n$ and $d$ be positive integers. Let $\mathbb{F}_{q}$ be a finite field
of characteristic at least $d(d-1)+1$. We now present the construction of our
PRG

$G:S\to\mathbb{F}_{q}^{n+1}$

for polynomials
$f\in\mathbb{F}_{q}[\mathbf{x},y]=\mathbb{F}_{q}[x_{1},\dots,x_{n},y]$ of
degree at most $d$. To simplify our notation, these polynomials are assumed to
be $(n+1)$-variate rather than $n$-variate.

######  Construction 5.1.

The construction is as follows:

  * •

Let $H:T\to\mathbb{F}_{q}^{n}$ be an explicit HSG for $n$-variate polynomials
of degree at most $2d-1$ over $\mathbb{F}_{q}$ with density $1-\delta$ and
seed length $\log|T|=O(d\log n+\log(1/\delta))$, where $\delta=C_{0}(2d-1)/q$
and $C_{0}>0$ is an absolute constant. For $i\in[n]$ and $s\in T$, denote the
$i$-th coordinate of $H(s)$ by $H(s)_{i}$. The existence of $H$ is guaranteed
by 2.3.

  * •

Let $S=T\times T\times\mathbb{F}_{q}\times\mathbb{F}_{q}$. Define
$G:S\to\mathbb{F}_{q}^{n+1}$ by

$G(r,s,u,v)=(H(s)_{1}\cdot u+H(r)_{1}\cdot v,\dots,H(s)_{n}\cdot
u+H(r)_{n}\cdot v,v).$

In other words, we use random $(r,s)\in T\times T$ to pick a plane in
$\mathbb{F}_{q}^{n+1}$, and use random
$(u,v)\in\mathbb{F}_{q}\times\mathbb{F}_{q}$ to pick a point on the plane. The
following lemma states that with high probability, a given indecomposable
polynomial $f\in\mathbb{F}_{q}[\mathbf{x},y]$ remains indecomposable when
restricted to the plane.

######  Lemma 5.2.

Let $f\in\mathbb{F}_{q}[\mathbf{x},y]$ be an indecomposable polynomial of
degree at most $d$ over $\mathbb{F}_{q}$. Let $(r,s)$ be a random element of
$T\times T$. Let $\mathbf{a}=(a_{1},\dots,a_{n})=H(r)$ and
$\mathbf{b}=(b_{1},\dots,b_{n})=H(s)$. Finally, let
$F=f(b_{1}x+a_{1}y,\dots,b_{n}x+a_{n}y,y)\in\mathbb{F}_{q}[x,y]$. Then

$\Pr\left[F~{}\text{is indecomposable over}~{}\mathbb{F}_{q}\right]\geq
1-2^{d-1}\delta.$

###### Proof.

Recall that $s_{\mathbf{a}}$ is the $\mathbb{F}_{q}$-linear automorphism of
$\mathbb{F}_{q}[\mathbf{x},y]$ that fixes $y$ and sends $x_{i}$ to
$x_{i}+a_{i}y$. As $f$ is indecomposable over $\mathbb{F}_{q}$, so is
$s_{\mathbf{a}}(f)$. By 2.6, $s_{\mathbf{a}}(f)$ is also indecomposable over
$\overline{\mathbb{F}}_{q}$. So $s_{\mathbf{a}}(f)-t$ is irreducible over
$\overline{\mathbb{F}_{q}(t)}$ by 2.8.

By 3.5, there exists a nonzero polynomial $B\in\mathbb{F}_{q}[\mathbf{x}]$ of
degree at most $d$ such that if $B(\mathbf{a})\neq 0$, then

$s_{\mathbf{a}}(f)-t=c\cdot g$ (2)

where $c\in\mathbb{F}_{q}^{\times}$ and
$g\in\mathbb{F}_{q}(t)[\mathbf{x},y]\subseteq\overline{\mathbb{F}_{q}(t)}[\mathbf{x},y]$
is a degree-$d$ polynomial satisfying Hypothesis (H). By the HSG property of
$H$, the event $B(\mathbf{a})\neq 0$ happens with probability at least
$1-\delta$. Condition on this event, so that (2) holds. As
$s_{\mathbf{a}}(f)-t$ is irreducible over $\overline{\mathbb{F}_{q}(t)}$, so
is $g$.

Let $m=2^{d-1}-1$. By 4.6, there exist nonzero polynomials
$Q_{1},\dots,Q_{m}\in\overline{\mathbb{F}_{q}(t)}[z_{1},\dots,z_{n}]$ of
degree at most $2d-1$ such that the union of the zero loci of these
polynomials contains all
$\mathbf{b}^{*}=(b_{1}^{*},\dots,b_{n}^{*})\in\overline{\mathbb{F}}_{q}^{n}$
for which $g(b_{1}^{*}x,\dots,b_{n}^{*}x,y)$ is reducible over
$\overline{\mathbb{F}_{q}(t)}$. By 2.4, $H$ is an HSG with density $1-\delta$
for polynomials of degree at most $2d-1$ over
$\overline{\mathbb{F}_{q}(t)}$.333Note that we are applying 2.4 to the
infinite extension $\overline{\mathbb{F}_{q}(t)}/\mathbb{F}_{q}$. In
principle, it should be possible to make the argument finitary by making some
adaptations, such as considering specific values of $t$. However, this may
increase the complexity of the proof. Therefore, for each $i\in[m]$, the
probability that $Q_{i}(\mathbf{b})=0$ is at most $\delta$. Condition on the
event $Q_{1}(\mathbf{b}),\dots,Q_{m}(\mathbf{b})\neq 0$. Then
$g(b_{1}x,\dots,b_{n}x,y)$ is irreducible over $\overline{\mathbb{F}_{q}(t)}$.
On the other hand, note that

$c\cdot
g(b_{1}x,\dots,b_{n}x,y)\stackrel{{\scriptstyle\eqref{eq:cdotg}}}{{=}}(s_{\mathbf{a}}(f))(b_{1}x,\dots,b_{n}x,y)-t=f(b_{1}x+a_{1}y,\dots,b_{n}x+a_{n}y,y)-t=F-t$

where the second step uses the definition
$s_{\mathbf{a}}(f)=f(x_{1}+a_{1}y,\dots,x_{n}+a_{n}y,y)\in\mathbb{F}_{q}[\mathbf{x},y]$.
So $F-t$ is irreducible over $\overline{\mathbb{F}_{q}(t)}$. By 2.8, $F$ is
indecomposable over $\overline{\mathbb{F}}_{q}$. So it is indecomposable over
$\mathbb{F}_{q}$.

The indecomposability of $F$ over $\mathbb{F}_{q}$ relies on the conditions
$B(\mathbf{a})\neq 0$ and $Q_{1}(\mathbf{b}),\dots,Q_{m}(\mathbf{b})\neq 0$.
By the union bound, these conditions are simultaneously satisfied with
probability at least $1-\delta-m\delta=1-2^{d-1}\delta$, which completes the
proof. ∎

Now we are ready to prove 1.1.

######  Theorem 5.3 (1.1 restated).

There exists an absolute constant $C>0$ such that for $\varepsilon>0$ and
$q\geq C(d2^{d}/\varepsilon+d^{4}/\varepsilon^{2})$ with
$\mathrm{char}(\mathbb{F}_{q})\geq d(d-1)+1$, $G$ as in 5.1 is a PRG for
$(n+1)$-variate polynomials of degree at most $d$ over $\mathbb{F}_{q}$ with
error $\varepsilon$ and seed length $O(d\log n+\log q)$.

###### Proof.

Let $f\in\mathbb{F}_{q}[\mathbf{x},y]$ be a polynomial of degree at most $d$.
We want to prove that $f(G(\mathbf{U}_{S}))$ and
$f(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})$ are $\varepsilon$-close (in statistical
distance). We may assume that $f$ is a non-constant polynomial, i.e.,
$\deg(f)\geq 1$, since the claim is trivial otherwise.

Our next step is the same as in [DV22]: $f$ can always be written in the form
$f=g(h)$, where $g\in\mathbb{F}_{q}[z]$ is a univariate polynomial and
$h\in\mathbb{F}_{q}[\mathbf{x},y]$ is indecomposable over $\mathbb{F}_{q}$.
Let $D=h(G(\mathbf{U}_{S}))$ and
$D^{\prime}=h(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})$. Then
$f(G(\mathbf{U}_{S}))=g(D)$ and
$f(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})=g(D^{\prime})$. If $D$ and $D^{\prime}$
are $\varepsilon$-close, then $g(D)$ and $g(D^{\prime})$ are also
$\varepsilon$-close. Thus, by replacing $f$ with $h$, we may assume that $f$
is indecomposable over $\mathbb{F}_{q}$.

Let $r,s,\mathbf{a},\mathbf{b}$ and $F$ be as in 5.2. Then by 5.2, the
probability that $F$ is decomposable over $\mathbb{F}_{q}$ over random $r$ and
$s$ is at most $2^{d-1}\delta=C_{0}2^{d-1}(2d-1)/q$, where $C_{0}$ is as in
5.1. Fix $r$ and $s$ such that $F$ is indecomposable over $\mathbb{F}_{q}$.
Then $f(G(r,s,u,v))=F(u,v)$ by definition. Applying 2.7 to $F$ shows that, for
such fixed $r$ and $s$, the distribution of $F(u,v)$, i.e., $f(G(r,s,u,v))$,
over random $u,v\in\mathbb{F}_{q}$ is $\varepsilon^{\prime}$-close to
$\mathbf{U}_{\mathbb{F}_{q}}$, where
$\varepsilon^{\prime}=C_{1}d^{2}/\sqrt{q}$ and $C_{1}>0$ is an absolute
constant. It follows that the statistical distance between
$f(G(\mathbf{U}_{S}))$ and $\mathbf{U}_{\mathbb{F}_{q}}$ is at most
$2^{d-1}\delta+\varepsilon^{\prime}$.

On the other hand, as $f$ is also indecompsable over $\mathbb{F}_{q}$,
applying 2.7 to $f$ shows that $f(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})$ is
$\varepsilon^{\prime}$-close to $\mathbf{U}_{\mathbb{F}_{q}}$. Therefore, the
statistical distance between $f(G(\mathbf{U}_{S}))$ and
$f(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})$ is at most

$(2^{d-1}\delta+\varepsilon^{\prime})+\varepsilon^{\prime}=2^{d-1}\delta+2\varepsilon^{\prime}=C_{0}2^{d-1}(2d-1)/q+2C_{1}d^{2}/\sqrt{q}$
(3)

which is bounded by $\varepsilon$ provided that $q\geq
C(d2^{d}/\varepsilon+d^{4}/\varepsilon^{2})$ and $C>0$ is a large enough
absolute constant. The seed length of $G$ is

$2\log|T|+2\log q=O(d\log n+\log(1/\delta)+\log q)=O(d\log n+\log q)$

as $\delta=C_{0}(2d-1)/q$. ∎

We conclude this section by proving 1.2, which states that the required field
size can be improved to $O(d^{4}/\varepsilon^{2})$ if we only want to fool
polynomials of prime degree.

######  Theorem 5.4 (1.2 restated).

There exists an absolute constant $C>0$ such that for $\varepsilon>0$ and
$q\geq C(d^{4}/\varepsilon^{2})$ with $\mathrm{char}(\mathbb{F}_{q})\geq
d(d-1)+1$, $G$ as in 5.1 is a PRG for $(n+1)$-variate polynomials of _prime_
degree up to $d$ with error $\varepsilon$ and seed length $O(d\log n+\log q)$.

###### Proof Sketch.

Let $f\in\mathbb{F}_{q}[\mathbf{x},y]$ be a polynomial whose degree
$d^{\prime}$ is prime and at most $d$. We want to prove that
$f(G(\mathbf{U}_{S}))$ and $f(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})$ are
$\varepsilon$-close (in statistical distance). Suppose $f$ is decomposable
over $\mathbb{F}_{q}$. Then $f=g(h)$ for some polynomials $g,h$ over
$\mathbb{F}_{q}$ where $\deg(g)\geq 2$, and as $d^{\prime}=\deg(f)$ is prime,
we must have $\deg(g)=d^{\prime}$ and $\deg(h)=1$. In this case, the theorem
follows by replacing $f$ with $h$, which has degree one, and applying 5.3. So
we may assume that $f$ is indecomposable over $\mathbb{F}_{q}$.

The rest of the proof follows that of 5.3, except that we could bound the
probability that $F$ is decomposable over $\mathbb{F}_{q}$ by $2\delta$,
rather than by $2^{d-1}\delta$, using the following observation:

In the application of 4.6, the polynomial has the special form
$g^{*}=f^{*}+ct$, where $f^{*}\in\mathbb{F}_{q}[\mathbf{x},y]$,
$c\in\mathbb{F}_{q}^{\times}$, and $\deg(f^{*})=d^{\prime}$. By making the
substitution $t\mapsto-c^{-1}t$, we may assume $c=-1$. Consider any
$\mathbf{a}\in\overline{\mathbb{F}}_{q}^{n}$ such that
$g^{*}_{\mathbf{a}}=g^{*}(a_{1}x,\dots,a_{n}x,y)$ is reducible over
$\overline{\mathbb{F}_{q}(t)}^{n}$. We claim that $g^{*}_{\mathbf{a}}$
factorizes into linear factors over $\overline{\mathbb{F}_{q}(t)}$. To see
this, note that $f^{*}_{\mathbf{a}}=f^{*}(a_{1}x,\dots,a_{n}x,y)$ is a
decomposable polynomial over $\overline{\mathbb{F}}_{q}$ of degree
$d^{\prime}$ by 2.8 and the fact that
$g^{*}_{\mathbf{a}}=f^{*}_{\mathbf{a}}-t$ is reducible over
$\overline{\mathbb{F}_{q}(t)}$. So we may write
$f^{*}_{\mathbf{a}}=\alpha(\beta)$ where
$\alpha\in\overline{\mathbb{F}}_{q}[z]$,
$\beta\in\overline{\mathbb{F}}_{q}[\mathbf{x},y]$, and $\deg(\alpha)>1$. As
$d^{\prime}$ is prime, we must have $\deg(\alpha)=d^{\prime}$ and
$\deg(\beta)=1$. As $\alpha$ is univariate, $\alpha-t$ factorizes into linear
factors $\alpha_{1},\dots,\alpha_{d^{\prime}}$ over
$\overline{\mathbb{F}_{q}(t)}$. So
$g^{*}_{\mathbf{a}}=\alpha(\beta)-t=(\alpha-t)(\beta)$ factorizes into the
linear factors $\alpha_{1}(\beta),\dots,\alpha_{d^{\prime}}(\beta)$ over
$\overline{\mathbb{F}_{q}(t)}$.

This observation shows that there is only one bad factorization pattern to
rule out, namely, the complete factorization into linear factors. This allows
us to save a factor of $2^{d-1}-1$ and reduce the error probability in 5.2
from $(2^{d}-1)\delta+\delta$ to $\delta+\delta=2\delta$. The bound on the
statistical distance between $f(G(\mathbf{U}_{S}))$ and
$f(\mathbf{U}_{\mathbb{F}_{q}^{n+1}})$ in (3) now becomes
$2\delta+2\varepsilon^{\prime}=2C_{0}(2d-1)/q+2C_{1}d^{2}/\sqrt{q}$, which is
bounded by $\varepsilon$ provided that $q\geq C(d^{4}/\varepsilon^{2})$ and
$C>0$ is a large enough absolute constant. ∎

##  6 Open Problems

We conclude with some open problems. The most obvious one is reducing the
required field size in our construction. Using Bogdanov’s [Bog05] paradigm, it
seems necessary for the field to be of size at least polynomial in $d$, since
this argument relies on the Weil bound (and indeed, as mentioned in Section 1,
the seed lengths of the known constructions over small fields like
$\mathbb{F}_{2}$ are worse). Still, one could hope to obtain seed length
$O(d\log n)$ with $q$ being polynomial in $d$, and not exponential in $d$. In
our construction, $q$ is exponential in $d$ due to the need to apply a union
bound over all possible vectors in $\\{0,1\\}^{d}$ characterizing the
factorization pattern of $f_{\mathbf{a}}$. It could very well be that there is
a more clever argument that rules out multiple vectors at once. We also
mention again 4.9. As explained in Section 4, improved upper bounds on the
quantity $N^{*}(d,D,\mathbb{F})$ in that question would improve the field size
required by our construction.

A related open problem is removing the requirement that the characteristic of
$\mathbb{F}_{q}$ is at least $d(d-1)+1$. This requirement comes from using
Lecerf’s [Lec07] arguments (dating back to Gao [Gao03] and Ruppert [Rup86,
Rup99]).

Finally, low-degree polynomials form a natural “weak” class of polynomials.
However, rather than assuming bounds on the degree of polynomials, one can
also consider other weak classes of polynomials, where the restriction comes
from bounding their algebraic circuit complexity. This forms another
interesting avenue for generalizing the results on PRGs for low-degree
polynomials. As an analogy, in the context of Boolean computation, the problem
of constructing explicit PRGs for weak computational classes (such as bounded-
depth circuits or read-once oblivious branching programs) is well studied (see
[Vad12]). For algebraic computational models, however, much less is known.
Most of the research in this area has focused on constructing _hitting sets_
of limited models of algebraic circuits (see [SY10, Sax09, Sax14] for some
surveys on this topic), due to the relation to the famous Polynomial Identity
Testing Problem. To the best of our knowledge, there is no known explicit
construction of PRGs for any natural class of algebraic computation. A
concrete and intriguing open problem is to explicitly construct PRGs for the
class of sparse polynomials, for which, as described in the references above,
there are many known explicit constructions of hitting sets.

## Acknowledgments

We thank Jesse Goodman and Pooya Hatami for helpful discussions. Part of this
work was carried out while the first two authors were visiting the Simons
Institute for the Theory of Computing at UC Berkeley. We thank the institute
for their support and hospitality.

## References

  * [ABK08] Noga Alon, Ido Ben-Eliezer, and Michael Krivelevich.  Small sample spaces cannot fool low degree polynomials.  In Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM 2008), volume 5171 of Lecture Notes in Computer Science, pages 266–275. Springer, 2008.
  * [AGHP92] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta.  Simple construction of almost k-wise independent random variables.  Random Structures & Algorithms, 3(3):289–304, 1992.
  * [BDN09] Arnaud Bodin, Pierre Debes, and Salah Najib.  Indecomposable polynomials and their spectrum.  Acta Arithmetica, 139(1):79–100, 2009.
  * [Bog05] Andrej Bogdanov.  Pseudorandom generators for low degree polynomials.  In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 21–30. ACM, 2005.
  * [BT13] Avraham Ben-Aroya and Amnon Ta-Shma.  Constructing small-bias sets from algebraic-geometric codes.  Theory of Computing, 9:253–272, 2013.
  * [BV10] Andrej Bogdanov and Emanuele Viola.  Pseudorandom bits for polynomials.  SIAM Journal on Computing, 39(6):2464–2486, 2010.
  * [CLO07] David A. Cox, John B. Little, and Donal O’Shea.  Ideals, Varieties and Algorithms.  Undergraduate Texts in Mathematics. Springer, 2007.
  * [CN10] Guillaume Cheze and Salah Najib.  Indecomposability of polynomials via Jacobian matrix.  Journal of Algebra, 324(1):1–11, 2010.
  * [CT13] Gil Cohen and Amnon Ta-Shma.  Pseudorandom generators for low degree polynomials from algebraic geometry codes.  Electronic Colloquium on Computational Complexity, TR13-155, 2013\.
  * [DV22] Harm Derksen and Emanuele Viola.  Fooling polynomials using invariant theory.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 399–406. IEEE, 2022.
  * [EGL+98] Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Velickovic.  Efficient approximation of product distributions.  Random Structures & Algorithms, 13(1):1–16, 1998.
  * [Eis95] David Eisenbud.  Commutative Algebra: With a View Toward Algebraic Geometry.  Springer Science & Business Media, 1995.
  * [Gao03] Shuhong Gao.  Factoring multivariate polynomials via partial differential equations.  Mathematics of Computation, 72(242):801–822, 2003.
  * [GX14] Venkatesan Guruswami and Chaoping Xing.  Hitting sets for low-degree polynomials with optimal density.  In Proceedings of the IEEE 29th Conference on Computational Complexity, CCC 2014, pages 161–168. IEEE Computer Society, 2014.
  * [HH23] Pooya Hatami and William Hoza.  Theory of unconditional pseudorandom generators.  Electronic Colloquium on Computational Complexity, TR23-019, 2023\.
  * [Kal95] Erich L. Kaltofen.  Effective Noether irreducibility forms and applications.  Journal of Computer and System Sciences, 50(2):274–295, 1995.
  * [KS01] Adam R. Klivans and Daniel A. Spielman.  Randomness efficient identity testing of multivariate polynomials.  In Proceedings on 33rd Annual ACM Symposium on Theory of Computing (STOC 2001), pages 216–223. ACM, 2001.
  * [Lec06] Grégoire Lecerf.  Sharp precision in Hensel lifting for bivariate polynomial factorization.  Mathematics of Computation, 75(254):921–933, 2006.
  * [Lec07] Grégoire Lecerf.  Improved dense multivariate polynomial factorization algorithms.  Journal of Symbolic Computation, 42(4):477–494, 2007.
  * [Lov09] Shachar Lovett.  Unconditional pseudorandom generators for low degree polynomials.  Theory of Computing, 5(1):69–82, 2009.
  * [Lu12] Chi-Jen Lu.  Hitting set generators for sparse polynomials over any finite fields.  In Proceedings of the 27th Conference on Computational Complexity, CCC 2012, pages 280–286. IEEE Computer Society, 2012.
  * [NN93] Joseph Naor and Moni Naor.  Small-bias probability spaces: Efficient constructions and applications.  SIAM Journal on Computing, 22(4):838–856, 1993.
  * [Raz87] Alexander A. Razborov.  Lower bounds on the size of bounded depth circuits over a complete basis with logical addition.  Matematicheskie Zametki, 41:598–607, 1987.  English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.
  * [Rup86] Wolfgang Ruppert.  Reduzibilität ebener kurven.  Journal für die reine und angewandte Mathematik, 1986(369):167–191, 1986.
  * [Rup99] Wolfgang M. Ruppert.  Reducibility of polynomials $f(x,y)$ modulo $p$.  Journal of Number Theory, 77(1):62–70, 1999.
  * [Sax09] Nitin Saxena.  Progress on polynomial identity testing.  Bulletin of the EATCS, 99:49–79, 2009.
  * [Sax14] Nitin Saxena.  Progress on polynomial identity testing-II.  Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, pages 131–146, 2014.
  * [Sha94] Igor Shafarevich.  Basic Algebraic Geometry 1: Varieties in Projective Space.  Springer, 1994.
  * [Smo93] Roman Smolensky.  On representations by low-degree polynomials.  In 34th Annual Symposium on Foundations of Computer Science, pages 130–138. IEEE Computer Society, 1993.
  * [SY10] Amir Shpilka and Amir Yehudayoff.  Arithmetic circuits: A survey of recent results and open questions.  Foundations and Trends in Theoretical Computer Science, 5(3-4):207–388, 2010.
  * [Ta-17] Amnon Ta-Shma.  Explicit, almost optimal, epsilon-balanced codes.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 238–251. ACM, 2017.
  * [Vad12] Salil P. Vadhan.  Pseudorandomness.  Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 2012.
  * [Vio09] Emanuele Viola.  The sum of _D_ small-bias generators fools polynomials of degree _D_.  computational complexity, 18(2):209–217, 2009.
  * [Wei49] André Weil.  Numbers of solutions of equations in finite fields.  Bulletin of the American Mathematical Society, 55:497–508, 1949\.


# Consistent Recurrent Neural Networks for 3D Neuron Segmentation.

###### Abstract

We present a recurrent network for 3D reconstruction of neurons that
sequentially generates binary masks for every object in an image with spatio-
temporal consistency. Our network models consistency in two parts: (i) local,
which allows exploring non-occluding and temporally-adjacent object
relationships with bi-directional recurrence. (ii) non-local, which allows
exploring long-range object relationships in the temporal domain with skip
connections. Our proposed network is end-to-end trainable from an input image
to a sequence of object masks, and, compared to methods relying on object
boundaries, its output does not require post-processing. We evaluate our
method on three benchmarks for neuron segmentation and achieved state-of-the-
art performance on the SNEMI3D [1] challenge.

Index Terms—  Recurrent Neural Network, Neuron Segmentation, Instance
Segmentation, Object Consistency.

##  1 Introduction

The field of connectomics aims to reconstruct the brain’s wiring diagram by
mapping the neural connections at the level of individual synapses. A
reconstruction of neurons’ anatomical structures and the synaptic connectivity
between them can help neuroscientists better understand the structure and
function of the brain [2]. Recent advances in Electron Microscopy (EM)
technology make it possible to generate terabytes of brain images at the
nanometer scale on an hourly basis [3]. Thus, efficient and accurate neuron
segmentation methods are required to process these images.

Previous approaches [4, 5] addressed neuron segmentation in multiple steps.
First, a convolutional neural network (CNN) is applied to predict neurons’
instance boundaries or affinities. A watershed transform [6] is then used to
generate an initial 3D over-segmentation, where segments are further merged
based on hand-crafted or learned features. However, the CNNs are applied
independently on each local sub-volume without any shape information about
neighboring regions. Thus, when image artifacts or unexpected appearance
occurs in the input volume, the CNNs make wrong predictions, leading to
merging and splitting errors in the final segmentation.

More recent approaches [7, 8] treat neuron segmentation as video object
tracking along the z-axes of a 3D image volume. These approaches alleviate the
appearance problem by learning spatial features through recurrent neural
network models. These models segment one object and generate the object mask
for the input sub-volume with additional input features from the previous
inference step. However, these methods are computationally expensive. For
instance, on a 9x9x20nm image volume of the zebra finch songbird dataset, one
inference step of the flood-filling networks [7] costs 41.05 EFLOPS with a
wall time of 3.15 hrs.

In terms of spatial consistency, the affinity-based methods [4, 5] learn them
all-in-one, while the tracking-based methods [7, 8] learn them one-by-one
without exploiting the pairwise non-occluding relationships. In terms of
temporal consistency during inference, the tracking-based methods run the
inference only in forward and backward directions, without long-range
consistency. As such, image slices with severe artifacts can lead to broken
segmentation. Our approach is inspired by the idea of spatio-temporal
recurrence previously demonstrated for video object segmentation [9], where
objects are segmented by propagating masks from a reference frame. We argue
that exploiting the reference frame’s semantic meaning has benefits in
learning long-range object relationships in sequences. As such, we aim to
extend spatial and temporal recurrence to explore local and non-local
relationships between objects in the volume to connect broken segments and
form more complete object masks.

Fig. 1:  Our proposed architecture for multi-neuron segmentation. (a) A
network of our Consistent ConvLSTM extract neurons from a sequence $I$ based
on a single label map $L_{t}$. (b) A single forward pass of our model
predicting the first object $S_{t,o}$ of a frame given the mask of the object
from the previous frame $S_{t-1,o}$. When $t$ is the reference frame,
$S_{t-1,o}=L_{t,o}$

Therefore, we propose a recurrent model that performs a sequential analysis of
the input image volume to deal with complex object distributions and generate
consistent predictions. We create a new recurrent module based on
Convolutional LSTM [10], as a building block of our network, to model local
and non-local object consistency. Given a single label map, our model can
segment multiple objects without post-processing. We require no intermediate
representation for our model; as such, its training is performed in an end-to-
end fashion. Accuracy results on three connectomics datasets show that our
method performs similar to state-of-the-art methods and surpasses human
accuracy for 3D neuron segmentation on the SNEMI3D [1] dataset. Our results
also demonstrate that our method consistently produces object masks that are
robust to image artifacts.

##  2 Methodology

###  2.1 Consistent Recurrent Neural Network

We propose a recurrent network, depicted in Fig 1, based on an encoder-decoder
architecture to solve the task of neuron segmentation. The network
incorporates spatio-temporal recurrence with our Consistent ConvLSTM
(CConvLSTM) module defined in Section 2.2. Our recurrence is configured in the
spatial domain (rows) to represent the object instances in a frame and in the
temporal domain (columns) to represent frames. The model’s input consists of
3D patches transformed into sequences of images along the z-direction of the
input volume and a single label map for each sequence. For refinement, each
sequence is accompanied by a channel carrying initial object mask estimation.
The output of our model is a set of predicted masks
$S=\\{S_{t,o},S_{t,o+1},...,S_{t,o+M}\\}$, where $S_{t,o}$ is the predicted
mask of object $o$ at frame $t$ and $M$ is the number of objects.

Fig. 2:  A CConvLSTM module models local object consistency with two ConvLSTM
layers to process input in the forward and backward directions. Non-local
object consistency is modeled with a skip connection that integrates the
reference hidden state $h^{k}_{r,o}$

###  2.2 Spatio-Temporal Consistency Module

To model object consistency, we introduce a new recurrent module, CConvLSTM
shown in Fig. 2, as a building block of our network. This module models local
object consistency by combining two ConvLSTM layers that process input in the
forward and backward directions. The output of the two layers is convolved
with the reference hidden state to model non-local object consistency. The bi-
directional flow analysis in the temporal domain has been shown in [11] to
yield improved predictive performance.

Therefore, given a sequence and a set of objects propagated from a reference
frame $r$, the output $h^{k}_{t,o}$ of the $k^{th}$ CConvLSTM layer for object
${o}$ at frame $t$ is computed as:

$\displaystyle h_{input}$
$\displaystyle=[B_{2}(h^{k-1}_{t,o})|f^{k^{\prime}}_{t}|S_{t-1,o}]$ (1)
$\displaystyle\overrightarrow{h_{state}}$
$\displaystyle=[\overrightarrow{h^{k}_{t,o-1}}|\overrightarrow{h^{k}_{t-1,o}}]$
(2) $\displaystyle\overleftarrow{h_{state}}$
$\displaystyle=[\overleftarrow{h^{k}_{t,o-1}}|\overleftarrow{h^{k}_{t-1,o}}]$
(3) $\displaystyle h^{k}_{t,o}$
$\displaystyle=CConvLSTM(h_{input},\overrightarrow{h_{state}},\overleftarrow{h_{state}},h^{k}_{r,o})$
(4)

where, B2 is the bilinear upsampling of the output of the previous CConvLSTM
layer by a factor of $2$. $f^{k}_{t}$ is the features from the encoder at
frame $t$ and $f^{k^{\prime}}_{t,k}$ is the projection of $f^{k}_{t}$ to lower
dimension via a convolution layer. $S_{t-1,o}$ is the predicted segmentation
mask of the object from the previous frame. $\overrightarrow{h^{k}_{t,o-1}}$
and $\overleftarrow{h^{k}_{t,o-1}}$ are the forward and backward components of
the spatial hidden state representation of the previous object.
$\overrightarrow{h^{k}_{t-1,o}}$ and $\overleftarrow{h^{k}_{t-1,o}}$ are the
forward and backward components of the temporal hidden state of the object
from the previous frame. For the first hidden state $h^{0}_{t,o}$ of the
object, we use the segmentation mask from the reference $S_{r,o}$ frame and
the zero matrix for the spatial hidden state. We assess the importance of the
local and non-local object consistency in Section 3.2.

###  2.3 Encoding Path

The encoder, illustrated in pink in Fig. 1, is a Resnet50 [12] that is
truncated at the last convolution layer. The encoder learns to extract
features, $f=\\{f_{t},f_{t+1},f_{t+2},f_{t+3},f_{t+4}\\}$, from an RGB image
${x\in R^{h\times w\times 3}}$ corresponding to the output of Resnet blocks.
$f_{t}$ corresponds to the output of the deepest block, and $f_{t+4}$
corresponds to the output of the block whose input is the image. A convolution
operation is used to extract the features from each block.

###  2.4 Decoding Path

The decoder, shown in dark blue in Fig. 1 (b), is a hierarchical recurrent
architecture of CConvLSTMs leveraging the different resolutions of the input
features $f$ and label map $L_{t}$. The label map is extracted with a series
of down-sampling operations corresponding to the resolution of features $f$ as
shown in blue in Fig. 1 (b). The output of each CConvLSTM is subsequently
merged with corresponding encoder features and object masks, which allows the
decoder to reuse low-level features and refine the final segmentation. The
decoder applies equation 4 in chains for the number of CConvLSTMs. The
decoder’s output is a set of $M$ predictions per image. $M$ is the number of
objects propagated and is always constant per sequence to ensure an object
mask will be empty if it disappears in subsequent frames. The constant $M$
also ensures the predicted mask in the temporal domain is consistent with the
spatial recurrence.

###  2.5 Implementation Details

Since the number of propagated objects is always equal to the number of
predicted objects, we estimate the parameters of our model by optimizing an
objective function based on the Hungarian algorithm [13] using soft
intersection over union. Thus, given a sequence of $m$ predicted and $g$
ground truth masks of length $N$, the loss can be expressed as:

$sIoU(m,g)=1.0-\frac{\sum_{i=1}^{N}m_{i}g_{i}}{(\sum_{i=1}^{N}m_{i}+g_{i}-m_{i}g_{i})}\\\
$

The network is trained using the Adam optimizer with a learning rate of
$10^{-6}$ and a batch size of 1 over 40 epochs. For the early ten epochs, the
ground-truth mask of objects from the previous frame is included as an
additional input channel to our CConvLSTM. For the remaining 30 epochs, the
object’s inferred mask is used to fine-tune the model, thus allowing the model
to learn to fix errors that may occur at inference time. The training was
carried out on a single NVIDIA Titan X GPU with 12GB RAM for 24 hours.

##  3 Experiments

###  3.1 Setup

We evaluate our method’s efficacy with experiments on three EM datasets from
different species, as described in Table 1. The ($x,y,z$) dimensions of each
datasets in voxels is: ($1024\times 1024\times 100$), ($500\times 500\times
500$), and ($1024\times 1024\times 105$) for SNEMI [1], FIBSEM [14], and FIBER
respectively. The FIBER dataset is in-house generated, the FIBSEM is public,
and the SNEMI is a benchmark for the SNEMI challenge.

Name | Species (region) | Volume
---|---|---
SNEMI [15] | Mouse (Cortex) | $6\text{\times}6\text{\times}3\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}^{3}$
FIBSEM [14] | Fruit Fly (Medulla) | $5\text{\times}5\text{\times}5\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}^{3}$
FIBER (in-house) | Mouse (Cerebellum) | $8\text{\times}8\text{\times}3\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}^{3}$

Table 1: The list of datasets used to evaluate our system. Each consists of a
training and testing volume. The training volume is split 80% for training and
20% for validation.

Our baseline model implements spatio-temporal (ST) recurrence. We consider
three options to analyze the importance of consistency: (i) local consistency
model STL (non-local consistency not used), (ii) non-local consistency model
STN (local consistency not used), and (iii) a combined model STC (both local
and non-local consistency used). We compare our best model against the SNEMI
challenge leaderboard and the affinity-based model, waterz [4]. We use the
author’s publicly available waterz method implementation and use the original
paper’s suggested hyper-parameters.

During inference, we process the input 3D volume patches in an overlapping
manner, starting with a labeled frame. The segmentation of the first frame is
initialized with its corresponding ground-truth. A watershed transform output
is used to initialize the first frame’s segmentation for volumes where no
ground-truth exists.

We analyze our results using the Adaptive Rand Index (ARI) [16] used by the
SNEMI challenge [1] to be consistent. The ARI measures the similarity between
two data clusters. The error is defined as one minus the maximal F-score of
the Rand index. A lower ARI score corresponds to better segmentation quality.

###  3.2 Results

In Fig. 3, we show the segmentation of 15 objects by the ST and STC models in
a validation sequence compared to ground-truth. As shown by the white circles,
propagation errors occur when consistency is not used. These observations are
further confirmed with the quantitative evaluations, shown in Table 2. The
non-local consistency model (STN) is faster and connects distant segments
better, and when combined with local consistency, produces the lowest ARI
value as demonstrated by the STC model shown in Table 2.

Fig. 3:  We extract 15 neurons from a sequence of 30 images from the SNEMI
dataset using the ST and our STC models. In comparison to the ground truth,
errors are circled in white.

Fig. 4:  Qualitative comparison of our STC to the waterz [4] method. Errors
shown in red and black circles.

Model | Accuracy (ARI) | Inference Time (seconds)
---|---|---
ST [9] | 0.13 | 520.0
STL | 0.082 | 640.0
STN | 0.045 | 605.0
STC | 0.035 | 660.0

Table 2: An assessment of local (L) and non-local (N) consistency compared to
baseline ST [9] model in terms of ARI (lower is better) and inference time in
seconds.

Method/Dataset |  SNEMI3D |  FIBSEM |  FIBER
---|---|---|---
PNI [5] | 0.024 | N/A | N/A
FFN [7] | 0.029 | N/A | N/A
STC (ours) | 0.035 | 0.106 | 0.091
(human values) | 0.059 | N/A | N/A
waterz [4] | 0.072 | 0.163 | 0.210

Table 3: Our STC achieved third place ranking on SNEMI3D [1] leaderboard and
outperform waterz [4] on all three datasets.

For a fair comparison against state-of-the-art methods, we start from the same
watershed output as the waterz[4] method. In Fig. 4, we highlight in red
circles errors in the waterz method that are addressed by our spatio-temporal
consistency. Although our method is robust to segmentation breakage, some
artifacts may not be fully corrected as shown in black if the watershed is
bad. In this case, fine-tuning the watershed before applying our model is an
alternate solution. In table 3, we compare our best model STC against the
SNEMI3D [1] challenge leaderboard. Our method achieved 0.035 ARI score,
surpassing the human accuracy, and is currently ranked third after PNI [5] and
FNN [7]. Our method also consistently outperformed the waterz[4] method on all
three datasets. We attribute our method’s strength to its ability to learn
long-range object relationships, critical for connectomics data. This is
demonstrated, in Figure 4, with the presence of segment splits in waterz and
their absense in our method. In terms of inference time on the SNEMI dataset,
our method requires $660$ seconds compared to 61 minutes for the FFN [7]
model.

##  4 Conclusion

The proposed recurrent model learns to deal with complex object distribution
across long sequences and produces segments that are consistent with each
other. By training our model end-to-end, we eliminated intermediate
representations that could potential introduce errors such as in the affinity-
based methods. Our model is also suited for interactive segmentation where
object propagation is driven by the user. Therefore, we plan to incorporate
our model in the proofreading of neurons to help correct automatic
segmentation errors.

##  5 Compliance with Ethical Standards

This is a numerical simulation study for which no ethical approval was
required.

##  6 Acknowledgments

This work was partially supported by NSF grant IIS-1607800.

## References

  * [1] Ignacio Arganda-Carreras, Srinivas C. Turaga, Daniel R. Berger, Dan Cireşan, Alessandro Giusti, Luca M. Gambardella, Jürgen Schmidhuber, Dmitry Laptev, Sarvesh Dwivedi, Joachim M. Buhmann, Ting Liu, Mojtaba Seyedhosseini, Tolga Tasdizen, Lee Kamentsky, Radim Burget, Vaclav Uher, Xiao Tan, Changming Sun, Tuan D. Pham, Erhan Bas, Mustafa G. Uzunbas, Albert Cardona, Johannes Schindelin, and H. Sebastian Seung,  “Crowdsourcing the creation of image segmentation algorithms for connectomics,”  Frontiers in Neuroanatomy, vol. 9, pp. 142, 2015.
  * [2] Joshua L Morgan and Jeff W Lichtman,  “Why not connectomics?,”  Nature methods, vol. 10, no. 6, pp. 494, 2013.
  * [3] Richard Schalek, Dongil Lee, Narayanan Kasthuri, Adi Suissa-Peleg, Thouis R. Jones, Verena Kaynig, Daniel Haehn, Hanspeter Pfister, David Cox, and Jeffery W. Lichtman,  “Imaging a 1 mm3 volume of rat cortex using a multibeam sem,”  in Microscopy and Microanalysis. 26 July 2016, vol. 22, pp. 582–583, Cambridge Univ Press.
  * [4] Jan Funke, Fabian Tschopp, William Grisaitis, Arlo Sheridan, Chandan Singh, Stephan Saalfeld, and Srinivas C. Turaga,  “A deep structured learning approach towards automating connectome reconstruction from 3d electron micrographs,”  CoRR, vol. abs/1709.02974, 2017.
  * [5] Kisuk Lee, Jonathan Zung, Peter Li, Viren Jain, and H. Sebastian Seung,  “Superhuman accuracy on the SNEMI3D connectomics challenge,”  CoRR, vol. abs/1706.00120, 2017.
  * [6] Aleksandar Zlateski and H. Sebastian Seung,  “Image segmentation by size-dependent single linkage clustering of a watershed basin graph,”  CoRR, vol. abs/1505.00249, 2015.
  * [7] Michal Januszewski, Jeremy Maitin-Shepard, Peter Li, Jörgen Kornfeld, Winfried Denk, and Viren Jain,  “Flood-filling networks,”  CoRR, vol. abs/1611.00421, 2016.
  * [8] Yaron Meirovitch, Alexander Matveev, Hayk Saribekyan, David Budden, David Rolnick, Gergely Ódor, Seymour Knowles-Barley, Raymond Thouis Jones, Hanspeter Pfister, William Jeff Lichtman, and Nir Shavit,  “A multi-pass approach to large-scale connectomics,”  arXiv: Quantitative Methods, 2016.
  * [9] C. Ventura, M. Bellver, A. Girbau, A. Salvador, F. Marques, and X. Giro i Nieto,  “Rvos: End-to-end recurrent network for video object segmentation,”  in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Los Alamitos, CA, USA, jun 2019, pp. 5272–5281, IEEE Computer Society.
  * [10] Xingjian Shi, Zhourong Chen, Hao Wang, Dit-Yan Yeung, Wai-Kin Wong, and Wang-chun Woo,  “Convolutional LSTM network: A machine learning approach for precipitation nowcasting,”  CoRR, vol. abs/1506.04214, 2015.
  * [11] Zhiyong Cui, Ruimin Ke, and Yinhai Wang,  “Deep bidirectional and unidirectional LSTM recurrent neural network for network-wide traffic speed prediction,”  CoRR, vol. abs/1801.02143, 2018.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  CoRR, vol. abs/1512.03385, 2015.
  * [13] H. W. Kuhn and Bryn Yaw,  “The hungarian method for the assignment problem,”  Naval Res. Logist. Quart, pp. 83–97, 1955.
  * [14] Shin-ya Takemura, C Shan Xu, Zhiyuan Lu, Patricia K Rivlin, Toufiq Parag, Donald J Olbris, Stephen Plaza, Ting Zhao, William T Katz, Lowell Umayam, et al.,  “Synaptic circuits and their variations within different columns in the visual system of drosophila,”  PNAS, 2015.
  * [15] Narayanan Kasthuri, Kenneth Jeffrey Hayworth, Daniel Raimund Berger, Richard Lee Schalek, José Angel Conchello, Seymour Knowles-Barley, Dongil Lee, Amelio Vázquez-Reina, Verena Kaynig, Thouis Raymond Jones, et al.,  “Saturated reconstruction of a volume of neocortex,”  Cell, vol. 162, no. 3, pp. 648–661, 2015.
  * [16] R. Unnikrishnan, C. Pantofaru, and M. Hebert,  “Toward objective evaluation of image segmentation algorithms,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 6, pp. 929–944, June 2007.