Union of hyperplanes over a finite field

Posted on 22 February 2022 by Remy

The following lemma is a (presumably well-known) result that Raymond Cheng and I happened upon while writing our paper Unbounded negativity on rational surfaces in positive characteristic (arXiv, DOI). Well, Raymond probably knew what he was doing, but to me it was a pleasant surprise.

Lemma. Let $q$ be a power of a prime $p$ , and let $x_0,\ldots,x_n \in \bar{\mathbf F}_q$ . Then $x_0,\ldots,x_n$ satisfy a linear relation over $\mathbf F_q$ if and only if

$\det \begin{pmatrix} x_0 & x_1 & \cdots & x_n \\ x_0^q & x_1^q & \cdots & x_n^q \\ \vdots & \vdots & \ddots & \vdots \\ x_0^{q^n} & x_1^{q^n} & \cdots & x_n^{q^n} \end{pmatrix} = 0.$

Proof. If $\sum_{i=0}^n c_ix_i = 0$ for $(c_0,\ldots,c_n) \in \mathbf F_q^n - \{0\}$ , then $c_i^{q^j} = c_i$ for all $i,j \in \{0,\ldots,n\}$ since $c_i \in \mathbf F_q$ . As $(-)^q \colon \bar{\mathbf F}_q \to \bar{\mathbf F}_q$ is a ring homomorphism, we find

$\begin{pmatrix} x_0 & x_1 & \cdots & x_n \\ x_0^q & x_1^q & \cdots & x_n^q \\ \vdots & \vdots & \ddots & \vdots \\ x_0^{q^n} & x_1^{q^n} & \cdots & x_n^{q^n} \end{pmatrix}\begin{pmatrix} c_0 \\ c_1 \\ \vdots \\ c_n \end{pmatrix} = 0,$

so the determinant is zero. Conversely, the union of $\mathbf F_q$ -rational hyperplanes $H \subseteq \mathbf P^n_{\mathbf F_q}$ is a hypersurface $Y$ of degree $|\check{\mathbf P}^n(\mathbf F_q)| = q^n + \ldots + q + 1$ (where $\check{\mathbf P}^n$ denotes the dual projective space parametrising hyperplanes in $\mathbf P^n$ ). Since the determinant above is a polynomial of the same degree $q^n + \ldots + q + 1$ that vanishes on all $\mathbf F_q$ -rational hyperplanes, we conclude that it is the polynomial cutting out $Y$ , so any $[x_0:\ldots:x_n] \in \mathbf P^n(\bar{\mathbf F_q})$ for which the determinant vanishes lies on one of the hyperplanes. $\qedsymbol$

Of course when the determinant is zero, one immediately gets a vector $(c_0,\ldots,c_n) \in \bar{\mathbf F}_q^{n+1} - \{0\}$ in the kernel. There may well be an immediate argument why this vector is proportional to an element of $\mathbf F_q^{n+1}$ , but the above cleverly circumvents this problem.

For concreteness, we can work out what this determinant is in small cases:

$n=0$ : a point $x_0 \in \bar{\mathbf F}_q$ only satisfies a linear relation over $\mathbf F_q$ if it is zero.
$n=1$ : the polynomial $x_0x_1^q-x_0^qx_1$ cuts out the $\mathbf F_q$ -rational points of $\mathbf P^1$ .
$n=2$ : the polynomial
$x_0x_1^qx_2^{q^2}+x_1x_2^qx_0^{q^2}+x_2x_0^qx_1^{q^2}-x_0^{q^2}x_1^qx_2-x_1^{q^2}x_2^qx_0-x_2^{q^2}x_0^qx_1$
cuts out the union of $\mathbf F_q$ -rational lines in $\mathbf P^2$ . This is the case considered in the paper.

Algebraic closure of the field of two elements

Posted on 1 April 2021 by Remy

I think I learned about this from a comment on MathOverflow.

Recall that the field of two elements $\mathbf F_2$ is the ring $\mathbf Z/2\mathbf Z$ of integers modulo $2$ . In other words, it consists of the elements $0$ and $1$ with addition $1+1 = 0$ and the obvious multiplication. Clearly every nonzero element is invertible, so $\mathbf F_2$ is a field.

Lemma. The field $\mathbf F_2$ is algebraically closed.

Proof. We need to show that every non-constant polynomial $f \in \mathbf F_2[x]$ has a root. Suppose $f$ does not have a root, so that $f(0) \neq 0$ and $f(1) \neq 0$ . Then $f(0) = f(1) = 1$ , so $f$ is the constant polynomial $1$ . This contradicts the assumption that $f$ is non-constant. $\qedsymbol$

Hodge diamonds that cannot be realised

Posted on 30 September 2020 by Remy

In Paulsen–Schreieder [PS19] and vDdB–Paulsen [DBP20], the authors/we show that any block of numbers

$\left(\begin{array}{ccccc} & & h^{n,n} & & \\ & \iddots & & \ddots & \\ h^{n,0} & & & & h^{0,n} \\ & \ddots & & \iddots & \\ & & h^{0,0} & & \end{array}\right) \in \big(\mathbf Z/m\big)^{(n+1)^2}$

satisfying $h^{0,0} = 1$ , $h^{p,q} = h^{n-p,n-q}$ , and $h^{p,q} = h^{q,p}$ (characteristic $0$ only) can be realised as the modulo $m$ reduction of a Hodge diamond of a smooth projective variety.

