Combinatorial equation system with exponentially many equations in quadratic many variables

Question

A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of equations (formulated by Michael Engelhardt).

Let $1\leq i\leq n$, $v_i \in \{ 1,2\ldots ,n \}$ and $x_i \in \{ 0,1,\ldots ,c-1 \}$. We have variables $\omega_{v_i,v_j,x_i,x_j} \in \mathbb{C}$ (with $\omega_{v_j, v_i, x_j, x_i} = \omega_{v_i, v_j, x_i, x_j}$ and $\omega_{v_i, v_i, x_j, x_i} = 0$).

For a fixed $n$ and $c$, we ask whether there is a set of $\omega_{v_i,v_j,x_i,x_j}$ which solves the following set of equation for every value of the varibles $x_i$:

$$ \sum_{\sigma \in S_n} \prod_{j=1}^{n/2} \omega_{\sigma(2j-1), \sigma(2j), x_{\sigma(2j-1)}, x_{\sigma(2j)}} = \prod_{i=1}^{n-1} \delta_{x_i,x_{i+1} } $$

where $S_n$ is the symmetric group.

---

n=4, c=2: Find a set of $4^2 2^2=64$ values of $\omega_{v_i,v_j,x_i,x_j}$ which satisfying these $2^4=16$ equations:

• $x_1=0,x_2=0,x_3=0,x_4=0$:

$$\omega_{1,2,0,0} \omega_{3,4,0,0} + \omega_{1,2,0,0} \omega_{4,3,0,0} + \omega_{1,3,0,0} \omega_{2,4,0,0} + \omega_{1,3,0,0} \omega_{4,2,0,0} + \omega_{1,4,0,0} \omega_{2,3,0,0} +\omega_{1,4,0,0} \omega_{2,3,0,0} + \omega_{2,1,0,0} \omega_{3,4,0,0} + \omega_{2,1,0,0} \omega_{4,3,0,0} + \omega_{2,3,0,0} \omega_{1,4,0,0} + \omega_{2,3,0,0} \omega_{4,1,0,0} + \omega_{2,4,0,0} \omega_{1,3,0,0} + \omega_{2,4,0,0} \omega_{3,1,0,0} + \omega_{3,1,0,0} \omega_{2,4,0,0} + \omega_{3,1,0,0} \omega_{4,2,0,0} + \omega_{3,2,0,0} \omega_{1,4,0,0} + \omega_{3,2,0,0} \omega_{4,1,0,0} + \omega_{3,4,0,0} \omega_{1,2,0,0} + \omega_{3,4,0,0} \omega_{2,1,0,0} + \omega_{4,1,0,0} \omega_{2,3,0,0} + \omega_{4,1,0,0} \omega_{3,2,0,0} + \omega_{4,2,0,0} \omega_{1,3,0,0} + \omega_{4,2,0,0} \omega_{3,1,0,0} + \omega_{4,3,0,0} \omega_{1,2,0,0} + \omega_{4,3,0,0} \omega_{2,1,0,0} = 1 $$

Because of $\omega_{v_j, v_i, x_j, x_i} = \omega_{v_i, v_j, x_i, x_j}$ , it simplifies to

$$\omega_{1,2,0,0} \omega_{3,4,0,0} + \omega_{1,3,0,0} \omega_{2,4,0,0} + \omega_{1,4,0,0} \omega_{2,3,0,0} = \frac{1}{8} $$

• $x_1=1,x_2=0,x_3=0,x_4=0$: $$\omega_{1,2,1,0} \omega_{3,4,0,0} + \omega_{1,3,1,0} \omega_{2,4,0,0} + \omega_{1,4,1,0} \omega_{2,3,0,0} = 0 $$

• $x_1=0,x_2=1,x_3=0,x_4=0$: $$\omega_{1,2,0,1} \omega_{3,4,0,0} + \omega_{1,3,0,0} \omega_{2,4,1,0} + \omega_{1,4,0,0} \omega_{2,3,1,0} = 0 $$

• $x_1=1,x_2=1,x_3=0,x_4=0$: $$\omega_{1,2,1,1} \omega_{3,4,0,0} + \omega_{1,3,1,0} \omega_{2,4,1,0} + \omega_{1,4,1,0} \omega_{2,3,1,0} = 0 $$

$\ldots$

