Counting Quasi-idempotent Irreducible Integral Matrices

E. Thörnblad and J. Zimmermann Department of Mathematics Uppsala University Box 480 751 06 Uppsala Sweden

                   erik.thornblad@math.uu.se
                  jakob.zimmermann@math.uu.se

Abstract Given any polynomial p in ℂ[X], we show that the set of irreducible matrices satisfying p(A) = 0 is finite. In the specific case of the polynomial p(X) = X^{2} − nX, we count the number of irreducible matrices in this set and analyze the resulting sequences and their asymptotics. Such matrices turn out to be related to generalized compositions and generalized partitions.

1 Introduction

In this paper we study the finiteness of the set of irreducible matrices that are annihilated by a given polynomial. This seems to be a classical problem in the spectral theory of integral matrices; however, we have not been able to find an answer to this question in the literature. We answer this question by the following theorem. Theorem 1. For any polynomial p ∈ ℂ[X], the set of irreducible integer matrices A such that p(A) = 0 is finite.

A related question was studied by Eskin, Mozes and Shah [5], who showed that the set of integral matrices with a given characteristic polynomial is, in general, not finite. All matrices in such a set are necessarily of the same dimension, something that is not true in our setting. Obviously their result implies that the set of integral matrices A satisfying p(A) = 0 is infinite for some polynomials p (namely, the characteristic polynomials), so we cannot expect Theorem 1 to be true for arbitrary matrices. As an example, note that the polynomial X − 1 annihilates the identity matrix of any dimension, so the above theorem is false for any class containing all identity matrices.

The motivation to study these questions comes from higher representation theory. The more general finiteness problem is motivated by a technique that is used when trying to understand certain 2-representations of finitary 2-categories; see [14]. The main idea is that there exists an element whose action is given by a non-negative, irreducible integral matrix that has to be annihilated by a certain polynomial. With this information one then tries to find all possible such matrices. In small cases, this can be done by hand, but a question that occurs quite naturally is whether or not this, in principle, always is possible, i.e., if there are always only finitely many such matrices, which is why we study this question here. For more details we refer the interested reader to [11, 13, 15, 16, 17].

Given that there is a finite number of irreducible integral matrices annihilated by a polynomial p, a natural next question is whether the cardinality of this set can be determined. For arbitrary polynomials, this seems difficult. However, for the polynomials f_{n} = X^{2} − nX, this can be done. In fact, we count these matrices in two different ways. First, we simply count all of them, which turns out to be equivalent to counting the number of generalized compositions. Secondly, we count these matrices up to permutation of their basis vectors. That is, we identify two k × k-matrices A, B if there exists a k × k-permutation matrix P such that conjugation of A by P yields B. This second case is more relevant to the problems that motivated this paper. There we know that there exists a basis such that the action is given by irreducible, non-negative matrices. However, the order of the basis vectors does not affect the problem; in other words we do not care about it and identify matrices that can be obtained from each other by permutation of basis vectors. A closed formula for the number of such matrices (in either of the two cases) is not attainable, but we determine the asymptotics of these sequences and show that they are in bijection to classes of generalized compositions and generalized partitions.

Our interest in the polynomial f_{n} = X^{2} − X stems from the following observation. Let A be a finite-dimensional ℂ-algebra of dimension n. Then F := A ⊗_{ℂ} A is an A-A-bimodule. It acts on the category of A-A-bimodules from the left by taking tensor products over A, i.e., for a A-A-bimodule M, the action of F is given by F (M) = A ⊗_{ℂ} A ⊗_{A} M. Now, we can observe that

F^{2} = F ∘ F = A ⊗_{ℂ} A ⊗_{A} A ⊗_{ℂ} A ≅ (A ⊗_{ℂ} A)^{⊕n} = F^{⊕n}.

Thus the action of F is quasi-idempotent. Therefore, on the level of the Grothendieck group, F induces a linear transformation that corresponds to a matrix [F] satisfying f_{n}([F]) = 0, i.e., the matrices mentioned in the paragraph above. These kinds of problems appear, for instance, in [15, 16].

The rest of the paper is outlined as follows. In the next section we introduce most of the necessary notation and preliminary results that we will need throughout the paper. In Section 3 we give a proof of Theorem 1. In Section 4 we study the integer sequences given by the number of irreducible integral matrices satisfying X^{2} = nX, both when counting all matrices and when identifying matrices that are the same after permuting their basis vectors. We show how these sequences are related to other known sequences, and discuss their asymptotics.

