text:
# Duality and Separation Theorems in Idempotent Semimodules

## 1. Introduction

In this paper, we study semimodules over semirings whose addition is idempotent, that we call idempotent semimodules.

A typical example of semiring with an idempotent addition is the max-plus semiring, $`_{\mathrm{max}}`$, which is the set $`\{\mathrm{}\}`$, equipped with the addition $`(a,b)\mathrm{max}(a,b)`$ and the multiplication $`(a,b)a+b`$. We shall also consider the completed max-plus semiring, $`\overline{}_{\mathrm{max}}`$, which is obtained by adjoining to $`_{\mathrm{max}}`$ a $`+\mathrm{}`$ element. The Boolean semiring $`𝔹`$ is a subsemiring of $`_{\mathrm{max}}`$ and $`\overline{}_{\mathrm{max}}`$ (obtained by keeping only the zero element, $`\mathrm{}`$, and the unit element, $`0`$).

Idempotent semimodules include a number of familiar examples. For instance, the set of convex functions defined on a vector space can be thought of as a semimodule over the max-plus semiring. Another familiar class of idempotent semimodules consists of sup-semilattices with a bottom element, which coincide with semimodules over the Boolean semiring.

The study of idempotent analogues of linear algebraic structures has a long history. Early works, motivated by problems from scheduling theory, graph theory, or dynamic programming, include ? (??), (?), (?), ? (???), ? (?), ? (??), (?), ? (??). The idempotent semimodules that we study here were already apparent in (?).

More recently, the interest for idempotent semimodules arose from the development of the max-plus algebraic approach to optimal control and asymptotic analysis (???), ? (??), and to discrete event systems (????). See ? (??) (??????), for more background. Other works, dealing specially with semimodules, are (?), ? (??), (?).

In this paper, we give Hahn-Banach type theorems for complete idempotent semimodules (the notion of completeness is defined in terms of the natural order of the semimodule). We show that a universal separation result holds (Theorem 8 below), without any additional assumptions on the semimodule or on the semiring, if one takes as a nonlinear dual space an opposite semimodule. To recover a separation theorem involving a linear dual space, we study more generally dual pairs, similar to the ones that arise classically in the theory of topological vector spaces: a predual pair consists of two complete semimodules $`X,Y`$, equipped with a bilinear continuous pairing $``$, and a dual pair is a predual pair which separates points (see §4). We introduce a Galois connection $`XY,x{}_{}{}^{}x`$, $`YX,yy^{}`$, which yields anti-isomorphisms between the lattices of the elements of $`X`$ and $`Y`$ which are closed for this correspondence. For instance, when $`X=\overline{}_{\mathrm{max}}^{n\times 1}`$ is the semimodule of $`n`$-dimensional column vectors over the completed max-plus semiring $`\overline{}_{\mathrm{max}}`$, $`Y=\overline{}_{\mathrm{max}}^{1\times n}`$, and $`yx=\mathrm{max}_{1in}(y_i+x_i)`$, all elements of $`X`$ and $`Y`$ are closed, and the conjugation operation is simply $`{}_{}{}^{}x=(x)^{}`$ and $`y^{}=(y)^{}`$ where $``$ denotes the transposition. For a class of idempotent semirings that we call reflexive, we show that dual pairs satisfy a more familiar, linear, geometric Hahn-Banach theorem, which has the following form (see Theorem 34 below): if $`V`$ is a complete subsemimodule of $`X`$, if $`xX`$ but $`xV`$, then there exist elements $`y,zY`$ such that

(1) $`yv=zv,vV,\mathrm{and}yxzx.`$
The separating pair $`(y,z)`$ is nothing but the pair of conjugates $`({}_{}{}^{}x,{}_{}{}^{}P_{V}^{}(x))`$, where $`P_V(x)`$ is the best approximation from below of $`x`$ by an element of $`V`$. Since $`P_V(x)`$ minimizes an analogue of Hilbert’s projective metric, (1) is similar to the separation property in Euclidean spaces, where $`P_V`$ is the orthogonal projector on $`V`$ and the vector $`(x,P_V(x))`$ gives the direction orthogonal to a separating hyperplane. The key discrepancy, by comparison with vector spaces, is that one needs pairs of linear forms to separate a point from a subspace, or more generally, from a convex set. The affine form of the separation theorem is illustrated in Fig. 1, which shows a max-plus polyhedron generated by three extremal points, $`A,B,C`$, a point $`M`$ which does not belong to the polyhedron, together with a half space $`H`$ (in light gray) which contains the polyhedron, but not the point $`M`$. The half-space is obtained from the projection $`P`$ of $`M`$. See §3.4 for details.

The present idempotent Hahn-Banach theorem extends several earlier results. The first theorem of this kind seems to have been proved by ? (?), for closed convex subsets of $`𝒦^n`$, where $`𝒦`$ is a semiring with an idempotent addition, satisfying some axioms which hold when $`𝒦=_{\mathrm{max}}`$. A similar result was proved by ? (?) under more general assumptions on the semiring, and in an infinite dimensional context, but assuming that the point to separate has invertible coordinates. The present Hahn-Banach theorem holds under more general assumptions, and yields direct explicit formulæ for separating hyperplanes. This generality is possible because we work in complete ordered structures. In the case of the max-plus semiring, this means that the coefficients of the separating half-spaces that we build can take the $`+\mathrm{}`$ value, so that these half-spaces need not be closed for the usual topology. Hence, our results apply even to some convex subsets which are not closed, see the example at the end of Remark 16 below. In (?), we apply the present results to convex functions over the max-plus semiring, and recover in particular a separation theorem à la Zimmerman for closed convex sets. The spirit of the present work is also very close to that of the theory developed by Litvinov, Maslov, and Shpiz (?), who establish idempotent analogues of several classical theorems of functional analysis. The representation theorem for linear forms (Corollary 39 below) and the related analytic form the Hahn-Banach theorem (Corollary 40 below) are extensions of the corresponding results of (?). Finally, we note that a preliminary version of the present results appeared in (?).

We thank V. Kolokoltsov, who suggested (?) to the second author the interest of revisiting max-plus residuation theory with a Galois connection point of view: the present work illustrates the fruitful character of this idea, which is also applied to different problems in (?). We thank M. Akian, P. Lotito, E. Mancinelli, I. Singer and E. Wagneur, for useful discussions. We also thank the referees for their careful reading and detailed comments.

## 2. Preliminaries

### 2.1. Complete Ordered Sets and Residuated Maps

We first recall some classical notions about ordered sets and residuated maps. See (???) for more details.

By ordered set, we will mean throughout the paper a set equipped with a partial order relation. For any subset $`X`$ of an ordered set $`(S,)`$, we denote by $`X`$ (resp. $`X`$) the least upper bound (resp. greatest lower bound) of $`X`$, when it exists. When $`X`$ (resp. $`X`$) belongs to $`X`$, we say that $`X`$ (resp. $`X`$) is the top (resp. bottom) element of $`X`$, and we write $`X`$ (resp. $`X`$) instead of $`X`$ (resp. $`X`$). We say that an ordered set $`(S,)`$ is complete if any subset $`XS`$ has a least upper bound. Then, $`S`$ has a bottom element, $`S=\mathrm{}`$, $`S`$ has a top element, $`S=S`$, and the greatest lower bound of a subset $`X`$ of $`S`$ is given by $`X=\{ySyx,xX\}`$, so that $`S`$ is a complete lattice.

If $`(S,)`$ and $`(T,)`$ are ordered sets, we say that a map $`f:ST`$ is monotone if $`ss^{}f(s)f(s^{})`$. We say that $`f`$ is residuated if there exists a map $`f^{\mathrm{}}:TS`$ such that

(2)
$$f(s)tsf^{\mathrm{}}(t).$$

The map $`f`$ is residuated if, and only if, for all $`tT`$, $`\{sSf(s)t\}`$ has a top element. Then,

(3) $`f^{\mathrm{}}(t)`$ $`=\{sSf(s)t\},tT,`$
which shows in particular that $`f^{\mathrm{}}`$ is monotone. If $`(X,)`$ is an ordered set, we denote by $`(X^{\mathrm{op}},\stackrel{\mathrm{op}}{})`$ the opposite ordered set, for which $`x\stackrel{\mathrm{op}}{}yxy`$. Due to the symmetry of the defining property (2), it is clear that $`f:ST`$ is residuated if, and only if, $`f^{\mathrm{}}:T^{\mathrm{op}}S^{\mathrm{op}}`$ is residuated. In particular, if $`f`$ is residuated,

(4) $`f(s)`$ $`=\{tTsf^{\mathrm{}}(t)\},sS,`$
and $`f`$ is monotone. One also checks that $`f`$ is residuated if, and only if, it is monotone, and there exists a monotone map $`f^{\mathrm{}}:TS`$ such that

(5)
$$ff^{\mathrm{}}I_T,f^{\mathrm{}}fI_S,$$

where $`I_X`$ denotes the identity map on a set $`X`$. Then, $`f`$ and $`f^{\mathrm{}}`$ satisfy (3),(4).

When $`S,T`$ are complete ordered sets, residuated maps can be characterized as follows. Consider the following property, for a map $`f:ST`$:

(6) $`US,f(U)=f(U),\mathrm{where}f(U)=\{f(x)xU\}.`$
This implies in particular that $`f`$ is monotone, and that $`f(S)=T`$ (take $`U=\mathrm{}`$ in (6)). We shall say that $`f`$ is continuous if it satisfies (6). (The term “continuous” can be related to Scott topology (?).) We get:

###### Lemma 1.

If $`(S,)`$ and $`(T,)`$ are complete ordered sets, then, a map $`f:ST`$ is residuated if, and only if, it is continuous.∎

(See (?, Th. 5.2), or (?, Th. 4.50) for a proof.) By symmetry, if $`(S,)`$ and $`(T,)`$ are complete ordered sets, and if $`f`$ is residuated, then, $`f^{\mathrm{}}:T^{\mathrm{op}}S^{\mathrm{op}}`$, is continuous, which means that:

(7)
$$f^{\mathrm{}}(U)=f^{\mathrm{}}(U),UT.$$

We warn the reader that when $`S=T=\{\pm \mathrm{}\}`$, a monotone map $`f:ST`$ is continuous (in the sense of (6)) if, and only if, it is lower semi-continuous in the ordinary sense and fixes $`\mathrm{}`$, whereas a monotone map $`g:T^{\mathrm{op}}S^{\mathrm{op}}`$ is continuous if, and only if, it is upper semi-continuous in the ordinary sense and fixes $`+\mathrm{}`$.

Using the monotonicity of $`f`$ and $`f^{\mathrm{}}`$, together with (5), we easily get that

(8a)
$$ff^{\mathrm{}}f=f,$$

(8b)
$$f^{\mathrm{}}ff^{\mathrm{}}=f^{\mathrm{}},$$

(8c)
$$f^{\mathrm{}}g^{\mathrm{}}=(gf)^{\mathrm{}},$$

where $`g`$ is a residuated map from $`T`$ to some ordered set. It is not difficult to check that

