text:
# Uniform Birkhoff interpolation with rectangular sets of nodes

## 1. Introduction

Apart from its historical importance (see e.g. Newton’s interpolation formula, Gauss’ quadrature formula), interpolation by polynomials still plays a central role in the local construction of various approximation schemes (splines, finite elements, cubature formulas, etc). The homogeneous Birkhoff-Hermite problem is one of the most general multivariate polynomial interpolation problems. In general, it depends on a set $`Z^n`$ of nodes, a “lower set” $`S`$ defining the “interpolation space” $`𝒫_S`$ of polynomials (to which the solution is required to belong to), and a set $`A_+^n`$ of derivatives which appear in the interpolation equations. The univariate case ($`n=1`$) is quite well understood, and it behaves fundamentally different from the multivariate case . For notational simplicity, we restrict here the the bivariate case.

In the literature one finds two types of results. On one hand, there are criteria whose conclusion holds in the generic case (when the points of $`Z`$ are in general position). A very good example is the work of R.A. Lorentz . On the other hand, there are more constructive results which use ideas from the univariate case to produce explicit solutions for some special classes of interpolation schemes. A good example is the work of Gasca and Maeztu  (for more complete list of references, and historical comments, we refer to the same ). In such results, although the shape of $`Z`$ is very special, it is very rare that it is the starting point. More precisely, the shape comes on the second place: it is the one for which the method works.

Clearly, the patterns of the general problem are far too complex to be understood in an unified manner. One of the few common features of all approaches is that the shape of $`Z`$ (and sometimes that of $`A`$ too) plays an essential role. On the other hand, when it comes to applications, it often happens that the set of nodes $`Z`$ is given, has a very particular shape (think e.g. of cubature formulas), and there are only special cases/aspects of the problem that need to be solved/understood.

In this paper we initiate the study of multivariate Birkhoff interpolation schemes with main emphasis on the shape of $`Z`$. After a short discussion on “shapes”, we will concentrate on the simplest shapes, namely the rectangular ones (see 2.5):

$$Z=\{(x_i,y_j):0ip,0jq\}$$

($`p`$ and $`q`$ are non-negative integers). Apart from the main definitions, and a short discussion on “cartesian shapes” and their relation with the uniqueness of Birkhoff-Lagrange schemes (see 2.4), section 2 also brings together the main constructions that are relevant to the study of rectangular sets of nodes (most importantly, the notion of blow-up presented in 2.3). At the end of the section we briefly compare the generic case with the rectangular case. In section 3 we present several regularity criteria which are very useful in examples, and we derive several consequences. Inspired by all the results and all the examples, we conjecture that lower sets $`S`$ that are part of a regular scheme with rectangular sets of nodes must be the result of a blow-up, and we relate this to a stronger version (for rectangular sets of nodes) of the Polya inequalities. The results presented in this section can also be viewed as a confirmation of the conjectures in many unrelated cases (depending on the size and shape of $`A`$). At the end, we prove that the conjectures hold true in one more case: $`p=q=1`$ (and, this time, for all $`A`$). On the other hand, by looking at the pictures associated to regular schemes, one observes another stricking property that regularity seems to imply (a geometric property this time!). Initially, it was tempting to formulate this property into yet another conjecture, but, to our surpprise, it turned out to be equivalent to the the Polya-type inequalities mentioned above. This is the content of Theorem 4.1 in Section 4. In the same section we point out yet another geometric property that regular schemes seem to share (Conjecture 3, which we use as a guide for constructing interesting examples, cf. e.g. Example 5.10). And, finally, Section 5 contains a large list of examples.

Finally, we would like to point out that, although the results presented here are quite satisfactory for handeling large classes of examples, we feel that the main achievement of this paper is the understanding we gain (e.g. that blow-ups are relevant, that $`A`$ is geometrically related to $`S`$, etc). In this direction, we also believe that finding relations with other fields (e.g. algebraic geometry or algebraic topology) would give a new understanding of the conjectures above and of the interpolation problem (e.g., note that “the degrees of multivariate polynomials” together form an operad, and the blow-up is one of the simplest operations associated to it; see 2.3). The existence of a deeper such relation is (yet) another conjecture we would like to adress here.

This paper is part of the second author’s PhD dissertation, and it has circulated as a Utrecht University preprint. The present version follows “qualified suggestions” and is considerably shorter (in particular, it skips some of the technical but completely elementary proofs which will be presented elsewhere ).

## 2. Main definitions and constructions

###### 2.1.

Main definitions/terminology: In this paper we will use the following notations/terminology:

* $`Z`$ denotes a finite set of points in $`^2`$, which plays the role of the set of nodes of the interpolation problem.
* $`A`$ denotes a finite set of pairs of non-negative integers, describing the (order of the) derivatives appearing in the interpolation problem. Typical examples are the rectangles $`R(u,v)`$ and the triangles $`T(n)`$:

$$R(u,v)=\{(i,j)_+^2:iu,jv\},$$

$$T(n)=\{(i,j)_+^2:i+jn\}.$$
* $`S`$ is a lower set, that is, a finite subset $`S_+^2`$ with the property that

$$(u,v)SR(u,v)S.$$

Corresponding to $`S`$ is the space

$$𝒫_S=\{P[x,y]:P=\underset{(i,j)S}{}a_{i,j}x^iy^j\},$$

and $`𝒫_S`$ plays the role of the interpolation space (where the interpolation is taking place).
* such triples $`(Z,A,S)`$ are called interpolation schemes, and the associated problem is: for given constants $`\{c_{i,j}(z):(i,j)A,zZ\}`$, find polynomials $`P𝒫_S`$ satisfying the equations

(1)
$$\frac{^{i+j}P}{x^iy^j}(z)=c_{i,j}(z),zZ,(i,j)A.$$

One says that $`(Z,A,S)`$ is solvable if the problem has solutions for any choice of the constants. One says that $`(Z,A,S)`$ is regular if the problem has unique solution. The simplest necessary condition for regularity is normality of $`(Z,A,S)`$, that is, $`|S|=|Z||A|`$. All schemes in this paper are assumed to be normal.
* the interpolation equations are in fact a system of linear equations, and one denotes by $`D(Z,A,S)`$ its determinant (well defined because of the normality condition). This is a polynomial on the coordinates of the nodes ($`2n`$ such coordinates, where $`n=|Z|`$). Hence, fixing $`(A,S)`$, if $`(Z,A,S)`$ is regular for one choice of $`Z`$, then it is regular for almost all choices of $`Z`$ (where “almost all” refers to the Lebesgue measure on $`^{2n}`$). In this case one says that $`(A,S)`$ is almost regular with respect to sets of $`n`$ nodes.

###### 2.2.

Representing lower sets: First of all, for any non-negative integers $`s`$, $`n_0n_1\mathrm{}n_s`$,

$$S_y(n_0,\mathrm{},n_s)=\{(i,j)^2:0is,0jn_i\}$$

