Generic Classification and Asymptotic Enumeration of Dope Matrices

Ankit Bisain

Abstract

For a complex polynomial $P$ of degree $n$ and an $m$ -tuple of distinct complex numbers $\Lambda=(\lambda_{1},\ldots,\lambda_{m})$ , the dope matrix $D_{P}(\Lambda)$ is defined as the $m\times(n+1)$ matrix $(c)_{ij}$ with $c_{ij}=1$ if $P^{(j)}(\lambda_{i})=0$ and $c_{ij}=0$ otherwise. We classify the set of dope matrices when the entries of $\Lambda$ are algebraically independent, resolving a conjecture of Alon, Kravitz, and O’Bryant. We also provide asymptotic upper and lower bounds on the total number of $m\times(n+1)$ dope matrices. For $m$ much smaller than $n$ , these bounds give an asymptotic estimate of the logarithm of the number of $m\times(n+1)$ dope matrices.

1 Introduction

Let $P\in\mathbb{C}[x]$ be a polynomial of degree $n$ , and let $\Lambda=(\lambda_{1},\ldots,\lambda_{m})$ be an $m$ -tuple of distinct complex numbers. Following Alon, Kravitz, and O’Bryant [1], we define the dope matrix of $P$ with respect to $\Lambda$ as the $m\times(n+1)$ matrix given by

D_{P}(\Lambda)\vcentcolon=\left(c_{ij}\right)_{i\in[m],j\in[0,n]}\quad\text{where }c_{ij}=\begin{cases}1\ \text{if }P^{(j)}(\lambda_{i})=0\\ 0\ \text{otherwise}.\end{cases}

Hence, the dope matrix tracks the pattern of common zeroes between $P$ and its derivatives – that is, the set of ordered pairs $(i,j)$ for which we have $P^{(j)}(\lambda_{i})=0$ . A matrix is called dope if it is of the form $D_{P}(\Lambda)$ for some $P$ and $\Lambda$ . Denote by $\mathcal{D}_{n}^{m}$ the set of $m\times(n+1)$ dope matrices.

The set of possible dope matrices for fixed $\Lambda$ and $n$ may depend on the values of the $\lambda_{i}$ . For example, if $P$ is a quadratic polynomial, then the conditions $P(\lambda_{1})=0$ , $P(\lambda_{3})=0$ , and $P^{\prime}(\lambda_{2})=0$ can be simultaneously satisfied only if $\lambda_{2}=\frac{\lambda_{1}+\lambda_{3}}{2}$ . In the language of dope matrices, this is

D_{P}((\lambda_{1},\lambda_{2},\lambda_{3}))=\begin{bmatrix}1&0&0\\ 0&1&0\\ 1&0&0\end{bmatrix}\implies\lambda_{2}=\frac{\lambda_{1}+\lambda_{3}}{2}.

For fixed $\Lambda$ and $n$ , define

\mathcal{D}_{n}(\Lambda)=\{D_{P}(\Lambda)\mid P\in\mathbb{C}[x],\ \deg P=n\}.

For any $a,b\in\mathbb{C}$ with $b\neq 0$ and any $\mathbb{Q}$ -automorphism $\varphi$ of $\mathbb{C}$ , it can be shown (see [4]) that

\mathcal{D}_{n}((\lambda_{1},\ldots,\lambda_{m}))=\mathcal{D}_{n}((a+b\varphi(\lambda_{1}),\ldots,a+b\varphi(\lambda_{m}))).

(*)

We denote the $m$ -tuple on the right-hand side as

a+b\varphi(\Lambda)\vcentcolon=(a+b\varphi(\lambda_{1}),\ldots,a+b\varphi(\lambda_{m})).

Define an affine algebraic dependence of $\Lambda$ to be any rational-coefficient polynomial $P$ such that $P(a+b\lambda_{1},a+b\lambda_{2},\ldots,a+b\lambda_{m})=0$ for all $a,b\in\mathbb{C}$ . For instance, $P(x_{1},\ldots,x_{m})\equiv 0$ is an affine algebraic dependence for any $\Lambda$ , and $P(x_{1},x_{2},x_{3})=x_{2}-\frac{x_{1}+x_{3}}{2}$ is an affine algebraic dependence of $(0,1,2)$ . From now on, we refer to $P\equiv 0$ as the trivial affine algebraic dependence, and refer to all other affine algebraic dependences as nontrivial.

Call $\Lambda$ affinely algebraically independent if it has no nontrivial affine algebraic dependences. Using (* ‣ 1), we can show (see Theorem 1.7) that $\mathcal{D}_{n}(\Lambda)$ is the same for any affinely algebraically independent $m$ -tuple $\Lambda$ . We define $\mathcal{D}_{n}^{\operatorname{gen}(m)}\vcentcolon=\mathcal{D}_{n}(\Lambda)$ for any choice of affinely algebraically independent $\Lambda$ . (The notation $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ is motivated by the fact that a generic $m$ -tuple $\Lambda$ is affinely algebraically independent.) We remark that $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ is natural to consider, as a generic $m$ -tuple $\Lambda$ is affinely algebraically independent. In a related direction, Alon, Kravitz, and O’Bryant [1, Theorem 6] have shown that $\left\lvert\mathcal{D}_{n}(\Lambda)\right\rvert$ is maximized exactly when $\mathcal{D}_{n}(\Lambda)=\mathcal{D}_{n}^{\operatorname{gen}(m)}$ .

In Section 2, we analyze $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ . Nathanson [4, Theorem 2] has characterized $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ when $m=1$ , and Alon, Kravitz, and O’Bryant [1, Theorem 1] have characterized $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ when $m=2$ . We first generalize the aforementioned results to a complete characterization of $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ for any $m$ , resolving a conjecture of the latter paper [1, Conjecture 15].

Theorem 1.1.

For all positive integers $m,n$ , the set $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ consists of exactly the $m\times(n+1)$ matrices with $\{0,1\}$ entries such that for all $k\in[0,n]$ , there are at most $k$ nonzero entries in the last $k+1$ columns.

Using this characterization, we are able to enumerate $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ .

Theorem 1.2.

The number of elements of $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ with $k$ ones is

\frac{n+1-k}{n+1}\binom{(n+1)m}{k},

and

\binom{(n+1)m-1}{n}-(m-2)\sum_{k=0}^{n-1}\binom{(n+1)m-1}{k}

is the size of $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ .

When $m=1$ , this sum simplifies to $2^{n}$ . When $m=2$ , it simplifies to $\binom{2n+1}{n}$ , matching a result of Alon, Kravitz, and O’Bryant [1, Corollary 2].

In Sections 3 and 4, we provide bounds on the size of $\mathcal{D}_{n}^{m}$ , giving a partial answer to a question posed in [1, Problem 16].

In Section 3, we focus on the $m\leq\frac{n^{2}+n}{2}$ case. Alon, Kravitz, and O’Bryant [1, Theorem 4] find an upper bound of $\binom{mn^{2}}{m+n}$ by applying a theorem of Rónyai, Babai, and Ganapathy [5, Theorem 1.1] regarding the number of zero-patterns of general sequences of polynomials. We improve this bound by directly applying the methods of [5] to the question at hand. We also find a lower bound on $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ . For $m\leq\frac{n^{2}+n}{2}$ , we have the following:

Theorem 1.3.

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfying $n(t)\to\infty$ and $1<m(t)\leq\frac{n(t)^{2}+n(t)}{2}$ , we have

(1+o(1))\log\left(n^{m}\binom{mn}{n}\right)\leq\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\leq(1+o(1))\log\left(n^{2m}\binom{mn}{n}\right).

Standard asymptotic notation, such as the $o(1)$ in the above theorem, is used throughout this paper and is explained in Section 1.1. We also freely make statements regarding the asymptotic behavior of $\binom{mn}{n}$ , which will follow from the asymptotic estimates of $\log\binom{mn}{n}$ in Section 1.1.

The lower bound in Theorem 1.3 comes from constructing a large set of elements of $\mathcal{D}_{n}^{m}$ . One possible construction is to consider only the case when $\Lambda$ is generic, which gives a lower bound of $\log\left\lvert\mathcal{D}_{n}^{\operatorname{gen}(m)}\right\rvert$ .

Another construction comes from taking a “generic” polynomial $P$ . Consider a polynomial $P$ such that no two derivatives of $P$ have a common root and no derivative of $P$ has a root of multiplicity more than $1$ . If we construct an element of $\mathcal{D}_{n}^{m}$ corresponding to the polynomial $P$ one row at a time, we have around $n$ choices for each row. Hence, this construction gives a lower bound of around $\log(n^{m})$ .

If $m=o(n)$ , then only the $\log\binom{mn}{n}$ term of the lower and upper bounds matter asymptotically. In this regime, the bounds essentially match (see Theorem 3.1 for a more precise statement) and $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ accounts for the lower bound. When $m=\omega(n)$ , only the $\log(n^{m})$ term in the lower bound matters, and hence the generic $P$ construction accounts for the lower bound. The construction for the $m=\Theta(n)$ case is a combination of the generic $\Lambda$ construction and the generic $P$ construction.

In Section 4, we focus on the $m>\frac{n^{2}+n}{2}$ regime. As $P^{(j)}$ has at most $n-j$ roots for each $j$ , any dope matrix can have at most $\frac{n^{2}+n}{2}$ nonzero rows. Hence, the growth rate of $\mathcal{D}_{n}^{m}$ in $m$ decreases after $m$ passes the threshold of $\frac{n^{2}+n}{2}$ . Beyond this threshold, we have the following results:

Theorem 1.4.

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfying $m(t),n(t)\to\infty$ , we have

(a)

