API REFERENCE/omnibias-sos

omnibias.sos.problem

0.1.0a2AlphaPython >=3.10AGPL / commercial

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

import omnibias.sos.problem

Module contract & mathematical conventions

Multivariate polynomials and the SOS certificate container.

A Polynomial is a sparse multi-index dictionary {(e_1, ..., e_n): coefficient} over n real variables, with just enough algebra (+, -, *, scalar scaling, evaluation, partial derivatives) to build the residual polynomials the Sum-of-Squares and auxiliary-functional machinery needs -- e.g. C - Phi - grad(V) . f for the background method.

SOSCertificate is the pure result container produced by omnibias.sos.certify.certify_sos; it is sealed into a tamper-evident v1 certificate by omnibias.sos.honesty.

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 →

CONSTANT

Exponent

omnibias.sos.ExponentSource ↗

Exponent = tuple[int, ...]

This exported constant is defined by the expression above. Its exact value and annotation come from the pinned source; use it with the module contract.

Read the implementation

Exponent = tuple[int, ...]

Other public import paths

• omnibias.sos.Exponent
• omnibias.sos.problem.Exponent

CLASS

Polynomial

omnibias.sos.PolynomialSource ↗

class Polynomial

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.

A sparse multivariate polynomial with real (float) coefficients.

Parameters

n_vars: Number of variables. coeffs: Mapping from exponent multi-index (length n_vars) to coefficient. Zero coefficients and duplicate keys are normalised away on construction.

Parameters

Name	Type & default	Contract
n_varsdataclass field	intRequired	Number of variables.
coeffsdataclass field	Mapping[Exponent, float]Required	Mapping from exponent multi-index (length n_vars) to coefficient. Zero coefficients and duplicate keys are normalised away on construction.

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 · zero and cancellation

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_zero_and_cancellation() -> None:
    x = Polynomial.variable(0, 1)
    assert (x - x).coeffs == {}
    assert (x - x).degree() == -1
    assert Polynomial.zero(3).evaluate([1.0, 2.0, 3.0]) == 0.0

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

Fields & methods

n_varsfield

n_vars: int

Number of variables.

View source ↗

coeffsfield

coeffs: Mapping[Exponent, float]

Mapping from exponent multi-index (length n_vars) to coefficient. Zero coefficients and duplicate keys are normalised away on construction.

View source ↗

__post_init__method

__post_init__(self) -> None

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

Returns: None

Validation & failure cases

• When len(key) != self.n_vars, raises ValueError(f'exponent {key!r} has length {len(key)}, expected {self.n_vars}').
• When any((e < 0 for e in key)), raises ValueError(f'negative exponent in {key!r}').

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 __post_init__(self) -> None:
        cleaned: dict[Exponent, float] = {}
        for exp, coeff in self.coeffs.items():
            key = tuple(int(e) for e in exp)
            if len(key) != self.n_vars:
                raise ValueError(
                    f"exponent {key!r} has length {len(key)}, expected {self.n_vars}"
                )
            if any(e < 0 for e in key):
                raise ValueError(f"negative exponent in {key!r}")
            value = float(coeff)
            if value != 0.0:
                cleaned[key] = cleaned.get(key, 0.0) + value
        # Drop terms that cancelled to exactly zero.
        object.__setattr__(self, "coeffs", {k: v for k, v in cleaned.items() if v != 0.0})

View source ↗

zeromethod

zero(cls, n_vars: int) -> Polynomial

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.

Returns: Polynomial

Executed regression · zero and cancellation

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_zero_and_cancellation() -> None:
    x = Polynomial.variable(0, 1)
    assert (x - x).coeffs == {}
    assert (x - x).degree() == -1
    assert Polynomial.zero(3).evaluate([1.0, 2.0, 3.0]) == 0.0

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

Method implementation

    def zero(cls, n_vars: int) -> Polynomial:
        return cls(n_vars, {})

View source ↗

constantmethod

constant(cls, value: float, n_vars: int) -> Polynomial

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

Parameters

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

Returns: Polynomial

Executed regression · false statement is inconclusive

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_false_statement_is_inconclusive() -> None:
    # x - 5 <= -4 on [-1, 1]; must never be "proved".
    cert = certify_nonneg_on_set(X1 - 5.0 * ONE1, [ONE1 - X1 * X1])
    assert cert.status == "inconclusive"
    assert not cert.certified

python -m pytest "packages/omnibias-sos/tests/test_positivstellensatz.py::test_false_statement_is_inconclusive" -q