• $x_1=1,x_2=1,x_3=1,x_4=1$: $$\omega_{1,2,1,1} \omega_{3,4,1,1} + \omega_{1,3,1,1} \omega_{2,4,1,1} + \omega_{1,4,1,1} \omega_{2,3,1,1} = \frac{1}{8} $$

One solution is: $\omega_{1,2,0,0}=\omega_{3,4,0,0}=\omega_{1,3,1,1}=\omega_{2,4,1,1}=\frac{1}{\sqrt{8}}$ and all other $\omega_{v_i,v_j,x_i,x_j}=0$.

Another simple solution can be obtained (n=4,c=3).

---

Question 1: Does this set of equation have solutions other than $(n,c=2)$ and $(n=4,c=3)$?

It seems likely that the answer to this question is no, because

• For the special case of $\omega_{v_i,v_j,x_i,x_j} \in \mathbb{R_+}$, Ilya Bogdanov has proved that these are the only solutions, using graph theoretical methods.
• The number of equations that need to be fulfilled grow as $c^n$, while the number of free variables $\omega_{v_i,v_j,x_i,x_j}$ grow only as $c^2\frac{n(n-1)}{2}$.

Even through, no answer is known for any other case.

Question 2: Have you seen any similar or related equation systems or problem in general before?

Answer 1

My answer concerns Question 2. When I was dealing with the system for $n=4$ I noticed that we can split it as follows (unfortunately, I failed to obtain essential advances from this observation).

Let $m=3$ and $X$ be an $m$-dimensional complex linear space with a basis $e_1, \dots, e_m$. Let $X^*$ be the dual space of the space $X$ (that is, the space of all complex-valued linear functionals on $X$) with the basis $e^*_1, \dots, e^*_m$ which is dual to $e_1, \dots, e_m$, that is satisfying the condition $e^*_i(e^j)=\delta_{i,j}$ for each $1\le i,j\le m$. Given values $\omega_{X,Y,x,y}$ for each $1\le X<Y\le n$ and $1\le x,y\le d$, each coloring $c$ of $[n]$ into $d$ colors provides vectors $x(c)\in X$ and $x^*(c)\in X^*$ such that

$$x(c)=\omega_{12, c(1)c(2)}e_1+\omega_{13, c(1)c(3)}e_2+\omega_{14, c(1)c(4)}e_3,\tag{1}$$

$$x^*(c)=\omega_{34, c(3)c(4)}e^*_1+\omega_{24, c(2)c(4)}e^*_2+\omega_{23, c(2)c(3)}e^*_3, \tag{2}$$

and $x^*(c)(x(c))$ equals $1$, if $c$ is monochromatic, and equals $0$, otherwise.

A next step to solve the system can be to find necessary and sufficient conditions when a family $\{x(c): c:[n]\to [d] \}\subset X$ of vectors can be expressed in the form (1). A necessary condition is that for any natural $k$ and any two sequences $(c_1,\dots, c_k)$ and $(c’_1,\dots, c’_k)$ of colorings $[n]\to [d]$ such that for each $1\le Y\le n$ and $1\le x,y\le d$ holds $$|\{j: c_j(1)=x\mbox{ and } c_j(Y)=y\}|=|\{j: c’_j(1)=x\mbox{ and } c’_j(Y)=y\}| $$

we have $\sum_{j=1}^k x(c_j)=\sum_{j=1}^k x(c’_j)$.

A similar necessary condition is when a family $\{x^*(c): c:[n]\to [d] \}\subset X^*$ of vectors can be expressed in the form (2).

I don’t know whether these conditions are sufficient. On the other hand, maybe based already on these condition it can be proved that in some cases the initial system has no solutions.

I have a weak hope that for bigger $n$ we can similarly split the system using tensor products, but I’m not a specialist in this domain.

PS. I formulated the essence of the original problem on existance of graphs with a certain coloring inherited by perfect matchings with a hope that a specialist will read it and solve. Its graph theoretical formulation is only introductive, because in fact it is about matchings on a compete graph with possible zero edge weights. Then the graph-theoretical problem transforms into an algebraic one about an existence of solutions of a special system of polynomial equations. Its graph-theoretical origin only determines the system structure.

According to our conjecture we have to show that the system is solvable iff $d=2$ or $d=3$ and $n=4$. We already know the solvability for the mentioned $(n,d)$. Moreover, the existence of solutions only in very special cases is very expected because the system has exponentially many ($d^n$) equations but only quadratically many ($d^2n(n-1)/2$) variables.

