API REFERENCE/omnibias-sos

omnibias.sos.monomials

0.1.0a2AlphaPython >=3.10AGPL / commercial

Sum-of-squares constructions, polynomial positivity checks, and rigorous validation of proposed Gram matrices.

import omnibias.sos.monomials

Module contract & mathematical conventions

Monomial bases and the Gram <-> coefficient linear maps.

An SOS decomposition writes p(x) = z(x)^T Q z(x) where z(x) is the vector of monomials up to half the degree of p. Multiplying two basis monomials z_i z_j yields the monomial with exponent basis[i] + basis[j], so the coefficient of a monomial alpha in z^T Q z is

sum over pairs (i, j) with basis[i] + basis[j] == alpha of mult * Q[i, j]

with mult = 1 on the diagonal and 2 off it (Q symmetric). This module builds the basis and that pair table -- the linear "coefficient-matching" constraints <A_alpha, Q> = p_alpha an SOS SDP must satisfy.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

CLASS

MonomialBasis

omnibias.sos.MonomialBasisSource ↗

class MonomialBasis

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

The monomial vector z(x) used to build a Gram matrix.

Parameters

Name	Type & default	Contract
n_varsdataclass field	intRequired	See the operation contract and implementation below.
exponentsdataclass field	tuple[Exponent, ...]Required	See the operation contract and implementation below.

Executed regression · is sos helper agrees

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_sos_helper_agrees() -> None:
    assert is_sos(X * X - X * Y + Y * Y + ONE)
    assert not is_sos(Polynomial(2, {(4, 2): 1.0, (2, 4): 1.0, (2, 2): -3.0, (0, 0): 1.0}))

python -m pytest "packages/omnibias-sos/tests/test_certify.py::test_is_sos_helper_agrees" -q

Regression example · monomial basis shape and order

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_monomial_basis_shape_and_order() -> None:
    basis = monomial_basis(2, 2)
    # 1, x, y, x^2, xy, y^2  (graded, constant first)
    assert basis[0] == (0, 0)
    assert len(basis) == 6
    assert all(sum(basis[i]) <= sum(basis[i + 1]) for i in range(len(basis) - 1))
    assert MonomialBasis.up_to_degree(3, 2).size == 10  # C(2+3,3)

python -m pytest packages/omnibias-sos/tests/test_problem.py -k test_monomial_basis_shape_and_order -q

Fields & methods

n_varsfield

n_vars: int

Declared int field on MonomialBasis. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

exponentsfield

exponents: tuple[Exponent, ...]

Declared tuple[Exponent, ...] field on MonomialBasis. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

up_to_degreemethod

up_to_degree(cls, n_vars: int, degree: int) -> MonomialBasis

See the class contract above and the exact method implementation below.

Parameters

Name	Type & default	Contract
n_varspositional-or-keyword	intRequired	See the operation contract and implementation below.
degreepositional-or-keyword	intRequired	See the operation contract and implementation below.

Returns: MonomialBasis

Executed regression · is sos helper agrees

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_sos_helper_agrees() -> None:
    assert is_sos(X * X - X * Y + Y * Y + ONE)
    assert not is_sos(Polynomial(2, {(4, 2): 1.0, (2, 4): 1.0, (2, 2): -3.0, (0, 0): 1.0}))

python -m pytest "packages/omnibias-sos/tests/test_certify.py::test_is_sos_helper_agrees" -q

Method implementation

    def up_to_degree(cls, n_vars: int, degree: int) -> MonomialBasis:
        return cls(n_vars, monomial_basis(n_vars, degree))

View source ↗

sizeproperty

size(self) -> int

See the class contract above and the exact method implementation below.

Returns: int

Executed regression · sosproblem default half degree and representability

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sosproblem_default_half_degree_and_representability() -> None:
    x = Polynomial.variable(0, 2)
    y = Polynomial.variable(1, 2)
    quartic = x * x * x * x + y * y * y * y + 1.0
    problem = SOSProblem.for_polynomial(quartic)
    assert problem.basis.size == monomial_basis(2, 2).__len__()
    assert problem.representable()

python -m pytest "packages/omnibias-sos/tests/test_problem.py::test_sosproblem_default_half_degree_and_representability" -q

Method implementation

    def size(self) -> int:
        return len(self.exponents)

View source ↗