While preparing for a talk on [DBP20], I came up with the following easy example of a Hodge diamond that cannot be realised integrally, while not obviously violating any of the conditions (symmetry, nonnegativity, hard Lefschetz, …).

Lemma. There is no smooth projective variety (in any characteristic) whose Hodge diamond is

$\begin{array}{ccccc} & & 1 & & \\ & 1 & & 1 & \\ 0 & & 1 & & 0 \\ & 1 & & 1 & \\ & & 1.\!\! & & \end{array}$

Proof. If $\operatorname{char} k > 0$ , we have $\sum_{p+q = i}h^{p,q} \geq h_{\operatorname{dR}}^i \geq h_{\operatorname{cris}}^i$ , with equality for all $i$ if and only if the Hodge–de Rham spectral sequence degenerates and $H_{\operatorname{cris}}^i$ is torsion-free for all $i$ . Because $H^2_{\operatorname{cris}}$ contains an ample class, we must have equality on $h^2$ , hence everywhere because of how spectral sequences and universal coefficients work.

Thus, in any characteristic, we conclude that $h^1_{\operatorname{Weil}}(X) = 2$ , so $\dim \mathbf{Pic}_X^0 = 1$ and the same for $\dim \mathbf{Alb}_X$ . Thus, $X \to \mathbf{Alb}_X$ is a fibration, so a fibre and a relatively ample divisor are linearly independent in the Néron–Severi group, contradicting the assumption $h^{1,1}(X) = 1$ . $\qedsymbol$

Remark. In characteristic zero, the Hodge diamonds

$\begin{array}{ccccc} & & 1 & & \\ & a & & a & \\ 0 & & 1 & & 0 \\ & a & & a & \\ & & 1 & & \end{array}$

cannot occur for any $a \geq 1$ , by essentially the same argument. Indeed, the only thing left to prove is that the image $X \to \mathbf{Alb}_X$ cannot be a surface. If it were, then $X$ would have a global 2-form; see e.g. [Beau96, Lemma V.18].

This argument does not work in positive characteristic due to the possibility of an inseparable Albanese map. It seems to follow from Bombieri–Mumford’s classification of surfaces in positive characteristic that the above Hodge diamond does not occur in positive characteristic either, but the analysis is a little intricate.

Remark. On the other hand, the nearly identical Hodge diamond

$\begin{array}{ccccc} & & 1 & & \\ & a & & a & \\ 0 & & 2 & & 0 \\ & a & & a & \\ & & 1 & & \end{array}$

is realised by $C \times \mathbf P^1$ , where $C$ is a curve of genus $a$ . This is some evidence that the full inverse Hodge problem is very difficult, and I do not expect a full classification of which Hodge diamonds are possible (even for surfaces this might be out of reach).

References.

[Beau96] A. Beauville, Complex algebraic surfaces. London Mathematical Society Student Texts 34 (1996).

[DBP20] R. van Dobben de Bruyn and M. Paulsen, The construction problem for Hodge numbers modulo an integer in positive characteristic. Forum Math. Sigma (to appear).

[PS19] M. Paulsen and S. Schreieder, The construction problem for Hodge numbers modulo an integer. Algebra Number Theory 13.10, p. 2427–2434 (2019).

Simplicial sets

Posted on 31 July 2020 by Remy

A few weeks ago, I finally struck up the courage to take some baby steps reading Lurie’s Higher topos theory. In a series of posts mostly written for my own benefit, I will untangle some of the basic definitions and provide some easy examples. The first one is one I was already somewhat familiar with: simplicial sets.

Definition. For each $n \in \mathbf N$ , write $[n]$ for the poset $0 \leq \ldots \leq n$ . The full subcategory of $\mathbf{Poset}$ on these $[n]$ is denoted $\Delta$ , the simplex category. Concretely, it has objects $[n]$ for all $n \in \mathbf N$ , and morphisms

$\operatorname{Hom}\big([m],[n]\big) = \left\{f \colon [m] \to [n]\ \Big|\ i \leq j \Rightarrow f(i) \leq f(j)\right\}.$

A simplicial set is a functor $X \colon \Delta^{\operatorname{op}} \to \mathbf{Set}$ . This can be described rather concretely using the objects $X_n = X([n])$ and the face and degeneracy maps between them; see e.g. Tag 0169. The category of simplicial sets is usually denoted $[\Delta^{\operatorname{op}}, \mathbf{Set}]$ , $\mathbf{sSet}$ , or $\mathbf{Set}_{\Delta}$ (in analogy with cosimplicial sets $\mathbf{Set}^\Delta = [\Delta,\mathbf{Set}]$ ).

The representable simplicial set $\operatorname{Hom}(-,[n])$ is usually denoted $\Delta^n$ or $\Delta[n]$ . Then the Yoneda lemma shows that the functor $\mathbf{sSet} \to \mathbf{Set}$ given by $X \mapsto X_n$ is represented by $\Delta^n$ , i.e.

$X_n = \operatorname{Hom}_{\mathbf{sSet}}\big(\Delta^n,X).$

Definition. The geometric realisation functor $| \cdot | \colon \mathbf{sSet} \to \mathbf{Top}$ is defined as follows: for $\Delta^n$ , the geometric realisation $|\Delta^n|$ is the standard $n$ -simplex

