Computing the kernel of a map between polynomial algebras

[John H Palmieri]

Does anyone have any tips for how to compute the kernel of a map between polynomial algebras, or for checking whether the map is injective? I have families of such maps involving algebras with many generators. I'm working over GF(2), if that matters. In one example I defined the map phi: R -> S where R has 12 generators, S has 19 generators, and did

    sage: phi.is_injective()

After about 30 hours, Sage quit on me, perhaps running out of memory ("Killed: 9"). An example of the sort of map I'm interested in:

sage: phi

Ring morphism:
  From: Multivariate Polynomial Ring in h20, h21, h30, h31, h40, h41, h50 over Finite Field of size 2
  To:   Multivariate Polynomial Ring in h20, h21, h30, h31, h40, h41, h50, xi1, xi2, xi3, xi4, xi5 over Finite Field of size 2
  Defn: h20 |--> h20
        h21 |--> h21
        h30 |--> h20*xi1^4 + h21*xi1 + h30
        h31 |--> h21*xi1^8 + h31
        h40 |--> h21*xi1^9 + h30*xi1^8 + h20*xi2^4 + h31*xi1
        h41 |--> h31*xi1^16 + h21*xi2^8
        h50 |--> h31*xi1^17 + h21*xi1*xi2^8 + h30*xi2^8 + h20*xi3^4

Any suggestions?

--

John

[Dima Pasechnik]

The standard way to find the kernel of a map 

phi: A->B is to take the

ring R generated by the gens of A and B and compute the Gröbner basis of the ideal I generated by {a-phi(a)|a in gens(A)}, and then

take the intersection of I with A.

(for the latter you have to take R with an appropriate order)

The Gröbner basis would be done by Singular.

Better Gröbner basis routines are available in the msolve spkg.

I'd try using msolve. There are also options such as computing I w.r.t. to an "easier" order and then chaniging the order (so-called Gröbner walk), they might work better here (it's all more of art than science here)

HTH

Dima

--

John

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/97318b8e-f4c9-4af3-a8ff-b901a4f2c971n%40googlegroups.com.

[Kwankyu]

Isn't this what you want?

sage: R.<x,y> = QQ[]
sage: phi = R.hom([x,x])
sage: phi
Ring endomorphism of Multivariate Polynomial Ring in x, y over Rational Field
  Defn: x |--> x
        y |--> x
sage: phi.kernel()
Ideal (x - y) of Multivariate Polynomial Ring in x, y over Rational Field

[Dima Pasechnik]

On Mon, Oct 30, 2023 at 12:54 PM Kwankyu <ekwa...@gmail.com> wrote:
>
> Isn't this what you want?
>
> sage: R.<x,y> = QQ[]
> sage: phi = R.hom([x,x])
> sage: phi
> Ring endomorphism of Multivariate Polynomial Ring in x, y over Rational Field
> Defn: x |--> x
> y |--> x
> sage: phi.kernel()
> Ideal (x - y) of Multivariate Polynomial Ring in x, y over Rational Field

that's the kernel of the endomorphism phi of R.
John's question is a bit different, and it will require
finding the intersection of such an ideal with the domain of his map.
His R=F_2[h20,...,h50,xi1,...,xi5] and phi induces an endomorphism of
R with the kernel <h_ij-phi(h_ij) I i,j in [(2,0),..,(5,0)]>.
Then phi is injective iff the intersection of this ideal with
F_2[h20,...,h50]={0}.
And this needs a Grobner basis computation.

By the way, using

h30 |--> h20*xi1^4 + h21*xi1 + h30
h31 |--> h21*xi1^8 + h31

one can split the problem into cases
1) xi1=0
2) h21=h20=0
(but perhaps it's only specific to this particular example)

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/487bf189-fce6-4b6b-9752-178602ff9808n%40googlegroups.com.

[John H Palmieri]

So Sage doesn't already use Gröbner bases when computing kernels of such maps? Okay, I'll try that.

Now that I've looked at the code a little bit, I see that `phi.is_injective()` just calls `phi.kernel()` and checks whether it's zero. I was hoping that there was something more clever: if I want to know whether something is injective, I only care whether the kernel is zero, not precisely what the kernel is.

By the way, this struck me as odd:

sage: phi
Ring morphism:
  From: Multivariate Polynomial Ring in h20, h21, h30, h31, h40, h41 over Finite Field of size 2
  To:   Multivariate Polynomial Ring in h20, h21, h30, h31, xi1, xi2, xi3, xi4 over Finite Field of size 2

  Defn: h20 |--> h20
        h21 |--> h21
        h30 |--> h20*xi1^4 + h21*xi1 + h30
        h31 |--> h21*xi1^8 + h31
        h40 |--> h21*xi1^9 + h30*xi1^8 + h20*xi2^4 + h31*xi1
        h41 |--> h31*xi1^16 + h21*xi2^8

sage: %time phi.is_injective()
CPU times: user 7.32 s, sys: 58.7 ms, total: 7.38 s
Wall time: 7.44 s

True

Note that phi doesn't do anything very interesting with h20 and h21: it sends each of those to itself. If I remove them from the domain (I need to keep them in the codomain because they're involved in other terms), the computation is slower:

sage: phi
Ring morphism:
  From: Multivariate Polynomial Ring in h30, h31, h40, h41 over Finite Field of size 2
  To:   Multivariate Polynomial Ring in h20, h21, h30, h31, xi1, xi2, xi3, xi4 over Finite Field of size 2
  Defn: h30 |--> h20*xi1^4 + h21*xi1 + h30

        h31 |--> h21*xi1^8 + h31
        h40 |--> h21*xi1^9 + h30*xi1^8 + h20*xi2^4 + h31*xi1
        h41 |--> h31*xi1^16 + h21*xi2^8

sage: %time phi.is_injective()
CPU times: user 15.7 s, sys: 101 ms, total: 15.8 s
Wall time: 15.9 s
True

I've seen this on two different machines: roughly double the time to do the second computation.

[John H Palmieri]

Are endomorphisms better to work with? I might be able to extend my map to an endomorphism of the larger ring, if that would make the computation easier. Probably just send xi1 -> xi1, xi2 -> xi2, etc.

[Dima Pasechnik]

On Mon, Oct 30, 2023 at 5:02 PM John H Palmieri <jhpalm...@gmail.com> wrote:
>
> So Sage doesn't already use Gröbner bases when computing kernels of such maps? Okay, I'll try that.

yes, it certainly does. I just thought that using a non-default
Gröbner basis backend would help.
(and you can only do this if you explicitly write out the ring and the
ideal in question)

>
> Now that I've looked at the code a little bit, I see that `phi.is_injective()` just calls `phi.kernel()` and checks whether it's zero. I was hoping that there was something more clever: if I want to know whether something is injective, I only care whether the kernel is zero, not precisely what the kernel is.

I don't think there is a magic way to decide whether the ideal has
trivial intersection (the intersection is exactly the kernel you're
after) with a subring
without either computing the appropriate Grobner basis, or using
resultants to eliminate variables.
(sometimes resultants work better, by the way)

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/4508d1de-c377-45b5-90f6-fabddebc12aen%40googlegroups.com.

[Dima Pasechnik]

On Mon, Oct 30, 2023 at 5:04 PM John H Palmieri <jhpalm...@gmail.com> wrote:
>
> Are endomorphisms better to work with? I might be able to extend my map to an endomorphism of the larger ring, if that would make the computation easier. Probably just send xi1 -> xi1, xi2 -> xi2, etc.

these are "already there", as if phi is an endomorphism then ker(phi)
is generated by a-phi(a) - so
whenever phi(a)=a this reduces to 0.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/0ddf54b3-1778-4fca-932c-bb5521963db2n%40googlegroups.com.

[John H Palmieri]

On Monday, October 30, 2023 at 12:28:18 PM UTC-7 Dima Pasechnik wrote:

On Mon, Oct 30, 2023 at 5:04 PM John H Palmieri <jhpalm...@gmail.com> wrote:
>
> Are endomorphisms better to work with? I might be able to extend my map to an endomorphism of the larger ring, if that would make the computation easier. Probably just send xi1 -> xi1, xi2 -> xi2, etc.

these are "already there", as if phi is an endomorphism then ker(phi)
is generated by a-phi(a) - so
whenever phi(a)=a this reduces to 0.

I don't understand this. Define phi: k[x,y,z] -> k[x,y,z] by

x -> y

y -> z

z -> 0

Then x - phi(x) = x - y  is not in the kernel. What do you mean by "ker(phi) is generated by a-phi(a)"?

[Dima Pasechnik]

On Mon, 30 Oct 2023, 20:25 John H Palmieri, <jhpalm...@gmail.com> wrote:

