On the Number of Singular Vector Tuples of Hyper-Cubical Tensors

By Shalosh B. EKHAD and Doron ZEILBERGER

Added May 23, 2016: The Conjecture at the end of this article has been brilliantly solved by Jay Pantone. See his article “The Asymptotic Number of Simple Singular Vector Tuples of a Cubical

Tensor”, available from http://arxiv.org/abs/1605.06099.

A week ago, Bernd Sturmfels [St] gave a fascinating Colloquium talk, here at Rutgers, where, among many other interesting facts, he mentioned the following theorem of Shmuel Friedland and Giorgio Ottaviani ([FO]).

Theorem ([F0], Theorem 1). The number of simple singular vector tuples of a generic m_{1} × ⋯ × m_{d} (d-dimensional) tensor equals the coefficient of ∏_{i=1}^{d} t_{i}^{m_{i}−1} in the polynomial

∏_{i=1}^{d} \frac{t̂_{i}^{m_{i}} − t_{i}^{m_{i}}}{t̂_{i} − t_{i}} , t̂_{i} = (∑_{j=1}^{d} t_{j}) − t_{i} .

Let’s call this number c(m_{1}, …, m_{d}).

We first observe that the generating function of this d-dimensional multi-sequence is a nice rational function.

Proposition 1. Let e_{i}(x_{1}, …, x_{d}) be the elementary symmetric function of the indeterminates x_{1}, …, x_{d}, of degree i. We have:

∑_{m_{1}=0}^{∞} … ∑_{m_{d}=0}^{∞} c(m_{1}, …, m_{d})x_{1}^{m_{1}} … x_{d}^{m_{d}} = ∏_{i=1}^{d} x_{i} (∏_{i=1}^{d}(1 − x_{i}))^{−1} (1 − ∑_{i=2}^{d}(i − 1)e_{i}(x_{1}, …, x_{d}))^{−1} .

Proof: Since

\frac{t̂_{i}^{m_{i}} − t_{i}^{m_{i}}}{t̂_{i} − t_{i}} = ∑_{k_{i}=0}^{m_{i}−1} t̂_{i}^{k_{i}}t_{i}^{m_{i}−1−k_{i}} ,

c(m_{1}, …, m_{k}) is the coefficient of ∏_{i=1}^{d} t_{i}^{m_{i}−1} in

∑_{k_{1}=0}^{m_{1}−1} … ∑_{k_{d}=0}^{m_{d}−1} ∏_{i=1}^{d} t̂_{i}^{k_{i}}t_{i}^{m_{i}−1−k_{i}} .

Hence

c(m_{1}, …, m_{d}) = ∑_{k_{1}=0}^{m_{1}−1} … ∑_{k_{d}=0}^{m_{d}−1} ConstantT ermOf ∏_{i=1}^{d} t̂_{i}^{k_{i}}t_{i}^{−k_{i}} .

Let

f(k_{1}, …, k_{d}) := ConstantT ermOf ∏_{i=1}^{d} t̂_{i}^{k_{i}}t_{i}^{−k_{i}} = CoeffOf ∏_{i=1}^{d} t_{i}^{k_{i}} in ∏_{i=1}^{d} (∑_{j=1}^{i−1} t_{j} + ∑_{j=i+1}^{d} t_{j})^{k_{i}} .

By the celebrated MacMahon Master Theorem ([M], Section III, Chapter II, p. 93ff) (with the d × d matrix that is all 1’s except 0 in the diagonal), we have

∑_{k_{1}=0}^{∞} … ∑_{k_{d}=0}^{∞} f(k_{1}, …, k_{d})x_{1}^{k_{1}} … x_{d}^{k_{d}} = (1 − ∑_{i=2}^{d}(i − 1)e_{i}(x_{1}, …, x_{d}))^{−1} .

Since

c(m_{1}, …, m_{d}) = ∑_{k_{1}=0}^{m_{1}−1} … ∑_{k_{d}=0}^{m_{d}−1} f(k_{1}, …, k_{d}) ,

the proposition follows by straightforward generatingfunctionology.

The fact that the generating function of c(m_{1}, …, m_{d}) is a rational function is equivalent to it satisfying a certain partial linear recurrence with constant coefficients, easily deduced from the generating function. Combined with the fact that both c(m_{1}, …, m_{d}) and f(k_{1}, …, k_{d}) are symmetric, enabled us to efficiently compute many values. It also follows (for example using Wilf-Zeilberger algorithmic proof theory, efficiently implemented in [AZ]) that the diagonal sequences

C_{d}(n) := c(n, …, n) [ n repeated d times] ,

are holonomic, alias P-recursive, that means that for each d, the sequence C_{d}(n) satisfies some homogeneous linear recurrence with polynomial coefficients. While one can use the method of [AZ], it is more efficient, since we know a priori that such a recurrence exists, to generate sufficiently many terms and then guess the recurrence. Using this method, we got the following proposition.

Proposition 2. The sequence C_{3}(n) = c(n, n, n) satisfies the following fifth-order linear recurrence equation with polynomial coefficients.

2 (n + 2) (245 n^{4} + 3094 n^{3} + 14447 n^{2} + 29474 n + 22100) (n + 1)^{2} C_{3} (n)

− (n + 2) (21805 n^{6} + 330981 n^{5} + 2012733 n^{4} + 6230951 n^{3} + 10263446 n^{2} + 8425060 n + 2639760) C_{3} (n + 1)

