Ask Your Question

Sage crash when computing variety for an ideal with many variables

asked 2021-02-02 13:04:30 +0200

ofir_ar gravatar image

updated 2021-02-03 19:38:42 +0200

I try to run a code (on a Jupyter notebook) which computes the variety of an ideal for some polynomial in many variables (64 for in this case. Notice I solve for a and not for x,y,z). My code crashes with the following message:

RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1
error occurred in or before standard.lib::stdhilb line 299: `    intvec hi = hilb( Id(1),1,W );`
expected intvec-expression. type 'help intvec;'
leaving standard.lib::stdhilb 
leaving standard.lib::groebner

This is the code:

K = PolynomialRing(GF(2),2^6,'a') 
R = K["x, y, z"]
x, y, z = R.gens()[0], R.gens()[1], R.gens()[2]
a = K.gens()

pbc = lambda p :(( p%(x^4+1))%(y^4+1))%(z^4+1)

e_L = Matrix([[R((1 + x + y + z)^(2^4)/(1 + x + y + z))],
X,Y,Z = [Matrix(g.powers(4)) for g in [x,y,z]]
XYZ = XY.tensor_product(Z)
poly = (Matrix(a)*XYZ.transpose())[0,0]
RHS_eq = Matrix([[pbc((1 + x*y + x*z + y*z) * poly)],
                 [pbc((1 + x + y + z) * poly)]])

IJK = list(Words(alphabet=range(4), length=3))
for i,j,k in IJK:
    P = pbc(e_L + (x^i*y^j*z^k)*e_L)
    lhs = RHS_eq + P
    Eq = Matrix([[R(lhs[0,0])],

I = K.ideal(Eq[0,0].coefficients() + Eq[1,0].coefficients() + [q^4+q for q in K.gens()])
sols = I.variety(GF(2^6,'w'))
sols_arr = np.asarray([list(sol.values()) for sol in sols])     
edit retag flag offensive close merge delete


Please make your code self-contained so that it works in a fresh session (e.g. poly is currently not defined). The error you quote is due to the groebner function in Singular choosing a wrong strategy. You could try entering your ideal into Singular and using std (instead of groebner) there.

rburing gravatar imagerburing ( 2021-02-02 14:15:17 +0200 )edit

How do I that?

ofir_ar gravatar imageofir_ar ( 2021-02-03 18:59:18 +0200 )edit

Please fix your code so that it works when pasted into Then try I.groebner_basis() instead of I.variety(...) to get some idea about the solutions (the Groebner basis is in particular a system of generators of your ideal).

rburing gravatar imagerburing ( 2021-02-03 19:06:08 +0200 )edit

@rburing Thank you for your comment, the code in my questions fails as expected now. If I understand right, the last three lines should be changes as you suggested.

ofir_ar gravatar imageofir_ar ( 2021-02-03 19:40:03 +0200 )edit

@rburing I understand that the Groebner basis is a set of polynomials then equated to 0 the solutions to these equations are the variety that I want. But Sage's variety function doesn't allow to choose which algorithm to use to calculate the Groebner basis. I can compute the Groebner basis with either I.groebner_basis(algorithm='singular:std') or I.groebner_basis() so this doesn't seem to be the issue.

ofir_ar gravatar imageofir_ar ( 2021-02-04 10:30:42 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2021-02-09 18:24:26 +0200

Max Alekseyev gravatar image

updated 2022-06-13 00:55:59 +0200

While there is a bug in Singular preventing from using the built-in .variety() method, I've done my own quick-n-dirty alternative implementation of this method.

In your example just run myvariety( Eq[0,0].coefficients() + Eq[1,0].coefficients() + [q^4+q for q in K.gens()] )to get the corresponding variety of size $128$ in a minute or so. In fact, the variety here represents a vector space over $\mathrm{GF}(2)$ spanned by 7 vectors (and $128 = 2^7$).

def myroots(p):
    return p.roots(multiplicities=False)

def myvariety(sys,vars=None):
    J = ideal( sys )
    R = J.ring()

    if vars==None:
        vars = R.gens()
    if len(vars)==0:
        return [dict()]

    T = list()

    v = vars[0]
    nvars = vars[1:]

    B = J.elimination_ideal(nvars).basis

    assert len(B) == 1
    assert B[0] != 0

    for q in myroots(B[0].univariate_polynomial()):
        S = myvariety( [r.subs({v:q}) for r in J.interreduced_basis()], nvars )
        for s in S:
        T += S
    return T
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-02-02 13:04:30 +0200

Seen: 1,576 times

Last updated: Jun 13 '22