# Certification

We provide support for certifying non-singular solutions to polynomial systems. The details of the implementation described in the article

Breiding, P., Rose, K. and Timme, S. "Certifying zeros of polynomial systems using interval arithmetic." arXiv:2011.05000

## Certify

`HomotopyContinuation.certify`

— Function```
certify(F, solutions, [p, certify_cache]; options...)
certify(F, result, [p, certify_cache]; options...)
```

Attempt to certify that the given approximate `solutions`

correspond to true solutions of the polynomial system $F(x;p)$. The system $F$ has to be an (affine) square polynomial system. Also attemps to certify for each solutions whether it approximates a real solution. The certification is done using interval arithmetic and the Krawczyk method^{[Moo77]}. Returns a `CertificationResult`

which additionall returns the number of distinct solutions. For more details of the implementation see ^{[BRT20]}.

**Options**

`show_progress = true`

: If`true`

shows a progress bar of the certification process.`max_precision = 256`

: The maximal accuracy (in bits) that is used in the certification process.`compile = false`

: See the`solve`

documentation.

**Example**

We take the first example from our introduction guide.

```
@var x y
# define the polynomials
f₁ = (x^4 + y^4 - 1) * (x^2 + y^2 - 2) + x^5 * y
f₂ = x^2+2x*y^2 - 2y^2 - 1/2
F = System([f₁, f₂], variables = [x,y])
result = solve(F)
```

```
Result with 18 solutions
========================
• 18 paths tracked
• 18 non-singular solutions (4 real)
• random seed: 0xcaa483cd
• start_system: :polyhedral
```

We see that we obtain 18 solutions and it seems that 4 solutions are real. However, this is based on heuristics. To be absolute certain we can certify the result

`certify(F, result)`

```
CertificationResult
===================
• 18 solution candidates given
• 18 certified solution intervals (4 real, 14 complex)
• 18 distinct certified solution intervals (4 real, 14 complex)
```

and see that there are indeed 18 solutions and that they are all distinct.

## CertificationResult

The result of `certify`

is a `CertificationResult`

:

`HomotopyContinuation.CertificationResult`

— Type`CertificationResult`

The result of `certify`

for multiple solutions. Contains a vector of `SolutionCertificate`

as well as a list of certificates which correspond to the same true solution.

`HomotopyContinuation.certificates`

— Function`certificates(R::CertificationResult)`

Obtain the stored `SolutionCertificate`

s.

`certificates(d::DistinctCertifiedSolutions)`

Return a vector of solution certificates in the DistinctSolutionCertificates object.

`HomotopyContinuation.distinct_certificates`

— Function`distinct_certificates(R::CertificationResult)`

Obtain the certificates corresponding to the determined distinct solution intervals.

`HomotopyContinuation.ncertified`

— Function`ncertified(R::CertificationResult)`

Returns the number of certified solutions.

`HomotopyContinuation.nreal_certified`

— Function`nreal_certified(R::CertificationResult)`

Returns the number of certified real solutions.

`HomotopyContinuation.ncomplex_certified`

— Function`ncomplex_certified(R::CertificationResult)`

Returns the number of certified complex solutions.

`HomotopyContinuation.ndistinct_certified`

— Function`ndistinct_certified(R::CertificationResult)`

Returns the number of distinct certified solutions.

`HomotopyContinuation.ndistinct_real_certified`

— Function`ndistinct_real_certified(R::CertificationResult)`

Returns the number of distinct certified real solutions.

`HomotopyContinuation.ndistinct_complex_certified`

— Function`ndistinct_complex_certified(R::CertificationResult)`

Returns the number of distinct certified complex solutions.

`HomotopyContinuation.save`

— Method`save(filename, C::CertificationResult)`

Store a text representation of the certification result `C`

on disk.

`HomotopyContinuation.show_straight_line_program`

— Function```
show_straight_line_program(R::CertificationResult)
show_straight_line_program(io::IO, R::CertificationResult)
```

Print a representation of the used straight line program.

## SolutionCertificate

A `CertificationResult`

contains in particular all `SolutionCertificate`

s:

`HomotopyContinuation.SolutionCertificate`

— Type`SolutionCertificate`

Result of `certify`

for a single solution. Contains the initial solutions and if the certification was successfull a vector of complex intervals where the true solution is contained in.

`HomotopyContinuation.is_certified`

— Function`is_certified(certificate::AbstractSolutionCertificate)`

Returns `true`

if `certificate`

is a certificate that `certified_solution_interval(certificate)`

contains a unique zero.

`HomotopyContinuation.is_real`

— Method`is_real(certificate::AbstractSolutionCertificate)`

Returns `true`

if `certificate`

certifies that the certified solution interval contains a true real zero of the system. If `false`

is returned then this does not necessarily mean that the true solution is not real.

`HomotopyContinuation.is_complex`

— Method`is_complex(certificate::AbstractSolutionCertificate)`

Returns `true`

if `certificate`

certifies that the certified solution interval contains a non-real complex zero of the system.

`HomotopyContinuation.is_positive`

— Method`is_positive(certificate::AbstractSolutionCertificate)`

Returns `true`

if `is_certified(certificate)`

is `true`

and the unique zero contained in `certified_solution_interval(certificate)`

is real and positive.

`HomotopyContinuation.solution_candidate`

— Function`solution_candidate(certificate::AbstractSolutionCertificate)`

Returns the given provided solution candidate.

`HomotopyContinuation.certified_solution_interval`

— Function`certified_solution_interval(certificate::AbstractSolutionCertificate)`

Returns an `Arblib.AcbMatrix`

representing a vector of complex intervals where a unique zero of the system is contained in. Returns `nothing`

if `is_certified(certificate)`

is `false`

.

`HomotopyContinuation.certified_solution_interval_after_krawczyk`

— Function`certified_solution_interval_after_krawczyk(certificate::ExtendedSolutionCertificate)`

Returns an `Arblib.AcbMatrix`

representing a vector of complex intervals where a unique zero of the system is contained in. This is the result of applying the Krawczyk operator to `certified_solution_interval(certificate)`

. Returns `nothing`

if `is_certified(certificate)`

is `false`

.

`HomotopyContinuation.certificate_index`

— Function`certificate_index(certificate::AbstractSolutionCertificate)`

Return the index of the solution certificate. Here the index refers to the index of the provided solution candidates.

`HomotopyContinuation.solution_approximation`

— Function`solution_approximation(certificate::AbstractSolutionCertificate)`

If `is_certified(certificate)`

is `true`

this returns the midpoint of the `certified_solution_interval`

of the given `certificate`

as a `Vector{ComplexF64}`

. Returns `nothing`

if `is_certified(certificate)`

is `false`

.