+ (−13230 n^{7} − 249641 n^{6} − 1998705 n^{5} − 8785333 n^{4} − 22847777 n^{3} − 35069178 n^{2} − 29331496 n − 10279296) ·

C_{3} (n + 2)

+ (21560 n^{7} + 413637 n^{6} + 3343917 n^{5} + 14735333 n^{4} + 38132651 n^{3} + 57777574 n^{2} + 47273504 n + 16026528) ·

C_{3} (n + 3)

− (n + 4) (4410 n^{6} + 70147 n^{5} + 452903 n^{4} + 1516515 n^{3} + 2769127 n^{2} + 2601986 n + 975888) C_{3} (n + 4)

+ (n + 5) (n + 4) (n + 3) (245 n^{4} + 2114 n^{3} + 6635 n^{2} + 8882 n + 4224) C_{3} (n + 5) = 0 ,

subject to the initial conditions C_{3}(1) = 1 , C_{3}(2) = 6 , C_{3}(3) = 37 , C_{3}(4) = 240 , C_{3}(5) = 1621 .

Using the methods of [WZ] and [Z], we found the following asymptotic formula. Proposition 3.

C_{3}(n) ∼ \frac{2}{\sqrt{3} π} 8^{n} · n^{−1}·

(1 − \frac{13}{3} n^{−1} + \frac{1477}{27} n^{−2} − \frac{93707}{81} n^{−3} + \frac{8343061}{243} n^{−4} − \frac{2866730137}{2187} n^{−5} + \frac{1204239422533}{19683} n^{−6} + O(n^{−7})) .

We observe that the “connective constant”, 8, is sub-dominant. With any other initial conditions it would have been 9. This is a very rare phenomenon in combinatorics. The sequence C_{3}(n) is sequence A271905 in the On-Line Encyclopedia of Integer Sequences [Sl]. For the record, here are the first few terms: 1, 6, 37, 240, 1621, 11256, 79717, 572928, 4164841, 30553116, 225817021, 1679454816, 12556853401, 94313192616, 711189994357, 5381592930816, 40848410792017, 310909645663332, 2372280474687277, 18141232682656320, 139010366280363601, 1067160872528170536, 8206301850166625797, 63203453697218605440. We tried to find a recurrence for C_{4}(n), but, since 160 terms did not suffice, we gave up. Nevertheless, using numerics, it if extremely likely that

C_{4}(n) ∼ α 81^{n} · n^{− \frac{3}{2}} ,

for some constant α, but we are unable to conjecture its value. For the record, here are the first few terms: 1, 24, 997, 51264, 2940841, 180296088, 11559133741, 765337680384,51921457661905, 3590122671128664, 252070718210663749, 17922684123178825536, 1287832671004683373753, 93368940577497932331288, 6821632357294515590873917, 501741975445243527381995520, 37121266623211130111114816929, 2760712710223967190110979892824, 206267049696409355312012281872181. The first few terms of C_{5}(n) are: 1, 120, 44121, 23096640, 14346274601, 9859397817600, 7244702262723241, 5582882474985676800. The first few terms of C_{6}(n) are: 1, 720, 2882071, 18754813440, 153480509680141, 1435747717722810960. Using reliable numeric estimates we are confident in making the following conjecture. Conjecture:

C_{d}(n) ∼ α_{d} · ((d − 1)^{d})^{n} · n^{−(d−1)/2} ,

for a constant α_{d}.

One of us (DZ) is pledging $100 dollars to the OEIS Foundation in honor of the first prover, and an additional $25 for an explicit expression for α_{d} in terms of d and π.

Readers are welcome to explore further using the Maple package SVT.txt available from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/svt.html, where there are many

more terms of the sequences C_{d}(n) for 3 ≤ d ≤ 6.

References

[AZ] Moa Apagodu and Doron Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Adv. Appl. Math. 37 (2006), 139-152.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html .

[FO] Shmuel Friedland and Giorgio Ottaviani, The number of singular vector tuples and uniqueness of best rank-one approximation of tensors, Journal Found. Comput. Math. 14 (2014), 1209-1242.

http://arxiv.org/abs/1210.8316 .

[M] Major Percy A. MacMahon, Combinatory Analysis, Originally published by Cambridge University Press, 1917, 1918, reprinted by Chelsea, N.Y., 1984.

[Sl] Neil J.A. Sloane, “The On-Line Encyclopedia of Integer Sequences”, http://www.oeis.org.

[St] Bernd Sturmfels, Eigenvectors of Tensors, Colloquium talk, Rutgers University, April 22, 2016.

[WZ] Jet Wimp and Doron Zeilberger, Resurrecting the asymptotics of linear recurrences, J. Math. Anal. Appl. 111 (1985), 162-177.

http://www.math.rutgers.edu/~zeilberg/mamarimY/WimpZeilberger1985.pdf .

[Z] Doron Zeilberger, AsyRec: A Maple package for Computing the Asymptotics of Solutions of Linear Recurrence Equations with Polynomial Coefficients, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, April 4, 2008.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/asy.html .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

zeilberg at math dot rutgers dot edu ; http://www.math.rutgers.edu/~zeilberg/ .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

( http://www.math.rutgers.edu/~zeilberg/pj.html) and arxiv.org .

First Written: April 29, 2016 ; This version: April 30, 2016 .