Revision history [back]

To lift C1 in terms of A1, we can use Singular's liftstd function to compute a Gröbner basis (standard basis) and the lift of the generators in one go. Using Singular directly would be a bit faster and maybe simpler to use, but from Sage, we could use it as follows:

def liftstd(I):
    I_sing = singular(I)
    singular.eval(f'matrix T; option(redSB); ideal gb = liftstd({I_sing._name}, T);')
    gb = singular('gb').sage()
    T = singular('T').sage()  # this conversion can take a considerable portion of time
    return gb.gens(), T

With A1, Id1, C1 defined in characteristic 0 as in the question, we can call it like this, where T is the desired transformation matrix:

sage: gb1, T = liftstd(Id1)  # about 4 minutes
sage: vector(gb1) == vector(A1) * T
True

Note that gb1 is a Gröbner basis that can be slightly different from C1, but is the same up to permutation and normalization (since we have used the option redSB to obtain a reduced Gröbner basis). The result from liftstd appears to have cleared denominators.

sage: gb1.is_groebner()
True
sage: sorted(C1) == sorted([p/p.lc() for p in gb1])
True

To lift C1 in terms of A1, we can use Singular's liftstd function to compute a Gröbner basis (standard basis) and the lift of the generators in one go. Using Singular directly would be a bit faster and maybe simpler to use, but from Sage, we could use it as follows:

def liftstd(I):
    I_sing = singular(I)
    singular.eval(f'matrix T; option(redSB); ideal gb = liftstd({I_sing._name}, T);')
    gb = singular('gb').sage()
    T = singular('T').sage()  # this conversion can take a considerable portion of time
    return gb.gens(), T

With A1, Id1, C1 defined in characteristic 0 as in the question, we can call it like this, where T is the desired transformation matrix:

sage: gb1, T = liftstd(Id1)  # about 4 minutes
sage: vector(gb1) == vector(A1) * T
True

Note that gb1 is a Gröbner basis that can be slightly different from C1, but is the same up to permutation and normalization (since we have used the option redSB to obtain a reduced Gröbner basis). The result from liftstd appears to have cleared denominators.

sage: gb1.is_groebner()
True
sage: sorted(C1) == sorted([p/p.lc() for p in gb1])
True

sage: lift_coeffs[0].denominator()
1368162068772907277016949808911674433443731715670078907923745566842319032218023389631644934432397528696968597075170914623476410897485963409010849263214726306499970668375272723902505492542578804635528861680478467483648734003200
sage: vector(lift_coeffs[1:32]).denominator()
2656390119210841608754981370882120113205857102430722953249676393122294033997615371473773495839032085051428692642636576714436971553290801783246162299823060549828740242317911755788137610144264508412396754742245938030951437820199254946394360942826997829288275150366754644953324917102942349871485467794222357245468234719335375771845013974468884379722016669288302764503021401318107329094660657757015547239722566526215291556857883675923230114898064723775663457116378618146964780224819530957477689490646036587994768392346835107733423453361617937580695957179594637828069492591400063540349984446852397354109287671639416489429684581776657409316670201740958431886602686864924701846786356441750340245959374442420515990922774839515663958555694585632127300568279856889192867103017906517301525030007958495348777414350304294826215034862534160497984985775719719885474544475502997778096966014848477429760000000000000000000
sage: vector(lift_coeffs[32:63]).denominator()
47108403017039852783571221674633224123403184742378006164117852516715317419896099460852953970280479173495445064152315046561513175890527026365848860620372742312104503344544264661558367744946603426009345747558665739151291962751244036615056187313189013733869788074886602481231471278125817799258392099089847778745311651501638395739945446023922108866268424690254839930414268645122365586352651354440509206702928280256096557379329823521976489183272686385168593623174968362910947981039697074928697888468982696663753624433821823437211625763633904986679802394055981580171322582161049009906471089351234141032235435807255040928416436348087365390235461192661173492514589750025082542753492059612398170931200000000000000000

To lift C1 in terms of A1, we can use Singular's liftstd function to compute a Gröbner basis (standard basis) and the lift of the generators in one go. Using Singular directly would be a bit faster and maybe simpler to use, but from Sage, we could use it as follows:

def liftstd(I):
    I_sing = singular(I)
    singular.eval(f'matrix T; option(redSB); ideal gb = liftstd({I_sing._name}, T);')
    gb = singular('gb').sage()
    T = singular('T').sage()  # this conversion can take a considerable portion of time
    return gb.gens(), T

With A1, Id1, C1 defined in characteristic 0 as in the question, we can call it like this, where T is the desired transformation matrix:

sage: gb1, T = liftstd(Id1)  # about 4 minutes
sage: vector(gb1) == vector(A1) * T
True

Note that gb1 is a Gröbner basis that can be slightly different from C1, but is the same up to permutation and normalization (since we have used the option redSB to obtain a reduced Gröbner basis). The result from liftstd appears to have cleared denominators.

sage: gb1.is_groebner()
True
sage: sorted(C1) == sorted([p/p.lc() for p in gb1])
True

Edit:

The analogous computation for the second ideal takes about 20 minutes. If one then constructs lift_coeffs as in rburing's answer, then (since the transformation matrices have integer coefficients) one needs to find the prime factors of the following denominators of lift_coeffs, which still seems to be a hard problem. At least, $29,41$ divide the bigger two.

sage: lift_coeffs[0].denominator()
1368162068772907277016949808911674433443731715670078907923745566842319032218023389631644934432397528696968597075170914623476410897485963409010849263214726306499970668375272723902505492542578804635528861680478467483648734003200
sage: vector(lift_coeffs[1:32]).denominator()
2656390119210841608754981370882120113205857102430722953249676393122294033997615371473773495839032085051428692642636576714436971553290801783246162299823060549828740242317911755788137610144264508412396754742245938030951437820199254946394360942826997829288275150366754644953324917102942349871485467794222357245468234719335375771845013974468884379722016669288302764503021401318107329094660657757015547239722566526215291556857883675923230114898064723775663457116378618146964780224819530957477689490646036587994768392346835107733423453361617937580695957179594637828069492591400063540349984446852397354109287671639416489429684581776657409316670201740958431886602686864924701846786356441750340245959374442420515990922774839515663958555694585632127300568279856889192867103017906517301525030007958495348777414350304294826215034862534160497984985775719719885474544475502997778096966014848477429760000000000000000000
sage: vector(lift_coeffs[32:63]).denominator()
47108403017039852783571221674633224123403184742378006164117852516715317419896099460852953970280479173495445064152315046561513175890527026365848860620372742312104503344544264661558367744946603426009345747558665739151291962751244036615056187313189013733869788074886602481231471278125817799258392099089847778745311651501638395739945446023922108866268424690254839930414268645122365586352651354440509206702928280256096557379329823521976489183272686385168593623174968362910947981039697074928697888468982696663753624433821823437211625763633904986679802394055981580171322582161049009906471089351234141032235435807255040928416436348087365390235461192661173492514589750025082542753492059612398170931200000000000000000

Even if you manage to compute the factorization, the primes might be too large to effectively compute the Gröbner bases modulo those primes, as Sage falls back to the generic (slow) toy implementation for primes larger than $2^31$.