The n-Category Café

Maybe we can categorify the argument by replacing the inequality $|X\times Y|+|Y\times X|\leq|X\times X|+|Y\times Y|$ by the set of injections $Inj(X\times Y + Y\times X,X\times X + Y\times Y)$?

The overall form of the “proof” would be a map (what kind?)

$In

I’m glad you’ve brought this back up, David, because I find Terry’s challenge highly thought-provoking. It shows up our ignorance deliciously.

For all that we know about the categorification of identities (with the theory of species etc.), we seem to know almost nothing about the categorification of inequalities.

One of the thoughts that Terry’s challenge provokes in me is “what exactly are we trying to do?” Let’s take something even simpler and more basic than Cauchy–Schwarz, the mother of all inequalities:

$$x^2 \geq 0.$$

How could one categorify it? Well, if we interpret “$X^2 \geq 0$” as “there exists an injection from the empty set to the cartesian square of any set $X$” then it’s obviously true, but so too is $X \geq 0$. So that makes it clear (if it wasn’t already) that sets are “nonnegative objects” and shouldn’t be treated as analogues of arbitrary real numbers.

And that makes us think about formal differences $X - Y$ of sets (whatever that means), and then the inequality $(X - Y)^2 \geq 0$ rearranges to

$$X \times X + Y \times Y \geq X \times Y + Y \times X,$$

which is one of the ones you listed in your post, David.

Now there are no natural transformations

$$X \times X + Y \times Y \leftrightarrows X \times Y + Y \times X$$

(I mean, natural in $X, Y \in Set$) in either direction, except for four non-injective ones from right to left. (They all send $(x, y)$ to either $(x, x)$ or $(y, y)$, and similarly $(y, x)$.) And if there are no natural transformations, what possible help could category theory be?

There is a possibility, though. Time spent playing the game of converting identities in rings into identities in semirings (or rig categories) taught me that often a “thickening” occurs. The most famous case is the implication

$$t = t^2 + 1 \implies t^6 = 1,$$

which holds in any ring. But in a semiring, the closest we can get is

$$t = t^2 + 1 \implies t^7 = t$$

(Andreas Blass’s Seven trees in one). The conclusion has been “thickened” by a factor of $t$. So who knows, maybe there’s some injective natural transformation like

$$6X Y + (X^3 + Y^3)2 X Y \to 6X Y + (X^3 + Y^3)(X^2 + Y^2)$$

(where the thickening is just something random I made up). If there is, would it be helpful, though?

Regarding the following…

If $f: X \to Y$ is a function between finite sets, then $\left| X \times_{f} X \right| \geq \left| X \right|^{2} / \left| Y \right|$.

…perhaps it may be helpful to try to write down in a reasonably direct way any monomorphism $X^{2} \rightarrow Y \times \left( X \times_{f} X \right)$, whether or not it is immediately category theoretic. To this end, I wonder if the following works.

As a preliminary step, for any pair $(y, y') \in Y \times Y$ such that $\left| f^{-1}(y) \right| \leq \left| f^{-1}(y') \right|$, choose any monomorphism $f^{-1}(y) \rightarrow f^{-1}(y')$, and denote it by $i_{y,y'}$.

Take $(x_1, x_2) \in X^{2}$. Suppose that $\left| f^{-1} \left( f(x_1) \right) \right| \lt \left| f^{-1} \left( f(x_2) \right) \right|$. In this case, send $(x_1, x_2)$ to $\left( f(x_1), \left( i_{f(x_1), f(x_2)}(x_1), x_2 \right) \right)$. Otherwise, namely if $\left| f^{-1} \left( f(x_1) \right) \right| \geq \left| f^{-1} \left( f(x_2) \right) \right|$, send $(x_1, x_2)$ to $\left( f(x_1), \left( x_1, i_{f(x_2), f(x_1)}(x_2) \right) \right)$.