Method implementation

    def constant(cls, value: float, n_vars: int) -> Polynomial:
        return cls(n_vars, {(0,) * n_vars: value})

View source ↗

variablemethod

variable(cls, index: int, n_vars: int) -> Polynomial

The degree-1 monomial x_index.

Parameters

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

Returns: Polynomial

Executed regression · zero and cancellation

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_zero_and_cancellation() -> None:
    x = Polynomial.variable(0, 1)
    assert (x - x).coeffs == {}
    assert (x - x).degree() == -1
    assert Polynomial.zero(3).evaluate([1.0, 2.0, 3.0]) == 0.0

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

Method implementation

    def variable(cls, index: int, n_vars: int) -> Polynomial:
        r"""The degree-1 monomial ``x_index``."""
        exp = [0] * n_vars
        exp[index] = 1
        return cls(n_vars, {tuple(exp): 1.0})

View source ↗

monomialmethod

monomial(cls, exponent: Exponent, coefficient: float=1.0) -> Polynomial

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

Parameters

Name	Type & default	Contract
exponentpositional-or-keyword	ExponentRequired	See the operation contract and implementation below.
coefficientpositional-or-keyword	floatDefault: 1.0	See the operation contract and implementation below.

Returns: Polynomial

Executed regression · random csp degree certificate reports oracle

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_random_csp_degree_certificate_reports_oracle() -> None:
    cert = random_csp_degree_certificate(n=3, n_clauses=2, half_degree=1, seed=0)
    assert 0 <= cert.oracle_unsat <= cert.n_clauses
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_random_csp_degree_certificate_reports_oracle" -q

Method implementation

    def monomial(cls, exponent: Exponent, coefficient: float = 1.0) -> Polynomial:
        return cls(len(exponent), {tuple(exponent): coefficient})

View source ↗

supportproperty

support(self) -> frozenset[Exponent]

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

Returns: frozenset[Exponent]

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 support(self) -> frozenset[Exponent]:
        return frozenset(self.coeffs)

View source ↗

degreemethod

degree(self) -> int

Total degree (-1 for the zero polynomial).

Returns: 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

Method implementation

    def degree(self) -> int:
        """Total degree (``-1`` for the zero polynomial)."""
        return max((sum(exp) for exp in self.coeffs), default=-1)

View source ↗

coefficientmethod

coefficient(self, exponent: Exponent) -> float

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

Parameters

Name	Type & default	Contract
exponentpositional-or-keyword	ExponentRequired	See the operation contract and implementation below.

Returns: float

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 coefficient(self, exponent: Exponent) -> float:
        return self.coeffs.get(tuple(exponent), 0.0)

View source ↗

evaluatemethod

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

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

Parameters

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

Returns: float

Validation & failure cases

• When len(point) != self.n_vars, raises ValueError(f'point has length {len(point)}, expected {self.n_vars}').

Executed regression · zero and cancellation

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_zero_and_cancellation() -> None:
    x = Polynomial.variable(0, 1)
    assert (x - x).coeffs == {}
    assert (x - x).degree() == -1
    assert Polynomial.zero(3).evaluate([1.0, 2.0, 3.0]) == 0.0

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

Method implementation

    def evaluate(self, point: Sequence[float]) -> float:
        if len(point) != self.n_vars:
            raise ValueError(f"point has length {len(point)}, expected {self.n_vars}")
        total = 0.0
        for exp, coeff in self.coeffs.items():
            term = coeff
            for value, power in zip(point, exp, strict=True):
                if power:
                    term *= float(value) ** power
            total += term
        return total

View source ↗

partialmethod

partial(self, index: int) -> Polynomial

Partial derivative d/dx_index.

Parameters

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

Returns: Polynomial

Executed regression · partial and gradient

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_partial_and_gradient() -> None:
    x = Polynomial.variable(0, 2)
    y = Polynomial.variable(1, 2)
    p = x * x * y + y  # x^2 y + y
    dpx = p.partial(0)  # 2 x y
    dpy = p.partial(1)  # x^2 + 1
    assert dpx.coefficient((1, 1)) == 2.0
    assert dpy.coefficient((2, 0)) == 1.0
    assert dpy.coefficient((0, 0)) == 1.0
    grad = p.gradient()
    assert grad[0].coeffs == dpx.coeffs
    assert grad[1].coeffs == dpy.coeffs

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

