Proof. We construct a verifier \(\mathsf{NL}\) machine for \(F\) based on the verifier \(\mathsf{NL}\) machine for \(f\). The witness is a concatenation of the witnesses for \(f(g(x,1)), f(g(x,2)), \ldots, f(g(x,p(x)))\), which we call \(w^1, w^2, \ldots, w^{p(x)}\).

Begin by composing with an \(\mathsf{FL}\) machine as in 1 to compute \(p(x)\) and store its output in a counter \(\mathtt{I}\). We can store this in binary, since \(\log(\mathrm{poly}(|x|)) = O(\log(|x|))\).

Initialise a counter \(\mathtt{i}=1\). While \(\mathtt{i} \leqslant\mathtt{I}\), compose with an \(\mathsf{FL}\) machine to compute \(g(x,\mathtt{i})\), then check the validity of \(w^{\mathtt{i}}\), and finally increase \(\mathtt{i}\) by \(1\). ◻

Proof. Let \({\det}_d\) be the polynomial \[{\det}_d \begin{pmatrix} y_{1,1} & \cdots & y_{1,d} \\ \vdots & \ddots & \vdots \\ y_{d,1} & \cdots & y_{d,d} \end{pmatrix} = \sum_{\pi\in S_d} \sgn(\pi) \prod_{i=1}^d y_{i,\pi(i)}.\] Define \(y_\bot := 0\). We crucially use the non-trivial fact (one can deduce this from the references in [32], see also the recent [33]) which is explicitly elaborated in [37] that there exist polynomials \({\det}_{d,+}(\mathbf{y})\) and \({\det}_{d,-}(\mathbf{y})\) with \({\det}_{d}={\det}_{d,+}-{\det}_{d,-}\) and functions \[t_+:\N\times\N\times\N\times\N \to (\N\times\N)\cup\{\bot\}, \qquad t_-:\N\times\N\times\N\times\N \to (\N\times\N)\cup\{\bot\}\] in \(\mathsf{FL}\) such that \[{\det}_{n,+}\begin{pmatrix} y_{1,1} & \cdots & y_{1,d} \\ \vdots & \ddots & \vdots \\ y_{d,1} & \cdots & y_{d,d} \end{pmatrix} = \sum_{\substack{1\leqslant q_0 \leqslant 2d\\1\leqslant q_1,\ldots,q_{d-1}\leqslant 2d^2}} \, \prod_{i=1}^d y_{t_+(d,i,q_{i-1},q_{i})}\] and \[{\det}_{d,-}\begin{pmatrix} y_{1,1} & \cdots & y_{1,d} \\ \vdots & \ddots & \vdots \\ y_{d,1} & \cdots & y_{d,d} \end{pmatrix} = \sum_{\substack{1\leqslant q_0 \leqslant 2d\\1\leqslant q_1,\ldots,q_{d-1}\leqslant 2d^2}} \, \prod_{i=1}^d y_{t_-(d,i,q_{i-1},q_{i})}.\] We discuss the witnesses for \({\det}_{d,+}\), where the witnesses for \({\det}_{d,-}\) are analogous. Let \(n:=|x|\). Let \(d:=p(x) \in \mathrm{poly}(n)\) and \(q_d:=1\). A witness is given by a list \((q_0,q_1,w^1,q_2,w^2,\ldots,q_d,w^d)\), where \(w^i\) is a witness for \(f(g(x,t_+(d,i,q_{i-1},q_i)))\). When traversing the witness, we have two counters in which we always store \(q_{i-1}\) and \(q_i\), which can be done in space \(O(\log(n))\), because \(q_i\leqslant 2d^2\in\mathrm{poly}(n)\). The witness \(w^i\) is then verified via composition as in 1 . ◻

