Coefficient growth in square chains
Shawn Walker




Suppose ((⋯((x^2-c_1)^2-c_2)^2⋯)^2-c_k-1)^2-c_k
splits into linear factors over ℤ and c_k≠0. We
show that for each j and each prime p, if p≤2^j-1 then
p divides c_j. Consequently,

    ln c_j>1/4·2^j  for j≥5

If we also have p≡3 (mod 4) then p^2^j-⌈ p⌉
divides c_j. Consequently, if k≥3, there exists some absolute
constant λ>0 so that,

    ln c_j>λ k2^j  for all j

These estimates argue against the possibility of explicitly constructing
polynomials of the given form for large k, as the coefficients
quickly become too large to manipulate.


Coefficient growth in square chains
    Shawn Walker
    December 30, 2023
===================================





§ MOTIVATION: FACTORING INTEGERS WITH SQUARE
CHAINS


Call a polynomial of the form 

    P(x)=((⋯((x^2-c_1)^2-c_2)^2⋯)^2-c_k-1)^2-c_k

a square chain of length k. Some square chains of lengths
k=3,4 are presented in <cit.>
which have the property that they have 2^k distinct integer roots.
Crandall and Pomerance then ask about the existence of longer square
chains, suggesting that sufficiently long chains might be useful for
factoring large integers. Indeed, a simple scheme shows promise:

Suppose n=pq is an odd semiprime, and that p and q are approximately
the same size. If P(x)∈ℤ[x] has about p/2≈q/2
distinct roots, one can reasonably hope that P(m)≡0 (mod p)
for about half of m∈{0,1,…,n-1}, and similarly hope P(m)≡0 (mod q)
for about half of m∈{0,1,…,n-1}. If we assume heuristically
that these are independent events, then about a quarter of the choices
of m yield (P(m),n)=p, and about a quarter yield (P(m),n)=q.
For a more rigorous analysis, see <cit.>.

To make this a tractable factoring algorithm, we need a polynomial
P which can be efficiently evaluated and has sufficiently many
distinct roots. Square chains are nearly ideal from the standpoint
of efficient evaluation. As a polynomial of degree 2^k, a square
chain of length k may have up to 2^k roots and may be evaluated
using only k multiplications. No polynomial of degree 2^k
can be evaluated with fewer multiplications (<cit.>).
An obstacle is finding square chains with many distinct roots.

Let us set aside the question of existence. Suppose that there exists
a square chain of length k which has exactly 2^k roots, counting
multiplicity, even if those roots are not all distinct. What properties
might such a square chain have?

We say a polynomial P crumbles over the unique factorization
domain D if P may be written as the product of (not necessarily
distinct) linear polynomials in D[x]. Unless otherwise indicated
by context, we will assume D=ℤ. Clearly x^2^k=(⋯(x^2-0)^2⋯-0)^2-0
crumbles over any UFD. Unfortunately, it has only 1 distinct root.
More generally, if we have any crumbling square chain P, then P(x)^2-0
is a crumbling square chain longer than P. But extending a chain
in this manner doesn't create any new roots. Conversely, any square
chain whose final coefficient is 0 has exactly the same root set as
a square chain of shorter length, and we can instead consider the
shorter square chain. To this end, call a square chain whose final
coefficient is nonzero a fundamental square chain.

While it may be a big ask, suppose we are able to find some fundamental
crumbling square chain P. Then it is guaranteed to have plenty
of distinct roots.

Let D be a unique factorization domain with 1_D+1_D≠0_D.
Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ D[x]
crumbles over D. If c_k≠0_D, then P has at least 2^k-1+1
distinct roots.



Let T_k={c_k}, and call this the k-th tail square set
of P. Note that c_k must be a perfect square; indeed, for
any root r of P, we have c_k=(⋯(r^2-c_1)^2⋯-c_k-1)^2.
So we may use the identity a^2-b^2=(a+b)(a-b), to split P(x)
into two square chains: 

    P(x)=((⋯(x^2-c_1)^2-⋯)^2-c_k-1-√(c_k))((⋯(x^2-c_1)^2-⋯)^2-c_k-1+√(c_k))

Since P crumbles and D[x] is a unique factorization domain,
each of these factors must crumble. Let T_k-1={c_k-1± t:t^2∈ T_k}
be the tail squares of the two factors. Exactly as was the case with
T_k, elements of T_k-1 must be perfect squares.

We then repeat this splitting with each factor, splitting P into
4 factors with tail square set T_k-2={c_k-2± t:t^2∈ T_k-1},
then 8 factors with tail square set T_k-3={c_k-3± t:t^2∈ T_k-2},
and so forth onto 2^k-1 factors of the form (x^2-a) with
a∈ T_1={c_1± t:t^2∈ T_2}. If we make the convention
that c_0=0, we may split the previous set of factors one more
time to get 2^k factors of the form (x-r) with r in the
set T_0={0± t:t^2∈ T_1}. That is, T_0 is the set
of roots of P.

