%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{87}
\addbibresource{matroid.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}



\usepackage{bm}

\input{header_fpsac}

%% define your title in the usual way
\title{Undecidability of $\bm{c}$-Arrangement Matroid Representations}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Lukas K\"uhne\thanks{\href{mailto:lukas.kuehne@mail.huji.ac.il}{lukas.kuehne@mail.huji.ac.il} Supported by a Minerva fellowship of the Max Planck Society, the Studienstiftung des deutschen Volkes and by ERC StG 716424 -- CASe.}\addressmark{1} \and Geva Yashfe\thanks{\href{mailto:geva.yashfe@mail.huji.ac.il}{geva.yashfe@mail.huji.ac.il} Supported by the ISF grant 1050/16.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Giv'at Ram, Jerusalem, Israel}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)

\abstract {A $c$-arrangement is an arrangement of dimension-$c$ subspaces such that all their sums have dimension a multiple of $c$. Matroids arising as normalized rank functions of $c$-arrangements are also known as multilinear matroids. We prove that there is no algorithm to decide whether a matroid is multilinear. In particular there is no algorithm to decide whether there exists a representable multiple of a given polymatroid.}

%% put your French abstract here, or comment this out if you don't have one

%% put your keywords here, or comment this out if you don't have them yet
\keywords{subspace arrangements, $c$-arrangements, matroids, polymatroids, word problems}

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
\section{Introduction} \label{sec:Intro}

The main objects in this extended abstract are matroids and their generalizations polymatroids.
\begin{defn}\label{def:matroid}
	A \emph{polymatroid} is a pair of a ground set $E$ together with a rank function $r:\mathcal{P}(E) \rightarrow \R$ such that $r$ is
	\begin{enumerate}
		\item \emph{monotone}, i.e.\ for each $S\subseteq T \subseteq E$ it holds that $r(S) \leq r(T)$ and 
		\item \emph{submodular}, i.e.\ for each $S,T\subseteq E$ it holds that $r(S)+r(T) \ge r(S\cup T)+ r(S\cap T)$.
	\end{enumerate}
	The pair $(E,r)$ is a \emph{matroid} if $r$ takes only integer values and $r(S)\le |S|$ holds for all $S\subseteq E$.
\end{defn}
It is common to study matroid representations by vector configurations or equivalently hyperplane arrangements over some field, for an overview see~\cite[Chapter 6]{Oxl11}.
Goresky and MacPherson extended this notion by introducing \emph{$c$-arrangements} in the context of stratified Morse theory~\cite{GM88}.
For a fixed integer $c\ge 1$, these are arrangements of $c$-dimensional subspaces in a vector space over a field such that the dimension of each sum of a subset of these subspaces has dimension a multiple of $c$ (this is dual, but equivalent, to the definition of~\cite{GM88}).
This condition ensures that the associated normalized rank function is the rank function of a matroid.

Matroids which are representable as $c$-arrangements are also called \emph{multilinear matroids}. 
The following is the multilinear representability problem over a field $\F$ posed by Björner in~\cite{Bjo92}.
\begin{prob}\label{prob:c_realizability}
	Given a matroid $M$, does there exist a $c\ge 1$ such that $M$ admits a $c$-arrangement representation over $\F$?
\end{prob}

Our main contribution is a computability theoretic result for $c$-arrangement representations.
\begin{theorem}\label{thm:undecidable_matroids}
	The multilinear representability problem is undecidable.
	This is true for any field $\F$. 
	Moreover, the problem remains undecidable if the field remains unspecified, or is allowed to be taken from some given set.
\end{theorem}
Note that $c$-arrangement rank functions are polymatroids.
In particular, it is impossible to test whether a polymatroid $r:\mathcal{P}(E) \rightarrow \R$ has a positive multiple which admits a linear representation over any given field $\F$. 
Here a linear representation of a polymatroid $r$ on $E$ is a collection of subspaces $\{U_e\}_{e\in E}$ of a vector space $V$ such that $\dim\left(\sum_{s\in S}U_s\right) = r(S)$ holds for all $S \subseteq E$.
\subsubsection*{Motivation and Future Work}
A primary motivation for this work is that extensions of these results to limits of rank functions have implications for rank inequalities. The following is a "limit variant" of the above, over a single field:
\begin{prob}\label{prob:limit_c_realizability}
	Let $\F$ be a field. Given a polymatroid $M=(E,r)$, does there exist a sequence of polymatroids $(M_i)_{i=1}^\infty$ with $M_i = (E_i, r_i)$ such that each $M_i$ has a positive multiple $n_i \cdot r_i$ which is representable over $\F$ and such that $r = \lim_{i\to\infty}r_i$?
\end{prob}