2 Preliminaries

2.1 Basic definitions and notation

All matrices in this paper are assumed to be square matrices containing only integer elements. We denote by Mat_{k,k}(𝕂) the set of k × k-matrices with elements in the set 𝕂, and denote by 0 the matrix (of appropriate size) of all zeros. For any matrix A, we denote by (A)_{i,j} the element in the i:th row and j:th column of A. For two matrices A, B of the same size, we say that A ≤ B provided that (A)_{i,j} ≤ (B)_{i,j} for all i, j. If A ≤ B and A ≠ B, then we write A < B. This defines a partial order on Mat_{k,k}(ℤ_{≥0}).

If (A)_{i,j} > 0 for all i, j, then A is called positive. If (A)_{i,j} ≥ 0 for all i, j, then A is called non-negative. We say that A is primitive if it is non-negative and there exists k > 0 such that A^{k} is positive. If A is non-negative and there for each pair i, j exists some k such that (A^{k})_{i,j} is positive, then A is said to be irreducible.

For f ∈ ℂ[X], we define the sets

K_{f}^{>0} = ⋃_{k>0}{A ∈ Mat_{k,k}(ℤ_{>0}) : f(A) = 0}
K_{f}^{≥0} = ⋃_{k>0}{A ∈ Mat_{k,k}(ℤ_{≥0}) : A is irreducible, f(A) = 0}

of all irreducible square positive (resp. non-negative) integral matrices that are annihilated by f. In particular, these sets contain 1×1-matrices. As mentioned above, we will study the case of f = X^{2} − nX in more detail, and define therefore f_{n}(X) := X^{2} − nX, K_{n}^{≥0} := K_{f_{n}}^{≥0} and K_{n}^{>0} := K_{f_{n}}^{>0}.

In Section 4 we count the elements in K_{n}^{≥0} in two different ways. First, we simply count all of them. Secondly, we count all matrices up to permutation of basis vectors, by which we mean the following. Let A, B ∈ Mat_{k,k}(ℤ_{≥0}) and denote by S_{k} the symmetric group on k elements. Then, to each σ ∈ S_{k}, we assign the (permutation) matrix P_{σ}, which is defined by P_{σ}e_{i} = e_{σ(i)}, on the elements of the standard basis {e_{i}} ⊆ ℝ^{k}. Note that P_{σ} is an orthogonal matrix, i.e., P_{σ}^{−1} = P_{σ}^{t}. We say that A and B are the same up to permutation of basis vectors, denoted A ≈ B, if there exists σ ∈ S_{k} such that P_{σ}^{−1}AP_{σ} = B. The set of all matrices in K_{n}^{≥0} up to permutation of basis vectors is denoted by \overline{K}_{n}^{≥0} := K_{n}^{≥0}/ ≈.

2.2 Auxiliary results

For the proofs of our results we will need the following statement.

Theorem 2. The semigroup ℤ_{≥0}^{k} is noetherian, for every k > 0, i.e., all of its ideals are finitely generated.

Proof. We may consider α ∈ Z_{≥0}^{k} as the exponent of a monomial X_{1}^{α_{1}}X_{2}^{α_{2}} ⋯ X_{k}^{α_{k}} in the polynomial ring ℂ[X_{1}, …, X_{n}]. With this identification, the result follows immediately from [8, Lemma III.12.3].

Now, we can identify the additive semigroup Mat_{k,k}(ℤ_{≥0}) of non-negative integral k × kmatrices with the additive semigroup ℤ_{≥0}^{k^{2}} and thus we get that every ideal in this semigroup is finitely generated. This will be needed in Section 3.

The second important theorem that we are going to use at different points throughout this work is the Perron-Frobenius theorem, more precisely the following version of it.

Theorem 3. Let A = (a_{i,j}) ∈ Mat_{k,k}(ℝ) be a non-negative irreducible matrix. Then the following holds.

(i) A has an eigenvalue r_{A} = r > 0, the so-called Perron-Frobenius eigenvalue, of algebraic multiplicity one and such that r > |λ|, for any other eigenvalue λ of A.

(ii) The Perron-Frobenius eigenvalue r satisfies

min_{i} ∑_{j} a_{ij} ≤ r ≤ max_{i} ∑_{j} a_{ij}.

(iii) If 0 ≤ A < B, then r_{A} ≤ r_{B}. Moreover, if B is irreducible, then r_{A} < r_{B}.