Due to system origin from the family $\mathcal M$ of all perfect matchings on a complete graph, the system structure is relatively simple and highly symmetric. So I read “Symmetry”by Hermann Weyl and in its conclusion I found the following advice.

What we learn from our whole discussion and what has indeed become a guiding principle in modern mathematics is this lesson: Whenever you have to do with a structure-endowed entity $\Sigma$ try to determine its group of automorphisms, the group of those element-wise transformations which leave all structural relations undisturbed. You can expect to gain a deep insight into the constitution of $\Sigma$ in this way. After that you may start to investigate symmetric configurations of elements, i.e. configurations which are invariant under a certain subgroup of the group of all automorphisms; and it may be advisable, before looking for such configurations, to study the subgroups themselves, e.g. the subgroup of those automorphisms which leave one element fixed, or leave two distinct elements fixed, and investigate what discontinuous or finite subgroups there exist, and so forth. In the study of groups of transformations one does well to stress the mere structure of such a group.

Indeed, I found some transformations of the system variables which keep solutions, but not to many. I particular, I don’t know how to construct a symmetric solution of the system from a given one.

The structure of the system is the following. For each vertices $i<j$ of $\{1,\dots, n\}=[n]$ and colors $c_i,c_j\in\{1,\dots,d\}=[d]$ we have a variable $ij,c_ic_j$ whose value is a complex number and is a weight of an edge from $i$ to $j$, whose endpoint $i$ is colored by $c_i$ and endpoint $j$ is colored by $c_j$. There are $d^n$ vertex colorings $c:[n]\to [d]$. Each coloring $c$ determines a weight $c(PM)$ of each perfect mathching $PM\in\mathcal M$ as $c(PM)=\prod ij,c(i)c(j)$. The corresponding to $c$ equation of the system is $\sum{PM\in\mathcal M} c(PM)=\delta(c),$ where $\delta(c)=1$, if $c$ is monochromatic, and $\delta(c)=0$, otherwise.

In some special cases we can say more. Recall that all presently known solutions are monochromatic, that is all their non-zero edge weights $ij,c_ic_j $ correspond to monochromatic edges, that is for $c_i=c_j$. I expect that by means of graph theory I can prove that if the system has a monochromatic solution then $d\le (n-1)(n-2)/2$, which fits the conjecture for $n=4$. But I guess this result has no physical value, so I didn’t write its proof or tried hard to improve this bound.

Another special (but still unsolved) case is $n=4$. In this case we can split the system in the following sense. If we fix values $ij,c_ic_j$ for all $i<j\ne 4$ then we obtain a linear system $Ax=b$ for the values $i4,c_ic_4$ for all $i<4$. It is well-known that this system has no solutions iff $\operatorname{rank} A<\operatorname{rank} A|b$, so we have to verify this condition for each choice of values $ij,c_ic_j$ for all $i<j\ne 4$.

As a visual aid, we present a system for $d=2$. For the sake of simplicity we restrict ourselves for monochromatic case, when $c_i=c_j$ for each $ij,c_ic_j$, which we therefore denote by $ij,c$. We have ${n\choose 2}d=12$ variables

12,1 13,1 14,1 22,1 23,1 24,1 12,2 13,2 14,2 22,2 23,2 24,2

When we fix values of $ij,c$ for $j\ne 4$, we can describe the structure of the system $Ax=b$ by the following table

      14,1 24,1 34,1 14,2 24,2 34,2
1111  23,1 13,1 12,1                1
1122                           12,1 
1212                      13,1      
1221  23,2                          
2112                 23,1           
2121       13,2                     
2211            12,2                
2222                 23,2 13,2 12,2 1

The first column lists the colorings of $[n]=[4]$ into $d=2$ colors, determining the respective row of the matrix $A$. There are $d^4=16$ colorings of $[4]$ into $2$ colors, but the monochromaticity condition implies that all rows corresponding to colorings containing monochromatic sets of odd size are zero, so we skipped these rows. All not listed entries of table are zeroes. The last column corresponds to the vector $b$.

Thus, for instance, the first three equations of the system $Ax=b$ are:

$23,1\cdot 14,1+13,1\cdot 24,1+12,1\cdot 34,1=1$

$12,1\cdot 34,2 =0$

$13,1\cdot 24,2 =0$.

PPS. I still think that if we find a way to essentially use the symmetry of the system then it can be enlightening. So maybe a book “Symmetry in Physics” (Macmillan, 1979) by J.P. Elliott and P.G. Dawber can be helpful.