For a given field $\F$, consider the set of all representable polymatroids on the ground set $[n]$, and identify their rank functions with points of $\R^{\mathcal{P}([n])}$.
The convex hull of these rank functions forms a convex cone $\Gamma_{n,\F}$, and its closure $\overline{\Gamma_{n,\F}}$ is therefore defined by the linear inequalities it satisfies.
These include Ingleton and Kinser's various inequalities (\cite{Ing69}, \cite{Kin09}). An undecidability result for the limit problem above would imply that there is no algorithm which, given $n\in \mathbb{N}$, outputs a finite set of linear inequalities defining $\overline{\Gamma_{n,\F}}$. It is not known whether these cones are polyhedral; undecidability for limits would give some evidence that they are not. We believe such a theorem can be proved with the methods presented here, and hope to include it in a version of our preprint in the near future.

Representable polymatroids are also representable as joint entropy functions of discrete random variables.
Thus, information theoretic inequalities such as the Zhang--Yeung inequalities are also rank inequalities of the cones $\overline{\Gamma_{n,\F}}$, see~\cite{ZY98}.
Limits of representable polymatroids are closely related to limits of entropy functions introduced by Mat\'{u}\v{s} as \emph{almost entropic matroids}~\cite{Mat07}. %For now, it seems difficult to extend our undecidability results to the entropic setting.

\subsubsection*{Main Ideas in the Proof}
The proof of \Cref{thm:undecidable_matroids} reduces subspace arrangement representability to the \emph{uniform word problem for finite groups} (UWPFG) which was shown to be undecidable by Slobodskoi~\cite{Slo81}.
\begin{description}
	\item[Instance] A finite presentation $\langle S\mid R\rangle$, that is $S$ is a finite set of generators and $R$ a finite set of relations in $S$, together with a word $w$ which is a product of elements in $S$ and their inverses.
	\item[Question] Does every group homomorphism from the group defined by the presentation $\langle S\mid R\rangle $ to a \emph{finite} group $G$ map $w$ to the identity in $G$?
\end{description}
The finite groups $G$ above can equivalently be replaced with matrix groups, by Mal'cev's theorem.

The main idea of the proof is a non-commutative von Staudt construction, encoding a set of multiplicative relations between \emph{matrices} of unspecified size.
This approach is inspired by the construction of Dowling geometries from finite groups~\cite{Dow73}.
 This yields combinatorial data and a corresponding representation problem ("weak" representation as a $c$-arrangement) which is easily shown to be undecidable. We then define an operation, which we call \emph{inflation}, that translates the "weak" problem into a finite set of $c$-arrangement representation problems.

The present note is an extended abstract. A preliminary version of the full paper is available on the arXiv~\cite{KY19}. Due to space limitations many details are omitted here, but all of them can be found in the preprint.

\section{Preliminaries}\label{sec:vS}

\begin{defn}\label{def:arr}
	Let $V$ be a vector space over a field $\F$ and consider a \emph{subspace arrangement} $\A=\{U_i\}_{i\in I}$ where each $U_i$ is a subspace of $V$. For $S \subseteq \A$, we use the notation $\A_S \coloneqq \sum_{U \in S}U$.
	\begin{enumerate}
		\item We call $\A$ a $c$-\emph{admissible arrangement}  if for any subset $X\subseteq \A$ the dimension of $\sum_{U\in X}U$ is a multiple of $c$. It is a $c$-\emph{arrangement} if in addition each of its subspaces has dimension $c$.
		\item For any $c\ge 1$ we denote by $r_{\A}^c$ the \emph{normalized} rank function $r_{\A}^c : \mathcal{P}(\A) \rightarrow \Q$ by setting $r_{\A}^c(X)\coloneqq \frac{1}{c}\dim (\A_X)$.
	\end{enumerate}
\end{defn}
Hence, an arrangement $\A$ of $c$-dimensional subspaces is a $c$-arrangement if and only if its normalized rank function $r_{\A}^c$ takes only integral values.
Next we state its relation to matroid representations.

\begin{defn}
	Fix a matroid $M$ on the ground set $E$ with rank function $r$.
	\begin{enumerate}
		\item A matroid $M=(E,r)$ is called \emph{multilinear} of order $c$ over a field $\F$ if there exists a \mbox{$c$-arrangement} $\A$ such that their (normalized) rank functions agree, i.e. $r=r_{\A}^c$ for a suitable identification of $E$ and $\A$.
		We say that the $c$-arrangement $\A$ \emph{represents} the matroid $M$ in that case.
		\item To define a weaker representability notion we additionally fix a basis $B$ of the matroid $M$.
		If there exists an arrangement $\A = \{A_e\}_{e\in E}$ of $c$-dimensional subspaces such that $r(X)\ge r_{\A}^c(X)$ holds for all subsets $X\subseteq E$  and $r(Y)= r_{\A}^c(Y)$ for all subsets $Y\subseteq E$ with $|Y\setminus B|\le 1$ we say that $\A$ \emph{weakly represents} $M$ with respect to the basis $B$.
		In this case, we also say $\A$ is a weak $c$-representation.
	\end{enumerate}
\end{defn}

