1 Introduction
Let
$f,g,h\in \mathbb {C}[x]$
be polynomials such that
$f=gh$
. Classical results of Gel’fond, Mahler and Mignotte provide upper bounds on the height of h (
$\ell _\infty $
norm of its vector of coefficients) given information on the coefficients of g and f [Reference AlexanderGel60, Reference MahlerMah62, Reference MignotteMig74, Reference MignotteMig88]. These results were used by Gel’fond in the study of transcendence and are widely used in computer algebra to prove upper bounds on the running time of algorithms, such as in the polynomial factorization algorithm of Lenstra, Lenstra, and Lovász [Reference Lenstra, Lenstra and LovászLLL82].
The first of these bounds was proved by Gel’fond [Reference AlexanderGel60] (see also [Reference MahlerMah62] and [Reference Bombieri and GublerBG06, Lemma 1.6.11]).
Theorem 1.1 (Gel’fond’s Lemma).
Let
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
. Then,
$$ \begin{align} \left\Vert {h} \right\Vert{}_{\infty} \leq 2^{\deg{f}}\frac{\left\Vert {f} \right\Vert{}_{\infty}}{\left\Vert {g} \right\Vert{}_{\infty}}. \end{align} $$
Improved bounds were provided by Mahler [Reference MahlerMah62] and consequently by Mignotte [Reference MignotteMig74].
Theorem 1.2 (Mignotte’s Bound [Reference MignotteMig74, Theorem 2]).
Let
$f, g, h \in \mathbb {Z}[x]$
such that
$f = gh$
. Then,
$$ \begin{align} \left\Vert {h} \right\Vert{}_1 \leq 2^{\deg{h}}\left\Vert {f} \right\Vert{}_2 \end{align} $$
Discussions about this classical inequality can be found in [Reference MignotteMig88, Section 2] and [Reference MignotteMig12, Chapter 4]. This bound is also known to be quite tight; for any
$d \in \mathbb {N}$
there exists
$h \in \mathbb {Z}[x]$
of degree d and
$f \in \mathbb {Z}[x]$
such that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_1 \geq \Omega \left(\frac{2^{d}}{d^2\log{d}} \right) \left\Vert {f} \right\Vert{}_2. \end{align*} $$
When
$\left \Vert {h} \right \Vert {}_0$
is guaranteed to be small relative to its degree, tighter bounds can be obtained. For instance, Giorgi, Grenet and Perret du Cray established the following bound by a straightforward induction on the polynomial division algorithm [Reference Giorgi, Grenet and du CrayGGPdC21].
Lemma 1.3 (Lemma 2.12 in [Reference Giorgi, Grenet and du CrayGGPdC21]).
Let
$f,g,h \in \mathbb {Z}[x]$
satisfy
$f=gh$
. Then
$$ \begin{align} \left\Vert {h} \right\Vert{}_{\infty} \leq \left\Vert {f} \right\Vert{}_{\infty} (\left\Vert {g} \right\Vert{}_{\infty} + 1)^{\frac{\left\Vert {h} \right\Vert{}_0+1}{2}}. \end{align} $$
While the bound given in (2) is close to being tight, in this paper we ask whether one can get an improvement if the factor g is sparse. For example, Khovanski
$\breve{\rm i}'$
s theory asserts that when studying real roots of polynomial equations, results analogous to Bézout’s theorem can be obtained, where the number of monomials in the equations takes the place of the degree in Bézout’s theorem [Reference KhovanskiĭKho91].
Besides being a self-motivated question, bounding the norm of cofactors of sparse polynomials has important applications in computer algebra which we discuss next.
1.1 The sparse representation
The sparse representation of polynomials is widely used in computer algebra as it is the most natural and succinct representation when polynomials are far from being “dense,” that is, when most of their coefficients are zero, or, equivalently, when they are supported on a small number of monomials [Reference Gathen and GerhardvzGG13, Reference Davenport, Siret and TournierDST93]. In this representation, a polynomial is described by a list of coefficient and degree pairs that correspond to its terms with nonzero coefficients. For example, a polynomial
$f \in R[x]$
over the ring R with t nonzero coefficients,
$f = \sum _{i=1}^{t}{c_i x^{e_i}}$
, is represented as
$\left \{ (c_i,e_i) \mid i = 1 \ldots t \right \}$
. Particularly interesting cases are when
$R = \mathbb {Z}$
or R is a finite field. When working over the integers, the size of the sparse representation of a polynomial
$f \in \mathbb {Z}[x]$
, denoted
$\text {size}\left ( f \right )$
, is
$$ \begin{align*} \text{size}\left( f \right) = \left\Vert {f} \right\Vert{}_0(\log_2{\left\Vert {f} \right\Vert{}_{\infty}} + \log_2{\deg{f}}) , \end{align*} $$
where
$\left \Vert {f} \right \Vert {}_0$
and
$\left \Vert {f} \right \Vert {}_\infty $
are the number of nonzero coefficients in f, and the maximal coefficient of f (in absolute value), respectively.Footnote 1 This makes the sparse representation especially useful for applications involving polynomials with high degree where most of the coefficients are zero. In particular, it is used by computer algebra systems and libraries such as Maple [Reference Monagan and PearceMP13], Mathematica [Reference WolframWol99], Sage [Reference SteinS+08], and Singular [Reference SchönemannSch03].
In the sparse representation, the degree could be exponentially larger than the representation size. Algorithms that run in polynomial time in terms of the sparse-representation size (i.e., number of terms, their bit complexity and the logarithm of the degree) are called sparse polynomial algorithms.
Although the basic arithmetic of sparse polynomials is fairly straightforward [Reference JohnsonJoh74], the sparse representation poses many challenges in designing efficient algorithms, and many seemingly simple problems are known to be NP-hard. For example, Plaisted proved that determining whether
$x^n-1$
divides a product of sparse polynomials (such that the size of the input is 
) is NP-complete [Reference PlaistedPla77, Reference PlaistedPla84]. Other NP-hard problems concerning sparse polynomials include: deciding whether there exists a common divisor of two polynomials and testing whether a polynomial has a cyclotomic factor [Reference PlaistedPla77].
The surveys of Davenport and Carette [Reference Davenport and CaretteDC09] and of Roche [Reference RocheRoc18] give a good picture of known results and open questions concerning sparse polynomials.
One of the long-standing open problems concerns exact divisibility of sparse polynomials. There are two versions to this problem. The decision problem asks, given two sparse polynomials f and g, to decide whether g divides f. The search problem, or the exact division problem, asks to compute the quotient polynomial
$f/g$
when it is known that g divides f.
The two problems are closely related but also differ in what we can hope to achieve. In the decision problem, the output is a single bit, allowing us to analyze the complexity in terms of the input size. Conversely, in the search (exact division) problem, the output size depends on the number of monomials in
$f/g$
, and thus may require an exponential number of bits (compared to the size of the input) to represent.
There are two quantities that affect the complexity of the exact division problem. The first, mentioned above, is the number of terms of the quotient
$f/g$
. It is easy to find examples in which
$f/g$
has exponentially many monomials. The second quantity is the height of the quotient
$f/g$
.
Prior to this work the only bounds on the height were exponential in
$\deg {h}$
, as in Equations (1),(2) and(3) (see also [Reference MignotteMig12]). In particular, Davenport and Carette note that even in the case where g exactly divides f, we need to perform
$\Omega (\|f/g\|_0\cdot \left \Vert {g} \right \Vert {}_0)$
operations on coefficients, and the number of bits required to represent a coefficient may be as large as
$ \deg f$
[Reference Davenport and CaretteDC09, Section III.B]. Therefore, in terms of the input size and
$\|f/g\|_0$
the only provable bounds on the running time of the exact division algorithm were of the form
$$ \begin{align} \Omega(\|f/g\|_0\cdot\left\Vert {g} \right\Vert{}_0\cdot \deg{f/g}). \end{align} $$
1.2 Our results
Our main result gives a new bound on the
$\ell _2$
-norm of
$f/g$
, for
$f,g\in \mathbb {C}[x]$
such that g divides f. This result improves the classical bounds of Gel’fond [Reference MahlerMah62] and Mignotte [Reference MignotteMig74] when the factor g is sparse. In what follows we assume without loss of generality that
$f(0) \neq 0$
as we can always remove powers of x that divide the polynomials without affecting their coefficients. In the general case,
$\deg {g}$
should be replaced by
$\deg {g}-\text {ord}_{0}{g}$
throughout.
Theorem 1.4. Let
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
and
$f(0) \neq 0$
. Define
$L(n) = n \log n$
, and let
$$ \begin{align} \text{M} \geq \max \left\{ \begin{array}{c} \min\{\left| \text{LC}(g) \right|,\left| \text{TC}(g) \right|\}\cdot \sqrt{e}\left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}} \left(\deg{g}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}\\ \max\{\left| \text{LC}({g}) \right|,\left| \text{TC}({g}) \right|\}\cdot \deg{g} \end{array} \right\}. \end{align} $$
where
$\text {LC}(g)$
and
$\text {TC}(g)$
are respectively the leading coefficient and the trailing coefficient of g and e is the basis of the natural log. Then
$$ \begin{align} \left\Vert {h} \right\Vert{}_2 \le \frac{\sqrt{2}\,\left\Vert {f} \right\Vert{}_1}{\text{M}} \left( 2\left\Vert {g} \right\Vert{}_0 \cdot L\!\left(12\left\Vert {g} \right\Vert{}_0 \deg g + 2\deg f\right)^2 \right)^{\left\Vert {g} \right\Vert{}_0 - 1}. \end{align} $$
Remark 1.5. We note that in (6) there must appear a term that inversely depends on
$|\text {LC}(g)|$
or on
$|\text {TC}(g)|$
since if
$hg=f$
then for every constant c we also have
$(c\cdot h)\cdot (g/c)=f$
. This scales
$\left \Vert {h} \right \Vert {}_2$
by a factor of c.
The following is an immediate corollary.
Corollary 1.6. Let
-
•
$f, g, h \in \mathbb {Z}[x]$
such that
$f = gh$
and
$f(0)\neq 0$
, or -
•
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
,
$f(0)\neq 0$
, and
$|\text {LC}(g)|,|\text {TC}(g)|\geq 1$
.
Then, it holds that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 &\leq \sqrt{\frac{\left\Vert {g} \right\Vert{}_0}{\deg g}}\cdot \left\Vert {f} \right\Vert{}_1\cdot \left(\widetilde{O}\left(\frac{\left\Vert {g} \right\Vert{}_0^{2.5} \cdot \deg^2{g} + \sqrt{\left\Vert {g} \right\Vert{}_0}\cdot \deg^2{f}} {\sqrt{\deg{g}}}\right) \right)^{\left\Vert {g} \right\Vert{}_0-1}\\ &\leq \sqrt{\frac{\left\Vert {g} \right\Vert{}_0}{\deg g}}\cdot \left\Vert {f} \right\Vert{}_1\cdot \left(\widetilde{O}\left( \frac{\left\Vert {g} \right\Vert{}_0^{2.5} \cdot \deg^2{f}}{\sqrt{\deg{g}}} \right) \right)^{\left\Vert {g} \right\Vert{}_0-1}. \end{align*} $$
In terms of bit representation size we have
$$ \begin{align} \log_2{\left\Vert {h} \right\Vert{}_{\infty}} \leq \log_2{\left\Vert {h} \right\Vert{}_{2}}\leq \log_2{\left\Vert {f} \right\Vert{}_{\infty}} + O\left(\left\Vert {g} \right\Vert{}_0\cdot \log_2{\deg{f}}\right). \end{align} $$
If all we know is that one among
$\text {LC}({g})$
,
$\text {TC}(g)$
is large then, using the estimate
$\text {M}\geq \max \left \{ \text {LC}(g),\text {TC}(g) \right \}\cdot \deg {g}$
, we obtain the following bound.
Corollary 1.7. Let
$f, g \in \mathbb {C}[x]$
such that
$f = gh$
and g is monic. Then it holds that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq \frac{\left\Vert {f} \right\Vert{}_1}{\deg{g}}\cdot \widetilde{O}\left( \left\Vert {g} \right\Vert{}_0^{3} \mathrm{deg}^2{f}\right)^{\left\Vert {g} \right\Vert{}_0-1}. \end{align*} $$
Unlike the bounds in Equations (1), (2) and (3), our bound on the height of h is not exponential in the degree or number of coefficients of h, but rather in the sparsity of the factor g, which for sparse polynomials may be exponentially smaller. Thus, when
$\left \Vert {g} \right \Vert {}_0$
is small, this gives an exponential improvement over the bounds of Gel’fond and Mignotte (Theorems 1.1, 1.2). In addition, Theorem 1.4 gives an exponential separation between exact and nonexact division since
$\log _2{\left \Vert {h} \right \Vert {}_{\infty }}$
can be as large as
$\Omega (\deg {f} \cdot \log _2{\left \Vert {g} \right \Vert {}_{\infty }})$
when allowing nonzero remainder. As noted in [Reference Davenport and CaretteDC09, Section III.A], for division with remainder, this coefficient growth is intrinsic.
Observation 1.8. Let
$f,g \in \mathbb {C}[x]$
and let
$q, r$
be the quotient and the remainder of f divided by g, respectively. For any
$\left \Vert {f} \right \Vert {}_{\infty }$
,
$\left \Vert {g} \right \Vert {}_{\infty }$
,
$\deg {f}$
, and
$\deg {g}$
, there exists f and g of sparsity
$2$
such that
$\left \Vert {r} \right \Vert {}_{\infty } = \left \Vert {f} \right \Vert {}_{\infty }\left \Vert {g} \right \Vert {}_{\infty }^{\deg {f} - \deg {g} + 1}$
.
Proof. Let
$d_1, d_2 \in \mathbb {N}$
and
$a \in \mathbb {C}$
with
$\left | a \right |\geq 1$
. We conclude the claim by noting that
$$ \begin{align*} x^{d_1} \bmod( x^{d_2 + 1} - ax^{d_2}) = a^{d_1 - d_2}x^{d_2}.\\[-38pt] \end{align*} $$
Theorem 1.4 also provides the following guarantee regarding the performance of the polynomial division algorithm in the exact case.
Theorem 1.9. When the division is exact, the bit complexityFootnote 2 of the (deterministic) polynomial division algorithm for polynomials
$f, g \in \mathbb {Z}[x]$
is
$$ \begin{align*} \widetilde{O}\left( \left\Vert {f/g} \right\Vert{}_0 \cdot \left\Vert {g} \right\Vert{}_0 \cdot \left( \log{\left\Vert {g} \right\Vert{}_{\infty}} + \log{\left\Vert {f} \right\Vert{}_{\infty}} + \left\Vert {g} \right\Vert{}_0\log{\deg{f}} \right) \right). \end{align*} $$
Note that when 
or 
, the bound in Theorem 1.9 is
$\widetilde {O}(\left \Vert {f/g} \right \Vert {}_0 (\log \deg {f} + \log H))$
where H is an upper bound on the heights of f and g.
Finally, we recall the following result of Giorgi et al. [Reference Giorgi, Grenet, du Cray and RocheGGPdCR22, Theorem 1.3], specialized to the case of univariate polynomials.
Theorem 1.10 [Reference Giorgi, Grenet, du Cray and RocheGGPdCR22, Theorem 1.3].
There exists a Monte Carlo randomized algorithm that, given two sparse polynomials
$f, g \in \mathbb {Z}[x]$
such that g divides f, and a bound T on the sparsity of the quotient
$f/g$
, computes the sparse representation of
$f/g$
with probability at least
$2/3$
. The algorithm requires
$$\begin{align*}\widetilde{O}\!\left( (\left\Vert {f} \right\Vert{}_0 + \left\Vert {g} \right\Vert{}_0 + T)\,( \log \deg{f} + \log H) \right) \end{align*}$$
bit operations, where H is an upper bound on the heights of the polynomials f, g, and
$f/g$
.
In combination with Theorem 1.4, we derive the corollary below.
Corollary 1.11. There exists a randomized algorithm that, given two sparse polynomials
$f, g \in \mathbb {Z}[x]$
, such that g divides f, the algorithm outputs the quotient polynomial
$f/g$
, with probability at least
$2/3$
. The running time of the algorithm is
$$ \begin{align*} \widetilde{O}\left( (\left\Vert {f} \right\Vert{}_0 + \left\Vert {g} \right\Vert{}_0 + \left\Vert {f/g} \right\Vert{}_0) \cdot \left( \log{\left\Vert {g} \right\Vert{}_{\infty}} + \log{\left\Vert {f} \right\Vert{}_{\infty}} + \left\Vert {g} \right\Vert{}_0\log{\deg{f}} \right) \right). \end{align*} $$
While Corollary 1.11 speaks about a randomized algorithm and not a deterministic one as in subsection 1.9, it has the advantage of having the term
$(\left \Vert {f} \right \Vert {}_0 + \left \Vert {g} \right \Vert {}_0 + \left \Vert {f/g} \right \Vert {}_0)$
, whereas Theorem 1.9 has
$ \left \Vert {f/g} \right \Vert {}_0\cdot \left \Vert {g} \right \Vert {}_0 $
, which in the relevant case is larger by a factor of
$\Omega (\left \Vert {g} \right \Vert {}_0 )$
.
1.3 Proof outline and comparison to [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24]
We explain the ideas behind the proof of Theorem 1.4 as all the other results mentioned above are simple corollaries of it. We first discuss the overall idea that led to the result of [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24] and then the improvement obtained in this paper.
The proof of Theorem 1.4 starts, as in [Reference Giesbrecht and RocheGR11, Theorem 2.9], by considering the discrete Fourier transform of the coefficient vector of h. Parseval’s identity gives
$$ \begin{align} \left\Vert {h} \right\Vert{}_2^2 = \frac{1}{p}\sum_{0 \leq i < p}\left| h(\omega^i) \right|^2 , \end{align} $$
where
$\omega $
is a primitive p-th root of unity for a prime
$p>\deg {h}$
. Hence,
$\left \Vert {h} \right \Vert {}_2 \leq \left | h(\theta ) \right |$
for some p-th root of unity
$\theta $
. Since
$\left | g(\theta ) \right |\cdot \left | h(\theta ) \right | = \left | f(\theta ) \right | \leq \left \Vert {f} \right \Vert {}_1$
,
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq \left| h(\theta) \right| \leq \frac{\left\Vert {f} \right\Vert{}_1}{\left| g(\theta) \right|}. \end{align*} $$
Hence, it suffices to lower bound the values of g at roots of unity in order to upper bound
$\left \Vert {h} \right \Vert {}_2$
. As g may vanish at
$1$
, the above approach cannot be applied directly. To overcome this, we observe that if
$p>2\deg {f}$
then the contribution of
$h(1)$
to the overall sum in (8) is not too large. Consequently, we can upper bound
$\left \Vert {h} \right \Vert {}_2$
by a similar expression, except that now
$\theta $
is a primitive root of unity.
Consider the restriction of g to the unit circle,
$\tilde {g}(x) = g(e^{ix}): [0, 2\pi ) \to \mathbb {C}$
. We prove by induction on the sparsity of g that outside the neighborhood of a small set of bad points
$B(g) \subset [0,2\pi )$
(intuitively, these are zeros of g and points at which
$g'$
attains unusually small values),
$g(e^{ix})$
attains large values. Indeed, when
$\deg {g} = 1$
this is relatively simple to show as g must be of the form
$x - \alpha $
(after rescaling) and since primitive roots of unity of relatively prime orders are somewhat far from each other, we can find many primes p so that the values of g on primitive p-th roots of unity are not too small.
For higher degrees, we note that if the derivative of g is not small in a large enough region then g is large on most of that region. Thus, by moving further away from the bad set for the derivative of g,
$B(g')$
in which
$g'$
attains unusually small values, we get that on this set g always attains large values. We then prove by a simple pigeonhole principle that there exists a prime p such that all primitive p-th roots of unity are far away from the bad set and conclude the result. This is the approach behind the proof of the main result in [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24].
Theorem 1.12 [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24, Theorem 1.5].
Let
$f, g \in \mathbb {C}[x]$
such that
$f = gh$
and g is monic. Then it holds that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq {\left\Vert {f} \right\Vert{}_1}\cdot \widetilde{O}\left( \left\Vert {g} \right\Vert{}_0^{3} \mathrm{deg}^2{f}\right)^{\left\Vert {g} \right\Vert{}_0-1}. \end{align*} $$
Note that this is similar to Corollary 1.6, except that it is larger by a factor of
$\deg {g}$
. We next explain how to regain that factor and more strongly, the additional factor of
$\text {M}$
appearing in Theorem 1.4.
Improvement over [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24].
To get the improved result, we note that in the sketch above, every time that we take a derivative of g, its leading coefficient grows by a factor equivalent to the degree. Intuitively, this should help increase the value of the derivative, and this is the source of the improvement. Note that for linear factors the proof considered monic polynomials, and this is also the inductive assumption that we make. Thus, the coefficient of the top monomial will contribute a multiplicative factor to the value of g, when we make g monic. This is sufficient to obtain the extra factor of
$\deg {g}$
in Corollary 1.6 compared to [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24, Theorem 1.5] (see Theorem 1.12).
One may notice, however, that after taking derivatives we need to remove all powers of x that divide the polynomial, so that the next derivative will reduce the sparsity. This can cause an abrupt drop in the degree, which will not give us the saving of roughly
$(\deg {g})^{O(\left \Vert {g} \right \Vert {}_0)}$
(see (5)). This can happen only if most of the monomials have degrees close to
$\deg {g}$
. In this case however, if we consider
$g_{\text {rev}}(x)=x^{\deg {g}}g(1/x)$
, then this makes most of the monomials of degrees that are considerably smaller than the top degree, thus allowing us to gain large factors in every derivative. On the other hand, once we move to
$g_{\text {rev}}$
, it may not be monic, and in fact, it may have a small leading term which will cost us a large factor in the bound. Balancing these two cases leads to the bound of (5), and is the main technical part of subsection 3.4.
2 Preliminaries
In this section, we set our notation, and state some basic facts that we shall later use.
2.1 General notation
Let R be a unique factorization domain (UFD) and let
$g,f \in R[x]$
be two polynomials. We say that g divides f, and denote it with
$g\mid f$
, when there is a polynomial
$h\in R[x]$
such that
$g\cdot h=f$
. We denote
$g \nmid f$
when this is not the case.
Let
$f=\sum _i f_i x^i$
,. We shall use the following notation:
$\left \Vert {f} \right \Vert {}_0$
denotes the sparsity of f (the number of nonzero
$f_i$
’s);
$\left \Vert {f} \right \Vert {}_p = \left ( \sum _{i}{\left | f_i \right |{}^p} \right )^{1/p}$
; if
$R\subseteq \mathbb {C}$
then
$\left \Vert {f} \right \Vert {}_{\infty } = \max _i{\left | f_i \right |}$
is the height of f;
$\text {ord}_{\alpha }{f}$
denotes the multiplicity of a root
$\alpha $
in f, in particular,
$\text {ord}_{0}{f} = \max {\left \{ i: x^i \mid f \right \}}$
;
$\text {LC}(f) \in R$
denotes the leading coefficient in f, that is, the coefficient of the highest degree term in f. Similarly,
$\text {TC}(f) \in R$
, the trailing coefficient of f, denotes the coefficient of the smallest degree term in f.
For a polynomial g we denote
$g_0 \triangleq (g/x^{\text {ord}_{0}{g}})$
and
$g_{\text {rev}}\triangleq x^{\deg {g}}\cdot g(1/x)$
. For example, if
${g=\sum _{i=1}^{s}c_i\cdot x^{n_i}}$
then
$g_0= \sum _{i=1}^{s}c_i\cdot x^{n_i-n_1}$
and
$g_{\text {rev}}=\sum _{i=1}^{s}c_i\cdot x^{n_s-n_i}$
. Observe that
$(g_{\text {rev}})_0=(g_0)_{\text {rev}}$
and that
$g_0=(g_{\text {rev}})_{\text {rev}}$
.
We denote the derivative of g by
$g'$
.
For any real or complex-valued function f, we define
$V(f)$
to be the set of zeros of f, that is,
$V(f) = \left \{ \alpha \mid f(\alpha ) = 0 \right \}$
, over the corresponding field. For a complex-valued function f we denote by
$\Re {f}$
and
$\Im {f}$
the real and imaginary parts of f, respectively.
For an integer
$k \in \mathbb {N}$
, we denote
$[k] = \left \{ 1, \dots , k \right \}$
. Throughout this paper,
$\log $
refers to the natural logarithm. We use
$\pi $
to denote the mathematical constant, while
$\pi (\cdot )$
refers to the prime counting function.
2.2 Useful facts
The following facts are simple and well known but for completeness we provide their proof.
Claim 2.1 (Discrete Parseval’s Identity).
Let
$f \in \mathbb {C}[x]$
and let
$n> \deg {f}$
. Then,
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2^2 = \frac{1}{n}\sum_{0 \leq i < n}{\left| h(\omega^i) \right|^2} \end{align*} $$
where
$\omega \in \mathbb {C}$
is a primitive n-th root of unity.
Proof. Recall that the
$n \times n$
Discrete Fourier Transform (DFT) matrix is
$$ \begin{align*} \frac{1}{\sqrt{n}}\left( \omega^{jk} \right)_{0 \leq j, k < n} \end{align*} $$
where
$\omega \in \mathbb {C}$
is a primitive n-th root of unity. Since the DFT matrix is unitary, applying it to the coefficient vector of h we conclude that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2^2 = \sum_{0 \leq i \leq \deg{h}}{\left| h_i \right|^2} = \frac{1}{n}\sum_{0 \leq i < n}{\left| h(\omega^i) \right|^2}.\\[-50pt] \end{align*} $$
Claim 2.2. Let
$f \in \mathbb {C}[x]$
. Then
$\left \Vert {f} \right \Vert {}_2 \leq \left \Vert {f} \right \Vert {}_1 \leq \sqrt {\deg {f} + 1}\left \Vert {f} \right \Vert {}_2$
.
Proof. The first inequality is immediate from definition and the second follows from the Cauchy-Schwartz inequality.
Claim 2.3. Let
$f \in \mathbb {C}[x]$
and let
$x \in \mathbb {C}$
such that
$\left | x \right |=1$
. Then
$\left | f(x) \right | \leq \left \Vert {f} \right \Vert {}_1$
.
Proof. This is a consequence of the triangle inequality.
Claim 2.4. For all
$0\leq t <1$
,
$$ \begin{align*} (1-t) \geq e^{-\frac{t}{1-t}} \end{align*} $$
Proof. Take the logarithm of both side and observe that the derivative is nonnegative (and that at
$t=0$
there is an equality).
2.2.1 Complex analysis
For general facts about complex analysis, see [Reference AhlforsAhl21, Reference TitchmarshTit02]. For the definition of harmonic functions, see [Reference AhlforsAhl21, Chapter 4.6] and [Reference Axler, Bourdon and WadeABW13].
Claim 2.5. Let
$f: \mathbb {C} \to \mathbb {R}$
be a harmonic function. If
$f(\omega ) = 0$
for every
$\omega $
such that
$\left | \omega \right | = 1$
, then
$f = 0$
.
We give the proof of this well known fact for completeness.
Proof. Let,
$$ \begin{align*} D = \left\{ \omega \in \mathbb{C} : \left| \omega \right| \leq 1 \right\} \end{align*} $$
be the unit disc. From the Maximum Modulus Principle for harmonic functions (see [Reference AhlforsAhl21, Chapter 4.6.2, Theorem 21]) and compactness of D we get that
$f(\omega ) = 0$
for all
$\omega \in D$
. It follows that f must vanish everywhere [Reference Axler, Bourdon and WadeABW13, Theorem 1.27].
Claim 2.6. Let
$f \in \mathbb {C}[x]$
be a polynomial. If
$\Re {f}$
(or equivalently,
$\Im {f}$
,
$\Re {f} + \Im {f}$
or
$\Re {f} - \Im {f}$
) is nonzero, then it has at most
$2\deg {f}$
roots on the unit circle.
Proof. Let
$S \subseteq \mathbb {C}$
be the set of roots of
$\Re {f}$
on the unit circle. We can write
$\Re {f}(x + iy) = u(x, y)$
where
$u: \mathbb {R}^2 \to \mathbb {R}$
is a bi-variate polynomial of total degree
$\deg {f}$
. Hence,
$$ \begin{align*} |S| = |V(u) \cap V(x^2 + y^2 - 1)|. \end{align*} $$
Since f is analytic,
$\Re {f}$
is harmonic. Claim 2.5 implies that
$\Re {f}$
does not vanish on the unit circle. Thus, from the irreducibility of
$x^2 + y^2 - 1$
, we deduce that
$V(u)$
and
$V(x^2 + y^2 - 1)$
have no component in common. From Bézout’s theorem (see, e.g., [Reference HarrisHar92, Theorem 18.3]) we conclude that
$$ \begin{align*} |S| \leq \deg{u} \cdot \deg{(x^2 + y^2 - 1)} = 2\deg{f}.\\[-38pt] \end{align*} $$
Claim 2.7. If
$\left | x - y \right | \leq \tfrac {1}{2}$
, then
$\left | e^{2\pi i x} - e^{2\pi i y} \right | \geq 4 \left | x - y \right |$
.
Proof. Since
$$\begin{align*}\left| e^{2\pi i x} - e^{2\pi i y} \right| = \left| e^{2\pi i (x-y)} - 1 \right|, \end{align*}$$
we may assume without loss of generality that
$y = 0$
. Let
$t = 2\pi x$
. Since
$\left | x \right | \leq \tfrac {1}{2}$
, we have
$\left | t \right | \leq \pi $
. If
$\left | t \right | \leq \pi /2$
, then
$$\begin{align*}\left| e^{it} - 1 \right| = \sqrt{(1 - \cos(t))^2 + \sin^2 (t)} \geq \left| \sin(t) \right| \geq \tfrac{2}{\pi} \left| t \right|, \end{align*}$$
where the last inequality follows from the fact that
$\sin (t)$
is concave on
$[0,\pi ]$
and convex on
$[-\pi ,0]$
. If
$\pi /2 \leq \left | t \right | \leq \pi $
, then
$$\begin{align*}\left| e^{it} - 1 \right| = \sqrt{(1 - \cos(t))^2 + \sin^2( t)} \geq \left| 1 - \cos(t) \right| \geq \tfrac{2}{\pi} \left| t \right|, \end{align*}$$
where the last inequality follows from the fact that
$1 - \cos (t)$
is positive and concave on both
$[\tfrac {\pi }{2}, \tfrac {3\pi }{2}]$
and
$[-\tfrac {3\pi }{2}, -\tfrac {\pi }{2}]$
. Substituting
$t = 2\pi x$
, we obtain
$$\begin{align*}\left| e^{2\pi i x} - 1 \right| \geq \tfrac{2}{\pi} \cdot 2\pi \left| x \right| = 4 \left| x \right|. \\[-40pt]\end{align*}$$
2.2.2 Number theory
Fact 2.8 [Reference Rosser and SchoenfeldRS62, Corollary 1].
Let
$\pi (n) = \left | \left \{ p \leq n: p \text { is prime} \right \} \right |$
be the prime-counting function. Then
$\pi (n) \geq \frac {n}{\log {n}}$
for
$n \geq 17$
.
The following fact is a strengthening of Bertrand’s postulate by Ramanujan.
Fact 2.9 [Reference RamanujanRam19].
Let
$n \in \mathbb {N}$
such that
$n \geq 6$
. Then, there exist at least two primes in the interval
$(n, 2n]$
.
3 A Bound on the
$\ell _2$
-norm of the cofactor polynomial
In this section, we prove our main result, Theorem 1.4. We first give the main two claims that are required for the proof and show how they imply the theorem, and then prove the claims in the next sections. To state the claims we require some definitions.
Definition 3.1. For a polynomial
$g(x)=\sum _{i=1}^{s}c_ix^{n_i}$
with
$n_1<n_2<\ldots <n_s$
and
$\prod _{i=1}^{s}c_i\neq 0$
we define
$d(g)\triangleq \prod _{i=1}^{s-1}(n_s-n_i)$
. When
$s=1$
we set
$d(g)=1$
.
Intuitively,
$d(g)$
captures the coefficient growth when we take derivatives of g (and clear factors of the form
$x^k$
).
To obtain an improved bound over the results in [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24], we introduce the function below.
Definition 3.2. For a polynomial
$g\in \mathbb {C}[x]$
we denote
$$ \begin{align*} \text{M}\triangleq \max\{\left| \text{LC}({g}) \right|\cdot d({g}),\left| \text{TC}({g}) \right|\cdot d(g_{\text{rev}})\}. \end{align*} $$
We next express our upper bound on the norm of the cofactor in terms of
$\text {M}$
.
Theorem 3.3. Let
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
. Denote
$L(n) = n\log {n}$
. Then,
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq \frac{\sqrt{2}\left\Vert {f} \right\Vert{}_1}{\text{M}{}} \left({2\left\Vert {g} \right\Vert{}_0 \cdot L\left( 12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) + 2\deg{f} \right)^2}\right)^{\left\Vert {g} \right\Vert{}_0-1}. \end{align*} $$
We prove Theorem 3.3 in subsection 3.3. We now state our upper bound on
$\text {M}$
, which is the source of the improvement over [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24].
Lemma 3.4. Let
$g \in \mathbb {C}[x]$
. Let
$\text {M} = \max \left \{ \left | \text {LC}({g}) \right | \cdot d({g}), \left | \text {TC}({g}) \right | \cdot d(g_{\text {rev}}) \right \}$
. Then,
$$ \begin{align*} \text{M} \geq \max \left\{ \begin{array}{c} \min\{\left| \text{LC}(g) \right|,\left| \text{TC}(g) \right|\}\cdot \sqrt{e}\left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}} \left(\deg{g}-\text{ord}_{0}{g}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}\\ \max\{\left| \text{LC}({g}) \right|,\left| \text{TC}({g}) \right|\}\cdot (\deg{g}-\text{ord}_{0}{g}) \end{array} \right\}. \end{align*} $$
We prove this result in subsection 3.4. Given the bounds above we can prove Theorem 1.4 and Corollary 1.6. We recall their statements.
Theorem 1.4. Let
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
and
$f(0) \neq 0$
. Define
$L(n) = n \log n$
, and let
$$ \begin{align*} \text{M} \geq \max \left\{ \begin{array}{c} \min\{\left| \text{LC}(g) \right|,\left| \text{TC}(g) \right|\}\cdot \sqrt{e}\left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}} \left(\deg{g}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}\\ \max\{\left| \text{LC}({g}) \right|,\left| \text{TC}({g}) \right|\}\cdot \deg{g} \end{array} \right\}. \end{align*} $$
where
$\text {LC}(g)$
and
$\text {TC}(g)$
are respectively the leading coefficient and the trailing coefficient of g and e is the basis of the natural log. Then
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \le \frac{\sqrt{2}\,\left\Vert {f} \right\Vert{}_1}{\text{M}} \left( 2\left\Vert {g} \right\Vert{}_0 \cdot L\!\left(12\left\Vert {g} \right\Vert{}_0 \deg g + 2\deg f\right)^2 \right)^{\left\Vert {g} \right\Vert{}_0 - 1}. \end{align*} $$
Proof of Theorem 1.4.
This is exactly the statement of Theorem 3.3 with the lower bound on
$\text {M}$
established in Lemma 3.4.
Corollary 1.6. Let
-
•
$f, g, h \in \mathbb {Z}[x]$
such that
$f = gh$
and
$f(0)\neq 0$
, or -
•
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
,
$f(0)\neq 0$
, and
$|\text {LC}(g)|,|\text {TC}(g)|\geq 1$
.
Then, it holds that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 &\leq \sqrt{\frac{\left\Vert {g} \right\Vert{}_0}{\deg g}}\cdot \left\Vert {f} \right\Vert{}_1\cdot \left(\widetilde{O}\left(\frac{\left\Vert {g} \right\Vert{}_0^{2.5} \cdot \deg^2{g} + \sqrt{\left\Vert {g} \right\Vert{}_0}\cdot \deg^2{f}} {\sqrt{\deg{g}}}\right) \right)^{\left\Vert {g} \right\Vert{}_0-1}\\ &\leq \sqrt{\frac{\left\Vert {g} \right\Vert{}_0}{\deg g}}\cdot \left\Vert {f} \right\Vert{}_1\cdot \left(\widetilde{O}\left( \frac{\left\Vert {g} \right\Vert{}_0^{2.5} \cdot \deg^2{f}}{\sqrt{\deg{g}}} \right) \right)^{\left\Vert {g} \right\Vert{}_0-1}. \end{align*} $$
In terms of bit representation size we have
$$ \begin{align*} \log_2{\left\Vert {h} \right\Vert{}_{\infty}} \leq \log_2{\left\Vert {h} \right\Vert{}_{2}}\leq \log_2{\left\Vert {f} \right\Vert{}_{\infty}} + O\left(\left\Vert {g} \right\Vert{}_0\cdot \log_2{\deg{f}}\right). \end{align*} $$
Proof of Corollary 1.6.
By Theorem 3.3
$$ \begin{align} \left\Vert {h} \right\Vert{}_2 \leq \frac{\sqrt{2}\left\Vert {f} \right\Vert{}_1}{\text{M}{}} \left({2\left\Vert {g} \right\Vert{}_0 \cdot L\left( 12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) + 2\deg{f} \right)^2}\right)^{\left\Vert {g} \right\Vert{}_0-1}, \end{align} $$
for
$L(n)=n\log (n)$
. As
$g(0)\neq 0$
,
$\text {ord}_{0}{g}=0$
. Hence,
$$ \begin{align} \left\Vert {g} \right\Vert{}_0{L\left( 12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) + 2\deg{f} \right)^2} =\tilde{O}\left(\left\Vert {g} \right\Vert{}_0^3 \deg^2{g} +\left\Vert {g} \right\Vert{}_0 \deg^2{f} \right). \end{align} $$
Either of the assumptions in the statement implies that
$\text {LC}(g),\text {TC}(g)\geq 1$
. Thus, Lemma 3.4 gives
$$ \begin{align} \text{M} \geq \sqrt{e} \left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}}\cdot \left( {\deg{g}}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}. \end{align} $$
Substituting (10) and (11) into (9) we obtain
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 &\leq \frac{\sqrt{2}\left\Vert {f} \right\Vert{}_1}{\text{M}{}} \left({2\left\Vert {g} \right\Vert{}_0 \cdot L\left( 12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) + 2\deg{f} \right)^2}\right)^{\left\Vert {g} \right\Vert{}_0-1} \\ &\leq \frac{\sqrt{2}\left\Vert {f} \right\Vert{}_1 \left( \tilde{O}\left(\left\Vert {g} \right\Vert{}_0^3 \deg^2{g} +\left\Vert {g} \right\Vert{}_0 \deg^2{f} \right)\right)^{\left\Vert {g} \right\Vert{}_0-1}}{\sqrt{e} \left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}}\cdot \left( {\deg{g}}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}}\\ &= \frac{\left\Vert {f} \right\Vert{}_1}{\sqrt{\deg{g}}}\left( \frac{\tilde{O}\left(\left\Vert {g} \right\Vert{}_0^3 \deg^2{g} +\left\Vert {g} \right\Vert{}_0 \deg^2{f} \right)}{\sqrt{\left\Vert {g} \right\Vert{}_0 \deg{g}}} \right)^{{\left\Vert {g} \right\Vert{}_0 -1}} \\ &=\frac{\left\Vert {f} \right\Vert{}_1}{\sqrt{\deg{g}}}\left(\tilde{O}\left(\frac{\left\Vert {g} \right\Vert{}_0^{2.5} \deg^2{g} +\sqrt{\left\Vert {g} \right\Vert{}_0} \deg^2{f}}{\sqrt{\deg{g}}} \right) \right)^{{\left\Vert {g} \right\Vert{}_0 -1}}.\\[-47pt] \end{align*} $$
The remainder of this section is devoted to proving Theorem 3.3 and Lemma 3.4.
3.1 Evaluations on the unit circle
To prove Theorem 3.3 we use a well known relation between the norm of a polynomial and its values at roots of unity of high orders.
The following lemma uses simple Fourier analysis to bound the norm of the quotient polynomial in a similar fashion to Theorem 2.9 of [Reference Giesbrecht and RocheGR11].
Lemma 3.5. Let
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
. Then,
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq \sqrt{2}\left\Vert {f} \right\Vert{}_1 \cdot \max_{\substack{1 \neq \omega \in \mathbb{C} \\ \omega^p = 1}} {\frac{1}{\left| g(\omega) \right|}} \end{align*} $$
where p is a prime such that
$p> 2\deg {f}$
and g does not vanish at any primitive root of unity of order p.
Proof. When g is constant the statement is trivial (see Claim 2.2), so we assume
$\deg {g}>0$
. From Parseval’s identity (Claim 2.1) we conclude
$\left \Vert {h} \right \Vert {}_2^2 = \frac {1}{p}\sum _{0 \leq i < p}{\left | h(\omega ^i) \right |{}^2}$
, where
$\omega $
is a primitive p-th root of unity. Claim 2.2 implies that
$$ \begin{align*} \left| h(\omega^0) \right|^2 = \left| h(1) \right|^2 \leq \left\Vert {h} \right\Vert{}_1^2 \leq \left\Vert {h} \right\Vert{}_2^2(\deg{h} + 1) \leq \left\Vert {h} \right\Vert{}_2^2\deg{f}. \end{align*} $$
By the choice of
$p> 2\deg f$
, it follows that
$$ \begin{align*} \frac{1}{p}\sum_{0 < i < p}{\left| h(\omega^i) \right|^2} = \left\Vert {h} \right\Vert{}_2^2 - \frac{\left| h(\omega^0) \right|^2}{p} \geq \left\Vert {h} \right\Vert{}_2^2 - \frac{\deg{f}}{p}\left\Vert {h} \right\Vert{}_2^2> \frac{1}{2}\left\Vert {h} \right\Vert{}_2^2. \end{align*} $$
In other words, the average value of
$\left | h(\omega ^i) \right |{}^2$
for
$0 < i < p$
is larger than
$\frac {1}{2}\left \Vert {h} \right \Vert {}_2^2$
. Hence, there exists a p-th root of unity
$\theta \neq 1$
such that
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2< \sqrt{2}\left| h(\theta) \right|. \end{align*} $$
Since
$f = gh$
we conclude that
$\left | f(\theta ) \right | = \left | g(\theta ) \right |\left | h(\theta ) \right |$
. By Claim 2.3,
$\left | f(\theta ) \right | \leq \left \Vert {f} \right \Vert {}_1$
. Hence,
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2< \sqrt{2}\left| h(\theta) \right| = \sqrt{2}\frac{\left| f(\theta) \right|}{\left| g(\theta) \right|} \leq \sqrt{2}\frac{\left\Vert {f} \right\Vert{}_1}{\left| g(\theta) \right|}. \end{align*} $$
By taking the maximum over all p-th roots of unity
$\omega \neq 1$
we get
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq \sqrt{2}\left\Vert {f} \right\Vert{}_1 \cdot \max_{\substack{1 \neq \omega \in \mathbb{C} \\ \omega^p = 1}} {\frac{1}{\left| g(\omega) \right|}} \end{align*} $$
as claimed.
Lemma 3.5 shows that in order to upper bound
$\left \Vert {h} \right \Vert {}_2$
, we have to lower bound the value of g at primitive roots of unity of some prime order
$p>2\deg {f}$
.
To build intuition for the proof of Theorem 3.3 we next consider the case where g is a simple linear factor of f,
$g(x)=x-\alpha $
. The general case is handled in subsection 3.3.
3.2 Linear factors
We first consider the special case where g is linear. We show that there exists a point
$\tilde {\alpha }$
on the unit circle such that g attains large values on any point on the unit circle that is far enough from
$\tilde {\alpha }$
. To conclude, we prove that there exists a prime p such that every p-th root of unity is far from
$\tilde {\alpha }$
.
Lemma 3.6. Let
$\alpha _1, \dots , \alpha _k \in \mathbb {R}$
. Then, any set of
$k + 1$
prime numbers P contains
$p\in P$
such that
$\left | a/p-\alpha _i \right |> \frac {1}{2\left ( \max {P} \right )^2}$
for every integer
$0 < \left | a \right | < p$
and
$i \in [k]$
.
Proof. Assume for the sake of contradiction that the statement is false. Thus, for every
$p \in P$
there exists
$i \in [k]$
such that
$\left | a/p - \alpha _i \right |\leq \frac {1}{2\left ( \max {P} \right )^2}$
for some
$0 < \left | a \right | < p$
. By the Pigeonhole Principle, there exists
$i \in [k]$
such that for two different primes
$p, q \in P$
,
$0 < \left | a \right | < p$
and
$0 < \left | b \right | < q$
we have
$$ \begin{align*} \begin{aligned} \left| a/p - \alpha_i \right| \leq \frac{1}{2\left( \max{P} \right)^2} &\quad\text{and}& \left| b/q - \alpha_i \right| \leq \frac{1}{2\left( \max{P} \right)^2}. \end{aligned} \end{align*} $$
This, however, leads to a contradiction
$$ \begin{align*} \frac{1}{\left( \max{P} \right)^2} \geq \left| \frac{a}{p} - \alpha_i \right| + \left| \alpha_i - \frac{b}{q} \right| \geq\left| \frac{a}{p} - \frac{b}{q} \right| = \left| \frac{ap - bq}{pq} \right| \geq 1/pq> \frac{1}{\left( \max{P} \right)^2}.\\[-44pt] \end{align*} $$
We use this lemma to claim that for any two different primes
$p_1$
and
$p_2$
, any point on the unit circle is somewhat far from either all primitive roots of unity of order
$p_1$
or from those of order
$p_2$
.
Lemma 3.7. Let
$\alpha \in \mathbb {C}$
, and let
$p_1, p_2 \in \mathbb {N}$
be two primes. Then for either
$p = p_1$
or
$p = p_2$
it holds that
$\left | \omega - \alpha \right |> \frac {1}{(\max \left \{ p_1, p_2 \right \})^2}$
for any primitive p-th root of unity
$\omega \neq 1$
.
Proof. First, observe that if
$\alpha $
is
$\frac {1}{(\max \left \{ p_1, p_2 \right \})^2}$
-far from any point on the unit circle, then we are done. So, assume that there exists a point
$\tilde {\alpha }$
on the unit circle such that
$\left | \alpha - \tilde {\alpha } \right | < \frac {1}{(\max \left \{ p_1, p_2 \right \})^2}$
. Let
$c \in [-\frac {1}{2}, \frac {1}{2})$
such that
$\tilde {\alpha } = e^{2\pi i c}$
. By Lemma 3.6 with
$k=1$
and
$\alpha _1=c$
either
$p = p_1$
or
$p = p_2$
satisfies
$$ \begin{align*} \left| \frac{a}{p} - c \right|> \frac{1}{2(\max\left\{ p_1, p_2 \right\})^2} , \end{align*} $$
for any integer
$0 < \left | a \right | < p$
. Let
$\omega \neq 1$
be any primitive p-th root of unity. Let
$a \in \mathbb {Z}$
,
$0 < \left | a \right | < p$
, such that
$\omega =e^{2\pi i \frac {a}{p}} $
. By the periodicity of
$2\pi i x$
, we can choose a to satisfy
$\left | \frac {a}{p} - c \right | \leq \frac {1}{2}$
. By Claim 2.7 it holds that
$$ \begin{align*} \left| \omega - \tilde{\alpha} \right| = \left| e^{2\pi i \frac{a}{p}} - e^{2\pi i c} \right| \geq 4\left| \frac{a}{p} - c \right|> \frac{2}{(\max\left\{ p_1, p_2 \right\})^2}. \end{align*} $$
The triangle inequality implies
$$ \begin{align*} \left| \omega - \alpha \right| \geq \left| \omega - \tilde{\alpha} \right| - \left| \tilde{\alpha} - \alpha \right|> \frac{1}{(\max\left\{ p_1, p_2 \right\})^2}.\\[-42pt] \end{align*} $$
The claim about the norm of the cofactor of a linear factor now follows easily.
Proposition 3.8. Let
$f \in \mathbb {C}[x]$
with a root
$\alpha $
. Then
$$\begin{align*}\left\Vert {f/(x - \alpha)} \right\Vert{}_2 \leq 16\sqrt{2} \left\Vert {f} \right\Vert{}_1 \deg^2{f} < 23 \left\Vert {f} \right\Vert{}_1 \deg^2{f}.\end{align*}$$
Proof. Lemma 3.5 applied to
$g=(x-\alpha )$
and
$h=f/g$
implies that
$$ \begin{align} \left\Vert {f/(x - \alpha)} \right\Vert{}_2 \leq \sqrt{2}\left\Vert {f} \right\Vert{}_1 \cdot \max_{\substack{1 \neq \omega \in \mathbb{C} \\ \omega^p = 1}}{ \frac{1}{\left| \omega - \alpha \right|} } , \end{align} $$
for any prime p satisfying
$p> 2\deg {f}$
such that
$\alpha $
is not a primitive root of unity of order p. By Fact 2.9, if
$\deg {f}\geq 2$
then the interval
$(2\deg {f}, 4\deg {f}]$
contains at least two primesFootnote 3
$p_1, p_2$
. Lemma 3.7 guarantees that for either
$p = p_1$
or
$p = p_2$
it holds that the distance of
$\alpha $
from any primitive p-th root of unity is larger than
$\frac {1}{(\max \left \{ p_1, p_2 \right \})^2}\geq \frac {1}{(4\deg {f})^2}$
. Hence,
$$ \begin{align*} \left\Vert {f/(x - \alpha)} \right\Vert{}_2 \leq \sqrt{2}\left\Vert {f} \right\Vert{}_1 \cdot \max_{\substack{1 \neq \omega \in \mathbb{C} \\ \omega^p = 1}}{ \frac{1}{\left| \omega - \alpha \right|} }\leq \sqrt{2} \left\Vert {f} \right\Vert{}_1 \cdot (4 \deg{f})^2 < 23 \left\Vert {f} \right\Vert{}_1 \deg^2{f} , \end{align*} $$
as claimed
3.3 Sparse factors
In this section we prove Theorem 3.3. As discussed in subsection 3.1, we do so by giving a lower bound on the value of g at suitable roots of unity. Similarly to the proof of Proposition 3.8, we will show that g attains large values everywhere, with the possible exception of a small neighborhood of a small number of points. We achieve this using induction on
$\left \Vert {g} \right \Vert {}_0$
.
We start with two simple claims.
Claim 3.9. Let
$f: \mathbb {R} \to \mathbb {R}$
be a continuously differentiable function, and
$\delta> 0$
. Let
$I = [a, b]$
be an interval in which both f and
$f'$
do not change sign. That is, each of them is either nonnegative or nonpositive in I. Then,
$|f(\beta )| \geq \delta \min _{\alpha \in I}|f'(\alpha )|$
for every
$\beta \in [a + \delta , b - \delta ]$
.
Proof. If
$b - a < 2\delta $
there is nothing to prove. Assume without loss of generality that
$f \geq 0$
in I, otherwise analyze
$-f$
. If
$f' \geq 0$
in I, then f is nondecreasing in I and so for every
$\beta \in {[a + \delta , b - \delta ]}$
it holds that
$$ \begin{align*} f(\beta) \geq f(\beta) - f(a)= \int_{a}^\beta{f'(y)dy}\geq (\beta - a)\min_{\alpha \in I}f'(\alpha)\geq \delta\min_{\alpha \in I}|f'(\alpha)|. \end{align*} $$
Similarly, if
$f' \leq 0$
in I, then for every
$\beta \in {[a + \delta , b - \delta ]}$
it holds that
$$ \begin{align*} f(\beta) \geq f(\beta) - f(b)= \int_{\beta}^{b}{-f'(y)dy}\geq (b - \beta)\min_{\alpha \in I}|f'(\alpha)| \geq \delta\min_{\alpha \in I}|f'(\alpha)|, \end{align*} $$
as claimed.
Claim 3.10. Let
$f: \mathbb {R} \to \mathbb {C}$
be a continuously differentiable function,
$\delta> 0$
and denote
$f_1 = \Re {f}$
,
$f_2 = \Im {f}$
. Let
$I = [a, b]$
be an interval in which each function among
$f_1, f^{\prime }_1, f_2, f^{\prime }_2, f_1' - f_2'$
and
$f_1' + f_2'$
is either nonnegative or nonpositive. Then,
$\left | f(\beta ) \right | \geq \frac {\delta }{\sqrt {2}}\min _{\alpha \in I}|f'(\alpha )|$
for every
$\beta \in [a + \delta , b - \delta ]$
.
Proof. Our assumption implies that any of the four functions
$\pm f_1' \pm f_2'$
has fixed sign in I. Since this also holds for
$f^{\prime }_1$
and
$f^{\prime }_2$
we conclude that
$\left | f_1' \right | - \left | f_2' \right |$
, which is equal to one of these four functions, is either nonnegative or nonpositive in I, as well. Without loss of generality assume
$\left | f_1' \right | \geq \left | f_2' \right |$
in I. For every
$\beta \in I$
,
$f'(\beta )=f^{\prime }_1(\beta ) + i\cdot f^{\prime }_2(\beta )$
. Hence,
$$ \begin{align*} 2\left| f^{\prime}_1(\beta) \right|^2\geq \left| f^{\prime}_1(\beta) \right|^2 + \left| f^{\prime}_2(\beta) \right|^2 = \left| f'(\beta) \right|^2 \geq \min_{\alpha \in I}\left| f'(\alpha) \right|^2. \end{align*} $$
Thus,
$\left | f_1'(\beta ) \right | \geq \frac {1}{\sqrt {2}}\min _{\alpha \in I}\left | f'(\alpha ) \right |$
for every
$\beta \in I$
. The result follows by Claim 3.9 and the fact that
$\left | f(\beta ) \right | \geq \left | f_1(\beta ) \right |$
.
In what comes next, we say that two points
$\alpha $
and
$\beta $
are
$\delta $
-far from each other if
$\left | \alpha - \beta \right | \geq \delta $
. Similarly, we say that a point is
$\delta $
-far from a set S if it is
$\delta $
-far from every point in S.
We next prove our main lemma that shows that with the exception of a small neighborhood of a small number of points, a sparse polynomial obtains not too small values on the unit circle.
Lemma 3.11. Let
$g \in \mathbb {C}[x]$
be a monic polynomial. Then, there exists a set
$B(g) \subseteq [0, 2\pi )$
, satisfying
$|B(g)|\leq 12(\left \Vert {g} \right \Vert {}_0 - 1)\cdot (\deg {g} - \text {ord}_{0}{g})$
, such that for every
$\delta>0$
, and every
$\alpha \in [0, 2\pi )$
which is
$(\left \Vert {g} \right \Vert {}_0 - 1)\delta $
-far from
$B(g)$
, it holds that
$\left | g(e^{i\alpha }) \right | \geq d(g)\left (\frac {\delta }{\sqrt {2}} \right )^{\left \Vert {g} \right \Vert {}_0-1}$
.
Proof. We prove the lemma by induction on
$s=\left \Vert {g} \right \Vert {}_0$
. The claim holds for
$s=1$
since clearly
$|g(e^{i\alpha })| = 1$
for any
$\alpha $
, when
$g(x)=x^m$
.
For the inductive step, suppose that the claim holds for s, and let
$g \in \mathbb {C}[x]$
be of sparsity
$s + 1$
. Since
$\left | (g/x^{\text {ord}_{0}{g}})(\omega ) \right | = \left | g(\omega ) \right |$
for every
$\omega $
on the unit circle we can consider
$g_0=(g/x^{\text {ord}_{0}{g}})$
instead of g, which is of degree
$\deg {g_0}=\deg {g}-\text {ord}_{0}{g}$
.
Let
$f: [0, 2\pi ) \to \mathbb {C}$
be defined as
$f(x) = g_0(e^{ix})$
. Denote with
$$ \begin{align*}\hat{g}(x)=\frac{g_0'(x)}{\deg{g_0}}\, ,\end{align*} $$
the monic polynomial which is a scalar multiple of
$g_0'$
. By Claim 3.15,
$d(\hat {g})=d(g_0')$
. Let
$$ \begin{align} \begin{aligned} H &= \left\{ \Re f, \Re f', \Im f, \Im f', \Re f' - \Im f', \Re f' + \Im f' \right\} \text{ and }\\ B(g) &= B(\hat{g}) \cup \left\{ \beta \in [0, 2\pi): h(\beta) = 0 \text{ for a nonzero } h \in H \right\}. \end{aligned} \end{align} $$
By Claim 2.6, each nonzero function in H has at most
$2\deg {g_0}$
zeros in
$[0, 2\pi )$
. Since
$\hat {g}(x)$
is monic and has sparsity s, we conclude by the inductive assumption that
$$ \begin{align*} \left| B(g) \right| \leq 12(s - 1)\deg{\hat{g}} + 12\deg{g_0} < 12s\deg{g_0}. \end{align*} $$
Let
$I = [a, b] \subseteq [0, 2\pi )$
be an interval that is
$(s - 1)\delta $
-far from
$B(g)$
. By the definition of
$B(g)$
, each functions in the set H, as defined in Equation (13), does not change its sign within I, since any sign change would have to go through a zero of the function. As
$f'(x) = ie^{ix}\cdot {g_0'}(e^{ix})$
, Claim 3.10 implies that for every
$\beta \in [a + \delta , b - \delta ]$
it holds that
$$ \begin{align} \begin{aligned} \left| g(e^{i\beta}) \right|&=\left| g_0(e^{i\beta}) \right|= \left| f(\beta) \right| \geq \frac{\delta}{\sqrt{2}}\min_{\alpha \in I}\left| f'(\alpha) \right| \\ &= \frac{\delta}{\sqrt{2}}\min_{\alpha \in I}\left| g_0'(e^{i\alpha}) \right|= \frac{\delta\cdot \deg{g_0}}{\sqrt{2}}\min_{\alpha \in I}\left| \hat{g}(e^{i\alpha}) \right|. \end{aligned} \end{align} $$
By definition,
$B(\hat {g})\subseteq B(g)$
. As
$\left \Vert {\hat {g}} \right \Vert {}_0 = s$
and each
$\beta \in I$
is at least
$(s-1)\delta $
-far from
$B(g)$
, we get from the induction hypothesis applied to
$\hat {g}$
, Equation (14) and Claim 3.15
$$ \begin{align*} \begin{aligned} \left| g(e^{i\beta}) \right| &\geq \frac{\delta\cdot \deg{g_0}}{\sqrt{2}}\min_{\alpha \in I}\left| \hat{g}(e^{i\alpha}) \right|\\&\geq \frac{\delta\cdot \deg{g_0}}{\sqrt{2}}\cdot d(\hat{g}) \left( \frac{\delta}{\sqrt{2}} \right)^{s-1}\\&= \frac{\delta\cdot \deg{g_0}}{\sqrt{2}}\cdot d({g_0'}) \left( \frac{\delta}{\sqrt{2}} \right)^{s-1}\\ &= d(g)\left( \frac{\delta}{\sqrt{2}} \right)^s. \end{aligned} \end{align*} $$
In other words, every
$\beta $
that is
$s\delta $
far from the set
$B(g)$
satisfies
$\left | g(e^{i\beta }) \right | \geq d(g)\left ( \frac {\delta }{\sqrt {2}} \right )^s$
, which proves the step of the induction.
Corollary 3.12. Let
$g \in \mathbb {C}[x]$
be a polynomial. Then, there exists a set
$B(g) \subseteq [0, 2\pi )$
, of size
$|B(g)|\leq 12(\left \Vert {g} \right \Vert {}_0 - 1)(\deg {g}-\text {ord}_{0}{g})$
, such that for every
$\delta>0$
and every
$\alpha \in [0, 2\pi )$
which is
$(\left \Vert {g} \right \Vert {}_0 - 1)\delta $
-far from
$B(g)$
, it holds that
$$\begin{align*}\left| g(e^{i\alpha}) \right| \geq \max\{\left| \text{LC}({g}) \right|\cdot d({g}),\left| \text{TC}({g}) \right|\cdot d(g_{\text{rev}})\}\cdot \left(\frac{\delta}{\sqrt{2}} \right)^{\left\Vert {g} \right\Vert{}_0-1}.\end{align*}$$
Proof. Let
$g_{\text {rev}}=x^{\deg {g}}g(1/x)$
. Since for every
$\alpha $
,
$\left | g(e^{i\alpha }) \right | = \left | g_{\text {rev}}(e^{-i\alpha }) \right |$
, we can consider either g or
$g_{\text {rev}}$
in order to prove the claim (replacing
$B(g)$
with
$B(g_{\text {rev}})$
if required). Note that
$g/\text {LC}(g)$
and
$g_{\text {rev}}/\text {LC}(g_{\text {rev}})=g_{\text {rev}}/\text {TC}(g)$
are monic polynomials. From Lemma 3.11 we have (where
$\alpha $
is
$\delta $
-far from either
$B(g)$
or
$B(g_{\text {rev}})$
, respectively)
$$ \begin{align*} \left| \frac{g(e^{i\alpha})}{\text{LC}(g)} \right| \geq d(g)\left(\frac{\delta}{\sqrt{2}} \right)^{\left\Vert {g} \right\Vert{}_0-1} &\Rightarrow \left| g(e^{i\alpha}) \right| \geq \left| \text{LC}(g) \right|\cdot d(g)\left(\frac{\delta}{\sqrt{2}} \right)^{\left\Vert {g} \right\Vert{}_0-1}\\ \left| \frac{g_{\text{rev}}(e^{i\alpha})}{\text{LC}(g_{\text{rev}})} \right|\geq d(g_{\text{rev}})\left(\frac{\delta}{\sqrt{2}} \right)^{\left\Vert {g} \right\Vert{}_0-1} &\Rightarrow \left| {g}(e^{i\alpha}) \right| \geq \left| \text{TC}({g}) \right|\cdot d(g_{\text{rev}})\left(\frac{\delta}{\sqrt{2}} \right)^{\left\Vert {g} \right\Vert{}_0-1}.\quad \\[-42pt] \end{align*} $$
Remark 3.13. Lemma 3.11 and Corollary 3.12 strengthen [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24, Lemma 3.6] that proved the weaker bound
$\left | g(e^{i\alpha }) \right | \geq \left ( \frac {\delta }{\sqrt {2}} \right )^{\left \Vert {g} \right \Vert {}_0-1}$
. This is also reflected in Lemma 3.14 that improves upon [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24, Lemma 3.7] by the same factor. Our improved bound in Theorem 3.3 will come from giving a lower bound on
$\text {M} = \max \left \{ \left | \text {LC}(g) \right |\cdot d(g),\left | \text {TC}(g) \right |\cdot d(g_{\text {rev}}) \right \}$
.
Lemma 3.14. Let
$g \in \mathbb {C}[x]$
. Let
$p_{\min {}} \in \mathbb {N}$
and
$L(n) = n\log {n}$
. Set
$p_{\max {}} = \lceil 2L(p_{\min {}} + 12\left \Vert {g} \right \Vert {}_0(\deg {g}-\text {ord}_{0}{g}))\rceil $
. Then, there exists a prime
$p \in (p_{\min {}}, p_{\max {}}]$
such that
$$ \begin{align*} \left| g(\omega) \right| \geq M \cdot \left(\frac{\pi}{\sqrt{2}\cdot\left\Vert {g} \right\Vert{}_0\cdot p_{\max{}}^2}\right)^{\left\Vert {g} \right\Vert{}_0-1}, \end{align*} $$
for any p-th root of unity
$\omega \neq 1$
.
Proof. If
$\left \Vert {g} \right \Vert {}_0 = 1$
, then the statement is trivial since
$\left | g(\omega ) \right | = \left | \text {LC}(g) \right |=\left | \text {TC}(g) \right |$
for every root of unity
$\omega $
. Hence, we can assume that
$\left \Vert {g} \right \Vert {}_0 \geq 2$
and
$\deg {g} \geq 1$
.
Let
$t = p_{\min {}} + 12\left \Vert {g} \right \Vert {}_0(\deg {g} - \text {ord}_{0}{g})$
, and let
$\pi (n)$
be the prime counting function. Our assumption implies that
$t \geq 24$
. By Fact 2.8 we conclude that
$$ \begin{align*} \begin{aligned} \pi(p_{\max{}}) &= \pi(\lceil 2t\log{t}\rceil ) \\ &\geq \frac{2t\log{t}}{ \log{2} + \log{t} + \log{\log{t}} }\\ &> \frac{2t\log{t}}{2\log{t}} = t. \end{aligned} \end{align*} $$
Let
$B(g)$
be as in Lemma 3.11 and
$$ \begin{align*} P = \left\{ p_{\min{}} < p \leq p_{\max{}} : p \text{ is prime} \right\}. \end{align*} $$
We bound the size of P by counting the primes in the interval
$(p_{\min {}}, p_{\max {}}]$
:
$$ \begin{align*} \left| P \right| \geq \pi(p_{\max{}}) - p_{\min{}}> t - p_{\min{}} = 12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) \geq \left| B(g) \right|. \end{align*} $$
By Lemma 3.6, there exists
$p \in P$
such that for any integer
$0 < a < p$
and any
$\alpha \in B(g)$
$$ \begin{align*} \left| a/p - \alpha/2\pi \right| \geq \frac{1}{2p_{\max{}}^2}. \end{align*} $$
Thus,
$$ \begin{align*} \left| 2\pi\frac{a}{p} - \alpha \right| \geq \frac{\pi}{p_{\max{}}^2}. \end{align*} $$
In particular, every nontrivial p-th root of unity is
$\frac { \pi }{ p_{\max {}}^2}$
-far from
$B(g)$
. Finally, by applying Corollary 3.12 with
$\delta = \frac { \pi }{\left \Vert {g} \right \Vert {}_0\cdot p_{\max {}}^2}$
, we conclude that for any p-th root of unity
$\omega \neq 1$
,
$$ \begin{align*} \left| g(\omega) \right| & \geq \max\{\left| \text{LC}({g}) \right|\cdot d({g}),\left| \text{TC}({g}) \right|\cdot d(g_{\text{rev}})\}\cdot \left(\frac{\pi}{\sqrt{2}\cdot \left\Vert {g} \right\Vert{}_0\cdot p_{\max{}}^2}\right)^{\left\Vert {g} \right\Vert{}_0-1}\\ &= M \cdot \left(\frac{\pi}{\sqrt{2}\cdot \left\Vert {g} \right\Vert{}_0\cdot p_{\max{}}^2}\right)^{\left\Vert {g} \right\Vert{}_0-1}. \\[-46pt]\end{align*} $$
We can now prove Theorem 3.3. We repeat its statement for convenience.
Theorem 3.3. Let
$f, g, h \in \mathbb {C}[x]$
such that
$f = gh$
. Denote
$L(n) = n\log {n}$
. Then,
$$ \begin{align*} \left\Vert {h} \right\Vert{}_2 \leq \frac{\sqrt{2}\left\Vert {f} \right\Vert{}_1}{\text{M}{}} \left({2\left\Vert {g} \right\Vert{}_0 \cdot L\left( 12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) + 2\deg{f} \right)^2}\right)^{\left\Vert {g} \right\Vert{}_0-1}. \end{align*} $$
Proof. Let
$p_{\min {}} = 2\deg {f}$
and
$p_{\max {}}$
as in Lemma 3.14. From Lemma 3.14 we conclude that there exists a prime
$p \in (p_{\min {}}, p_{\max {}}]$
such that
$$ \begin{align*} \left| g(\omega) \right| \geq \text{M} \cdot \left( \frac{\pi }{\sqrt{2}\cdot \left\Vert {g} \right\Vert{}_0\cdot (\lceil 2L(12\left\Vert {g} \right\Vert{}_0(\deg{g} - \text{ord}_{0}{g}) + 2\deg{f}) \rceil)^2} \right)^{\left\Vert {g} \right\Vert{}_0-1} \end{align*} $$
for any primitive p-th root of unity
$\omega \neq 1$
. The theorem then follows from Lemma 3.5.
As
$d(g) \geq 1$
we have
$\text {M} \geq \text {LC}(g)$
. Hence Theorem 3.3 implies the bound stated in [Reference Nahshon, Shpilka, Hauenstein, Lee and ChenNS24, Theorem 3.8]. We next prove stronger lower bounds on
$\text {M}$
.
3.4 Improved lower bound on
$\text {M}$
In this section we prove Lemma 3.4 which lower bounds
$\text {M} = \max \{\left | \text {LC}({g}) \right |\cdot d({g}),\left | \text {TC}({g}) \right |\cdot d(g_{\text {rev}})\}$
. For this we first lower bound the product
$ d(g)\cdot d(g_{\text {rev}})$
.
To fix notation, denote
$$ \begin{align} g(x)=\sum_{i=1}^{s}c_ix^{n_i} \end{align} $$
and recall
$d(g)$
as given in Definition 3.1. For the rest of the section we recall the notation from subsection 2.1:
$g_0=g/x^{\text {ord}_{0}{g}}$
and
$g_{\text {rev}}=x^{\deg {g}}\cdot g(1/x)$
.
Claim 3.15. Let
$g\in \mathbb {C}[x]$
. Then
$d(g)=d(g_0)=\deg {g_0} \cdot d((g_0)')$
.
Proof. The claim follows by an easy calculation. Using (15) we have
$$\begin{align*}d(g_0) = \prod_{i=1}^{s-1}\left((n_s-n_1)-(n_i-n_1)\right) = \prod_{i=1}^{s-1}(n_s-n_i)=d(g). \end{align*}$$
Next, observe that
$$\begin{align*}(g_0)' = (\sum_{i=1}^{s}c_ix^{n_i-n_1})' = \sum_{i=2}^{s}(n_i-n_1)c_ix^{n_i-n_1-1}. \end{align*}$$
Hence,
$$ \begin{align*} \deg{g_0}\cdot d((g_0)') &= (n_s-n_1)\cdot \prod_{i=2}^{s-1}\left((n_s-n_1-1)-(n_i-n_1-1)\right)\\ &=\prod_{i=1}^{s-1}(n_s-n_i)=d(g).\\[-47pt] \end{align*} $$
Claim 3.16. Let g as in (15). Then,
$d(g_{\text {rev}}) = \prod _{i=2}^{s}(n_i-n_1)$
.
Proof. The case
$s = 1$
is clear. For
$1\leq i\leq s$
let
$m_{s-i+1} = n_s - n_i$
. Clearly,
$0 = m_1 < m_2 < \ldots < m_s = n_s-n_1$
. Then,
$g_{\text {rev}} = \sum _{i=1}^{s}c_ix^{n_s-n_i} = \sum _{i=1}^{s}c_{s-i+1}x^{m_i}$
and we get that
$$\begin{align*}d(g_{\text{rev}}) = \prod_{i=1}^{s-1}(m_s-m_i) = \prod_{i=1}^{s-1}\left((n_s-n_1)-(n_s-n_{s-i+1})\right) = \prod_{i=2}^{s}(n_i-n_1).\\[-48pt] \end{align*}$$
The next propositions contain the main technical calculations used to estimate
$\text {M}$
.
Proposition 3.17. Let g as in (15). Denote
$N \triangleq n_s - n_1$
and
$k \triangleq \lfloor \frac {s-2}{2} \rfloor $
. If
$s\geq 2$
then,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq \sqrt{2\pi k} N \left(\frac{k(N-k)}{e}\right)^{\frac{s-2}{2}}. \end{align*} $$
Proof. Using Claim 3.16,
$$ \begin{align} \max\left\{ d(g),d(g_{\text{rev}}) \right\} &\geq \sqrt{d(g) d(g_{\text{rev}})} \notag \\ &= \left( \prod_{i=1}^{s-1}(n_s-n_i)\cdot \prod_{i=2}^{s}(n_i-n_1)\right)^{1/2}\notag\\ &=\left((n_s-n_1)^2\cdot \prod_{i=2}^{s-1}\left((n_s-n_i) (n_i-n_1)\right)\right)^{1/2}. \end{align} $$
For
$1\leq i \leq s-2$
let
$z_i=n_{i+1}-n_1$
. Clearly,
$1\leq z_1<\cdots < z_{s-2}<N$
. We rewrite (16) as
$$ \begin{align} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq N\cdot \left(\prod_{i=1}^{s-2}\left(z_i(N-z_i) \right)\right)^{1/2}. \end{align} $$
We next lower bound the RHS of (17). Denote
$\phi (x)=x(N-x)$
. Clearly
$\phi (x)=\phi (N-x)$
. Furthermore
$\phi (x+1)-\phi (x)=N-1-2x$
making
$\phi $
monotone increasing for
$1\leq x\leq N/2$
and decreasing for
$x>N/2$
. We thus have that
$$ \begin{align*} \phi(1)=\phi(N-1)<\phi(2)=\phi(N-2)<\cdots < \phi(\lfloor N/2\rfloor)=\phi(\lceil N/2 \rceil). \end{align*} $$
Denote
$\delta = \mathbb {1}_{\text {s is odd}}$
. Substituting into (17), and recalling
$k= \lfloor \frac {s-2}{2} \rfloor $
, we get
$$ \begin{align*} \begin{aligned} \max\left\{ d(g),d(g_{\text{rev}}) \right\} &\geq N\cdot\left( \prod_{i=1}^{s-2}\phi(z_i)\right)^{1/2} \\ &= N \cdot ((k+1)(N-k-1))^{\delta/2} \prod_{i=1}^{k}(i(N-i)) \\ &\geq N \cdot ((k+1)(N-k-1))^{\delta/2} \cdot k! \cdot (N-k)^k. \end{aligned} \end{align*} $$
By Robbin’s estimate of the factorial function [Reference RobbinsRob55]
$$ \begin{align*} \sqrt{2\pi k} (k/e)^{k} \leq \sqrt{2\pi k} k^{k}e^{-k} e^{\frac{1}{12k+1}} \leq k!, \end{align*} $$
and the fact that in our setting
$(k+1)(N-k-1) \geq k(N-k)$
, we conclude that
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} &\geq N \cdot ((k+1)(N-k-1))^{\delta/2} \cdot \sqrt{2\pi k} \cdot \left(\frac{k(N-k)}{e}\right)^{k} \notag \\ &\geq N \cdot \sqrt{2\pi k} \left( \frac{k(N-k)}{e} \right)^{k + \delta/2}\\ &= N \cdot \sqrt{2\pi k} \left( \frac{k(N-k)}{e} \right)^{\frac{s-2}{2}} \ .\notag\\[-43pt] \end{align*} $$
Proposition 3.18. Let g as in (15). Denote (as before)
$N \triangleq n_s - n_1$
and
$k \triangleq \lfloor \frac {s-2}{2} \rfloor $
. If
$s\geq 6$
then,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq N\cdot \sqrt{2\pi k} \left(\frac{s(N-1)-3}{4e}\right)^{\frac{s-2}{2}}. \end{align*} $$
Proof. Since
$s \geq 6$
, it holds that
$k = \lfloor \frac {s-2}{2}\rfloor \geq 2$
. By Proposition 3.17, it is enough to show that
$k(N-k) \geq \frac {s(N-1)-3}{4}$
. Since
$N = n_s - n_1 \geq s - 1$
and by the monotonicity of
$k(N-k)$
for
$k\leq N/2$
it holds that,
$$ \begin{align*} k(N-k) &= \left\lfloor \frac{s-2}{2}\right\rfloor \left(N - \left\lfloor \frac{s-2}{2}\right\rfloor\right) \notag \\ &\geq \frac{s-3}{2}\left(N - \frac{s-3}{2}\right)\notag\\ &=\frac{1}{4}\left(N(2s-6)-(s-3)(s-3) \right) \notag\\ &= \frac{1}{4}\left(Ns+N(s-6)-(s-3)^2 \right)\notag\\ &\geq^{(*)} \frac{1}{4}\left(Ns+(s-1)(s-6)-(s-3)^2 \right)\notag\\ &=\frac{s(N-1)-3}{4}, \end{align*} $$
where
$^{(*)}$
holds as
$s\geq 6$
and hence
$N(s-6)\geq (s-1)(s-6)$
.
Proposition 3.19. Let g as in (15). If
$s\geq 2$
then
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq \sqrt{e} \left(\frac{s}{4e}\right)^{\frac{s-1}{2}}(n_s-n_1)^{\frac{s}{2}}. \end{align*} $$
Proof. We first note that for
$s = 2$
, trivially
$d(g)=d(g_{\text {rev}})=(n_s-n_1)$
and for
$s=3$
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} &= (n_s-n_1)\max\left\{ n_s-n_2,n_2-n_1 \right\}\\ &\geq \frac{1}{2}(n_s-n_1)^2>\frac{3}{4\sqrt{e}}(n_s-n_1)^{\frac{3}{2}}, \end{align*} $$
and the claim holds in both cases. For the cases of
$s=4$
and
$s=5$
, we use Proposition 3.17 with
$k=1$
to deduce that,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq N\cdot \sqrt{2\pi} \left(\frac{N-1}{e} \right)^{\frac{s - 2}{2}} \end{align*} $$
For
$s = 4$
we have
$N = n_s - n_1 \geq 3$
, which implies
$N - 1 \geq \frac {2}{3}N$
and so,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq N\cdot \sqrt{2\pi} \left(\frac{2N}{3e} \right) \geq \frac{N^{2}}{e}. \end{align*} $$
Similarly, for
$s = 5$
we have
$N = n_s - n_1 \geq 4$
, which implies
$N - 1 \geq \frac {3}{4}N$
and so,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq \sqrt{2\pi}\ N \left(\frac{3N}{4e} \right)^{\frac{3}{2}} \geq \sqrt{e}\left(\frac{5}{4e}\right)^2 N^{\frac{5}{2}}. \end{align*} $$
From now on we shall assume
$s \geq 6$
. Now observe that,
$$ \begin{align*} s(N-1) - 3 = sN - (s + 3) = sN \cdot \left(1 - \frac{s + 3}{sN} \right) \geq sN \cdot \left(1 - \frac{s + 3}{s(s-1)} \right). \end{align*} $$
Applying Claim 2.4 with
$t = \frac {s+3}{s(s-1)}$
yields
$$ \begin{align*} s(N-1) - 3 \geq sN \cdot \left(1 - \frac{s + 3}{s(s-1)} \right)\geq sN \cdot e^{-\frac{s+3}{s(s-1) - (s+3)}} = sN \cdot e^{-\frac{s+3}{(s-3)(s+1)}} \end{align*} $$
Substituting in Proposition 3.18 we get,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} \geq N\cdot \sqrt{2\pi k} \left(\frac{sN}{4e}\right)^{\frac{s-2}{2}} \cdot e^{-\frac{(s+3)(s-2)}{2(s-3)(s+1)}} \end{align*} $$
We observe that for
$s \geq 6$
,
$$ \begin{align*} e^{-\frac{(s+3)(s-2)}{2(s-3)(s+1)}} = e^{-\frac12 \left(1+ \frac{1}{s-3}\right)\left(1+\frac{2}{s+1}\right)} \geq e^{-\frac12 \left(1+ \frac{1}{3}\right)\left(1+\frac{2}{7}\right)} \geq \frac{1}{\sqrt{6}} \end{align*} $$
and that
$\pi (s-3) \geq \frac {3}{2}s$
. We can therefore deduce that,
$$ \begin{align*} \max\left\{ d(g),d(g_{\text{rev}}) \right\} &\geq N\cdot \sqrt{\frac{\pi k}{3}} \left(\frac{sN}{4e}\right)^{\frac{s-2}{2}} \\ &\geq N\cdot\sqrt{\frac{\pi(s-3)}{6} } \left(\frac{sN}{4e}\right)^{\frac{s-2}{2}} \\& \geq N\cdot \sqrt{\frac{s}{4}}\left(\frac{sN}{4e}\right)^{\frac{s-2}{2}} \\ &= \sqrt{e} \left(\frac{s}{4e}\right)^{\frac{s-1}{2}}N^{\frac{s}{2}} = \sqrt{e} \left(\frac{s}{4e}\right)^{\frac{s-1}{2}}(n_s-n_1)^{\frac{s}{2}}, \end{align*} $$
as claimed.
We are now ready to prove Lemma 3.4. We recall its statement.
Lemma 3.4. Let
$g \in \mathbb {C}[x]$
. Let
$\text {M} = \max \left \{ \left | \text {LC}({g}) \right | \cdot d({g}), \left | \text {TC}({g}) \right | \cdot d(g_{\text {rev}}) \right \}$
. Then,
$$ \begin{align*} \text{M} \geq \max \left\{ \begin{array}{c} \min\{\left| \text{LC}(g) \right|,\left| \text{TC}(g) \right|\}\cdot \sqrt{e}\left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}} \left(\deg{g}-\text{ord}_{0}{g}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}\\ \max\{\left| \text{LC}({g}) \right|,\left| \text{TC}({g}) \right|\}\cdot (\deg{g}-\text{ord}_{0}{g}) \end{array} \right\}. \end{align*} $$
Proof. Recall
$\text {M} = \max \left \{ \left | \text {LC}({g}) \right | \cdot d({g}), \left | \text {TC}({g}) \right | \cdot d(g_{\text {rev}}) \right \}$
. Clearly
$d(g),d(g_{\text {rev}})\geq (\deg {g}-\text {ord}_{0}{g})$
and therefore
$$\begin{align*}\text{M} \geq \max\left\{ \left| \text{LC}({g}) \right|,\left| \text{TC}({g}) \right| \right\}\cdot(\deg{g}-\text{ord}_{0}{g}). \end{align*}$$
In addition, since
$\max \left \{ \left | \text {LC}(g) \right |\cdot d(g),\left | \text {TC}({g}) \right |\cdot d(g_{\text {rev}}) \right \} \geq \min \left \{ \left | \text {LC}(g) \right |,\left | \text {TC}({g}) \right | \right \}\cdot \max \{ d(g), d(g_{\text {rev}})\}$
, Proposition 3.19 implies that
$$\begin{align*}\text{M} \geq \min\{\left| \text{LC}(g) \right|,\left| \text{TC}(g) \right|\}\cdot \sqrt{e} \left(\frac{\left\Vert {g} \right\Vert{}_0}{4e}\right)^{\frac{\left\Vert {g} \right\Vert{}_0-1}{2}}\cdot \left( {\deg{g}-\text{ord}_{0}{g}}\right)^{\frac{\left\Vert {g} \right\Vert{}_0}{2}}.\\[-44pt]\end{align*}$$
4 Polynomial division algorithm
In this section, we analyze the polynomial division algorithm (see [Reference Cox, Little and O’SheaCLO13, Chapter 1.5] or [Reference Gathen and GerhardvzGG13, Chapter 2.4]), also called long division or Euclidean division algorithm. We consider a version in which we are given upper bounds on the sparsity and height of the quotient polynomial. Namely, if the sparsity of the quotient polynomial is bounded by s, and its coefficients are bounded (in absolute value) by c, then we execute s steps of the division algorithm and return True if and only if at termination the remainder is zero. If at any step
$\left \Vert {q} \right \Vert {}_{\infty }> c$
, we return False.
The correctness of Algorithm 1 is due to the fact that in every step of the loop, we reveal a single term of the quotient. By definition of c and s, the coefficient of the term cannot exceed c, and the number of terms cannot be larger than s, unless
$g \nmid f$
.
Proposition 4.1. The bit complexity of Algorithm 1 is
$$ \begin{align*} \widetilde{O}\left( (\left\Vert {f} \right\Vert{}_0 + s \cdot \left\Vert {g} \right\Vert{}_0) \cdot (\log{\left\Vert {g} \right\Vert{}_{\infty}} + \log{\left\Vert {f} \right\Vert{}_\infty} + \log{c} + \log\deg{f}) \right) \end{align*} $$
Proof. We first prove upper bounds on
$\left \Vert {r} \right \Vert {}_0$
and
$\left \Vert {r} \right \Vert {}_\infty $
at each step of the algorithm. As at the beginning
$r=f$
. At each iteration of the While loop the number of terms of r increases (additively) by at most
$\left \Vert {g} \right \Vert {}_0 - 1$
(as we subtract
$t\cdot g$
from r, and we know that the leading terms cancel). Similarly,
$\left \Vert {r} \right \Vert {}_{\infty }$
increases (additively) in each step by at
$ \left \Vert {g} \right \Vert {}_{\infty } \cdot c$
. As at the beginning
$r=f$
we get that in every step of the algorithm it holds that
$$ \begin{align*} \begin{aligned} \left\Vert {r} \right\Vert{}_0 &\leq \left\Vert {f} \right\Vert{}_0 + s(\left\Vert {g} \right\Vert{}_0-1), \\ \left\Vert {r} \right\Vert{}_{\infty} & \leq {\left\Vert {f} \right\Vert{}_{\infty}} + s\cdot c \cdot {\left\Vert {g} \right\Vert{}_{\infty}}. \end{aligned} \end{align*} $$
This implies that at every step the representation size of r is at most
$$ \begin{align*} \begin{aligned} \text{size}\left( r \right) &= \left\Vert {r} \right\Vert{}_0\cdot(\log_2{\left\Vert {r} \right\Vert{}_\infty} + \log_2{\deg{r}}) \\ &\leq (\left\Vert {f} \right\Vert{}_0 + s\cdot (\left\Vert {g} \right\Vert{}_0 - 1)) \cdot ( \log_2{\left\Vert {f} \right\Vert{}_{\infty}} + \log_2{s} + \log_2{c} +\log_2{\left\Vert {g} \right\Vert{}_{\infty}} + \log_2{\deg{f}}). \end{aligned} \end{align*} $$
The algorithm performs in-place addition and subtraction to the polynomials
$q, r$
. Each iteration of the While loop requires
$\left \Vert {g} \right \Vert {}_0$
multiplications (for computing
$t\cdot g$
),
$\left \Vert {g} \right \Vert {}_0$
additions (for subtracting
$t\cdot g$
from r) and a single division, of integers (for computing t), whose absolute values are at most
$$ \begin{align*} B \leq \left\Vert {r} \right\Vert{}_\infty+ c\cdot \left\Vert {g} \right\Vert{}_\infty \leq {\left\Vert {f} \right\Vert{}_{\infty}} + (s+1)\cdot c \cdot {\left\Vert {g} \right\Vert{}_{\infty}}. \end{align*} $$
Each of these integers requires at most
$b = \lceil \log _2 B \rceil $
bits to represent, and so these arithmetic operations can be performed in time
$$ \begin{align*} O(b\log b) = \widetilde{O}(b)= \widetilde{O}( \log \left\Vert {f} \right\Vert{}_\infty + \log s+ \log c ) \end{align*} $$
(see [Reference Harvey and van der HoevenHvdH21]). In addition, we perform operations on the exponent that require
$O(\log \deg f)$
time and we have to store both q and r in memory. Storing q requires storing s terms, each term has degree at most
$\deg f$
and coefficient which is at most c in absolute value. Thus, the cost of storing q is at most
$\text {size}\left ( q \right )\leq s(\log _2{\deg {f}} + \log _2{c})$
.
Combining all these estimates we get that the running time is at most
$$ \begin{align*} \widetilde{O}\left((\left\Vert {f} \right\Vert{}_0 + s \cdot \left\Vert {g} \right\Vert{}_0) \cdot (\log{\left\Vert {g} \right\Vert{}_{\infty}} + \log{\left\Vert {f} \right\Vert{}_\infty} + \log{c} + \log\deg{f}) \right).\\[-42pt] \end{align*} $$
The proof of Theorem 1.9 easily follows.
Proof of Theorem 1.9.
Set
$s =\deg {f}\geq \left \Vert {f/g} \right \Vert {}_0$
and let
$c =\log _2{\left \Vert {f} \right \Vert {}_{\infty }} + O(\left \Vert {g} \right \Vert {}_0\cdot \log {\deg {f}})\geq \left \Vert {f/g} \right \Vert {}_\infty $
be the upper bound given in (7) on the absolute value of coefficients of
$f/g$
. Note that
$\deg f$
is a very rough upper bound on
$\|f/g\|_0$
, but as the division is exact the algorithm will terminate after
$\left \Vert {f/g} \right \Vert {}_0$
iterations. Thus, we may assume in the upper bound calculations that
$s=\left \Vert {f/g} \right \Vert {}_0$
. Substituting these values to Proposition 4.1 (and observing that
$\left \Vert {f} \right \Vert {}_0 \leq \left \Vert {g} \right \Vert {}_0\left \Vert {f/g} \right \Vert {}_0$
), gives the desired result.
Acknowledgments
The authors would like to thank Bruno Grenet for his helpful comments and for suggesting Corollary 1.11. We would also like to thank the anonymous referees for their comments that helped improve the presentation of our results.
Competing interest
The authors have no competing interest to declare.
Financial support
This research was co-funded by the European Union (ERC, EACTP, 101142020), the Israel Science Foundation (grant number 514/20) and the Len Blavatnik and the Blavatnik Family Foundation. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Open access