is clearly a lower set. Conversely, any lower set $`S`$ can be uniquely written in such a way. Given any set $`B^2`$, we introduce the notation

$$B_y[\alpha ]=\{\beta :(\alpha ,\beta )B\}.$$

Then, given a lower set $`S`$, the associated $`s`$ is the maximal number $`i`$ with the property that $`S_y[i]\mathrm{}`$, while $`n_i`$ is determined by $`S_y[i]`$:

$$S_y[i]=\{0,1,\mathrm{},n_i\}$$

A similar discussion is obtained by interchanging the role of $`x`$ and $`y`$. Representing $`S`$ both as $`S_y(n_0,\mathrm{},n_s)`$ and as $`S_x(m_0,m_1,\mathrm{},m_t)`$, the relation between the two is:

$$t=n_0,m_j=max\{i:n_ij\}.$$

Another way of representing lower sets is by making use of its “exterior boundary points”. Given $`S`$, a point $`(u,v)S`$ is called a boundary point if $`(u+1,v+1)S`$. We denote by $`S`$ the set of such points. We consider the following two possibilities:

1. $`(u,v+1)S`$;
2. $`(u+1,v)S`$.

We denote by $`_eS`$ the set of boundary points $`(u,v)`$ for which neither of the two conditions above is satisfied (“exterior boundary points”), by $`_iS`$ the set of those which satisfy both conditions (“interior boundary points”), by $`_xS`$ the set of those for which only (ii) holds true (“$`x`$-direction boundary points”), and by $`_yS`$ the set of those for which only (i) holds true (“$`y`$-direction boundary points”). These four sets form a partition of the boundary $`(S)`$ of $`S`$.

The set $`_eS`$ of exterior boundary points determines $`S`$ uniquely, since

$$S=\underset{(u,v)_eS}{}R(u,v).$$

It is actually useful to label the elements of $`_eS`$ by $`(a_k,b_1)`$, $`(a_{k1},b_2)`$, $`\mathrm{}`$ , $`(a_1,b_k)`$, indexed so that $`a_1<a_2<\mathrm{}<a_k`$, and $`b_1<b_2<\mathrm{}<b_k`$.

Then an element $`(u,v)`$ is in $`S`$ if and only if

$$a_{l1}<ua_l,0vb_{kl+1}$$

for some $`l\{0,1,\mathrm{}k\}`$. Also,

$$_eS=\{(a_i,b_j):i+j=k+1\},_iL=\{(a_i,b_j):i+j=k\},$$

$$_xS=\{(u,b_{kj}):1jk,a_j<u<a_{j+1}\},$$

$$_yS=\{(a_{ki},v):1ik,b_i<v<b_{i+1}\}.$$

###### 2.3.

Blowing up lowers sets:  Central to Birkhoff interpolation with rectangular sets of nodes is the notion of blow-up. Given $`p,q`$ non-negative integers, and a lower set $`S`$, we definer a new lower set $`S^{p,q}`$ which is obtained by “blowing up” each of the points of $`S`$ to a $`(p,q)`$-rectangle. One may think that a copy of $`R(p,q)`$ is placed on each of the points of $`S`$, and then one pushes these rectangles minimally to the right and upwards until they become disjoint. For an example with $`p=1`$, $`q=2`$, see the picture.

More formally,

$$S^{p,q}=\{(\alpha ,\beta ):([\frac{\alpha }{p+1}],[\frac{\beta }{q+1}])S\}.$$

If $`S=S_y(n_0,\mathrm{},n_s)`$, then $`S^{p,q}=S_y(n_0^{^{}},\mathrm{},n_s^{}^{^{}})`$, where

$$k^{}=(q+1)(k+1)1,n_i^{^{}}=(p+1)(n_j+1)1)\text{where}j=[\frac{i}{q+1}].$$

In terms of the exterior boundary points, $`_eS^{p,q}`$ consists of the pairs $`((p+1)u,(q+1)v)`$ with $`(u,v)_eS`$.

It is interesting to point out the structure underlying these operations, structure that becomes even more important in higher dimensions. Let us denote by $`(n)`$ the set of all lower sets $`L_+^n`$. Then, for any positive integers $`n`$, $`k_1,\mathrm{},k_n`$, there are “operations”

$$(n)\times (k_1)\times \mathrm{}\times (k_n)(k_1+\mathrm{}+k_n)$$

as follows: given $`(S,S_1,\mathrm{},S_n)`$, the result $`S^{}=S(S_1,\mathrm{},S_n)`$ of this operation is the lower set with the property that

$$𝒫_S^{}=\{P(P_1(x_1,\mathrm{},x_{k_1}),P_2(x_{k_1+1},\mathrm{},x_{k_1+k_2}),\mathrm{}):P𝒫_S,P_i𝒫_{S_i}\}.$$

These operations make $`\{(n)\}`$ into an operad , which we will call the multi-degree operad. The reason for the terminology is that lower sets can be viewed as an extension to higher dimension of the ordered set of natural numbers (non-negative integers): any natural number $`n`$ defines a lower set $`[n]=\{0,\mathrm{},n\}`$, and these are all the possible lower sets in dimension one. In general, an $`n`$-multivariate polynomials will have an associated lower set playing the role of degree, and $`𝒫_S`$ will be the space of polynomials “of degree (at most) $`S`$”. In particular, lower sets arise naturally also when discussing symbols of multi-deifferantial operators. Note also that the blow-up is one of the simplest operations encoded in the operad $`\{(n)\}`$:

$$S^{p,q}=S([p],[q]).$$

Shapes more complicated then the rectangular one would probably require the use of the other operations associated to $`\{(n)\}`$.

###### 2.4.

Particular shapes:  We now give a more precise meaning to the “shape” of a set of nodes. First of all, given a lower set $`S`$, one says that a set of nodes $`Z`$ is $`S`$-cartesian if it is of type

$$Z=\{(x_i,y_j):(i,j)S\},$$

where the $`x_i`$’s are distinct real numbers, and similarly the $`y_j`$’s. We say that $`Z`$ is cartesian if it is $`S`$-cartesian for some lower set $`S`$.

On the other hand, any set of nodes $`Z`$ induces two lower sets $`S_x(Z)`$, and $`S_y(Z)`$, which reflect the shape of $`Z`$. To describe $`S_y(Z)`$, one covers $`Z`$ by lines $`l_0,\mathrm{},l_k`$ parallel to the $`OY`$ axis, and define the numbers $`n_i`$ so that on each line $`l_i`$ there are exactly $`n_i+1`$ points of $`Z`$. We index the lines so that $`n_0n_1\mathrm{}n_k`$, and we define $`S_y(Z)=S_y(n_0,\mathrm{},n_k)`$. The lower set $`S_x(Z)`$ is defined similarly, by interchanging the role of $`x`$ and $`y`$.