%\begin{figure}[bh!]
%	\centering
%	\includegraphics[width=0.3\linewidth]{pics/triangle_matroid}
%	\caption{The geometric representation of a triangle matroid.
%		The families $\{x^{(1)},y^{(2)},z^{(3)}\}$ and $\{y^{(1)},x^{(2)},w^{(3)}\}$ form circuits of the matroid which as specified in \Cref{def:matroid_N} encodes the relations $yxz=1$ and $xyw=1$.
%	}
%	\label{fig:triangle_matroid}
%\end{figure}

\section{A Non-Commutative von Staudt Construction}\label{sec:staudt}
Before describing the details of the non-commutative von Staudt construction and its relation to subspace arrangements we state two short lemmas.

\begin{lemm}\label{lem:block_matrices}
	Let $\F$ be a field and $A,B,C\in M_k(\F)$ any $k\times k$ matrices. 
Then the block matrix $
		\begin{bsmallmatrix}
		-I_k & 0    &  C\\
		A    & -I_k &  0\\
		0    & B     & -I_k 
		\end{bsmallmatrix}$
		has rank $2k+\rk(BAC-I_k)$.			
\end{lemm}

\begin{lemm}\label{lem:rank_permuatation_matrix}
	Let $\sigma\in S_k$ be a permutation with no fixed points, i.e.\ a derangement, and $A_{\sigma}$ the corresponding $k\times k$ permutation matrix over some field $\F$.
	Then $\rk(A_{\sigma}-I_k)\ge \frac{k}{2}$.
\end{lemm}

\begin{defn}\label{def:triangle_matroid}
	A matroid $M$ is a \emph{triangle matroid} if it is of rank $3$ and there exists a basis $\{b^{(1)},b^{(2)},b^{(3)}\}$ such that all remaining elements of $M$ are contained in the flats spanned by $\{b^{(1)},b^{(2)}\}$, $\{b^{(1)},b^{(3)}\}$ or $\{b^{(2)},b^{(3)}\}$.
	We call the flats $\{b^{(1)},b^{(2)}\}$, $\{b^{(1)},b^{(3)}\}$ or $\{b^{(2)},b^{(3)}\}$ the \emph{sides} of the triangle.
\end{defn}
%\Cref{fig:triangle_matroid} depicts the geometric representation of a triangle matroid.
Before considering \mbox{$c$-arran}\-ge\-ment representations, we investigate weak subspace arrangement representations of a triangle matroid with respect to the basis $\{b^{(1)},b^{(2)},b^{(3)}\}$.
The triangle matroid will be constructed from a group presentation.

\begin{defn}\label{def:matroid_N}
	Let $\langle S\mid R \rangle $ be a finite presentation.
	Using some Tietze transformations if necessary, we can assume that any relation in $R$ is of length three.
	
	We now construct a triangle matroid $N_{S,R}$ on the ground set $E_{S,R}$ with the basis $B = \{b^{(1)}, b^{(2)}, b^{(3)}\}$ by describing its dependent flats $\mathcal{F}_{S,R}$ of rank $2$, where we regard the indices cyclically modulo $3$:
\begin{align*}
E_{S,R} \coloneqq 				   & \{b^{(i)}, e^{(i)}, x^{(i)}, x^{-1^{(i)}}\mid 1\le i \le 3\mbox{ and }x\in S  \}, \\
\mathcal{F}_{S,R} \coloneqq & \{\bigcup_{a\in E_{S,R}}\{a^{(i)} \}\cup \{b^{(i+1)}\}\mid  \mbox{ for any fixed }1\le i \le 3\} \,\cup \\
& \{ \{x^{(i)},x^{-1^{(j)}},e^{(k)}\}\mid \mbox{ for } x\in S\mbox{ and pairwise different  } 1\le i,j,k\le 3 \}\, \cup \\
& \{\{e^{(1)},e^{(2)},e^{(3)}\}\} \, \cup \{  \{x^{(2)},y^{(1)},z^{(3)}\} \mid \mbox{ for any } xyz \in R \}.
\end{align*}
\end{defn}
%The proofs of the following propositions in this section all use \Cref{lem:block_matrices} and follow standard ideas, though they become more technical in this setting. See for instance chapter 6 in \cite{Oxl11}.
%
%\begin{prop}\label{pro:G_weak_representation}
%	Let $\langle S\mid R \rangle $ be a group presentation with relations of length three and let $G$ be a finite group with a homomorphism $\phi: G_{S,R}\rightarrow G$.
%	Set $n\coloneqq |G|$.
%	Fix any field $\F$.
%	Then there exists an arrangement $\A_{G,\phi}$ of $n$-dimensional subspaces over $\F$ that weakly represents the matroid $N_{S,R}$ with respect to the basis $\{b^{(1)},b^{(2)},b^{(3)}\}$.
%\end{prop}
%
%The idea is to take the regular representation of the group $G$ on $\F^n$. This is just the action of $G$ on itself by left multiplication, linearized to an action by permutation matrices on a vector space of dimension $|G|$.
%
%\begin{prop}\label{pro:weak_representation_G}
%	Let $\langle S\mid R \rangle $ be a finite group presentation with relations of length three and consider the matroid $N_{S,R}$.
%	Any weak representation of $N_{S,R}$ with respect to the basis $\{b^{(1)},b^{(2)},b^{(3)}\}$ by a subspace arrangement $\A$ over a field $\F$ yields a group $G_{\A}$ and a group homomorphism $\phi_{\A}:G_{S,R}\rightarrow G_{\A}$.
%\end{prop}