If $\frac{n^{2}+n}{2}<m=\Theta(n^{2})$ , then $\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\sim\log\left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert$ ;
(b)

If $\log m=\omega(\log n)$ , then $\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\sim\log\left(\dbinom{m}{\frac{n^{2}+n}{2}}\right)$ .

When $n$ is fixed, $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ is a polynomial in $m$ , and we can compute the two leading terms:

\left\lvert\mathcal{D}_{n}^{m}\right\rvert=\frac{\left(\frac{n^{2}+n}{2}\right)!}{1!2!\cdots n!}\binom{m}{\frac{n^{2}+n}{2}}+\frac{\left(\frac{n^{2}+n}{2}\right)!}{1!2!\cdots n!}\left(1+\frac{(n-1)(n-2)}{4}\right)\binom{m}{\frac{n^{2}+n}{2}-1}+O\left(m^{\frac{n^{2}+n}{2}-2}\right).

1.1 Preliminaries and Notation

We now check that $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ is well-defined.

Lemma 1.5.

If an $m$ -tuple $\Lambda=(\lambda_{1},\ldots,\lambda_{m})$ of distinct complex numbers is affinely algebraically independent, then there exist complex numbers $a,b$ such that $a+b\Lambda$ is algebraically independent.

Proof.

We have that for all polynomials $P\in\mathbb{Q}[x_{1},\ldots,x_{m}]\setminus\{0\}$ , the polynomial $P(a+b\Lambda)\in\mathbb{C}[a,b]$ is not identically zero. We want to show that there exist $a,b\in\mathbb{C}$ such that $P(a+b\Lambda)\neq 0$ for all $P\in\mathbb{Q}[x_{1},\ldots,x_{n}]\setminus\{0\}$ . We’ll show, more generally, that if $S$ is any countable subset of $\mathbb{C}[a,b]\setminus\{0\}$ , then there exist $a,b$ such that $Q(a,b)\neq 0$ for all $Q\in S$ .

View each $Q\in S$ as a polynomial in $b$ with coefficients being polynomials in $a$ . For some $k$ , the coefficient of $b^{k}$ in $Q$ is some nonzero polynomial $R$ in $a$ . For any $a$ with $R(a)\neq 0$ , we have that $Q(a,b)$ has finitely many roots as a polynomial in $b$ . For each $Q\in S$ , pick some such polynomial $R$ , and let $A_{Q}$ be the set of roots of $R$ . Since each $A_{Q}$ is finite, we have that $\bigcup_{Q\in S}A_{Q}$ is countable, and hence, we can pick some $a_{0}\in\mathbb{C}$ that isn’t in $A_{Q}$ for any $Q\in S$ .

We claim that for some $b_{0}\in\mathbb{C}$ , we have $Q(a_{0},b_{0})\neq 0$ for all $Q\in S$ . Let $B_{Q}$ be the set of roots of $Q(a_{0},b)$ viewed as a polynomial in $b$ . By the definition of $a_{0}$ , we have that each $B_{Q}$ is finite, so $\bigcup_{Q\in S}B_{Q}$ is countable. Hence, there is some $b_{0}\in\mathbb{C}$ that isn’t in $B_{Q}$ for any $Q\in S$ , as desired. ∎

We’ll also recall a fact from [4] allowing us to equate $D_{n}(\Lambda)$ and $\mathcal{D}_{n}(\Lambda^{\prime})$ when we have linear maps or $\mathbb{Q}$ -automorphisms of $\mathbb{C}$ sending $\Lambda$ to $\Lambda^{\prime}$ .

Lemma 1.6.

[4, Theorem 5] For any $\mathbb{Q}$ -automorphism $\varphi$ and complex numbers $a,b$ with $b\neq 0$ , we have $\mathcal{D}_{n}(\Lambda)=\mathcal{D}_{n}(a+b\varphi(\Lambda))$ .

The idea of the proof is, for any polynomial $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}$ , to consider the polynomial

P_{a+b\varphi}(x)\vcentcolon=\varphi(a_{n})\left(\frac{x-a}{b}\right)^{n}+\varphi(a_{n-1})\left(\frac{x-a}{b}\right)^{n-1}+\cdots+\varphi(a_{0}).

This polynomial has the property that $\mathcal{D}_{P}(\Lambda)=\mathcal{D}_{P_{a+b\varphi}}(a+b\Lambda)$ for all $P$ . A more complete explanation can be found in [4].

We are now ready to check that $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ is well-defined.

Theorem 1.7.

If $\Lambda_{1}$ and $\Lambda_{2}$ are affinely algebraically independent $m$ -tuples of complex numbers, then $\mathcal{D}_{n}(\Lambda_{1})=\mathcal{D}_{n}(\Lambda_{2})$ .

Proof.

Let $\Lambda$ be an algebraically independent $m$ -tuple of complex numbers. By Lemma 1.5, there are constants $a_{1},b_{1},a_{2},b_{2}\in\mathbb{C}$ such that $a_{1}+b_{1}\Lambda_{1}$ and $a_{2}+b_{2}\Lambda_{2}$ are algebraically independent. Now, there exists some $\mathbb{Q}$ -automorphism $\varphi$ of $\mathbb{C}$ sending $a_{1}+b_{1}\Lambda_{1}$ to $a_{2}+b_{2}\Lambda_{2}$ (see the introduction of [1] for further discussion of this fact). Hence,

\mathcal{D}_{n}(\Lambda_{1})=\mathcal{D}_{n}(a_{1}+b_{1}\Lambda_{1})=\mathcal{D}_{n}(\varphi(a_{1}+b_{1}\Lambda_{1}))=\mathcal{D}_{n}(a_{2}+b_{n}\Lambda_{2})=\mathcal{D}_{n}(\Lambda_{2}),

as desired. ∎

To state our results on asymptotic dope matrix counts, we will use standard asymptotic notation. For functions $f,g\colon\mathbb{Z}\to\mathbb{R}$ , we can compare the growth rates of $f$ and $g$ with the following:

1.

$f=O(g)$ if, for some constant $K$ , we have $\left\lvert f\right\rvert\leq K\left\lvert g\right\rvert$ for all sufficiently large $t$ ;
2.

$f=\Theta(g)$ if, for some constants $K,K^{\prime}$ , we have $K\left\lvert g\right\rvert\leq\left\lvert f\right\rvert\leq K^{\prime}\left\lvert g\right\rvert$ for all sufficiently large $t$ ;
3.

$f\sim g$ if, as $t$ approaches $\infty$ , we have that $\frac{f}{g}$ approaches $1$ ;
4.

$f=o(g)$ if, for any constant $\varepsilon$ , we have $\left\lvert f\right\rvert\leq\varepsilon\left\lvert g\right\rvert$ for all sufficiently large $t$ ;
5.

$f=\omega(g)$ if, for any constant $M$ , we have $\left\lvert f\right\rvert\geq M\left\lvert g\right\rvert$ for all sufficiently large $t$ .

We will frequently need to analyze the asymptotic behavior of $n!$ and $\log\binom{mn}{n}$ . We will make use of the following inequalities:

1.

For any positive integer $n$ , we have $n\log n-n\leq\log n!\leq n\log n$ .
2.

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>1}$ satisfying $n(t)\to\infty$ , we have:

$\log\binom{mn}{n}=n\log\left(\frac{m^{m}}{(m-1)^{(m-1)}}\right)+O(\log n)=n\log m+O(n).$

In particular, $\log\binom{mn}{n}$ grows linearly when $m=O(1)$ and is $\omega(n)$ when $m=\omega(1)$ .

The inequality follows from

n\log n-n\leq\int_{1}^{n}\log x\mathrm{d}x\leq\log 2+\log 3+\cdots+\log n\leq n\log n,

since $\log n!=\log 2+\log 3+\cdots+\log n$ . The first asymptotic estimate on $\log\binom{mn}{n}$ follows directly from Stirling’s approximation, and the second follows from the fact that $2\leq\left(\frac{m}{m-1}\right)^{m-1}<e$ for all $m>1$ .

2 Generic Dope Matrices

In this section we will prove Theorem 1.1. We first outline the proof of the $m=2$ case from [1, Section 4], as our proof uses many ideas from it. It makes use of the following result (slightly rephrased) of Gessel and Viennot.

Theorem 2.1.

[3, Corollary 3] Let $\mathcal{G},\mathcal{H}\subset\mathbb{Z}_{\geq 0}$ be finite sets. If $\left\lvert\mathcal{G}\cap[0,c]\right\rvert\leq\left\lvert\mathcal{H}\cap[0,c]\right\rvert$ for every $c\in\mathbb{Z}_{\geq 0}$ , then the matrix of binomial coefficients

\left[\binom{g}{h}\right]_{g\in\mathcal{G},h\in\mathcal{H}}

has rank $\left\lvert\mathcal{G}\right\rvert$ .

Outline of Proof of Theorem 1.1 when $m=2$ .

Take $\Lambda=(0,1)$ , and let $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}$ . For a $2\times(n+1)$ matrix $M$ , we can view the equation $D_{P}(\Lambda)=M$ as a system of linear equations in $a_{n},\ldots,a_{0}$ via

P^{(s)}(0)=0\iff a_{s}=0\quad\text{and}\quad P^{(s)}(1)=0\iff\sum_{i=0}^{n}\binom{n-i}{s}a_{i}=0.

When $M$ does not satisfy the property in Theorem 1.1, for some $k$ , it has at least $k+1$ ones in the last $k+1$ columns. Take the minimum $k$ with the preceding property and look at the last $k+1$ columns. The resulting linear equations are linearly independent by Theorem 2.1.

