Get Permanent Results Faster by Counting Stars

AI Statement

This work was developed in an exchange with GPT-6 Astra. The author laid out the old story that embedding counts are linear combinations of homomorphism counts (see, e.g., [25, 26, 27, 29, 30, 31, 32, 33, 34, 37, 38, 35, 36, 28, 39, 4]) and suggested finding a cutoff between different evaluation methods in view of the superexponential number of terms incurred by this technique. The LLM developed the vast majority of the technical work and the author subsequently invested significant effort in distilling the core idea and improving the presentation.

Introduction

We give a dynamic program that computes the permanent of an $n \times n$ matrix $A$

significantly faster than previous algorithms. Below, let $O^*(\cdot)$ suppress polynomial factors.

For comparison, known algorithms based on Ryser’s and Glynn’s formulas use $O(2^n n)$ operations [2, 5]. Knuth asked whether $\operatorname{per}(A)$ for a general real $n \times n$ matrix $A$ can be computed using fewer than $2^n$ arithmetic operations [1 Exercise 4.6.4–11, p. 497]. Writing the running time as $O(2^n/s(n))$, Björklund [7] and Li [8] obtain savings $s(n) = \exp(\Omega(\sqrt{n/\log n}))$ and $\exp(\Omega(\sqrt{n}))$, respectively, for integer matrices with polynomially many bits. For finite rings with $q \le n$ elements, Björklund and Williams [9] achieve savings $\exp(\Omega(n/q))$. Knuth’s question for general real matrices however remained unanswered, and savings were only known conditionally [10] under Strassen’s asymptotic rank conjecture [12, 13].

The Algorithm

Throughout, we view $A$ as the edge weights of a complete bipartite graph $G = (L \cup R, E)$ with left vertices $L = \{u_1,\ldots,u_n\}$, right vertices $R = \{v_1,\ldots,v_n\}$, and weight $A_{ij}$ on the edge $u_i v_j$. Moreover, we write $\mathcal{P}_n$ for the set-partitions of $[n]$, with $|\mathcal{P}_n| = \exp((1+o(1))n\log n)$.

The Binet–Minc identity

The starting point of our algorithm is the classical Binet–Minc formula, which expresses the permanent as a signed sum over $|\mathcal{P}_n|$ terms that are individually easy to compute. As $|\mathcal{P}_n|$ is superexponential, we cannot directly use this formula to obtain faster permanent algorithms. In this paper, we develop mechanisms for evaluating the formula more efficiently.

To explain the Binet–Minc formula itself, start with the matching $M$ of $n$ disjoint edges $u_i s_i$. A left-pinned map $\varphi$ from $M$ to $G$ is a map $\varphi: V(M) \to V(G)$ with $\varphi(u_i) = u_i$ and $\varphi(s_i) \in R$ for all $i \in[n]$. Its weight is $w(\varphi) = \prod_i A_{i,\varphi(i)}$, where we abuse notation and read $\varphi(s_i) = v_j$ as $\varphi(i) = j$. Write $\Phi(M)$ for the set of left-pinned maps from $M$ to $G$. As the injective maps $\varphi\in\Phi(M)$ correspond to permutations of $[n]$, we have

While general maps $\varphi\in\Phi(M)$ need not be injective, we can isolate the injective maps by Möbius inversion. For a partition $\pi\in\mathcal{P}_n$, define the quotient $M/\pi$ of $M$ by identifying, for every block $B \in\pi$, the vertices $\{s_i \mid i \in B\}$ to a vertex $s_B$. Then $M/\pi$ is a disjoint union of stars, a star forest. We define left-pinned maps from $M/\pi$ exactly as above and denote their set by $\Phi(M/\pi)$. The Binet–Minc identity (cf. Theorem 2.1) now recovers the right-hand side of (1) by signed cancellation of map counts, using coefficients $\mu(\pi) \in\mathbb{Z}$:

For a fixed partition $\pi\in\mathcal{P}_n$, the inner sum in (2) factors over the stars, as each star can independently choose a placement $\varphi(s_B) = v_j$ for its center $s_B$. We obtain:

The right-hand side can be evaluated with $O(n^2)$ ring operations. Together with (2), this allows us to evaluate $\operatorname{per}(A)$ with $O^*(|\mathcal{P}_n|)$ ring operations, which is far from optimal.