(9a) $`f\text{ is injective}f^{\mathrm{}}f=I_Sf^{\mathrm{}}\text{ is surjective,}`$
(9b) $`f\text{ is surjective}ff^{\mathrm{}}=I_Tf^{\mathrm{}}\text{ is injective.}`$
Moreover, if $`\{f_i\}_{iI}`$ is an arbitrary family of residuated maps from a complete ordered set $`S`$ to a complete ordered set $`T`$,

(10)
$$(\underset{iI}{}f_i)^{\mathrm{}}=\underset{iI}{}f_i^{\mathrm{}},$$

where the $``$ and $``$ are taken pointwise.

### 2.2. Semimodules over Idempotent Semirings

In the sequel, $`(𝒦,,,\epsilon ,e)`$ denotes a semiring whose addition is idempotent (i.e. $`aa=a`$), and $`\epsilon `$ and $`e`$ are the neutral elements for $``$ and $``$, respectively. We shall adopt the usual conventions, and write for instance $`ab`$ instead of $`ab`$. An idempotent commutative monoid $`(S,,\epsilon )`$ can be equipped with the natural order relation, $`abab=b`$, for which $`ab=\{a,b\}`$ and $`\epsilon =𝒦`$. We say that the semiring $`𝒦`$ is complete if it is complete as a naturally ordered set, and if the left and right multiplications, $`L_a^𝒦,R_a^𝒦:𝒦𝒦`$, $`L_a^𝒦(x)=ax`$, $`R_a^𝒦(x)=xa`$, are continuous.

A (right) $`𝒦`$-semimodule $`X`$ is a commutative monoid $`(X,,\epsilon )`$, equipped with a map $`X\times 𝒦X`$, $`(x,\lambda )x\lambda `$ (right action), that satisfies

(11a)
$$x(\lambda \mu )=(x\lambda )\mu ,$$

(11b)
$$(xy)\lambda =x\lambda y\lambda ,x(\lambda \mu )=x\lambda x\mu ,$$

(11c)
$$x\epsilon =\epsilon ,$$

(11d)
$$xe=x,$$

for all $`x,yX`$, $`\lambda ,\mu 𝒦`$. Since $`(𝒦,)`$ is idempotent, $`(X,)`$ is idempotent:

$$xx=x$$

(it follows from (11b) and (11d) that $`x=xe=x(ee)=xexe=xx`$). Axiom (11c) may be we rewritten more explicitly as $`x\epsilon _𝒦=\epsilon _X`$. It implies that

(12) $`\epsilon _X\lambda =\epsilon _X.`$
Indeed, for any $`xX`$, $`\epsilon _X\lambda =(x\epsilon _𝒦)\lambda =x(\epsilon _𝒦\lambda )=x\epsilon _𝒦=\epsilon _X`$, using (11a) and the fact that $`\epsilon _𝒦`$ is absorbing for the product of $`𝒦`$.

The notion of left $`𝒦`$-semimodule is defined dually. Throughout the paper, all the semimodules that we shall consider will be over idempotent semirings. We shall also consider $`𝒦`$-bisemimodules: a bisemimodule is a set equipped with two, right and left, $`𝒦`$-semimodule structures, such that the right and left actions commute. In particular, an idempotent semiring $`𝒦`$ is a $`𝒦`$-bisemimodule if one take as left and right actions the semiring product $`(a,b)ab`$.

When $`𝒦`$ is a complete idempotent semiring, we say that a right $`𝒦`$-semimodule $`X`$ is complete if it is complete as a naturally ordered set, and if, for all $`vX`$ and $`\lambda 𝒦`$, the left and right multiplications, $`R_\lambda ^X:XX`$, $`xx\lambda `$ and $`L_v^X:𝒦X`$, $`\mu v\mu `$, are both continuous. Complete left $`𝒦`$-semimodules and complete $`𝒦`$-bisemimodules are defined in a similar way. In the sequel, all semimodules will be right semimodules, unless otherwise specified. We shall also use the notion of linear map (as usual, a map between semimodules is linear if it preserves finite sums and commutes with the action).

###### Example 2 (Free Complete Semimodules and Semimodules of Functions).

Let $`𝒦`$ denote a complete idempotent semiring. A free complete right $`𝒦`$-semimodule is of the form $`𝒦^I`$ for some arbitrary set $`I`$: the elements of $`𝒦^I`$ are functions $`I𝒦`$, and $`𝒦^I`$ is equipped with the addition $`(a,b)ab,(ab)(i)=a(i)b(i)`$, and the action $`(a,\lambda )a\lambda ,(a\lambda )(i)=a(i)\lambda `$, for all $`a,b𝒦^I,\lambda 𝒦`$. By considering the action $`(a,\lambda )\lambda a,(\lambda a)(i)=\lambda a(i)`$, one can see $`𝒦^I`$ as a left semimodule.

The semimodule $`\overline{}_{\mathrm{max}}^{n\times 1}`$, evoked in the introduction, is an example of a free complete right $`\overline{}_{\mathrm{max}}`$-semimodule. Another example in the same category, to which we will return from time to time in this paper, is the set $`\overline{}_{\mathrm{max}}^𝒰`$ of functions from a set $`𝒰`$ to $`\overline{}_{\mathrm{max}}`$, with the pointwise supremum as $``$ operation and the conventional addition of a real constant as (left or right) action. This semimodule (that we refer to as $``$ for short in the sequel) is complete.

In a complete semimodule $`X`$, we define, for all $`x,yX`$ and $`\lambda 𝒦`$,

(13a) $`x\backslash y`$ $`\stackrel{\mathrm{def}}{=}(L_x^X)^{\mathrm{}}(y)=\{\lambda 𝒦x\lambda y\},`$
(13b) $`x/\lambda `$ $`\stackrel{\mathrm{def}}{=}(R_\lambda ^X)^{\mathrm{}}(x)=\{yXy\lambda x\}`$
(recall our convention to write $``$, instead of $``$, to emphasize the fact the the supremum belongs to the set). Paraphrasing the definition of residuated maps,

(14) $`x\lambda y\lambda x\backslash yxy/\lambda .`$
The residuation formulæ (5), (7), (8) and (10) yield

(15a) $`x(x\backslash y)y,`$ $`(x/\lambda )\lambda x,`$
(15b) $`(x\backslash y)\lambda x\backslash (y\lambda ),`$ $`x(\lambda /\mu )(x\lambda )/\mu ,`$
(15c) $`x\backslash (x\lambda )\lambda ,`$ $`(x\lambda )/\lambda x,`$
(15d) $`x\backslash (U)=(x\backslash U),`$ $`(U)/\lambda =(U/\lambda ),`$
(15e) $`x(x\backslash (x\lambda ))=x\lambda ,`$ $`((x\lambda )/\lambda )\lambda =x\lambda ,`$
(15f) $`x\backslash (x(x\backslash y))=x\backslash y,`$ $`((x/\lambda )\lambda )/\lambda =x/\lambda ,`$
(15g) $`\lambda \backslash (x\backslash z)=(x\lambda )\backslash z,`$ $`(x/\mu )/\lambda =x/(\lambda \mu ),`$
(15h) $`(U)\backslash y=(U\backslash y),`$ $`x/(\mathrm{\Lambda })=(x/\mathrm{\Lambda }),`$
for all $`x,y,zX`$, $`UX`$, $`\mathrm{\Lambda }𝒦`$, where $`(U\backslash y)=\{u\backslash yuU\}`$, $`x/\mathrm{\Lambda }=\{x/\lambda \lambda \mathrm{\Lambda }\}`$, etc. (In the right formula (15b) and in the left formula (15g), $`𝒦`$ is seen respectively as a right and left semimodule over itself.) Finally, if $`X`$ is a bisemimodule and $`\mu ,\nu 𝒦`$, the maps $`xx\lambda `$ and $`x\nu x`$ commute, hence, by (8c), their residuated maps commute, which means that

(16) $`(\nu \backslash x)/\mu `$ $`=\nu \backslash (x/\mu ).`$
Since there is no ambiguity, we may simply write $`\nu \backslash x/\mu `$ for (16).

###### Remark 3.

Note that (13a) is dual of the definition (5.1) in ?; the latter requires the assumption that the action of vectors on scalars satisfies $`x(_{\lambda \mathrm{\Lambda }}\lambda )=_{\lambda \mathrm{\Lambda }}(x\lambda )`$ — see ? which is written for right action of vectors on scalars — whereas, in this paper, we stick to the more natural assumption that this property holds with $``$ instead of $``$: this is the case for instance if the underlying semiring is a semiring of formal series, or of matrices, over a complete idempotent semiring.

### 2.3. Opposite Semimodules

If $`X`$ is a complete right $`𝒦`$-semimodule, we call opposite semimodule of $`X`$ the left $`𝒦`$-semimodule $`X^{\mathrm{op}}`$ with underlying set $`X`$, addition $`(x,y)\{x,y\}`$ (the $``$ is for the natural order of $`X`$) and left action $`𝒦\times XX`$, $`(\lambda ,x)x/\lambda `$. For clarity, we shall sometimes denote by $`(\lambda ,x)\lambda \stackrel{\mathrm{op}}{}x=x/\lambda `$ the left action of $`X^{\mathrm{op}}`$. That $`X^{\mathrm{op}}`$ is a complete semimodule follows from formulæ (15d), (15g), and (15h). In particular, (15g) yields

(17) $`(\lambda \mu )\stackrel{\mathrm{op}}{}x`$ $`=x/(\lambda \mu )=(x/\mu )/\lambda =\lambda \stackrel{\mathrm{op}}{}(\mu \stackrel{\mathrm{op}}{}x),`$
for all $`\lambda ,\mu 𝒦`$ and $`xX^{\mathrm{op}}`$, which shows why $`X^{\mathrm{op}}`$ must be considered as a left rather than a right semimodule. Indeed, considering $`(x,\lambda )x/\lambda `$ as a right action would require the property symmetrical to (17) to hold, that is, by (11a), $`x/(\lambda \mu )=(x/\lambda )/\mu `$, but this property need not hold for a semimodule $`X`$ over a noncommutative semiring $`𝒦`$.

Denoting by $`\stackrel{\mathrm{op}}{\backslash }`$ and $`\stackrel{\mathrm{op}}{/}`$ the residuated operations built from $`\stackrel{\mathrm{op}}{}`$, we get from (14),

(18a) $`\lambda \stackrel{\mathrm{op}}{\backslash }x=(L_\lambda ^{X^{\mathrm{op}}})^{\mathrm{}}(x)`$ $`=\{yXy/\lambda x\}=x\lambda ,`$
(18b) $`x\stackrel{\mathrm{op}}{/}y=(R_y^{X^{\mathrm{op}}})^{\mathrm{}}(x)`$ $`=\{\lambda 𝒦y/\lambda x\}=x\backslash y.`$
Eqn (18a) is an involutivity property: the residuated law of the residuated law of the right action of $`X`$ is the right action of $`X`$ itself. Therefore,

###### Proposition 4.

For all complete $`𝒦`$-semimodules $`X`$, $`(X^{\mathrm{op}})^{\mathrm{op}}=X`$. ∎