Suppose j∈{0,1,…,k-1}. What can we say about the size
of T_j? Distinct elements of T_j+1 yield distinct elements
of T_j: if {c_j± t}∩{c_j± s}≠∅ then
t=± s, and so t^2=s^2. Each nonzero element of T_j+1
yields two distinct elements of T_j: if c_j+t=c_j-t, then
2t=0, and so t=0 since D is an integral domain and 2≠0.
As such,

    |T_j|={[ 2(|T_j+1|-1)+1    if 0∈ T_j+1;       2|T_j+1|     if 0∉T_j+1 ]}≥2(|T_j+1|-1)+1

Consequently, 

    |T_0|≥2(|T_1|-1)+1≥2^2(|T_2|-1)+1≥⋯≥2^k-1(|T_k-1|-1)+1


To complete the argument, we note that |T_k-1|=2|T_k|=2 since
0∉T_k by hypothesis.

As an aside, the bound of proposition <ref> is met exactly
when D=ℤ_q for a prime q satisfying q≡1 (mod 2^k-1),
and when the square chain P of length k is given by

    P(x)     =(⋯((x^2-0)^2⋯-0)^2-2^-1)^2-2^-2
        =(x^2^k-1-2^-1)^2-2^-2
        =(x^2^k-1-1)(x^2^k-1-0)

In this case, 0 is a root of P with multiplicity 2^k-1,
and each 2^k-1-th root of unity (mod q) is a root
of P with multiplicity 1.



§ COEFFICIENT GROWTH


Perhaps more interesting than proposition <ref> is a specialization
of its contrapositive: for an odd characteristic finite field, fundamental
crumbling square chains must be of strictly bounded length.

Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ F[x]
crumbles over the finite field F with char(F)≠2.
If |F|≤2^j-1 then 

    c_j=c_j+1=⋯=c_k=0_F




Suppose c_i is the last non-zero coefficient in P, so that
Q(x)=(⋯(x^2-c_1)^2-⋯)^2-c_i is a fundamental
crumbling square chain over F. By proposition <ref>,
Q must have at least 2^i-1+1 distinct roots in F. Of course,
2^i-1+1≤|F|, as Q can have, at most, all of F as roots.
So 2^i-1+1≤|F|≤2^j-1. Consequently, i<j, and so all
coefficients of index j or larger must be zero.

Our primary interest in corollary <ref> will be in
the case F=ℤ_p for p any prime. But corollary <ref>
does not cover the case of ℤ_2. Instead, we derive a
similar, if weaker, result to cover ℤ_2.

Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ℤ[x]
crumbles over ℤ. Then c_2≡ c_3≡⋯≡ c_k≡0 (mod 2)



Consider the tail square sets T_j from proposition <ref>.
Let us adopt the convention that T_k+1={0}. This is consistent
with our previous definition, as it makes T_k={c_k± t:t^2∈ T_k+1}={c_k}.

For an arbitrary j>1, choose an arbitrary t^2∈ T_j. Then
c_j-1± t∈ T_j-1 by definition, and so c_j-1± t are
both squares. Thus,

    c_j-1± t≡0,1, or 4 (mod 8)

The limited set of congruence classes that these elements fall into
lets us somewhat limit what congruence classes their difference falls
into. That is,

    (c_j-1+t)-(c_j-1-t)≡2t≡0,1,3,4,5, or 7 (mod 8),

This limits the congruence classes t may fall into as well:

    t≡0,2,4, or 6 (mod 8).

So t must be even. Since t was chosen arbitrarily, each element
t^2∈ T_j must be the square of an even number.

For a given j with 1<j<k+1, choose any r^2∈ T_j+1.
By the previous argument, r is even. We have (c_j+r)∈ T_j
and so (c_j+r) is even. Consequently, c_j must be even.

As a consequence of corollary <ref>, coefficients
in long crumbling square chains over ℤ must have many
prime factors. This implies a lower bound on the size of those coefficients.
To quantify this, define the primorial of m as:

    m#=∏_[ p prime;    p≤ m ]p



Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ℤ[x]
crumbles over ℤ. Then for each j, we have 2^j-1#
divides c_j. If c_k≠0 and j≥5, then ln c_j>2^j-2.



c_j is even for j≥2 by lemma <ref>. For each odd
prime p≤2^j-1, corollary <ref> tells us that
p divides c_j. Thus 2^j-1# divides c_j.

Suppose c_k>0. We claim that c_j>0 for each j. Clearly
c_j≥0. To see that c_j≠0, let i be an arbitrary
index 1≤ i<k. We may write the equation P(x)=0 as


    (⋯(x^2-c_1)^2-⋯)^2=c_i±√(⋯±√(c_k))