$|\Delta^n| := \left\{(x_0,\ldots,x_n) \in \mathbf R^{n+1}\ \Bigg|\ x_i \geq 0, \sum_{i=0}^n x_i = 1\right\} \subseteq \mathbf R^{n+1}.$

(If no confusion arises, it may also be denoted $\Delta^n$ .) This is functorial in $[n]$ : for a map $a \colon [m] \to [n]$ (equivalently, by the Yoneda lemma, a map $a \colon \Delta^m \to \Delta^n$ ) we get a continuous map $a \colon |\Delta^m| \to |\Delta^n|$ by

$a(x_0,\ldots,x_m)_j = \sum_{i \in a^{-1}(j)} x_i.$

For an arbitrary simplicial set $X$ , write

$|X| := \underset{\Delta^n \to X}{\operatorname{colim}}\ |\Delta^n|,$

where the transition map $|\Delta^m| \to |\Delta^n|$ corresponding to a map $\Delta^m \to \Delta^n$ over $X$ is defined via

$\operatorname{Hom}_{\mathbf{sSet}}\big(\Delta^m,\Delta^n\big) \stackrel\sim\leftarrow \operatorname{Hom}_\Delta\big([m],[n]\big) \to \operatorname{Hom}_{\mathbf{Top}}\big(|\Delta^m|,|\Delta^n|\big).$

This is functorial in $X$ , and when $X = \Delta^n$ it coindices with the previous definition because the identity $\Delta^n \to \Delta^n$ is terminal in the index category.

Remark. In a fancier language, $| \cdot |$ is the left Kan extension of the functor $[n] \mapsto |\Delta^n|$ along the Yoneda embedding $\Delta \to \mathbf{sSet}$ . (Those of you familiar with presheaves on spaces will recognise the similarity with the definition of $f^{-1}\mathscr F$ for $f \colon X \to Y$ a continuous map of topological spaces, which is another example of a left Kan extension.)

Remark. It is a formal consequence of the definitions that geometric realisation preserves arbitrary colimits (“colimits commute with colimits”). This also follows because it is a left adjoint to the singular set functor, but we won’t explore this here.

Wisdom. The most geometric way to think about a simplicial set is through its geometric realisation.

For example, we can define the $i^{\text{th}}$ horn $\Lambda_i^n$ in $\Delta^n$ as the union of the images of the maps $\Delta^{n-1} \to \Delta^n$ coming from the face maps $\delta^j_n \colon [n-1] \to [n]$ for $j \neq i$ . Since geometric realisation preserves colimits (alternatively, stare at the definitions), we see that the geometric realisation of $\Lambda^i_n$ is obtained in the same way from the maps $|\Delta^{n-1}| \to |\Delta^n|$ , so it is the $n$ -simplex with its interior and face opposite the $i^{\text{th}}$ vertex removed.

The geometric realisation is a good first approximation for thinking about a simplicial set. However, when thinking about $\infty$ -categories (e.g. in the next few posts), this is actually not the way you want to think about a simplicial set. Indeed, homotopy of simplicial sets (equivalently their geometric realisations) is stronger than equivalence of $\infty$ -categories. (More details later, hopefully.)

A strange contractible space

Posted on 3 July 2020 by Remy

Here’s a strange phenomenon that I ran into when writing a MathOverflow answer a few years ago.

Lemma. Let $X$ be a set endowed with the cofinite topology, and assume $X$ is path connected. Then $X$ is contractible.

The assumption is for example satisfied when $|X| \geq |\mathbf R|$ , for then any injection $f \colon [0,1] \hookrightarrow X$ is a path from $x_0 = f(0)$ to $x_1 = f(1)$ . Path connectedness of cofinite spaces is related to partitioning the interval into disjoint closed subsets; see the remark below for some bounds on the cardinalities.

Proof. The result is trivial if $X$ is finite, for then both are equivalent to $|X| = 1$ . Thus we may assume that $X$ is infinite. Choose a path $f \colon [0,1] \to X$ from some $x_0 = f(0)$ to some $x_1 = f(1) \neq x_0$ . This induces a continuous map $[0,1] \times X \to X \times X$ . Choose a bijection

$g \colon (X \setminus \{x_0,x_1\}) \times X \stackrel \sim\to X,$

and extend to a map $\bar g \colon X \times X \to X$ by $g(x_0,x) = x$ and $g(x_1,x) = x_1$ for all $x \in X$ . Then $\bar g$ is continuous: the preimage of $x \in X$ is $g^{-1}(x) \cup (x_0,x)$ if $x \neq x_1$ , and $g^{-1}(x) \cup (x_0,x) \cup x \times X$ if $x = x_1$ , both of which are closed. Thus $\bar g \circ (f \times \mathbf 1_X)$ is a homotopy from $\mathbf 1_X$ to the constant map $x_1$ , hence a contraction. $\qedsymbol$

I would love to see an animation of this contraction as $t$ goes from $0$ to $1$ … I find especially the slightly more direct argument for $|X| \geq |\mathbf R|$ given here elusive yet somehow strangely visual.

Remark. If $X$ is countable (still with the cofinite topology), then $X$ is path connected if and only if $|X| = 1$ . In the finite case this is clear (because then $X$ is discrete), and in the infinite case this is a result of Sierpiński. See for example this MO answer of Timothy Gowers for an easy argument.

