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: community: our work

Topic: Rémy Tuyéras

Rémy Tuyéras (Jul 08 2024 at 02:27):

Logical independence versus Probabilistic independence

Recently, I found a formula that clarifies the link between stochastic and logical independence, but I'm still struggling to escape the measure theory aspect. Ideally, my goal would be to abstract both concepts of independence in a single setting.

For anyone reading this: I am potentially looking for insights or references that could help clarify the content below in terms of category theory. Any direction or references would be welcome.

Logical independence

For a given set of axioms $B$ (say written in a logic $\mathcal{L}$ which uses propositional logic as a basis), define $\neg B:= \{\neg \varphi~|~\varphi \in B\}$.

One says that a set $B$ of axioms in $\mathcal{L}$ is independent from another set $A$ of axioms in $\mathcal{L}$ if we can find two models $\mathcal{M}$ and $\mathcal{M}'$ such that:

$\mathcal{M} \vDash A \cup \neg B$

$\mathcal{M}' \vDash A \cup B$

Stochastic independence

Let $(\Omega,\mathcal{E},P)$ be a measure space for a probability measure $P:\mathcal{E} \to [0,1]$.

For every pair $(A,B)$ of events $A \in \mathcal{E}$ and $B \in \mathcal{E}$, we define $\delta(A,B) = P(A\cap B)-P(A)P(B)$. We say that the events $A$ and $B$ are independent if the formula $\delta(A,B) = 0$ holds.

Proposition. The formula $\delta(A,B) = P(A \cap B)P(A^c \cap B^c) - P(A \cap B^c)P(A^c \cap B)$ holds.
proof. Write $P(A) = P(A \cap B) + P(A \cap B^c)$ and $P(B) = P(B \cap A) + P(B \cap A^c)$ and insert these expressions in the expression for $\delta(A,B)$. Expand, then factor out $P(B \cap A)$ and finally observe that
$P(A^c \cap B^c) = 1- P(B \cap A) -P(B \cap A^c)-P(A \cap B^c)$
$\square$

Now, our goal is to reformulate the expression above. For this, we can use the product probability measure $P_2:\mathcal{E}\otimes \mathcal{E}\to [0,1]$, which is generated by the images $P_2(X \times Y) = P(X)P(Y)$ for every $(X,Y) \in \mathcal{E} \times \mathcal{E}$. Also, for every pair $(X,Y)$ of events in $\mathcal{E}\times\mathcal{E}$, let us denote $X \oplus Y = (X \cap Y^c) \times (X^c \cap Y)$.

Our new notations reduce the expression of $\delta(A,B)$ to this:

$\delta(A,B) = P_2\big(A \oplus B^c\big) - P_2\big(A \oplus B\big)$

In other words, two events $A$ and $B$ are independent if the probability of finding a configuration in $\Omega \otimes \Omega$ that validates the event $A \oplus B^c$ is equal to the probability of finding a configuration in $\Omega \otimes \Omega$ that validates the event $A \oplus B$.

Conclusion and question

There seems to be an analogy between stochastic and logical independence here. I tried to come up with an algebraic definition of stochastic independence by requiring a bijection $A \oplus B^c \cong A \oplus B$, but this hasn't helped me escape the probability measure context.

Does anyone have intuitions on this or know some references that have explored this?

Eric M Downes (Jul 08 2024 at 04:02):

How about $\Sigma$-algebra instead of measure theory?

Every [[sigma algebra]] is a boolean algebra with countable joins, and in which every non-bottom element is a member of a maximal filter closed under countable meets... IIRC thats the same as "complete". Books on boolean algebras should have this, and it looks like the connection you are making, at least from a distance. I believe you could phrase $p$ just as a monotonic (along inclusions) map from the lattice of subsets to the total order on $\mathbb{R}$. In logic the appropriate codomain is then just $\mathbb{B}$ I guess. A rewrite in terms of monotonic-maps of locales should be immediate, and that at least escapes (explicit) measure theory to something category-adjacent.

Matteo Capucci (he/him) (Jul 08 2024 at 07:11):

Unfortunately a measure is not just a map of lattices, since it maps antichains of the algebra to sums in R. That's the fundamental quirk that messes up measure theory (and makes it useful, really)

Eric M Downes (Jul 08 2024 at 07:20):

Thanks, Matteo. If you impose inclusion-exclusion as an extra assumption, which already holds for the [edit: finite] rank functions of modular lattices, is that insufficient?