I think that this defines a monomorphism. To see this, take $(x_1, x_2)$ and $(x_1', x_2')$ in $X^{2}$ which map to the same thing in $Y \times \left( X \times_{f} X \right)$. Observe first that it is impossible that $\left| f^{-1} \left( f(x_1) \right) \right| \lt \left| f^{-1} \left( f(x_2) \right) \right|$ but that $\left| f^{-1} \left( f(x_1') \right) \right| \geq \left| f^{-1} \left( f(x_2') \right) \right|$. Indeed, we would then have that $f(x_1) = f(x_1')$, and also that $i_{f(x_1), f(x_2)}(x_1) = x_1'$. But $i_{f(x_1), f(x_2)}(x_1)$ is in $f^{-1}\left(f(x_2) \right)$ whereas $x_1'$ is in $f^{-1}\left( f(x_1') \right) = f^{-1}\left( f(x_1) \right)$, so we would then have that $f(x_2) = f(x_1)$, which contradicts our assumption that $\left| f^{-1} \left( f(x_1) \right) \right| \lt \left| f^{-1} \left( f(x_2) \right) \right|$.

An entirely analogous argument demonstrates that it is impossible that $\left| f^{-1} \left( f(x_1) \right) \right| \geq \left| f^{-1} \left( f(x_2) \right) \right|$ but that $\left| f^{-1} \left( f(x_1') \right) \right| \lt \left| f^{-1} \left( f(x_2') \right) \right|$. Indeed, we would then have that $f(x_1) = f(x_1')$, and also that $i_{f(x_1'), f(x_2')}(x_1') = x_1$, from which, as above, we would be able to deduce that $f(x_2') = f(x_1')$, contradicting our assumption that $\left| f^{-1} \left( f(x_1') \right) \right| \lt \left| f^{-1} \left( f(x_2') \right) \right|$.

Suppose now that $\left| f^{-1} \left( f(x_1) \right) \right| \lt \left| f^{-1} \left( f(x_2) \right) \right|$ and that $\left| f^{-1} \left( f(x_1') \right) \right| \lt \left| f^{-1} \left( f(x_2') \right)\right|$. Then $x_2 = x_2'$, and moreover $f(x_1) = f(x_1')$ and $i_{f(x_1), f(x_2)}(x_1) = i_{f(x_1'), f(x_2')}(x_1')$. Putting all of these facts together, we obtain that $i_{f(x_1), f(x_2)}(x_1) = i_{f(x_1), f(x_2)}(x_1')$, which, since $i_{f(x_1), f(x_2)}$ is a monomorphism, implies that $x_1 = x_1'$. Hence $(x_1, x_2) = (x_1', x_2')$, as required.

An entirely analogous argument demonstrates that $(x_1, x_2) = (x_1', x_2')$ also holds if $\left| f^{-1} \left( f(x_1) \right) \right| \gt \left| f^{-1} \left( f(x_2) \right) \right|$ and $\left| f^{-1} \left( f(x_1') \right) \right| \gt \left| f^{-1} \left( f(x_2') \right) \right|$.

Finally, if $\left| f^{-1} \left( f(x_1) \right) \right| = \left| f^{-1} \left( f(x_2) \right) \right|$ and $\left| f^{-1} \left( f(x_1') \right) \right| = \left| f^{-1} \left( f(x_2') \right) \right|$, then it is immediate that $(x_1, x_2) = (x_1', x_2')$, as required.