Proof. A proof of the first two statements can be found in Gantmacher’s book [7, Chapter XIII, §2]. More precisely, (i) is Theorem 2 and (ii) is Remark 2. Lastly, (iii) follows from [1, 2.1.5 & 2.1.10].

3 Finiteness proof for irreducible matrices

In this section we prove that the set K_{f}^{≥0} is finite, for any f ∈ ℂ[X]. Before we can do this, we need some notation and a lemma.

Let x, y ∈ ℤ_{≥0}^{r}. We say that x < y provided that x_{i} ≤ y_{i}, for all i, and there exists j such that x_{j} < y_{j}. The reason for this partial order is the fact that we are going to study ideals I in Mat_{k,k}(ℤ_{≥0}) ≊ ℤ_{≥0}^{k^{2}}. By Theorem 2, we know that I is finitely generated, say by some B_{1}, … B_{r}. Then, for every X ∈ I, we have X = ∑_{i=1}^{r} c_{i}B_{i}. So, to every X we can assign its coefficient vector c_{X} = (c_{i}) ∈ ℤ_{≥0}^{r}. Now, we want to compare matrices in X, Y ∈ I and then we get that c_{X} < c_{Y} implies X < Y, so we can study these coefficient vectors instead.

Lemma 4. Let M ⊆ ℤ^{r} be an infinite set. Then there exists an infinite ascending chain in M with respect to < as defined above.

Proof. Note that M is countably infinite, so there is an enumeration of M = {m^{(n)}}, where m^{(n)} = (m_{1}^{(n)}, …, m_{r}^{(n)}). Now, since M is infinite, there exists one component in which m^{(n)} is unbounded. Without loss of generality assume it is the first component. Pick a subsequence n_{k} such that the sequence in the first component of m^{(n_{k})} is strictly increasing, i.e., m_{1}^{(n_{k})} < m_{1}^{(n_{k+1})}, for all k. Then there exists a subsequence (n_{k_{l}}) that is non-decreasing in the second component, i.e., such that m_{2}^{(n_{k_{l}})} ≤ m_{2}^{(n_{k_{l+1}})} for l. Similarly, by taking subsequences of subsequences we get a subsequence (n_{p}) of n_{k} such that m_{1}^{(n_{p})} < m_{1}^{(n_{p+1})} and m_{i}^{(n_{p})} ≤ m_{i}^{(n_{p+1})}, for all p and all 2 ≤ i ≤ r. This yields that m^{(n_{p})} is an infinite ascending chain in M.

Now we are ready to prove the main result of this section, which is Theorem 1 from the introduction.

Theorem 5. For any polynomial f ∈ ℂ[x], the set K_{f}^{≥0} is finite.

Proof. Let f = ∑_{i=0}^{d} α_{i}x^{i}, for α_{i} ∈ ℂ and A ∈ Mat_{k,k}(ℤ_{≥0}) such that f(A) = 0. Then the set of eigenvalues of A is a subset of the zeros of f. Denote by x_{0} the zero of f with the highest absolute value, which by Theorem 3 is an upper bound for the absolute value of all eigenvalues of A.

As a first step we prove that the size of the matrix, i.e., k, is bounded. Since A is irreducible, there exists N > 1 such that B := ∑_{i=0}^{N} A^{i} is positive. On the other hand we know that f(A) = ∑_{i=0}^{d} α_{i}A^{i} = 0, which implies that A^{d} is a ℂ-linear combination of smaller powers of A. Together, we get that there exist γ_{i} ∈ ℂ such that

B = ∑_{i=0}^{d} γ_{i}A^{i},

and as all A^{i} are non-negative, we get that B′ := ∑_{i=0}^{d} A^{i} is positive. Note that the eigenvalues of B′ are of the form ∑_{i=0}^{d} λ^{i}, where λ is an eigenvalue of A. In particular, the largest eigenvalue λ_{B′} of B′ is less than or equal to ∑_{i=0}^{d} |x_{0}|^{i}. Now, we can apply Theorem 3.(ii) to obtain

k ≤ min_{i} ∑_{j} b_{ij} ≤ λ_{B′} ≤ ∑_{i=0}^{d} |x_{0}|^{i},

since all b_{ij} ≥ 1. Thus k is bounded.

Now fix k and assume that the set Y = {A ∈ Mat_{k,k}(ℤ_{≥0}) : f(A)} = 0 is infinite. Consider the ideal I ⊆ Mat_{k,k}(ℤ_{≥0}) ≃ ℤ_{≥0}^{k^{2}} generated by Y. We want to use the fact that ℤ_{≥0}^{k^{2}} is noetherian to obtain a contradiction and thus prove that Y has to be finite.