## 3. Nonlinear Projectors, Universal Separation Theorem and Hilbert projective metric

### 3.1. Nonlinear Projector

Let $`V`$ denote a complete subsemimodule of a complete semimodule $`X`$ over a complete idempotent semiring $`𝒦`$, i.e., a subset of $`X`$ that is stable by arbitrary sups and by the action of scalars. We call canonical projector on $`V`$ the map

$$P_V:XX,P_V(x)=\{vVvx\}$$

(the least upper bound of $`\{vVvx\}`$ belongs to this set by definition of complete subsemimodules). It is readily seen that $`P_V^2=P_V`$ and that $`P_V(X)=V`$. We say that $`W`$ is a generating family of a complete subsemimodule $`V`$ if any element $`vV`$ can be written as $`v=\{w\lambda _wwW\}`$, for some $`\lambda _w𝒦`$.

###### Theorem 5 (Projector Formula).

If $`V`$ is a complete subsemimodule of $`X`$ with generating family $`W`$, then

(19) $`P_V(x)=\underset{wW}{}w(w\backslash x).`$
###### Proof.

We can write $`P_V(x)=_{wW}w\lambda _w`$, for some $`\lambda _w𝒦`$. From $`P_V(x)x`$, we get $`w\lambda _wx`$, or, equivalently, $`\lambda _ww\backslash x`$. This shows that $`P_V(x)_{wW}w(w\backslash x)`$. But, $`_{wW}w(w\backslash x)`$ is an element of $`V`$, which, by (15a), is less than or equal to $`x`$. This proves (19). ∎

We may rewrite (19) as $`P_V=_{wW}P_w,`$ where $`P_w`$ denotes the projector on the “one dimensional” space $`w𝒦`$. Similar formulæ for the projector appeared in (?).

###### Proposition 6 (Dual characterization of the projector).

Let $`VX`$ denote a complete subsemimodule with generating family $`W`$. Then,

(20)
$$P_V(x)=\{zXw\backslash zw\backslash x,wW\}.$$

###### Proof.

Since $`w\backslash zw\backslash xzw(w\backslash x)`$, this follows from (19). ∎

###### Example 7.

We return to the $`\overline{}_{\mathrm{max}}`$-semimodule $``$ introduced at Example 2 and discuss the application of previous results in this section. First of all, observe that

$$f,g,f\backslash g=\underset{u𝒰}{inf}\left(g(u)f(u)\right),$$

with the convention here that $`+\mathrm{}\mathrm{}=+\mathrm{}`$, since in any complete idempotent semiring $`𝒦`$, $`𝒦\backslash 𝒦=𝒦\backslash 𝒦=𝒦`$. (Observe however that $`(𝒦)(𝒦)=\epsilon (𝒦)=\epsilon =𝒦`$, which translates, in $`\overline{}_{\mathrm{max}}`$, as $`\mathrm{}+\mathrm{}=\mathrm{}`$, so that this “rule” written in conventional notation is ambiguous, and one must keep in mind what are the correct algebraic operations hidden behind the conventional notation to apply the rule correctly.)

Assume now that $`𝒰`$ is a locally convex topological vector space and consider the complete subsemimodule $`V`$ generated by the set $`W`$ of continuous linear functions over $`𝒰`$. This semimodule consists of the identically $`\mathrm{}`$ function over $`𝒰`$, and of the l.s.c. convex functions over $`𝒰`$ which do not take the value $`\mathrm{}`$. For any $`f`$, $`P_V(f)`$, as defined in §3.1, is the classical l.s.c. convex hull of $`f`$. For $`wW`$,

$$w\backslash f=\underset{u𝒰}{inf}\left(f(u)w(u)\right)=\underset{u𝒰}{sup}\left(w(u)f(u)\right),$$

which coincides, up to a change of sign, with the Legendre-Fenchel transform $`f^{}`$ of $`f`$ evaluated at $`w`$. Eqn (19) then yields

$$P_V(f)()=\underset{wW}{}w(w\backslash f)=\underset{wW}{}\left(w()f^{}(w)\right),$$

that is to say, the l.s.c. convex hull of $`f`$ is the Legendre-Fenchel transform of the Legendre-Fenchel transform of $`f`$.

Finally, Eqn (20) says that the l.s.c. convex hull of $`f`$ is the least function $`g`$ in $``$ such that $`g^{}`$ is less than, or equal to, $`f^{}`$ (pointwise).

### 3.2. Universal Separation Theorem

###### Theorem 8 (Universal Separation Theorem).

Let $`VX`$ denote a complete subsemimodule, and let $`xX`$. Then,

(21a) $`vV,`$ $`v\backslash P_V(x)=v\backslash x,`$
and
(21b) $`xV`$ $`x\backslash P_V(x)=x\backslash x.`$
Seeing $`y\backslash x`$ as a “scalar product”, Eqn (21a) says that the vector $`(x,P_V(x))`$ is “orthogonal” to the semimodule $`V`$, and (21b) shows that the “hyperplane” $`\{yy\backslash P_V(x)=y\backslash x\}`$ separates $`x`$ from $`V`$, if and only if $`xV`$. This terminology will be justified in §4.

###### Proof.

Since, by definition, the $``$ in (20) belongs to the set, we have that $`v\backslash P_V(x)v\backslash x`$, for all $`vV`$. Using $`P_V(x)x`$ and the monotonicity of $`yv\backslash y`$, we get the reverse inequality, which shows (21a). If $`xV`$, then $`P_V(x)=x`$, and $`x\backslash P_V(x)=x\backslash x`$, trivially. Conversely, if $`x\backslash P_V(x)=x\backslash x`$, we have, by (14), that $`P_V(x)x(x\backslash x)`$, and, by (15e), that $`x(x\backslash x)=x`$, which shows that $`P_V(x)x`$. Since $`P_V(x)x`$, we have $`x=P_V(x)V`$. ∎

###### Remark 9.

The separating set $`H=\{vVv\backslash P_V(x)=v\backslash x\}`$ is a semimodule. Indeed, by (15h) it is stable by addition and (15g) shows that it is stable by scalar action.

###### Remark 10.

According to the previous remark, it is sufficient to check (21a) only for $`v`$ ranging in a generating subset $`W`$ of $`V`$.

###### Example 11.

For the semimodule $``$ introduced at Example 2 and the subsemimodule $`V`$ of l.s.c. convex functions generated by the subset $`W`$ of continuous linear functions as discussed at Example 7, the equality (21a) (restricted to $`vW`$ as observed in the previous remark) of the Separation Theorem says that the Legendre-Fenchel transform of any function $`f`$ coincides with the Legendre-Fenchel transform of its l.s.c. convex hull. As for (21b), observe first that $`f\backslash f=0`$ unless $`f`$ assumes only $`\pm \mathrm{}`$ values (in this latter case, $`f\backslash f=+\mathrm{}`$). Let us put aside this singular situation first. Then (21b) says that $`f`$ coincides with its l.s.c. convex hull at all points if and only if it is itself l.s.c. convex.

In the singular case, and according to (21b), $`f`$ is l.s.c. convex if and only if $`f\backslash P_V(f)=inf_{u𝒰}\left(P_V(f)(u)f(u)\right)=+\mathrm{}`$, that is, $`P_V(f)(u)f(u)=+\mathrm{}`$ for all $`u`$. According to the rule $`\mathrm{}+\mathrm{}=+\mathrm{}`$ which applies here, this shows that $`f(u)=+\mathrm{}`$ implies that $`P_V(f)(u)=+\mathrm{}`$. On the other hand, if $`f(u)=\mathrm{}`$, then $`P_V(f)(u)=\mathrm{}`$ because $`P_V(f)f`$ pointwise. Finally, in all cases, we have reached the conclusion that (21b) says that $`f`$ coincides with its l.s.c. convex hull at all points if and only if it is itself l.s.c. convex.

The “scalar product” $`y\backslash x`$ separates points, in the following sense:

###### Proposition 12 (Separation of Points).

If $`X`$ is a complete $`𝒦`$-semimodule, then, for all $`x,yX`$,

(22) $`(zX,x\backslash z=y\backslash z)x=y.`$
###### Proof.

If $`x\backslash z=y\backslash z`$ for all $`zX`$, taking $`z=x`$, we get that $`ex\backslash x=y\backslash x`$, hence $`yx`$. By symmetry, $`xy`$. ∎

Finally, we note that all the above results have dual versions for the semimodule $`X^{\mathrm{op}}`$: they are derived readily from (18). For instance, if $`VX^{\mathrm{op}}`$ is a complete subsemimodule, we define

(23) $`P_V^{\mathrm{op}}(x)`$ $`={}_{}{}^{\mathrm{op}}\{vVv\stackrel{\mathrm{op}}{}x\}=\{vVvx\},`$
where $`{}_{}{}^{\mathrm{op}}=`$ denotes the least upper bound associated with $`\stackrel{\mathrm{op}}{}`$, and the dual version of Theorem 8 reads:

###### Theorem 13 (Dual Separation Theorem).

Let $`VX^{\mathrm{op}}`$ denote a complete subsemimodule, and let $`xX`$. Then,

(24a) $`vV,`$ $`P_V^{\mathrm{op}}(x)\backslash v=x\backslash v,`$
and
(24b) $`xV`$ $`P_V^{\mathrm{op}}(x)\backslash x=x\backslash x.`$
In the same way, dualizing (22), we get the following separation property for points:

(25) $`(zX,z\backslash x=z\backslash y)x=y.`$
###### Remark 14.

It is natural to ask whether the projector

$$Q_V(x)=\{vVvx\}$$

can be defined when $`V`$ is a subsemimodule of $`X`$, rather than a semimodule of $`X^{\mathrm{op}}`$ as in (23). The difficulty is that $`Q_V(x)`$ need not belong to $`V`$. For instance, when $`V\overline{}_{\mathrm{max}}^3`$ is the subsemimodule generated by the columns of the matrix

$$\left(\begin{array}{cc}0& 1\\ 1& 0\\ 0& 0\end{array}\right),$$

$$Q_V\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right)$$

does not belong to $`V`$. However, in the special case when $`V`$ is a complete subsemimodule of $`X`$ stable by arbitrary infs, we have $`Q_V(x)V`$, for all $`xX`$, and $`Q_V`$ preserves arbitrary sups, whereas $`P_V`$ need not have this property.

We now derive from Theorem 8 a Hahn-Banach theorem for complete convex subsets, in the spirit of (?). We say that a subset $`C`$ of a complete semimodule over a complete semifield $`𝒦`$ is convex (resp. complete convex) if for all finite (resp. arbitrary) families $`\{x_i\}_{iI}C`$ and $`\{\alpha _i\}_{iI}𝒦`$, such that $`_{iI}\alpha _i=e`$, we have that $`_{iI}\alpha _ix_iC`$. Theorem 8 has an immediate extension to convex sets.

###### Corollary 15 (Separating a Point from a Convex Set).

If $`C`$ is a complete convex subset of a complete $`𝒦`$-semimodule $`X`$, and if $`xX`$ is not in $`C`$, then we have