(just to state things explicitly: every distributive lattice is modular, rank functions are monotonic maps from graded posets to $\mathbb{Z}$, which morally at least seems generalizable, IE for two lattice elements is $p(x\vee y)+p(x\wedge y)=p(x)+p(y)$ where $p$ is a rank function, and IE has higher-order expressions as well, with alternating signs like Euler's Characteristic, as well as a generalization due to Rota for arbitrary posets.)

Eric M Downes (Jul 08 2024 at 07:21):

Oh sorry that's only the finite case.

Eric M Downes (Jul 08 2024 at 07:30):

I have not understood this paper by Peter May, so I may be missing badly, but it discusses inclusion-exclusion in the deepest and broadest context of which I am aware, and seems broadly applicable. And I believe IE is sufficient to get antichains to map to sums, so even if the lattice is not finite modular and you don't have IE for a rank function for free, maybe the category you want to generalize to is triangulated, and that could help.

Sam Staton (Jul 08 2024 at 07:59):

I might be misunderstanding this discussion, but if not, one nice angle is effect algebras. These sort-of generalize Boolean algebras by thinking in terms of partial operations.

On a finite set $n$, a probability measure is the same thing as an effect algebra homomorphism $P(n)\to [0,1]$. Here $P(n)$ is regarded with the partial monoid structure given by disjoint union, and $[0,1]$ is regarded with the partial monoid structure given by addition where it is possible.

It's not as ad hoc as it might sound because these things fully embed in presheaves on finite Boolean algebras.

For the infinitary case, there are $\sigma$-effect algebras which have the analogous correspondence, since every $\sigma$-algebra is also a $\sigma$-effect algebra.

Matteo Capucci (he/him) (Jul 08 2024 at 09:33):

Eric M Downes said:

Thanks, Matteo. If you impose inclusion-exclusion as an extra assumption, which already holds for the [edit: finite] rank functions of modular lattices, is that insufficient?

(just to state things explicitly: every distributive lattice is modular, rank functions are monotonic maps from graded posets to $\mathbb{Z}$, which morally at least seems generalizable, IE for two lattice elements is $p(x\vee y)+p(x\wedge y)=p(x)+p(y)$ where $p$ is a rank function, and IE has higher-order expressions as well, with alternating signs like Euler's Characteristic, as well as a generalization due to Rota for arbitrary posets.)

The main problem is that $(\overline\R,+)$ is not a lattice since $+$ is not idempotent. This problem aside, asking explicitly for an inclusion-exclusion relation does work (you can concot a suitable version for the countable case) but then your just asking explicitly for it, not hiding it in the underlying structure :(

Eric M Downes (Jul 08 2024 at 09:53):

(I think you need the codomain to be an ordered ring, not a lattice for monotone maps from a lattice to express independence (as in, have the possibility of being homomorphic on meet), but maybe I misunderstand what Remy is trying to do here, and admittedly I have not looked into this in detail.)

Regarding asking for IE explicitly -- yeah totally its not elegant, but the purpose was to allow us to abstract away from measure theory, and I was suggesting doing that by using lattices + IE as the latter plays well with lattices, and is an example of a kind of categorical trace discussed in the May paper. (The effect algebras Sam Stanton suggested seem like they are nearly lattices, and quite interesting.)

Rémy Tuyéras (Jul 08 2024 at 23:00):

@Eric M Downes @Matteo Capucci (he/him) @Sam Staton Thanks for the feedback! It will take me some time to go through it all (got a pretty busy week :grimacing:), but that's the kind of feedback I was looking for!

Rémy Tuyéras (Jul 18 2024 at 10:38):

This Saturday, I will be flying to Tokyo to give a talk at the FHE & MPC Tokyo Residency, organized by the Ethereum community. Ethereum is also hosting the EDCON 2024 in Tokyo during that time.

At the residency, I will present my paper on Constructing a Fully Homomorphic Encryption Scheme with the Yoneda Lemma. The audience will have diverse math backgrounds, though most will not be familiar with category theory.

In a few lines, asymmetric cryptography has been relying on the commutativity of the Yoneda Lemma to produce cryptosystems with sound correctness. For example:

1. In ElGamal, you take a (commutative) group $G$, choose a secret key $x \in \mathbb{Z}$ and publish the power $g^x$ for some publicly known $g \in G$. To encrypt a message $m \in G$, choose a homomorphism of the form $h:f \mapsto f^y$ and send the ciphertext $(h(g),m\cdot h(g^x))$.

   How do you decrypt this ciphertext? If you have the secret key $x$, you can compute $m = m\cdot h(g^x) \cdot (h(g)^{x})^{-1}$.

2. With lattic-based frameworks, you take an $R$-module $M$, choose a secret key $x \in M^n$ and publish a vector of the form $Ax+e$ for some publicly known $(n,N)$-matrix $A$ and (forgettable) small random vector $e \in M^N$. To encrypt a message $m \in M$, choose a homomorphism of the form $h:f \mapsto y^Tf$ and send the ciphertext $(h(A),m + h(Ax+e))$.

   How do you decrypt this ciphertext? If you have the secret key $x$, you can compute $m \simeq m+h(Ax+e)-h(A)x$.

Conclusion: the main ingredients to the decryption algorithms are the commutativity equations:

• $h(g^x) = h(g)^x$ and
• $h(Ax) = h(A)x$.

Now where is Yoneda? Well, for a given limit sketch $T$, the Yoneda Lemma gives us an isomorphism

$\mathsf{Hom}(T(d,-),X) \cong X(d)$

representing any morphism $g:T(d,-) \to X$ as some map "$x \mapsto \langle g, x\rangle$" for some representative $g \in X(d)$. And for every morphism $h:X \to Y$, it also gives us the naturality property

$h(\langle g, x\rangle) = \langle h(g), x\rangle,$

which is basically recovering the commutative ingredient needed to decrypt in ElGamal and lattice-based systems. After noticing that, you can write down what you need to recover most FHE cryptosystems using the Yoneda Lemma. As a direct application, you can choose arbitrary theories $T$ and see what kind of cryptosystem you get.