8
$\begingroup$

Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is about a closely related but weaker problem:

Question: Is there a polynomial time algorithm which inputs an ASM $M$ of size $n$ and outputs an integer $k\in \{1,\ldots,a(n)\}$, such that the map $M\to k$ is bijective?

Note that the algorithm can use the product formula for the number of ASMs or any of its many variations and generalizations, so I am not asking for a new proof.

Example: To emphasize the difference, note that there is a simple polynomial time algorithm which takes a partition $\lambda$ of $n$ and outputs an integer $k\in \{1,\ldots,p(n)\}$. Namely, precompute all integers $p(n,m)$ of the numbers of partitions of $n$ with largest part $m$. This is easy to do using formulas $p(n,m) = p(n-m,1) + \ldots + p(n-m,m)$. Depending on $\lambda_1\in \{1,2,\ldots\}$, split the interval intro smaller intervals $\{1,\ldots,p(n,1)\}$, $\{p(n,1)+1,\ldots,p(n,1)+p(n,2)\}$, etc. Proceed recursively.

Note: One can show that such algorithm exists for the MacMahon box formula but the construction is somewhat technical, at least the one I found.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ You might be interested in the talk Greg Kuperberg gave at Jim Propp's 64th birthday conference: dept.math.lsa.umich.edu/~speyer/JIM/abstracts.html#Kuperberg. He is interested in developing a framework for expressing ideas like "there can be no bijective proof that the number of order n ASMs is the same as order n TSSCPPs." $\endgroup$
    – Sam Hopkins
    Commented Aug 28 at 19:58
  • $\begingroup$ I wonder whether this has been investigated in the literature on the complexity theory of the six vertex model, since ASMs are a special case. $\endgroup$
    – Gjergji Zaimi
    Commented Aug 28 at 21:36
  • $\begingroup$ Unsure if relevant for the question, but at the OEIS A005130 page there are two links to bijective proofs: Ilse Fischer and Matjaz Konvalinka, A bijective proof of the ASM theorem, Part I: the operator formula, Markus Fulmek, A statistics-respecting bijection between permutation matrices and descending plane partitions without special parts. See also Bijective proofs of alternating sign matrix theorems. $\endgroup$
    – Fabius Wiesner
    Commented Aug 28 at 21:37
  • $\begingroup$ @FabiusWiesner -- I studied these papers before and the answer is: they are relevant but not helpful. A bijective proof in [FK] of A=B via AC=BC does not give an efficient listing as in the question (Fulmek's paper is about something else). Thanks anyway. $\endgroup$
    – Igor Pak
    Commented Aug 29 at 0:10
  • 1
    $\begingroup$ @GjergjiZaimi I found the paper Complexity Classification Of The Six-Vertex Model by Jin-Yi Cai, Zhiguo Fu, Mingji Xia hard to understand, but I think they are saying that the special case of the six-vertex model relevant for ASM enumeration is $\#P$-hard (since all six "values" are nonzero, where I think the values should be the weights of the vertices, i.e. all $1$). Of course the special case one needs for this problem, where the relevant graphs are certain subsets of a square and the boundary conditions on the boundary of the square are restricted, might be easier. $\endgroup$
    – Will Sawin
    Commented Aug 29 at 17:16

0

Reset to default

You must log in to answer this question.