There’s also some study of path connectedness of cofinite topological spaces of cardinality strictly between $\aleph_0 = |\mathbf N|$ and $\mathfrak c = |\mathbf R|$ , if such cardinalities exist. See this MO question for some results. In particular, it is consistent with ZFC that the smallest cardinality for which $X$ is path connected is strictly smaller than $\mathfrak c$ .

Limits as equalisers of products

Posted on 11 April 2020 by Remy

The first and second corollary below are well-known category theory lemmas. We give a slightly different argument than usual (i.e. we took a trivial result and changed it into something much more complicated).

Here is a lovely little definition:

Definition. Given a small diagram $D \colon \mathcal I \to \mathbf{Set}$ of sets, write $\bigcup D$ for the small category with

$\operatorname{ob}\left( \bigcup D \right) = \bigcup_{i \in \operatorname{ob} \mathcal I} D(i),$

and morphisms

$\operatorname{Mor}\big(a_i,b_j\big) = \left\{f \in \operatorname{Mor}(i,j)\ \Big|\ D(f)(a_i) = b_j\right\}$

for $a_i \in D(i)$ and $b_j \in D(j)$ (where $i, j \in \operatorname{ob} \mathcal I$ ), with composition induced by composition of maps $D(i) \to D(j)$ .

Note that by the Yoneda lemma, this category is isomorphic (not just equivalent!) to $(h \downarrow D)^{\operatorname{op}}$ , where $h \colon \mathcal I^{\operatorname{op}} \to [\mathcal I,\mathbf{Set}]$ is the Yoneda embedding. Indeed, $a_i \in D(i)$ are in bijection with natural transformations $h_i = \operatorname{Mor}_{\mathcal I}(i,-) \to D$ , and morphisms $a_i \to b_j$ correspond to a morphism $f \colon i \to j$ rendering commutative the associated diagram

$\begin{array}{ccccc}h_j\!\!\!\! & & \!\!\!\!\!\!\stackrel{- \circ f}\longrightarrow\!\!\!\!\!\! & & \!\!\!\!h_i \\ & \!\!\!\!\searrow\!\!\!\!\!\!\!\! & & \!\!\!\!\!\!\!\!\swarrow\!\!\!\! \\ & & D.\! & & \end{array}$

Example 1. If $\mathcal I = (\bullet \rightrightarrows \bullet)$ , then a diagram $D$ is a pair of sets $S, T$ with parallel arrows $f, g \colon S \rightrightarrows T$ . Then $\bigcup D$ looks like a ‘bipartite preorder’ where every source object has outgoing valence $2$ :

$\begin{array}{ccc}s_1 & \to & t_1 \\ & \searrow\!\!\!\!\!\!\nearrow & \\ s_2 & & t_2 \\ & \searrow & \\ \vdots & & \vdots \end{array}$

Example 2. Given a set $S$ , write $S^{\operatorname{disc}}$ for the discrete category on $S$ , i.e. $\operatorname{ob}(S^{\operatorname{disc}}) = S$ and

$\operatorname{Mor}(a,b) = \begin{cases}\{\mathbf{1}_a\}, & a = b, \\ \varnothing, & \text{else}.\end{cases}$

If $\mathcal I = I^{\operatorname{disc}}$ is itself a discrete category, then $D$ is just a collection $\mathbf S = \{S_i\ |\ i \in I\}$ of sets, and

$\bigcup D = \left(\bigcup \mathbf S\right)^{\operatorname{disc}}.$

Remark. Giving a functor $F \colon \bigcup D \to \mathscr C$ is the same thing as giving functors $F(i) \colon D(i)^{\operatorname{disc}} \to \mathscr C$ and natural transformations

$F(f) \colon F(i) \to F(j) \circ D(f)^{\operatorname{disc}}$

of functors $D(i)^{\operatorname{disc}} \to \mathscr C$ for all $f \colon i \to j$ in $\mathcal I$ , such that

$F(g \circ f) = \left(F(g) \star \mathbf 1_{D(f)^{\operatorname{disc}}}\right) \circ F(f)$

for all $i \stackrel f\to j \stackrel g\to k$ in $\mathcal I$ (where $\star$ denotes horizontal composition of natural transformations, as in Tag 003G).

Example 3. Let $\mathcal I$ be a small category, and consider the diagram $D_{\mathcal I} \colon (\bullet \rightrightarrows \bullet) \to \mathbf{Set}$ given by the source and target maps $s, t \colon \operatorname{ar}(\mathcal I) \rightrightarrows \operatorname{ob}(\mathcal I)$ . Then we have a functor

$F \colon \bigcup D_{\mathcal I} \to \mathcal I$

given on objects by

$\begin{align*} \big(f \in \operatorname{ar}(\mathcal I)\big) &\mapsto s(f),\\ \big(i \in \operatorname{ob}(\mathcal I)\big) &\mapsto i \end{align*}$

and on morphisms by

$\begin{align*} \big(s \colon f \to s(f)\big) &\mapsto \mathbf 1_{s(f)},\\ \big(t \colon f \to t(f)\big) &\mapsto f. \end{align*}$

