26
$\begingroup$

Here is a concrete, if seemingly unmotivated, aspect of the question I am interested in:

Question 1. Let $a$ and $b$ be two elements of a (noncommutative) semiring $R$ such that $1+a^3$ and $1+b^3$ and $\left(1+b\right)\left(1+a\right)$ are invertible. Does it follow that $1+a$ and $1+b$ are invertible as well?

The answer to this question is

  • "yes" if $ab=ba$ (because in this case, $1+a$ is a left and right divisor of the invertible element $\left(1+b\right)\left(1+a\right)$, and thus must itself be invertible; likewise for $1+b$).

  • "yes" if $R$ is a ring (because in this case, $1+a$ is a left and right divisor of the invertible element $1+a^3 = \left(1+a\right)\left(1-a+a^2\right) = \left(1-a+a^2\right)\left(1+a\right)$, and thus must itself be invertible; likewise for $1+b$).

  • "yes" if $1+a$ is right-cancellable (because in this case, we can cancel $1+a$ from $\left(1+a\right) \left(\left(1+b\right)\left(1+a\right)\right)^{-1} \left(\left(1+b\right)\left(1+a\right)\right) = 1+a$ to obtain $\left(1+a\right) \left(\left(1+b\right)\left(1+a\right)\right)^{-1} \left(1+b\right) = 1$, which shows that $1+a$ is invertible), and likewise if $1+b$ is left-cancellable.

I am struggling to find semirings that are sufficiently perverse to satisfy none of these cases and yet have $\left(1+b\right)\left(1+a\right)$ invertible. (It is easy to find cases where $1+a^3$ is invertible but $1+a$ is not; e.g., take $a = \begin{pmatrix} 0&1\\ 0&0 \end{pmatrix}$ in the matrix semiring $\mathbb{N}^{2\times 2}$.)

The real question I'm trying to answer is the following (some hopefully reasonably clear handwaving included):

Question 2. Assume we are given an identity that involves only positive integers, addition, multiplication and taking reciprocals. For example, the identity can be $\left(a^{-1} + b^{-1}\right)^{-1} = a \left(a+b\right)^{-1} b$ or the positive Woodbury identity $\left(a+ucv\right)^{-1} + a^{-1}u \left(c^{-1} + va^{-1}u\right)^{-1} va^{-1} = a^{-1}$. Assume that this identity always holds when the variables are specialized to arbitrary elements of an arbitrary ring, assuming that all reciprocals appearing in it are well-defined. Is it then true that this identity also holds when the variables are specialized to arbitrary elements of an arbitrary semiring, assuming that all reciprocals appearing in it are well-defined?

There is a natural case for "yes": After all, the same claim holds for commutative semirings, because in this case, it is possible to get rid of all reciprocals in the identity by bringing all fractions to a common denominator and then cross-multiplying with these denominators. However, this strategy doesn't work for noncommutative semirings (and even simple-looking equalities of the form $ab^{-1} = cd^{-1}$ cannot be brought to a reciprocal-free form, if I am not mistaken). Question 1 is the instance of Question 2 for the identity \begin{align} \left(1+a^3\right)^{-1} \left(1+b^3\right)^{-1} \left(1+a\right) \left(\left(1+b\right)\left(1+a\right)\right)^{-1} \left(1+b\right) = \left(1+a^3\right)^{-1} \left(1+b^3\right)^{-1} \end{align} (where, of course, the only purpose of the $\left(1+a^3\right)^{-1} \left(1+b^3\right)^{-1}$ factors is to require the invertibility of $1+a^3$ and $1+b^3$). Indeed, if $\alpha$ and $\beta$ are two elements of a monoid such that $\beta\alpha$ is invertible, then we have the chain of equivalences \begin{align} \left(\alpha\text{ is invertible} \right) \iff \left(\beta\text{ is invertible} \right) \iff \left( \alpha \left(\beta\alpha\right)^{-1} \beta = 1 \right) \end{align} (easy exercise).

