Re: [sage-support] Computing the kernel of a map between polynomial algebras
Thanks, Dima. That works for me, too, and it's much faster than Sage was.
Now I'm trying some bigger examples...
On Monday, October 30, 2023 at 3:56:00 PM UTC-7 Dima Pasechnik wrote:
> 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
>
> On Mon, Oct 30, 2023 at 9:02 PM Dima Pasechnik wrote:
> >
> >
> >
> > On Mon, 30 Oct 2023, 20:50 Dima Pasechnik, wrote:
> >>
> >>
> >>
> >> On Mon, 30 Oct 2023, 20:25 John H Palmieri,
> 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
> 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.
> >
> >
> >>
> >>
> >>>
> >>>
> >>>
> >>> >
> >>> > On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
> >>> >>
> >>> >> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
> >>> >> >
> >>> >> > Isn't this what you want?
> >>> >> >
> >>> >> > sage: R. = 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 .
> >>> >> 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)
> >>> >>
> >>> >> >
> >>> >> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik
> wrote:
> >>> >> >>
> >>> >> >>
> >>> >> >>
> >>> >> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
> wrote:
> >>> >> >>>
> >>> >> >>> 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
Re: [sage-support] Computing the kernel of a map between polynomial algebras
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
On Mon, Oct 30, 2023 at 9:02 PM Dima Pasechnik wrote:
>
>
>
> On Mon, 30 Oct 2023, 20:50 Dima Pasechnik, wrote:
>>
>>
>>
>> On Mon, 30 Oct 2023, 20:25 John H Palmieri, 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 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.
>
>
>>
>>
>>>
>>>
>>>
>>> >
>>> > On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
>>> >>
>>> >> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
>>> >> >
>>> >> > Isn't this what you want?
>>> >> >
>>> >> > sage: R. = 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 .
>>> >> 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)
>>> >>
>>> >> >
>>> >> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
>>> >> >>
>>> >> >>
>>> >> >>
>>> >> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
>>> >> >> wrote:
>>> >> >>>
>>> >> >>> 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,
Re: [sage-support] Computing the kernel of a map between polynomial algebras
On Mon, 30 Oct 2023, 20:50 Dima Pasechnik, wrote:
>
>
> On Mon, 30 Oct 2023, 20:25 John H Palmieri,
> 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
>> 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.
>
>
>>
>>
>> >
>> > On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
>> >>
>> >> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
>> >> >
>> >> > Isn't this what you want?
>> >> >
>> >> > sage: R. = 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 .
>> >> 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)
>> >>
>> >> >
>> >> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik
>> wrote:
>> >> >>
>> >> >>
>> >> >>
>> >> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
>> wrote:
>> >> >>>
>> >> >>> 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?
>> >> >>
>> >> >>
>> >> >> 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)
>> >> >>
Re: [sage-support] Computing the kernel of a map between polynomial algebras
On Mon, 30 Oct 2023, 20:25 John H Palmieri, 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
> 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.
>
>
> >
> > On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
> >>
> >> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
> >> >
> >> > Isn't this what you want?
> >> >
> >> > sage: R. = 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 .
> >> 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)
> >>
> >> >
> >> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
> >> >>
> >> >>
> >> >>
> >> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
> wrote:
> >> >>>
> >> >>> 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?
> >> >>
> >> >>
> >> >> 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
>
Re: [sage-support] Computing the kernel of a map between polynomial algebras
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
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)"?
>
> On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
>>
>> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
>> >
>> > Isn't this what you want?
>> >
>> > sage: R. = 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 .
>> 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)
>>
>> >
>> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
>> >>
>> >>
>> >>
>> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
wrote:
>> >>>
>> >>> 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?
>> >>
>> >>
>> >> 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.
>> >
>> > --
>> > 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/487bf189-fce6-4b6b-9752-178602ff9808n%40googlegroups.com.
>
> --
> 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.
>
Re: [sage-support] Computing the kernel of a map between polynomial algebras
On Mon, Oct 30, 2023 at 5:04 PM John H Palmieri 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.
>
> On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
>>
>> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
>> >
>> > Isn't this what you want?
>> >
>> > sage: R. = 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 .
>> 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)
>>
>> >
>> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
>> >>
>> >>
>> >>
>> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri, wrote:
>> >>>
>> >>> 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?
>> >>
>> >>
>> >> 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.
>> >
>> > --
>> > 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/487bf189-fce6-4b6b-9752-178602ff9808n%40googlegroups.com.
>
> --
> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-support/0ddf54b3-1778-4fca-932c-bb5521963db2n%40googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
"sage-support"
Re: [sage-support] Computing the kernel of a map between polynomial algebras
On Mon, Oct 30, 2023 at 5:02 PM John H Palmieri 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)
>
> 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.
>
> On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
>>
>> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
>> >
>> > Isn't this what you want?
>> >
>> > sage: R. = 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 .
>> 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)
>>
>> >
>> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
>> >>
>> >>
>> >>
>> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri, wrote:
>> >>>
>> >>> 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?
>> >>
>> >>
>> >>
Re: [sage-support] Computing the kernel of a map between polynomial algebras
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.
On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
> >
> > Isn't this what you want?
> >
> > sage: R. = 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 .
> 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)
>
> >
> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
> >>
> >>
> >>
> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
> wrote:
> >>>
> >>> 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?
> >>
> >>
> >> 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
> .
> >
> > --
> > 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/487bf189-fce6-4b6b-9752-178602ff9808n%40googlegroups.com
> .
>
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/0ddf54b3-1778-4fca-932c-bb5521963db2n%40googlegroups.com.
Re: [sage-support] Computing the kernel of a map between polynomial algebras
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.
On Monday, October 30, 2023 at 7:14:16 AM UTC-7 Dima Pasechnik wrote:
> On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
> >
> > Isn't this what you want?
> >
> > sage: R. = 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 .
> 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)
>
> >
> > On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
> >>
> >>
> >>
> >> On Mon, 30 Oct 2023, 05:57 John H Palmieri,
> wrote:
> >>>
> >>> 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?
> >>
> >>
> >> 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
> >>>
Re: [sage-support] Computing the kernel of a map between polynomial algebras
On Mon, Oct 30, 2023 at 12:54 PM Kwankyu wrote:
>
> Isn't this what you want?
>
> sage: R. = 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 .
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)
>
> On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
>>
>>
>>
>> On Mon, 30 Oct 2023, 05:57 John H Palmieri, wrote:
>>>
>>> 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?
>>
>>
>> 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.
>
> --
> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-support/487bf189-fce6-4b6b-9752-178602ff9808n%40googlegroups.com.
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/CAAWYfq3h5d_swFG%2B83EtuDdA15KFuXrekmzeUX4WFU3-H8jfAA%40mail.gmail.com.
Re: [sage-support] Computing the kernel of a map between polynomial algebras
Isn't this what you want?
sage: R. = 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
On Monday, October 30, 2023 at 6:08:16 PM UTC+9 Dima Pasechnik wrote:
>
>
> On Mon, 30 Oct 2023, 05:57 John H Palmieri, wrote:
>
>> 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?
>>
>
> 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
>>
>>
>> .
>>
>
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/487bf189-fce6-4b6b-9752-178602ff9808n%40googlegroups.com.
Re: [sage-support] Computing the kernel of a map between polynomial algebras
On Mon, 30 Oct 2023, 05:57 John H Palmieri, wrote:
> 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?
>
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+unsubscr...@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
>
> .
>
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/CAAWYfq20q%3Dt1RzkNvxCT5RW9GNQAXHX7JfuKsCWaJjv_2F2aEw%40mail.gmail.com.
[sage-support] Computing the kernel of a map between polynomial algebras
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
--
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+unsubscr...@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.
