# Representability of the Direct Sum of $q$-Matroids

Heide Gluesing-Luerssen and Benjamin Jany11footnotemark: 1 Department of
Mathematics, University of Kentucky, Lexington KY 40506-0027, USA;
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>HGL was partially supported by the
grant #422479 from the Simons Foundation.

(February 22, 2023)

###### Abstract

While there are many parallels between matroid theory and $q$-matroid theory,
most notably on the level of cryptomorphisms, there are substantial
differences when it comes to the direct sum. The direct sum of $q$-matroids
has been introduced in the literature only recently. In this short note we
show that the direct sum of representable $q$-matroids may not be
representable. It remains an open question whether representability of the
direct sum can be characterized by the given $q$-matroids.

Keywords: $q$-matroid, direct sum, representability.

##  1 Introduction

A $q$-matroid is the $q$-analogue of a matroid. The ground space is a finite-
dimensional vector space over some finite field and the rank function is
defined on the subspace lattice of that ground space. It satisfies the natural
analogues of the rank function of a matroid. $q$-Matroids have garnered a lot
of attention in the coding-theory community due to their close relation to
rank-metric codes; we refer to [14, 16, 12, 6, 2, 9, 13] for further details.

The notion of a $q$-matroid has only been introduced in 2018 in [14], and its
theory is still in the beginnings. Fortunately, a long catalogue of
cryptomorphisms has already been established in [3]. It tells us that
$q$-matroids can be defined by any of its abundance of structures, such as
independent spaces, bases, circuits, flats, etc, and provides us with
$q$-analogues of the axioms that need to be satisfied. More recently, an
additional cryptomorphism, based on cyclic flats, has been derived in [1].

Despite this extensive list of cryptomorphisms, it turns out that the notion
of direct sum for $q$-matroids is far from obvious. None of the many ways of
defining the direct sum of classical matroids has a well-defined $q$-analogue
(see 2.5 for further details). Furthermore, in [7] it has been shown that
there is no coproduct in the category of $q$-matroids with strong maps as
morphisms. This stands in contrast to the matroid case and suggests that a
direct sum of $q$-matroids will not behave well with respect to its flats.
Nonetheless, just recently a notion of direct sum of $q$-matroids has been
introduced in [4] by way of the rank function. In the same paper some
essential properties of the direct sum have been established, and in [7] it
has been shown that it is a coproduct in the category of $q$-matroids with
linear weak maps as morphisms. The latter implies that the direct sum of
$q$-matroids on ground spaces $E_{1}$ and $E_{2}$ is the unique $q$-matroid
with the most independent spaces among all $q$-matroids on $E_{1}\oplus E_{2}$
whose restrictions to $E_{i}$ are isomorphic to the given $q$-matroids. All
these results suggest that the proposed notion of direct sum is the
appropriate one, and it remains to investigate its properties.

In this short note we will discuss representability of the direct sum. For a
$q$-matroid whose ground space is an ${\mathbb{F}}_{q}$-vector space,
representability can be naturally defined over any field extension of
${\mathbb{F}}_{q}$; see 2.3 below. In contrast to the representation of
classical matroids, this fixes a priori the characteristic of the
‘representing field’, and the only free parameter is the degree of the field
extension. So far, very little is known about representability of $q$-matroids
(such as any obstruction criteria).

In this short paper we show the somewhat surprising fact that the direct sum
of two ${\mathbb{F}}_{q^{m}}$-representable $q$-matroids may not be
${\mathbb{F}}_{q^{m}}$-representable or, even worse, not be representable over
any field extension of ${\mathbb{F}}_{q}$. In order to present examples we
will derive the following results. Firstly, if the direct sum is representable
then it is so by a block diagonal matrix whose blocks represent the summands
(3.4). Secondly, we introduce the notion of paving $q$-matroids as the natural
$q$-analogue of paving matroids. For representable paving $q$-matroids of the
same rank we derive a condition on the representing matrices that prevents the
block diagonal matrix to represent the direct sum (3.6). This will allow us to
construct the desired examples. It remains an open question whether
representability of the direct sum can in general be characterized in terms of
the summands.

Notation: Throughout, let ${\mathbb{F}}={\mathbb{F}}_{q}$. For any finite-
dimensional ${\mathbb{F}}$-vector space $E$ we denote by ${\mathcal{L}}(E)$
the subspace lattice of $E$. For a matrix $M\in{\mathbb{F}}_{q^{a}}^{k\times
n}$ we use $\mbox{\rm rs}(M)\subseteq{\mathbb{F}}_{q^{a}}^{n}$ for the row
space of $M$. The abbreviation RREF stands for reduced row echelon form. We
set ${\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times
n}:=\bigcup_{y=1}^{n}{\mathbb{F}}^{y\times n}$, that is,
${\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times n}$ is the
set of all matrices over ${\mathbb{F}}$ with $n$ columns and at most $n$ rows.
The collection of all their row spaces is ${\mathcal{L}}({\mathbb{F}}^{n})$.

##  2 The Direct Sum of $q$-Matroids

######  Definition 2.1.

A _$q$ -matroid with ground space $E$_ is a pair ${\mathcal{M}}=(E,\rho)$,
where $E$ is a finite-dimensional ${\mathbb{F}}$-vector space and
$\rho:{\mathcal{L}}(E)\longrightarrow{\mathbb{N}}_{\geq 0}$ is a map
satisfying

  * (R1)

Dimension-Boundedness: $0\leq\rho(V)\leq\dim V$ for all
$V\in{\mathcal{L}}(E)$;

  * (R2)

Monotonicity: $V\leq W\Longrightarrow\rho(V)\leq\rho(W)$ for all
$V,W\in{\mathcal{L}}(E)$;

  * (R3)

Submodularity: $\rho(V+W)+\rho(V\cap W)\leq\rho(V)+\rho(W)$ for all
$V,W\in{\mathcal{L}}(E)$.

The value $\rho(V)$ is called the _rank of_ $V$ and
$\rho({\mathcal{M}}):=\rho(E)$ the _rank_ of the $q$-matroid. A subspace
$V\in{\mathcal{L}}(E)$ is _independent_ if $\rho(V)=\dim V$ and _dependent_
otherwise. The dependent spaces all of whose proper subspaces are independent
are called _circuits_. A space $V\in{\mathcal{L}}(E)$ is a _flat_ if it is
inclusion-maximal in the set $\\{W\in{\mathcal{L}}(E)\mid\rho(W)=\rho(V)\\}$,
and a space is _open_ if it is the sum of circuits.

######  Remark 2.2.

It is well known (see [14, Thm. 8]) that the collection of independent spaces
uniquely determines the $q$-matroid, and the same is true for the collections
of dependent spaces, open spaces, and circuits. For this and many more
cryptomorphisms for $q$-matroids we refer to [3]. Furthermore, together with
their rank values the cyclic flats also uniquely determine the $q$-matroid;
see [1, 10] and specifically [1] for the resulting cryptomorphism.

An abundance of $q$-matroids is obtained as follows. Recall that $\mbox{\rm
rs}(\cdot)$ denotes the row space of a matrix.

######  Theorem 2.3 ([14, Sec. 5]).

Let ${\mathbb{F}}_{q^{m}}$ be a field extension of
${\mathbb{F}}={\mathbb{F}}_{q}$ and let $G\in{\mathbb{F}}_{q^{m}}^{k\times
n}$. Define the map
$\rho:{\mathcal{L}}({\mathbb{F}}^{n})\longrightarrow{\mathbb{N}}_{0}$ via

$\rho(V)={\rm rk}\,(GY\mbox{${}^{\sf T}$}),\ \text{ where
$Y\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times n}$ is
such that $V=\mbox{\rm rs}(Y)$}$

(and where the rank is taken over ${\mathbb{F}}_{q^{m}}$). Then $\rho$ is
well-defined and ${\mathcal{M}}_{G}:=({\mathbb{F}}^{n},\rho)$ is a
$q$-matroid. It is called the $q$-matroid _represented by $G$_. A $q$-matroid
${\mathcal{M}}$ with ground space ${\mathbb{F}}^{n}$ is called
_${\mathbb{F}}_{q^{m}}$ -representable_ if ${\mathcal{M}}={\mathcal{M}}_{G}$
for some matrix
$G\in{\mathbb{F}}_{q^{m}}^{\>\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times
n}$ (whose rank equals the rank of ${\mathcal{M}}$). The $q$-matroid
${\mathcal{M}}$ is called _representable_ if it is
${\mathbb{F}}_{q^{m}}$-representable over some field extension
${\mathbb{F}}_{q^{m}}$.

In short, for a representable $q$-matroid
${\mathcal{M}}_{G}=({\mathbb{F}}^{n},\rho)$ with
$G\in{\mathbb{F}}_{q^{m}}^{\>\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times
n}$ we have

$\rho(\mbox{\rm rs}(Y))={\rm rk}\,(GY\mbox{${}^{\sf T}$})\ \text{ for all
matrices $Y\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times
n}$}.$ (2.1)

Clearly, ${\mathcal{M}}_{G}$ depends only on the row space of $G$; in other
word, ${\mathcal{M}}_{G}={\mathcal{M}}_{UG}$ for all $U\in{\rm
GL}_{k}({\mathbb{F}}_{q^{m}})$. In the context of the rank-metric on
${\mathbb{F}}_{q^{m}}^{n}$ the row space of $G$ is known as the _rank-metric
code generated by $G$_. Many invariants of the code (but not all) can be
determined by the associated $q$-matroid. For further details we refer to [14,
12, 2, 9] and Section 6 in the survey [11]. We will briefly touch on the
relation to rank-metric codes in 3.5 and 3.6. Furthermore, representability of
the uniform $q$-matroids can easily be described with the aid of maximum rank-
distance codes (MRD codes).

######  Example 2.4.

Let ${\mathcal{U}}_{k,n}(q)$ be the _uniform $q$-matroid of rank $k$_ with
ground space ${\mathbb{F}}_{q}^{n}$; that is, the rank function is given by
$\rho(V)=\min\\{k,\dim V\\}$ for all
$V\in{\mathcal{L}}({\mathbb{F}}_{q}^{n})$. Then ${\mathcal{U}}_{0,n}(q)$ and
${\mathcal{U}}_{n,n}(q)$ are representable over ${\mathbb{F}}_{q}$. Precisely,
${\mathcal{U}}_{0,n}(q)$ is represented by the $1\times n$-zero matrix and
${\mathcal{U}}_{n,n}(q)$ by the $n\times n$-identity matrix. We call
${\mathcal{U}}_{0,n}(q)$ and ${\mathcal{U}}_{n,n}(q)$ the _trivial_ and the
_free_ $q$-matroid over ${\mathbb{F}}_{q}^{n}$, respectively. For $0<k<n$, the
uniform $q$-matroid ${\mathcal{U}}_{k,n}(q)$ is representable over
${\mathbb{F}}_{q^{m}}$ if and only if $m\geq n$. Indeed, a matrix
$G\in{\mathbb{F}}_{q^{m}}^{k\times n}$ represents ${\mathcal{U}}_{k,n}(q)$ iff
${\rm rk}\,(GY\mbox{${}^{\sf T}$})=k$ for all $Y\in{\mathbb{F}}_{q}^{k\times
n}$ of rank $k$. But this is equivalent to $G$ generating an MRD code [5, Thm.
2 and 3] and such a matrix $G$ exists if and only if $m\geq n$; see [11, Rem.
3.10].

