Residues and the Combinatorial Nullstellensatz
- PDF / 407,492 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 201 Views
Residues and the Combinatorial Nullstellensatz Roman Karasev1,2
© Akadémiai Kiadó, Budapest, Hungary 2018
Abstract We interpret the Combinatorial Nullstellensatz of Noga Alon as a multidimensional residue formula, describe some consequences of this interpretation and related open problems. Keywords Multidimensional residues · Combinatorial Nullstellensatz · The Cayley–Bacharach theorem Mathematics Subject Classification 05E99 · 14M25 · 52C35
1 Introduction The Combinatorial Nullstellensatz of Noga Alon [2] turned out to be an efficient tool to obtain results in combinatorics and discrete geometry. This is an almost elementary algebraic statement, but it has not so elementary consequences and generalizations. In the recent papers [12,16] a version of the Combinatorial Nullstellensatz was expressed as a certain formula, which turned out to be useful in several problems (see [13,14], for example): Theorem 1.1 (The Combinatorial Nullstellensatz) Suppose a multivariate polynomial f (x1 , x2 , . . . , xn ) over a field F has degree at most c1 + c2 + · · · + cn , where ci are nonnegative integers. Denote by C the coefficient at x1c1 . . . xncn in f . Let A1 , A2 , …, An be arbitrary subsets of F such that |Ai | = ci + 1 for any i. Put ϕi (x) = α∈Ai (x − α). Then C=
αi ∈Ai
f (α1 , . . . , αn ) . ϕ1 (α1 ) . . . ϕn (αn )
(1.1)
Supported by the Federal professorship program Grant 1.456.2016/1.4 and the Russian Foundation for Basic Research Grant 18-01-00036.
B
Roman Karasev [email protected] http://www.rkarasev.ru/en/
1
Department of Mathematics, Moscow Institute of Physics and Technology, Institutskiy per. 9, Dolgoprudny, Russia 141700
2
Institute for Information Transmission Problems of the Russian Academy of Sciences, Bolshoy Karetny per. 19, Moscow, Russia 127994
123
R. Karasev
In particular, if C = 0, then there exists a system of representatives αi ∈ Ai such that f (α1 , α2 , . . . , αn ) = 0. The general way to apply this theorem, developed by Fedor Petrov in [12], is as follows: Express a combinatorial statement in the from that a certain polynomial f of appropriate degree attains a nonzero value on the product A1 × · · · × An . In order to prove this, by the theorem, we need to show that C is nonzero. Then we try to modify the polynomial f without changing C, usually it corresponds to a special choice of the parameters of the initial combinatorial problem, and obtain another polynomial g such that the right hand side of (1.1) contains one (or slightly more) summands that are easy to calculate. In [12] a simple proof of this theorem was given, using the Lagrange interpolation formula, see the review [8] for more information about interpolation. The emphasis of this note is that this formula can be viewed, less elementary, as a multidimensional residue formula. In what follows we explain the meaning of this and try to show other situations when this point of view may be useful. For example, this allows, with some care, to consider the case when the sets Ai are multisets (sets with some mult
Data Loading...