The relation between the two is that a set of nodes $`Z`$ is cartesian if and only if $`S_x(Z)=S_y(Z)`$. In turn, this implies that cartesian sets of nodes show up naturally in relation with the uniqueness of Birkhoff-Lagrange schemes. Birkhoff-Lagrange schemes are those for which $`A`$ contains only the origin (and is then suppressed from the notation). Given any $`Z`$, there exists at least one lower set $`S`$ so that the Birkhoff-Lagrange scheme $`(Z,S)`$ is regular. However, $`S`$ is unique if and only if $`Z`$ is cartesian. For details, see .

###### 2.5.

Rectangular shapes: Of special interest for us are the cartesian sets with respect to the rectangles $`R(p,q)`$. Such sets are called $`(p,q)`$ rectangular (or just rectangular if we do not want to emphasize $`p`$ and $`q`$). Hence, $`Z`$ is $`(p,q)`$ rectangular precisely when it is obtained by intersecting $`(p+1)`$ vertical lines with $`(q+1)`$ horizontal lines. Writing

$$Z=\{(x_i,y_j):0ip,0jq\}$$

where the $`x_0,\mathrm{},x_p`$ are distinct real numbers, and similarly $`y_0,\mathrm{},y_q`$, the determinant $`D(Z,A,S)`$ is a polynomial on only $`t=p+q+2`$ variables (namely the $`x_i`$’s, and the $`y_j`$’s). We then say that a pair $`(A,S)`$ is almost regular with respect to $`(p,q)`$-rectangular sets of nodes if there exists such a $`Z`$ so that $`(Z,A,S)`$ is regular. As in the generic case, this implies that $`(Z,A,S)`$ is regular for almost all choices of the $`(p,q)`$-rectangular set s $`Z`$ (this time, of course, the “almost” part refers to the Lebesgue measure on $`^t`$). The regularity is defined similarly. Of course, one can also allow complex nodes, and talk about (almost) regularity with respect to $`(p,q)`$-rectangular sets of complex nodes.

###### 2.6.

Examples: To get a feeling about the effect that the shape of $`Z`$ has on regularity, let us point out two cases. For $`A=\{(0,0),(1,1)`$, there are no regular schemes whith rectangular sets of nodes, while there are many regular schemes with the set of nodes in general position. Consider now the case where

$$A=\{(0,0),(0,1)\}.$$

Then one can show that all schemes $`(A,S)`$ in which $`S`$ has the property that $`|S|=2n`$ and $`S`$ contains at most $`n`$ elements on the $`OX`$ axis, are almost regular with respect to sets of $`n`$ nodes. On the other hand, there is only one scheme which is almost regular with respect to $`(p,q)`$-rectangular sets of nodes, namely $`S=R(1,0)^{p,q}=R(2p+1,q)`$. These will become clear in the next sections.

###### 2.7.

Polya conditions:  To compare the multivariate case with the univariate one, and general sets of nodes with rectangular ones, it is interesting to look at Polya conditions. These are certain algebraic inequalities that are forced by regularity. The classical Polya condition  say that, given the regular scheme $`(Z,A,S)`$ then, for any lower subset $`LS`$,

(2)
$$n|LA||L|,$$

where $`n=|Z|`$. This follows quite easily by counting the numbers of zero in the determinant associated to the interpolation equations (1). Moreover, in the limit case (when equality holds) $`(Z,AL,L)`$ must be regular too. This corollary applies to the univariate case as well. Writing $`A=\{a_0,a_1,\mathrm{},a_s\}`$ with $`a_0<a_1<\mathrm{}<a_s`$, the Polya conditions become:

$$a_ini,0is.$$

Moreover, this condition actually insures regularity for almost all sets of nodes $`Z`$ . More precisely, given $`(A,S)`$ with $`|S|=n|A|`$, $`(A,S)`$ is almost regular if and only if it satisfies the Polya conditions. Moreover, if $`n=2`$, then the Polya conditions are sufficient also for regularity. Such properties do not hold in the multivariate case.

When the shape of $`Z`$ is particular, one can strengthen these inequalities. For instance, using boundary points (see 2.2 above), and by a careful analysis of the zeros in the determinant associated to interpolation equations, one can prove  that if $`(Z,A,S)`$ is regular and $`Z`$ is $`(p,q)`$-rectangular, then, for any lower subset $`LS`$,

$$n|AL||L|+pq|AL|+(p+q)|A_eL|+p|A_yL|+q|A_xL|.$$

## 3. Regularity criteria

In this section we bring together several regularity criteria for uniform Birkhoff interpolation schemes with rectangular sets of nodes, then we present some consequences and then point out a property that schemes with rectangular sets of nodes seem to satisfy (as suggested by the general criteria, proven for $`|A|6`$, and also for $`p=q=1`$). Since the proofs of these criteria, although a bit technical, are completely elementary, they will be presented elsewhere . Many examples illustrating the usefulness of the criteria will be presented in the last section.

Throughout this section, $`(Z,A,S)`$ is a uniform Birkhoff scheme, with a $`(p,q)`$-rectangular set of nodes

$$Z=\{(x_i,y_j):0ip,0jq\}.$$

We denote by $`A_x`$ the elements of $`A`$ on the $`OX`$ axis, we also use the similar notations $`A_y`$, $`S_x`$, $`S_y`$, and we put $`Z_x=\{x_0,\mathrm{},x_p\}`$ (the projection of $`Z`$ on the $`OX`$ axis), and similarly $`Z_y`$.

###### Proposition 3.1.

If $`(Z,A,S)`$ is regular, then

$$|A||A_x||A_y|.$$

Moreover, if the equality holds, then $`S`$ must be:

$$S=R(p^{},q^{}),p^{}=(p+1)|A_x|1,q^{}=(q+1)|A_y|1.$$

This property puts restrictions on the set $`A`$. For instance, if $`mix(A)`$ is the number of mixed derivatives coming from $`A`$, one immediately gets

(3)
$$\sqrt{mix(A)}\sqrt{|A|}1.$$

The next property takes care of the case where one of the lower sets $`S_y(A)`$ or $`S_x(A)`$ associated to $`A`$ (see 2.4) is rectangular. We then have (for the notation $`A_y[\alpha ]`$, see 2.2):

###### Theorem 3.2.

If $`Z`$ $`A`$ has the property that $`S_y(A)`$ is $`(s,t)`$\- rectangular (in particular, if $`A`$ is $`(s,t)`$\- rectangular), then the scheme $`(Z,A,S)`$ is regular if and only if

1. $`S=R(p^{},q^{})`$, with $`p^{}=(s+1)(p+1)1,q^{}=(t+1)(q+1)1`$.
2. The univariate scheme $`(Z_x,A_x,S_x)`$ is regular.
3. All the univariate schemes $`(Z_y,A_y[\alpha ],S_y)`$, with $`\alpha A_x`$, are regular.

The next criterion shows the influence that lower subsets of $`A`$ have on $`S`$.

###### Theorem 3.3.

If $`(Z,A,S)`$ is solvable (i.e. the interpolation equations have at least one solution, but not necessarily unique), and if $`A`$ contains a lower set $`R`$, then $`S`$ must contain the lower set $`R^{p,q}`$.

