Keywords: multivariate interpolation, algebraic curves .
<ph f="ecbx">Expected term bases for generic multivariate Hermite interpolation</ph>

Marcin Dumnicki

Institut of Mathematics, Jagiellonian University, Reymonta 4, 30-059 Krakow, Poland E-mail address: Marcin.Dumnicki@im.uj.edu.pl

1 Introduction.

We denote by N   the set of nonnegative integers, by K   a field of characteristic zero. Let I n : = { 1 , 2 , . . . , n }   . We will use the natural one-to-one correspondence between monomials x α ∈ K [ x 1 , . . . , x n ]   and multiindices α ∈ N n   . For any two multiindices α , β   we will write β ≤ α   if α − β   has only nonnegative entries.
By a Ferrers diagram F   we understand a finite subset F ⊂ N n   such that if α ∈ F   , β ≤ α   then β ∈ F   .
Let F = { F j } j = 1 r   be a finite sequence of Ferrers diagrams, let P = { p j } j = 1 r   be the sequence of parwise different points in K n   . The interpolation ideal assigned to F   and P   is the ideal I = { f ∈ K [ x 1 , . . . , x n ] : ∂ | α | f ∂ x α ( p i ) = 0 , α ∈ F i , i = 1 , . . . , r } .   Let us introduce the multivariate Hermite interpolation problem, that is the problem of finding a basis B = B ( F , P )   of K [ x 1 , . . . , x n ] / I   as a vector space over K   . The classical approach is to compute the Grobner basis of I   with respect to an admissible ordering (cf. [4] ). This method gives a minimal basis (with respect to the chosen admissible ordering) of the quotient space.
However, due to time complexity, it is not very practical.
Consider the sequence of Ferrers diagrams F   and an admissible ordering.
The basis B   depends on the sequence of points P ∈ ( K n ) r   , but there exists one special basis (called the generic basis) which is the same for almost all P   , that is for P   in a Zariski open, dense subset of ( K n ) r   . The problem of finding the interpolation basis (generic or not) for the lexicographical ordering without using the Buchberger’s algorithm was solved in [5] (the non-generic case) and [3] (the generic case).
For a total degree ordering the methods of finding the interpolation basis without the Buchberger algorithm are not known. An important question that arises here is:
How can we characterize the sequences of Ferrers diagrams for which the generic basis B   of interpolation is contained in the set { α : | α | ≤ d }   ?
If we assume that all Ferrers diagrams are of the form { α : | α | ≤ m }   then this problem is closely related to the problem of finding the actual dimension of the space of hypersurfaces (in K n   ) of degree d   having generic singularities of multiplicity m   (homogeneous generic singularities problem) or up to multiplicity m   (inhomogeneous generic singularities problem).
The last problem was solved by J. Alexander and A. Hirschowitz ([1] , [2] ) who showed that for the number of singularities large enough this dimension is the expected dimension, however they do not give a bound for the number of singularities needed. For some cases the problem was studied in many other papers. The homogeneous case for n = 2   , m ≤ 12   is completed in [6] , the inhomogeneous case for n = 2   , m ≤ 4   in [8] . A more computational approach to this problem can be found in [10] and [9] .
We present an effective criterion for the sequence F   to have the desired form of the basis B   . As a result we present new proofs for the inhomogeneous generic singularities problem for m ≤ 12   together with the bound for the number of singularities needed. Moreover, for arbitrary m   we give the bound for sufficient number of singularities of multiplicity k ≤ 12   :
Theorem 1. Let Γ d , p 0 , . . . , p m   denote the space of all plane curves of degree d   passing through p 0   generic points and having p j   generic singularities of order j   , for j = 1 , . . . , m   . Let 0 ≤ k ≤ 12   , k ≤ m   .
There exists r ( m , k )   , r ( m , k ) ≤ max { 6 ( m + 1 ) , 4 ( m + 1 ) ( 2 m + 1 ) ( k + 1 ) ( k + 2 ) }   such that if p k > r ( m , k )   then Γ d , p 0 , . . . , p m   has the expected dimension (as a vector space over base field) equal to dim Γ d , p 0 , . . . , p m = max { 0 , ( d + 1 ) ( d + 2 ) 2 − ∑ k = 0 m p k ( k + 1 ) ( k + 2 ) 2 } .  
We discuss the method of finding such bounds, and present the strict values for k , m ≤ 7   . Our method is a new one, we do not refer to the methods used in other papers.
In sections 2–4 we introduce the methods and prove lemmas used in section 5, which is the main section for this paper. An example of using our method for finding the basis B   for arbitrary sequence of Ferrers diagrams appears in section 6.

2 Generically correct problems.