evaluatemethod

evaluate(self, point: Sequence[float]) -> list[float]

The numeric vector z(point).

Parameters

Name	Type & default	Contract
pointpositional-or-keyword	Sequence[float]Required	See the operation contract and implementation below.

Returns: list[float]

Method implementation

    def evaluate(self, point: Sequence[float]) -> list[float]:
        """The numeric vector ``z(point)``."""
        out: list[float] = []
        for exp in self.exponents:
            term = 1.0
            for value, power in zip(point, exp, strict=True):
                if power:
                    term *= float(value) ** power
            out.append(term)
        return out

View source ↗

Read the implementation

class MonomialBasis:
    """The monomial vector ``z(x)`` used to build a Gram matrix."""

    n_vars: int
    exponents: tuple[Exponent, ...]

    @classmethod
    def up_to_degree(cls, n_vars: int, degree: int) -> MonomialBasis:
        return cls(n_vars, monomial_basis(n_vars, degree))

    @property
    def size(self) -> int:
        return len(self.exponents)

    def evaluate(self, point: Sequence[float]) -> list[float]:
        """The numeric vector ``z(point)``."""
        out: list[float] = []
        for exp in self.exponents:
            term = 1.0
            for value, power in zip(point, exp, strict=True):
                if power:
                    term *= float(value) ** power
            out.append(term)
        return out

Related APIsomnibias.sos.monomial_basis↗

Other public import paths

• omnibias.sos.MonomialBasis
• omnibias.sos.monomials.MonomialBasis

CLASS

SOSProblem

omnibias.sos.SOSProblemSource ↗

class SOSProblem

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

The problem "is polynomial a sum of squares in basis?".

basis defaults to the full monomial basis up to ceil(deg(p) / 2).

Parameters

Name	Type & default	Contract
polynomialdataclass field	PolynomialRequired	See the operation contract and implementation below.
basisdataclass field	MonomialBasisRequired	See the operation contract and implementation below.

Executed regression · is sos helper agrees

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_sos_helper_agrees() -> None:
    assert is_sos(X * X - X * Y + Y * Y + ONE)
    assert not is_sos(Polynomial(2, {(4, 2): 1.0, (2, 4): 1.0, (2, 2): -3.0, (0, 0): 1.0}))

python -m pytest "packages/omnibias-sos/tests/test_certify.py::test_is_sos_helper_agrees" -q

Regression example · sosproblem default half degree and representability

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sosproblem_default_half_degree_and_representability() -> None:
    x = Polynomial.variable(0, 2)
    y = Polynomial.variable(1, 2)
    quartic = x * x * x * x + y * y * y * y + 1.0
    problem = SOSProblem.for_polynomial(quartic)
    assert problem.basis.size == monomial_basis(2, 2).__len__()
    assert problem.representable()

python -m pytest packages/omnibias-sos/tests/test_problem.py -k test_sosproblem_default_half_degree_and_representability -q

Fields & methods

polynomialfield

polynomial: Polynomial

Declared Polynomial field on SOSProblem. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

basisfield

basis: MonomialBasis

Declared MonomialBasis field on SOSProblem. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

for_polynomialmethod

for_polynomial(cls, polynomial: Polynomial, *, half_degree: int | None=None) -> SOSProblem

See the class contract above and the exact method implementation below.

Parameters

Name	Type & default	Contract
polynomialpositional-or-keyword	PolynomialRequired	See the operation contract and implementation below.
half_degreekeyword-only	int | NoneDefault: None	See the operation contract and implementation below.

Returns: SOSProblem

Executed regression · is sos helper agrees

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_sos_helper_agrees() -> None:
    assert is_sos(X * X - X * Y + Y * Y + ONE)
    assert not is_sos(Polynomial(2, {(4, 2): 1.0, (2, 4): 1.0, (2, 2): -3.0, (0, 0): 1.0}))

python -m pytest "packages/omnibias-sos/tests/test_certify.py::test_is_sos_helper_agrees" -q

Method implementation

    def for_polynomial(
        cls, polynomial: Polynomial, *, half_degree: int | None = None
    ) -> SOSProblem:
        if half_degree is None:
            half_degree = (max(polynomial.degree(), 0) + 1) // 2
        basis = MonomialBasis.up_to_degree(polynomial.n_vars, half_degree)
        return cls(polynomial, basis)