Dynamic programming baseline

In preparation for the full construction, we first evaluate (2) by a dynamic programming approach that constructs the partitions $\pi\in\mathcal{P}_n$ and maps $\varphi\in\Phi(M/\pi)$ together, one star at a time. This already yields $O^*(2^n)$ time. At any given point in the construction, the program only remembers the set of left vertices used so far and a little information about one currently active star that is being constructed. The full dynamic program, discussed later, will use more states.

More formally, the basic DP tracks contributions of partial maps that already cover a set $S \subseteq[n]$ of left vertices and have a currently active star of size $k \in\mathbb{N}$ whose center maps to a given right vertex $v_j \in R$. We use $(k,j)=(0,0)$ when no star is active. The table is organized as follows:

Starting from the initial entry $D[\varnothing;0,0]=1$, each step either

• begins a new star with the smallest yet uncovered left vertex $u_i$ and chooses its center image $v_j$ on the right, thereby proceeding to $D[S\cup\{i\};1,j]$, or

• grows the current star by adding an arbitrary leaf $i\notin S$ from the left vertices, or

• closes the current star, proceeding to $D[S;0,0]$.

The steps are weighted so that all ways of constructing $(\pi,\varphi)$ contribute a total of $\mu(\pi)w(\varphi)$ to the final value $D[[n];0,0]$, matching the contribution of $(\pi,\varphi)$ in (2). Because the table has $O^*(2^n)$ entries and each depends on polynomially many earlier entries, this approach allows us to evaluate (2) with $O^*(2^n)$ operations. Our actual speedup from Theorem 1.1 follows the same idea, but it adds an extra layer of bookkeeping.

If there were only small stars

Before explaining the full DP leading to Theorem 1.1, imagine first that we could limit the stars grown by the basic DP to have at most $r$ leaves. In this case, covering $|S|=s$ left vertices requires at least $s/r$ stars. Since our DP rules force each new star to begin at the smallest uncovered vertex, the set $S$ must contain the initial segment $1,\ldots,\lceil s/r\rceil$. This forced prefix leaves only $2^{n-s/r}$ choices for $S$, which in turn leaves only $O^*(c_r^n)$ table entries for some $c_r<2$. This idea was already used by Koivisto for partitioning into sets of bounded size [40 Section 2].

Large stars may form in stellar nurseries

While it would be convenient to simply discard large stars, we must find a way to handle them. Our solution is to defer their formation until the very end, where they can be handled in one batch.

More concretely, for a cutoff $r\in\mathbb{N}$ chosen later, we modify the basic DP by (i) growing only stars with at most $r$ leaves, as above, and (ii) allowing the DP to defer the next vertex $u\in L$ to be destined for a large star. Whenever this happens, the DP commits to a right vertex $v\in R$ adjacent to $u$, but not to the actual star with center $v$ that will receive $u$; recall that $\varphi$ may map several star centers to $v$. At the end, we compute the contributions of all large stars simultaneously by summing over all groupings of leaves with the same center image into large stars.

This last step requires some bookkeeping, which we keep in a stellar nursery $\mathbf{d}=(d_1,\ldots,d_n)$, where $d_j$ simply counts deferred leaves with center $v_j$. This data suffices to reconstruct the relevant number of groupings, and it gives rise to an enlarged DP table

A crude bound suggests there could be up to $\binom{2n}{n}$ vectors $\mathbf{d}$, erasing any savings. However, on closer inspection, a delicate trade-off arises: As in the basic DP, each deferred leaf is chosen as the smallest uncovered vertex and therefore extends the initial segment covered by $S$. This reduces the number of relevant DP states, exactly as in the small-star case discussed before. Thus, while tracking stellar nurseries incurs an exponential cost, it also reduces the number of DP states by an exponential factor. The final speedup hinges on the balance between these two factors: the total number of DP states must remain bounded by $(2-\varepsilon)^n$.

From stargazing to number crunching

To make this trade-off favorable, we additionally allow a budget of at most $\alpha_r n$ stars larger than $r$, for sufficiently small $\alpha_r>0$. The centers of these stars then have at most $\alpha_r n$ distinct images, so we only need to consider stellar nurseries with at most $\alpha_r n$ nonzero entries. Counting them together with the compatible covered sets $S$ yields an exponential saving.