Unsurprisingly, not every $q$-matroid is representable; see [9, Sec. 4] and
[4, Sec. 3.3]. In the next section we will present examples showing that the
direct sum of representable $q$-matroids need not be representable.

Before turning to the direct sum of $q$-matroids, we briefly summarize some
properties of the direct sum of (classical) matroids. We refer to Section 4.2
in the monograph [15] by Oxley for further details.

######  Remark 2.5.

Let $M_{i}=(S_{i},r_{i}),i=1,2,$ be two matroids on disjoint ground sets
$S_{1}$ and $S_{2}$. Then $M=(S,r)$, where $S=S_{1}\cup S_{2}$ and
$r(A)=r_{1}(A\cap S_{1})+r_{2}(A\cap E_{2})$ for all $A\subseteq S$, is a
matroid and called the direct sum of $M_{1}$ and $M_{2}$, denoted by
$M_{1}\oplus M_{2}$. We denote by ${\mathcal{I}}(M_{1}\oplus M_{2})$ and
${\mathcal{I}}(M_{i})$ the collections of independent sets in $M_{1}\oplus
M_{2}$ and $M_{i}$, respectively, and use similar notation for the collections
of circuits, flats, and open sets (the definitions of these sets are as in 2.1
where we replace the dimension by the cardinality and the vector space sum by
the set-theoretic union). The following holds true.

  * (a)

The independent sets satisfy ${\mathcal{I}}(M_{1}\oplus M_{2})=\\{I_{1}\cup
I_{2}\mid I_{i}\in{\mathcal{I}}(M_{i})\\}$.

  * (b)

The circuits satisfy ${\mathcal{C}}(M_{1}\oplus
M_{2})={\mathcal{C}}(M_{1})\cup{\mathcal{C}}(M_{2})$.

  * (c)

The flats satisfy ${\mathcal{F}}(M_{1}\oplus M_{2})=\\{F_{1}\cup F_{2}\mid
F_{i}\in{\mathcal{F}}(M_{i})\\}$.

  * (d)

The open sets satisfy ${\mathcal{O}}(M_{1}\oplus M_{2})=\\{O_{1}\cup O_{2}\mid
O_{i}\in{\mathcal{O}}(M_{i})\\}$.

  * (e)

If $M_{i}$ is represented by the matrices $G_{i}$ (over the same field
${\mathbb{F}}$) for $i=1,2$, then $M_{1}\oplus M_{2}$ is represented by the
matrix

$\begin{pmatrix}G_{1}&0\\\ 0&G_{2}\end{pmatrix}.$ (2.2)

The above implies that the direct sum of matroids can also be defined by way
of independent sets, circuits, flats, or open sets (and many more). It is easy
to see that the obvious $q$-analogue of the rank function above or of any of
the properties (a) – (d) does not lead to a well-defined notion for a direct
sum of $q$-matroids. In addition, (e) does not generalize. In fact, if $G_{i}$
represents the $q$-matroid ${\mathcal{M}}_{i}$, then the $q$-matroid
represented by $G$ in (2.2) (in the sense of 2.3) depends on the choice of the
representing matrices $G_{i}$. This is not surprising as the rank of

$\begin{pmatrix}G_{1}&0\\\
0&G_{2}\end{pmatrix}\begin{pmatrix}Y_{1}\mbox{${}^{\sf T}$}\\\
Y_{2}\mbox{${}^{\sf T}$}\end{pmatrix}=\begin{pmatrix}G_{1}Y_{1}\mbox{${}^{\sf
T}$}\\\ G_{2}Y_{2}\mbox{${}^{\sf T}$}\end{pmatrix}$

depends on the relation between $G_{1}$ and $G_{2}$. This has already been
observed in [4, Rem. 22] and [7, Prop. 4.5]. The latter is used in [7] to
establish the non-existence of a coproduct in the category of $q$-matroids
with strong maps as morphisms.

Fortunately, in [4] the authors introduce a notion of direct sum of
$q$-matroids. We will present a slightly different definition of the same
construction. Its form will be beneficial for further computations.

Throughout the paper we will use the following notation.

######  Notation 2.6.

For any direct sum $E=E_{1}\oplus E_{2}$ of ${\mathbb{F}}$-vector spaces
$E_{1}$ and $E_{2}$ we denote by $\pi_{i}:E\longrightarrow E_{i}$ the
corresponding projections. Furthermore, for $n_{1},n_{2}\in{\mathbb{N}}$ and
$n=n_{1}+n_{2}$, we set
${\mathbb{F}}^{n}={\mathbb{F}}^{n_{1}}\oplus{\mathbb{F}}^{n_{2}}$ such that
$\pi_{1}:{\mathbb{F}}^{n}\longrightarrow{\mathbb{F}}^{n_{1}}$ and
$\pi_{2}:{\mathbb{F}}^{n}\longrightarrow{\mathbb{F}}^{n_{2}}$ are the
projections onto the first $n_{1}$ and last $n_{2}$ coordinates, respectively.
In order to accommodate for the correct matrix sizes, we write
${\mathbb{F}}^{n_{1}}\oplus 0$ and $0\oplus{\mathbb{F}}^{n_{2}}$ for
${\mathbb{F}}^{n_{1}},\,{\mathbb{F}}^{n_{2}}$ considered as subspaces of
${\mathbb{F}}^{n}$.

######  Theorem 2.7 ([4, Sec. 7]).

Let ${\mathcal{M}}_{i}=(E_{i},\rho_{i}),\,i=1,2,$ be $q$-matroids and set
$E=E_{1}\oplus E_{2}$. Define
$\rho^{\prime}_{i}:{\mathcal{L}}(E)\longrightarrow{\mathbb{N}}_{0},\
V\longmapsto\rho_{i}(\pi_{i}(V))$ for $i=1,2$. Then
${\mathcal{M}}^{\prime}_{i}=(E,\rho^{\prime}_{i})$ is a $q$-matroid. Set
${\mathcal{X}}=\\{X\in{\mathcal{L}}(E)\mid\rho_{1}^{\prime}(X)+\rho_{2}^{\prime}(X)<\dim
X\\}$ and ${\mathcal{X}}_{0}={\mathcal{X}}\cup\\{0\\}$. Define

$\rho:{\mathcal{L}}(E)\longrightarrow{\mathbb{N}}_{0},\quad V\longmapsto\dim
V+\min_{X\in{\mathcal{X}}_{0}\cap{\mathcal{L}}(V)}\big{(}\rho^{\prime}_{1}(X)+\rho^{\prime}_{2}(X)-\dim
X\big{)}\ \text{ for }V\in{\mathcal{L}}(E).$ (2.3)

