# Puiseux Series and Algebraic Solutions of First Order Autonomous AODEs – A
MAPLE Package

François Boulier  Univ. Lille, CNRS, Centrale Lille, Inria, UMR 9189 -
CRIStAL, Lille, France<EMAIL_ADDRESS>,  José Cano  Dpto.
Algebra, análisis matemático, geometría y topología, Universidad de
Valladolid, Spain<EMAIL_ADDRESS>,  Sebastian Falkensteiner  Research
Institute for Symbolic Computation (RISC), Johannes Kepler University Linz,
Austria<EMAIL_ADDRESS>and  J.Rafael Sendra  Dpto. de Física y
Matemáticas, Universidad de Alcalá, Madrid, Spain<EMAIL_ADDRESS>
###### Abstract.

There exist several methods for computing exact solutions of algebraic
differential equations. Most of the methods, however, do not ensure existence
and uniqueness of the solutions and might fail after several steps, or are
restricted to linear equations. The authors have presented in previous works a
method to overcome this problem for autonomous first order algebraic ordinary
differential equations and formal Puiseux series solutions and algebraic
solutions. In the first case, all solutions can uniquely be represented by a
sufficiently large truncation and in the latter case by its minimal
polynomial.

The main contribution of this paper is the implementation, in a MAPLE package
named FirstOrderSolve, of the algorithmic ideas presented therein. More
precisely, all formal Puiseux series and algebraic solutions, including the
generic and singular solutions, are computed and described uniquely. The
computation strategy is to reduce the given differential equation to a simpler
one by using local parametrizations and the already known degree bounds.

The second author was partially supported by MTM2016-77642-C2-1-P (AEI/FEDER,
UE). The third and fourth authors were partially supported by FEDER/Ministerio
de Ciencia, Innovación y Universidades Agencia Estatal de
Investigación/MTM2017-88796-P (Symbolic Computation: new challenges in Algebra
and Geometry together with its applications). The third author was also
supported by the Austrian Science Fund (FWF): P 31327-N32. The fourth author
is member of the Research Group ASYNACS (Ref. CT-CE2019/683).

keywords Maple, Symbolic computation, Algebraic differential equation, Formal
Puiseux series solution, Algebraic solution.

##  1\. Introduction

The problem of finding power series solutions of ordinary differential
equations has been extensively studied in the literature. A method to compute
generalized formal power series solutions, i.e. power series with real
exponents, and to describe their properties is the Newton polygon method. A
description of this method is given in [Fin89, Fin90] and more recently in
[GS91, DDRJ97, Aro00]. In [Can05], the second author, using the Newton polygon
method, gives a theoretical description of all generalized formal power series
solutions of a non-autonomous first order ordinary differential equation as a
finite set of one parameter families of generalized formal power series. This
description of the solutions is in general not algorithmic by several reasons.
One of them is that there is no bound on the number of terms which have to be
computed in order to guarantee the existence of a generalized formal power
series solution when extending a given truncation of a determined potential
solution. Also the uniqueness of the extension can not be ensured a-priori.

In [CFS20] this problem has been overcome by the authors for autonomous first
order differential equations by using a local version of the algebro-geometric
approach introduced in [FG04].

In [VGW18] they derive an associated differential system to find rational
general solutions of non-autonomous first order differential equations by
considering rational parametrizations of the implicitly defined curve. We
instead consider its places and obtain an associated differential equation of
first order and first degree which can be transformed into an equation of a
very specific type [BB56]. Using the known bounds for computing places of
algebraic curves (see e.g. [Duv89]), existence and uniqueness of the solutions
and the termination of our computations can be ensured.

In [ACFG05] the results of [FG04, FG06] are generalized to algebraic
solutions. It is well known that algebraic solutions can be represented as
Puiseux series. The advantage is that they can be fully described by its
minimal polynomial. In this package we mainly follow [ACFG05], but we use an
adapted version of the algorithm there for deciding the existence of algebraic
solutions and computing all of them in the affirmative case.

##  2\. Theoretical and Algorithmic Framework

In this section we recall the main notions and results that are used in our
implementations. For further details we refer to [CFS20] in the case of formal
Puiseux series and to [ACFG05] in the case of algebraic solutions.

Let $\mathbb{K}$ be a computable field of characteristic zero such as the
rational numbers $\mathbb{Q}$ and let us denote by $\overline{\mathbb{K}}$ its
algebraic closure. Let us consider the differential equation

(2.1) $F(y,y^{\prime})=0,$

where $F\in\mathbb{K}[y,p]$ is square-free and non-constant in the variables
$y$ and $p$. We are looking for formal Puiseux series and algebraic solutions
of (2.1). In the case of formal Puiseux series solutions we will represent the
full series by a sufficiently large truncation such that existence and
uniqueness are guaranteed. In the case of algebraic solutions we look for its
minimal polynomial.

We associate to (2.1) the affine algebraic curve
$C(F)\subset\overline{\mathbb{K}}^{2}$ defined by the zero set of $F(y,p)$ in
$\overline{\mathbb{K}}^{2}$. We denote by $\mathscr{C}(F)$ the Zariski closure
of $C(F)$ in $\overline{\mathbb{K}}_{\infty}^{2}$, where
$\overline{\mathbb{K}}_{\infty}=\overline{\mathbb{K}}\cup\\{\infty\\}$ denotes
the one-point compactification of $\overline{\mathbb{K}}$. In the case of
formal Puiseux series solutions we will look for local parametrizations of
$\mathscr{C}(F)$ and in the case of algebraic solutions for algebraic
parametrizations, respectively.

###  2.1. Formal Puiseux Series Solutions

Formal Puiseux series can either be expanded around a finite point or at
infinity. In the first case, since equation (2.1) is invariant under
translation of the independent variable, without loss of generality we can
assume that the formal Puiseux series is expanded around zero and it is of the
form $\varphi(x)=\sum_{j\geq j_{0}}a_{j}\,x^{j/n}$, where
$a_{j}\in\overline{\mathbb{K}},$ $n\in\mathbb{Z}_{>0}$ and
$j_{0}\in\mathbb{Z}$. In the case of infinity we can use the transformation
$x=1/z$ obtaining the (non-autonomous) differential equation
$F(y(z),-z^{2}y^{\prime}(z))=0$. In order to deal with both cases in a unified
way, we will study equations of the type

(2.2) $F(y(x),(1-h)x^{h}y^{\prime}(x))=0,$

with $h\in\\{0,2\\}$ and its formal Puiseux series solutions expanded around
zero. We note that for $h=0$ equation (2.2) is equal to (2.1) and for $h=2$
the case of formal Puiseux series solutions expanded at infinity is treated.

We use the notations $\mathbb{L}[[x]]$ for the ring of formal power series,
$\mathbb{L}((x))$ for its fraction field and
$\mathbb{L}((x))^{*}=\bigcup_{n\geq 1}\mathbb{L}((x^{1/n}))$ for the field of
formal Puiseux series expanded at zero with coefficients in some field
$\mathbb{L}$. We call the minimal natural number $n$ such that $\varphi(x)$
belongs to $\mathbb{L}((x^{1/n}))$ the ramification order of $\varphi(x)$.
Moreover, for $\varphi(x)=\sum_{j\geq j_{0}}a_{j}\,x^{j/n}$ with
$a_{j_{0}}\neq 0$ we call $j_{0}/n\in\mathbb{Q}$ the order of $\varphi$,
denoted by $\operatorname{ord}_{x}(\varphi(x))$, and set
$\operatorname{ord}_{x}(\varphi(x))=\infty$ for $\varphi=0$.

Additionally to (2.2) we may require that a formal Puiseux series solution
$y(x)$ of (2.2) fulfills the initial conditions
$y(0)=y_{0},((1-h)x^{h}y^{\prime}(x))(0)=p_{0}$ for some fixed
$\mathbf{p}_{0}=(y_{0},p_{0})\in\overline{\mathbb{K}}_{\infty}^{2}$. In the
case where $y(0)=\infty$, $\tilde{y}(x)=1/y(x)$ is a Puiseux series solution
of a new first order differential equation of the same type, namely the
equation given by the numerator of the rational function
$F(1/y,-(1-h)x^{h}p/y^{2})$, and $\tilde{y}(0)\in\overline{\mathbb{K}}$.
Therefore, in the sequel, we may assume that
$\mathbf{p}_{0}\in\overline{\mathbb{K}}\times\overline{\mathbb{K}}_{\infty}$.

#### Formal Parametrizations.

Let us recall some classical terminology on local parametrizations of
algebraic curves and its algorithmic aspects, for further details see e.g.
[Wal50, Duv89].

A formal parametrization centered at $\mathbf{p}_{0}\in\mathscr{C}(F)$ is a
pair of formal Puiseux series
$A(t)\in\overline{\mathbb{K}}((t))^{2}\setminus\overline{\mathbb{K}}^{2}$ such
that $A(0)=\mathbf{p}_{0}$ and $F(A(t))=0$. In the set of all formal
parametrizations of $\mathscr{C}(F)$ we introduce the equivalence relation
$\sim$ by defining $A(t)\sim B(t)$ if and only if there exists a formal power
series $s(t)\in\overline{\mathbb{K}}[[t]]$ of order one such that
$A(s(t))=B(t)$. A formal parametrization is said to be irreducible if it is
not equivalent to another one in $\overline{\mathbb{K}}((t^{m}))^{2}$ for some
$m>1$. An equivalence class of an irreducible formal parametrization
$(a(t),b(t))$ is called a place of $\mathscr{C}(F)$ centered at the common
center point $\mathbf{p}_{0}$ and is denoted by $[(a(t),b(t))]$.

Let $\operatorname{IFP}(\mathbf{p}_{0})$ denote the set of all irreducible
formal parametrizations of $\mathscr{C}(F)$ at $\mathbf{p}_{0}$ and
$\operatorname{Places}(\mathbf{p}_{0})$ containing the places of
$\mathscr{C}(F)$ centered at $\mathbf{p}_{0}$. Computationally we have to
truncate the formal parametrizations. There are bounds presented in [Duv89,
Sta00] such that

  1. (1)

the truncations of the formal parametrizations $(a(t),b(t))$ at
$\mathbf{p}_{0}$ are in one-to-one correspondence to
$\operatorname{Places}(\mathbf{p}_{0})$;

  2. (2)

the orders $\operatorname{ord}_{t}(a(t)-y_{0}),\operatorname{ord}_{t}(b(t))$
are determined;

  3. (3)

no further extension of the ground field for computing the following
coefficients have to be done.

For the monic case, a bound for the number of steps to compute it is
$2(\deg_{p}(F)-1)\deg_{y}(F)+1$ or the Milnor number. For the general case, a
similar bound based on the degree of the polynomial can be derived.

