# Witness Sets

A `WitnessSet`

$W$ is the basic data structure to work with positive dimensional solution sets $V(F)$ of a polynomial system $F$. The general idea is to intersect $V(F)$ with an (affine) linear space $L$ such that the intersection $V(F) ∩ L$ consists of only finitely many points (witnesses). Over the complex numbers the number of points is independent of the linear space $L$ and called the *degree* of $V(F)$.

`HomotopyContinuation.WitnessSet`

— Type`WitnessSet(F, L, S)`

Store solutions `S`

of the polynomial system `F(x) = L(x) = 0`

into a witness set.

To compute a `WitnessSet`

call `witness_set`

.

`HomotopyContinuation.witness_set`

— Function`witness_set(F; codim = nvariables(F) - length(F), dim = nothing, options...)`

Compute a `WitnessSet`

for `F`

in the given dimension (resp. codimension) by sampling a random (affine) linear subspace. After constructing the system this calls `solve`

with the provided `options`

.

`witness_set(F, L; options...)`

Compute `WitnessSet`

for `F`

and the (affine) linear subspace `L`

.

`witness_set(W::WitnessSet, L; options...)`

Compute a new `WitnessSet`

with the (affine) linear subspace `L`

by moving the linear subspace stored in `W`

to `L`

.

**Example**

```
julia> @var x y;
julia> F = System([x^2 + y^2 - 5], [x, y])
System of length 1
2 variables: x, y
-5 + x^2 + y^2
julia> W = witness_set(F)
Witness set for dimension 1 of degree 2
```

To obtain information about a `WitnessSet`

the following functions are provided.

`HomotopyContinuation.solutions`

— Method`solutions(W::WitnessSet)`

Get the solutions stored in `W`

.

`HomotopyContinuation.results`

— Method`results(W::WitnessSet)`

Get the results stored in `W`

.

`HomotopyContinuation.system`

— Function`system(W::WitnessSet)`

Get the system stored in `W`

.

`HomotopyContinuation.linear_subspace`

— Function`linear_subspace(W::WitnessSet)`

Get the linear subspace stored in `W`

.

`HomotopyContinuation.dim`

— Method`dim(W::WitnessSet)`

The dimension of the algebraic set encoded by the witness set.

`HomotopyContinuation.codim`

— Method`codim(W::WitnessSet)`

The dimension of the algebraic set encoded by the witness set.

`MultivariatePolynomials.degree`

— Method`degree(W::WitnessSet)`

Returns the degree of the witness set `W`

. This equals the number of solutions stored.

To test for completeness of a `WitnessSet`

you can perform a `trace_test`

`HomotopyContinuation.trace_test`

— Function`trace_test(W::WitnessSet; options...)`

Performs a trace test ^{[LRS18]} to verify whether the given witness set `W`

is complete. Returns the trace of the witness set which should be theoretically be 0 if `W`

is complete. Due to floating point arithmetic this is not the case, thus is has to be manually checked that the trace is sufficiently small. Returns `nothing`

if the trace test failed due to path tracking failures. The `options`

are the same as for calls to `witness_set`

.

```
julia> @var x y;
julia> F = System([x^2 + y^2 - 5], [x, y])
System of length 1
2 variables: x, y
-5 + x^2 + y^2
julia> W = witness_set(F)
Witness set for dimension 1 of degree 2
julia> trace = trace_test(W)
9.981960497718987e-16
```

APA

- LRS18Leykin, Anton, Jose Israel Rodriguez, and Frank Sottile. "Trace test." Arnold Mathematical Journal 4.1 (2018): 113-125.