Facial Image Processing for Sleepiness Estimation

Natalia I. Vargas-Cuentas, Avid Roman-Gonzalez * Image Processing Research Laboratory (INTI-Lab), Universidad de Ciencias y Humanidades (UCH) * avid.roman-gonzalez@ieee.org Abstract-Sleepiness could cause different accidents at work and in our daily lives. Activities such as driving a car, handling heavy machinery, being in charge of controlling a satellite or monitoring a nuclear plant, are activities that require short visual and motor reaction times. These reactions could be affected by sleepiness. The highest number of these accidents is related to vehicular accidents. WHO statistics show that 1.2 million people worldwide die every year due to road crashes, 50 million people are injured, and more than 3,000 people die daily from road traffic injuries. The primary objective of the present work is to develop a tool based on techniques of artificial intelligence and image processing that can detect states of sleepiness in people whose work needs the greatest attention -to avoid accidents. The idea is to develop an algorithm that can be executed on a computer and through a webcam can record the face of the person or worker to analyze the video and through facial recognition techniques can identify the eyes of the person, and thus identify eyelashes that would be an indicator of sleepiness. It is expected to have an algorithm developed in MATLAB to detect drowsiness and provide some notification.

Keywords-Sleepiness, face detection, eye detection, vehicular accident, yes-no questions.

I. INTRODUCTIÓN

CCORDING to [START_REF] Horstmann | Sleepiness-related accidents in sleep apnea patients[END_REF], it can be seen that sleepiness is a cause for different accidents, especially motorized accidents. WHO statistics show that 1.2 million people worldwide die every year due to road crashes, 50 million people are injured, and more than 3,000 people die daily from road traffic injuries. (World report on the prevention of road traffic injuries, WHO 2004). Activities such as driving a car, handling heavy machinery, being in charge of moving a satellite or monitoring a nuclear plant are activities that require short visual and motor reaction times; these attitudes are affected by drowsiness.

According to [START_REF] De | Somnolencia y cansancio durante la conducción: accidentes de tránsito en las carreteras del Perú[END_REF], Peru's statistics indicate that in 2007 there were 3510 deaths due to traffic accidents and 49,857 injuries, most of them due to the tiredness of the drivers. One of the cities that suffers from these accidents due to drowsiness is Arequipa, which according to [START_REF] Caso | Hábitos del sueño y accidentes de tránsito en conductores de ómnibus interprovincial de Arequipa, Perú[END_REF] is the third city with more passengers flow. Faced with this reality, the Ministry of Transportation of Peru has created regulations that indicate that the maximum time of driving a car should be 5 hours in the day and 4 hours in the night, this is a rule that currently does not carry out in our country.

The implemented algorithm, capable of detecting the level of drowsiness of users, can prevent fatal accidents that can be more frequent due to fatigue and drowsiness. A business model will be developed to look for a selfsustaining project. This business model would be based on giving monitoring and information gathering services. As has been observed, drowsiness is a major cause of accidents that occur at work, especially in drivers of interregional public transportation. In that sense, many research groups around the world work on different tools to determine the fatigue of people and give warning signals to prevent the user from sleeping. In work [START_REF] King | Early driver fatigue detection from electroencephalography signals using artificial neural networks[END_REF] a system of fatigue detection is presented in the conductor through the analysis of electroencephalographic signals and using neural networks for their classification. The authors analyzed alpha, beta, delta, and theta rhythms. As a result, they achieved an 83.06% success rate in the standings. A more recent work is presented in [START_REF] Chang | Driver fatigue surveillance via eye detection[END_REF], where the authors present a method for the monitoring of driver fatigue through eye tracking. Computer vision and image processing techniques are used on images recorded by an infrared camera. In this paper, they also use a neural network for the classification of signals. The results that the authors obtained show a 97% success in the discrimination. Based on this background we developed a drowsiness detector based on the analysis of facial images. With the development of an algorithm with the ability to detect the face and eyes of people, and through determining the level of individuals drowsiness, it is expected to provide a tool to aid to reduce the number of workplace accidents. Likewise, with the help of the Internet and ICT, an efficient, cost-effective system with monitoring, alert, and reporting capacity will be offered. This paper is structured as follow. Section 2 presents the methodology used in this research. In Section 3 one shows the results obtained in the testing process. Section 4 one interprets the results although the discussion and conclusion for this study.

II. METHODOLOGY

The present project seeks to develop a system for monitoring, alert, and reporting levels of drowsiness for people. This evaluation system of levels of sleepiness is a noninvasive tool.

A

For this purpose, the study will consist of the following components:

1) Hardware.

2) An Algorithm for image analysis.

3) Development of APP for a mobile device. 4) Web server for data storage.

A. Acquisition of the images:

The implementation of the system with the ability to determine the degree of drowsiness of the people will be carried out using a mobile device (smartphone or tablet) with frontal camera. The algorithm of the image acquisition applies a preprocessing step for the improvement of the picture contrast.

B. Image Analysis:

For the image analysis, we will use algorithms that were already used for other applications such as [START_REF] Vargas-Cuentas | Diagnosis of Autism Using an Eye Tracking System[END_REF].

Likewise, feature extraction and classification algorithms are implemented. The entire process of image analysis begins with face detection. Face detection is performed using the Viola-Jones algorithm [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF]. The next step is to recognize both eyes; this step is also done using the Viola-Jones algorithm. Finally, the task is to identify the eyes individually, separating the left eye from the right eye. To be able to detect the eyes correctly, they must be open. In that sense, if the algorithm fails to detect eyes could be because, in the frame (image) that we are analyzing, the eyes are closed, which would imply that the person is blinking. The classification stage is the final task of the entire process. As the entry to the algorithm of classification or discrimination we have the set of features and the output is the level of drowsiness detected, among them, one can mention:

• K-NN (K-nearest neighbor)

• K-means • Artificial Neuronal Network • Support Vector Machine • Linear Discriminant Analysis

C. App for Mobile Devices:

It is also planned to develop an application (app) for mobile devices, which should be installed on the user's cell phone. This smartphone, using its front camera, will acquire the images and send the information through the internet to a server initially located in the Image Processing Research Laboratory (INTI-Lab) at Universidad de Ciencias y Humanidades (UCH ). Likewise, the application to be developed will be connected to the GPS service of the same mobile phone, to be able to provide such information for the reports that will be elaborated.

D. Web server for data storage

The server as information technology will allow storing text files that contain the personal data of each user, and other details that may be important to generate statistics and make correct decisions. This aspect will ensure an accurate monitoring and control of each user. Also, this information can be distributed to interested state entities to generate statistics such as the Ministry of Transport and Communications. The server will be implemented with the algorithms for the data processing.

III. RESULTS

Figure 1 shows the application of the presented methodology. In front of an image that includes the user's face, the algorithm first detects the face, then both eyes and finally the detection of the right eye and left eye separately. This situation is possible thanks to the person's eyes are open In the case of Figure 2, since the person has their eyes closed (possibly by blinking), the algorithm only recognizes the eye and the two eyes together without identifying the right eye and the left eye Independent. The project will contribute to the improvement of specialized technical capabilities for biomedical signal analysis in general. Among the applications and uses of this project, we can mention mainly the interprovincial transport companies. These companies could begin to monitor the fatigue of their drivers and have a tool to alert the drivers themselves to wake up or change drivers. Likewise, another possible use and application would be through the Ministry of Transport and Communications, who could apply this tool to monitor transport companies, also to have better statistics, and try to enforce established standards. In general, the companies, which in their production processes include tasks where it is needed a high concentration of the worker, could also make use the resulting prototype to avoid accidents due to the fatigue of its operators. The present project will have a critical technological impact for our country (Peru) since it would be the first time that a system of monitoring, warning and reporting of levels of drowsiness in people to prevent accidents will be developed. With the advancement of technology and the lowering costs of the materials used in the proposed prototype, it could even have an industry oriented to the commercialization of these systems. In this way, the country's economy could become more dynamic, establishing a self-sustaining business model.

The social impact will be imperative for this project, as it is expected to significantly reduce the number of accidents (often with human losses) caused by the fatigue and fatigue of people in dangerous jobs and who need high concentration. The society will be the primary beneficiary of the results of the present work. The realization of this project will not cause any harmful impact on our ecosystem. According to the results found, the efficiency of the algorithm of drowsiness estimation is enough to be able to use it in real conditions.

Figure 1 :

 1 Figure 1: Cascade detection when user's eyes are open

Figure 2 :

 2 Figure 2: Cascade detection when user's eyes are close

Acknowledgements

This work was supported by self-funding Universidad de Ciencias y Humanidades (UCH).


Enrico Carlini
email: enrico.carlini@polito.it

AND Maria Virginia Catalisano
email: catalisano@diptem.unige.it

Alessandro Oneto
email: alessandro.oneto@inria.fr

Disma

Dipartimento Di

ENERGETICA, GESTIONALE E DEI Ingegneria Meccanica

UNIVERSITÀ Trasporti

On the Hilbert function of general fat points in P 1 × P 1

Keywords: 2010 Mathematics Subject Classification. Primary 14C20, 15A69 Secondary 13A02, 13D02, 14N15 Hilbert functions, fat points, linear systems, Horace method

We study the bi-graded Hilbert function of ideals of general fat points with same multiplicity in 1 × 1 . Our first tool is the multiprojective-affine-projective method introduced by the second author in previous works with A.V. Geramita and A. Gimigliano where they solved the case of double points. In this way, we compute the Hilbert function when the smallest entry of the bi-degree is at most the multiplicity of the points. Our second tool is the differential Horace method introduced by J. Alexander and A. Hirschowitz to study the Hilbert function of sets of fat points in standard projective spaces. In this way, we compute the entire bi-graded Hilbert function in the case of triple points.

INTRODUCTION