View source ↗

representablemethod

representable(self) -> bool

Whether every monomial of the polynomial can appear in z^T Q z.

A monomial outside the product support (e.g. an odd-degree term the basis cannot build) makes the SOS problem infeasible.

Returns: bool

Executed regression · sosproblem default half degree and representability

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sosproblem_default_half_degree_and_representability() -> None:
    x = Polynomial.variable(0, 2)
    y = Polynomial.variable(1, 2)
    quartic = x * x * x * x + y * y * y * y + 1.0
    problem = SOSProblem.for_polynomial(quartic)
    assert problem.basis.size == monomial_basis(2, 2).__len__()
    assert problem.representable()

python -m pytest "packages/omnibias-sos/tests/test_problem.py::test_sosproblem_default_half_degree_and_representability" -q

Method implementation

    def representable(self) -> bool:
        """Whether every monomial of the polynomial can appear in ``z^T Q z``.

        A monomial outside the product support (e.g. an odd-degree term the basis
        cannot build) makes the SOS problem infeasible.
        """
        products = set(gram_products(self.basis.exponents))
        return self.polynomial.support <= products

View source ↗

Read the implementation

class SOSProblem:
    r"""The problem "is ``polynomial`` a sum of squares in ``basis``?".

    ``basis`` defaults to the full monomial basis up to ``ceil(deg(p) / 2)``.
    """

    polynomial: Polynomial
    basis: MonomialBasis

    @classmethod
    def for_polynomial(
        cls, polynomial: Polynomial, *, half_degree: int | None = None
    ) -> SOSProblem:
        if half_degree is None:
            half_degree = (max(polynomial.degree(), 0) + 1) // 2
        basis = MonomialBasis.up_to_degree(polynomial.n_vars, half_degree)
        return cls(polynomial, basis)

    def representable(self) -> bool:
        """Whether every monomial of the polynomial can appear in ``z^T Q z``.

        A monomial outside the product support (e.g. an odd-degree term the basis
        cannot build) makes the SOS problem infeasible.
        """
        products = set(gram_products(self.basis.exponents))
        return self.polynomial.support <= products

Related APIsomnibias.sos.gram_products↗

Other public import paths

• omnibias.sos.SOSProblem
• omnibias.sos.monomials.SOSProblem

FUNCTION

arrangement_adapted_basis

omnibias.sos.arrangement_adapted_basisSource ↗

arrangement_adapted_basis(polynomial: Polynomial, arrangement: Sequence[Sequence[float]], *, degree: int) -> MonomialBasis

Sparse monomial basis concentrated on an axis-aligned arrangement.

Ambient total-degree monomials up to degree are kept. Each hyperplane a·x + b = 0 contributes extra pure powers of its dominant coordinate up to half the polynomial's degree in that variable, so a well that is a high even power of one arrangement form can be certified at a *lower* ambient degree than the total-degree basis.

This chooses tightness, never soundness. Failures are reported (theory 07-05 G5), not excluded.

Parameters

Name	Type & default	Contract
polynomialpositional-or-keyword	PolynomialRequired	See the operation contract and implementation below.
arrangementpositional-or-keyword	Sequence[Sequence[float]]Required	See the operation contract and implementation below.
degreekeyword-only	intRequired	See the operation contract and implementation below.

ReturnsMonomialBasis

Explicit validation & failure cases

• When degree < 0, raises ValueError(f'degree must be >= 0, got {degree}').
• When len(coords) < n, raises ValueError('each arrangement form must have at least n_vars coefficients').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · adapted basis is sparser than total degree

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_adapted_basis_is_sparser_than_total_degree() -> None:
    spec = named_adapted_problems()[0]
    poly = spec["polynomial"]
    adapted = arrangement_adapted_basis(poly, spec["arrangement"], degree=1)
    assert certify_sos(poly, basis=adapted).certified
    assert not certify_sos(poly, half_degree=1).certified

python -m pytest "packages/omnibias-sos/tests/test_adapted_basis.py::test_adapted_basis_is_sparser_than_total_degree" -q

Read the implementation