From Theorem 2 we get that I is finitely generated. Let B_{1}, …, B_{r} be a set of generators of I. Note that f does not necessarily annihilate any of the B_{i}. Then we can express every A ∈ Y as a linear combination of the B_{i}, i.e.,

A = ∑_{i=1}^{r} c_{A,i}B_{i}.

The set M = {c_{A}} of coefficient vectors is an infinite subset of ℤ_{≥0}^{r} and thus Lemma 4 yields that there is an infinite ascending chain c_{A_{k}} in M. On the other hand, we have already seen that this means that this is equivalent to having an infinite ascending chain A_{k} of matrices in Y, with respect to <.

However, by Theorem 3 (3), this yields that there is an infinite sequence of different Perron-Frobenius eigenvalues, a contradiction, as all eigenvalues, in particular, have to be zeros of f.

4 Counting quasi-idempotent matrices

In this section we consider quasi-idempotent matrices, which are matrices A satisfying A^{2} = nA for some n ≥ 1. Recall that

K_{n}^{≥0} = ⋃_{k>0}{A ∈ Mat_{k,k}(ℤ_{>0}) : A^{2} = nA}
K_{n}^{>0} = ⋃_{k>0}{A ∈ Mat_{k,k}(ℤ_{≥0}) : A is irreducible, A^{2} = nA}

Our first result shows that such matrices factorize in a natural way.

Proposition 6. Let A ∈ Mat_{k,k}(ℤ_{≥0}) be irreducible. Then the following are equivalent:

(i) A^{2} − nA = 0, i.e., A ∈ K_{n}^{≥0};

(ii) A has rank 1, trace n and there exist v, w ∈ ℤ_{>0}^{k} such that A = vw^{t};

(iii) A^{2} − nA = 0 and A is positive, i.e., A ∈ K_{n}^{>0}.

Proof. Clearly (iii) implies (i).

To show that (i) implies (ii), let A be an irreducible matrix satisfying A^{2} = nA. The only possible eigenvalues of A are 0 and n. By Theorem 3, we have that n has to be the Perron-Frobenius eigenvalue. In particular, all other eigenvalues have to be zero. Thus it follows that A has rank 1 and trace n, and that it can be written as vw^{t} for some v, w ∈ ℤ^{k}. However, since A is irreducible, it cannot have a row or column consisting of 0’s, which means that all v_{i}, w_{i} are non-zero. Since A is non-negative, we have v, w ∈ ℤ_{>0}^{k}.

Finally, to show that (ii) implies (iii), let A be an irreducible matrix with rank 1 and trace n such that M = vw^{t} for some v, w ∈ ℤ_{>0}^{k}. Then

A^{2} = (vw^{t})(vw^{t}) = v(w^{t}v)w^{t} = v (∑_{i=1}^{k} w_{i}v_{i}) w^{t} = n · vw^{t} = nA,

where we use that ∑_{i=1}^{k} w_{i}v_{i} is the trace of A. Since v and w are positive, A is also positive.

This result shows that, if we want to count matrices in K_{n}^{≥0}, we may restrict our attention to pairs (v, w) ∈ ℤ_{>0}^{k} × ℤ_{>0}^{k} such that ∑_{i=1}^{k} v_{i}w_{i} = n. Such pairs may be seen as generalized compositions as introduced by Corteel and Hitczenko [3]. More formally, a generalized composition of n is a generalized word v_{1}^{w_{1}}v_{2}^{w_{2}} ⋯ v_{k}^{w_{k}} such that v_{i}, w_{i} > 0 and ∑_{i} v_{i}w_{i} = n. To simplify notation, if v = (v_{1}, …, v_{k}) and w = (w_{1}, …, w_{k}), then we write v^{w} to represent the above word. We let

C_{n} = {v^{w} : v, w ∈ ℤ_{>0}^{k}, ∑_{i=1}^{k} v_{i}w_{i} = n}

be the set of all generalized compositions and let c_{n} denote the cardinality of this set.

By Proposition 6, each generalized composition then corresponds to a positive matrix satisfying A^{2} − nA = 0. However, this identification is not injective. For instance, since (2, 2) · (1, 1)^{t} = (1, 1) · (2, 2)^{t}, the generalized compositions 2^{1}2^{1} and 1^{2}1^{2} correspond to the same matrix. Therefore the question becomes, which generalized compositions should be identified? It turns out that we only need to look at those generalized compositions that have greatest common divisor 1, where the greatest common divisor of v^{w} is defined as follows:

gcd (v^{w}) = \begin{cases}gcd (v_{1}, v_{2}, …, v_{k}), & if k > 1; \\ v_{1}, & if k = 1. \end{cases}

For each n ≥ 1, let

D_{n} = {v^{w} ∈ C_{n} : gcd (v^{w}) = 1},

and denote by d_{n} the cardinality of D_{n}.

Lemma 7. The map

φ : D_{n} → K_{n}^{≥0},
v^{w} ↦ vw^{t},

is a bijection.

Proof. By Proposition 6 it follows that φ is well-defined. To show surjectivity, let A ∈ K_{n}^{≥0} be a k × k-matrix. By Proposition 6 we know that there exist v, w ∈ ℤ_{>0}^{k} such that A = vw^{t}. Moreover, if gcd (v^{w}) = c ≠ 1, then we can write A = (\frac{1}{c}v)(cw)^{t}. Setting v′ = \frac{1}{c}v and w′ = cw, we get v^{′w′} ∈ D_{n}, as the trace of A = v′w^{′t} is n and thus φ is surjective.

To show injectivity, let v^{w}, v^{′w′} ∈ D_{n} and assume that φ(v^{w}) = φ(v^{′w′}). Then vw^{t} = v′w^{′t}, which is only possible if v = cv′ or cv = v′ for some c ∈ ℤ. This in turn implies that gcd (v^{w}) ≠ 1 or gcd (v^{′w′}) ≠ 1, a contradiction.

When we count elements of \overline{K}_{n}^{≥0}, we identify matrices that are equal after permutation of basis vectors. Permuting the basis vectors of a matrix vw^{t} corresponds to applying the same permutation to the elements of the generalized composition v^{w} = v_{1}^{w_{1}} … v_{k}^{w_{k}}. Counting up to permutation of basis vector therefore means that we should consider generalized partitions rather than generalized compositions. A generalized partition of n is defined to be a generalized composition v_{1}^{w_{1}}v_{2}^{w_{2}} ⋯ v_{k}^{w_{k}} where we additionally assume that v_{1}w_{1} ≥ v_{2}w_{2} ≥ ⋯ ≥ v_{k}w_{k}. For all n > 0, we let

P_{n} = {v^{w} : v, w ∈ ℤ_{>0}^{k}, ∑_{i=1}^{k} v_{i}w_{i} = n, v_{1}w_{1} ≥ v_{2}w_{2} ≥ ⋯ ≥ v_{k}w_{k}}

be the set of all generalized partitions of n, and we let p_{n} denote the cardinality of P_{n}.

Analogously to the previous case, it turns out that the set of all generalized partitions is slightly larger than \overline{K}_{n}^{≥0} and that the correct set to consider is

Q_{n} = {v^{w} ∈ P_{n} : gcd (v^{w}) = 1},

i.e., , all generalized partitions that have greatest common divisor 1. We denote the cardinality of Q_{n} by q_{n}.

Lemma 8. The map

φ : Q_{n} → \overline{K}_{n}^{≥0},
v^{w} ↦ vw^{t},

is a bijection.

Proof. Analogous to the proof of Lemma 7.

Due to the results above, instead of considering the numbers |K_{n}^{≥0}| and |\overline{K}_{n}^{≥0}|, we may consider the sequences (d_{n})_{n=1}^{∞} (\underline{A280782}) and (q_{n})_{n=1}^{∞} (\underline{A280783}), respectively. The following lemma shows that these are related via Möbius inversion to the sequences (c_{n})_{n=1}^{∞} (\underline{A129921}) and (p_{n})_{n=1}^{∞} (\underline{A006171}), respectively. Recall that the Möbius function μ : ℤ_{>0} → \{−1, 0, 1\} is defined on prime powers p^{k} by

μ(p^{k}) = \begin{cases}0, & if k > 2; \\ −1, & if k = 1; \\ +1, & if k = 0. \end{cases}

and extended to non-prime powers p_{1}^{k_{1}}p_{2}^{k_{2}} … p_{m}^{k_{m}} multiplicatively, i.e., μ(p_{1}^{k_{1}}p_{2}^{k_{2}} … p_{m}^{k_{m}}) := ∏_{i=1}^{m} μ(p_{i}^{k_{i}}).