(26a) $`v\backslash xe`$ $`=v\backslash y\nu ,vC,`$
(26b) $`x\backslash xe`$ $`>x\backslash y\nu ,`$
with

(27) $`\nu `$ $`=\underset{vC}{}(v\backslash xe),y=\underset{vC}{}v(v\backslash xe).`$
###### Proof.

Consider the complete $`𝒦`$-semimodule $`Y=X\times 𝒦`$ and the complete subsemimodule $`V`$ generated by the vectors $`(v\lambda ,\lambda )`$, where $`vC`$ and $`\lambda 𝒦`$. It is easy to see that $`(v,e)`$ belongs to $`V`$ iff $`v`$ belongs to the complete convex set generated by $`C`$, which coincides with $`C`$. When $`xC`$, then $`(x,e)V`$, and applying Theorem 8, we have that

$$(v,e)\backslash (x,e)=(v,e)\backslash P_V((x,e)),vC.$$

$$(x,e)\backslash (x,e)>(x,e)\backslash P_V((x,e)).$$

By using this result with

$`(y,\nu )`$ $`=P_V((x,e))`$
$`=\underset{vC}{}(v,e)\left((v,e)\backslash (x,e)\right)`$
(thanks to (19))
$`=\underset{vC}{}(v,e)(v\backslash xe)`$
(since $`(a,\lambda )\backslash (b,\lambda ^{})=a\backslash b\lambda \backslash \lambda ^{}`$), the proof is completed. ∎

###### Remark 16.

Observe that if $`xC`$, then $`P_V((x,e))=(x,e)`$, $`\nu =e`$ and $`y=x`$. Moreover, if $`\nu `$ is invertible, then it is easy to see that $`y\nu ^1`$ belongs to $`C`$ and can thus be considered as the projection of $`x`$ onto the convex subset $`C`$. Indeed, setting $`P_C(x)=y\nu ^1`$ (whenever this expression is defined), the image of $`C`$ by $`P_C`$ is $`C`$ and $`P_CP_C=P_C`$.

When $`\nu `$ is not invertible (in $`\overline{}_{\mathrm{max}}`$, this means that $`\nu =\epsilon `$ since $`\nu `$ is not greater than $`e`$), we still do have a separating equation but its interpretation in terms of projection onto $`C`$ is missing. This happens in the following example: $`X=𝒦=\overline{}_{\mathrm{max}}`$ and $`C=(\mathrm{},+\mathrm{}]`$. This $`C`$ is complete convex but not closed in the usual topology. Nevertheless, the previous theory still applies and we can separate $`x=\mathrm{}`$ from $`C`$. Calculations show that $`y=\nu =\mathrm{}`$ and relations (26) can be checked to be true.

### 3.3. Generalized Hilbert projective metric

Consider $`d_H:X\times X𝒦`$ defined by $`d_H(x,y)=(x\backslash y)(y\backslash x)`$. Observe that $`d_H(x,y)=d_H(y,x)`$ when $`𝒦`$ is commutative. When $`X=\overline{}_{\mathrm{max}}^n`$, $`d_H`$ is nothing but an additive version of Hilbert projective metric, which is the map

$$\delta _H(x,y)=\underset{1i,jn}{\mathrm{max}}\mathrm{log}\left(\frac{x_i}{y_i}\frac{y_j}{x_j}\right)$$

for $`x,y`$ ranging in the open positive cone of $`^n`$. When $`x,y^n`$,

$$d_H(x,y)=\underset{1i,jn}{\mathrm{min}}(x_iy_i+y_jx_j)=\delta _H(\mathrm{exp}x,\mathrm{exp}y),$$

where $`\mathrm{exp}`$ operates coordinatewise.

###### Theorem 17.

The map $`d_H`$ satisfies the following properties:

* anti-triangular inequality (when $`𝒦`$ is commutative):

$$d_H(x,z)d_H(x,y)d_H(y,z);$$
* definiteness:

$$d_H(x,y)=ex=y\lambda ,\lambda 𝒦,$$
* nonpositiveness:

$$d_H(x,y)x\backslash x\text{and }d_H(x,y)(x\backslash x)(y\backslash y)\text{ when }𝒦\text{ is commutative.}$$

###### Proof.

* Anti-triangular inequality:

$`(x\backslash y)(y\backslash x)(y\backslash z)(z\backslash y)`$ $`=(x\backslash y)(y\backslash z)(z\backslash y)(y\backslash x)(x\backslash z)(z\backslash x)`$
by (15b) and (15a).
* Definiteness: if $`d_H(x,y)=e`$ we have that

$$x=x(x\backslash y)(y\backslash x)y(y\backslash x)x,$$

hence $`x=y(y\backslash x)`$.
* Nonpositiveness:

$$(x\backslash y)(y\backslash x)x\backslash (y(y\backslash x))x\backslash x.$$

In conventional Euclidean spaces, the projection of a point onto a subspace minimizes the distance from that point to any point of the subspace. We show here that $`d_H`$ is maximized by projection.

###### Theorem 18.

For all $`xX`$ and $`vV`$, where $`V`$ is a complete subsemimodule of a semimodule $`X`$, we have that $`d_H(x,v)d_H(x,P_V(x))`$.

###### Proof.

$`d_H(x,P_V(x))`$ $`=(x\backslash P_V(x))(P_V(x)\backslash x)`$
$`x\backslash P_V(x)`$ $`\text{(because }P_V(x)x)`$
$`=x\backslash \left(\underset{vV}{}(v(v\backslash x))\right)`$
$`x\backslash (v(v\backslash x)),`$ $`vV`$
$`(x\backslash v)(v\backslash x),`$ $`vV`$ $`(\text{by (}\text{15b}\text{))}`$
$`=d_H(x,v),`$ $`vV.`$
###### Example 19.

Once again we return to our favorite illustration described at Examples 2 and 7. For two functions $`f`$ and $`g`$ in $``$, we consider

$$d_H(f,g)=\underset{u𝒰}{sup}\left(f(u)g(u)\right)+\underset{v𝒰}{sup}\left(g(v)f(v)\right).$$

This is a “form factor”, which measures “how far” is $`fg`$ from a constant map. Indeed, when $`f,g`$ are finite, $`d_H(f,g)`$ is nothing but the difference between the sup and the inf of of $`fg`$. Then, Theorem 18 says that the l.s.c. convex hull of $`f`$ is, among all l.s.c. convex functions, one which minimizes this form factor difference with $`f`$ (but of course not the only one).

### 3.4. A Two Dimensional Example

We consider the convex set generated by points $`A,B,C`$ of coordinates $`(0,0),(1,3)`$ and $`(3,4)`$ in $`_{\mathrm{max}}^2`$. Figure 2

represents these 3 points in this space and the convex set is depicted in dark grey (notice it has two “antennas” ending in $`A`$ and $`C`$ in addition to the polygon with nonempty interior). Figure 3 is a

representation in the 3D space where (a fragment of) the subsemimodule $`V`$ — introduced in the proof of Corollary 15 — generated by points $`A,B,C`$ (now with coordinates $`(0,0,0),(1,3,0)`$ and $`(3,4,0)`$) is represented. The intersection of this subsemimodule with the $`(x,y)`$-plane is the convex set represented in Figure 2. The “cylinder” is parallel to the vector $`(1,1,1)`$. Figure 4

is a representation of what can be seen by an observer located at a remote point along the vector $`(1,1,1)`$.

We now consider projecting the point $`M`$ of coordinates $`(1,0)`$ (in $`_{\mathrm{max}}^2`$) onto the convex set. According to Remark 16, this point is first projected on the subsemimodule $`V`$ at point $`N`$ of coordinates $`(1,0,1)`$ in $`(_{\mathrm{max}}^3)`$: indeed, this is the “best approximation from below” of $`M`$ by an element of the subsemimodule. The reader can check this claim by using the provided explicit formulæ (19). Then, $`N`$ is brought back to $`_{\mathrm{max}}^2`$ by “normalization” of the $`z`$-coordinate to $`0`$, yielding the point $`P`$ of coordinates $`(0,1,0)`$. Points $`M,N,P`$ are shown in the three figures.

Relations (26) yield the following

$`\mathrm{min}(1x,y,0)`$ $`=\mathrm{min}(1x,y,1),(x,y)\text{ in the convex set;}`$
$`\mathrm{min}(1(1),0,0)`$ $`>\mathrm{min}(1(1),0,1)\text{when applied to }M.`$
The former equation simplifies into $`\mathrm{min}(1x,y,0)1`$ which says that $`1x1`$ or $`y1`$: this is the union of two half planes, corresponding to the light grey region in Figure 1.

Observe that in Figure 2, points $`M`$ and $`N`$ are located at the same place because it turns out that they are located on the same vertical line of $`_{\mathrm{max}}^3`$, whereas in Figure 4, points $`N`$ and $`P`$ are located at the same place: this is a general fact because normalization always implies a move in the direction in which the observer of this figure is located.

In Figures 2 and 4, several zones around the convex set are also shown:

* in light grey conic zones, it turns out that all points project onto a particular “extreme” point of the convex set;

+ in the grey zone attached to point $`C`$ (and in the whole positive orthant $`(x0,y0)`$ as well), there is a single move in the $`(x,y)`$-plane, that is, the projection onto the subsemimodule coincides with that onto the convex set;
    + in the other two grey zones, there are actually two moves: one caused by the projection onto the subsemimodule, the other one caused by normalization; this is materialized by dotted line arrows in Figure 2; in Figure 4, the latter move (caused by normalization) is not visible for reasons already explained hereabove.
* in the white zones of the positive orthant, as already mentioned, the moves are always one-phase (i.e. horizontal); in the white zone which $`M`$ belongs to, the former move is vertical (thus it cannot be visualized on Figure 2) and the latter one (normalization) is (as everywhere) along the first diagonal.

Finally, level sets of the generalized Hilbert metric are shown around point $`M`$ in those figures.

###### Example 20.

It is useful to understand the geometry of affine max-plus hyperplanes of $`_{\mathrm{max}}^2`$, that we shall call lines. The general line is defined by an equation of the form

$$axbyc=a^{}xb^{}yc^{},$$

for some $`a,b,c,a^{},b^{},c^{}_{\mathrm{max}}`$, but not all the coefficients are needed. For instance, the lines with equations $`2xy=1xy3`$ and $`2xy=y3`$, coincide. More generally, it is not difficult to see that there are $`12`$ generic shapes of lines, as shown in Figure 5.

Indeed, a generic line can be defined by three real numbers $`a,b,c`$ plus a “sign” information, which tells the side of the equation in which the corresponding coefficients is dominant (say “$``$” for the left hand side, “$``$” for the right and side, and a dot when coefficients on both sides are equal). For instance, the line with equation $`axc=byc`$ can be denoted $`L(a,b,\dot{c})`$. This notation can be justified by introducing the symmetrized max-plus semiring (???). It is fundamental to note that a line with a dotted coefficient has dimension $`2`$ in the usual sense. Note also that half-planes are special lines, since for instance an inequality of the form $`xy`$ can be written as an equation $`x=xy`$.