In these linear equations, only the $k+1$ variables $a_{n},a_{n-1},\ldots,a_{n-k}$ have nonzero coefficients, so we must have $a_{n}=a_{n-1}=\cdots=a_{n-k}=0$ . However, if $a_{n}=0$ , then $P$ cannot be a degree- $n$ polynomial, which gives a contradiction.

To show that any matrix $M$ with at most $k$ ones in the last $k+1$ columns is attainable, we add all-one columns to the left end of the matrix until the number of ones is one smaller than the number of columns. Say we added $c$ columns, and let $M^{\prime}$ be the matrix with the $c$ columns added. Take the resulting system of equations and append $a_{n+c}=1$ , ensuring that our desired polynomial has degree exactly $n+c$ .

By Theorem 2.1, the resulting equations are linearly independent, and hence have a unique solution. Letting $P_{0}$ be the polynomial corresponding to this solution, we have that $D_{P_{0}}(\Lambda)$ is not the zero matrix, since $P^{(n+c)}(0)\neq 0$ . Hence, $D_{P_{0}}(\Lambda)$ must have at most $n+c$ ones, and is hence exactly $M^{\prime}$ . Now, $D_{P_{0}^{(c)}}(\Lambda)$ is $M$ , as desired. ∎

We now introduce notation that will be helpful in our proof of Theorem 1.1

Definition 2.2.

Call a matrix safe if the last $k+1$ columns contain at most $k$ nonzero entries for all $k$ . Similarly, call a matrix almost-safe if the last $k+1$ columns contain at most $k+1$ nonzero entries for all $k$ .

Throughout this section, we will let $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}$ denote a general polynomial with $\deg P\leq n$ . Note that the set of such $P$ forms a complex vector space of dimension $n+1$ with basis given by $1,x,\ldots,x^{n}$ . Hence, for a fixed integer $s$ and complex number $t$ , we can view $P^{(s)}(t)$ as a linear form in $P$ :

(a_{0},\ldots,a_{n})\mapsto\sum_{j=0}^{n}{j(j-1)\cdots(j+1-s)t^{j-s}}a_{j}.

We will use $\Lambda=(\lambda_{1},\ldots,\lambda_{m})$ and $\mathbf{S}=(S_{1},\ldots,S_{m})$ to denote arbitrary $m$ -tuples of complex numbers and $m$ -tuples of subsets of $\{0,1,\ldots,n\}$ , respectively. Denote by $P^{(\mathbf{S})}(\Lambda)$ the set of linear forms $P^{s}(\lambda_{i})$ for $i\in[m]$ and $s\in S_{i}$ , and denote by $M(\mathbf{S})$ the matrix $(c_{ij})_{i\in[m],\ j\in[0,n]}$ , where $c_{ij}$ is $1$ if $j\in S_{i}$ and $0$ otherwise.

2.1 Reduction to the Key Lemma

The key lemma is the following linear independence property:

Lemma 2.3.

If $M(\mathbf{S})$ is almost-safe and $\Lambda$ is generic, then $P^{\mathbf{S}}(\Lambda)$ is linearly independent.

Before proving this lemma, we will show how it implies Theorem 1.1. The proof is similar to the proof of the $m=2$ case in [1], with Lemma 2.3 replacing the result of Gessel-Viennot.

Proof of Theorem 1.1.

First, we show that being safe is necessary. Let $\Lambda$ be a generic $m$ -tuple. Suppose for some $\mathbf{S}$ such that $M(\mathbf{S})$ is not safe, there exists a polynomial $P$ such that $D_{P}(\Lambda)=M(\mathbf{S})$ .

Take the smallest $k$ such that the last $k+1$ columns contain at least $k+1$ nonzero entries. The linear forms corresponding to these entries are linear functions of $a_{n},a_{n-1},\ldots,a_{n-k}$ and are linearly independent by Lemma 2.3. Hence, $a_{n}=0$ , contradicting the assumption that $P$ is degree- $n$ .

To show that the condition is sufficient, given any safe matrix $M$ , we prepend columns where the top two entries are $1$ and the remaining entries are $0$ such that the resulting matrix $M^{\prime}$ has exactly $n+c$ nonzero entries, where $c$ is the number of prepended columns. We have that $M^{\prime}$ is safe.

Let $\mathbf{S}$ be such that $M(\mathbf{S})=M^{\prime}$ . By Lemma 2.3, $P^{\mathbf{S}}(\Lambda)$ consists of $n+c$ independent linear forms. Appending the linear form $P^{(n+c)}(\lambda_{1})$ corresponds to adding a one to the last column of $M^{\prime}$ , which makes $M^{\prime}$ remain almost-safe, so by Lemma 2.3, $P^{\mathbf{S}}(\Lambda)\cup\{P^{(n+c)}(\lambda_{1})\}$ is a set of $n+c+1$ independent linear forms. Hence, there is some nonzero polynomial $P_{0}$ with degree at most $n+c$ such that $P_{0}^{(n+c)}(\lambda_{1})=1$ , and for all $i\in[m]$ and $s\in S_{i}$ , we have $P_{0}^{(s)}(\lambda_{i})=0$ . Since $P_{0}^{(n+c)}(\lambda_{1})=1$ , we have that $P_{0}$ has degree exactly $n+c$ .

We next show that we cannot have $P_{0}^{(s)}(\lambda_{i})=0$ for any $i\in[m]$ and $s\not\in S_{i}$ . Consider $\mathbf{S}^{\prime}=(S_{1},\ldots,S_{i-1},S_{i}\cup\{s\},S_{i+1},\ldots,S_{m})$ . If $P_{0}^{(s)}(\lambda_{i})=0$ , then $P_{0}$ is zero on every element of $P^{\mathbf{S}^{\prime}}(\Lambda)$ . However, $M(\mathbf{S})$ is almost-safe, so $P^{\mathbf{S}^{\prime}}(\Lambda)$ contains $n+c+1$ linearly independent linear functions by Lemma 2.3. This forces $P_{0}$ to be the zero polynomial, which is a contradiction. Thus, $D_{P_{0}}(\Lambda)$ is exactly $M^{\prime}$ , and hence $D_{P_{0}^{(c)}}(\Lambda)$ is the desired matrix. ∎

2.2 Demonstration of Proof Technique

As the proof of Lemma 2.3 is fairly technical, we provide a demonstration of the proof for a small almost-safe matrix.

Consider the $\mathbf{S}$ corresponding to the following $3\times 6$ matrix, which is almost-safe:

M(\mathbf{S})=\begin{bmatrix}1&1&0&0&1&0\\ 0&0&0&1&0&0\\ 1&0&0&0&1&0\end{bmatrix}.

We will show that if $\Lambda=(0,1,t)$ for some transcendental $t$ , then $P^{\mathbf{S}}(\Lambda)$ is linearly independent.

We want to show that for generic $t$ , the linear forms

P(0),P^{\prime}(0),P^{(4)}(0),P^{(3)}(1),P(t),P^{(4)}(t)

are linearly independent. It suffices to show that the result holds for at least one transcendental $t$ , as we can then take a $\mathbb{Q}$ -automorphism mapping $t$ to any transcendental number of our choosing. The key idea is to check the special case of $t$ very close to $0$ .

Taking linear combinations, we find that the span of the aforementioned linear forms is the same as the span of

P(0),P^{\prime}(0),P^{(4)}(0),P^{(3)}(1),\frac{P(t)-P(0)-tP^{\prime}(0)}{t^{2}/2},\frac{P^{(4)}(t)-P^{(4)}(0)}{t}.

The last two forms are polynomials in $t$ , and can hence be continuously extended to $t=0$ . At $t=0$ , the forms are equal to

P(0),P^{\prime}(0),P^{(4)}(0),P^{(3)}(1),P^{(2)}(0),P^{(5)}(0).

These linear forms correspond to the $2\times 6$ almost-safe matrix

\begin{bmatrix}1&1&1&0&1&1\\ 0&0&0&1&0&0\end{bmatrix},

and hence are linearly independent by the $m=2$ case of the theorem. By the fact that linear independence is equivalent to nonzero determinant, we can extend the linear independence of

P(0),P^{\prime}(0),P^{(4)}(0),P^{(3)}(1),\frac{P(t)-P(0)-tP^{\prime}(0)}{t^{2}/2},\frac{P^{(4)}(t)-P^{(4)}(0)}{t}

from $t=0$ to all $t$ in some neighborhood of $0$ . Hence, they are linearly independent for some transcendental $t$ , implying the desired result.

One can view the argument above as showing that we can combine the roots at $0$ and $t$ , and hence combine the corresponding rows of the matrix.

The proof in the general case consists of two parts. First, we prove a claim generalizing the choice of linear combinations in the above proof. We then generalize the $t\to 0$ argument, allowing us to combine the $\lambda_{i}$ ’s under certain conditions. Once this is done, Lemma 2.3 follows from repeatedly combining the $\lambda_{i}$ ’s.

2.3 Derivatives as Linear Combinations

We first, using Theorem 2.1, find linear combinations that limit to derivatives.

Lemma 2.4.

Fix $d\in\mathbb{Z}_{\geq 0}$ . Let $\mathbf{S}=(S_{1},S_{2})$ , where $S_{1},S_{2}\subset[0,d]$ . Suppose that in $M(\mathbf{S})$ , for all $0\leq k\leq d$ , there are at most $k+1$ nonzero entries in columns $[d-k,d]$ , with equality holding for $k=d$ . Then there exist constants $c_{s,1}$ for $s\in S_{1}$ and $c_{s,2}$ for $s\in S_{2}$ such that the following holds:

For every polynomial $P$ , there exists a polynomial $Q\in\mathbb{C}[\lambda,\varepsilon]$ such that

