R.<y,x> = PolynomialRing(QQ)
# There is a reason for the order of variables
# I'll later want to do f % y^i and for that sage
# needs y to have "higher precedence" than x.
#
# ... just ignore this for now.
R
def extended_euclid(f , g, R = R):
old_d, d = f , g
old_u, u = R.one() , R.zero()
old_v, v = R.zero(), R.one()
while not d.is_zero():
q = old_d // d
old_d , d = d , (old_d - q * d)
old_u , u = u , (old_u - q * u)
old_v , v = v , (old_v - q * v)
l = old_d.lc()
return (old_d / l, old_u / l, old_v / l)
def HenselLift(f, g, h, a, b, y_mon, R = R, monic = False):
'''
Expecting polynomials f, g, h, a, b, y_mon
from the ring R such that
* f - gh = 1 mod y_mon
* ag + bh = 1 mod y_mon
and y_mon is y^i for some i.
It will return polynomials g', h', a', b' such that
* g = g' mod y_mon^2
* h = h' mod y_mon^2
* f = g'h' mod y_mon^2
* a'g' + b' h' = 1 mod y_mon^2
'''
if (f - g*h) % y_mon != R.zero(): raise ValueError("f - gh is not 0 mod I")
if (a*g + b*h) % y_mon != R.one(): raise ValueError("ag + bh is not 1 mod I")
gamma = f - g * h
g1 = g + (b * gamma)
h1 = h + (a * gamma)
if monic:
q , r = (g1 - g) // g , (g1 - g) % g
g1 = (g + r) % y_mon^2
h1 = (h1 * ( 1 + q)) % y_mon^2
delta = a*g1 + b*h1 - R.one()
a1 = a*(1 - delta)
b1 = b*(1 - delta)
return (g1, h1, a1, b1)
def iteratedHenselLift(f, g, h, a, b, y_mon, k, R = R, monic = False):
if k == 1:
return HenselLift(f, g, h, a, b, y_mon, R, monic)
else:
g1, h1, a1, b1 = iteratedHenselLift(f, g, h, a, b, y_mon, k-1, R, monic)
y_mon_1 = y^(2**(k-1))
return HenselLift(f,g1, h1, a1, b1, y_mon_1, R, monic)
f = x^2 - 2*x*y - 3*y^2 + 3*x - 5*y + 2
f % y
factor(f % y)
g = x + 1
h = x + 2
_ , a, b = extended_euclid(g, h)
a*g + b*h == 1
gk, hk, ak, bk = iteratedHenselLift(f, g, h, a, b, y, k = 5, monic = True)
print(gk)
print(hk)
Great, we found our factors!
Let's take $f(x,y) = x^3 + x - y$ which is actually irreducible.
However, $f \bmod{y} = x^3 + x = x (x^2 + 1)$.
f = x^3 + x - y
f0 = (f % y)
factor(f0)
g = x
h = x^2 + 1
_, a,b = extended_euclid(g, h)
gk, hk, ak, bk = iteratedHenselLift(f, g, h, a, b, y, k = 5, monic = True)
print(gk)
We appear to be getting some garbage. Perhaps this suggests that we started off with an $f(x,y)$ that was irreducible.
(Spoiler: This intuition is wrong.)
f = x^4 - y^2 - 2*y - 1
f
f0 = f % y
factor(f0)
g = x - 1
h = (x + 1)*(x^2 + 1)
_, a,b = extended_euclid(g, h)
gk, hk, ak, bk = iteratedHenselLift(f, g, h, a, b, y, k = 5, monic = True)
print(f"gk: {gk}")
print("")
print(f"hk: {hk}")
Garbage again. Suggests that $f(x,y)$ is irreducible, right?
factor(f)
Hunh?!?!
The polynomial $f(x,y)$ actually has two irreducible factors, $g^\ast = (x^2 - y - 1)$ and $h^\ast = (x^2 + y + 1)$. However, when we went modulo $y$, the polynomial $g^\ast = x^2 - 1 \bmod{y}$ factorised further into $(x - 1)$ and $(x + 1)$. We picked up $g = x - 1$ to start the entire lifting process, and $g$ was only part of an actual factor of $f(x,y)$. Perhaps it isn't surprising that the lifted version looked messy.
But how do we really distinguish the mess in Example 2 and Example 3?
Suppose on the other hand, we did the entire lifting process starting with $g_1 = x +1$ instead, what would we end up with?
g1 = (x + 1)
h1 = (x - 1) * (x^2 + 1)
_, a1, b1 = extended_euclid(g1, h1)
gk_prime, _, _, _ = iteratedHenselLift(f, g1, h1, a1, b1, y, k=5, monic = True)
gk_prime
That's messy too, but that's also expected for the same reasons mentioned above --- $x+1$ is only part of a real factor of $f(x,y)$ and so its lift looks messy.
However, $g_k'$ and $g_k$ together are part of a proper factor of $f$. What is their product going to be?
gk_prime * gk
(gk_prime * gk) % y^(2**5)
Aha! When we combine the two factors together and go modulo $y^{2^k}$, we do recover our original factor.
Therefore, this perhaps suggest the following:
If $f(x,y)$ was reducible, then this $g_k$ is supposed to be part of a proper factor $g^\ast(x,y)$ of $f$. Note that $\deg_x(g^\ast) < \deg_x(f)$ and $\deg_y(g^\ast) \leq \deg_y(f)$ (since $f$ is monic in $x$, each factor must be monic in $x$ too so the degree in $x$ must be smaller).
Claim(?): $f(x,y)$ is reducible if and only if we can find some $g_k'(x,y)$ such that $\tilde{g}(x,y) = g_k \cdot g_k' \bmod{y^{2^k}}$ satisfies $\deg_x(\tilde{g}) < \deg_x(f)$ and $\deg_y(\tilde{g}) \leq \deg_y(f)$.
Turns out, the above claim is indeed true, and we can actually test if such a $g_k'$ exists by just writing down a system of linear equations to solve.