## 4. Dual Semimodules and Hahn-Banach Theorems

### 4.1. Dual and Predual Pairs

Given a complete idempotent semiring $`𝒦`$, we call predual pair a complete right $`𝒦`$-semimodule $`X`$ together with a complete left semimodule $`Y`$ equipped with a bracket $``$ from $`Y\times X`$ to a complete $`𝒦`$-bisemimodule $`Z`$, such that, for all $`xX`$, the maps $`𝖱_x:YZ`$, $`yyx`$ and $`𝖫_y:XZ`$, $`xyx`$ are respectively left and right linear, and continuous. We shall denote by $`(Y,X)`$ or simply $`Y,X`$ this predual pair. The most familiar choice of $`Z`$, which corresponds to “classical” bilinear forms, is $`Z=𝒦`$. The semiring $`𝒦`$ yields another $`𝒦`$-bisemimodule $`Z=𝒦^{\mathrm{op}}`$, with addition $`(x,y)\{x,y\}`$, right action $`(x,\lambda )\lambda \backslash x`$, and left action $`(\lambda ,x)x/\lambda `$.

We say that $`Y`$ separates $`X`$ if

$$(yY,yx_1=yx_2)x_1=x_2,$$

and that $`X`$ separates $`Y`$ if

$$(xX,y_1x=y_2x)y_1=y_2.$$

A predual pair $`(Y,X)`$ such that $`X`$ separates $`Y`$ and $`Y`$ separates $`X`$ is a dual pair. This notion is inspired by the dual pairs which arise in the theory of topological vectors spaces, see ?, Chapter 4, (?) or ?, Chapter 5, (?).

###### Example 21.

The right semimodule $`𝒦^I`$ forms a dual pair with the left semimodule $`𝒦^I`$ (both were introduced at Example 2), for the canonical bracket $`ab=_{iI}a(i)b(i)`$.

###### Theorem 22 (Opposite Dual Pair).

Let $`X`$ denote a complete right $`𝒦`$-semimodule. Then, the semimodules $`X^{\mathrm{op}},X`$ form a dual pair for the bracket $`X^{\mathrm{op}}\times X𝒦^{\mathrm{op}}`$, $`(y,x)yx=x\backslash y`$.

###### Proof.

The bilinearity and continuity of $``$ follows from (15d), (15g), (15h), and (16). Eqn (22) shows that $`X^{\mathrm{op}}`$ separates $`X`$, and Eqn (25) shows that $`X`$ separates $`X^{\mathrm{op}}`$. ∎

A different example of predual pair arises when considering the (topological) dual $`X^{}`$ of a complete semimodule $`X`$, which is the set of linear continuous maps $`y:X𝒦`$. The spaces $`X^{},X`$ form a predual pair for the bracket $`yx=y(x)`$, and $`X`$ trivially separates $`X^{}`$, but $`X^{}`$ need not separate $`X`$ (see Example 38 below).

###### Example 23.

Consider again the dual pair $`(𝒦^I,𝒦^I)`$ of Example 21. With any element $`a𝒦^I`$ is associated an element of the dual, $`𝖫_a:(𝒦^I)^{}`$, $`bab`$, and any element of the dual is of this form. Thus, $`(𝒦^I)^{}`$ can be identified to $`𝒦^I`$, and $`(𝒦^I)^{}`$ trivially separates $`𝒦^I`$ (indeed, if $`b,c𝒦^I`$ are such that $`b(i)c(i)`$ for some $`iI`$, the Dirac function at point $`i`$, $`\delta _i(𝒦^I)^{},\delta _i(d)=d(i)`$, separates $`b`$ from $`c`$).

### 4.2. Involutions

Given a bracket $``$ from $`Y\times X`$ to a complete $`𝒦`$-bisemimodule $`Z`$, and an arbitrary element $`\phi Z`$, we define the maps:

(28a) $`XY,x{}_{}{}^{}x`$ $`=\{yYyx\phi \},`$
(28b) $`YX,yy^{}`$ $`=\{xXyx\phi \}.`$
Thus, $`{}_{}{}^{}x=𝖱_x^{\mathrm{}}(\phi )`$ and $`y^{}=𝖫_y^{\mathrm{}}(\phi )`$.

###### Proposition 24.

If $`(Y,X)`$ is a predual pair, then

(29a) $`({}_{}{}^{}x)^{}`$ $`x,`$ $`{}_{}{}^{}(({}_{}{}^{}x)^{})`$ $`={}_{}{}^{}x,xX,`$
(29b) $`{}_{}{}^{}(y^{})`$ $`y,`$ $`({}_{}{}^{}(y^{}))^{}`$ $`=y^{},yY.`$
###### Proof.

We have

(30) $`xy^{}yx\phi y{}_{}{}^{}x.`$
Consider now the maps $`\iota _{\mathrm{}}:YX,yy^{}`$ and $`\iota _r:XY,x{}_{}{}^{}x`$. Eqn (30) shows that $`\iota _{\mathrm{}}:(Y,)(X,\stackrel{\mathrm{op}}{})`$ is residuated, with $`\iota _{\mathrm{}}^{}{}_{}{}^{\mathrm{}}=\iota _r`$. Thus, (29a) and (29b) follow from (5) and (8). ∎

We call closed the elements of $`X`$ and $`Y`$ of the form $`y^{}`$ and $`{}_{}{}^{}x`$, respectively. We set $`\overline{X}=\{y^{}yY\}`$ and $`\overline{Y}=\{{}_{}{}^{}xxX\}`$.

###### Proposition 25.

The sets of closed elements $`\overline{X}`$ and $`\overline{Y}`$ are complete inf-subsemilattices of $`X`$ and $`Y`$, respectively,

###### Proof.

The set $`\overline{X}`$ is the image of the map $`\iota _{\mathrm{}}:(Y,)(X,\stackrel{\mathrm{op}}{})`$ which is residuated, and, by Lemma 1, this image must be a complete sup-subsemilattice of $`X`$ for the order $`\stackrel{\mathrm{op}}{}`$, i.e., a complete inf-subsemilattice of $`X`$ for the order $``$. ∎

(We warn the reader that the sup laws of $`\overline{X}`$ and $`\overline{Y}`$ do not coincide with those of $`X`$ and $`Y`$, in general.) It follows from (29) that $`({}_{}{}^{}x)^{}=x`$ (resp. $`{}_{}{}^{}(y^{})=y`$) if and only if $`x`$ (resp. $`y`$) is closed, hence:

###### Proposition 26.

The map $`x{}_{}{}^{}x`$ is an anti-isomorphism of complete lattices $`\overline{X}\overline{Y}`$, with inverse $`yy^{}`$.

Recall that if $`S,T`$ are complete lattices, a map $`f:ST`$ is an anti-isomorphism if, for all $`US`$, $`f(U)=f(U)`$ and $`f(U)=f(U)`$. A map $`f:ST`$ is antitone if $`ss^{}f(s)f(s^{})`$.

###### Proof.

We already know that $`x{}_{}{}^{}x`$ is an antitone bijection from $`\overline{X}`$ to $`\overline{Y}`$ with inverse $`yy^{}`$. A bijective antitone map between complete lattices whose inverse is antitone is automatically an anti-isomorphism of complete lattices. ∎

Since $`Z`$ is a complete $`𝒦`$-bisemimodule, $`\lambda \backslash \mu `$, and, dually, $`\mu /\nu `$ are well defined for $`\mu Z`$ and $`\lambda ,\nu 𝒦`$. Considering the predual pair $`(𝒦,Z)`$ for the bracket $`\lambda \mu =\lambda \mu `$ allows us to define $`\lambda ^{}=\lambda \backslash \phi `$. We define dually $`{}_{}{}^{}\nu =\phi /\nu `$.

###### Proposition 27.

If $`xX`$ and $`yY`$ are closed, then

(31a) $`z\backslash x`$ $`={}_{}{}^{}xz^{},zX,`$
(31b) $`y/t`$ $`={}_{}{}^{}ty^{},tY.`$
###### Proof.

For all $`xX`$ and $`\nu Z`$, consider the maps $`L_x^X:𝒦X,\mu x\mu `$ and $`L_\nu ^Z:𝒦Z`$, $`\mu \nu \mu `$. We have $`𝖫_yL_x^X(\lambda )=yx\lambda =yx\lambda `$, for all $`\lambda 𝒦`$, that is:

$$𝖫_yL_x^X=L_{yx}^Z,yY,xX.$$

Now, if $`x`$ is closed, we have $`x=y^{}`$ for some $`yY`$, i.e., $`x=𝖫_y^{\mathrm{}}(\phi )`$. Hence, $`z\backslash x=z\backslash y^{}=(L_z^X)^{\mathrm{}}𝖫_y^{\mathrm{}}(\phi )=(𝖫_yL_z^X)^{\mathrm{}}(\phi )=(L_{yz}^Z)^{\mathrm{}}(\phi )=yz^{}`$, which shows (31a). We have proved in passing the following identity, that we tabulate for further use:

(32)
$$yY,zX,z\backslash y^{}=yz^{}.$$

The proof of (31b) is dual. ∎

### 4.3. Reflexive Semirings

We say that a complete idempotent semiring $`𝒦`$ equipped with a distinguished element $`\phi `$ is left (resp. right) reflexive if $`{}_{}{}^{}(\lambda ^{})=\lambda `$ (resp. $`({}_{}{}^{}\lambda )^{}=\lambda `$), for all $`\lambda 𝒦`$, where the operations $`\lambda \lambda ^{}`$, $`\mu {}_{}{}^{}\mu `$ are defined as in (28), by considering $`𝒦`$ as a bisemimodule over itself, and taking the bracket $`\lambda \mu =\lambda \mu `$. (The element $`\phi `$ need not be unique; indeed, if $`𝒦`$ is left, or right, reflexive for $`\phi `$, and if $`\lambda `$ is invertible, it is not difficult to check that $`𝒦`$ is also left (or right) reflexive for $`\phi \lambda `$ and $`\lambda \phi `$. We shall sometimes write, more properly, that $`(𝒦,\phi )`$ is reflexive.)

Using (9a), together with $`\mu ^{}=\iota _{\mathrm{}}(\mu )`$ and $`{}_{}{}^{}\lambda =\iota _r(\lambda )=\iota _{\mathrm{}}^{}{}_{}{}^{\mathrm{}}(\lambda )`$, we get

$`\lambda \lambda ^{}\text{ is injective}`$ $`𝒦\text{ is left reflexive,}`$
(33a) $`\lambda {}_{}{}^{}\lambda \text{ is surjective,}`$
$`\lambda {}_{}{}^{}\lambda \text{ is injective,}`$ $`𝒦\text{ is right reflexive,}`$
(33b) $`\lambda \lambda ^{}\text{ is surjective.}`$
The interest in reflexive semirings stems in particular from the following result.

###### Proposition 28.

If $`𝒦`$ is right reflexive, then the set of closed elements $`\overline{X}`$ is a complete subsemimodule of $`X^{\mathrm{op}}`$.

###### Proof.