How ‘category theoretic’ is this monomorphism? Actually I think it is constructible category theoretically. We have (purely category theoretically) that $X^{2}$ is isomorphic to $\bigsqcup_{y \in Y} \bigsqcup_{y' \in Y} f^{-1}(y) \times f^{-1}(y')$. Thus it suffices to construct a map $f^{-1}(y) \times f^{-1}(y') \rightarrow Y \times \left( X \times_{f} X \right)$ for every $(y,y') \in Y^{2}$. To do this in the way I did above, the only thing one really needs is that one of $\left| f^{-1}(y) \right| \lt \left| f^{-1}(y') \right|$, $\left| f^{-1}(y) \right| \gt \left| f^{-1}(y') \right|$, or $\left| f^{-1}(y) \right| = \left| f^{-1}(y') \right|$ must hold. If one defines all of the ingredients in the last sentence in a category theoretic way (e.g. defining a finite set to be one isomorphic to $\bigsqcup_{n} 1$ for some $n \in \mathbb{N}$, where $1$ is a one element set), this will reduce to the fact that, for any pair of natural numbers $n$ and $n'$, one of $n \leq n'$, $n \geq n'$, or $n = n'$ must hold, which will be perfectly true when working category theoretically as well. Once one has this, everything else in my definition of the map is straightforwardly expressible ‘category theoretically’ (in terms of arrows between sets), as is the proof that we have a monomorphism.

I think it would be naïve to imagine that one can construct a monomorphism by only some immediate application of some ‘doctrinal’ properties of the category of sets. The formulation of the problem only really makes sense because of the fact that one can express a finite set as a coproduct of $1$’s, so I think one has to expect a non-trivial result to dig down to that level. This does not preclude of course that it might be possible to formulate some useful greater level of generality in which one can carry out the same kind of argument.

This is all off the cuff, so I hope I have not made some egregious error(s); apologies in advance if so! I have not thought about how this argument relates to usual proofs of the Cauchy-Schwartz inequality, I just came up with it directly.

The argument by Robin gives a wonderful categorical proof that $(X \times X) \sqcup (Y \times Y)$ is at least as large as $(X \times Y) \sqcup (Y \times X)$ in the category of sets.

Terry Tao then showed how to deduce from this the relative version, that $(X \times_Y X) \sqcup (Z \times_Y Z)$ is at least as large as $(X \times_Y Z) \sqcup (Z \times_Y X)$. The idea is to apply Robin’s proof in each fiber associated to an element $y \in Y$. One of the problems is then to turn Terry Tao’s argument into a categorical proof.

I would say that his argument is already categorical to a large degree. Below is a rephrasing of the same argument to make it look a bit more categorical.

In a Grothendieck topos $\mathcal{E}$ we could define the size $|X|$ of an object $X$ in the topos as the disjoint union of the fibers $p^*(E)$, where $p$ goes over the isomorphism classes of points of the topos. For example, in the category of sets (or $G$-sets for $G$ a group), the size is just the underlying set. If you take a sheaf on a sober topological space $X$, then the size of the sheaf is the underlying set of $Y$, where $Y \to X$ is the local homeomorphism (étale space) associated to the sheaf. The functor $|.|$ that sends an object $X$ to its size $|X|$ preserves colimits and pullbacks (but not necessarily binary products or the terminal object).

Because the functor $p^*$ preserves disjoint unions and products and $|.|$ preserves coproducts, the equality $|X \times X| + |Y \times Y| \geq |X \times Y| + |Y \times X|$ then holds in any topos. If you apply this to the slice topos over $Y$, then you get the equality $|X \times_Y X| + |Z \times_Y Z| \geq |X \times_Y Z| + |Z \times_Y X|$. Here we say $A \geq B$ if the cardinality of $A$ is greater than or equal to the cardinality of $B$.

For the original problem, you can use that $|.|$ preserves pullbacks, and then you get $|X \times_Y X| = |X| \times_{|Y|} |X|$ which is bigger than $|X|^2/|Y|$ using the result for sets.

Even for the simpler version, and taking $X$ to be a finite set of cardinality $n \ge 3$ and $Y = 1$, there’s no equivariant embedding $X + X \hookrightarrow X \times X + 1$.

To see this, we can work in HoTT: Consider first equivariant maps $X \to X \times X + 1$. These are elements of the type

(Here I take as a classifying type for the symmetric group, $BS_n$, the type of $n$-element sets.)

Since $BS_{n-1}$ is connected, any element on the right must factor through one of the 5 coproduct inclusions. But since $n-1\ge2$, there are no elements in the type $\prod_{A:BS_{n-1}}A$ (no fixed point of an $(n-1)$-element set under permutation), so the only choices are the constant map to the final unit type, or the constant map to the penultimate one, and the latter corresponds to the diagonal map $\prod_{X:BS_n}(X \to X\times X)$.

So if we have an embedding, it must be the diagonal. But that means there’s no element of the type

since both compositions with the coproduct inclusions $X \hookrightarrow X + X$ must be the diagonal.

There is a recent paper of Pak and Ikenmeyer which gives an interesting perspective on this. https://arxiv.org/abs/2204.13149.

Among many other results, they prove that, subject to reasonable assumptions about complexity theory, that there isn’t an efficient way to convert efficient algorithms for recognizing elements in two sets X and Y into an injection from 2XY into X^2+Y^2. (Discussion in Section 2.3 and 2.4.)