Then ${\mathcal{M}}:=(E,\rho)$ is a $q$-matroid, called the _direct sum of
${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$_ and denoted by
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$. A space $V$ is dependent in
${\mathcal{M}}$ iff ${\mathcal{X}}\cap{\mathcal{L}}(V)\neq\emptyset$, and as a
consequence the collection of circuits of
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is given by
${\mathcal{C}}({\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2})=\\{X\in{\mathcal{X}}\mid
X\text{ is inclusion-minimal in }{\mathcal{X}}\\}$.

A short proof showing that ${\mathcal{M}}_{i}^{\prime}$ is a $q$-matroid is
given at [7, Thm. 5.2] (see also [4, Thm. 41] for the case where $\dim
E_{j}=1$ for $j\neq i$). The fact that $\rho$ is a rank function can be found
in [4, Thm. 29] and also follows from [8, Thm. 3.6 and its proof]. In both
references, $\rho(V)$ is defined as

$\rho(V)=\dim V+\min_{X\leq
V}\big{(}\rho^{\prime}_{1}(X)+\rho^{\prime}_{2}(X)-\dim X\big{)},$ (2.4)

but since $\rho^{\prime}_{1}(0)+\rho^{\prime}_{2}(0)-\dim 0=0$, we can
restrict ourselves to taking the minimum over
${\mathcal{X}}_{0}\cap{\mathcal{L}}(V)$.

The direct sum has some expected properties; see [4, Thm. 47, Cor. 48] or [10,
Thm. 5.6].

######  Theorem 2.8.

Consider the situation from 2.7 and let $V_{i}\in{\mathcal{L}}(E_{i})$. Then
$\rho_{i}(V_{i})=\rho^{\prime}_{i}(V_{i})$ and $\rho^{\prime}_{j}(V_{i})=0$ if
$j\neq i$. Furthermore, $\rho(V_{1}\oplus
V_{2})=\rho_{1}(V_{1})+\rho_{2}(V_{2})$. As a consequence
$\rho({\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2})=\rho_{1}({\mathcal{M}}_{1})+\rho_{2}({\mathcal{M}}_{2})$.

Note that by the above, $E_{i}$ is a loop space of
${\mathcal{M}}^{\prime}_{j}$ for $j\neq i$ (by definition a loop space is a
space with rank $0$). The process from ${\mathcal{M}}_{j}$ to
${\mathcal{M}}^{\prime}_{j}$ in 2.7 is called _adding a loop space_ in [4]. It
is a special instance of the direct sum because
${\mathcal{M}}^{\prime}_{j}={\mathcal{M}}_{j}\oplus{\mathcal{U}}_{0}(E_{i})$
for $i\neq j$, where ${\mathcal{U}}_{0}(E_{i})$ is the trivial $q$-matroid on
the ground space $E_{i}$ (that is, all spaces have rank value $0$). The
process of adding a loop space can easily be described for representable
$q$-matroids.

######  Remark 2.9.

Let $n_{1},n_{2}\in{\mathbb{N}}$. Let
${\mathcal{M}}_{1}=({\mathbb{F}}^{n_{1}},\rho_{1})$ be a representable
$q$-matroid, say ${\mathcal{M}}_{1}={\mathcal{M}}_{G}$ for some
$G\in{\mathbb{F}}_{q^{m}}^{k\times n_{1}}$. Define
${\mathcal{M}}_{1}^{\prime}=({\mathbb{F}}^{n_{1}+n_{2}},\rho_{1}^{\prime})$,
where $\rho_{1}^{\prime}(V)=\rho_{1}(\pi_{1}(V))$ for all
$V\in{\mathcal{L}}({\mathbb{F}}^{n_{1}+n_{2}})$. Then
${\mathcal{M}}_{1}^{\prime}={\mathcal{M}}_{G^{\prime}}$, where
$G^{\prime}=(G\mid 0)\in{\mathbb{F}}^{k\times(n_{1}+n_{2})}$.

As already alluded to, the independent spaces, flats, etc. do not behave well
under taking direct sums of $q$-matroids. Only one structure behaves nicely:
the cyclic flats. We briefly mention the following properties. They will not
be needed for the rest of the paper, but rather serve to illustrate the
contrast to the direct sum of classical matroids; see 2.5(a) –(d). The
discrepancy with respect to representability will be discussed in the next
section.

######  Remark 2.10 (see [10]).

Let ${\mathcal{M}}_{i}=(E_{i},\rho_{i}),\,i=1,2,$ and
${\mathcal{M}}={\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$. As in 2.5 we use the
notation ${\mathcal{I}}({\mathcal{M}})$ for the collection of independent
spaces, and similarly for the flats, circuits, and open spaces. Furthermore,
set
${\mathcal{Z}}({\mathcal{M}})={\mathcal{F}}({\mathcal{M}})\cap{\mathcal{O}}({\mathcal{M}})$.
Its elements are called the _cyclic flats_ of ${\mathcal{M}}$. We set
${\mathcal{I}}({\mathcal{M}}_{1})\oplus{\mathcal{I}}({\mathcal{M}}_{2})=\\{I_{1}\oplus
I_{2}\mid I_{i}\in{\mathcal{I}}({\mathcal{M}}_{i})\\}$ and similarly for the
other collections. Then
${\mathcal{I}}({\mathcal{M}}_{1})\oplus{\mathcal{I}}({\mathcal{M}}_{2})\subset{\mathcal{I}}({\mathcal{M}}),\
\;{\mathcal{F}}({\mathcal{M}}_{1})\oplus{\mathcal{F}}({\mathcal{M}}_{2})\subset{\mathcal{F}}({\mathcal{M}}),\
\;{\mathcal{O}}({\mathcal{M}}_{1})\oplus{\mathcal{O}}({\mathcal{M}}_{2})\subset{\mathcal{O}}({\mathcal{M}})$,
and ${\mathcal{C}}({\mathcal{M}}_{i})\subset{\mathcal{C}}({\mathcal{M}})$ for
$i=1,2$. In general equality does not hold in any of these cases, but, on the
positive side, we have
${\mathcal{Z}}({\mathcal{M}}_{1})\oplus{\mathcal{Z}}({\mathcal{M}}_{2})={\mathcal{Z}}({\mathcal{M}}).$

##  3 Representability of the Direct Sum

In this section we turn to representability of the direct sum of representable
$q$-matroids. We will provide an example of ${\mathbb{F}}_{4}$-representable
$q$-matroids over the ground space ${\mathbb{F}}_{2}^{4}$ for which the direct
sum is not representable over any field extension ${\mathbb{F}}_{2^{m}}$. A
crucial ingredient will be paving $q$-matroids defined below. We show that if
${\mathcal{M}}_{1},\,{\mathcal{M}}_{2}$ are paving $q$-matroids of the same
rank and represented by matrices $G_{i}$ satisfying a certain condition, then
the direct sum ${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is not represented
by the block diagonal matrix $\text{diag}(G_{1},G_{2})$. This will be used to
create the desired example. A second example will be provided where the direct
sum is representable only over larger fields than the summands.

Note that in the context of representability, it suffices to consider
$q$-matroids with ground space ${\mathbb{F}}^{n}$.

######  Definition 3.1.

A $q$-matroid ${\mathcal{M}}=({\mathbb{F}}^{n},\rho)$ is _paving_ if $\dim
C\geq\rho({\mathcal{M}})$ for all circuits $C$ of ${\mathcal{M}}$.

A large class of paving $q$-matroids is given as follows.

######  Example 3.2.

Let $n\in{\mathbb{N}}$ and $1\leq k<n$. Let ${\mathcal{S}}$ be a collection of
$k$-dimensional subspaces of ${\mathbb{F}}^{n}$ with the property that
$\dim(X\cap Y)\leq k-2$ for all distinct $X,Y\in{\mathcal{S}}$. For
$V\in{\mathcal{L}}({\mathbb{F}}^{n})$ define

$\rho(V)=\left\\{\begin{array}[]{cl}k-1&\text{if
}V\in{\mathcal{S}},\\\\[2.15277pt] \min\\{k,\dim
V\\}&\text{otherwise.}\end{array}\right.$

Then ${\mathcal{M}}=({\mathbb{F}}^{n},\rho)$ is $q$-matroid of rank $k$; see
[9, Prop. 4.6]. The circuits are the spaces in ${\mathcal{S}}$ and all
$(k+1)$-dimensional spaces not containing a space in ${\mathcal{S}}$. Thus
${\mathcal{M}}$ is paving. We will make use of this construction later in 3.7.
Further examples can be found in [9, Sec. 4].

For the following result recall 2.6.

######  Proposition 3.3.

Let ${\mathcal{M}}_{i}=({\mathbb{F}}^{n_{i}},\rho_{i}),i=1,2,$ be paving
$q$-matroids with $\rho_{1}({\mathcal{M}}_{1})=\rho_{2}({\mathcal{M}}_{2})=k$.
Let $n=n_{1}+n_{2}$ and
${\mathcal{M}}=({\mathbb{F}}^{n},\rho)={\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$.
Denote by ${\mathcal{C}}_{1},\,{\mathcal{C}}_{2}$ and ${\mathcal{C}}$ the
collections of circuits of ${\mathcal{M}}_{1},\,{\mathcal{M}}_{2}$, and
${\mathcal{M}}$, respectively. Then every $C\in{\mathcal{C}}$ has dimension at
least $k$ and

$\\{C\in{\mathcal{C}}\mid\dim C=k\\}=\\{C_{1}\oplus 0\mid
C_{1}\in{\mathcal{C}}_{1},\,\dim C_{1}=k\\}\cup\\{0\oplus C_{2}\mid
C_{2}\in{\mathcal{C}}_{2},\,\dim C_{2}=k\\}.$

For the proof recall that in any $q$-matroid $(E,\rho)$ a $k$-dimensional
circuit $C$ satisfies $\rho(C)=k-1$.

###### Proof.

We start with the stated identity. Denote the set on the right hand side by
${\mathcal{V}}$.
“$\supseteq$” Let $C_{1}\oplus 0\in{\mathcal{V}}$. From 2.8 we obtain
$\rho(C_{1}\oplus 0)=\rho_{1}(C_{1})=k-1$, and thus $C_{1}\oplus 0$ is
dependent in ${\mathcal{M}}$. Clearly, every subspace of $C_{1}\oplus 0$ is of
the form $I_{1}\oplus 0$ where $I_{1}$ is independent in ${\mathcal{M}}_{1}$.
Using again 2.8 we conclude that $I_{1}\oplus 0$ is independent in
${\mathcal{M}}$ and thus $C_{1}\oplus 0$ is a circuit of ${\mathcal{M}}$ of
dimension $k$. The same reasoning holds for $0\oplus C_{2}\in{\mathcal{V}}$.
“$\subseteq$” By 2.7 a subspace $C\in{\mathcal{L}}({\mathbb{F}}^{n})$ is a
circuit of ${\mathcal{M}}$ if and only if it is inclusion-minimal subject to

$\rho_{1}(\pi_{1}(C))+\rho_{2}(\pi_{2}(C))\leq\dim C-1,$ (3.1)

where $\pi_{1},\,\pi_{2}$ are the projections from ${\mathbb{F}}^{n}$ to the
first $n_{1}$ and last $n_{2}$ coordinates, respectively. Let
$C\in{\mathcal{C}}$ and dim $C\leq k$.
1) Let $\dim\pi_{1}(C)=k$ (which implies $\dim C=k$). Then (3.1) implies that
$\pi_{1}(C)$ is a dependent space of ${\mathcal{M}}_{1}$, and thus a circuit
thanks to the paving property. Hence $\rho_{1}(\pi_{1}(C))=k-1$ and thus
$\rho_{2}(\pi_{2}(C))=0$ by (3.1). But then $\pi_{2}(C)=0$ by the paving
property of ${\mathcal{M}}_{2}$, and thus $C=\pi_{1}(C)\oplus 0$. In the same
way we have $C=0\oplus\pi_{2}(C)$ if $\dim\pi_{2}(C)=k$.
2) Let $\dim\pi_{i}(C)=\ell_{i}<k$ for $i=1,2$. Then $\pi_{i}(C)$ is
independent in ${\mathcal{M}}_{i}$ and $\rho_{i}(\pi_{i}(C))=\ell_{i}$. Now we
obtain $\dim
C\leq\dim\pi_{1}(C)+\dim\pi_{2}(C)=\ell_{1}+\ell_{2}=\rho_{1}(\pi_{1}(C))+\rho_{2}(\pi_{2}(C))$
in contradiction to (3.1). Hence this case does not arise. This also shows
that all circuits have dimension at least $k$, and the proof is complete. ∎

We now turn to representability of the direct sum and start with the following
unsurprising result.

######  Theorem 3.4.

Let ${\mathcal{M}}_{i}=({\mathbb{F}}^{n_{i}},\rho_{i}),i=1,2,$ be $q$-matroids
of rank $k_{i}$. Let $n=n_{1}+n_{2}$ and
${\mathcal{M}}={\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$. Suppose
${\mathcal{M}}$ is representable over ${\mathbb{F}}_{q^{m}}$. Then
${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ are representable over
${\mathbb{F}}_{q^{m}}$ and ${\mathcal{M}}={\mathcal{M}}_{G}$ for a matrix $G$
of the form

$G=\begin{pmatrix}G_{1}&0\\\ 0&G_{2}\end{pmatrix},$

where $G_{i}\in{\mathbb{F}}_{q^{m}}^{k_{i}\times n_{i}}$ are such that
${\mathcal{M}}_{G_{i}}={\mathcal{M}}_{i}$.

###### Proof.

Let ${\mathcal{M}}=({\mathbb{F}}^{n},\rho)$ and suppose
${\mathcal{M}}={\mathcal{M}}_{G}$ for some matrix $G$ over
${\mathbb{F}}_{q^{m}}$. Since $\rho({\mathcal{M}})=k:=k_{1}+k_{2}$ by 2.8, we
may assume that $G$ is in ${\mathbb{F}}_{q^{m}}^{k\times n}$ and has rank $k$.
Furthermore, without loss of generality let $G$ be in RREF. Then we can write
$G$ as

$G=\begin{pmatrix}G_{1}&G^{\prime}&\\\ 0&G_{2}\end{pmatrix}$

for some matrices $G_{1}\in{\mathbb{F}}_{q^{m}}^{t_{1}\times
n_{1}},\,G_{2}\in{\mathbb{F}}_{q^{m}}^{t_{2}\times n_{2}}$ of full row rank
and some matrix $G^{\prime}\in{\mathbb{F}}_{q^{m}}^{t_{1}\times n_{2}}$. Hence
$t_{1}+t_{2}=k_{1}+k_{2}$. We show that
${\mathcal{M}}_{1}={\mathcal{M}}_{G_{1}}$. To do so, let
$Y\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times n_{1}}$
and set $\hat{Y}=(Y\mid 0)$, which is in
${\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times n}$. Then
$V:=\mbox{\rm rs}(Y)$ is in ${\mathcal{L}}({\mathbb{F}}^{n_{1}})$ and $V\oplus
0=\mbox{\rm rs}(\hat{Y})$. With the aid of (2.1) and 2.8 we compute

${\rm rk}\,(G_{1}Y\mbox{${}^{\sf T}$})={\rm rk}\,(G\hat{Y}\mbox{${}^{\sf
T}$})=\rho(\mbox{\rm rs}(\hat{Y}))=\rho(V\oplus 0)=\rho_{1}(V).$

This shows that ${\mathcal{M}}_{1}={\mathcal{M}}_{G_{1}}$. As a consequence,
$t_{1}=k_{1}$ and $t_{2}=k_{2}$. Next,
$k_{2}=\rho_{2}({\mathbb{F}}^{n_{2}})=\rho(0\oplus{\mathbb{F}}^{n_{2}})=\rho(\mbox{\rm
rs}(0\mid I_{n_{2}}))={\rm
rk}\,\mbox{$\left(\begin{smallmatrix}{G^{\prime}}\\\\[1.72218pt]
{G_{2}}\end{smallmatrix}\right)$}$. Since ${\rm rk}\,G_{2}=k_{2}$ this implies
$\mbox{\rm rs}(G^{\prime})\subseteq\mbox{\rm rs}(G_{2})$. Using that $G$ is in
RREF, we conclude $G^{\prime}=0$ and hence $G$ is block diagonal. In the same
way as above we obtain ${\mathcal{M}}_{2}={\mathcal{M}}_{G_{2}}$. This
concludes the proof. ∎

We will now make use of some notions that are standard in the theory of rank-
metric codes. The proof of 3.6 below illustrates the well known fact that for
a representable $q$-matroid ${\mathcal{M}}_{G}$ the dimension of a dependent
space equals the rank-weight of a suitable codeword in the dual code
$\mbox{\rm rs}(G)^{\perp}=\ker G$ (where the dual is defined with respect to
the standard inner product).

######  Definition 3.5.

For a vector $v=(v_{1},\ldots,v_{n})\in{\mathbb{F}}_{q^{m}}^{n}$ we define the
${\mathbb{F}}$-_support_ of $v$ as the subspace

$\mbox{\rm
supp}(v)=\mbox{$\langle{v_{1},\ldots,v_{n}}\rangle$}_{{\mathbb{F}}}\leq{\mathbb{F}}_{q^{m}}.$

The _rank-weight_ of $v$ is $\mbox{$\mbox{\rm wt}_{\mbox{\rm\footnotesize
rk}}$}(v):=\dim\mbox{\rm supp}(v)$.

######  Theorem 3.6.

For $i=1,2$ let $G_{i}\in{\mathbb{F}}_{q^{m}}^{k\times n_{i}}$ be of rank $k$
and ${\mathcal{M}}_{i}={\mathcal{M}}_{G_{i}}$ be the associated $q$-matroids.
Suppose ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ are both paving. Suppose
furthermore that there exist vectors $v_{i}\in\ker G_{i}$ such that
$\mbox{$\mbox{\rm wt}_{\mbox{\rm\footnotesize rk}}$}(v_{1})=\mbox{$\mbox{\rm
wt}_{\mbox{\rm\footnotesize rk}}$}(v_{2})=k$ and $\mbox{\rm
supp}(v_{1})=\mbox{\rm supp}(v_{2})$. Then
${\mathcal{M}}={\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is not represented by

$G=\begin{pmatrix}G_{1}&0\\\ 0&G_{2}\end{pmatrix}.$ (3.2)

###### Proof.

Let ${\mathcal{N}}={\mathcal{M}}_{G}$, that is, ${\mathcal{N}}$ is the
$q$-matroid generated by $G$. We will show that ${\mathcal{N}}$ and
${\mathcal{M}}$ do not have the same circuits of dimension at most $k$.
First of all, 3.3 implies that all circuits of ${\mathcal{M}}$ have dimension
at least $k$, and the $k$-dimensional ones are also circuits of
${\mathcal{N}}$ thanks to their form described in that proposition.
We will show the existence of a circuit of ${\mathcal{N}}$ of dimension at
most $k$ that is not a circuit of ${\mathcal{M}}$. To do so, let $\mbox{\rm
supp}(v_{1})=\mbox{$\langle{\alpha_{1},\ldots,\alpha_{k}}\rangle$}$ for some
(${\mathbb{F}}$-linearly independent) $\alpha_{i}\in{\mathbb{F}}_{q^{m}}$. Set
$\alpha=(\alpha_{1},\ldots,\alpha_{k})\in{\mathbb{F}}_{q^{m}}^{k}$. Then there
exist matrices $Y_{i}\in{\mathbb{F}}^{k\times n_{i}}$ of rank $k$ such that
$\alpha Y_{i}=v_{i}$ for $i=1,2$. Hence $0=G_{i}Y_{i}\mbox{${}^{\sf
T}$}\alpha\mbox{${}^{\sf T}$}$, and thus ${\rm rk}\,(G_{i}Y_{i}\mbox{${}^{\sf
T}$})<k$ for $i=1,2$. This shows that $V_{i}:=\mbox{\rm
rs}(Y_{i})\in{\mathcal{L}}({\mathbb{F}}^{n_{i}})$ is a dependent space of
${\mathcal{M}}_{i}$. Since $\dim V_{i}=k$, the paving property implies that
$V_{i}$ is a circuit of ${\mathcal{M}}_{i}$. Now we have

$G\begin{pmatrix}Y_{1}\mbox{${}^{\sf T}$}\\\ Y_{2}\mbox{${}^{\sf
T}$}\end{pmatrix}\alpha\mbox{${}^{\sf T}$}=\begin{pmatrix}0\\\
0\end{pmatrix},$

which means that $G(Y_{1}\mid Y_{2})\mbox{${}^{\sf T}$}$ has rank less than
$k$. Therefore $W:=\mbox{\rm rs}(Y_{1}\mid
Y_{2})\in{\mathcal{L}}({\mathbb{F}}^{n_{1}+n_{2}})$ is a $k$-dimensional
dependent space of ${\mathcal{N}}$. Since $Y_{1}$ and $Y_{2}$ are both
nonzero, $W$ is not a circuit of the direct sum ${\mathcal{M}}$ thanks to 3.3.
Since ${\mathcal{M}}$ does not have any circuits of dimension less than $k$,
we conclude that $W$ contains a circuit of ${\mathcal{N}}$ of dimension at
most $k$ that is not a circuit of ${\mathcal{M}}$. This implies that
${\mathcal{N}}\neq{\mathcal{M}}$, and $G$ does not represent ${\mathcal{M}}$.
∎

Now we are ready to provide an example of a direct sum of representable
$q$-matroids that is not representable over any field extension.

######  Proposition 3.7.

Let ${\mathbb{F}}={\mathbb{F}}_{2}$ and
${\mathbb{F}}_{4}=\\{0,1,\omega,\omega+1\\}$. Consider the matrix

$G_{1}=\begin{pmatrix}1&\omega&0&\omega+1\\\
0&0&1&\omega\end{pmatrix}\in{\mathbb{F}}_{4}^{2\times 4}$

and set
${\mathcal{M}}_{1}:={\mathcal{M}}_{G_{1}}=({\mathbb{F}}^{4},\rho_{1})$. Then
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{1}$ is not representable over any field
extension ${\mathbb{F}}_{2^{m}}$.

###### Proof.

1) We first show that ${\mathcal{M}}_{1}$ is of the form as in 3.2 and thus
paving of rank $2$. Set ${\mathcal{V}}=\\{\mbox{\rm rs}(Y_{1}),\,\mbox{\rm
rs}(Y_{2}),\,\mbox{\rm rs}(Y_{3}),\,\mbox{\rm rs}(Y_{4}),\,\mbox{\rm
rs}(Y_{5})\\}$, where

$Y_{1}\\!=\\!\begin{pmatrix}1\\!&\\!0\\!&\\!0\\!&\\!0\\\
0\\!&\\!1\\!&\\!0\\!&\\!0\end{pmatrix},Y_{2}\\!=\\!\begin{pmatrix}1\\!&\\!0\\!&\\!1\\!&\\!1\\\
0\\!&\\!1\\!&\\!0\\!&\\!1\end{pmatrix},Y_{3}\\!=\\!\begin{pmatrix}1\\!&\\!0\\!&\\!0\\!&\\!1\\\
0\\!&\\!0\\!&\\!1\\!&\\!1\end{pmatrix},Y_{4}\\!=\\!\begin{pmatrix}0\\!&\\!1\\!&\\!1\\!&\\!0\\\
0\\!&\\!0\\!&\\!0\\!&\\!1\end{pmatrix},Y_{5}\\!=\\!\begin{pmatrix}1\\!&\\!1\\!&\\!0\\!&\\!1\\\
0\\!&\\!0\\!&\\!1\\!&\\!0\end{pmatrix}.$ (3.3)

One can verify, by hand or with for instance SageMath, that

$\rho_{1}(V)=\left\\{\begin{array}[]{cl}1,&\text{for }V\in{\mathcal{V}},\\\
\min\\{2,\dim V\\},&\text{otherwise.}\end{array}\right.$ (3.4)

For instance, $\rho_{1}(V)=1$ for all $1$-dimensional subspaces simply
reflects that the columns of $G_{1}$ are linearly independent over
${\mathbb{F}}_{2}$. Furthermore, $G_{1}Y_{2}\mbox{${}^{\sf
T}$}=\mbox{$\left(\begin{smallmatrix}{\omega}&{1}\\\\[1.72218pt]
{\omega+1}&{\omega}\end{smallmatrix}\right)$}$, which has rank $1$. Similarly,
the rank of all subspaces can easily be verified. As a consequence,
${\mathcal{M}}_{1}$ is of the form as in 3.2 and thus paving of rank $2$.
Clearly, the matrix

$\hat{G}_{1}=\begin{pmatrix}1&\omega+1&0&\omega\\\
0&0&1&\omega+1\end{pmatrix},$

obtained from $G$ by replacing the primitive element $\omega$ by its conjugate
$\omega+1$, also represents ${\mathcal{M}}_{1}$.
2) We show that $G_{1}$ and $\hat{G}_{1}$ are the only matrices over any field
extension ${\mathbb{F}}_{2^{m}},\,m\geq 1,$ that represent
${\mathcal{M}}_{1}$. To do so, let $m\geq 1$ and
$H=(h_{1},\,h_{2},\,h_{3},\,h_{4})\in{\mathbb{F}}_{2^{m}}^{2\times 4}$ be such
that ${\mathcal{M}}_{H}={\mathcal{M}}_{1}$. Thus ${\rm rk}\,(HY\mbox{${}^{\sf
T}$})={\rm rk}\,(G_{1}Y\mbox{${}^{\sf T}$})$ for all matrices
$Y\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times 4}$.
Without loss of generality we may assume that $H$ is in RREF. Clearly ${\rm
rk}\,(H)=2$. Moreover, $h_{1},\ldots,h_{4}$ are linearly independent over
${\mathbb{F}}_{2}$ because ${\mathcal{M}}_{1}$ has no loops (a loop is a
1-dimensional space of rank 0). Next, ${\rm rk}\,(HY_{1}\mbox{${}^{\sf
T}$})=1={\rm rk}\,(HY_{4}\mbox{${}^{\sf T}$})$ shows that
$h_{2}\in\mbox{$\langle{h_{1}}\rangle$}_{{\mathbb{F}}_{2^{m}}}$ and
$h_{4}\in\mbox{$\langle{h_{2}+h_{3}}\rangle$}_{{\mathbb{F}}_{2^{m}}}$. Hence
$h_{2}$ and $h_{4}$ are not pivot columns of $H$. All of this implies that $H$
must be of the form

$H=\begin{pmatrix}1&\alpha&0&\alpha\beta\\\ 0&0&1&\beta\end{pmatrix}\text{ for
some }\alpha,\,\beta\in{\mathbb{F}}_{2^{m}}.$

The ${\mathbb{F}}_{2}$-linear independence of the columns of $H$ implies that
$\alpha,\,\beta\not\in{\mathbb{F}}_{2}$. Next,

$1={\rm rk}\,(HY_{3}\mbox{${}^{\sf T}$})={\rm
rk}\,\begin{pmatrix}1+\alpha\beta&\alpha\beta\\\
\beta&1+\beta\end{pmatrix}={\rm rk}\,\begin{pmatrix}1&\alpha\beta\\\
1&1+\beta\end{pmatrix},$

and this results in $\alpha\beta=1+\beta$. Using this, we continue with

$1={\rm rk}\,(HY_{2}\mbox{${}^{\sf T}$})={\rm
rk}\,\begin{pmatrix}1+\alpha\beta&\alpha+\alpha\beta\\\
1+\beta&\beta\end{pmatrix}={\rm rk}\,\begin{pmatrix}\beta&\alpha+1+\beta\\\
1+\beta&\beta\end{pmatrix}={\rm rk}\,\begin{pmatrix}\beta&\alpha+1\\\
1+\beta&1\end{pmatrix}.$

Using the determinant and $\alpha\beta=1+\beta$ we conclude that
$\alpha+\beta=0$, hence $\alpha=\beta$, and with $\alpha\beta=1+\beta$ we
arrive at $\beta^{2}+\beta+1=0$. Thus
$\beta\in{\mathbb{F}}_{4}\setminus{\mathbb{F}}_{2}$ (and $m$ is even), and the
two choices $\beta\in\\{\omega,\omega+1\\}$ lead to
$H\in\\{G_{1},\hat{G}_{1}\\}$.
3) Consider now ${\mathcal{M}}={\mathcal{M}}_{1}\oplus{\mathcal{M}}_{1}$. From
2) and 3.4 we know that if ${\mathcal{M}}$ is
${\mathbb{F}}_{2^{m}}$-representable for some $m\in{\mathbb{N}}$, then $m$ is
even and any representing matrix is of the form

$G=\begin{pmatrix}G^{\prime}_{1}&0\\\ 0&G^{\prime}_{2}\end{pmatrix},\ \text{
where }G^{\prime}_{i}\in\\{G_{1},\,\hat{G}_{1}\\}.$

Since $v=(1,1,\omega,1)\in\ker
G_{1},\,\hat{v}=(1,1,\omega+1,1)\in\ker\hat{G}_{1}$ satisfy $\mbox{\rm
supp}(v)=\mbox{\rm supp}(\hat{v})=\mbox{$\langle{1,\omega}\rangle$}$ we may
apply 3.6 and conclude that ${\mathcal{M}}$ is not representable over any
field extension ${\mathbb{F}}_{2^{m}}$. ∎

In the following case, the direct sum is not representable over the same field
as the summands, but over a field extension. Recall the uniform $q$-matroids
from 2.4.

######  Proposition 3.8.

Let ${\mathcal{M}}_{1}={\mathcal{U}}_{1,2}(q)$. Then ${\mathcal{M}}_{1}$ is
representable over ${\mathbb{F}}_{q^{2}}$, whereas
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{1}$ is representable over
${\mathbb{F}}_{q^{m}}$ iff $m\geq 4$.

###### Proof.

We know already from 2.4 that ${\mathcal{M}}_{1}$ is representable over
${\mathbb{F}}_{q^{2}}$. Even more, for any $m\geq 2$ any matrix $G=\big{(}1\
\alpha\big{)}$ with $\alpha\in{\mathbb{F}}_{q^{m}}\setminus{\mathbb{F}}_{q}$
represents ${\mathcal{M}}_{1}$. Consider now
${\mathcal{M}}={\mathcal{M}}_{1}\oplus{\mathcal{M}}_{1}=({\mathbb{F}}^{4},\rho)$.
With the aid of the very definition of the direct sum one easily verifies that
$\rho(V)=1$ for all $1$-dimensional spaces $V\leq{\mathbb{F}}^{4}$, while for
the $2$-dimensional spaces

$\rho(V)=\left\\{\begin{array}[]{cl}1,&\text{if
}V=\mbox{$\langle{e_{1},e_{2}}\rangle$}\text{ or
}V=\mbox{$\langle{e_{3},e_{4}}\rangle$},\\\
2,&\text{otherwise,}\end{array}\right.$ (3.5)

where $e_{1},\ldots,e_{4}$ are the standard basis vectors of
${\mathbb{F}}^{4}$. Suppose ${\mathcal{M}}$ is representable over
${\mathbb{F}}_{q^{m}}$. 3.4 tells us that ${\mathcal{M}}$ has a representing
matrix of the form

$G=\begin{pmatrix}1&\beta&0&0\\\ 0&0&1&\gamma\end{pmatrix}\ \text{ for some
}\beta,\gamma\in{\mathbb{F}}_{q^{m}}\setminus{\mathbb{F}}.$

1) Let $m=2$. Then ${\mathbb{F}}_{q^{2}}=\mbox{$\langle{1,\beta}\rangle$}$.
Thus $\gamma=a+b\beta$ for some $a,b\in{\mathbb{F}}$. Set

$V=\mbox{\rm rs}(Y),\text{ where }Y=\begin{pmatrix}a&b&0&1\\\
1&0&1&0\end{pmatrix}.$

Then $\dim V=2$ and ${\rm rk}\,(GY\mbox{${}^{\sf T}$})=1$. This contradicts
(3.5), and thus $G$ does not represent ${\mathcal{M}}$.
2) Let $m=3$. Then
${\mathbb{F}}_{q^{3}}=\mbox{$\langle{1,\beta,\beta^{2}}\rangle$}$ and

