%% The class cedram-ALCO is just a wrapper around amsart.cls (version 2) %% implementing the layout of the journal, and some additionnal %% administrative commands. %% You can place one option: %% * "Unicode" if the file is UTF-8 encoded. \documentclass[ALCO,Unicode]{cedram} %% Here you might want to add some standard packages if those %% functionnalities are required. %\usepackage[matrix,arrow,tips,curve]{xy} % ... %% The production will anyway use amsmath (all ams utilities except %% amscd for commutative diagrams which you need to load explicilty if %% required), hyperref, graphicx, mathtools, enumitem... %% User definitions if necessary... Such definitions are forbidden %% inside titles, abstracts or the bibliography. \DeclarePairedDelimiter\abs{\lvert}{\rvert} \DeclareMathOperator{\Supp}{Supp} \DeclareMathOperator{\Pf}{Pf} \DeclareMathOperator{\Spin}{Spin} \DeclareMathOperator{\sign}{sgn} %\newcommand\C{{\mathbb C}} \newcommand\F{{\mathbb F}} \newcommand\N{{\mathbb N}} \newcommand\Q{{\mathbb Q}} \newcommand\R{{\mathbb R}} \newcommand\T{{\mathbb T}} \newcommand\Z{{\mathbb Z}} \newcommand\cB{{\mathcal B}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\fa{{\mathfrak a}} \newcommand\fm{{\mathfrak m}} \newcommand\fn{{\mathfrak n}} \newcommand\fp{{\mathfrak p}} \newcommand\fq{{\mathfrak q}} \newcommand\bfA{{\bf A}} \newcommand\bfP{{\bf P}} \renewcommand\geq{\geqslant} \renewcommand\leq{\leqslant} %Something useful only for this sample's sake: you can erase this line in your file (or find it useful...) %% The title of the paper: amsart's syntax. \title %% The optionnal argument is the short version for headings. [Representability of orthogonal matroids over partial fields] %% The mandatory argument is for the title page, summaries, headings %% if optionnal void. {Representability of orthogonal matroids over partial fields} %% Authors according to amsart's syntax + distinction between Given %% and Proper names: \author[\initial{M.} Baker]{\firstname{Matthew} \lastname{Baker}} %% Do not include any other information inside \author's argument! %% Other author data have special commands for them: \address{Georgia Institute of Technology\\ School of Mathematics\\ 686 Cherry Street\\ Atlanta\\ GA 30332-0160 (USA)} %% e-mail address \email{mbaker@math.gatech.edu} %% possibly home page URL (not encouraged by journal's style) %\urladdr{https://en.wikipedia.org/wiki/Marin\_Mersenne} %% Acknowledgements are not a footnote in %% \author, but are given apart: \thanks{The authors' research was supported by a Simons Foundation Travel Grant and NSF Research Grant DMS-2154224.} %% If co-authors exist, add them the same way, in alaphabetical order %\author{\firstname{Joseph} \lastname{Fourier}} %\address{Universit\'e de Grenoble\\ % Institut Moi-m\^eme\\ % BP74, 38402 SMH Cedex (France)} %\email{fourier@fourier.edu.fr} \author[\initial{T.} Jin]{\firstname{Tong} \lastname{Jin}} \address{Georgia Institute of Technology\\ School of Mathematics\\ 686 Cherry Street\\ Atlanta\\ GA 30332-0160 (USA)} \email{tongjin@gatech.edu} % Key words and phrases: \keywords{matroid, Grassmannian, orthogonal matroid} %% Mathematical classification (2010) %% This will not be printed but can be useful for database search \subjclass{05B35, 12K99} \begin{document} %% Abstracts must be placed before \maketitle \begin{abstract} Let $r \leq n$ be nonnegative integers, and let $N = \binom{n}{r} - 1$. For a matroid $M$ of rank $r$ on the finite set $E = [n]$ and a partial field $k$ in the sense of Semple--Whittle, it is known that the following are equivalent: (a) $M$ is representable over $k$; (b) there is a point $p = (p_J) \in \mathbf{P}^N(k)$ with support $M$ (meaning that $\mathrm{Supp}(p) := \{J \in \binom{E}{r} \; \vert \; p_J \ne 0\}$ of $p$ is the set of bases of $M$) satisfying the Grassmann-Pl{\"u}cker equations; and (c) there is a point $p = (p_J) \in \mathbf{P}^N(k)$ with support $M$ satisfying just the 3-term Grassmann-Pl{\"u}cker equations. Moreover, by a theorem of P. Nelson, almost all matroids (meaning asymptotically 100\%) are not representable over any partial field. We prove analogues of these facts for Lagrangian orthogonal matroids in the sense of Gelfand--Serganova, which are equivalent to even Delta-matroids in the sense of Bouchet. \end{abstract} \maketitle % First paragraph after a section is not indented. If there is text % below the title before the first section, it should be unindented % like this. \section{Introduction}\label{section:introduction} For simplicity, throughout this introduction $k$ will denote a field, but all statements remain true when $k$ is a {\em partial field} in the sense of Semple and Whittle~\cite{SW96}, and the proofs will be written in that generality. Let $E$ be a finite set of size $n$, which for concreteness we will sometimes identify with the set $[n] \coloneqq \{ 1,2,\ldots,n \}$. Let $r$ be a nonnegative integer, and let $N = \binom{n}{r} - 1$. Let $\binom{E}{r}$ denote the family of all $r$-subsets of $E$. We will be considering the projective space $\bfP^N(k)$ with coordinates indexed by the $r$-element subsets of $E$. Let $A$ be an $r \times n$ matrix of rank $r$ whose columns are indexed by $E$. Define $\Delta: \binom{E}{r} \to k$ by $\Delta(J) = \det A_J$, where $A_J$ is the $r \times r$ maximal square submatrix whose set of columns is $J$. We can extend the map $\Delta$ to all subsets of $E$ of size at most $r$ by setting $\Delta(J) = 0$ if $|J| < r$. For every $S \in \binom{E}{r+1}$, $T \in \binom{E}{r-1}$, and $x \in S$, we define $\sign(x; S, T)$ to be $(-1)^m$, where $m$ is the number of elements $s \in S$ with $s > x$ plus the number of elements $t \in T$ with $t > x$. Basic properties of determinants imply that the point $p = (p_J)_{J \in \binom{E}{r}} \in \bfP^N(k)$ defined by $p_J \coloneqq \Delta(J)$ satisfies the following homogeneous quadratic equations, called the {\em Pl{\"u}cker equations} (cf. e.g. \cite[\S{4.3}]{MS15}): \begin{equation} \label{eq:GP} \sum_{x \in S} \sign(x; S, T) X_{S \backslash \{x \}} X_{T \cup \{x\}} = 0. \end{equation} When $S \backslash T = \{i < j < k\}$, we may assume without loss of generality that $T \backslash S = \{\ell\}$ and $\ell > k$. Then we obtain the {\emph{$3$-term Pl{\"u}cker} equations}, which are of particular importance: \begin{equation} \label{eq:3termGP} X_{S \backslash \{i\}}X_{T \cup \{i\}} - X_{S \backslash \{j\}}X_{T \cup \{j\}} + X_{S \backslash \{k\}}X_{T \cup \{k\}} = 0. \end{equation} The following result is fundamental: \begin{theo}\label{theorem:G-P} Let $k$ be a field. The following are equivalent for a point $p = (p_J) \in \bfP^N(k)$: \begin{enumerate} \item There exists an $r \times n$ matrix $A$ of rank $r$ with entries in $k$ such that $p_J = \det(A_J)$ for any $J \in \binom{E}{r}$. \item The point $p$ satisfies the Pl{\"u}cker equations. \item The support $\Supp(p) = \{J \in \binom{E}{r} \; \vert \; p_J \ne 0\}$ of $p$ is the set of bases of a matroid of rank $r$ on $E$, and $p$ satisfies the $3$-term Pl{\"u}cker equations. \end{enumerate} \end{theo} The equivalence of (1) and (2) in the theorem is just the well-known classical fact that the Grassmannian variety of $r$-dimensional subspaces of a fixed $n$-dimensional vector space is defined (set-theoretically) by the Pl{\"u}cker equations. The equivalence of (2) and (3) is a folklore fact, but we are not aware of a published reference which furnishes a direct proof, so we give one in Section~\ref{section:G-P} below. One of the interesting features of Theorem~\ref{theorem:G-P} is that it is a `purely algebraic' fact about matrices over a field but its statement involves the combinatorial notion of a matroid. Recall that a {\emph{matroid}} $M$ on $E$ is a nonempty collection $\cB$ of subsets of $E$ satisfying the following {\em exchange axiom}: \begin{quote} If $B_1, B_2 \in \cB$, then for any $x \in B_1 \backslash B_2$, there exists an element $y \in B_2 \backslash B_1$ such that $(B_1 \backslash \{x\} ) \cup \{y\}$ belongs to $\cB$. \end{quote} This turns out to be equivalent to the {\em a priori} stricter {\em strong exchange axiom}: \begin{quote} If $B_1, B_2 \in \cB$, then for any $x \in B_1 \backslash B_2$, there exists an element $y \in B_2 \backslash B_1$ such that $(B_1 \backslash \{x\} ) \cup \{y\}$ and $(B_2 \backslash \{y\} ) \cup \{x\}$ both belong to $\cB$. \end{quote} The set $E$ is called the {\emph{ground set}} of $M$, and the members of $\cB$ are called the {\emph{bases}}. All bases of a matroid $M$ have the same cardinality, called the {\emph{rank}} of $M$. A matroid whose bases are the support of some point $p = (p_J) \in \bfP^N(k)$ satisfying the Pl{\"u}cker equations (or, equivalently, the 3-term Pl{\"u}cker equations) is called {\em representable} over $k$. It is natural to ask whether a `typical' matroid is representable over some field. The answer turns out to be no. This follows by combining the following two estimates: \begin{theorem}[Knuth \cite{Kn74}]\label{theorem:numberofmatroids} Denote by $m_n$ the number of isomorphism classes of matroids on ground set $[n] = \{1, 2, \dots, n\}$. Then \[ \log \log m_n \geq n - \frac{3}{2}\log n - O(1). \] \textup{(}Here $\log$ is taken to base two.\textup{)} \end{theorem} \begin{theorem}[Nelson~\cite{Ne18}] For $n \geq 12$, the number $r_n$ of isomorphism classes of matroids on the ground set $[n]$ which are representable over some field satisfies \[ \log r_n \leq n^3 / 4. \] \end{theorem} Combining these two estimates, we obtain: \begin{theorem}\label{theorem:not-representableM} Asymptotically 100\% of all matroids are not representable over any field. \end{theorem} One can generalize the classical Grassmannian varieties by the Lagrangian orthogonal Grassmannians $OG(n, 2n)$, which parameterise all $n$-dimensional maximal isotropic subspaces of a given $2n$-dimensional vector space endowed with a symmetric, non-degenerate bilinear form. The combinatorial counterpart of this point of view is the notion of a \emph{Lagrangian orthogonal matroid}, also known as an {\em even Delta-matroid}~\cite{Bo89}. For simplicity, we omit the adjective `Lagrangian' and refer to such objects as \emph{orthogonal matroids}. \begin{defi} Denote by $X\Delta Y$ the symmetric difference of two sets $X,Y$. An {\emph{orthogonal matroid}} on $E$ is a nonempty collection $\cB$ of subsets of $E$ satisfying the following axiom: if $B_1, B_2 \in \cB$, then for any $x_1 \in B_1 \Delta B_2$, there exists an element $x_2 \in B_2 \Delta B_1$ with $x_2 \ne x_1$ such that $B_1 \Delta\{x_1, x_2\} \in \cB$. \end{defi} Like the usual Grassmannian, the Lagrangian orthogonal Grassmannian $OG(n, 2n)$ is also a projective variety cut out by homogeneous quadratic polynomials, known in this case as the {\emph{Wick equations}} \cite{Ri12,We93} (see equations \eqref{eq:Wick} below for a precise formulation). The simplest Wick equations have precisely four non-zero terms. By analogy with Theorem~\ref{theorem:G-P}, we will prove: \begin{theorem}\label{theorem:Wick} Let $k$ be a field.\footnote{In \S\ref{section:Wick}, we will generalize this fact, and the statement of Theorem~\ref{theorem:Wick}, to partial fields $k$.} Let $n \in \N$, set $E = [n]$ and $N = 2^n - 1$, and consider the projective space $\bfP^N(k)$ with coordinates indexed by the subsets of $[n]$. The following are equivalent for a point $p = (p_J) \in \bfP^N(k)$. \begin{enumerate} \item There exists a skew-symmetric matrix $A$ over $k$ with rows and columns indexed by $E$ and a subset $T \subseteq E$ such that $p_J = \Pf(A_{J \Delta T})$ for all $J \subseteq E$. \textup{(}Here $A_J$ denotes the $|J| \times |J|$ square submatrix whose sets of row and column indices are both $J$, and $\Pf$ denotes the Pfaffian of a skew-symmetric matrix.\textup{)} \item The point $p$ satisfies the Wick equations. \item The support of $p$ is the set of bases of an orthogonal matroid on $E$, and $p$ satisfies the $4$-term Wick equations. \end{enumerate} \end{theorem} In particular, a point $p \in \bfP^{N}(k)$ belongs to $OG(n, 2n)$ if and only if there is a subset $T \subseteq E$ such that $\Supp(p) \Delta T$ is the set of bases of an orthogonal matroid and $p$ satisfies the $4$-term Wick relations. If $M$ is an orthogonal matroid, we say that $M$ is {\em representable} over $k$ if there is a skew-symmetric matrix $A$ over $k$ with rows and columns indexed by $E$ and a subset $T \subseteq E$ such that $p_J = \Pf(A_{J \Delta T})$ for all $J \subseteq E$. By analogy with Nelson's theorem, we estimate the number of representable orthogonal matroids and show: \begin{theorem}\label{theorem:not-representableOM} Asymptotically 100\% of orthogonal matroids are not representable over any field. \end{theorem} \section{Representations of Matroids over Partial Fields}\label{section:G-P} Partial fields are generalizations of fields which have proven to be very useful for studying representability of matroids. They were originally introduced by Semple and Whitte~\cite{SW96}, but the definitions below are from~\cite{PvZ13}.\footnote{In \cite{BL21}, one finds a slightly different definition of partial fields from the one in \cite{PvZ13} (there is an additional requirement that $G$ generates $R$ as a ring), but the difference is irrelevant for our purposes in this paper.} \begin{defi} A {\emph{partial field}} $P$ is a pair $(G, R)$ consisting of a commutative ring $R$ with $1$ and a subgroup $G$ of the group of units of $R$ such that $-1$ belongs to $G$. We say $p$ is an {\emph{element}} of $P$ and write $p \in P$ if $p \in G \cup \{0\}$. \end{defi} \begin{exam} A partial field with $G = R \backslash \{0\}$ is the same thing as a field. \end{exam} \begin{exam} The partial field $\F^{\pm}_1 = (\{1, -1\}, \Z)$ is called the {\emph{regular partial field}}. \end{exam} \begin{defi} Let $P = (G, R)$ be a partial field. A {\emph{strong $P$-matroid}} of rank $r$ on $E = [n]$ is a projective solution $p = (p_J) \in {\bfP}^N(P)$ to the Pl{\"u}cker equations \eqref{eq:GP}, \ie $p_J \in P$ for all $J \in \binom{E}{r}$, not all $P_J$ are zero, and $p$ satisfies \eqref{eq:GP} viewed as equations over $R$. A {\emph{weak $P$-matroid}} of rank $r$ on $E = [n]$ is a projective solution $p = (p_J)$ to the $3$-term Pl{\"u}cker equations \eqref{eq:3termGP} such that $\Supp(p) \coloneqq \{J \; \vert \; p_J \neq 0 \}$ is the set of bases of a matroid of rank $r$ on $E$. \end{defi} \begin{rema} Let $P$ be a partial field. If $M$ is a strong or weak $P$-matroid, corresponding to a Pl{\"u}cker vector $p \in {\bfP}^N(P)$, then $\Supp(p) \coloneqq \{J \; \vert \; p_J \neq 0 \}$ is the set of bases of a matroid $\underline{M}$ on $E$, called the {\em underlying matroid} of $M$. We say that a matroid $\underline{M}$ is {\emph{$P$-representable}} (or {\emph{representable over $P$}}) if it is the support of a strong (or, equivalently, by the following theorem, weak) $P$-matroid. \end{rema} The following is a generalization of Theorem~\ref{theorem:G-P} to partial fields: \begin{theorem}\label{theorem:partialfieldG-P} Let $P = (G, R)$ be a partial field and let $0 \leq r \leq n \in \N$. Let $N = \binom{n}{r} - 1$. Then the following are equivalent for a nonzero point $p = (p_J) \in \bfP^N(P)$: \begin{enumerate}[label=(\arabic*)] \item \label{it111}There exists a matrix $A$ with entries in $P$ such that $p_J = \det(A_J)$ for all $J \in \binom{[n]}{r}$. \item \label{it222} $p$ satisfies the Pl{\"u}cker equations \eqref{eq:GP}, i.e., $p$ is the Pl{\"u}cker vector of a strong $P$-matroid. \item \label{it333} $p$ is the Pl{\"u}cker vector of a weak $P$-matroid. \end{enumerate} \end{theorem} \begin{proof} It follows from standard properties of determinants for matrices over commutative rings that~\ref{it111} implies~\ref{it222}, and~\ref{it222} implies~\ref{it333} is true by definition. It remains to show that~\ref{it333} implies~\ref{it111}. The idea is that given $p: \binom{[n]}{r} \to P$ whose support is the set of bases of a matroid $M$, we will explicitly construct an $r \times n$ matrix $A$ over $P$ such that $\det(A_J) = p(J)$ for all $r$-element subsets $J \subseteq [n]$. Without loss of generality, by relabeling the elements of $E$ and rescaling the projective vector $p$ if necessary, we may assume that $[r] = \{1, 2, \dots, r\}$ is a basis of $M$ and that $p([r]) = 1$. We define \[ A = (I_r \; \vert \; a_{ij})_{1 \leq i \leq n, r+1 \leq j \leq n}, \] where $a_{ij} = (-1)^{r+i}p([r] \backslash \{i\} \cup \{j\})$. We claim that $\det(A_J) = p(J)$ for all $J \in \binom{[n]}{r}$. The proof is by induction on $v_J \coloneqq r - |J \cap [r]|$. If $v_J = 0$, then $J = [r]$ and $\det(A_J) = p_J = 1$. If $v_J = 1$, $J = [r] \backslash \{i\} \cup \{j\}$ for some $i \in [r]$ and $j \in [n] \backslash [r]$, and elementary properties of determinants give \[ \det(A_J) = (-1)^{i+r}a_{ij} = p(J). \] Now suppose $v_J = l \geq 2$. Then $k \coloneqq |J \cap [r]| \leq r - 2$. Fix $a < b \in J \backslash [r]$. We wish to show that $\det(A_J) = p(J)$. {\bf{Case 1. }}Suppose $J$ is a basis of $M$. Then by the basis exchange property, there exists $i \in [r] \backslash J$ such that $B' \coloneqq J \backslash \{a\} \cup \{i\}$ is a basis. By the basis exchange property again, there exists $j \in [r] \backslash B'$ such that $B'' \coloneqq B' \backslash \{b\} \cup \{j\}$ is also a basis. Without loss of generality, we may assume that $i < j$, and then applying the $3$-term Grassmann-Pl{\"u}cker relations to $S = J \backslash \{b\} \cup \{i, j\}$ and $T = J \backslash \{a\}$ (so that $S \backslash T = \{i < j < a\}$), we obtain \[ p(S \backslash \{i\}) p(T \cup \{i\}) - p(S \backslash \{j\}) p(T \cup \{j\}) + p(S \backslash \{a\}) p(T \cup \{a\}) = 0. \] Since \[ |(S \backslash \{i\}) \cap [r]| = |(T \cup \{i\}) \cap [r]| = |(S \backslash \{j\}) \cap [r]| = |(T \cup \{j\}) \cap [r]| = k+1 \] and $|(S \backslash \{a\}) \cap [r]| = k+2$, the inductive hypothesis implies that \[ \det(A_{S \backslash \{i\}}) \det(A_{T \cup \{i\}}) - \det(A_{S \backslash \{j\}}) \det(A_{T \cup \{j\}}) + \det(A_{S \backslash \{a\}}) p(T \cup \{a\}) = 0. \] Moreover, since $S \backslash \{a\} = B''$ is a basis, $p(S \backslash \{a\}) = \det(A_{S \backslash \{a\}}) \ne 0$. This gives $p(T \cup \{a\}) = \det(A_{T \cup \{a\}})$ as desired. {\bf{Case 2. }}Suppose $J$ is not a basis of $M$, i.e., $p(J)=0$. Note that if there exist distinct $i, j \in [r] \backslash J$ such that $J \backslash \{a, b\} \cup \{i, j\}$ is a basis, then the proof from Case 1 still works. Therefore, we may assume that no such $i$ and $j$ exist. Then for every $i \in [r] \backslash J$, $J_i' \coloneqq J \backslash \{a\} \cup \{i\}$ is not a basis and $\det(A_{J_i'}) = p(J_i') = 0$. By $(1) \Rightarrow (2)$ applied with $S = [r] \cup \{a\}$ and $T = J \backslash \{a\}$, we have \begin{equation} \label{eq:PluckerA} \begin{split} \sign(a; S, T) \det(A_{[r]}) \det(A_J) & + \sum_{i \in [r] \cap J} \sign(i; S, T) \det(A_{S \backslash\{i\}}) \det(A_{T \cup \{i\}}) \\ & + \sum_{i \in [r] \backslash J}\sign(i; S, T)\det(A_{S \backslash\{i\}}) \det(A_{T \cup \{i\}})\\ & = 0. \end{split} \end{equation} If $i \in [r] \cap J$, then $T \cup \{i\} = T$ so $\det(A_{T \cup \{i\}}) = 0$. If $i \in [r] \backslash J$, then $T \cup \{i\} = J_i'$ so $\det(A_{J_i'}) = 0$. Together with \eqref{eq:PluckerA}, this forces $\det(A_J) = 0 = p_J$. \end{proof} We now explain briefly how to see that Theorem~\ref{theorem:not-representableM} (Nelson's theorem) implies that asymptotically 100\% of all matroids are not representable over any partial field. \begin{defi} Let $P_1 = (G_1, R_1)$ and $P_2 = (G_2, R_2)$ be partial fields. A map $\varphi: R_1 \to R_2$ is called a {\emph{homomorphism}} of partial fields if $\varphi$ is a ring homomorphism and $\varphi(G_1) \subseteq G_2$. \end{defi} Matroid representability over partial fields is preserved by homomorphisms. More precisely: \begin{prop}[Semple-Whittle~\cite{SW96}] Let $\varphi: P_1 \to P_2$ be a homomorphism of partial fields. If a matroid $M$ is $P_1$-representable, then $M$ is also $P_2$-representable. \end{prop} On the other hand, we also have: \begin{lemm} \label{lemma:homomtofield} If $P=(G,R)$ is a partial field, there exists a homomorphism $P \to k$ for some field $k$. \end{lemm} \begin{proof} Take a maximal ideal $\fm \subseteq R$ and consider the field $k \coloneqq R/\fm$. Then the natural quotient homomorphism $R \twoheadrightarrow k$ induces a homomorphism of partial fields $P \to k$. \end{proof} We deduce: \begin{coro} If a matroid is representable over a partial field $P$, then it is representable over a field $k$. \end{coro} Combining this fact with Theorem~\ref{theorem:not-representableM}, we obtain: \begin{coro} Asymptotically 100\% of all matroids are not representable over any partial field. \end{coro} \section{Representations of Orthogonal Matroids}\label{section:OM} In this section, we provide some background on orthogonal matroids and their representations. Recall from Section~\ref{section:introduction} that an {\em orthogonal matroid} on $E$ is a nonempty collection $\cB$ of subsets of $E$ satisfying the symmetric exchange axiom. As with their matroid counterparts, this axiom can be replaced with an {\em a priori} stricter {\emph{strong symmetric exchange axiom}} (see, for example, \cite[Theorem 4.2.4]{BGW03}): \begin{prop}[Strong Symmetric Exchange] If $M$ is an orthogonal matroid, then for any $B_1, B_2 \in \cB$ and $x_1 \in B_1 \Delta B_2$, there exists $x_2 \in \cB$ with $x_2 \ne x_1$ such that both $B_1 \Delta \{x_1, x_2\}$ and $B_2 \Delta \{x_1, x_2\}$ belong to $\cB$. \end{prop} \begin{exam} Every matroid is also an orthogonal matroid. In fact, matroids are by definition just orthogonal matroids whose bases all have the same cardinality. \end{exam} From the definition, one sees easily that any two bases of an orthogonal matroid have the same parity. \begin{exam}\label{exm:representable} Let $E = [4]$ and consider $\cB = \{\emptyset, \{1, 2\}, \{1, 4\}, \{2, 4\}\}$. This is an orthogonal matroid. If we keep the same ground set $E$ and replace every member $B$ of $\cB$ with $B \Delta \{3\}$, we obtain another orthogonal matroid $M' = (E, \cB')$ where $\cB' = \{\{3\}, \{1, 2, 3\}, \{1, 3, 4\}, \{2, 3, 4\}\}$. This is an example of a general operation on orthogonal matroids called {\em twisting}. \end{exam} The determinant of a matrix $A$ admits a refinement for skew-symmetric matrices called the {\em Pfaffian}. The Pfaffian $\Pf(A)$ can be defined recursively as follows. By convention, we define the Pfaffian of the empty matrix to be $1$. Now let $A$ be an $n \times n$ skew-symmetric matrix over a ring $R$, where $n \geq 1$. If $n$ is odd, we set $\Pf(A) \coloneqq 0$. If $n = 2$, we have \[ \Pf \begin{pmatrix} 0 & a \\ -a & 0 \end{pmatrix} \coloneqq a. \] Finally, if $n \geq 4$, we set \[ \Pf(A) \coloneqq \sum_{j = 2}^n (-1)^j \Pf(A_{\{1, j\}}) \Pf(A_{\{2, \dots, j-1, j+1, \dots, n\}}), \] where $A_J$ denotes the $|J| \times |J|$ square submatrix whose rows and columns are indexed by $J$. If $A$ is a $(2k) \times (2k)$ skew-symmetric matrix of indeterminates, $\Pf(A)$ is a homogeneous polynomial of degree $d = 2k-1$ whose coefficients all belong to $\{ 0,1,-1 \}$. A basic fact about the Pfaffians is that $(\Pf(A))^2 = \det(A)$ for every skew-symmetric matrix $A$~\cite{Ca49}. \begin{prop}[{Wenzel \cite[Prop. 2.3 ]{We93}}] \label{proposition:Pfaffian} Let $A$ be an $n \times n$ skew-symmetric matrix over a ring $R$. Let $N = 2^n - 1$. The point $(p_J)_{J \subseteq E} \in \bfP^N(R)$ defined by $p_J = \Pf(A_J)$ satisfies the homogeneous quadratic polynomial equations \begin{equation} \label{eq:Wick} \sum_{j = 1}^k (-1)^j \cdot X_{J_1 \Delta\{i_j\}} \cdot X_{J_2 \Delta \{i_j\}} = 0, \end{equation} called the {\em Wick equations},\footnote{These identities are known to physicists as Wick's theorem~\cite{Mu99}. We follow \cite{Ri12} rather than \cite{We93} in our terminology.} for all $J_1, J_2 \subseteq [n]$ and $J_1 \Delta J_2 = \{i_1 < \cdots < i_k\}$. \end{prop} We are especially interested in the shortest possible Wick equations, where $|J_1 \Delta J_2| = 4$, called the {\emph{$4$-term Wick equations}}. Concretely, if $J \subseteq [n]$ and $a < b < c < d \in [n] \backslash J$ are distinct, we have: \begin{gather*} X_{Jabcd}X_{J} - X_{Jab}X_{Jcd} + X_{Jac}X_{Jbd} - X_{Jad}X_{Jbc} = 0, \\ X_{Jabc}X_{Jd} - X_{Jabd}X_{Jc} + X_{Jacd}X_{Jb} - X_{Jbcd}X_{Ja} = 0. \end{gather*} Here, and from now on, $Ja$ means $J \cup \{a\}$ in order to simplify the notation. If $P$ is a partial field, we may consider the projective solutions in $\bfP^N(P)$ to the different kinds of Wick equations. \begin{defi} A {\emph{strong orthogonal matroid}} over $P$ is a projective solution $p = (p_J)$ to the Wick equations \eqref{eq:Wick}. A {\emph{weak orthogonal matroid}} over $P$ is a projective solution $p = (p_J)$ to $4$-term Wick equations whose support $\Supp(p) = \{J \; \vert \; p_J \neq 0 \}$ is the set of bases of an orthogonal matroid on $E$. \end{defi} \begin{rema} One can generalize the definition of weak and strong orthogonal matroids over $P$ from partial fields to tracts in the sense of~\cite{BB19} and obtain cryptomorphic descriptions of these objects along the lines of {\em loc. cit.}, see~\cite{JK23}. \end{rema} \begin{prop}[{Wenzel \cite[Theorem 2.2]{We93}}] \label{proposition:normalOM} Let $P = (G, R)$ be a partial field. Given a strong orthogonal matroid over $P$ with $p_\emptyset = 1$, there exists an $n \times n$ skew-symmetric matrix $A$ over $R$ such that $\Pf(A_J) = p_J$. \end{prop} \begin{prop}\label{proposition:supp} Let $P$ be a partial field. The support of every strong orthogonal matroid over $P$ is the set of bases of an orthogonal matroid. \end{prop} \begin{proof} If $p_\emptyset = 1$, then $\Supp(p)$ gives an orthogonal matroid by Theorem 3.3 of \cite{We93}. Otherwise, let $p \in {\bfP^N(P)}$ be the Wick vector of a strong orthogonal matroid over $P$ (i.e., a point of the Lagrangian orthogonal Grassmannian $OG(n, 2n)$ over $P$), and choose $T \ne \emptyset$ such that $p_T = 1$. Consider the point $q \in \bfP^N(P)$ whose coordinates are defined by $q_J = p_{J \Delta T}$. We claim that $q$ also satisfies the Wick equations. In fact, for any $J_1, J_2 \subseteq [n]$ with $J_1 \Delta J_2 = (J_1 \Delta T) \Delta (J_2 \Delta T) = \{i_1 < \cdots < i_k\}$, we have \[ \begin{split} \sum_{j = 1}^k (-1)^j \cdot q_{J_1 \Delta \{i_j\}} \cdot q_{J_2 \Delta \{i_j\}} & = \sum_{j = 1}^k (-1)^j \cdot p_{J_1 \Delta \{i_j\} \Delta T} \cdot q_{J_2 \Delta \{i_j\} \Delta T}\\ & = \sum_{j = 1}^k (-1)^j \cdot p_{(J_1 \Delta T) \Delta \{i_j\}} \cdot p_{(J_2 \Delta T) \Delta \{i_j\}} \\ & = 0. \end{split} \] Since $\emptyset \in \Supp(q)$, this gives an orthogonal matroid $M$ with set of bases $\Supp(p) \Delta T$. Therefore, $\Supp(p)$ is the set of bases for the twist $M \Delta T$. \end{proof} \begin{defi} Let $M$ be an orthogonal matroid, and let $P$ be a partial field. Then $M$ is {\emph{$P$-representable}} if there exists a skew-symmetric matrix $A = (a_{ij})_{i, j \in E}$ with entries in $P$ and a subset $T \subseteq E$ such that \[ \cB \Delta T \coloneqq \{B \Delta T \; \vert \; B \in \cB\} = \{J \subseteq E \; \vert \; \Pf(A_J) \neq 0 \}. \] \end{defi} \begin{exam} The two orthogonal matroids in Example~\ref{exm:representable} are both $\R$-representable. To see this, let \[ A = \begin{pmatrix} 0 & -3 & 0 & 1 \\ 3 & 0 & 0 & 6 \\ 0 & 0 & 0 & 0 \\ -1 & -6 & 0 & 0 \\ \end{pmatrix}. \] Then $\{J \subseteq [4] \; \vert \; \Pf(A_J) \in \R^\times\} = \{\emptyset, \{1, 2\}, \{1, 4\}, \{2, 4\}\}$. Using the same notation from Example~\ref{exm:representable}, we find that $\cB = \cB' \Delta \{3\} = \{\emptyset, \{1, 2\}, \{1, 4\}, \{2, 4\}\}$. \end{exam} \begin{rema} In general, one can choose $T = \emptyset$ in the representation if and only if $\emptyset$ is a basis. In this case, we say that the orthogonal matroid is {\emph{normal}}. \end{rema} \section{Orthogonal Matroids and Orthogonal Grassmannians}\label{section:Wick} Let $P$ be a partial field and let $N = 2^n - 1$. Our goal for this section is to connect the notions of strong orthogonal matroids, weak orthogonal matroids, and representable matroids over $P$. We begin with the following lemma on normal orthogonal matroids. \begin{lemma}\label{lemma:normal} Suppose $M$ is a normal orthogonal matroid. If $\emptyset \ne J \subseteq [n]$ is a basis, there exists another basis $J' \subseteq J$ with $|J'| = |J| -2$. \end{lemma} \begin{proof} We apply the symmetric exchange axiom to the bases $J$ and $\emptyset$. Pick some $a \in J$. Then there exists $a \ne b \in J = J \Delta \emptyset$ such that $J' = J \Delta\{a,b\}$ is a basis, and $|J'| = |J| - 2$. \end{proof} Using this lemma, we now prove the desired result for normal orthogonal matroids. \begin{theorem}\label{theorem:normalWick} The followings are equivalent for a point $p \in \bfP^{N}(P)$ with $p_\emptyset = 1$: \begin{enumerate}[label=(\arabic*)] \item \label{it1} There exists a skew-symmetric matrix $A$ over $P$ such that $p_J = \Pf(A_J)$ for all $J \subseteq [n]$. \item \label{it2} $p$ is a strong $P$-orthogonal matroid. \item \label{it3} $p$ is a weak $P$-orthogonal matroid. \end{enumerate} \end{theorem} \begin{proof} \ref{it1} $\Rightarrow$ \ref{it2} follows from Proposition~\ref{proposition:Pfaffian}, and~\ref{it2} $\Rightarrow$~\ref{it3} follows from Proposition~\ref{proposition:supp}. So it suffices to prove that~\ref{it3} $\Rightarrow$~\ref{it1}. Given a point $p = (p_J) \in\bfP^{N}(P)$ with support equal to the orthogonal matroid $M$ and satisfying the $4$-term Wick equations, let $A = (a_{ij})$ be the skew-symmetric matrix defined by \[ a_{ij} = p_{\{i,j\}} \in P, \; 1 \leqslant i < j \leqslant n. \] We claim that $p_J = \Pf(A_J)$ for all $J \subseteq [n]$. When $|J|$ is odd, or $|J| = 0$ or $2$, we clearly have $p_J = \Pf(A_J)$. Now suppose $J = \{i_1, i_2, i_3, i_4\}$, where $1 \leqslant i_1 < i_2 < i_3 < i_4 \leqslant n$. Let $J_1 = \{i_1\}$ and $J_2 = \{i_2, i_3, i_4\}$. Since $p$ satisfies the $4$-term Wick equations, we have \[ p_{\emptyset} p_{J} - p_{\{i_1, i_2\}} p_{\{i_3, i_4\}} + p_{\{i_1, i_3\}} p_{\{i_2,i_4\}} - p_{\{i_1,i_4\}} p_{\{i_2,i_3\}} = 0. \] But $p_J = \Pf(A_J)$ when $|J| = 2$. Therefore, by the recursive definition of Pfaffians, $p_J = \Pf(J)$ when $|J| = 4$. Now suppose $p_J = \Pf(A_J)$ for bases $J$ with $|J| = 0, 2, 4, \dots, 2r-2$. Let $J = \{i_1, \dots, i_{2r}\}$ be a basis of $M$ with $1 \leqslant i_1 < \dots < i_{2r} \leqslant n$. By Lemma ~\ref{lemma:normal}, there exists another basis $J' \subseteq J$ with $|J'| = 2r -4$. Without loss of generality $J \backslash J'= \{i_1, i_2, i_3, i_4\}$. Let $J_1 = \{i_1, i_5, \dots, i_{2r}\}$ and let $J_2 = \{i_2, i_3, \dots, i_{2r}\}$. By the $4$-term Wick relations, we have \[ p_{J'}p_{J} - p_{J_1 \cup \{i_2\}}p_{J_2 \backslash \{i_2\}} + p_{J_1 \cup \{i_3\}}p_{J_2 \backslash \{i_3\}} - p_{J_1 \cup \{i_4\}}p_{J_2 \backslash \{i_4\}} = 0. \] Since $p_{J'} \ne 0$, by Proposition~\ref{proposition:Pfaffian} and induction, we obtain that $p_J = \Pf(A_J)$. Finally, suppose $J = \{i_1, \dots, i_{2r}\} \subseteq [n]$ is not a basis for $M$. If there exists $\{a, b, c, d\} \subseteq J$ such that $J' = J \backslash \{a,b,c,d\}$ is a basis, then the same proof would apply, giving $\Pf(A_J) = p_J = 0$. Otherwise, we have $p_{J'} = 0$ for all $J' \subseteq J$ with $|J'| = |J| - 4$. Therefore, \[ \begin{split} \Pf(A_J) & = \sum_{j = 2}^{2r} (-1)^j \cdot p_{\{i_1, i_j\}} \cdot p_{\{i_2, \dots, \hat{i_j}, \dots, i_{2r}\}} \\ & = \sum_{j = 2}^{2r} (-1)^j \cdot p_{\{i_1, i_j\}} \cdot \left(\sum_{j \ne k = 3}^{2r} (-1)^k \cdot p_{\{i_2, i_k\}} \cdot p_{\{i_3, \dots, i_{2r}\} \backslash \{i_j, i_k\}} \right)\\ & = 0.\qedhere \end{split} \] \end{proof} We now turn to the general case. \begin{theorem}\label{theorem:PFWick} The following are equivalent for arbitrary point $p \in \bfP^{N}(P)$: \begin{enumerate}[label=(\arabic*)] \item \label{it11} There exists a skew-symmetric matrix $A$ over $P$ such that $p_J = \Pf(A_J)$ for all $J \subseteq [n]$. \item \label{it22} $p$ is a strong $P$-orthogonal matroid. \item \label{it33} $p$ is a weak $P$-orthogonal matroid \end{enumerate} \end{theorem} \begin{proof} Again, it suffices to prove ~\ref{it33} $\Rightarrow$~\ref{it11}. Let $p = (p_J)$ be a point in $\bfP^N(P)$ satisfying the $4$-term Wick equations and assume that $\Supp(p)$ is the set of bases of an orthogonal matroid. Pick $p_{T} \ne 0$ and without loss of generality $p_T = 1$. Consider the point $q = (q_J) = (p_{J \Delta T}) \in \bfP^N(P)$. Since $q_\emptyset = 1$ and $q$ satisfies all the $4$-term Wick equations, it follows from Theorem~\ref{theorem:normalWick} that $q$ satisfies {\em all} of the Wick equations. So $p$ satisfies all of the Wick equations as well. \end{proof} \section{The Number of Representable Orthogonal Matroids}\label{section:how-many} In this section, we establish an upper bound for the number of orthogonal matroids on $[n]$ which are representable over some partial field. For this, we use a theorem of Nelson~\cite{Ne18} concerning zero patterns of a collection of polynomials. For a polynomial $f \in \Z[x_1, \dots, x_m]$, we write $||f||$ for the maximal absolute value of the coefficients of $f$. In particular, $||0|| = 0$. Let $k$ be a field, and let $\psi_k: \Z[x_1, \dots, x_m] \to k[x_1, \dots, x_m]$ be the ring homomorphism induced by the natural homomorphism $\varphi_k: \Z \to k$. Let $f_1, \dots, f_N \in \Z[x_1, \dots, x_m]$. We say a set $S \subseteq [N]$ is {\emph{realizable}} with respect to $\{f_1, \dots, f_N\}$ if there is a field $k$ and a vector ${\bf{u}} \in k^m$ such that \[ S = \{i \in [N] \; \vert \; \psi_k(f_i)({\bf{u}}) \ne 0 \}. \] \begin{theorem}[Nelson]\label{theorem:Nelson} Let $c, d \in \Z$ and let $f_1, \dots, f_N \in \Z[x_1, \dots, x_m]$ with $\deg(f_i) \leq d$ and $||f_i|| \leq c$ for all $i$. Let $\log$ denote the logarithm to base $2$. If $r$ satisfies \[ r > \binom{Nd + m}{m} (\log(3r) + N\log(c(eN)^d)), \] then $\{f_1, \dots, f_N\}$ has at most $r$ realizable sets. \end{theorem} \begin{theorem} If $n \geq 12$, then the number of normal orthogonal matroids on [n] representable over some field is at most $2^{n^3}$. \end{theorem} \begin{proof} Let $A$ be an $n \times n$ skew-symmetric matrix of indeterminates, where $a_{i, i} = 0$ and $a_{i, j} = x_{i,j}$ for $i > j$. For ease of notation, we relabel the indeterminates as $x_1, \dots, x_m$, where $m = \frac{n(n-1)}{2}$. Let $\{f_1, \dots, f_N\}$ be the Pfaffians of all square submatrices of $A$ of even size, where \[ N = \sum_{0 \leq k \leq n, \text{ $k$ is even}}\binom{n}{k} = 2^{n-1}. \] Notice that $\deg f_i \leq n-1$ and $||f_i|| = 1$ for every $i = 1, \dots, N$. If $M$ is a $k$-representable normal orthogonal matroid on $[n]$, there exists a skew-symmetric matrix $A$ over $k$ such that $\cB = \{J \subseteq E \; \vert \; A_{J} \text{ is nonsingular}\}$. This means precisely that $\cB$ is realizable with respect to $\{f_1, \dots, f_N\}$, so it suffices to show the number of realizable sets for $\{f_1, \dots, f_N\}$ is at most $2^{n^3}$. In Theorem~\ref{theorem:Nelson}, let $c = 1, d = n-1, N = 2^{n-1}$, and $r = 2^{n^3}$, where $n \geq 12$. Then by standard inequalities, we have \[ \begin{split} \binom{Nd + m}{m} & = \binom{2^{n-1}(n-1) + \frac{n(n-1)}{2}}{\frac{n(n-1)}{2}}\\ & \leq \binom{n \cdot 2^n}{n^2} \\ & \leq \left(\frac{e\cdot n \cdot 2^{n-1}}{n^2}\right)^{n^2} \\ & < \left(\frac{2^{n+1}}{n}\right)^{n^2}, \end{split} \] and \[ \begin{split} \log(3r) + N\log(c(eN)^d) & = \log 3 + n^3 + (n-1)\cdot 2^{n-1}(\log e + n-1) \\ & \leq 2 + n^3 + (n-1)\cdot 2^{n-1}(n+1)\\ & < n^2 \cdot 2^{n-1}. \end{split} \] Therefore, \[ \begin{split} \binom{Nd + m}{m} (\log(3r) + N\log(c(eN)^d)) & < \left(\frac{2^{n+1}}{n}\right)^{n^2} \cdot n^2 \cdot 2^{n-1} \\ & = 2^{n^3} \cdot \frac{2^{n^2 + n - 1}}{n^{n^2 - 2}} < 2^{n^3} = r. \end{split} \] By Theorem~\ref{theorem:Nelson}, $\{f_1, \dots, f_N\}$ has at most $r = 2^{n^3}$ realizable sets, so there are at most $2^{n^3}$ normal orthogonal matroids on $[n]$ which are representable over some field. \end{proof} \begin{coro} Asymptotically 100\% of all orthogonal matroids are not representable over any field. \end{coro} \begin{proof} Let $k$ be a field and let be a $k$-representable orthogonal matroid. Then for any $T \in \cB$, $M \Delta T$ is a normal representable orthogonal matroid. This shows the number of representable orthogonal matroid on $[n]$ is at most $2^n \cdot 2^{n^3}$. The result now follows from Theorem~\ref{theorem:numberofmatroids}. \end{proof} \begin{lemma} Let $\varphi: P_1 \to P_2$ be a homomorphism of partial fields. If an orthogonal matroid $M$ is $P_1$-representable, then $M$ is also $P_2$-representable. \end{lemma} \begin{proof} Let $A = (a_{ij})$ be a skew-symmetric matrix over $P_1$ and $T$ a subset of $E$ such that the pair $(A,T)$ represents $M$. Consider the new matrix $B = \varphi(A) \coloneqq (\varphi(a_{ij}))$. If $\Pf(A_J) = 0$ then $\Pf(B_J) = \varphi(0) = 0 \in P_2$. If $\Pf(A_J) \neq 0$, then $\Pf(B_J) = \varphi(\Pf(A_J)) \neq 0$. This shows that the pair $(B,T)$ represents $M$. \end{proof} Combined with Lemma~\ref{lemma:homomtofield}, this yields: \begin{coro} If an orthogonal matroid is representable over a partial field $P$, then it is representable over some field $k$. \end{coro} We conclude: \begin{coro} Asymptotically 100\% of all orthogonal matroids are not representable over any partial field. \end{coro} \longthanks{We thank Tianyi Zhang for helpful discussions on the proof of Theorem~\ref{theorem:G-P}.} %\nocite{*} \bibliographystyle{mersenne-plain} \bibliography{ALCO_Baker_806} \end{document}