Method implementation

    def partial(self, index: int) -> Polynomial:
        r"""Partial derivative ``d/dx_index``."""
        out: dict[Exponent, float] = {}
        for exp, coeff in self.coeffs.items():
            power = exp[index]
            if power == 0:
                continue
            lowered = list(exp)
            lowered[index] = power - 1
            key = tuple(lowered)
            out[key] = out.get(key, 0.0) + coeff * power
        return Polynomial(self.n_vars, out)

View source ↗

gradientmethod

gradient(self) -> tuple[Polynomial, ...]

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

Returns: tuple[Polynomial, ...]

Executed regression · partial and gradient

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_partial_and_gradient() -> None:
    x = Polynomial.variable(0, 2)
    y = Polynomial.variable(1, 2)
    p = x * x * y + y  # x^2 y + y
    dpx = p.partial(0)  # 2 x y
    dpy = p.partial(1)  # x^2 + 1
    assert dpx.coefficient((1, 1)) == 2.0
    assert dpy.coefficient((2, 0)) == 1.0
    assert dpy.coefficient((0, 0)) == 1.0
    grad = p.gradient()
    assert grad[0].coeffs == dpx.coeffs
    assert grad[1].coeffs == dpy.coeffs

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

Method implementation

    def gradient(self) -> tuple[Polynomial, ...]:
        return tuple(self.partial(i) for i in range(self.n_vars))

View source ↗

__add__method

__add__(self, other: Polynomial | float) -> Polynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	Polynomial | floatRequired	See the operation contract and implementation below.

Returns: Polynomial

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 __add__(self, other: Polynomial | float) -> Polynomial:
        if isinstance(other, Polynomial):
            self._check_same_arity(other)
            out = dict(self.coeffs)
            for exp, coeff in other.coeffs.items():
                out[exp] = out.get(exp, 0.0) + coeff
            return Polynomial(self.n_vars, out)
        return self + Polynomial.constant(float(other), self.n_vars)

View source ↗

__neg__method

__neg__(self) -> Polynomial

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

Returns: Polynomial

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 __neg__(self) -> Polynomial:
        return Polynomial(self.n_vars, {exp: -coeff for exp, coeff in self.coeffs.items()})

View source ↗

__sub__method

__sub__(self, other: Polynomial | float) -> Polynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	Polynomial | floatRequired	See the operation contract and implementation below.

Returns: Polynomial

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 __sub__(self, other: Polynomial | float) -> Polynomial:
        return self + (-other if isinstance(other, Polynomial) else -float(other))

View source ↗

__rsub__method

__rsub__(self, other: float) -> Polynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	floatRequired	See the operation contract and implementation below.

Returns: Polynomial

Method implementation

    def __rsub__(self, other: float) -> Polynomial:
        return Polynomial.constant(float(other), self.n_vars) - self

View source ↗

__mul__method

__mul__(self, other: Polynomial | float) -> Polynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	Polynomial | floatRequired	See the operation contract and implementation below.

Returns: Polynomial

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 __mul__(self, other: Polynomial | float) -> Polynomial:
        if isinstance(other, Polynomial):
            self._check_same_arity(other)
            out: dict[Exponent, float] = {}
            for exp_a, coeff_a in self.coeffs.items():
                for exp_b, coeff_b in other.coeffs.items():
                    key = tuple(a + b for a, b in zip(exp_a, exp_b, strict=True))
                    out[key] = out.get(key, 0.0) + coeff_a * coeff_b
            return Polynomial(self.n_vars, out)
        return Polynomial(
            self.n_vars, {exp: coeff * float(other) for exp, coeff in self.coeffs.items()}
        )

View source ↗

__repr__method

__repr__(self) -> str

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

Returns: str

Method implementation

    def __repr__(self) -> str:
        if not self.coeffs:
            return f"Polynomial(n_vars={self.n_vars}, 0)"
        terms = ", ".join(
            f"{exp}:{coeff:g}" for exp, coeff in sorted(self.coeffs.items())
        )
        return f"Polynomial(n_vars={self.n_vars}, {{{terms}}})"

View source ↗

Read the implementation