$\gamma=c_{0}+c_{1}\beta+c_{2}\beta^{2},\quad\beta^{3}=b_{0}+b_{1}\beta+b_{2}\beta^{2}\text{
for some }b_{i},\,c_{i}\in{\mathbb{F}}.$

This implies
$\beta\gamma=c_{2}b_{0}+(c_{0}+c_{2}b_{1})\beta+(c_{1}+c_{2}b_{2})\beta^{2}$.
Now we have the following cases:
i) If $c_{2}=0$, then ${\rm rk}\,(GY\mbox{${}^{\sf T}$})=1$ for

$Y=\begin{pmatrix}c_{0}&c_{1}&0&1\\\ 1&0&1&0\end{pmatrix}.$

ii) If $c_{2}\neq 0=c_{1}+c_{2}b_{2}$, then ${\rm rk}\,(GY\mbox{${}^{\sf
T}$})=1$ for

$Y=\begin{pmatrix}c_{2}b_{0}&c_{0}+c_{2}b_{1}&0&1\\\ 0&1&1&0\end{pmatrix}.$

iii) If $c_{2}\neq 0\neq c_{1}+c_{2}b_{2}$, we have $(c_{1}+c_{2}b_{2})\gamma-
c_{2}\beta\gamma=f_{0}+f_{1}\beta$ for some $f_{i}\in{\mathbb{F}}$ and thus
${\rm rk}\,(GY\mbox{${}^{\sf T}$})=1$ for