$\endgroup$
12
  • 1
    $\begingroup$ If you have no inverses in your identity then since the free semiring embeds in the free ring you get any ring identity in the semiring signature is a semiring identity. I would guess what you would like for Q2 to prove if you add to the free semiring relations saying certain elements are units then this embeds in the free ring with the same relations adjoined but I have no idea if that is true. $\endgroup$ Jul 28, 2021 at 17:14
  • 1
    $\begingroup$ @BenjaminSteinberg: Yes, all my semirings have $1$; I don't know how I'd define reciprocals otherwise :) $\endgroup$ Jul 28, 2021 at 19:31
  • 3
    $\begingroup$ And yes, the claim is definitely true for identities with no reciprocals, even if I assume the existence of some reciprocals. So if there was a way to "clear the denominators" in an arbitrary identity, I would be done. $\endgroup$ Jul 28, 2021 at 19:33
  • 1
    $\begingroup$ @darijgrinberg The identity you were considering at the end of your post can be replaced by the simpler identity $(1+a^3)^{-1}(1+a)[c(1+a)]^{-1}c=(1+a^3)^{-1}$ (i.e. there is no need to assume that $c$ is the sum of two simpler pieces, since there is no need to include $(1+b^3)$). Thus, question #1 simplifies to: If $1+a^3$ and $c(1+a)$ are units in a semiring (for some $a,c$), is $1+a$ a unit? $\endgroup$ Jul 30, 2021 at 18:53
  • 2
    $\begingroup$ @PaceNielsen: Note also that we can replace "$c\left(1+a\right)$ is a unit" by "$d\left(1+a\right) = 1$" in your question. This might make it simpler to analyze. $\endgroup$ Jul 30, 2021 at 21:14

3 Answers 3

11
$\begingroup$

Tim Campion's idea works, though his example needs a little fixing. As in Tim's answer, we will find a rig with two elements $X$ and $Y$ such that $X+Y=1$ but $XY \neq YX$.

Let $(M,+,0)$ be any commutative monoid. Let $R$ be the set of endomorphisms of $M$ obeying $\phi(x+y)=\phi(x)+\phi(y)$ and $\phi(0)=0$. Then $R$ is a rig, with $(\alpha+\beta)(x) = \alpha(x) + \beta(x)$ and $(\alpha \beta)(x) = \alpha(\beta(x))$.

Let $M$ be $\{ 0,1,2 \}$ with $x+y \mathrel{:=} \max(x,y)$. Define \begin{gather*} \alpha(0) = 0,\ \alpha(1) = 0,\ \alpha(2) = 2 \\ \beta(0) = 0,\ \beta(1) = 1,\ \beta(2) = 1. \end{gather*} Then $\alpha+\beta=\mathrm{Id}$ but $\alpha \beta \neq \beta \alpha$.

$\endgroup$
6
  • 4
    $\begingroup$ For the benefit of people only looking at David's answer: $X+Y=1\Rightarrow XY=YX$ can also be expressed as the identity $(x(x+y)^{-1})(y(x+y)^{-1})=(y(x+y)^{-1})(x(x+y)^{-1})$, as Tim explained. $\endgroup$ Aug 8, 2021 at 12:57
  • $\begingroup$ Nice! That’s a good example $\endgroup$
    – Tim Campion
    Aug 8, 2021 at 14:33
  • 1
    $\begingroup$ Great job! I'm seeing the endomorphisms of $M$ are just the weakly increasing maps from $M$ to $M$. Interesting to see how much combinatorial structure fits into the basic concepts of semirings! $\endgroup$ Aug 8, 2021 at 16:04
  • 4
    $\begingroup$ @darijgrinberg (To be precise, an endomorphism of M is an order preserving map which also preserves the bottom element). I think it’s a pretty good rule of thumb that if you’re looking for a commutative monoid which behaves very differently from an abelian group, then join semilattices are a very good place to look. $\endgroup$
    – Tim Campion
    Aug 8, 2021 at 16:21
  • $\begingroup$ Wow. This endomorphism semiring (for any finite chain $M$) appeared as a counter-example in my (student,, and deservedly forgotten) paper link.springer.com/article/10.1007/s10958-006-0157-z, THis counter-example also showed that some subtraction-free corollaries in the ring case are not such in a semiring case (namely, if $1=bf+f^{n-1}a$ and $f^n=0$, then $af^ka=0$ for all $k\leq n-2$ in the ring case, but not in the semiring one). For $n=2$, this seems to hive almost the same example, as I see a posteriori... $\endgroup$ Oct 31, 2021 at 21:28
22
$\begingroup$