Problems regarding polynomial interpolation are very classical and have been studied since the beginning of last century. In the classic case, we consider a set of points on the projective plane and we want to compute the dimension of the linear system of curves of given degree passing through the set of points with prescribed multiplicity. Sometimes, the linear conditions imposed by the the multiple points on the space of curves of given degree are not always independent. In these cases, we say that we have unexpected curves. In the case of less than 8 points, these cases were explained by G. Castelnuovo [START_REF] Castelnuovo | Ricerche generali sopra i sistemi lineari di curve piane[END_REF] and, more recently, in the work of M. Nagata [START_REF] Nagata | On rational surfaces, ii. Memoirs of the College of Science[END_REF]. In general, the situation is completely described by the famous SHGH Conjecture which takes the name after the works of B. Segre [START_REF] Segre | Alcune questioni su insiemi finiti di punti in geometria algebrica[END_REF], B. Harbourne [START_REF] Harbourne | Complete linear systems on rational surfaces[END_REF], A. Gimigliano [START_REF] Gimigliano | On linear systems of plane curves[END_REF] and A. Hirschowitz [START_REF] Hirschowitz | Une conjecture pour la cohomologie des diviseurs sur les surfaces rationnelles génériques[END_REF].

In the language of modern commutative algebra, this means to compute the Hilbert function of the ideal of fat points with prescribed multiplicity and look at its Hilbert function in a given degree. By parameter count, we expect that such a dimension is the difference between the dimension of the space of curves of the fixed degree and the number of conditions imposed by the fat points. If this is the actual dimension, we say that the set of fat points impose independent conditions on the linear system of curves of the fixed degree.

In this paper, we want to consider a multi-graded interpolation problem. We consider ideals of fat points in 1 × 1 with support in general position and we look at its bi-graded Hilbert function. The case of double points has been settled by the second author together with A.V. Geramita and A. Gimigliano [START_REF] Catalisano | Higher secant varieties of Segre-Veronese varieties[END_REF]. They introduced a method called multiprojective-affine-projective method which allows to reduce the multi-graded problem to a question in the standard projective plane.

A milestone for polynomial interpolation problems is the work by J. Alexander and A. Hirschowitz in which the authors considered ideals of double points in general position in the standard n-dimensional projective spaces. Exceptional cases where ideals of double points fail to give independent conditions on hypersurfaces of some degree were known since the beginning of last century, but we had to wait until 1995 for a complete classification which is now the so-called Alexander-Hirschowitz Theorem. The complete proof came after a series of enlightening papers where they developed a completely new method of approach called méthode d'Horace différentielle [AH92b, AH92a, AH95, AH00].

In our computations, we use the multiprojective-affine-projective method of [START_REF] Catalisano | Higher secant varieties of Segre-Veronese varieties[END_REF] to reduce the problem to the study of fat points in 2 , where we use the differential Horace method of [START_REF] Alexander | An asymptotic vanishing theorem for generic unions of multiple points[END_REF].

Formulation of the problem and main results. Let S = [x 0 , x 1 ; y 0 , y 1 ] = i, j S i, j be the bi-graded coordinate ring of 1 × 1 , namely S i, j is the vector space of bi-homogeneous polynomials of bi-degree (i, j). Definition 1.1. Let {P 1 , . . . , P s } be a set of points in 1 × 1 . We will always assume, except when explicitly mentioned, that they are in general position. Let ℘ i ⊂ S be the prime ideal defining the point P i , respectively. The scheme of fat points of multiplicity m ≥ 1 with support at the P i 's is the 0-dimensional scheme defined by the ideal

I , 1 × 1 = ℘ m 1 ∩ . . . ∩ ℘ m s .
If there is no ambiguity, we simply denote it by I . For short, we denote by HF the Hilbert function of the quotient ring S/I .

QUESTION. Let be a scheme of fat points of multiplicity m in 1 × 1 . What is the bi-graded Hilbert function of ?

It is well-known that if a, b 0, then the Hilbert function stabilize and is equal to degree of the scheme , i.e., if is a scheme of s fat points of multiplicity m, HF (a, b) = s m+1 2 .

In this paper, we study the Hilbert function in the case of general fat points of multiplicity m in 1 × 1 . E. Guardo and A. Van Tuyl give a bound for the region where the Hilbert function of general fat points becomes constant, see [START_REF] Guardo | Fat points in 1 × 1 and their Hilbert functions[END_REF]. Our first result is Theorem 3.10, where we compute the Hilbert function for low bi-degrees, namely for bi-degrees (a, b) such that min{a, b} ≤ m. Observe that, in all our formulas, we use the standard rule that i j = 0 if i < j. Since in each row and column the Hilbert function is eventually constant and Theorem 3.10 gives us the Hilbert function only for bi-degrees such that min{a, b} ≤ m, in general we are left with an intermediate region where we cannot conclude our computations (see Example 3.13). However, in case of triple points, we are able to give a complete description of the Hilbert function in Theorem 4.6. (3) s = 5 and (a, b) = (5, 4), where HF X (5, 4) = 29.

Theorem 4.6. Let = 3P 1 + . . . + 3P s ⊂ 1 × 1 . Then, HF (a, b) = min {(a + 1)(b + 1), 6s} ,
Structure of the paper. In Section 2, we explain our approach and we describe the main tools we are going to use. In particular, we describe the multiprojective-affine-projective method, introduced by the second author together with A.V. Geramita and A. Gimigliano [START_REF] Catalisano | Higher secant varieties of Segre-Veronese varieties[END_REF], and the differential Horace method of J. Alexander and A. Hirschowitz [START_REF] Alexander | An asymptotic vanishing theorem for generic unions of multiple points[END_REF]. In Section 3, we prove Theorem 3.10. In Section 4, by the differential Horace method we compute the complete bi-graded Hilbert function in the case of triple points (Theorem 4.6). In the Appendix, we implement our results with the algebra software Macaulay2 [GS].

Acknowledgements.

APPROACH AND TOOLS

2.1. Multiprojective-affine-projective method. In [START_REF] Catalisano | Higher secant varieties of Segre-Veronese varieties[END_REF], the authors introduced a method to reduce the multi-graded problem to the graded case. We describe this method in the case of 1 × 1 , which is the one of our interest. We consider the following birational map

φ: 1 × 1 2 -→ 2 , ([a 0 : a 1 ], [b 0 : b 1 ]) → a 1 a 0 , b 1 b 0 → 1 : a 1 a 0 : b 1 b 0 .
This map is well-defined on the chart = {a 0 b 0 = 0}. Given a set of fat points X = m 1 P 1 + . . . + m s P s in n defined by the ideal

I X , n = ℘ m 1 1 ∩ . . . ∩ ℘ m s
s , we denote by HF X (d) the standard graded Hilbert function in degree d of the corresponding quotient ring. In case of no ambiguity about the ambient space, we simply denote the ideal as I X .

Lemma 2.1. [CGG05, Theorem 1.5] Let a, b be positive integers and let be a 0-dimensional scheme with support in

( 1 × 1 ) \ . Let X = aQ 1 + bQ 2 + φ( ) ⊂ 2 , where Q 1 = [0 : 1 : 0], Q 2 = [0 : 0 : 1]. Then, dim(I , 1 × 1 ) (a,b) = dim(I X , 2 ) a+b .
Notation. From now on, let be a scheme of s fat points of multiplicity m in 1 × 1 , i.e., = mP 1 + . . . + mP s ; let X be the scheme defined as in Lemma 2.1, i.e.,

X = aQ 1 + bQ 2 + mP 1 + . . . + mP s ,
where, with an abuse of notation, we denote by P i both the point in 1 × 1 and its image in 2 . Moreover, let a,b ( ) be the linear system of curves in 1 × 1 of bi-degree (a, b) passing through and let d (X ) be the linear system of curves in 2 of degree d passing through Z.

By Lemma 2.1, our original question is equivalent to the following. QUESTION. Let X = aQ 1 + bQ 2 + mP 1 + . . . + mP s ⊂ 2 be a scheme of fat points in general position. What is the dimension of the linear system a+b (X )?

The virtual dimension of the linear system a+b (X ), given by a parameter count, is

vir. dim a+b (X ) = a + b + 2 2 - a + 1 2 - b + 1 2 -s m + 1 2 ,
which coincides with the virtual dimension of the linear system a,b ( )

vir. dim a,b ( ) = (a + 1)(b + 1) -s m + 1 2 .
The expected dimension is defined as the maximum between 0 and the virtual dimension. If the actual dimension is equal to the virtual dimension, we say that X imposes independent conditions in degree a + b. Similarly for . If the actual dimension is bigger than the expected value, we say that the linear system is defective and we call defect the difference between the expected dimension and the actual dimension. In these cases, we call algebraic defect the difference between the actual dimension and the virtual dimension. Note that the algebraic defect might be bigger than the defect.

In case of small number of points, the dimension of linear systems of curves with multiple base points of any multiplicity is known. This story goes back to the work of G. Castelnuovo [START_REF] Castelnuovo | Ricerche generali sopra i sistemi lineari di curve piane[END_REF] and attracted a lot of attention in the commutative algebra and algebraic geometry community. Just to mention some of them, see [Nag60, Seg61, DG84, Har85, Gim88, Hir89, AH95, AH00].

2.2. Lemmata. The following results, are well-known facts for the experts in the area and can be found in several papers in the literature. We explicitly recall for convenience of the reader. Lemma 2.2. Let Z be a 0-dimensional scheme in 2 . Then:

(1) if Z imposes independent conditions in degree d, then, it is true also for any Z ⊂ Z;

(2) if d (Z) is empty, then d (Z ) is empty for any Z ⊃ Z.

Proof. (1) It is enough to consider the following chain of inequalities:

d + 2 2 -deg(Z ) ≤ dim d (Z ) ≤ dim d (Z) + deg(Z \ Z ) = = d + 2 2 -deg(Z) + (deg(Z) -deg(Z )).
(2) If there are no curves of degree d through Z, then, there are no curves of degree d through Z .

