Theorems 9 and 10 suggest that we can use the number of exposed points at each corner to classify the effects of corner cutting on the form of sparse resultants obtained by the Dixon method.
4.3.1 At Most 2 Exposed Points at Each Corner
It seems clearer to re-state the results of rectangular corner cutting in [2] as follows:
Theorem 11 The Dixon determinant |D|is the sparse resultant of the corner cut monomial sup- port A ⊆ Am,n if A has at most two exposed point with respect to each of the four corners of Am,n.
The classical results of [12] becomes the special case in which there is exactly one exposed point at each corner.
4.3.2 At Most 3 Exposed Points at Each Corner
The BKK degree bound [9] motivates the following definitions.
Definition 5 The area deficiency at a corner of a corner-cut monomial supportAis twice the area reduced at the corner between the convex hulls of Aand Am,n.
Definition 6 The excess degree at a corner of a corner-cut monomial support A is the difference between the area deficiency and the number of exterior points at the corner.
Example 14 Consider the following monomial supportA ⊆ A4,4, |A|= 10:
CHAPTER 4. EXPOSED POINTS 30
t t t
t t t t
t
t t
©©©©¡¡¡¡
¢¢¢¢¢¢¢¢HHHH 4,4
4,0 0,0
0,4
The excess degree at each corner is:
area deficiency − number of exterior points = excess degree, 8 2
0 10 − 6 2
0 7 = 2 0
0 3
u t
The excess degree at a corner with three exposed points has the following geometric interpreta- tion.
Theorem 12 If a cornerK of a corner-cut monomial supportA ⊆ Am,n has exactly three exposed points, the exposed points can be written as
(0, y1),(x2, y2),(x3, n) (m, y1),(x2, y2),(x3, n)
(0, y1),(x2, y2),(x3,0) (m, y1),(x2, y2),(x3,0) (4.35) Note that the notations at a corner are independent of the same notations at other corners. As diagonals, the point (x2, y2) and the corner K determine a rectangle whose area is A, the point (x2, y2) and the point (x3, y1) determine a rectangle whose area isA0. The excess degree at corner K is
²= min(A, A0) (4.36)
Figure 4.1 shows that howA, A0 are computed by the three exposed points at the bottom left corner when K= (0,0).
Proof
Use brute force calculation.
Q.E.D
For the rest of discussion in this section, we recall the following important properties of the Dixon matrix and sparse resultants: (1) maximal minors of the Dixon matrix are multiples of the sparse resultant [13, 19], (2) sparse resultants are irreducible [9], and (3) the degree of the sparse resultant in the coefficients of each of the polynomialsf, g,h is twice the area of the convex hull of the monomial supportAof f,g,h. These properties and Theorem 9 suggest that the results of [14, 15] can be rephrased as follows:
CHAPTER 4. EXPOSED POINTS 31
s
s s
y2
x2 y1
x3
Figure 4.1: WhenK = (0,0), A=x2y2, A0 = (x3−x2)(y1−y2).
Theorem 13 If each corner of a corner-cut monomial supportAhas at most three exposed points and for each corner with three exposed points the excess degree is one, then the Dixon matrix is maximal and the sparse resultant is the Dixon determinant divided by a product of brackets, each bracket in the product consists of the three exposed points at a corner.
Example 15 Consider the following monomial supportA ⊆ A5,5, |A|= 19:
t
t t t t t t
t t tt
t
t t t
t t
t t t
t
@@
@@
QQ QQ
©©©©¡¡ 5,5
5,0 0,0
0,5
Since the excess degree at each corner is 1 and the set of the exposed points at each corner is respectively
{(0,2),(1,3),(2,5)} {(2,5),(3,4),(5,3)}
{(0,2),(1,1),(2,0)} {(2,0),(4,1),(5,2)} (4.37) by Theorem 13, we know that the Dixon matrix is maximal and its A-resultant is
|D|
021120ã204152ã253453ã021325
u t
A generalization of Theorem 13 is the following conjecture [17]:
Conjecture 1 If each corner of a corner-cut monomial supportAhas at most three exposed points, then the sparse resultant is
Q |D|
(i,j)∈KBi,j²i,j (4.38)
where K ⊆ {(0,0),(m,0),(m, n),(0, n)} and Bi,j is the bracket determined by the three exposed points at corner (i, j), ²i,j is the excess degree at corner (i, j).
Some special cases of the conjecture will be proved in Chapter 5.
CHAPTER 4. EXPOSED POINTS 32 4.3.3 Any Number of Exposed Points at Each Corner
Theorems 9 and 10 also suggest that [16] proved a special case of the following conjecture.
Conjecture 2 Suppose corner (i, j), i= 0, m and j = 0, n, of a corner-cut monomial support A has Ni,j exposed points, and whenNi,j ≥3the excess degree at corner (i, j) isNi,j−1. A maximal minor of the Dixon matrix can be obtained by dropping anyNi,j−3 rows and anyNi,j−3 columns associated with exposed points for each corner (i, j) with Ni,j ≥ 3. The sparse resultant is the chosen maximal minor divided by a product of pairs of brackets; one bracket in the pair comes from the three remaining exposed points not involved in the dropping of rows and another bracket in the pair comes from the three remaining exposed points not involved in the dropping of columns.
The following example illustrates Conjecture 2 at the bottom right corner, Theorem 11 at the top right corner, and Conjecture 1 at the top left corner.
Example 16 Consider the following monomial supportA ⊆ A4,4, |A|= 9:
t
t t
t
t t
t
t t
©©©©¡¡¡¡
¢¢¢¢¢¢¢¢HHHH 4,4
4,0 0,0
0,4
The excess degree at each corner and the set of exposed points at each corner are respectively:
1 0
0 3 , {(0,0),(1,1),(2,4)} {(2,4),(4,3)}
{(0,0)} {(0,0),(2,1),(3,2),(4,3)} .
Since(0,0)is a bottom and left singular exposed point and(4,3)is a right singular exposed point, by Theorem 8,(0,0)6∈ R,(0,0)6∈ C,(7,3)6∈C. So we have
{(0,0),(2,1),(3,2),(4,3)} ⊕(−1,0)∩ R={(1,1),(2,2),(3,3)}
{(0,0),(2,1),(3,2),(4,3)} ⊕(3,0)∩ C ={(3,0),(5,1),(6,2)}
Thus, by Conjecture 2, the sparse resultant can be written as nine expressions:
|D(11,30)|
001124ã003243ã213243, |D(11,51)|
001124ã003243ã003243, |D(11,62)|
001124ã003243ã002143,
|D(22,30)|
001124ã002143ã213243, |D(22,51)|
001124ã002143ã003243, |D(22,62)|
001124ã002143ã002143,
|D(33,30)|
001124ã002132ã213243, |D(33,51)|
001124ã002132ã003243, |D(33,62)|
001124ã002132ã002143.
Here D(στ, ab) represents the maximal minor obtained by removing the row indexed by (σ, τ) and
the column indexed by(a, b) from the Dixon matrix D. ut
Chapter 5
Corners with Three Exposed Points
This chapter examines an important corner cutting situation in which there are exactly three exposed points at a corner. Recall Conjecture 1:
If each corner of a corner-cut monomial support A has at most three exposed points, then the sparse resultant is
Q |D|
(i,j)∈KBi,j²i,j (5.1)
whereK ⊆ {(0,0),(m,0),(m, n),(0, n)}andBi,j is the bracket determined by the three exposed points at corner (i, j),²i,j is the excess degree at corner (i, j).
Except for specific quantities, the following derivations and discussions are applicable to any of the four corners. We will thus put quantities peculiar to a corner in a box with four quad- rants according to the convention of Section 2.4. In particular, we will simply write ² instead of ²i,j in the discussion. Let T be the set of the three exposed points at the corner, that is, T ={(x1, y1),(x2, y2),(x3, y3)}. Note that actuallyT is
{(0, y1),(x2, y2),(x3, n)} {(m, y1),(x2, y2),(x3, n)}
{(0, y1),(x2, y2),(x3,0)} {(m, y1),(x2, y2),(x3,0)}
(5.2)
and we definew1, h1, w2, h2 to be
w1 = x2 m−x2 x2 m−x2
h1 = n−y2 n−y2
y2 y2
, (5.3)
w2= x3−x2 x2−x3 x3−x2 x2−x3
h2 = y2−y1 y2−y1 y1−y2 y1−y2
. (5.4)
33
CHAPTER 5. CORNERS WITH THREE EXPOSED POINTS 34 Section 5.1 shows for rows and columns near exposed points within a range 0..min(w1, w2)− 1×0..min(h1, h2)−1, their entries can be greatly simplified in case they are considered as the rows or columns of a determinant. Section 5.2 presents the cases having been successfully proved to generate the expected denominator in (5.1).