Tables for numbers of zeros with multiplicity at least r

1. News

Tue Sep 27 20:15:45 CEST 2011 The data files are now put in a zip and a tar.gz file.
Fri 28 Feb 21:37:46 CET 2014 Site moved from own hosting to github pages.

2. Background

We consider non-zero polynomials [;F(X_1, \ldots , X_m) \in \mathbb{F}[X_1, \ldots , X_m]\setminus \{0\};] where [;\mathbb{F};] is any field.

2.1. Multiplicity

Consider a point [;\vec{a}=(a_1, \ldots , a_m)\in \mathbb{F}^m;]. Let [;J_t \subseteq \mathbb{F}[X_1, \ldots , X_m];] be the ideal generated by

We say that [;\vec{a};] is a zero of [;F;] of multiplicity [;r;] if [;\mathbb{F}(X_1, \ldots , X_m) \in J_r \backslash J_{r+1};]. Equivalently, multiplicity can be defined using the Hasse derivative.

2.2. The problem

Let [;\prec;] be the pure lexicographic ordering with [;X_m \prec \cdots \prec X_1;]. Assume the only thing we know about [;F(X_1, \ldots , X_m);] is its leading monomial [;X_1^{i_1}\cdots X_m^{i_m};] (taken of course with respect to [;\prec;]). Let [;S_1, \ldots , S_m \subseteq \mathbb{F};] be finite sets, say [;s_1= |S_1|, \ldots , s_m=|S_m|;]. We would like to know what is the maximal attainable number of zeros in [;S_1 \times \cdots \times S_m;] of multiplicity at least [;r;] for such a polynomial. The function [;D(i_1, \ldots ,i_m,r,s_1, \ldots ,s_m);] from [3] upper bounds this number. Similarly, the function [;H(i_1, \ldots , i_m,r,s_1, \ldots , s_m);] from [4] serve as a lower bound. Below we list values of [;D(i_1, \ldots , i_m,r,q, \ldots ,q);] and [;H(i_1, \ldots , i_m,r,q, \ldots ,q);] for a number of cases. The upper bound [;D(i_1,\ldots,i_m,r,q,\ldots,q);] is an improvement to the upper bound

Here, the first expression comes from a corollary to the generalized Schwartz-Zippel bound [1] [2] and [;q^m;] is the number of points in the ensemble under consideration.

3. How to read the data

When [;m=2;], we can put the lower and upper bounds in a table. When [;m;] is larger, we consider tables of tables as we will see later.

For instance for [;m=2;], [;r=2;] and [;s_1=s_2=q=3;], the table looks a follows.

Table 3.1. Lower and Upper Bounds: 2 Variables, Multiplicity 2, [;q = 3;].

	[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]	[;i_1=4;]	[;i_1=5;]
[;i_2=0;]	0-0	0-0	3-3	3-3	6-6	6-6
[;i_2=1;]	0-0	1-1	3-4	4-5	6-7	7-7
[;i_2=2;]	3-3	3-3	5-5	6-7	7-8	8-8
[;i_2=3;]	3-3	4-4	6-6
[;i_2=4;]	6-6	6-6	7-7
[;i_2=5;]	6-6	7-7	8-8

Each entry [;(i_1,i_2);] contains "[;H(i_1,i_2,3,3,3);] - [;D(i_1,i_2,2,3,3);]".

In addition to this table, we also find a table which compares the upper bound calculated by [;D;] and the upper bound from (2.1). Here, each cell contains

Table 3.2. New Bound Vs. Previous Bound: 2 variables, multiplicity 2, [;q = 3;].

	[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]	[;i_1=4;]	[;i_1=5;]
[;i_2=0;]	0/0	0/1	3/0	3/1	6/0	6/1
[;i_2=1;]	0/1	1/2	4/0	5/1	7/0	7/2
[;i_2=2;]	3/0	3/1	5/1	7/0	8/1	8/1
[;i_2=3;]	3/1	4/2	6/1
[;i_2=4;]	6/0	6/1	7/2
[;i_2=5;]	6/1	7/2	8/1

As an example where [;m>2;], let [;m=4;], [;r=2;] and [;s_1=s_2=s_3=s_4=q=2;]. The table consists of 16 matrices of size [;4 \times 4;]. We here only list the upper left part.

Table 3.3. Lower and Upper Bound: 4 variables, multiplicity 2, [;q = 2;].

		[;i_3=0;]							[;i_3=1;]
		[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]				[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]
[;i_4=0;]	[;i_2=0;]	0-0	0-0	8-8	8-8		[;i_4=0;]	[;i_2=0;]	0-0	4-4	8-12	12-12
	[;i_2=1;]	0-0	4-4	8-12	12-12			[;i_2=1;]	4-4	8-8	12-14	14-14
	[;i_2=2;]	8-8	8-8					[;i_2=2;]	8-12	12-12
	[;i_2=3;]	8-8	12-12					[;i_2=3;]	12-12	14-14
		[;i_3=0;]							[;i_3=1;]
		[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]				[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]