class Polynomial:
    """A sparse multivariate polynomial with real (float) coefficients.

    Parameters
    ----------
    n_vars:
        Number of variables.
    coeffs:
        Mapping from exponent multi-index (length ``n_vars``) to coefficient.
        Zero coefficients and duplicate keys are normalised away on construction.
    """

    n_vars: int
    coeffs: Mapping[Exponent, float]

    def __post_init__(self) -> None:
        cleaned: dict[Exponent, float] = {}
        for exp, coeff in self.coeffs.items():
            key = tuple(int(e) for e in exp)
            if len(key) != self.n_vars:
                raise ValueError(
                    f"exponent {key!r} has length {len(key)}, expected {self.n_vars}"
                )
            if any(e < 0 for e in key):
                raise ValueError(f"negative exponent in {key!r}")
            value = float(coeff)
            if value != 0.0:
                cleaned[key] = cleaned.get(key, 0.0) + value
        # Drop terms that cancelled to exactly zero.
        object.__setattr__(self, "coeffs", {k: v for k, v in cleaned.items() if v != 0.0})

    # -- constructors ------------------------------------------------------- #

    @classmethod
    def zero(cls, n_vars: int) -> Polynomial:
        return cls(n_vars, {})

    @classmethod
    def constant(cls, value: float, n_vars: int) -> Polynomial:
        return cls(n_vars, {(0,) * n_vars: value})

    @classmethod
    def variable(cls, index: int, n_vars: int) -> Polynomial:
        r"""The degree-1 monomial ``x_index``."""
        exp = [0] * n_vars
        exp[index] = 1
        return cls(n_vars, {tuple(exp): 1.0})

    @classmethod
    def monomial(cls, exponent: Exponent, coefficient: float = 1.0) -> Polynomial:
        return cls(len(exponent), {tuple(exponent): coefficient})

    # -- structure ---------------------------------------------------------- #

    @property
    def support(self) -> frozenset[Exponent]:
        return frozenset(self.coeffs)

    def degree(self) -> int:
        """Total degree (``-1`` for the zero polynomial)."""
        return max((sum(exp) for exp in self.coeffs), default=-1)

    def coefficient(self, exponent: Exponent) -> float:
        return self.coeffs.get(tuple(exponent), 0.0)

    # -- evaluation & calculus ---------------------------------------------- #

    def evaluate(self, point: Sequence[float]) -> float:
        if len(point) != self.n_vars:
            raise ValueError(f"point has length {len(point)}, expected {self.n_vars}")
        total = 0.0
        for exp, coeff in self.coeffs.items():
            term = coeff
            for value, power in zip(point, exp, strict=True):
                if power:
                    term *= float(value) ** power
            total += term
        return total

    def partial(self, index: int) -> Polynomial:
        r"""Partial derivative ``d/dx_index``."""
        out: dict[Exponent, float] = {}
        for exp, coeff in self.coeffs.items():
            power = exp[index]
            if power == 0:
                continue
            lowered = list(exp)
            lowered[index] = power - 1
            key = tuple(lowered)
            out[key] = out.get(key, 0.0) + coeff * power
        return Polynomial(self.n_vars, out)

    def gradient(self) -> tuple[Polynomial, ...]:
        return tuple(self.partial(i) for i in range(self.n_vars))

    # -- algebra ------------------------------------------------------------ #

    def __add__(self, other: Polynomial | float) -> Polynomial:
        if isinstance(other, Polynomial):
            self._check_same_arity(other)
            out = dict(self.coeffs)
            for exp, coeff in other.coeffs.items():
                out[exp] = out.get(exp, 0.0) + coeff
            return Polynomial(self.n_vars, out)
        return self + Polynomial.constant(float(other), self.n_vars)

    __radd__ = __add__

    def __neg__(self) -> Polynomial:
        return Polynomial(self.n_vars, {exp: -coeff for exp, coeff in self.coeffs.items()})

    def __sub__(self, other: Polynomial | float) -> Polynomial:
        return self + (-other if isinstance(other, Polynomial) else -float(other))

    def __rsub__(self, other: float) -> Polynomial:
        return Polynomial.constant(float(other), self.n_vars) - self

    def __mul__(self, other: Polynomial | float) -> Polynomial:
        if isinstance(other, Polynomial):
            self._check_same_arity(other)
            out: dict[Exponent, float] = {}
            for exp_a, coeff_a in self.coeffs.items():
                for exp_b, coeff_b in other.coeffs.items():
                    key = tuple(a + b for a, b in zip(exp_a, exp_b, strict=True))
                    out[key] = out.get(key, 0.0) + coeff_a * coeff_b
            return Polynomial(self.n_vars, out)
        return Polynomial(
            self.n_vars, {exp: coeff * float(other) for exp, coeff in self.coeffs.items()}
        )

    __rmul__ = __mul__

    def _check_same_arity(self, other: Polynomial) -> None:
        if self.n_vars != other.n_vars:
            raise ValueError(
                f"arity mismatch: {self.n_vars} vs {other.n_vars} variables"
            )

    def __repr__(self) -> str:
        if not self.coeffs:
            return f"Polynomial(n_vars={self.n_vars}, 0)"
        terms = ", ".join(
            f"{exp}:{coeff:g}" for exp, coeff in sorted(self.coeffs.items())
        )
        return f"Polynomial(n_vars={self.n_vars}, {{{terms}}})"

