Pith. sign in

REVIEW 3 major objections 4 minor 15 references

Classical counting functions from binomial coefficients to partition numbers fit in #L, and bounded-length plethysm coefficients admit poly-time log²-space verifiers.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 22:09 UTC pith:62CPCMCB

load-bearing objection A systematic, mostly convincing #L catalog with a genuinely new witness-compression technique; the headline GL2-plethysm containment is real but the #TISP half rests on a cited KOH-tree bijection that a referee should check rather than wave through. the 3 major comments →

arxiv 2607.15881 v1 pith:62CPCMCB submitted 2026-07-17 math.CO cs.CC

Counting in logarithmic space

\'Alvaro Guti\'errez , Christian Ikenmeyer , Greta Panova This is my paper
classification math.CO cs.CC MSC 05A1968Q1505-0405E1068R0511P81
keywords counting complexitylog-space#Lcombinatorial interpretationsplethysm coefficientsKronecker coefficientsstandard Young tableauxhook-length formula
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper's central claim is that a large collection of classical counting problems — binomial and multinomial coefficients, Catalan, Narayana, Stirling, Fibonacci, and Euler numbers, the partition function, and the number of standard Young tableaux of arbitrary shape — are computed by nondeterministic Turing machines that use only logarithmic space; these functions therefore lie in the class #L, a small subclass of #P. The authors supply an explicit toolkit: composition lemmas that turn products and determinants of #L functions into #L or GapL functions, and a p-adic valuation technique that converts rational product formulas (such as the hook-length formula) into #L-verifiable products. They then prove a sharper result for representation-theoretic multiplicities: Hermite coefficients — which are simultaneously GL2-plethysm coefficients and rectangular Kronecker coefficients — can be counted by a polynomial-time, log²-space verifier, and the same holds for GL2-plethysm coefficients with a bounded-length outer partition. A sympathetic reader should care because #P membership is too coarse to distinguish the many counting functions with polynomial-time algorithms; #L is a natural 'tiny witness' analogue, and the paper's machine constructions make the witness sets concrete.

Core claim

For every listed function, the paper constructs a verifier machine that reads the input in unary, reads a witness string once from left to right, and accepts exactly the intended set of objects (subsets, Dyck paths, domino sequences, ballot sequences, partitions, tableaux, or a compressed representation of them). The main technical novelty is the treatment of the hook-length formula: using Legendre's formula and p-adic valuations, the rational formula for #SYT(λ) is rewritten as a product over primes of p^{v_p(n!) - v_p(hooks)}, and each exponent is shown to be log-space computable, so the whole count is in #L even for unbounded shapes. The deepest result is the log²-space verifier for Hermi

What carries the argument

The central object is the verifier NL-machine — a deterministic log-space machine with a read-once, left-to-right witness tape — together with two composition theorems: one turns products ∏ f(g(x,i)) of #L functions into #L, and the other turns determinants of #L functions into GapL. For the plethysm results, the key object is the marked KOH tree, a rooted tree counting Hermite coefficients via a #P-interpretation from a companion paper; the authors compress it to a 'small KOH witness' of logarithmic depth (but polynomial size), whose defining conditions can be checked by a read-once poly-time log²-space verifier. The Kirillov–Reshetikhin/GOH formula then expresses bounded-length GL2-plethys

Load-bearing premise

The central results for Hermite coefficients (Theorem 6.3) and their bounded-length generalization (Theorem 1.1) depend on the correctness of the marked KOH tree bijection from a companion paper: if that bijection miscounts even one Hermite coefficient, the new log²-space verifier would count the wrong number of witnesses, and the plethysm conclusion would fall.

What would settle it