In terms of the remark above, it is given by the functors $F(\operatorname{ar}) \colon \operatorname{ar}(\mathcal I)^{\operatorname{disc}} \to \mathcal I$ taking $f$ to $s(f)$ and the natural inclusion $F(\operatorname{ob}) \colon \operatorname{ob}(\mathcal I)^{\operatorname{disc}} \to \mathcal I$ , along with the natural transformations

$\begin{align*} F(s)(f) = \mathbf 1_{s(f)} \colon F(\operatorname{ar})(f) &\to F(\operatorname{ob})(s(f)) \\ F(t)(f) = f \colon F(\operatorname{ar})(f) &\to F(\operatorname{ob})(t(f)). \end{align*}$

We can now formulate the main result.

Lemma. Let $\mathcal I$ be a small category. Then the functor $F \colon \bigcup D_{\mathcal I} \to \mathcal I$ of Example 3 is cofinal.

Recall that a functor $F \colon \mathcal J \to \mathcal I$ is cofinal if for all $i \in \mathcal I$ , the comma category $(i \downarrow F)$ is nonemptry and connected. See also Tag 04E6 for a concrete translation of this definition.

Proof. Let $i \in \operatorname{ob}(\mathcal I)$ . Since $F(i) = i$ , the identity $i \to F(i)$ gives the object $(i,\mathbf 1_i)$ in $(i \downarrow F)$ , showing nonemptyness. For connectedness, it suffices to connect any $(x,f)$ (i.e. $f \colon i \to F(x)$ ) to the identity $(i, \mathbf 1_i$ ) (i.e. $\mathbf 1_i \colon i \to F(i)$ ). If $x \in \operatorname{ar}(\mathcal I)$ , then the commutative diagram

$\begin{array}{ccccccc}i & = & i & = & i & = & i \\ \!\!\!\!\!{\tiny f}\downarrow & & \!\!\!\!\!\!\!\!{\tiny xf}\downarrow & & || & & || \\ s(x) & \overset x\to & t(x) & \overset{xf}\leftarrow & i & = & i \\ || & & || & & || & & || \\ F(x) & \underset{F(t)}\to & F(t(x)) & \underset{F(t)}\leftarrow & F(xf) & \underset{F(s)}\to & F(i) \end{array}$

gives a zigzag

$(x,f) \stackrel t\to (t(x),xf) \stackrel t\leftarrow (xf,\mathbf 1_i) \stackrel s\to (i,\mathbf 1_i)$

of morphisms in $(i \downarrow F)$ connecting $(x,f)$ to $(i,\mathbf 1_i)$ . If instead $x \in \operatorname{ob}(\mathcal I)$ , we can skip the first step, and the diagram

$\begin{array}{ccccccc} i & = & i & = & i \\ \!\!\!\!\!\!{\tiny f}\downarrow & & || & & || \\ x & \overset{f}\leftarrow & i & = & i \\ || & & || & & || \\ F(x) & \underset{F(t)}\leftarrow & F(f) & \underset{F(s)}\to & F(i) \end{array}$

gives a zigzag

$(x,f) \stackrel t\leftarrow (f,\mathbf 1_i) \stackrel s\to (i,\mathbf 1_i)$

connecting $(x,f)$ to $(i,\mathbf 1_i)$ . $\qedsymbol$

Corollary 1. Let $D \colon \mathcal I^{\operatorname{op}} \to \mathscr C$ be a small diagram in a category $\mathscr C$ with small products. Then there is a canonical isomorphism

$\lim_{\leftarrow} D = \operatorname{Eq}\left( \prod_{i \in \operatorname{ob}(\mathcal I)} D(i) \rightrightarrows \prod_{f \in \operatorname{ar}(\mathcal I)} D(s(i)) \right),$

provided that either side exists.

Proof. By the lemma, the functor

$F \colon \left(\bigcup D_{\mathcal I}\right)^{\operatorname{op}} \to \mathcal I^{\operatorname{op}}$

is initial. Hence by Tag 002R, the natural morphism

$\lim_{\leftarrow} D \to \lim_{\leftarrow} D \circ F$

is an isomorphism if either side exists. But $\left(\bigcup D_{\mathcal I}\right)^{\operatorname{op}}$ is a category as in Example 1, and it’s easy to see that the limit over a diagram $\left(\bigcup D_{\mathcal I}\right)^{\operatorname{op}} \to \mathscr C$ is computed as the equaliser of a pair of arrows between the products. $\qedsymbol$

Of course this is not an improvement of the traditional proof, because the “it’s easy to see” step at the end is very close to the same statement as the corollary in the special case where $\mathcal I$ is of the form $\bigcup D$ for some $D \colon (\bullet \rightrightarrows \bullet) \to \mathbf{Set}$ . But it’s fun to move the argument almost entirely away from limits and into the index category.

Corollary 2. Let $\mathscr C$ be a category that has small products and equalisers of parallel pairs of arrows. Then $\mathscr C$ is (small) complete. $\qedsymbol$

Application of Schur orthogonality

Posted on 1 April 2020 by Remy

The post that made me google ‘latex does not exist’.

Lemma. Let $\epsilon$ be a finite group of order $\Sigma$ , and write $\equiv$ for the set of irreducible characters of $\epsilon$ . Then