Other public import paths

• omnibias.sos.Polynomial
• omnibias.sos.problem.Polynomial

CLASS

RationalPolynomial

omnibias.sos.RationalPolynomialSource ↗

class RationalPolynomial

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.

A multivariate polynomial with **exact** ~fractions.Fraction coefficients.

The auxiliary-functional residual C - Phi - grad(V) . f must be formed exactly: float polynomial arithmetic rounds (products of dyadic rationals can overflow the 53-bit mantissa), which would make the certified inequality about a slightly different polynomial than intended. This type keeps every coefficient exact so the sealed bound is sound to the last bit. It exposes the same coefficient / support surface as Polynomial, so the rational rounding and certifier accept it directly.

Parameters

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

Fields & methods

n_varsfield

n_vars: int

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

View source ↗

coeffsfield

coeffs: Mapping[Exponent, Fraction]

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

View source ↗

__post_init__method

__post_init__(self) -> None

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

Returns: None

Validation & failure cases

• When len(key) != self.n_vars, raises ValueError(f'exponent {key!r} has length {len(key)}, expected {self.n_vars}').

Method implementation

    def __post_init__(self) -> None:
        cleaned: dict[Exponent, Fraction] = {}
        for exp, coeff in self.coeffs.items():
            key = tuple(int(e) for e in exp)
            if len(key) != self.n_vars:
                raise ValueError(f"exponent {key!r} has length {len(key)}, expected {self.n_vars}")
            value = cleaned.get(key, Fraction(0)) + Fraction(coeff)
            cleaned[key] = value
        object.__setattr__(self, "coeffs", {k: v for k, v in cleaned.items() if v != 0})

View source ↗

zeromethod

zero(cls, n_vars: int) -> RationalPolynomial

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.

Returns: RationalPolynomial

Method implementation

    def zero(cls, n_vars: int) -> RationalPolynomial:
        return cls(n_vars, {})

View source ↗

constantmethod

constant(cls, value: Fraction | int, n_vars: int) -> RationalPolynomial

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

Parameters

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

Returns: RationalPolynomial

Method implementation

    def constant(cls, value: Fraction | int, n_vars: int) -> RationalPolynomial:
        return cls(n_vars, {(0,) * n_vars: Fraction(value)})

View source ↗

from_polynomialmethod

from_polynomial(cls, polynomial: Polynomial) -> RationalPolynomial

Exact lift of a float Polynomial (each float is its dyadic rational).

Parameters

Name	Type & default	Contract
polynomialpositional-or-keyword	PolynomialRequired	See the operation contract and implementation below.

Returns: RationalPolynomial

Method implementation

    def from_polynomial(cls, polynomial: Polynomial) -> RationalPolynomial:
        """Exact lift of a float :class:`Polynomial` (each float is its dyadic rational)."""
        return cls(polynomial.n_vars, {exp: Fraction(c) for exp, c in polynomial.coeffs.items()})

View source ↗

supportproperty

support(self) -> frozenset[Exponent]

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

Returns: frozenset[Exponent]

Method implementation

    def support(self) -> frozenset[Exponent]:
        return frozenset(self.coeffs)

View source ↗

degreemethod

degree(self) -> int

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

Returns: int

Method implementation

    def degree(self) -> int:
        return max((sum(exp) for exp in self.coeffs), default=-1)

View source ↗

coefficientmethod

coefficient(self, exponent: Exponent) -> Fraction

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

Parameters

Name	Type & default	Contract
exponentpositional-or-keyword	ExponentRequired	See the operation contract and implementation below.

Returns: Fraction

Method implementation

    def coefficient(self, exponent: Exponent) -> Fraction:
        return self.coeffs.get(tuple(exponent), Fraction(0))

View source ↗

to_floatmethod

to_float(self) -> Polynomial

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

Returns: Polynomial