The answer to your first question is yes (which was very surprising to me, to be honest). I have no idea whether the second question also has a positive answer. (By the way, don't let the work below fool you. This took me an entire week of serious computations to discover the main idea.)

We will assume $(1+a^3)u=1$ and $d(1+a)=1$. We find that $$ d+au = d(1+(1+a)au) = d((1+a^3)u+(a+a^2)u)=d(1+a)(1+a^2)u=(1+a^2)u. $$ Thus, we compute $$ (1+a)d = d[1+(1+a)ad] = d[1+ad+a^2d] = d[u+a^3u+a^2d+ad] $$ $$ =d[a^2(d+au) + ad + u] = d[a^2(1+a^2)u+ad+u] = d[a(d+au)+a^4u+u] $$ $$ =d[a(1+a^2)u+(1+a^4)u] = d(1+a)(1+a^3)u=1. $$


Edited to add: A similar idea works for higher odd powers. The fifth power case is sufficient to give the main idea.

Assume $(1+a^5)u=1=d(1+a)$. We find $$ d+(a+a^3)u = d[(1+a^5)u + (1+a)(a+a^3)u] = d(1+a)(1+a^2+a^4)u=(1+a^2+a^4)u. $$ Then we compute $$ (1+a)d=d^3[(1+a)^2+(1+a)^3ad] = d^3[(1+a)^2(1+a^5)u + (a+3a^2+3a^3+a^4)d] = d^3[u+2au+a^2u+2a^6u + (a+3a^2+3a^3)d + a^4[(a+a^3)u+d]] = \cdots $$ and you keep reducing monomials with $d$ to monomials involving only $a$ and $u$.

$\endgroup$
6
  • $\begingroup$ Wow!! (It's probably worth saying that this answers the generalized Question 1 from the comments, not the original Question 1.) Do you think something like this could help if $1+a^3$ is replaced by $1+a^m$ for any odd $m>0$ ? $\endgroup$ Aug 6, 2021 at 22:27
  • $\begingroup$ Rather, it answers the original question 1 and the generalized question (and even a slightly more general question, since I only assumed $1+a^3$ was right invertible). I'll give the odd exponent question some thought. $\endgroup$ Aug 6, 2021 at 22:31
  • $\begingroup$ I meant that it doesn't directly refer to the notations from Question 1, for future readers of the thread. $\endgroup$ Aug 6, 2021 at 22:32
  • $\begingroup$ Aren't the notations the same? If $1+a^3$ is invertible then it is right invertible. Also, if $(1+b)(1+a)$ is invertible, then $(1+a)$ is left invertible. $\endgroup$ Aug 6, 2021 at 22:35
  • $\begingroup$ Oh, I see -- your answer does fit Question 1 pretty well indeed. $\endgroup$ Aug 6, 2021 at 22:42
9
$\begingroup$

The answer to the second question is no in general.

For instance, in an associative ring, the elements $x(x+y)^{-1}$ and $y(x+y)^{-1}$ necessarily commute — in other words, if $a + b = 1$, then $a$ and $b$ commute (since we have $b = 1-a$, so $ab = a(1-a) = a - a^2 = (1-a)a = ba$).

This need not be so in an an associative semiring. For instance, consider the join-semilattice $S$ of subsets of $\{x,y\}$ (so $S$ is a 4-element idempotent commutative monoid), and let $R$ be the semiring of $(\emptyset, \cup)$-preserving endomorphisms of $S$. Let $X \in R$ fix $x$ and carry $y$ to $\emptyset$; let $Y \in R$ fix $y$ and carry $x$ to $\emptyset$. Then $X + Y = 1$ but $X$ and $Y$ do not commute see David Speyer’s answer for a counterexample.

(One way of looking this is that we're asking whether every localization of a finitely-generated free noncommutative semiring $\mathbb N\{x_1,\dotsc, x_n\}(f(x_1,\dotsc,x_n)^{-1})$ injects into its group completion (i.e. is additively cancellative) — the above example shows that the the answer is no when we look at $\mathbb N\{x,y\}(x+y)^{-1}$.)

(By the way — I was initially trying to prove that the answer to (2) was yes. The localization $\mathbb N\{x,y\}(x+y)^{-1}$ was the first one I tried after monomial localizations. Since (2) already fails there, I suspect that the phenomenon is widespread, making the positive answer to (1) all the more surprising!)

$\endgroup$
2
  • 3
    $\begingroup$ Why do X and Y not commute in your join-semilattice example? $\endgroup$ Aug 8, 2021 at 7:41
  • $\begingroup$ Oof. Never post past bedtime. $\endgroup$
    – Tim Campion
    Aug 8, 2021 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.