$\forall (,) \in \epsilon : \hspace{1em} \sum_{\Xi \in \equiv} \Xi(()\overline\Xi()) = \begin{cases}|C_\epsilon(()|, & \exists \varepsilon \in \epsilon: (\varepsilon = \varepsilon), \\ 0, & \text{else}.\end{cases}$
$\forall \Xi,\underline\Xi \in \equiv : \hspace{1em} \Sigma^{-1}\sum_{\text O)) \in \epsilon} \Xi(\text O)))\overline{\underline\Xi}(\text O))) = \begin{cases}1, & \Xi = \underline\Xi,\\ 0, &\text{else}.\end{cases}$

Proof. First consider the case $\epsilon = 1$ . This is just an example; it could also be something much better. Then the second statement is obvious, and the first is left as an exercise to the reader. The general case is similar. $\qedsymbol$

Here is a trivial consequence:

Corollary. Let $\mathbf R$ be a positive integer, and let $f \in \mathbf C^\times[\mathbf R] \setminus \{1\}$ . Then

$\sum_{X = 1}^{\mathbf R} f^X = 0.$

Proof 1. Without loss of generality, $f$ has exact order $\mathbf R > 1$ . Set $\epsilon = \mathbf Z/\mathbf {RZ}$ , let $((,)) = (1,0) \in \epsilon^2$ , and note that

$\nexists \varepsilon \in \epsilon : (\varepsilon = \varepsilon).$

Part 1 of the lemma gives the result. $\qedsymbol$

Proof 2. Set $\epsilon = \mathbf Z/\mathbf {RZ}$ as before, let $\Xi \colon \epsilon \to \mathbf C^\times$ be the homomorphism $\varepsilon \mapsto f^{3\varepsilon}$ , and $\underline \Xi \colon \epsilon \to \mathbf C^\times$ the homomorphism $\varepsilon \mapsto f^{2\varepsilon}$ . Then part 1 of the lemma does not give the result, but part 2 does. $\qedsymbol$

In fact, the corollary also implies the lemma, because both are true ( $\mathbf 1 \Rightarrow \mathbf 1$ ).

Graph colourings and Hedetniemi’s conjecture II: universal colouring

Posted on 8 February 2020 by Remy

In my previous post, I stated the recently disproved Hedetniemi’s conjecture on colourings of product graphs (see this post for my conventions on graphs). In the next few posts, I will explain some of the ideas of the proof from an algebraic geometer’s perspective.

Today we will start with the universal colouring on $G \times \mathbf{Hom}(G, K_n)$ .

Lemma. Let $G$ be a graph. Then there exists an $n$ -colouring $\phi_{\operatorname{univ}}$ on $G \times \mathbf{Hom}(G, K_n)$ such that for every graph $H$ and every $n$ -colouring $\phi$ on $G \times H$ , there is a unique morphism $f \colon H \to \mathbf{Hom}(G, K_n)$ such that $f^*\phi_{\operatorname{univ}} = \phi$ .

Proof. By this post, we have the adjunction

(1) $\operatorname{Hom}(G \times H, K_n) \cong \operatorname{Hom}(H, \mathbf{Hom}(G, K_n)).$

In particular, the identity $\mathbf{Hom}(G,K_n) \to \mathbf{Hom}(G,K_n)$ gives an $n$ -colouring $\phi_{\operatorname{univ}} \colon G \times \mathbf{Hom}(G, K_n) \to K_n$ under this adjunction. If $H$ is any other graph, (1) gives a bijection between morphisms $H \to \mathbf{Hom}(G, K_n)$ and $n$ -colourings of $G \times H$ , which by naturality of (1) is given by $f \mapsto f^* \phi_{\operatorname{univ}} := \phi_{\operatorname{univ}} \circ (\operatorname{id}_G \times f)$ . $\qedsymbol$

Corollary. To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case $H = \mathbf{Hom}(G,K_n)$ , for every $n$ and every loopless graph $G$ .

Proof. Suppose by contradiction that there is a counterexample $(G,H)$ , i.e. there are loopless graphs $G$ and $H$ such that

(2) $n = \chi(G \times H) < \min(\chi(G), \chi(H)).$

Then there exists an $n$ -colouring $\phi \colon G \times H \to K_n$ , so the lemma gives a map $f \colon H \to \mathbf{Hom}(G,K_n)$ such that $\phi = f^*\phi_{\operatorname{univ}}$ . This forces $\chi(H) \leq \chi(\mathbf{Hom}(G,K_n))$ since an $m$ -colouring on $\mathbf{Hom}(G,K_n)$ induces an $m$ -colouring on $H$ by pullback. Thus, (2) implies

$\chi(G \times \mathbf{Hom}(G,K_n)) \leq n < \min(\chi(G),\chi(H)) \leq \min(\chi(G), \chi(\mathbf{Hom}(G,K_n))),$

showing that $(G,\mathbf{Hom}(G,K_n))$ is a counterexample as well. $\qedsymbol$

Corollary. Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph $G$ and any $n \in \mathbf Z_{>0}$ , either $G$ or $\mathbf{Hom}(G,K_n)$ admits an $n$ -colouring. $\qedsymbol$

Example. By the final example of my previous post and the proof of the first corollary above, the cases $n \leq 2$ are trivially true. We can also check this by hand:

If $G$ does not have a $1$ -colouring, then it has an edge. Then $\mathbf{Hom}(G,K_1)$ has no edges by construction, since $K_1$ has no edges. See also Example 2 of this post.
If $G$ does not have a $2$ -colouring, then it has an odd cycle $C_m \subseteq G$ . We need to produce a $2$ -colouring on $\mathbf{Hom}(G,K_2)$ . Choose identifications $V(K_2) \cong \mathbf Z/2$ and $V(C_m) \cong \mathbf Z/m$ with adjacencies $\{i,i+1\}$ . Consider the map

$\begin{align*}\Sigma \colon \mathbf{Hom}(G,K_2) &\to K_2\\f &\mapsto \sum_{c \in C_m} f(c) \in \mathbf Z/2.\end{align*}$
To show this is a graph homomorphism, we must show that for adjacent $f, g$ we have $\Sigma(f) \neq \Sigma(g)$ . If two maps $f, g \colon G \to K_2$ are adjacent, then for adjacent $x, y \in G$ we have $f(x) \neq g(y)$ . Taking $(x,y) = (c_i, c_{i+1})$ shows that $f(c_i) = g(c_{i+1}) + 1$ , so

$\Sigma(f) = \sum_{i = 1}^m f(c_i) = \sum_{i=1}^m \Big(g(c_{i+1}) + 1 \Big) = \Sigma(g) + 1 \in \mathbf Z/2,$
since $m$ is odd. $\qedsymbol$

The case $n = 3$ is treated in [EZS85], which seems to be one of the first places where the internal Hom of graphs appears (in the specific setting of $\mathbf{Hom}(-,K_n)$ ).

References.

[EZS85] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica 5.2, p. 121–126 (1985).

Graph colourings and Hedetniemi’s conjecture I: statement of conjecture

Posted on 5 February 2020 by Remy

The past three posts have been building up to the statement of the recently disproved Hedetniemi’s conjecture. I wanted to make an attempt to write about this, because from a first reading the main ideas of the counterexample seemed very familiar to an algebraic geometer. (More about this in a future post, hopefully.)

Definition. A colouring of a loopless graph $G$ with $n$ colours is a graph homomorphism $G \to K_n$ . The chromatic number $\chi(G)$ of $G$ is the smallest positive integer $n$ such that $G$ admits a colouring with $n$ colours.

Note that if $G$ has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is $\chi(G) \leq \# V(G)$ , since $G$ is a subgraph of the complete graph on $V(G)$ .

Example. We have $\chi(G) = 1$ if and only if $G$ has no edges (we say that $G$ is discrete), and $\chi(G) \leq 2$ if and only if $G$ contains no odd cycles (we say that $G$ is bipartite). Indeed, if you try to produce a $2$ -colouring by colouring adjacent vertices opposite colours, either this produces a $2$ -colouring or you find an odd cycle.

Conjecture (Hedetniemi). Let $G$ and $H$ be graphs. Then

$\chi(G \times H) = \min(\chi(G), \chi(H)).$

Remark. Note that $\chi(G \times H) \leq \min(\chi(G), \chi(H))$ : if $G \to K_n$ is a colouring, then the composition $G \times H \to G \to K_n$ is a colouring of $G \times H$ , and similarly for $H$ . Thus, it remains to rule out $\chi(G \times H) = n$ with $\chi(G) > n$ and $\chi(H) > n$ .

Example. The case where $\chi(G \times H) \leq 2$ is easy to check:

If $\chi(G) > 1$ and $\chi(H) > 1$ , then both $G$ and $H$ have an edge, hence so does $G \times H$ . Then $\chi(G \times H) > 1$ .
If $\chi(G) > 2$ and $\chi(H) > 2$ , then both $G$ and $H$ contain an odd cycle. If $G$ has an $n$ -cycle and $H$ an $m$ -cycle with $n$ and $m$ odd, then these give morphisms $C_n \to G$ and $C_m \to H$ . Wrapping around $m$ (resp. $n$ ) times gives morphisms $C_{mn} \to G$ , $C_{mn} \to H$ , hence to the product: $C_{mn} \to G \times H$ . Thus, $G \times H$ does not admit a $2$ -colouring since $C_{mn}$ doesn’t.

Thus, if $\chi(G \times H) \leq 2$ , then $\chi(G \times H) = \min(\chi(G), \chi(H))$ .

Internal Hom in the category of graphs

Posted on 2 February 2020 by Remy

In this earlier post, I described what products in the category of graphs look like. In my previous post, I gave some basic examples of internal Hom. Today we will combine these and describe the internal Hom in the category of graphs.

Definition. Let $G$ and $H$ be graphs. Then the graph $\mathbf{Hom}(G, H)$ has vertices $\operatorname{Map}(V(G), V(H))$ , and an edge from $f \colon V(G) \to V(H)$ to $g \colon V(G) \to V(H)$ if and only if $\{x,y\} \in E(G)$ implies $\{f(x), g(y)\} \in E(H)$ (where we allow $x = y$ as usual).

Lemma. If $G$ , $H$ , and $K$ are graphs, then there is a natural isomorphism

$\operatorname{Hom}(G \times H, K) \stackrel\sim\to \operatorname{Hom}(G, \mathbf{Hom}(H, K)).$

In other words, $\mathbf{Hom}(H,K)$ is the internal Hom in the symmetric monoidal category $(\mathbf{Grph}, \times)$ .

Proof. There is a bijection