Since the right-hand side of this equation must be non-negative for
every choice of signs, we have c_i≥√(c_i+1+⋯)≥√(c_i+1).
As the choice of i was arbitrary, we may apply this inequality
recursively, yielding c_j≥√(c_k). But c_k≠0;
it follows that c_j≠0 as well.

Together with the fact that 2^j-1# divides c_j, the positivity
of c_j implies that 2^j-1#≤ c_j.

<cit.> establish:

    [ x(1-1/2ln x)≤ln(x#)           for x≥563 ]


An exhaustive calculation (omitted) demonstrates the looser bound

    [   1/2x<ln(x#) for 11≤ x≤563 ]


Thus 

    [ 1/22^j-1<ln(2^j-1#)≤ln c_j                if 11≤2^j-1 ]





§ AN ASYMPTOTIC REFINEMENT


It seems unlikely the lower bounds given in proposition <ref>
are the best possible. ln(x#)∼ x, and so it seems likely,
at the very least, that ln c_j≥2^j-1 for j sufficiently
large. At the same time, it is plausible that for some primes p,
not only must p divide c_j, but possibly p^i divides
c_j for some appropriate condition on p, i and j. Indeed,
some reflection shows that primes of the form 4n+3 must be much
more prevalent than we've heretofore indicated.

Let ν_p(n)=max{e∈ℤ:p^e|n} be the exponent
of p in the prime factorization of n.

As noted by <cit.>, at least some of
the coefficients in a crumbling square chain must be expressable as
half the sum of two squares. We show that every coefficient in a crumbling
square chain must be so expressable. By the sum of two squares theorem,
if p≡3 (mod 4), then ν_p(a^2+b^2) must
be even. And so ν_p(c_j) must be even for every coefficient
c_j in a crumbling square chain.

What's more, by similar considerations as go into the sum of two squares
theorem, we can propagate powers forward to following coefficients,
so that ν_p(c_j+1)≥2ν_p(c_j).

We collect these ideas into the following lemma.

Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ℤ[x]
crumbles over ℤ. If p is prime with p≡3 (mod 4),
and p≤2^j-1 then ν_p(c_j)≥2^j-⌈ p⌉
.



Suppose ⌈ p⌉ =h-1. Then p divides c_h
by corollary <ref>.

Choose an arbitrary t^2∈ T_h+1. By definition, c_h± t∈ T_h.
All members of T_h are squares, so there exist r,s so that
c_h+t=r^2 and c_h-t=s^2. Then 2c_h=r^2+s^2,
that is 2c_h is the sum of two squares.

By the sum of two squares theorem, since p≡3 (mod 4)
and p divides r^2+s^2, then p^2 divides both r^2
and s^2. It follows that ν_p(c_h)≥2^1=2^h-⌈ p⌉.

To handle the more general case, we proceed inductively. Suppose ν_p(c_j-1)≥2^j-1-⌈ p⌉.
We will show that ν_p(c_j)≥2^j-⌈ p⌉.

As before, choose an arbitrary t^2∈ T_j, making c_j-1± t∈ T_j-1.
Write c_j-1+t=r^2 and c_j-1-t=s^2. Then 2c_j-1=r^2+s^2.
Since p≠2,

    ν_p(r^2+s^2)     =ν_p(2c_j-1)
        =ν_p(c_j-1)
       ≥2^j-1-⌈ p⌉


Also, we may write r^2+s^2=(r+is)(r-is) as the product of two
Gaussian integers. We recall two well known results: the Gaussian
integers form a unique factorization domain, and p is a prime Gaussian
integer since p≡3 (mod 4). As such, it makes sense
to extend our definition of ν_p to Gaussian integers. Now,
ν_p(r+is)=ν_p(r-is) since p is its own complex conjugate.
Thus 

    2ν_p(r+is)     =ν_p(r+is)+ν_p(r-is)
        =ν_p((r+is)(r-is))
        =ν_p(r^2+s^2)
       ≥2^j-1-⌈ p⌉

So 

    ν_p(r+is)≥1/22^j-1-⌈ p⌉

Any power of p that divides r+is must divide both r and s,
so

    ν_p(r), ν_p(s)≥1/22^j-1-⌈ p⌉

implying that

    ν_p(r^2), ν_p(s^2)≥2^j-1-⌈ p⌉


Since r^2 and s^2 share a common power of p, their difference
r^2-s^2=2t must share the same common power. That is, 

    ν_p(2t)     =ν_p(r^2-s^2)
       ≥2^j-1-⌈ p⌉

Since p≠2, this implies that 

    ν_p(t)≥2^j-1-⌈ p⌉

 and so 

    ν_p(t^2)≥2^j-⌈ p⌉

As t^2 was chosen arbitrarily, this inequality holds for any
t^2∈ T_j.

Choose any u^2∈ T_j+1. We have c_j± u∈ T_j by
definition. So 

    ν_p(c_j+u), ν_p(c_j-u)≥2^j-⌈ p⌉

Since c_j+u and c_j-u share a common power of p, their
sum, (c_j+u)+(c_j-u)=2c_j must share the same common power.
That is,

    ν_p(2c_j)     =ν_p((c_j+u)+(c_j-u)).
       ≥2^j-⌈ p⌉

And since p≠2, 

    ν_p(c_j)≥2^j-⌈ p⌉


By proposition <ref>, later coefficients “pick up”
many primes as divisors. By lemma <ref>, once a coefficient
acquires a divisor p≡3 (mod 4), each later coefficient
is divisible many times by the same prime. Define 

    x#_3:4=∏_[     p prime; p≡3 (mod 4);        p≤ x ]p


Together, proposition <ref> and lemma <ref>
imply:

Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ℤ[x]
crumbles over ℤ. Let 

    D_j=2^j-1#·∏_i=0^j-1(2^j-1-i#_3:4)^2^i

 For each j, D_j divides c_j. If c_k≠0, then
for some absolute constant λ>0 and each j≥3,

    ln c_j>λ j2^j




For primes p≤2^j-1:

If p≢3 (mod 4) then ν_p(D_j)=1.

If p≡3 (mod 4) then 

    ν_p(D_j)=1+∑_i=0^j-1-⌈ p⌉2^i=2^j-⌈ p⌉


Thus by corollary <ref> and lemma <ref>,
D_j divides c_j.

Corollaries of the Siegel-Walfisz theorem give ln(x#_3:4)∼1/2x,
c.f. <cit.>. So
there must be some constant λ_3:4>0 satisfying λ_3:4x<ln(x#_3:4)
for all x≥3. Similarly, by the prime number theorem, ln(x#)∼ x,
and thus there is a constant λ_1 so that λ_1x<ln(x#)
for all x≥2. Let 4λ=min(λ_1,λ_3:4).
Then for j≥3


    [                                   ln D_j                                        = ln(2^j-1#)+∑_i=0^j-12^i·ln(2^j-1-i#_3:4);                                                                                 = ln(2^j-1#)+∑_i=0^j-32^i·ln(2^j-1-i#_3:4);                                                                                 >          4λ2^j-1+ 4λ∑_i=0^j-32^i·2^j-1-i;                                                                                 =                           4λ2^j-1(1+j-2);                                                                                 =                               2λ(j-2)2^j;                                                                                 ≥                                   λ j2^j ]


If c_k≠0, then c_j>0 as argued in proposition <ref>.
Since D_j divides c_j, positivity of c_j forces D_j≤ c_j.
And so λ j2^j<ln D_j≤ln c_j.

We can sharpen the closed form estimate slightly:

Suppose P(x)=(⋯(x^2-c_1)^2-⋯)^2-c_k∈ℤ[x]
crumbles over ℤ, k≥3, and c_k>0. Then there
exists an absolute constant λ>0 so that for all j,

    ln c_j>λ k2^j




We observed in the proof of proposition <ref> that c_j≥√(c_k)
so,

    ln c_j   ≥ln c_k/2^k-j
        >λ k2^k/2^k-j
        =λ k2^j


It is interesting to note that this statement is enough to show the
length of the chain influences the size of c_1, as it shows that
ln c_1≥2λ k.



§ DISCUSSION AND RELATED WORK


To factor a product of two 500-bit primes using the algorithm described
in section <ref>, we would need to start by constructing
a fundamental crumbling square chain of length not much smaller than
500. According to proposition <ref>, the coefficient
c_400 of such a chain would be at least e^2^398≈9.3×10^119
bits in length. By way of comparison, estimates place the total digital
storage capacity of the world at approximately 10^22 bits as
of the year 2019. Even if we knew how to construct such a chain, precalculating
the coefficients of such a chain would clearly be infeasible.

Finding fundamental crumbling square chains has proven difficult.
While <cit.> provides a characterization
of length 3 fundamental crumbling square chains, and <cit.>
describes two infinite families of length 4 fundamental crumbling
square chains, no fundamental crumbling square chains of length 5
are known. Indeed, <cit.> points
out that a crumbling square chain of length 5 with distinct roots
would advance understanding of a historied question known as the Prouhet-Tarry-Escott
problem.

<cit.> discuss a more general family
of polynomials, which they term gems. By construction, their gems
are polynomials which are efficiently computable, crumble over ℤ,
and have distinct roots. While the highest known degree of a square
chain that crumbles over ℤ is 16, the authors of that
article describe gems of degrees up to 55.

plainnat