To cover all partitions $\pi$, we run the DP at several cutoffs $r$ and large-star budgets $\alpha_r$. As $r$ increases, more stars can be grown directly and fewer need the nursery. By an elementary counting argument, we can identify a fixed finite list of geometrically increasing cutoffs and corresponding fractions $\alpha_r$, independent of $n$, such that every partition $\pi$ is handled by some cutoff: The main text shows an existence statement, and the appendix shows that 280 cutoffs suffice for Theorem 1.1.

To conclude, we assign each partition $\pi\in\mathcal{P}_n$ to a unique cutoff from the finite parameter list and remember this choice when forming large stars from the stellar nursery. Summing contributions over the different cutoffs makes each $(\pi,\varphi)$ contribute exactly $\mu(\pi)w(\varphi)$. Overall, this evaluates (2) with $O^*((2-\varepsilon)^n)$ operations for a fixed $\varepsilon>0$ and proves Theorem 1.1.

Related Ideas

The Binet–Minc identity generalizes formulas found by Binet in 1812; its general form was given by Minc in 1979 [3]. It is an application of Möbius inversion on the lattice of set partitions, which was used for more general subgraph counting problems [25, 26]. The concrete Binet–Minc identity was used algorithmically for rectangular permanents [20]. It also occurs in circuit homogenization [21], set-multilinearization [22], and in works on the complexity of monomial symmetric polynomials [23, 24].

Our algorithm is inspired by Koivisto’s smallest-element ordering for set partitions with bounded block size [40], and by the chromatic-number algorithm of Björklund et al. [11], which combines specialized coloring routines with three-way partitioning under the asymptotic rank conjecture.

Neither False nor Obvious

An exponential improvement over the long-standing $O^*(2^n)$ time algorithms for permanents, under a dubious paper title, should naturally raise doubts. One answer to such concerns is provided in the ancillary proof of the following Lean statement. See Appendix § 8 for the definitions used.

theorem main_abp :
  ∃ (C : ℝ) (d : ℕ), 0 < C ∧ ∀ n : ℕ, ∃ G : ABP n,
    (∀ A : Fin n → Fin n → ℤ, G.output A = permanent A) ∧
    (G.vertices + G.transitions : ℝ) ≤ C * (n+1 : ℝ)^d * (2 : ℝ)^((0.999994 : ℝ)*n)

This certifies that the ABP existence part (over $\mathbb{Z}$) asserted by Theorem 1.1 is true. Let us also explain why it might be true, i.e., why it evades known lower bounds in restricted models.

1. It is known that monotone arithmetic circuits for the permanent require $\Omega(2^n)$ size [14]. Our algorithm however crucially uses signed terms and their cancellations.

2. ABPs for the permanent require size $\Omega(2^n)$ when every source-to-sink path uses the same fixed row order [15 Theorem 2.4]. While our rule for beginning stars would be compatible with the ascending row order, arbitrary uncovered left vertices may be added as leaves to the current star. This means that different walks through the ABP can use different row orders.

3. The standard conversion from ABPs to determinants translates our Theorem 1.1 into a determinantal representation of dimension $O^*((2-\varepsilon)^n)$ for the permanent. Landsberg and Ressayre [16] prove a $2^n-1$ lower bound under equivariance, but this requires that row permutations of the input lift to compatible symmetries of the representation. Because we need to choose the smallest uncovered left vertex when beginning a new star, our rules impose an order on the left vertices, so our representation lies outside this model.

Note also that the recent subexponential $\#3$-SAT algorithms [41, 42] give $2^{o(v+e)}$ time for counting perfect matchings in graphs with $v$ vertices and $e$ edges, when used with a standard reduction. For dense $n \times n$ permanent instances, this encoding has $\Theta(n^2)$ variables, so it does not give the bound in Theorem 1.1. However, a more efficient reduction is not ruled out.

Preliminaries

Throughout, rings are commutative with identity, and additions and multiplications have unit cost. For a statement $\phi$, the Iverson bracket $[\phi]$ is 1 if $\phi$ holds and 0 otherwise.

