The Binomial Theorem for Algebraic Structures 1

4
函数的自变量 算术 算术平均；等差中顶；算术 中顶 算术级数；等差级数 等差序列 等差级数 边 数组; 数组 前号 递升序 X 的升幂 断语; 断定 结合律 假定平均数 假定；假设 非对
average average speed axiom axiom of existence axiom of extension axiom of inclusion axiom of pairing axiom of power axiom of specification
仰角 静摩擦角; 极限角 最大斜率的角 倾斜角 相交角；交角 投射角 旋转角 扇形角 三角形内角和 同顶角 角移位 角动量 角运动 角速度 年（年利率 X%） 逆时针方向；返时针方向 逆时针力矩 反导数; 反微商 逆对数；反对数 反对称 顶点 接近；趋近 近似值 近似；略计；逼近 阿刺伯数字系统 任意 任意常数 弧 弧长 反余弦函数
7
centripedal force force centroid certain event chain rule chance change of axes change of base change of coordinates change of subject change of variable characteristic equation characteristic function characteristic of logarithm characteristic root chart check digit checking chord chord of contact circle circular circular function circular measure circular motion circular permutation circumcentre circumcircle circumference circumradius

3 Let c = 2 . Then we have m−1 i=0
n
c =n
i
= 2n(c(k−1) logc n − 1) = 2nk − 2n,
k
= 2n(clog2 n − 1)
c −1 c−1
m
xi .
We choose G(x) = i≥0 xi gi . Rewrite in terms of G(x): G(x) − g0 = 2G(x) + xi . x
k
Trees 39. 41. 43. x = x−n
k n
k
n k n k =
k=0
k m
n
=
k=0
k n−k = n! n m
n
k=0
1 k , k! m
k=0
n k
x+k , 2n
k+1 (−1)n−k , m+1
m
n = m
n+1 k+1
m
k (−1)m−k , m n+k , k
Every tree with n vertices has n − 1 edges. Kraft inequality: If the depths of the leaves of a binary tree are d1 , . . . , dn :
i=
i=1 n
n(n + 1) , 2
n
i2 =
i=1
n(n + 1)(2n + 1) , 6
n
n
i3 =
i=1
n2 (n + 1)2 . 4
In general: im =
i=1 n−1 i=1

i=1 n
h i gi .
s∈Si (xi
In the special case m = n, where each gi is a univariate polynomial of the form stronger conclusion holds, as follows.
− s), a
Theorem 1.1 Let F be an arbitrary field, and let f = f (x1 , . . . , xn ) be a polynomial in F [x1 , . . . , xn ]. Let S1 , . . . , Sn be nonempty subsets of F and define gi2 , . . . , sn ∈ Sn so that
In this paper we prove these two theorems, which may be called Combinatorial Nullstellensatz, and describe several combinatorial applications of them. After presenting the (simple) proofs of the above theorems in Section 2, we show, in Section 3 that the classical theorem of Chevalley and Warning on roots of systems of polynomials as well as the basic theorem of Cauchy and Davenport on the addition of residue classes follow as simple consequences. We proceed to describe additional applications in Additive Number Theory and in Graph Theory and Combinatorics in Sections 4,5,6,7 and 8. Many of these applications are known results, proved here in a unified way, and some are new. There are several known results that assert that a combinatorial structure satisfies certain combinatorial property if and only if an appropriate polynomial associated with it lies in a properly defined ideal. In Section 9 we apply our technique and obtain several new results of this form. The final Section 10 contains some concluding remarks and open problems.

Binomial equations
We introduce in this section a particular kind of polynomial equations, that have nice computational properties. A binomial system of polynomial equations is one where each equation has only two terms. We also assume that the system has only a finite number of solutions, i.e., the solution set is a finite set of points in Cn . We are interested in determining the exact number of solutions, and in efficient computational procedures for solving the system. Let’s start with an example. Consider the binomial system given by 8x2 y 3 − 1 = 0 2x3 y 2 − yx = 0. (1)
2
Newton polytopes
Many of the polynomial systems that appear in practice are far from being “generic,” but rather present a number of structural features that, when properly exploited, allow for much more efficient computational techniques. This is quite similar to the situation in numerical linear algebra, where there is a big difference in performance between algorithms that take into account the sparsity structure of a matrix and those that do not. For matrices, the standard notion of sparsity is relatively straightforward, and relates mostly to the number of nonzero coefficients. In computational algebra, however, there exists a much more refined notion of sparsity that refers not only to the number of zero coefficients of a polynomial, but also to the underlying combinatorial structure. This notion of sparsity for multivariate polynomials is usually presented in terms of the Newton polytope of a polynomial, defined below. � Definition 2. Consider a multivariate polynomial p(x1 , . . . , xn ) = α cα xα . The Newton polytope of p, denoted by New(f ), is defined as the convex hull of the set of exponents α, considered as vectors in Rn . Thus, the Newton polytope of a polynomial always has integer extreme points, given by a subset of the exponents of the polynomial. Example 3. Consider the polynomial p(x, y ) = 5 − xy − x2 y 2 + 3y 2 + x4 . Its Newton polytope New(f ), displayed in Figure 1, is the convex hull of the points (0, 0), (1, 1), (2, 2), (0, 2), (4, 0). Example 4. Consider the polynomial p(x, y ) = 1 − x2 + xy + 4y 4 . Its Newton polytope New (p) is the triangle in R2 with vertices {(0, 0), (2, 0), (0, 4)}. Newton polytopes are an essential tool when considering polynomial arithmetic because of the fol­ lowing fundamental identity: New(g · h) = New(g ) + New(h), where + denotes the Minkowski addition of polytopes. 9­2