P^{(d)}(\lambda)=\sum_{s\in S_{1}}c_{s,1}\frac{P^{(s)}(\lambda)}{s!}\varepsilon^{s-d}+\sum_{s\in S_{2}}c_{s,2}\frac{P^{(s)}(\lambda+\varepsilon)}{s!}\varepsilon^{s-d}+\varepsilon Q(\lambda,\varepsilon)

(

\star

)

holds for all $\lambda,\varepsilon\in\mathbb{C}$ .

Proof.

Let $P(x)=a_{0}(x-\lambda)^{0}+\cdots+a_{d}(x-\lambda)^{d}+(x-\lambda)^{d+1}Q_{0}(x-\lambda)$ . We will view the $a_{i}$ as variables. We can write $P^{(s)}$ evaluated at $\lambda$ and $\lambda+\varepsilon$ in the basis of the $a_{i}$ as follows:

\frac{P^{(s)}(\lambda)}{s!}\varepsilon^{s-d}=\varepsilon^{s-d}a_{s}\quad\text{and}\quad\frac{P^{(s)}(\lambda+\varepsilon)}{s!}=\sum_{t=s}^{n}\binom{t}{s}\varepsilon^{t-d}a_{t}.

Hence, the right-hand side of $\star$ ‣ 2.4 contains only linear combinations of $\left\{\varepsilon^{t-d}a_{t}\mid t\in[0,n]\right\}$ . For any choice of the $c_{s,2}$ ’s, we can pick $Q$ to make the coefficient of $\varepsilon^{t-d}a_{t}$ zero for $t>d$ , and we can pick $c_{t,1}$ to make the coefficient of $\varepsilon^{t-d}a_{t}$ zero for $t\in S_{1}$ . Hence, it suffices to pick $c_{s,2}$ such that, for all $t\in[0,d]\setminus S_{1}$ , the coefficient of $\varepsilon^{t-d}a_{t}$ in the right-hand side of $\star$ ‣ 2.4 matches the corresponding coefficient in the left-hand side.

Let $\mathcal{G}=[0,d]\setminus S_{1}$ and $\mathcal{H}=S_{2}$ . For all $g\in\mathcal{G}$ , the coefficient of $\varepsilon^{g-d}a_{g}$ in some term in the right-hand side of ( $\star$ ‣ 2.4) is

\sum_{s\in\mathcal{H}}\binom{g}{s}c_{s,2}

The column condition implies $\left\lvert S_{1}\cap[0,c]\right\rvert+\left\lvert S_{2}\cap[0,c]\right\rvert\geq c+1$ for all $c$ , so $\left\lvert\mathcal{G}\cap[0,c]\right\rvert\leq\left\lvert\mathcal{H}\cap[0,c]\right\rvert$ for all $c$ . Now, by Theorem 2.1, we can find constants $c_{h,2}$ such that for all $g$ in $\mathcal{G}$ ,

\sum_{h\in\mathcal{H}}\binom{g}{h}c_{h,2}=\begin{cases}0\quad\text{if }g\neq d\\ d!\quad\text{if }g=d,\end{cases}

as desired. ∎

2.4 Combining Roots

We make use of the following fact, which allows us to take limits of linear dependences:

Proposition 2.5.

Let $\gamma_{1},\ldots,\gamma_{\ell}$ be continuous maps from $\mathbb{C}$ to some complex vector space. If $\gamma_{1}(0),\ldots,\gamma_{\ell}(0)$ are linearly independent, then $\gamma_{1}(t),\ldots,\gamma_{\ell}(t)$ are linearly independent for all $t$ in some neighborhood of $0$ .

This follows from the fact that, in a given complex vector space, linearly independent $\ell$ -tuples of vectors form an open set.

We now prove the claim allowing us to “combine” $\lambda_{1}$ and $\lambda_{m}$ . This will be the inductive step in our proof of Lemma 2.3.

Lemma 2.6.

Suppose $m>1$ , and suppose that $M(\mathbf{S})$ is almost-safe. Define $\Lambda^{\prime}=\Lambda\setminus\{\lambda_{m}\}$ and $\mathbf{S}^{\prime}=(S^{\prime}_{1},\ldots,S^{\prime}_{m-1})$ , where

•

$S^{\prime}_{i}=S_{i}$ for $2\leq i\leq m-1$
•

$s\in S^{\prime}_{1}$ if and only if for some $t\leq s$ , we have $\left\lvert S_{1}\cap[t,s]\right\rvert+\left\lvert S_{m}\cap[t,s]\right\rvert\geq s-t+1$ .

Then, we have:

(a)

the matrix $M(\mathbf{S}^{\prime})$ is almost-safe,
(b)

if $P^{\mathbf{S}^{\prime}}(\Lambda^{\prime})$ is linearly independent, then so is $P^{\mathbf{S}}(\Lambda)$ , and
(c)

if $\Lambda$ is generic, so is $\Lambda^{\prime}$ .

Proof.

The proof of (c) is clear. We will begin by proving (a).

Consider the row vector obtained as follows:

1.

Add the first and $m$ th rows of $M(\mathbf{S})$ , obtaining some vector $v$ .
2.

We index the components of $v$ with $0,1,\ldots,n$ . If, for some $j$ , the $j$ th component of $v$ is at least $2$ , subtract $1$ from the $j$ th component and add $1$ to the $(j+1)$ th component.
3.

Repeat the previous step until it cannot be repeated anymore.

This aligns with the intuition of combining the roots of row $1$ and row $m$ , since we expect a double root of $P^{(j)}$ to become a root of $P^{(j)}$ and a root of $\left(P^{(j)}\right)^{\prime}=P^{(j+1)}$ . We claim that, no matter which choices are made during step 2, this process will always result in the row vector corresponding to $S^{\prime}_{1}$ .

Let $v_{i}$ denote the vector obtained in step 1, and let $v_{f}$ denote the vector obtained at the end of the process. We use $v$ to denote an arbitrary vector at any point in the process.

For each $s$ , consider the quantity $C_{s}(v)\vcentcolon=\max_{t\leq s}\left(v\cdot\mathbf{1}_{[t,s]}-(s-t+1)\right)$ , where $\mathbf{1}_{[t,s]}$ is the row vector that is $1$ on the columns $[t,s]$ and $0$ elsewhere. During any application of step 2 above, $C_{s}(v)$ is unchanged if $j<s$ , is decreased by $1$ if $j=s$ , and is unchanged if $j>s$ . In the $j=s$ case, taking $t=s$ , we must have that $C_{s}(v)\geq 0$ after the application of step 2. Hence, $C_{s}(v_{i})\geq 0$ if and only if $C_{s}(v_{f})\geq 0$ .

Since $M(\mathbf{S})$ is almost-safe, we have $C_{n}(v_{i})\leq 0$ . Hence, we must also have $C_{n}(v_{f})\leq 0$ – in particular, the $n$ th component of $v_{f}$ cannot be more than $1$ . By definition, the $j$ th component of $v_{f}$ cannot be more than $1$ for any $j<n$ . Thus, all components of $v_{f}$ are either $0$ or $1$ .

We have $v_{i}\cdot\mathbf{1}_{[t,s]}=\left\lvert S_{1}\cap[t,s]\right\rvert+\left\lvert S_{m}\cap[t,s]\right\rvert$ , so $C_{s}(v_{i})\geq 0$ if and only if $s\in S^{\prime}_{1}$ . Since $C_{s}(v_{f})\geq 0$ is equivalent to both $C_{s}(v_{i})\geq 0$ and the $j$ th component of $v_{f}$ being nonzero, $v_{f}$ is the row vector corresponding to $S^{\prime}_{1}$ .

As a corollary of this alternate characterization, we have $\left\lvert S_{1}\right\rvert+\left\lvert S_{m}\right\rvert=\left\lvert S^{\prime}_{1}\right\rvert$ , and hence $P^{\mathbf{S}}(\Lambda)$ and $P^{\mathbf{S}^{\prime}}(\Lambda^{\prime})$ have the same number of elements. We also have that if $M(\mathbf{S})$ is almost-safe, then so is $M(\mathbf{S}^{\prime})$ , as all steps of the above process preserve the property that the sum of the entries of the last $k+1$ columns is at most $k+1$ for all $k$ .

We now prove (b). Recall that we use $P$ to denote a general polynomial of degree at most $n$ . We claim that for each $s^{\prime}\in S^{\prime}_{1}$ , there exist a polynomial $Q_{s^{\prime}}$ , independent of $\varepsilon$ but possibly dependent on $\Lambda$ and $P$ , and constants $c_{s,i}$ , possibly dependent on $\varepsilon$ , such that

P^{(s^{\prime})}(\lambda_{1})-\varepsilon Q_{s^{\prime}}(\varepsilon)=\left(\sum_{s\in S_{1}}c_{s,1}P^{(s)}(\lambda_{1})\right)+\left(\sum_{s\in S_{m}}c_{s,m}P^{(s)}(\lambda_{1}+\varepsilon)\right).

If $s\in S_{1}$ , the result is clear. Otherwise, take the largest $t$ such that $\left\lvert S_{1}\cap[t,s^{\prime}]\right\rvert+\left\lvert S_{m}\cap[t,s^{\prime}]\right\rvert\geq s^{\prime}-t+1$ . For this $t$ , we have $\left\lvert S_{1}\cap[t,s^{\prime}]\right\rvert+\left\lvert S_{m}\cap[t,s^{\prime}]\right\rvert=s^{\prime}-t+1$ , as otherwise $t+1$ would have the same property. Applying Lemma 2.4 to the polynomial $P^{(t)}$ , the degree $d=s^{\prime}-t$ , $\lambda=\lambda_{1}$ , $\varepsilon=\lambda_{m}-\lambda_{1}$ , and the sets $\mathbf{S}=(\{s-t\mid s\in S_{1},s\geq t\},\{s-t\mid s\in S_{m},s\geq t\})$ gives the desired $Q$ and $c_{s,i}$ .