The permanent counts injective left-pinned maps from the matching $M$ to $G$. Binet–Minc recovers this count from left-pinned maps of the star forests $M/\pi$. Identify each left vertex $u_i$ with its ordered label $i$. For a nonempty block $B$ and a partition $\pi$, let

Proof. Fix a map $f:[n]\to[n]$ sending each left vertex $u_i$ to the right vertex $v_{f(i)}$, and let $\sigma$ partition the left vertices by their images under $f$. The map $f$ contributes the weight $\prod_{i=1}^{n}A_{i,f(i)}$ for each partition $\pi$ on whose blocks it is constant, that is, for each $\pi$ refining $\sigma$. The total coefficient of this contribution is therefore

The inner sum is the signed sum over permutations of $C$: their cycles have supports $B$, and a support of size $b$ admits $(b-1)!$ cycles, each of sign $(-1)^{b-1}$. This sum equals $|C|=1$, since for $|C|>1$ composing with a fixed transposition pairs opposite signs. Exactly the bijections $f$ survive, each with coefficient one. ▫

The individual map counts in (5) are easy to evaluate by (3), but there are superexponentially many partitions $\pi$. We therefore construct $\pi$ and $\varphi$ together and share work whenever partial constructions have the same possible continuations. The following model captures such computations.

With $D[\mathrm{s}]=1$, all node values can be evaluated by dynamic programming in topological order. Joining disjoint ABPs to a new common source and sink by unit transitions gives an ABP computing the sum of their outputs.

Basic Dynamic Programming

Following the introduction, we first realize the Binet–Minc sum (5) by an ABP whose paths construct star forests $M/\pi$ together with their left-pinned maps $\varphi$. The ABP nodes are indexed by $(S;k,j)$, where $S\subseteq[n]$ tracks the covered left vertices, including the leaves of the currently open star. If $(k,j)=(0,0)$, then no star is open. Otherwise, $k\in\{1,\ldots,n\}$ is the current number of leaves in the open star, and $j\in[n]$ specifies its center image $v_j$. Accordingly, the source and sink are $\mathrm{s}=(\varnothing;0,0)$ and $\mathrm{t}=([n];0,0)$. The construction rules sketched in the introduction manifest themselves in the ABP as three types of labeled transitions, see also Figure 2:

Note that Begin requires a closed state with $S\ne[n]$, while Grow and Close require an open star. The ABP has at most $O^*(2^n)$ nodes, each with $O(n)$ outgoing transitions: a closed node has at most $n$ Begin transitions, and an open node has at most $n$ Grow transitions and one Close transition.

To obtain a topological order, sort the nodes by increasing $|S|$, with open states before closed states at each level. Then Close advances within a level, and every other transition increases $|S|$.

Proof. Every source-to-sink path determines a partition $\pi\in\mathcal{P}_n$ and a left-pinned map $\varphi\in\Phi(M/\pi)$: each Begin transition begins a star $B$ and chooses $\varphi(s_B)=v_j$, the subsequent Grow transitions add its remaining leaves, and Close ends the star. The stars appear in order of their smallest leaves, and each star’s smallest leaf comes first. Conversely, a pair $(\pi,\varphi)$ together with an ordering of each star’s leaves with its smallest leaf first determines a unique source-to-sink path.

Fix $(\pi,\varphi)$. For a star $B$ of size $b$ with $\varphi(s_B)=v_j$, each of its $(b-1)!$ leaf orders contributes the factor $(-1)^{b-1}\prod_{i\in B}A_{ij}$ to the path weight. Summing these factors over the leaf orders gives $\mu(B)\prod_{i\in B}A_{ij}$. The leaf orders are chosen independently for each star, so the paths realizing $(\pi,\varphi)$ have total weight $\mu(\pi)w(\varphi)$. Summing over $\varphi\in\Phi(M/\pi)$ gives $\mu(\pi)\sum_{\varphi\in\Phi(M/\pi)}w(\varphi)$, and then summing over $\pi\in\mathcal{P}_n$ gives $\operatorname{per}(A)$ by (5). ∎

Constructing the ABP

For our main construction, we build on the ABP from § 3. For a cutoff $r \ge1$, the main part described in § 4.2 grows stars with at most $r$ leaves and records deferred leaves in a stellar nursery. In § 4.3, we describe star-formation gadgets that form the large stars from the stellar nursery post-hoc to obtain the combined ABP.