$Y=\begin{pmatrix}f_{0}&f_{1}&0&1\\\
c_{1}+c_{2}b_{2}&-c_{2}&1&0\end{pmatrix}.$

In all cases we obtain a contradiction to (3.5) and conclude that
${\mathcal{M}}$ is not representable over ${\mathbb{F}}_{q^{3}}$.
3) Let $m\geq 4$. We show that ${\mathcal{M}}$ is represented by the matrix

$G=\begin{pmatrix}1&z&0&0\\\ 0&0&1&z^{2}\end{pmatrix}\ \text{ for any
$z\in{\mathbb{F}}_{q^{m}}$ of degree at least~{}$4$}.$

Denote by ${\mathcal{D}}({\mathcal{M}})$ and
${\mathcal{D}}({\mathcal{M}}_{G})$ the collections of dependent spaces of
${\mathcal{M}}$ and ${\mathcal{M}}_{G}$, respectively. We will show that

${\mathcal{D}}({\mathcal{M}}_{G})={\mathcal{D}}({\mathcal{M}}).$ (3.6)

To do so, we first determine the set
${\mathcal{X}}=\\{X\in{\mathcal{L}}({\mathbb{F}}^{4})\mid\rho_{1}(\pi_{1}(X))+\rho_{1}(\pi_{2}(X))<\dim
X\\}$ from 2.7. Since ${\mathcal{M}}_{1}$ is the uniform $q$-matroid of rank
$1$, we have
$\rho_{1}(\pi_{1}(X))+\rho_{1}(\pi_{2}(X))=\min\\{1,\dim\pi_{1}(X)\\}+\min\\{1,\dim\pi_{2}(X)\\}\leq
2$ for all $X\in{\mathcal{L}}({\mathbb{F}}^{4})$, which together with (3.5)
implies

${\mathcal{X}}=\\{X\leq{\mathbb{F}}^{4}\mid\dim X\geq
3\\}\cup\\{\mbox{$\langle{e_{1},e_{2}}\rangle$},\mbox{$\langle{e_{3},e_{4}}\rangle$}\\}.$

The form of ${\mathcal{X}}$ shows that every subspace of ${\mathbb{F}}^{4}$
containing a space in ${\mathcal{X}}$ is itself in ${\mathcal{X}}$. Now it
follows from 2.7 that

${\mathcal{X}}={\mathcal{D}}({\mathcal{M}}).$

We now turn to the $q$-matroid
${\mathcal{M}}_{G}=({\mathbb{F}}^{4},\hat{\rho})$. By definition
$\hat{\rho}(\mbox{\rm rs}(Y))={\rm rk}\,(GY\mbox{${}^{\sf T}$})$ for any
matrix $Y\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times
4}$. Set $G^{\prime}_{1}=(1\ \;z)$ and $G^{\prime}_{2}=(1\ \;z^{2})$, thus

$G=\begin{pmatrix}G^{\prime}_{1}&0\\\ 0&G^{\prime}_{2}\end{pmatrix}.$

Since both $G^{\prime}_{1}$ and $G^{\prime}_{2}$ represent the $q$-matroid
${\mathcal{M}}_{1}$, any matrix $Y=(Y_{1}\mid
Y_{2})\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times 4}$
satisfies

${\rm rk}\,(G^{\prime}_{i}Y_{i}\mbox{${}^{\sf T}$})=\rho_{1}(\pi_{i}(\mbox{\rm
rs}(Y))).$