By our assumptions, $P^{\mathbf{S^{\prime}}}(\Lambda^{\prime})$ , which is

\left(P^{(S_{2}^{\prime},\ldots,S_{m-1}^{\prime})}((\lambda_{2},\ldots,\lambda_{m-1}))\right)\bigcup\left(\bigcup_{s^{\prime}\in S^{\prime}_{1}}\left\{P^{(s^{\prime})}(\lambda_{1})-\varepsilon Q_{s^{\prime}}(\varepsilon)\right\}\right)

evaluated at $\varepsilon=0$ , is linearly independent. Every linear form in the above set is continuous in $\varepsilon$ , and hence the above set is linearly independent for some transcendental $\varepsilon\neq 0$ by Proposition 2.5. Its span for this $\varepsilon$ is a subspace of the span of $P^{\mathbf{S}}(\Lambda)$ , and has dimension $\left\lvert P^{\mathbf{S}^{\prime}}(\Lambda^{\prime})\right\rvert=\left\lvert P^{\mathbf{S}}(\Lambda)\right\rvert$ . Hence, $P^{\mathbf{S}}(\Lambda)$ is linearly independent. ∎

We can now repeatedly combine elements to prove that all almost-safe matrices are linearly independent.

Proof of Lemma 2.3.

We proceed by induction on $m$ . The base case of $m=1$ is trivial. The induction step follows immediately from Lemma 2.6. ∎

2.5 Enumeration

The enumeration of generic dope matrices follows from a direct application of the cycle lemma.

Definition 2.7.

We say that a sequence of ones and zeroes is $t$ -dominating if for every $\ell>0$ , the number of zeroes among the first $\ell$ entries is more than $t$ times the number of ones.

The cycle lemma allows us to count the number of $t$ -dominating sequences with a given number of ones and zeroes.

Theorem 2.8.

[2, Cycle Lemma] Let $a,b,t$ be nonnegative integers with $a\geq tb$ . For any sequence $p_{1},\ldots,p_{a+b}$ of $a$ zeroes and $b$ ones, exactly $a-tb$ of the cyclic shifts of the sequence are $t$ -dominating.

Proof of Theorem 1.2.

To prove the assertion for fixed $k$ , consider the map from $\left(c_{ij}\right)_{i\in[m],j\in[0,n]}\in\mathcal{D}_{n}^{\operatorname{gen}(m)}$ to $(m-1)$ -dominating sequences $a_{1},\ldots,a_{m(n+1)}$ given by $c_{ij}\leftrightarrow a_{m(n+1-j)+i}$ . By Theorem 1.1, this is a bijection between elements of $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ with $k$ ones and $m$ -dominating sequences with $k$ ones.

By Theorem 2.8, of the $\binom{(n+1)m}{k}$ length- $m(n+1)$ sequences with $k$ ones and $m(n+1)-k$ zeroes,

\frac{n+1-k}{n+1}\dbinom{(n+1)m}{k}=\binom{(n+1)m-1}{k}-(m-1)\binom{(n+1)m-1}{k-1}

of them are $(m-1)$ -dominating, using the convention $\binom{N}{-1}=0$ , implying the assertion for fixed $k$ . Summing over $0\leq k\leq N$ gives the desired formula for $\left\lvert\mathcal{D}_{n}^{\operatorname{gen}(m)}\right\rvert$ . ∎

Remark 2.9.

When $m=2$ , the size of $\mathcal{D}_{n}^{\operatorname{gen}(m)}$ simplifies to $\binom{2n+1}{n}$ . In this case, a direct counting argument is possible. The earlier map gives a bijection between $\mathcal{D}_{n}^{\operatorname{gen}(2)}$ and $1$ -dominating $\{0,1\}$ sequences. Deleting the first element of the sequence and treating zeroes as ups and ones as downs, the $1$ -dominating $\{0,1\}$ sequences are in bijection with length- $(2n+1)$ left factors of Dyck paths, of which there are $\binom{2n+1}{n}$ .

From the formula in Theorem 1.2, we can find good closed-form estimates for $\left\lvert D_{n}^{\operatorname{gen}(m)}\right\rvert$ . For $m=1,2$ , we have the exact formulas $2^{n}$ and $\binom{2n+1}{n}$ , respectively. For larger $m$ , we have the following:

Corollary 2.10.

For $m\geq 3$ and $n\geq 1$ , we have

\frac{1}{n+1}\dbinom{(n+1)m}{n}\leq\left\lvert\mathcal{D}_{n}^{\operatorname{gen}(m)}\right\rvert\leq\left(1+\frac{1}{m-2}\right)^{2}\frac{1}{n+1}\dbinom{(n+1)m}{n}.

Proof.

We use the formula in 1.2. The lower bound follows by considering the $k=n$ term. For the upper bound, note that the $k=n-\ell$ term is

	$\displaystyle\frac{\ell+1}{n+1}\binom{(n+1)m}{n-\ell}$	$\displaystyle\leq\frac{1}{n+1}\binom{(n+1)m}{n}\left[\frac{(\ell+1)n^{\ell}}{((n+1)m-n)^{\ell}}\right]$
		$\displaystyle\leq\frac{1}{n+1}\binom{(n+1)m}{n}\left[(\ell+1)(m-1)^{-\ell}\right].$

Summing over $0\leq\ell\leq n$ , we have

\left\lvert\mathcal{D}_{n}^{\operatorname{gen}(m)}\right\rvert\leq\frac{1}{n+1}\binom{(n+1)m}{n}\cdot\left(\sum_{\ell=0}^{\infty}(\ell+1)(m-1)^{-\ell}\right)=\left(1+\frac{1}{m-2}\right)^{2}\frac{1}{n+1}\dbinom{(n+1)m}{n},

as desired. ∎

3 $\mathcal{D}_{n}^{m}$ for Small $m$

In this section, we will prove Theorem 1.3. We also remark that, combining our lower bound and upper bound, we have the following asymptotic estimate for $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ when $m=o(n)$ :

Theorem 3.1 (Corollary of Theorem 1.3).

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfying $n(t)\to\infty$ and $m=o(n)$ , we have

\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert=(1+o(1))\log\binom{mn}{n}.

3.1 Upper Bound

We will prove the following upper bound.

Proposition 3.2.

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfying $n(t)\to\infty$ , we have

\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\leq(1+o(1))\log\left(n^{2m}\binom{mn}{n}\right).

Let $f_{1},\ldots,f_{T}$ be a sequence of polynomials in $N$ variables.

Definition 3.3.

We define a zero-pattern to be a subset $S$ of $[T]$ of the form

S=\left\{a|f_{a}(u)=0\right\}

for some $u\in\mathbb{C}^{N}$ .

Our proof closely follows the proof of the following result of Rónyai, Babai, and Ganapathy, which provides a bound on the number of zero-patterns of general sequences of polynomials:

Theorem 3.4.

[5, Theorem 4.1] Let $f_{1},\ldots,f_{T}$ be a sequence of polynomials in $N$ variables, where each polynomial has degree at most $d$ . For any $t$ , the number of zero-patterns is at most

\left(\binom{T}{0}+\cdots+\binom{T}{t}\right)+\binom{N+(T-t-1)d}{N}.

Our proof uses the key ideas from the proof of Theorem 3.4, with the main difference being that we can estimate the degrees of polynomials more carefully in the specific case of the sequence $\left\{P^{(j)}(\lambda_{i})\right\}$ .

Proof of Proposition 3.2.

Since we assume that $P$ is of degree $n$ , we may assume $P$ is monic, as scaling does not affect roots. Let $P=x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}$ and $\Lambda=(\lambda_{1},\ldots,\lambda_{m})$ , where $a_{j},\lambda_{i}\in\mathbb{C}$ are variables. We view each $P^{(j)}(\lambda_{i})$ as a polynomial in $(a_{0},\ldots,a_{n-1},\lambda_{1},\ldots,\lambda_{m})$ . Let $S_{1},\ldots,S_{M}\subset[m]\times[0,n-1]$ denote the zero-patterns of $\{P^{(j)}(\lambda_{i})\}$ , where we may exclude $j=n$ since $P^{(n)}$ is the constant polynomial $(n-1)!$ .

Call a zero-pattern large if it has size larger than $n$ , and small otherwise. The number of small zero-patterns is at most

\binom{mn}{0}+\binom{mn}{1}+\cdots+\binom{mn}{n}\leq n\binom{mn}{n}.

For each large zero-pattern $S_{k}$ , consider the polynomial

Q_{k}(P,\Lambda)\vcentcolon=\prod_{(i,j)\not\in S_{k}}P^{(j)}(\lambda_{i}).

We claim that the $Q_{k}$ are linearly independent (this is proven in [5, Theorem 1.1]). Suppose, for the sake of contradiction, that some linear combination $\sum_{k}\alpha_{k}Q_{k}$ is identically zero, where the $\alpha_{k}$ are not all zero. Consider some index $\ell$ that maximizes $\left\lvert S_{\ell}\right\rvert$ over all $\ell$ with $\alpha_{\ell}\neq 0$ . Evaluating $\sum_{k}\alpha_{k}Q_{k}$ at the $(P,\Lambda)$ corresponding to the zero pattern $S_{\ell}$ gives $\alpha_{\ell}=0$ , which is a contradiction, as desired.

Hence, the $Q_{k}$ ’s are linearly independent. Furthermore, all of the monomials of the $Q_{k}$ ’s corresponding to large zero-patterns are in the set