For any monomial x α ∈ K [ x 1 , . . . , x n ]   , α ∈ N n   , a multiindex β ∈ N n   and a point a = ( a 1 , . . . , a n ) ∈ K n   we define φ ( x α , β , a ) = { α 1 ! ⋅ ⋯ ⋅ α n ! ( α 1 − β 1 ) ! ⋅ ⋯ ⋅ ( α n − β n ) ! a 1 α 1 − β 1 ⋅ ⋯ ⋅ a n α n − β n , if β ≤ α , 0 , otherwise.   φ ( x α , β , a )   is just a partial derivative of x α   with respect to β   taken at the point a   .
Let p 1 , . . . , p r   be r   distinct points (nodes) in K n   . Let F = { F i } i = 1 r   . Define a set of conditions C F = { ( p , β ) ∈ K n × N n : ∃ i ∈ I r p = p i , β ∈ F i } .   The cardinality of C F   (denoted by c   ) is equal to the sum ∑ i = 1 r # F i   . Let us assume that the set of monomials B ⊂ K [ X 1 , . . . , X n ]   of cardinality c   is given. We can order sets C F = { ( p , β ) 1 , . . . , ( p , β ) c }   and B = { x α 1 , . . . , x α c }   and define the matrix M = [ a k , ℓ ] k = 1 , . . . , c ℓ = 1 , . . . , c ,   where a k , ℓ = φ ( x α ℓ , β , p )   , ( p , β ) = ( p , β ) k   . We say that the interpolation problem for the sequence of Ferrers diagrams F   and the set of monomials B   is correct (shortly ( F , B )   is correct) if det M ≠ 0   . Of course the correctness of the interpolation problem does not depent on ordering of F   and B   .
Let us make the following observation. The interpolation problem is correct if and only if the following is true:
For any set of values (of cardinality c   ) we can find a polynomial P   in the linear space spanned by B   over K   having prescribed values and derivatives in each node. The matrix M   is just the matrix of the linear equation solving this problem, and B   is the basis of the quotient space K [ x 1 , . . . , x n ] / I   , where I   is the interpolation ideal.
The determinant of the matrix M   can be considered as a polynomial of n r   coordinates of nodes, say det M ∈ K [ p 1 1 , . . . , p 1 n , p 2 1 , . . . , p 2 n , . . . , p r 1 , . . . , p r n ]   .
We say that the interpolation problem ( F , B )   is generically correct if det M   is a nonzero polynomial.
Observe that ( F , B )   is generically correct if and only if there exists a set of nodes P   for which ( F , B )   is correct, and if and only if it is correct for the set of points from a Zariski open, dense subset of ( K n ) r   . Hence B   is a generic basis for interpolation.
Let F   be a Ferrers diagram, B   a set of monomials, B ′ = { x α 1 , . . . , x α k } ⊂ B   , # B ′ = # F   . We say that B ′   is exceptional in B   with respect to F   if the following conditions are fulfilled:
1. For any P = { x β 1 , . . . , x β k } ⊂ B   , P ≠ B ′   such that ∏ i = 1 k x α i = ∏ i = 1 k y β i   the problem ( { F } , P )   is not generically correct, 2. The problem ( { F } , B ′ )   is generically correct.
Theorem 2. Let ( F , B )   be a generically correct interpolation problem, let P   be a set of monomials, let F   be a Ferrers diagram.
Denote F ′ = F ∪ { F }   (this is not the sum of sets, but adding an element to the sequence), B ′ = B ∪ P   . If B ∩ P = ∅   , # F = # P   and P   is exceptional in B ′   with respect to F   , then the problem ( F ′ , B ′ )   is generically correct.
In the proof we will use the following Lemma:
Lemma 3 (generalized Laplace rule). Let M ∈ ℳ ( n , n ; K )   be a square matrix, let k ∈ N   , 1 ≤ k < n   . Denote M = [ M 1 M 2 ] ,   where M 1 ∈ ℳ ( k , n ; K )   and M 2 ∈ ℳ ( n − k , n ; K )   . Let S = { ( a 1 , . . . , a k ) : a i ∈ I n , a 1 < a 2 < ⋅ ⋅ ⋅ < a k }   be the set of all possible chosing of k   columns (without order). Let m 1 S   be the minor of M 1   determined by S ∈ S   , m 2 S   be the n − k × n − k   minor of M 2   determined by I n \ S   . Then det M = ∑ S ∈ S sgn ( s ( S ) ) m 1 S m 2 S ,   where sgn ( s ( S ) ) = ± 1   , s ( S )   being a permutation s ( S ) = ( 1 2 . . . k k + 1 . . . n a 1 a 2 . . . a k b 1 . . . b n − k )   with b 1 , . . . , b n − k   being numbers from I n \ S   in increasing order.
Proof. (Theorem  2 ). Denote by M   the matrix corresponding to the problem ( F , B )   , by M ′   the enlarged matrix corresponding to the problem ( F ′ , B ′ )   . Let c = # P   , s = # B   . Observe that M ′   is of the following form:
M ′ = [ M K 1 K 2 N ] ,   where K 1   is the matrix with s   rows corresponding to the conditions from C F   and c   columns assigned to new monomials from P   , K 2   is the matrix with c   rows corresponding to the conditions from F   and s   columns corresponding to the monomials from B   . The matrix N   is just the matrix of the ( { F } , P )   problem. In the last c   rows we have the new indeterminates (adding F   to F   is adding a new independent node to interpolation). From the generalized Laplace rule the determinant of M ′   is the sum of all possible c   -minors (i. e. minors of rank c   ) from the matrix [ K 2 N ]   multiplicated by a suitable minor from the matrix [ M K 1 ]   (with coefficients 1   or − 1   ) (see Lemma  3 ). It is easy to see that every c   -minors from [ K 2 N ]   is a monomial with coefficient (possibly equal to 0   ). This monomial is determined only by choosing c   columns (that is, c   monomials from B ′   ) and is equal to the product of chosen c   monomials divided by some monomial depending only on F   . The determinant of N   is a monomial with nonzero coefficient (this follows from the assumption). If any other minor gives the same monomial then the product of c   chosen monomials is equal to the product of c   last monomials, hence this minor is zero (this follows from the assumption that P   is exceptional). Consequently considering det M   as a polynomial of new indeterminates with coefficients being old indeterminates, the monomial det N   has a coefficient det M   which is nonzero. □   Proof. (Lemma  3 ). Let S j   denote the group of permutations of I j   . We have the correspondence S k × S n − k × S ∋ ( η 1 , η 2 , S ) ↦ η 1 ¯ ∘ η 2 ¯ ∘ s ( S ) ∈ S n ,   where
η 1 ¯ ( i ) = { η 1 ( i ) , i ≤ k i , i > k ,
η 2 ¯ ( i ) = { η 2 ( i − k ) + k , i > k i , i ≤ k .
Observe that the above correspondence is one-to-one. Let M = [ a i , j ]   .
From the definition det M = ∑ σ ∈ S n sgn ( σ ) a 1 , σ ( 1 ) ⋅ ⋯ ⋅ a n , σ ( n ) .   We can identify η 1   with η 1 ¯   , η 2   with η 2 ¯   . Proceeding with the deteminant we have
det M = ∑ S ∈ S ∑ η 1 ∈ S k , η 2 ∈ S n − k sgn ( s ( S ) ) ⋅ sgn ( η 1 ) ⋅ sgn ( η 2 ) ⋅
⋅ a 1 , η 1 ( S ( 1 ) ) ⋅ ⋯ ⋅ a k , η 1 ( S ( k ) ) ⋅ a k + 1 , η 2 ( S ( k + 1 ) ) ⋅ ⋯ ⋅ a n , η 2 ( S ( n ) ) .
Now we can sum up this equation with respect to η 1   obtaining the minor of M 1   given by S   , and then we can do the same for η 2   finishing the proof. □   Define F d n = { α ∈ N n : | α | < d }   . The cardinality of F d n   is equal to ( n + d − 1 n )   . We need the following lemma:
Lemma 4. Let n , d ∈ N   , n ≥ 1   , d ≥ 1   . Consider the set B   of ( n + d − 1 n )   monomials. The exponents of monomials from B   form a set B ′   in N n   . Then the interpolation problem ( { F d n } , B )   is generically correct if and only if the set B ′   does not lie on a hypersurface of degree d − 1   . In particular, for d = 1   ( { F 1 n } , { x α } )   is generically correct.
Proof. The determinant of the matrix M   assigned to the problem ( { F d n } , B )   is a monomial with coefficient. It is enough to calculate this coefficient. Let B ′ = { a i = ( a 1 i , . . . , a n i ) , i = 1 , . . . , r }   . For every condition α ∈ F d n   and point a i   the assigned entry in M   is equal to a 1 i ( a 1 i − 1 ) ( a 1 i − 2 ) ⋯ ︸ α 1 ⋅ a 2 i ( a 2 i − 1 ) ( a 2 i − 2 ) ⋯ ︸ α 2 ⋅ ⋯ ⋅ a n i ( a n i − 1 ) ( a n i − 2 ) ⋯ ︸ α n ,   where i   is the index of the column. Observe that by adding a suitable linear combination of rows assigned to all β ≤ α   we can obtain each entry equal to ( a 1 i ) α 1 ( a 2 i ) α 2 . . . ( a n i ) α n .   Since we take all α ∈ F d n   , we will find in M   all possible products of a 1 i , . . . , a n i   up to degree d − 1   . Now
det M ≠ 0 ⟺ the rows of M do not satisfy linear equation with
nonzero coefficient
⟺ the points from B ′ do not satisfy an equation of
degree d − 1 .
□  

3 Interpolation on the plane.

Assume now that n = 2   , F d : = F d 2   . For any finite sequence a 1 , . . . , a k   , a i ∈ I i   we define the diagram of type ( a 1 , . . . , a k )   by F = { α ∈ N 2 : ∃ i ∈ I k | α | = i − 1 , α 2 < a i } .   Observe that the diagram of type ( 0 )   is the empty diagram. For example, F   of type ( 1 , 2 , 2 )   is equal to { ( 0 , 0 ) , ( 1 , 0 ) , ( 0 , 1 ) , ( 2 , 0 ) , ( 1 , 1 ) }   . Define the type ( a ¯ , a 1 , . . . , a k ) : = ( 1 , 2 , . . . , a , a 1 , . . . , a k )   . For example ( 3 ¯ , 4 , 3 , 2 ) = ( 4 ¯ , 3 , 2 ) = ( 1 , 2 , 3 , 4 , 3 , 2 )   . F d   is of type ( d ¯ ) = ( 1 , 2 , 3 , . . . , d )   . We say that the diagram has at most k   steps if it is of type ( a ¯ , a 1 , . . . , a k )   , a ≥ a 1 ≥ a 2 ≥ ⋅ ⋅ ⋅ ≥ a k ≥ 0   . Any diagram with at most k   steps is a Ferrers diagram. We say that the diagram F   is k   -diagram if k ( k + 1 ) / 2 | # F   and F   has at most k   steps.
The lowest degree problem. With every Ferrers diagram F   we can assign a set of monomials S F = { x α : α ∈ F }   . Now we restrict our studies to the following situation:
Let d ≥ 1   . We want to solve an interpolation problem for a sequence of diagrams F d   , that is, we want to find a “good” set of monomials B   such that the problem ( { F d } k , B )   is generically correct. By “good” we understand the set given by a Ferrers diagram (of cardinality c = k d ( d + 1 ) / 2   ) with at most 1 step. This restriction is natural:
For the purpose of interpolation we want to use the set of c   first monomials with respect to total degree ordering. If the number of nodes multiplied by the cardinality of F d   coincides with the cardinality of some F ℓ   than we want this F ℓ   to be a “good” set of monomials. It is not always so, for example one can show that ( { F 2 } 2 , F 3 )   is not generically correct for interpolation.
However one can expect that for the number of nodes large enough the problem is generically correct for good set of monomials. We will solve this problem in the cases d = 1 , . . . , 13   , i. e. we will show that interpolating values and partial derivatives up to order 12   can be done using polynomials with the lowest possible degree. For d = 1 , 2 , 3   all initial cases will be proven here, for 4 ≤ d ≤ 13   a suitable computation can be done using a computer program.
We will say that the problem ( { F d } k , F )   is generically correct if the problem ( { F d } k , S F )   is generically correct. For a generically correct problem ( { F d } k , F )   we will say that F   is good for interpolating in k   nodes of type F d   .

4 Reductions.

We say that a d   -diagram F   of type ( a ¯ , a 1 , . . . , a d )   , ( a d > 0   ), is d   -reducible if the following holds: there exist v 1 , . . . , v d ∈ N   such that v i = max { ℓ : ℓ ∈ { 1 , . . . , d } , ℓ ≤ a i , ℓ ≠ v j for i < j ≤ d } .   If F   is d   -reducible then the diagram r ( F )   of type ( a ¯ , a 1 − v 1 , . . . , a d − v d )   will be called a d   -reduction of F   .
We say that a d   -diagram F   of type ( a ¯ , a 1 , . . . , a d )   is proper if a ≥ d   and ∀ i = 1 , . . . , k − 1   a i = a i + 1 ⟹ a i ≥ d   . A proper d   -diagram is safely proper if it is of type ( a ¯ , a 1 , . . . , a d )   , a ≥ 2 d   , a d > 0   .
Remark. Observe that ( 3 ¯ , 3 , 3 )   is not a proper 3   -diagram, such as ( 4 ¯ , 1 , 1 )   , but ( 3 ¯ , 3 , 3 , 3 )   is.
Remark. Observe how we can find a sequence ( v 1 , . . . , v d )   for reducing proper diagram. We start from v d   and then define all the v i   in decreasing order. As long as a i   is strictly smaller than v i   we take v i = a i   . When a i ≤ d   for v i   we choose the greatest number between 1   and d   that has not been used before.
If E   is a finite set of monomials then by degred ( E )   we will denote the degree of a product of monomials from E   , degred ( E ) = deg ∏ x α ∈ E x α .   Now we will show useful lemmas and a proposition:
Lemma 5. Every proper d   -diagram is d   -reducible.
Lemma 6. If F   is a safely proper d   -diagram then the d   -reduction of F   is a proper d   -diagram.
Proposition 7. Let F   be a proper d   -diagram, let F ′   be the d   -reduction of F   . Let S   be the set of monomials assigned to F   , S ′   be the set of monomials assigned to F ′   . Then S \ S ′   is exceptional in S   with respect to F d   .
Proof. (Lemma  5 ). Assume that F   of type ( a ¯ , a 1 , . . . , a d )   is proper but not reducible. Then there exists i , j ∈ I d   , i < j   such that a i = v j   . But then a i ≤ a j   implies a i ≥ d   , so it must exist v i   suitable for a i   , contradiction. □   Proof. (Lemma  6 ). It is easy to see that the d   -reduction of a diagram with at most d   steps is a diagram with at most d   steps. Also # r ( F ) = # F − d ( d + 1 ) / 2   , so r ( F )   is again a d   -diagram. Let F   be a diagram of type ( a ¯ , a 1 , . . . , a d )   , a d > 0   , a ≥ d   . Applying the reduction ( v 1 , . . . , v n )   to F   we have the following:
v i = a i ⟹ v j = a j for j > i , v i < a i ⟹ v 1 < v 2 < ⋅ ⋅ ⋅ < v i .   So some of a i   will be cancelled to 0   , all weak inequalities reduce to strong ones and all equalities a i + 1 = a i + 1   reduce to weak inequalities. The last may happen only for a i ≥ 2 d   , so if a i − v i = a i + 1 − v i + 1   then a i − v i ≥ d   . □   Proof. (Proposition  7 ). This proposition is fundamental. Together with Theorem  2 it allows the “induction step”.
Let E = S \ S ′   . We want to show that the problem ( { F d } , E )   is generically correct. The exponents of monomials (considered as points in N 2   ) lie on d   skew lines L 1 , . . . , L d   (with equations y + x + k = 0   for some k   ). We may assume that the line L i   contains exactly i   points from E   . Suppose that there exists a curve C   of degree d − 1   containing all these points. Then the intersection of L d   with C   has at least d   points, and then (by Bezout’s theorem, see [7] ) L d   must be a part of C   . Inductively the equation of C   must contain a product of all L i   , so it has degree at least d   , contradiction.
Now we want to satisfy the first condition. We will show that the method of choosing v i   used in the reduction gives strictly maximal possible degree ( degred ( E )   ) of product of reduced monomials not lying on a curve of degree d − 1   . In fact we will show (by induction with respect to k   ) that having chosen v k , . . . , v d   the procedure described above used for v 1 , . . . , v k − 1   gives the maximal possible degree.
Assume that v k , . . . , v d   have been chosen using the above procedure, and v k − 1 ′ ≠ v k − 1   is given. If v k − 1 ′ > v k − 1   then a k − 1 ≥ d   . Consider the following cases:
v k − 1 ′ > d   means that more than d   points lie on a line, so the remaining d ( d + 1 ) / 2 − v k − 1 ′ < d ( d − 1 ) / 2   points lie on a curve of degree d − 2   and all points lie on a curve of degree d − 1   .
v k − 1 ′ ≤ d   means that v k − 1 ′ = v i   for some i ≥ k   . In this case d ( d + 1 ) / 2 − i ( i + 1 ) / 2   points lie on d − i   lines, two sets (each consisting of i   ) points lie on two additional lines, and the remaining i ( i + 1 ) / 2 − 2 i = ( i − 1 ) ( i − 2 ) / 2 − 1   points lie on a curve of degree i − 3   . In conclusion all points lie on a curve of degree i − 3 + 2 + ( d − i ) = d − 1   .
The case v k − 1 ′ > v k − 1   has been excluded, now assume v k − 1 ′ < v k − 1   . We will apply the above method to obtain the maximal degree of product of reduced monomials. Consider two cases.
Case 1. a k − 1 ≥ d   . We will choose v i   for reduction. In the upper line we will write the original choice, in the lower that following v k − 1 ′   :
v d . . . v k v k − 1
v d . . . v k v k − 1 ′
. Of course the next number chosen in the upper line will be v k − 2   . In the lower line we choose the maximal possible number (by induction we know how to choose to obtain the maximal degree), which is now v k − 1   . We can follow this until the choice of v k − 1 ′   in the upper line is made. If this happens, we have used the same numbers in both lines, and from now on we are choosing the same way:
v d . . . v k v k − 1 v k − 2 . . . v k − ℓ v k − 1 ′ v k − ℓ − 2 . . . v 1
v d . . . v k v k − 1 ′ v k − 1 . . . v k − ℓ + 1 v k − ℓ v k − ℓ − 2 . . . v 1
Denote the degree of the largest reduced monomial by s   , let p = s − d   . The degree of the product while reducing as in the first line is D 1 = ∑ i = k d v i ( p + i ) + ∑ i = k − ℓ k − 1 v i ( p + i ) + v k − 1 ′ ( p + k − ℓ − 1 ) + ∑ i = 1 k − ℓ − 2 v i ( p + i ) .   The same for the second line is D 2 = ∑ i = k d v i ( p + i ) + v k − 1 ′ ( p + k − 1 ) + ∑ i = k − ℓ k − 1 v i ( p + i − 1 ) + ∑ i = 1 k − ℓ − 2 v i ( p + i ) .  
D 1 − D 2 = ∑ i = k − ℓ k − 1 v i ( p + i − ( p + i − 1 ) ) +
+ v k − 1 ′ ( p + k − ℓ − 1 − ( p + k − 1 ) ) =
= ( ∑ i = k − ℓ k − 1 v i ) − v k − 1 ′ ℓ > ( ∑ i = k − ℓ k − 1 v k − 1 ′ ) − v k − 1 ′ ℓ = 0 ,
which proves case 1.
Case 2. a k − 1 < d   means a k − 1 = v k − 1   and for some k − 1 > i > ℓ 1   we have a i = v i   , so we choose this v i   in both lines. Now in each step we choose the largest possible number, which can be the same in both the upper and lower line for i = ℓ 1 , . . . , ℓ 2   .
v d . . . v k v k − 1 v k − 2 . . . v ℓ 1 + 1 v ℓ 1 v ℓ 1 − 1 . . . v ℓ 2
v d . . . v k v k − 1 ′ v k − 2 . . . v ℓ 1 + 1 v ℓ 1 v ℓ 1 − 1 . . . v ℓ 2
Originally, in the upper line, we now choose v ℓ 2 − 1   . In the lower line we can choose v k − 1   , which is now the greatest and has not been chosen yet. Then we choose with a “shift” until v ℓ 3 = v k − 1 ′   in the upper line is chosen. When this happens the same situations occurs in both lines.
. . . v k v k − 1 v k − 2 . . . v ℓ 2 v ℓ 2 − 1 v ℓ 2 − 2 . . . v ℓ 3 v ℓ 3 − 1 . . . v 1
. . . v k v k − 1 ′ v k − 2 . . . v ℓ 2 v k − 1 v ℓ 2 − 1 . . . v ℓ 3 + 1 v ℓ 3 − 1 . . . v 1
Let s   denote again the greatest degree of reduced monomial, let p = s − d   .
Then
D 1 = ∑ i = k d v i ( p + i ) + v k − 1 ( p + k − 1 ) + ∑ i = ℓ 2 k − 2 v i ( p + i ) +
+ ∑ i = ℓ 3 + 1 ℓ 2 − 1 v i ( p + i ) + v ℓ 3 ( p + ℓ 3 ) + ∑ i = 1 ℓ 3 − 1 v i ( p + i ) ,
D 2 = ∑ i = k d v i ( p + i ) + v k − 1 ′ ( p + k − 1 ) + ∑ i = ℓ 2 k − 2 v i ( p + i ) +
+ v k − 1 ( p + ℓ 2 − 1 ) + ∑ i = ℓ 3 + 1 ℓ 2 − 1 v i ( p + i − 1 ) + ∑ i = 1 ℓ 3 − 1 v i ( p + i ) .
D 1 − D 2 = v k − 1 ( p + k − 1 ) − v k − 1 ′ ( p + k − 1 ) +
+ v ℓ 3 ( p + ℓ 3 ) − v k − 1 ( p + ℓ 2 − 1 ) + ∑ i = ℓ 3 + 1 ℓ 2 − 1 v i >
> v k − 1 ( k − ℓ 2 ) + v ℓ 3 ( ℓ 3 − k + 1 ) + ∑ i = ℓ 3 + 1 ℓ 2 − 1 v ℓ 3 =
= v k − 1 ( k − ℓ 2 ) + v ℓ 3 ( ℓ 3 − k + 1 + ℓ 2 − ℓ 3 − 1 ) =
= ( k − ℓ 2 ) ( v k − 1 − v ℓ 3 ) ≥ 0 .
We have shown the following: Let F   be a reducible d   -diagram of type ( a ¯ , a 1 , . . . , a d )   with reduction v 1 , . . . , v d   . Choose a set E ′   of monomials from F   having the three following properties:
  • (1) # E ′ = d ( d + 1 ) / 2   ,
  • (2) exponents of monomials from E ′   do not lie on a curve of degree d − 1   ,
  • (3) degred ( E ′ ) = degred ( E )   .
Let δ = max { deg x α : x α ∈ F }   . Let w i = # { x α : x α ∈ E , deg x α = i }   . Then w δ − j = v d − j   for j = 0 , . . . , d − 1   . In conclusion, if we want to choose the set of monomials E ′   with above properties, we must choose v d   monomials with maximal degree, v d − 1   monomials with degree δ − 1   and so on. Among chosen monomials with prescribed degrees our reduction choses the monomials with the greatest possible product of the second coordinate. This proves that E   is exceptional. □   Now we can formulate and prove the main technical theorem.
Theorem 8. Let p , d   be positive integers. Assume that for every proper d   -diagram F   of cardinality p d ( d + 1 ) / 2   the following conditions are satisfied:
  • (1) F   is safely proper,
  • (2) the problem ( { F d } p , F )   is generically correct.
Then for any k ≥ p   the diagram F   of cardinality k d ( d + 1 ) / 2   with at most 1 step is good for interpolation, that is the problem ( { F d } k , F )   is generically correct.
Proof. Let F   be a diagram of cardinality k d ( d + 1 ) / 2   with at most 1 step.
Assume that the problem ( { F d } k , F )   is not generically correct. Naturally F   is a proper diagram and can be reduced k − p   times to a proper d   -diagram G   of cardinality p d ( d + 1 ) / 2   (Lemmas  5 and  6 ). Each reduction produces a diagram which is not good for interpolation (Proposition  7 and Theorem  2 ).
Hence the problem ( { F d } p , G )   is not generically correct, which contradicts the assumption. □  

5 Main results.

Now we solve the problem for d = 1 , 2 , 3   by showing all initial cases. For d = 1   (Lagrange interpolation) it is enough to observe that every 1   -diagram is 1   -reducible and eventually reduces to the diagram of type ( 1 )   .
Theorem 9. The problem ( { F 2 } k , F )   is generically correct for F   with at most 1 step if and only if k / ∈ { 2 , 5 }   . In other words, we can interpolate values and first order derivatives using polynomials with the lowest possible degree in any number of points apart from the case of 2   or 5   points.
Proof. We can check by direct computation that all 2   -diagrams of cardinality 18   are good for interpolation. However we present here another method not requiring computation of any determinant. A 2   -diagram of cardinality 15 is one of the following: F 1 = ( 5 ¯ )   , F 2 = ( 4 ¯ , 4 , 1 )   , F 3 = ( 4 ¯ , 3 , 2 )   . It is easy to see that the first diagram can be obtained as a reduction of a proper 2   -diagram of type ( 5 ¯ , 2 , 1 )   only. The ( 5 ¯ , 2 , 1 )   diagram can be obtained only from ( 5 ¯ , 3 , 3 )   which is not a reduction of another proper 2   -diagram. In conclusion if we reduce a 2   -diagram with at most one step to the diagram of cardinality 15   we obtain either F 2   or F 3   . So it is enough to prove that these diagrams are good for interpolation. Both F 2   and F 3   reduce to ( 4 ¯ , 2 )   . Then the reduction goes as follows:
( 4 ¯ , 2 ) → ( 3 ¯ , 3 ) → ( 2 ¯ , 2 , 1 ) → ( 2 ¯ )   which is obviously good for interpolating in one point. In view of Theorem  8 we have proven our statement for k > 5   . For k = 1 , 3 , 4   the corresponding diagrams are ( 2 ¯ )   , ( 3 ¯ , 3 )   , ( 4 ¯ , 2 )   and we have shown they are good. For k = 2 , 5   we can calculate the determinant, but the next remark will prove that case.
□   Remark. Consider a plane curve (can be reducible) of degree d   . It has ( d + 1 ) ( d + 2 ) / 2   monomials. If d   is not divisible by three then the last number is divisible by three, let p = ( d + 1 ) ( d + 2 ) / 6   . If p > 5   (which gives d > 4   ) then the problem ( { F 2 } p , F d )   is generically correct. Hence for a generic set of p   points the determinant is nonzero, so the only solution for a set of values and derivatives equal to 0 is a zero polynomial. This shows that a curve of degree greater than 4 (and not divisible by 3) cannot have ( d + 1 ) ( d + 2 ) / 6   singularities in general position. For the case d = 4   we can take the double conic passing through general 5 points, and for d = 2   the double line passing through any 2 points, so determinant of the matrix in these cases is equal to 0   . For d = 3 n   we have the following: the curve of degree d   having ( ( d + 1 ) ( d + 2 ) − 2 ) / 6   generic singularities cannot pass through additional generic point.
Remark. We can consider the problem of interpolating values in p 1   nodes and values with first order derivatives in p 2   nodes, that is the problem ( { F 1 , . . . , F 1 ︸ p 1 , F 2 , . . . , F 2 ︸ p 2 } , F )   , where F   is a complementary diagram with at most one step. If p 2 / ∈ { 2 , 5 }   then we can first 1   -reduce the diagram F   p 1   times to obtain a diagram with at most 1 step and then use Theorem  9 . It is easy to see that the only not 2   -reducible diagram of cardinality greater than 2 is of type ( a ¯ , 1 , 1 )   . If it is a reduction of another diagram then a = 1   , and the last diagram is good for interpolating values in 3 points. We have shown that if p 1 ≥ 3   or p 2 / ∈ { 2 , 5 }   then F   is good for interpolation. In fact only ( p 1 , p 2 ) ∈ { ( 0 , 2 ) , ( 0 , 5 ) }   cannot be interpolated by a diagram with at most 1 step.
Theorem 10. The problem ( { F 3 } k , F )   is generically correct for F   with at most 1 step if and only if k / ∈ { 2 , 5 }   .
Proof. Again we will consider all 3   -diagrams of cardinality 30 (that is diagrams for interpolating in 5 points) that can be achieved as a sequence of reductions of a 3   -diagram with at most 1 step. Here are the list of them:
( 5 ¯ , 5 , 5 , 5 ) , ( 6 ¯ , 3 , 3 , 3 ) , ( 6 ¯ , 4 , 3 , 2 ) , ( 6 ¯ , 4 , 4 , 1 ) ,
( 6 ¯ , 5 , 3 , 1 ) , ( 6 ¯ , 5 , 4 ) , ( 6 ¯ , 6 , 2 , 1 ) , ( 6 ¯ , 6 , 3 ) .
In fact there are three another diagrams of cardinality 30   with at most 3   steps: ( 6 ¯ , 5 , 2 , 2 )   , ( 7 ¯ , 1 , 1 )   , ( 7 ¯ , 2 )   . Two of them are not proper, the last can be obtained from one of the following:
F 1 = ( 7 ¯ , 3 , 3 , 2 ) F 2 = ( 7 ¯ , 4 , 3 , 1 ) F 3 = ( 7 ¯ , 5 , 2 , 1 ) .   F 1   cannot be obtained from a 3   -diagram, F 2   is a reduction of ( 7 ¯ , 5 , 5 , 4 )   which is not a reduction of a 3   -diagram, F 3   can be produced from ( 7 ¯ , 6 , 4 , 4 )   which again is not a result of reduction.
The diagram ( 5 ¯ , 5 , 5 , 5 )   1 reduces to ( 5 ¯ , 4 , 3 , 2 ) → ( 5 ¯ , 3 )   which is good for interpolating in 3   nodes (Lemma  11 ). Another reductions:
( 6 ¯ , 3 , 3 , 3 ) → ( 6 ¯ , 2 , 1 ) → ( 5 ¯ , 3 ) ,
( 6 ¯ , 4 , 3 , 2 ) → ( 6 ¯ , 3 ) → ( 4 ¯ , 4 , 4 ) → ( 3 ¯ , 3 , 2 , 1 ) → ( 3 ¯ ) ,
( 6 ¯ , 4 , 4 , 1 ) → ( 6 ¯ , 2 , 1 ) ,
( 6 ¯ , 5 , 3 , 1 ) → ( 6 ¯ , 3 ) ,
( 6 ¯ , 5 , 4 ) → ( 5 ¯ , 5 , 3 , 1 ) → ( 5 ¯ , 3 ) ,
( 6 ¯ , 6 , 2 , 1 ) → ( 6 ¯ , 3 ) .
The last ( 6 ¯ , 6 , 3 )   diagram will be done in Lemma  12 . This shows the correctness of an interpolation problem for at least 6   nodes. For k = 1 , 3 , 4   the corresponding diagrams are ( 3 ¯ )   , ( 5 ¯ , 3 )   and ( 6 ¯ , 3 )   , which are also good for interpolation. □   Remark. Again we can consider the problem of interpolating values in p 1   point, values and first order derivatives in p 2   points, values and derivatives up to order two in p 3   points. It it easy to see that for suitably large p i   for some i ∈ I 3   the problem is generically correct. Using the above techniques one can show that p 1 > 9   , p 2 > 5   or p 3 > 5   is enough. All exceptional triples also can be found:
( 0 , 2 , 0 ) ( 0 , 5 , 0 ) ( 0 , 1 , 1 ) ( 1 , 1 , 1 ) ( 0 , 0 , 2 ) ( 1 , 0 , 2 ) ( 2 , 0 , 2 )   ( 3 , 0 , 2 ) ( 0 , 1 , 2 ) ( 0 , 3 , 2 ) ( 0 , 1 , 4 ) ( 1 , 1 , 4 ) ( 0 , 0 , 5 ) .  
Lemma 11. The problem ( { F 3 } 3 , ( 5 ¯ , 3 ) )   is generically correct.
Proof. To F = ( 5 ¯ , 3 )   we apply the reduction ( 1 , 3 , 2 )   instead of ( 1 , 2 , 3 )   .
Let D   be the degree of a product of reduced monomials. In this case D = 25   .
Let us choose 6   monomials from F   such that the degree of their product is greater or equal to 25   . Moreover, assume that these monomials do not lie on a conic. The only possibility to do that is to choose 2   monomials of degree 5   , 3   of degree 4   and 1   of degree 3   (like in our reduction ( 1 , 3 , 2 )   ), the other is to choose 3   monomials of degree 5   . But now the degree of the first coordinate in the product of chosen monomials is at least 12   , while originally it is equal to 10   . This shows that the set of chosen monomials is exceptional.
( 5 ¯ , 3 ) ⟶ ( 1 , 3 , 2 ) ( 3 ¯ , 3 , 2 , 1 ) → ( 3 ¯ ) ,   which completes the proof. □  
Lemma 12. The problem ( { F 3 } 5 , ( 6 ¯ , 6 , 3 ) )   is generically correct.
Proof. Again the first reduction will be ( 1 , 3 , 2 )   reduction. In this case the same argument works, namely the degree of the first variable in product of chosen monomials is equal to 17, while the product of three monomials of maximal degree gives 18. So ( 6 ¯ , 6 , 3 ) ⟶ ( 1 , 3 , 2 ) ( 5 ¯ , 5 , 3 , 1 ) → ( 5 ¯ , 3 )   and use Lemma  11 . □   Now we can formulate the main theorem for the homogeneous conditions.
Theorem 13. Let 1 ≤ d ≤ 13   . For any set of nodes of cardinality k   greater than six the interpolation problem ( { F d } k , F )   is generically correct for F   with at most 1 step. Additionally, if d ≤ 9   then the problem ( { F d } 6 , F )   is generically correct for F   with at most 1   step.
Proof. For d ≤ 3   the proofs were presented here. For greater value of d   more complicated computations are needed. To deal with all initial cases we used a suitable computer program. First, it produced all proper d   -diagrams for k 1   points. All these diagrams, being safely proper, were then reduced to ℓ ( k 1 , k 2 )   safely proper d   -diagrams for k 2 < k 1   points (this operation greatly reduced the number of determinants to be computed). To that list all reductions of diagrams with at most 1 step for 6 , . . . , k 1 − 1   points were added. Finally the program checked all determinants. Here is the table which contains the number of cases ( # k i   denotes the number of proper d   -diagrams for k i   points):
d k 1 # k 1 k 2 # k 2 ℓ ( k 1 , k 2 )
2 6 2 − − − − 2
3 6 4 − − − − 4
4 13 52 6 9 4
5 20 899 6 21 5
6 20 6471 6 60 7
7 20 48274 6 175 12
8 20 369629 6 524 23
9 20 2887492 6 1571 41
10 16 5755270 6 4811 189
11 14 15296608 6 14918 714
12 13 53382738 6 46707 2349
13 11 71128794 6 147123 19787
Remark. The same method can be used for larger values of d   , but the time used for computation is deteriorating. For d = 10 , . . . , 13   the problem ( { F d } 6 , F )   for F   with at most one step is not generically correct. We need at least 7   nodes.
If we want to interpolate with ”mixed” conditions we can use the following Theorem.
Theorem 14. Let S = { F j }   be a finite sequence of diagrams, F j = F s ( j )   . Let n ( ℓ ) = # { j : s ( j ) = ℓ }   . Assume that for some d , p   the problem ( { F d } p , F )   is generically correct for any d   -diagram F   . Let D = max { ℓ : n ( ℓ ) ≠ 0 }   . Define h   as the least natural number such that h ≥ 2 D , h ( h + 1 ) > ( p − 1 ) d ( d + 1 ) .   Take q ∈ N   such that q > h ( h − 1 ) + 2 D ( h − 1 ) d ( d + 1 ) .   If n ( d ) ≥ q   then the problem ( S , F )   is generically correct for a suitable F   with at most 1 step.
Proof. We want to reduce F   with all needed e   -reductions for e ≠ d   to F ′   , then d   -reduce F ′   to one of the d   -diagrams. To do so, we must first know that every e   -reduction is possible for e ≤ D   . It is true as long as the diagram being reduced is of type ( a ¯ , a 1 , . . . , a D )   , a ≥ 2 D   . If a < 2 D   then the D   -diagram of type ( a ¯ , a 1 , . . . , a D )   has at most ( 2 D − 1 ) 2 D / 2 + D ( 2 D − 1 )   points. On the other hand our diagram has at least q d ( d + 1 ) / 2   points, contradiction. Now assume that F ′   is of type ( a ¯ , a 1 , . . . , a D )   . While F ′   has more than d   steps the d   -reduction does not change a   . It is enough to choose a   such that every diagram of type ( a ¯ , a 1 , . . . , a d )   contain more than ( p − 1 ) d ( d + 1 ) / 2   points.
The cardinality of such diagram is at least a ( a + 1 ) / 2   . We can see that q   was chosen to allow both to reduce F   to F ′   and then safely d   -reduce F ′   . □   Remark. For d = 1   it is enough to take q > 2 D ( 2 D − 1 )   , for d = D   taking q ≥ p   is also enough, provided that all d   -diagrams for p   points are safely proper.
Now we are able to proof the Theorem  1 .
Proof. Observe that, following the notations from Theorem  14 , if h = 2 D   then q > h ( h − 1 ) + 2 D ( h − 1 ) d ( d + 1 ) = 4 D ( 2 D − 1 ) d ( d + 1 ) .   Otherwise, if h > 2 D   and D ≥ 2   then h ( h − 1 ) + 2 D ( h − 1 ) d ( d + 1 ) < D h ( h − 1 ) d ( d + 1 ) ≤ D ( p − 1 ) d ( d + 1 ) d ( d + 1 ) ,   so taking q > D ( p − 1 )   is enough. For D = 1   also q > D ( p − 1 )   is enough.
Now taking D = m + 1   , d = k + 1   and p = 7   we complete the proof. □   Remark. Here are the exact values of r ( m , k )   for small m , k   :
k 0 1 2 3 4 5 6 7
m
0 0 − − − − − − −
1 0 5 − − − − − −
2 3 5 5 − − − − −
3 8 6 5 6 − − − −
4 15 6 5 6 5 − − −
5 24 8 6 7 5 7 − −
6 35 11 6 7 6 7 6 −
7 48 16 8 7 6 7 6 7
All exceptions were found by a computer program using bounds from Theorem  14 and reduction methods. If the reduction fails the determinant was computed. This, together with some more sophisticated methods2 , allows to reduce the time of computation considerably. The values computed with Theorem  14 are certainly not optimal. We can better them by refining arguments used in the proof of Theorem  14 or by investigating ”mixed initial cases”:
Theorem 15. Let p , d , D   be nonzero natural numbers. Assume that every diagram F   of cardinality p d ( d + 1 ) / 2   with at most D   steps has the following properties:
  • (1) F   is safely proper (with respect to D   ),
  • (2) the problem ( { F d } p , F )   is generically correct.
Let S   be any sequence of Ferrers diagrams containing at least p   diagrams of type ( d ¯ )   and only diagrams of type ( k ¯ )   for k ≤ D   . Then the diagram F   of suitable cardinality with at most 1 step is good for interpolation, that is the problem ( S , F )   is generically correct.
Proof. Use techniques similar to that used in proof of Theorem  8 . □   Remark. It is enough to assume that F   is proper (not necessarily safely proper) with respect to D   . Here are the values of bounds for r ( m , k )   obtained from Theorem  15 :
k 0 1 2 3 4 5 6 7
m
0 0 − − − − − − −
1 2 5 − − − − − −
2 9 5 5 − − − − −
3 18 6 5 6 − − − −
4 30 10 6 6 5 − − −
5 45 15 7 7 5 8 − −
6 63 21 10 7 6 7 7 −
7 84 28 14 8 6 7 6 7

1 This diagram is not safely proper, but every diagram that reduces to it is safely proper.

2 for example one can create a list of ”good” diagrams for small number of points and then try to reduce to one of these diagrams

6 Constrained correctness.

For a finite sequence S   of Ferrers diagrams, S = { F i } i = 1 k   , F i = F d i   , define the diagram F S = { ( α 1 + ⋯ + α k , β ) ∈ N 2 : ( α i , β ) ∈ F i , i = 1 , . . . , k } .   Each level in F S   is a sum of levels of diagrams from S   . The cardinality of F S   is equal to ∑ i = 1 k d ( i ) ( d ( i ) + 1 ) / 2   , so we can consider the problem ( S , F S )   .
Theorem 16. The problem ( S , F S )   is generically correct.
Remark. The diagram F S   is the minimal diagram for generic interpolation for lexicographical ordering (see [3] ).
Proof. Let S ′ = { F i } i = 1 k − 1   . Define R = F S \ F S ′   . It is easy to see that R   is a set of multiindices from F S   with d ( k )   points on the lowest level ( N × { 0 }   ), d ( k ) − j   points on the level N × { j }   . The same method as in the proof of Proposition  7 can be applied. Namely, we choose d ( k ) ( d ( k ) + 1 ) / 2   monomials with the lowest possible second exponent, not lying on a curve of degree d ( k ) − 1   . Among them we choose the monomials with the greatest first exponent. The only possible choice to do that is to choose the set R   . Also monomials from R   do not lie on a curve of degree d ( k ) − 1   . Hence, R   is exceptional in F S   with respect to F d ( k )   and we use induction. □   References

  1. Alexander J., Hirschowitz A.: An asymptotic vanishing theorem for generic unions of multiple points. Invent. Math. 140, 303-325 (2000)
  2. Alexander J., Hirschowitz A.: Polynomial interpolation in several variables. J. Algebraic Geometry 4, 201-222 (1995)
  3. Apel J.,Stuckrad J., Tworzewski P., Winiarski T.: Term bases for multivariate interpolation of Hermite type. Univ. Iagell. Acta Math. 37, 37-49 (1999)
  4. Becker T., Weispfenning V.: Grobner Bases. Springer-Verlag New York, 1993
  5. Cerlienco L., Mureddu M.: From algebraic sets to monomial linear bases by means of combinatorial algorithms. Discrete Math. 139 (1995)
  6. Ciliberto C., Miranda R.: Linear systems of plane curves with base points of equal multiplicity. Trans. Amer. Math. Soc. 352, 4037-4050 (2000)
  7. Fulton W.: Algebraic Curves. W. A. Benjamin, Inc. 1978
  8. Mignon T.: Systemes lineaires de courbes planes a singularites ordinaires imposees. CRAS 327, 651-654 (1998)
  9. Moller H. M., Sauer T.: H-bases for polynomial interpolation and system solving. Adv. Comput. Math. 12, 335-362 (2000)
  10. Sauer T.: Polynomial interpolation of minimal degree and Grobner bases. London Math. Soc. Lecture Notes Ser. 251, Cambr. Univ. Press, Cambridge (1998)