In particular, if $`A`$ is lower, one can completely clarify the situation. The outcome makes use of the univariate Hermite polynomials for the set of nodes $`Z_x`$. For non-negative integers $`u`$, $`a`$, and a node $`x_s`$, we consider

$$H_a^{u,s}(x)=\varphi _s(x)\underset{k=u}{\overset{a}{}}\frac{(xx_s)^k}{u!(ku)!}(\frac{1}{\varphi _s})^{(ku)}(x_s),$$

where

$$\varphi _s(x)=(xx_0)^{a+1}\mathrm{}\widehat{(xx_s)^{a+1}}\mathrm{}(xx_p)^{a+1}.$$

We make the convention that $`H_{a,s}^u(x)=0`$ if $`a<u`$. Similarly, we denote by $`H_b^{v,t}`$ the univariate Hermite polynomials associated to the set of nodes $`Z_y`$. We also write

$$_eS=\{(a_k,b_1),\mathrm{},(a_1,b_k)\},$$

as in 2.2. With these, we have:

###### Theorem 3.4.

If the set $`A`$ of derivatives is lower, then $`(Z,A,S)`$ is regular if and only if $`S=A^{p,q}`$.

Moreover, in this case, for any $`(u,v)A`$, and any node $`(x_s,y_t)Z`$, the polynomial

$`H_{u,v}^{s,t}(x,y)=`$
$`H_u^{a_1,s}(x)(H_v^{b_k,t}(y)H_v^{b_{k1},t}(y))+H_u^{a_2,s}(x)(H_v^{b_{k1},t}(y)H_v^{b_{k2},t}(y))+`$
$`\mathrm{}+H_u^{a_{k1},s}(x)(H_v^{b_2,t}(y)H_v^{b_1,t}(y))+H_u^{a_k,s}(x)H_v^{b_1,t}(y)`$
is the fundamental interpolation polynomial at the node $`(x_i,y_j)`$, with respect to the derivative $`(u,v)`$, i.e.

$$\frac{^{\alpha +\beta }H_{u,v}^{s,t}}{x^\alpha y^\beta }(x_i,y_j)=\{\begin{array}{cc}1\hfill & \text{if}\alpha =u,\beta =v,i=s,j=t\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}.$$

The next property determines $`S`$ “around the coordinate axes”. We use again the notations $`S_y[\beta ]`$, $`S_x[\alpha ]`$ introduced in 2.2.

###### Theorem 3.5.

If $`(Z,A,S)`$ is a regular UR Birkhoff scheme, where the set of nodes $`Z`$ is $`(p,q)`$-rectangular, then

$`S_x[0]=S_x[1]=\mathrm{}=S_x[q]`$ $`=`$ $`\{0,1,\mathrm{},p^{}\},`$
$`S_y[0]=S_y[1]=\mathrm{}=S_y[p]`$ $`=`$ $`\{0,1,\mathrm{},q^{}\},`$
where $`p^{}=(p+1)|A_x|1,q^{}=(q+1)|A_y|1`$.

And, finally, the following shows how one can move or remove points of $`A`$ on the coordinate axes. We denote by $`S^{}`$ the set obtained from $`S`$ by removing the lowest $`(p,q)`$-rectangle on its most right (that is, remove the last $`(p+1)`$ elements of $`S`$ from each of the lines $`y=i`$, with $`0iq`$). Note that $`S^{}`$ is lower if and only if $`|S_x(q+1)|p^{}(p+1)`$.

###### Theorem 3.6.

Let $`(Z,A,S)`$ be an uniform Birkhoff scheme with rectangular set of nodes. Then:

1. If $`(Z,A,S)`$ is regular, then the univariate scheme $`(Z_x,A_x,S_x)`$ must be regular.
2. If $`\stackrel{~}{A}^2`$ is obtained from $`A`$ by moving some of its elements on the $`OX`$ axis, then $`(Z,\stackrel{~}{A},S)`$ is still regular if $`(Z_x,\stackrel{~}{A}_x,S_x)`$ is.
3. If $`A^{}`$ is obtained from $`A`$ by removing one of its elements from the $`OX`$ axis, $`S^{}`$ is lower, and and both univariate schemes $`(Z_x,A_x,S_x)`$ and $`(Z_x,A_x^{},S_x^{})`$ are regular, then $`(Z,A,S)`$ is regular if and only if $`(Z,A^{},S^{})`$ is.

There is an obvious variation obtained by interchanging $`x`$ and $`y`$. Also, there is a particularly good way of changing $`A`$. Let us denoted by $`A_{max}`$ the set obtained by replacing the elements of $`A`$ on the $`OX`$ axis with $`\{0,p+1,2(p+1),\mathrm{},(p+1)(|A_x|1)\}`$. This is the “maximal replacement” allowed by the univariate Polya condition (see 2.7). Moreover, $`(A_{max,x},S_x)`$ is automatically regular with respect to all sets of $`(p+1)`$ nodes (under the normality condition $`|S_x|=(p+1)|A_x|`$). In particular, applying first (ii) and then (iii), we deduce that $`(Z,A,S)`$ is regular if and only if $`(Z_x,A_x,S_x)`$ and $`(Z,A_{max}^{},S^{})`$ are.

A large number of examples which show the usefulness of these criteria are presented in Section 3. Let us now point out several consequences. First of all, using Theorem 3.5 to determine $`S`$, and then Theorem 3.6 to reduce the size of the problem (and $`A_{max}`$ to simplify), we immediately deduce

###### Corollary 3.7.

If $`A`$ contains no mixed derivative, then $`(Z,A,S)`$ is regular if and only if the univariate schemes $`(Z_x,A_x,S_x)`$ and $`(Z_y,A_y,S_y)`$ are regular and

$$S=T^{p,q},\text{where}T=R(|A_x|1,0)R(0,|A_y|1).$$

The next case (one mixed derivative) is easier to state in terms of almost regularity instead of regularity.

###### Corollary 3.8.

Assume that $`A`$ contains only one mixed derivative, call it $`(\alpha ,\beta )`$, and let $`\{(a_i,0):0is\}`$ be the elements of $`A`$ on the $`OX`$ axis, and $`\{(0,b_j):0jt\}`$ the ones on the $`OY`$ axis. Then $`(A,S)`$ is almost regular with respect to $`(p,q)`$-rectangular sets of nodes if and only if $`s,t1`$,

$$a_ii(p+1),b_jj(q+1),\alpha 2p+1,\beta 2q+1$$

(for all $`i`$ and $`j`$), and

$$S=T^{p,q},\text{where}T=R(|A_x|1,0)R(0,|A_y|1)R(1,1).$$

###### Proof.

