# Tables for numbers of zeros with multiplicity at least r

Department of Mathematical Sciences, Aalborg University,
Fredrik Bajers Vej 7G, 9220 Aalborg Øst, Denmark

## 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

[; \{(X_1-a_a)^{p_1}\cdots (X_m-a_m)^{p_m} \mid p_1+ \cdots +p_m=t\} . ;]

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  upper bounds this number. Similarly, the function [;H(i_1, \ldots , i_m,r,s_1, \ldots , s_m);] from  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

[; \min\bigg\{ \frac{q^{m-1}}{r} \sum_{j=1}^m i_j , q^m\bigg\} ;] .
(2.1)

Here, the first expression comes from a corollary to the generalized Schwartz-Zippel bound   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.

 [;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

[; \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) ;]

 [;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.

 [;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  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

[; D(i_1,i_2,2,3,3);] / [;\big(CF(i_1,i_2,2,3,3) - D(i_1,i_2,2,3,3)\big) ;] ,

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

 [;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

 Augot, D., Stepanov, M.: "Interpolation based decoding of Reed-Muller Codes", slides from talk at Special Semester on Gröbner Bases and Related Methods, RICAM, 2006, http://www.ricam.oeaw.ac.at/specsem/srs/groeb/download/Augot.pdf
 Dvir, Z., Kopparty, S., Saraf, S., Sudan, M.: "Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers", arXiv:0901.2529v2, 2009, 26 pages.
 Geil, O., Thomsen, C.: "Weighted Reed—Muller codes revisited," Designs, codes and cryptography, Vol. 66, 2013, pp. 195—220.
 Geil, O., Thomsen, C.: "More results on the number zeros of multiplicity [;r;]," manuscript, 2014, 14 pages.