Orbit-finite systems of linear equations

Consider the following decision problem, over the equality symmetry.

Input: an orbit-finite system of linear equations S over \mathbb Z_2

Decide: does S have a solution (not necessarily finitely-supported)?

Inspired by Eryk’s beautiful solution of this problem, we present another solution, using an amazing theorem from topological dynamics.

Example 1. The variables are pairs ab where a,b\in \atoms, a\neq b. The system is

    \[\set{ab+ba=1|a,b\in\atoms,a\neq b}.\]

This system has a solution: for each unordered  pair \set{a,b} assign the value 1 to exactly one of ab,ba. In other words, the solution is a choice function from {\atoms\choose 2}\to \atoms^{(2)}. There is no finitely supported solution.

It is clear (by a compactness argument) that a system S has a solution if and only if every finite subsystem of S has a solution. However, it is not clear how to verify whether this is the case.

Example 2. Consider the system

    \[\set{ab+bc+ca=1|\set{a,b,c}\in{\atoms\choose 3}}.\]

This system has a constant solution, mapping every variable to 1. One can prove  – this is an interesting challenge – that in every solution, the values of ab and ba are the same. In other words, the system

    \[\set{ab+bc+ca=1}\cup\set{12+21=0}\]

has no solution (where 12 and 21 are variables). However, the smallest subsystem of this system which has no solution seems to be quite large (we found one with 5 variables and 9 equations).

We posed the problem of decidability of a given system has a solution to Eryk. At 5 am the next morning, Eryk came up with a beautiful solution. His solution uses the following observations.

Lemma 1. An orbit-finite system of linear equations in the symmetry (\Rat,=) is also an orbit-finite system of linear equations in the symmetry (\Rat,\le).

This fact can be easily seen if one identifies orbit-finite sets with sets definable using quantifier-free formulas in the underlying relational structure. Then it is obvious that any set which is definable using quantifier-free formulas in (\Rat,=) is also definable in (\Rat,\le). Another proof is to observe that any single-orbit set in (\Rat,=) splits into several, but finitely many orbits in (\Rat,\le).

Lemma 2. In the symmetry (\Rat,\le), if a system S has some solution, then it has a solution which is equivariant, i.e., invariant under the action of the automorphism group \aut{\Rat,\le}.

(Note that passing to the symmetry (\Rat,\le) is crucial, due to Example 1.)

Finally, testing whether there is an equivariant solution of an orbit-finite system in the symmetry (\Rat,\le) is easy – simply test all (finitely many) possible equivariant valuations, and for each of them, test whether it is a solution. The running time of this algorithm is roughly 2^n where n is the number of orbits of the set of variables in the symmetry (\Rat,\le).

Eryk’s proof of Lemma 2 uses a very neat Ramsey argument. We will not present his proof here. Instead, we present an alternative proof, which uses the following result due to Pestov, which itself is proved using Ramsey’s theorem, but follows easily from a beautiful theorem from this paper of Kechris, Pestov and Todorcevic.

Theorem (Pestov, 98).  Every continuous action of the automorphism group \aut{\Rat,\le} on a compact space X has a fixpoint.

Recall that a continuous action of a group G on a topological space X is a continuous mapping G\times X\to X, denoted (g,x)\mapsto g\cdot x, with the property that (g\cdot h)\cdot x=g\cdot (h\cdot x) and 1\cdot x=x for all g,h\in G and x\in X.

\aut{\Rat,\le} inherits its topology from \Rat^\Rat with the product topology. [The product topology on X^Y (where X, Y are two sets) is given by specifying as a basic open set any set of the form U_f, where f is a fixed finite partial mapping f:Y\to X, and U_f is the set of mappings from Y to X extending f. If X is finite, then X^Y is a compact space, by Tychonoff’s theorem.]

We now show that Lemma 2 is an immediate consequence of the above result.

Proof of Lemma 2. Let \textrm{Var} denote the set of all variables of the system S. Consider the set of all valuations \textrm{Val}=\set{0,1}^\textrm{Var} of those variables. This set is a compact space by Tychonoff’s theorem. Moreover, the group \aut{\Rat,\le} acts on \textrm{Val} by renaming the names of the variables, i.e., for \pi\in\aut{\Rat,\le} and v\in\textrm{Val}, \pi\cdot v is the valuation which assigns to a variable x the value v(\pi\cdot x). It is easy to check that this action is continuous, as expected.

The set of solutions of S is its subset:

    \[\textrm{solutions}\subset\textrm{Val},\]

and it is easy to see that it is a closed subset. [This follows from the fact that a single equation e defines the set \textrm{Val}_e of valuations satisfying e, and this set is closed, as it is a finite positive boolean combination of conditions of the form x\neq i, where x is some variable and i\in\set{0,1}. Therefore \textrm{Val}_e is a finite positive boolean combination of complements of basic open sets, so a closed set. In turn, the set of solutions is equal to \bigcap_{e\in S}\textrm{Val}_e, so is an (infinite) intersection of closed sets, so a closed set.]

In effect, the set of solutions is a compact set, which is invariant under the action of \aut{\Rat,\le}, since the system S itself is invariant. Therefore, \aut{\Rat\le} acts continuously on the compact set of solutions. Hence, by the theorem above, there is a fixpoint r of this action, that is, an invariant solution!

 

 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>