\left\{a_{0}^{b_{0}}\cdots a_{n-1}^{b_{n-1}}\cdot\lambda_{1}^{c_{1}}\cdots\lambda_{m}^{c_{m}}\mid b_{0}+b_{1}+\cdots+b_{n-1}\leq mn-n,\ 0\leq c_{i}\leq\frac{n^{2}+n}{2}\right\}.

This is a set of size $\binom{mn}{n}\cdot\left(\frac{n^{2}+n+2}{2}\right)^{m}$ , so the $Q_{k}$ ’s corresponding to large zero-patterns lie in a space of dimension $\binom{mn}{n}\cdot\left(\frac{n^{2}+n+2}{2}\right)^{m}$ . Hence, we have

\left\lvert\mathcal{D}_{n}^{m}\right\rvert\leq\binom{mn}{n}\cdot\left(\left(\frac{n^{2}+n+2}{2}\right)^{m}+n\right),

giving the desired bound. ∎

3.2 Lower Bound

We now establish the lower bound on $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ from Theorem 1.3.

Proposition 3.5.

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfying $n(t)\to\infty$ and $1<m(t)\leq\frac{n(t)^{2}+n(t)}{2}$ , we have

\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\geq(1+o(1))\log\left(n^{m}\binom{mn}{n}\right).

The idea behind the construction is, for some well chosen $a$ , to start with an $a\times(n+1)$ matrix $M\in\mathcal{D}_{n}^{\operatorname{gen}(a)}$ , to pick $P$ and $\Lambda$ such that $D_{P}(\Lambda)=M$ , and then to append $m-a$ elements to $\Lambda$ . We first prove a claim allowing us to find $P$ such that many distinct rows can be appended to $D_{P}(\Lambda)$ .

Call an $m\times(n+1)$ matrix $T$ -limited if each row has at most $T$ ones. Call an $m\times(n+1)$ safe matrix saturated if it has exactly $n$ ones in total. We let $C(m,n,T)$ denote the number of $m\times(n+1)$ safe $T$ -limited saturated matrices.

Proposition 3.6.

Let $\Lambda=(\lambda_{1},\ldots,\lambda_{a})$ be affinely algebraically independent, and $M$ be an $a\times(n+1)$ safe $T$ -limited saturated matrix. Then there is a degree- $n$ polynomial $P$ such that $D_{P}(\Lambda)=M$ . Furthermore, this polynomial $P$ has the property that for any $\lambda\in\mathbb{C}$ , at most $T$ of the entries of $D_{P}((\lambda))$ are one.

Proof.

Using Theorem 1.1, we can pick some polynomial $P$ such that $D_{P}(\Lambda)=M$ . Fix an arbitrary $\lambda\in\mathbb{C}$ . We claim that for some $b\in[a]$ , the $a$ -tuple $\Lambda_{b}$ obtained from $\Lambda$ by replacing $\lambda_{b}$ with $\lambda$ is affinely algebraically independent. If $\Lambda$ with $\lambda$ appended is already affinely algebraically independent, the result is clear.

Otherwise, let $Q_{0}$ be a minimum-degree affine algebraic dependence of $(\lambda,\lambda_{1},\ldots,\lambda_{a})$ . We claim that $Q_{0}$ divides all algebraic dependences. Suppose, for the sake of contradiction, that $Q$ is another affine algebraic dependence such that $Q_{0}$ does not divide $Q$ . Viewing $Q_{0},Q$ as polynomials in the first variable and taking the resultant gives a nonzero polynomial $R$ with $R(t_{1}+t_{1}\lambda_{1},\ldots,t_{1}+t_{2}\lambda_{a})=0$ for all $t_{1},t_{2}$ , contradicting the affine algebraic independence of $\Lambda$ .

Now, if we choose $b$ such that $x_{b}$ appears in $Q_{0}$ , we find that $\Lambda_{b}$ is affinely algebraically independent. For this $b$ , by Theorem 1.1, $D_{P}(\Lambda_{b})$ must have at most $n$ ones, so the number of ones in $D_{P}((\lambda))$ is at most the number of ones in the row of $\lambda_{b}$ , which is at most $T$ by assumption, as desired. ∎

Now, we execute the construction mentioned earlier.

Lemma 3.7.

For integers $m,n,a,T$ with $0\leq a\leq m\leq\frac{n^{2}+n}{T^{2}+T}$ , we have

\left\lvert\mathcal{D}_{n}^{m}\right\rvert\geq C(a,n,T)\cdot\left(\frac{n+1}{e(T^{2}+T)}-\frac{a}{en}\right)^{m-a}.

Proof.

For each $a\times(n+1)$ safe $T$ -limited saturated matrix $M$ , we construct many matrices in $\mathcal{D}_{n}^{m}$ whose top $a$ rows are $M$ as follows:

1.

Pick an algebraically independent $a$ -tuple of complex numbers $\lambda_{1},\ldots,\lambda_{a}$ . Pick $P$ as in Proposition 3.6 so that $D_{P}((\lambda_{1},\ldots,\lambda_{a}))=M$ .
2.

For each $a+1\leq i\leq m$ , iteratively choose $\lambda_{i}$ to be any value not equal to any of $\lambda_{1},\ldots,\lambda_{i-1}$ so that $D_{P}((\lambda_{i}))$ is nonzero.

We will show that there must be many possible choices for each $\lambda_{i}$ in Step 2. We have that $\lambda$ is a root of the degree- $\left(n(n+1)/2\right)$ polynomial $\prod_{j=0}^{n}P^{(j)}$ of multiplicity $\sum_{t}\frac{t(t+1)}{2}$ , where the summation is over all lengths of runs of ones, with multiplicity, in $D_{P}((\lambda))$ . Since $D_{P}((\lambda))$ has at most $T$ nonzero entries, and $\frac{x(x+1)}{2}$ is convex, $\lambda$ is a root of the degree- $\left(n(n+1)/2\right)$ polynomial $\prod_{j=0}^{n}P^{(j)}$ of multiplicity at most $T(T+1)/2$ . Note that $D_{P}((\lambda))$ is nonzero if and only if $\lambda$ is a root of $\prod_{j=0}^{n}P^{(j)}$ . Hence, the number of possible choices for $\lambda_{i+1}$ is at least

\left\lceil\frac{n(n+1)/2}{T(T+1)/2}\right\rceil-i=\left\lceil\frac{n^{2}+n}{T^{2}+T}\right\rceil-i.

Since $P^{(j)}$ has at most $n$ roots for any $j$ , there are at most $n$ possible values of $\lambda_{i+1}$ corresponding to the same not-all-zero row. Thus, given a choice of $\lambda_{1},\ldots,\lambda_{i},$ there are at least $\frac{1}{n}\left(\left\lceil\frac{n^{2}+n}{T^{2}+T}\right\rceil-i\right)$ possibilities for the $(i+1)$ th row. For each $a\times(n+1)$ safe $T$ -limited saturated matrix, this construction gives at least

\prod_{i=a}^{m-1}n^{-1}\left(\left\lceil\frac{n^{2}+n}{T^{2}+T}\right\rceil-i\right)

elements in $\mathcal{D}_{n}^{m}$ . For any nonnegative integers $b<k$ , we have

\left(k(k-1)\cdots(k+1-b)\right)^{1/b}\geq\left(k(k-1)\cdots(1)\right)^{1/k}\geq\frac{k}{e},

where the first inequality follows from the fact that the left-hand side is decreasing in $b$ , and the second inequality is justified in Section 1.1. Taking $k=\left\lceil\frac{n^{2}+n}{T^{2}+T}\right\rceil-a$ and $b=m-a$ , we find that the number of elements in $\mathcal{D}_{n}^{m}$ is at least

C(a,n,T)\prod_{i=a}^{m-1}n^{-1}\left(\left\lceil\frac{n^{2}+n}{T^{2}+T}\right\rceil-i\right)\geq C(a,n,T)n^{a-m}\left(\frac{\left\lceil\frac{n^{2}+n}{T^{2}+T}\right\rceil-a}{e}\right)^{m-a},

which exceeds the bound required. ∎

To prove Proposition 3.5, it remains to analyze the size of the bound in Lemma 3.7.

Proposition 3.8.

Suppose positive integers $a$ and $T$ with $T$ divisible by $3$ satisfy $T\leq n$ and $(a-2)T/3>n$ . Then we have

C(a,n,T)\geq\frac{1}{n+1}\binom{an}{n}\left(1-a(n+1)2^{-T/3}\right).

Proof.

The number of $a\times(n+1)$ safe matrices with exactly $t$ ones in the first row and $n$ ones in total is at most

f(t)\vcentcolon=\binom{n}{t}\binom{(a-1)n}{n-t}.

Here, the first term counts the number of ways to distribute $t$ ones into the first row and the second term counts the number of ways to distribute the remaining ones. Here, we are ignoring the condition given by $M$ being safe, but use the fact that the last column cannot have ones.

We have, for all $t\leq n-1$ ,

f(t+1)=f(t)\cdot\frac{n-t}{t+1}\cdot\frac{n-t}{(a-2)n+t}<f(t)\frac{n}{t(a-2)}\leq f(t)\frac{T/3}{t}.

For $t\geq 2T/3$ , the function $f$ decays by a factor of at least $2$ when $t$ increases by $1$ . The number of $a\times(n+1)$ safe $T$ -limited saturated matrices is at least, by Corollary 2.10,

\frac{1}{n+1}\binom{a(n+1)}{n}-a\left(\sum_{t\geq T+1}f(t)\right),

as the number of $a\times(n+1)$ $\{0,1\}$ matrices with at least $t$ ones in a given row is at most $f(t)$ . Since $f(T+i)\leq 2^{-i-T/3}f(2T/3)$ , we get