Lemma 2.3. Let Z be a scheme of fat points in 2 in general position. If there exists a specialization Z of Z such that d ( Z) is non-defective, then it is true also for d (Z).

Proof. It follows by upper semicontinuity of the Hilbert function.

Remark 2.4. The analogous of Lemma 2.2 and Lemma 2.3 also hold if we consider schemes of fat points in 1 × 1 . This tells us that, in order to prove that a scheme of s fat points of multiplicity m in 1 × 1 imposes independent conditions in bi-degree (a, b) for any number of point s, it is enough to consider

s 1 = (a + 1)(b + 1) m+1 2 and s 2 = (a + 1)(b + 1) m+1 2
, and to prove that:

• (a,b) ( ) has expected dimension for s = s 1 , i.e., equal to (a + 1)(b + 1) -s 1 m+1 2 ; • (a,b) ( ) is empty for s = s 2 .
Notation. Let Z be a scheme of fat points and r = {L = 0} be a line in 2 . We denote:

Res r (Z): the residue of Z with respect to r is the scheme defined by the ideal I Z : (L);

Tr r (Z): the trace of Z over r is the scheme defined by the ideal I Z + (L).

More explicitly, if Z = m 1 P 1 + . . . + m s P s and the points P 1 , . . . , P s have support on the line r, we have that Res r (Z) = (m 1 -1)P 1 + . . . + (m s -1)P s + m s +1 P s +1 + . . . + m s P s ⊂ 2 ; Tr r (Z) = m 1 P 1 + . . . + m s P s ⊂ r.

Lemma 2.5. [CGG05, Lemma 2.2] Let Z ⊂ 2 be a 0-dimensional scheme, and let P 1 , . . . , P s be general points on a line r.

(1) If dim d (Z + P 1 + . . .

+ P s-1 ) > dim d-1 (Res r (Z)), then dim d (Z + P 1 + . . . + P s ) = dim d (Z) -s; (2) if dim d-1 (Res r (Z)) = 0 and dim d (Z) ≤ s, then dim d (Z + P 1 + . . . + P s ) = 0.
2.3. Horace method. The Horace method provides a very powerful tool to prove that a base-curve free linear system has the expected dimension by using an inductive approach.

Let Z = m 1 P 1 + . . . + m s P s ⊂ 2 be a scheme with support in general points in 2 . By parameter count, we know that

(2.1) dim d (Z) ≥ max 0, d + 2 2 - s i=1 m i + 1 2 .
By Lemma 2.3, if we find a specialization Z of our scheme such that dim d ( Z) is as expected, we conclude that the same is true for Z. We specialize some of the points to be collinear. Assume that P 1 , . . . , P s lie on the line r = {L = 0}. Then, we have Castelnuovo's inequality,

(2.2) dim (I Z, 2 ) d ≤ dim (I Res r ( Z), 2 ) d-1 + dim (I Tr r ( Z),r ) d .
This inequality allows us to use induction because on the right hand side we have the dimension of linear system d-1 (Res r ( Z)) of plane curves with lower degree and the dimension of the ideal of a 0-dimensional scheme embedded in 1 . Thus, if we can prove that the right hand side in (2.2) equals the right hand side of (2.1), we can conclude. Unfortunately, sometimes the arithmetic does not allow this method to work for any specialization. In order to overcome this problem, J. Alexander and A. Hirschowitz introduced in a series of papers the so-called differential Horace method [AH92a, AH92b, AH95, AH00]. Here, we follow the exposition of [START_REF] Gimigliano | The ideal resolution for generic 3-fat points in 2[END_REF].

Definition 2.6. In the ring of formal functions S = x, y , we say that an ideal is vertically graded with respect to y if it is of the form

I = I 0 ⊕ I 1 y ⊕ I 2 y 2 ⊕ . . . ⊕ ( y m )
, where the I i 's are ideals in

x .

Let Z be a 0-dimensional scheme in 2 with support at a point P lying on line r. We say that Z is vertically graded with base r if there is a regular system of parameters (x, y) at P such that r is defined by y = 0 and the ideal of Z is vertically graded in the localization of the coordinate ring of 2 at the point P.

For any positive integer t, we define the (t + 1)-th residue and trace of Z with respect to r by the ideals:

(t + 1)-th residue: I Res t r (Z) := I Z + (I Z : I t+1 r )I t r ; (t + 1)-th trace: I Tr t r (Z) := (I Z : I t r ) ⊗ r ;
where r denotes the structure sheaf of the line r. In Res t r (Z), we remove the (t +1)-th slice of Z; in Tr t r (Z), we consider only the (t + 1)-th slice of Z.

If Z = Z 1 + . . . + Z s is a non-connected 0-dimensional scheme of fat points, we denote by Res t r (Z) = Res t r (Z 1 ) + . . . + Res t r (Z s ) and Tr t r (Z) = Tr t r (Z 1 ) + . . . + Tr t r (Z s ).
Example 2.7. Let Z = 3P be a triple point in 2 . Let I P = (x, y) and r = { y = 0}. We have that Z is vertically graded with base r because we can write I Z = I 0 ⊕ I 1 y ⊕ I 2 y 2 ⊕ ( y 3 ), where I i = (x 3-i ) ⊂

x . If t = 0, we obtain the usual residue and trace, i.e., I Res 0 r (Z) := (x 3 , x 2 y, x y 2 , y 3 ) + (x 3 , x 2 y, x y 2 , y 3 ) : ( y) = = (x 2 , x y, y 2 ) ⊂ x, y ;

I Tr 0 r (Z) := (x 3 , x 2 y, x y 2 , y 3 ) ⊗ x, y ( y) = (x 3 ) ⊂ x, y ( y)
.

f If we consider other values of t, we consider different slices on the line r. If t = 1, we get