The conditions on the $`a_i`$’s and the $`b_j`$’s are just the univariate Polya conditions (see 2.7). On the other hand, if we require that no nontrivial polynomial of type $`P=(yy_0)\mathrm{}(yy_q)Q(x)𝒫_S`$ may satisfy the homogeneous interpolation equations of the scheme, we see that $`|S_x[q+1]|2p+1`$, and, similarly $`|S_x[p+1]|2q+1`$. Using also Theorem 3.5 and the fact that $`S`$ is lower, these inequalities immediately imply the last part of the statement. This allows us to remove elements of $`A`$ from the coordinate axes (use Theorem 3.6 and $`A_{max}`$) and reduce the problem to $`s=1`$ and $`t=1`$, $`a_1=(p+1)`$, $`b_1=(q+1)`$. Finally, if the inequalities on $`\alpha `$ and $`\beta `$ do not hold, we have $`(\alpha ,\beta )R(p+1,q+1)`$, and, using the Polya inequality for $`L=R(p+1,q+1)`$ (cf. 2.7) we would obtain

$$3n(n+p+q+3)+2pq+p+q,$$

i.e. $`3n3n+1`$ which is impossible. Conversely, if $`\alpha `$ and $`\beta `$ satisfy these inequalities, then we can move $`(p+1,0)A`$ to $`(\alpha ,0)`$, and then $`S_y(A)`$ becomes rectangular and we can apply Theorem 3.2. ∎

###### Corollary 3.9.

If $`(A,S)`$ is almost regular with respect to $`(p,q)`$-rectangular sets of nodes, and $`|A|6`$, then $`S`$ is of type $`T^{p,q}`$ for some lower set $`T`$.

###### Proof.

Using (3), $`A`$ will contain at most one mixed derivative except for the case where $`|A|=6`$ and $`A`$ contains two mixed derivatives. The first cases follow from the previous corollary, while the last one follows from the limit case of Proposition 3.1. ∎

The results above (see also below, and the section on examples) suggest the following

###### Conjecture 1.

If a scheme $`(A,S)`$ is almost regular with respect to $`(p,q)`$-rectangular sets of nodes, then $`S=R^{p,q}`$ for some lower set $`R`$.

Let us give a stronger version of this conjecture, which also has a geometric interpretation that is easier to visualize (see the next section). Given a lower set $`S`$, we denote by $`n_{p,q}(S)`$ the number of elements $`(\alpha ,\beta )S`$ with the property that $`\alpha `$ is divisible by $`(p+1)`$, and $`\beta `$ is divisible by $`(q+1)`$. The following can be interpreted as a Polya-type inequality for rectangular sets of nodes.

###### Conjecture 2.

($`p,q)`$-Polya conjecture) If a scheme $`(A,S)`$ is almost regular with respect to $`(p,q)`$-rectangular sets of nodes, then

(4)
$$|LA|n_{p,q}(L)$$

for all lower sets $`LS`$.

Let us point out the relation with the Polya condition, as well as the relation between the two conjectures.

###### Proposition 3.10.

Consider the scheme $`(A,S)`$ with $`|S|=n|A|`$, where $`n=(p+1)(q+1)`$.

1. For all lower sets $`L`$, $`n_{p,q}(L)\frac{1}{n}|L|`$. In particular, Conjecture 2 is a strengthening of the Polya conditions (2).
2. $`S=R^{p,q}`$ for some lower set $`R`$ if and only if $`n_{p,q}(S)|A|`$ (and then equality must hold). In particular, Conjecture 2 implies Conjecture 1.

###### Proof.

Given a lower set $`L`$, we define a new lower set $`L_{p,q}`$ obtained from $`L`$ by “collapsing $`(p,q)`$-rectangles to points”:

$$L_{p,q}=\{(\alpha ,\beta ):((p+1)\alpha ,(q+1)\beta )L\}.$$

First of all, it is clear that $`n_{p,q}(S)=|S_{p,q}|`$. Secondly, it is easy to see that $`(L^{p,q})_{p,q}=L`$, and $`L(L_{p,q})^{p,q}`$ for all lower sets $`L`$. Passing to cardinalities in the last inequality, we obtain (i).

On the other hand, one immediately sees that $`S_{p,q}`$ is the smallest lower set with the property its $`(p,q)`$-blow up contains $`S`$. In particular, if $`S=R^{p,q}`$ for some lower set $`R`$, then $`R`$ must coincide with $`S_{p,q}`$. So, the condition that $`S=R^{p,q}`$ for some lower set $`R`$ is equivalent to saying that $`S(S_{p,q})^{p,q}`$ becomes equality. Passing to cardinalities, we have $`|A|n_{p,q}(S)`$, and the requirement is that equality holds. This proves (ii). ∎

Regarding (the stronger) Conjecture 2, it is verified in all examples we looked at, and the results of this section can be used to verify it in many other cases. Let us point out that it is true also when $`p1`$, $`q1`$. We state here the case $`p=q=1`$, which will be very useful when looking at examples.

###### Theorem 3.11.

Given $`A`$ and $`S`$, $`p=q=1`$, the following are equivalent:

1. The scheme $`(A,S)`$ is regular for some $`(1,1)`$-rectangular set of nodes $`Z`$.
2. The scheme $`(Z,A,S)`$ is regular for any $`(1,1)`$-rectangular set of nodes $`Z`$.

In this case moreover, $`(A,S)`$ satisfies Conjecture 2 (hence also Conjecture 1).

###### Proof.

By changing coordinates