We know from Proposition 25 that $`\overline{X}`$ is stable by arbitrary sups for $`\stackrel{\mathrm{op}}{}`$. It remains to check that for all $`x\overline{X}`$ and $`\lambda 𝒦`$, $`\lambda \stackrel{\mathrm{op}}{}x=x/\lambda \overline{X}`$. By definition of $`\overline{X}`$, we have $`x=y^{}=𝖫_y^{\mathrm{}}(\phi )`$ for some $`yY`$. Using (8c) and the right linearity of $``$, we get $`𝖫_yR_\lambda ^X=R_\lambda ^𝒦𝖫_y(R_\lambda ^X)^{\mathrm{}}𝖫_y^{\mathrm{}}=𝖫_y^{\mathrm{}}(R_\lambda ^𝒦)^{\mathrm{}}`$, hence $`x/\lambda =(R_\lambda ^X)^{\mathrm{}}𝖫_y^{\mathrm{}}(\phi )=𝖫_y^{\mathrm{}}(R_\lambda ^𝒦)^{\mathrm{}}(\phi )=𝖫_y^{\mathrm{}}(\phi /\lambda )=𝖫_y^{\mathrm{}}(\mu \backslash \phi )`$ for some $`\mu 𝒦`$, since, by (33b), $`\mu \mu ^{}=\mu \backslash \phi `$ is surjective. Using (8c) again, $`x/\lambda =𝖫_y^{\mathrm{}}(L_\mu ^𝒦)^{\mathrm{}}(\phi )=(L_\mu ^𝒦𝖫_y)^{\mathrm{}}(\phi )=𝖫_{\mu y}^{\mathrm{}}(\phi )=(\mu y)^{}`$, which shows that $`x/\lambda \overline{X}`$. ∎

###### Example 29.

Let us consider once again the dual pair $`(𝒦^I,𝒦^I)`$ of Examples 22123. Since $`{}_{}{}^{}d(i)=\phi /d(i)`$, and since $`a^{}(i)=a(i)\backslash \phi `$, we see that all the elements of the right (resp. left) semimodule $`𝒦^I`$ are closed as soon as $`𝒦`$ is right (resp. left) reflexive.

We next exhibit a fundamental class of reflexive idempotent semirings. We say that a (non necessarily commutative) semiring is a semifield if its non-zero elements have a multiplicative inverse. A complete idempotent semiring $`𝒦`$ is never a semifield (unless $`𝒦=\{\epsilon ,e\}`$), because the maximal element of $`𝒦`$, $`𝒦`$, satisfies $`(𝒦)^2=𝒦`$. For this reason, we shall call (in a slightly abusive way) complete semifield a complete semiring $`𝒦`$ such that all elements except $`\epsilon `$ and $`𝒦`$ have a multiplicative inverse. For instance, $`\overline{}_{\mathrm{max}}=(\{\pm \mathrm{}\},\mathrm{max},+)`$ is a complete semifield.

###### Proposition 30.

A complete idempotent semifield $`𝒦`$ is reflexive: if $`𝒦=\{\epsilon ,e\}`$, one must take $`\phi =\epsilon `$, otherwise, one may take any invertible $`\phi `$.

###### Proof.

This follows readily from $`{}_{}{}^{}x=\phi x^1`$, $`x^{}=x^1\phi `$, for $`x\{\epsilon ,𝒦\}`$, $`{}_{}{}^{}\epsilon =\epsilon ^{}=𝒦`$, $`{}_{}{}^{}(𝒦)=(𝒦)^{}=\epsilon `$. ∎

If $`G`$ is a group, we denote by $`𝒦[[G]]`$ the complete group $`𝒦`$-semialgebra over $`G`$, i.e. the free complete $`𝒦`$-semimodule $`𝒦^G`$, whose elements are denoted as formal sums $`_{gG}s_gg`$ where $`\{s_g\}_{gG}`$ is a family of elements of $`𝒦`$, equipped with the Cauchy product

$$(st)_u=\underset{\genfrac{}{}{0pt}{}{gh=u}{g,hG}}{}s_gt_h.$$

If $`\phi `$ is an element of $`𝒦`$, we denote by $`\phi _{𝒦[[G]]}`$ the element of $`𝒦[[G]]`$ whose coefficients all are equal to $`𝒦`$, except the coefficient of the unit, which is equal to $`\phi _𝒦`$. We also denote by $`\phi _{nn}𝒦^{n\times n}`$ the matrix whose diagonal entries are equal to $`\phi `$ and whose out-diagonal entries are equal to $`𝒦`$.

The abundance of reflexive semirings is shown by the following immediate property.

###### Proposition 31 (Transfer Property).

Let $`G`$ denote a group. If $`(𝒦,\phi )`$ is a left (or right) reflexive complete idempotent semiring, then so are $`(𝒦^{n\times n},\phi _{nn})`$ and $`(𝒦[[G]],\phi _{𝒦[[G]]})`$.∎

###### Proposition 32.

If $`𝒦`$ is reflexive and if $`(Y,X)`$ form a predual pair for which $`Y`$ separates $`X`$, then, all the elements of $`X`$ are closed.

###### Proof.

Since $`𝒦`$ is right reflexive, $`\overline{X}=\{y^{}yY\}`$ is a complete subsemimodule of $`X^{\mathrm{op}}`$ (Proposition 28), hence, applying the Dual Separation Theorem (Eqn (24a)) to $`V=\overline{X}X^{\mathrm{op}}`$ and to an arbitrary $`xX^{\mathrm{op}}`$, we get, $`yY,P_{\overline{X}}^{\mathrm{op}}(x)\backslash y^{}=x\backslash y^{},`$ and, using (32),

(34) $`yY,yP_{\overline{X}}^{\mathrm{op}}(x)^{}=yx^{}.`$
Since $`𝒦`$ is left reflexive, by (33a), $`\lambda \lambda ^{}`$ is injective, and, using (34), we get $`yY,yP_{\overline{X}}^{\mathrm{op}}(x)=yx`$. Since $`Y`$ separates $`X`$, $`P_{\overline{X}}^{\mathrm{op}}(x)=x`$, which shows that $`x\overline{X}`$. Thus, $`X=\overline{X}`$. ∎

Gathering Proposition 26 and Proposition 32 together with the symmetric result to Proposition 32, we get:

###### Corollary 33.

If $`(Y,X)`$ is a dual pair for a reflexive semiring $`𝒦`$, then the map $`x{}_{}{}^{}x`$, together with its inverse $`yy^{}`$, are anti-isomorphisms of lattices between $`X`$ and $`Y`$.

###### Theorem 34 (Hahn-Banach Theorem, Geometric Form).

Let $`(Y,X)`$ denote a predual pair for a left reflexive semiring $`𝒦`$. If $`VX`$ is a complete subsemimodule whose elements are all closed, and if $`x`$ is closed, then,

(35a) $`{}_{}{}^{}P_{V}^{}(x)v={}_{}{}^{}xv,`$ $`vV,`$
and
(35b) $`{}_{}{}^{}P_{V}^{}(x)x={}_{}{}^{}xx`$ $`xV.`$
###### Proof.

Using (31a), we rewrite the universal separation property (Eqn 21) as:

(36a) $`vV,`$ $`{}_{}{}^{}P_{V}^{}(x)v^{}={}_{}{}^{}xv^{},`$
and
(36b) $`xV`$ $`{}_{}{}^{}P_{V}^{}(x)x^{}={}_{}{}^{}xx^{}.`$
Since $`𝒦`$ is left reflexive, as noted in (33a), $`\lambda \lambda ^{}`$ is injective, hence, (36) implies (35). ∎

A weaker statement, which is easier to remember, is the following.

###### Corollary 35.

If $`(Y,X)`$ is a predual pair for a reflexive complete semiring $`𝒦`$ such that $`Y`$ separates $`X`$, if $`V`$ is a complete subsemimodule of $`X`$, and if $`xX`$, then, the Hahn-Banach type property (35) holds.∎

### 4.4. Representation of Linear Forms

We now study the dual pair $`(X^{},X)`$. The following result characterizes the linear form $`{}_{}{}^{}x`$.

###### Theorem 36.

Let $`𝒦`$ be a complete idempotent reflexive semiring, let $`X`$ be a complete $`𝒦`$ semimodule, and consider the dual pair $`(X^{},X)`$ equipped with its canonical bracket. Then,

$${}_{}{}^{}x(y)=\phi /(y\backslash x),x,yX.$$

###### Proof.

If $`fX^{}`$ is such that $`f(x)\phi `$, we get from $`xy(y\backslash x)`$ that $`\phi f(x)f(y)(y\backslash x)`$, hence $`f(y)\phi /(y\backslash x)`$, for all $`yX`$. Thus, $`{}_{}{}^{}x(y)\phi /(y\backslash x)`$. To show that the equality holds, it suffices to show that the map $`g:X𝒦`$, $`y\phi /(y\backslash x)`$ is linear continuous and satisfies $`g(x)\phi `$. Since $`g(x)=\phi /(x\backslash x)\phi /e=\phi `$, the latter condition is satisfied. If $`𝒦`$ is reflexive, the map $`𝒦𝒦,\lambda \phi /\lambda `$, which is an anti-isomorphism of lattices, sends arbitrary infs to arbitrary sups, and conversely:

(37a) $`\phi /(\mathrm{\Lambda })`$ $`=(\phi /\mathrm{\Lambda }),\mathrm{\Lambda }𝒦,`$
(37b) $`\phi /(\mathrm{\Lambda })`$ $`=(\phi /\mathrm{\Lambda }),\mathrm{\Lambda }𝒦,`$
(the residuation equality (37b) holds even if the complete idempotent semiring $`𝒦`$ is not reflexive). Using (37a) and (15h), we get that for all $`VX`$,

$$\phi /((V)\backslash x)=\phi /((V\backslash x))=(\phi /(V\backslash x)),$$

which shows that $`g`$ preserves arbitrary sups. It remains to show that $`g(y\lambda )=g(y)\lambda `$, for all $`yX`$, $`\lambda 𝒦`$. Since

$$g(y\lambda )=\phi /((y\lambda )\backslash x)=\phi /(\lambda \backslash (y\backslash x)),$$

it suffices to show that $`\phi /(\lambda \backslash \alpha )=(\phi /\alpha )\lambda `$ holds for all $`\alpha 𝒦`$. Since $`𝒦`$ is reflexive, we can write $`\alpha =\beta \backslash \phi `$, with $`\beta =\phi /\alpha `$, hence, $`\phi /(\lambda \backslash \alpha )=\phi /(\lambda \backslash (\beta \backslash \phi ))=\phi /((\beta \lambda )\backslash \phi )=\beta \lambda =(\phi /\alpha )\lambda `$. ∎

###### Corollary 37 ($`X^{}`$ separates $`X`$).

If $`𝒦`$ is a complete idempotent reflexive semiring and if $`X`$ is a complete $`𝒦`$ semimodule, then $`X^{}`$ separates $`X`$.

###### Proof.

