{'fraction_non_alphanumeric': 0.07644201578627809, 'fraction_numerical': 0.01636308439587128, 'mean_word_length': 3.1027525221073606, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 52, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Yes, the"missing axiom"of matroid theory is lost forever

We prove there is no sentence in the monadic second-order language MS0 that characterises when a matroid is representable over at least one field, and no sentence that characterises when a matroid is K-representable, for any infinite field K. By way of contrast, because Rota's Conjecture is true, there is a sentence that characterises F-representable matroids, for any finite field F.


Introduction
A matroid captures the notion of a discrete collection of points in space. Sometimes these points can be assigned coordinates in a consistent way, and sometimes they cannot. The problem of characterising when a matroid is representable has been the prime motivating force in matroid research since Whitney's founding paper [9].
Plenty of effort has been invested in characterising matroid representability via excluded minors. Less attention has been paid to the prospect of characterisating representability via axioms. Perhaps this is because of Vámos's well-known article [8], which has been interpreted as stating that no such characterisation is possible (see [2]). In [5], we pointed out that the possibility of characterising representable matroids in the language of Whitney's axioms was still open; that, in other words, it was still not proved that "the missing axiom of matroid theory is lost forever", contra Vámos's title. We conjectured that in fact there was no such characterisation, and we made some partial progress towards resolving the conjecture by showing that it was impossible to characterise the class of representable matroids, or the class of matroids representable over an infinite field, using a logical language based on the rank function. However, that language imposed quite strong constraints on the form of quantification. In this article, we present a language with no such constraints, and we prove that it is impossible to characterise representability, or representability over an infinite field, in this more natural language.
The language that we develop is a form of monadic second-order logic, MS 0 . As we show in Section 2, MS 0 is expressive enough to state the matroid axioms, and to state when a matroid contains an isomorphic copy of a fixed minor. This means that any minor-closed class of matroids can be characterised with a sentence in MS 0 , as long as it has a finite number of excluded minors. In particular, since Rota's Conjecture has been positively resolved by Geelen, Gerards, and Whittle (see [3]), it follows that the class of F-representable matroids can be characterised by a sentence in MS 0 , whenever F is a finite field. Our main results show that this is not the case for the class of matroids that are representable over at least one field, nor for the class of K-representable matroids, when K is any infinite field.
We say that a matroid is representable if it is representable over at least one field. Theorem 1. 1. There is no sentence, ψ, in MS 0 , such that a matroid is representable if and only if it satisfies ψ. Theorem 1. 2. Let K be any infinite field. There is no sentence, ψ K , in MS 0 , such that a matroid is K-representable if and only if it satisfies ψ K .
These theorems may seem stronger than those in [5], but in fact the results are independent of each other. The logical language used in [5] had constraints on quantification, unlike MS 0 , but it also had access to the rank function, and to the arithmetic of the integers, while MS 0 does not. Theorems 1.1 and 1.2 follow easily from the next two lemmas. Let k be a positive integer. Define g 1 (k, 0) to be 3 k 2 k(k+1) , and recursively define g 1 (k, i + 1) to be 2 g 1 (k,i) . Let f 1 (k) be g 1 (k, k). Thus f 1 (k) is where the tower of exponents has height k + 1. Recall that if M and M are matroids with disjoint ground sets, then M ⊕ M is the direct sum of M and M . Lemma 1. 3. Let k be a positive integer. There is a partition of the set of matroids into blocks, P 1 , . . . , P N 1 (k) , such that N 1 (k) ≤ f 1 (k) and the following property holds: for any sentence, ψ, in MS 0 with k variables, whenever M and M are matroids that belong to the same block, then, for any matroid, M , either M ⊕ M and M ⊕ M both satisfy ψ, or neither satisfies ψ.
Proof of Theorem 1. 1. Assume that there is a sentence, ψ, in MS 0 , that characterises representable matroids. Let k be the number of variables in ψ, and let P 1 , . . . , P N 1 (k) be the partition provided by Lemma 1. 3. Because there are infinitely many prime numbers, we can let p and p be distinct primes such that the projective planes M = PG(2, p) and M = PG(2, p ) belong to the same block. Now, setting M to be M , we see that either PG(2, p) ⊕ PG(2, p) and PG(2, p ) ⊕ PG(2, p) both satisfy ψ, or neither satisfies ψ. In either case we have a contradiction, since the first of these direct sums is a representable matroid, and the second is not.
Let k be a positive integer. We say that matroids M and M are equivalent if, for any sentence ψ with k variables, and any matroid M , either both M ⊕ M and M ⊕ M satisfy ψ, or neither do. Lemma 1.3 shows that this equivalence relation has finite index for any k. In this way, the proof of Theorem 1.1 is reminiscent of the Myhill-Nerode characterisation of regular languages (see [6] or [1, Section 6.1]). By way of contrast, the theorem in [5] used a proof technique that was essentially an Ehrenfeucht-Fraïssé game (see [1,Section 2.2]).
For every k, there is a partition of matroids into finitely many blocks, such that two matroids from the same block satisfy exactly the same k-variable sentences. This follows from Lemma 1.3 by letting M be the empty matroid U 0,0 , or from the fact that there are only finitely many rank-k 0-types (see [4,Section 3.4] for an explanation).
For the next lemma, we construct families of matroids by using gain graphs. Loosely, a gain graph is a graph equipped with edge labels that come from a group. For each such graph, there is a gain-graphic matroid, whose ground set is the edge set of the graph. In Section 5, we introduce two families of gain graphs. A hoop matroid is the gain-graphic matroid that corresponds to a gain graph of the form Γ(K, α, s). Here K is a field, s ≥ 3 is an integer, and α is a non-zero element of K with order greater than s. The edge labels of the gain graph Γ(K, α, s) come from the multiplicative group of K. We also introduce a family of gain graphs, ∆(L, β, t). In this case L is a field, t ≥ 3 is an integer, and β is a non-zero element with order greater than 2t(t − 1). A loop matroid is gain-graphic, corresponding to a gain graph of the form ∆(L, β, t).
If M is a hoop matroid, corresponding to the gain graph Γ(K, α, s), and M is the loop matroid of ∆(L, β, t), then M and M can be glued together along a rank-2 flat, to form an amalgam of the two matroids. The resulting matroid is denoted Amal(M, M ). In the case that K = L and α = β, where the order of α is greater than max{s, 2t(t − 1)}, then both M and M can be represented over K, but Amal(M, M ) can be represented over K if and only if s = t. This means that the following lemma quickly leads to a proof of Theorem 1.2, with hoop matroids playing the same role that projective planes did in the proof of Theorem 1. 1. Details of the proof will be left until the end of the paper. If k is a positive integer, then g 2 (k, 0) is 2 k 2 3 k 17 k , and g 2 (k, i + 1) is 2 g 2 (k,i) . Define f 2 (k) to be g 2 (k, k) Lemma 1. 4. Let k be a positive integer. There is a partition of the set of hoop matroids into blocks, P 1 , . . . , P N 2 (k) , such that N 2 (k) ≤ f 2 (k) and the following property holds: for any sentence, ψ, in MS 0 with k variables, whenever M and M are hoop matroids that belong to the same block and M is a loop matroid, when Amal(M, M ) and Amal(M , M ) are defined, either both satisfy ψ, or neither satisfies ψ. Lemma 1.4 also implies the following (unsurprising) fact: using MS 0 to characterise increasingly large finite fields requires increasingly large sentences.
Corollary 1. 5. There is no integer, N , such that, for every finite field, F, there is a sentence, ψ F , in MS 0 containing at most N variables, with the property that a matroid is F-representable if and only if it satisfies ψ F .
In fact Lemma 1.4 is sufficient to prove both Theorem 1.1 and Theorem 1.2, since, if Amal(M, M ) is not representable over the field K, then it is not representable over any field (Lemma 5.3). However, we feel that Lemma 1.3 is more intuitive, and also interesting in its own right, so we prefer to prove that lemma, and then note the easy changes required to produce a proof of Lemma 1.4. For all matroid essentials we refer to Oxley [7].

Monadic second-order logic
We construct the logical language MS 0 for making statements about matroids. It includes an unlimited supply of variables, X 1 , X 2 , X 3 , . . . along with the binary predicate, ⊆, the unary predicates, Sing and Ind, as well as the standard connectives ∧ and ¬, and the quantifiers ∃ and ∀. The variables will be interpreted as representing subsets of a ground set. Thus X i ⊆ X j is interpreted as the statement that X i is a subset of X j and Sing(X i ) is interpreted as the statement that X i has cardinality equal to one. Moreover, Ind(X i ) is interpreted as the statement that X i is independent in a given matroid.
We recursively define formulas in MS 0 , and simultaneously define their sets of variables. The following statements define expressions known as atomic formulas.
(1) X i ⊆ X j is an atomic formula, for any variables X i and X j , and Sing(X i ) is an atomic formula, for any variable X i , and Var(Sing(X i )) = {X i }. (3) Ind(X i ) is an atomic formula, for any variable X i , and Var(Ind(X i )) = {X i }. A formula is an expression generated by a finite application of the following rules. Every formula has an associated set of variables and free variables: (1) Every atomic formula, ψ, is a formula, and Fr(ψ) = Var(ψ).
(4) If ψ is a formula and X i ∈ Fr(ψ), then ∃X i ψ and ∀X i ψ are formulas, and Var(∃X i ψ) = Var(∀X i ψ) = Var(ψ), while Fr( A variable in Var(ψ) is free if it is in Fr(ψ), and bound otherwise. A formula is quantifier-free if all of its variables are free, and is a sentence if all its variables are bound. Rule (3) insists that no variable can be free in one of ψ 1 and ψ 2 and bound in the other, if ψ 1 ∧ ψ 2 is to be a formula. We can overcome this constraint if necessary by relabelling the bound variables in a formula.
Next we spend some time illustrating the expressive power of MS 0 . It is powerful enough to state the axioms for matroids, and to characterise when a matroid contains a fixed minor.
If t ≥ 2 is an integer, we use Union t (X i 1 , . . . , X it , X i t+1 ) as shorthand for the statement Thus Union t (X i 1 , . . . , X it , X i t+1 ) is interpreted as being true if and only if X i t+1 is equal to X i 1 ∪ · · · ∪ X it . (The variable X stands for some variable not equal to any of X i 1 , . . . , X i t+1 .) Now we let the predicate Max(X i ) stand for Thus Max(X i ) is interpreted as the statement that X i is maximal with respect to satisfying the predicate Ind.
The family of sets on which the predicate Ind returns 'true' is the collection of independent sets of a matroid if and only the following sentences are satisfied: Next we let N be a fixed matroid on the ground set {1, . . . , n}, with I as its collection of independent sets. Let D be the set of dependent subsets of N . A matroid has a minor isomorphic to N if and only if it contains distinct elements x 1 , . . . , x n , and an independent set, X n+1 , such that {x 1 , . . . , x n } ∩ X n+1 = ∅, and {x i 1 , . . . , x it } ∪ X n+1 is independent precisely when {i 1 , . . . , i t } is an independent set of N . In this case, N is isomorphic to the minor produced by contracting X n+1 and restricting to the set {x 1 , . . . , x n }. Thus we see that a matroid has a minor isomorphic to N if and only if it satisfies the following sentence:

Proof of Lemma 1.3
Throughout this section we let k be a fixed positive integer. Recall that A registry is a (k + 2) × k matrix with rows indexed by Ind, Sing, and X 1 , . . . , X k , and columns indexed by X 1 , . . . , X k . An entry in row Ind or in row X i must be 'T' or 'F'. An entry in row indexed by Sing is either '<', '=', or '>'. It follows that there are at most g 1 (k, 0) = 3 k 2 k(k+1) possible registries.
An l-stacked matroid is a tuple, (M, Y 1 , . . . , Y l ), where M is a matroid, 0 ≤ l ≤ k, and each Y i is a subset of the ground set of M . Note that each matroid, M , is also a 0-stacked matroid, (M ). We define a depth-0 tree to be a registry. Recursively, a depth-(i + 1) tree is a non-empty set of depth-i trees. If T is a depth-(i + 1) tree, then the depth-i trees it contains are its children. Note that we can use an easy inductive argument to show there are no more than g 1 (k, i + 1) depth-(i + 1) trees, and hence no more than f 1 (k) depth-k trees.
To each l-stacked matroid, M = (M, Y 1 , . . . , Y l ), we associate a depth-(k− l) tree, T (M). Thus each matroid is associated with a depth-k tree. A kstacked matroid, (M, Y 1 , . . . , Y k ) corresponds to a depth-0 tree, which is a registry. Informally, we think of this registry as containing information about the truth values of the statements Sing Formally, we first define T (M) in the case that l = k. Then T (M) is a depth-0 tree (a registry). The entry of T (M) in row Ind and column X i is 'T' if and only if Y i is independent in M . The entry in row X i and column X j is 'T' if and only if Y i ⊆ Y j . Finally, the entry in row Sing and column X i is '<', '=', or '>', according to whether |Y i | is less than, equal to, or greater than one. When l < k, we recursively define T (M) to be the set In other words, we let Y l+1 range over all subsets of the ground set E(M ), while keeping Y 1 , . . . , Y l fixed. This produces a collection of (l + 1)-stacked matroids, each of which is thus associated with a depth-(k − l − 1) tree. We define the set of these trees to be the depth-(k − l) tree associated with M. Now let B be the set of (k + 2) × k matrices with rows indexed by Ind, Sing, and X 1 , . . . , X k , and columns indexed by X 1 , . . . , X k , where each entry is either 'T' or 'F'. Thus a matrix in B records the truth values of the predicates Ind(X i ), Sing(X i ), and X i ⊆ X j for a particular set-system. If ψ is a quantifier-free formula in MS 0 , then ψ is logically equivalent to a boolean expression in the predicates Sing(X i ), Ind(X i ), and X i ⊆ X j . Hence we can consider any such quantifier-free formula to be a function from B to {T, F}.
Next we define an operation that takes pairs of registries into B. The sum of two registries is produced by simply summing the two matrices, entry by entry, under the following summation rules: Let ψ be a formula in MS 0 using k variables. By relabelling, we can assume that Var(ψ) = {X 1 , . . . , X k }. Let l be the number of free variables in ψ. By relabelling we can assume that Fr(ψ) = {X 1 , . . . , X l }. We can also assume that ψ is in prenex normal form. That is, We now define what it means for a pair of depth-(k − l)-trees, T and T , to be compatible (relative to ψ).
In the case that l = k, then ψ is quantifier-free, and T and T are a pair of registries. We say that this pair is compatible if and only if their sum is taken to 'T' by the quantifier-free formula ψ. (Remembering that ψ is a function from B to {T, F}.) Now assume that l < k. Thus T and T are non-empty sets of depth-(k − l − 1) trees. First consider the case that Q l+1 = ∃. Then T and T are compatible if and only if T contains a depth-(k − l − 1) tree, T 0 , and T contains a depth-(k − l − 1) tree, T 0 , such that T 0 and T 0 are compatible relative to the formula Similarly, if Q l+1 = ∀, we say that T and T are compatible if and only if T 0 and T 0 are compatible relative to Proof. Note that T (M) and T (M ) are depth-(k − l) trees. First assume that l = k, so that ψ is a quantifier-free formula. Then T (M) and T (M ) are depth-0 trees, that is, registries. Let ω be the matrix in B that is produced by summing T (M) and T (M ). As we have noted, the entry of ω in row Similarly, the entry of ω in row Ind and column This establishes the base case of the proof.
Next we assume that l < k. Consider the case that Q l+1 = ∃. Then T (M) and T (M ) are compatible relative to ψ if and only if there are depth-(k − l − 1) trees T 0 ∈ T (M) and T 0 ∈ T (M ) such that T 0 and T 0 are compatible relative to In other words, if and only if ∃X l+1 Q l+2 X l+2 · · · Q k X k ψ is true. Since this formula is equal to ψ, this completes the proof when Q l+1 = ∃.
Assume that Q l+1 = ∀. Then T (M) and T (M ) are compatible relative to ψ if and only if, for all depth-(k−l−1) trees T 0 ∈ T (M) and T 0 ∈ T (M ), T 0 and T 0 are compatible relative to Q l+2 X l+2 · · · Q k X k ψ . By induction, this is true if and only if, for every choice of subset Y l+1 ⊆ E(M ), and for every choice of Y l+1 ⊆ E(M ), the (l + 1)-stacked matroid, In other words, if and only if ∀X l+1 Q l+2 X l+2 · · · Q k X k ψ is true. This completes the proof. Now let ψ be a sentence in MS 0 using k variables. By relabelling and using standard techniques, we assume that ψ = Q 1 X 1 · · · Q k X k ψ . Let

Amalgams
Let M 1 and M 2 be simple matroids with ground sets E 1 and E 2 , rank functions r 1 and r 2 , and closure operators cl 1 and cl 2 for every pair of flats, F and F , in M 1 | ), then [7, Theorem 11. 4.10] implies that is the rank function of an amalgam of M 1 and M 2 , known as the proper amalgam. We denote this amalgam by Amal(M 1 , M 2 ). Henceforth, we consider only the case that r 1 ( ) = 2. Since every rank-2 uniform matroid is modular, this means that M 1 | is modular, so that Amal(M 1 , M 2 ) is defined.
Proposition 4. 1. Assume that M i is a simple matroid with ground set E i , rank function r i , and closure operator cl i , for i = 1, 2.
so by (1), the rank of X in Amal(M 1 , M 2 ) is less than |X|, as desired. By symmetric arguments, we see that if (i) or (ii) holds, then X is dependent in Amal(M 1 , M 2 ). Next we assume that (iii) holds. Since X ∩ E 1 contains no circuits of M 1 it follows that y is not in X. If X ∩ contains distinct elements, u and v, then by performing circuit exchange on {y, u, v} and a circuit contained in (X − E 2 ) ∪ y that contains y, we obtain a circuit of M 1 contained in X ∩ E 1 . This contradiction means that |X ∩ | ∈ {0, 1}. Let Y be X ∪ y. Then Again we see that X is dependent in Amal(M 1 , M 2 ), and this completes the proof of the 'if' direction.
For the 'only if' direction, we assume that X is dependent in Amal(M 1 , M 2 ). As X ∩ E 1 is independent in M 1 and X ∩ E 2 is independent in M 2 , it follows that X is contained in neither E 1 nor E 2 . There is some set Assume that amongst all such sets, Y has been chosen so that it is as small as possible. If y is an element in Y − (X ∪ E 2 ), then we could replace Y with Y − y. Therefore no such element exists. By symmetry it follows that This contradiction means that there is an element, y, in Y − X. The minimality of Y means that It follows that y is in cl 1 ((Y − y) ∩ E 1 ) and cl 2 ((Y − y) ∩ E 2 ), but not cl 1 ((Y − y) ∩ ). We combine the observations in this paragraph to deduce that |X ∩ | < |Y ∩ | < 3.
Assume that |X ∩ | = 1, so that |Y ∩ | = 2 and Y = X ∪ y. Let x be the element in X ∩ . Since cl 1 (X ∩ E 1 ) = cl 1 ((Y − y) ∩ E 1 ) contains x and y, it contains . As y is in cl 2 Now we assume that |X ∩ | = 0. If Y ∩ = {y}, then Y = X ∪ y, and y is in so statement (iii) holds. Therefore we assume that Y ∩ = {y, y }, and hence Y = X ∪ {y, y }. Earlier statements imply that y ∈ cl 1 ((X ∩ E 1 ) ∪ y ) ∩ cl 2 ((X ∩ E 2 ) ∪ y ) and If X ∩ E 1 is a flat of M 1 , and X ∩ E 2 is a flat of M 2 , then r 1 (Y ∩ E 1 ) = r 1 ((X ∩ E 1 ) ∪ y) = r 1 (X ∩ E 1 ) + 1. Similarly, r 2 (Y ∩ E 2 ) = r 2 (X ∩ E 2 ) + 1. But this means that which is a contradiction. Now, by using symmetry, we can assume that y is in cl 1 (X ∩ E 1 ). This means that y , and hence , is contained in cl 1 (X ∩ E 1 ). Also, so statement (i) holds, and the proof is complete.

Gain-graphic matroids
Next we introduce two families of matroids via gain graphs. If G is an undirected graph (possibly containing loops and multiple edges) with edge set E and vertex set V , then A(G) is the following subset of E × V × V : {(e, u, v) : e is a non-loop edge joining u and v} ∪ {(e, u, u) : e is a loop incident with u}.
A gain graph (over the group H) is a pair (G, σ), where G is a graph, and σ is a function from A(G) to H, such that σ(e, u, v) = σ(e, v, u) −1 for every non-loop edge e with end-vertices u and v. We say that σ is a gain function.
Note that, in general, H may be nonabelian, and the value of σ(C) depends on the choice of starting point and orientation for C; however, if σ(C) is equal to the identity of H, then this equality will hold no matter which starting point and orientation we choose. In this case, we say that C is balanced. A cycle that is not balanced is unbalanced.
The gain-graphic matroid M (G, σ) has the edge set of G as its ground set. The circuits of M (G, σ) are exactly the edge sets of balanced cycles, along with the minimal edge sets that induce connected subgraphs containing at least two unbalanced cycles and no balanced cycles. Any such subgraph is either a theta graph, or a handcuff. The former consists of two vertices joined by three internally-disjoint paths; the latter is two edge-disjoint cycles joined by a single path, which intersects the cycles only in its end-vertices. Note that this path may have length zero, in which case the two cycles share a single vertex.
Assume that (G, σ) is a gain graph, where σ takes A(G) to the multiplicative group of a field, K. Let v 1 , . . . , v m and e 1 , . . . , e n be orderings of the vertex and edge sets of G. We define a matrix, D(G, σ), with entries from K. The rows of D(G, σ) are labelled by v 1 , . . . , v m and the columns are labelled by e 1 , . . . , e n . If e i is a balanced loop, then column e i contains all zeroes. If e i is an unbalanced loop, let v j be the vertex incident with e i ; then column e i contains a 1 in row v j , and zeroes in every other row. Now assume that e i joins v j and v k , where j < k. Column e i contains a 1 in row v j , and the entry in row v k is −σ(e i , v j , v k ). All other entries in the column are zero. Next we construct two families of gain graphs. Let s ≥ 3 be an integer, and let K be a field containing a non-zero element, α, with order greater than s. The gain graph Γ(K, s, α) has vertex set {u 1 , . . . , u s+1 }. Each vertex u i in {u 2 , . . . , u s } is incident with a loop, a i . In addition, u 1 is incident with the loop a, and u s+1 is incident with the loop b. The parallel edges x i and y i join u i and u i+1 for each i in {1, . . . , s}. Moreover, the edges x, y, and z join u 1 and u s+1 . The gain function, σ, will be into the multiplicative group of K. We define σ so that it takes each loop to α and each x i to 1. Furthermore, σ(y i , u i , u i+1 ) = α for each i in {1, . . . , s}, while σ(x, u 1 , u s+1 ) = 1, σ(y, u 1 , u s+1 ) = α s−1 , and σ(z, u 1 , u s+1 ) = α s . A gain-graphic matroid of the form M (Γ(K, s, α)) is said to be a hoop matroid. Now let t ≥ 3 be an integer. We let L be a field, and we let β be an element in L − {0} with order greater than 2t(t − 1). We construct the gain graph ∆(L, t, β). It has {v 1 , . .
and β t(t−1) , respectively. A gain-graphic matroid of the form M (∆(L, t, β)) is a loop matroid. Figure 1 shows Γ(K, s, α) and ∆(L, t, β). The edge labels of loops have been omitted. Every edge label corresponds to the orientation of the edge shown in the drawing. If G is a graph and X is a set of edges, then G[X] denotes the subgraph of G containing the edges in X and all vertices that are incident with at least one edge in X.
Lemma 5.2. Let K be a field, let s ≥ 3 be an integer, and let α be an element in K − {0} with order greater than 2s(s − 1). Let M be M (Γ(K, s, α)) and let M be M (∆(K, s, α)). Then Amal(M, M ) is K-representable.
Proof. Let be {a, b, x, y, z}. Let (G, σ) be the signed graph Γ (K, s, α), and let (G , σ ) be ∆ (K, s, α). The lemma will follow from Proposition 5.1 if we can prove that Amal(M, M ) is gain-graphic and corresponds to a gain graph over the multiplicative group of K. To this end, we construct a gain graph by gluing together G and G . We identify the vertices u 1 and v 1 , as well as u s+1 and v 2s . Let H be the resulting graph. Note that σ ∪ σ is a gain function for H. Let For the first direction, we assume that X is a circuit in N . As N is an amalgam of M and M , we assume that X is contained in neither E(M ) nor E(M ). We start by considering the case that X is a balanced cycle in (H, σ∪σ ). If X contains an edge joining u 1 and u s+1 , then this edge is g, and H[X] contains a path with vertex sequence u 1 , u 2 , . . . , u s+1 , for otherwise X is contained in E(M ) or E(M ). The product of edge labels along this path is α j , where j ≤ s. We also require that α j = α s(s−1) , since g is labelled with α s(s−1) , and X is a balanced cycle. But α j = α s(s−1) cannot hold, as α has order greater than 2s(s − 1), and s ≥ 3 so s(s − 1) > s. Therefore we conclude that X does not contain any edge between u 1 and u s+1 . Let α j be the product of edge labels along the path in H[X] with vertex sequence u 1 , u 2 , . . . , u s+1 . Thus 0 ≤ j ≤ s. Let α p(s−1)+qs be the product of edge labels along the path in H[X] with vertex sequence v 1 , v 2 , . . . , v 2s , where p and q are non-negative integers. Thus 0 ≤ p(s − 1) + qs ≤ 2s(s − 1) and α j = α p(s−1)+qs , as X is balanced. As the order of α is greater than 2s(s−1), we deduce that j = p(s − 1) + qs, and hence j is equal to 0, s − 1, or s. In these three cases, x, y, or z is an element in cl M (X − E(M )) ∩ cl M (X − E(M )). Thus statement (iii) of Proposition 4.1 holds, so X is dependent in Amal(M, M ). Now we can assume that X does not contain a balanced cycle of (H, σ∪σ ). Thus H[X] is a theta graph or a handcuff. Let We can now assume that neither has no vertices of degree one, the forest must be a path, and its endvertices must be u 1 = v 1 and u s+1 = v 2s , contradicting our assumption. By symmetry, it follows that each of H[X − E(M )] and H[X − E(M )] contains an unbalanced cycle. Since H[X] is connected, either u 1 or u s+1 is on a path from one of these cycles to the other. Let us assume the former, since the latter case is identical. Now a is in a handcuff, and hence in a circuit of M that is contained in (X − E(M )) ∪ a, and also in a circuit of M that is contained in (X − E(M )) ∪ a. Thus statement (iii) of Proposition 4.1 holds, and X is dependent in Amal(M, M ). We have proved that if X is dependent in N , it is dependent in Amal(M, M ).
For the other direction, we assume that X is independent in N . This means that H[X] contains no balanced cycles, and any connected component of H[X] contains at most one cycle. Let us assume for a contradiction that X is dependent in Amal(M, M ). In fact, we can assume that X is a circuit of Amal(M, M ). As N is an amalgam, it follows that neither One of the three statements in Proposition 4.1 must hold.
We prove the following statements for M and M simultaneously, by letting {M 1 , M 2 } be {M, M }. Recall that X ∩ = ∅ and neither a nor b is in cl M 2 (X − E(M 1 )). As one of the statements from Proposition 4.1 must hold, either there is an edge between u 1 and u s+1 that is in both cl M 2 (X −E(M 1 )) and cl M 1 (X −E(M 2 )), or cl M 1 (X − E(M 2 )) contains . Therefore in either case we can let w be an edge between u 1 and u s+1 that is in cl M 1 (X − E(M 2 )). Let C be a circuit of . We can assume that the columns of D labelled by the elements of B form a identity matrix. As the fundamental circuits relative to B all have cardinality three, every column of D contains either one or two non-zero elements. By scaling, we can assume that the first non-zero entry in each column is 1. Thus D = D(G, σ), for some gain graph (G, σ) over the field L. By examining the fundamental circuits relative to B, we see that G is the graph in Figure 2. By scaling rows of D, we can assume that σ(x i , u i , u i+1 ) = 1 for each i = 1, . . . , s and σ(e i , v i , v i+1 ) = 1 for each i = 1, . . . , 2t − 1. For i ∈ {1, . . . , s}, let α i be σ(y i , u i , u i+1 ) and for i ∈ {1, . . . , 2t−1}, let β i be σ(f i , v i , v i+1 ). Let γ, δ, , and ζ be σ(x, u 1 , u s+1 ), σ(y, u 1 , u s+1 ), σ(z, u 1 , u s+1 ), and σ(g, u 1 , u s+1 ). Because {x 1 , . . . , x s , x} is a balanced cycle in Γ(K, s, α), and hence a circuit in Amal(M, M ), it follows that it is also a balanced cycle in (G, σ). This means that γ = 1. Next we notice that ({y 1 , . . . , y s } − y i ) ∪ {x i , y} is a balanced cycle of Γ(K, s, α) and hence of (G, σ), for any i in {1, . . . , s}. The product of edge labels on this cycle is α 1 · · · α s α −1 i δ −1 , which implies that α i = α 1 · · · α s δ −1 for any i ∈ {1, . . . , s}. This in turn implies that α i = α j for any i, j ∈ {1, . . . , s} and that δ = α s−1 1 . As {y 1 , . . . , y s , z} is a balanced cycle, it follows that = α s 1 .  . . , e t , f t+1 , . . . , f 2t−1 , g} are both balanced cycles, it now follows that the products β 1 · · · β t = (α s−1 1 ) t and β t+1 · · · β 2t−1 = (α s 1 ) t−1 are both equal to ζ. Thus α st−t Let o be the order of α 1 in L. Since s = t, we know that  6. Proof of Lemma 1.4 This section is dedicated to proving Lemma 1. 4. The main ideas required here are essentially identical to those in Section 3, so we omit many details.
We again let k be a fixed positive integer; a registry is again a (k + 2) × k matrix with rows indexed by Ind, Sing, and X 1 , . . . , X k , and columns indexed by X 1 , . . . , X k . As before, an entry in row X i is either 'T' or 'F', and an entry in row Sing is either '<', '=', or '>'. However, in this case, an entry in row Ind is either 'F', or an ordered pair from the set {T, F} × { , a, b, x, y, z, ∅, skew}.
It follows that there are at most 2 k 2 3 k 17 k = g 2 (k, 0) possible registries.
A depth-0 tree is a registry, and a depth-(i + 1) tree is a non-empty set of depth-i trees, so there are no more than f 2 (k) depth-k trees. Assume that M is either a hoop matroid, M (Γ(K, s, α)), or a loop matroid, M (∆(L, t, β)), for some choices of fields, K and L, integers s, t ≥ 3, and elements α ∈ K−{0} and β ∈ L − {0} with orders greater than s and t(t − 1) respectively. In the case that M satisfies these conditions, we define an l-stacked matroid to be a tuple, (M, Y 1 , . . . , Y l ), where 0 ≤ l ≤ k and each Y i is a subset of the ground set of M .
If M = (M, Y 1 , . . . , Y k ) is a k-stacked matroid, then T (M) is a registry. The entry in row X i and column X j of this registry is 'T' if and only if Y i ⊆ Y j . The entry in row Sing and column X i is '<', '=', or '>', according to whether |Y i | is less than, equal to, or greater than one. The entries in row Ind are more complicated. Let be {a, b, x, y, z}. Consider the entry in row Ind and column X i . If Y i is dependent in M , then the entry is 'F'. Assume that Y i is independent. Then the entry is an ordered pair from The set of matrices, B, is exactly as described in Section 3, so that a quantifier-free formula in k variables is a function from B to {T, F}. We produce the sum of two registries as before, by summing entry by entry. The rule for summing in a row labelled by Sing or by X i is the same as before, but we need to define the rule for summing entries in the Ind row.
We will describe ω, the sum of ω 1 and ω 2 . If either ω 1 or ω 2 is 'F', then ω is 'F'. Assume that ω 1 and ω 2 are both ordered pairs from {T, F} × { , a, b, x, y, z, ∅, skew}. If the first component of ω 1 (respectively, ω 2 ) is 'T', then ω is 'F' if and only if the second entry in ω 2 (respectively, ω 1 ) is not equal to 'skew'. Now assume that the first components of ω 1 and ω 2 are both equal to 'F'. Then ω is 'F' if and only if ω 1 and ω 2 have identical second components, and this component is a, b, x, y, or z.
The summing operation we have just described has been designed to align with the conditions in Proposition 4.1. Proof. This is immediate from the definition of T (M) and T (M ), the definition of the summing operation, and Proposition 4.1.
Now we assume ψ = Q l+1 X l+1 Q l+2 X l+2 · · · Q k X k ψ is a formula in prenex form with k variables, l of which are free. Thus ψ is a quantifier-free formula. The definition of two depth-(k − l) trees being compatible relative to ψ is identical to that in Section 3, except that we use the new summing operation for registries when we define the compatability of depth-0 trees. 7. Acknowledgements