In the following theorem we establish the connection between the UWPFG and weak $c$-arrangement representations.
Without loss of generality we can assume that that both the relations and the word $w$ are of the length three.

\begin{theorem}\label{theo:weak_undecidable}
	Consider a UWPFG instance given by finite presentation $\langle S\mid R \rangle $  and an element $w\in S$.
	Then, the answer to this instance is negative, i.e.\ there exists a finite group $G$ with a homomorphism $\phi: G_{S,R}\rightarrow G$ and $\phi(w)\neq e_G$, if and only if there exists a weak $c$-representation $\A=\{A_e\}_{e\in E_{S,R}}$ over a field $\F$ of the matroid $N_{S,R}$ with respect to the basis $\{b^{(1)},b^{(2)},b^{(3)}\}$ such that
	\begin{equation}\label{eq:rank_2}
	r^c_{\A}( \{w^{(1)},e^{(1)}\}) > 1.
	\end{equation}
\end{theorem}

This theorem crucially relies on Malcev's theorem, stating that finitely generated matrix groups are residually finite.
The reminder of the proof follows standard ideas, though they become more technical in this setting.
A frequently used tool is \Cref{lem:block_matrices} in connection with the circuits of the form $\{x^{(2)},y^{(1)},z^{(3)}\} $.
% See for instance chapter 6 in \cite{Oxl11}.

\section{Algebraic Inflation}

We develop an algebraic inflation technique to produce a $c$-arrangement from  a weak $c$-representation.
The inflation consists of two steps.
Both steps use an elementary inflation procedure which we describe first.

\subsection{Elementary Inflation}
Let $\mathcal{U}=\left\{ U_{e}\right\} _{e\in E}$ be a subspace arrangement, $c\in \N$ and $S\subseteq E$ a subset.
Furthermore, choose a vector space $W$ of dimension at least $c$.
Intuitively, we enlarge each subspace $U_e$ with $e\in S$ by a generic $c$-dimensional subspace of $W$.

Formally, denote the ambient vector space of $\U$ by $V$ and embed $V$ together with the arrangement $\U$ in a larger vector space $\widetilde{V}$ of large enough dimension.
Let $S\subseteq E$ and $W\le \widetilde{V}$ be a subspace of dimension at least $c$.
Note that $W$ may intersect $V$ non-trivially.
We define a new subspace arrangement $\widetilde{\mathcal{U}}$ as follows.
\begin{enumerate}
	\item Choose $|S|$-many generic subspaces $W_{1},\ldots,W_{|S|} $ of $W$ each of dimension $c$.
	\item Let $S=\{s_1,\dots,s_{|S|}\}$. The new subspace arrangement $\widetilde{\mathcal{U}}$ lives in $\widetilde{V}$ and consists of the subspaces $\widetilde{U}_{s_i} \coloneqq U_{s_i}+W_i$ for $i=1,\dots,|S|$ together with $\widetilde{U}_{e} \coloneqq U_e$ for all $e \in E\setminus S$.
\end{enumerate}

We note that taking $\widetilde{V}$ of dimension $\dim (V+ W)$ is sufficient.

\begin{rmrk} Up to an automorphism of $\widetilde{V}$ fixing $V$, a subspace $W\le \widetilde{V}$ is determined by its dimension together with its intersection with $V$.
This will suffice for our uses of this construction, and we will give this data instead of constructing $W,\widetilde{V}$ in what follows.
\end{rmrk}

\begin{defn}
The arrangement resulting from an application of the elementary inflation construction above to the arrangement $\U$, the subset $S \subseteq E$, and a subspace $W$ of dimension $d$ satisfying $W' = W \cap V$ will be denoted by $\mathcal{EI}_c(\U, S, d, W')$.
\end{defn}

\subsection{Extensions and Full Arrangements}\label{sec:sub_ext}
Before describing the details of inflation, we define a general class of subspace arrangements that arise from the inflation steps which we will call extensions.
The main idea of what follows is to inflate weak representations outside of the subspace spanned by the basis of the matroid in such a way that, after sufficiently many applications of the procedure, the ranks of the subspaces no longer depend on the given weak representation but only on the combinatorics of the matroid.

\begin{defn}\label{def:extension}
	Let $\U=\left\{ U_{e}\right\} _{e\in E}$ be a subspace arrangement in a vector space $V$ and let $M=(E,r)$ be a triangle matroid with a distinguished basis $B$.
	We call $\U$ an \emph{extension of a weak $c$-representation of $M$ with respect to $B$}, or for short an extension of $M$, if $\{U_e\cap U_B\}_{e\in E}$ is a weak $c$-representation of $M$ with respect to $B$ and we have for every $T\subseteq E$ and $D\subseteq B$
	\begin{equation}\label{eq:reg}
	\dim(U_T\cap U_D)\le c(r(T)+r(D)-r(T\cup D)).
	\end{equation}