I Res 1 r (Z) := (x 3 , x 2 y, x y 2 , y 3 ) + (x 3 , x 2 y, x y 2 , y 3 ) : ( y 2 ) ( y) = = (x 3 , x y, y 2 ) ⊂ x, y ; I Tr 1 r (Z) := (x 3 , x 2 y, x y 2 , y 3 ) : ( y) ⊗ x, y ( y) = (x 2 ) ⊂ x, y ( y) . f If t = 2, we get I Res 2 r (Z) := (x 3 , x 2 y, x y 2 , y 3 ) + (x 3 , x 2 y, x y 2 , y 3 ) : ( y 3 ) ( y 2 ) = = (x 3 , x 2 y, y 2 ) ⊂ x, y ; I Tr 2 r (Z) := (x 3 , x 2 y, x y 2 , y 3 ) : ( y 2 ) ⊗ x, y ( y) = (x) ⊂ x, y ( y) . f Lemma 2.8 ((Lemma d'Horace différentielle)). [GI04, Proposition 2.6] Let Z = R + S ⊂ 2 be
a scheme of fat points where R is a 0-dimensional scheme of general fat points with support on a line r and S is a scheme of general fat points with support on 2 . If

(1) dim (I Res t r (R)+S, 2 ) d-1 = d+1 2 -deg(Res t r (R) + S); (2) dim (I Tr t r (R),r ) d = d + 1 -deg(Tr t r (R)); then, dim d (Z) = d + 2 2 -deg(Z).

HILBERT FUNCTION IN LOW BI-DEGREES

We are now ready to start our computations. We use the following notation. Let denote a scheme of s fat points of multiplicity m in 1 × 1 , i.e., = mP 1 + . . . + mP s .

Let Z be the scheme of fat points in 2 constructed from and a bi-degree (a, b), where we always assume a ≥ b≥ 0, as described in Lemma 2.1, i.e.,

X = aQ 1 + bQ 2 + mP 1 + . . . + mP s .
We can consider multiplicities m ≥ 2 since the case of simple points is trivial.

Given two points A, B ∈ 2 , we use the notation AB for the line passing through them.

3.1. The case m = min{a, b}. In this section, we start our computations by considering m = b. Since the cases b = 0 is trivial, we may assume b ≥ 1.

Let a = bk + c, with 0 ≤ c ≤ b -1. Then, as we mentioned in Remark 2.4, we consider

s 1 = (a + 1)(b + 1) b+1 2 =      2k for c < b-2 2 ; 2k + 1 for b-2 2 ≤ c < b -1; 2k + 2 for c = b -1. s 2 = (a + 1)(b + 1) b+1 2 = 2k + 1 for c < b-2 2 ; 2k + 2 for c ≥ b-2
2 . We first prove the following lemma that will be useful for our methods.

Lemma 3.1. Let X = aQ 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 where a = bk + c, with 0 ≤ c ≤ b -1, and s = 2k + 1. Then, the unique (irreducible) curve C ∈ k+1 (kQ 1 + Q 2 + P 1 + . . . + P s ) is contained in the base locus of a+b (X ) with multiplicity at least b -c.
Proof. We proceed by induction on bc. First, observe that, if C is a general element in a+b (X ), we have

deg(C ∩ C ) = ak + (s + 1)b = deg(C) deg(C ) + b -c; then, by Bézout's Theorem, C is contained in a+b (X ). If b -c = 1, the claim is obvious. Let b -c ≥ 2.
We can remove the curve and we get a +b (X ), where

X = a Q 1 + b Q 2 + b P 1 +. . .+ b P s , with a = a -k and b = b -1. Now, a = b k + c where c ≤ b -2 = b -1. By inductive hypothesis, the curve C is contained with multiplicity b -c = b -1 -c in a +b (X )
and, consequently, the claim follows.

Before the general case, we consider particular cases depending on the congruence class of a modulo b.

Lemma 3.2. [a ≡ 0 (mod b)] Let X = bkQ 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 . Then, dim b(k+1) (X ) = max 0, b(k + 1) + 2 2 - bk + 1 2 -(s + 1) b + 1 2 .
except for s = 2k + 1, where the defect is equal to 1.

Proof.

[CASE s = 2k + 1] In this case, we expect the linear system b(k+1) (X ) to be empty. The conclusion follows because, by Lemma 3.1, the unique (irreducible) curve C in the linear system k+1 (kQ

1 + Q 2 + P 1 + . . . + P 2k+1 ) is contained with multiplicity b in the base locus of b(k+1) (X ). [CASE s > 2k + 1] Since dim b(k+1) (X ) = 1 for s = 2k + 1, the linear system is empty for s > 2k + 1. [CASE s = 2k] We know that dim b(k+1) (X ) ≥ b(k + 1) + 2 2 - bk + 1 2 -(2k + 1) b + 1 2 = b + 1.
Let X be the specialized scheme where we assume that the points P 1 , . . . , P k are collinear with Q 2 and lie on a line r (here, with an abuse of notation, we still call the specialized points by P i 's). By Lemma 2.3, it is enough to prove the following.

Claim: dim b(k+1) ( X ) = b + 1.
We add an extra point A on the line r and consider the scheme

X + A. If we prove that dim b(k+1) ( X + A) = b,
we are done. The line r is a fixed component for b(k+1) ( X + A); hence, we can remove it and

dim b(k+1) ( X + A) = dim b(k+1)-1 (Res r ( X + A)).
Now, we proceed by induction on b.

If b = 1, dim k (Res r ( X + A)) = k + 2 2 - k + 1 2 -k = 1 = b. Now, let b ≥ 2. The lines Q 1 P i are a fixed component of dim b(k+1)-1 (Res r ( X + A)), for i = k + 1, . . . , 2k.
Hence, after removing them, we conclude by induction

(3.3) dim b(k+1)-1) (Res r ( X + A)) = dim (b-1)(k+1) (X ) = b, where X = (b -1)kQ 1 + (b -1)Q 2 + (b -1)P 1 + . . . + (b -1)P 2k . Now, the claim is proved. Lemma 3.3. [a ≡ b -1 (mod b)] Let X = (bk + b -1)Q 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 . Then, dim b(k+2)-1 (X ) = max 0, b(k + 2) + 1 2 - b(k + 1) 2 -(s + 1) b + 1 2 .
Proof. In the notations of Remark 2.4, we have that s 1 = s 2 = 2k + 2. Hence, we just need to prove that b(k+2)-1 (X ) is empty in the case of 2k + 2 points. Let X be the specialized scheme, where the points Q 2 , P 1 , . . . , P k+1 lie on a line r. By Lemma 2.3, it is enough to prove the following claim.

Claim: dim b(k+2)-1 ( X ) = 0. The line r is a fixed component of the linear system b(k+2)-1 (X ), hence b(k+2)-1 ( X ) = b(k+2)-2 (Res r ( X )).
We proceed by induction on b.

If b = 1, dim k+1 ( X ) = dim k (Res r ( X ) = k + 2 2 - k + 1 2 -(k + 1) = 0.
Assume b ≥ 2. The lines Q 1 P i are contained in the base locus of b(k+2)-2 (Res r ( X )), for i = k+2, . . . , 2k+2, and, after removing them, we conclude by induction

(3.4) dim b(k+2)-2 ( X ) = dim (b-1)(k+2)-1 (X ) = 0, where X = (b -1)(k + 1) -1 Q 1 + (b -1)Q 2 + (b -1)P 1 + . . . + (b -1)P 2k+2 . Now, the claim is proved. Proposition 3.4. Let X = aQ 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 where a = bk + c, with 0 ≤ c ≤ b -1, and s = 2k + 1. Then, dim a+b (X ) = a + b + 2 2 - a + 1 2 -(2k + 2) b + 1 2 + b -c 2 = c + 2 2 .
In particular, for bc ≥ 2, it is defective.

Proof. By Lemma 3.1, the unique (irreducible) curve C in the linear system k+1 (kQ

1 + Q 2 + P 1 + . . . + P s ) is contained with multiplicity b -c in a+b (X ).
Therefore, after removing it, we obtain

dim a+b (X ) = dim c(k+2) (X ),
where

X = c(k + 1)Q 1 + cQ 2 + c P 1 + . . . + c P s . Then, by Lemma 3.2, we get dim a+b (X ) = c(k + 2) + 2 2 - c(k + 1) + 1 2 -(2k + 2) c + 1 2 = c + 2 2 .
Proposition 3.5. Let X = aQ 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 where a = bk + c, with 0 ≤ c ≤ b -1, and s = 2k + 2. Then,

dim a+b (X ) = 0.
Proof. We proceed by induction on bc. If bc = 1, then the claim follows from Lemma 3.3. Then, we assume bc ≥ 2. The curve C ∈ k+1 (kQ 1 + Q 2 + P 1 + . . . + P s-1 ) is contained in the base locus of the linear system. After removing it, we obtain that

dim b(k+1)+c (X ) = dim a +b (X ),
where

X = a Q 1 + b Q 2 + b P 1 + . . .+ b P s-1 + bP s where a = a -k and b = b -1. Consider the subscheme X = a Q 1 + b Q 2 + b P 1 + . . . + b P s-1 + b P s . Since c ≤ b -2 = b -1,
we conclude by induction that the linear system a +b (X ) is empty and, a fortiori, also a +b (X ) is empty.

Proposition 3.6. Let X = aQ 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 where a = bk + c, with 0 ≤ c ≤ b -1, and s = 2k. Then,

dim a+b (X ) = a + b + 2 2 - a + 1 2 -(2k + 1) b + 1 2 = (b + 1)(c + 1).
Proof. We proceed by induction on bc.

If b -c = 1, then a ≡ b -1 (mod b) and the claim follows from Lemma 3.3. Let b -c ≥ 2.
We consider extra points A 1 , . . . , A c+1 where A 1 is general and A 2 , . . . , A c+1 lie on the unique curve in the linear system k+1 (kQ 1 + Q 2 + P 1 + . . . + P s + A 1 ). Thus, by Bézout's Theorem, C is fixed component for the linear system of curves ofdegree a + b through

X + A 1 + . . . + A c+1 . Hence, (3.5) dim a+b (X + A 1 + . . . + A c+1 ) = dim a +b (X ),
where

X = a Q 1 + b Q 2 + b P 1 + . . . + b P s , with a = a -k and b = b -1. Now, a = b k + c with c ≤ b -2 = b -1. By induction, (3.6) dim a +b (X ) = (b + 1)(c + 1) = b(c + 1). Since (3.7) dim a+b (X ) ≤ dim a+b (X + A 1 + . . . + A c+1 ) + (c + 1)
and by (3.5) and (3.6), we get

dim a+b (X ) ≤ (b + 1)(c + 1).
Since the expected dimension is always a lower bound for the actual dimension, we conclude.

Summarizing all previous results, we obtain the following result.

Theorem 3.7.

Let X = aQ 1 + bQ 2 + bP 1 + . . . + bP s ⊂ 2 with a ≥ b. Then, HF X (a + b) = min a + b + 2 2 , a + 1 2 + (s + 1) b + 1 2 , except for s = 2k + 1 and a = bk + c, with 0 ≤ c ≤ b -2,
where

HF X (a + b) = a + b + 2 2 - c + 2 2 .
Remark 3.8. In the case b = 2, this result was already proved in [CGG05, Proposition 2.1].

3.2.

The case m > min{a, b}. Let X = aQ 1 + bQ 2 + mP 1 + . . . + mP s ⊂ 2 with a ≥ b and m > b. First, note that if the linear system a+b (X ) is not empty, then, by Bézout's Theorem, we have that all the lines

Q 1 P i are contained
dim a+b (X ) = dim 2(a+b-m) ((a + b -m)Q 1 + (a + b -m)Q 2 + (a + b -m)P).
This is non-defective and we get dim a+b (X ) = a+b-m+2 2 . If s ≥ 2, we remove the lines Q 1 P i , for i = 1, . . . , s, with multiplicity mb and we get a+b (X ) = a +b (X ), where X = a Q 1 + bQ 2 + bP 1 + . . . + bP s and a = as(mb) < b. Since s ≥ 2, it is enough to show that a +b (X ), where X = a Q 1 + bQ 2 + bP 1 + bP 2 , is empty. Assume dim a +b (X ) = 0. Since the lines Q 2 P 1 , Q 2 P 2 and P 1 P 2 are in the base locus of a +b (X ) with multiplicity at least ba , we need to have

a + b ≥ 3(b -a ). Let b -a = 2t if b -a is even; 2t + 1 if b -a is odd.
We remove the lines Q 2 P 1 , Q 2 P 2 and P 1 P 2 with multiplicity t and we get

dim a +b (X ) = dim a +b-3t (X ),
where

X = a Q 1 + b Q 2 + b P 1 + b P 2 where b = b -2t. Note that, since a + b ≥ 3(b -a ), then a + b -3t ≥ 0. If b -a = 2t, we have a = b and, since t ≥ 1, dim 2b -t (X ) = 0. If b -a = 2t + 1, we have a = b -1 and dim 2b -t-1 (X ) = 0.
This concludes the proof. Proof. By using the multiprojective-affine-projective method, we need to look at the linear system a+b (X ) with X = aQ 1 + bQ 2 + mP 1 + . . .

+ mP s . Let a -s(m -b) < b.
If s ≥ 2, by Proposition 3.9, dim a+b (X ) = 0. Since in this case the inequality

(3.8) (a + 1)(b + 1) ≤ s m + 1 2 -s m -b 2 ,
holds, we conclude. If s = 1 and as(mb) < 0, again by Proposition 3.9, dim a+b (X ) = 0. Since the inequality (3.8) is still true, we conclude. If 0 ≤ a + bm < b, by Proposition 3.9, we have that

dim a+b (X ) = a + b -m + 2 2 = c + 2 2 . Now, assume a -s(m -b) ≥ b.
As explained in Section 3.2, we may reduce to the case where m = b, namely,

dim a+b (X ) = dim a +b (X ),
where X = a Q 1 + bQ 2 + bP 1 +. . .+ bP s , with a = a -s(m-b) ≥ b. Hence, by Theorem 3.7, the dimension of a +b (X ) is the maximum between 0 and Proof. It follows from 3.10 by computing the Hilbert function in bi-degrees ((m -1)(k + 1) + s -1, m -1) and (m(k + 1) -1, m) and checking that it is equal to the degree of .

a -s(m -b) + b + 2 2 - a -s(m -b) + 1 2 -(s + 1) b + 1 2 = = a + b + 2 2 - a + 1 2 - b + 1 2 -s m + 1 2 + s m -b 2 = = (a + 1)(b + 1) -s m + 1 2 + s m -
A nice property of 0-dimensional schemes is that their Hilbert function is eventually constant to the degree of the scheme. Corollary 3.12 gives us lower bounds on the bi-degrees for which the Hilbert function gets constant. Hence, we are left with a limited unknown region.

Example 3.13. We give an explicit example to describe the situation after Theorem 3.10. Here, we look at the Hilbert function of 5 random points of multiplicity 5 in 1 × 1 . The computation has been done with the algebra software Macaulay2 [GS]. In the table we underline the defective cases. The shaded region indicates the area that we are not yet able to compute with our result.

TRIPLE POINTS

In this section, we complete Theorem 3.10 in the case of triple points in 1 × 1 . By Lemma 2.1, we want to compute all the dimensions of the linear systems a+b (X ) where

X = aQ 1 + bQ 2 + 3P 1 + . . . + 3P s ⊂ 2 .
Accordingly with Remark 2.4, we first focus on the two extremal cases s = s 1 and s = s 2 where

s 1 = (a + 1) • (b + 1) 6 , s 2 = (a + 1) • (b + 1) 6 .
Considering the results of the previous section, we only have to consider the cases with a, b ≥ 4. Due to technical reasons in our general argument, we prefer to separately consider the cases (a, b) = (4, 4), (5, 4).

Lemma 4.1 (Case (4, 4)). Let X = 4Q 1 + 4Q 2 + 3P 1 + . . . + 3P s ⊂ 2 . Then, for any s, the Hilbert function of X in degree 8 is as expected, i.e., HF X (8) = min {45, 20 + 6s} .

Proof. We need to prove that X imposes independent conditions in degree 8 for s = s 1 = 4. Since, for s = 4, dim 8 (X ) = 1, we would have also that 8 (X ) is empty for s > 4. Hence, by Lemma 2.2, we conclude. Let s = 4. By Lemma 2.3, it is enough to prove that, for a generic point A, 8 (X + A) is empty. Consider the unique (irreducible) cubic in the linear system 3 (2Q 1 + Q 2 + P 1 + . . . + P 4 + A). By Bézout's Theorem, this cubic is a fixed component of the linear system and dim 8 (X + A) = dim 5 (X ), with X = 2Q 1 +3Q 2 +2P 1 +. . .+2P 4 . By Theorem 3.7, we have that 5 (X ) is empty and we conclude. Lemma 4.2 (Case (5, 4)). Let X = 5Q 1 + 4Q 2 + 3P 1 + . . . + 3P s ⊂ 2 . Then, the Hilbert function of X in degree 9 is as expected, i.e., HF X (9) = min{55, 25 + 6s}, except for s = 5 where HF X (9) = 54, instead of 55.

Proof. If s = s 1 = s 2 = 5, we consider the unique (irreducible) cubic C in 3 (2Q 1 + Q 2 + P 1 + . . . + P 5 ). By Bézout's Theorem, the curve is contained in the base locus of 9 (X ). Then, by [CGG05, Proposition 2.1], we have dim 9 (X ) = dim 6 (3Q 1 + 3Q 2 + 2P 1 + . . . + 2P 5 ) = 1.

Since the linear system has dimension 1 for s = 5, then 9 (X ) is empty for s > 5.

Consider now s = 4. We need to show that dim 9 (X ) = 6. Let A 1 , A 2 be two points such that A 1 is general and A 2 lies on the unique (irreducible) cubic in 3 (2Q 1 + Q 2 + P 1 + . . . + P 4 + A 1 ). By Lemma 2.3, it is enough to show that dim 9 (X + A 1 + A 2 ) = 4. By Bézout's Theorem, the cubic is in the base locus. Then, dim 9

(X + A 1 + A 2 ) = dim 6 (X ),
where X = 3Q 1 + 3Q 2 + 2P 1 + . . . + 2P 4 . By [CGG05, Proposition 2.1], we conclude.

From now on, let a ≥ b ≥ 4 and a + b ≥ 10. Our computations will be structured as follows.

Step 1: Let r be a general line. We specialize the scheme X to a scheme X having some of the triple points with support lying generically on r, but, with suitable degrees in such a way that, by differential Horace method, the line r and the line Q 1 Q 2 become fixed components and can be removed. Let T := Res Q 1 Q 2 (Res r ( X )) be the residual scheme.

Step 2: If necessary, we specialize another point P i on the line r in such a way that the lines r and Q 1 Q 2 are again fixed components and we can remove them. Let T such a specialization and consider W := Res Q 1 Q 2 (Res r ( T )) the residual scheme.

Step 3: The scheme W has a some of the points which are in general position over the line r. Then, we use induction on b and Lemma 2.5 to conclude. Our procedure will depend on the congruence class of a + b modulo 5. The reason of this dependency will be clear during the proof and it will be caused by our particular approach.

Notation. Recalling the constructions of Section 2.3, we denote by D (i) r (P) the 0-dimensional scheme defined by (x i , y), where {x, y} are a regular system of parameters at P such that r is the line y = 0. More in general, let D (i 1 ,...,i m ) r (P) be the 0-dimensional scheme with support at P and such that Tr j r D (i 0 ,...,i m ) r (P) = D (i j ) r (P), for any j = 1, . . . , m. We denote by r (3P) the slice of the triple point that we want to consider on the line r.

Lemma 4.3. Let X = aQ 1 + bQ 2 + 3P 1 + . . . + 3P s ⊂ 2 with s ≥ s 1 , a ≥ b ≥ 4 and a + b ≥ 10. Let a + b = 5h + c, with 0 ≤ c ≤ 4, and let x = h + 1 for c = 0; h + 2 for c = 1, 2, 3, 4; y = h -1 for c = 0; h -2 for c = 1, 2, 3, 4. .
Let X be a specialization of X having P 1 , . . . , P x+ y lying generically on a line r and, in cases c = 2, 3, 4, having also P x+ y+1 lying on the line r, with the following degrees deg( r (3P i )) = 3 for i = 1, . . . , x;

2 for i = x + 1, . . . , x + y; deg( r (3P x+ y+1 )) =     
1 for c = 2;

2 for c = 3;

3 for c = 4;

Then:

(1) for c = 4.

x + y + 1 ≤ s 1 = (a+1)•(b+1) 6 ; (2) dim a+b ( X ) = dim a+b-2 Res Q 1 Q 2 Res r ( X ) . (3) Res Q 1 Q 2 Res r ( X ) = (a -1)Q 1 + (b -1)Q 2 + +                                2P 1 + . . . + 2P h+1 + D (3,1)
Proof. (i) It is enough to show that

(a+1)(b+1) 6 ≥ x + y + 1 = 2h + 1. Since (a + 1) • (b + 1) 6 -(2h + 1) ≥ a(5b -7) -7b -25 30 ≥ (b -4)(5b + 6) -1 30 ,
then, in case b > 4, we are done. For b = 4, we have a ≥ 6, hence a(5b -7) -7b -25 = 13a -53 > 0.

(ii) First, by Bézout's Theorem, we prove that r is a fixed component for a+b ( X ). Now, for a general C ∈ a+b ( X ), we have

deg(r ∩ C) = 3x + 2 y + deg( r (3P x+ y+1 )) = 5h + c + 1 = a + b + 1.
So, we remove the line r. Since in Res r ( X ) the points Q 1 and Q 2 have still multiplicity a and b, respectively, the line Q 1 Q 2 is a fixed component for a+b-1 Res r ( X ) , and we are done.

(iii) Easily follows from the definition of X .

3 for i = x + 1, . . . , x + y; deg( r (3P x+ y+1 )) =            2 for c = 1;
3 for c = 2;

3 for c = 3;

2 for c = 4. deg( r (3P x+ y+2 )) = 1 for c = 3; 3 for c = 4.

Denote by W

:= Res Q 1 Q 2 Res r ( T ) . Then: (i) for c = 3, 4, x + y + 2 ≤ s 1 = (a + 1) • (b + 1) 6 ; (ii) dim a+b-2 ( T ) = dim a+b-4 Res Q 1 Q 2 Res r ( T ) ; (iii) W = (a -2)Q 1 + (b -2)Q 2 + P 1 + . . . + P 2h + +                3P 2h+1 . . . + 3P s for c = 0; D (3,1) r (P 2h+1 ) + 3P 2h+2 . . . + 3P s for c = 1; D (2)
r (P 2h+1 ) + 3P 2h+2 . . . + 3P s for c = 2;

P 2h+1 + D (3,2)
r (P 2h+2 ) + 3P 2h+3 . . . + 3P s for c = 3;

P 2h+1 + 2P 2h+2 + 3P 2h+3 . . . + 3P s for c = 4; and Res r (W ) = (a -2)Q 1 + (b -2)Q 2 +                3P 2h+1 . . . + 3P s for c = 0; P 2h+1 + 3P 2h+2 . . . + 3P s for c = 1; 3P 2h+2 . . . + 3P s for c = 2; +D (2) r (P 2h+2 ) + 3P 2h+3 . . . + 3P s for c = 3; P 2h+2 + 3P 2h+3 . . . + 3P s for c = 4. Proof. (i) It is enough to prove that (a+1)(b+1) 6 ≥ x + y + 2 = 2h + 2. Since b ≥ 4, (a + 1) • (b + 1) 6 -(2h + 2) ≥ a(5b -7) -7b + 36 -55 30 ≥ 5b 2 -14b - 19 30 .
(ii) We prove that r is a fixed component for a+b-2 ( T ). Now, for a general C ∈ a+b-2 ( T ), we have

deg(r ∩ C) = 2x + 3 y + deg( r (3P x+ y+1 )) + deg( r (3P x+ y+2 )) = 5h + c -1 = a + b -1.
So, by Bézout's Theorem, we may remove the line r. Since in Res r ( T ) the points Q 1 and Q 2 have multiplicity a -1 and b -1, respectively, we have that the line Q 1 Q 2 is a fixed component of a+b-3 Res r ( T ) .

(iii) Easily follows from Lemma 4.3(iii) and the definition of T .

We are ready to complete our computations in the case of triple points. The final result is the following.

Theorem 4.5.

Let X = aQ 1 + bQ 2 + 3P 1 + . . . + 3P s ⊂ 2 , with a ≥ b ≥ 1. Then, HF X (a + b) = min a + b + 2 2 , a + 1 2 + b + 1 2 + 6s ,
as expected, except for

(1) b = 1 and s < 2 5 (a + 1), where HF X (a + 1) • for s = s 1 , a+b (X ) has dimension as expected, dim a+b (X ) = (a + 1)(b + 1) -6s 1 ;

= a+1 2 + 1 + 5s; (2) s odd, say s = 2k + 1, and (a) (a, b) = (4k + 1, 2), where HF X (4k + 3) = a+b+2 2 -1; (b) (a, b) = (3k, 3), where HF X (3k + 3) = a+b+2 2 -1; (c) (a, b) = (3k + 1, 3), where HF X (3k + 4) = a+1 2 + b+1 2 + 6s -1; (3) s =
• for s = s 2 , a+b (X ) is empty.

By the previous lemmas, we reduce to the linear system a+b-4 (W ), where W := Res Q 1 Q 2 Res r ( T ) is as in Lemma 4.3 and Lemma 4.4. If we prove that, for s = s 1 , dim a+b-4 (W ) = (a + 1)(b + 1) -6s 1 and, for s = s 2 , a+b-4 (W ) is empty, then, by the semicontinuity of the Hilbert function, we are done.

[CASE s = s 1 ] Recall that, by Lemma 4.3 and Lemma 4.4:

W = (a -2)Q 1 + (b -2)Q 2 + P 1 + . . . + P 2h +                      3P 2h+1 . . . + 3P s , for c = 0; D (3,1) r (P 2h+1 ) + 3P 2h+2 . . . + 3P s , for c = 1; D (2)
r (P 2h+1 ) + 3P 2h+2 . . . + 3P s , for c = 2;

P 2h+1 + D (3,2) r (P 2h+2 ) + 3P 2h+3 . . . + 3P s ,
for c = 3;

P 2h+1 + 2P 2h+2 + 3P 2h+3 . . . + 3P s , for c = 4.
The expected dimension of a+b-4 (W ) is

exp. dim a+b-4 (W ) = (a -1)(b -1) -2h -6(s 1 -2h) + 2c = = (a + 1)(b + 1) -6s 1 -2(5h + c) + 10h + 2c = (a + 1)(b + 1) -6s 1 .
Thus, we need to prove that, for s = s 1 , W imposes independent conditions to the curves of degree a+ b-4. We use Lemma 2.5(i). Let

W 1 = W -{P 1 , . . . , P 2h } for c = 0, 1, 2; W -{P 1 , . . . , P 2h+1 } for c = 3, 4, that is, W 1 = (a -2)Q 1 + (b -2)Q 2 +                3P 2h+1 . . . + 3P s 1 for c = 0; D (3,1) r (P 2h+1 ) + 3P 2h+2 . . . + 3P s 1 for c = 1; D (2)
r (P 2h+1 ) + 3P 2h+2 . . . + 3P s 1 for c = 2;

D (3,2) r (P 2h+2 ) + 3P 2h+3 . . . + 3P s 1 for c = 3; 2P 2h+2 + 3P 2h+3 . . . + 3P s 1 for c = 4. Claim 1. For s = s 1 , • dim a+b-4 (W 1 + P 1 + • • • + P 2h-1 ) > dim a+b-5 (Res r (W 1 )), for c = 0, 1, 2; • dim a+b-4 (W 1 + P 1 + • • • + P 2h ) > dim a+b-5 (Res r (W 1 )), for c = 3, 4.
Proof of Claim 1. By parameter count, we know that the left hand sides are always greater or equal than (a+1)(b+1)-6s 1 +1 which is strictly positive, by definition of s 1 . Since the line Q 1 Q 2 is a fixed component for a+b-5 (Res r (W 1 )), we also have

dim a+b-5 (Res r (W 1 )) = dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))),
where