Let now $Y=(Y_{1}\mid
Y_{2})\in{\mathbb{F}}^{\raisebox{-0.51234pt}{$\boldsymbol{\cdot}$}\times 4}$
be such that $\mbox{\rm rs}(Y)\in{\mathcal{D}}({\mathcal{M}})={\mathcal{X}}$.
Then

$\hat{\rho}(\mbox{\rm rs}(Y))={\rm rk}\,(GY\mbox{${}^{\sf T}$})\leq{\rm
rk}\,(G^{\prime}_{1}Y_{1}\mbox{${}^{\sf T}$})+{\rm
rk}\,(G^{\prime}_{2}Y_{2}\mbox{${}^{\sf T}$})=\rho_{1}(\pi_{1}(\mbox{\rm
rs}(Y)))+\rho_{1}(\pi_{2}(\mbox{\rm rs}(Y)))<{\rm rk}\,Y.$

This shows that
${\mathcal{D}}({\mathcal{M}})\subseteq{\mathcal{D}}({\mathcal{M}}_{G})$. This
can also be concluded from the coproduct property of
${\mathcal{M}}\oplus{\mathcal{M}}$; see [7, Thm. 5.5]. It remains to show the
converse containment. Let now $Y\in{\mathbb{F}}^{t\times 4}$ be a matrix of
rank $t$ such that $\mbox{\rm rs}(Y)\in{\mathcal{D}}({\mathcal{M}}_{G})$. Thus

${\rm rk}\,(GY\mbox{${}^{\sf T}$})<t.$ (3.7)

We will show that $\mbox{\rm rs}(Y)$ is in ${\mathcal{X}}$. For $t\geq 3$
every $Y$ satisfies (3.7) and $\mbox{\rm rs}(Y)$ is contained in
${\mathcal{X}}$, while for $t=1$ no matrix $Y$ satisfies (3.7). It remains to
consider the case $t=2$. Let

$Y=\begin{pmatrix}a_{1}&b_{1}&c_{1}&d_{1}\\\
a_{2}&b_{2}&c_{2}&d_{2}\end{pmatrix}$

be of rank $2$ and satisfying (3.7). Without loss of generality let $Y$ be in
RREF. We compute

$GY\mbox{${}^{\sf T}$}=\begin{pmatrix}a_{1}+b_{1}z&a_{2}+b_{2}z\\\
c_{1}+d_{1}z^{2}&c_{2}+d_{2}z^{2}\end{pmatrix}$

and

$\det(GY\mbox{${}^{\sf
T}$})=(a_{1}c_{2}-a_{2}c_{1})+(b_{1}c_{2}-b_{2}c_{1})z+(a_{1}d_{2}-a_{2}d_{1})z^{2}+(b_{1}d_{2}-b_{2}d_{1})z^{3}.$

Recall that $1,z,z^{2},z^{3}$ are linearly independent over ${\mathbb{F}}_{q}$
by choice of $z$. Thanks to the RREF of $Y$ we only have to consider the
following cases.
i) If $a_{1}=b_{1}=a_{2}=b_{2}=0$, then $\mbox{\rm
rs}(Y)=\mbox{$\langle{e_{3},e_{4}}\rangle$}$ is in ${\mathcal{X}}$.
ii) Let $a_{1}=1,a_{2}=0,b_{1}=0,b_{2}=1$. Then $\det(GY\mbox{${}^{\sf
T}$})=c_{2}-c_{1}z+d_{2}z^{2}-d_{1}z^{3}$ and (3.7) implies
$c_{1}=c_{2}=d_{1}=d_{2}=0$. Thus $\mbox{\rm
rs}(Y)=\mbox{$\langle{e_{1},e_{2}}\rangle$}$, which is in ${\mathcal{X}}$.
iii) Let $a_{1}=1$ and $a_{2}=b_{2}=0$. Then $\det(GY\mbox{${}^{\sf
T}$})=c_{2}+b_{1}c_{2}z+d_{2}z^{2}+b_{1}d_{2}z^{3}$ and (3.7) implies
$c_{2}=d_{2}=0$. But this contradicts that $Y$ has rank $2$ and thus this case
does not occur.
iv) Let $a_{1}=a_{2}=0=b_{2}$ and $b_{1}=1$. Then $\det(GY\mbox{${}^{\sf
T}$})=c_{2}z+d_{2}z^{3}$ and (3.7) implies $c_{2}=d_{2}=0$, which contradicts
${\rm rk}\,Y=2$. Hence this case does not occur either.
All of this establishes (3.6). Thanks to 2.2, more specifically [3, Cor. 73],
we arrive at ${\mathcal{M}}={\mathcal{M}}_{G}$, and this shows the
${\mathbb{F}}_{q^{m}}$-representability of ${\mathcal{M}}$. ∎