On Monday, October 30, 2023 at 12:28:18 PM UTC-7 Dima Pasechnik wrote:

On Mon, Oct 30, 2023 at 5:04 PM John H Palmieri <jhpalm...@gmail.com> wrote:
>
> Are endomorphisms better to work with? I might be able to extend my map to an endomorphism of the larger ring, if that would make the computation easier. Probably just send xi1 -> xi1, xi2 -> xi2, etc.

these are "already there", as if phi is an endomorphism then ker(phi)
is generated by a-phi(a) - so
whenever phi(a)=a this reduces to 0.

I don't understand this. Define phi: k[x,y,z] -> k[x,y,z] by

x -> y

y -> z

z -> 0

Then x - phi(x) = x - y  is not in the kernel. What do you mean by "ker(phi) is generated by a-phi(a)"?

OK, sorry, we're getting confused. 

You are interested in checking whether phi, like this:

phi: k[x,y,z] -> k[x',y',z']

x->y', y->z', z->0

is an epimorphism. This is the same as saying that the kernel of phi, which is the intersection of the ideal

(x-y', y-z', z) in k[x,y,z,x',y',z'] with k[x,y,z], is trivial, i.e., zero. (in this case it's not trivial, it contains z).

So yes, one can think of phi as inducing an endomorphism of  k[x,y,z,x',y',z'], of a special kind.

How this relates to endomorphisms of k[x,y,z], I don't know.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/e301dc26-c7b5-4f82-a74a-57eaf0769d0dn%40googlegroups.com.

[Dima Pasechnik]

On Mon, 30 Oct 2023, 20:50 Dima Pasechnik, <dim...@gmail.com> wrote:

On Mon, 30 Oct 2023, 20:25 John H Palmieri, <jhpalm...@gmail.com> wrote:

On Monday, October 30, 2023 at 12:28:18 PM UTC-7 Dima Pasechnik wrote:

On Mon, Oct 30, 2023 at 5:04 PM John H Palmieri <jhpalm...@gmail.com> wrote:
>
> Are endomorphisms better to work with? I might be able to extend my map to an endomorphism of the larger ring, if that would make the computation easier. Probably just send xi1 -> xi1, xi2 -> xi2, etc.

these are "already there", as if phi is an endomorphism then ker(phi)
is generated by a-phi(a) - so
whenever phi(a)=a this reduces to 0.

I don't understand this. Define phi: k[x,y,z] -> k[x,y,z] by

x -> y

y -> z

z -> 0

Then x - phi(x) = x - y  is not in the kernel. What do you mean by "ker(phi) is generated by a-phi(a)"?

OK, sorry, we're getting confused. 

You are interested in checking whether phi, like this:

phi: k[x,y,z] -> k[x',y',z']

x->y', y->z', z->0

is an epimorphism. This is the same as saying that the kernel of phi, which is the intersection of the ideal

(x-y', y-z', z) in k[x,y,z,x',y',z'] with k[x,y,z], is trivial, i.e., zero. (in this case it's not trivial, it contains z).

So yes, one can think of phi as inducing an endomorphism of  k[x,y,z,x',y',z'], of a special kind.

How this relates to endomorphisms of k[x,y,z], I don't know.

if phi had a fixed point, like x->cx with c in k^*,

then one could be a bit more economic, and do not introduce x' (and the corresponding ideal generator x-cx'), but immediately substitute it with x/c.

[Dima Pasechnik]

Hi John,
I tried running msolve on your input (more precisely, converting it
into the problem of
finding the Grobner basis w.r.t. to the elimination order, as I
explained), and I see that
it's an injective map.

Computation takes about 3 minutes on an old laptop.
Specifically, I merely run msolve at the command line, on the attached
input file x2,
and output file y2
as follows. Here -v 2 is verbosity level, -t 4 means 4 threads, -e 10
means eliminate
the 1st 10 variables.
(I renamed the variables in (almost) alphabetical order, as I thought
msolve cannot
handle variable names like you have, but, no it wasn't actually necessary)

As far as I can see, the outputted basis does not have elements which only
have the varibles in the domain of your map (in x2 they are p, q, r,
s, t, u, v),
meaning that the map has no nontrivial kernel.

$ msolve -f x2 -o y2 -v 2 -g 2 -t 4 -e 10

[John H Palmieri]

Thanks, Dima. That works for me, too, and it's much faster than Sage was. Now I'm trying some bigger examples...