\end{defn}

If inflations of weak $c$-arrangements are to be extensions, it follows they may never modify the dimensions of subspaces corresponding to the distinguished basis. Further, if $\U=\{U_e\}_{e\in E}$ is an extension of a weak $c$-representation of $M$ and its rank function depends only on the combinatorics of $M$, the dimension of $U_X \cap U_B$ must not depend on the original weak $c$-representation.
The following definition of a defect gives the difference between the dimension of each intersection $U_X \cap U_B$ and what it ought to be.

\begin{defn}\label{def:regular}
	Let $M=(E,r)$ be a triangle matroid with a distinguished basis $B$ and $\U=\left\{ U_{e}\right\} _{e\in E}$ an extension of a weak $c$-representation of $M$ with respect to $B$.
	For a subset $S\subseteq E$ we define the \emph{defect} of $S$ to be $\de_{\U} (S)= c\cdot r(S)-\dim(U_S\cap U_B)$.
	We call a subset $S\subseteq E$ \emph{full with respect to the basis $B$}, or just full for short,
	if $\de_{\U}(S)=0$.	
\end{defn}


\subsection{An Inflation Step}\label{sec:alg_reg}

\begin{figure}[ht!]
	\begin{subfigure}[b]{0.4\linewidth}
		\centering
		\includegraphics[scale=.6]{pics/regularization_pair}
		\caption{Inflation of the pair $(x,y)$.}
		\label{fig:regularization_pair}
	\end{subfigure}
	\begin{subfigure}[b]{0.6\linewidth}
		\centering
		\includegraphics[scale=.6]{pics/regularization_basis}
		\caption{Inflation with respect to the basis $B$.}
		\label{fig:regularization_basis}
	\end{subfigure}
	\caption{The two inflation steps.}
	\label{fig:regularization}
\end{figure}