The final construction relies on a specific parameter choice that is supplied in § 5, which also bounds the effective size of the combined ABP. This section keeps these parameters unspecified for now and focuses on the ABP construction and correctness.

Only Small Stars

As a warm-up, consider a restricted Binet–Minc sum over pairs $(\pi,\varphi)$ such that all blocks in $\pi$ are of size at most $r$, i.e., all stars in $M/\pi$ have at most $r$ leaves:

Koivisto’s strategy [40] for partitioning into sets of bounded size allows us to evaluate (10) with exponential savings: Ordering stars by their smallest leaves forces a large covered prefix of left vertices, which significantly restricts the state space.

More concretely, we construct a modified ABP for (10) by keeping Grow transitions from the basic ABP only when $k < r$. The source-to-sink paths in this modified ABP construct exactly the pairs $(\pi,\varphi)$ with $|B| \le r$ for every $B \in\pi$, and as in the proof of Lemma 3.1, the paths realizing each such pair still have total weight $\mu(\pi)w(\varphi)$. To bound the effective size of this ABP, consider a path from the source to a node $(S;k,j)$. For $S \subseteq[N]$, define the prefix length

Now say that the path to $(S;k,j)$ uses exactly $b \in\mathbb{N}$ transitions of type Begin. Each such Begin transition covers the smallest uncovered left vertex, so $\operatorname{pref}(S) \ge b$. Moreover, each star has at most $r$ leaves, so $|S| \le rb$. Combining this, we find that only nodes with $|S| \le r\operatorname{pref}(S)$ are reachable from the source in the modified ABP. Thus the modified ABP has effective size $O^*(c_r^n)$ for some $c_r < 2$, later quantified in Lemma 5.2.

Stellar Nurseries

Next, we fix a cutoff $r$ as above and a rational fraction $0\leq\alpha_r\leq1$, and allow for up to $\alpha_r n$ larger stars. For a partition $\pi$, write $q_s(\pi)$ for the number of blocks $B\in\pi$ with $|B|>s$. We first construct the main part for the restricted Binet–Minc sum

In § 4.3, we will further restrict this sum by assigning each partition to one cutoff.

The main part of the ABP keeps the transitions from § 4.1, with Grow still restricted to $k<r$. For a leaf $i$ destined for a large star $B$, we choose its center image $\varphi(s_B)=v_j$ but defer its block membership to be handled by a star-formation gadget introduced in the next subsection.

To enable this strategy, we extend the indexing of the ABP nodes to $(S,\mathbf{d};k,j)$, where $\mathbf{d}=(d_1,\ldots,d_n)\in\mathbb{N}^n$ is the stellar nursery. Here $d_j$ counts deferred leaves with chosen center image $v_j$; the star-formation gadget will use this information to count large stars. For $S\neq[n]$, we maintain stellar nursery information through the following transitions, where $e_j$ is the $j$th unit vector:

Defer: $(S,\mathbf{d};0,0)\xrightarrow{A_{ij}}(S\cup\{i\},\mathbf{d}+e_j;0,0)$ with $i=\min([n]\setminus S)$ and $j\in[n]$, (13)

Note that, for normalization purposes, we may only Defer if no small star is actively being constructed. We can safely keep only nodes with $|\operatorname{supp}(\mathbf{d})|\leq\alpha_r n$.

The source is $(\varnothing,0;0,0)$ and § 4.3 will attach a star-formation gadget at each node $([n],\mathbf{d};0,0)$ of the main part, leading to the common sink $t_r$. Figure 3 summarizes the construction.

Forming Stars in Stellar Nurseries

Fix a finite set $\mathcal{R}=\{r_1<\cdots<r_\ell\}$ of cutoffs and rational fractions $0\le\alpha_s\le1$ for $s\in\mathcal{R}$, all independent of $n$. Their values will later be chosen in § 5.

We now clear the stellar nursery by forming large stars in it, essentially re-using the DP from § 3. Consider a path to a closed terminal node $\tau_{\mathbf d}=([n],\mathbf d;0,0)$ of the main part at cutoff $r$, and let $U_j$ be its set of deferred leaves with chosen center image $v_j$, so $|U_j|=d_j$. We call $U_j$ a cluster. By Fact 4.2, it suffices to enforce $r(\rho)=r$ for the partition $\rho$ formed by these large stars.

