and such that there are exactly $t$ identical rows with index $< \ell_2$ in $N(\pi' \circ \pi)[x'](\pi' \circ \pi)[y']$. In the equation above we used that $g_{[y]}(\pi') \circ g_{[y]}(\pi) = g_{[y]}(\pi' \circ \pi)$, because $g_{[y]}$ is a group homomorphism. Now we see that $\ell_2 = \ell$ because the row $(N[x'][y'])_{k-}$ is always mapped to the respective $(t+1)$-st row of the same kind in each matrix. This is what we had to show.
Similarly one can see that $h^{-1}_{[x]}(\pi) = h_{[x]}(\pi^{-1})$. This shows that $h_{[x]}$ is a group homomorphism.

It remains to prove: For every $[x'] \in \Omega_{[x]}$ and each $[y'] \in \Cc[x']$, it holds $h_{[x]}(\pi)(J_{[x'][y']}) = J_{\pi[x']\pi[y']}$. This is true by the definition of $h_{[x]}$ and Lemma <ref>. The fact that $(N\pi[x']\pi[y'])_{h_{[x]}(\pi)(j),g_{[x]}(\pi)(i)} = N[x'][y']_{j,i}$ for each $[x'] \in \Omega_{[x]}$, $[y'] \in \Cc[x']$, $\pi \in \Stab_G(\mu)$, $i \in I_{[x']}$, and $j \in J_{[x'][y']}$ is also true by definition.

This finishes the construction and correctness proof of the matrices $N[x'][y']$ for all $[x'] \in \Omega_{[x]}$ and $[y'] \in \Cc[x']$ and of the associated homomorphism $h_{[x]} : \Stab_G(\mu) \lra J_{\Omega_{[x]}}$. Items (b) and (d) of the inductive step are thus covered. To complete the inductive step we still have to define the matrices $M[x']$ for all $[x'] \in \Omega_{[x]}$.

*Definition of the M-matrices
Let $[x'] \in \Omega_{[x]}$. Informally, $M[x']$ is obtained by collecting all the rows of the matrices $(N[x'][y'] \cdot M[y'])$, for all $[y'] \in \Cc[x']$, and putting them together as the rows of $M[x']$. Formally, let

\[
I_{[x']} := \biguplus_{[y'] \in \Cc[x']} J_{[x'][y']}.
\]

Note that by construction, the sets $J_{[x'][y']}, J_{[x'][y'']}$ are pairwise disjoint if $[y'] \neq [y'']$. Then the rows of $M[x'] \in \bbF_2^{I_{[x']} \times E}$ are defined as follows: For $[y'] \in \Cc[x']$ and $(i,[x'],[y']) \in J_{[x'][y']}$, we let

\[
M[x']_{(i,[x'],[y']),-} := (N[x'][y'] \cdot M[y'])_{(i,[x'],[y']),-}.
\]

This matrix has the desired kernel:

For every $[x'] \in \Omega_{[x]}$, the matrix $M[x']$ defined as above satisfies:

\[
\Ker(M[x']) = \Stab_E(x').
\]

By definition of $M[x']$, a vector $\mathbf{v} \in \bbF_2^E$ is in $\Ker(M[x'])$ if and only if
$\mathbf{v} \in \Ker(N[x'][y'] \cdot M[y'])$ for all $[y'] \in \Cc[x']$. By Lemma <ref>, this is the case iff $\mathbf{v} \in \Stab_E([y'] \cap x')$, for all $[y'] \in \Cc[x']$. That is to say,

\[
\mathbf{v} \in \bigcap_{[y'] \in \Cc[x']} \Stab_E([y'] \cap x').
\]

This is equivalent to $\mathbf{v} \in \Stab_E(x')$ because $x' = \bigcup_{[y'] \in \Cc[x']} ([y'] \cap x')$ (see Proposition <ref>).

Finally, we have to provide the homomorphism $g_{[x]}: \Stab_G(\mu) \lra \Sym(I_{\Omega_{[x]}})$, where $I_{\Omega_{[x]}} = \biguplus_{[x'] \in \Omega_{[x]}} I_{[x']}$.
Note that $I_{\Omega_{[x]}} = J_{\Omega_{[x]}}$ by definition of the index sets $I_{[x']}$.

Therefore we can simply set $g_{[x]} := h_{[x]}$. This homomorphism indeed satisfies the desired properties:

For each $[x'] \in \Omega_{[x]}$ and each $\pi \in \Stab_G(\mu)$, it holds $g_{[x]}(\pi)(I_{[x']}) = I_{\pi[x']}$. Furthermore, $M\pi[x'] = (g_{[x]}(\pi),\pi)M[x']$.

Let $\pi \in \Stab_G(\mu)$ and $[x'] \in \Omega_{[x]}$. Due to Lemma <ref>, $\pi[x']$ is again a $\sim$-class in $\tc(\mu)$. Because $\pi$ extends to an automorphism of $\mu$, it also holds

\[
\pi(\Cc[x']) = \{ \pi[y'] \mid [y'] \in \Cc[x']  \} = \Cc(\pi[x']).
\]

Hence, by Lemma <ref>, $h_{[x]}(\pi)$ maps the set $I_{[x']} = \biguplus_{[y'] \in \Cc[x']} J_{[x'][y']}$ to the set $I_{\pi[x']} = \biguplus_{\pi[y'] \in \Cc\pi[x']} J_{\pi[x']\pi[y']}$.
It remains to show $(M\pi[x'])_{g_{[x]}(\pi)(i),\pi(e)} = M[x']_{i,e}$ for each $i = (j,[x'],[y']) \in I_{[x']}$, and $e \in E$.
By definition of the $M$-matrices, we have:

\begin{align*}
(M\pi[x'])_{g_{[x]}(\pi)(i),\pi(e)} = (M\pi[x'])_{(j',\pi[x'],\pi[y']),\pi(e)} &=  (N\pi[x']\pi[y'] \cdot M\pi[y'])_{(j',\pi[x'],\pi[y']),\pi(e)}\\
&= (N[x'][y'] \cdot M[y'])_{(j,[x'],[y']),e}\\
&= M[x']_{i,e}.
\end{align*}

Here, $j'$ is such that $(j',\pi[x'],\pi[y']) = g_{[x]}(\pi)(j,[x'],[y']) = h_{[x]}(\pi)(j,[x'],[y'])$. The final equality holds for the following reason: $(N\pi[x']\pi[y'] \cdot M\pi[y'])_{(j',\pi[x'],\pi[y']),\pi(e)}$ is the product of row $j'$ of $N\pi[x']\pi[y']$ with column $\pi(e)$ of $M\pi[y']$. The lemma we are currently proving already holds for $M[y']$ by induction hypothesis, so $(M\pi[y'])_{-\pi(e)} = g_{[y']}(\pi)(M[y']_{-e})$. Also, we have $(N\pi[x']\pi[y'])_{j',-} = g_{[y']}(\pi)((N[x'][y'])_{j,-})$ by Lemma <ref>. Then Proposition <ref> tells us that $(N\pi[x']\pi[y'])_{j',-} \cdot (M\pi[y'])_{-,\pi(e)} = (N[x'][y'])_{j,-}\cdot (M[y'])_{-e}$ because these vector products are really the same sums of products, where the summands are just reordered by $g_{[y']}(\pi)$.

§.§ Construction of the circuit

We construct the circuit $\widehat{C}(\mu) = (V_C,E_C)$ from the matrices that we have defined in the previous section.
The set of gates is

\[
V_C := \biguplus_{\stackrel{x \in \tc(\mu)}{(i,[x],[y]) \in I_{[x]}} } \mathbf{g}_{i,[x],[y]}.
\]

So every row of any of the $M[x]$-matrices with index $(i,[x],[y])$ will correspond to a gate $\mathbf{g}_{i,[x],[y]}$. The construction will ensure that

\[
\chi(\Xx(\mathbf{g}_{i,[x],[y]}))= M[x]_{(i,[x],[y]),-}^T.
\]

Thus, the gate will compute the XOR over precisely the input gates labelled with edges that have a $1$-entry in the row $M[x]_{(i,[x],[y]),-}$.

For every atom $x \in \tc(\mu)$, we have $I_{[x]} = \{ [x] \}$. We define the corresponding gate $\mathbf{g}_{[x]}$ as an input gate of $\widehat{C}(\mu)$ with $\ell(\mathbf{g}_{[x]}) = e$, where $e \in E$ is the edge such that $[x] \subseteq \{e_0,e_1\}$.

If $x \in \tc(\mu)$ is not an atom, then for every $(i,[x],[y]) \in I_{[x]}$, $\mathbf{g}_{i,[x],[y]}$ is an internal gate that has incoming wires from exactly those gates $\mathbf{g}_{j,[y],[z]}$ such that the matrix $N[x][y]$ has a $1$-entry in row $(i,[x],[y])$ and column $(j,[y],[z])$. Note that $(j,[y],[z]) \in I_{[y]}$, so $[z] \in \Cc[y]$. Formally, the set of children of $\mathbf{g}_{i,[x],[y]}$ is:

\[
\mathbf{g}_{i,[x],[y]}E_C := \{ \mathbf{g}_{j,[y],[z]}  \mid (j,[y],[z]) \in I_{[y]}, (N[x][y])_{(i,[x],[y]),(j,[y],[z])} = 1 \}.
\]

It remains to specify the root of $\widehat{C}(\mu)$. Consider the matrix $M[\mu]$. Let $(i,[\mu],[y])$ be a row of $M[\mu]$ with a maximum number of one-entries. We define the root $r$ to be the gate $\mathbf{g}_{i,[\mu],[y]}$.

The figure below shows the matrices and XOR-gates for an object $x$ consisting of two connected components $[y] \cap x$ and $[y'] \cap x$. The matrices $N[x][y]$ and $N[x][y']$ have just one row each in this example, and we are assuming that $\Cc[y] = \{[z]\}$ and $\Cc[y'] = \{[z']\}$, and that $M[y] = N[y][z] \cdot M[z]$ has three rows and $M[y'] = N[y'][z'] \cdot M[z']$ has two rows.

[radius=1.5,fill=yellow, opacity=0.3] (1.3+7,-6) circle;
[radius=1.5,fill=red, opacity=0.3] (1.5+10.5,-6) circle;

[radius=0.5,fill=yellow, opacity=0.3] (0.5,-6) circle;
[radius=0.5,fill=red, opacity=0.3] (5.5,-6) circle;

[radius=0.3,fill=yellow, opacity=0.3] (1.85,1.4) circle;
[radius=0.3,fill=red, opacity=0.3] (2.9,1.4) circle;

at (2,2) $x = \{\underbrace{ y_1, y_2}, \underbrace{y'_1, y'_2}  \}$;
at (1.85,1.4) $[y]$;
at (2.9,1.4) $[y']$;

(Mx) at (2,0) $M[x] = \left[   \begin{array}{c} (N[x][y] \cdot M[y]) \\ (N[x][y']\cdot M[y'])            \end{array}  \right] $;
(My) at (0.5,-2*3) $M[y]$;
(MyPrime) at (5.5,-2*3) $M[y']$;

(Nxy) at (1,-2*1.5) $N[x][y] = \left[ \begin{array}{ccc} 1 & 1& 1  \end{array} \right]$;
(NxyPrime) at (5,-2*1.5) $N[x][y'] = \left[ \begin{array}{cc} 1 & 0 \end{array}  \right]$;

(xyGate) at (1.5+7,0.2) $\oplus \mathbf{g}_{1,[x],[y]}$;
(xyPrimeGate) at (1.5+9,-0.3) $\oplus \mathbf{g}_{1,[x],[y']}$;

(yGate1) at (1.5+6,-2*3) $\oplus \mathbf{g}_{1,[y],[z]}$;
(yGate2)at (1.5+7,-2*2.5) $\oplus \mathbf{g}_{2,[y],[z]}$;
(yGate3) at (1.5+8,-2*3) $\oplus \mathbf{g}_{3,[y],[z]}$;
(yPrimeGate) at (1.5+11,-2*2.5) $\oplus \mathbf{g}_{1,[y'],[z']}$;
at (13,-2*3) $\oplus \mathbf{g}_{2,[y'],[z']}$;

[->] (xyGate.south)– (yGate1);
[->] (xyGate.south)– (yGate2);
[->] (xyGate.south)– (yGate3);

[->] (xyPrimeGate.south)– (yPrimeGate.west);

[dashed] (Mx.south)– (Nxy);
[dashed] (Mx.south)– (NxyPrime);
[dashed]  (Nxy.south)– (My);
[dashed] (NxyPrime.south)– (MyPrime);

Example showing how the XOR-gates are connected according to the $N$-matrices.

Now we prove that $\widehat{C}(\mu)$ has the desired properties.

Every $\pi \in \Stab_G(\mu)$ extends to an automorphism of the circuit $\widehat{C}(\mu)$, that is:

\[
\Stab_G(\mu) \leq \Stab_G(\widehat{C}(\mu)).
\]

Let $\pi \in \Stab_G(\mu)$. We claim that the following mapping $\sigma : V_C \lra V_C$ is an automorphism of $\widehat{C}(\mu)$ that $\pi$ extends to. We let

\[
\sigma(\mathbf{g}_{i,[x],[y]}) := \mathbf{g}_{g_{[x]}(\pi)(i,[x],[y])},
\]

where $g_{[x]} : \Stab_G(\mu) \lra \Sym(I_{\Omega_{[x]}})$ is the group homomorphism for $\Omega_{[x]}$ from the construction of the matrices in the previous subsection. We have to show three things about $\sigma$. Firstly, that $\sigma \in \Sym(V_C)$. Secondly, that $\sigma$ maps wires to wires and non-wires to non-wires of $\widehat{C}(\mu)$. Finally, that for every input gate $\mathbf{g}_{[x]}$ it holds: $\ell(\sigma(\mathbf{g}_{[x]})) = \pi(\ell(\mathbf{g}_{[x]}))$. This last statement actually follows directly from the definition of $g_{[x]}$ for atoms $x \in \tc(\mu)$: If $[x] \subseteq \{e_0,e_1\}$, then $\pi(\ell(\mathbf{g}_{[x]})) = \pi(e)$, and $g_{[x]}(\pi)([x]) = \pi[x] \subseteq \{\pi(e_0), \pi(e_1)\}$, so $\ell(\sigma(\mathbf{g}_{[x]})) = \pi(e)$.

The fact that $\sigma \in \Sym(V_C)$ follows because for each orbit $\Omega_{[x]}$, we have that $g_{[x]}(\pi) \in \Sym(I_{\Omega_{[x]}})$, and the set of gates $V_C$ can be partitioned into these orbits so that each part has the form $\{ \mathbf{g}_{i,[x'],[y]} \mid (i,[x'],[y]) \in I_{\Omega_{[x]}} \}$, for some orbit $\Omega_{[x]}$.

It remains to prove that $\sigma$ preserves the wire structure of the circuit. For any two gates $\mathbf{g}_{i,[x],[y]}, \mathbf{g}_{j,[x'],[y']}$, we have

\[
(\mathbf{g}_{i,[x],[y]}, \mathbf{g}_{j,[x'],[y']}) \in E_C \text{ if and only if } [y] = [x'] \text{ and }(N[x][y])_{(i,[x],[y]),(j,[y],[y'])} = 1.
\]

The latter equation holds if and only if

\[
(N\pi[x]\pi[y])_{h_{[x]}(\pi)(i,[x],[y]),g_{[y]}(\pi)(j,[y],[y'])}  = 1.
\]

This is true by Lemma <ref>. If $[x'] = [y]$, then we have $\sigma(\mathbf{g}_{j,[x'],[y']}) = \mathbf{g}_{g_{[y]}(\pi)(j,[y],[y'])}$. Furthermore, it holds $\sigma(\mathbf{g}_{i,[x],[y]}) = \mathbf{g}_{g_{[x]}(\pi)(i,[x],[y])}$. By the definition in the previous section, $g_{[x]} = h_{[x]}$, and it holds that $g_{[x]}(\pi)(i,[x],[y])$ is of the form $(\ell, \pi[x],\pi[y])$, and $g_{[y]}(\pi)(j,[y],[y'])$ is of the form $(\ell', \pi[y],\pi[y'])$, so these are indeed row- and column-indices of the matrix $N\pi[x]\pi[y]$. So altogether, the above equation is equivalent to:
(\sigma \mathbf{g}_{i,[x],[y]}, \sigma \mathbf{g}_{j,[x'],[y']}) \in E_C.

As in the case of the circuit $C(\mu)$, this lemma implies that the orbit-size of $\widehat{C}(\mu)$ cannot be greater than the orbit-size of $\mu$ (here, $\Orb_G(\mu)$ again refers to the $\Aut(G)$-orbit and not to the $\Stab_G(\mu)$-orbit, which would be pointless).

\[
|\Orb_G(\widehat{C}(\mu))| \leq |\Orb_G(\mu)|.
\]

Analogous to the proof of Corollary <ref>.

For every internal gate $\mathbf{g} := \mathbf{g}_{i,[x],[y]} \in V_C$ it holds:

\[
\Xx(\mathbf{g}) = \chi^{-1}(M[x]_{(i,[x],[y]),-}^T).
\]

By induction. For each input gate $\mathbf{g}_{[x]}$ with $[x] \subseteq \{e_0,e_1\}$ we have $\Xx(\mathbf{g}_{[x]}) = \{ e\}$.

Now let $\mathbf{g} = \mathbf{g}_{i,[x],[y]}$ be an internal gate. By definition of $\widehat{C}(\mu)$, it holds

\[
\mathbf{g}E_C = \{ \mathbf{g}_{j,[y],[z]}  \mid (j,[y],[z]) \in I_{[y]}, (N[x][y])_{(i,[x],[y]),(j,[y],[z])} = 1 \}.
\]

\begin{align*}
\Xx(\mathbf{g}) &= \bigtriangleup_{ \stackrel{(j,[y],[z]) \in I_{[y]},} {(N[x][y])_{(i,[x],[y]),(j,[y],[z])} = 1 }} \Xx(\mathbf{g}_{j,[y],[z]})\\
&= \chi^{-1}\Big( \sum_{ \stackrel{(j,[y],[z]) \in I_{[y]},} {(N[x][y])_{(i,[x],[y]),(j,[y],[z])} = 1 }} \chi(\Xx(\mathbf{g}_{j,[y],[z]})) \  \  \mod 2 \Big)\\
&= \chi^{-1}(((N[x][y])_{(i,[x],[y]),-} \cdot M[y])^T).
\end{align*}

The last step uses the induction hypothesis and the fact that $I_{[y]}$ is the row-index-set of $M[y]$. By the definition of the matrix $M[x]$ in the previous subsection, we have $(N[x][y])_{(i,[x],[y]),-} \cdot M[y] = M[x]_{(i,[x],[y]),-}$. This finishes the proof.

The fan-in dimension of $\widehat{C}(\mu)$ is at most $\log (\maxOrb_E(\mu))$.

Consider any gate $\mathbf{g} := \mathbf{g}_{i,[x],[y]} \in V_C$. By definition of $\widehat{C}(\mu)$, the children of $\mathbf{g}$ are

\[
\mathbf{g}E_C = \{ \mathbf{g}_{j,[y],[z]}  \mid (j,[y],[z]) \in I_{[y]}, (N[x][y])_{(i,[x],[y]),(j,[y],[z])} = 1 \}.
\]

By Lemma <ref>, we have for each of these children:

\[
\Xx(\mathbf{g}_{j,[y],[z]}) = \chi^{-1}(M[y]_{(j,[y],[z]),-}).
\]

Thus, the gate matrix $M\mathbf{g} \in \bbF_2^{\mathbf{g}E_C \times E}$ is a submatrix of $M[y]$: It consists precisely of those rows $(j,[y],[z])$ of $M[y]$ such that $(N[x][y])_{(i,[x],[y]),(j,[y],[z])} = 1$. Therefore,
$\rk(M\mathbf{g}) \leq \rk (M[y]).$
Now we can argue as in the proof of Lemma <ref> in order to bound $\rk (M[y])$. Using the Orbit-Stabiliser Theorem, we obtain again:

\[
\log(\maxOrb_E(\mu)) \geq |E| - \dim \Stab_E(y).
\]

By Lemma <ref>, we have $\Ker(M[y]) = \Stab_E(y)$. Therefore, with the Rank Theorem we obtain:

\[
\rk(M[y]) = |E| - \dim \ \Stab_E(y) \leq \log (\maxOrb_E(\mu)).
\]

In total, we have $\rk(M\mathbf{g}) \leq  \log (\maxOrb_E(\mu))$. Since $\mathbf{g} \in V_C$ was arbitrary, this is a bound on the fan-in dimension of $\widehat{C}(\mu)$.

For the root $r$ of $\widehat{C}(\mu)$, it holds

\[
| \Xx(r) | \geq \frac{|\sup_{\CFI}(\mu)|}{\log (\maxOrb_E(\mu))}.
\]

By definition of $\widehat{C}(\mu)$, we have $r = \mathbf{g}_{i,[\mu],[y]}$ for some $(i,[\mu],[y]) \in I_{[\mu]}$ such that $M[\mu]_{(i,[\mu],[y]),-}$ is a row with a maximum number of $1$-entries. We have

\[
\Xx(r) = \chi^{-1}(M[\mu]_{(i,[\mu],[y]),-}^T)
\]

according to Lemma <ref>. Therefore, we have to show that $M[\mu]$ has a row with at least $\frac{|\sup_{\CFI}(\mu)|}{\log (\maxOrb_E(\mu))}$ many $1$-entries.

Claim: For every $e \in \sup_{\CFI}(\mu)$ there is a row of $M[\mu]$ which is non-zero in column $e$.

Proof of claim: Since $\sup_{\CFI}(\mu)$ is the minimal CFI-support of $\mu$, it holds that $\chi(e) \notin \Stab_E(\mu)$. Otherwise there is a smaller support not containing $e$. Suppose for a contradiction that all rows of $M[\mu]$ are zero in column $e$. Then $\chi(e) \in \Ker(M[\mu])$. But this contradicts the fact that $\Ker(M[\mu]) = \Stab_E(\mu)$ (Lemma <ref>). This proves the claim.

Now take a subset $\Bb$ of the rows of $M[\mu]$ that forms a basis of the row space of $M[\mu]$. By Lemma <ref>, we have $|\Bb| \leq \log (\maxOrb_E(\mu))$. For every $e \in E$ such that some row of $M[\mu]$ is non-zero in column $e$, there must also be a row in $\Bb$ that is non-zero in column $e$ (else $\Bb$ does not generate the whole row space). So by the claim and by the size bound on $\Bb$, there is a row in $\Bb$ with at least $\frac{|\sup_{\CFI}(\mu)|}{\log (\maxOrb_E(\mu))}$ many $1$-entries.

So far we have shown Properties 1, 2 and 3 from Theorem <ref>. Property 1 is proved by Corollary <ref>, Property 2 by Lemma <ref>, and Property 3 by Lemma <ref>.
It remains to estimate the size of the circuit under the assumption that every space $\Stab_E([y] \cap x)$ has a symmetric basis.

§.§ Bounding the size of the circuit

Let $\text{Atoms}(\mu) \subseteq \tc(\mu)$ denote the set of atoms in $\tc(\mu)$, and $\text{Sets}(\mu) := \tc(\mu) \setminus \text{Atoms}(\mu)$.
The size of $\widehat{C}(\mu)$ is

\[
|V_C| = |\{e \in E \mid e_0 \text{ or } e_1 \in \text{Atoms}(\mu)\}| + \sum_{\stackrel{([x],[y]), x \in \text{Sets}(\mu),}{[y] \in \Cc[x]}} |J_{[x][y]}|.
\]

In other words: The size of $\widehat{C}(\mu)$ is determined by the total number of rows of all $N[x][y]$-matrices.

By definition of $\widehat{C}(\mu)$, $|V_C| = \sum_{[x], x \in \tc(\mu)} | I_{[x]} |$. For each $x \in \tc(\mu) \cap \text{Sets}(\mu)$, we have $|I_{[x]}| = \sum_{[y] \in \Cc[x]} |J_{[x][y]}|$. Every set $J_{[x][y]}$ is exclusively associated with the pair $([x],[y])$, so

\[
\sum_{[x], x \in \tc(\mu)} | I_{[x]} | = \sum_{\stackrel{([x],[y]), x \in \text{Sets}(\mu),}{[y] \in \Cc[x]}} |J_{[x][y]}|.
\]

For each atomic $x \in \tc(\mu)$, $|I_{[x]}| = 1$.

Let $I,J$ be abstract index sets and $A \in \bbF_2^{J \times I}, \mathbf{b} \in \bbF_2^J$ such that the linear equation system $A \cdot \mathbf{x} = \mathbf{b}$ has a unique solution $\mathbf{s} \in \bbF_2^I$. Let $\mathbf{G} \leq \Sym(I)$ be a permutation group acting on the columns of $A$. Every $\pi \in \mathbf{G}$ that stabilises the row-set of $(A|\mathbf{b})$

\[
R := \{ (A_{j-},\mathbf{b}_j) \mid j \in J \}
\]

also stabilises the solution vector $\mathbf{s}$. The action of $\pi$ on $R$ is given by $\pi(A_{j-},\mathbf{b}_j) = (\pi(A_{j-}),\mathbf{b}_j)$.

If $\pi \in \mathbf{G}$ stabilises $R$, then there is a permutation $\sigma \in \Sym(J)$ that is induced by the action of $\pi$ on $R$, i.e. $\pi(A_{j-},\mathbf{b}_j) = (A_{\sigma j,-}, \mathbf{b}_{\sigma j})$ for all $j \in J$. For every $j \in J$, it holds $A_{j-} \cdot \mathbf{s} = \mathbf{b}_j$, because $\mathbf{s}$ is a solution to the equation system. Since $A_{j-} \cdot \mathbf{s} = \pi(A_{j-}) \cdot \pi(\mathbf{s})$, and $\mathbf{b}_j = \mathbf{b}_{\sigma j}$, $\pi(\mathbf{s})$ is a solution to the equation $A_{\sigma j -} \cdot \mathbf{x} = \mathbf{b}_{\sigma j}$. Since $\sigma \in \Sym(J)$, it follows that $\pi(\mathbf{s})$ is a solution for every equation. By assumption, $A \cdot \mathbf{x} = \mathbf{b}$ has a unique solution. Therefore, $\pi(\mathbf{s}) = \mathbf{s}$.

Let the setting be as in the previous lemma. Let $\Orb_G(R) := \{ \pi(R) \mid \pi \in G \}$, and $\Orb_G(\mathbf{s}) := \{ \pi(\mathbf{s}) \mid \pi \in G\}$ denote the respective $G$-orbits of the row-set of $(A|\mathbf{b})$ and of $\mathbf{s}$. Then

\[
| \Orb_G(\mathbf{s}) | \leq | \Orb_G(R) |.
\]

Lemma <ref> says that $\Stab_G(R) \leq \Stab_G(\mathbf{s})$. Thus, the corollary follows with the Orbit-Stabiliser Theorem.

Hence, in order to bound $|V_C|$, we have to bound the number of rows of each of the $N[x][y]$-matrices. To do so, we revisit the proofs of Lemmas <ref> and <ref>. We will see that the matrix that is constructed in these lemmas can be chosen to have polynomial size if a symmetric basis for $\Stab_E([y] \cap x)$ exists. The first step in the construction of $N[x][y]$ in Lemma <ref> is to solve a family of linear equation systems. We now show that the symmetries of such systems correspond to symmetries of their solutions.

Let $I,J$ be abstract index sets and $A,A' \in \bbF_2^{I \times J}, \mathbf{b}, \mathbf{b}' \in \bbF_2^I$ such that the linear equation systems $A \cdot \mathbf{x} = \mathbf{b}$ and $A' \cdot \mathbf{x} = \mathbf{b}'$ each have a unique solution $\mathbf{s}, \mathbf{s'}$, respectively. Let $\mathbf{G} \leq \Sym(J)$ be a permutation group acting on the columns of $A$. Let $\pi \in \mathbf{G}$ a permutation that maps the row-set of the extended coefficient matrix $(A|\mathbf{b})$

\[
R = \{ (A_{i-},\mathbf{b}_i) \mid i \in I \}
\]

to the row-set $R'$ of $(A'|\mathbf{b}')$. Here, the action of $\pi$ on $R$ is $\pi(A_{i-},\mathbf{b}_i) := (\pi(A_{i-}),\mathbf{b}_i)$. Then $\pi(\mathbf{s}) = \mathbf{s}'$.

We only have to show that $\pi(\mathbf{s})$ is a solution of $A' \cdot \mathbf{x} = \mathbf{b}'$. Then we have $\pi(\mathbf{s}) = \mathbf{s}'$ by uniqueness of the solution.
If $\pi \in \mathbf{G}$ maps $R$ to $R'$, then there is a permutation $\sigma \in \Sym(I)$ that is induced by the action of $\pi$, i.e. $\pi(A_{i-},\mathbf{b}_i) = (A'_{\sigma i,-}, \mathbf{b}'_{\sigma i})$ for all $i \in I$. For every $i \in I$, it holds $A_{i-} \cdot \mathbf{s} = \mathbf{b}_i$, because $\mathbf{s}$ is a solution to the equation system. Since (by Proposition <ref>) $A_{i-} \cdot \mathbf{s} = \pi(A_{i-}) \cdot \pi(\mathbf{s}) = A'_{\sigma i -} \cdot  \pi(\mathbf{s})$, and $\mathbf{b}_i = \mathbf{b}'_{\sigma i}$, $\pi(\mathbf{s})$ is a solution to the equation $A'_{\sigma i -} \cdot \mathbf{x} = \mathbf{b}'_{\sigma i}$. Since every row of $(A'|\mathbf{b}')$ has such a preimage under $\pi$, it follows that $\pi(\mathbf{s})$ is a solution for every equation in $A' \cdot \mathbf{x} = \mathbf{b}'$. By assumption, the equation system has a unique solution. Therefore, $\pi(\mathbf{s}) = \mathbf{s}'$.

The next lemma will become interesting once we are dealing with symmetric bases of vector spaces. It shows that the permutation invariance of a set of vectors (for example a symmetric basis) is preserved under linear maps and appropriate group homomorphisms.

Let $M \in \bbF_2^{I \times J}$ and let $\mathbf{G} \leq \Sym(J)$ be a permutation group acting on the columns of $M$. Let $B \subseteq \bbF_2^J$ be a set of vectors and $S := \Stab_{\mathbf{G}}(B)$. Let $g : \mathbf{G} \lra \Sym(I)$ be a group homomorphism such that for all $\pi \in \mathbf{G}$, $(g(\pi),\pi)M = M$.

Then $g(S)$ stabilises the set $M\cdot B = \{ M \cdot \mathbf{v} \mid \mathbf{v} \in B \}$.

Let $\pi \in S$ and $\mathbf{v} \in B$. Let $\mathbf{w} = M \cdot \mathbf{v}$. We show that $(g(\pi))^{-1}(\mathbf{w}) = M \cdot \pi(\mathbf{v})$. For each $i \in I$, we have

\[
M_{i,-} \cdot \pi(\mathbf{v}) = \pi(M_{(g(\pi))(i),-}) \cdot  \pi(\mathbf{v}) = M_{(g(\pi))(i),-} \cdot \mathbf{v}.
\]

The first equality holds because $(g(\pi),\pi)M = M$ by assumption and the second one is due to Proposition <ref>. It follows that $g(\pi)(M \cdot \pi(\mathbf{v})) = M \cdot \mathbf{v} = \mathbf{w}$. So $(g(\pi))^{-1}(\mathbf{w}) = M \cdot \pi(\mathbf{v})$. We have $\pi(\mathbf{v}) \in B$ because $\pi \in S$. Therefore, $(g(\pi))^{-1}(\mathbf{w}) \in M \cdot B$. Because $\mathbf{w} = M \cdot \mathbf{v}$ was arbitrary, we know that $(g(\pi))^{-1} = g(\pi^{-1}) \in g(S)$ stabilises the set $M \cdot B$. Since $\pi \in S$ was also arbitrary, $g(S)$ stabilises $M \cdot B$.

Finally, we provide the exact definition of what we mean by a symmetric basis. This definition is tailored to the spaces $\Stab_E([y] \cap x)$ that occur for the objects in $\tc(\mu)$. When we say “symmetric basis”, we actually mean two bases: We require that both the basis of $\Stab_E([y] \cap x)$ as well as its extension to a  basis of the ambient space be symmetric. Symmetry is meant in the sense that the orbit must have polynomial size.

Let $x \in \tc(\mu)$ and $[y] \in \Cc[x]$. We say that the vector space $\Gamma := \Stab_E([y] \cap x) \leq \bbF_2^E$ has a symmetric basis if there exist two bases

\[
\Bb_\Gamma \subseteq \Bb
\]

such that $\Bb_\Gamma$ is a basis of $\Gamma=\Stab_E([y] \cap x)$ and $\Bb$ is a basis of $\bbF_2^E$, and such that: The group

\begin{align*}
\Stab_{\Stab_G([y] \cap x)}&(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb) =\\
&\{ \pi \in \Stab_G([y] \cap x) \mid \pi(\Bb_{\Gamma}) = \Bb_{\Gamma} \text{ and } \pi(\Bb) = \Bb \} \leq \Stab_G([y] \cap x)
\end{align*}

has index $\leq \text{\upshape poly}(|\GG^S|)$ in $\Stab_G([y] \cap x)$.

In the above definition, the polynomial $\text{poly}( \cdot )$ is of course meant to be fixed for the whole family of CFI-instances that we are considering in Theorem <ref>.
Now let us continue with the main lemma that bounds the size of $N[x][y]$ assuming the existence of a symmetric basis.

Let $x \in \tc(\mu)$ and $[y] \in \Cc[x]$. If $\Stab_E([y] \cap x)$ has a symmetric basis, then the number of rows of $N[x][y]$ is polynomial in $|\GG^S|$.

We show that there is a Boolean matrix $N$ with a polynomial number of rows which satisfies conditions (i) and (ii) from Lemma <ref>. This proves the lemma because $N[x][y]$ is defined as the smallest such matrix.

Consider the proof of Lemma <ref>. When applied to $\Gamma = M[y] \cdot \Stab_E([y] \cap x)$ and $\Delta = M[y] \cdot \bbF_2^E = \Im(M[y])$, the proof shows that there is a matrix $N \in \bbF_2^{[k] \times I_{[y]}}$, for $k = \dim (\Im \ M[y]) - \dim (M[y] \cdot \Stab_E([y] \cap x))$, such that $\Ker(N) \cap \Im(M[y])= M[y] \cdot \Stab_E([y] \cap x)$. In the proof, $k$ linear equation systems $A_i \cdot \mathbf{x} = \mathbf{b}_i$ are defined, each one with a unique solution. Then, for $i \in [k]$, the $i$-th row of $N$ is defined as the unique solution to the equation system $A_i \cdot \mathbf{x} = \mathbf{b}_i$. The matrix $A_i$ is the same for every $i \in [k]$.
It depends on the choice of a basis for $M[y] \cdot \Stab_E([y] \cap x)$ and an extension to a basis of $\Im(M[y])$. More precisely, let $\{\mathbf{w}_1,...,\mathbf{w}_k\}$ be the vectors that extend the basis of $M[y] \cdot \Stab_E([y] \cap x)$ to a basis of $\Im(M[y])$.
The rows of $A_i$ are the basis vectors of $\Im(M[y])$, and the vector $\mathbf{b}_i$ has exactly one $1$-entry in the row corresponding to $\mathbf{w}_i$. In this way, $\mathbf{b}_i$ is defined for every $i \in [k]$.

One can check that this proof of Lemma <ref> still goes through if one uses a generating set for the space $M[y] \cdot \Stab_E([y] \cap x)$ instead of a basis for the rows of $A_i$ – as long as the extension $\{\mathbf{w}_1,...,\mathbf{w}_k\}$ to a basis of the full space $\Im(M[y])$ is a linearly independent set of vectors. This changes nothing and in particular, each equation system $A_i \cdot \mathbf{x} = \mathbf{b}_i$ will still have a unique solution because we have just added some redundant equations.

We choose appropriate bases now. Since $\Stab_E([y] \cap x)$ has a symmetric basis by assumption, there are bases $\Bb_\Gamma \subseteq \Bb$ of $\Stab_E([y] \cap x)$ and $\bbF_2^E$, respectively, such that $\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ has small index in $\Stab_G([y] \cap x)$. Let $\Bb'_\Gamma := M[y] \cdot \Bb_\Gamma \setminus \{\mathbf{0}\}$ and $\Bb' := M[y] \cdot \Bb \setminus \{\mathbf{0}\}$. Then $\Bb'_\Gamma$ is a generating set for $M[y] \cdot \Stab_E([y] \cap x)$, and $\Bb' \setminus \Bb'_\Gamma$ extends this generating set to a basis of $\Im(M[y])$. Importantly, $\Bb' \setminus \Bb'_\Gamma$ is a linearly independent set of vectors (while $\Bb'_\Gamma$ may be linearly dependent). This is because $\Ker(M[y]) = \Stab_E(y)$ (Lemma <ref>), and $\Stab_E(y) \leq \Stab_E([y] \cap x)$. Thus, if there were a subset $K \subseteq \Bb' \setminus \Bb'_\Gamma$ such that $\sum K = 0$, then the sum of the $M[y]$-preimages of the vectors in $K$ would be in $\Ker(M[y]) = \Stab_E(y)$. This cannot be the case because $\Bb_\Gamma$ is a basis for $\Stab_E([y] \cap x) \geq \Stab_E(y)$, so no linear combination of vectors in $\Bb \setminus \Bb_\Gamma$ can be in $\Stab_E(y)$.

Now apply Lemma <ref> to the matrix $M = M[y] \in \bbF_2^{I_{[y]} \times E}$, $\mathbf{G} = \Stab_G([y] \cap x), B = \Bb_\Gamma$ and the homomorphism $g$ defined like this: $g : \Stab_G([y] \cap x) \lra \Sym(I_{[y]})$ maps any $\pi \in \Stab_G([y] \cap x)$ to the $I_{[y]}$-restriction of the permutation $g_{[y]}(\pi) \in \Sym(I_{\Omega_{[y]}})$. This is well-defined and $g(\pi) \in \Sym(I_{[y]})$ because $\Stab_G([y] \cap x) \leq \Stab_G([y])$ by Corollary <ref>, and $g_{[y]}(\Stab_G([y]))$ maps $I_{[y]}$ to itself by Lemma <ref>.

Now it follows with Lemma <ref> that $g(\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma)) \leq \Sym(I_{[y]})$ stabilises the set $M[y] \cdot \Bb_{\Gamma} \subseteq \bbF_2^{I_{[y]}}$. It holds $\Bb'_\Gamma = M[y] \cdot \Bb_{\Gamma}  \setminus \{\mathbf{0}\}$, and the zero-vector forms a singleton orbit with respect to permutations of the entries, so also $\Bb'_\Gamma$ is stabilised by $g(\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma))$.
Similarly, by applying Lemma <ref> to $B = \Bb$, we get that $g(\Stab_{\Stab_G([y] \cap x)}(\Bb))$ stabilises $\Bb'$.

Every permutation $\pi \in \Sym(I_{[y]})$ that stabilises the sets $\Bb'_\Gamma$ and $\Bb'$ induces a permutation $\sigma \in \Sym(\Bb')$, whose restriction to $\Bb'_\Gamma$ is a permutation in $\Sym(\Bb'_\Gamma)$. Since the rows of each coefficient matrix $A_i$ are the vectors in $\Bb'$, every $\pi \in \Sym(I_{[y]})$ that fixes $\Bb'$ setwise reorders the rows of $A_i$. The right hand side $\mathbf{b}_i$ has only one $1$-entry in the row corresponding to $\mathbf{w}_i \in \Bb' \setminus \Bb'_\Gamma$. So if $\pi$ also stabilises $\Bb'_\Gamma$, the action of $\pi$ on $(A_i|\mathbf{b}_i)$ moves the row vector $\pi^{-1}(\mathbf{w}_i) \in \Bb' \setminus \Bb'_\Gamma$ to the row where $\mathbf{b}_i$ has its $1$-entry. Up to a reordering of rows, this yields one of the other linear equation systems $\{ (A_i|\mathbf{b}_i) \mid i \in [k] \}$, because in some linear equation system, the equation with coefficient vector $\pi^{-1}(\mathbf{w}_i)$ has a $1$ on the right hand side. So any $\pi$ that stabilises both $\Bb'_\Gamma$ and $\Bb'$ induces a permutation on the set of linear equation systems $\{ (A_i|\mathbf{b}_i) \mid i \in [k] \}$ in the sense of Lemma <ref> (with the action of column permutations on the row set of an equation system as defined there).

\[
\Ss := g(\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma)) \cap g(\Stab_{\Stab_G([y] \cap x)}(\Bb)).
\]

As we argued above, this group fixes both $\Bb'$ and $\Bb'_\Gamma$.
Therefore, it induces a permutation on the equation systems and so  Lemma <ref> tells us that $\Ss$ also induces a corresponding permutation on the set

\[
\{ \mathbf{s}_i \in \bbF_2^{I_{[y]}} \mid \mathbf{s}_i \text{ is the unique solution to } A_i \cdot \mathbf{x} = \mathbf{b}_i \}
\]

(where $\Ss$ acts on these vectors by permuting the entries). These solution vectors form exactly the rows of the matrix $N \in \bbF_2^{[k] \times I_{[y]}}$ that is being constructed in the proof of Lemma <ref>. Therefore, the group $\Ss$ acting on the columns of $N$ induces corresponding permutations on the rows of $N$. In other words, for every $\pi \in \Ss$ there is a $\sigma \in \Sym_k$ such that $(\sigma, \pi)N = N$. Now we close the rows of $N$ under the action of $g(\Stab_G([y] \cap x))$, exactly like in the proof of Lemma <ref>. This yields a matrix satisfying the desired conditions (a) and (b). We now argue that for each row of $N$, only $\text{poly}(k+|\GG^S|)$ many rows are added to form the closure under $g_{[y]}(\Stab_G([y] \cap x))$.

To show this, we have to bound the size of
$\Orb(N_{i-}) = \{ \pi(N_{i-}) \mid \pi \in g(\Stab_G([y] \cap x)) \}$. Let $\Orb(N)$ denote the $g(\Stab_G([y] \cap x))$-orbit of the set of rows of $N$, and $\Stab(N) \leq g(\Stab_G([y] \cap x))$ the setwise stabiliser of the set of rows. It holds $|\Orb(N_{i-}) | \leq k \cdot |\Orb(N) |$ because any image of the row $N_{i-}$ is an element of at least one of the $k$-element row sets in $\Orb(N)$. Together with the Orbit-Stabiliser Theorem, we get

\[
|\Orb(N_{i-}) | \leq k \cdot |\Orb(N) | = k \cdot \frac{|g(\Stab_G([y] \cap x)) |}{| \Stab(N) |}.
\]

By what we argued above, we have
$\Ss \leq \Stab(N)$ and thus

\begin{align*}
\frac{|g(\Stab_G([y] \cap x)) |}{| \Stab(N) |} &\leq \frac{|g(\Stab_G([y] \cap x)) |}{| \Ss |}\\ &\leq \frac{|g(\Stab_G([y] \cap x)) |}{| g(\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)) |}.
\end{align*}

The last inequality holds because $g(\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)) \leq \Ss$.
It is not difficult to prove that the application of a group homomorphism can only decrease the index of $H$ in $G$, i.e. $[h(G) : h(H)] \leq [G : H]$. According to Definition <ref>, the index of $\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ in $\Stab_G([y] \cap x)$ is polynomially bounded in$ | \GG^S|$. As $g$ is a group homomorphism, this is also a bound for the index of the image under $g$, which is equal to the fraction above.
In total, we have shown:

\[
|\Orb(N_{i-}) | \leq k \cdot \text{poly}(| \GG^S|) \leq \text{poly}(k+| \GG^S|).
\]

Now this orbit bound applies to each of the $k$ rows of $N$, so when closing the rows of $N$ under the action of $g(\Stab_G([y] \cap x))$, we add at most $\text{poly}(k+| \GG^S|)$ many new rows to the matrix. Because $k  = \dim (\Im \ M[y]) - \dim (M[y] \cdot \Stab_E([y] \cap x)) \leq \dim (\Im \ M[y]) \leq |E|$ (this holds because $M[y]$ is a linear map defined on the $|E|$-dimensional space $\bbF_2^E$), $\text{poly}(k+|\GG^S|) = \text{poly}(|\GG^S|)$. The resulting matrix is a candidate for $N[x][y]$, so this shows that $N[x][y]$ has at most $\text{poly}(|\GG^S|)$ many rows.

If for all $x \in \tc(\mu)$ and all $[y] \in \Cc[x]$, $\Stab_E([y] \cap x)$ has a symmetric basis, then $|V_C|$ has size polynomial in $|\GG^S|$.

This follows directly from Lemma <ref> and Lemma <ref> (remember that $|J_{[x][y]}|$ is the number of rows of $N[x][y]$), and from the fact that $|\tc(\mu)|$ is polynomial in $|\GG^S|$ because $\mu$ is CPT-definable in $\GG^S$.

This proves Property 4 from Theorem <ref>.

§.§ Which vector spaces have symmetric bases?

We have shown that the size of $\widehat{C}(\mu)$ can be polynomially bounded if for all $x \in \tc(\mu)$ and all $[y] \in \Cc[x]$, the stabiliser space $\Stab_E([y] \cap x)$ has a symmetric basis. If this is not the case, then we do not know anything about the size of $\widehat{C}(\mu)$. There may be other ways to bound it but a priori we have to assume that it is super-polynomial then. This makes these symmetric XOR-circuits less useful for deriving lower bounds against CPT than in the CFI-symmetric case, unless, of course, we know that the object $\mu$ satisfies the symmetric basis property.

This leads to the question what the class of h.f. sets with the symmetric basis property looks like. We do not have a definitive answer but we can show: All CFI-symmetric objects admit symmetric bases, there are easy examples of objects with symmetric bases which are not CFI-symmetric, and there also exist objects which do not admit symmetric bases but may a priori be CPT-definable. This latter result shows that there is unfortunately little hope to generally prove that all CPT-definable objects over CFI-graphs admit symmetric bases.

In the following, whenever we have a Boolean vector space $\bbF_2^I$ over some index-set $I$, then $\widetilde{\bbF}_2^{I}$ denotes the even subspace of $\bbF_2^I$, i.e. the subspace consisting of all vectors with even Hamming weight. Moreover, $\bbF_2^I \oplus \bbF_2^J$ denotes the direct sum of the two vector spaces. If $I$ and $J$ are disjoint, then $\bbF_2^I \oplus \bbF_2^J$ is simply equal to $\bbF_2^{I \cup J}$.

Let $\mu \in \HF(\widehat{E})$ be CFI-symmetric. Then $\mu$ satisfies the symmetric basis condition from Definition <ref>.

Proof sketch. Let $x \in \tc(\mu)$ and $[y] \in \Cc[x]$. Let $\Gamma := \Stab_E([y] \cap x) \leq \bbF_2^E$. We have to define two bases $\Bb_\Gamma \subseteq \Bb$ of $\Gamma$ and of $\bbF_2^E$, respectively, such that the group $\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ has polynomial index in $\Stab_G([y] \cap x)$. Since $\mu$ is CFI-symmetric, by Definition <ref>, the $\Aut_{\CFI}(\GG)$-orbit of $[y] \cap x$ has size exactly two. One can prove that then, the stabiliser space $\Stab_E([y] \cap x)$ is a direct sum of a subspace on some coordinate set $I \subseteq E$ containing exactly the vectors with even Hamming weight and the full Boolean space on coordinates $E \setminus I$. It is relatively easy to construct a basis for such a space whose orbit has only linear size: For the even subspace of $\bbF_2^I$ one can fix one coordinate $i \in I$ and take the basis $\{ \chi(i)+\chi(e) \mid e \in I \setminus \{i \} \}$, which is symmetric up to the choice of $i$. For the space $\bbF_2^{E \setminus I}$, we can simply take the canonical basis consisting of the unit vectors. Details are in the appendix.

Let $x \in \tc(\mu)$ and $[y] \in \Cc[x]$. Let $\Gamma := \Stab_E([y] \cap x) \leq \bbF_2^E$. We have to define two bases $\Bb_\Gamma \subseteq \Bb$ of $\Gamma$ and of $\bbF_2^E$, respectively, such that the group $\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ has polynomial index in $\Stab_G([y] \cap x)$.
Since $\mu$ is CFI-symmetric, by Definition <ref>, the $\Aut_{\CFI}(\GG)$-orbit of $[y] \cap x$ has size exactly two. We have $\Aut_{\CFI}(\GG) \cong \bbF_2^E$, so by the Orbit-Stabiliser Theorem, $\Stab_E([y] \cap x)$ is a subspace of $\bbF_2^E$ with co-dimension one.
We use this to analyse the structure of the space $\Stab_E([y] \cap x)$. The group $\Stab_G([y] \cap x)$ is a subgroup of $\Aut(G) \leq \Sym(V)$ and therefore also acts on the edge set $E$. Thus, we can partition $E$ into its $\Stab_G([y] \cap x)$-orbits. Let $\Pp = \{P_1,...,P_m\}$ denote this orbit partition of $E$.

Claim 1: For exactly one of the orbits $P_i$, the projection of $\Stab_E([y] \cap x)$ onto the coordinates in $P_i$, denoted $\Stab_E([y] \cap x)|_{P_i}$ is isomorphic to the space $\widetilde{\bbF}_2^{P_i}$, that is, the space that contains all even Hamming-weight vectors. For all other orbits $P_j$, for $j \in [m] \setminus \{i\}$, $\Stab_E([y] \cap x)|_{P_j}$ is the full space $\bbF_2^{P_j}$.

Proof of claim. It cannot be the case that for all orbits, the projection of $\Stab_E([y] \cap x)$ is the full space on that orbit. If this were so, then $\Stab_E([y] \cap x) = \bbF_2^E$, but we know that $\Stab_E([y] \cap x)$ is a proper subspace of $\bbF_2^E$. So there exists a $P_i \in \Pp$ such that $\Stab_E([y] \cap x)|_{P_i} \neq \bbF_2^{P_i}$. Then we know that $\Stab_E([y] \cap x)|_{P_i}$ contains no unit vector at all because if it did, then it would contain all unit vectors, since $\Stab_G([y] \cap x)$ is transitive on the orbit $P_i$ and the space $\Stab_E([y] \cap x)$ is invariant under the action of $\Stab_G([y] \cap x)$ on the coordinates (Lemma <ref>).
Because $\Stab_E([y] \cap x)$ has only co-dimension one in $\bbF_2^E$, adding one new unit vector to $\Stab_E([y] \cap x)$ suffices to turn the space $\Stab_E([y] \cap x)|_{P_i}$ into $\bbF_2^{P_i}$. This is only possible if $\Stab_E([y] \cap x)|_{P_i} = \widetilde{\bbF}_2^{P_i}$. It remains to argue that for all $j \neq i$, we have $\Stab_E([y] \cap x)|_{P_j} = \bbF_2^{P_j}$. If there were another $j$ such that $\Stab_E([y] \cap x)|_{P_j} \neq \bbF_2^{P_j}$, then $\Stab_E([y] \cap x)|_{P_j} = \widetilde{\bbF}_2^{P_j}$, for the same reason as in the case of $P_i$. But then the co-dimension of $\Stab_E([y] \cap x)$ in $\bbF_2^E$ would be $\geq 2$: There is no way to add a single vector to $\Stab_E([y] \cap x)$ in order to get to the full space $\bbF_2^E$. If we add a vector that has odd Hamming weight on both $P_i$ and $P_j$, then the resulting space only has vectors where the Hamming weight on $P_i$ and $P_j$ has the same parity. In particular, unit vectors for coordinates in $P_i$ and $P_j$ are still missing. So in total, the only way for $\Stab_E([y] \cap x)$ to have co-dimension exactly one in $\bbF_2^E$ is if $\Stab_E([y] \cap x)$ has the claimed structure.

Claim 2: For every $y \in \tc(\mu)$, there exists a partition $\Pp = \{P_1,...,P_m\}$ of $E$ such that $\Stab_E(y) = \bbF_2^{P_1} \oplus \bigoplus_{i=2}^m \widetilde{\bbF}_2^{P_i}$.

Proof of claim: If $y$ is an atom of the form $e_j$, for $e \in E$ and $j \in \{0,1\}$, then $\Stab_E(y)$ contains all vectors in $\bbF_2^E$ that are zero at coordinate $e$. Thus, $\Stab_E(y) = \bbF_2^{E \setminus \{e\}} \oplus \widetilde{\bbF}_2^{\{e\}}$.

Now let $y$ be a set. It can be partitioned into a set $\Cc(y)$ of connected components. Each component $\gamma \in \Cc(y)$ can be written as $\gamma = [z] \cap y$ for some $z \in \tc(\mu)$. By Claim 1, there is a partition $E = A_\gamma \uplus B_\gamma$ such that $\Stab_E([z] \cap y) = \bbF_2^{A_\gamma} \oplus \widetilde{\bbF}_2^{B_\gamma}$. Using Proposition <ref>, we get

\[
\Stab_E(y) = \bigcap_{\gamma \in \Cc(y)} \Stab_E(\gamma) = \bigcap_{\gamma \in \Cc(y)} \Big( \bbF_2^{A_\gamma} \oplus \widetilde{\bbF}_2^{B_\gamma} \Big).
\]

Now define the partition $\Pp = \{P_1,...,P_m\}$ of $E$ such that $P_1 := \bigcap_{\gamma \in \Cc(y)} A_\gamma$, and the other parts form a partition of $\bigcup_{\gamma \in \Cc(y)} B_\gamma$ such that for each $P_i$ and each $\gamma \in \Cc(y)$, $P_i$ is either completely contained in $B_\gamma$ or completely outside of $B_\gamma$. It can be checked that indeed

\[
\bigcap_{\gamma \in \Cc(y)} \Big( \bbF_2^{A_\gamma} \oplus \widetilde{\bbF}_2^{B_\gamma} \Big) = \bbF_2^{P_1} \oplus \bigoplus_{i=2}^m \widetilde{\bbF}_2^{P_i}.
\]

Now we can put Claim 1 and Claim 2 together to define the desired bases for $\Stab_E([y] \cap x)$ and $\bbF_2^E$. According to Claim 1, we can write $\Stab_E([y] \cap x) = \bbF_2^A \oplus \widetilde{\bbF}_2^B$ for a partition $E = A \uplus B$.
Fix an arbitrary edge $f \in B$. We define

\[
\Bb_\Gamma := \{ \chi(e) \mid e \in A\} \cup \{ \chi(\{ e,f\}) \mid e \in B \setminus \{f \} \}.
\]

It is not hard to check that this is indeed a basis of $\bbF_2^A \oplus \widetilde{\bbF}_2^B$. The basis $\Bb$ of $\bbF_2^E$ is then simply defined as $\Bb := \Bb_\Gamma \cup \{ \chi(f) \}$.

Now the group
$\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ contains all permutations in $\Stab_G([y] \cap x)$ that fix the edge $f$ and fix the sets $A$ and $B$ (setwise). By Claim 1, $B \subseteq E$ is a $\Stab_G([y] \cap x)$-orbit and $A$ is a union of $\Stab_G([y] \cap x)$-orbits, so the latter condition is fulfilled by all permutations in $\Stab_G([y] \cap x)$. Therefore,  $\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ is simply the pointwise stabiliser of $f$ in $\Stab_G([y] \cap x) \leq \Sym(E)$, and this has index at most $|E|$. This is polynomial in $|\GG^S|$.

Finally, we have to verify that the last requirement of Definition <ref> is satisfied. Namely, we have to show that for each $B \in \{ \Bb_\Gamma, \Bb\}$ and every non-empty $K \subseteq B$ with $\Big( \sum K \Big) \in \Stab(y)$, there are two (or one) vectors in $K$ whose sum is already in $\Stab(y)$. So let $B = \Bb_\Gamma$ and $K \subseteq \Bb_\Gamma$ such that $\Big( \sum K \Big) \in \Stab(y)$. By Claim 2, the vector $\sum K$ has even Hamming weight on every part $P_i \in \Pp$ with $i \geq 2$. If $\sum K$ is non-zero on the part $P_1$, then $K$ contains some unit vector $\chi(e)$ with $e \in P_1$. This unit vector is in $\Bb_\Gamma$ because it must hold that $P_1 \subseteq A$, since $\Stab_E(y) \leq \Stab_E([y] \cap x)$. Therefore, we can choose $K' = \{ \chi(e) \}$. This works because $\chi(e) \in \Stab_E(y)$, as  $\Stab_E(y)$ contains all unit vectors for all edges in $P_1$ (Claim 2). In case that $\sum K$ is zero on $P_1$, it must be non-zero and even on some part $P_i$ with $i \geq 2$.  Then either some vector $\chi(\{e,f\}) \in \Bb_\Gamma$ is in $K$ (in which case $e,f \in P_i$ and so $\chi(\{e,f\}) \in \Stab_E(y)$), or there are two vectors $\mathbf{k}_1, \mathbf{k}_2 \in K$, each of which has exactly one $1$-entry in $P_i$, and potentially, both have an additional $1$-entry for the edge $f$ (note: it cannot happen that only one of $\mathbf{k}_1, \mathbf{k}_2$ has a $1$-entry for $f$, because then,
$P_i$ intersects both $A$ and $B$. This is not possible because then there would be a vector in $\Stab_E(y)$ that is odd on $A$ and odd on $B$, but this is not a vector in $\Stab_E([y] \cap x)$, contradicting $\Stab_E(y) \leq \Stab_E([y] \cap x)$).
Since $\mathbf{k}_1(f) = \mathbf{k}_2(f)$, the sum $\mathbf{k}_1 + \mathbf{k}_2$ is even on $P_i$ and zero on every other part in $\Pp$ and therefore in $\Stab_E(y)$. We can argue similarly in case that $B = \Bb$. Thus, all requirements from Definition <ref> are fulfilled by $\Bb_\Gamma$ and $\Bb$.

Thus, all CFI-symmetric h.f. sets satisfy the symmetric basis property from Definition <ref>. But are there any other objects that have symmetric bases? The answer is affirmative. To keep things simple, we do not give a fully specified example but only sketch how a family of non-CFI-symmetric h.f. sets with symmetric bases may look like. In the following, we always write $\widetilde{\bbF}_2^{I}$ for the subspace of $\bbF_2^I$ that consists of all vectors with even Hamming weight.

For $n \in \bbN$, let $E_n$ denote an $n$-element set of base edges. We do not fix a specific family $(G_n = (V_n,E_n))_{n \in \bbN}$ of base graphs. Let $A_n \uplus B_n \uplus \{e\} = E_n$ be an arbitrary partition of the edge set such that one part is a singleton. Consider again Example <ref>. There, we defined the CFI-symmetric object $\mu_{\{e,f,g\}} = \{ \{ \mu_{\{f,g\}}, e_0  \},   \{ \widetilde{\mu}_{\{f,g\}}  , e_1 \} \}$. In this construction,  $\mu_{\{f,g\}}$ and its automorphic image $\widetilde{\mu}_{\{f,g\}}$ are sets that are stabilised by every $\rho \in \Aut_{\CFI}(\GG)$ that flips an even number of edges in $\{f,g\}$. Such objects can be defined more generally for any set of edges. This is done in the CFI-algorithms from <cit.>. So let $\mu_{B_n}, \widetilde{\mu}_{B_n}$ denote two sets that together form an $\Aut_{\CFI}(\GG_n)$-orbit and are stabilised by any $\rho \in \Aut_{\CFI}(\GG_n)$ flipping an even number of edges in $B_n$. In other words, $\Stab_E(\mu_{B_n}) = \bbF_2^{A_n \cup \{e\}} \oplus \widetilde{\bbF}_2^{B_n}$.
Now for every $n \in \bbN$, let

\[
\mu_n := \{ \{ \mu_{B_n}, e_0    \} \} \in \HF(\widehat{E}_n).
\]

This object is similar to the one from Example <ref>, with the difference that the connected component of $\{ \mu_{B_n}, e_0    \}$ contains just this set itself, and therefore, the $\Aut_{\CFI}(\GG_n)$-orbit of this component has size four instead of two. Thus, $\mu_n$ is not CFI-symmetric. However, it does satisfy the symmetric basis property (assuming that $\mu_{B_n}$ does – which is possible since $\mu_{B_n}$ could e.g. be CFI-symmetric). Let $y = \{ \mu_{B_n}, e_0    \}$ and $x = \mu_n$. Then $[y] \cap x = y$, and hence $\Stab_E([y] \cap x) = \Stab_E(y) = \Stab_E(\{ \mu_{B_n}, e_0    \})$. It is not hard to construct a symmetric basis for this space. By the properties of $\mu_{B_n}$, we have

\[
\Stab_E(y) \cong \bbF_2^{A_n} \oplus \widetilde{\bbF}_2^{B_n}.
\]

In other words, this space contains every vector that has even Hamming weight on $B_n$ and a zero entry at coordinate $e$. A basis for this can be defined as in the proof of Lemma <ref>: Fix some $f \in B_n$. Then include in the basis $\Bb_\Gamma$ every unit vector $\chi(g)$ for $g \in A_n$ and the vector $\chi(\{f,g\})$ for each $g \in B_n \setminus \{f \}$. Let $\Bb := \Bb_\Gamma \cup \{ \chi(e), \chi(f) \}$.
We have not specified the base graphs exactly, so we have not made any assumptions on $\Aut(G)$.  Suppose now that $A_n$ and $B_n$ lie in different orbits of $\Stab_G([y] \cap x)$.
This makes sense because otherwise, $\mu_{B_n}$ would not necessarily be stabilised. Then $\Stab_{\Stab_G([y] \cap x)}(\Bb_\Gamma) \cap \Stab_{\Stab_G([y] \cap x)}(\Bb)$ is the pointwise stabiliser of $\{e,f\}$ in $\Stab_G([y] \cap x)$. This has index $\leq n^2$, which is polynomial.

Objects with symmetric bases are therefore indeed a strict generalisation of CFI-symmetric objects. Nonetheless, there currently exists no choiceless algorithm for the CFI query that requires the construction of objects which go beyond the CFI-symmetric ones.

Finally, the most important question is whether there also exist objects that are neither CFI-symmetric nor have symmetric bases.
Ideally, we would like the answer to be that every CPT-definable object $\mu$ satisfies the symmetric basis condition. Then, super-polynomial size lower bounds against suitable circuits would actually separate CPT from  because they would rule out any CPT-algorithm for the CFI-query, not just special algorithms like the CFI-symmetric ones. We do not know if this ideal situation is in fact reality. However, we have an example that suggests it is not.

The line of thought is this: An obvious way to show that every CPT-definable object $\mu$ has the symmetric basis property would be to try and exploit the fact that for every $x \in \tc(\mu)$ and every $[y] \in \Cc[x]$, $\Stab_E([y] \cap x)$ must have a polynomial index in $\Aut_{\CFI}(\GG^S) \leq \bbF_2^E$ (otherwise, the orbit of $[y] \cap x \subseteq \tc(\mu)$ would be super-polynomial, so $\mu$ would not be CPT-definable). This is perhaps the most obvious consequence that follows from the CPT-definability of $\mu$. To simplify things a bit, let us assume that  $\Aut_{\CFI}(\GG^S) = \bbF_2^E$. Then in terms of vector spaces, $[\bbF_2^E : \Stab_E([y] \cap x)]$ being polynomial means that the codimension of $\Stab_E([y] \cap x)$ in $\bbF_2^E$, i.e. $|E| - \dim \ \Stab_E([y] \cap x)$, is logarithmic. What we also know by Lemma <ref> is that the space $\Stab_E([y] \cap x)$ is invariant under the action of the permutation group $\Stab_G([y] \cap x)$. This leads to the question if these two restrictions on $\Stab_E([y] \cap x)$ are sufficient to show that $\Stab_E([y] \cap x)$ necessarily has a symmetric basis in the sense of Definition <ref>? Unfortunately, the answer is no. There is a family of Boolean vector spaces together with permutation groups on their index sets such that the spaces are invariant under the permutations, have at most logarithmic codimension in the ambient space, and do not admit a symmetric basis. We construct such an example in Lemma <ref> below. From this it does not follow directly that there are actually families of CFI-graphs and CPT-definable h.f. sets over them which do not have the symmetric basis property. It just means that we cannot show the symmetric basis property for general CPT-definable sets with arguments that are only based on the obvious properties of vector spaces which can occur as $\Stab_E([y] \cap x)$ in CPT-definable objects.

There exists a family of Boolean vector spaces $(\Gamma_n)_{n \in \bbN}$, a function $t(n) \in \Theta(n)$ with $\Gamma_n \leq \bbF_2^{t(n)}$, and a family of permutation groups $(\mathbf{G}_n)_{n \in \bbN}$ with $\mathbf{G}_n \leq \Sym_{t(n)}$ such that

* $\Gamma_n$ is $\mathbf{G}_n$-invariant.

* The codimension of $\Gamma_n$ in $\bbF_2^{t(n)}$ is $\Oo(\log n)$.

* For any pair of bases $\Bb_\Gamma \subseteq \Bb$ such that $\Bb_\Gamma$ is a basis of $\Gamma_n$ and $\Bb$ is a basis of $\bbF_2^{t(n)}$, $[\mathbf{G}_n : \Stab_{\mathbf{G}_n}(\Bb)] \geq \Big(\frac{n}{(\log n)^2}\Big)^{\log n}$, which is super-polynomial in $n$.

Proof sketch. We define $\Gamma_n$ as the direct sum of $\log n$ many even spaces $\widetilde{\bbF}_2^{P_i}$, for $i \in [\log n]$. The index-sets $P_i$ are pairwise disjoint and form a partition of $[n]$. The group $\mathbf{G}_n$ is defined as the setwise stabiliser of the partition $\{P_1,...,P_{\log n}\}$. Thus, the space $\Gamma_n$ is $\mathbf{G}_n$-invariant. The fact that the codimension of $\Gamma_n$ in $\bbF_2^n$ is $\Oo(\log n)$ is not difficult to see. The lower bound on the orbit size of any pair of bases $\Bb_\Gamma \subseteq \Bb$ holds because extending any $\Bb_\Gamma$ to a basis of $\bbF_2^E$ requires to choose at least one point in each part $P_i$, for $i \in [\log n]$. These are $\log n$ choices, each from a set of size $\frac{n}{\log n}$. The orbit size of this tuple of choices is super-polynomial in $n$. The detailed proof can be found in the appendix.

Define $t(n)$ as the next even natural number $\geq n$. We now construct $\Gamma_n$ and $\mathbf{G}_n$. Let $\Pp_n$ be a partition of $[t(n)]$ into $\approx \log n$ many parts such that each part is roughly of the same size, namely $\approx \frac{n}{\log n}$. Importantly, every part must be of even size; such a partition exists because $t(n)$ is even. For a part $P \in \Pp_n$, let $\widetilde{\bbF}_2^P \leq \bbF_2 ^{t(n)}$ denote the Boolean vector space that contains all vectors whose projection to $P$ has even Hamming weight and which are zero outside of $P$. Then we define

\[
\Gamma_n := \bigoplus_{P \in \Pp_n} \widetilde{\bbF}_2^P.
\]

In other words, $\Gamma_n$ contains exactly those vectors that have even Hamming weight on each of the parts in $\Pp_n$ (but not all vectors with even Hamming weight in $\bbF_2^{t(n)}$, namely not the vectors which are odd on an even number of parts). The permutation group $\mathbf{G}_n \leq \Sym_{t(n)}$ is defined as the largest group that setwise stabilises the partition $\Pp_n$. So $\mathbf{G}_n$ contains the direct product $\mathbf{H_n} := \prod_{P \in \Pp_n} \Sym(P)$ and all permutations that map each part of $\Pp_n$ to another part.

It is clear that $\Gamma_n$ is invariant under $\mathbf{G}_n$. Furthermore, the co-dimension of $\Gamma_n$ is logarithmic in $t(n) \approx n$: Suppose $\Bb_\Gamma$ is any basis of $\Gamma_n$. Then it can be extended to a basis of $\bbF_2^{t(n)}$ by adding one unit vector $e_P$ for each part $P \in \Pp_n$, such that $e_P$ has a $1$-entry in $P$ and is zero otherwise. The number of parts is logarithmic, so the same holds for the codimension. Finally, we have to prove the third condition.

Let $\Bb_\Gamma \subseteq \Bb$ be arbitrary bases for $\Gamma$ and $\bbF_2^{t(n)}$, respectively. Observe that $\Stab_{\mathbf{G}_n}(\Bb) \leq \Stab_{\mathbf{G}_n}(\Bb \setminus \Bb_\Gamma)$ because $\Gamma_n$ is $\mathbf{G}_n$-invariant and so, the vectors in $\Bb \setminus \Bb_\Gamma$ cannot be moved into $\Gamma$. Therefore:
$[\mathbf{G}_n : \Stab(\Bb \setminus \Bb_\Gamma)] \leq [\mathbf{G}_n : \Stab(\Bb)]$. Thus, it suffices to show the desired lower bound for $[\mathbf{G}_n : \Stab(\Bb \setminus \Bb_\Gamma)]$. Let $\mathbf{w}_1,...,\mathbf{w}_{\log n}$ be an enumeration of $\Bb \setminus \Bb_\Gamma$. For each $i \leq \log n$, let $\Qq_i \subseteq \Pp_n$ denote the set of parts $P \in \Pp_n$ such that $\mathbf{w}_i$ has odd Hamming weight on $P$. We know that for each $i$, $\Qq_i \neq \emptyset$ because otherwise, $\mathbf{w}_i$ would be in $\Gamma$. Moreover, each $P \in \Pp_n$ is in at least one of the $\Qq_i$ because otherwise, $\Bb$ would not generate the whole space $\bbF_2^{t(n)}$.

Now in order to estimate $|\Stab(\Bb \setminus \Bb_\Gamma)|$, we first estimate the size of the pointwise stabiliser of $\Bb \setminus \Bb_\Gamma$ in $\mathbf{H}_n$, $\StabP_{\mathbf{H}_n}(\Bb \setminus \Bb_\Gamma)$. This is the subgroup of $\mathbf{H}_n$ that stabilises each $\mathbf{w}_i \in \Bb \setminus \Bb_\Gamma$, so it consists of all permutations that fix each part $P \in \Pp_n$ and each $\mathbf{w}_i$.
We can bound this stabiliser as follows:

\[
|\StabP_{\mathbf{H}_n}(\Bb \setminus \Bb_\Gamma)| \leq \prod_{P \in \Pp_n} (|P|-1)!
\]

This holds because for each part $P \in \Pp_n$, there is a vector $\mathbf{w}_i \in \Bb \setminus \Bb_\Gamma$ which has odd weight on $P$. Since each part $P$ has even size, $\mathbf{w}_i$ is not the all-$1$-vector on $P$ (nor the all-zero vector, of course); therefore, the vector $\mathbf{w}_i$ is not fixed by all permutations in $\Sym(P)$ but at most by $(|P|-1)!$ many of them (for example, if $\mathbf{w}_i|_P$ is a unit vector).
Now because $[\mathbf{G}_n  :  \mathbf{H}_n] = (\log n)!$, we have

\[
| \StabP_{\mathbf{G}_n}(\Bb \setminus \Bb_\Gamma)| \leq  (\log n)! \cdot |\StabP_{\mathbf{H}_n}(\Bb \setminus \Bb_\Gamma)|.
\]

Furthermore, $[\Stab_{\mathbf{G}_n}(\Bb \setminus \Bb_\Gamma)  :  \StabP_{\mathbf{G}_n}(\Bb \setminus \Bb_\Gamma) ] \leq (\log n)!$. So in total, we get:

\[
\Stab_{\mathbf{G}_n}(\Bb \setminus \Bb_\Gamma)  \leq  (\log n)!^2 \cdot  \prod_{P \in \Pp_n} (|P|-1)!
\]

Since $|\mathbf{G}_n| = (\log n)! \cdot \prod_{P \in \Pp_n} |P|!$, we get for the index:

\[
[\mathbf{G}_n : \Stab_{\mathbf{G}_n}(\Bb)] \geq [\mathbf{G}_n : \Stab_{\mathbf{G}_n}(\Bb \setminus \Bb_\Gamma)] \geq 1/(\log n)! \cdot \prod_{P \in \Pp_n} |P| \geq \Big( \frac{n}{(\log n)^2}  \Big)^{\log n}.
\]

The last inequality follows because $\Pp_n$ consists of $\log n$ many parts of size $\frac{n}{\log n}$ each, and because $(\log n)! \leq (\log n)^{\log n}$.

We do not know if there actually exist CFI-graphs $(\GG_n^S)_{n \in \bbN}$ and h.f. sets $(\mu_n)_{n \in \bbN}$ over them in which $\Gamma_n \cong \Stab_E([y] \cap x)$ for some $x,y \in \tc(\mu_n)$, and $\mathbf{G}_n \cong \Stab_G([y] \cap x)$. This could a priori be the case. Anyway, we can conclude that the question whether a CPT-definable object $\mu$ over some CFI-instance $\GG^S$ admits symmetric bases for all relevant spaces $\Stab_E([y] \cap x)$ cannot be answered without using further information about $\GG^S$ and $\mu$: It seems that CPT-definability of the objects is not sufficient to infer the existence of the required symmetric bases (or this requires more sophisticated techniques than just using the logarithmic bound on the codimension). It should be remarked, though, that making further progress in this direction seems only useful once we have a strong enough lower bound for these circuits, which would separate the CFI-symmetric algorithms from $\ptime$. Then, as a next step, one could try to see in how far this generalises to all choiceless algorithms.

§ APPLICATION TO HYPERCUBE CFI-STRUCTURES

Our second main result is a lower bound against symmetric XOR-circuits over $n$-dimensional hypercubes. It shows that the circuits corresponding to CFI-symmetric h.f. sets over hypercube CFI-structures do not exist if we make the circuit parameters slightly more restrictive than in Theorem <ref> (so note that we are returning to the CFI-symmetric setting now). First, however, we have to check that these hypercube CFI-structures  indeed satisfy the preconditions of Theorem <ref>.
The theorem mainly depends on three parameters of the base graphs: The treewidth of the graph, the CFI-support gap of the h.f. sets, and the fact that the CFI-graphs over the base graphs are $\Cc^{\tw_n}$-homogeneous.

The $n$-dimensional hypercube $\H_n$ is the undirected graph with universe $\{0,1\}^n$ in which there is an edge between any two words with Hamming distance exactly one. We let $E_n$ denote this edge relation and $V_n = \{0,1\}^n$ the vertex set of $\H_n$. Its automorphism group is the semi-direct product $\bbF_2^n \rtimes \Sym_n$, where $\Sym_n$ acts on the positions of the binary words and $\bbF_2^n$ acts on $\{0,1\}^n$ via the bitwise XOR-operation  <cit.>. We will in the following pretend that $\Aut(\H_n) \cong \Sym_n$, i.e. we ignore teh action of $\bbF_2^n$. This makes things easier and besides, if $\Sym_n$-symmetric XOR-circuits with the necessary properties do not exist, then this is “even more true” for the larger symmetry group $\bbF_2^n \rtimes \Sym_n$. Precisely, the group action is given by $\pi(v_1...v_n) = v_{\pi^{-1}(1)}v_{\pi^{-1}(2)}...v_{\pi^{-1}(n)}$, for every word $v \in \{0,1\}^n$ and $\pi \in \Sym_n$. In the hypercube, this corresponds to applying the same permutation $\pi$ to the neighbourhood of every vertex; this preserves the graph structure of the hypercube.

In the following, when we speak about CFI-structures over hypercubes, we do not distinguish between isomorphic ones, so we only consider the even and the odd CFI-structure over $\H_n$ and denote them $\HH_n^0$ and $\HH_n^1$, respectively. The size $|\HH_n^i|$ of these CFI-structures is polynomial in $2^n = |\H_n|$, because the CFI-construction increases the size of the graph exponentially in the maximum degree. This maximum degree in $\H_n$ is $n$, so the size increase by a factor of $2^n$ is still polynomial in $|\H_n|$. Now let us check the relevant properties of the hypercubes and their CFI-structures.

*Treewidth of hypercubes

The treewidth of the $n$-dimensional hypercube $\H_n$ is a function in $\Theta(2^{n}/\sqrt{n})$.

This is close to being linear in $2^n = |\H_n|$, so it is sufficiently large to translate into a meaningful lower bound on the input sensitivity of the resulting circuits. In particular, it is super-constant, and thus, the hypercube CFI-query is undefinable in fixed-point logic with counting.

*Homogeneity of hypercubes
Recall that a structure $\AA$ is $\Cc^k$-homogeneous for all tuples of some length $\ell \leq k$ if for all tuples $\bar{a}, \bar{b}$ of length $\leq \ell$ it holds: If $\bar{a}$ and $\bar{b}$ have the same $\Cc^k$-type in $\AA$, then there is an automorphism of $\AA$ that moves $\bar{a}$ to $\bar{b}$.
The next lemma is a technical ingredient that we need for the homogeneity result for hypercube CFI-structures. It shows the homogeneity condition for specific tuples. The full proof is given in the appendix.

We say that a tuple $\bar{\alpha}$ in $V(\HH_n^i)$ contains a star if there is a centre $c \in V(\H_n)$ such that for each incident edge $e \in E_n(c)$, there is an entry of $\alpha$ in the edge gadget $e^*$.

Let $\tw_n \in \Theta(2^n/\sqrt{n})$ denote the treewidth of $\H_n$. Let $\bar{\alpha}$ be a tuple in $V(\HH_n^i)$ that contains a star and has length at most $(\tw_n/n)-2$. Let $\gamma, \gamma' \in V(\HH_n^i)$ and let $\tp(\bar{\alpha}\gamma)$ denote the $\Cc^{\tw_n}$-type of this extended tuple.

If $\tp(\bar{\alpha}\gamma) = \tp(\bar{\alpha}\gamma')$, then there is an automorphism $\rho \in \Aut(\HH_n^i)$ such that $\rho(\gamma) = \gamma'$ and $\rho(\bar{\alpha}) = \bar{\alpha}$.

Proof sketch. The proof is mostly standard and works similarly as the homogeneity proofs in <cit.> and <cit.>. Firstly, one can show that if $\tp(\bar{\alpha}\gamma) = \tp(\bar{\alpha}\gamma')$, then $\gamma$ and $\gamma'$ must be in the same gadget of the CFI-structure. This holds even though the gadgets are not identifiable by means of a preorder: Using the parameters $\bar{\alpha}$, the gadgets of $\gamma$ and $\gamma'$ can be defined with a constant number of variables. Thus, we know that $\gamma$ and $\gamma'$ are in the same, say, edge gadget $e^*$ (the case where they are in a vertex gadget is analogous). If $\gamma = \gamma'$, then there is nothing to show. Else, we need to find an automorphism in $\Aut_{\CFI}(\HH_n^i)$ that flips $e^*$ and does not move any element of $\bar{\alpha}$. This is possible if there exists a cycle in $\H_n$ passing through $e$ and through none of the edges in $\bar{\alpha}$. If such a cycle does not exist, then the tuple $\bar{\alpha}\gamma$ marks the boundary of some sufficiently small subgraph of $\HH_n^i$, which, importantly, has treewidth $< \tw_n$. Then one can show that $\gamma$ and $\gamma'$ are definable in $\Cc^{\tw_n}$ using the parameters $\bar{\alpha}$. This works by using a transfer of the Cops' winning strategy from the cops and robber game to a winning strategy for Spoiler in the bijective $\tw_n$-pebble game, as in <cit.>. Thus, the desired cycle and hence automorphism must exist because otherwise, $\tp(\bar{\alpha}\gamma) \neq \tp(\bar{\alpha}\gamma')$.

TODO: Take the true proof from the thesis!!

We assume that $\tp(\bar{\alpha}\gamma) = \tp(\bar{\alpha}\gamma')$.
The first half of the proof consists in establishing that then, $\gamma, \gamma'$ are in the same edge or vertex gadget. Assume first that $\gamma, \gamma' \in \widehat{E}$. Now suppose for a contradiction that the edge gadget of $\gamma$ and $\gamma'$ is not the same. Let $\{u,v\} \in E_n$ be the edge in whose gadget $\gamma$ is, and let $\{u',v'\} \in E_n$ be the corresponding edge for $\gamma'$.
W.l.o.g. we may assume $u \neq u'$ and $u \neq v'$. Now let $s_1,...,s_n \in E_n$ be the edges that form the star which is covered by $\bar{\alpha}$ according to the assumption. We may assume that the centre of the star is the string $0^n$, because the automorphism group of the hypercube is transitive and so we can always move the centre of the star to $0^n$. Let $s_i$ denote the edge $\{0^n, 0^{i-1}10^{n-i}\}$, i.e. the edge along which the position $i$ is flipped.

Let $U \subseteq [n]$ be the positions at which the string $u$ is $1$. We construct a $\Cc^{5}$-formula $\phi_u(x)$ that defines the gadget $u^*$ in $\HH^i_n$ using the star $s_1,...,s_n$ as parameters. More precisely, let $s'_1,...,s'_n$ be the respective vertices in the edge gadgets that occur in $\bar{\alpha}$.

Our formula uses some auxiliary formulas: $\psi_{\dist=\ell}(x,y) \in \Cc^3$ which asserts that there is a path of length $\ell$ from $x$ to $y$. This can be expressed with only three variables by requantifying variables in an alternating way (see e.g. Proposition 3.2 in <cit.>). Also, we use a formula $\psi_\approx(x,y)$ which asserts that $x$ and $y$ are in the same vertex-gadget. This can be expressed by saying that both of them have exactly $n$ neighbours, and: For every neighbour $z$ of $x$, $z$ is either also a neighbour of $y$ or adjacent to a neighbour of $y$ (in the same edge-gadget). The same must hold for every neighbour $z$ of $y$. Expressing this requires not more than five variables in total. Now we define:

\begin{align*}
\phi_u(x) := &\bigwedge_{i \in U} \exists z  (\psi_{\dist=1+2(|U|-1)}(s'_i,z) \land \psi_\approx(z,x) ) \land \\
&\bigwedge_{i \in [n] \setminus U} \neg \exists z  (\psi_{\dist=1+2(|U|-1)}(s'_i,z) \land \psi_\approx(z,x) ).
\end{align*}

Claim: $\HH_n^i \models \phi_u(a)$ iff $a \in u^*$.

Proof of claim: We are assuming that $s_i$ is the edge between $0^n$ and the string with a $1$ at position $i$. Now we show that $\HH_n^i \models \phi_u(a)$ if $a \in u^*$: We have to check that for every $i \in [n]$, the respective conjunct of the formula is satisfied. If $i \in U$, then for any $s_i' \in s_i^*$, there exists $z \in u^*$ such that there is a path from $s_i'$ to $a$ of length exactly $1+2(|U|-1)$ in $\HH_n^i$: The path goes one step from $s_i'$ into the vertex gadget for $0^{i-1}10^{n-i}$, and from there, the path follows a shortest path of length $|U|-1$ in $\H_n$ that goes from  $0^{i-1}10^{n-i}$ to the vertex $u$ and flips the remaining $|U|-1$ zeros on the way. That path in the CFI-structure $\HH^i_n$ is twice as long because every edge is subdivided by a gadget. The path will end in some node in the vertex-gadget $u^*$. If $i \notin U$, then there is no path from $s_i'$ of length $1+2(|U|-1)$ that ends in a node in $u^*$: The shortest path from $s_i'$ into the gadget $u^*$ requires $1+2|U|$ steps. Hence, $\HH_n^i \models \phi_u(a)$.

If $a \notin u^*$, then $\HH_n^i \not\models \phi_u(a)$, because $\phi_u(a)$ can only be satisfied if the required paths exist (do not exist, respectively) in $\H_n$, and the above arguments also show that these conditions are only satisfiable if $a$ is in the gadget of $u$. This proves the claim.

Therefore, we have

\[
\HH_n^i \models \exists x ( E x \gamma \land \phi_u(x)  ),
\]

\[
\HH_n^i \not\models \exists x ( E x \gamma' \land \phi_u(x)  ).
\]

This is a contradiction to the assumption that $\bar{\alpha}\gamma$ and  $\bar{\alpha}\gamma'$ have the same $\Cc^{\tw_n}$-type, because $\phi_u$ has only $\Oo(n)$ many variables. Thus we have shown that there is one edge $g \in E_n$ such that $\gamma, \gamma' \in g^*$.

In case that $\gamma$ and $\gamma'$ are both in vertex gadgets, then the same argument shows that they must be in the same gadget $u^*$ because we can define this gadget with the above formula. Similarly, we can argue if $\gamma$ is in a vertex gadget and $\gamma'$ is in an edge gadget: Then we define the vertex gadget of $\gamma$ with the above formula, and $\gamma'$ will not satisfy it. So the types of the tuples being equal entails that $\gamma$ and $\gamma'$ must be in the same gadget, be it of an edge or vertex.

In the second half of the proof we show that there is an automorphism $\rho \in \Aut(\HH_n^i)$ that maps $\bar{\alpha}\gamma$ to $\bar{\alpha}\gamma'$, again under the assumption that $\tp(\bar{\alpha}\gamma) = \tp(\bar{\alpha}\gamma')$.
We first deal with the case that $\gamma, \gamma' \in g^*$ for some edge gadget $g^*$.
It is not necessary to permute the hypercube, so it suffices to find an edge-flip automorphism, i.e. $\rho \in \Aut_{\CFI}(\HH_n^i)$.

In case that $\gamma = \gamma'$, there is nothing to show. So let us assume that w.l.o.g. $\gamma = g_0$ and $\gamma' = g_1$. We need to find $\rho \in \Aut(\HH_n^i)$ such that $\rho(g_0) = g_1$, and such that $\rho$ fixes $\bar{\alpha}$. Now we call an edge $e = \{u,v\} \in E_n$ fixed if $e_0$ or $e_1$ occurs in $\bar{\alpha}$. We call a vertex $v \in V_n$ fixed if some node in$v^*$ occurs in $\bar{\alpha}$. We know that $g$ is not fixed because if it is, then $\bar{\alpha}g_0$ and $\bar{\alpha}g_1$ have different types. A cycle in $\H_n$ is called fixed if at least one edge or one vertex on it is fixed. Else, the cycle is free. If there exists a free cycle in $\H_n$ on which $g$ lies, then the desired automorphism is $\rho_F \in \Aut_{\CFI}(\HH_n^i)$, where $F$ is the edge-set of the free cycle.

Otherwise, every cycle on which $g$ lies is fixed. We want to show that in this case, $\bar{\alpha}\gamma$ and $\bar{\alpha}\gamma'$ do not have the same $\Cc^{\tw_n}$-type and so, this situation cannot occur.

Let $u,v \in \{0,1\}^n$ be the endpoints of $g$. Let $X_u \subseteq \{0,1\}^n$ be the set of vertices in $\H_n$ that are reachable from $u$ via paths using only free vertices and free edges in $E_n \setminus \{g\}$. The set $X_u$ is meant to include the fixed vertices which are reachable in this way. Similarly, we define $X_v$ as the set of reachable vertices from $v$ via such free paths (also including fixed vertices). Because no free cycle exists, the sets $X_u$ and $X_v$ must be disjoint (except for potential shared fixed vertices). We restrict the graph to one of these sets, it does not matter which. So let $X := X_u$.
We now consider the graphs $G$ and $G'$, which are induced subgraphs of $\HH^i_n$ on the universe

\begin{align*}
\Xx := \{ v^Y \mid v^Y \in v^*, v \in X \} &\cup \{ e_j \mid j \in \{0,1 \}, e \in E(\H_n[X]) \}\\
&\cup \{ a \in \widehat{E} \mid a \text{ an entry in } \bar{\alpha}\gamma \} \cup \{ \gamma'\}.
\end{align*}

Now $G := (\HH_n^i[\Xx], \bar{\alpha}\gamma)$ and $G' := (\HH_n^i[\Xx], \bar{\alpha}\gamma')$, that is, they are both the same induced subgraph of the CFI-graph, expanded with the respective tuples of constants (strictly speaking, the constant symbol for $\gamma$ and $\gamma'$ should be the same, but with the interpretation $\gamma$ and $\gamma'$, respectively).

Claim: Spoiler wins the bijective
$\tw_n$-pebble game on $G$ and $G'$.

Proof of claim: Trivially, the treewidth of $\H_n[X]$ is at most $\tw_n$ because $\tw_n$ is the treewidth of the whole hypercube, so the subgraph $\H_n[X]$ cannot have a larger treewidth. Hence, the Cops win the Cops and Robber game on $\H_n[X]$ with $\tw_n$ many cops.

Spoiler's goal is to pebble in both structures $G$ and $G'$ the vertex $e_1$ in every edge in $E_n(u) \setminus \{g\}$, i.e. every edge incident to $u$, except $g$. If he achieves that, then he wins in the next round: Assume w.l.o.g. that the gadget $u^*$ is even. Then in $G'$, an even number of neighbours of every vertex in $u^*$ is pebbled or equal to the constant $\gamma' = g_1$. In $G$, this number is odd for every vertex in $u^*$, because $\gamma = g_0$. Therefore, Spoiler can then place an additional pebble on an arbitrary vertex in $u^*$ and wins because Duplicator's bijection must map the gadget $u^*$ in $G$ to $u^*$ in $G'$.

Now Spoiler can achieve this goal by a standard argument, as for example given in <cit.>: Initially, the “target vertex” for Spoiler is $u$. This means that he has to pebble the $e_1$-vertices in all its incident edges in both graphs. Duplicator's bijections can flip edges, which changes the set of target vertices for Spoiler. Suppose $F \subseteq E(\H_n[X])$ is the set of edges flipped by Duplicator in a given round. This has the effect that every vertex in $\H_n[X]$ whose $F$-degree is odd changes its role from target- to non-target vertex and vice versa. However, Duplicator cannot flip edges which are pebbled by Spoiler. If Spoiler places his pebbles on edges (or their endpoints) according to the Cops' winning strategy (while Duplicator “moves the robber” by flipping paths), then he can eventually pin down a target vertex that Duplicator cannot move anywhere else. From such a position, he can enforce a situation as described above and wins the game. This argument is well-known; the only additional difficulty in our setting is that the base graph is not ordered, so we have to argue that Duplicator cannot win by playing bijections other than edge-flips. This can be enforced by Spoiler, using at most $n$ extra pebbles: The important observation is that Duplicator's bijection must respect distances to all pebbles on the board and to the parameters $\bar{\alpha}\gamma$. So Duplicator can only map a gadget $w^*$ to some other gadget $\pi(w^*)$ if the vertices $w$ and $\pi(w)$ have the same distance in $\H_n[X]$ to every pebbled vertex and parameter. This holds because if Duplicator disrespects distances between such marked elements, then Spoiler can easily win using three pebbles, that he moves along the shortest paths.

Now Spoiler can simply start by pebbling some star in $\H_n[X]$ with $n$ pebbles. Once a star is pebbled in $G$ and $G'$, it follows with the argument used earlier in the proof of this lemma that any $w \in V(\H_n[X])$ has a unique set of distances to the edges of the star, and therefore, Duplicator is then forced to map every $w^*$ to a unique vertex gadget $\pi(w^*)$. This entails that there is also a unique edge gadget $\pi(e^*)$ that she has to map each $e^*$ to. So, from that moment on, Duplicator is indeed limited to playing only edge-flips, and then, Spoiler wins in the aforementioned way using the Cops' strategy. This proves the claim.

The claim directly entails that $\bar{\alpha}\gamma$ and $\bar{\alpha}\gamma'$ do not have the same $\Cc^{\tw_n}$-type if $g$ does not lie on a free cycle. This finishes the case where $\gamma$ and $\gamma'$ are in an edge gadget. The other case is that $\gamma = u^*_Y$ and $\gamma' = u^*_{Y'}$ are both in some vertex gadget $u^*$. Then there is an even-sized set of edges $F = Y \triangle Y'$ incident with $u$ in $\H_n$ such that we have to flip the edges in $F$ (and no other edges in $E(u)$) in order to map $\gamma$ to $\gamma'$. This is possible if we can pair up the edges in $F$ in such a way that each pair $\{f_1,f_2\} \subseteq F$ lies on a free cycle (that avoids all other edges in $E(u)$). Suppose for a contradiction that there is some pair $\{f_1,f_2\} \subseteq F$ which is not on a free cycle. Then let $g := f_1$, and make the same argument as above in the case where we wanted to flip the edge $g$ (with the difference that we now remove both $f_1$ and $f_2$ in order to get the two sets $X_u$ and $X_v$ that are not connected by any free path). Then the above proof shows that the two nodes in the gadget $f_1^*$ are distinguishable in $\Cc^{\tw_n}$ using the parameters $\bar{\alpha}$. But then also $\gamma$ and $\gamma'$ in $u^*$ are distinguishable because one of them is adjacent to the $0$-node in $f_1^*$, and the other is adjacent to the $1$-node in $f_1^*$. So again, the required free cycles must exist because otherwise, $\bar{\alpha}\gamma$ and $\bar{\alpha}\gamma'$ have distinct $\Cc^{\tw_n}$-types.

The structures $\HH_n^0$ and $\HH_n^1$ are homogeneous in the following sense:

Let $\tw_n$ denote the treewidth of $\H_n$.
For any tuples $\bar{\alpha}, \bar{\alpha}'$ in $V(\HH_n^i)$ of length $|\bar{\alpha}| = |\bar{\alpha}'| \leq \tw_n/n-n-1$ it holds: If $\bar{\alpha}$ and $\bar{\alpha}'$ have the same $\Cc^{\tw_n}$-type in $\HH_n^i$, then there is an automorphism of $\HH_n^i$ that maps $\bar{\alpha}$ to $\bar{\alpha}'$.

First of all, we show the following statement via induction on $|\bar{\alpha}|$.

Claim 1:
Let $\bar{s}$ be a tuple of length $n$ that contains a star. If $\tp(\bar{s}\bar{\alpha}) = \tp(\bar{s}\bar{\alpha}')$, then there is an automorphism of $\HH_n^i$ that maps the tuple $\bar{s}\bar{\alpha}$ to $\bar{s}\bar{\alpha}'$.

Proof of claim: In the base case, $|\bar{\alpha}| = 0$, there is nothing to show because the identity permutation is the desired automorphism then.

For the inductive step, let $\bar{\alpha} = \bar{\beta}\gamma$ where $|\bar{\beta}| = |\bar{\alpha}|-1$, and similarly, write $\bar{\alpha}' = \bar{\beta}'\gamma'$. Since $\tp(\bar{s}\bar{\alpha}) = \tp(\bar{s}\bar{\alpha}')$, we also have $\tp(\bar{s}\bar{\beta}) = \tp(\bar{s}\bar{\beta}')$. Therefore, the induction hypothesis gives us an automorphism $\pi \in \Aut(\HH_n^i)$ such that $\pi(\bar{s}\bar{\beta}) = \bar{s}\bar{\beta}'$. Since automorphisms preserve types, we have $\tp(\bar{s}\bar{\beta}\gamma) = \tp(\pi(\bar{s}\bar{\beta}\gamma)) = \tp(\bar{s}\bar{\beta}'\pi(\gamma)) = \tp(\bar{s}\bar{\beta}'\gamma')$.

The length of the tuples $\bar{s}\bar{\beta}'\pi(\gamma)$ and $\bar{s}\bar{\beta}'\gamma'$ is at most $\tw_n/n-1$, so we can apply Lemma <ref> to them. This gives us another automorphism $\sigma$ such that $\sigma(\bar{s}\bar{\beta}'\pi(\gamma)) =  \bar{s}\bar{\beta}'\gamma'$. In total, $\sigma \circ \pi \in \Aut(\HH_n^i)$ is the desired automorphism that maps $\bar{s}\bar{\alpha}$ to $\bar{s}\bar{\alpha}'$.

Now we will use Claim 1 to prove the lemma. Let $\bar{\alpha}$ and $\bar{\alpha}'$ be as in the lemma. Let $\bar{s}$ be a tuple of length $n$ that contains a star (and only a star). By Lemma 34 in <cit.>, there exists a tuple $\bar{s}'$ such that $\tp(\bar{s}\bar{\alpha}) = \tp(\bar{s}'\bar{\alpha}')$.
This holds because $(\HH_n^i,  \bar{\alpha}) \equiv_{\Cc^{\tw_n}} (\HH_n^i,\bar{\alpha}')$ (Theorem <ref>), and so for any extension of the tuple $\bar{\alpha}$ (which has length at most $\tw_n - n$) by only $n$ elements, there is an extension of $\bar{\alpha}'$ that preserves the type.

Claim 2: There exists an automorphism $\sigma \in \Aut(\HH_n^i)$ such that $\sigma(\bar{s}) = \bar{s}'$.

Proof of claim: Let $s_1,...,s_n \in E_n$ be the edges of the star that is covered by $\bar{s}$ and $s'_1,...,s'_n \in E_n$ be the edges of the star of $\bar{s}'$. There is an automorphism $\sigma' \in \Aut(\H_n)$ such that $s'_i = \sigma'(s_i)$, for every $i$. This is easy to see because we can map the centre $c$ of one star to the centre $c'$ of the other, and apply the right permutation to its incident edges. In $\HH_n^i$, the gadgets $c^*$ and $c'^*$ are either both even or both odd, in relation to the tuple $\bar{s}$.
That is, if we pretend that the vertices $\bar{s}_i$ are the $1$-vertices in their respective edge-gadgets, then the vertex-gadgets $c^*$ and $c'^*$ have the same parity: This is because we can express in, say, $\Cc^{5}$ that every vertex in $c^*$ is connected with an even number of vertices in $\bar{s}$ (and $\bar{s}'$, respectively).

We say that there is a mismatch between $\sigma'(\bar{s})$ and $\bar{s}'$ at position $i$ if $\sigma'(\bar{s})_i$ is the $0$-vertex in its edge gadget, and  $\bar{s}'_i$ the $1$-vertex, or vice versa. By what we just argued, the number of mismatches between $\sigma'(\bar{s})$ and $\bar{s}'$ is even. This can be corrected with an automorphism $\rho_F \in \Aut_{\CFI}(\HH_n^i)$ that flips edges along $\ell$ disjoint cycles originating in $c'$, where $\ell$ is half the number of mismatches. Then $\sigma = \rho_F \circ \sigma'$ is an automorphism that takes $\bar{s}$ to $\bar{s}'$. This proves the claim.

With Claim 2, we get that $\tp(\bar{s}'\sigma(\bar{\alpha})) = \tp(\bar{s}'\bar{\alpha}')$ because automorphisms preserve types. The fact that $\bar{s}$ contains a star is easily definable in counting logic, so $\bar{s}'$ also contains a star. Therefore, the lemma now follows from Claim 1, which gives us an automorphism $\pi$ that maps $\sigma(\bar{\alpha})$ to $\bar{\alpha}'$. Then $\pi \circ \sigma$ is the automorphism whose existence is claimed in the lemma.

In total, the hypercube CFI-structures satisfy the homogeneity condition required by Theorem <ref> for all tuples of length bounded by $\tw_n /n - n -1$, which is in $\Theta(\tw_n/n)$.

*CFI-support gap of hypercube CFI-structures

Recall from Definition <ref> that the CFI-support gap of a h.f. set $\mu$ is $\alpha(\mu) = \frac{s(\mu)}{|\sup_{\CFI}(\mu)|}$ where $s(\mu)$ denotes the size of the smallest support; this depends on the structure.
Let again $\HH_n^i$ denote the odd/even CFI-structure over the $n$-dimensional hypercube, and let $E_n$ be the edge set of that hypercube. Let $\HH_n$ denote the full CFI-graph over $\H_n$ (see Section <ref>). We would like to prove an upper bound on the ratio $\alpha(\mu)$ over all h.f. sets $\mu \in \HF(\widehat{E}_n)$. Here, $s(\mu)$ denotes the size of the smallest $\Aut(\HH_n^i)$-support of $\mu$, and $\sup_{\CFI}(\mu)$ the size of the smallest CFI-support of $\mu$. Recall from Definition <ref> that a CFI-support of $\mu$ is a set of edges $S \subseteq E$ such that any edge-flip $\rho_F \in \Aut_{\CFI}(\HH_n)$ that fixes all edges in $S$ also fixes $\mu$. The edge-flips considered here are not necessarily automorphisms of $\HH_n^i$, so they include all combinations of flipped edges and not only cycles.

Let $n \in \bbN$ and $\mu \in \HF(\widehat{E}_n)$. Let $S \subseteq E$ be a smallest CFI-support of $\mu$. Then there exists an $\Aut(\HH_n^i)$-support of $\mu$ of size at most $|S|+n$.

Every $\rho_F \in \Aut_{\CFI}(\HH_n)$ such that $F \cap S = \emptyset$ fixes $\mu$. This holds in particular for every such $\rho_F \in \Aut_{\CFI}(\HH_n^i) \leq \Aut_{\CFI}(\HH_n)$. Thus, let $\bar{\alpha}$ be an arbitrary tuple in $\widehat{E}_n$ that contains exactly one vertex $e_i$ from every edge $e \in S$. So $|\bar{a}| = |S|$. Then any automorphism of the form $(\rho_F, \text{id}) \in \Aut(\HH_n^i)$ that fixes $\bar{\alpha}$ also fixes $\mu$. Now extend $\bar{\alpha}$ to a tuple $\bar{\beta}$ that contains a star. This is always possible such that $|\bar{\beta}| \leq |\bar{\alpha}|+n$. Now any automorphism in $\Aut(\HH_n^i)$ that fixes $\bar{\beta}$ must have $\text{id}$ as its second component, because any $(\rho_F, \pi) \in \Aut(\HH_n^i)$ with $\pi \neq \text{id}$ moves every star in the hypercube. So in total, every automorphism that fixes $\bar{\beta}$ fixes $\mu$, and the length of $\bar{\beta}$ is at most $|S| + n$.

Let $\tw_n \in \Theta(2^n/\sqrt{n})$ denote the treewidth of the $n$-dimensional hypercube. Let $\alpha(n) := \max_{\stackrel{\mu \in \HF(\widehat{E}_n),}{s(\mu) \in \Omega(\tw_n/n)}} \alpha(\mu)$ be the maximum CFI-support gap that can occur for any object in $\HF(\widehat{E}_n)$ with minimum support size at least $\Omega(\tw_n/n)$.

There is a function $g(n) \in \Oo(1)$ which is an upper bound for $\alpha(n)$.

Let $\mu \in \HF(\widehat{E}_n)$ be an object whose minimum $\Aut(\HH_n^i)$-support size $s(\mu)$ is at least $\Omega(\tw_n/n)$. By Lemma <ref>, its smallest CFI-support $\sup_{\CFI}(\mu)$ must have size at least $s(\mu) - n$. Thus, the CFI-support gap $\frac{s(\mu)}{|\sup_{\CFI}(\mu)|}$ is at most $\frac{s(\mu)}{s(\mu) -n} = 1 + \frac{n}{s(\mu) -n}$. Since $s(\mu) \in \Theta(2^n/n^{1.5})$, this expression is asymptotically equal to $1$.

Consequently, in the setting of Theorem <ref>, we can take a constant function $g(n)$ for the upper bound of the CFI support gap. This is convenient because it means that Theorem <ref> yields XOR-circuits that are sensitive to as many edges as possible, namely $\Omega(\tw_n/n)$ many. We are aiming to prove that the symmetric circuits given by the theorem cannot exist, so it is good that the support gap does not loosen the constraints on the circuits here.

In total, we can summarise our result for hypercube CFI-structures like this:

If there exists a super-symmetric and CFI-symmetric $\CPT$-program $\Pi$ that decides the CFI-query on the family of all hypercube CFI-structures $(\HH_n^i)_{n \in \bbN}$, then for every $\H_n = (V_n,E_n)$, there exists an XOR-circuit $C_n$ over $\H_n$ that satisfies:

* The number of gates in $C_n$ is polynomial in $2^n$.

* The orbit-size $|\Orb_{\H_n}(C_n)|$ of the circuit is polynomial in $2^n$.

* $C_n$ is sensitive to $\Omega(2^n/n^{1.5})$ many edges in $E_n$.

* The (unrestricted) fan-in dimension of $C_n$ is $\Oo(n)$.

This is simply Theorem <ref>, instantiated with the hypercube CFI-structures. The bounds come from the fact that $|\HH_n^i| = \text{poly}(2^n)$ and because the homogeneity condition for $\HH_n^i$ holds for all tuples of length at most $\Oo(\tw_n/n) = \Oo(2^n/n^{1.5})$.

§ LOWER BOUNDS FOR FAMILIES OF SYMMETRIC XOR-CIRCUITS OVER HYPERCUBES

If we could successfully show that circuits with the properties from Theorem <ref> do not exist, then this would imply that no super- and CFI-symmetric choiceless algorithm can solve the hypercube CFI-problem.
Unfortunately, we only manage this to a certain extent. We impose slightly stronger constraints on the circuits and then show that such circuit families over hypercubes indeed cannot exist. Concretely, we strengthen the symmetry condition on the circuits and assume that they are stabilised by all automorphisms of the base graphs (i.e. $n$-dimensional hypercubes), so their orbit size is one. Theorem <ref> states only that the orbit-size of the circuits has to be polynomial. Moreover, we impose the condition that the (orbit-wise) number of children and parents of every gate has to be logarithmically bounded. This may be related to the logarithmic bound on the fan-in dimension that we get from Theorem <ref>, but it is probably a stronger restriction. For circuits with these properties over the $n$-dimensional hypercubes, we show that they are not sensitive to enough input gates and hence violate Property 3 from Theorem <ref>.

Our lower bound is inspired by an “almost right” construction of circuits satisfying the properties from Theorem <ref>. The most difficult part about constructing such circuits seems to be the condition that they should have polynomial orbit size with respect to the action of $\Sym_n$ on $\{0,1\}^n$. A first idea would be to use some tree with logarithmic degree whose leafs are labelled with the elements of $\{0,1\}^n$. This would satisfy all properties except (maybe) the orbit-size. Actually, we do not have a proof that tree-like circuits with the required orbit size do not exist, but we suspect that trees are not symmetric enough. Our result from this section also points in that direction, as we will explain later.

Instead of tree-like circuits, there is another more or less obvious construction idea, that could be considered the opposite of trees: In order to build a circuit that is guaranteed to be symmetric under the hypercube automorphisms, we can simply use the hypercube itself: Cut the hypercube in the middle, and use one half of the hypercube as the circuit. The output gate will then be, for example, the string $0^n$, and the input gates are labelled with the strings of Hamming weight $(n/2)$, which are located in the “middle slice” of the hypercube. This construction is visualised below.

[dot/.style=draw,circle,minimum size=1.5mm,inner sep=0pt,outer sep=0pt,fill=blue,circ/.style=draw,circle,minimum size=2.5mm,inner sep=0pt, fill=red,
circY/.style=draw,circle,minimum size=2.5mm,inner sep=0pt, fill=yellow]

[dot,label=below:$1100$] (gate1100) at (-4,0) ;
[dot,label=below:$1010$] (gate1010) at (-2,0) ;
[dot,label=below:$1001$] (gate1001) at (0,0) ;

[dot,label=below:$0110$] (gate0110) at (2,0) ;
[dot,label=below:$0101$] (gate0101) at (4,0) ;

[dot,label=below:$0011$] (gate0011) at (6,0) ;

[dot,fill=red,label=left:$1000$] (gate1000) at (-3+1,2) ;
[dot,fill=red,label=left:$0100$] (gate0100) at (0,2) ;
[dot,fill=red,label=right:$0010$] (gate0010) at (2,2) ;
[dot,fill=red,label=right:$0001$] (gate0001) at (4,2) ;

[dot,fill=red,label=above:$0000$] (gate0000) at (1.1,3.5) ;

[->, thick] (gate0000) edge (gate1000);
[->, thick] (gate0000) edge (gate0100);
[->, thick] (gate0000) edge (gate0010);
[->, thick] (gate0000) edge (gate0001);

[->, thick] (gate1000) edge (gate1100);
[->, thick] (gate1000) edge (gate1010);
[->, thick] (gate1000) edge (gate1001);
[->, thick] (gate0100) edge (gate0110);
[->, thick] (gate0100) edge (gate0101);
[->, thick] (gate0100) edge (gate1100);
[->, thick] (gate0010) edge (gate1010);
[->, thick] (gate0010) edge (gate0110);
[->, thick] (gate0010) edge (gate0011);
[->, thick] (gate0001) edge (gate1001);
[->, thick] (gate0001) edge (gate0101);
[->, thick] (gate0001) edge (gate0011);

The $4$-dimensional hypercube cut in half. Red nodes are XOR-gates, blue nodes input gates.

The circuit satisfies the correct size and orbit size bounds (namely, the orbit size of the circuit is one by construction), and also, it has degree $n$, which is logarithmic in $|\HH_n^i|$. Since the degree is an upper-bound for the fan-in dimension, the logarithmic fan-in bound is satisfied as well. However, we can observe that the circuit is actually not sensitive to any input bit at all. Already in the second layer, counted from the input layer, all inputs cancel out (in the above example, this is in the root): Each input bit arrives at the root an even number of times. So we learn from this construction that it is possible to build highly symmetric circuits by making them very DAG-like, but the high number of distinct paths that any given input bit can take through the circuit can easily lead to the input bit cancelling itself at some point in the circuit. This happens whenever this number of paths is even. So roughly speaking, tree-like circuits and these “halved-hypercube circuits” are two extremes: With trees, the sensitivity condition (Property 3 in Theorem <ref>) is clearly satisfied, but the symmetry condition is not obvious. Conversely, in the halved hypercubes, the symmetry is satisfied by construction but the circuits are not sensitive to any input bit. The question is: What is in between these two extremes? We will now show that the input-cancellation effect from the halved-hypercube circuits actually occurs in a larger class of symmetric circuits. In some sense, this rules out all circuits that are too similar to the halved hypercube. Roughly speaking, these include all circuits over the $n$-dimensional hypercube that are stabilised by all permutations in $\Sym_n$ and have “orbit-wise” logarithmic in- and out-degree.

Fix a family $(C_n)_{n \in \bbN}$ of XOR-circuits such that the input gates of $C_n$ are labelled with edges of the $n$-dimensional hypercube $\H_n$. As in the previous section, the circuits are connected DAGs with a designated unique output gate, the root.
We define

\begin{align*}
\Aut(C_n) := &\{  \sigma \in \Sym(V_{C_n}) \mid \sigma \text{ is an automorphism of the rooted DAG } (V_C,E_C,r) \\
&\text{and there exists a } \pi \in \Sym_n \text{ s.t. } \ell(\sigma(g)) = \pi(\ell(g)) \text{ for every input gate } g  \}.
\end{align*}

Note that in particular, every automorphism must fix the root of the circuit and must permute the leafs in a way that complies with a permutation in $\Sym_n$ acting on the labels of leafs.
We say that a permutation $\pi \in \Sym_n$ extends to an automorphism $\sigma \in \Aut(C_n)$ if $\sigma$ maps the input gates $g$ such that $\ell(\sigma(g)) = \pi(\ell(g))$ is satisfied. It may be that the identity permutation in $\Sym_n$ extends to non-trivial circuit automorphisms in $C_n$. In this case, the circuit is not rigid and every permutation in $\Sym_n$ has multiple circuit automorphisms that it extends to.
For a gate $g$ in $C_n$ and a parent $h$ of $g$, we let
\[
\Orbit_{(g)}(h) := \{ \sigma(h) \mid \sigma \in \Aut(C_n), \sigma(g) = g  \}.
\]

\[
\Orbit_{(h)}(g) := \{ \sigma(g) \mid \sigma \in \Aut(C_n), \sigma(h) = h  \}.
\]

So these are the orbits of $g$, $h$, respectively, with respect to those circuit automorphisms that fix the child $g$, or the parent $h$, respectively. Note that $\Orbit_{(g)}(h) \subseteq E_C g$, and $\Orbit_{(h)}(g) \subseteq hE_C$ because circuit automorphisms preserve the wires and if one endpoint of a wire is fixed, then the image of the other endpoint must still be connected with the fixed gate. In the rest of this section, we prove:

Let $(C_n)_{n \in \bbN}$ be a family of XOR-circuits over the $n$-dimensional hypercubes such that for all $n \in \bbN$ it holds:

* The size $|V_{C_n}|$ is polynomial in $2^n$ (and thus polynomial in $|\HH_n^i|$).

* Every permutation $\pi \in \Sym_n$ acting on $\{0,1\}^n$ extends to a circuit-automorphism of $C_n$. Thus, the $\Sym_n$-orbit of $C_n$ has size one.

* There exists a function $f(n) \in \Oo(n)$ such that for all large enough $n$, for every gate $g$ and every parent $h$ of $g$ in $C_n$, both $|\Orbit_{(g)}(h)|$ and $|\Orbit_{(h)}(g)|$ are at most $f(n)$.

Then for any constant $\epsilon > 0$, it holds for all large enough $n$: The circuit $C_n$ can only be sensitive to an input gate $g$ if $\ell(g) = \{u,v\}$ is an edge such that the zero-one-split in the binary strings $u,v \in \{0,1\}^n$ is more imbalanced than $\epsilon n$ vs. $(1-\epsilon)n$. In other words, only if the number of $1$s or the number of $0$s in $u$ and $v$ is $< \epsilon n$, then this input gate contributes to the output of $C_n$.

In particular, these circuits do not satisfy Property 3 from Theorem <ref> and are therefore ruled out:

Let $(C_n)_{n \in \bbN}$ be a circuit family as in Theorem <ref>. Then for all large enough $n$, the circuit $C_n$ is sensitive to strictly less than
$o(2^n/n^{1.5})$ many inputs.

According to Exercise 9.42 on page 492 of <cit.>, it holds for any $\alpha \leq \frac{1}{2}$:

\[
\sum_{k \leq \alpha n} \binom{n}{k} = 2^{nH(\alpha)-\frac{1}{2}\log n + \Oo(1)},
\]

where $H(\alpha) = \alpha \log(\frac{1}{\alpha}) + (1-\alpha)\log(\frac{1}{1-\alpha})$. According to Theorem <ref>, the only edges of $\H_n$ that $C_n$ can be sensitive to are between binary strings with less than $\epsilon n$ many one- or zero-entries, for any $\epsilon > 0$. The number of potential endpoints of such edges is twice the above sum, for $\alpha = \epsilon$. The degree of $\H_n$ is $n$, so in total, $C_n$ is sensitive to at most $2n \cdot \sum_{k \leq \epsilon n} \binom{n}{k}$ many edges of $\H_n$. We can calculate that this is in $o(2^n/n^{1.5})$, for any $0 < \epsilon < \frac{1}{2}$:

\begin{align*}
&\lim_{n\to\infty} \frac{2^n}{n^{1.5} \cdot 2n \cdot 2^{nH(\epsilon)-\frac{1}{2}\log n + \Oo(1)}} = \\
&\lim_{n\to\infty} \frac{2^{(1-H(\epsilon))n +\frac{1}{2}\log n - \Oo(1)}}{2n \cdot n^{1.5}} = \infty
\end{align*}

In the last step, we used that $H(\epsilon) < 1$, which holds as long as $\epsilon$ is chosen to be strictly less than $\frac{1}{2}$.

This proves Theorem <ref>.
This result does not yet completely rule out the existence of a symmetric circuit family as required by
Theorem <ref>: Firstly, we assume the circuits here to be fully symmetric, i.e. they are stabilised by every permutation in $\Sym_n$; in Theorem <ref>, the circuits need only have a polynomial orbit with respect to the automorphisms of the base graph, so they are stabilised by many, but not necessarily by all these automorphisms. Secondly, in Theorem <ref>, we only have a logarithmic bound on the fan-in dimension, but it is not clear that this also entails a bound on the orbit-wise number of children and parents of each gate as in Property 3 above. Nevertheless, we hope that this negative result for the existence of fully symmetric bounded-degree XOR-circuits is a useful starting point to rule out further circuit classes over hypercubes, and eventually defeat all circuits from Theorem <ref>.

§.§ Supporting partitions of permutation groups

The proof of the theorem relies on group-theoretic techniques, which allow us to approximate every permutation group of index $\text{poly}(2^n)$ by a product of large alternating groups. This idea comes from Anderson and Dawar's paper on symmetric circuits and fixed-point logic <cit.>. There, it is shown that any group $G \leq \Sym_n$ has a unique coarsest supporting partition $\Sp(G)$. This is the coarsest partition of $[n]$ such that every $\pi \in \Sym_n$ which stabilises each part setwise is in $G$. Here, we extend this concept and define alternating supporting partitions. The alternating group $\Alt_n \leq \Sym_n$ is the group containing only permutations with even sign. A permutation has even sign if it inverts the order of an even number of pairs in $[n]$.

Let $A$ be a set and $\G \leq \Sym(A)$ be a permutation group acting on $A$. An alternating supporting partition of $\G$ is a partition $\Pp$ of $A$ such that

\[
\prod_{\stackrel{P \in \Pp}{|P| < 5 }} \Sym(P) \times \prod_{\stackrel{P \in \Pp}{|P| \geq 5 }} \Alt(P) \leq \G.
\]

The difference to the “standard” supporting partitions is that the odd permutations within the parts of an alternating supporting partition need not be contained in the supported group $\G$. On parts of size $< 5$, we require the full symmetric group to be in $\G$, because otherwise, the proof of the next lemma is problematic, and in our application, constant-size parts will not play a big role anyway.
We have to verify that alternating supporting partitions work just like the original supporting partitions from <cit.>. Concretely, the desirable properties are that there always exists a unique coarsest supporting partition of a group $G$ and that $G$ is sandwiched between the pointwise and the setwise stabiliser of that partition.

Each permutation group $\G \leq \Sym(A)$ has a unique coarsest alternating supporting partition, denoted $\Sp_A(\G)$.

The proof is similar to the one of Lemma 1 in <cit.>. We need to prove that for any two alternating supporting partitions $\Pp, \Pp'$, the finest partition of which both of them are refinements is still an alternating supporting partition. Then the lemma follows directly.
This “finest common coarsification” of $\Pp$ and $\Pp'$, denoted $\Ee(\Pp,\Pp')$ is defined like this: Let $\sim \subseteq A^2$ be the transitive closure of the relation “$a$ and $b$ occur together in some part $P$ of $\Pp$ or $\Pp'$”. The equivalence classes of $\sim$ are the parts of $\Ee(\Pp,\Pp') =: \Ee$. We want to show that any even permutation within any part $Q$ of $\Ee$ (that pointwise fixes everything outside of $Q$) is also in $\G$. We do this by proving: If $P \in \Pp, P' \in \Pp'$ have non-empty intersection, then $\Alt(P \cup P') \leq \G$.
Since $\Alt(P \cup P') $ is generated by pairs of transpositions $(x y)(x' y')$, it suffices to show that all such pairs are in $\G$. So consider $(x y)(x' y')$, for $x,y,x',y' \in P \cup P'$ pairwise distinct. We distinguish the following cases: If $x,x',y,y'$ are all in $P$ (or analogously, in $P'$), then $(x y)(x' y') \in \Alt(P) \leq \G$ (using that $\Pp$ is an alternating supporting partition of $\G$).

The next case is that $x \in P \setminus P'$, $y \in P' \setminus P$, and $x',y'$ are in the same part, say, both are in $P'$. In this case, let $z \in P \cap P'$, and $a,b \in P \setminus \{ x,z\}$ be two distinct elements (if such $a,b$ do not exist, then $|P| \leq 3$, and so $\Sym(P) \leq \G$, which means that the following argument works even without these $a,b$). It holds $(x y)(x' y') = (x z)(a b)(z y)(x' y')(x z)(a b)$. The number of transpositions within $P$ and within $P'$ is even (we always swap $a$ and $b$ when we swap $x$ and $z$, and we swap $x'$ and $y'$ together with $(z y)$), so this product is in $\Alt(P) \times \Alt(P')$ and therefore in $\G$, because both $\Pp$ and $\Pp'$ are supporting partitions of $\G$.

Another case is that $x,x' \in P \setminus P'$ and $y,y' \in P' \setminus P$. Let again $z \in P \cap P'$, and fix some $a,b \in P \setminus \{ x,x',z \}$ and $a',b' \in P' \setminus \{ y,y',z \}$. Again, if this is not possible, then $P$ and $P'$ are smaller than $5$ and so all permutations on them are in $\G$, which makes the next step only easier.
Consider $(x z)(a b)(z y)(a' b')(x z)(a b)(x' z)(a b)(z y')(a' b')(x' z)(a b)$. This is equal to $(x y)(x' y')$ and again in $\Alt(P) \times \Alt(P')$ and hence in $\G$.

It remains the case where $x,y \in P$ and $x',y' \in P'$. We can assume that $x,y \in P \setminus P'$ and $x',y' \in P'$ because $\Alt(P) \times \Alt(P') \leq \G$, and so we can move the elements that are to be swapped anywhere within $P$, $P'$, respectively. Then we can simulate the permutation $(x y)(x' y')$ by applying the previous case twice: First, we execute $(x x')(y y')$, and then $(x y')(y x')$. Both are in $\Alt(P) \times \Alt(P')$, as shown above, and hence, in total, we have $(x y)(x' y') \in \Alt(P) \times \Alt(P') \leq \G$.

So we have shown that we can take the union of two intersecting parts from $\Pp$ and $\Pp'$, and the alternating group on this union will also be in $\G$. Iterating this, we can show that $\Alt(Q) \leq \G$, for every $Q \in \Ee$, because all parts of $\Ee$ can be obtained by iteratively taking the union of intersecting parts of $\Pp$ and $\Pp'$. It remains to show that for all $Q \in \Ee$ with $|Q| < 5$, $\Sym(Q) \leq \G$. But this is clear since such parts $Q \in \Ee$ can only be the union of small parts $P \in \Pp$ and $P' \in \Pp'$. Then we have $\Sym(P) \leq \G$ and $\Sym(P') \leq \G$. We can easily see that every transposition in $\Sym(P \cup P')$ is also in $\G$ by arguing as above, just that we do not need dummy-transpositions anymore in order to keep the sign even.

For any $\G \leq \Sym(A)$, and any $\sigma \in \Sym(A), \sigma \Sp_A(\G) = \Sp_A(\sigma G \sigma^{-1})$.

As mentioned in <cit.>, it holds $\sigma \Ee(\Pp,\Pp') = \Ee(\sigma \Pp, \sigma \Pp')$ for any $\sigma \in \Sym(A)$. Therefore, it remains to show that for any alternating supporting partition $\Pp$ of $\G$, and any $\sigma \in \Sym(A)$, $\sigma \Pp$ is an alternating supporting partition of $\sigma G \sigma^{-1}$. So let

\[
\pi \in \prod_{\stackrel{P \in \sigma \Pp}{|P| < 5 }} \Sym(P) \times \prod_{\stackrel{P \in \sigma \Pp}{|P| \geq 5 }} \Alt(P).
\]

\[
(\sigma^{-1} \pi \sigma) \in \prod_{\stackrel{P \in \Pp}{|P| < 5 }} \Sym(P) \times \prod_{\stackrel{P \in \Pp}{|P| \geq 5 }} \Alt(P).
\]

Therefore, $(\sigma^{-1} \pi \sigma) \in \G$ because $\Pp$ is an alternating supporting partition of $\G$. Consequently, $\pi \in \sigma \G \sigma^{-1}$, and so, $\sigma \Pp$ is an alternating supporting partition of $ \sigma \G \sigma^{-1}$.

Let $\G \leq \Sym(A)$. Then:

\[	\prod_{\stackrel{P \in \Sp_A}{|P| < 5 }} \Sym(P) \times \prod_{\stackrel{P \in \Sp_A}{|P| \geq 5 }} \Alt(P) \leq \G \leq \Stab(\Sp_A(\G)).\]

The first part is by definition of alternating supporting partitions. For the second part, let $\sigma \in G$. Then $\sigma G \sigma^{-1} = G$. So $\sigma \Sp_A(G) = \Sp_A(G)$ by the preceding lemma.

Thus, every group has a unique coarsest alternating supporting partition and is sandwiched between its pointwise and setwise stabiliser. Now the reason why we introduce these alternating supporting partitions is because they have a useful property: For groups of index $\leq \text{poly}(2^n)$, the coarsest alternating supporting partition has at most a sublinear number of singleton parts. The proof of this hinges on the following lemma, which we only prove in the appendix because this is quite lengthy and requires a few more prerequisites. In short, the lemma works similarly as Theorem 5.2 B in <cit.>. The difference is that here, the index is upper-bounded by $2^{nk}$, whereas in <cit.>, the bound is much smaller, namely only $n^k$. In the following, we use the notation from <cit.>, so for any group $H \leq \Sym_n$, and any subset $\Delta \subseteq [n]$, $H^{(\Delta)}$ denotes the subgroup of $H$ that fixes $\Delta$ pointwise.

Let $(G_n)_{n \in \bbN}$ be a family of groups such that for all $n$, $G_n \leq \Sym_n$. Assume that there exists some constant $k \in \bbN$ such that asymptotically, $[\Sym_n : G_n] \leq 2^{nk}$.

Then there exists a constant $0 < c \leq 1$ such that for all large enough $n$, $G_n$ has a subgroup $H_n$ such that $\Alt(A) \leq H_n^{([n] \setminus A)}$ for some $H_n$-orbit $A$ of size $|A| \geq cn$.

With this lemma, one can show:

Let $k \in \bbN$ be a constant and $(G_n)_{n \in \bbN}$ be a family of groups such that $G_n \leq \Sym_n$ and for all large enough $n$, $[\Sym_n : G_n] \leq 2^{nk}$. Then the number of singleton parts in $\Sp_A(G_n)$ grows at most sublinearly. In other words: There is no constant $0 < c \leq n$ such that for all large enough $n$, there exists a $\Delta_n \subseteq [n]$ of size $|\Delta_n| \geq cn$ on which $\Sp_A(G_n)$ contains only singleton parts.

Proof sketch. We let $\Delta_n \subseteq [n]$ be the set of points which are in singleton parts of $\Sp_A(G_n)$. For a contradiction, we assume that $|\Delta_n|$ grows linearly. Then we consider the action of $G_n$ on $\Delta_n$, while every point outside of $\Delta_n$ is fixed. Denote this subgroup of $G_n$ as $H_n$. Then
Lemma <ref> applied to $H_n$ yields a contradiction. One can show that $[\Sym(\Delta_n) : H_n] \leq 2^{nk}$, just like it is assumed for the index of $G_n$ in $\Sym_n$. Hence, Lemma <ref> entails that $H_n$ contains an alternating group on a linearly-sized orbit $A$. However, then $A$ would be a single part in $\Sp_A(G_n)$, which contradicts the fact that the permutation domain of $H_n$ is the set of positions in singleton parts. The full proof is in the appendix.

Assume for a contradiction that there was a constant $0 < c \leq 1$ such that for every large enough $n$, there exists a subset $\Delta_n \subseteq [n]$ of size $|\Delta_n| \geq cn$, which is precisely the set of elements in singleton parts in $\Sp_A(G_n)$. In the following, we assume that the size of $\Delta_n$ is not only lower-bounded linearly, but that there also exists some other constant $1 > d > c$ such that $|\Delta_n| \leq dn$, for all large enough $n$. We deal with the other case in the end.

Let $H_n := (G_n^{([n] \setminus \Delta)})^{\Delta}$ be the subgroup of $G_n$ that fixes every point outside of $\Delta$, restricted to its action on $\Delta$. We now show that $[\Sym(\Delta) : H_n] > 2^{nk}$, for every $k \in \bbN$. Indeed, if there were a $k \in \bbN$ such that $[\Sym(\Delta) : H_n] \leq 2^{nk}$ for all large enough $n$, then by Lemma <ref>, all the $H_n$ would have a subgroup $H'_n$ containing the alternating group on an orbit $A$ of size $|A| \geq c' \cdot |\Delta|$, where $c'$ is the constant from the lemma. More precisely, $\Alt(A) \leq H_n'^{(\Delta \setminus A)}$. Thus, every even permutation on $A$ (that fixes everything in $\Delta$ outside of $A$) would be contained in $H_n$, and since $H_n$ is a subgroup of $G_n$ that fixes everything outside of $\Delta$, this means that $\Alt(A) \leq G^{([n] \setminus A)}$. But then, $A \subseteq \Delta$ would be a part of the coarsest alternating supporting partition $\Sp_A(G_n)$. This contradicts the fact that $\Sp_A(G_n)$ only has singleton parts on $\Delta$. Therefore, we must have that $[\Sym(\Delta_n) : H_n] > 2^{nk}$, for every $k \in \bbN$.

As a next step, we calculate that this entails a violation of the assumption that $[\Sym_n : G_n]$ can be upper-bounded by $2^{nk}$, for some $k$. Namely, if $[\Sym(\Delta_n) : H_n] > 2^{nk}$ for all $k \in \bbN$, then $|H_n| < \frac{|\Delta_n|!}{2^{nk}}$, for every choice of $k$. Then we also have $|G_n| < \frac{|\Delta_n|!}{2^{nk}} \cdot (n-|\Delta_n|)!$. This is because by Lemma <ref>, every element of $G_n$ stabilises $\Sp_A(G_n)$ setwise and so in particular, maps singleton parts only to singleton parts; therefore, $[n] \setminus \Delta$ is a union of $G$-orbits and so $H_n$ is normal in $G_n$. It follows for the index, for every $k \in \bbN$:

\begin{align*}
[\Sym_n : G_n] &= \frac{n!}{|G_n|} > \frac{n! \cdot 2^{nk}}{|\Delta_n|! \cdot (n-|\Delta_n|)!}.
\end{align*}

Since $cn \leq |\Delta_n| \leq dn$, we have $|\Delta_n| \leq dn$ and $n-|\Delta_n| \leq (1-c)n$. So we can 	continue:

\begin{align*}
\frac{n! \cdot 2^{nk}}{|\Delta_n|! \cdot (n-|\Delta_n|)!} &\geq \frac{n! \cdot 2^{nk}}{(dn)! \cdot ((1-c)n)!}\\
& \approx 2^{nk} \cdot \Big( \frac{1}{d}\Big)^{dn} \cdot \Big( \frac{1}{1-c}\Big)^{(1-c)n} \cdot \frac{1}{\sqrt{2\pi \cdot d(1-c) \cdot n}}
\end{align*}

Since $d < 1$ and $(1-c) < 1$, the above product is greater than $2^{nk}$ (for large enough $n$). Because this lower bound for $[\Sym_n : G_n]$ holds for every $k \in \bbN$, we can conclude that $[\Sym_n : G_n] > 2^{nk}$, for every $k$. But the assumption of Theorem <ref> says that there exists a $k \in \bbN$ such that for all large enough $n$, $[\Sym_n : G_n] \leq 2^{nk}$. This is a contradiction. This proves the theorem in case that $|\Delta_n|$ can be upper-bounded by some linear function $d \cdot n$, for $d < 1$. The case that $|\Delta_n| > dn$, for all $d < 1$, cannot occur: Lemma <ref> applied to $G_n$ states that $G_n$ contains an alternating group of linear degree (which fixes the rest pointwise). Therefore, for all large enough $n$, $\Sp_A(G_n)$ must have at least one part of linear size. So it is impossible that all but sublinearly many elements of $[n]$ are in singleton parts in $\Sp_A(G_n)$.

§.§ The cancellation of input bits in highly symmetric circuits

We now return to the proof of Theorem <ref>. The alternating supporting partitions are used to approximate the stabiliser groups of the gates.
For a gate $g \in V_{C_n}$, we denote by $\Sp_A(g)$ the coarsest alternating supporting partition of the group

\[
\Stab_n(g) := \{  \pi \in \Sym_n \mid \pi \text{ extends to an automorphism of } C_n \text{ that fixes } g \}.
\]

Here, we mean that at least one of the automorphisms that $\pi$ extends to fixes $g$. It can be seen that $\Stab_n(g)$ is indeed a subgroup of $\Sym_n$ because it contains the identity permutation, and: If $\pi, \pi' \in \Stab_n(g)$, then there exist circuit automorphisms $\sigma, \sigma'$ that $\pi, \pi'$ extend to such that $\sigma(g) = \sigma'(g) = g$. Thus, $\sigma \circ \sigma'$ fixes $g$ and is a circuit automorphism that $\pi \circ \pi'$ extends to. Thus, $\Stab_n(g) \leq \Sym_n$.

Importantly, $\Stab_n(g) \leq \Stab(\Sp_A(g))$ (Lemma <ref>), so every permutation in $\Stab_n(g)$ acts as a permutation on the parts of $\Sp_A(g)$. The supporting partition of an automorphic image of a gate can be obtained by applying a corresponding permutation in $\Sym_n$ to the supporting partition:

Let $g, \sigma g$ be two gates in $C_n$, for a $\sigma \in \Aut(C_n)$. Let $\pi \in \Sym_n$ be a permutation that extends to the circuit automorphism $\sigma$. Then

\[
\Sp_A(\sigma g) = \pi (\Sp_A(g)).
\]

By Lemma <ref>, the partition $\pi \Sp_A(g)$ is the coarsest alternating supporting partition of the group $\pi \Stab_n(g) \pi^{-1}$. It holds $\pi \Stab_n(g) \pi^{-1} = \Stab_n(\sigma g)$.

Next, we would like to formalise what it means that a given input gate $g$ cancels itself out in the circuit:

Let $g$ be an input gate of an XOR-circuit $C$. The circuit $C$ is sensitive to the input gate $g$ if and only if the number of distinct paths from the root to $g$ is odd.

Via induction on the number of gates in $C$. In a circuit where $g$ is the root, there is only one path and the input determines the output. The smallest possible case where the number of paths from the root to $g$ is even is if $C$ consists of a root with two children $h_1,h_2$, and one input gate $g$ that is the child of both $h_1$ and $h_2$. Clearly, the input bit is canceled in the root.

For the inductive step, let $h_1,...,h_m$ be the children of the root $r$. Let $p_i$ be the number of distinct paths from $h_i$ to the input $g$. By the induction hypothesis, the output of $h_i$ depends on $g$ iff $p_i$ is odd (use the statement for the smaller subcircuit rooted at $h_i$). The number of distinct paths from $r$ to $g$ is $\sum p_i$. That number is even iff an even number of the $p_i$ is odd. Then the input $g$ has no influence on the value computed at $r$ because only the $h_i$ with $p_i$ odd are sensitive to $g$, and these effects cancel at $r$ because it is an even number. If an odd number of the $p_i$ is odd, then $r$ is sensitive to $g$.

Thus, our goal is to prove that the number of paths between the root and each input gate labelled with a “too balanced edge” of $\H_n$ is even.

. As one would expect, these path counts are invariant under the symmetries of the circuit.

Let $g,g'$ be two gates in $C_n$ in the same $\Aut(C_n)$-orbit. Then the number of paths from the root to $g$ is the same as from the root to $g'$.

This is necessarily the case since every automorphism fixes the root and maps paths to paths and “non-paths” to non-paths.

Now the technical theorem that we want to prove in the next step reads as follows. From it, Theorem <ref> follows with Lemma <ref>.

Let $(C_n)_{n \in \bbN}$ be a family of XOR-circuits with the properties mentioned in Theorem <ref>.
Let a gate $g_n$ in every $C_n$ and a constant $\epsilon > 0$ be fixed such that $\Sp_A(g_n)$ contains at least two parts of size $\geq \epsilon \cdot n$.

Then for all large enough $n$, the number of distinct paths from the root of $C_n$ to $g_n$ is even.

The proof idea is vaguely similar to a technique known as “bottleneck counting”, that has been used in proof complexity to establish lower bounds for resolution.
Roughly speaking, we associate with every gate in a circuit a certain quantity of which we know that it must be high in the root and much lower in the input gates. Furthermore, we will prove that this quantity can only change by a small amount as we move from a gate to its parents. In other words: The quantity cannot “jump” from the low value at the leafs to the high value at the root, but it has to pass through many intermediate values in the middle of the circuit. We will then show that certain intermediate values, which must necessarily occur at some gates, entail that the number of paths from the root to the gate is even.

First, here is an observation about supporting partitions (or partitions in general). In most cases, their orbit has at least quadratic size, unless the partition has a very particular shape.

Let $\Pp$ be some partition of $[n]$, for some $n \geq 4$, and let $\Stab_n(\Pp) \leq \Alt_n$ denote the setwise stabiliser of the partition in the alternating group. Then the orbit size of $\Pp$, that is, $(1/2)n!/|\Stab_n(\Pp)|$, is at least $\Omega(n^2)$ unless $\Pp$ has one of the following forms:

* $\Pp = \{ [n] \}$.

* $\Pp = \{ \{s\}, [n] \setminus \{s\}  \}$, for some $s \in [n]$.

* $\Pp = \{ \{s\} \mid s \in [n]  \}$.

Proof sketch. It is easy to see that in each of the three cases above, the $\Alt_n$-orbit of $\Pp$ has size one or $n$ (since we are assuming $n$ to be large enough such that $\Alt_n$ acts transitively on $[n]$). It remains to show that the orbit size is at least quadratic if $\Pp$ has any other form. In that case, $\Pp$ must contain some part $P$ of size $|P| \geq 2$, whose complement in $[n]$ is also of size $\geq 2$. Since $\Alt_n$ is transitive on the subsets of $[n]$ (for each fixed subset-size), the part $P$ has $\binom{n}{|P|}$ many $\Alt_n$-images, which is in $\Omega(n^2)$. If $|P| > n/2$, then we are done because any permutation that does not map $P$ to itself is not in $\Stab_n(\Pp)$ then, and so the $\Alt_n$-orbit of $\Pp_n$ is as large as claimed. Otherwise, if $|P| \leq n/2$, then $|\Stab_n(\Pp)| \leq (1/2) \cdot k! \cdot (|P|!)^k \cdot (n-k|P|)!$, where $k$ is the number of parts of size $|P|$ in $\Pp$. One can show that this is maximised for $k=n/|P|$ or $k=1$. Now the rest is just a calculation of a suitable lower bound on the orbit size using the Orbit-Stabiliser theorem.

It is easy to see that in each of the three cases above, the $\Alt_n$-orbit of $\Pp$ has size one or $n$ (since we are assuming $n$ to be large enough such that $\Alt_n$ acts transitively on $[n]$). It remains to show that the orbit-size is at least quadratic if $\Pp$ has any other form.
In that case, $\Pp$ must contain some part $P$ of size $|P| \geq 2$, whose complement in $[n]$ is also of size $\geq 2$. Since $\Alt_n$ is transitive on the subsets of $[n]$ (for each fixed subset-size), the part $P$ has $\binom{n}{|P|}$ many $\Alt_n$-images, which is in $\Omega(n^2)$. If $|P| > n/2$, then we are done because any permutation that does not map $P$ to itself is not in $\Stab_n(\Pp)$ then, and so the $\Alt_n$-orbit of $\Pp_n$ is as large as claimed.

Otherwise, if $|P| \leq n/2$, we estimate $|\Stab_n(\Pp)|$ as follows: Let $k$ be the number of parts in $\Pp$ of size $|P|$. Then

\[
|\Stab_n(\Pp)| \leq (1/2) \cdot k! \cdot (|P|!)^k \cdot (n-k|P|)!
\]

This is maximised for $k = n/|P|$ or $k = 1$ because if $k < \frac{n}{|P|}$, it can be calculated that decreasing $k$ by one makes the expression larger, so if $k$ is not largest possible, then the bound for $\Stab_n(\Pp)$ is maximised by making $k$ as small as possible.

We have already dealt with the case that $k=1$ above (where we assumed $|P|$ to be so large that no other part of this size can exist). Therefore, assume now that $k = n/|P|$.
Then we get for the orbit-size of $\Pp$:

\begin{align*}
&\frac{n!}{(n/|P|)! \cdot (|P|!)^{n/|P|}} \approx \frac{(n/e)^n \cdot \sqrt{2\pi n} }{ (n/|P|)! \cdot (|P|/e)^n \cdot \sqrt{2\pi|P|}^{(n/|P|)} } \\
\approx& \Big(\frac{n}{|P|} \Big)^n \cdot \frac{\sqrt{2\pi n}}{\Big(\frac{n\sqrt{2\pi|P|} }{|P| \cdot e}\Big)^{n/|P|}}\\
\geq & \Big(\frac{n}{|P|} \Big)^n \cdot \Big(\frac{\sqrt{|P|} \cdot e}{ n\sqrt{2\pi}}\Big)^{n/|P|}\\
= &  \Big( \frac{n^{1-1/|P|} \cdot e^{1/|P|} }{|P|^{1-1/(2|P|)} \cdot \sqrt{2\pi}^{1/|P|}}  \Big)^n
\end{align*}

We have $2 \leq |P| \leq n/2$, so the fraction is at least $2$, which makes the whole term certainly greater than $n$.

In combination with our assumption that orbits of parents and children have size $\Oo(n)$, this lemma will help us to get a handle on the interplay of the supporting partitions of parent and child gates.
We now define the quantity that we associate with each gate, as described above. This quantity is actually rather a vector, that we call the size profile (of the supporting partition). It is invariant under symmetries, so we define this measure not for individual gates but for their entire orbits. For a gate $g \in V_{C_n}$, we denote by $[g]$ its $\Aut(C_n)$-orbit in $V_{C_n}$.
A size profile is a mapping $\zeta : \bbN \lra \bbN$. For an orbit $[g]$, we define $\zeta[g] : \bbN \lra \bbN$ as follows:

\[
\zeta[g](i) := |\{ P \in \Sp_A(g) \mid |P| = i \}|.
\]

Due to Lemma <ref>, this definition is indeed independent of the choice of the representative $g$ of the orbit.
Note that, as we promised earlier, the measure $\zeta$ differs considerably between the root and the input gates of a circuit. For the root $r$, $\zeta[r](n) = 1$, and $\zeta[r](i) = 0$ for all $i < n$. This is because our circuits are invariant under all permutations in $\Sym_n$ by assumption, so the root is stabilised by all permutations, and hence its coarsest alternating supporting partition contains just one large part. For the input gates, by contrast, we know that their supporting partition always has two parts: If an input gate is labelled with a hypercube edge, say, $\{0^a1^{n-a}, 0^{a-1}1^{n-a+1}\}$, then its supporting partition is $\{ \{ 1,...,a-1 \}, \{a \}, \{a+1,...,n \} \}$. Unless either $a$ or $b$ are very small, this partition has two large parts. We will prove that, with each layer in the circuit, the size profile of the gates cannot change very much, so for example, the largest part will grow by one, and another part will shrink by one, as we go one layer up in the circuit. As a consequence, in the middle of the circuit, we must encounter several different part sizes in the supporting partitions until we can reach the supporting partition $\{ [n]\}$ at the root. In particular, we will encounter even part sizes in some gates, and when that happens, this more or less leads to an even number of paths.

Before we come to this heart of the proof, we observe that gates in the same orbit also have the same number of parents from every orbit:

Let $g,g'$ be two gates in the same $\Aut(C_n)$-orbit. Let $h \in E_C g$ be a parent of $g$. Then $|\Orbit(h) \cap E_Cg| = |\Orbit(h) \cap E_Cg'|$.

Let $\sigma \in \Aut(C_n)$ be such that $g' = \sigma g$. Then $\sigma(\Orbit(h) \cap E_Cg) \subseteq \Orbit(h) \cap E_C g'$. Conversely, $\sigma^{-1}(\Orbit(h) \cap E_C g') \subseteq \Orbit(h) \cap E_Cg$.

The next lemma is the key in our proof. It tells us precisely how the size-profiles of the gates can differ between children and parents. Essentially, the size of large parts can only change by at most one.

Let $0 < \epsilon < 1$ be any constant. Let $g$ a gate in $C_n$, $h$ a parent of $g$. Assume that $|\Orbit_{(g)}(h)| \in \Oo(n)$ and $|\Orbit_{(h)}(g)| \in \Oo(n)$.
Let $\Delta : \{ m \in \bbN \mid m \geq \epsilon \cdot n \} \lra \bbN$ be the function defined as $\Delta(s) := \zeta[h](s) - \zeta[g](s)$. For all large enough $n \in \bbN$ and every $s \geq \epsilon \cdot n$ it holds:

* $|\Delta(s)| \leq 2$.

* If $\Delta(s) = 2$, then $\Delta(s+1) = -1, \Delta(s-1) = -1$. If additionally $s$ is odd, then $|\Orbit_{(g)}(h)|$ is even.

* If $\Delta(s) = -2$, then $\Delta(s+1) = 1, \Delta(s-1) = 1$. If additionally $s$ is even, then $|\Orbit_{(g)}(h)|$ is even.

* If no value of $\Delta$ is $2$ or $-2$, then one of the following is possible:

* If $\Delta(s) = 1$, then $\Delta(s-1) = -1$ or $\Delta(s+1) = -1$. In case that $s$ is odd and $\Delta(s+1) = -1$, then $|\Orbit_{(g)}(h)|$ is even.

* If $\Delta(s) = -1$, then $\Delta(s-1) = 1$ or $\Delta(s+1) = 1$. In case that $s$ is even and $\Delta(s-1) = 1$, then $|\Orbit_{(g)}(h)|$ is even.

* If $\Delta(s) \neq 0$, then for all other $s'$ except the ones mentioned in the cases above, it holds $\Delta(s') = 0$.

Let $\Sp_A^*(g) \subseteq \Sp_A(g)$ be the set of parts of size $\geq \epsilon \cdot n$ and $\Sp_A^*(h) \subseteq \Sp(h)_A$ the parts of size $\geq \epsilon \cdot n -1$ in $\Sp_A(h)$.

Claim: There is a bijection $\gamma : \Sp_A^*(g) \lra \Sp_A^*(h)$ such that:

* For every $Q \in \Sp_A^*(g)$, it holds $|\gamma(Q) \cap Q| \geq |Q|-1$.

* For every $Q \in \Sp_A^*(g)$, it holds $|\gamma(Q) \setminus Q| \leq 1$.

* There is at most one part $Q \in \Sp_A^*(g)$ such that $|\gamma(Q) \cap Q| = |Q|-1$.

* There is at most one part $Q \in \Sp_A^*(g)$ such that $|\gamma(Q) \setminus Q| = 1$.

[line width = 0.5mm]
[fill=green!20] (0,0) rectangle (2.8,-0.75) node[pos=.5] $\gamma(Q)$;
[fill=green!20] (-0.2,-1) rectangle (2.6,-1.75) node[pos=.5] $Q$;

(0,0) – (-1,0);
(0,-0.75) – (-1,-0.75);

(0,-1) – (-1,-1);
(0,-1.75) – (-1,-1.75);

(2.8,0) – (3.8,0);
(2.8,-0.75) – (3.8,-0.75);

(2.6,-1) – (3.8,-1);
(2.6,-1.75) – (3.8,-1.75);

This is the most extreme way how $Q$ and $\gamma(Q)$ may differ: Each has at most one element that is not shared with the other part.

Proof of claim: Construct $\gamma$ by defining $\gamma(Q) \in \Sp_A^*(h)$ as the part whose intersection with $Q$ is largest possible. This is well-defined because there are only two cases how $\Sp_A(h)|_Q$ can look like: It either consists of one part or we have $\Sp_A(h)|_Q = \{\{s\}, Q \setminus \{s\} \}$, for some $s \in Q$.
Everything else is ruled out by Lemma <ref> and Theorem <ref>. This is because by assumption, only $\Oo(n)$ many parents of $g$ are in $\Orbit_{(g)}(h)$. Therefore, the restriction of $\Sp_A(h)$ to $Q$, denoted $\Sp_A(h)|_Q$, can have at most $\Oo(n)$ many images under $\Alt(Q)$: Namely, every permutation in $\Alt(Q)$ extends to a circuit automorphism that fixes $g$ because $Q$ is a part in $\Sp_A(g)$. Moreover, by Lemma <ref>, any two distinct $\Alt(Q)$-images of $\Sp_A(h)|_Q$ must be the $Q$-restrictions of supporting partitions of distinct parents of $g$. So indeed, $\Orbit_{(g)}(h)$ contains at least as many gates as the size of the $\Alt(Q)$-orbit of $\Sp_A(h)|_Q$. This size can only be in $\Oo(n)$ if $\Sp_A(h)|_Q$ consists of singletons only or has just one big part or if it as a one-vs-rest split (because of Lemma <ref>, where we also use that $|Q| \in \Theta(n)$). The case that $\Sp_A(h)|_Q$ consists only of singletons cannot happen because $Q$ has linear size and by Theorem <ref>, $\Sp_A(h)$ has at most $o(n)$ many singletons. Therefore, $\Sp_A(h)|_Q$ indeed either consists of one part or we have $\Sp_A(h)|_Q = \{\{s\}, Q \setminus \{s\} \}$, for some $s \in Q$. Thus, $\gamma(Q)$ is well-defined (and indeed, every part $\gamma(Q) \in \Sp_A(h)$ has size $\geq \epsilon \cdot n -1$).

The above reasoning also directly proves statement (a). Statement (b) follows in a similar way because if it were not true, then $\Sp_A(g)|_{\gamma(Q)}$ would have $\Omega(n^2)$ many images under $\Alt(\gamma(Q))$ (again by combining Theorem <ref> and Lemma <ref>), resulting in $\Orbit_{(h)}(g)$ being too large.

We show that $\gamma$ is injective: If it were not, then there would be some $P \in \Sp_A^*(h)$ and $Q_1, Q_2 \in \Sp_A^*(g)$ such that $|Q_1 \cap P| \geq |Q_1|-1$ and $|Q_2 \cap P| \geq |Q_2|-1$. This is impossible because then, by Lemma <ref>, $\Sp_A(g)|_P$ has $\Omega(n^2)$ many automorphic images under $\Alt(P)$, but $\Alt(P)$ fixes $h$, so $h$ has more than $\Oo(n)$ many children in $\Orbit_{(h)}(g)$, which is a contradiction.

Also, $\gamma$ is surjective: Suppose there were a part $P \in \Sp_A(h)$ of size $\geq g(n) - 1$ that has no preimage. Then $\Sp_A(g)|_{P}$ must consist of parts smaller than $\epsilon \cdot n$.
Then again, $\Sp_A(g)|_{P}$ has $\Omega(n^2)$ many images under $\Alt(P)$ by Lemma <ref> (using also that the number of singleton parts in $\Sp_A(g)$ is sublinear and hence less than $|P|$ by Theorem <ref>).

If statement (c) were not true, then there would be two parts $Q_1, Q_2 \in \Sp_A^*(g)$ such that $|\gamma(Q_i) \cap Q_i| = |Q_i|-1$. Then $\Alt(Q_1) \times \Alt(Q_2)$ fixes $g$ but generates $\Omega(n^2)$ many distinct automorphic images of $\Sp_A(h)$. Then again, $|\Orbit_{(g)}(h)|$ is greater than $\Oo(n)$, which contradicts the assumptions of the lemma.

Similarly, statement (d) is shown: If it were not true, then $h$ would have too many children in $\Orbit_{(h)}(g)$. This proves the claim.

Now with the claim we see that there are five possible cases:

* $\gamma(Q) = Q$ for all $Q \in \Sp_A^*(g)$.

* There is one part $Q \in \Sp_A^*(g)$ such that $|\gamma(Q) \cap Q| = |Q|-1$ and $\gamma(Q) \subseteq Q$, and for all other parts $Q'$, $\gamma(Q') = Q'$.

* There is one part $Q$ with $|\gamma(Q) \setminus Q| = 1$ and $\gamma(Q) \supseteq Q$, and for all other parts $Q'$, $\gamma(Q') = Q'$.

* There is one part $Q$ that satisfies $|\gamma(Q) \cap Q| = |Q|-1$ and $|\gamma(Q) \setminus Q| = 1$. For all other parts $Q'$, $\gamma(Q') = Q'$.

* There is one part $Q_1$ that satisfies $|\gamma(Q_1) \cap Q_1| = |Q_1|-1$ (and $\gamma(Q_1) \subseteq Q_1$), and another part $Q_2$ that satisfies $|\gamma(Q_2) \setminus Q_2| = 1$ (and $Q_2 \subseteq \gamma(Q_2)$), and for all other parts $Q'$, $\gamma(Q') = Q'$.

In Case 1, the $\Delta$-vector is zero.

In Case 2, we have $\Delta(|Q|) = -1$ and $\Delta(|Q|-1) = 1$, and all other entries of $\Delta$ are zero.

In Case 3, we have $\Delta(|Q|) = -1$ and $\Delta(|Q|+1) = 1$, and all other entries of $\Delta$ are zero.

In Case 4, the $\Delta$-vector is zero.

In Case 5, we have to distinguish several cases. If $|Q_1| = |Q_2|$, then $\Delta(|Q_1|) = -2$ and $\Delta(|Q_1|-1) = 1, \Delta(|Q_1|+1) = 1$. If $|Q_1| \neq |Q_2|$ and $|Q_1|-1 \neq |Q_2|+1$ , then $\Delta(|Q_1|) = -1, \Delta(|Q_2|) = -1, \Delta(|Q_1|-1) = 1, \Delta(|Q_2|+1) = 1$. If $|Q_1| = |Q_2|+2$, then $\Delta(|Q_1|) = -1, \Delta(|Q_2|) = -1, \Delta(|Q_1|-1) = 2$.