Let us note that the solutions of (2.2) will be independent of the chosen
representative of a place. Hence, regarding uniqueness of the prolongation,
number of field extensions, etc. it does not matter which local
parametrization we chose (for example classical Puiseux parametrizations or
rational Puiseux parametrization [Duv89]). For representing the solution
parametrizations, which is not the goal of the current paper, however, it
would be relevant.

#### Puiseux Solution Place.

Let $\operatorname{Sol}_{\overline{\mathbb{K}}((x))^{*}}(\mathbf{p}_{0})$ be
the set containing the non-constant formal Puiseux series solutions of
equation (2.2), expanded at zero, with coefficients in $\overline{\mathbb{K}}$
and with $\mathbf{p}_{0}$ as initial values. Then the mapping
$\Delta:\operatorname{Sol}_{\overline{\mathbb{K}}((x))^{*}}(\mathbf{p}_{0})\longrightarrow\operatorname{IFP}(\mathbf{p}_{0})$
defined as

$\Delta(y(x))=\left(y(t^{n}),(1-h)t^{hn}\,\frac{d\,y}{d\,x}(t^{n})\right),$

where $n$ is the ramification order of $y(x)$, is well-defined and injective.
Moreover, we denote by
$\delta:\operatorname{Sol}_{\overline{\mathbb{K}}((x))^{*}}(\mathbf{p}_{0})\longrightarrow\operatorname{Places}(\mathbf{p}_{0})$
the map $\delta(y(x))=[\Delta(y(x))]$.

An irreducible formal parametrization
$A(t)\in\operatorname{IFP}(\mathbf{p}_{0})$ is called a solution
parametrization of (2.1) if $A$ is in the image $\mathrm{Im}(\Delta)$.
Similarly, a place in $\mathrm{Im}(\delta)$ is called a (Puiseux) solution
place.

It can be shown that for solution parametrizations
$(a(t),b(t))\in\operatorname{IFP}(\mathbf{p}_{0})$, corresponding to a
solution with ramification index $n$, it holds that

(2.3) $\displaystyle
n(1-h)=\operatorname{ord}_{t}(a(t)-y_{0})-\operatorname{ord}_{t}(b(t)).$

This condition is invariant for the representative of a place. In particular,
all Puiseux series solutions in the same solution place have the same
ramification order. It turns out that condition (2.3) is already sufficient
for solution places at $\mathbf{p}_{0}$ with $y_{0}\in\overline{\mathbb{K}}$.
Let us highlight this statement (see Theorem 10 in [CFS20]):

######  Theorem 2.1.

Let $\mathcal{P}=[(a(t),b(t))]\in\operatorname{Places}(\mathbf{p}_{0})$ and
$h=0$. Then $\mathcal{P}$ is a solution place if and only if equation (2.3)
holds for an $n\in\mathbb{Z}_{>0}$. In the affirmative case the ramification
order of $\mathcal{P}$ is equal to $n$.

Also the solutions with $h=2$ can be computed algorithmically. For this
purpose let us give in the following some insight into to proof of Theorem
2.1.

Let $\mathbb{L}$ be a subfield of $\overline{\mathbb{K}}$. For a given
parametrization $(a(t),b(t)))\in\mathbb{L}((t))^{2}$ satisfying (2.3), our
strategy is to find $s(t)\in\overline{\mathbb{K}}[[t]]$ with
$\operatorname{ord}_{t}(s(t))=1$ such that $(a(s(t)),b(s(t)))$ satisfies the
associated differential equation

(2.4) $a^{\prime}(s(t))\cdot s^{\prime}(t)=n(1-h)\,t^{n(1-h)-1}\,b(s(t)).$

Let $k=\operatorname{ord}_{t}(a(t)-y_{0}),r=\operatorname{ord}_{t}(b(t))$ and
$n(1-h)=k-r>0$. By transforming (2.4) into an equation of Briot-Bouquet type
[BB56], the solutions $s(t)=\sum_{i=1}^{\infty}\sigma_{i}\,t^{i}$ fulfill the
following items.

  1. (1)

If $h=0$, there are exactly $n$ solutions where $\sigma_{1}^{n}\in\mathbb{L}$
and $\sigma_{i}\in\mathbb{L}(\sigma_{1})$ are uniquely determined for $i>1$.

  2. (2)

If $h=2$, there is no solution or up to $n$ one-parameter families of
solutions with $\sigma_{1}^{n}\in\mathbb{L}$, $\sigma_{r-k}\in\mathbb{L}$ is a
free parameter; $\sigma_{2},\ldots,\sigma_{r-k-1}\in\mathbb{L}(\sigma_{1})$
and for $i>r-k$ the coefficients
$\sigma_{i}\in\mathbb{L}(\sigma_{1},\sigma_{r-k})$ are uniquely determined.

After computing the solutions $s(t)$ of the associated differential equation,
we obtain the solutions of the original differential equation by
$a(s(x^{1/n}))$.

#### Solution Truncations.

Since we cannot compute all coefficients of the Puiseux series solution, we
have to truncate at some point. A point
$\mathbf{p}_{0}=(y_{0},p_{0})\in\mathscr{C}(F)$ is called a critical curve
point if $p_{0}\in\\{0,\infty\\}$ or $\frac{\partial F}{\partial
p}(\mathbf{p}_{0})=0$ or $y_{0}=\infty$. Under our assumptions, the set of
critical curve points is finite. The only formal Puiseux series solution with
non-critical $\mathbf{p}_{0}$ as initial tuple is a formal power series and
its determined solution truncation is given by $y_{0}+p_{0}x$.

Assume that $\mathbf{p}_{0}\in\mathscr{C}(F)$ is a critical curve point. Then,
by the properties of the solutions of the associated differential equations,
the bound on the number of computational steps from [Duv89, Sta00] also holds
for the computation of the determined solution truncations. In particular,
equation (2.3) can be checked, no further extensions of the ground field for
computing the coefficients are necessary and the ramification index is
determined. For the general case, a similar bound based on the degree of the
polynomial can be derived and we will write $N$ for such a bound.

Algorithm 1 PuiseuxSolve

0: A first-order AODE $F(y,y^{\prime})=0$, where $F\in\mathbb{K}[y,p]$ is
square-free with no factor in $\mathbb{K}[y]$ or $\mathbb{K}[p]$.

0: A set consisting of all solution truncations of $F(y,y^{\prime})=0$
(expanded around zero and around infinity).

1: If $(\infty,\infty)\in\mathscr{C}(F)$, then perform the transformation
$\tilde{y}=1/y$ and apply the following steps additionally to the numerator of
$F(1/y,-p/y^{2})$ and $\mathbf{p}_{0}=(0,0)$ in order to obtain the solutions
of negative order.

2: Compute the set of critical curve points $\mathcal{B}(F)$ (for
$y_{0}\in\overline{\mathbb{K}}$) and $\mathbb{V}(F(y,0))$ (for
$y_{0}=\infty$).

3: For every point
$(y_{0},p_{0})\in\mathscr{C}(F)\setminus\mathcal{B}(F),y_{0}\neq\infty$, a
determined solution truncation is $y_{0}+p_{0}x$.

4: Add to the output the constant solutions $y(x)=y_{0}$ corresponding to
$(y_{0},0)\in\mathscr{C}(F),y_{0}\neq\infty$.

5: For every place centered at a critical curve point
$\mathbf{p}_{0}=(y_{0},p_{0})\in\mathcal{B}(F)$ and
$(\infty,p_{0})\in\mathscr{C}(F)$, compute the first $N$ terms of a formal
parametrization $(a(t),b(t))$.