def arrangement_adapted_basis(
    polynomial: Polynomial,
    arrangement: Sequence[Sequence[float]],
    *,
    degree: int,
) -> MonomialBasis:
    """Sparse monomial basis concentrated on an axis-aligned arrangement.

    Ambient total-degree monomials up to ``degree`` are kept. Each
    hyperplane ``a·x + b = 0`` contributes extra pure powers of its
    dominant coordinate up to half the polynomial's degree in that
    variable, so a well that is a high even power of one arrangement
    form can be certified at a *lower* ambient degree than the
    total-degree basis.

    This chooses tightness, never soundness. Failures are reported
    (theory 07-05 G5), not excluded.
    """
    if degree < 0:
        raise ValueError(f"degree must be >= 0, got {degree}")
    n = polynomial.n_vars
    exponents = set(monomial_basis(n, degree))
    max_power = [0] * n
    for exp in polynomial.support:
        for i, power in enumerate(exp):
            if power > max_power[i]:
                max_power[i] = int(power)
    for form in arrangement:
        coords = [float(c) for c in form]
        if len(coords) < n:
            raise ValueError("each arrangement form must have at least n_vars coefficients")
        # Dominant coordinate of a·x (+ optional offset).
        axis = max(range(n), key=lambda i: abs(coords[i]))
        half = (max_power[axis] + 1) // 2
        for power in range(degree + 1, half + 1):
            exp = [0] * n
            exp[axis] = power
            exponents.add(tuple(exp))
    ordered = tuple(sorted(exponents, key=lambda e: (sum(e), e)))
    return MonomialBasis(n, ordered)

Related APIsomnibias.sos.MonomialBasis↗omnibias.sos.monomial_basis↗

Other public import paths

• omnibias.sos.arrangement_adapted_basis
• omnibias.sos.monomials.arrangement_adapted_basis

FUNCTION

gram_products

omnibias.sos.gram_productsSource ↗

gram_products(basis: Sequence[Exponent]) -> dict[Exponent, list[tuple[int, int, int]]]

Map each product monomial alpha to the (i, j, mult) that build it.

mult is 1 when i == j and 2 otherwise, so that sum mult * Q[i, j] over the list equals the coefficient of alpha in z(x)^T Q z(x) for a symmetric Q (only i <= j are listed).

Parameters

Name	Type & default	Contract
basispositional-or-keyword	Sequence[Exponent]Required	See the operation contract and implementation below.

Returnsdict[Exponent, list[tuple[int, int, int]]]

Executed regression · is sos helper agrees

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_sos_helper_agrees() -> None:
    assert is_sos(X * X - X * Y + Y * Y + ONE)
    assert not is_sos(Polynomial(2, {(4, 2): 1.0, (2, 4): 1.0, (2, 2): -3.0, (0, 0): 1.0}))

python -m pytest "packages/omnibias-sos/tests/test_certify.py::test_is_sos_helper_agrees" -q

Regression example · products are disjoint per entry

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_products_are_disjoint_per_entry() -> None:
    # Each Gram entry (i, j) feeds exactly one product monomial -- the property the
    # exact rational projection relies on.
    basis = monomial_basis(3, 2)
    seen: set[tuple[int, int]] = set()
    for pairs in gram_products(basis).values():
        for i, j, _mult in pairs:
            assert (i, j) not in seen
            seen.add((i, j))

python -m pytest packages/omnibias-sos/tests/test_problem.py -k test_products_are_disjoint_per_entry -q

Read the implementation

def gram_products(
    basis: Sequence[Exponent],
) -> dict[Exponent, list[tuple[int, int, int]]]:
    r"""Map each product monomial ``alpha`` to the ``(i, j, mult)`` that build it.

    ``mult`` is ``1`` when ``i == j`` and ``2`` otherwise, so that
    ``sum mult * Q[i, j]`` over the list equals the coefficient of ``alpha`` in
    ``z(x)^T Q z(x)`` for a symmetric ``Q`` (only ``i <= j`` are listed).
    """
    products: dict[Exponent, list[tuple[int, int, int]]] = {}
    size = len(basis)
    for i in range(size):
        for j in range(i, size):
            alpha = tuple(a + b for a, b in zip(basis[i], basis[j], strict=True))
            mult = 1 if i == j else 2
            products.setdefault(alpha, []).append((i, j, mult))
    return products

Other public import paths

• omnibias.sos.gram_products
• omnibias.sos.monomials.gram_products

FUNCTION

gram_to_poly