Now attach a gadget from Lemma 4.4 at each closed terminal $\tau_{\mathrm d}$, with common sink $\mathrm t_r$. Denote the resulting ABP by $B_r$ and its source by $s_r=(\varnothing,0;0,0)$. The attached gadgets multiply each main-part path weight by $C_r(\mathbf d)$, giving the output

Indeed, expanding $C_r(\mathbf d)$ pairs the small blocks $\sigma$ from the main part with large blocks $\rho$; Fact 4.2 ensures that $\pi=\sigma\cup\rho$ is assigned to $r$. Conversely, each assigned pair $(\pi,\varphi)$ determines a unique main-part path for each choice of small-star leaf orders with the smallest leaf first. These paths are retained because their nursery support is at most $q_r(\pi)\leq\alpha_r n$. Summing the leaf orders gives $\mu(\sigma)w(\varphi)$ as in Lemma 3.1, including all factors $A_{ij}$; the term $\rho$ in $C_r(\mathbf d)$ supplies $\mu(\rho)$. Their product is $\mu(\pi)w(\varphi)$.

Proof. By (17), each partition contributes exactly once to the output $\sum_{r\in\mathcal{R}}F_r(A)$, which equals $\operatorname{per}(A)$ by Theorem 2.1.

The Economics of Stellar Nurseries

We now choose the cutoffs and large-star budgets. The budgets must be small enough that each cutoff ABP retains an exponential saving, yet generous enough that every partition has an admissible cutoff. The following parameter lemma shows that both requirements can be met by a fixed finite choice, independent of $n$. Throughout, denote binary entropy by

We will write $\alpha_j$, $c_j$, and $E_j$ for the parameters at cutoff $r_j$.

We first quantify the saving provided by a covered prefix, as in § 4.1 and [40 Lemma 3]: As the cutoff $r$ grows, larger stars can cover more leaves without beginning another star, so this restriction becomes weaker. Nevertheless, in our setup, it still subtracts $\Theta(n/r)$ from the exponent. Eventually, we will show that the bookkeeping overhead for stellar nurseries fits into this saving.

Proof. Fix $p\in\{0,\ldots,N\}$. If $\operatorname{pref}(S)=p$ and $|S|\leq rp$, then $S=[p]\cup T$ with $T\subseteq\{p+1,\ldots,N\}$ and $|T|\leq(r-1)p$. Since $0<c-1<1$, each such $T$ has weight $(c-1)^{|T|-(r-1)p}\geq1$. Their number is therefore at most the sum of these weights over all subsets $T$, which the binomial theorem evaluates as

Summing over the $N+1$ possible values of $p$ proves the claim.

Recall that the nursery entry $d_j$ counts deferred leaves with chosen center image $v_j$. Every deferred leaf increases one such count and extends the covered prefix. The resulting reduction in possible covered sets can compensate for the number of ways to choose these counts. We therefore count stellar nurseries together with their compatible covered sets: even many deferred leaves can be affordable when they are assigned to few center images.

Proof. First fix $\mathbf{d}$ with $m=\sum_j d_j\le n$. A path from the source to $(S,\mathbf{d};k,j)$ uses exactly $m$ Defer transitions; let $b$ be its number of Begin transitions. Each of these $m+b$ transitions covers the smallest uncovered label, and each begun star has at most $r$ leaves. Thus

It follows that $[m]\subseteq S$, and the injective map $S\mapsto T=\{i-m:i\in S\setminus[m]\}\subseteq[n-m]$ gives $|T|=|S|-m\le r(\operatorname{pref}(S)-m)=r\operatorname{pref}(T)$. Then Lemma 5.2, with $N=n-m$ and $c=c_r$, bounds the number of such sets $T$, and hence of sets $S$, by $(n-m+1)c_r^{n-m}\le(n+1)c_r^{n-m}$.

Next sum over $\mathbf{d}$. A positive coordinate contributes $\sum_{a\ge1}c_r^{-a}=1/(c_r-1)$, so choosing its support gives