Method implementation

    def to_float(self) -> Polynomial:
        return Polynomial(self.n_vars, {exp: float(c) for exp, c in self.coeffs.items()})

View source ↗

partialmethod

partial(self, index: int) -> RationalPolynomial

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

Parameters

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

Returns: RationalPolynomial

Method implementation

    def partial(self, index: int) -> RationalPolynomial:
        out: dict[Exponent, Fraction] = {}
        for exp, coeff in self.coeffs.items():
            power = exp[index]
            if power == 0:
                continue
            lowered = list(exp)
            lowered[index] = power - 1
            key = tuple(lowered)
            out[key] = out.get(key, Fraction(0)) + coeff * power
        return RationalPolynomial(self.n_vars, out)

View source ↗

__add__method

__add__(self, other: RationalPolynomial) -> RationalPolynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	RationalPolynomialRequired	See the operation contract and implementation below.

Returns: RationalPolynomial

Validation & failure cases

• When self.n_vars != other.n_vars, raises ValueError(f'arity mismatch: {self.n_vars} vs {other.n_vars} variables').

Method implementation

    def __add__(self, other: RationalPolynomial) -> RationalPolynomial:
        if self.n_vars != other.n_vars:
            raise ValueError(f"arity mismatch: {self.n_vars} vs {other.n_vars} variables")
        out = dict(self.coeffs)
        for exp, coeff in other.coeffs.items():
            out[exp] = out.get(exp, Fraction(0)) + coeff
        return RationalPolynomial(self.n_vars, out)

View source ↗

__neg__method

__neg__(self) -> RationalPolynomial

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

Returns: RationalPolynomial

Method implementation

    def __neg__(self) -> RationalPolynomial:
        return RationalPolynomial(self.n_vars, {exp: -c for exp, c in self.coeffs.items()})

View source ↗

__sub__method

__sub__(self, other: RationalPolynomial) -> RationalPolynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	RationalPolynomialRequired	See the operation contract and implementation below.

Returns: RationalPolynomial

Method implementation

    def __sub__(self, other: RationalPolynomial) -> RationalPolynomial:
        return self + (-other)

View source ↗

__mul__method

__mul__(self, other: RationalPolynomial | Fraction | int) -> RationalPolynomial

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

Parameters

Name	Type & default	Contract
otherpositional-or-keyword	RationalPolynomial | Fraction | intRequired	See the operation contract and implementation below.

Returns: RationalPolynomial

Validation & failure cases

• When self.n_vars != other.n_vars, raises ValueError(f'arity mismatch: {self.n_vars} vs {other.n_vars} variables').

Method implementation

    def __mul__(self, other: RationalPolynomial | Fraction | int) -> RationalPolynomial:
        if isinstance(other, RationalPolynomial):
            if self.n_vars != other.n_vars:
                raise ValueError(f"arity mismatch: {self.n_vars} vs {other.n_vars} variables")
            out: dict[Exponent, Fraction] = {}
            for exp_a, coeff_a in self.coeffs.items():
                for exp_b, coeff_b in other.coeffs.items():
                    key = tuple(a + b for a, b in zip(exp_a, exp_b, strict=True))
                    out[key] = out.get(key, Fraction(0)) + coeff_a * coeff_b
            return RationalPolynomial(self.n_vars, out)
        scalar = Fraction(other)
        return RationalPolynomial(self.n_vars, {exp: c * scalar for exp, c in self.coeffs.items()})

View source ↗

Read the implementation

