Application Examples

Examples from the applications section of SAGBI and Groebner Bases Detection are written below in Julia, using Oscar.jl and SagbiGbDetection.jl.

# Oscar handles the polynomial rings; SagbiGbDetection handles the
# Groebner and SAGBI checks.
using Oscar
using SagbiGbDetection
using Combinatorics

Sullivant-Talaska Ideal

For the cycle graph on four vertices, the Sullivant-Talaska ideal I_4 is generated by minors of selected cyclic submatrices. The code below detects weights where these generators form a Groebner basis.

# Polynomial ring QQ[s_ij] for an n x n symmetric matrix.
function define_ring(n)
    variables_R = vec(["s_$(i)$(j)" for i in 1:n, j in 1:n])
    return polynomial_ring(QQ, variables_R)
end

# Start with an n x n matrix and impose symmetry.
function symmetric_generic_matrix(v, n)
    generic_matrix = reshape(v, n, n)
    for i in 1:n
        for j in 1:i-1
            generic_matrix[i, j] = generic_matrix[j, i]
        end
    end
    return generic_matrix
end

# Convert the Julia submatrix before taking its determinant in Oscar.
function determinant_mpoly(submatrix::Matrix)
    return det(matrix(submatrix))
end

# All s x s minors, indexed by choices of rows and columns.
function compute_minors(matrix::Matrix{T}, s::Int) where T
    m, n = size(matrix, 1), size(matrix, 2)
    if m < s || n < s || s < 1
        throw(ArgumentError("Invalid values for m, n, or s"))
    end

    determinants = T[]
    for rows_combination in Combinatorics.combinations(1:m, s)
        for cols_combination in Combinatorics.combinations(1:n, s)
            minor = matrix[rows_combination, cols_combination]
            push!(determinants, determinant_mpoly(copy(minor)))
        end
    end
    return determinants
end

# The generators are the 3 x 3 minors of the selected cyclic submatrices.
function k_submatrices_minors(generic_matrix, rows, cols, k)
    minors_vec = eltype(generic_matrix)[]
    for i in 1:k
        sub_matrix = generic_matrix[rows[i], cols[i]]
        append!(minors_vec, compute_minors(sub_matrix, 3))
    end
    return minors_vec
end

# Symmetric 4 x 4 matrix for the cycle graph.
n = 4
R, v = define_ring(n)
generic_matrix = symmetric_generic_matrix(v, n)

# Cyclic 3-row windows.
rows = Vector{Vector{Int}}(undef, n)
for i in 1:n
    rows[i] = [(j + i - 2) % n + 1 for j in 1:3]
end

# Matching cyclic 3-column windows.
cols = Vector{Vector{Int}}(undef, n)
for i in 1:n
    cols[i] = [(j + i + 1) % n + 1 for j in 0:2]
end

# Detect Groebner weights for the resulting generators.
G = k_submatrices_minors(generic_matrix, rows, cols, n)
weight_vectors = weightVectorsRealizingGB(G, R)
length(weight_vectors)
# 9

Minors Of A General Matrix

Here the generators are the 2 x 2 minors of a general 3 x 3 matrix.

# Coordinate ring for a generic 3 x 3 matrix.
T, v = polynomial_ring(QQ, [
    "t11", "t12", "t13",
    "t21", "t22", "t23",
    "t31", "t32", "t33",
])
(t11, t12, t13, t21, t22, t23, t31, t32, t33) = v

t_ij = [
    t11 t12 t13
    t21 t22 t23
    t31 t32 t33
]

# SAGBI weights for the 2 x 2 minors.
minors = compute_minors(t_ij, 2)
weightVectorsRealizingSAGBI(minors, T)
# 6 weight vectors

Truncation Variety

The truncation variety V_{1,3} gives an example where no tested term order makes the parametrization a SAGBI basis.

# Coordinate ring for the parametrization.
S, v = polynomial_ring(QQ, [
    "s", "z1", "z2", "z3", "z4", "z5",
    "z6", "z7", "z8", "z9", "z10",
])
(s, z1, z2, z3, z4, z5, z6, z7, z8, z9, z10) = v

# Parametrizing polynomials for V_{1,3}.
Q = [
    s,
    s*z1,
    s*z2,
    s*z3,
    s*z4,
    s*z5,
    s*z6,
    s*z7,
    s*z8,
    s*z9,
    s*(z1*z5 - z2*z4),
    s*(z1*z6 - z3*z4),
    s*(z2*z6 - z3*z5),
    s*(z1*z8 - z2*z7),
    s*(z1*z9 - z3*z7),
    s*(z2*z9 - z3*z8),
    s*(z4*z8 - z5*z7),
    s*(z4*z9 - z6*z7),
    s*(z5*z9 - z6*z8),
    s*(z10 + z1*(z5*z9 - z6*z8) - z2*(z4*z9 - z6*z7) + z3*(z4*z8 - z5*z7)),
]

# The empty output records that no SAGBI weight was found.
weightVectorsRealizingSAGBI(Q, S)
# []