Res Q 1 Q 2 (Res r (W 1 )) = (a -3)Q 1 + (b -3)Q 2 +                3P 2h+1 . . . + 3P s , for c = 0; P 2h+1 + 3P 2h+2 . . . + 3P s , for c = 1; 3P 2h+2 . . . + 3P s , for c = 2; D (2) r (P 2h+2 ) + 3P 2h+3 . . . + 3P s , for c = 3; P 2h+2 + 3P 2h+3 . . . + 3P s , for c = 4.
Now, we want to prove our claim by induction, but we need to be careful because we might fall in one of the defective cases we have considered above.

(a) Non-defective case. If we do not fall in one of the defective cases, we have that, by induction and by observing that general simple points, in the case c = 1, 4, and a general 2-jet, in the case c = 3, impose independent conditions, we have (4.9)

dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) =                max {0, (a -2)(b -2) -6(s 1 -2h)} , for c = 0; max {0, (a -2)(b -2) -6(s 1 -2h) + 5} , for c = 1; max {0, (a -2)(b -2) -6(s 1 -2h) + 6} , for c = 2; max {0, (a -2)(b -2) -6(s 1 -2h) + 10} , for c = 3; max {0, (a -2)(b -2) -6(s 1 -2h) + 11} , for c = 4. If a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) is empty, the claim is trivial. Otherwise, for c = 0, 1, 2, dim a+b-4 (W 1 + P 1 + • • • + P 2h-1 ) -dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) ≥ (a + 1)(b + 1) -6s 1 + 1 -(a -2)(b -2) + 6(s 1 -2h) -      0
similarly, for c = 3, 4, we obtain (4.10) dim a+b-4 (W

1 + P 1 + • • • + P 2h ) -dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) ≥ 3, for c = 3; 5, for c = 4.
In particular, we obtain that the Claim 1 holds under the assumption (a).

