Why is HAMILTONIAN CYCLE so different from PERMANENT?

Question

A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such that $f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$. That is, it is possible to replace each variable $y_j$ of $g$ by a variable $x_i$ or a constant $0$ or $1$ so that the resulting polynomial coincides with $f$.

I am interested in (the reasons for) the difference between the permanent polynomial PER and the Hamiltonian cycle polynomial HAM: $$ \mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \ \mbox{and} \ \ \ \ \mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)} $$ where the first summation is over all permutations $h:[n]\to[n]$, and the second is only over all cyclic permutations $h:[n]\to[n]$.

Question: Why HAM is not a monotone projection PER? Or it still is?

I am not asking for proofs, just for intuitive reasons.

Motivation: the largest known monotone circuit lower bound for PER (proved by Razborov) remains "only" $n^{\Omega(\log n)}$. On the other hand, results of [Valiant](https://web.vu.lt/mif/s.jukna/boolean/valiant-completeness.pdf) imply that $$ \mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$} $$ where $$ \mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j} $$ with the summation is over all subsets $S\subseteq [n]$ of size $|S|=\sqrt{n}$. I myself couldn't get a "simple, direct" reduction form these general results, but [Alon and Boppana](https://web.vu.lt/mif/s.jukna/boolean/Alon-Boppana.pdf) claim (in Sect. 5) that already $m=25n^2$ is sufficient for this reduction.

But wait: it is well known that CLIQUE requires monotone circuits of size $2^{n^{\Omega(1)}}$ (first proved by Alon and Boppana using Razborov's method).

So, were HAM a monotone projection of PER, we would have $2^{n^{\Omega(1)}}$ lower bound also for PER.

Actually, why HAM is not even a non-monotone projection of PER? Over the boolean semiring, the former is NP-complete, while the latter is in P. But why? Where is a place where being cyclic for a permutation makes it so special?

P.S. One obvious difference could be: HAM covers [n] by just one (long) cycle, whereas PER can use may disjoint cycles for this. Thus, to project PER to HAM the hard direction seems to be: ensure that the absence of a Hamiltonian cycle implies the absence of any covering with disjoint cycles in the new graph. Is this the reason for HAM not being a projection of PER?

P.P.S. Actually, Valiant proved a more impressing result: every polynomial $f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$ with $c_u\in\{0,1\}$, whose coefficients $c_u$ are p-time computable, is a projection (not necessarily monotone if the algo is non-monotone) of HAM$_m$ for $m$ = poly$(n)$. PER also has this property, but only over fields of characteristic $\neq 2$. So, in this sense, HAM and PER are indeed "similar", unless we are not in GF(2) where, as Bruno remembered, PER turns to DETERMINANT, and is easy.

Answer 1

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone projections of polynomials with nonnegative coefficients lead to the Newton polytope of one being an extended formulation of the Newton polytope of the other, and then applying the recent lower bounds on extended formulations.

Let $f(x_1,\dotsc,x_n)$ and $g(y_1,\dotsc,y_m)$ be polynomials with nonnegative coefficients (as is the case here). Suppose that $f$ is a monotone projection of $g$ under the assignment $\pi$ (following the notation of the question). Under $\pi$, each monomial of $g$ gets mapped either to 0 (iff one of its variables gets mapped to 0) or to a monomial of $f$: there can't be any cancellations because of non-negativity.

Let $New(f)$ denote the Newton polytope of $f$, and similarly for $New(g)$.

Claim: there is an extended formulation for $New(f)$ in $\mathbb{R}^m$, using $\leq n+m$ variables, and a number of constraints that is at most $n+m$ plus the number of constraints defining $New(g)$.

Here's how: Let $e_1,\dotsc,e_m$ be the coordinates on $\mathbb{R}^m$ (in which $New(g)$ lives; viz., an integer point in $\mathbb{R}^m$ with coordinates $(e_1,\dotsc,e_m)$ corresponds to the monomial $y_1^{e_1} \dotsb y_m^{e_m}$). For those $i$ such that $\pi(y_i)=0$, intersect $New(g)$ with $\{e_i = 0\}$ (since only monomials that do not involve $y_i$ can contribute to the projection); this adds at most $m$ additional constraints. Let $P$ denote the resulting polytope. Then $\pi$ induces a linear map $L_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$, such that $L_{\pi}(P) = New(f)$. This last part follows from the lack of cancellations. Thus we get an extended formulation for $New(f)$ by taking $n+m$ variables, the constraints for $P$ on the $m$ variables, and the constraints defining $L_{\pi}$ (of which there are at most $n$, one for each $x_i$). QED Claim

Now take $f$ to be the $n$-th Hamilton cycle polynomial and $g$ to be the $m$-th permanent, and suppose that $f$ is a monotone projection of $g$. The Newton polytope of the permanent (and determinant, incidentally), is the cycle cover polytope. This polytope is easily described by the "edge" variables $e_{ij}$ and the $m$ equations stating that every vertex has degree exactly 2.

The Newton polytope of the Ham. Cycle polynomial is the Hamiltonian cycle polytope (surprise, surprise). But this polytope is the TSP polytope, which requires $2^{n^{\Omega(1)}}$ equations to describe any extended formulation of, which, when $m$ is subexponential, contradicts the small extended formulation given by the cycle cover polytope and $L_{\pi}$ as above.

(Note that this argument fails if $f$, $g$, or $\pi$ can have negative coefficients, as then there can be cancellations, so $L_{\pi}$ need not map onto $New(f)$.)

It's interesting to note that the geometry of these polytopes is closely related to the fact that matching is in $\mathsf{P}$ while Hamilton cycle is $\mathsf{NP}$-complete, but I think the above reasoning shows how the geometric structure here really can add something beyond that complexity classification.