Thus far we provided two examples. In the first one, the direct sum of
representable $q$-matroids is not representable, and in the second one it
requires a larger field size for a representation than the summands. In fact,
almost all examples that we were able to compute fall into one of the two
categories. The only examples known to us where the direct sum is
representable over the same field as both summands, are such that one summand
is representable over ${\mathbb{F}}_{q}$. While we are not able to prove a
general statement about these specific direct sums, we can discuss two extreme
cases. If ${\mathcal{M}}_{1}$ is the trivial $q$-matroid
${\mathcal{U}}_{0,n_{1}}(q)$ we have seen already in 2.9 and the paragraph
preceding it, that ${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is representable
over the same field as ${\mathcal{M}}_{2}$. The other extreme, where
${\mathcal{M}}_{1}$ is the free $q$-matroid, is dealt with in the following
proposition.

######  Proposition 3.9.

Let ${\mathcal{M}}_{1}={\mathcal{U}}_{n_{1},n_{1}}(q)$, which is representable
by $I_{n_{1}}$, and let the $q$-matroid
${\mathcal{M}}_{2}=({\mathbb{F}}_{q}^{n_{2}},\rho_{2})$ be represented by
$G_{2}\in{\mathbb{F}}_{q^{m}}^{k_{2}\times n_{2}}$. Then
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is representable over
${\mathbb{F}}_{q^{m}}$ and a representing matrix is given by

$G=\begin{pmatrix}I_{n_{1}}&0\\\ 0&G_{2}\end{pmatrix}.$

###### Proof.

Set $n=n_{1}+n_{2}$. We first consider the $q$-matroid ${\mathcal{M}}_{G}$ and
determine its rank function, which we denote by $\rho_{G}$. Let
$V\in{\mathcal{L}}({\mathbb{F}}^{n})$ and $V=\mbox{\rm rs}(Y)$ where
$Y\in{\mathbb{F}}^{\ell\times n}$ of rank $\ell$. Without loss of generality,
we may assume that $Y$ is in reduced row echelon. Then $Y$ partitions as

$Y=\begin{pmatrix}Y_{1}&\hat{Y}\\\ 0&Y_{2}\end{pmatrix},$ (3.8)

for some $Y_{i}\in{\mathbb{F}}^{\ell_{i}\times n_{i}}$ and $\hat{Y}$ of
corresponding size, and where ${\rm rk}\,(Y_{i})=\ell_{i}$ for $i=1,2$. This
means that $\mbox{\rm rs}(Y_{1})=\pi_{1}(V)$, which has dimension $\ell_{1}$,
and $\mbox{\rm rs}(Y_{2})=\pi_{2}(V\cap(0\oplus{\mathbb{F}}^{n_{2}}))$, which
has dimension $\ell_{2}$. Now we have

$GY\mbox{${}^{\sf T}$}=\begin{pmatrix}Y_{1}\mbox{${}^{\sf T}$}&0\\\
G_{2}\hat{Y}\mbox{${}^{\sf T}$}&G_{2}Y_{2}\mbox{${}^{\sf T}$}\end{pmatrix},$

and since $Y_{1}\mbox{${}^{\sf T}$}$ has full column rank, we obtain the rank
value

$\rho_{G}(V)={\rm rk}\,(GY\mbox{${}^{\sf T}$})={\rm rk}\,(V_{1})+{\rm
rk}\,(G_{2}Y_{2}\mbox{${}^{\sf
T}$})=\dim\pi_{1}(V)+\rho_{2}(\pi_{2}(V\cap(0\oplus{\mathbb{F}}^{n_{2}}))).$
(3.9)

We now turn to ${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ and denote its rank
function by $\rho$. We use (2.4) to evaluate $\rho$, thus

$\rho(V)=\dim V+\min_{X\leq V}\sigma(X),\ \text{ where
}\sigma(X)=\dim\pi_{1}(X)+\rho_{2}(\pi_{2}(X))-\dim X.$ (3.10)

Consider again $V=\mbox{\rm rs}(Y)$ with $Y$ as in(3.8). Let $X$ be a subspace
of $V$ of dimension $x$. Then $X$ is of the form $X=\mbox{\rm rs}(SY)$ for
some $S\in{\mathbb{F}}^{x\times\ell}$ of rank $x$. Again, we may assume $S$ in
reduced row echelon form and can partition the matrix as

$S=\begin{pmatrix}S_{1}&\hat{S}\\\ 0&S_{2}\end{pmatrix},$

where $S_{i}\in{\mathbb{F}}^{x_{i}\times\ell_{i}}$ of rank $x_{i}$ and
$\hat{S}$ accordingly. Then

$SY=\begin{pmatrix}S_{1}Y_{1}&S_{1}\hat{Y}+\hat{S}Y_{2}\\\
0&S_{2}Y_{2}\end{pmatrix}.$

The two diagonal blocks have full row rank and $\pi_{1}(X)=\mbox{\rm
rs}(S_{1}Y_{1})$ while $\pi_{2}(X)=\mbox{\rm
rs}\mbox{$\left(\begin{smallmatrix}{S_{1}\hat{Y}+\hat{S}Y_{2}}\\\\[1.72218pt]
{S_{2}Y_{2}}\end{smallmatrix}\right)$}$. Now we have

$\sigma(X)={\rm rk}\,(S_{1}Y_{1})+\rho_{2}(\pi_{2}(X))-\dim
X=\rho_{2}(\pi_{2}(X))-{\rm rk}\,(S_{2}Y_{2}),$

which we want to minimize over all subspaces $X$ of $V$. Note that this
expression does not depend on $\pi_{1}(X)$. Furthermore, since ${\rm
rk}\,(S_{2}Y_{2})$ does not depend on $\hat{S}$ and $\rho_{2}$ is non-
decreasing, the minimum is attained by a space $X$ of the form $X=\mbox{\rm
rs}(0\mid S_{2}Y_{2})$. Thus we arrive at

$\sigma(X)=\rho_{2}(\pi_{2}(X))-\dim(\pi_{2}(X)),$

which we have to minimize over all subspaces $\pi_{2}(X)$ of $\mbox{\rm
rs}(Y_{2})$. It is easy to see that the rank function $\rho$ of any
$q$-matroid satisfies $\rho(V)-\dim V\leq\rho(W)-\dim W$ whenever $W\leq V$
(see for instance [4, Lem. 2]), and thus we conclude that the minimum is
attained by a subspace $X$ such that $\pi_{2}(X)=\mbox{\rm rs}(Y_{2})$.
Choosing $X=\mbox{\rm rs}(0\mid Y_{2})$, we may rewrite (3.10) as

$\rho(V)=\dim V+\rho_{2}(\mbox{\rm rs}(Y_{2}))-\dim\mbox{\rm rs}(Y_{2})={\rm
rk}\,(Y_{1})+\rho_{2}(\mbox{\rm rs}(Y_{2})),$

which agrees with (3.9). All of this shows that
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}={\mathcal{M}}_{G}$, as stated. ∎

The following summarizes the open problems concerning representability of the
direct sum.

######  Open Problem 3.10.

Let ${\mathcal{M}}_{i}=({\mathbb{F}}_{q}^{n_{i}},\rho_{i}),\,i=1,2$, be
representable $q$-matroids. Let ${\mathbb{F}}_{q^{\widehat{m}}}$ be the
smallest field over which both ${\mathcal{M}}_{1},\,{\mathcal{M}}_{2}$ are
representable.

  * (a)

Can one characterize representability of
${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ in terms of the summands?

  * (b)

If ${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is representable, what is the
smallest degree $m$ such that ${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$ is
representable over ${\mathbb{F}}_{q^{m}}$? Under which conditions do we have
$m=\widehat{m}$?

We believe that studying representability of $q$-matroids, especially finding
obstructions to representability, will be a challenging, but highly
instructive topic for a better understanding of $q$-matroids and their
differences to matroids. A characterization of representability of the direct
sum in terms of the summands may be a first step in this direction. Note that
3.6 provides already an obstruction to representability in a special case.

## References

  * [1] G. Alfarano and E. Byrne.  The cyclic flats of a $q$-matroid.  Preprint 2022. arXiv: 2204.02353.
  * [2] E. Byrne, M. Ceria, S. Ionica, and R. Jurrius.  Weighted subspace design from $q$-polymatroids.  Preprint 2021. arXiv: 2104.12463.
  * [3] E. Byrne, M. Ceria, and R. Jurrius.  Constructions of new $q$-cryptomorphisms.  J. Comb. Theory. Ser. B, 153:149–194, 2022.
  * [4] M. Ceria and R. Jurrius.  The direct sum of $q$-matroids.  Preprint 2021. arXiv: 2109.13637v4.
  * [5] E. M. Gabidulin.  Theory of codes with maximal rank distance.  Probl. Inf. Transm., 21:1–12, 1985.
  * [6] S. R. Ghorpade and T. Johnsen.  A polymatroid approach to generalized weights of rank metric codes.  Des. Codes Cryptogr., 88:2531–2546, 2020.
  * [7] H. Gluesing-Luerssen and B. Jany.  Coproducts in categories of $q$-matroids.  arXiv: 2111. 09723v2, 2021.
  * [8] H. Gluesing-Luerssen and B. Jany.  Independent spaces of $q$-polymatroids.  Algebr. Comb., 5:727–744, 2022.
  * [9] H. Gluesing-Luerssen and B. Jany.  $q$-Polymatroids and their relation to rank-metric codes.  J. Algebr. Comb., 56:725–753, 2022.
  * [10] H. Gluesing-Luerssen and B. Jany.  Decompositions of $q$-matroids using cyclic flats.  arXiv: 2302.02260, 2023.
  * [11] E. Gorla.  Rank-metric codes.  In W. C. Huffman, J.-L. Kim, and P. Solé, editors, A Concise Encyclopedia of Coding Theory, pages 227–250. CRC, 2021.  See also arXiv 1902.02650.
  * [12] E. Gorla, R. Jurrius, H. López, and A. Ravagnani.  Rank-metric codes and $q$-polymatroids.  J. Algebraic Combin., 52:1–19, 2020.
  * [13] T. Johnsen, R. Pratihar, and H. Verdure.  Weight spectra of Gabidulin rank-metric codes and Betti numbers.  São Paulo J. Math. Sci., 2022.  https://doi.org/10.1007/s40863-022-00314-y.
  * [14] R. Jurrius and R. Pellikaan.  Defining the $q$-analogue of a matroid.  Electron. J. Combin., 25:P3.2, 2018.
  * [15] J. Oxley.  Matroid Theory.  Oxford Graduate Text in Mathematics. Oxford University Press, 2nd edition, 2011.
  * [16] K. Shiromoto.  Codes with the rank metric and matroids.  Des. Codes Cryptogr., 87:1765–1776, 2019.


11institutetext: Technische Universiteit Eindhoven

# The problem of popular primes: Logjam

Wouter Bokslag

###### Abstract

This paper will discuss the Logjam attack on TLS. The Logjam attack allows,
under certain conditions, to defeat the security provided by TLS. This is done
by manipulating server and client into using weak and deprecated _export
grade_ crypto, and subsequently breaking the Diffie-Hellman key exchange. We
explore how the attack works conceptually and how exactly TLS is vulnerable to
this attack. Also, the conditions under which the attack can be mounted are
discussed, and an estimate of the impact of the attack is presented. Lastly,
several mitigations are presented.

##  1 Introduction

In recent days, awareness about the security of communications is on the rise.
More and more websites provide secure connections to protect visitors from
Man-in-the-Middle attacks that might compromise confidentiality and/or
integrity of the communication. Initiatives like Let’s Encrypt[8] further
facilitate the transition towards encrypted communication.

TLS is a cryptographic protocol that facilitates setting up and using secure
communication channels, supporting several authentication methods and
different cryptographic suites. TLS is well known for its use in HTTPS, but
also IMAP, SMTP and many other protocols rely on TLS. As such, the security of
TLS is very important. In the past, various vulnerabilities in the TLS
protocol or in its implementations were found, such as the Lucky 13[2] and
FREAK[10][5] attacks.

In this paper, we discuss the Logjam attack, that targets the Diffie-Hellman
key exchange protocol. In Section 2 we will discuss Diffie-Hellman, and
briefly cover how it can be attacked. The parts of the TLS protocol that are
relevant are discussed in Section 3, while the actual Logjam attack is
explained in Section 4. Different countermeasures are presented in Section 5,
and the main points of this paper are summarized in the conclusion in Section
6.

The Logjam attack is applicable against TLS versions 1.0, 1.1 and 1.2. In this
paper, when the term TLS is used, version 1.2 is meant except if stated
otherwise.

##  2 Breaking Diffie Hellman

The Diffie-Hellman key exchange[7] is a cryptographic algorithm that is used
in order to securely generate a shared secret between two communicating
parties. This key can then be used as a symmetric key in order to allow the
parties to communicate securely.

$\begin{array}[]{@{} l c r @{}}$Alice$&&$Bob$\\\ \\\ g,p&&g,p\\\ $Generate
$a\in\mathbb{Z}_{p}\\\ &\xrightarrow[\rule{56.9055pt}{0.0pt}]{g^{a}}\\\
&&$Generate $b\in\mathbb{Z}_{p}\\\
&\xleftarrow[\rule{56.9055pt}{0.0pt}]{g^{b}}\\\
s\leftarrow(g^{b})^{a}&&s\leftarrow(g^{a})^{b}\\\ \end{array}$

After running the Diffie-Hellman key exchange protocol, Alice and Bob have
obtained shared secret $s=g^{ab}$. An attacker that intercepts their
communication will have the values of $g^{a}$ and $g^{b}$, but will be unable
to obtain the shared secret $g^{ab}$. In order to obtain this, the attacker
will have to compute a discrete logarithm to either obtain the secret exponent
$a$ or $b$. The security of the Diffie-Hellman protocol resides in the fact
that solving the discrete log problem is computationally hard.

Solving the Discrete Log problem for large groups $p$ is efficiently done
using the number field sieve algorithm[13]. Other algorithms exist that can
solve the discrete log problem faster, such as the one presented by Barbulescu
et al. [4], but these algorithms have additional constraints111The algorithm
by Barbulescu et al. requires the finite field to be of small characteristic,
rendering them unsuitable for attacking real-world Diffie-Hellman key
exchanges.

The Number Field Sieve algorithm consists of four steps. We will not discuss
the algorithm in detail, but will present a short overview of the steps, as
this is relevant for understanding the Logjam attack. More details about the
number field sieve algorithm can easily be found online, a great introduction
is presented in _A Tale of Two Sieves_[12] by Pomerance.

The first step is Polynomial selection, which takes a relatively short time
and is easily parallelized, but is important as it has great influence on the
running time of the second step[3], which is the sieving step. During the
sieving, ranges of field elements are factored in order to find elements that
are B-smooth222A number is B-smooth if it only consists of prime factors less
than B. In other words, it can be factored in relatively small primes. .
Sieving also parallelizes well. The third step is linear algebra. A large
matrix is built, consisting of the coefficient vectors found in the previous
step. This step can, to some extent, also be parallelized. The fourth and
final step is the descent. In this step, the output of the previous step is
used to compute the discrete log for a given $a,g$.

##  3 TLS

Before we discuss how Logjam uses the number field sieve algorithm in order to
attack TLS, we first discuss in some detail how the relevant part of TLS
works333Many ways of using TLS are possible, like using client certificates
for authentication. We do not discuss these features and limit ourselves to
the TLS handshake protocol in the most common scenario, where the only the
server authenticates to the user by means of a signed certificate. .

When a client connects to a server through TLS, he sends a ClientHello
message. The format of the message is as follows, as specified444For the sake
of brevity, for some of the TLS messages mentioned in this section, the full
message structure definition is omitted or shortened. in RFC 5246[6]:

      struct {
          ProtocolVersion client_version;
          Random random;
          SessionID session_id;
          CipherSuite cipher_suites<2..2^16-2>;
          CompressionMethod compression_methods<1..2^8-1>;
          select (extensions_present) {
              case false: struct {};
              case true: Extension extensions<0..2^16-1>;
          };
      } ClientHello;

The server receives the ClientHello message, and picks a cipher from the
CipherSuite list that both client and server support555Ideally, the server
picks the most secure cipher suite that is mutually supported.. For the Logjam
attack, the DHE ciphersuites are relevant. The server replies with a
ServerHello message, structured as follows:

      struct {
          ProtocolVersion server_version;
          Random random;
          SessionID session_id;
          CipherSuite cipher_suite;
          CompressionMethod compression_method;
          select (extensions_present) {
              case false: struct {};
              case true: Extension extensions<0..2^16-1>;
          };
      } ServerHello;

The ServerHello is followed by a ServerCertificate message, containing
containing the server’s certificate and the certificate chain linking the
certificate to a trusted Certificate Authority. In the case of a DHE-family
ciphersuite, the server now sends a ServerKeyExchange message

      struct {
          select (KeyExchangeAlgorithm) {
              case dh_anon:
                  ServerDHParams params;
              case dhe_dss:
              case dhe_rsa:
                  ServerDHParams params;
                  digitally-signed struct {
                      opaque client_random[32];
                      opaque server_random[32];
                      ServerDHParams params;
                  } signed_params;
      } ServerKeyExchange;

Note that the ServerKeyExchange contains signed Diffie-Hellman parameters, but
does not contain the actual cipher suite that was chosen by the server. This
is relevant for the Logjam attack, as explained in the next section. The
server ends the Hello phase by sending a ServerHelloDone message. The client
has now received the server’s Diffie-Hellman parameters, namely the modulus
$p$, generator $g$ and the server’s Diffie-Hellman public value $Y_{s}$, and
responds to the server by sending a ClientKeyExchange message, containing the
client’s Diffie-Hellman public value $Y_{c}$. The client now sends the
Finished message, securely encrypted with the negotiated cipher and key. The
server responds by also sending a Finished message, finalizing the handshake.

Clients _may_ use the so-called _False Start_[9]. This allows the client send
an encrypted data packet _before_ it received the Finished message from the
server, in order to reduce the latency caused by the TLS handshake protocol.

##  4 Logjam

Logjam[1] is an attack on TLS, that makes use of a protocol flaw in TLS in
conjunction with support for obsolete and insecure protocols. The attack works
as follows:

###  4.1 Target selection

In order to be vulnerable for the Logjam attack, there are some properties
that must hold for the server configuration. The server should either support
an export-grade cipher suite, or support DHE with a small prime. Export-grade
ciphers are ciphers that were intentionally weakened in the 1990s in order to
comply with US export laws on cryptographic technology.

The authors of the original research paper demonstrated that attacking 512-bit
primes is very possible with today’s technology, while the precomputation for
768-bit primes should be feasible for academic research teams. According to
Adrian et al., it is possible that nation-state level opponents could break a
small number of 1024-bit Diffie-Hellman groups, although the precomputation
would still take a very long time. They argue that this is possibly already
the case, based on evidence of the NSA’s VPN decryption infrastructure that
were leaked by Edward Snowden[14].

An important issue is that some primes are used by many different servers.
This allows an attacker to do the precomputation once, and use the log db in
order to attack many different servers. While computation for 512-bits primes
is not extremely expensive, this definitely increases the plausibility of
attacks against 1024-bit Diffie-Hellman groups, as this would only be
sufficiently rewarding if more than a single target server can be attacked
using the log db. According to Adrian et al., at the time they published their
research paper, 8.4% of the top million websites are vulnerable for the Logjam
attack as they support the use of 512-bit groups. An attacker who is able to
compute a log db for the _single most used 1024-bit group_ is able to attack
37.1% of the one million most popular websites.

###  4.2 Precomputation of log db

Once the prime $p$ that is used by the targeted server(s) is known, the
attacker proceeds to perform a precomputation. This largely follows the steps
outlined in Section 2, but the precomputation only involves the first three
steps. The reason is that the first three stages of the algorithm are solely
based on the prime $p$. If we want to compute $a$ from $y=g^{a}\mod p$, we
only need to use the values of $y$ and $g$ in the descent stage. Logjam
exploits this by precomputing the first three steps for a desired prime $p$,
and storing the intermediate result in a _log db_. When attempting to compute
a discrete log in the field $\mathbb{Z}_{p}$, the log db is used as input for
the descent phase.

Computing a log db takes a long time. However, it is important to know that,
while the Logjam attack focuses on downgrading a TLS connection to export
grade crypto (as explained in the next step), a nation-state level attacker
could possibly attack servers that only support regular, 1024-bit DHE cipher
suites.

###  4.3 Man-in-the-Middle of a connection

When the attacker has built a log db for a given prime, he can abuse a Man-in-
the-Middle scenario and intercept and decrypt the communication between the
client and the server. This works as illustrated in figure 1.

Figure 1: Message Sequence Chart of the Logjam attack. Source: [1]

The ClientHello message is modified by the attacker, removing all
cryptographic suites and adding an export-grade suite that is supported by the
server. The server trivially accepts to use this suite, as it is the only
suite they both ’support’. The ServerHello message that is sent to the client
is now modified, the DHE_EXPORT cipher choice is replaced by regular DHE as
not to arouse suspicion and to not depend on DHE_EXPORT support on the client
side. When the server sends his signed ServerKeyExchange message, this
discrepancy between cipher suite choices between client and server is not a
problem, as the DHE parameters have the same format. The server also sent his
Diffie-Hellman public value $g^{b}$, and the attacker starts to solve the
discrete log problem using the log db, in order to uncover $b$. The client
will send his public value, and send the Finished message. As soon as the
attacker found the value $b$, the attacker sends the message and herewith
completes the TLS handshake. He is now able to decrypt any encrypted traffic
between client and server, and can also modify and re-encrypt data.

If the client uses False Start, he might send a first encrypted data packet
before receiving the server’s Finished message. In that case, the attacker may
decrypt the packet at any time when the discrete log has been found. Even with
the log db, finding $b$ is computationally hard, but there are tricks to hide
or increase the time-frame required by the attacker in order to be able to
send a valid Finished message. The client’s browser will timeout if the server
does not send any new TLS message within a certain time-frame. However, the
attacker can send a TLS warning alert which, besides resetting the timeout, is
ignored by the client. The attacker could open a TLS session to a server the
client is _expected_ to connect to by injecting an invisible element from the
target server in an unencrypted webpage that is also visited by the client,
and solve the discrete log with little time pressure. This connection can then
be kept alive, in order to avoid suspicion due to a long wait when the client
visits the target server.

##  5 Countermeasures

Logjam relies on several server and client settings, and different
possibilities exist to limit or fully mitigate the risks of the Logjam attack.
In this section, we discuss several safeguards that may be implemented by the
server and/or by the client.

###  5.1 Server-side countermeasures

  * •

Randomization of the parameter $p$. Although generating a prime $p$ that is
safe to use666Not all primes are safe, there are some constraints on which
primes are suitable for use. Some servers actually use unsafe primes. David et
al. [1] found 6.8% of servers are configured with a $p$ for which $(p−1)/2$ is
composite, potentially rendering them vulnerable to attack if it consists
solely of relatively small prime factors[11]. is computationally expensive, it
should be possible to let the server generate one upon installation. In that
case, there is less reward for an attacker to do the precomputation for any
prime $p$, as it will allow him to attack only a single server. Additionally,
the prime could be regenerated periodically, in order to further limit the
potential gain for an attacker.

  * •

Disable support for export-grade cipher suites. Export grade cipher suites use
small, 512-bits primes, and as such must be considered unsafe. The server
should not be using primes shorter than 2048 bits.

  * •

Use ECDHE instead of DHE. ECDHE is a variant of Diffie-Hellman which operates
in an elliptic curve instead of a finite field. The advantage here is that
discrete log algorithms for elliptic curves do not benefit as much from
precomputation, raising the bar for an attacker.

###  5.2 Client-side countermeasures

  * •

Require long primes $p$. Currently, 2048 bits primes are considered secure,
while 1024 bits primes may be compromised when considering nation-state level
opponents. Note that the client should actually check if $p>2^{1024}$ as a
1024 bits prime can simply be padded with zeroes in order to be accepted as a
2048 bits.

  * •

Reduce TLS handshake timeout. This provides the attacker with a shorter time
window in which he must solve the DL, increasing the difficulty of the attack.
Also, the timeout should be separate from the current timer, in order to
ensure that it cannot be reset by the attacker using TLS warning alert
messages.

  * •

Be careful with TLS False Start. Even when using shorter timeouts (as
discussed before), the data that is transmitted before the handshake completes
can be decrypted by an attacker as soon as he solved the discrete log for this
session and obtains the shared secret.

##  6 Conclusion

It is expected that TLS 1.3 will mitigate the Logjam attack by adding a field
to the ServerKeyExchange message, that contains the cipher suite chosen by the
server. This field should, like the Diffie-Hellman parameters, be protected
against tampering by a signature. This solves the vulnerability, as an
attacker can no longer trick the client into believing a strong cipher suite
was chosen, while the server chose a deprecated and insecure cipher suite. TLS
1.2, however, can be expected to remain supported for a long time, and until
support is phased out the Logjam attack remains a serious threat. Precautions
must be taken in order to limit the risks of abuse, and different
countermeasures exist. In the opinion of the author, a solution that is in
most cases relatively easy to implement would be to either adopt strong,
2048-bit primes, or to diversify 1024-bit primes by (preferably periodically)
generating them on the server. This would either make precomputation
infeasible or at least drastically decrease the advantage of precomputation,
as the resulting log db could only be used against a single server. Other
solutions, like transitioning away from DHE towards ECDHE, are possibly more
secure, but require larger changes to existing infrastructure, as not all
software supports the stronger ECDHE cipher suite families.

## References

  * [1] David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, et al.  Imperfect forward secrecy: How diffie-hellman fails in practice.  2015\.
  * [2] Nadhem J Al Fardan and Kenneth G Paterson.  Lucky thirteen: Breaking the tls and dtls record protocols.  In Security and Privacy (SP), 2013 IEEE Symposium on, pages 526–540. IEEE, 2013.
  * [3] Shi Bai.  Polynomial selection for the number field sieve.  PhD thesis, PhD thesis, Australian National University, 2011.
  * [4] Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé.  A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic.  In Advances in Cryptology–Eurocrypt 2014, pages 1–16. Springer, 2014.
  * [5] Benjamin Beurdouche, Karthikeyan Bhargavan, Antoine Delignat-Lavaud, Cédric Fournet, Markulf Kohlweiss, Alfredo Pironti, Pierre-Yves Strub, and Jean Karim Zinzindohoue.  A messy state of the union: Taming the composite state machines of tls.  In IEEE Symposium on Security and Privacy, 2015.
  * [6] Tim Dierks and Eric Rescorla.  The transport layer security (tls) protocol version 1.2, august 2008. url http://www. ietf. org/rfc/rfc5246. txt.  Technical report, RFC 5246, 2008.
  * [7] Whitfield Diffie and Martin E Hellman.  New directions in cryptography.  Information Theory, IEEE Transactions on, 22(6):644–654, 1976.
  * [8] Linux Foundation.  About let’s encrypt.  https://letsencrypt.org/about/.  Accessed: 27-01-2016.
  * [9] A Langley, N Modadugu, and B Moeller.  Transport layer security (tls) false start.  draft-bmoeller-tls-falsestart-00, June, 2, 2010.
  * [10] Inria Microsoft.  Smack: State machine attacks.  https://mitls.org/pages/attacks/SMACK.  Accessed: 27-01-2016.
  * [11] Stephen C Pohlig and Martin E Hellman.  An improved algorithm for computing logarithms over gf (p) and its cryptographic significance. 1978 january: Ieee transactions on information theory.  Article submitted on, 1976.
  * [12] Carl Pomerance.  A tale of two sieves.  Biscuits of Number Theory, 85, 2008.
  * [13] Oliver Schirokauer.  The impact of the number field sieve on the discrete logarithm problem in finite fields.  In Proceedings of the 2002 Algorithmic Number Theory workshop at MSRI, 2008.
  * [14] Der Spiegel.  Prying eyes: Inside the nsa’s war on internet security.  http://www.spiegel.de/international/germany/inside-the-nsa-s-war-on-internet-security-a-1010361.html.  Accessed: 27-01-2016.