(b) b -3 = 1. In this case, we know that we have defect; in particular, we have similarly, for c = 3, 4, we obtain dim a+b-4 (W

dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) =                max {0, (a -2)(b -2) -5(s 1 -2h)} , for c = 0; max {0, (a -2)(b -2) -5(s 1 -2h) + 4} , for c = 1; max {0, (a -2)(b -2) -5(s 1 -2h) + 5} , for c = 2; max {0, (a -2)(b -2) -5(s 1 -2h) + 8} , for c = 3; max {0, (a -2)(b -2) -5(s 1 -2h) + 9} , for c = 4. If a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) is empty, the claim is trivial. Otherwise, for c = 0, 1, 2, dim a+b-4 (W 1 + P 1 + • • • + P 2h-1 ) -dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) ≥ (a + 1)(b + 1) -6s 1 + 1 -(a -2)(b -2) + 5(s 1 -2h) -      0
1 + P 1 + • • • + P 2h ) -dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) ≥ 5h - 5(a + 1) 6 - 1 for c = 3; -1 for c = 4; ≥ 5h -6 6 > 0.
In particular, we obtain that the Claim 1 holds under the assumption (b).

(c) b -3 = 1 and algebraic defect (for the definition, see Section 2) equal to 1. In these cases, since the algebraic defect is equal to 1, we may adapt the computations to obtain (4.9) and (4.10). In particular, we obtain dim a+b-4 (W Hence, Claim 1 holds also in this case.

1 + P 1 + • • • + P 2h-1 ) -dim a+b-6 (Res Q 1 Q 2 (Res r (W 1 ))) ≥                3
(d) b -3 = 1 and algebraic defect equal to 3. In this case, we cannot adapt the previous computations. This defective case would appear only for (a -3, b -3) = (3k, 3), for some positive integer k, and if (a + 1)(b + 1) -6s 1 + 1 = 1. Therefore, only if 7(3k + 4) = 6s 1 . This is a contradiction, cause the left hand side is clearly not divisible by 3.

Therefore, Claim 1 is proved.

Claim 2. For s = s 1 , W 1 gives independent conditions to the curves of degree a + b -4.

Proof of Claim 2.

Let

W 1 = (a -2)Q 1 + (b -2)Q 2 + 3P 2h+1 . . . + 3P s for c = 0, 1, 2; 3P 2h+2 + 3P 2h+3 . . . + 3P s for c = 3, 4.
Since W 1 ⊃ W 1 , by Lemma 2.3, it is enough to check that the claim holds for W 1 . Again, we need to be careful because we might fall in a defective case. We consider them separately.

(a) (a -2, b -2) = (3k + 1, 3), for some positive integer k. In this case, we have that s 1 = 3k + 4 and 3k + 8 = 5h + c. Therefore, if c = 0, 1, 2,

s 1 -2h < 2k + 1 ⇐⇒ k >     
1 for c = 0;

3 for c = 1; 5 for c = 2; and, if c = 3, 4,