omnibias.sos.gram_to_polySource ↗

gram_to_poly(gram: Sequence[Sequence[float]], basis: Sequence[Exponent], n_vars: int) -> Polynomial

Expand z(x)^T Q z(x) back into a Polynomial.

Parameters

Name	Type & default	Contract
grampositional-or-keyword	Sequence[Sequence[float]]Required	See the operation contract and implementation below.
basispositional-or-keyword	Sequence[Exponent]Required	See the operation contract and implementation below.
n_varspositional-or-keyword	intRequired	See the operation contract and implementation below.

ReturnsPolynomial

Executed regression · gram roundtrip

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_gram_roundtrip() -> None:
    basis = monomial_basis(2, 1)  # (0,0),(1,0),(0,1)
    gram = [[0.0, 0.0, 0.0], [0.0, 1.0, 1.0], [0.0, 1.0, 1.0]]
    poly = gram_to_poly(gram, basis, 2)  # (x + y)^2
    assert poly.coefficient((2, 0)) == 1.0
    assert poly.coefficient((1, 1)) == 2.0
    assert poly.coefficient((0, 2)) == 1.0

python -m pytest "packages/omnibias-sos/tests/test_problem.py::test_gram_roundtrip" -q

Read the implementation

def gram_to_poly(
    gram: Sequence[Sequence[float]], basis: Sequence[Exponent], n_vars: int
) -> Polynomial:
    r"""Expand ``z(x)^T Q z(x)`` back into a :class:`Polynomial`."""
    coeffs: dict[Exponent, float] = {}
    for alpha, pairs in gram_products(basis).items():
        acc = 0.0
        for i, j, mult in pairs:
            acc += mult * float(gram[i][j])
        if acc != 0.0:
            coeffs[alpha] = acc
    return Polynomial(n_vars, coeffs)

Related APIsomnibias.sos.gram_products↗omnibias.sos.Polynomial↗

Other public import paths

• omnibias.sos.gram_to_poly
• omnibias.sos.monomials.gram_to_poly

FUNCTION

monomial_basis

omnibias.sos.monomial_basisSource ↗

monomial_basis(n_vars: int, degree: int) -> tuple[Exponent, ...]

All monomials in n_vars variables of total degree 0..degree.

Returned in graded order (degree ascending); the constant monomial is first.

Parameters

Name	Type & default	Contract
n_varspositional-or-keyword	intRequired	See the operation contract and implementation below.
degreepositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnstuple[Exponent, ...]

Explicit validation & failure cases

• When n_vars < 0 or degree < 0, raises ValueError('n_vars and degree must be non-negative').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · is sos helper agrees

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_sos_helper_agrees() -> None:
    assert is_sos(X * X - X * Y + Y * Y + ONE)
    assert not is_sos(Polynomial(2, {(4, 2): 1.0, (2, 4): 1.0, (2, 2): -3.0, (0, 0): 1.0}))

python -m pytest "packages/omnibias-sos/tests/test_certify.py::test_is_sos_helper_agrees" -q

Regression example · gram roundtrip

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_gram_roundtrip() -> None:
    basis = monomial_basis(2, 1)  # (0,0),(1,0),(0,1)
    gram = [[0.0, 0.0, 0.0], [0.0, 1.0, 1.0], [0.0, 1.0, 1.0]]
    poly = gram_to_poly(gram, basis, 2)  # (x + y)^2
    assert poly.coefficient((2, 0)) == 1.0
    assert poly.coefficient((1, 1)) == 2.0
    assert poly.coefficient((0, 2)) == 1.0

python -m pytest packages/omnibias-sos/tests/test_problem.py -k test_gram_roundtrip -q

Read the implementation

def monomial_basis(n_vars: int, degree: int) -> tuple[Exponent, ...]:
    """All monomials in ``n_vars`` variables of total degree ``0..degree``.

    Returned in graded order (degree ascending); the constant monomial is first.
    """
    if n_vars < 0 or degree < 0:
        raise ValueError("n_vars and degree must be non-negative")
    out: list[Exponent] = []
    for total in range(degree + 1):
        out.extend(_compositions(n_vars, total))
    return tuple(out)

Other public import paths

• omnibias.sos.monomial_basis
• omnibias.sos.monomials.monomial_basis

← Package overviewRunnable learning examples →