The standard formula for determinants of an n×n matrix (equation 1 in the paper) is the sum of n! terms, one term for each permutation of {1..n}.
The paper details a method (equation 11) in which the sum is instead over all what they call »partial partitions of {1..n}«, denoted PP(n). I don’t know the size of PP(n), but if their claim is correct then PP(n) has exponentially less elements than S(n) (which has n! elements). I don’t see the value of |PP(n)| in the paper, but if it’s O(n^42), that would be an example of something that’s superexponentially smaller/faster. (n! is approximately n^n/e^n, the Stirling Formula.)
There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a singleton. For example, the partial partitions of {1,2,3} are:
but most of these contain a part that only has one element. For example {1} | {2, 3} has the singleton part {1}. Only five of them have no singleton part:
{}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
(In fact all five of these consist of just a single part, but that’s just an artifact of using such a small example. If there are more than three elements then we can have things like {1, 2} | {3, 4}.)
In general the number of partial partitions of n elements that have no singleton parts is the n’th Bell number[0]. The Bell numbers grow much more slowly than the factorials, but still much faster than any polynomial.
Comments
A new explicit formula for the determinant that contains superexponentially fewer terms than the usual Leibniz formula
What does "superexponentially fewer" mean?
»More than exponential«.
The standard formula for determinants of an n×n matrix (equation 1 in the paper) is the sum of n! terms, one term for each permutation of {1..n}.
The paper details a method (equation 11) in which the sum is instead over all what they call »partial partitions of {1..n}«, denoted PP(n). I don’t know the size of PP(n), but if their claim is correct then PP(n) has exponentially less elements than S(n) (which has n! elements). I don’t see the value of |PP(n)| in the paper, but if it’s O(n^42), that would be an example of something that’s superexponentially smaller/faster. (n! is approximately n^n/e^n, the Stirling Formula.)
There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a singleton. For example, the partial partitions of {1,2,3} are:
but most of these contain a part that only has one element. For example {1} | {2, 3} has the singleton part {1}. Only five of them have no singleton part: (In fact all five of these consist of just a single part, but that’s just an artifact of using such a small example. If there are more than three elements then we can have things like {1, 2} | {3, 4}.)In general the number of partial partitions of n elements that have no singleton parts is the n’th Bell number[0]. The Bell numbers grow much more slowly than the factorials, but still much faster than any polynomial.
[0] https://en.wikipedia.org/wiki/Bell_number