# Combinatorial equation system with exponentially many equations in quadratic many variables

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?

• The notation is strange. If I said $X_i$ is a variable, and $\omega_{X_i}$ is a variable, then literally what that means is that for each value of $X_i$, I have a separate variable $\omega_{X_i}$. If $X_i = 5$, then there is a variable $\omega_5$. If $X_i = -3$, then there is a variable $\omega_{-3}$. This cannot possibly be what you intended. If you clarify this, I think the whole question might be easier to read. Also: Please consider summing over $\sigma \in S_n$, the symmetric group, and writing $\sigma(j)$ instead of $P^{(m)}(j)$. ... – Zach Teitler Apr 20 at 7:29
• ... I don't completely understand why you need $\omega_{X_i,X_j,x_i,x_j}$. Could you just write $\omega_{i,j}$ and have the same information? Or not? I'm sorry to ask such stupid questions, but I just find the notation confusing. Would you be willing to write out the full system of equations for a small case, say $n=c=2$? – Zach Teitler Apr 20 at 7:31
• @ZachTeitler Your understanding of variables notation is correct. An example of a full system (for $n=4$ and $c=2$) on which you ask is provided in this question. – Alex Ravsky Apr 20 at 17:27
• @ZachTeitler Thanks for your comment, i updated the question now, improved the notation according to your suggestion, thank you! Also added the n=4,c=2 example following exactly the notation used here. Does that help? – Mario Krenn Apr 21 at 8:30

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 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 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.