Let $`x,yX`$. If $`f(x)=f(y)`$ for all $`fX^{}`$, we have in particular, $`{}_{}{}^{}x(x)={}_{}{}^{}x(y)`$. Since $`\lambda \phi /\lambda ,𝒦𝒦`$ is injective, we get $`x\backslash x=y\backslash x`$, hence $`xy(y\backslash x)=y(x\backslash x)y`$, which shows that $`xy`$. By symmetry, $`yx`$. ∎

###### Example 38.

The following counterexample shows that, when $`𝒦`$ is not reflexive, $`X^{}`$ need not separate $`X`$.

Consider the semiring $`\overline{}_{\mathrm{max}}=\{\{\mathrm{},+\mathrm{}\},\mathrm{max},+,0,\mathrm{}\}`$ which is complete. $`X=\{\{\mathrm{},+\mathrm{}\},\mathrm{max}\}`$ is a complete $`\overline{}_{\mathrm{max}}`$-semimodule for the action $`(x,\lambda )x+\lambda `$ (with the convention $`\mathrm{}+\mathrm{}=\mathrm{}`$). Let us prove that $`X^{}`$, the set of $`\overline{}_{\mathrm{max}}`$-linear maps from $`X`$ to $`\overline{}_{\mathrm{max}}`$, consists only of the two following elements :

1. $`xX\mathrm{}`$ ;
2. $`xXx+\mathrm{}`$ .

Let $`\varphi X^{}`$ a linear map and let us assume that it takes only finite values on $``$. Then, for all $`p`$,

$$\varphi (p)=\varphi (pn)+nn,n,$$

therefore $`\varphi (p)n=+\mathrm{}`$ which is a contradiction.

Let us assume that there exists $`p`$ such that $`\varphi (p)=\mathrm{}`$. By monotony of $`\varphi `$, $`\varphi (q)=\mathrm{}`$ for all $`qp`$. Moreover $`\varphi (p+n)=\varphi (p)+n=\mathrm{}`$, for $`n\{+\mathrm{}\}`$, which implies $`\varphi (x)=\mathrm{}`$ for all $`x`$.

Let us assume that there exists $`p`$ such that $`\varphi (p)=+\mathrm{}`$. By monotony of $`\varphi `$, $`\varphi (q)=+\mathrm{}`$ for all $`qp`$. Moreover $`\varphi (p)=\varphi (pn)+n=+\mathrm{}`$, for $`n`$, which shows that $`\varphi (x)=+\mathrm{}`$ for all $`x`$, and $`\varphi (\mathrm{})=\mathrm{}`$, since $`\varphi `$ is linear, so that $`\varphi (x)=x+\mathrm{}`$ for all $`x\overline{}_{\mathrm{max}}.`$

Thus, any linear form on $`X`$ is constant on the set of finite elements of $`X`$, which shows that $`X^{}`$ does not separate $`X`$.

Since $`X^{}`$ separates $`X`$ and $`X`$ separates $`X^{}`$, we get as an immediate corollary of Theorem 36, and Corollary 33, the following Riesz representation theorem, which extends (?, Theorem 5.2).

###### Corollary 39 (Riesz Representation Theorem).

Let $`𝒦`$ denote a complete idempotent reflexive semiring, and $`X`$ a complete $`𝒦`$-semimodule. Then, any continuous linear form $`fX^{}`$ can be represented as

(38)
$$f(y)={}_{}{}^{}x(y)=\phi /(y\backslash x),yX,$$

for some $`xX`$, and the unique $`xX`$ which satisfies (38) is equal to $`f^{}`$.

We get as a last, immediate corollary, the following extension of (?, Theorem 5.3).

###### Corollary 40 (Hahn-Banach Theorem, Analytic Form).

If $`𝒦`$ is a complete idempotent reflexive semiring, and if $`V`$ is a complete subsemimodule of a complete $`𝒦`$-semimodule $`X`$, then any continuous linear form defined on $`V`$ has a continuous extension to $`X`$.

###### Example 41 (Complete Semilattices).

A complete sup-semilattice $`(X,)`$ can be thought of as a complete semimodule over the Boolean semiring $`𝔹=\{\epsilon ,e\}`$, with addition $`(x,y)\{x,y\}`$ and action $`xe=x`$ and $`x\epsilon =X`$. The dual $`X^{}`$ is the set of maps $`x^{}:X\{\epsilon ,e\}`$ which preserve arbitrary sups. Let us take $`\phi =\epsilon `$, together with the bracket $`x^{}x=x^{}(x)`$ (as noted in Proposition 30, the Boolean semiring has the exceptional feature of being reflexive for $`\phi =\epsilon `$). For any $`aX`$, we have $`{}_{}{}^{}a=\{x^{}X^{}x^{}(a)=\epsilon \}`$, and it is not difficult to see that $`{}_{}{}^{}a(x)=\epsilon `$ if $`xa`$, and $`{}_{}{}^{}a(x)=e`$, otherwise. By Corollary 37, $`X^{}`$ separates $`X`$ and, by Corollary 33, $`x{}_{}{}^{}x`$ establishes an anti-isomorphism between the lattices $`X`$ and $`X^{}`$. An equivalent property was already noticed by ? (?).

### 4.5. Application: Duality between Row and Column Spaces

Let $`𝒦`$ denote a complete reflexive semiring, and let $`A𝒦^{n\times p}`$. The free complete semimodules $`X=𝒦^{p\times 1}`$ and $`Y=𝒦^{1\times n}`$ form a predual pair for the bracket $`yx=yAx`$. We have $`y^{}=\{xyAx\phi \}=(yA)\backslash \phi `$, and dually , $`{}_{}{}^{}x=\phi /(Ax)`$. Hence,

(39a) $`\overline{X}`$ $`=\{(yA)\backslash \phi yY\},`$
(39b) $`\overline{Y}`$ $`=\{\phi /(Ax)xX\}.`$
Let $`(A)=\{yAyY\}`$ denote the row space of $`A`$, i.e., the left $`𝒦`$-subsemimodule of $`𝒦^{1\times p}`$ generated by the rows of $`A`$, and, dually, let $`𝒞(A)=\{AxxX\}`$ denote the column space of $`A`$. Since $`𝒦`$ is reflexive, the maps $`zz\backslash \phi =(z_i\backslash \phi )_{1ip}`$ and $`z\phi /z=(\phi /z_i)_{1ip}`$ are mutually inverse antitone bijections between $`𝒦^{1\times p}`$ and $`𝒦^{p\times 1}=X`$. By (39a), $`zz\backslash \phi `$ sends $`(A)`$ to $`\overline{X}`$, hence, $`(A)`$ and $`\overline{X}`$ are anti-isomorphic lattices. Dually, $`𝒞(A)`$ and $`\overline{Y}`$ are anti-isomorphic lattices. By Proposition 26, $`\overline{X}`$ and $`\overline{Y}`$ are anti-isomorphic lattices. Composing anti-isomorphisms, we see that the map:

$$(A)𝒞(A),z\left[\phi /\left(A(z\backslash \phi )\right)\right]\backslash \phi =A(z\backslash \phi )$$

is an anti-isomorphism of lattices. We have proved the following result, which extends a theorem of Markowsky (see (?, Theorem 1.2.3)) for Boolean matrices.

###### Theorem 42.

The row space and column space of a matrix with entries in a complete idempotent reflexive semiring are anti-isomorphic lattices.∎


format: text

text:
# Comment on ”First-principles calculation of the superconducting transition in MgB2 within the anisotropic Eliashberg formalism”

## Abstract

Choi et al. \[Phys. Rev. B 66, 020513 (2002)\] recently presented first principles calculations of the electron-phonon coupling and superconductivity in MgB2, emphasizing the importance of anisotropy and anharmonicity. We point out that (1) variation of the superconducting gap inside the $`\sigma `$\- or the $`\pi `$-bands can hardly be observed in real samples, and (2) taking the anisotropy of the Coulomb repulsion into account influences the size of the small gap, $`\mathrm{\Delta }_\pi .`$

In a recent paper Louie , as well as in a follow-up paper Choi , Choi et al. presented an ab initio calculation of the superconducting transition and superconducting properties of MgB2. The important improvement over existing calculations was that they allowed the order parameter to vary freely over the Fermi surface, i.e. $`\mathrm{\Delta }=\mathrm{\Delta }\left(𝐤\right)`$, and at the same time took the anharmonicity into account. As a consequence, they had to compute the fully anisotropic electron-phonon interaction, $`\lambda (𝐤,𝐤^{})`$, and to solve the corresponding Eliashberg equation. The Coulomb pseudopotential, $`\mu ^{}(𝐤,𝐤^{})`$, was assumed not to depend on $`𝐤`$ and $`𝐤^{}`$, and was treated as an adjustable parameter. First-generation ab initio calculations of the superconducting transition and superconducting properties of MgB2 had assumed $`\mathrm{\Delta }`$ to be constant and had therefore solved merely the isotropic Eliashberg equation Kong . Moreover, anharmonicity had been neglected. It was soon pointed out Amy  that the calculated electron-phonon coupling suggests that the gap on the two $`\pi `$ sheets of the Fermi surface is smaller than that on the two $`\sigma `$ sheets, and that anharmonicity is important. This led to the so-called two-band model. Ab initio calculations of the second generation Amy ; GolubovJPCM ; Brinkman  allowed for two, and sometimes four gaps, $`\mathrm{\Delta }_n,`$ and thus had to compute $`\lambda _{nn^{}}`$ , to estimate the anisotropy of $`\mu _{nn^{}}^{},`$ and to solve the corresponding Eliashberg equations.

Here we shall comment on (1) whether consequences of anisotropy beyond that of the two-band model may be observed and (2) whether at this level of detail Choi et al.’s assumption of a uniform Coulomb repulsion is warranted.

1. Ref. Louie,  implies that there is a distribution of gaps *within* the $`\sigma `$ and the $`\pi `$-sheets, not only in the calculations for perfectly clean MgB2, but also in the actual material; in other words, that the distribution of gaps shown in Fig. 2 of Ref. Choi,  is *observable.* However, in the theory of anisotropic superconductivity it is known that any intraband nonuniformity of the order parameter is suppressed by strong intraband impurity scattering. It is not immediately obvious, though, when scattering should be considered strong in this connection. Since excitation gaps are not equal to the order parameters any more, one needs to compare individual densities of states (DOS), $`N(E)`$, for the two $`\sigma `$-bands (or the two $`\pi `$-bands) with each other for a given scattering strength, and check whether $`|N_{\sigma 1}N_{\sigma 2}||N_{\sigma 1}+N_{\sigma 2}|`$. The relevant expression can be found in Ref. Golubov, . In the limit of large scattering rates, $`\gamma `$, one can derive an analytical expression for this criterion, namely $`\gamma >\sqrt{\mathrm{\Delta }\delta \mathrm{\Delta }}`$ (Ref. gaps, ), where $`\mathrm{\Delta }`$ is the average order parameter, and $`\delta \mathrm{\Delta }`$ is the variation of the order parameter over the Fermi surface in question. With the data from Refs. Louie, ; Choi,  for $`\mathrm{\Delta }`$ and $`\delta \mathrm{\Delta }`$, this gives characteristic scattering rates of respectively 2 and 1.5 meV for the $`\sigma `$ and $`\pi `$-bands. Therefore, to observe 4 distinct gaps in MgB2 one needs samples with scattering rates smaller than 2 meV, that is, with mean free paths beyond 1500 Å. To observe gap variations beyond the 4-band model, far cleaner samples are needed. This is the reason why at most two distinct gaps have been observed in experiments. It is even surprising that the difference of 5 meV between the gaps of the $`\sigma `$ and the $`\pi `$-bands is not smeared out. This seems to be due to the inability of common impurities to couple between the disparate $`\sigma `$ and $`\pi `$-band wavefunctionsMazin , so that $`\gamma _{\sigma \pi }\gamma _{\sigma \sigma }\gamma _{\pi \pi }`$.