Extending the sum beyond $m\le n$ only increases the bound. Multiplying by $(n+1)c_r^n$ therefore bounds the choices of $(S,\mathbf{d})$. There are at most $1+n\min(r,n)$ choices of $(k,j)$ and $O(n)$ outgoing transitions per node in the main part. By Lemma 4.4, each attached star-formation gadget has size $O((n+1)^{|\mathcal{R}|+4})$. Since $\mathcal{R}$ is fixed, attaching one per reachable closed terminal preserves (20). □

The binomial entropy bound gives

Indeed, $\binom{n}{p}\le2^{nH(p/n)}$, and $H(u)-u\log_2(c_r-1)$ is increasing on $[0,1/c_r]$. For $r=r_j$ and $\alpha_j\le1/c_j$, (20) therefore gives effective size $O^*(2^{E_jn})$, with $E_j$ as defined in Lemma 5.1. This identifies the main remaining expense, namely, choosing the occupied center images. For small $\alpha_r$, this costs roughly $n\alpha_r\log(1/\alpha_r)$ in the exponent. Comparing this with the saving of order $n/r$ suggests budgets of order $1/(r\log(r+1))$, with a sufficiently small constant.

Finally, the coverage of partitions relies on the distribution of stars across cutoffs. A star of size $b$ contributes weight $r_j$ at each cutoff $r_j<b$. By choosing geometrically increasing cutoffs, we can bound the sum of these weights by $O(b)$. For geometrically increasing cutoffs, taking $\alpha_j$ of order $1/(r_j\log(r_j+1))$ gives weighted thresholds $r_j\alpha_jn$ of order $n/j$, since $\log(r_j+1)=\Theta(j)$. Their harmonic sum eventually exceeds the $O(n)$ bound on the total contribution of all stars, forcing some cutoff test to succeed. The final parameter lemma formalizes this.

Proof of Lemma 5.1. Take $r_j=2^{j-1}$, $c_j=2-\frac{1}{2r_j}$, and $\alpha_j=\frac{1}{64r_jj}$. Bernoulli’s inequality shows that $c_j(c_j-1)^{r_j-1}\ge1+\frac{3r_j-1}{4r_j^2}>1$, and $\alpha_j<1/2<1/c_j$. For $r=r_j$, use $H(x)\le x\log_2(e/x)$, $-\log_2(c_j-1)\le1$, $\log_2r=j-1$, and $\log_2j\le j$ to obtain

By harmonic divergence, choose a fixed finite $\ell$ with $\sum_{j=1}^{\ell}1/j\ge128$. For every partition $\pi\in\mathcal{P}_n$,

since the sum of the dyadic cutoffs below $|B|$ is less than $2|B|$. If no cutoff were admissible for $\pi$, then $q_{r_j}(\pi)>\alpha_jn$ for every $j$, and hence we contradict (24) by $\sum_{j=1}^{\ell}r_jq_{r_j}(\pi)>\frac{n}{64}\sum_{j=1}^{\ell}\frac{1}{j}\ge2n$. □

Finishing the Proof

We have collected all ingredients to prove the main theorem.

Proof of Theorem 1.1. Choose $\mathcal{R}$ and the parameters from Lemma 5.1. By Corollary 4.5, the combined ABP $\mathcal{B}$ computes $\operatorname{per}(A)$. Let $\gamma=\max_{j\in[\ell]}E_j<1$. Summing the bounds for $B_{r_j}$ from Proposition 5.3 and (23) over the fixed finite set $\mathcal{R}$ gives effective size $O^*(2^{\gamma n})$ for $\mathcal{B}$. Exploring allowed transitions via BFS constructs its reachable part on input $n\in\mathbb{N}$ and the fixed parameters, with polynomial work per node. Splitting each $-A_{ij}$ transition into labels $-1$ and $A_{ij}$ gives elementary labels with constant overhead. Finally, evaluation via DP in topological order uses linearly many ring operations in the size of this ABP, so construction and evaluation take $O^*(2^{\gamma n})$ time and ring operations, respectively.

Setting $\varepsilon=2-2^\gamma>0$ gives a fixed exponential saving. Using the parameters of Appendix § 7 in this construction gives $2^\gamma<2-10^{-40}$ and hence the stated value for $\varepsilon$. □

