Distinguish the notion of multi-index set completeness and downward-closedness

The notions of completeness and downward-closedness appear in the code but have never been clearly distinguished. This issue is to pick up the point raised in #81 (closed) and focus on these two notions and their relation with the code.

Let's recall some basic definitions.

Downward-closedness

The downward-closedness property of a multi-index set is commonly referred to in the Minterpy papers; it is also the requirement for the multi-dimensional DDS to work.

There are several ways to define downward-closedness, I usually define it as follows...

Let \mathcal{A} be a multi-index set. The downward neighbors \mathcal{A}^- of \mathcal{A} is defined as follows:

\mathcal{A}^- \equiv \{ \boldsymbol{\alpha} - \boldsymbol{e}_m : \boldsymbol{\alpha} \in \mathcal{A}, m = 1, \ldots M, \alpha_m > 0 \}

where \boldsymbol{e}_m is the m-th unit vector. The elements of downward neighbors \mathcal{A}^- may or may not be included in the multi-index set \mathcal{A}.

A multi-index set is downward-closed if and only if all the downward neighbors of the set are included in the set

\mathcal{A}^- \subset \mathcal{A}.

Completeness

The notion of completeness of a multi-index set has never actually been referred to in any of the Minterpy papers. However, its definition is implied in the code.

Let \mathcal{A} be a multi-index set. \mathcal{A} is said to be complete with respect to an lp-degree l_p and a polynomial degree n if and only if it contains all the elements that satisfy the condition \lVert \boldsymbol{\alpha} \rVert_{l_p} \leq n, where \lVert \cdot \rVert_{l_p} indicates the l_p-norm.

Downward-closedness vs completeness

Here are some basic differences between the two notions and their relation with the code:

• A downward-closed multi-index set may or may not be complete, but a complete multi-index set is always downward-closed as well.
• The definition of completeness requires the specification of both l_p-degree and the polynomial degree; in other words, completeness can only be defined (and verified) with respect to those parameters. On the other hand, downward-closedness does not require them and can be verified without any reference to those parameters. The is_lexicographically_complete() function checks whether a multi-index set has "holes" in it, no need for lp-degree or poly. degree.
• DDS requires the multi-index set that defines a polynomial to be downward-closed but not complete per se.
• the get_exponent_matrix() used by the from_degree() constructor of the MultiIndexSet class creates, by construction, a complete multi-index set. There is no way to specifically create a particular downward-closed multi-index set of a given spatial dimension; such operation is most probably not meaningful anyway.

As an illustration, the multi-index set

MultiIndexSet
[[0 0]
 [1 0]
 [2 0]
 [0 1]]

is downward-closed (there are no "holes" so DDS should work fine with it) but not complete with respect to the polynomial degree 2 and the lp-degree 1.0. The complete multi-index set with respect to that parameter is actually:

MultiIndexSet
[[0 0]
 [1 0]
 [2 0]
 [0 1]
 [1 1]
 [0 2]]

Moreover, the current code base sometimes mixed up these two notions. For instance, currently the make_complete() method of MultiIndexSet creates a multi-index set that is complete with respect to the given lp-degree (it calls the get_exponent_matrix() function). However, the property is_complete is actually checking whether the exponent is downward-closed (termed "lexicographically complete" in the code). This can cause confusion and needs to be cleaned up.

What to do?

These two notions should be clearly distinguished. I suggest to have separate properties is_complete and is_downward_closed. Although I'm not sure whether a complete multi-index set is necessary in some application, I am inclined to keep the property, redefine it and add a new property is_downward_closed.