[;i_4=1;]	[;i_2=0;]	0-0	4-4	8-12	12-12		[;i_4=1;]	[;i_2=0;]	4-4	8-8	12-14	14-14
	[;i_2=1;]	4-4	8-8	12-14	14-14			[;i_2=1;]	8-8	11-11	14-15	15-15
	[;i_2=2;]	8-12	12-12					[;i_2=2;]	12-14	14-14
	[;i_2=3;]	12-12	14-14					[;i_2=3;]	14-14	15-15

3.1. Closed formula when [;m=2;]

Proposition 16 in [4] upper bounds [;D(i_1,i_2,r,s_1,s_2);] by closed formulas.

We provide tables comparing the true value of [;D;] and the closed formulas. For instance for [;m=2;], [;r=2;] and [;s_1=s_2=q=3;], the table looks a follows. Each entry [;i_1,i_2);] contains

where [;CF;] is the closed formula from Proposition 19.

Table 3.4. Upper Bound and CF Bound: 2 variables, multiplicity 2, [;q = 3;].

	[;i_1=0;]	[;i_1=1;]	[;i_1=2;]	[;i_1=3;]	[;i_1=4;]	[;i_1=5;]
[;i_2=0;]	0/0	0/1	3/0	3/0	6/0	6/0
[;i_2=1;]	0/1	1/1	4/0	5/0	7/0	7/0
[;i_2=2;]	3/0	3/1	5/0	7/0	8/0	8/0
[;i_2=3;]	3/1	4/1	6/0
[;i_2=4;]	6/0	6/0	7/0
[;i_2=5;]	6/1	7/0	8/0

4. Calculation of the bounds

A program written in Haskell was used to generate the numbers. The source code is available as a plain .hs file and as a pretty printed file. Further, you can find the file at github. For a commented version, please refer to the thesis of C. Thomsen. The Haskell functions for [;D;], [;H;], (2.1) and the closed formula are called d, h, sz', (sz) and cf, respectively, and are programmed such that

• [;\texttt{d [}i_1, \ldots, i_m\texttt{]}\ r\ \texttt{[}s_1, \ldots, s_m\texttt{]} = D(i_1, \ldots, i_m, r, s_1, \ldots, s_m);]
• [;\texttt{h [}i_1, \ldots, i_m\texttt{]}\ r\ \texttt{[}s_1, \ldots, s_m\texttt{]} = H(i_1, \ldots, i_m, r, s_1, \ldots, s_m);]
• [;\texttt{cf [}i_1, \ldots, i_m\texttt{]}\ r\ \texttt{[}s_1, \ldots, s_m\texttt{]} = CF(i_1, \ldots, i_m, r, s_1, \ldots, s_m);]
• [;\texttt{sz [}i_1, \ldots, i_m\texttt{]}\ r\ \texttt{[}s_1, \ldots, s_m\texttt{]} =;] [;\min \big\{ (i_1 s_2 \cdots s_m + s_1 i_2 s_3 \cdots s_m + \cdots + s_1 \cdots s_{m-1}·i_m)/r, s_1 \cdots s_m \big\};]
• [;\textstyle\texttt{sz' [}i_1, \ldots, i_m\texttt{]}\ r\ q = \min\big\{ \frac{q^{m-1}}{r} \sum_{j=1}^m i_j , q^m\big\};]

5. Bounds

In this section you find tables containing the bounds as explained in Section 3.

Download files as zip or tar.gz.

For each combination of [;m;], [;r;] and [;q;], there are two or three files:

1. Lower-Upper: A file containing
   "[; H(i_1, \ldots, i_m, r, q, \ldots, q) \textrm{ - } D(i_1,\ldots,i_m,r,q,\ldots,q) ;]".
2. SZ: A file containing
   "[; \textstyle D(i_1,i_2,2,3,3) \textrm{ / } \big( \min\big\{ \frac{q^{m-1}}{r} \sum_{j=1}^m i_j , q^m \big\} - D(i_1,i_2,2,3,3) \big) ;]".
3. CF: If [;m=2;], a file containing
   "[; D(i_1,i_2,2,3,3) \textrm{ / } \big(CF(i_1,i_2,2,3,3) - D(i_1,i_2,2,3,3)\big) ;]".

6. Acknowledgements

Thanks to Dr Douglas R. Woodall for creating the original version of LaTeXMathML.js and thanks to Jeff Knisley for updating LaTeXMathML.js. Thanks to Avital Oliver and helpers for creating TeXtheWorld and thanks to CodeCogs for rendering math symbols nicely.

7. References