class RationalPolynomial:
    r"""A multivariate polynomial with **exact** :class:`~fractions.Fraction` coefficients.

    The auxiliary-functional residual ``C - Phi - grad(V) . f`` must be formed
    exactly: float polynomial arithmetic rounds (products of dyadic rationals can
    overflow the 53-bit mantissa), which would make the certified inequality about
    a slightly different polynomial than intended.  This type keeps every
    coefficient exact so the sealed bound is sound to the last bit.  It exposes the
    same ``coefficient`` / ``support`` surface as :class:`Polynomial`, so the
    rational rounding and certifier accept it directly.
    """

    n_vars: int
    coeffs: Mapping[Exponent, Fraction]

    def __post_init__(self) -> None:
        cleaned: dict[Exponent, Fraction] = {}
        for exp, coeff in self.coeffs.items():
            key = tuple(int(e) for e in exp)
            if len(key) != self.n_vars:
                raise ValueError(f"exponent {key!r} has length {len(key)}, expected {self.n_vars}")
            value = cleaned.get(key, Fraction(0)) + Fraction(coeff)
            cleaned[key] = value
        object.__setattr__(self, "coeffs", {k: v for k, v in cleaned.items() if v != 0})

    @classmethod
    def zero(cls, n_vars: int) -> RationalPolynomial:
        return cls(n_vars, {})

    @classmethod
    def constant(cls, value: Fraction | int, n_vars: int) -> RationalPolynomial:
        return cls(n_vars, {(0,) * n_vars: Fraction(value)})

    @classmethod
    def from_polynomial(cls, polynomial: Polynomial) -> RationalPolynomial:
        """Exact lift of a float :class:`Polynomial` (each float is its dyadic rational)."""
        return cls(polynomial.n_vars, {exp: Fraction(c) for exp, c in polynomial.coeffs.items()})

    @property
    def support(self) -> frozenset[Exponent]:
        return frozenset(self.coeffs)

    def degree(self) -> int:
        return max((sum(exp) for exp in self.coeffs), default=-1)

    def coefficient(self, exponent: Exponent) -> Fraction:
        return self.coeffs.get(tuple(exponent), Fraction(0))

    def to_float(self) -> Polynomial:
        return Polynomial(self.n_vars, {exp: float(c) for exp, c in self.coeffs.items()})

    def partial(self, index: int) -> RationalPolynomial:
        out: dict[Exponent, Fraction] = {}
        for exp, coeff in self.coeffs.items():
            power = exp[index]
            if power == 0:
                continue
            lowered = list(exp)
            lowered[index] = power - 1
            key = tuple(lowered)
            out[key] = out.get(key, Fraction(0)) + coeff * power
        return RationalPolynomial(self.n_vars, out)

    def __add__(self, other: RationalPolynomial) -> RationalPolynomial:
        if self.n_vars != other.n_vars:
            raise ValueError(f"arity mismatch: {self.n_vars} vs {other.n_vars} variables")
        out = dict(self.coeffs)
        for exp, coeff in other.coeffs.items():
            out[exp] = out.get(exp, Fraction(0)) + coeff
        return RationalPolynomial(self.n_vars, out)

    def __neg__(self) -> RationalPolynomial:
        return RationalPolynomial(self.n_vars, {exp: -c for exp, c in self.coeffs.items()})

    def __sub__(self, other: RationalPolynomial) -> RationalPolynomial:
        return self + (-other)

    def __mul__(self, other: RationalPolynomial | Fraction | int) -> RationalPolynomial:
        if isinstance(other, RationalPolynomial):
            if self.n_vars != other.n_vars:
                raise ValueError(f"arity mismatch: {self.n_vars} vs {other.n_vars} variables")
            out: dict[Exponent, Fraction] = {}
            for exp_a, coeff_a in self.coeffs.items():
                for exp_b, coeff_b in other.coeffs.items():
                    key = tuple(a + b for a, b in zip(exp_a, exp_b, strict=True))
                    out[key] = out.get(key, Fraction(0)) + coeff_a * coeff_b
            return RationalPolynomial(self.n_vars, out)
        scalar = Fraction(other)
        return RationalPolynomial(self.n_vars, {exp: c * scalar for exp, c in self.coeffs.items()})

    __rmul__ = __mul__

Related APIsomnibias.sos.Polynomial↗

Other public import paths

• omnibias.sos.RationalPolynomial
• omnibias.sos.problem.RationalPolynomial

CLASS

SOSCertificate

omnibias.sos.SOSCertificateSource ↗

class SOSCertificate

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.

Result of an SOS certification attempt.

A status == "proved" certificate carries a rational Gram matrix whose outward-rounded interval LDL^T pivots are all strictly positive, so p(x) = z(x)^T Q z(x) >= 0 for **all** x. A status == "inconclusive" certificate makes **no** positivity claim -- the SDP was infeasible, the rational rounding failed, or the positive-definite margin was not met.

Attributes

status: "proved" or "inconclusive". n_vars: Number of variables of the certified polynomial. basis: The monomial-basis exponents z(x) used for the Gram matrix. gram: The rational Gram matrix Q (as strings, exact) that matches the polynomial coefficients exactly, or None when inconclusive. pivots: The interval LDL^T pivots (lo, hi) of Q; every lo > 0 on a proved certificate. pd_margin: min_j pivot_j.lo -- the certified positive-definiteness margin (> 0 iff proved). coeff_residual: Max absolute polynomial-coefficient mismatch after exact rational rounding (0 on a proved certificate; the rounding is exact). detail: Human-readable explanation, especially of an inconclusive verdict.