Finally, by clearing denominators and working over $\mathbb{Z}/2^t\mathbb{Z}$ with $t\in\mathbb{N}$ sufficiently large to recover the permanent exactly, we obtain the following bit complexity version of Theorem 1.1.

Corollary 6.1. For $\varepsilon$ as above, there is an algorithm for computing permanents of $n\times n$ rational matrices with $B$-bit numbers in $\operatorname{poly}(B)\cdot O^*((2-\varepsilon)^n)$ bit operations.

Explicit Choice of Constants

This appendix gives explicit rational parameters for 280 cutoffs that yield $\varepsilon= 10^{-40}$ in the main construction. For $\mathcal{R} = \{1 = r_1 < \cdots< r_\ell\}$ and fractions $\alpha_j$, set $\beta_1 = 2$ and $\beta_j = r_j - r_{j-1}$ for $j \ge2$. Every partition satisfies

For a singleton the inner sum is zero. Otherwise, if $r_i$ is the largest selected cutoff below $|B|$, it telescopes to $r_i+1 \le|B|$. Consequently every partition has an admissible cutoff as soon as

Indeed, if no cutoff were admissible for $\pi$, then $q_{r_j}(\pi) > \alpha_j n$ for every $j$, contradicting (25).

Bounds for the Parameters

For rational $1 \le y \le2$, put $z=(y-1)/(y+1)$ and

The expansion $\ln y = 2\sum_{h\ge0} z^{2h+1}/(2h+1)$ gives

For any positive rational $x$, write $x=2^k y$ with $1 \le y < 2$. Adding the intervals for $\ln y$ and $k\ln2$ (reversing the latter endpoints when $k<0$) gives rational bounds $\lambda_-(x) \le\ln x \le\lambda_+(x)$.

For every triple $(r_j,\alpha_j,c_j)$ in (28)–(29), the following rational inequalities hold:

where

The logarithmic inequality proves the subset-counting condition. The positive numerator and $\lambda_-(2)>0$ give $E_j\le U_j$, proving the required effective-size bounds for the cutoff ABPs by § 5. The weighted mass is the rational number

Direct rational summation gives

Thus (25) guarantees that every partition meets at least one cutoff test, for every $n$. Finally, $r_{j+1}+3\le\frac{4}{3}(r_j+3)$ implies $K=r_{280}\le4(4/3)^{279}-3<10^{36}$. Convexity gives $2^{1-10^{-38}}\le2-10^{-38}<2-10^{-40}$, proving the claimed choice of $\varepsilon$.

Definitions for the Lean Statement

We expand the definitions used by main_abp on page 4.

variable {n : ℕ} (A : Fin n → Fin n → ℤ)

theorem main_abp :
  ∃ (C : ℝ) (d : ℕ), 0 < C ∧ ∀ n : ℕ, ∃ G : ABP n,
    (∀ A : Fin n → Fin n → ℤ, G.output A = permanent A) ∧
    (G.vertices + G.transitions : ℝ) ≤ C * (n+1 : ℝ)^d * (2 : ℝ)^((0.999994 : ℝ)*n)

noncomputable def ABP.output (G : ABP n) :=
  G.paths A G.vertices G.sink

noncomputable def permanent : ℤ :=
  ∑ p : Equiv.Perm (Fin n),
  ∏ i, A i (p i)

noncomputable def ABP.paths (G : ABP n) :
  ℕ → Fin G.vertices → ℤ
  | 0, v => if v = G.source then 1 else 0
  | k+1, v =>
    (if v = G.source then 1 else 0) +
      ∑ e : Fin G.transitions,
        if G.head e = v then
          (G.label e).eval A * G.paths k (G.tail e)
        else 0

structure ABP (n : ℕ) where
  (vertices transitions : ℕ)
  (source sink : Fin vertices)
  (tail head :
    Fin transitions → Fin vertices)
  label : Fin transitions → Label n
  rank : Fin vertices → Fin vertices
  increasing : ∀ e,
    rank (tail e) < rank (head e)

def Label.eval : Label n → ℤ
  | .variable i j => A i j
  | .constant c => c

inductive Label (n : ℕ)
  | variable (i j : Fin n)
  | constant (c : ℤ)