2. For the Coulomb pseudopotential, Choi et al. used $`\mu ^{}(𝐤,𝐤^{})=\mu ^{}(\omega _c)=0.12`$ (with the cut-off frequency $`\omega _c5\omega _{ph}^{\mathrm{max}})`$ and stated that the superconducting properties of MgB2 were not very sensitive to the choice of $`\mu ^{}(\omega _c).`$ This at first seems plausible, because the Coulomb pseudopotential enters the Eliashberg equation only in the combination $`\lambda (𝐤,𝐤^{},\nu \nu ^{})\mu ^{}(𝐤,𝐤^{}),`$ and the $`\lambda `$-distribution varies on the scale of $``$1.8, $``$0.3, and $``$0.2 for $`\sigma \sigma `$-, $`\pi \pi `$-, and $`\sigma \pi `$-scattering respectively \[see Fig. 3 of Ref. Louie, \]. Therefore, at most the $`\sigma \pi `$-scattering can be influenced by anisotropy of $`\mu ^{}`$. We shall argue that the $`\sigma \pi `$-interband Coulomb matrix elements *are* considerably smaller than the intraband matrix elements due to the very small overlap of the $`\sigma `$\- and $`\pi `$-band charge densitiesGolubovJPCM  and that this is sufficient to influence the superconducting properties, in particular the size of the small gap, $`\mathrm{\Delta }_\pi `$.

Choi et al. do not give the band-integrated values of their coupling constants, but by integrating Fig. 3 of Ref. Louie,  with the DOS-ratio $`N_\pi /N_\sigma =1.37`$ according to:

$`\lambda _{nn^{}}(0)`$ $``$ $`{\displaystyle \frac{1}{N}}{\displaystyle \underset{𝐤,𝐤^{}}{}}{\displaystyle \frac{\delta (\epsilon _{n𝐤})}{N_n}}\lambda (𝐤,𝐤^{},0)\delta (\epsilon _{n^{}𝐤^{}})`$
$`=`$ $`{\displaystyle \frac{1}{N}}{\displaystyle \underset{𝐤,𝐤^{}}{}}W_{n𝐤}\lambda (𝐤,𝐤^{},0)W_{n^{}𝐤^{}}N_n^{}`$
for the phonon-mediated coupling of an electron in band $`n`$ to all electrons in band $`n^{},`$ we can map Choi *et al.*’s fully anisotropic model onto a two-gap model with $`\lambda _{\sigma \sigma }=0.78,\lambda _{\sigma \pi }=0.15,\lambda _{\pi \sigma }=0.11,`$ and $`\lambda _{\pi \pi }=0.21.`$ These $`\lambda `$-values yield the mass-renormalization parameters in Fig. 2 of Ref. Louie, : $`m^{}/m1=\lambda _\sigma =\lambda _{\sigma \pi }+\lambda _{\sigma \sigma }0.94`$ and $`\lambda _\pi =\lambda _{\pi \sigma }+\lambda _{\pi \pi }0.32.`$ The total isotropic (thermodynamic) $`\lambda =(N_\sigma \lambda _\sigma +N_\pi \lambda _\pi )/N=0.61`$, which of course is the same as the one given by Choi *et al.* Here, and in Eq. Comment on ”First-principles calculation of the superconducting transition in MgB2 within the anisotropic Eliashberg formalism”, $`N`$ is the DOS summed over all bands. With this two-gap model we have performed strong-coupling Eliashberg calculations in order to compare the results for $`T_c`$ and the gaps with those resulting from the fully anisotropic treatment. For all four spectral functions we used the isotropic $`\alpha ^2F(\omega )`$ from Fig. 1 of Ref. Louie,  scaled to produce the $`\lambda `$-matrix given above. The $`\mu ^{}(\omega _c)`$-matrix is obtained from Eq. Comment on ”First-principles calculation of the superconducting transition in MgB2 within the anisotropic Eliashberg formalism” with $`\lambda (𝐤,𝐤^{},0)`$ substituted by Choi *et al.*’s $`\mu ^{}(\omega _c)`$. The resulting $`T_c`$ and the gaps are shown by dashed lines in Fig. 1 as functions of $`\mu ^{}(\omega _c)`$. At $`\mu ^{}(\omega _c)=0.12,`$ as used by Choi *et al.*, we get $`T_c=43`$ K, $`\mathrm{\Delta }_\sigma =7.2`$ meV, and $`\mathrm{\Delta }_\pi =1.3`$ meV. The corresponding values quoted by Choi *et al.* are 39 K, 6.8 meV and 1.8 meV. These differences are hardly due to intraband anisotropy, first of all because it can only increase $`T_c`$. Secondly, increasing the number of gaps from two to four in the Eliashberg equations, which should account for most of the anisotropy beyond the two gap model, we found rather small changesNote .

If, on the other extreme, we assume that there is no Coulomb repulsion between the $`\sigma `$ and $`\pi `$-electrons, then the corresponding two-gap treatment gives the full lines in Fig. 1 and, hence, $`T_c=38`$ K, $`\mathrm{\Delta }_\sigma =6.5`$ meV, and $`\mathrm{\Delta }_\pi =1.8`$ meV for $`\mu ^{}(\omega _c)=0.12`$, incidentally, rather close to the values quoted in Refs. Louie, ; Choi, . If the magnitude of $`\mu ^{}`$ in both calculations shown in Fig. 1 is adjusted to produce the same $`T_c`$ of 39 K, the value of the lower gap changes from $``$ 2 eV (diagonal) to $``$ 0.4 eV (uniform).

That uniform and diagonal Coulomb pseudopotentials yield different results is not surprising: The same total Eliashberg $`\mu ^{}`$ in the uniform case is distributed over intra- and interband terms so that the $`\sigma \sigma `$-part of the pairing interaction suffers less than in the case of a diagonal $`\mu ^{}`$. $`\lambda _{\sigma \sigma }`$ is more important for the critical temperature, and $`\lambda _{\sigma \pi }`$ for generating $`\mathrm{\Delta }_\pi `$. For uniform $`\mu ^{}`$, therefore, the $`T_c`$ and $`\mathrm{\Delta }_\sigma `$ are larger, and $`\mathrm{\Delta }_\pi `$ is much smaller.

Having demonstrated that the assumed structure of $`\mu ^{}`$ matters for the details of the superconducting properties of MgB2 Note2 , the size of $`\mathrm{\Delta }_\pi `$ in particular, let us finally estimate this structure from first principles. The unrenormalized $`\mu `$ is the matrix element $`n𝐤,n𝐤|V_C|n^{}𝐤^{},n^{}𝐤^{}`$ for scattering a Cooper pair from state $`|n^{}𝐤^{}`$ to state $`|n𝐤`$ via a phonon with wave-vector $`𝐤𝐤^{}.`$ Inserting this matrix element in Eq. Comment on ”First-principles calculation of the superconducting transition in MgB2 within the anisotropic Eliashberg formalism” instead of $`\lambda (𝐤,𝐤^{},0)`$ yields $`\mu _{nn^{}}.`$ Here $`V_C(𝐫,𝐫^{})`$ is the screened Coulomb interaction between the electrons, and since it has short range in good metals, it makes sense to take it proportional to the delta-function $`\delta (𝐫𝐫^{}).`$ This leads to the following estimate:

$`\mu `$ $``$ $`N{\displaystyle \left|\psi _{n𝐤}(𝐫)\right|^2\left|\psi _{n^{}𝐤^{}}(𝐫)\right|^2d^3r}`$
$`\mu _{nn^{}}`$ $``$ $`N_n^{}{\displaystyle \left|\psi (𝐫)\right|_n^2\left|\psi (𝐫)\right|_n^{}^2d^3r},`$ (2)
where $`\left|\psi (𝐫)\right|_n^2_𝐤\left|\psi _{n𝐤}(𝐫)\right|^2\delta (\epsilon _{n𝐤})/N_n`$ is the shape, normalized to 1 in the cell or the crystal, of the electron density of band $`n`$ at the Fermi level. These $`\sigma `$ and $`\pi `$ densities are shown in Fig.2, and they yield for the ratios of the integrals in Eq.2

$$\left|\psi \right|_\sigma ^4:\left|\psi \right|_\pi ^4:\left|\psi \right|_\sigma ^2\left|\psi \right|_\pi ^23.0:1.8:1.$$
(3)
These ratios reflect the facts that the $`\sigma `$-density is more compact than the $`\pi `$-density, and that the overlap of these two densities is small. Note that the exceptional smallness of the interband impurity scattering Mazin  in MgB2 is due not only to this difference in charge density, but also to a disparity of the $`\sigma `$ and $`\pi `$ wave functions.

From Eqs. 2, 3 we get: $`\mu _{\sigma \sigma }`$:$`\mu _{\pi \pi }`$:$`\mu _{\sigma \pi }`$:$`\mu _{\pi \sigma }`$=3.1:2.6:1.4:1. Now, any anisotropy in the bare pseudopotential is further *enhanced* in the renormalized $`\mu ^{}`$: In the one-band case $`\mu `$ is renormalized as $`\mu ^{}(\omega _c)=\mu /\left[1+\mu \mathrm{ln}(W/\omega _c)\right]`$, where $`W`$ is a characteristic electronic energy of the order of the bandwidth or plasma frequency. For the multi-band case, this is a matrix equation with $`W`$ being a diagonal matrix with elements $`W_n`$. Assuming for simplicity that $`\mu _{\sigma \sigma }=\mu _{\pi \pi }=A\mu _{\sigma \pi }`$ with $`A>1`$, and that $`\mu _{\sigma \sigma }\mathrm{log}(W_\sigma /\omega _c)=\mu _{\pi \pi }\mathrm{log}(W_\pi /\omega _c)=L,`$ one obtains: $`A^{}=A+(AA^1)L`$. For MgB$`_2,`$ $`L0.51`$ and $`A2.3,`$ so that $`A^{}34,`$ which is very different from the uniform $`\mu `$.

In conclusion: Any difference between the results of the fully anisotropic Eliashberg formalism and those of the two-gap formalism will hardly be observable in real MgB2-samples. On the other hand, the anisotropy of the Coulomb pseudopotential is likely to have an observable effect on the size of the small gap, $`\mathrm{\Delta }_\pi `$.

The authors thank W.E. Pickett for numerous helpful discussions, and for critical reading of the manuscript.