Parameters

Name	Type & default	Contract
statusdataclass field	strRequired	"proved" or "inconclusive".
n_varsdataclass field	intRequired	Number of variables of the certified polynomial.
basisdataclass field	tuple[Exponent, ...]Required	The monomial-basis exponents z(x) used for the Gram matrix.
gramdataclass field	tuple[tuple[str, ...], ...] | NoneRequired	The rational Gram matrix Q (as strings, exact) that matches the polynomial coefficients exactly, or None when inconclusive.
pivotsdataclass field	tuple[tuple[float, float], ...]Required	The interval LDL^T pivots (lo, hi) of Q; every lo > 0 on a proved certificate.
pd_margindataclass field	floatRequired	min_j pivot_j.lo -- the certified positive-definiteness margin (> 0 iff proved).
coeff_residualdataclass field	floatRequired	Max absolute polynomial-coefficient mismatch after exact rational rounding (0 on a proved certificate; the rounding is exact).
detaildataclass field	strRequired	Human-readable explanation, especially of an inconclusive verdict.

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

Fields & methods

statusfield

status: str

"proved" or "inconclusive".

View source ↗

n_varsfield

n_vars: int

Number of variables of the certified polynomial.

View source ↗

basisfield

basis: tuple[Exponent, ...]

The monomial-basis exponents z(x) used for the Gram matrix.

View source ↗

gramfield

gram: tuple[tuple[str, ...], ...] | None

The rational Gram matrix Q (as strings, exact) that matches the polynomial coefficients exactly, or None when inconclusive.

View source ↗

pivotsfield

pivots: tuple[tuple[float, float], ...]

The interval LDL^T pivots (lo, hi) of Q; every lo > 0 on a proved certificate.

View source ↗

pd_marginfield

pd_margin: float

min_j pivot_j.lo -- the certified positive-definiteness margin (> 0 iff proved).

View source ↗

coeff_residualfield

coeff_residual: float

Max absolute polynomial-coefficient mismatch after exact rational rounding (0 on a proved certificate; the rounding is exact).

View source ↗

detailfield

detail: str

Human-readable explanation, especially of an inconclusive verdict.

View source ↗

certifiedproperty

certified(self) -> bool

Whether this is a sound proof of global nonnegativity.

Returns: bool

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 certified(self) -> bool:
        """Whether this is a sound proof of global nonnegativity."""
        return self.status == "proved"

View source ↗

Read the implementation

class SOSCertificate:
    r"""Result of an SOS certification attempt.

    A ``status == "proved"`` certificate carries a rational Gram matrix whose
    outward-rounded interval ``LDL^T`` pivots are all strictly positive, so
    ``p(x) = z(x)^T Q z(x) >= 0`` for **all** ``x``.  A ``status ==
    "inconclusive"`` certificate makes **no** positivity claim -- the SDP was
    infeasible, the rational rounding failed, or the positive-definite margin was
    not met.

    Attributes
    ----------
    status:
        ``"proved"`` or ``"inconclusive"``.
    n_vars:
        Number of variables of the certified polynomial.
    basis:
        The monomial-basis exponents ``z(x)`` used for the Gram matrix.
    gram:
        The rational Gram matrix ``Q`` (as strings, exact) that matches the
        polynomial coefficients exactly, or ``None`` when inconclusive.
    pivots:
        The interval ``LDL^T`` pivots ``(lo, hi)`` of ``Q``; every ``lo > 0`` on a
        proved certificate.
    pd_margin:
        ``min_j pivot_j.lo`` -- the certified positive-definiteness margin
        (``> 0`` iff proved).
    coeff_residual:
        Max absolute polynomial-coefficient mismatch after exact rational
        rounding (``0`` on a proved certificate; the rounding is exact).
    detail:
        Human-readable explanation, especially of an inconclusive verdict.
    """

    status: str
    n_vars: int
    basis: tuple[Exponent, ...]
    gram: tuple[tuple[str, ...], ...] | None
    pivots: tuple[tuple[float, float], ...]
    pd_margin: float
    coeff_residual: float
    detail: str

    @property
    def certified(self) -> bool:
        """Whether this is a sound proof of global nonnegativity."""
        return self.status == "proved"

Other public import paths

• omnibias.sos.SOSCertificate
• omnibias.sos.problem.SOSCertificate

← Package overviewRunnable learning examples →