C(a,n,T)\geq\frac{1}{n+1}\binom{a(n+1)}{n}-a2^{-T/3}f(2T/3).

By Vandermonde’s identity, we have

\binom{a(n+1)}{n}\geq\binom{an}{n}=\sum_{i=0}^{n}f(i)\geq f(2T/3).

Hence,

C(a,n,T)\geq\frac{1}{n+1}\binom{a(n+1)}{n}-a2^{-T/3}f(2T/3)\geq\frac{1}{n+1}\binom{a(n+1)}{n}\left(1-a(n+1)2^{-T/3}\right),

which exceeds the desired bound. ∎

We are now ready to prove Proposition 3.5.

Proof of Proposition 3.5.

For $\frac{n}{(\log n)^{2}}\geq m$ , use the lower bound $\left\lvert\mathcal{D}_{n}^{m}\right\rvert\geq\left\lvert\mathcal{D}_{n}^{\operatorname{gen}(m)}\right\rvert$ to get

\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\geq\log\left\lvert\mathcal{D}_{n}^{\operatorname{gen}(m)}\right\rvert\geq\log\left(\frac{1}{n+1}\binom{m(n+1)}{n}\right)=(1+o(1))\log\left(n^{m}\binom{mn}{n}\right),

where the second inequality follows from Corollary 2.10 and the last estimate of the error term follows from bounds $\log(n^{m})\leq n/\log n=o(n)$ and $\log\binom{mn}{n}\geq\log\binom{2n}{n}=\Theta(n)$ .

We use Lemma 3.7 for the remaining regions. For $m\geq n\sqrt{\log n}$ , take $a=n$ and $T=1$ , so $C(a,n,T)\geq 1$ . We have assumed $m\leq\frac{n^{2}+n}{2}=\frac{n^{2}+n}{T^{2}+T}$ , so we may apply Lemma 3.7, which gives

\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\geq(m-n)\log\left(\frac{n+1}{2e}-\frac{1}{2}\right)=(1+o(1))m\log n=(1+o(1))\log(n^{m}).

This is equal to $(1+o(1))\log\left(n^{m}\binom{mn}{n}\right)$ because we can estimate $\log\binom{mn}{n}$ by

\log\binom{mn}{n}\leq\log\left((mn)^{n}\right)\leq 3n\log n=o(m\sqrt{\log n}).

Finally, for $\frac{n}{(\log n)^{2}}\leq m\leq n\sqrt{\log n}$ , take $T/3=10\left\lceil\log n\right\rceil^{3}$ and $a=\left\lceil\frac{m}{T/3}\right\rceil+3$ . For large enough $n$ , we have $m\leq\frac{n^{2}+n}{T^{2}+T}$ , so we can apply Lemma 3.7. For large enough $n$ , we have:

\frac{n+1}{e(T^{2}+T)}-\frac{a}{en}\geq\frac{n}{100T^{2}}\quad\text{and}\quad m-a\geq m\left(1-\frac{1}{\log n}\right),

allowing us to estimate that, using Proposition 3.8, $\log\left(\frac{\left\lvert\mathcal{D}_{n}^{m}\right\rvert}{C(a,n,T)}\right)\geq(1+o(1))\log\left(n^{m}\right)$ . For sufficiently large $n$ , we also have

\binom{an}{n}\geq(\log n)^{-100n}\binom{mn}{n}\quad\text{and}\quad 1-a(n+1)2^{-T/3}\geq\frac{1}{2},

which will allow us to estimate $\log C(a,n,t)\geq(1+o(1))\log\left(\binom{mn}{n}\right)$ . For $n$ large enough for the aformentioned inequalities to hold, putting everything together gives

\left\lvert\mathcal{D}_{n}^{m}\right\rvert\geq\frac{1}{2(n+1)}(\log n)^{-100n}\binom{mn}{n}\cdot\left(\frac{n}{100T^{2}}\right)^{m\left(1-\frac{1}{\log n}\right)},

which is $\left(\binom{mn}{n}n^{m}\right)^{1+o(1)}$ , as desired. ∎

4 $\mathcal{D}_{n}^{m}$ for Large $m$

The goal of this section is to prove Theorem 1.4.

Let $V(m,n)$ denote the number of elements in $\mathcal{D}_{n}^{m}$ with no all-zero rows. As $P^{(j)}$ has at most $n-j$ roots for each $j$ , the $j$ th column of any element of $\mathcal{D}_{n}^{m}$ has at most $n-j$ ones, and so $V(m,n)=0$ for all $m>\frac{n^{2}+n}{2}$ .

Proposition 4.1.

For all $m,n$ , we have

\left\lvert\mathcal{D}_{n}^{m}\right\rvert=\sum_{k=0}^{\frac{n^{2}+n}{2}}\binom{m}{k}V(k,n).

Proof.

The right-hand side counts $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ by conditioning on the number $k$ of not-all-zero rows, since the number of possible submatrices consisting of only those $k$ rows is $V(k,n)$ . ∎

We can now conclude the first part of Theorem 1.4.

Corollary 4.2.

We have, for $m>\frac{n^{2}+n}{2}$ ,

\max\left(\binom{m}{\frac{n^{2}+n}{2}}V\left(\frac{n^{2}+n}{2},n\right),\ \left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert\right)\leq\left\lvert\mathcal{D}_{n}^{m}\right\rvert\leq\binom{m}{\frac{n^{2}+n}{2}}\left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert.

Hence, if $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfy $m(t),n(t)\to\infty$ , then:

(a)

if $m=\Theta(n^{2})$ and $m>\frac{n^{2}+n}{2}$ , then $\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\sim\log\left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert$ ;
(b)

if $\log m=\omega(\log n)$ , then $\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\sim\log\left(\dbinom{m}{\frac{n^{2}+n}{2}}\right)$ .

Proof.

The lower bound of $\binom{m}{\frac{n^{2}+n}{2}}V\left(\frac{n^{2}+n}{2}\right)$ follows by taking the last term in Proposition 4.1, and the lower bound of $\left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert$ follows from noting that $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ is an increasing function of $m$ . The upper bound follows from applying the inequality

\dbinom{m}{\frac{n^{2}+n}{2}}\cdot\dbinom{\frac{n^{2}+n}{2}}{k}\geq\dbinom{m}{k}

after expanding both sides by Proposition 4.1. The asymptotic estimates follow directly from the inequalities. ∎

Proposition 4.1 also tells us that for fixed $n$ , $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ is a polynomial in $m$ of degree $\frac{n^{2}+n}{2}$ . We now compute the value of $V\left(\frac{n^{2}+n}{2}-t,n\right)$ for $t\in\{0,1\}$ , giving us the leading terms of this polynomial. We will first need the following strengthening of Proposition 3.6.

Proposition 4.3.

Let $\Lambda=(\lambda_{1},\ldots,\lambda_{a})$ be affinely algebraically independent, and let $M$ be an $a\times(n+1)$ safe matrix. Note that $M$ is not necessarily saturated.

Let $T$ be a positive integer such that at most one of the rows of $M$ has more than $T$ ones. Then there is a degree- $n$ polynomial $P$ with the property that $D_{P}(\Lambda)=M$ , and the property that for any $\lambda\in\mathbb{C}\setminus\Lambda$ , at most $T$ of the entries of $D_{P}((\lambda))$ are one.

Proof.

Append rows of the form $(1,0,\ldots,0)$ to $M$ until it is saturated. Let $M^{\prime}$ denote the resulting matrix, and let $a^{\prime}$ be the number of rows of $M^{\prime}$ . Note that $M^{\prime}$ is safe. Pick complex numbers $\lambda_{a+1},\ldots,\lambda_{a^{\prime}}$ such that $\Lambda^{\prime}=(\lambda_{1},\ldots,\lambda_{a^{\prime}})$ is algebraically independent.

Now, we apply the argument of Proposition 3.6 to $M^{\prime}$ and $\Lambda^{\prime}$ . Consider some $\lambda\in\mathbb{C}\setminus\Lambda$ . We claim that there exist at least two $b\in[a^{\prime}]$ such that the $a^{\prime}$ -tuple $\Lambda_{b}^{\prime}$ obtained from $\Lambda^{\prime}$ by replacing $\lambda_{b}$ with $\lambda$ is affinely algebraically independent. If $\Lambda^{\prime}$ with $\lambda$ appended is already affinely algebraically independent, the result is clear.

Otherwise, let $Q_{0}$ be a minimal-degree affine algebraic dependence of $(\lambda,\lambda_{1},\ldots,\lambda_{a^{\prime}})$ . As in the proof of Proposition 3.6, $Q_{0}$ must divide all other affine algebraic dependences. We claim that there are at least $3$ variables with a nonzero coefficient in $Q_{0}$ .

Suppose otherwise. Then, there is some nonzero two-variable polynomial $Q$ and distinct constants $\alpha_{1},\alpha_{2}\in\mathbb{C}$ such that $Q(a+b\alpha_{1},a+b\alpha_{2})=0$ for all $a,b\in\mathbb{C}$ . However, substituting $a=\frac{-\alpha_{2}x+\alpha_{1}y}{\alpha_{1}-\alpha_{2}}$ and $b=\frac{x-y}{\alpha_{1}-\alpha_{2}}$ implies $Q(x,y)=0$ for all $x,y\in\mathbb{C}$ , so $Q$ is identically zero, which is a contradiction, as desired.

Now, there are at least two values of $b$ such that $x_{b}$ has nonzero coefficient in $Q_{0}$ . For these values of $b$ , we have that $\Lambda^{\prime}_{b}$ is affinely algebraically independent. At least one of these choices of $b$ must have the property that the $b$ th column of $M^{\prime}$ has at most $T$ nonzero entries, implying the desired result. ∎