Lemma 9. The sequences (c_{n})_{n=1}^{∞}, (d_{n})_{n=1}^{∞} ,(p_{n})_{n=1}^{∞} and (q_{n})_{n=1}^{∞} satisfy

\begin{cases}c_{n} = ∑_{r|n} d_{r}; \\ d_{n} = ∑_{r|n} μ(r)c_{n/r}, \end{cases} and  \begin{cases}p_{n} = ∑_{r|n} q_{r}; \\ q_{n} = ∑_{r|n} μ(r)p_{n/r}. \end{cases}

Proof. We prove the first two equalities only. For any n ≥ 1, let C_{n,r} denote the set of generalized compositions v^{w} of n such that gcd(v^{w}) = r. Note that {C_{n,r} : r|n} is a partition of C_{n}. Moreover, for any n ≥ 1 and any r that divides n, the map

C_{n,r} → D_{n/r},
v_{1}^{w_{1}} ⋯ v_{k}^{w_{k}} ↦ (v_{1}/r)^{w_{1}} ⋯ (v_{k}/r)^{w_{k}},

is easily seen to be a bijection. This proves the first equality. The second equality follows from the Möbius inversion formula (cf. [9]). The proof for the sequences (p_{n})_{n=1}^{∞} and (q_{n})_{n=1}^{∞} is done in the same spirit.

4.1 Analysis of the asymptotics

As mentioned, the sequence (c_{n})_{n=1}^{∞} was studied by Corteel and Hitczenko [3]. Using standard methods from analytic combinatorics, they determined the asymptotic growth rate of (c_{n})_{n=1}^{∞}. As we show next, the sequence (d_{n})_{n=1}^{∞} grows asymptotically at the same rate as (c_{n})_{n=1}^{∞}. As a shorthand we write a_{n} ∼ b_{n}, if

lim_{n→∞} \frac{a_{n}}{b_{n}} = 1.

Proposition 10. As n → ∞,

d_{n} ∼ \frac{1}{ρσ′(ρ)}ρ^{−n},  (1)

where σ(z) = ∑_{n≥1} \frac{z^{n}}{1−z^{n}} and ρ is the unique real root of σ(z) = 1 in [0, 1].

Proof. As shown by Corteel and Hitczenko [3], the asymptotics in (1) hold also for (c_{n})_{n=1}^{∞}. It suffices therefore to show that c_{n} ∼ d_{n}. Note that

c_{n} − log_{2}(n)c_{n/2} ≤ ∑_{r|n} μ(r)c_{n/r} = d_{n} ≤ c_{n},

i.e.,

1 − \frac{log_{2}(n)c_{n/2}}{c_{n}} ≤ \frac{d_{n}}{c_{n}} ≤ 1.

Since (c_{n})_{n=1}^{∞} grows exponentially, the left hand side tends to 1 as n → ∞. This completes the proof.

Approximately we have ρ = 0.406148005001 …, and so d_{n} ∼ (0.481225 …)(2.462156 …)^{n}. To arrive at an asymptotic formula for (q_{n})_{n=1}^{∞}, we choose to analyze the more tractable

(p_{n})_{n=1}^{∞}. However, the asymptotics of (p_{n})_{n=1}^{∞} do not, to our knowledge, exist in the literature, though they have been discussed on mathoverflow.net [4], with user ‘lucia’ outlining the correct analysis. For completeness, we outline a version of lucia’s argument in Section 4.1.1 (and correct some incorrect terms in that answer). There it is shown that (p_{n})_{n=1}^{∞} grows superlinearly, which implies that its Möbius inversion (q_{n})_{n=1}^{∞} must grow asymptotically at the same rate, i.e., q_{n} ∼ p_{n}. The proof of this is identical to that of Lemma 10.

Proposition 11. Let S_{m} be as in (2) below. As n → ∞,

q_{n} ∼ \frac{1}{\sqrt{2πS_{1}(ω)}} exp (S_{−1}(ω) + \frac{n}{ω} ) ,

where ω = ω(n) ∈ (0, 1) is the unique solution to S_{0}(ω) = n.

4.1.1 Asymptotics of generalized partitions

We turn to the asymptotics of the sequence (p_{n})_{n=1}^{∞}. The generating function for generalized partitions is

P (z) = ∑_{n≥1} p_{n}z^{n} = ∏_{n=1}^{∞}(1 − z^{n})^{−d(n)},