$$(x,y)(2\frac{xx_0}{x_1x_0}1,2\frac{yy_0}{y_1y_0}1,$$

we can always assume

$$Z=\{(1,1),(1,1),(1,1),(1,1)\},$$

and this proves the equivalence of (i) and (ii). Assume now that there exists a lower subset $`LS`$ such that $`n_{1,1}(L)>|AL|`$. This precisely mens that $`R=L_{1,1}`$ (where we use the notations from the previous proof) satisfies $`|R|>|AL|`$. We now consider the space $`𝒫_{2R}`$ of polynomials spanned by $`x^{2\alpha }y^{2\beta }`$ with $`(\alpha ,\beta )R`$. Note that $`𝒫_{2R}𝒫_S`$. Next, since the polynomials in $`𝒫_{2R}`$ depend on $`|R|>|A|`$ variables (the coefficients), we find a non-zero polynomial $`P𝒫_{2R}`$ such that

(5)
$$\frac{^{i+j}P}{x^iy^j}(1,1)=0,(i,j)A$$

But $`P𝒫_{2R}`$ implies that $`P(x,y)=P(x,y)=P(x,y)=P(x,y)`$. Taking derivatives, these relations still hold true, at least up to a sign. In particular, (5) implies that $`P`$ satisfies all the equations (1) corresponding to derivatives coming from $`AL`$, and with the constants $`c_{i,j}(z)`$ equal to zero (the homogeneous equations). On the other hand, since $`L`$ is lower and $`P𝒫_L`$, all the derivatives of $`P`$ coming from $`AL`$ are identically zero. Hence $`P𝒫_{2R}𝒫_S`$ would be a non-trivial solution of the homogeneous equations associated to our scheme, which contradicts regularity. ∎

Note also that, with the same argument as above (using the $`(p+1)^{th}`$ and the $`(q+1)^{th}`$ roots of unity) proves the following

###### Corollary 3.12.

If $`(A,S)`$ is regular with respect to $`(p,q)`$-rectangular sets of complex nodes, then it satisfies Conjecture 2 (hence also of Conjecture 1).

## 4. Geometric aspects

In this section we discuss the geometric interpretations of the inequalities (4), which are easy to visualize on the picture (see the next section).

Roughly speaking, this property says that $`S`$ is obtainable by attaching a copy of the rectangle $`R(p,q)`$ to each point of $`A`$, and then moving these rectangles upwards or to the right until they become disjoint. To make this more precise, we need to use “shifts” of $`A`$ in $`S`$, which are transformations which move $`A`$ step by step, at each step one of its elements being moved upwards or to the right on a new position which is still in $`S`$ and which is not occupied by any other element of $`A`$. We also consider the set

$$𝒵^{p,q}=\{((p+1)i,(q+1)j):i,j\text{positive integers}\},$$

which can be viewed as the blow up of the lattice $`𝒵`$ of integral points situated in the first quadrant.

###### Theorem 4.1.

Given $`(A,S)`$ ($`|S|=n|A|`$, $`n=(p+1)(q+1)`$), the following are equivalent

1. $`|LA|n_{p,q}(L)`$ for all lower sets $`LS`$.
2. there exists a shift of $`A`$ in $`S`$ which moves $`A`$ to $`S𝒵^{p,q}`$.

###### Proof.

Before starting the proof, let us fix some notations. Given an element $`eS`$, we denote by $`e^r`$ the one step translation of $`e`$ to the right, and similarly $`e^u`$ (upwards translation). Also, for any lower set $`L`$, we consider two new lower sets $`\stackrel{}{L}`$ and $`\overline{L}`$ such that

$$\stackrel{}{L}L\overline{L},n_{p,q}(\stackrel{}{L})=n_{p,q}(L)=n_{p,q}(\overline{L}),$$

and such that $`\stackrel{}{L}`$ is the smallest possible one, while $`\overline{L}`$ is the largest possible. Note that $`\overline{L}=(L_{p,q})^{p,q}`$. It is easy to see that $`\overline{L_1L_2}=\overline{L_1}\overline{L_2}`$, and similarly for intersections and also for the operations $`\stackrel{}{L}`$, and

$$n_{p,q}(L)=\frac{1}{n}|\overline{L}|.$$

We now turn to the proof. Assume first that such a shift $`\mathrm{\Lambda }`$ exists, and let $`LS`$ be a lower set. Then the points of $`L𝒵^{p,q}`$ will be obtained by moving some of the points of $`A`$, and those points must come from $`AL`$. Hence $`\mathrm{\Lambda }`$ defines a bijection between a subset of $`AL`$ and $`L𝒵^{p,q}`$, and this proves the desired inequality. We now keep $`p`$ and $`q`$ fixed, we denote by $`𝒫`$ the set of pairs $`(A,S)`$ that satisfy (i) and have $`|S|=n|A|`$, and we prove that (ii) holds for any $`(A,S)𝒫`$ by induction on $`|S|`$. The starting point is $`|S|=n`$. Then $`A`$ is forced to be $`\{(0,0)\}`$ (apply the condition to $`L=\{(0,0)\}`$), $`S`$ is forced to be the rectangle $`R(p,q)`$ (apply the condition to $`L=S`$), hence $`A=S𝒵^{p,q}=\{(0,0)\}`$. Assume now that $`(A,S)`$ does satisfy (i), and the implication has been shown for all pairs $`(A^{},S^{})`$ with $`|S^{}|<|S|`$. If one of the points of $`A`$ can be moved one step upwards, or one step to the right, so that the condition (i) is still satisfied (by $`S`$ and the new set $`A`$), then we perform the move. We repeat this if still possible. This process will stop at some point (e.g. because $`A`$ cannot be moved outside $`S`$). Hence, we may assume that $`A`$ is “maximal”, in the sense that none of its elements can be moved any further without violating (i). We will show that $`A=S𝒵^{p,q}`$. We first prove the following:

Claim 1: If $`LS`$ is a lower subset with $`|AL|=n_{p,q}(L)`$, then either $`\overline{L}=S`$, or $`AL=𝒵^{p,q}L`$.

Proof of the claim: We first show that $`(AL,\overline{L})𝒫`$. First of all, $`|\overline{L}|=n_{p,q}(L)=|AL|`$. Secondly, for any lower set $`P\overline{L}`$ one has $`\overline{P}\overline{L}`$, hence $`\overline{LP}=\overline{L}\overline{P}=\overline{P}`$. This, and the fact that $`(A,S)`$ does satisfy (i), imply that

$$n_{p,q}(P)=n_{p,q}(LP)|A(LP)|=|(AL)P|$$

for all $`P\overline{L}`$ lower. Hence $`(AL,\overline{L})𝒫`$. Assume now that $`\overline{L}S`$. Then, by the induction hypothesis, there is a shift that moves $`AL`$ to $`𝒵^{p,q}\overline{L}=𝒵^{p,q}L`$. Since this shift stays inside $`L`$, it does not touches the elements in $`AL`$, hence it can be viewed as a shift $`\mathrm{\Lambda }`$ of the entire $`A`$, which leaves $`AL`$ intact. In other words, the image $`A^{}`$ of $`\mathrm{\Lambda }`$ is given by

$$A^{}L=𝒵^{p,q}L,A^{}L=AL.$$

Now, for any $`PS`$ lower, one has

$$\begin{array}{cc}\hfill |A^{}P|& =|A^{}(PL)|+|A^{}(PL)|\hfill \\ & =|A^{}(PL)|+|A(PL)|\hfill \\ & =|(A^{}L)(PL)|+|A(PL)||AL|\hfill \\ & n_{p,q}(PL)+n_{p,q}(PL)n_{p,q}(L)\hfill \\ & =n_{p,q}(R)\hfill \end{array}$$

In the inequality above we used that $`(A^{}L,\overline{L})`$ and $`(A,S)`$ satisfy (i), and that $`|AL|=n_{p,q}(L)`$. This shows that $`(A^{},S)𝒫`$. From the maximality of $`A`$, the shift must be the identity shift, which precisely means that $`AL=𝒵^{p,q}L`$. This concludes the proof of the claim.

Claim 2: If $`eA𝒵(p,q)`$ is an element with the property that $`e^rA`$, then

$$e_y(\stackrel{}{S})_e(\stackrel{}{S}).$$

Proof of the claim: Denote by $`A_e^r`$ the new set obtained from $`A`$ by moving $`e`$ to $`e^r`$. By the maximality of $`A`$, $`(A_e^r,S)`$ does not satisfy (i), hence we find a lower set $`L`$ such that $`|A_e^rL|<n_{p,q}(L)`$. But $`|A_e^rL|`$ is either $`|AL|1`$ (if $`eL`$, $`e^rL`$), or $`|AL|`$ (in the remaining cases). Since $`|AL|n_{p,q}(L)`$, we must have

$$|AL|=n_{p,q}(L),eL,e^rL.$$

We now use the previous claim. Since $`e(AL)𝒵(p,q)`$, we must have $`\overline{L}=S`$. In turn, this implies that $`\stackrel{}{L}=\stackrel{}{S}`$, hence, since $`e^rL`$, we have $`e^r\stackrel{}{S}`$. On the other hand, applying (i) to the largest lower set which does not contain $`e`$, we immediately see that $`S`$ contains at least one element in $`𝒵^{p,q}`$ larger then $`e`$. In other words, $`e\stackrel{}{S}`$. But the elements $`e\stackrel{}{S}`$ with $`e^r\stackrel{}{S}`$ are exactly those those situated on $`_y(\stackrel{}{S})_e(\stackrel{}{S})`$. This concludes the proof of the claim.

Clearly, one can replace $`e^r`$ by $`e^u`$, and arrive to a similar conclusion. In particular, if $`eA𝒵^{p,q}`$, then either $`e^r`$ or $`e^u`$ must be in $`A`$ (otherwise we must have $`e_e(\stackrel{}{S})`$, which is a contradiction because the extremal boundary points of $`\stackrel{}{S}`$ belong to $`𝒵^{p,q}`$).

We are now ready to prove that $`A=L𝒵^{p,q}`$. If this is not so, then we pick up an extremal element $`e`$ of $`A𝒵^{p,q}`$. That means that $`eA𝒵^{p,q}`$, and $`A𝒵^{p,q}`$ contains no other element whose coordinates are greater or equal to the coordinates of $`e`$. Then at least one of the positions $`e^u`$ or $`e^r`$ are not in $`A`$. Otherwise, since $`e`$ is extremal, $`e^r`$ and $`e^u`$ would both be in $`𝒵^{p,q}`$, and that is clearly impossible. Hence, combined with the previous remark, one (and only one) of these two elements are in $`A`$. Hence we may assume that

$$e^rA,e^uA.$$

From Claim 2, and the extremality of $`e`$, we deduce that

$$e^r_y(\stackrel{}{S})_e(\stackrel{}{S}),e^u𝒵^{p,q}.$$

Let $`e^{}`$ be the exterior boundary point of $`\stackrel{}{S}`$ with the property that the segment $`l=[e,e^{}]`$ is parallel to $`OY`$ (see Fig. 5). We apply condition (i) to the lower set $`SQ_e`$, where $`Q_e`$ is as in the picture. (i.e. $`SQ_e`$ is the largest lower subset of $`S`$ which does not contain $`e`$). We immediately get $`|l𝒵^{p,q}||lA|`$. Since $`e`$ is the only point of $`A`$ situated on $`l`$ but not on $`𝒵^{p,q}`$, we find a point $`f=(\alpha ,\beta )Al𝒵^{p,q}`$ with the property that $`\stackrel{~}{f}=(\alpha +p,\beta )`$ is in $`l𝒵^{p,q}`$ but it is not in $`A`$. We then consider the shift that moves $`f`$ to $`\stackrel{~}{f}`$, and leaves the rest of $`A`$ unchanged. The maximality of $`A`$ implies again the existence of a lower set $`L`$ with the property that $`|AL|=n_{p,q}(L)`$, $`fL`$, $`\stackrel{~}{f}L`$. We can now use Claim 1 above. Since $`\stackrel{~}{f}L`$ and $`\stackrel{~}{f}𝒵^{p,q}`$, one cannot have $`\overline{L}=S`$. Hence we must have $`AL=𝒵^{p,q}L`$. On the other hand, since $`L`$ is lower and $`e`$ sits below $`f`$, it follows that $`eAL=L`$, hence $`e𝒵^{p,q}`$. This contradicts the choice of $`e`$, and concludes the proof of the Theorem.

Let us point out another geometric property that is suggested by examples. This time, we will use inverse shifts, which are defined exactly like shifts, but moving downwards and to the left.

###### Conjecture 3.

If $`(A,S)`$ is almost regular with respect to $`(p,q)`$-rectangular sets of nodes, then there is an inverse shift of $`A`$ in $`S`$, which moves $`A`$ to a lower set $`R`$, and $`S=R^{p,q}`$.

As in Theorem 4.1 (and proven using the same ideas), this geometrical condition is equivalent to an algebraic condition, which says that $`|AL||RL|`$ for all lower sets $`L`$. Note also that one should only allow certain type of shifts which do not violate certain “regularity conditions”. What “regularity condition” exactly means is still to be discovered, but it certainly excludes moving new elements to the axes (cf. the results of the previous section). Also, it is tempting to combine the last conjecture and Theorem 4.1 into a stronger (unifying conjecture) which states the existence of (certain) shifts of $`R`$ into $`S𝒵^{p,q}`$, which move $`(i,j)`$ to $`((p+1)i,(q+1)j)`$, and which, at some intermediate step, cover $`A`$.

Note that in almost all the cases we have considered so far (e.g. no mixed derivatives, or lower sets of derivatives), moving $`A`$ backwards to a lower set was possible in only one way. Hence Conjecture 3 would explain the uniqueness of $`S`$ (proven by us in each case separately. Also, one can use this conjecture as a guide for constructing interesting examples (e.g. where $`S`$ is not unique, see Example 5.10).

## 5. Examples

In this section we present several examples that illustrate the results of the previous sections. For simplicity, we restrict most of the examples to the case $`p=q=1`$, i.e. the case of $`(1,1)`$-rectangular sets of nodes. One of the simplifications comes from the fact that, in this case, the notions of regular and almost regular coincide (cf. Theorem 3.11). Hence, unless otherwise specified, the term “regular” in this section stands for“regular with respect to $`(1,1)`$-rectangular sets of nodes”. Passing to the general case of $`(p,q)`$-rectangular sets of nodes require some care on almost regularity versus regularity, but many of the arguments remain the same.

###### Example 5.1.

Let $`A`$ be as in Fig. 6. Then there is no lower set $`S`$ which makes $`(A,S)`$ into a regular scheme. Assume there is one. First of all, it must be $`R(5,5)`$, as implied by Proposition 3.1. In this case however, the inequality (4) (insured by Theorem 3.11) is violated by the lower set $`L`$ drawn in the picture. Hence, there is no lower set $`S`$ which makes $`(A,S)`$ regular.

$$s(Z_{1,1},A)=0.$$

Note also that after moving any of the first two points of $`A`$ situated on the line $`y=3`$ one step downwards, the condition is no longer violated, and one can actually show that the resulting schemes are regular. However, moving the last point on that line (i.e. $`(3,3)`$) one step downwards, produces a scheme which is still non-regular since the same condition is violated (this time by $`L^{}`$ shown in Fig. 7).

###### Example 5.2.

Consider now $`A`$ as in Fig. 8. As above, regularity forces $`S=R(5,5)`$. This time however, the inequality (4) is satisfied. Let us show that $`(A,S)`$ is regular. We first remark that $`S_y(A)`$ is $`(3,3)`$-rectangular, hence we can use Theorem 3.2 to reduce the regularity of $`(A,S)`$ to the regularity of several univariate schemes. In turn, the univariate schemes are being taking care of by the Polya condition (see 2.7). When $`p,q1`$ the same arguments apply to conclude that $`(A,S)`$ is almost regular (with respect to $`(p,q)`$-rectangular sets of nodes) if and only if $`S=R(2p+3,2q+3)`$. Moreover, given the set of nodes $`Z`$, Theorem 3.2 rephrases the regularity of $`(Z,A,S)`$ in terms of the regularity of certain induced univariate schemes which are easier to handle.

###### Example 5.3.

We consider now the variation of the previous example shown in Fig. 9. One cannot apply Theorem 3.2 directly, but one can first invoke Theorem 3.6 to re-arrange the points of $`A`$ on $`OX`$ to occupy the first three positions. Then $`S_y(A)`$ becomes rectangular, and Theorem 3.6 can be used. Alternatively, one can use Theorem 3.6 twice (once on each of the axes) to and then reduce the problem to the one of the previous example.

###### Example 5.4.

Let $`A`$ be as in Fig. 10. Using Theorem 3.5, we see that $`S`$ must contain $`S_0`$ shown in the picture, and it must be contained in $`R(5,5)`$. Using Theorem 3.11 (namely that $`S`$ is of type $`R^{1,1}`$ for some lower set $`R`$), we see that $`S`$ is obtained from $`S_0`$ together with a copy of the rectangle $`R(1,1)`$. But there are only two ways one can add such a rectangle to $`S_0`$ to obtain a lower set, and the two possibilities are shown as Case $`1`$ and Case $`2`$ in the picture. In the first case, the inequality (4) (insured by Theorem 3.11) with $`L=S\{(3,1)\}`$ is not satisfied. The situation is different in the second case, when we obtain a regular scheme. To see this, one first uses Theorem 3.6 to remove the last point of $`A`$ situated on $`OY`$, and then one treats the remaining scheme as in Example 5.2. Hence, again, there is only one $`S`$ which makes the scheme regular.

###### Example 5.5.

Let us now describe two examples which show that the inequalities (4) do not imply regularity with respect to $`(1,1)`$-rectangular sets of nodes. Consider the scheme $`(A,S)`$ appearing on the left hand side of Fig. 11. It does satisfy the desired condition, but it is not regular. To see this, we remark that $`A`$ can be obtained from $`\stackrel{~}{A}`$ (see right hand side of Fig. 11) by removing the last element from $`OX`$. Hence we can apply Theorem 3.6 to $`(\stackrel{~}{A},\stackrel{~}{S})`$ to conclude that it is regular if $`(A,S)`$ is. But this cannot happen because the regularity of $`(\stackrel{~}{A},\stackrel{~}{S})`$ and the fact that $`\stackrel{~}{A}`$ is lower would imply that $`\stackrel{~}{S}=\stackrel{~}{A}^{1,1}`$ (cf. Theorem 3.4), which is not the case.

We should say here that what causes the non-regularity in this example is another simple condition that must be satisfied by all regular schemes (and, in this example, it is not): the number of points of $`A`$ on the line $`y=1`$ cannot exceed those on the line $`y=0`$.

###### Example 5.6.

A bit more subtle is the example drawn in Fig. 12, which still satisfies the inequalities (4). We advise the reader to try to guess a “general regularity condition” that is broken in this example. We now give an argument that proves that $`(A,S)`$ cannot be regular. Assume it is. We first move the last two elements of $`A`$ on $`OX`$ to new positions to get the scheme $`(A^{},S^{})`$ of Fig. 12. By Theorem 3.6 (and the univariate Polya conditions, see 2.7), $`(A^{},S^{})`$ is still regular. Now, choose $`L`$ as in the picture. One has $`|L|=4|AL|`$, i.e. we are in the limit case of the Polya condition. Hence (see 2.7) $`(AL,L)`$ must be regular too. But, by the same arguments as in the example above, $`(AL,L)`$ cannot be regular.

###### Example 5.7.

Let us return to the set $`A`$ appearing in the last example in 5.5 (Fig. 12), and look for all $`S`$’s which make $`(A,S)`$ regular. As in Example 5.4, there are two possible cases. One of them is precisely the one treated in Example 5.5, while the other one is shown in Fig. 13. The last one is regular. To see this, one first uses Theorem 3.6 to remove the last point of $`A`$ situated on $`OY`$. The resulting scheme $`(A^{},S^{})`$ has $`S_x(A)`$ rectangular, hence we can use Theorem 3.2 (or, more precisely, the version obtained by interchanging $`x`$ and $`y`$). The subsequent univariate schemes are regular (by 2.7 again).

###### Example 5.8.

A similar example is obtained by considering $`A`$ as in Fig. 14. As before, $`S`$ must be obtained from $`S_0`$ in the picture by adding one copy of $`R(1,1)`$. There are two possible ways to do that, but only the one shown in the picture produces a regular scheme. However, we do not know how to use the general results of the previous sections to prove the non-regularity of the other scheme.

###### Example 5.9.

Consider now $`A`$ as in Fig. 15. As before, Theorem 3.5 tells us what $`S`$ must be around the axes. We then have to fit three more (disjoint) copies of $`R(1,1)`$ inside $`R(5,5)`$ to get the lower set $`S`$. This time, this is possible in only one way (as in the picture). One sees that the inequalities (4) are satisfied, and one can actually show that the scheme is regular.

###### Example 5.10.

In all the previous examples, given $`A`$, there was at most one $`S`$ making $`(A,S)`$ regular. Here is an example where two such $`S`$’s can be chosen. Consider $`A`$ as in Fig. 16. As in the previous examples, $`S`$ is contained in $`R(5,5)`$ and must be obtained by adding one copy of $`R(1,1)`$ to the blow up $`(T_2)^{1,1}`$ of the triangle $`T_2`$. This is possible in two ways, with the resulting $`S`$’s: $`S_y(2,1,1)^{1,1}`$ and $`S_y(2,2,1)^{1,1}`$ (see also Fig. 17). That both resulting schemes are regular follows again by removing one point and then using Theorem 3.2.

It is interesting to discuss this example in the light of Conjecture 3. Note that, in all the examples we have considered so far, moving $`A`$ backwards to a lower set was possible in only one way, hence the conjecture suggest the uniqueness of $`S`$ (proven by us in each case separately). In the example under discussion, the process of “moving $`A`$ backwards” to a lower set is not unique; there are clearly (only) two ways of doing so, as shown in Fig. 17: the extremal element of $`A`$ can be moved one step down, or one step to the left. And this is how we actually constructed this example. Similarly, one can find examples where the number of choices for $`S`$ equals a given number.