Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: have you seen this operation before?

Matteo Capucci (he/him) (Nov 26 2024 at 16:14):

Have you ever seen the binary operation $a \odot b = a^{-\log b}$ before? It's a commutative monoid structure on $[0,\infty]$ which distributes over multiplication. You get it by conjugating $*$ by $-\log$, as I learnt from an offhand remark in the intro of this paper.
A similar trick can be used to find an operation on $[-\infty, +\infty]$ which $+$ distributes over, conjugating by $1/\exp$ now, you get the much more notorious softplus (or log-sum-exp) operation $a \oplus b = -\log(e^{-a}+e^{-b})$.

John Baez (Nov 26 2024 at 16:34):

I feel I've almost thought about these but chickened out. So can we iterate this trick indefinitely, getting commutative monoid operations $\ast_n$ such that $\ast_0$ is ordinary addition and $\ast_n$ distributes over $\ast_{n-1}$ for all $n \in \mathbb{Z}$?

Mike Stay (Nov 26 2024 at 16:34):

Yes

Mike Stay (Nov 26 2024 at 16:35):

And the limit is the tropical rig.

John Baez (Nov 26 2024 at 16:36):

I was just thinking about similar things recently when I learned that in the 1300s Thomas Bradwardine would call something like $(5/2)^{1/2}$ "half" of $5/2$, but in a deliberately extended sense of "half".

John Baez (Nov 26 2024 at 16:37):

The Nicole Oresme extended this idea to work out a general theory of fractional exponents.

Mike Stay (Nov 26 2024 at 16:37):

The particular operation Matteo is looking at is (up to sign) also the one the Diffie–Hellman key exchange uses. In that setup, Alice and Bob pick a large prime $p$ and a generator $g$ and do all their computations modulo $p$. Each of them picks a secret exponent (say $a$ and $b$, respectively). They compute $A=g^a$ and $B=g^b$ respectively and publish them. To communicate, Alice computes $B^a = B^{\log_g A}$ and Bob computes $A^b = A^{\log_g B}$. Since computing the discrete log to the base $g$ is hard, no one else can figure out their shared secret.

Mike Stay (Nov 26 2024 at 16:38):

Thanks, fixed.

John Baez (Nov 26 2024 at 16:48):

You've told me this more than once before, @Mike Stay, but I tend to forget it - maybe because I never spend any time thinking about cryptography in general or Diffie-Hellman in particular. I must have the instincts of a pure mathematician, because instead of cryptography I actually find it more interesting to think about the idea of a "meta-ring" $R$ with operations $\ast_0, \ast_1, \ast_2$ such that $(R, \ast_0, \ast_1)$ is a ring and also $(R, \ast_1, \ast_2)$ is a ring. (And so on, with even more operations.)

Matteo Capucci (he/him) (Nov 26 2024 at 16:57):

John Baez said:

I feel I've almost thought about these but chickened out. So can we iterate this trick indefinitely, getting commutative monoid operations $\ast_n$ such that $\ast_0$ is ordinary addition and $\ast_n$ distributes over $\ast_{n-1}$ for all $n \in \mathbb{Z}$?

There should be such a hierarchy of operations if you continue conjugating and maybe I'm just getting bamboozled by exponents, but it seems $*_3 = \odot_1$ isn't associative?

Matteo Capucci (he/him) (Nov 26 2024 at 16:58):

Mike Stay said:

And the limit is the tropical rig.

Why? :O

Mike Stay (Nov 26 2024 at 17:16):

We're exponentiating a bunch of times, adding, then taking the log a bunch of times. Whichever parameter starts larger gets much larger after exponentiating, at which point adding the two doesn't make much difference to the size of the larger, and then you take logs to bring them back down. So we have this hierarchy:
$a *_{-\infty} b = a \max b$
...
$a *_{-n} b = \ln(\cdots \ln(\exp\cdots \exp a + \exp \cdots \exp b)\cdots)$
...
$a *_{-2} b = \ln(\exp a *_{-1} \exp b)$
$a *_{-1} b = \ln(\exp a *_0 \exp b)$
$a *_0 b = a + b$
$a *_1 b = \exp(\ln a *_0 \ln b) = a * b$
$a *_2 b = \exp(\ln a *_1 \ln b)$
...
$a *_n b = \exp(\cdots \exp(\ln\cdots \ln a + \ln \cdots \ln b)\cdots)$

Mike Stay (Nov 26 2024 at 17:26):

Diffie–Hellman is analogous to $*_2$.

Mike Stay (Nov 26 2024 at 17:36):