where d(n) is the number of divisors of n. Such a generating function is precisely of the form covered in Meinardus’s theorem [6]; however, the corresponding Dirichlet series ∑_{n=1}^{∞} d(n)n^{−s}ζ^{2}(s) has a double pole at s = 1, implying that Meinardus’s theorem cannot

be applied in this case. Results by Brigham [2] imply that log p_{n} ∼ π\sqrt{\frac{n log n}{3}}. However, this does not imply precise asymptotics for (p_{n})_{n=1}^{∞}. Our argument is via the saddle-point method; in particular we make use of more general results, which only require us to verify that P satisfies certain conditions.

For our analysis, the series

S_{m}(ω) := ∑_{k≥1} ∑_{ℓ|k} ℓd(ℓ)k^{m}e^{−k/ω},

for m ≥ −1 are important. Note that each S_{m}(ω) is absolutely convergent for any ω ∈ (0, ∞). Series of this form are amenable to analysis using Mellin transforms. By using convolution properties and the Mellin inversion theorem, one finds that

S_{m}(ω) = \frac{1}{2πi} ∫_{m+3−i∞}^{m+3+i∞} ω^{s}Γ(s)ζ(s − m)ζ(s − m − 1)^{2}ds.

The function Γ(s) has simple poles at 0, −1, −2, … and ζ(s) has a simple pole at 1 and trivial zeros at −2, −4, −6, … (which will cancel most or all poles of Γ(s)). Consider the contour integral of the same integrand over the rectangular contour with corners −A − Ri, −A + Ri, m + 3 + Ri, m + 3 − Ri, where A > 1 can be chosen arbitrarily. This contour encloses all poles and can be evaluated using the Cauchy residue theorem. Now let R → ∞ to obtain that S_{m}(ω) can be approximated well by the sum of the residues. We obtain, for any A > 1,

\frac{S_{m}(ω)}{(m + 1)!} = \begin{cases}ζ(2)ω (log ω + γ + \frac{ζ′(2)}{ζ(2)}) + \frac{log ω}{4} + \frac{log 2π}{4} − \frac{1}{288ω} + O(ω^{−A}), & if m = −1; \\ ζ(2)ω^{2} (log ω + 1 + γ + \frac{ζ′(2)}{ζ(2)}) + \frac{ω}{4} + \frac{1}{288} + O(ω^{−A}), & if m = 0; \\ ζ(2)ω^{m+2} (log ω + H(m + 1) + γ + \frac{ζ′(2)}{ζ(2)}) + \frac{ω^{m+1}}{4(m+1)} + O(ω^{−A}), & if m ≥ 1, \end{cases}

(2)

where H(m) := ∑_{k=1}^{m} k^{−1}, and f(ω) = O(g(ω)) means that lim sup_{ω→∞} f(ω)/g(ω) < ∞. For |θ| < π we have the expansion

log P (e^{iθ−1/ω}) − log P (e^{−1/ω}) = ∑_{k≥1} ∑_{ℓ|k} ℓd(ℓ)e^{−k/ω} (\frac{e^{ikθ} − 1}{k})

= ∑_{k≥1} ∑_{ℓ|k} ℓd(ℓ)e^{−k/ω} ∑_{m≥1} \frac{(iθ)^{m}k^{m−1}}{m!}

= ∑_{m≥1} \frac{(iθ)^{m}}{m!} ∑_{k≥1} ∑_{ℓ|k} ℓd(ℓ)k^{m−1}e^{−k/ω}

= ∑_{m≥1} \frac{(iθ)^{m}}{m!} S_{m−1}(ω).

Note also that log P (e^{−1/ω}) = S_{−1}(ω).

The asymptotic growth rate of the sequence (p_{n})_{n=1}^{∞} can be expressed in terms of n and the functions S_{−1}, S_{0} and S_{1} as follows.

Theorem 12. As n → ∞,

p_{n} ∼ \frac{1}{\sqrt{2πS_{1}(ω)}} exp (S_{−1}(ω) + \frac{n}{ω} ) ,

where ω = ω(n) is the unique solution in (0, ∞) to S_{0}(ω) = n. Proof. The result can be deduced from the more general result [6, Theorem VIII.4], provided that the function P is H -admissible, which in this case is equivalent to verifying that the following conditions are satisfied.

(i) S_{0}(ω) → ∞ and S_{1}(ω) → ∞ as ω → ∞. (ii) There exists a function θ_{0} : (0, ∞) → (0, π) such that

∑_{m≥3} \frac{(iθ)^{m}}{m!} S_{m−1}(ω) → 0,