Let $M=(E,r)$ be a triangle matroid and $\U=\left\{ U_{e}\right\} _{e\in E}$ an extension of a weak $c$-representation of $M$ with respect to $B$.
We now describe an \emph{inflation} procedure that given a subset $S \subseteq E\setminus B$ yields a subspace arrangement $\mathcal{I}(\U,S)$ in which $S$ is full.
In this construction, we assume that any proper subset of $S$ is full in $\U$.
The procedure is split up into two steps.
\begin{description}
	\item[Step 1] We first perform an elementary inflation to the subset $S$.
	We call this step $S$-\emph{inflation}.
	For cases of the form $S=\{x,y\}$, with both $x$ and $y$ lying on the same side of the triangle of $M$, this is depicted in \Cref{fig:regularization_pair}.
	
	We elementary inflate by setting $\U^1 \coloneqq \mathcal{EI}_c(\U, S, c(\vert S \vert - 1) +\de_{\U}(S) , 0)$.
	At the end of this step, we have added a $c$-dimensional subspace to each $U_s$ for $s\in S$.
	Every proper subset of $m$ of these $c$-dimensional subspaces spans a subspace of total dimension $m\cdot c$.
	However, taken all together they span a subspace of dimension $c(\vert S\vert -1) + \de_{U}(S)$, which is in general less than $c\vert S\vert $.
	\item[Step 2] As second step we inflate the sum of these subspaces with respect to the basis $B$ which we call $B$-\emph{inflation}.
	Again, the case of $S$ being equal to two points lying on the same side of the triangle of $M$ is depicted in~\Cref{fig:regularization_basis}.
	
	While the previous step did not depend on $M$ being a triangle matroid, this step does:
	Consider the subset $C_M(S)\subseteq B$ such that $r(S)=r(S\cup C_M(S) )=r_M(C_M(S))$.
	If it exists, it is unique. Otherwise, we write $C_M(S)=\emptyset$, and in this case it follows that $\de_{\U}(S)=0$.
	
	Let $W'$ be a generic $\de_{\U}(S)$-dimensional subspace of $U^1_{C_M(S)}$ or $0$ if $C_M(S)=\emptyset$.
	Then we elementary inflate again by setting $\U^2\coloneqq \mathcal{EI}_c(\U^1,S, c\vert S \vert ,W')$. 
	
	At the end of this step we have added disjoint $c$-dimensional subspaces to each  $U_s$ for $s\in S$ such that $S$ is a full subset in $\U^2$.
	We set $\mathcal{I}(\U,S)\coloneqq \U^2$.
	
\end{description}

\noindent The next theorem describes the difference of the rank functions after both inflation steps.

\begin{theorem}\label{theo:alg_reg}
	Let $\U$ be an extension of a weak $c$-representation of a triangle matroid $M = (E,r)$ with respect to a distinguished basis $B$.
	Let $S \subseteq E \setminus B$ and assume that every subset $S'\subsetneq S$ is full.
	Let $\U' = \mathcal{I}(\U, S)$ be the inflation.
	
	Then if $A\subseteq E$ is any subset disjoint from $S$ and $Z \subseteq S$, we have:
	\[
	r_{\U'}^c(A\cup Z) =
	\begin{cases}
	r^c_\U (A\cup Z) + 2\vert Z \vert, & Z\subsetneq S, \\
	r^c_\U (A\cup S \cup C_M(S)) + 2\vert S\vert - 1, & Z = S,
	\end{cases}
	\]
	where $C_M(S)$ is the unique subset of $B$ such that $r(S)=r(S\cup C_M(S) )=r_M(C_M(S))$, or $\emptyset$ if it does not exist.
\end{theorem}

The last theorem enables us to prove that $S$ is full in the inflation $\mathcal{I}(\U, S)$.
\begin{coro}\label{cor:after_reg}
	Let $\U$ be an extension of a weak $c$-representation of a triangle matroid $M = (E,r)$ with respect to a distinguished basis $B$.
	Let $S \subseteq E \setminus B$ such that every $S'\subsetneq S$ is full and let $\U' = \mathcal{I}(\U, S)$ be the inflation.
	Then $\U'$ is an extension of $M$ and $S$ is full in $\U'$.
\end{coro}

\section{Combinatorial Inflation}

This section describes a combinatorial inflation procedure for polymatroids which mirrors the algebraic one described in the previous section.
\begin{defn}\label{def:partial_polymatroid}
	Let $M=(E,r)$ be a triangle matroid with a distinguished basis $B$.
	We call a polymatroid $g$ defined on $E$ an \emph{extension} of $M$ if for all $C\subseteq B$ and $S\subseteq E$ it satisfies
	\begin{equation}\label{eq:partial}
	g(C)+g(S)-g(S\cup C)=r(C)+r(S)-r(S\cup C).\tag{*}
	\end{equation}
\end{defn}
The condition in \Cref{eq:partial} reflects the condition of an extension given in \Cref{def:extension}.
It ensures that subspace arrangements representing $g$ are weak $c$-representations of $M$ when intersected with the subspace corresponding to $B$.
Note that applying $\eqref{eq:partial}$ with $S=C$ implies $g(C)=r(C)$ for all $C\subseteq B$.

We define a combinatorial inflation operation on the family of all polymatroid extensions $g:\mathcal{P}(E)\rightarrow\R_{\ge 0}$
of a triangle matroid $M=(E,r)$ with a distinguished basis $B$.
This mirrors the algebraic construction as specified in \Cref{theo:alg_reg}.
\begin{defn}\label{def:comb_reg}
	Given $g:\mathcal{P}(E)\rightarrow \R_{\ge 0}$ which is a polymatroid extension of a triangle matroid $M$ with distinguished basis $B$, together with a subset $S\subseteq E \setminus B$, we define the inflation $g'$ as follows:
	let $A \subseteq E$ be any subset disjoint from $S$, and let $Z \subseteq S$.	
	Then we define
	\[
	g'(A\cup Z) \coloneqq \begin{cases}
	g(A\cup Z) + 2|Z|, & Z\subsetneq S,\\
	g(A \cup S\cup C_M(S)) + 2|S| - 1, & Z = S,
	\end{cases}
	\]
	where $C_M(S)$ is the unique subset of $B$ such that $r(S)=r(S\cup C_M(S) )=r_M(C_M(S))$, or $\emptyset$ if it does not exist.
	The rank function $g'$ resulting from this construction, applied to $g$ and the subset $S$, will be denoted by $\mathcal{I}_\text{comb}(g,S)$.
	The polymatroid $\mathcal{I}_\text{comb}(g,S)$ is again an extension of $M$
\end{defn}
%\begin{prop}\label{prop:comb_reg}
%	Let $g$ be a polymatroid extension of a matroid $M=(E,r)$ with respect to the distinguished basis $B$ and $S\subseteq E \setminus B$.
%	Then $ \mathcal{I}_\text{comb}(g,S)$ is also a polymatroid extension from $M$ with respect to $B$.
%\end{prop}

Given a weak $c$-arrangement $\mathcal{A}$ and its matroid, one can iteratively inflate each at every subset, in such a way that every subset is full in the resulting extension of $\mathcal{A}$. The main part of the next theorem is that the algebraic process is compatible with the combinatorial one, if inflations are performed in an appropriate order.
\begin{theorem}\label{thm:regularization}
	Let $M=(E,r)$ be a triangle matroid with distinguished basis $B$. Then there is a polymatroid extension $g$ of $M$ such that $M$ has a  weak $c$-representation with respect to $B$ if and only if $c\cdot g$ has a subspace arrangement representation $\U$, that is $r_{\U}^c=g$.
	
	Moreover, given a weak $c$-representation $\A$ of $M$, the subspace arrangement $\U$ representing $c\cdot g$ can be chosen to be an extension of $\A$.
\end{theorem}

\section{Bases and Separation}\label{sec:c-bases}

This section has two main purposes. The first is to translate questions about polymatroids and $c$-admissible arrangements to questions about matroids and $c$-arrangements. The second is more directly related to inflations and the von Staudt construction: \cref{thm:regularization} gives a method by which to iteratively inflate a weak $c$-representation $\A$ of a triangle matroid into a $c$-admissible subspace arrangement $\U$.
This construction gives an arrangement of a combinatorial type that does not depend on $\A$. 

We want to apply group-theoretic undecidability results to this construction, where the weak arrangement $\A$ is constructed from a group presentation as in \Cref{sec:staudt}. For this, we need to check whether some two subspaces of $\A$ are different, and this needs to be encoded in the combinatorics; but the rank function of $\U$ contains no such information. It does not even know whether $\A$ was constructed from a trivial representation of the group or a faithful one.
\subsection{Expansions and $c$-Bases}
A representation of a polymatroid is a subspace arrangement. There is a way to construct a vector arrangement from such an object: pick a basis for every subspace, and take the set of all basis vectors. If we keep track of which vector came from each subspace, the subspace arrangement can be reconstructed.

The construction above is not purely combinatorial: the resulting matroid depends on the specific choice of bases. However, if the ground field is large enough and the bases are chosen generically, this issue disappears. The matroid obtained by such generic choices depends only on the polymatroid $g$ of the subspace arrangement. It is called the \emph{free expansion} $\mathscr{F}(g)$.

In fact there are only finitely many possible vector arrangements obtained by picking bases for a subspace arrangement representing the polymatroid $g$. The matroids arising in this way are called the \emph{expansions} of $g$, and form a subset of the weak images of $\mathscr{F}(g)$. For further details, see~\cite{Ngu86} or~\cite{Oxl11} (with slightly different terminology and notation). 

It is routine to check that the above carries over to $c$-admissible arrangements and $c$-arrangements, with the latter replacing vector arrangements.
Given a $c$-admissible arrangement $\U$ we obtain a \emph{$c$-basis} by picking $c$-dimensional subspaces of each element $U$ in $\A$ which minimally generate $U$.
%We collect the relevant definitions and lemmas here.
%\begin{defn}[Arrangement $c$-bases and polymatroid expansions]
%	\
%	
%	Let $\mathcal{U}=\left\{ U_{e}\right\} _{e\in E}$ be a $c$-admissible
%		subspace arrangement, and denote $d_{e}=\frac{1}{c}\dim U_{e}$ for
%		each $e\in E$. A \emph{$c$-basis} of $\mathcal{U}$ is a $c$-arrangement
%		$\mathcal{W} = \{U_{e,i}\}_{\substack{e\in E, \\ 1\le i\le d_e}}$
%		in the same ambient vector space as $\U$, satisfying that for each $e\in E$ we have $U_{e}=\sum_{i=1}^{d_{e}}U_{e,i}$.
%		In this situation, we denote $\mathcal{W}_e \coloneqq \{U_{e,i}\}_{1\le i\le d_e}$.
%
%The \emph{combinatorial type of the $c$-basis $\mathcal{W}$} is the matroid given by $r^c_\mathcal{W}$.
%		
% An \emph{expansion} of a polymatroid $(E,g)$ is a matroid with rank function $r$ on the ground set $\{(e,i) \mid e\in E, 1\le i\le g(e)\}$ satisfying that for any $S \subseteq E$: \[
%		r\left(\{(e,i)\mid e\in S, 1\le i\le g(e)\}\right) = g(S).
%		\] In particular, the combinatorial type of a $c$-basis of $\U$ is an expansion of $r^c_\U$. The converse does not always hold.
%\end{defn}

The results we need are that a polymatroid $g$ has a finite set of expansions, computable from $g$, together with the fact that a $c$-admissible subspace arrangement over an algebraically closed field has $c$-bases.

\subsection{Separated Extensions and Inequalities}\label{sec:sep_ineq}
Let $\A=\{A_e\}_{e\in E}$ be a weak $c$-representation of one of the triangle matroids $N_{S,R}$ constructed in \Cref{sec:staudt}.
As remarked at the beginning of this section, if $\U$ is an  arrangement resulting from an inflation of $\A$ such that all subsets of $\U$ are full, the rank function $r^c_\U$ does not contain enough information to determine whether $A_x \neq A_y$ for given $x,y\in E$.
However, inequalities of the form $A_x \neq A_y$, or equivalently $r^c_\A(\{x,y\}) > 1$ are precisely what we need in order to apply Slobodskoi's undecidability theorem, using our \Cref{theo:weak_undecidable}.

To overcome this difficulty, the strategy is to modify $\U$ by adding a subspace $W$ which is contained in $A_x$ but not in $A_y$ (provided that they are in fact distinct). Our method hinges on the fact that the rank function $r^c_\U$ does not depend on anything other than combinatorial data. Therefore we need to make sure $W$ can be  chosen to have some pre-determined dimension, and for this it is necessary to bound $\frac{1}{c}\dim(A_x \cap A_y)$ away from $1$ in a manner independent of $c$. 

We actually need more: it is necessary that the overlap of $A_x$ with any subspace in $\U$ is controlled. That this can be done is a consequence of the following definition and proposition.

\begin{defn}
	Let $M=\left(E,r\right)$ be a triangle matroid with distinguished
	basis $B$ and let $\mathcal{A}=\left\{ A_{e}\right\} _{e\in E}$
	be a weak $c$-representation of $M$.
	An arrangement $\mathcal{U}=\left\{ U_{e}\right\} _{e\in E}$ that is an extension of $\mathcal{A}$ is  \emph{well-separated} with respect to a given
	$x\in E$ if for any $T\subseteq E$, either $A_{x}\subseteq U_{T}$ or
	$\dim\left(A_{x}\cap U_{T}\right)\le\frac{1}{2}c$.
\end{defn}

\begin{prop}\label{prop:well_separated}
	Let $\left\langle S\mid R\right\rangle $ be a finite
	presentation, let $G$ be a finite group, and let $\varphi:G_{S,R}\rightarrow G$
	be a homomorphism.
	Let $\mathcal{A}= \mathcal{A}_{G,\varphi}$ be the weak $c$-representation 
	of the matroid $N_{S,R}=(E_{S,R},r)$ with respect to the distinguished basis $B=\left\{ b^{\left(1\right)},b^{\left(2\right)},b^{\left(3\right)}\right\} $ induced by the homomorphism $\phi$ as in~\Cref{theo:weak_undecidable}.
	Let $\mathcal{U}=\left\{ U_{e}\right\} _{e\in E}$
	be an extension of $\A$ and assume that $U_{T}$ is full in $\mathcal{U}$ for any $T\subseteq E_{S,R}$.
	Then $\mathcal{U}$ is well-separated with respect
	to $x^{\left(1\right)}\in E_{S,R}$ for any $x\in S$.
\end{prop}

The proof of this is based on \cref{lem:rank_permuatation_matrix}.

In the notation above, when $\mathcal{U}$ is well-separated with respect to $x^{(1)}$, and $\mathcal{A}_{x^{(1)}} \neq \mathcal{A}_{y^{(1)}}$ for some $y^{(1)} \in E_{S,R}$, there is always an expansion $r$ of the rank function $2\cdot r^c_\mathcal{U}$ which witnesses this fact. 
That is, if $\mathcal{W} = \{W_{e,i}\}_{e,i}$ has the combinatorial type of $r$, and we define $\mathcal{U}' = \{U'_e\}_{e\in E}$ by $U'_e = \sum_i W_{e,i}$ and $\mathcal{A}' = \{A'_e\}_{e\in E}$ by $A'_e = U'_e \cap U'_B$, then $A'_{x^{(1)}} \neq A'_{y^{(1)}}$. We say $r$ is an expansion \emph{separating} $x^{(1)}$ \emph{from} $y^{(1)}$.

Note that in this situation, $r_{\mathcal{U}'} = 2r_\mathcal{U}$, but this is not an issue. One can think of $\mathcal{U}'$ as an extension of a weak $2c$-arrangement representing $N_{S,R}$.

\section{Proof of \Cref{thm:undecidable_matroids}}\label{sec:main_proof}

In this section we connect our previous results to prove \Cref{thm:undecidable_matroids}.

\begin{theorem}
	For each instance of the uniform word problem for finite groups, there exists a finite set of matroids $\{M_1,\ldots,M_n\}$ (computable from the given instance of the problem,) such that at least one of them is representable as a $c$-arrangement if and only if the answer to the given instance of the UWPFG is negative.
\end{theorem}
\begin{proof}
	Let $\langle S \mid R\rangle$ be a finite presentation of a group and $w\in S$. Let $M = N_{S,R} = (E_{S,R}, r)$ be the corresponding matroid with distinguished basis $B = \{b^{(1)},b^{(2)},b^{(3)}\}$, as constructed in \cref{def:matroid_N}. Let $g$ be the polymatroid extending $M$ constructed in \cref{thm:regularization}, and let $\{M_i\}_{i=1}^n$ be the set of expansions of $2g$ which separate $w^{(1)}$ from $e^{(1)}$.
	
	By the results of \cref{sec:sep_ineq}, at least one of $M_1,\ldots,M_n$ is representable as a $c$-arrangement if and only if there exists a weak $c$-representation $\A = \{A_e\}_{e\in E_{S,R}}$ of $N_{S,R}$ such that $A_{w^{(1)}} \neq A_{e^{(1)}}$. This occurs if and only if the solution to the UWPFG instance is negative by \cref{theo:weak_undecidable}.
\end{proof}

Hence by Slobodskoi's theorem~\cite{Slo81}, existence of $c$-arrangement representations of matroids is undecidable. This proves \cref{thm:undecidable_matroids}.



\acknowledgements{We would like to thank K.~Adiprasito for introducing us to the topic of $c$-arrangements and for advice and helpful discussions.
Furthermore, we are grateful to Rudi Pendavingh for helpful conversations on the non-commutative von Staudt construction.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