Compute a Hermite coefficient a^{(nk-r,r)}_{n[k]} for a small instance such as n=3, k=2, r=2 using the independent formula a = p_r(n×k)−p_{r−1}(n×k) (with p_r counting partitions in an n×k box), then compare with the number of small KOH witnesses of type (n,k,r) accepted by the paper's verifier machine. Any disagreement for any single tuple (n,k,r) disproves the claimed bijection and collapses Theorem 6.3. A full check requires implementing the verifier of §6.3 and enumerating small KOH witnesses on small inputs.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Every sequence satisfying a constant-term linear recurrence with FL-computable nonnegative coefficients — including Fibonacci numbers, factorials, and involutions — is in #L, giving explicit witness encodings for each.
  • The partition function is in #L and hence in FP, giving a direct counting-witness formulation for p(n) without relying on Euler's pentagonal theorem.
  • The number of standard Young tableaux of any shape is in #L, via p-adic valuations of the hook-length formula, and hence can be certified by a log-space verifier even though the shape has unbounded length.
  • Bounded-length GL2-plethysm coefficients are in GapL and have poly-time log²-space verifiers, moving a piece of two longstanding open problems (Stanley's Problems 9 and 10) from #P-coarse to a much smaller counting class.
  • Containment in #L implies containment in FP, so the paper yields new polynomial-time algorithms for these functions, with the caveat that the algorithms are non-constructive in the witness sense.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the KOH-tree bijection is correct, the log²-space verifier for Hermite coefficients could in principle be turned into an explicit algorithm for computing rectangular Kronecker coefficients in time roughly poly(n) with only log²(n) working space, a drastic improvement over current methods.
  • The p-adic valuation technique that places #SYT(λ) in #L suggests a general principle: any counting function with a product formula whose prime exponent functions are FL-computable sits in #L; this could apply to other rational formulas, such as plane partition counts or other hook-content specializations.
  • The paper's open questions point toward a conditional route to disproving #P-completeness of contingency-table counting and of plethysm coefficients for unbounded length: a positive #L or log^k-space answer would separate these problems from #P-complete ones under standard assumptions.
  • The log²-space verifier for bounded-length GL2-plethysm uses a fixed number of counters per tree level; a natural testable next step is to see whether the depth bound fails for unbounded length, which would explain why that case remains open and indicate which new compression ideas are needed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper develops a general toolkit for proving containment in the counting class #L and applies it to many classical enumerative, representation-theoretic, and number-theoretic functions. Its central new result is Theorem 1.1: for a fixed bound C on the length of the outer partition μ, the GL2-plethysm coefficients a^{(|μ|k−r,r)}_{μ[k]} belong to #TISP(poly(n), log² n) ∩ GapL. The proof reduces the bounded-length case to the Hermite coefficient case via Theorem 6.28, and the Hermite case is handled by constructing a polylog-space verifier for a compressed witness family ('small KOH witnesses') built from the marked KOH tree interpretation of [PPS26]. The paper also contains many smaller results, including #L containment for binomial/multinomial coefficients, Catalan and Stirling numbers, the partition function, q-binomial coefficients, SYT counts of unbounded shape, and several geometric and crystal-theoretic functions.

Significance. If the proofs are fully correct, the paper makes a substantial contribution: it provides a unified method for exhibiting log-space verifiable counting witnesses for a wide range of classical functions, and it obtains a non-trivial polylog-space verifier for a family of plethysm coefficients that contains the 'rectangular Kronecker/Hermite' cases. The constructive nature of the proofs is a clear strength, as are the explicit bounds on witness size and the many open problems that could lead to conditional separations. The main new containment, the #TISP(poly, log²) half of Theorem 1.1, is explicitly 'hinging' on the published marked KOH tree bijection of [PPS26]; this is a standard citation dependency, but it should be stated precisely, since a failure of that bijection would break the new containment. The paper is largely self-contained apart from that external result and a few standard cited formulas.

major comments (3)
  1. [§6.1, Proposition 6.12] This bijection between marked KOH trees and small KOH witnesses is the load-bearing step for Theorem 6.3 and hence for the #TISP half of Theorem 1.1. The proof is only a sketch. In the forward direction, conditions (5)–(9) are asserted to hold without showing how the compressed edge labels (j,x) interact with the extra term b(v↑↓j(v),x(v)+1) in condition (8), or why the recursive a(v) of (6.11) matches (6.7) for internal nodes, not just true leaves. In the reverse direction, the formulas for µ are stated but not verified to produce a partition satisfying the child-label equation (6.7). Please provide a complete, step-by-step proof (or a detailed appendix), since a gap here would invalidate the central new containment.
  2. [§5, Theorem 5.15] The proof of the unbounded-shape hook-length formula result is incomplete as written. The first use of Theorem 2.5 is said to give p^{v_p(n!)−v_p(∏ hooks)} in #L from the function (1^p)↦p, but that function is p, not p^E. The second application of Theorem 2.5 then multiplies over primes, but the factor needed is p^E, not p. A correct proof requires first constructing a #L witness for exponentiation (e.g., (1^p, 1^E)↦p^E via repeated multiplication) and then composing it with the FL-computable exponent E. This is likely fixable, but as written the proof does not establish the theorem.
  3. [§6.4, Theorem 6.21] The witness encoding for the functions c+(r) and c−(r) is described ambiguously and appears internally inconsistent. The text says the witness is 'w = d e_1 r_1, d e_2 r_2, ...' with e_j=1 if the j-th cell is in D, but then states 'Every time we read a symbol d we decrease R by k+1+j−i'. If d is a literal marker preceding every cell, this decrements R for every box, not just boxes in D; if d instead indicates membership in D, then e_j is redundant and the reading rule is misstated. Since Theorem 6.21 supplies the GapL half of Theorem 1.1 for bounded-length μ, please rewrite the encoding and the update rules precisely.
minor comments (4)
  1. [§2.6, Theorem 2.10] The proof claims that the extremal graph is a chain and that a chain has 2^{N−1} source–sink paths. A directed chain has exactly one source–sink path. The induction argument gives a loose upper bound of 2^N, which is enough for the theorem, but the 'extremal graph' claim should be corrected or removed.
  2. [§5, Lemma 5.14] The space bound is misjustified. The counter v is bounded by log_p(n!) = O(n log n), which as an integer requires O(log n) bits, not O(log² n). The statement 'O(n log n) = O(n²)' is also inaccurate (if n is the number of boxes, the input length is Θ(n)). The conclusion of the lemma is correct, but the justification should be fixed.
  3. [§3, Theorem 3.26] The description of the end of the witness is inconsistent: the machine is said to accept and stop when the pair (a,b) reaches (1,1), but later says 'The end of the witness should be (0,0)'. Please clarify the intended terminator of the witness.
  4. [§6.3, Proposition 6.18] The statement 'Storing n, k, and r requires O(log²(n+k+r)) space' is not right in itself; storing these three integers takes O(log(n+k+r)) bits. The log² bound comes from the per-level counters along a path of logarithmic depth. Please rephrase so the space accounting is clear.

Circularity Check

0 steps flagged

No circularity: the log^2-space verifier is an independent construction; the [PPS26] dependency is external, not a reduction of the target to its inputs.

full rationale

The main new result, Theorem 1.1, is proved by constructing an explicit poly-time O(log^2)-space verifier for `small KOH witnesses` (Definitions 6.6 and 6.10; Propositions 6.18 and 6.19). The number of accepting paths equals the number of marked KOH trees via the internal bijection in Proposition 6.12, and equals the Hermite coefficient only by invoking the published [PPS26] combinatorial interpretation. This is load-bearing and co-authored by Panova, so it is a self-citation, but it is not circular: [PPS26] is a parameter-free combinatorial bijection for the coefficients, not a prior instance of the complexity containment being proved, and this paper does not define the coefficient as the number of those trees by construction. The paper itself flags the dependency, saying in the introduction `Hinging on a combinatorial interpretation for these coefficients [PPS26]`, and the proof of Theorem 6.3 says `By [PPS26], these coefficients count the number of KOH trees`. This is a correctness/verification dependency, not a circular reduction. The GapL halves of Theorems 6.3 and 1.1 are independently supported by equation (6.2) and Corollary 5.4. Theorem 6.30 is explicitly conditional on [GOS+26, Conjecture 1.1] and is not used for the main theorem. All other #L claims are backed by explicit log-space verifiers from standard formulas (binomial coefficients, recurrences, hook-length formula, etc.). No equation in the paper reduces to its own input, and no fitted parameter is renamed as a prediction. Therefore the derivation chain is not circular.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 1 invented entities

The central claims rest on standard complexity-theoretic facts and on prior published combinatorial interpretations. No free parameters or ad-hoc fitted values appear. The main invented object, the small KOH witness, is directly tied to the KOH trees of [PPS26].

axioms (4)
  • standard math Standard definitions and closure properties of L, NL, #L, GapL, and log-space reductions (e.g., FL⊆#L, NL=coNL).
    Used throughout, e.g., in §2.3, §2.4, and Theorem 2.5.
  • domain assumption Determinant is complete for GapL (Allender-Ogihara and Valiant).
    Used in Theorem 2.6 and Theorem 3.24.
  • domain assumption Correctness of known combinatorial formulas: hook-length formula, Jacobi-Trudi, KOH formula, GOH formula, and the bijection between marked KOH trees and Hermite coefficients from [PPS26].
    These are invoked as black boxes in §3.18, §5.15, §6.1, and the proof of Theorem 6.3.
  • domain assumption The rational generating function results of [GOS+26] (co-authored by Gutiérrez) for fixed μ.
    Used only for Theorem 6.30, which is conditional on a conjecture.
invented entities (1)
  • small KOH witness independent evidence
    purpose: A compressed, logarithmically deep encoding of marked KOH trees that can be checked by a log²-space verifier.
    Proposition 6.12 gives a proven bijection between marked KOH trees and small KOH witnesses, so the new construct is tied to an existing, independently defined object.

pith-pipeline@v1.3.0-alltime-deepseek · 3027 in / 11871 out tokens · 506188 ms · 2026-08-01T22:09:45.490077+00:00 · methodology

0 comments
read the original abstract

We study the class $\#\mathsf{L}$ of functions counting accepting paths of non-deterministic log-space Turing machines and construct methods to prove containment in $\#\mathsf{L}$. We prove that a large number of classical combinatorial and number theoretic functions belong to this class: classical functions from enumerative combinatorics (multinomial coefficients, Catalan numbers, linear extensions of trees, Stirling numbers, etc), algebraic combinatorics (number of standard Young tableaux, etc), discrete geometry, number theoretic functions, representation theoretic multiplicities in a large class of cases. We show that $\mathrm{GL}_2$-plethysm coefficients of bounded length outer partition can be counted by log$^2$-space polytime verifiers. We pose numerous questions and conjectures on $\#\mathsf{L}$ containment and its generalizations, that suggest venues for conditionally disproving $\#\mathsf{P}$-completeness. While studying which combinatorial functions are in $\#\mathsf{P}$ provides a formal way of (dis)proving the existence of combinatorial interpretations, the lower class $\#\mathsf{L}$ serves as an analogue for functions computable in polynomial time.

Figures

Figures reproduced from arXiv: 2607.15881 by \'Alvaro Guti\'errez, Christian Ikenmeyer, Greta Panova.

Figure 1
Figure 1. Figure 1: A verifier NL machine: the input tape is of size n and read-only; the witness tape is of poly(n) size and left-to-right read-once only; the work tape is of log(n) size; the output is 1-bit. 2.2. On verifier NL machines. The “read-once, left-to-right” restriction on the witness tape of a verifier NL machine plays an important role in Theorem 2.1. A verifier NP machine can simply copy the witness onto the wo… view at source ↗
Figure 2
Figure 2. Figure 2: A machine over an arbitrary alphabet Σ, with a constant number c of work tapes, and in which the witness tape can be read a constant C of times. This machine can be simulated by the verifier NL machine of [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Left, a marked KOH tree of type (n, k, r) = (15, 7, 36). The marks are separated by a semicolon. The value of r is calculated as r = 8 − (12 + 5 + 32)/2 + (15 · 7)/2 = 36. Right, the corresponding small KOH witness. Note how sequences of edges labeled 1 are split up, and the values of a are only stored at true leaves, and instead of partitions µ only their length is stored at internal nodes. Note that in t… view at source ↗
Figure 4
Figure 4. Figure 4: Left, a small KOH witness. Right, its encoding. 6.3. The polylog space machine. Given 1 n 0 1k 0 1r on the input tape, we can read the encoding of a small KOH witness from left to right once and verify that it is a small KOH witness of type (n, k, r) using only logarithmic space, as follows. • While reading, we ensure the syntactic correctness of the string of symbols. For this, we store the number of open… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 6 linked inside Pith

  1. [5]

    arXiv:2412.15006. 40 Á. GUTIÉRREZ, C. IKENMEYER, AND G. PANOV A [HV95] Lane Hemaspaandra and Heribert Vollmer. The satanic notations: counting classes beyond #P and other definitional adventures.ACM SIGACT News, 26(1):2–13,

    arXiv

  2. [6]

    On the gradient of the coefficient of the characteristic polynomial

    [Ike25] Christian Ikenmeyer. On the gradient of the coefficient of the characteristic polynomial. arXiv:2511.04954,

    arXiv

  3. [12]

    Computational complexity in algebraic combinatorics.Current Developments in Mathematics, 2023(1):241–280,

    [Pan25a] Greta Panova. Computational complexity in algebraic combinatorics.Current Developments in Mathematics, 2023(1):241–280,

    2023

  4. [14]

    Signed combinatorial interpretations in algebraic combinatorics

    [PR24] Igor Pak and Colleen Robichaux. Signed combinatorial interpretations in algebraic combinatorics. arXiv:2406.13902,

    Pith/arXiv arXiv

  5. [1988]

    Online Turing machine simulator, 2012.https://turingmachinesimulator.com

    [Uga12] Martín Ugarte. Online Turing machine simulator, 2012.https://turingmachinesimulator.com. COUNTING IN LOGARITHMIC SPACE 41 [Val79a] Leslie Valiant. Completeness classes in algebra. InProceedings of the eleventh annual ACM symposium on Theory of Computing, pages 249–261,

    2012

  6. [1992]

    A geometric and gener- ating function approach to plethysm

    [GOS+26] Álvaro Gutiérrez, Rosa Orellana, Franco Saliola, Anne Schilling, and Mike Zabrocki. A geometric and gener- ating function approach to plethysm. arXiv:2511.02649,

    Pith/arXiv arXiv

  7. [1994]

    Which graph motif parameters count? In50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), pages 23–1

    [BCDI25] Markus Bläser, Radu Curticapean, Julian Dörfler, and Christian Ikenmeyer. Which graph motif parameters count? In50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), pages 23–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

    2025

  8. [1995]

    Plethysm is in #BQP

    [CHP+26] Matthias Christandl, Aram Harrow, Greta Panova, Pietro Posta, and Michael Walter. Plethysm is in #BQP. arXiv:2602.08441,

    Pith/arXiv arXiv

  9. [2004]

    Geometric complexity theory VII: Nonstandard quantum group for the plethysm problem

    [Mul07] Ketan Mulmuley. Geometric complexity theory VII: Nonstandard quantum group for the plethysm problem. arXiv:0709.0749,

    Pith/arXiv arXiv

  10. [2007]

    Geometric complexity theory VI: The flip via positivity

    [Mul10] Ketan Mulmuley. Geometric complexity theory VI: The flip via positivity. arXiv:0704.0229,

    Pith/arXiv arXiv

  11. [2010]

    Determinant: Combinatorics, algorithms, and complexity.Chicago Journal of Theoretical Computer Science, 1997(5), December

    [MV97] Meena Mahajan and V Vinay. Determinant: Combinatorics, algorithms, and complexity.Chicago Journal of Theoretical Computer Science, 1997(5), December

    1997

  12. [2017]

    Field-independent Kronecker-plethysm isomor- phisms

    [IOT25] Christian Ikenmeyer, Heidi Omar, and Dimitrios Tsintsilidas. Field-independent Kronecker-plethysm isomor- phisms. arXiv:2509.10069,

    Pith/arXiv arXiv

  13. [2024]

    Positivity of the symmetric group characters is as hard as the polynomial time hierarchy.International Mathematics Research Notices, 2024(10):8442–8458,

    [IPP24] Christian Ikenmeyer, Igor Pak, and Greta Panova. Positivity of the symmetric group characters is as hard as the polynomial time hierarchy.International Mathematics Research Notices, 2024(10):8442–8458,

    2024

  14. [2025]

    Polynomial time classical versus quantum algorithms for representation theoretic multiplicities

    [Pan25b] Greta Panova. Polynomial time classical versus quantum algorithms for representation theoretic multiplicities. arXiv:2502.20253,

    arXiv

  15. [2026]

    Functional closure properties of finiteN-weighted automata

    [DI24] Julian Dörfler and Christian Ikenmeyer. Functional closure properties of finiteN-weighted automata. In51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), pages 134–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

    2024