s 1 -2h -1 < 2k + 1 ⇐⇒ k > 0 for c = 3; 2 for c = 4.
Therefore, for large values of k, we do not risk to fall in the defective cases. Hence, we are left with the cases (a, b) = (6, 5), (9, 5), (12, 5) where it can be easily checked by specialization that W 1 impose independent conditions.

(b) (a -2, b -2) = (3k + 1, 3). In this case, observe that, if c = 0, 1, 2,

(a -1)(b -1) -6(s 1 -2h) = (a + 1)(b + 1) -6s 1 + 2h -2c ≥ 2h -2c ≥ 0;
and, if c = 3, 4,

(a -1)(b -1) -6(s 1 -2h -1) = (a + 1)(b + 1) -6s 1 + 2h -2c + 6 ≥ 2h -2c + 6 ≥ 2.
Therefore, since in the defective cases, we have that the dimension of the linear system is equal to 1, then we are left to only check the case where c = 2, h = 2 and (a+1)(b+1)-6s 1 = 0. Since it has to be a+ b = 12 and the defective cases (a -2, b -2) = (3k, 3), (5, 4) do not satisfy this condition, a fortiori, we have that that b -2 = 2 and, consequently, (a, b) = (8, 4) with s 1 = 7. However, in this case, (a + 1)(b + 1) -6s 1 = 0 and we obtain a contradiction.

Therefore, Claim 2 is proved. Now by Lemma 2.5(i), with W 1 = Z, and Claim 1 it follows that, for s = s 1 , dim a+b-4 (W ) = dim a+b-4 (W 1 ) -2h for c = 0, 1, 2; dim a+b-4 (W 1 ) -2h -1 for c = 3, 4.

By Claim 2 and easy computation, it follows that dim a+b-4 (W ) = (a + 1)(b + 1) -6s 1 . Hence, CASE s = s 1 is proved.

[CASE s = s 2 ] We need to prove that, for s = s 2 , the linear system a+b-4 (W ) is empty.

If s 2 = s 1 the conclusion follows from the previous case. So, assume that s 2 > s 1 . We use Lemma 2.5(ii). Let

W 2 = W -{P 1 , . . . , P 2h } for c = 0, 1, 2; W -{P 1 , . . . , P 2h+1 } for c = 3, 4; that is, W 2 = (a -2)Q 1 + (b -2)Q 2 +                3P 2h+1 . . . + 3P s 2 for c = 0; D (3,
)) = dim a+b-6 (Res Q 1 Q 2 (Res r (W 2 ))),
where

Res Q 1 Q 2 (Res r (W 2 )) = (a -3)Q 1 + (b -3)Q 2 +                3P
s =      s 2 -2h for c = 0; s 2 -2h -1 for c = 1, 2; s 2 -2h -2 for c = 3, 4.
Again, we need to be careful to distinguish when we fall in the defective cases.

(a) (a -3, b -3) is not a defective case. In this case, we have (recall that a

+ b = 5h + c) (a -2)(b -2) -6s = (a + 1)(b + 1) -3(a + b) + 3 -6s = = (a + 1)(b + 1) -6s 2 -3h -3c + 3 +      0
s -(2k + 1) = 35h + 7c -35 6 -2h - 10h + 2c -17 3 +      0 for c = 0;
-1 for c = 1, 2;

-2 for c = 3, 4;

≥ 3h + 3c -1 6 +      0 for c = 0; -1 for c = 1, 2; -2 for c = 3, 4; = 3h-1 6 for c = 0, 2 , 4; 3h-4 6
for c = 1, 3.

Hence, since h ≥ 2, we have that s > 2k + 1 and Claim 3 holds under assumption (e).

(f) (a -3, b -3) = (5, 4). In this case, we have h = 3, c = 0 and s 2 = 12. Hence, s = s 2 -2h = 6, so we do not fall in the defective case and Claim 3 holds under assumption (f).

Hence, Claim 3 is completely proved. If h = 2 and c = 0, 1, 2, since we assume s 2 > s 1 , we are left only with the following cases: (a, b) = (6, 4), (7, 4), (6, 6), (8, 4). Among these cases, only for (a, b) = (4, 4) we have that (a + 1)(b + 1) -6s 2 + 4 = 49 -54 + 4 = -1 < 0; but, since (a -2, b -2) = (4, 4) is a non-defective case, we have dim a+b-4 (W 2 ) = 0. Therefore, excluding this case, we have dim a+b-4 (W 2 ) ≤ exp. dim a+b-4 (W 2 ) ≤ 2h for c = 0, 1, 2;

2h + 1 for c = 3, 4; because, since s 2 > s 1 , we have (a + 1)(b + 1) -6s 2 ≤ -1. Hence, Claim 4 is proved. Now, by Claim 3, Claim 4 and Lemma 2.5(ii), with W 2 = Z, it follows that also CASE s = s 2 is proved.

Therefore, as a direct corollary of Theorem 4.5, we obtain the following formulas for the complete bi-graded Hilbert function for schemes of triple points. In this appendix, we implement our results with the algebra software Macaulay2 [GS]. With the standard tools of the software, we would need to first construct the ideal of fat points by using random coordinates and then we would compute the Hilbert function with the implemented command hilbertFunction.

These computations, since they involve Gröbner basis, might not even finish in reasonable time. Here is a possible code to try this. Therefore, it is enough to prove the following claim.

Claim. Let m ≥ 3. Consider X i = a i Q 1 + b i Q 2 + m i P 1 + . . . + m i P s , where a i = 3m -6 + i(2m -4), b i = 3 + i, m i = 2 + i and s = 4m -7, for any 0 ≤ i ≤ m -3. Then, a i +b i (X i ) has dimension as expected.

In particular, this concludes the proof because we have that X coincides with X m-3 .

Proof of Claim. We proceed by induction on i. If i = 0, we conclude by [CGG05, Proposition 2.1]. Let 0 < i ≤ m -3. Consider again the curve C and let X i = X i + A 1 + . . . + A m-3-i , where the points A i 's are general on the curve C. The expected dimension of a i +b i ( X i ) is still positive. In fact, since m ≥ i + 3, exp. dim a i +b i ( X i ) = exp.

dim a i +b i (X i ) -(m -3 -i) = = 1 + i(m - 7 2 ) - 1 2 i 2 -(m -3 -i) ≥ i 2 + 1.
Now, for a general element C ∈ a i +b i ( X i ). Hence, the curve C is a fixed component and can be removed. Then, by induction, we have

dim a i +b i (X i ) ≤ dim a i +b i ( X i ) + (m -3 -i) = dim a i-1 +b i-1 (X i-1 ) + (m -3 -i) = = (a i-1 + 1)(b i-1 + 1) -(4m -7) m i-1 + 1 2 + (m -3 -i) = = exp. dim a i +b i (X i ).
This concludes the proof.

For

  any bi-homogeneous ideal I in S, we define the Hilbert function of S/I as HF S/I (a, b) := dim (S/I) (a,b) = dim S (a,b) -dim I (a,b) , for (a, b) ∈ 2 .

Theorem 3. 10 .

 10 Let a ≥ b and assume m ≥ b. Let = mP 1 + . . . + mP s ⊂ 1 × 1 . Then, HF (a, b) = min (a + 1)(b + 1), s m + 1 2 -s mb 2 , except if s = 2k + 1 and a = bk + c + s(mb), with c = 0, . . . , b -2, where HF (a, b) = (a + 1)(b + 1) -c + 2 2 .

  b = 1 and s < 2 5 (a + 1), where HF (a, 1) = 5s; (2) s odd, say s = 2k + 1, and (a, b) = (4k + 1, 2), where HF (4k + 1, 2) = (a + 1)(b + 1) -1; (a, b) = (3k, 3), where HF (3k, 3) = (a + 1)(b + 1) -1; (a, b) = (3k + 1, 3), where HF (3k + 1, 3) = 6s -1;

  in the base locus with multiplicity at least mb. If as(mb) ≥ b, we have that dim a+b (X ) = dim a +b (X ), with X = a Q 1 + bQ 2 + bP 1 + . . . + bP s , where a = as(mb). Therefore, this case can be reduced to the case m = b that we treated in the previous section. Here, we consider the case as(mb) < b. Proposition 3.9. Let X = aQ 1 + bQ 2 + mP 1 + . . . + mP s ⊂ 2 with a ≥ b, m > b and as(mb) < b. Then, a+b (X ) is empty, except for s = 1, with 0 ≤ a + bm < b, where dim a+b = a+b-m+2 2 . Proof. Assume that a-s(m-b) < 0. Let s , m be the quotient and the reminder, respectively, of the division between a and mb, i.e., a = s (mb) + m , with s < s and 0 ≤ m < mb. Then, dim a+b (X ) = dim b (X ), where X = 0 • Q 1 + bQ 2 + bP 1 + . . . + bP s + (mm )P s +1 + mP s +2 + . . . + mP s . Since mm > b, we conclude that b (X ) is empty. Now, we are left with the cases 0 ≤ as(mb) < b. If s = 1, we have m ≤ a + b and a < m. By Bézout's Theorem, we can remove all the lines Q 1 P 1 with multiplicity mb and Q 2 P 1 with multiplicity mb. Then, we get

3. 3 .

 3 Bi-graded Hilbert function in extremal bi-degrees. By Lemma 2.1, we can translate our previous computations to get the expressions for the bi-graded Hilbert function of schemes of general fat points in 1 × 1 in extremal bi-degrees. Theorem 3.10. Let a ≥ b and assume m ≥ b. Let = mP 1 + . . . + mP s ⊂ 1 × 1 . Then, HF (a, b) = min (a + 1)(b + 1), s m + 1 2 -s mb 2 except if s = 2k + 1 and a = bk + c + s(mb), with c = 0, . . . , b -2, where HF (a, b) = (a + 1)(b + 1) -c + 2 2 .