Proof. If \(\#\mathsf{L}\subseteq \mathsf{FP}_{\geqslant 0} \subseteq \#\mathsf{P}= \#\mathsf{L}\) then \(\mathsf{FP}_{\geqslant 0}=\#\mathsf{P}\). The class \(\mathsf{P}\) can be identified with the subclass of \(\mathsf{FP}_{\geqslant 0}\) of functions with a 1-bit output. Given a function \(f\) in \(\#\mathsf{P}\), the decision problem \(f>^?0\) is at most as hard as computing \(f\) itself, hence we may write \(\mathsf{NP}\subseteq\#\mathsf{P}=\mathsf{FP}_{\geqslant 0}\). So \(\mathsf{NP}\) is a subset of \(\mathsf{FP}_{\geqslant 0}\) composed of functions with a \(1\)-bit output, that is \(\mathsf{NP}\subseteq \mathsf{P}\). ◻

Proof. Let \(\ast^a\) denote a sequence of \(a\) many arbitrary symbols. Consider the following counting function #padded3Sat. \[\mathrm{\small \#padded3Sat}(\varphi,\ast^{2^{\sqrt{n}}-|\varphi|-1}) = \mathrm{\small \#3Sat}(\varphi),\] where \(\varphi\) denotes the binary encoding of a Boolean formula on \(n\) variables and \(n\) clauses. The input length is \(N := 2^{\sqrt{n}}\), and a witness is a string of \(n=(\log(N))^2\) many bits that represents a truth assignment. Checking a witness can be done by copying it to the work tape and then going over all clauses in \(\varphi\). This can be done in polynomial time. Hence, \(\mathrm{\small \#padded3Sat}\in\#\mathsf{TISP}(\mathrm{poly}(n),\log^2(n))\). By assumption we have \(\#\mathsf{TISP}(\mathrm{poly}(n),\log^2(n))\subseteq\mathsf{FP}\), so there exists \(c\) such that \(\mathrm{\small \#padded3Sat}\) can be solved in time \(N^c = 2^{c\sqrt{n}}\). Hence, also \(\mathrm{\small \#3Sat}\) can be solved in time \(2^{c\sqrt{n}}\), using the same algorithm. ◻

Proof. An \(\mathsf{NL}\) machine with \(c\log(n)\) space in the work tape can have at most \(2^{c\log(n)} = n^c\) many configurations. Since the machine is not allowed to loop endlessly, the whole configuration graph must have no directed cycles. Since the non-deterministic guesses of non-deterministic Turing machines are in binary, a configuration can only lead to one of two possible configurations.

We claim that the graph with the most possible source-sink paths on \(N\) vertices and with the above contraints is the following: \[\bullet \rightrightarrows \bullet \rightrightarrows \bullet \cdots \bullet \rightrightarrows \bullet\] Indeed, suppose by induction that it is true for graphs on \(N-1\) vertices. Note that it has \(2^{N-1}\) source-sink paths. Consider a graph on \(N\) vertices now. Let \(s\) be the source and \(a, b\) be its children; let \(t\) be the sink. By induction hypothesis, the number of \(a\)-\(t\) paths is at most \(2^{N-1}\), and the number of \(b\)-\(t\) too by a similar argument. Since there are no cycles, there are at most \(2^N\) many \(s\)-\(t\) paths. The above graph realizes this maximum.

Since \(\#\mathsf{L}\) is the class of functions that count paths in the configuration graph, this count is bounded above by \(2^{n^c}\). ◻

Proof. The upper bound is given by the previous theorem. The existence is given by the following construction. Consider the machine that takes as input \(n\), computes and stores \(n^c\) in a counter \(\mathtt{a}\) (occupying \(c\log(n)\) bits). Then outputs a single \(1\), and while \(\mathtt{a} > 0\) it outputs a \(0\) then decreases \(\mathtt{a}\) by \(1\). ◻

Proof. The elementary school algorithm suffices, with a minor modification for the multiplication: Instead of adding up all shifted products of a factor with the digits of the other factor, an additions is performed after every product of a digit with a factor. ◻

Proof. The binomial coefficient \(\binom{n}{k}\) counts the number of \(k\)-subsets of \([n]\). Encode a \(k\)-subset \(S\) of \([n]\) as a word \(w_1w_2\ldots w_n\) where \(w_i = 1\) if \(i\in S\) and \(0\) otherwise. We construct a verifier \(\mathsf{NL}\) machine with \(2\) binary-encoded counters that takes as input \((1^n \, 0 \, 1^k)\) and a read-once left-to-right witness \(w\) as a \(\{0,1\}\)-string, and accepts if and only if \(w\) is encoding a \(k\)-subset of \(n\).

The first counter \(\mathtt{a}\) is allocated \(\log(n)\) space, and the second counter \(\mathtt{b}\) is allocated \(\log(k)\) space. Note that both are in \(O(\log(n+k+1))\)-space.

We begin by reading \(1^n\) and \(1^k\) and storing their values in the two counters \(\mathtt{a}\) and \(\mathtt{b}\). We then read \(w\) once left-to-right. For each \(w_i\), the first counter always decreases by one, and the second counter decreases by one only if \(w_i = 1\). After reading the whole witness \(w\), the machine accepts if and only if both counters are at \(0\). ◻

Proof. We use the formula \(\binom{n}{a_1,\ldots,a_k}= \binom{n}{a_1} \binom{n-a_1}{a_2} \cdots = \binom{m_1}{a_1}\binom{m_2}{a_2}\cdots\) to reduce the problem to the setting of Theorem [thm:product].

The function \(f : (1^n\,0\,1^k) \mapsto \binom{n}{k}\) is in \(\#\mathsf{L}\) by Theorem [thm:binomial]. Next, we claim the function \[g : (x \,0\,0\, i) \mapsto (1^{n-a_1-\cdots-a_{i-1}}\,0\,1^{a_i})\] is in \(\mathsf{FL}\), where \(x=(1^n\, 0\, 1^{a_1}\, 0\,\dots\, 0\, 1^{a_k})\), \(k\leqslant n\), and \(1\leqslant i\leqslant k\) is encoded in binary. Initialise binary-encoded counters \(\mathtt{A} = 2n\) and \(\mathtt{b} = i\). Read the input \(x\) from the left until we read a \(0\), then decrease \(\mathtt{b}\) by \(1\) and keep reading. When \(\mathtt{b} = 0\) stop; we have found the \(i\)th \(0\) in \(x\). Now start reading from the current position and to the left; every time we find a \(1\) decrease \(\mathtt{A}\) by \(1\). When you reach the beginning of the input tape we have \(\mathtt{A}=n-a_1-\cdots-a_{i-1}\). Write a \(1\) in the output tape, decrease \(\mathtt{A}\) by \(1\), repeat until \(\mathtt{A}=0\). Then write a \(0\) in the output. Use the same technique to find the \(i\)th \(0\) of \(x\) again, and read to the right to set \(\mathtt{A} \leftarrow a_i\). Output \(\mathtt{A}\) in unary again to finish.

By similar considerations, the function \(p : x\mapsto k\) (the number of \(0\)s in \(x\), written in binary) is in \(\mathsf{FL}\) and its output is \(O(\log(|x|))\) in size. Hence we are in the hypotheses of Theorem [thm:product]. ◻

Proof. Catalan numbers count the number of Dyck paths of length \(2n\). We construct an algorithm of the type of Algorithm 7. Encode a Dyck path as a binary string by interpreting \(1\) as an up-step and \(0\) as a down-step. Initialise two binary-encoded counters: \(\mathtt{a}=2n\) will check the length of the string and \(\mathtt{b}=0\) will check that the Dyck path stays at non-negative height. For each bit \(w_i\) in the witness: if \(w_i=1\) then decrease \(\mathtt{a}\) by one, increase \(\mathtt{b}\) by one; if \(w_i=0\) then decrease both counters by one. Then check that both counters are at least \(0\).

At the end, check that \(\mathtt{a}=0=\mathtt{b}\). ◻

Proof. The Narayana number \(N(n,k)\) counts the number of Dyck paths of length \(2n\) with exactly \(k\) peaks. We take the algorithm from Theorem [thm:catalan] and make a small modifications to it. We add one more binary-encoded counter \(\mathtt{c}\) initialised at \(k\), which will count the number of peaks. We also add a \(1\)-bit counter \(\mathtt{d}\) to detect these peaks.

In the main loop, if \(w_i=1\) then set \(\mathtt{d}=1\); if \(w_i=0\) and \(\mathtt{d}=0\) then do nothing; if \(w_i=0\) and \(\mathtt{d}=1\) then set \(\mathtt{d}=0\) and decrease \(\mathtt{c}\) by one.

At the end, check also that \(\mathtt{c}=0=\mathtt{d}\). ◻

Proof. The Fibonacci number \(F_n\), with \(F_1=1,F_2=2\), counts domino sequences of \(n\): the number of \(\{1,2\}\)-strings which sum to \(n\). If each \(1\) and \(2\) is written in binary, then a domino sequence is a \(\{0,1\}\)-string of length \(n\) such that each \(0\) is preceded by a \(1\); this will be our witness. We construct an algorithm of the form of Algorithm 4.

Initialise a binary-encoded counter \(\mathtt{a}=n\) and a \(1\)-bit counter \(\mathtt{b}=0\) which we use to remember the last bit encountered. For each \(w_i\), decrease \(\mathtt{a}\) by one. If \(w_i=1\) then set \(\mathtt{b}=1\). If \(w_i=0\) then check \(\mathtt{b}=1\) (otherwise reject) and set \(\mathtt{b}=0\).

At the end, accept if \(\mathtt{a}=0\), otherwise reject. ◻

Proof. Consider the directed multigraph whose vertices are the non-negative integers and with

• \(D(k,i)\) arcs from \(k\) to \(k-i\) for each \(k>C\) and \(1\leqslant i\leqslant C\),

• \(A(k)\) arcs from \(k\) to \(0\) for each \(1\leqslant k \leqslant C\).

Then \(\sum_{i=1}^C D(n,i) A({n-i}) = A(n)\) counts the number of paths from \(n\) to \(0\). For instance, the following is the graph associated to the Fibonacci numbers \(\{F_n\}_{n\geqslant 1}\), where the base cases are \(n=1\) and \(n=2\) for consistency: \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/zepqjfiw.png}\label{tbzqeuiy}\end{figure}\tag{5}\]

A path \((p_0 = n, p_1, p_2, \ldots, p_\ell, 0)\) from \(n\) to \(0\) can be encoded with a tuple of numbers \[i_1, d_1, i_2, d_2, \ldots, i_\ell, d_\ell, a\] such that the \(1\leqslant i_j \leqslant C\) encode the jump sizes from a given node \(p_{j-1}\) of the path to the next node \(p_j = p_{j-1}-i_j\), the \(1 \leqslant d_j \leqslant D(p_{j-1},i_j)\) choose which of the arcs to use for this one step, and \(1\leqslant a\leqslant A(p_{\ell})\) chooses which of the arcs to take from \(p_{\ell}\) to \(0\). In the case of Fibonacci numbers we have \(d_j=1\) always, and the tuple of the \(i_j\in\{1,2\}\) is a domino sequence.

A sequence encodes a valid path if and only if \[\begin{cases} 1\leqslant i_j \leqslant C & \text{for all~}1\leqslant j\leqslant\ell,\\ 1\leqslant d_j \leqslant D(p_{j-1},i_j) & \text{for all~}1\leqslant j\leqslant\ell,\\ 1\leqslant a\leqslant A(p_{\ell}),\\ 1 \leqslant p_\ell \leqslant C < p_{\ell-1}. \end{cases}\] Note that these properties can be checked sequentially: first check the inequalities for \(j=1\), then for \(j=2\), etc. Two counters can be used to keep track of \(p_{j-1}\) and \(p_j = p_{j-1} - i_j\) at any given time. The parameters \(C\) and \(A(1),\ldots,A(C)\) are constants; the parameters \(D(k,i)\) are \(\mathrm{poly}(k)\) size (and so in particular \(\mathrm{poly}(n)\) size) and computable in \(O(\log(k+i)) = O(\log(n))\) space. Therefore all of these properties can be checked in log-space using an algorithm like the one in Algorithm 4. ◻

First proof of Corollary [cor:factorial]. We have \(n! = n\cdot(n-1)!\) and thus it follows from the previous theorem. ◻

Second proof of Corollary [cor:factorial]. The factorial is in the hypotheses of Theorem [thm:product], where \(f = p : (1^n) \mapsto n\) is in \(\mathsf{FL}_{\geqslant 0}\) and poly-size, and \(g : (1^n\,0\,1^i) \mapsto i\) in \(\mathsf{FL}\). ◻

Proof. The witness is a sequence \((n_0,k_0,d_0),(n_1,k_1,d_1),\ldots,(n_m,k_m,d_m)\), where the numbers \(n_i,k_i,d_i\) are encoded in binary. They are subject to \[\begin{cases} (n_0,k_0) = (n,k)\\ \exists \ell=\ell(s) : (n_s,k_s) = (n_{s-1}-i_\ell, k_{s-1}-j_\ell) &\text{for all}~1\leqslant s < m,\\ 1\leqslant d_{s-1} \leqslant D(n_{s-1},k_{s-1},i_{\ell(s)},j_{\ell(s)})&\text{for all}~1\leqslant s < m,\\ (n_m,k_m)\in B,\\ 1\leqslant d_m \leqslant A(n_m,k_m). \end{cases}\]

We keep 4 main counters \(\mathtt{a},\mathtt{b},\mathtt{c},\mathtt{d}\). Initialise \((\mathtt{a},\mathtt{b}) \leftarrow (n_0, k_0)\) and check that they are equal to \(n\) and \(k\) respectively. In the \(s\)th step, the counters \((\mathtt{a},\mathtt{b})\) store \((n_{s-1}, k_{s-1})\) and we read \((\mathtt{c},\mathtt{d}) \leftarrow (n_s, k_s)\). Check the local validity of the witness: for \(\ell=1,\ldots,C\) check if \((\mathtt{c},\mathtt{d}) = (\mathtt{a} - i_\ell, \mathtt{b} - j_\ell)\). If all checks fail, then reject the witness. If on the contrary a pair \((i_\ell,j_\ell)\) is found, compute and store \(\mathtt{D}\leftarrow D(n,k,i_\ell,j_\ell)\) and check that \(1\leqslant d_{s-1}\leqslant\mathtt{D}\). If \((\mathtt{c},\mathtt{d})\in B\) is a base case, then check \(1\leqslant d_s \leqslant A(\mathtt{c},\mathtt{d})\) and that this is the last entry of the witness. Otherwise reassign \((\mathtt{a}, \mathtt{b}) \leftarrow (\mathtt{c}, \mathtt{d})\) and repeat. ◻

Proof. They are subject to the \(2\)-dimensional recursions \[c(n+1,k) = n\, c(n,k) + c(n,k-1) \quad\text{and}\quad S(n+1,k) = k\, S(n,k) + S(n,k-1),\] and thus the result follows from Theorem [thm:2-dim]. ◻

Proof. Initialize a counter \(\mathtt{j}=0\) and \(C\) many counters \(\mathtt{b}_i = a_i\) for \(i=1,\ldots,C\) encoded in binary in \(O(\log(n+|\mathbf{a}|))\) space. The witness is the sequence \(w_1,\ldots,w_n\) encoded with the \(C\) symbols: \(1,2,\ldots,C\). We read the witness symbol by symbol. At each new symbol \(w_j\) increase \(\mathtt{j}\) by one (so that \(\mathtt{j} = j\)). Set \(i:=w_{\mathtt{j}}\) and increase \(\mathtt{b}_i\) by one, then, if \(i>1\), check if \(\mathtt{b}_i\leqslant\mathtt{b}_{i-1}\). If that check fails then the witness is not a ballot sequence. When the witness has been fully read, check \(\mathtt{j}=n\). ◻

Proof. Standard Young tableaux of a given shape are in correspondence to ballot sequences as follows. An SYT \(T\) gives the ballot sequence \(w(T)\) where \(w(T)_i\) is equal to the row number of the row where the box with entry \(i\) in \(T\) is. Apply the algorithm from Theorem [thm:ballots] with \(a_i=0\) and adding a check that \(\mathtt{b}_i=\lambda_i\) in the end.

If the width of \(\lambda\) is bounded instead, then change the role of rows for columns in the previous correspondence. Compose the \(\mathsf{FL}\) function from Lemma [lem:transposition] and the verifier \(\mathsf{NL}\) machine of Theorem [thm:ballots] as in 1 . ◻

Proof. Suppose \(\ell(\lambda)\leqslant C\). The output of the function can be rewritten as \[\Big(\underbrace{ \underline{1^C\,0}~ \underline{1^C\,0}~ \dots \underline{1^C\,0} }_{\lambda_C~\text{times}} \, \dots \, \underbrace{ \underline{1^2\,0}~ \underline{1^2\,0}~ \dots \underline{1^2\,0} }_{\lambda_2-\lambda_3~\text{times}} \, \underbrace{ \underline{1\,0}~ \underline{1\,0}~ \dots \underline{1\,0} }_{\lambda_1-\lambda_2~\text{times}} \Big)\,.\] Initialise \(C\) counters \(\mathtt{a}_1 = \lambda_1, \dots, \mathtt{a}_C = \lambda_C\). While \(\mathtt{a}_C > 0\), write \(1^C\,0\) in the output tape and decrease all counters by one. Once the while-loop is finished, delete the counter \(\mathtt{a}_C\). At this stage we have \(\mathtt{a}_i = \lambda_i-\lambda_C\) for all \(i\). Run a new while-loop, this time controlled by \(\mathtt{a}_{C-1} > 0\), and writing \(1^{C-1}\,0\) in each iteration. After this second while-loop, \(\mathtt{a}_i = \lambda_i-\lambda_{C-1}\) for all \(i\). Iterate this process until all counters have been deleted.

Suppose now \(\lambda_1\leqslant C\). Initialise a counter \(\mathtt{a}=1\). For each run of \(1\)s in the input, if the run is of length at least \(\mathtt{a}\) then write a \(1\) in the output tape. Then write a \(0\) in the output, increase \(\mathtt{a}\), and repeat. Once \(\mathtt{a} > \lambda_1\), stop. ◻

Proof. This function satisfies the recursion \(F(n) = F(n-1) + (n-1)F(n-2)\) and so the claim follows from Theorem [thm:recurrence]. ◻

Proof. Suppose that the length of \(\lambda\) is bounded by \(C\). It is well known that SSYTs of shape \(\lambda\) and entries \(\{1,\ldots,m\}\) correspond via standardization to SYTs of shape \(\lambda\) with at most \(m-1\) descents and set \(R \subset [n]\) of \(m\) elements, such that the descents of \(T\) are a subset of \(R\) and \(n\in R\). Here \(i\) is a descent of \(T\) if it appears in a higher row than \(i+1\) in \(T\). Thus SSYTs with entries \(\leqslant N\) are in bijection with \[\Big\{(S,R, T) \,\Big|\, \begin{array}{ll} S \subseteq [N], ~R \subseteq [n],~ |S|=|R| \geqslant\ell(\lambda), \\[-.6em] T\in\mathrm{SYT}(\lambda),~\text{ descents of T are \subseteq R} \end{array} \Big\}.\] The correspondence is as follows: Given an SSYT \(P\), let \(S=\{s_1,\ldots,s_m\}\) be the labels of the elements which appear at least once in \(P\). Then \(T\) is the standardization of \(P\): reading the smallest entries with values \(s_1\) left-to-right, replace them with \(1,2,\ldots,a_1\) in that order and put \(a_1\) in the set \(R\). Then read the elements equal to \(s_2\), left-to-right, replace them with \(a_1+1,\ldots,a_2\), add \(a_2\) to \(R\) and continue. Since entries of the same values in \(Q\) form horizontal strips, their standardized values would not form any descents in \(T\).

Here our witness is thus an indicator sequence giving the set \(S\) and a ballot sequence \(w\) corresponding to an SYT \(T\) as in Corollary [cor:syt95fixed95ell] with some symbols ‘\(r\)’ between entries in \(w_i\). Set a counter \(\mathtt{m}=|S|\). While reading the ballot sequence \(w\) we set \(\mathtt{m} \leftarrow \mathtt{m}-1\) every time \(w_{i+1}>w_{i}\) as this is equivalent to \(i\) being a descent of the corresponding \(T\) or if we have the symbol ‘\(r\)’ written between \(w_i\) and \(w_{i+1}\) with \(w_i\geqslant w_{i+1}\), which corresponds to an entry in the set \(R\) that does not come from a descent (if ‘\(r\)’ is between \(w_i> w_{i+1}\) we consider the witness invalid). In the end we should have \(\mathtt{m}=1\).

Suppose now the width of \(\lambda\) is bounded instead. Then encode the tableau \(T\) by its column ballot sequence \(w\) instead. Now there is a descent if \(w_i \geqslant w_{i+1}\). The rest of the algorithm works similarly. ◻

Proof. Let \(n\) be the number of vertices of \(T\). We have \(|\mathrm{dfs}(T)| = 2(n-1) \in O(n)\), and hence we need a verifier \(\mathsf{NL}\) machine in \(O(\log(n))\) space.

Let \(r\) be the root of \(T\), let \(\Delta(r) = (v_1,v_2,\ldots,v_{\delta(r)})\) be its children. Knuth’s formula admits the recursion \[e(T) = \binom{\mathsf{hl}_T(r)-1}{\mathsf{hl}_T(v_1),\ldots,\mathsf{hl}_T(v_{\delta(r)})} \prod_{v_i\in\Delta(r)} e(T_{v_i}),\] where \(T_v\) is the subtree rooted at \(v\) (and thus \(T_v\) has \(\mathsf{hl}_T(v)\) nodes). Use \(\mathrm{Coeff}_T(r)\) to denote the multinomial coefficient in this formula. We then have \[e(T) = \prod_{v\in T} \mathrm{Coeff}_T(v).\] Since the multinomial coefficients are in \(\#\mathsf{L}\) (Theorem [thm:multinomial]), we are almost in the hypotheses of Theorem [thm:product]; it remains to show that the hook-lengths are \(\mathsf{FL}\) computable.

Let \(v_1, v_2, \ldots, v_n\) be the nodes of \(T\), ordered by their first visit in \(\mathrm{dfs}(T)\). That is, \(v_1\) is the root, and for each \(1\) in \(\mathrm{dfs}(T)\) we find a new node. To compute \(\mathsf{hl}_T(v_i)\) initialise two counters \(\mathtt{a}=1\) and \(\mathtt{b}=1\). Scan \(\mathrm{dfs}(T)\) left-to-right starting at \(v_i\). For each \(1\) increase \(\mathtt{a}\) and \(\mathtt{b}\). For each \(0\) decrease \(\mathtt{b}\). When \(\mathtt{b}=0\) we have scanned through all of \(T_{v_i}\) and return \(\mathtt{a} = \mathsf{hl}_T(v_i)\).

Apply Theorem [thm:product] to conclude. ◻

Proof. It is shown in [42] that the difference \(\binom{n}{k}-\binom{n}{k-1}\) counts the number of \(k\)-subsets of \([n]\) whose encoding word \(w\) is a ballot sequence: for each prefix \(w_1\ldots w_i\) there are at most as many \(1\)s as \(0\)s. We apply now the algorithm from Theorem [thm:ballots] with \(a_i=0\) and an additional counter \(\mathtt{k}\) which reads the number of \(1\)s.

Alternatively, notice that \(\#\mathrm{SYT}((n-k,k)) = \binom{n}{k}-\binom{n}{k-1}\) and the result follows from Corollary [cor:syt95fixed95ell]. ◻

Proof. By the dual and the primal Jacobi–Trudi identities [23], the differences equal \[\#\mathrm{SSYT}_n((b,a)') \quad\text{and}\quad \#\mathrm{SSYT}_n((b,a)),\] respectively. The results follow therefore from Corollary [cor:ssyt95fixed95ell]. ◻

Proof. By [39], we can express the Stirling numbers as the specialisation of some elementary or complete homogeneous symmetric polynomials, \[c(n,k) = e_{n-k}(1,2,\ldots,n-1) ~~\text{and}~~ S(n,k) = h_{n-k}(1,2,\ldots,k).\] By the dual and the primal Jacobi–Trudi identities [23], the differences in the statement equal specialisations of Schur polynomials \[s_{(n-a,n-b)'}(1,2,\ldots,n-1) \quad\text{and}\quad s_{(b,a)}(1,2,\ldots,n),\] respectively. Recall that \(s_\lambda(x_1, \ldots, x_n)\) is the generating function of \(\mathrm{SSYT}_n(\lambda)\), which is in bijection with \[\Big\{(S,R, T) \,\Big|\, \begin{array}{ll} S \subseteq [N], ~R \subseteq [n],~ |S|=|R| \geqslant\ell(\lambda), \\[-.6em] T\in\mathrm{SYT}(\lambda),~\text{ descents of T are \subseteq R} \end{array} \Big\}\] as in the proof of Corollary [cor:ssyt95fixed95ell]. Hence the specialisation \(s_{(a,b)}(1,2,\ldots,n)\) counts the number of tuples \((S,R,W,C)\) such that

• \((S,R,T)\) belong to the set above,

• \(W\) is the (row) ballot sequence of \(T\),

• if the descents of \(W\) are at positions \(d_1, d_2, \ldots, d_{m-1}\) then for all \(1\leqslant j\leqslant m\) we have \(1\leqslant c_i \leqslant s_j\) for all \(d_{j-1} < i \leqslant d_j\). (Here \(i_0\) is set to \(0\).)

To encode this as a witness, we order it as \[\begin{gather} w_1, *, \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wrxkdqaz.png}\tag{10}\end{figure} , c_1, w_2, *, c_2, \ldots, w_{d_1}, *, c_{d_1},\\ w_{d_1+1}, \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wrxkdqaz.png}\tag{10}\end{figure} , *, c_{d_1+1}, \ldots, w_{d_2}, *, c_{d_2}, \\ \ldots, w_{d_{m-1}+1}, \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wrxkdqaz.png}\tag{10}\end{figure} , *, c_{d_{m-1}+1}, \ldots, w_{d_m}, *, c_{d_m} \end{gather}\] where each \(*\) is either a 0 or a symbol ‘\(r\)’. That is, we alternate \(W\), the indicator function for \(R\), and \(C\), and we place the \(j\)th element of \(S\) right after the \((j-1)\)st descent \((w_{d_{j-1}}, w_{d_j})\) of \(W\).

The elements of \(S\) are written in increasing order. The validity of \((S,R,T)\) can be checked in log-space as in the proof of Corollary [cor:ssyt95fixed95ell]. To check the validity of \(C\), initialize a counter \(\mathtt{b}=1\). After the \(j\)th descent, set \(\mathtt{b} = s_j\). Use one work tape to check \(W\) is a ballot sequence, use another work tape to check when there is a descent, another to check \(1 \leqslant c_i \leqslant\mathtt{b}\) for each \(c_i\) read, and another to check \(S\) is an increasing tuple. Each work tape takes up log-space (as they appear either in the machines of Corollaries [cor:factorial],  [cor:stirling] or [cor:ssyt95fixed95ell]).

For the Stirling numbers of the first kind, the proof is similar, using column ballot sequences instead. ◻

Proof. Suppose that we have to choose from \(N\) many elements to arrange into \(m\) many cycles of length \(i\) each. Assume the elements are chosen from \([N]\). Choose integers \(1 \leqslant a_1<a_2< \cdots <a_{m} \leqslant N\), then choose a set \(S_1 \subset [a_1-1]\) of \(i-1\) many elements, arrange them in \((i-1)!\) many ways, with \(a_1\) at the beginning these form the first cycle of length \(i\). Then choose the \(i-1\) many elements \(S_2\) from the \(a_2-i-1\) remaining elements and so on. The number of cycles with maximal elements \(a_1,\ldots,a_{m}\) is then \[\begin{gather} Z(N,m,i;\,a_1, \ldots, a_{m}) := \\ \binom{a_1-1}{i-1} (i-1)! \binom{a_2-i-1}{i-1} (i-1)! \cdots \binom{a_{m} - (m-1)i -1}{i-1} (i-1)!. \end{gather}\]

To create a permutation of \(n\) with cycle type \(\alpha\), choose the elements in \(1\)-cycles from \([n]\), the elements in \(2\)-cycles from \([n-m_1]\), those in \(3\)-cycles from \([n-m_1-2m_2]\), etc. We obtain \[\frac{n!}{z_\alpha} = \prod_{i=1}^n ~\sum_{\mathbf{a}\in\binom{[N_i]}{m_i}} Z(N_i,m_i,i;\,\mathbf{a})\] where \(N_i = n- \sum_{j=1}^{i-1} j m_j = N_{i-1} - (i-1) m_{i-1}\).

If \(x=(1^{m_1}\,0\,1^{m_2}\,0\,\dots)\) denotes the input, the functions sending \((1^i\,0\, x)\) to \(N_i\) and \(m_i\) are in \(\mathsf{FL}\). We now show that \[(1^N\,0\,1^m\,0\,1^i)\mapsto \sum_{\mathbf{a}\in\binom{[N]}{m}} Z(N,m,i;\,\mathbf{a})\] is in \(\#\mathsf{L}\), after which the proof concludes by an application of Theorem [thm:product].

The algorithm then proceeds as follows. We keep counters \(\mathtt{a}, \mathtt{A}, \mathtt{b}\). The witness encodes \(m\) elements \(a_1,\ldots,a_{m}\) and the witnesses for binomials and factorials which we have constructed in Theorem [thm:binomial] and Corollary [cor:factorial]. The witness is ordered \[\textstyle a_1,~ \mathtt{witness}\big(\binom{a_1-1}{i-1}\big),~ \mathtt{witness}((i-1)!);\quad a_2,~ \mathtt{witness}\big(\binom{a_2-i-1}{i-1}\big),~ \mathtt{witness}((i-1)!);~~ \ldots\] Set \(\mathtt{a}=a_1\) and \(\mathtt{A} = \mathtt{a}-1\). Check that the next two blocks of the witness are a witness for \(\binom{\mathtt{A}}{i-1}\) and \((i-1)!\). Then set \(\mathtt{b}=\mathtt{a}\) and read \(\mathtt{a}\leftarrow a_2\). Check \(\mathtt{b}<\mathtt{a}\leqslant N\). Set \(\mathtt{A} \leftarrow \mathtt{A}+(\mathtt{a}-\mathtt{b}) - i\) and once again check that the next two blocks of the witness are a witness for \(\binom{\mathtt{A}}{i-1}\) and \((i-1)!\). Repeat until having read all of the witness. ◻

Proof. The coefficients of the determinant are computable in \(\#\mathsf{L}\) per Theorem [thm:binomial]. The determinant is then in \(\mathsf{GapL}\) from Theorem [thm:detofsharpL]. ◻

Proof. The idea is similar to Theorem [thm:2-dim], but it does not follow directly because of the term \(E(n-1,n-k)\) of slightly different form. The witness is a sequence \({(n_0,k_0),(n_1,k_1),\ldots,(n_m,k_m)}\), where the numbers \(n_i,k_i\) are encoded in binary. We keep 4 counters \(\mathtt{a},\mathtt{b},\mathtt{c},\mathtt{d}\). Read the witness \(\mathtt{a} \leftarrow n_0\), \(\mathtt{b}\leftarrow k_0\) and check that they are equal to \(n\) and \(k\) respectively. Next read \(\mathtt{c}\leftarrow n_1\), \(\mathtt{d}\leftarrow k_1\) and check the local validity of the witness: if \(\mathtt{a}=1\) and \(\mathtt{b}=1\) we stop and accept the witness, and if \(\mathtt{b}=0\) we reject the witness; otherwise if \(\mathtt{a}>1\) check if \(\mathtt{c} = \mathtt{a}\) and \(\mathtt{d}= \mathtt{b}-1>0\) or else if \(\mathtt{c}=\mathtt{a}-1\) and \(\mathtt{d}=\mathtt{a}-\mathtt{b}>0\). If neither condition is satisfied, reject the witness; otherwise assign \(\mathtt{a} \leftarrow \mathtt{c}, \mathtt{b} \leftarrow \mathtt{d}\), and read into \((\mathtt{c},\mathtt{d}) \leftarrow (n_2,k_2)\). Perform the checks and continue with the reassignments of counter values and reading the witness. The end of the witness should be \((0,0)\), we then stop. The number of pairs that are read is \(m<n^2\) and the witness is polynomially sized. ◻

Proof. A crucial part of the problem is that we cannot encode a permutation directly as a witness, as we cannot check if it is indeed a sequence of distinct numbers by reading the witness only a fixed number of times. In this case, the RSK algorithm, which maps permutations \(w\) to SYTs \((P,Q)\) of the same shape \(\lambda\), gives that the length of the longest increasing subsequence of \(w\) is equal to the length of the first row, i.e. \(\lambda_1\) via Greene’s theorem, see e.g. [22]. Since \(\#\mathrm{SYT}(\lambda) = \#\mathrm{SYT}(\lambda')\), we can consider instead having \(\ell(\lambda) <k\). So \[\#{\rm Av}_n(1\ldots k) = \sum_{\lambda \vdash n, \ell(\lambda)<k} (\#\mathrm{SYT}(\lambda))^2.\] Then our witness consists of the partition \(\lambda\) encoded as \((1^{\lambda_1}\,0\,1^{\lambda_2}\,0\dots0\,1^{\lambda_\ell})\) and two witnesses for \(\# \mathrm{SYT}(\lambda)\) from Corollary [cor:syt95fixed95ell]. It is crucial that the partition \(\lambda\) can be stored in memory with a fixed number of log-space counters (encoded in binary): \(\mathtt{\lambda_1,\lambda_2,\ldots,\lambda_{\ell}}\) with \(\ell<k\) and the partition can thus be read many times to verify the shapes of the two SYTs. ◻

Proof. The length of the input is \(2(n-1)\), so we can initialize a counter \(\mathtt{a}\leftarrow n-1\). Output the least significant digit of \(\mathtt{a}\); that is the sign \((-1)^{n-1}\). Copy \(\mathtt{a}\) to the output tape. Then, while \(\mathtt{a} > 1\), write a \(0\) in the output tape and decrease \(\mathtt{a}\) by \(1\). ◻

Proof. Here, the input size is \(N = \sum_{i,j} |A_{i,j}|+ \sum_i |b_i| + 2nm+2m\). The witness is \(\mathbf{x}=(x_1,\ldots,x_n)\) with each integer encoded in binary. Note that a rough upper bound on the coordinates is \(|x_i|<(Nn)^n\). We will read the witness into \(n\) counters \(\mathtt{x_i} \leftarrow x_i\). Keep counters \(\mathtt{s}, \mathtt{a}, \mathtt{i}, \mathtt{j}, \mathtt{b}\) in \(\log(N)\)-space encoded in binary. Set \(\mathtt{i}=1\), \(\mathtt{s}=0\) and \(\mathtt{j}=1\). Read \(\mathtt{a} \leftarrow A_{i,j}\), set \(\mathtt{s} \leftarrow \mathtt{s} + \mathtt{a}*\mathtt{x_j}\), see Lemma [lem:elementary], and keep increasing \(\mathtt{j}\) until it reaches \(n\). Read \(\mathtt{b}\leftarrow b_i\) and check if \(\mathtt{s} \leqslant\mathtt{b}\). Increase \(\mathtt{i}\) by 1, reset the counters and repeat. ◻

Proof. We have \(kP = \#\{A\mathbf{x}\leqslant k\mathbf{b}\}\). Compose the function \((1^{b_i},1^k) \mapsto (1^{kb_i})\) (which is in \(\mathsf{FL}\)) with the verifier \(\mathsf{NL}\) machine of Theorem [thm:polytopes]. ◻

Proof. The input size is \(N = 2|\alpha|+n+m\) since for a valid input we should have \(|\beta|=|\alpha|\). We consider the general case, the 0-1 contingency tables are treated in the same way. The witness is \[w = A_{1,1},A_{1,2},A_{1,3},\cdots,A_{1,m};A_{2,1},A_{2,2},\ldots,A_{2,m};\ldots;A_{n,1},\ldots,A_{n,m},\] with \(A_{i,j}\) encoded in unary and we use the symbols \(,\) and \(;\) as delimiters. In the algorithm we keep \(m\) many counters \(\mathtt{b_i}\) initialized at \(0\) for \(i=1,\ldots,m\), counters \(\mathtt{a}\) and \(\mathtt{A}\), indices \(\mathtt{i},\mathtt{j}\) and \(\mathtt{m},\mathtt{n}\). We read the first \(n\) bits from \(w\) into \(\mathtt{n}\) recorded in \(\log(n)\) space in binary. Next read \(\mathtt{a} \leftarrow \alpha_1\) in binary. Set \(\mathtt{i}\leftarrow 1, \mathtt{j} \leftarrow 1\). Read \(\mathtt{A} \leftarrow A_{1,1}\) (i.e. the first part of \(w\) before the first \(,\)) in binary, set \(\mathtt{a} \leftarrow \mathtt{a}-\mathtt{A}\). Set \(\mathtt{b_j} \leftarrow \mathtt{b_j}+\mathtt{A}\). Next, increase \(\mathtt{j}\) by 1, and repeat the last steps: \(\mathtt{A} \leftarrow A_{1,2}\), \(\mathtt{a} \leftarrow \mathtt{a} - \mathtt{A}\), \(\mathtt{b_j} \leftarrow \mathtt{b_j}+\mathtt{A}\). When reaching the first \(;\) we check if \(\mathtt{a}=0\), otherwise the witness is invalid. Then increase \(\mathtt{i}\), reset \(\mathtt{j}\leftarrow 1\), read the input \(\mathtt{a} \leftarrow \alpha_i\) and repeat the above steps. In the end we have the counters \(\mathtt{b_1},\ldots,\mathtt{b_m}\) and we check if \(\mathtt{b_j}=\beta_j\) from reading the input. ◻

Proof. Littlewood–Richardson coefficients count integer points in the hive polytope which is a triangular array of variables with local inequalities and boundary conditions. The dimension of the polytope is \(\binom{n}{2}\), the inequalities are of the type \(a+c \geqslant b+d\) for all rhombi in a triangular grid of the variables. The boundary conditions give that the variables on the sides are \(\lambda\), \(\mu\), \(\nu\), respectively. Then the resulting polytope has a fixed number of variables, inequalities, the linear inequalities have constant coefficients \(\{-1,0,1\}\) and the vector \(b\) has entries \(0\) or \(\in \{\lambda_i,\mu_i,\nu_i, i=1,\ldots,n\}\). Theorem [thm:polytopes] then applies and the result follows. ◻

Proof. We have \[m_\mu\cdot m_\nu(x_1,\ldots,x_n) = \sum k_{\mu,\nu}^\lambda m_\lambda(x_1,\ldots,x_n),\] where \[k_{\mu,\nu}^\lambda = \#\{ (\alpha,\beta)\in\mathrm{WComp}^2 \mid \mathrm{sort}(\alpha) = \mu, ~ \mathrm{sort}(\beta) = \nu, ~ \alpha + \beta = \lambda \}.\]

We construct a machine taking input \(\lambda,\mu,\nu\) in unary and witness \(w\), which checks if \(w\) is in the above set. Initialize \(3n\) counters \[\mathtt{c_1^\lambda}, \ldots, \mathtt{c_n^\lambda}, \mathtt{c_1^\mu}, \ldots, \mathtt{c_n^\mu}, \mathtt{c_1^\nu}, \ldots, \mathtt{c_n^\nu}\] to the values of the parts of \(\lambda,\mu\) and \(\nu\). We then read the witness and use another \(2n\) (fixed number) counters to store \(\alpha\) and \(\beta\). With another index counter \(\mathtt{i}\) we check that \(\mathtt{\alpha_i}+\mathtt{\beta_i}=\lambda_i.\) We then sort \(\mathtt{\alpha}\) and \(\mathtt{\beta}\) using bubblesort and check if they are equal to \(\mu,\nu\), respectively. ◻

Proof. Initialise two binary-encoded counters \(\mathtt{i}=i\) and \(\mathtt{I}=i+1\); these will require at most \(\log(n)\)-space each. Initialise two more counters: \(\mathtt{a}=0\) to keep track of which parentheses pair up, and \(\mathtt{j}=1\) that will be used to keep track of the position of the last open bracket ever read; these will require at most \(\log(m)\)-space each.

We read \(x\) from left to right. If the current entry \(x_k\) is not equal to \(\mathtt{i}\) nor \(\mathtt{I}\), do nothing. If \(x_k = \mathtt{i}\), then increase \(\mathtt{a}\) by \(1\). If \(x_k = \mathtt{I}\) and \(\mathtt{a}>0\), then decrease \(\mathtt{a}\) by \(1\). If \(x_k = \mathtt{I}\) and \(\mathtt{a}=0\), then set \(\mathtt{j} \leftarrow k\).

When we have read the whole of \(x\), the counter \(\mathtt{j}\) points to the right-most unpaired closing bracket. Read through \(x\) once again, copying everything to the output tape. Except, when at \(x_\mathtt{j}\), copy \(\mathtt{i}\) to the output tape instead. ◻

Proof. Loop through \(\mathtt{i}=1,\ldots,n-1\). Then compose with the \(\mathsf{FL}\) function from Theorem [thm:crystal32operator] to compute \(E_{\mathtt{i}}\,.\,x\). Accept if \(E_{\mathtt{i}}\,.\,x=0\) for all \(\mathtt{i}\). ◻

Proof. Begin by asking ‘is \(x\) a highest weight element?’, which we can do in \(\mathsf{L}\) by Corollary [cor:highest32weight].

Then, for \(\mathtt{i}=1,2,\ldots,n\), initialise a counter \(\mathtt{b}=\lambda_\mathtt{i}\). Read through \(x\) again; if \(x_k=\mathtt{i}\) then \(\mathtt{b}\leftarrow\mathtt{b}-1\). When \(x\) is fully read, check \(\mathtt{b}=0\); otherwise reject. ◻

Proof. We adapt the machine from Theorem [thm:crystal32operator] to compute \(\varepsilon_i(x)\). To do this, we add a counter \(\mathtt{e}=0\). Whenever \(\mathtt{a}=0\) in the machine of Theorem [thm:crystal32operator], we have found an unpaired ‘)’ and thus we increase \(\mathtt{e}\) by \(1\). When we finish reading \(x\) we have \(\mathtt{e}=\varepsilon_i(x)\). Output this value instead of \(E_i\,.\,x\).

A similar machine can be constructed for computing \(\varphi_i(y)\), by reading \(y\) right-to-left. Store it in a counter \(\mathtt{f}\).

Both of these values are upper-bounded by the length of \((x,y)\).

Finally output \(E_i\,.\,x\) followed by \(y\) if \(\mathtt{f} < \mathtt{e}\), or \(x\) followed by \(E_i\,.\,y\) otherwise. ◻

Proof. The witness is a partition \(\lambda_1, \lambda_2, \ldots\) written in binary. A counter is used to check that \(\sum_i \lambda_i = n\). Another two counters check that \(\lambda_i \leqslant\lambda_{i-1}\) for all \(i\). ◻

Proof. Take the verifier \(\mathsf{NL}\) machine from Theorem [thm:partition]. Add one counter to check the length of \(\lambda\) is less than \(\ell\). Add another counter to check that \(\lambda_1\leqslant k\). ◻

Proof. We first observe that \[\binom{n}{a}_{\!\!q} = \sum_r p_r( (n-a) \times a)\cdot q^r\] and therefore \[\binom{n}{a_1,\ldots,a_k}_{\!\!q} = \sum_{r_1,r_2,\ldots} p_{r_1}((n-a_1)\times a_1) p_{r_2}( (n-a_1-a_2) \times a_2) \cdots q^{r_1+r_2+\cdots} .\] We proceed like in the proof of Theorem [thm:product]. The witness is a sequence of the witnesses \(w^{(1)},w^{(2)},\ldots\) from Corollary [cor:partitions32in32a32box], together with integers \(r_i\), so \(w=r_1, w^1; r_2, w^2; \cdots\). We initialise counters \(\mathtt{n}=n\), \(\mathtt{i}=1,\mathtt{R}=0,\mathtt{d}=0\). After reading \(\mathtt{d}\leftarrow r_\mathtt{i}\), we set \(\mathtt{R} \leftarrow \mathtt{R} + \mathtt{d}\). Read and check the validity of \(w^{\mathtt{i}}\) as a witness for \(p_{\mathtt{r_i}}((\mathtt{n}-a_{\mathtt{i}})\times a_\mathtt{i})\). Then increase \(\mathtt{i}\) by \(1\), set \(\mathtt{n}\leftarrow\mathtt{n}- a_\mathtt{i}\), and repeat. In the end check \(\mathtt{R}=r\). ◻

Proof. Initialise two binary-encoded counters \(\mathtt{n}=n\) and \(\mathtt{k}=k\). Initialise one more binary-encoded counters \(\mathtt{q}\). While \(\mathtt{q}*\mathtt{k} \leqslant\mathtt{n}\), increase \(\mathtt{q}\) by 1. Once \(\mathtt{q}*\mathtt{k} > \mathtt{n}\), decrease \(\mathtt{q}\) by 1. Return \(\mathtt{q}\) and \(\mathtt{n}-\mathtt{q}*\mathtt{k}\). Multiplication, comparison, and difference require an extra auxiliary counter, so in total 4 counters are needed. ◻

Proof. Create a counter \(\mathtt{n}=n\). Loop through \(\mathtt{k}=2,\ldots,n-1\). Perform Euclidean division \(n/\mathtt{k}\) to find a remainder. If at any point the remainder is \(0\), reject. Otherwise, accept. ◻

Proof. The witness is a tuple \(d, q, a_1, a_2, \ldots, a_{k}\) of \(k+2\) integers in binary, such that \(1 \leqslant d \leqslant n = dq\), and such that \(1\leqslant a_i \leqslant d\) for all \(i\). ◻

Proof. For \(\mathtt{d}=1,\ldots,n\) call the \(\mathsf{FL}\) machine from Theorem [thm:euclidean32div] to compute \(n/\mathtt{d}\). If the remainder is \(0\), add \(\mathtt{d}^k\) to a cumulative counter \(\mathtt{c}\). At the end, output \(\mathtt{c}\). ◻

Proof. The witness is \(k\). Compute the greatest common divisor of \(n\) and \(k\) by successive applications of the Euclidean division algorithm from Theorem [thm:euclidean32div]. Accept if \(\gcd(k,n) = 1\) and \(k\leqslant n\). ◻

Proof. The statement follows by an application of Theorem [thm:product]. The function \(f : (1^p)\mapsto p\) is clearly in \(\#\mathsf{L}\). Set \(f(\emptyset)=1\). The function \[\label{eq:is32prime32divisor} g : (1^n\,0\,1^p) \mapsto \begin{cases} 1^p & \text{if p|n and p is prime},\\ \emptyset & \text{otherwise} \end{cases}\tag{12}\] is in \(\mathsf{FL}\) by Theorems [thm:euclidean32div] and [primes]. The radical of \(n\) is the function \((1^n)\mapsto\prod_{p=1}^n f(g(1^n\,0\,1^p))\), which is therefore in \(\#\mathsf{L}\). ◻

Third proof of Corollary [cor:factorial]. Fix a prime \(p\). Legendre’s formula gives \(v_p(n!) = \lfloor n/p\rfloor + \lfloor n/p^2\rfloor + \lfloor n/p^3\rfloor + \cdots\). Note that the sum is finite. We can therefore compute \(v_p(n!)\) in \(O(\log(n))\)-space by adding the results of Euclidean divisions of \(n\) by the successive powers \(p^k\) of \(p\), while \(p^k \leqslant n\). The function \((1^n)\mapsto p^{v_p(n!)}\) is in \(\#\mathsf{L}\), a witness being a tuple of \(v_p(n!)\)-many numbers \(1\leqslant a_i \leqslant p\). (Here we are applying Theorem [thm:product], where the number of factors is \(\log_p(n!) = O(n \log (n))\), and hence can be stored in \(O(\log_2(\log_p(n!))) = O(\log_2(n))\)-space.)

All prime divisors of \(n!\) are smaller or equal than \(n\). Hence the formula \[n! = \prod_{p\leqslant n~\text{prime}} p^{v_p(n!)}\] is in the hypotheses of Theorem [thm:product]. ◻

Proof. The input is of length \(m=\lambda_1+\ell(\lambda) = O(|\lambda|)\), so we need to construct a \(\log(|\lambda|)\)-space machine. We count the number of \((0,1)\) ordered pairs.

Initialise a counter \(\mathtt{v}=0\). Read \(x=\mathrm{Maya}(\lambda)\) from right to left, keeping track of the position with a counter \(\mathtt{i}\) in a loop, starting with \(\mathtt{i} = m\).

If \(x_{\mathtt{i}}=0\), set \(\mathtt{i}\leftarrow \mathtt{i}-1\). If \(x_{\mathtt{i}}=1\), start another counter \(\mathtt{j}=\mathtt{i}-1\) which performs an inner loop. Check if \(x_{\mathtt{j}} = 0\), in which case \(\mathtt{v}\leftarrow\mathtt{v}+1\); otherwise do nothing. Then decrease \(\mathtt{j}\) by \(1\) and repeat. When \(\mathtt{j}<0\), stop this inner \(\mathtt{j}\)-loop; we have added to \(\mathtt{v}\) the number of 0s to the left of the 1 at \(x_\mathtt{i}\); this corresponds to the number of boxes in \([\lambda]\) in one row. \[\ytableausetup{boxsize={.96em}} \ydiagram{7,7,6,4,3,2,2}*[*(blue!30)]{0,0,0,0,3} \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wzptklsd.png}\label{iazmqxrj}\end{figure}\tag{14}\] Then set \(\mathtt{i}\leftarrow \mathtt{i}-1\) and repeat until \(\mathtt{i}=0\).

At the end, output the value of \(\mathtt{v}\). ◻

Proof. Let \(n = |\lambda|\). The input is of length \(\lambda_1+\ell(\lambda) = O(n)\), so we need to construct a \(\log(n)\)-space machine. To do so, we interpret \(\mathrm{Maya}(\lambda)\) as a \(p\)-abacus, count the number of beads below holes, then interpret it as a \(p^2\)-abacus, count the number of beads below holes, etc.

Initialise two counters \(\mathtt{r}=p\) and \(\mathtt{v}=0\). Read \(x=\mathrm{Maya}(\lambda)\) from right to left, keeping track of the position with a counter \(\mathtt{i}\) in a loop.

Now perform the \(\mathtt{i}\)-loop and the \(\mathtt{j}\)-inner loop described in the proof of Lemma [lem:maya32size], except that \(\mathtt{j}\) is initialised at \(\mathtt{i}-\mathtt{r}\) and decreased by \(\mathtt{r}\) each time.

At the end of the \(\mathtt{i}\)-loop, the value of \(\mathtt{v}\) counts the cells of \([\lambda]\) whose hook-length is divisible by \(\mathtt{r} = p\). Set \(\mathtt{r} \leftarrow \mathtt{r}*p\) and repeat, adding to the same counter \(\mathtt{v}\). Whenever \(\mathtt{r} > |x|\), the value of \(\mathtt{v}\) is \(v_p(\prod_{c\in[\lambda]}\mathsf{hl}_\lambda(c))\).

The maximum value that \(\mathtt{v}\) can attain is upper-bounded by \(\log_p(\prod \mathsf{hl}_\lambda(c))\), which by the hook-length formula is upper bounded by \(\log_p(n!) = O(n\log(n)) = O(n^2)\) and hence can be stored in \(O(\log_2(n))\)-space. ◻

Proof. Write \[\#\mathrm{SYT}(\lambda) = \frac{n!}{\prod_{c\in[\lambda]} \mathsf{hl}_\lambda(c)} = \prod_{p\leqslant n~\text{prime}} p^{v_p(n!) - v_p(\prod_{c\in[\lambda]} \mathsf{hl}_\lambda(c))},\] where we used that the prime divisors of \(n!\) are at most \(n\), and since \(\#\mathrm{SYT}(\lambda)\) is an integer the same holds for the denominator. The function sending \(\mathrm{Maya}(\lambda)\) to \(v_p(n!) - v_p(\prod_{c\in[\lambda]} \mathsf{hl}_\lambda(c))\) is in \(\mathsf{FL}\), as we saw in the third proof of Corollary [cor:factorial] and in Lemma [lem:hl32val]. The function \((1^p) \mapsto p\) is trivially in \(\#\mathsf{L}\) (where we set \(\emptyset \mapsto 1\)). Hence by Theorem [thm:product], given any fixed \(p\) the function \[\mathrm{Maya}(\lambda) \mapsto p^{v_p(n!) - v_p(\prod_{c\in[\lambda]} \mathsf{hl}_\lambda(c))}\] is in \(\#\mathsf{L}\). The function sending \((1^p)\) to \((1^p)\) if \(p\) is a prime or \(\emptyset\) otherwise is in \(\mathsf{FL}\) by Theorem [primes]. Apply Theorem [thm:product] again to conclude. ◻

Proof. Clear from the definition of a partition. ◻

Proof. In the base case \(x = 0\) the right-most sum is empty and the statement holds by 19 . For the induction step (\(x\geqslant 1\)), we calculate \[\begin{align} a^{(j,1^x)} &\stackrel{\eqref{eq:KOHtreea}}= (a^{(j,1^{x-1})}+2)\cdot1 - 2 \ell(\mu^{(j,1^{x-1})})\\ &\stackrel{\mathrm{ind.\,hyp.}}{=} 2x + (a+2)j - 2 |\mu'_{\leqslant j}| - 2 \sum_{y=0}^{x-1}\ell(\mu^{(j,1^{y})}). \qedhere \end{align}\] ◻

Proof. Suppose \(T\) is a marked KOH tree of type \((n,k,r)\) and construct \(T'\). We begin by showing that \(T'\) is a small KOH witness of type \((n,k,r)\).

Conditions [sw:lex]–[sw:unique] of the definition of a small KOH witness are trivially satisfied. Condition [sw:len] holds since the outgoing edges of a node \((\mu,a,b)\) in \(T\) correspond to the various parts of \(\mu\), and the \(b\)-values of the children sum up to \(\ell(\mu)\). Similarly, conditions [sw:k] and [sw:b] hold because \(\sum_j j\cdot m_j(\mu) = |\mu|\). Condition [sw:mone] follows directly from Definition [de:KOH]. Condition [sw:a] holds by Lemma [lem:a]. Conditions [sw:t1]–[sw:tK] hold by definition of a marked KOH tree.

We now show how given a small KOH witness \(T'\) one can recover \(T\). First note that for any internal node \(v\) of \(T'\) different from the root one can recover the triple \((\mu,a,b)\) labelling the corresponding node of \(T\) as follows: \(a\) is given by the function \(a(v)\) (see Lemma [lem:a]), \(b\) is given by \(b(v)\) (Lemma [lem:partition]), and \(\mu\) is completely determined by the formulas \[\begin{align} \mu'_1 &= \ell(v),\\ \mu'_2 &= \ell(v) - b(v\mathord{\uparrow}\mathord{\downarrow}_{j(v),x(v)+1}),\\ \mu'_j &= \ell(v) - b(v\mathord{\uparrow}\mathord{\downarrow}_{j(v),x(v)+1}) - \sum_{1<i<j} b(v\mathord{\downarrow}_{i,0}) \end{align}\] for any \(j\geqslant 3\) (again by Lemma [lem:partition]). For the root \(R\), a similar set of formulas hold, by replacing \(b(v\mathord{\uparrow}\mathord{\downarrow}_{j(v),x(v)+1})\) by \(b(v\mathord{\downarrow}_{1,0})\). Similarly, for any true leaf labelled with \(a\) and marked with \(t\), the corresponding leaf of \(T\) is labelled by \(((1),a,1)\) and marked by \(t\). For any edge \((u,v)\) labelled \((j,0)\) of \(T'\), create an edge labeled \(j\) between the node of \(T\) corresponding to \(u\) and the node of \(T\) corresponding to \(v\). For any edge \((u,v)\) labelled \((j,x)\) with \(x\geqslant 1\), create an edge labeled \(1\) between the node of \(T\) corresponding to \(u\mathord{\downarrow}_{j,x-1}\) and the node of \(T\) corresponding to \(v\).

Since \(b(v)=1\) for true leaves, a leaf of \(T\) must correspond to a partition of \(1\). Conditions [sw:root], [sw:x-1], and [sw:unique] ensure that any node of \(T\) has at most one outgoing edge labelled \(j\) for each \(j\). Conditions [sw:len]–[sw:b] ensure that for each node \((\mu,a,b)\) of \(T\), then \(\mu\) is a partition of \(b\) and the outgoing edges correspond to the distinct parts of \(\mu\) (see Lemma [lem:partition]). Condition [sw:a] checks the defining property of \(a\) is satisfied, thanks to Lemma [lem:a]. Finally, Condition [sw:lex] fixes an order of the leaves of \(T\) and [sw:t1]–[sw:tK] ensure that the marks of these leaves are consistent with those of a KOH tree.

It is clear that these two processes are inverse to each other. ◻

Proof. Let \(T'\) be a small KOH witness and let \(T\) be the corresponding marked KOH tree. Recall that each node \(u\) of \(T'\) corresponds to a node of \(T\) labelled by a triple \((\mu,a,b)\). Suppose \(u\) is not the root. If \(v\) is a child of \(u\) in \(T'\), then there exists a path in \(T\) in which there is one edge labelled \(j>1\). Thus the partition labelling \(v\) in \(T\) is of size at most \(|\mu|/j = b/j \leqslant b/2\).

Consequently, a path from the root \((\lambda,n,k)\) to a leaf of \(T'\) can be of length at most \(\log_2(k)+1\). ◻

Proof. We use Proposition [p:bijection] and instead show that a KOH tree of type \((n,k,r)\) has at most \(k\) leaves.

Let \(T(\mu,n,k)\) denote a marked KOH tree with root \((\mu,n,k)\). The proof is by induction on \(k\). If \(k=1\) then the tree \(T(\mu,n,k)\) consists of one vertex which is the leaf. Suppose the trees of type \((n',k',r')\) with \(k'\leqslant k-1\) have at most \(k'\) many leaves. Consider the children of the root of \(T(\mu,n,k)\). Let \(\mu=(1^{m_1}2^{m_2}\ldots r^{m_r})\). First, suppose that \(m_1 \neq k\) (have \(m_i \leqslant k/i <k\) for all \(i\geqslant 2\)). Then the children vertices are \(v_j = (\mu^{(j)}, a^{(j)}, m_j)\) for \(j\in J:=\{ j: m_j\geqslant 1\}\) (the set of row lengths of \(\mu\)). We have that \(\sum_j j m_j = |\mu|=k\) and hence \(\sum_j m_j \leqslant k\). Finally, the set of leaves of \(T(\mu,n,k)\) is the union of the sets of leaves of \(T(v_j)\). By induction, each \(T(v_j)\) has at most \(m_j<k\) many leaves and so the total number of leaves of \(T(\mu,n,k)\) is \(\leqslant\sum_j m_j \leqslant k\).

Next, suppose that \(m_1=k\). Then \(n_1=(n+2)1-2k=n +2(1-k)<n\) and there is exactly one child \((\mu^{(1)},a^{(1)},k)\). If \(\mu^{(1)} \neq (1^k)\) the above analysis applies. Otherwise we have a path of vertices \(( (1^k),a^{(j)},k)\) with \(a^{(j)}\) strictly decreasing until it branches out, at which point the above analysis applies, and the proof is done by induction. ◻

Proof. We use Proposition [p:bijection] and instead show that the sum of the \(a\)-values at all leaves of a KOH tree of type \((n,k,r)\) is at most \(nk\). To see the last part, we use the fact that the KOH tree definition from [8] is a direct unravelling of the KOH formula 18 , and the intermediate label \(a^{(j)}\) computed via equation 19 are the integers appearing in the binomials of 18 , so we have \[\genfrac{[}{]}{0pt}{}{a+b}{b} = \sum_{\mu\vdash b} \, \prod_{m_j(\mu)\ne0} \genfrac{[}{]}{0pt}{}{a^{(j)} + m_j(\mu)}{m_j(\mu)}.\] Since these are Laurent polynomials in \(q\) with positive coefficients, the maximal degrees of the products do not exceed the maximal degree on the left, which is \(ab\). So for every vertex labelled \((\mu,a,b)\) we have \[\sum_j a^{(j)}m_j(\mu) \leqslant ab,\] where the labels of its children are \((-,a^{(j)},m_j(\mu))\). The KOH formula is applied recursively to each quantum binomial coefficient, giving the branching in the vertices of the tree, and the leaves appear when \(b=1\). Expanding the above inequality along the tree we get that the sum of the leaf labels under the vertex \((\mu,a,b)\) is at most \(ab\), and the claim follows since the root has \((a,b) =(n,k)\). ◻

Proof. We use the idea from the proof of Lemma [lem:sum32of32a32values]. For a vertex \(v\) labeled by \((\mu,a,b)\), let \(\phi(v) = ab\), we will show that the \(\phi\) values decrease strictly from a parent to a child as long as the child is not a leaf.

Let \(v\) be an internal vertex, so \(b>1\). First, suppose that \(\mu=(1^b)\), then \(v\) has only one child \(w\) with a label \((\mu^1,a_1,b_1)\) where \(\mu^1 \vdash b_1=b\) and \(a_1 = (a+2)1 -2b \leqslant a-2\) since \(b\geqslant 2\). Then \[\phi(w) =a_1b_1 \leqslant(a-2)b = \phi(v) -2b \leqslant\phi(v)-4.\]

Next, if \(\mu = (1^{m_1}2^{m_2}\ldots)\) with \(m_j \geqslant 1\) for some \(j>1\), we consider the children \(w^{(j)}\) corresponding to \(m_j \geqslant 1\) with labels \((\mu^{(j)}, a^{(j)},m_j)\). We have that \[\phi(w^{(j)}) = ( (a+2)j -2|\mu'_{\leqslant j}|)m_j =a\cdot(jm_j) -2m_j\cdot ( |\mu'_{\leqslant j}|-j).\] For \(j=1\), if \(m_1 >0\) we have \(\mu'_1=m_1+\cdots = \ell(\mu) \geqslant 2\), since the partition is not just a single row or column. At the same time, \(1m_1 = b - \sum_{j \geqslant 2} jm_j \leqslant b-2\), since \(m_j\geqslant 1\) for some \(j\geqslant 2\). So \(\phi(w^{(1)}) \leqslant a(1m_1)-2 \leqslant a (b-2)-2\leqslant ab -4=\phi(v) -4\).

For \(j>1\) with \(m_j>0\) we have that \(|\mu'_{\leqslant j}|= \sum_{i\leqslant j} (m_i+m_{i-1}+\cdots+m_b) >j\) unless \(\mu=(b)\) and so \(\phi(w^{(j)}) \leqslant a\cdot(jm_j)-2 \leqslant\phi(v)-2\). If \(\mu=(b)\) then \(w\) is a leaf and \(\phi(w)=\phi(v)\).

Hence in all cases, but possibly \(w\) being a leaf, we have that \(\phi(w) \leqslant\phi(v)-2\).

For every path from the root to a leaf \(v_0 \to v_1 \to v_2 \to \cdots \to v_s\) we have that \(nk-2s=\phi(v_0) -2s \geqslant\phi(v_1)-2(s-1) \geqslant\cdots \geqslant\phi(v_{s-1}) -2 \geqslant\phi(v_s)-2 \geqslant-2,\) so \(s < (nk+2)/2\), and the path has at most \(\lfloor nk/2 \rfloor+2\) many vertices. ◻

Proof. From the bijection between nodes, the number of vertices in the small witness and the original tree are the same per Proposition [p:bijection]. We will bound the number of KOH tree vertices. First, the number of leaves in a KOH tree is at most \(k\), which is Lemma [lem:at32most32b32leaves]. For each leaf, consider the shortest path in the tree to the root, by Lemma [lem:koh32tree32depth] it has \(O(nk)\) vertices. Every vertex of the tree lies on (at least) one such path (a path that starts from a leaf below it), thus the total number of vertices is bound by the number of leaves times the maximal length of these paths, which gives \(O(nk^2)\). ◻

Proof. We just need to bound the required space. Storing \(n\), \(k\), and \(r\) requires \(O(\log_2(n+k+r))\) space. For the counters checking the markings of true leafs, begin by noting that there are at most \(k\) true leaves (Lemma [lem:at32most32b32leaves]) and thus the counters are upper bounded by \(S := (a_1 + a_2 + \cdots + a_K) \leqslant nk\) by Lemma [lem:sum32of32a32values]. This is at most polynomial in \(n\) and \(k\) and thus takes \(O(\log_2(n+k))\) space to store.

For the remaining counters we introduce some notation. There is a family of counters per level of the small KOH witness \(T'\). Let \(T\) be the corresponding marked KOH tree. Let \(\mathcal{L}'_K\) be the set of nodes of \(T'\) at level \(K\), and let \(\mathcal{L}_K\) be the corresponding nodes in \(T\). Every other counter in level \(K+1\) is upper-bounded by the size of the largest partition \(\lambda^{(K)}\) among those appearing in the labels of \(\mathcal{L}_K\) (note that the \(a\)-values are not stored at a vertex, and only one column sum is stored at a vertex). In turn, this partition is of size at most \(|\lambda^{(K-1)}|/2\) for all \(K>1\), as we argued in the proof of Lemma [lem:log32depth], whereas \(|\lambda^{(1)}|\) and \(|\lambda^{(2)}|\) are at most \(k\). There is a constant amount of counters per level, so the total amount of space used is at most \[O\Big( \log_2(k) + \log_2(k/2) + \log_2(k/4) + \cdots + \log_2(k/2^{\log_2(k)})\Big)\] by Lemma [lem:log32depth]. Since there are \(\log_2(k)\) many summands, each of which is at most \(\log_2(k)\), this quantity simplifies to \(O(\log_2(k)^2)\). ◻

Proof. Let \(T\) be a small KOH witness. By Lemma [lem:poly32many32nodes], it has polynomially many nodes. After visiting each node, we update a constant number of counters, taking \(\mathrm{poly}\)-time for each counter. Hence the total time required is polynomial. ◻

Proof of Theorem [thm:Hermite]. The Hermite coefficients are in \(\mathsf{GapL}\) by Corollary [cor:partitions32in32a32box] and 17 . By [8], these coefficients count the number of KOH trees of type \((n,k,r)\). By Proposition [p:bijection], these are in bijection with small KOH witnesses. By Propositions [p:polylog] and [p:polytime], the Turing machine with a read-once left-to-right witness tape constructed in this section checks the validity of a small KOH witness in poly-time and \(\log(n+k+r)^2\)-space. ◻

Proof. First note that we must have \(k+1\geqslant\ell(\lambda)\), as otherwise the Schur specialization is 0. The expression via the \(q\)-hook-content formula is a polynomial in \(q\), but it can be computed as an infinite series in \(q\) where it happens that the larger coefficients cancel. Namely, let \(C = \sum_i(i-1)\lambda_i\) and expand each term \(1/(1-q^{\mathsf{hl}(u)})\) as a geometric sum, we then have \[\begin{align} q^C \prod_{u \in [\lambda]} \frac{ 1-q^{k+1+\mathsf{ct}(u)}}{1-q^{\mathsf{hl}(u)}} = q^C \prod_{u \in [\lambda]} (1-q^{k+1+\mathsf{ct}(u)}) (1+q^{\mathsf{hl}(u)} +q^{2\mathsf{hl}(u)}+\cdots) \\ = \sum_{D \subseteq [\lambda]} (-1)^{|D|} \sum_{\mathbf{r}} q^C \prod_{u \in [\lambda]\setminus D} q^{r_u \mathsf{hl}(u)} \prod_{u \in D} q^{k+1+\mathsf{ct}(u) +r_u \mathsf{hl}(u)}, \end{align}\] where the sum is over subsets \(D\) of boxes in the Young diagram \([\lambda]\) and the vector \(\mathbf{r}\) contains one non-negative integer entry for every box \(u\in [\lambda]\). To obtain the coefficient \(c_r(\lambda,k)\) of \(q^r\) in \(s_\lambda(1,q,\ldots,q^{k})\) we need to equate the exponents to \(r\) and select only those. The positive terms are those indexed by a subset \(D\) of even cardinality; let \[c_+(r) = \#\Big\{ (D, \mathbf{r})\mid D \subseteq [\lambda], ~ |D|~\text{even}, ~C+\!\!\sum_{u \in [\lambda]} r_u \mathsf{hl}(u) + \!\sum_{u \in D} (k+1+\mathsf{ct}(u)) =r\Big\}\] and likewise, set \(c_-(r)\) for the subsets \(D\) of odd cardinality. Then \(c_r(\lambda,k) = c_+(r) - c_-(r)\), and we need to show that the functions sending \((1^{\lambda_1}\,0\,1^{\lambda_2}\,0\,\dots\,0\,0\,1^k\,0\,0\,1^{r})\) to \(c_+(r)\) and \(c_-(r)\) are in \(\#\mathsf{L}\).

The witness for \(c_+\) (for \(c_-\) is completely analogous) is a word of 5 symbols \(\{0,1,d,\mathrm{``},\mathrm{''},\mathrm{``};\mathrm{''}\}\) as follows: \(w=d^{e_1}r_1,d^{e_2}r_2,d^{e_3}r_3,d^{e_4}r_4,\ldots,r_{\lambda_1};r_{\lambda_1+1},\ldots\) with \(e_j=1\) if the \(j\)th cell is in \(D\) (reading row by row, where cells are separated by commas and rows by semicolons). To read and check the witness, the working tape has counters \(\mathtt{C},\mathtt{d}\leftarrow 0,\mathtt{i}\leftarrow 1,\mathtt{j}\leftarrow 1,\mathtt{h},\mathtt{R}, \mathtt{r}\). Set \(\mathtt{C}\leftarrow C\) in binary, which we can do because \(C\leqslant|\lambda|^2\). We read the witness row by row, where the row index counter \(\mathtt{i}\) starts from one, and at every semicolon increases by 1. The column index counter \(\mathtt{j}\) resets at 1 after every semicolon and is increased by 1 each time we read a comma. At each semicolon we check that \(\mathtt{j}=\lambda_i\). Initialise the counter \(\mathtt{R}\leftarrow r-\mathtt{C}\), which will keep track of the sum of exponents. Every time we read a symbol \(d\) we decrease \(\mathtt{R}\) by \(k+1+\mathtt{j}-\mathtt{i}\), and increase \(\mathtt{d}\) by 1. We also compute the hook length \(\mathtt{h} \leftarrow \lambda_i - \mathtt{i}+\lambda_j'-\mathtt{j}+1\) for the box at \((\mathtt{i},\mathtt{j})\) (read the number of 0s in the input every time there at least \(\mathtt{j}\) many 1s in the string between two 0s, that would give \(\lambda_j'\)). Set \(\mathtt{R} \leftarrow \mathtt{R} - \mathtt{h}*\mathtt{r}\), where \(\mathtt{r}\leftarrow r_u\) from the witness at that step. In the end, check if \(\mathtt{R}=0\) and \(\mathtt{d}\) is even to accept the witness. ◻

Proof. From 21 we get \(a^\lambda_{\mu[k]}=c_r(\mu,k)-c_{r-1}(\mu,k)\). Use Theorem [thm:schur95q-specialization] to conclude. ◻

Proof. The classical \(q\)-analogue of this identity expresses \(s_\lambda\circ s_k(1,q)\) as polynomial in \(q\)-binomials and is proven in [62]. The \(q\)-binomials are all centered around the same unimodal peak. Homogenise the original formula to obtain an expression for \(s_\lambda\circ s_k(t,q)\), then set \(t=q^{-1}\) to conclude. ◻

Proof. The result follows from repeated applications of the Clebsch–Gordan rule \[[a][b] = [a+b-1] + [a+b-3] + \cdots + [|a-b|+1].\] This is done e.g. in [8] for the \(q\)-analogue version of the result. The proof of the quantum version is similar. ◻

Proof. Let \(n=|\mu|\) and \(\ell=\ell(\mu)-1\). We use the identity \(s_n\circ s_m(q,q^{-1}) = \genfrac{[}{]}{0pt}{}{n+m}{n}\) together with 22 to write \[\begin{align} s_\mu\circ s_k&(q,q^{-1}) = \sum_{m=0}^k s_n\circ s_{k-m}(q,q^{-1}) \sum_{\underline{\nu}} \prod_{\substack{1 \leqslant i \leqslant\ell \\ 1 \leqslant j \leqslant n}} s_{P_j^i(\underline{\nu})} \circ s_{m_j(\nu^{(i)})} (q,q^{-1}) \\ &= \sum_{m=0}^k \sum_{b_0} a_{b_0}(n,k-m) \cdot [b_0] \sum_{\underline{\nu}} \prod_{\substack{1 \leqslant i \leqslant\ell \\ 1 \leqslant j \leqslant n}} \sum_{b_{i,j}} a_{b_{i,j}}(P_j^i(\underline{\nu}),m_j(\nu^{(i)})) \cdot [b_{i,j}] \\&= \sum_{m=0}^k \sum_{\mathbf{b}} a_{b_0}(n,k-m) \cdot [b_0] \sum_{\underline{\nu}} \prod_{\substack{1 \leqslant i \leqslant\ell \\ 1 \leqslant j \leqslant n}} a_{b_{i,j}}(P_j^i(\underline{\nu}),m_j(\nu^{(i)})) \cdot [b_{i,j}]\,. \end{align}\] Take the coefficient of \([r]\) in this expression. By the definition of \(\mathrm{CG}_k(\mathbf{b})\), we obtained the claimed formula. ◻

Proof of Theorem [thm:GL232in32L2]. Let \(n=|\mu|\) and \(\ell=\ell(\mu)-1\). By Theorem [plet32recursion], \(a_{\mu[k]}^{(nk-r,r)}=a_{nk-2r+1}(\mu,k)\) counts the number of tuples of KOH small witnesses \((T_0) \sqcup (T_{i,j})^{1 \leqslant i \leqslant\ell}_{1 \leqslant j \leqslant n}\) together with a sequence of integers which are a witness for the Clebsch–Gordan coefficient and which we also indexed similarly, \((t_0) \sqcup (t_{i,j})^{1 \leqslant i \leqslant\ell}_{1 \leqslant j \leqslant n}\). The tuples depend on a matrix of integers and an admissible configuration.

To encode an admissible configuration \(\underline{\nu}\), we consider the sequence of their transposes \(\alpha^{(1)}, \alpha^{(2)}, \ldots\) instead. We can recover \(m_j(\nu^{(i)})\) as \(\alpha_j^{(i)}-\alpha_{j+1}^{(i)}\). Our witness records these partitions as sequences of \(\ell\) terms, encoded in binary: \[\begin{gather} m\,;\, \alpha_1^{(1)}, \ldots, \alpha_1^{(\ell)}\,;\, b_0, T_0, t_{0}\,;\,\\ \alpha_2^{(1)}, \ldots, \alpha_2^{(\ell)}\,;\, b_{11}, \ldots, b_{\ell1}\,,\, T_{11},\ldots , T_{\ell1}\,,\, t_{11},\ldots , t_{\ell1}\,;\, \\ \alpha_3^{(1)}, \ldots, \alpha_3^{(\ell)}\,;\, b_{12}, \ldots, b_{\ell2}\,,\, T_{12},\ldots , T_{\ell2}\,,\, t_{12},\ldots , t_{\ell2}\,;\, \ldots \end{gather}\] Start by reading \(m\), storing \(\alpha_1^{(1)}, \ldots, \alpha_1^{(\ell)}\) for later, and \(b_0\), check that \(\alpha^{(\ell)}_j=0\) for each \(j\) for every row \(j\) we read. Check that \(T_0\) is a KOH small witness for \(a_{b_0}(n,k-m)=a^{((n(k-m)+b_0-1)/2,(n(k-m)-b_0+1)/2)}_{n[k-m]}\). Then read and store \(\alpha_2^{(1)}, \ldots, \alpha_2^{(\ell)}\,;\, b_{11}, \ldots, b_{\ell1}\) and check that \(\alpha_1^{(i)}\geqslant\alpha_2^{(i)}\) for every \(i=1,\ldots,\ell\). This is enough to compute \(P_1^i(\underline{\nu})\) and \(m_1(\nu^{(i)})\) for \(i=1,\ldots,\ell\) and check they are \(\geqslant 0\), remembering that in the computation of \(P\) we take \(\alpha^{(0)}_1=n\) and \(\alpha^{(0)}_i=0\) for \(i>1\). Check the validity of the KOH small witnesses \(T_{11}, \ldots, T_{\ell1}\). Check also that \(t_0, t_{11}, \ldots, t_{\ell1}\) satisfy the conditions of the first \(\ell+1\) elements of a witness of a Clebsch–Gordan coefficient (see Lemma [lem:q-int-product]). Now read and store \(\alpha_3^{(1)}, \ldots, \alpha_3^{(\ell)}\,;\, b_{12}, \ldots, b_{\ell2}\). This is enough to compute \(P_2^i(\underline{\nu})\) and \(m_2(\nu^{(i)})\) for \(i=1,\ldots,\ell\). Only now is it possible to forget \(\alpha_1^{(1)}, \ldots, \alpha_1^{(\ell)}\), and hence we need \(9\ell\) (fixed number) of counters just to keep track of the admissible configuration. The algorithm continues iterating the previous checks until the \(\ell\)’th row.

One needs another \(\ell\) counters to keep the partial sizes of the partitions \(\alpha^{(i)}\), and in the end check that the \(\alpha_j^{(i)}\) indeed do form an admissible configuration for condition (2) of Definition [de:AC]. All of these \(10\ell\) counters we have discussed are upper bounded by \(|\mu|\) and hence occupy log-space. They can be updated in polynomial time. The remaining checks have already been seen to be occupy at most \(\log^2\)-space and take at most poly-time. ◻

Proof. This follows from Theorem [thm:2-dim]. The coefficients involved in the linear recursion come from the coefficients in \(q^\bullet z^\bullet\) of the denominator of a simplified expression for \(A_\mu(z,q)\). These coefficients are at most polynomial, since the denominator only depends on \(\mu\), which is given and constant. ◻