as ω → ∞, uniformly in 0 < |θ| < θ_{0}(ω). (iii) For the same function θ_{0},

ℜ (\frac{1}{2} log S_{1}(ω) + ∑_{m≥1} \frac{(iθ)^{m}}{m!} S_{m−1}(ω)) → −∞,

as ω → ∞, uniformly in θ_{0}(ω) < |θ| < π.

Using (2), the first condition is obviously true, and the last two can be readily checked to hold true for θ_{0}(ω) = ω^{−a}, for any 4/3 < a < 3/2. Further details are omitted. Corollary 13. As n → ∞,

p_{n} ∼ \frac{1}{ω^{1/4}(2n)^{1/2}} exp (\frac{2n}{ω} − ω (ζ(2) − \frac{1}{4}) − \frac{1}{288}) ,

where ω = ω(n) is the unique solution in (0, ∞) to S_{0}(ω) = n. Furthermore,

ω ∼ \frac{2}{π} \sqrt{\frac{3n}{log n}},

as n → ∞, which implies

log p_{n} ∼ π\sqrt{\frac{n log n}{3}}.

5 Acknowledgments

The second author wants to thank his supervisor Volodymyr Mazorchuk for proposing the problem, many very helpful discussions and for double-checking the counting. Moreover, he would like to thank Konstantinos Tsougkas for discussions concerning the proof of Lemma 4, Andrea Pasquali for discussions regarding Section 3 and Daniel Tubbenhauer for discussions about Theorem 5.

References

[1] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, 1979.

[2] N. A. Brigham, A general asymptotic formula for partition functions, Proc. Amer. Math. Soc. 1 (1950), 182–191.

[3] S. Corteel and P. Hitczenko, Generalizations of Carlitz compositions, J. Integer Sequences, 10 (2007), Paper 07.8.8.

[4] David Ellis, Mathoverflow question, Number of representations of an integer as an (arbitrary) sum of products, March 10 2014. Available at https://tinyurl.com/ydyrvnkg.

[5] A. Eskin, S. Mozes, and N. Shah, Unipotent flows and counting lattice points on homogeneous varieties, Ann. of Math. 143 (1996), 253–299.

[6] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[7] F. Gantmacher, The Theory of Matrices, Volume 2, Chelsea Publishing Company, 1959.

[8] P. A. Grillet, Abstract Algebra, Springer Science + Business Media, LLC, 2007.

[9] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fourth Edition, Oxford University Press, 1960.

[10] T. Kildetoft and V. Mazorchuk, Special modules over positively based algebras, Documenta Math., 21 (2016), 1171–1192.

[11] T. Kildetoft, M. Mackaay, V. Mazorchuk, and J. Zimmermann, Simple transitive 2representations of small quotients of Soergel bimodules, to appear in Trans. Amer.

Math. Soc., DOI: https://doi.org/10.1090/tran/7456.

[12] K. H. Kim, N. S. Ormes, and F. W. Roush, The spectra of nonnegative integer matrices via formal power series, J. Amer. Math. Soc. 13 (2000), 773–806.

[13] M. Mackaay and V. Mazorchuk, Simple transitive 2-representations for some 2subcategories of Soergel bimodules, J. Pure Appl. Algebra 221 (2017), 565–587.

[14] V. Mazorchuk and V. Miemietz, Cell 2-representations of finitary 2-categories, Compos. Math. 147 (2011), 1519–1545.

[15] V. Mazorchuk and V. Miemietz, Transitive 2-representations of finitary 2-categories, Trans. Amer. Math. Soc. 368 (2016), 7623–7644.

[16] V. Mazorchuk and X. Zhang, Simple transitive 2-representations for two nonfiat 2-categories of projective functors, preprint, January 1 2016. Available at

    https://arxiv.org/abs/1601.00097.

[17] J. Zimmermann, Simple transitive 2-tepresentations of Soergel bimodules in type B_{2}, J. Pure Appl. Algebra 221 (2017), 666–690.

2010 Mathematics Subject Classification: Primary 15B36; Secondary 05A15, 05A16. Keywords: generalized composition, generalized partition, quasi-idempotent matrix, positive integral matrix.

(Concerned with sequences \underline{A006171} \underline{A129921}, \underline{A280782}, and \underline{A280783}.)

Received February 24 2017; revised versions received November 3 2017; April 6 2018. Published in Journal of Integer Sequences, May 9 2018.

Return to Journal of Integer Sequences home page.