On Mon, Oct 30, 2023 at 5:02 PM John H Palmieri <jhpalmier...@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)
>
> 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 <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)
>>
>> >
>> > 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, <jhpalm...@gmail.com> 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/4508d1de-c377-45b5-90f6-fabddebc12aen%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/CAAWYfq1bbPWxVJx9sXxhcZbfV6Qjs-_RLZ1EjkrpEj9sA3LyJQ%40mail.gmail.com.