Distributivity for $*_2$:
$a *_2 (b *_1 c) = \exp(\ln a *_1 \ln (b *_1 c))$
$= \exp(\ln a *_1 (\ln b *_0 \ln c))$
$= \exp(\ln a * (\ln b + \ln c))$
$= \exp(\ln a * \ln b + \ln a * \ln c)$
$= \exp(\ln a *_1 \ln b) *_1 \exp(\ln a *_1 \ln c)$
$= (a *_2 b) *_1 (a *_2 c)$

The other cases ($n$ distributing over $n-1$) work by induction, and everything distributes over $\max$.

Mike Stay (Nov 26 2024 at 17:42):

Associativity of $*_2$:
$(a *_2 b) *_2 c = \exp(\ln (a *_2 b) *_1 \ln c)$
$= \exp(\ln \exp(\ln a *_1 \ln b) *_1 \ln c)$
$= \exp(\ln a *_1 \ln b *_1 \ln c)$
$= \exp(\ln a * \ln b * \ln c)$ and $*$ is associative, so
$= a *_2 (b *_2 c)$
All other $n$ work similarly.

Mike Stay (Nov 26 2024 at 17:51):

Note that the arguments to $*_n$ for $n > 2$ have to be larger than $e^{e^{⋰^e}}$ (of height $n-2$) so that the iterated logarithm doesn't try to take the log of a negative number.

Mike Stay (Nov 26 2024 at 18:27):

Because Matteo's operation has a minus sign, it's not associative, for the same reason minus isn't. We can recover his operation by defining $a \odot b = (1/a) *_2 b = a *_2 (1/b)$.

John Baez (Nov 26 2024 at 18:34):

Mike Stay said:

Note that the arguments to $*_n$ for $n > 2$ have to be larger than $e^{e^{⋰^e}}$ (of height $n-2$) so that the iterated logarithm doesn't try to take the log of a negative number.

Yes, so I was wrong in my description since I guess the unit for $\ast_0$, namely ordinary addition, isn't in the domain of $\ast_2$, or maybe $\ast_3$, and so on.

Mike Stay (Nov 26 2024 at 18:48):

I think your meta-ring still exists, just going in the other direction. $(\mathbb{R}, *_0, *_1)$ is a ring, $(\mathbb{R}, *_{-1}, *_0)$ is a ring, $(\mathbb{R}, *_{-2}, *_{-1})$ is a ring, etc.

Clémence Chanavat (Nov 26 2024 at 19:04):

I remember seeing this youtube video about that (or almost that). This is apparently called "Commutative hyperoperation"

Matteo Capucci (he/him) (Nov 27 2024 at 13:42):

Matteo Capucci (he/him) said:

John Baez said:

I feel I've almost thought about these but chickened out. So can we iterate this trick indefinitely, getting commutative monoid operations $\ast_n$ such that $\ast_0$ is ordinary addition and $\ast_n$ distributes over $\ast_{n-1}$ for all $n \in \mathbb{Z}$?

There should be such a hierarchy of operations if you continue conjugating and maybe I'm just getting bamboozled by exponents, but it seems $*_3 = \odot_1$ isn't associative?

In hindsight I had to be wrong because conjugation by an isomorphism always yields a well-defined operation inheriting all the properties, including distributivity

Matteo Capucci (he/him) (Nov 27 2024 at 13:43):

Mike Stay said:

We're exponentiating a bunch of times, adding, then taking the log a bunch of times. Whichever parameter starts larger gets much larger after exponentiating, at which point adding the two doesn't make much difference to the size of the larger, and then you take logs to bring them back down.

Make sense! It's interesting that also varying the base of exp/log yields the same behaviour

Mike Stay (Nov 27 2024 at 16:12):

I wonder if there's a continuous version of the hierarchy. It should be related to "tetration" since we're looking at power towers like $e^{e^{⋰^e}}$...

Ah, looks like there's a solution to Abel's functional equation for $\exp$ letting you do tetration at real heights. So it at least makes sense to say $*_{1.5}$. I don't know if $*_\lambda$ distributes over $*_{\lambda - 1}$ for all $\lambda$ or just for $\lambda \in \mathbb{Z}$.

Daniel Geisler (Nov 27 2024 at 17:51):

See Tetration for Complex Bases by Paulsen for extending tetration to the complex numbers. For a more general treatment of fractionally iterated functions see Some formulas for fractional iteration.

Note: I'm currently reviewing how solid the foundations are for the main papers in extending tetration.

Ryo Suzuki (Nov 30 2024 at 09:44):

I have seen a categorification of the operation (a,b) |-> a^log b. It is defined as Adj(C,D^op)^op, here Adj(C,D^op) is the category of left adjoint functor F:C→D^op. This operation behaves distributively with respect to the product of categories. I learned this from https://alg-d.com/math/kan_extension/log.pdf, but this is unfortunately written in Japanese.