$\begin{align*}\alpha \colon \operatorname{Map}(V(G), V(\mathbf{Hom}(H, K))) &\stackrel\sim\to \operatorname{Map}(V(G \times H), V(K))\\\phi &\mapsto \bigg((g,h) \mapsto \phi(g)(h)\bigg).\end{align*}$

So it suffices to show that $\phi$ is a graph homomorphism if and only if $\psi = \alpha(\phi)$ is. The condition that $\phi$ is a graph homomorphism means that for any $\{x,y\} \in E(G)$ , the functions $\phi(x), \phi(y) \colon V(H) \to V(K)$ have the property that $\{a,b\} \in E(H)$ implies $\{\phi(x)(a), \phi(y)(b)\} \in E(K)$ . This is equivalent to $\{\psi(x,a),\psi(y,b)\} \in E(K)$ for all $\{x,y\} \in E(G)$ and all $\{a,b\} \in E(H)$ . By the construction of the product graph $G \times H$ , this is exactly the condition that $\psi$ is a graph homomorphism. $\qedsymbol$

Because the symmetric monoidal structure on $\mathbf{Grph}$ is given by the categorical product, it is customary to refer to the internal $\mathbf{Hom}(G,H)$ as the exponential graph $H^G$ .

Example 1. Let $S^{\operatorname{disc}}$ be the discrete graph on a set $S$ . Then $\mathbf{Hom}(S^{\operatorname{disc}}, K)$ is the complete graph with loops on the set $V(K)^S$ . Indeed, the condition for two functions $f, g \colon S \to V(K)$ to be adjacent is vacuous since $S^{\operatorname{disc}}$ has no edges.

In particular, any function $V(G) \to V(\mathbf{Hom}(S^{\operatorname{disc}}, K))$ is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function $V(G \times S^{\operatorname{disc}}) \to V(H)$ is a graph homomorphism, since $G \times S^{\operatorname{disc}}$ is a discrete graph.

Example 2. Conversely, $\mathbf{Hom}(H, S^{\operatorname{disc}})$ is discrete as soon as $H$ has an edge, and complete with loops otherwise. Indeed, the condition

$\{x,y\} \in E(H) \Rightarrow \{f(x),g(y)\} \in E(S^{\operatorname{disc}}) = \varnothing$

can only be satisfied if $E(H) = \varnothing$ , and in that case is true for all $f$ and $g$ .

In particular, a function $V(G) \to V(\mathbf{Hom}(H, S^{\operatorname{disc}}))$ is a graph homomorphism if and only if either $G$ or $H$ has no edges. Under the adjunction above, this corresponds to the fact that a function $V(G \times H) \to S$ is a graph homomorphism to $S^{\operatorname{disc}}$ if and only if $G \times H$ has no edges, which means either $G$ or $H$ has no edges.

Example 3. Let $S^{\operatorname{loop}}$ be the discrete graph on a set $S$ with loops at every point. Then $\mathbf{Hom}(S^{\operatorname{loop}}, K) = K^S$ is the $S$ -fold power of $K$ . Indeed, the condition that two functions $f, g \colon S \to V(K)$ are adjacent is that $\{f(s), g(s)\} \in E(K)$ for all $s \in S$ , which means exactly that $\{\pi_s(f), \pi_s(g)\} \in E(K)$ for each of the projections $\pi_s \colon K^S \to K$ .

In particular, graph homomorphisms $f \colon G \to \mathbf{Hom}(S^{\operatorname{loop}}, K)$ correspond to giving $S$ graph homomorphisms $f_s \colon G \to K$ . Under the adjunction above, this corresponds to the fact that a graph homomorphism $g \colon G \times S^{\operatorname{loop}} \to K$ is the same thing as $S$ graph homomorphisms $g_s \colon G \to K$ , since $G \times S^{\operatorname{loop}}$ is the $S$ -fold disjoint union of $G$ .

Example 4. Let $* = \{\operatorname{pt}\}^{\operatorname{loop}}$ be the terminal graph consisting of a single point with a loop (note that we used $*$ instead for $\{\operatorname{pt}\}^{\operatorname{disc}}$ in this earlier post). The observation above that $G \times * \cong G$ also works the other way around: $* \times G \cong G$ . Then the adjunction gives

$\operatorname{Hom}(G, K) \cong \operatorname{Hom}(*, \mathbf{Hom}(G,K)).$

This is actually true in any symmetric monoidal category with internal hom and identity object $*$ . We conclude that a function $f \colon V(G) \to V(K)$ is a graph homomorphism if and only if $\mathbf{Hom}(G, K)$ has a loop at $f$ . This is also immediately seen from the definition: $\mathbf{Hom}(G, K)$ has a loop at $f$ if and only if $\{x,y\} \in E(G)$ implies $\{f(x), f(y)\} \in E(H)$ .

Example 5. Let $K_n$ and $K_m$ be the complete graphs on $n$ and $m$ vertices respectively. Then $\mathbf{Hom}(K_n, K_m)$ has as vertices all $n$ -tuples $(a_1,\ldots,a_n) \in \{1,\ldots,m\}^n$ , and an edge from $(a_1,\ldots,a_n)$ to $(b_1,\ldots,b_n)$ if and only if $a_i \neq b_j$ when $i \neq j$ . For example, for $n = 2$ we get an edge between $(a_1, a_2)$ and $(b_1, b_2)$ if and only if $a_1 \neq b_2$ and $a_2 \neq b_1$ .