Proposition 4.4.

We have the following values of $V(m,n)$ :

	$\displaystyle V\left(\frac{n^{2}+n}{2},n\right)$	$\displaystyle=\frac{\left(\frac{n^{2}+n}{2}\right)!}{1!2!\cdots n!}\quad\text{and}\quad$
	$\displaystyle V\left(\frac{n^{2}+n}{2},n-1\right)$	$\displaystyle=\frac{\left(\frac{n^{2}+n}{2}\right)!}{1!2!\cdots n!}\left(1+\frac{(n-1)(n-2)}{4}\right).$

Proof.

For the first formula, note that if an element of $\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}$ has no all-zero rows, then each row must have exactly one nonzero entry and the $j$ th column must have exactly $n+1-j$ ones. We show that all matrices satisfying the aforementioned conditions are in $\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}$ . This gives the desired enumeration, as we are then placing $n+1-j$ indistinguishable rows for each $j\in[n]$ .

To show that all such matrices are attainable, consider the polynomial $(x-\lambda_{1})\cdots(x-\lambda_{n})$ , where $\lambda_{1},\ldots,\lambda_{n}$ are affinely algebraically independent. By Proposition 3.6 on $P=(x-\lambda_{1})\cdots(x-\lambda_{n})$ , $\Lambda=(\lambda_{1},\ldots,\lambda_{n})$ , and $T=1$ , all of the roots of the derivatives of the $P^{(j)}$ are distinct, implying the desired result.

For the second formula, note that if an element of $\mathcal{D}_{n}^{\frac{n^{2}+n}{2}-1}$ has all not-all-zero rows, then it must be one of the following:

(a)

an element of $\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}$ with no all-zero rows, and with the bottom row removed;
(b)

a matrix where the $j$ th column has exactly $n+1-j$ ones, some row has a nonzero entry in exactly two columns (say $n+1-j$ and $n+1-j^{\prime}$ with $j^{\prime}>j+1$ ), and the remaining rows have exactly one nonzero entry each.

The $j^{\prime}>j$ condition can be assumed by symmetry; the $j^{\prime}\neq j+1$ condition arises since $P^{(n-j^{\prime})}(t)=P^{(n-j^{\prime}-1)}(t)=0$ would imply that $t$ is a multiplicity $2$ root of $P^{(n-j^{\prime})}$ , giving $P^{(n-j^{\prime})}$ more that $j^{\prime}$ roots counted with multiplicity.

We show that such matrices are attainable. The result is clear for matrices in (a). For matrices in (b), applying Proposition 4.3 to the value $T=1$ , the $1$ -tuple $\Lambda=(0)$ , and the one-row matrix with ones in columns $n+1-j$ and $n+1-j^{\prime}$ , we get a suitable polynomial.

Now, we count this set of matrices. There are $V\left(\frac{n^{2}+n}{2},n\right)$ matrices in (a), since the bottom row is uniquely determined by the other rows. The number of matrices in (b) is, conditioning on $j$ and $j^{\prime}$ ,

	$\displaystyle\sum_{2\leq j+1<j^{\prime}\leq n}\frac{\left(\frac{n^{2}+n}{2}-1\right)!}{1!2!\cdots n!}\cdot jj^{\prime}$	$\displaystyle=\frac{\left(\frac{n^{2}+n}{2}-1\right)!}{1!2!\cdots n!}\cdot\sum_{j^{\prime}=3}^{n}j^{\prime}\sum_{j<j^{\prime}-1}j$
		$\displaystyle=\frac{\left(\frac{n^{2}+n}{2}-1\right)!}{1!2!\cdots n!}\cdot\sum_{j^{\prime}=3}^{n}\frac{j^{\prime}(j^{\prime}-1)(j^{\prime}-2)}{2}$
		$\displaystyle=\frac{\left(\frac{n^{2}+n}{2}-1\right)!}{1!2!\cdots n!}\cdot\frac{(n+1)n(n-1)(n-2)}{8},$

giving the desired formula. ∎

The second part of Theorem 1.4 directly follows.

Corollary 4.5.

When $n$ is fixed, we have

\left\lvert\mathcal{D}_{n}^{m}\right\rvert=\frac{\left(\frac{n^{2}+n}{2}\right)!}{1!2!\cdots n!}\binom{m}{\frac{n^{2}+n}{2}}+\frac{\left(\frac{n^{2}+n}{2}\right)!}{1!2!\cdots n!}\left(1+\frac{(n-1)(n-2)}{4}\right)\binom{m}{\frac{n^{2}+n}{2}-1}+O\left(m^{\frac{n^{2}+n}{2}-2}\right).

5 Future Work

In Theorem 1.3, we believe the lower bound is the correct asymptotic formula for $\left\lvert\mathcal{D}_{n}^{m}\right\rvert$ .

Conjecture 5.1.

For $m(t),n(t)\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ satisfying $n(t)\to\infty$ and $1<m(t)\leq\frac{n(t)^{2}+n(t)}{2}$ , we have

\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\sim\log\left(n^{m}\binom{mn}{n}\right).

If this conjecture is true, then if $m=\omega(n^{2})$ , $\log\left\lvert\mathcal{D}_{n}^{m}\right\rvert\sim\log\left(\dbinom{m}{\frac{n^{2}+n}{2}}\cdot\left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert\right)$ follows from the inequalities in Corollary 4.2, since Stirling’s approximation on the formula for $V\left(\frac{n^{2}+n}{2},n\right)$ in Proposition 4.4 would give $\log\left(V\left(\frac{n^{2}+n}{2},n\right)\right)\sim\log\left\lvert\mathcal{D}_{n}^{\frac{n^{2}+n}{2}}\right\rvert$ .

Our proof of upper bounds on $\mathcal{D}_{n}^{m}$ for $m\leq\frac{n^{2}+n}{2}$ gives no information about the elements of the set $\mathcal{D}_{n}^{m}$ . A natural further direction to investigate is the properties of the matrices in $\mathcal{D}_{n}^{m}$ .

Question 5.2.

In terms of $m$ and $n$ , how many entries can be ones?

6 Acknowledgments

This research was conducted at the University of Minnesota Duluth REU, and was supported by Jane Street Capital, the NSA (grant number H98230-22-1-0015), and the CYAN Undergraduate Mathematics Fund at MIT.

We would like to thank Noah Kravitz for his helpful discussions and guidance throughout the research and writing process. We are also grateful to Brian Lawrence for valuable feedback on this paper, and Sean Li for helpful discussions. Finally, we would like to especially thank Joe Gallian for organizing and running the REU.

References

[1] Noga Alon, Noah Kravitz and Kevin O’Bryant “Counting Dope Matrices” In arXiv, 19 May 2022 URL: https://arxiv.org/abs/2205.09302
[2] Nachum Dershowitz and Shmuel Zaks “The cycle lemma and some applications” In European J. Combin. 11.1, 1990, pp. 35–40 DOI: 10.1016/S0195-6698(13)80053-4
[3] Ira Gessel and Gérard Viennot “Binomial determinants, paths, and hook length formulae” In Adv. in Math. 58.3, 1985, pp. 300–321 DOI: 10.1016/0001-8708(85)90121-5
[4] Melvyn B. Nathanson “Interactions of zeros of of polynomials and multiplicity matrices” In arXiv arXiv, 15 March 2022 URL: https://arxiv.org/abs/2203.02477
[5] Lajos Rónyai, László Babai and Murali K. Ganapathy “On the number of zero-patterns of a sequence of polynomials” In J. Amer. Math. Soc. 14.3, 2001, pp. 717–735 DOI: 10.1090/S0894-0347-01-00367-8

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139

Email Address: [email protected]

Generic Classification and Asymptotic Enumeration of Dope Matrices

Abstract

1 Introduction

Theorem 1.1.

Theorem 1.2.

Theorem 1.3.

Theorem 1.4.

1.1 Preliminaries and Notation

Lemma 1.5.

Proof.

Lemma 1.6.

Theorem 1.7.

Proof.

2 Generic Dope Matrices

Theorem 2.1.

Outline of Proof of Theorem 1.1 when m=2m=2.

Definition 2.2.

2.1 Reduction to the Key Lemma

Lemma 2.3.

Proof of Theorem 1.1.

2.2 Demonstration of Proof Technique

2.3 Derivatives as Linear Combinations

Lemma 2.4.

Proof.

2.4 Combining Roots

Proposition 2.5.

Lemma 2.6.

Proof.

Proof of Lemma 2.3.

2.5 Enumeration

Definition 2.7.

Theorem 2.8.

Proof of Theorem 1.2.

Remark 2.9.

Corollary 2.10.

Proof.

3 𝒟nm\mathcal{D}_{n}^{m} for Small mm

Theorem 3.1 (Corollary of Theorem 1.3).

3.1 Upper Bound

Proposition 3.2.

Definition 3.3.

Theorem 3.4.

Proof of Proposition 3.2.

3.2 Lower Bound

Proposition 3.5.

Proposition 3.6.

Proof.

Lemma 3.7.

Proof.

Proposition 3.8.

Proof.

Proof of Proposition 3.5.

4 𝒟nm\mathcal{D}_{n}^{m} for Large mm

Proposition 4.1.

Proof.

Corollary 4.2.

Proof.

Proposition 4.3.

Proof.

Proposition 4.4.

Proof.

Corollary 4.5.

5 Future Work

Conjecture 5.1.

Question 5.2.

6 Acknowledgments

References

Outline of Proof of Theorem 1.1 when $m=2$ .

3 $\mathcal{D}_{n}^{m}$ for Small $m$

4 $\mathcal{D}_{n}^{m}$ for Large $m$