6: Check equation (2.3): In the negative case, $[(a(t),b(t)]$ is not a
solution place.

7: In the affirmative case, compute the first $N$ terms of the solutions
$s(t)$ of (2.4).For $y_{0}\neq\infty$ there exists exactly $n$ solutions. For
$y_{0}=\infty$ the associated differential equation is either unsolvable or
contains a free parameter.

8: The first $N$ terms of $a(s(x^{1/n}))$ are the solution truncations with
$\mathbf{p}_{0}$ as initial tuple.

For finite initial values we are able to ensure uniqueness of the extension of
the truncated Puiseux series solutions (see also [CFS20][Theorem 14]). In the
case of $y_{0}=\infty$ some truncations may coincide for specific values
obtained in the solution of the reparametrization.

###  2.2. Algebraic Solutions

In this section we consider a subclass of formal Puiseux series, namely
algebraic series. These are $y(x)\in\overline{\mathbb{K}}((x))^{*}$ such that
there exists a non-zero $G\in\overline{\mathbb{K}}[x,y]$ with $G(x,y(x))=0$.
Since the field of formal Puiseux series is algebraically closed, all
algebraic solutions can be represented as (formal) Puiseux series.

In [ACFG05] a bound on the degree of algebraic general solutions is given.
There the authors indicate how to use these results in order to compute all
algebraic solutions of such a given differential equation. A more detailed
proof of this fact can be found in [Fal20].

The first important observation is that if there exists one non-constant
algebraic solution of (2.1), then all of them can be found easily by a shift
in the minimal polynomial (see [Fal20][Theorem 4.1.22]).

######  Theorem 2.2.

Let $F\in\mathbb{K}[y,y^{\prime}]$ be irreducible and let $y(x)$ be a non-
constant solution of $F=0$ algebraic over $\overline{\mathbb{K}}(x)$ with
minimal polynomial $G\in\overline{\mathbb{K}}[x,y]$. Then all formal Puiseux
series solutions $\operatorname{Sol}_{\overline{\mathbb{K}}((x))^{*}}(F)$ are
algebraic and given by $G(x+c,y)$, where $c\in\overline{\mathbb{K}}$.

The second important computational aspect is the degree bound on the solutions
[ACFG05][Theorem 3.4, Theorem 3.8]:

######  Theorem 2.3.

Let $F\in\mathbb{K}[y,y^{\prime}]$ be irreducible and let $y(x)$ be a non-
constant solution of $F=0$ algebraic over $\overline{\mathbb{K}}(x)$ with
minimal polynomial $G\in\overline{\mathbb{K}}[x,y]$. Then

$\deg_{x}(G)=\deg_{p}(F),\quad\deg_{y}(G)\leq\deg_{y}(F)+\deg_{p}(F).$

The third result is used to construct candidates of algebraic solutions:

######  Lemma 2.4.

Let $G(x,y)\in\mathbb{K}[x,y]$ be an irreducible polynomial with
$d_{x}=\deg_{x}G,d_{y}=\deg_{y}G$. Let $y(x)$ be a Puiseux series solution of
$G(x,y)=0$ expanded at $x=0$ with $\operatorname{ord}_{x}(y(x))=\nu$. Let
$\nu^{\prime}=\min\\{\nu,0\\}$ and write $y(x)=\bar{y}(x)+\varphi(x)$ with
$\operatorname{ord}_{x}(\varphi(x))>N>0$ where

(2.5) $\displaystyle N$ $\displaystyle\geq
2\,d_{x}\,d_{y}-2\,\nu^{\prime}\,(d_{y}-1).$

Assume that $A(x,y)\in\mathbb{K}[x,y],\deg_{x}A\leq d_{x}$, $\deg_{y}A\leq
d_{y}$ is of minimal degree such that

(2.6) $\displaystyle\operatorname{ord}_{x}(A(x,\bar{y}(x))$
$\displaystyle>2\,d_{x}\,d_{y}-\nu^{\prime}(d_{y}-1),$

holds. Then $A(x,y)$ is, up to a constant factor, equal to $G(x,y)$.

###### Proof.

Let $R(x)$ be the resultant of $G(x,y)$ and $A(x,y)$ with respect to $y$. It
is well known that there exist polynomials $B(x,y)$, $C(x,y)$ with
$\deg_{y}B<d_{y}$, $\deg_{y}C<d_{y}$ such that

$G(x,y)\,B(x,y)+A(x,y)\,C(x,y)=R(x).$

Evaluating at $\bar{y}(x)$ we obtain

(2.7)
$G(x,\bar{y}(x))\,B(x,\bar{y}(x))+A(x,\bar{y}(x))\,C(x,\bar{y}(x))=R(x).$

Since $\nu^{\prime}\leq 0$, it follows that
$\operatorname{ord}_{x}C(x,\bar{y}(x))\geq\nu^{\prime}\,\deg_{y}C\geq\nu^{\prime}(d_{y}-1)$
and similarly for $B(x,\bar{y}(x))$. Hence, by (2.6), we have that

$\operatorname{ord}_{x}(A(x,\bar{y}(x))\,C(x,\bar{y}(x)))>2\,d_{x}\,d_{y}.$

Let us proof that
$\operatorname{ord}_{x}(G(x,\bar{y}(x))>\nu^{\prime}(d_{y}-1)+N$. Taking the
Taylor series of $G(x,\bar{y}(x)+\varphi(x))$ and because
$G(x,\bar{y}(x)+\varphi(x))=0$, we have:

$\displaystyle
G(x,\bar{y}(x))=-\sum_{j=1}^{d_{y}}\frac{1}{j!}\frac{\partial^{j}G}{\partial
y^{j}}(x,\bar{y}(x))\,\varphi(x)^{j}.$

The order in $x$ of each term on the right hand side of above equation is
greater than $\nu^{\prime}\,(d_{y}-1)+N$, so it is for the left hand side.
Now, because of (2.5), we have that

$\displaystyle\operatorname{ord}_{x}(G(x,\bar{y}(x))\,B(x,\bar{y}(x)))>\nu^{\prime}(d_{y}-1)+N+\nu^{\prime}(d_{y}-1)\geq
2\,d_{x}\,d_{y}.$

Hence, the left hand side of (2.7) has order greater than $2\,d_{x}\,d_{y}$
and the right hand side is a polynomial of degree less than or equal to
$2\,d_{x}\,d_{y}$. Hence, $R(x)=0$, and therefore, $G(x,y)$ and $A(x,y)$ have
a common factor. Since $G(x,y)$ is an irreducible polynomial, it is a factor
of $A(x,y)$. Then, by the degree conditions on $A(x,y)$, the statement
follows. ∎

In [ACFG05] the method of detecting candidates $G(x,y)$ for algebraic
solutions of the differential equations $F(y,y^{\prime})=0$ consists by
computing $\bar{y}(x)$, the first $N$ terms of a power series solution $y(x)$
of the differential equations $F(y,y^{\prime})=0$, with a regular curve point
of $\mathscr{C}(F)$ as initial tuple. Hence, in this case the solution $y(x)$
is of order $0$ and $\nu^{\prime}=0$. Choose $N>d_{x}\,d_{y}$ and construct,
by solving a linear system of equations, a polynomial $A$ fulfilling the
properties (2.5) and (2.6). This approach reduced the number of formal power
series solutions that we can use to construct a candidate. Lemma 2.4 allows to
choose any Puiseux series solutions of the differential equations and reduce
the computational cost.

Once a candidate $A(x,y)$ is detected, we can check whether it is an actual
algebraic solution of the differential equation $F(y,y^{\prime})=0$ by
checking whether the differential pseudo remainder of $F(y,y^{\prime})$ with
respect $A(x,y)$ is zero. These results lead to the following algorithm.

Algorithm 2 AlgebraicSolve

0: A first-order AODE $F(y,y^{\prime})=0$, where $F\in\mathbb{K}[y,p]$ is
irreducible over $\overline{\mathbb{K}}(y)$.

0: The minimal polynomial of an algebraic solution of $F(y,y^{\prime})=0$,
describing all solutions, if it exists.

1: Compute the minimal number of terms of all Puiseux solutions of
$F(y,y^{\prime})=0$ using PuiseuxSolve and choose one of them, denote it by
$\hat{y}(x)$. Let $\nu$ be its order, $\nu^{\prime}=\min(\nu,0)$ and $n$ its
ramification index.

2: Let $d_{x}=\deg_{p}F$ and $d_{y}=\deg_{y}F+\deg_{p}F$.

3: Compute the prolongation $\bar{y}(x)$ of $\hat{y}(x)$ up to order
$N=2\,d_{x}\,d_{y}-2\,\nu^{\prime}\,(d_{y}-1)+1/n$.

4: Compute $A(x,y)\in\overline{\mathbb{K}}[x,y]$ fulfilling the required
conditions from Lemma 2.4 by an ansatz of unknown coefficients and solving the
resulting linear system.

5: Check whether $\operatorname{prem}(F,A)=0$. If so, then $A(x,y)$ is an
actual solution. Otherwise there exists no algebraic solution.

##  3\. The Package FirstOrderSolve

In this section, we present the structure and content of the MAPLE package
FirstOrderSolve. It consists several procedures that implement in particular
the algorithms PuiseuxSolve and AlgebraicSolve described above. This package
computes the Puiseux series solutions and algebraic solutions of first order
autonomous AODEs with coefficients in an algebraic extension field of
$\mathbb{Q}$.

###  3.1. Overview of the Software Structure

The created MAPLE package is initialized by the command

> with(FirstOrderSolve):
The main procedures are

  * •

SolutionTruncations: for computing all formal Puiseux series solutions
(Algorithm PuiseuxSolve);

  * •

AlgebraicSolution: for computing the minimal polynomial of the algebraic
solutions (Algorithm AlgebraicSolve);

  * •

GenericSolutionTruncation: for computing a truncation of the solutions with
non-critical initial tuple;

  * •

ProlongSolutionTruncation: for prolonging the solution truncations up to a
higher degree.

These four commands are public to the user. The package is divided into
several sub-packages BriotBouquetSolve, LocalSolve, AlgebraicSolve, which are
not accessible for the user, and uses the hierarchy scetched below.

FirstOrderSolve AlgebraicSolve LocalSolve BriotBouquetSolve  Figure 1. The
hierarchy of the package.

The main commands in the sub-packages are the following.

  * •

ParametrizationSetAlgCurve: for computing the formal parametrizations of an
implicitly defined algebraic curve by using the command algcurves:-puiseux;

  * •

ReparametrizationSet: for computing the solutions of the associated
differential equation by using BriotBouquetSolve;

  * •

BriotBouquetSolve: for computing the unique solution of a first-order
differential equation in quasi-solved form (which is called an equation of
Briot-Bouquet type [BB56][Section 80,86]); this procedure is using a Newton
type algorithm for solving the resulting linear system in several variables;

In the following, we give a description of the procedures in the package
FirstOrderSolve. The package is available at risc.jku.at/sw/firstordersolve/,
where a more detailed information on the commands is presented in the help.

###  3.2. Description of the Software Components

> SolutionTruncations
Computes all Puiseux series solutions of a given first order autonomous
ordinary differential equation.
Since the equation is autonomous, the translation of the independent variable
by any constant in a solution is again a solution. Hence, the only relevant
expansion points are $0$ and infinity.
The solutions expanded at $0$ can be split into two sets: a generic solution
and a set of particular solutions. The generic solution is addressed in
GenericSolutionTruncation and consists of all solutions starting with a non-
critical curve point. Each critical curve point corresponds to a set (that
could be empty) of particular Puiseux series solutions.
The command computes the generic solution, all particular solutions expanded
at $0$ and all solutions expanded at infinity. The solutions are represented
as truncations such that existence and uniqueness is ensured. In other words,
the truncations are in one-to-one correspondence to the solutions. By setting
the optional arguments genericsolution, const, computeFinite, computeInf to
false, the corresponding subsets of the solution set can be suppressed. The
remaining option iv$=y_{0}$ represents an initial condition of the format
$y(0)=y_{0}$, where $y_{0}$ is an element of the ground field or an algebraic
extension field of it, which is additionally taken into account.

  * $\diamond$

Calling Sequence: > SolutionTruncations(F, N, options)

  * $\diamond$

Input: a polynomial $F$ in $y,y^{\prime}$, a rational number $N$ (by default
set to zero) and several optional arguments: genericsolution, const,
computeFinite, computeInf (all boolean) and a constant iv.

  * $\diamond$

Output: a list consisting of three components: the generic solutions, the
solutions expanded at $0$ and the solutions expanded at infinity represented
as truncated Puiseux series (modulo $x^{N}$).

> GenericSolutionTruncation
The first order differential equation has a generic local solution
$y(x)=y_{0}+y_{1}x+\mathcal{O}(x^{2})$, where $F(y_{0},y_{1})=0$. If $F$ is
irreducible as polynomial and $(y_{0},y_{1})$ is a regular affine point of the
curve implicitly defined by $F$, the extension of $y_{0}+y_{1}x$ to a solution
$y(x)$ is guaranteed and unique. The command GenericSolutionTruncation
computes the first terms of the generic (formal) power series solutions,
expanded around $0$, of the given differential equation.

Note that for every irreducible component one generic solution is computed.
Thus, all generic solutions of $F=0$ are given by the union of the generic
solutions of the components. If the given differential equation is known to be
irreducible, the optional argument irreducible=true (see below) can be used in
order to speed up computations.

The output of the command is a set of lists with two entries: a polynomial in
$x$ representing the solution computed modulo $x^{N}$ involving an unspecified
parameter $\\_CC$ and a set of exceptional values for $\\_CC$. For these
values the generic solution would in general not lead to a solution of the
given differential equation or might involve fractional exponents. Finally,
let us mention that, if the precision of the output is not high enough, it is
possible to use the command ProlongSolutionTruncation; see below.

  * $\diamond$

Calling Sequence: > GenericSolutionTruncation(F, N, options)

  * $\diamond$

Input: a polynomial $F$ in $y,y^{\prime}$, a rational number $N$ (by default
set to zero), and optionally irreducible as boolean.

  * $\diamond$

Output: is a set of lists with two entries: a polynomial in $x$ representing
the solution computed modulo $x^{N}$ involving an unspecified parameter
$\\_CC$ and a set of exceptional values for $\\_CC$.

> ProlongSolutionTruncation
For the given first order differential equation, if an appropriate change of
variables $z(x)=y(x)+s(x)$ is performed, the resulting equation

$G(x,z(x),z^{\prime}(x))=F(y(x)+s(x),y^{\prime}(x)+s^{\prime}(x))=0$

might be of Briot-Bouquet type. In case that $s(x)$ is such a solution
truncation of $y(x)$, existence and uniqueness of the solution $z(x)$ of $G$
are ensured and the following coefficients can be found by a Newton type
algorithm. In particular, this is the case when $s(x)$ is an output element of
GenericSolutionTruncation or SolutionsTruncations.

In this situation, the command ProlongSolutionTruncation prolongs the first
terms of a truncated Puiseux series solution $s(x)$ of
$F(y(x),y^{\prime}(x))=0$.

  * $\diamond$

Calling Sequence: > ProlongSolutionTruncation(F, s, N, x0)

  * $\diamond$

Input: a polynomial $F$ in $y,y^{\prime}$, a polynomial $s$, a rational number
$N$ and $x0$ equals $0$ or infinity (by default set to zero)

  * $\diamond$

Output: it is again a truncated Puiseux series computed until the order
$x^{N}$ (or $1/x^{N}$)

> AlgebraicSolution
Algebraic solutions of the first order autonomous differential equation are
represented by its minimal polynomisl, say $G(x,y)$. In this case, all the
functions $y(x)$ with $G(x,y(x))=0$ are solutions of this differential
equation and can be represented as Puiseux series.

Assuming that $F$ is an irreducible polynomial, the existence of algebraic
solutions can be decided and, in the affirmative case, all solutions are
algebraic and are given as shift of the independent variable, namely by
$G(x+c,y)$. Therefore, by factorizing the given differential equation, all
algebraic solutions can be found using this procedure for every component.

The command AlgebraicSolution decides the existence of algebraic solutions of
the given differential equation. Furthermore, if a solution exists the output
is the minimal polynomial of the solution. The other solutions then can be
easily found by shifting $x$. The solutions are found by checking whether a
particular solution is algebraic. Efficiency of the algorithm highly depends
on the chosen initial value. The procedure is using a formal power series
solution, which means non-negative integer exponents for the solution, with a
relatively small number of algebraic extensions of the ground field. Similarly
to the command GenericSolutionTruncation, if the given differential equations
is known to be irreducible, this can be specified by the optional argument
irreducible=true.

  * $\diamond$

Calling Sequence: > AlgebraicSolution(F, options)

  * $\diamond$

Input: $F$ is a first-order differential polynomial, and irreducible is a
boolean option.

  * $\diamond$

Output: the decision on the existence of algebraic solutions of the
differential equation. If a solution exists the output is the minimal
polynomial of the solution.

###  3.3. Usage of the Package

In order to use the package, download the file FirstOrderSolve.m from
https://risc.jku.at/sw/firstordersolve/ and save it as your local folder.
After starting Maple you redefine the variable libname as

> libname:=libname, ’path of user local folder’;

Then, after executing the command

> with(FirstOrderSolve);

the package can be used. In the appendix we provide a Maple Worksheet
illustrating the usage of our package for the computation of all Puiseux
series solutions of first-order autonomous ordinary differential equations. We
provide at https://risc.jku.at/sw/firstordersolve/ an extended version of this
file.

## References

  * [ACFG05] J.M. Aroca, J. Cano, R. Feng, and X.-S. Gao.  Algebraic General Solutions of Algebraic Ordinary Differential Equations.  In Proceedings of the 2005 international symposium on Symbolic and algebraic computation, pages 29–36. ACM, 2005.
  * [Aro00] J.M. Aroca.  Puiseux Solutions of Singular Differential Equations, pages 129–145.  Birkhäuser Basel, Basel, 2000.
  * [BB56] C.A. Briot and J.C. Bouquet.  Recherches sur les proprietés des équations différentielles.  Journal de l’Ecole Polytechnique, 21:36:133–198, 1856.
  * [Can05] J. Cano.  The Newton Polygon Method for Differential Equations.  In Proceedings of the 6th International Conference on Computer Algebra and Geometric Algebra with Applications, IWMM’04/GIAE’04, pages 18–30, Berlin, Heidelberg, 2005. Springer-Verlag.
  * [CFS20] Jose Cano, Sebastian Falkensteiner, and J Rafael Sendra.  Existence and Convergence of Puiseux Series Solutions for First Order Autonomous Differential Equations.  Journal of Symbolic Computation, 2020.
  * [DDRJ97] J. Della Dora and F. Richard-Jung.  About the Newton Algorithm for non-linear Ordinary Differential Equations.  In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, pages 298–304, New York, NY, USA, 1997\. ACM.
  * [Duv89] D. Duval.  Rational Puiseux Expansion.  Compositio Mathematica, 70(2):119–154, 1989.
  * [Fal20] S. Falkensteiner.  Power Series Solutions of AODEs - Existence, Uniqueness, Convergence and Computation.  PhD thesis, RISC Hagenberg, Johannes Kepler University Linz, 2020.
  * [FG04] R. Feng and X.-S. Gao.  Rational General Solutions of Algebraic Ordinary Differential Equations.  In Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 155–162. ACM, 2004.
  * [FG06] R. Feng and X.-S. Gao.  A polynomial time Algorithm for finding rational general solutions of first order autonomous ODEs.  Journal of Symbolic Computation, 41(7):739–762, 2006.
  * [Fin89] H. Fine.  On the Functions defined by Differential Equations, with an Extension of the Puiseux Polygon Construction to these Equations.  American Journal of Mathematics, 11:317–328, 1889.
  * [Fin90] H. Fine.  Singular Solutions of Ordinary Differential Equations.  American Journal of Mathematics, 12:295–322, 1890.
  * [GS91] D.Y. Grigoriev and M. Singer.  Solving Ordinary Differential Equations in Terms of Series with Real Exponents.  Trans A.M.S., 327:329–351, 1991.
  * [Sta00] P. Stadelmeyer.  On the Computational Complexity of Resolving Curve Singularities and Related Problems.  PhD thesis, RISC, Johannes Kepler University Linz, 2000.
  * [VGW18] N.T. Vo, G. Grasegger, and F. Winkler.  Deciding the Existence of Rational General Solutions for First-Order Algebraic ODEs.  Journal of Symbolic Computation, 87:127–139, 2018.
  * [Wal50] R.J. Walker.  Algebraic Curves.  Princeton University Press, 1950.


#  Minor-closed classes of binary functions

Benjamin R. Jones
Faculty of Information Technology
Monash University
Clayton, Victoria 3800
Australia
Email<EMAIL_ADDRESS>
###### Abstract

Binary functions are a generalisation of the cocircuit spaces of binary
matroids to arbitrary functions. Every rank function is assigned a binary
function, and the deletion and contraction operations of binary functions
generalise matroid deletion and contraction.

We give the excluded minor characterisations for the classes of binary
functions with well defined minors, and those with an associated rank
function. Within these classes, we also characterise the classes of binary
functions corresponding to polymatroids, matroids and binary matroids by their
excluded minors. This gives a new proof of Tutte’s excluded minor
characterisation of binary matroids in the more generalised space of binary
functions.

##  1 Introduction

A _binary function_ on a finite _ground set_ $E$ is a function $f\colon
2^{E}\to\mathbb{R}$ with $f(\emptyset)=1$.

Binary functions were introduced in [3] as a generalisation of cocircuit
spaces of binary matroids. A rank transform assigns a (not necessarily
matroid) rank function to any binary function. When $f$ is the indicator
function of a binary vector space, then the rank transform on $f$ gives the
rank function of the associated binary matroid. Aspects of the theory of
binary matroids have been extended to binary functions, including deletion,
contraction, duality and Tutte-Whitney polynomials [3, 4, 5].

Many important results in graph and matroid theory are characterisations of
classes closed under deletion and contraction by a set of _excluded minors_.
In graph theory, results range from Wagner’s characterisation [16] of planar
graphs to the theorem of Robertson and Seymour [12] that any minor-closed
class of graphs can be characterised by a finite set of excluded minors.

The first excluded minor characterisations for matroids were due to Tutte, and
included the classes of regular [14] and graphic [15] matroids. A proof of
Rota’s conjecture, that the number of excluded minors for matroids
representable over any given finite field is finite, has been announced [7].
The excluded minors for representability over finite fields have been found
for the fields $GF(2)$ [14], $GF(3)$ [1, 13] and $GF(4)$ [6]. Unlike graphs,
minor-closed classes of matroids can have an infinite number of excluded
minors. One of the first discovered examples is the class of matroids
representable over any field [9].

In this paper, we establish the first excluded minor characterisations of
classes of binary functions. We find excluded minor characterisations of those
binary functions for which every minor is well defined, and of those with well
defined rank functions. We also find the excluded minor characterisation for
the class of binary functions corresponding to binary matroids.

We identify the classes of binary functions corresponding, via the rank
transform, to matroids and polymatroids, and give excluded minor
characterisations of these classes. By classifying matroids and binary
matroids in the larger class of binary functions, we find a novel proof of
Tutte’s characterisation of binary matroids among matroids.

##  2 Operations on binary functions

For a binary function $f\colon 2^{E}\to\mathbb{R}$, we have $f(\emptyset)=1$.
Unless otherwise stated, we will assume that $f$ is a binary function with
ground set $E$. The _order_ of a binary function is the size of its ground
set.

Contraction and deletion operations on binary functions were introduced in
[3].

The _contraction_ of a set $X\subseteq E$ from a binary function $f$ gives the
binary function $f/X\colon 2^{E\backslash X}\to\mathbb{R}$ given by

$f/X(Y)=f(Y).$

The _deletion_ of $X\subseteq E$ from $f$ gives the binary function
$f\backslash X\colon 2^{E\backslash X}\to\mathbb{R}$ given by

$f\backslash X(Y)=\frac{\sum_{Z\subseteq X}f(Y\cup Z)}{\sum_{Z\subseteq
X}f(Z)}.$

We will write $f/e$ instead of $f/\\{e\\}$ when contracting by a single
element $e\in E$, and likewise write $f\backslash{e}$ for
$f\backslash\\{e\\}$.

Two binary functions $f$ and $f^{\prime}$, with ground sets $E$ and
$E^{\prime}$ respectively, are _isomorphic_ if there is a bijection $\phi:E\to
E^{\prime}$ such that, for all $X\subseteq E$,
$f(X)=f^{\prime}(\\{\phi(x):x\in X\\})$.

Note that deletion and contraction of elements commute, as shown in [3]. We
define a _minor_ of a binary function $f$ to be a binary function obtained by
a sequence of contractions and deletions of ground set elements from $f$. A
minor of a binary function $f$ is _proper_ if it has order less than the order
of $f$.

A minor of a binary function may not be well defined. For example, if
$f(\\{e\\})=-1$, then $f\backslash e$ is not well defined. We call a binary
function $f$ _stable_ if, for all disjoint $X,Y\subseteq E$, $f/X\backslash Y$
is well defined.

A class of stable binary functions is _minor-closed_ if it closed under taking
minors.

An _excluded minor_ of a minor-closed class $\mathcal{C}$ of binary functions
is a binary function $f\notin\mathcal{C}$, such that all proper minors of $f$
are in $\mathcal{C}$. Equivalently, $f$ is an excluded minor of $\mathcal{C}$
if $f\notin\mathcal{C}$ and, for every $e\in E$,
$f\backslash{e},f/e\in\mathcal{C}$.

There is only one binary function of order zero, namely
$f:\\{\emptyset\\}\to\mathbb{R}$ where $f(\emptyset)=1$.

When $|E|=1$, we define $f_{\alpha}\colon 2^{E}\to\mathbb{R}$ to be the unique
(up to isomorphism) order-one binary function with $f_{\alpha}(E)=\alpha$.

##  3 Well-definedness of minors and rank

The first step to understanding minor-closed classes of binary functions is to
understand stable binary functions. It turns out that this class is minor-
closed.

######  Proposition 3.1.

The stable binary functions are a minor-closed class.

Proof. Let $g$ be a minor of a stable binary function $f$. Any minor of $g$ is
also a minor of $f$ and so is well defined. Therefore $g$ is stable.
$\hfill\Box$

Since this class is closed under taking minors, we can characterise it in
terms of its excluded minors.

######  Theorem 3.2.

A binary function is stable if and only if it has no minor isomorphic to
$f_{-1}$.

Proof. $(\Leftarrow)$ The binary function $f_{-1}$ is not stable, as
$f_{-1}\backslash E$ is not well defined. Therefore, any binary function that
has $f_{-1}$ as a minor is not stable.

$(\Rightarrow)$ If $f$ is not stable, there is some minor of $f$ which is not
well defined. Hence there exists disjoint $X,Y\subseteq E$ such that
$f\backslash X/Y$ is not well defined. Then $f\backslash X$ is not well
defined, since contraction of a well defined binary function is well defined.
Let $|X|$ be minimum such that $f\backslash X$ is not well defined and note
that $X$ is nonempty, as $f$ is well defined.

Let $e\in X$, and take $g=f\backslash(X\backslash\\{e\\})$. The binary
function $g$ on ground set $E^{\prime}=E\backslash(X\backslash\\{e\\})$ is
well defined, while $g\backslash e=f\backslash X$ is not. Therefore
$g(\\{e\\})=-1$, and so $f\backslash(X\backslash\\{e\\})/(E\backslash
X)=g/(E^{\prime}\backslash\\{e\\})\cong f_{-1}$, as required. $\hfill\Box$

The _rank transform_ $Q$ takes a binary function $f$ to its _rank function
$Qf\colon 2^{E}\to\mathbb{R}$_, defined in [3] by

$Qf(X):=\log_{2}\left(\frac{\sum\limits_{Y\subseteq
E}f(Y)}{\sum\limits_{Y\subseteq E\backslash X}f(Y)}\right).$ (3.1)

Note that $Qf(X)$ is not defined for all binary functions, as the fraction in
(3.1) may be undefined or nonpositive. We say a binary function $f$ is
_rankable_ if $Qf$ is well defined. We remark from [3] that if $f$ is
rankable, $Qf(\emptyset)=0$, and that for any function $\rho\colon
2^{E}\to\mathbb{R}$ with $\rho(\emptyset)=0$ there is a binary function $f$
with $Qf=\rho$.

We will now determine some properties of rankable binary functions.

######  Proposition 3.3.

A binary function $f$ on ground set $E$ is rankable if and only if, for each
$X\subseteq E$,

$\sum\limits_{Y\subseteq X}f(Y)>0.$

Proof.  $(\Rightarrow)$ Suppose $f$ is rankable. Then, for each $X\subseteq
E$,

$\begin{array}[]{rcl}Qf(E)-Qf(E\backslash
X)&=&\log_{2}\left(\frac{\sum\limits_{Y\subseteq
E}f(Y)}{f(\emptyset)}\right)-\log_{2}\left(\frac{\sum\limits_{Y\subseteq
E}f(Y)}{\sum\limits_{Y\subseteq X}f(Y)}\right)\\\
&=&\log_{2}\left({\sum\limits_{Y\subseteq X}f(Y)}\right),\end{array}$

is well defined, and hence $\sum\limits_{Y\subseteq X}f(Y)>0$.

$(\Leftarrow)$ Suppose for each $X\subseteq E$ that $\sum\limits_{Y\subseteq
X}f(Y)>0$. Then, for any $Z\subset E$,

$Qf(Z)=\log_{2}\left(\frac{\sum\limits_{Y\subseteq
E}f(Y)}{\sum\limits_{Y\subseteq E\backslash Z}f(Y)}\right)$

is well defined, so $f$ is rankable. $\hfill\Box$

######  Proposition 3.4.

If $f$ is rankable, then it is stable.

Proof. We prove the contrapositive. Suppose $f\colon 2^{E}\to\mathbb{R}$ is a
non-stable binary function. By Theorem 3.2, $f$ has $f_{-1}$ as a minor, and
so $E$ can be partitioned into sets $E=\\{e\\}\cup X\cup Z$ such that
$f\backslash{X}/Z=f_{-1}$ (on ground set $\\{e\\}$). Hence we have

$\begin{array}[]{rl}-1=f\backslash{X}/Z(\\{e\\})&=\dfrac{\sum_{Y\subseteq
X}f(Y\cup\\{e\\})}{\sum_{Y\subseteq X}f(Y)}\\\ &\\\ &=\dfrac{\sum_{Y\subseteq
X\cup\\{e\\}}f(Y)}{\sum_{Y\subseteq X}f(Y)}-1,\end{array}$

and so $\sum_{Y\subseteq X\cup\\{e\\}}f(Y)=0$. But by Proposition 3.3 we have
that $f$ is not rankable.$\hfill\Box$

######  Proposition 3.5.

The class of rankable binary functions is minor-closed.

Proof. By Proposition 3.4, every rankable binary function is stable. We only
have to show that rankable binary functions are closed under taking minors.

Let $f\colon 2^{E}\to\mathbb{R}$ be a rankable binary function, and $e\in E$.
Consider contraction. For all $X\subseteq E\backslash\\{e\\}$,

$\sum\limits_{Y\subseteq(E\backslash\\{e\\})\backslash
X}f/e(Y)=\sum\limits_{Y\subseteq E\backslash(X\cup\\{e\\})}f(Y)>0,$

and so, by Proposition 3.3, $f/e$ is rankable.

Now consider deletion. We first note that $1+f(\\{e\\})=\sum_{Y\subseteq
E\backslash(E\backslash\\{e\\})}f(Y)>0$, so $f\backslash e$ is well defined.
We have, for any $X\subseteq E\backslash\\{e\\}$,

$\sum\limits_{Y\subseteq(E\backslash\\{e\\})\backslash X}f\backslash
e(Y)=\sum\limits_{Y\subseteq
E\backslash(X\cup\\{e\\})}\frac{f(Y)+f(Y\cup\\{e\\})}{1+f(\\{e\\})}=\frac{1}{1+f(\\{e\\})}\sum\limits_{Y\subseteq
E\backslash X}f(Y)>0,$

and so $f\backslash e$ is rankable. Hence, contraction and deletion of a
rankable binary function gives a rankable binary function.$\hfill\Box$

We can now find the excluded minors of this class.

######  Theorem 3.6.

A binary function is rankable if and only if it has no minor isomorphic to
$f_{\alpha}$ for any $\alpha\leq-1$.

Proof. We write $f_{\alpha\leq-1}$ for some binary function $f_{\alpha}\colon
2^{\\{e\\}}\to\mathbb{R}$ with $f(\\{e\\})=\alpha\leq-1$.

$(\Rightarrow)$ Suppose $f$ has some $f_{\alpha\leq-1}$ as a minor. By
Proposition 3.3 the rank function of any $f_{\alpha\leq-1}$ is not defined, as
$\sum_{Y\subseteq E}f(Y)=1+\alpha\leq 0$. As rankable binary functions are
minor-closed by Proposition 3.5, $f$ is not rankable.

$(\Leftarrow)$ let $f\colon 2^{E}\to\mathbb{R}$ be a non-rankable binary
function. Suppose for contradiction that $f$ has no $f_{\alpha\leq-1}$ minor.
Furthermore, let us take $f$ with $|E|$ minimal. Therefore, all proper minors
of $f$ are rankable.

As $f$ is not rankable, by Proposition 3.3 there is some $X\subseteq E$ such
that

$\sum\limits_{Y\subseteq X}f(Y)\leq 0.$

As $f(\emptyset)=1$, we must have $X\neq\emptyset$, so let $e\in X$. Consider
$f\backslash{e}$, which is rankable. By Proposition 3.3, we have

$\sum\limits_{Y\subseteq
X\backslash\\{e\\}}f\backslash{e}(Y)=\sum\limits_{Y\subseteq
X\backslash\\{e\\}}\frac{f(Y)+f(Y\cup\\{e\\})}{f(\emptyset)+f(\\{e\\})}=\frac{1}{1+f(\\{e\\})}\sum\limits_{Y\subseteq
X}f(Y)>0.$

Hence $1+f(\\{e\\})<0$, and so $f/(E\backslash\\{e\\})\cong f_{\beta}$, for
some $\beta=f(\\{e\\})<-1$. As no proper minor of $f$ is isomorphic to some
$f_{\alpha\leq-1}$, we must have $f=f_{\beta}$, for $\beta<-1$. Therefore, if
$f$ is not rankable, it must have some $f_{\alpha\leq 1}$ as a minor.
$\hfill\Box$

Rankable binary functions are of particular interest, as the deletion and
contraction operations of binary functions correspond, via the rank transform,
to the rank deletion and contraction operations of matroids. From [3, Lemma
4.3] we have the following result.

######  Proposition 3.7.

Let $f\colon 2^{E}\to\mathbb{R}$ be a rankable binary function, and let
$X\subseteq E$ and $Y\subseteq E\backslash X$. Then

$\begin{array}[]{l}Q(f/X)(Y)=Qf(Y\cup X)-Qf(X),\\\ Q(f\backslash
X)(Y)=Qf(Y).\end{array}$

Note here that deletion and contraction for these rank functions are the same
operations as those used for rank functions of matroids and polymatroids.

##  4 Indicator functions of binary linear spaces

A binary function whose rank function is that of a binary matroid will be the
indicator function of a binary vector space. We will call these binary
functions _straight_. More formally, a binary function $f$ is _straight_ if it
is $\\{0,1\\}$-valued and, for all $X,Y\subseteq E$, if $f(X)=f(Y)=1$ then
$f(X\Delta Y)=1$. A binary function is _crooked_ if it is not straight.

Deletion and contraction operations on binary functions were shown to
correspond to matroid deletion and contraction in Proposition 3.7. As binary
matroids are closed under taking minors, the straight binary functions are a
minor-closed class.

We have the following result on minors of crooked binary functions, which will
be useful in finding the excluded minors of straight binary functions.

######  Theorem 4.1.

Let $f$ be a $\\{0,1\\}$-valued binary function. If $f$ is crooked, then it
has a crooked proper minor.

Proof.

As $f$ is crooked, there is some $X,Y\subseteq E$ such that
$f(X)=f(Y)=1\text{, and }f(X\Delta Y)=0$. Let us choose such $X$ and $Y$ with
minimum union.

Since $f(\emptyset)=1$, $X$ and $Y$ are distinct, so without loss of
generality take $e\in X\backslash Y$. We have

$\displaystyle f\backslash
e(X\backslash\\{e\\})=\frac{1+f(X\backslash\\{e\\})}{1+f(\\{e\\})},$ (4.1)
$\displaystyle f\backslash e(Y)=\frac{1+f(Y\cup\\{e\\})}{1+f(\\{e\\})},$ (4.2)
$\displaystyle f\backslash e((X\backslash\\{e\\})\Delta
Y)=\frac{f((X\backslash\\{e\\})\Delta Y)}{1+f(\\{e\\})}.$ (4.3)

Suppose that $f(X\backslash\\{e\\})=1$. As $f(Y)=1$, and
$|(X\backslash\\{e\\})\cup Y|<|X\cup Y|$, then by the minimality of $X$ and
$Y$, we have $f((X\backslash\\{e\\})\Delta Y)=1$. By (4.1) and (4.3) we have
$f\backslash e(X\backslash\\{e\\})=2/(1+f(\\{e\\}))$ and $f\backslash
e((X\backslash\\{e\\})\Delta Y)=1/(1+f(\\{e\\}))$ respectively. However, there
is no $f(\\{e\\})\in\\{0,1\\}$ such that $f\backslash e$ is
$\\{0,1\\}$-valued, and so $f\backslash e$ is crooked.

Let us now consider the case where $f(X\backslash\\{e\\})=0$. Suppose for
contradiction that $f\backslash e$ is straight.

As $f\backslash e$ is $\\{0,1\\}$-valued, $f(\\{e\\})=0$ by (4.1), as
$f(X\backslash\\{e\\})=0$. This in turn implies that $f(Y\cup\\{e\\})=0$ by
(4.2).

So by (4.1) and (4.2), $f\backslash e(X\backslash\\{e\\})=f\backslash e(Y)=1$,
and so $f\backslash e((X\backslash\\{e\\})\Delta Y)=1$ as $f\backslash e$ is
straight. Hence by (4.3) $f((X\Delta Y)\backslash\\{e\\})=1$.

We have $f((X\backslash\\{e\\})\Delta Y)=f(Y)=1$, and
$|(X\backslash\\{e\\})\Delta Y\cup Y|<|X\cup Y|$, and so by the minimality of
$X$ and $Y$ we have $f(X\backslash\\{e\\})=1$, which is a contradiction.
Therefore $f\backslash e$ is crooked. $\hfill\Box$

Theorem 4.1 implies that any excluded minor for the class of straight binary
functions is not $\\{0,1\\}$-valued. We now find the excluded minors for the
straight binary functions.

######  Theorem 4.2.

A binary function is straight if and only if it has no minor isomorphic to any
of:

  * •

$f_{\alpha}$, where $\alpha\in\mathbb{R}\backslash\\{0,1\\}$,

  * •

$g\colon 2^{\\{a,b\\}}\to\mathbb{R}$, where

$g(X)=\left\\{\begin{array}[]{rl}1&|X|=0,1\\\
-1&|X|=2\end{array}\right.,\text{ and}$

  * •

$f_{\mathcal{U}_{2,4}}\colon 2^{\\{a,b,c,d\\}}\to\mathbb{R}$, where

$f_{\mathcal{U}_{2,4}}(X)=\left\\{\begin{array}[]{rl}0&|X|=1,2\\\ 1&|X|=0,3\\\
-1&|X|=4.\end{array}\right.$

Proof. There is only one binary function of order 0, and it is straight.
Therefore, all crooked binary functions of order 1 will be excluded minors for
the class of straight binary functions.

A binary function of order 1, $f_{\alpha}$, is straight only if and only if
$\alpha\in\\{0,1\\}$, and so $f_{\alpha}$ is an excluded minor for the class
of straight binary functions for all
$\alpha\in\mathbb{R}\backslash{\\{0,1\\}}$.

We will now let $f$ be an excluded minor for the class of straight binary
functions of order at least two. By Proposition 4.1, $f$ is not
$\\{0,1\\}$-valued. For any $X\subset E$, $f/(E\backslash X)$ is a proper
minor of $f$, and so it is straight. So $f(X)=f/(E\backslash
X)(X)\in\\{0,1\\}$ for all $X\subset E$. As $f$ is not $\\{0,1\\}$-valued, we
must have $f(E)\notin\\{0,1\\}$.

Let $e\in E$. Then

$f\backslash
e(E\backslash\\{e\\})=\frac{f(E\backslash\\{e\\})+f(E)}{1+f(\\{e\\})}.$ (4.4)

Since $f\backslash
e(E\backslash\\{e\\}),f(E\backslash\\{e\\}),f({e})\in\\{0,1\\}$, and
$f(E)\notin\\{0,1\\}$, we must have $f(E)\in\\{-1,2\\}$ by (4.4).

Case 1: Suppose $f(E)=2$. By (4.4), we have $f(\\{e\\})=1$ and
$f(E\backslash\\{e\\})=0$ for all $e\in E$. Take distinct $d,e\in E$, and
consider the straight binary function $f\backslash e$. We have

$\displaystyle f\backslash
e(E\backslash\\{e\\})=\frac{f(E\backslash\\{e\\})+f(E)}{1+f(\\{e\\})}=\frac{0+2}{1+1}=1,$
(4.5) $\displaystyle f\backslash
e(\\{d\\})=\frac{f(\\{d\\})+f(\\{d,e\\})}{1+f(\\{e\\})}=\frac{1+f(\\{d,e\\})}{2},$
(4.6) $\displaystyle f\backslash
e(E\backslash\\{d,e\\})=\frac{f(E\backslash\\{d,e\\})+f(E\backslash\\{d\\})}{1+f(\\{e\\})}=\frac{f(E\backslash\\{d,e\\})+0}{2}.$
(4.7)

As $f\backslash e(\\{d\\})\in\\{0,1\\}$, and $f(E)=2$, we must have $|E|\geq
3$ by (4.6). We must then have $f(\\{d,e\\})\in\\{0,1\\}$, as
$\\{d,e\\}\subset E$, and so $f\backslash e(\\{d\\})=1$ by (4.6). Likewise,
$f\backslash e(E\backslash\\{d,e\\})=0$ by (4.7), as
$f(E\backslash\\{d,e\\})\in\\{0,1\\}$.

Using (4.5), we have $f\backslash e(E\backslash\\{e\\})=f\backslash
e(\\{d\\})=1$, and $f\backslash
e((E\backslash\\{e\\})\Delta\\{d\\})=f\backslash e(E\backslash\\{d,e\\})=0$.
Hence $f\backslash e$ is crooked, which is a contradiction. So $f$ is not an
excluded minor for the straight binary functions if $f(E)=2$.

Case 2: Suppose then that $f(E)=-1$. Then for all $e\in E$,
$f(E\backslash\\{e\\})=1$ by (4.4), as $f\backslash
e(E\backslash\\{e\\})\in\\{0,1\\}$. Take distinct $d,e\in E$.

$f\backslash
e(E\backslash\\{d,e\\})=\frac{f(E\backslash\\{d,e\\})+1}{1+f(\\{e\\})}.$ (4.8)

As $f\backslash{e}$ is straight, $f\backslash
e(E\backslash\\{d,e\\})\in\\{0,1\\}$, and so
$f(E\backslash\\{d,e\\})=f(\\{e\\})$, for any $d,e\in E$. Hence if $f(E)=-1$,
then $f(X)$ is constant for all sets $X\subseteq E$ of size 1 or $|E|-2$. This
constant is either 0 or 1.

Subcase 2.1: Suppose that $f(X)=1$ for all $X\subseteq E$ of size 1 or
$|E|-2$. If $|E|=2$, then there is a unique binary function $g$ satisfying
these conditions, namely

$g(X)=\left\\{\begin{array}[]{rl}1,&|X|=0,1,\\\ -1,&|X|=2.\end{array}\right.$

Deletion and contraction of any element gives a straight binary function, and
so $g$ is an excluded minor for the class of straight binary functions.

For $|E|\geq 3$, take distinct $d,e\in E$. We have

$\displaystyle f\backslash
e(E\backslash\\{d,e\\})=\frac{f(E\backslash\\{d,e\\})+f(E\backslash\\{e\\})}{1+f(\\{e\\})}=\frac{1+1}{1+1}=1,$
(4.9) $\displaystyle f\backslash
e(\\{d\\})=\frac{f(\\{d\\})+f(\\{d,e\\})}{1+f(\\{e\\})}=\frac{1+f(\\{d,e\\})}{1+1},$
(4.10) $\displaystyle f\backslash
e(E\backslash\\{e\\})=\frac{f(E\backslash\\{e\\})+f(E)}{1+f(\\{e\\})}=\frac{1-1}{1+1}=0.$
(4.11)

As $|E|\geq 3$, $f(\\{d,e\\})\in\\{0,1\\}$. Therefore, as $f\backslash{e}$ is
$\\{0,1\\}$-valued, $f(\\{d,e\\})=1$ and $f\backslash{e}(\\{d\\})=1$ by
(4.10). But then $f\backslash{e}$ is not straight, as $f\backslash
e(E\backslash\\{d,e\\})=f\backslash e(\\{d\\})=1$, but $f\backslash
e(E\backslash\\{e\\})=0$. Hence $f$ is not an excluded minor for the class of
straight binary functions.

Subcase 2.2: Suppose that $f(X)=0$ for all $X\subseteq E$ of size 1 or
$|E|-2$.

Note, there is no binary function of order 2 which satisfies this condition.
For $|E|\geq 3$, take any distinct $e,d\in E$. We have

$\displaystyle f\backslash
e(E\backslash\\{e\\})=\frac{f(E\backslash\\{e\\})+f(E)}{1+f(\\{e\\})}=f(E\backslash\\{e\\})-1,$
(4.12) $\displaystyle f\backslash
e(E\backslash\\{d,e\\})=\frac{f(E\backslash\\{d,e\\})+f(E\backslash\\{e\\})}{1+f(\\{e\\})}=f(E\backslash\\{e\\}),$
(4.13) $\displaystyle f\backslash
e(\\{d\\})=\frac{f(\\{d\\})+f(\\{d,e\\})}{1+f(\\{e\\})}=f(\\{d,e\\}).$ (4.14)

As $f\backslash{e}$ is $\\{0,1\\}$-valued and $f(E\backslash\\{e\\})=1$, we
must have $f\backslash{e}(E\backslash\\{e\\})=0$ for all $e\in E$ by (4.12).
Therefore $f\backslash e(E\backslash\\{d,e\\})=1$ by (4.13). As $f\backslash
e$ is straight, we must have $f\backslash e(\\{d\\})=f(\\{d,e\\})=0$ by
(4.14). Combining these results gives the following evaluations on $f$

$f(X)=\left\\{\begin{array}[]{rl}0,&|X|=1,2,|E|-2,\\\ 1,&|X|=0,|E|-1,\\\
-1,&\phantom{|}X\phantom{|}=E.\end{array}\right.$

If $|E|=3$, then no such function satisfies these conditions. If $|E|=4$,
these conditions define a unique (up to isomorphism) binary function, which we
will call $f_{\mathcal{U}_{2,4}}$. It is straightforward to confirm that all
proper minors of $f_{\mathcal{U}_{2,4}}$ are straight. Hence
$f_{\mathcal{U}_{2,4}}$ is an excluded minor for the class of straight binary
functions.

Finally, let us suppose that $|E|\geq 5$. Take distinct $a,b,c,d\in E$. We
have

$\displaystyle f\backslash
d(\\{c\\})=\frac{f(\\{c\\})+f(\\{c,d\\})}{1+f(\\{d\\})}=\frac{0+0}{1+0}=0,$
(4.15) $\displaystyle f\backslash
d(E\backslash\\{a,d\\})=\frac{f(E\backslash\\{a,d\\})+f(E\backslash\\{a\\})}{1+f(\\{d\\})}=\frac{0+1}{1+0}=1.$
(4.16)

Likewise, $f\backslash d(E\backslash\\{b,d\\})=1$ by (4.16). As $f\backslash
d$ is straight and $f\backslash
d((E\backslash\\{a,d\\})=f(E\backslash\\{b,d\\}))=1$, then $f\backslash
d(\\{a,b\\})=1$, and so

$f\backslash
d(\\{a,b\\})=\frac{f(\\{a,b\\})+f(\\{a,b,d\\})}{1+f(\\{d\\})}=f(\\{a,b,d\\})=1.$
(4.17)

We have $f\backslash c(\\{a,b\\})=1$ by (4.17) and $f\backslash c(\\{d\\})=0$
by (4.15), so $f\backslash c(\\{a,b,d\\})=0$ as $f\backslash{c}$ is straight.
But,

$f\backslash
c(\\{a,b,d\\})=\frac{f(\\{a,b,d\\}+f(\\{a,b,c,d\\})}{f(\emptyset)+f(\\{c\\})}=\frac{1+f(\\{a,b,c,d\\})}{1+0},$

and so $f(\\{a,b,c,d\\})=-1$. But as $|E|\geq 5$, we have
$f(\\{a,b,c,d\\})\in\\{0,1\\}$. Therefore, no other excluded minors exist.
$\hfill\Box$

##  5 Matroids and polymatroids

For $k\in\mathbb{N}$, a binary function $f\colon 2^{E}\to\mathbb{R}$ is _$k$
-polymatroidal_ if $f$ is rankable and $Qf\colon 2^{E}\to\mathbb{R}$ satisfies
the following:

  * R0)

$\forall X\subseteq E,~{}Qf(X)\in\mathbb{N}\cup\\{0\\},$

  * R1)

$\forall X\subseteq E,~{}Qf(X)\leq k|X|,$

  * R2)

$\forall X\subseteq E,\forall e\in E\backslash X,~{}Qf(X)\leq
Qf(X\cup\\{e\\}),$

  * R3)

$\forall X\subseteq E,~{}\forall a,b\in E\backslash X\text{ and }a\neq
b,~{}Qf(X)+Qf(X\cup\\{a,b\\})\leq Qf(X\cup\\{a\\})+Qf(X\cup\\{b\\}).$

A function satisfying R0–R3 is the rank function of a $k$-polymatroid [10], so
$k$-polymatroidal binary functions are those with $k$-polymatroid rank
functions. Let $\mathcal{M}_{k}$ denote the class of $k$-polymatroidal binary
functions.

Note that the deletion and contraction operations for polymatroid rank
functions are the same as matroid deletion and contraction, and it is well
known (cf. [2]) that $k$-polymatroid rank functions are minor-closed. Combined
with Proposition 3.7, this gives the following.

######  Remark 5.1.

For each $k\in\mathbb{N}$, $\mathcal{M}_{k}$ is closed under taking minors.

We can now determine the excluded minors of $\mathcal{M}_{k}$.

######  Theorem 5.2.

A binary function is $k$-polymatroidal if and only if it has no minor
isomorphic to any of:

  * •

$f_{\alpha}$, where $\alpha\in\mathbb{R}\backslash\\{0,1,3,\ldots,2^{k}-1\\}$,
and

  * •

$f_{\alpha,\beta,\gamma}\colon 2^{\\{a,b\\}}\to\mathbb{R}$, where
$0\leq\alpha\leq\beta\leq\gamma\leq k-1$ are integers and

$\left.\begin{array}[]{lcl}f_{\alpha,\beta,\gamma}(\emptyset)&=&1,\\\
f_{\alpha,\beta,\gamma}(\\{a\\})&=&2^{\alpha+\gamma-\beta+1}-1,\\\
f_{\alpha,\beta,\gamma}(\\{b\\})&=&2^{\gamma+1}-1,\\\
f_{\alpha,\beta,\gamma}(\\{a,b\\})&=&2^{\alpha+\gamma+1}-2^{\gamma+1}-2^{\alpha+\gamma-\beta+1}+1.\\\
\end{array}\right.$

Proof.  We first consider $k$-polymatroidal binary functions of order 1. As
the unique binary function of order 0 is $k$-polymatroidal, any order 1 binary
function $f$ is an excluded minor for $\mathcal{M}_{k}$ if and only if
$f\notin\mathcal{M}_{k}$. Again, we write $f_{\alpha}$ as the binary function
of order 1 where $f_{\alpha}(E)=\alpha$, which is unique up to isomorphism.

By Theorem 3.6, $f_{\alpha}$ is not rankable if $\alpha\leq-1$. If
$-1<\alpha<0$, then $Qf_{\alpha}$ does not satisfy R2. If $\alpha$ is not of
the form $2^{n}-1$ for some $n\in\mathbb{N}$, then $Qf_{\alpha}$ does not
satisfy R0. If $\alpha>2^{k}-1$, then $Qf_{\alpha}$ does not satisfy R1. Hence
$f_{\alpha}$ is $k$-polymatroidal only if
$\alpha\in\\{0,1,3,\ldots,2^{k}-1\\}$. Finally, it is straightforward to check
that for each $\alpha\in\\{0,1,3,\ldots,2^{k}-1\\}$, $f_{\alpha}$ is
$k$-polymatroidal.

Hence the excluded minors of $\mathcal{M}_{k}$ of order one are $f_{\alpha}$,
where $\alpha\in\mathbb{R}\backslash\\{0,1,3,\ldots,2^{k}-1\\}$. We now
consider excluded minors $f$ of order at least two.

By Theorem 3.6, every binary function of order at least two which is not
rankable has a proper minor that is not rankable. Hence any excluded minor of
$\mathcal{M}_{k}$ of order at least two is rankable. Let $f$ to be an excluded
minor of $\mathcal{M}_{k}$ of order at least 2. Then $Qf$ does not satisfy one
of R0, R1, R2 or R3.

Suppose $Qf$ does not satisfy R0. Then there is some $X\subseteq E$ such that
$f(X)\notin\mathbb{N}\cup\\{0\\}$.

As $f(\emptyset)=0$, we have that $X$ is nonempty. Take $e\in X$, and as
$f/e\in\mathcal{M}_{k}$, we know
$Q(f/e)(X\backslash\\{e\\})\in\mathbb{N}\cup\\{0\\}$. But
$Q(f/e)(X\backslash\\{e\\})=Qf(X)-Qf(\\{e\\})$, and so
$Qf(\\{e\\})\notin\mathbb{N}\cup\\{0\\}$. But, as $|E|\geq 2$, there is some
$d\in E\backslash\\{e\\}$, and $Q(f\backslash
d)(\\{e\\})=Qf(\\{e\\})\notin\mathbb{N}\cup\\{0\\}$, and so $f\backslash
d\notin\mathcal{M}_{k}$.

Hence $Qf$ must satisfy R0.

Suppose now that $Qf$ satisfies R0, but does not satisfy R1. Then there exists
$X\subseteq E$ such that $Qf(X)>|X|$.

Clearly, $X\neq\emptyset$, so let $e\in X$. Consider
$f\backslash(E\backslash\\{e\\})\in\mathcal{M}_{k}$, which is a proper minor
of $f$, and so $Qf(\\{e\\})=Q(f\backslash(E\backslash\\{e\\}))(\\{e\\})\leq
k$.

But then
$Q(f/e)(X\backslash\\{e\\})=Qf(X)-Qf(\\{e\\})>k|X|-k=k|X\backslash\\{e\\}|$,
and so $f/e\notin\mathcal{M}_{k}$.

Hence $Qf$ must satisfy R1.

Suppose now that $Qf$ satisfies R0 and R1, but does not satisfy R2. That is,
there exists $X\subset E$ and $e\in E\backslash X$ such that
$Qf(X)>Qf(X\cup\\{e\\})$. Then we have
$Q(f/X)(\\{e\\})=Qf(X\cup\\{e\\})-Qf(X)<0$, and so $f/X\notin\mathcal{M}_{k}$.
But since $Qf$ satisfies R0 and R1, $X\neq\emptyset$. Hence $f/X$ is a proper
minor of $f$, so $f$ is not an excluded minor of $\mathcal{M}_{k}$.

Hence $Qf$ must satisfy R2.

Finally, suppose now that $Qf$ satisfies R0, R1 and R2, but does not satisfy
R3. Therefore there exist distinct $a,b\in E$ and $X\subseteq
E\backslash\\{a,b\\}$ such that

$Qf(X)+Qf(X\cup\\{a,b\\})>Qf(X\cup\\{a\\})+Qf(X\cup\\{b\\}).$ (5.1)

Suppose there is some $c\in X$. Then, as $f/c\in\mathcal{M}_{k}$ and satisfies
R3,

$Q(f/c)(X\backslash\\{c\\})+Q(f/c)(X\backslash\\{c\\}\cup\\{a,b\\})\leq
Q(f/c)((X\backslash\\{c\\})\cup\\{a\\})+Q(f/c)((X\backslash\\{c\\})\cup\\{b\\}).$

This can be written as

$Qf(X)+Qf(X\cup\\{a,b\\})-2Qf(\\{c\\})\leq
Qf(X\cup\\{a\\})+Qf(X\cup\\{b\\})-2Qf(\\{c\\}),$

which is equivalent to

$Qf(X)+Qf(X\cup\\{a,b\\})\leq Qf(X\cup\\{a\\})+Qf(X\cup\\{b\\}).$

This contradicts (5.1), and so we must have $X=\emptyset$, and (5.1) becomes

$Qf(\emptyset)+Qf(\\{a,b\\})>Qf(\\{a\\})+Qf(\\{b\\}).$ (5.2)

Suppose $c\in E\backslash{\\{a,b\\}}$. Then, as $f\backslash
c\in\mathcal{M}_{k}$ and satisfies R3,

$Q(f\backslash c)(\emptyset)+Q(f\backslash c)(\\{a,b\\})\leq Q(f\backslash
c)(\\{a\\})+Q(f\backslash c)(\\{b\\}),$

which is equivalent to

$Qf(\emptyset)+Qf(\\{a,b\\})\leq Qf(\\{a\\})+Qf(\\{b\\}).$

This contradicts (5.2), and so $E\backslash\\{a,b\\}$ is empty. Therefore, $f$
must have order 2, i.e. $E=\\{a,b\\}$, and

$Qf(\\{a,b\\})>Qf(\\{a\\})+Qf(\\{b\\}).$ (5.3)

We now know that our excluded minor $f$ must have order 2 and its rank
function must satisfy R0, R1, R2 and (5.3). As $Qf$ satisfies (5.3), we know
$f\notin\mathcal{M}_{k}$, so it remains to show that all proper minors of $f$
are $k$-polymatroidal.

We know that $Q(f\backslash a)(\\{b\\})=Qf(\\{b\\})$ is a nonnegative integer
at most $k$ as $Qf$ satisfies R0, R1 and R2. As $Q(f\backslash a)$ has order
one, it trivially satisfies R3. Hence, $f\backslash a\in\mathcal{M}_{k}$, and
similarly $f\backslash b\in\mathcal{M}_{k}$.

We know that $Q(f/a)(\\{b\\})=Qf(\\{a,b\\})-Qf(\\{a\\})$ is a nonnegative
integer as $Qf$ satisfies R0, R1 and R2. Hence, $Q(f/a)$ satisfies R0 and R2.
As $Q(f\backslash a)$ has order one, it trivially satisfies R3. We must then
add the restriction that $Qf(\\{a,b\\})-Qf(\\{a\\})\leq k$ in order that
$Q(f/a)$ satisfies R1 and so $f/a\in\mathcal{M}_{k}$. Similarly, we have
$Qf(\\{a,b\\})-Qf(\\{b\\})\leq k$ as $f/b\in\mathcal{M}_{k}$.

Without loss of generality, let $Qf(\\{a\\}\leq Qf(\\{b\\})$. The necessary
and sufficient conditions for $f$ are

$f\colon 2^{\\{a,b\\}}\to\mathbb{R},\text{ where
}\left\\{\begin{array}[]{l}Qf(\\{a\\}),Qf(\\{b\\}),Qf(\\{a,b\\})\in\mathbb{N}\cup\\{0\\},\\\
Qf(\\{a\\})\leq Qf(\\{b\\})\leq k,\\\
Qf(\\{a\\})+Qf(\\{b\\})<Qf(\\{a,b\\})\leq k+Qf(\\{a\\}).\end{array}\right.$

Setting $Qf(\\{a\\})=\alpha,Qf(\\{b\\})=\beta,$ and
$Qf(\\{a,b\\})=\alpha+\gamma+1$, these conditions are equivalent to
$\alpha,\beta,\gamma\in\mathbb{N}\cup\\{0\\}$ and
$0\leq\alpha\leq\beta\leq\gamma\leq k-1$. So the excluded minors of
$\mathcal{M}_{k}$ of order two are of the form

$\left.\begin{array}[]{lcl}f_{\alpha,\beta,\gamma}(\emptyset)&=&1,\\\
f_{\alpha,\beta,\gamma}(\\{a\\})&=&2^{\alpha+\gamma-\beta+1}-1,\\\
f_{\alpha,\beta,\gamma}(\\{b\\})&=&2^{\gamma+1}-1,\\\
f_{\alpha,\beta,\gamma}(\\{a,b\\})&=&2^{\alpha+\gamma+1}-2^{\gamma+1}-2^{\alpha+\gamma-\beta+1}+1.\\\
\end{array}\right.$

$\hfill\Box$

It is perhaps surprising that the excluded minors of $k$-polymatroidal binary
functions have such a relatively simple structure. While there are an infinite
number of excluded minors of order one, there are only finitely many excluded
minors of $\mathcal{M}_{k}$ of order two, and the number is polynomial in $k$.

Polymatroids and $k$-polymatroid rank functions are a generalisation of the
matroid rank functions, which are the $1$-polymatroids. The above theorem can
be applied to give the following excluded minor characterisation of binary
functions with corresponding matroid rank functions.

######  Corollary 5.3.

A binary function is 1-polymatroidal (_matroidal_) if and only if it has no
minor isomorphic to any of:

  * •

$f_{\alpha}$, where $\alpha\in\mathbb{R}\backslash\\{0,1\\}$, and

  * •

$f\colon 2^{\\{a,b\\}}\to\mathbb{R}$, where

$f(X)=\left\\{\begin{array}[]{rl}1,&|X|=0,1,\\\ -1,&|X|=2.\end{array}\right.$

Theorem 4.2 gave an excluded minor characterisation of the straight binary
functions. As each straight binary function is matroidal, combining this
theorem with Corollary 5.3 give the excluded minor characterisation of
straight binary functions within the class of matroidal binary functions.

######  Theorem 5.4.

A matroidal binary function is straight if and only if it has no minor
isomorphic to $f_{\mathcal{U}_{2,4}}\colon 2^{\\{a,b,c,d\\}}\to\mathbb{R}$,
where

$f_{\mathcal{U}_{2,4}}(X)=\left\\{\begin{array}[]{rl}0,&|X|=1,2,\\\
1,&|X|=0,3,\\\ -1,&|X|=4.\end{array}\right.$

Proof. Follows from Theorem 4.2 and Corollary 5.3. $\hfill\Box$

The rank functions of the straight binary functions are the binary matroid
rank functions, so this result is equivalent to an excluded minor
characterisation of binary matroids within the class of matroids. Here,
$Qf_{\mathcal{U}_{2,4}}$ is the rank function of the uniform matroid
${\mathcal{U}_{2,4}}$, and so Theorem 5.4 is equivalent to a classical result
in structural matroid theory[14].

######  Theorem 5.5 (Tutte, 1958).

A matroid is binary if and only if it has no minor isomorphic to
${\mathcal{U}_{2,4}}$.

##  6 Further work

This paper lays the groundwork for using binary functions as a tool to
investigate minor-closed classes of a number of types of structures.

Binary functions can be used to find new or shorter proofs for excluded minor
characterisations of classes of graphs, matroids and other types of objects.
In this paper we found a new proof of the characterisation of binary matroids
among matroids. One candidate for further investigation are the binary
polymatroids, which generalise the binary matroids. It is known that the set
of excluded minors of the binary polymatroids among polymatroids is infinite
[8, 11], but they have not been fully described. If the binary functions that
represent binary polymatroids have a simple characterisation, then these could
be used to investigate the class of binary polymatroids.

Binary functions admit an infinite number of minor operations [4, 5], and one
could investigate classes of binary functions closed under minor operations
other than deletion and contraction.

## References

  * [1] R. Bixby, On Reid’s characterization of the ternary matroids, J. Combin. Theory Ser. B, 26 (1979) 174–204
  * [2] J. Bonin and C. Chun, Decomposable polymatroids and connections with graph coloring, European J. Combin. 89 (2020) 103179
  * [3] G. E. Farr, A generalization of the Whitney rank generating function, Math. Proc. Cambridge Philos. Soc. 113 (1993) 267–280.
  * [4] G. E. Farr, Some results on generalised Whitney functions, Adv. in Appl. Math. 32 (2004) 239–262.
  * [5] G. E. Farr, On the Ashkin–Teller Model and Tutte–Whitney Functions, Combin. Probab. Comput. 16 (2007) 251–260
  * [6] J. Geelen, A. H. Gerards and A. Kapoor, The excluded minors for GF(4)-representable matroids, J. Combin. Theory Ser. B 79 (2000) 247–299
  * [7] J. Geelen, A. H. Gerards and G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014) 736–743
  * [8] T. Huynh, Answer to a question “Representability of polymatroids over $GF(2)$”, http://mathoverflow.net/questions/37548/representability-of-polymatroids-over-gf2 (2010)
  * [9] T. Lazarson, The representation problem for independence functions, J. London Math. Soc. 1 (1958) 21–25
  * [10] J. Oxley and G. Whittle, A characterization of Tutte invariants of 2-polymatroids, J. Combin. Theory Ser. B 59 (1993) 210–244
  * [11] J. Oxley, C. Semple, G. Whittle, A wheels-and-whirls theorem for 3-connected 2-polymatroids, SIAM J. Discrete Math. 30 (2016) 493–524
  * [12] N. Robertson and P. Seymour, Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004) 325–357
  * [13] P. Seymour, Matroid representation over GF(3), J. Combin. Theory Ser. B 26 (1979) 159–173
  * [14] W. T. Tutte, A homotopy theorem for matroids I, II, Trans. Amer. Math. Soc. 88 (1958) 144–174
  * [15] W. T. Tutte, Matroids and graphs, Trans. Amer. Math. Soc. 90 (1959) 527–552
  * [16] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570–590