b 2 ,

 2 except for s = 2k + 1 and as(mb) = bk + c, with 0 ≤ c ≤ b -1, where the dimension isc+2 2 . Since by Lemma 2.1 we have dim (a,b) ( ) = dim a+b (X ), we conclude. Remark 3.11. In [GVT04, Corollary 3.4], the authors proved that, for any row and column, in the notation of the latter theorem, the bi-graded Hilbert function of is constant for max(a, b) ≥ sm. Theorem 3.10 improves this result and tells us that the b-th column, for b ≤ m, becomes constant for a ≥ smsb 2 . Corollary 3.12. Let be a scheme of s fat points of multiplicity m and in general position in 1 × 1 . Assume that a ≥ b and set k = s 2 . Then, for b ∈ {m -1, m}, the Hilbert function of in the b-th column is constant for a ≥ b(k + 1) + s(mb) -1 and equal to the degree of , i.e., HF (a, b) = s m+1 2 .

r(P

  h+2 ) + . . . + D (3,1) r (P 2h ) + 3P 2h+1 . . . + 3P s , for c = 0; 2P 1 + . . . + 2P h+2 + D (3,1) r (P h+3 ) + . . . + D (3,1) r (P 2h ) + 3P 2h+1 . . . + 3P s , for c = 1; 2P 1 + . . . + 2P h+2 + D (3,1) r (P h+3 ) + . . . + D (3,1) r (P 2h ) + D (3,2) r (P 2h+1 ) + 3P 2h+2 . . . + 3P s , for c = 2; 2P 1 + . . . + 2P h+2 + D (3,1) r (P h+3 ) + . . . + D (3,1) r (P 2h ) + D (3,1) r (P 2h+1 ) + 3P 2h+2 . . . + 3P s , for c = 3; 2P 1 + . . . + 2P h+2 + D (3,1) r (P h+3 ) + . . . + D (3,1) r (P 2h ) + 2(P 2h+1 ) + 3P 2h+2 . . . + 3P s .

Lemma 4. 4 .

 4 Notation as in Lemma 4.3. Denote by T := Res Q 1 Q 2 Res r ( X ) . Let T be a specialization of T such that, in cases c = 1, T has also P x+ y+1 lying generically on the line r, and, in case c = 3, 4, T has also P x+ y+2 lying on the line r, with the following degrees deg( r (3P i )) = 2 for i = 1, . . . , x;

  5 and (a, b) = (5, 4), where HF X (9) = 54, instead of 55. Proof. The cases b ≤ 3 and (a, b) = (4, 4), (5, 4) follow from Theorem 3.7, Theorem 3.10, Lemma 4.1 and Lemma 4.2, respectively. Let b ≥ 4, a + b ≥ 10 and set a + b = 5h + c, with 0 ≤ c ≤ 4. By Remark 2.4, we need to show:

  for c = 0; 5 for c = 1; 6 for c = 2; = 3(a + b) -12h -2 -

  , for c = 0; 4, for c = 1; 5, for c = 2; = 3(a + 4) -10h -2 -s 1 -

  , for c = 0; 1, for c = 1; 3, for c = 2; 2, for c = 3; 4, for c = 4.

6 +

 6 c = 3, 4. Since h ≥ 2, we have (a -2)(b -2) -6s ≤ 0 and Claim 3 holds under assumption (a). (b) b -3 = 1. In this case, we know that triple points given 5 condition instead of 6. Since a + b = 5h + c, we have s 2 = 6 for c = 4. Since h ≥ 2, we have (a -2)(b -2) -5s ≤ 0 and Claim 3 holds under assumption (b).(c) b -3 = 2. In this case, we have that s 2 = s 1 and it follows from CASE s = s 1 . (d) (a -3, b -3) = (3k, 3). If k = 1, we have (a, b) = (6, 6), s 2 = 9 and s = 4 > 2k + 1. Hence, in this case Claim 3 holds. Assume now k ≥ 2. Then, a + b ≥ 15 and h ≥ 3. Moreover, since a = 3k + 3 and a + b = 5h + c, we obtain k = 5h+c-h ≥ 3, we have that s > 2k + 1 and Claim 3 holds under assumption (d). (e) b -3 = 3 and a -3 = 3k + 1. Since a = 3k + 4 and a + b = 5h + c, we get k = 5h+c-10 3 . Therefore,

Claim 4 .

 4 For s = s 2 , dim a+b-4 (W 2 ) ≤ 2h for c = 0, 1, 2;2h+ 1 for c = 3, 4. Proof of Claim 4. Since a + b = 5h + c, the expected dimension of a+b-4 (W 2 ) is exp. dim a+b-4 (W 2 ) = a -1)(b -1) -6(s 2 -2h) + 0} for c = 0; max{0, (a -1)(b -1) -6(s 2 -2h) + 2} for c = 1; max{0, (a -1)(b -1) -6(s 2 -2h) + 4} for c = 2; max{0, (a -1)(b -1) -6(s 2 -2h) + 7} for c = 3; max{0, (a -1)(b -1) -6(s 2 -2h) + 9} for c = 4; = max{0, (a + 1)(b + 1) -6s 2 + 2h} for c = 0, 1, 2; max{0, (a + 1)(b + 1) -6s 2 + 2h + 1} for c = 3, 4.Now, if h > 2 or if h = 2 and c = 3, 4, we have that (a + 1)(b + 1) -6s 2 ≥ -5. Therefore, exp. dim a+b-4 (W 2 ) = (a + 1)(b + 1) -6s 2 + 2h for c = 0, 1, 2;2h + 1 for c = 3, 4.

Theorem 4. 6 .

 6 Let = 3P 1 + . . . + 3P s ⊂ 1 × 1 . Then, HF (a, b) = min {(a + 1)(b + 1), 6s} ,except for (1) b = 1 and s < 2 5 (a + 1), where HF (a, 1) = 5s; (2) s odd, say s = 2k + 1, and (a, b) = (4k + 1, 2), where HF (4k + 1, 2) = (a + 1)(b + 1) -1; (a, b) = (3k, 3), where HF (3k, 3) = (a + 1)(b + 1) -1; (a, b) = (3k + 1, 3), where HF (3k + 1, 3) = 6s -1; (3) s = 5 and (a, b) = (5, 4), where HF X (5, 4) = 29. Proof. It directly follows from Lemma 2.1 and Theorem 4.5. APPENDIX A. Macaulay2 CODE

  = bi-degree; S = QQ[x_0,x_1,y_0,y_1, Degrees => {{1,0},{1,0},{0,1},{0,1}}] I = intersect for i from 1 to s list (ideal(random(QQ)*x_0 + random(QQ)*x_1, random(QQ)*y_0+random(QQ)*y_1))^m; hilbertFunction({a,b},I)Now, consider the unique curve C of degree 2m -3 passing simply through all the points Q 2 , P 1 , . . . , P s and with multiplicity 2m -4 at Q 1 . Then, for a general C ∈ a+b (X ), we havedeg(C ∩ C ) = (2m -1)(m -2)(2m -4) + (m + 1) + (4m -7)m, deg(C) deg(C ) = ((2m -1)(m -2) + (m + 1))(2m -3).Hence, we get that the curve C is contained in the base locus of a+b (X ) becausedeg(C ∩ C ) -deg(C) deg(C ) = (4m -7)m -(m + 1)(2m -4) -(2m -1)(m -2) = 2.Then, we can remove it and we obtain dim a+b (X ) = dim a +b (X ),where X = a Q 1 + b Q 2 + (m -1)P 1 + . . . + (m -1)P s , with a = a -(2m -4) = 3m -6 + (m -3)(2m -4) and b = m. The expected dimension is (a + 1)(b + 1) -

  deg(C ∩ C ) = a i (2m -4) + b i + (4m -7)m i + m -3 -i = = (2m -3)(a i + b i ) + 1 = deg(C) deg(C ) + 1.

  The authors are grateful to R. Fröberg for suggesting the problem. The third author thanks all the participants of the Problem Solving Seminar in Commutative Algebra at the Department of Matematics of Stockholm University for useful discussions. The first author acknowledges the finacial support of the Politecnico di Torino (Italy) through the "Ricerca di Base" fund RDB_17. The second author was supported by MIUR funds (PRIN 2010-11 grant 2010S47ARA-004 -Geometria delle Varietà Algebriche) (Italy) and by the Università degli Studi di Genova through the "Progetti di Ateneo 2015".

  Claim 3. For s = s 2 , the linear system a+b-5 (Res r (W 2 )) is empty.Proof of Claim 3. As in the proof of Claim 1, since the line Q 1 Q 2 is a fixed component for a+b-5 (Res r (W 2 )), we have dim a+b-5 (Res r (W 2

	r	1)	(P 2h+1 ) + 3P 2h+2 . . . + 3P s 2 for c = 1;
	D (2) r (P 2h+1 ) + 3P 2h+2 . . . + 3P s 2	for c = 2;
	D (3,2)

r (P 2h+2 ) + 3P 2h+3 . . . + 3P s 2 for c = 3; 2P 2h+2 + 3P 2h+3 . . . + 3P s 2 for c = 4.

  3P 2h+3 . . . + 3P s 2 for c = 3;P 2h+2 + 3P 2h+3 . . . + 3P s 2 for c = 4. Note that in Res Q 1 Q 2 (Res r (W 2)) there are s triple points, where

	2h+1 . . . + 3P s 2	for c = 0;
	P 2h+1 + 3P 2h+2 . . . + 3P s 2	for c = 1;
	3P 2h+2 . . . + 3P s 2	for c = 2;
	D (2) r (P 2h+2 ) +

Our main results Theorem 3.10 and Theorem 4.5 allow us to give a numerical function which computes the Hilbert function of schemes of general fat points in 1 × 1 very quickly, even for large numbers, where the usual functions cannot be efficient due to the Gröbner basis computation. Here is a possible implementation of this in the language of the algebra software Macaulay2 [GS].