Recent MathOverflow Questions

Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?

Math Overflow Recent Questions - Thu, 06/08/2017 - 14:34

Question 1 What is the number of pairs of commuting elements in GL_n(F_q) ?

I am aware of many results concerning commuting elements in Mat_n(F_q), but I am interested in GL i.e. non-degenerate matrices. In particular Feit, Fine 1960, results for many kinds of Lie algebras obtained recently Jason Fulman, Robert Guralnick, and even Motivic Donaldson... is related to counting nilpotent matrices - see beautiful answer on by Olivier Schiffmann.

[EDIT after answers] Answers say: the number of commuting pairs in ANY group equals to number of conjugacy classes multiply order of group. Number of conjugacy classes in $GL(n,F_q)$ has nice generating function MO8415, MO104457 (or links in answers below): $$ \sum_{n\geq 0} |number~of~conjugacy~classes~in~GL(n,F_q)| x^n = \prod_{j\geq 1} \frac{1-x^j}{1-qx^j} $$

[end EDIT]

Question 1b If we take limit q->1 can we get number of commuting elements in S_n ? (Standard analogy S_n = GL_n(F_1) ).

[EDIT after answers] There is beautiful formula for $S_n$ which can count m-tuples of commuting elements, number of involutions, number of elements of order k and so on - just one formula can do it all - see MO272045. From the answer there we know that there is certain q-analog of that formula for GL(n,F_q). However it does not immediately cover the case of commuting pairs (m-tuples) and also the limit q->1 is not clear. In particular it is not clear to me how generating function above can in the limit q->1 give generating functions for conjugacy classes in $S_n$ - partition function. So there is place to think more (imho). [end EDIT]

Question 2 what about triples, n-tuples ?

[EDIT after answers] Is it open problem ? Since it is not covered by powerful analysis in papers quoted in MO answer [end EDIT]

Question 3 what about other finite algebraic groups ? (In view of results Fulman, Guralnick for Lie algebras it seems natural).

Question 4 for compact simple groups over R one can put for example Killing Riemnanian metric and consider volumes for such manifolds - are there some results ?

PS By the way nice fact on pairs of commuting elements is here: 5/8 bound in group theory


Question 1c By the way can computer algebra systems like GAP or MAGMA get the answer on such question for small "n", but in the form of polynomial in "q", or they can deal only with fixed q ?

(See answer in comment by Alexander Konovalov ).

Why is it customary to have formal series at infinity in the context of resurgence and 1-summability?

Math Overflow Recent Questions - Thu, 06/08/2017 - 08:29

In the context of the theory of 1-summability and resurgence, it is customary to deal with formal series "at infinity" rather than at $0$ $$ \sum_{n=0}^{\infty}a_nz^{-n} $$ This is stated for example at the beginning of section 3 on Why is this? is there really any preference over using $t=1/z$? $$ \sum_{n=0}^{\infty}a_nt^{n} $$

Monodromy representation of elementary simple covers

Math Overflow Recent Questions - Thu, 06/08/2017 - 08:22

Let $X$, $Y$ be smooth, connected, compact manifolds (for instance, projective varieties) and $f \colon X \longrightarrow Y$ be a finite, branched cover of degree $n$, with branch locus $B \subset Y$. We can then associate to $f$ its monodromy representation $$\theta_f \, \colon \pi_1(Y-B) \longrightarrow S_n,$$ so that $\mathrm{im} \, \theta_f$ is a transitive subgroup of $S_n$. Conversely, isomorphism classes of connected covers of $Y$, branched over $B$, are in bijection to monodromy representations of the type above, up to conjugacy in $S_n$.

We now assume that $f$ is simple, that is that for all $b \in B$ the fibre $f^{-1}(b)$ consists of exactly $n-1$ points, and we call $f$ an elementary cover if it is not possible to factor it as $$X \stackrel{g}{\longrightarrow} Z \stackrel{h}{\longrightarrow} Y,$$ where $g\colon X \longrightarrow Z$ is a branched cover and $h \colon Z \longrightarrow Y$ is an ordinary (i.e, unramified) cover.

Q. What is the characterization of simple, elementary covers $f \colon X \longrightarrow Y$, branched over $B$, in terms of their monodromy representation $\theta_f$?

Orbit decomposition of the restriction of an equivariant sheaf?

Math Overflow Recent Questions - Thu, 06/08/2017 - 08:12

All sets and groups in the question are finite.

In order to understand equivariant sheaves better I'm trying to prove some basic facts from Mackey theory using equivariant sheaves. The main obstacle i've been faced with is the difficulty of keeping track of all the different equivalences.

Let $G$ be a group and $K \lt G$ a subgroup. Perhaps one of the most basic canonical equivalences is between $Sh_G(G/K)$ and $Sh_K(pt)$. This can be implemented as follows:

Let $p: G \to pt$ and $q : G \to G/K$ be the projections. Then one has the following compositions:

$$Sh_K(pt) \overset{k \mapsto k^{-1}}{\longrightarrow} Sh_{K^{op}}(pt) \overset{p^*}{\to} Sh_{G \times K^{op}}(G) \overset{q^{K^{op}}_*}{\to} Sh_G(G/K)$$


  1. First arrow is the inversion isomorphism from $K$ to $K^{op}$. It is obviously an equivalence.
  2. The second arrow is the pullback which remembers the left $G$-equivariant structure coming from the fact that the projection $G/K \to pt$ is left $G$-equivariant. This is an equivalence since the $G$-action is free.
  3. The third arrow is $K^{op}$-invariant sections of the pushforward along $q: G \to G/K$. This is an equivalence since the right $K^{op}$ action is free.

The functor in the other direction is the composition of the pseudo inverses.

This is all very neat until one tries to use this equivalence to prove stuff. I'll try to explain with an example. Suppose we wanted Mackey's induction formula. In other words we'd like to describe the functor $Res^K_G \circ Ind^G_H$ in terms of other functors.

Let $p: G/H \to pt$ and $q: G/K \to pt$. In this notation the composition above admits the following description:

$$Sh_G(G/H) \overset{p_*}{\to} Sh_G(pt) \overset{Res^K_G}{\to} Sh_K(pt)$$

By commutativity of the corresponding diagram this composition is isomorphic to the composition:

$$Sh_G(G/H) \overset{Res^K_G}{\to} Sh_K(G/H) \overset{p_*}{\to} Sh_K(pt)$$

Once one realizes that the category $Sh_K(G/H)$ splits as a direct sum $\bigoplus_{\mathcal{O}} Sh_K(\mathcal{O})$ over all $K$-orbits in $G/H$, then the second functor above $p_*$ becomes easy to describe as it is just a direct sum of induction functors.

However, the following functor:

$$F: Sh_K(pt) \to Sh_G(G/H) \overset{Res^K_G}{\to} Sh_K(G/H) \to \bigoplus_{\mathcal{O} \in I} Sh_K(\mathcal{O})$$

Obtained by composing the first functor with equivalences seems rather mysterious.

It looks like it should be a sum over certain restriction functors (a fact we already know if we know about the classical mackey formula). Beyond that however this functor is completely mysterious to me. In order to compute it I found no other choice other than composing all the functors involved and which resulted in a huge expression I didn't manage to decipher.

How can one describe $F$ using the language of equivariant sheaves?

How does one compute similar functors in practice?

Of course I already know what $F$ should be from the classical Mackey formula but i'm looking for a way to "grab hold" of this functor using the language equivariant sheaves.

Polynomials and matrices in $\Bbb F_q$

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:52
  1. Given a polynomial $p(x)\in\Bbb F_q[x]$ of degree $n$ where $q=p^\alpha$ with $p$ a prime and $\alpha\in\Bbb N$ how many different matrices $A_1,\dots,A_k\in \Bbb F_q^{m\times m}$ can we have such that $$p(A_1)=\dots= p(A_k)=0$$ holds on the condition $$\operatorname{vec}(A_1),\dots,\operatorname{vec}(A_k)\in\Bbb F_q^{m^2}$$ are independent in $\Bbb F_q^{m^2}$?

  2. Given a polynomial $p(x,y)\in\Bbb F_q[x,y]$ of $(x,y)$ degree $(n_x,n_y)$ where $q=p^\alpha$ with $p$ a prime and $\alpha\in\Bbb N$ how many different matrices $A_1,\dots,A_{k_x}\in \Bbb F_q^{m\times m}$ and $B_1,\dots,B_{k_y}\in \Bbb F_q^{m\times m}$ can we have such that $$p(A_i,B_j)=0$$ holds at every $i\in\{1,\dots,k_x\}$ and every $j\in\{1,\dots,k_y\}$ on the condition $$\operatorname{vec}(A_1),\dots,\operatorname{vec}(A_k)\in\Bbb F_q^{m^2}$$ $$\operatorname{vec}(B_1),\dots,\operatorname{vec}(B_k)\in\Bbb F_q^{m^2}$$ are independent in $\Bbb F_q^{m^2}$ and when does $$\mathsf{span}(\operatorname{vec}(A_i))\cap\mathsf{span}(\operatorname{vec}(B_j))=\{0^{m^2}\}$$ hold?

Exterior powers of $Sym^p T$ over Gr(k,n)

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:45

Let G=Gr(k,n) the Grassmannian of $k$-dimensional subspaces of $\mathbb{C}^n$ and denote by $T$ the (rank $k$) tautological bundle over $G$, and by $Sym^p T$ its $p$-th symmetric power. Is there any known formula for computing the exterior powers $$\wedge^q(Sym^pT)$$ in terms of Schur powers $\Sigma^{\lambda}T$?

I am aware of other plethysm formulae (say, for $Sym^k(\wedge^2) $) but I haven't been able to find a reference in the literature for this particular case.

The most relevant case for me is $p=2$, but having a general result would be immensely useful.

Sylvester–Gallai theorem with circle version and plane version

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:33

The Sylvester–Gallai theorem in geometry states that, given a finite number of points in the Euclidean plane, either

  1. All the points are collinear; or

  2. There is a line which contains exactly two of the points.

I think the theorem is also true for circle and plane version, can you give a proof of these versions?

Conjecture: (circle version):

Given a finite number of points in the Euclidean plane, either

  1. All the points are concyclic; or

  2. There is a circle which contains exactly three points.

Conjecture: (Plane version)

Given a finite number of points in the three-dimensional space, either

  1. All the points in a plane; or

  2. There is a plane which contains exactly three points.

Zero digits of a p-adic algebraic number

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:27

This question might be too simple and I just don't see something very obvious, so I apologize in advance if that is so.

Let $p$ be a prime number and let $\mathbb Z_p$ denote the ring of $p$-adic integers. Let $\alpha \in \mathbb Z_p$ be an algebraic number of degree $d \geq 2$ (i.e. with a minimal polynomial in $\mathbb Z[x]$ of degree $d \geq 2$). This number can be written in the form

$$ \alpha = \sum\limits_{i = 0}^\infty a_ip^i, $$

where $a_i \in \{0, 1, \ldots, p - 1\}$. Intuitively it should be the case that, as $i$ gets bigger, we cannot have too many $a_i$'s in succession being zero. In other words, if for some sufficiently large $i_0$ it is the case that

$$a_{i_0} = a_{i_0+1} = \ldots = a_{i_0 + h} = 0,$$

then $h$ cannot be too big. Otherwise, the integer $m = \sum\limits_{i = 0}^{i_0 - 1}a_ip^i$ would approximate $\alpha$ "too well". Is there any way to quantify this heuristics and prove it, whether effectively or not? (optimally, I want to know an upper bound on $h$)

Game theoretic aspects of Wang tiles?

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:22

Wang tiles are interesting in that they can simulate Turing machines. My question is whether anyone has studied there game theoretic properties?

In particular, we could imagine a game in which you have a plane with some wang tiles on it, and players take turns placing tiles adjacent to tiles already on the board. The last player to place a tiles wins. This is only one example of how to gamify Wang tiles, of course.

Is there any research into the games based on Wang tiles?

Lie algebra structures on the space of smooth vector fields

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:20

Assume that $L=(\mathbb{R}^n,, [\;\;.\;\;])$ is a Lie algebra structure on $\mathbb{R}^n$. Associated with $L$, there is a natural Lie algebra structure $\tilde{L}$ on $\chi^{\infty}(\mathbb{R}^n)$, the space of smooth vector fields on $\mathbb{R}^n$ as follows:

$$ [f \partial/\partial{x_i}, g\partial/\partial{x_j}]=fg[\partial/\partial{x_i}, \partial/\partial{x_j}]+(f\partial g/\partial x_i) \partial/\partial{x_j}-(g\partial f/\partial x_j) \partial/\partial{x_i}$$

1.Is it true to say that $L_1\simeq L_2$ if and only if $\tilde{L_1}\simeq \tilde{L_2}?$

  1. Is there a non Abelian Lie algebra structure $L$ on $\mathbb{R}^n$ such that for every two vector fields $X,Y$ and every diffeomorphism $H$ between two open subsets of $\mathbb{R}^n$, we have $H_*[X,Y]=[H_*X,H_*Y]$?

The second question on coordinate free property of the Lie braket, is a motivation to define a new Lie algebra structure on $\chi^{\infty}(M)$ for every $n$ dimensional manifold $M$.

Idelic/Hom representation of locally free class groups

Math Overflow Recent Questions - Thu, 06/08/2017 - 07:17

Let $K$ be a number field with ring of integers $\mathcal{O}_K$ and let $G$ be a finite abelian group. Elements in $KG$ may be regarded as maps on the character group $\widehat{G}$ of $G$ via

$$\sum_{s\in G} \gamma_s s^{-1}\mapsto\left(\chi\mapsto \sum_{s\in G} \gamma_s \chi(s)^{-1}\right),$$

and this induces an isomorphism

$$ KG \simeq \prod_{\psi} K(\psi)$$

of algebras. Here $\psi$ ranges over a set of representatives of $\widehat{G}$ under the action of the absolute Galois group of $K$, and $K(\psi)$ is the field $K$ ajoint with $\psi(s)$ for $s\in G$.

Let $M$ denote the maximal $\mathcal{O}_K$-order in $KG$. Then

$$ M \simeq \prod_{\psi} \mathcal{O}(\psi), $$

where $\mathcal{O}(\psi)$ is the ring of integers in $K(\psi)$, and so its locally free class group

$$(*)\hspace{1em}\mbox{Cl}(M) \simeq \prod_{\psi}\mbox{Cl}(\mathcal{O}(\psi)).$$

Now, we have an idelic description for $\mbox{Cl}(M)$ given by

$$\mbox{Cl}(M)\simeq \frac{J(KG)}{(KG)^\times U(M)},$$

where $J(KG)$ is the restricted direct product of $(K_vG)^\times$ with respect $(\mathcal{O}_{K_v}G)^\times$ as $v$ ranges over the (finite) primes in $K$, and $U(M) = \prod_v M_v^\times$. Regarding elements in $K_vG$ as maps on $\widehat{G}$, elements in $M_v$ are precisely whose images are algebraic units. There is a similar description for $\mbox{Cl}(\mathcal{O}(\psi))$ for each $\psi$.

Question: How does one describe the isomorphism $(*)$ in terms of these idelic/Hom-descriptions of the class groups?

If $K$ contains all $\exp(G)$th roots of unity, then this is easy. We can just map $(K_vG)^\times$ to $K_v^\times$ componentwise for each $v$. But otherwise, there are more primes involved idelic description of $\mbox{Cl}(\mathcal{O}_K)$ (one needs to range over all primes in $K(\psi)$). How does one take this into account?

Reference for map $\operatorname{Hom}^d(C,\mathbb{P}^1) \to \operatorname{Sym}^d(C)$

Math Overflow Recent Questions - Thu, 06/08/2017 - 06:57

For a curve $C$ over a finite field, I am looking at the map $\phi: \operatorname{Hom}^d(C,\mathbb{P}^1) \to \operatorname{Sym}^d(C)$ where $\operatorname{Hom}^d(C,\mathbb{P}^1)$ are the functions of degree $d$ from $C \to \mathbb{P}^1$ in the $\operatorname{Hom}$-scheme $\operatorname{Hom}(C, \mathbb{P}^1)$, defined by $$\phi: f \mapsto [0]\cdot \Gamma_f$$

i.e. we intersect the graph of $f$ in $C \times \mathbb{P}^1$ with the line $[\sigma]$ in $C \times \mathbb{P}^1$ (which is the inverse image of $\sigma$ under the projection to $\mathbb{P}^1$.

For example the $f$ in the picture would map to $\phi(f) = 2\cdot P_1 + 3\cdot P_2 + 2\cdot P_3 + 2\cdot P_4$

I have looked at Kollár's Rational Curves on Algebraic Varieties and Chapter 9 of Nakajima's Lectures on Hilbert Schemes of Points on Surfaces however I can't find the information I need of this map.

For example, is $\phi$ flat? What is the dimension of the fiber of $\phi$? Etc. Etc.

Does anyone know of a reference for this topic?

Proof that GPY conjecture implies a weak twin primes conjecture?

Math Overflow Recent Questions - Thu, 06/08/2017 - 06:53

This post Density of prime pairs whose gap is less than the average gap says that it is conjectured that (in case # means the cardinal of the set) $$ \#\{p_n<x|\alpha < \frac{p_{n+1} - p_n}{\log(p_n)}<\beta \} \sim \pi(x) \int_{\alpha}^{\beta} \frac{1}{e^t}dt$$. Let $p_n$ denote the $n$'th prime number. Define the set $$A_1(p_N) = \{g_n = p_{n+1} - p_n | p_{n+1} < p_N\}$$ We make the following notations: $|A_1(p_N)|$ is the number of elements in $A_1(p_N)$ and $\sum A_1(p_N)$ is the sum of the elements in $A_1(p_N)$. It is known form prime number theorem that $|A_1(p_N)| \sim \frac{p_N}{\log(p_N)}$ and obviously $\sum A_1(p_N) \sim p_N$. Define $$ A_2(p_N) = \left\{g_n \in A_1(p_N)| g_n < \frac{\sum A_1(p_n)}{|A_1(p_n)|}\right\}$$ The quantity on the right of the inequality $\frac{\sum A_1(p_n)}{|A_1(p_n)|} \sim \log(p_n)$ It is conjectured (I think GPY applies here too ) that $|A_2(p_N)| \sim N \int_{0}^1 \frac{1}{e^t}dt = c_2\cdot |A_1(p_N)|$ where $c_2$ is a strictly positive constant. Further more define in a similar fashion: $$ A_3(p_N) = \left\{g_n \in A_{2}(p_N)| g_n \leq \frac{\sum A_{2}(p_n)}{|A_{2}(p_n)|}\right\} $$ the process can continue of course. The question is about $|A_3(p_N)|$ whether is $\infty$ or not? The interesting thing is (if somebody can check it would be great) that $\sum A_2(p_N) < e \cdot |A_1(p_N)|$ hence $$ \frac{\sum A_2(p_N)}{|A_2(p_N)|} < \frac{e}{c_2} \approx 4.3$$ This is, if correct, a connection with twin prime conjecture right? I think $|A_3(p_N)| \to \infty$ because a set $A_2(p_N)$ with an infinity of elements must have an infinity of elements with magnitude $\leq$ with the mean. So does this prove that GPY conjecture implies a weak twin prime conjecture?

Cup Product - Leibniz Rule

Math Overflow Recent Questions - Thu, 06/08/2017 - 06:37

I'm trying to prove the Leibniz Rule: $$\partial(u \smile v) = \partial(u) \smile v + (-1)^{|u|} \ u \smile \partial(v) $$ and I'm having some difficulties.

Here's my attempt: Let $|u| = p$, $|v|=q$ and $\sigma: \Delta^{p+q+1} \longrightarrow X$.

  1. $(\partial u \smile v)([\sigma]) = \displaystyle \sum_{i=0}^{p} (-1)^{i} u([\sigma d^{i} \lambda_{p}]) \cdot v([\sigma \rho_{q}]) + (-1)^{p+1} \ u([\sigma \lambda_{p}]) \cdot v([\sigma \rho_{q}])$. Ok, so far.

  2. Here's the problem with the proof I found: $(u \smile \partial v)([\sigma]) = u([\sigma \lambda_{p}]) \cdot \partial v ([\sigma \rho_{q+1}])$. But $\partial v ([\sigma \rho_{q+1}]) = \displaystyle \sum_{j=p}^{p+q+1} (-1)^{j-p} v([\sigma \rho_{q+1} d^{j-p}])$. We split the sum: $j = p: (-1)^{p-p} v([\sigma \rho_{q+1} d^{j}]) = v([\sigma \rho_{q}])$ and $j \geq p+1: (-1)^{p} \displaystyle \sum_{j=p+1}^{p+q+1} (-1)^{j} v([\sigma\rho_{q+1} d^{j}])= (-1)^{p}\displaystyle \sum_{j=p+1}^{p+q+1} (-1)^{j} v([\sigma d^{j} \rho_{q}])$.

I don't understand the sum when $j \geq p+1$. Shouldn't there be a $-(-1)^{p}$ and why do we have the $d^{j}$ instead of $d^{j-p}$?

I'm sorry if my question is too dumb but I'm having a hard time with this. Any help would be greatly appreciated.

What is the classification of this group?

Math Overflow Recent Questions - Thu, 06/08/2017 - 04:45

Let $K=\mathbb C((t))$ and $O=\mathbb C[[t]]$, and $n\geq 1$. Consider the matrix $$J_{2n}=\begin{pmatrix} 0& I_n \\ -I_n & 0\end{pmatrix},$$ And let $\Psi : K^{2n}\times K^{2n}\rightarrow K$ given by $$\Psi(u,v)=u\cdot J_{2n}\cdot \overline v,$$ where $\overline{f(t)}=f(-t)$.

  • What is the type of the group $S(\Psi)_{2n}(K)=\{g\in SL_{2n}(K); \Psi(g,g)=\Psi\}$? (as in the table given by Tits)

  • Is it Split? Simply connected?

  • Is $P=S(\Psi)_{2n}(O)$ is a maximal parahoric subgroup?

This has been studied by Pappas and Rapoport for a Hermitian $\Psi$, but I couldn't find any reference for this case.


Pseudo-Anosov Matrices of surfaces (reference request)

Math Overflow Recent Questions - Thu, 06/08/2017 - 04:19

can the pseudo-Anosov monodromy matrix of some space be of the form of a reducible or block matrix? Any such reference can be helpful. Thanks.

Generalizing a codistributive property of sufficiently disjoint normal subgroups to protomodular categories

Math Overflow Recent Questions - Wed, 06/07/2017 - 15:33

In a poset, whenever the meets and joins below exist, their universal properties induce a containment $$(A\vee B)\wedge (A\vee C)\geq A\vee(B\wedge C).$$ This is an instance of codistributivity. In a lattice distributivity is equivalent to codistributivity, but this requires the above identity to hold for several ordered triples $A,B,C$.

In the categories of groups and of modules, when dealing with sufficiently disjoint subobjects, a codistributive identity holds. Below is the argument for groups (and modules).

Proposition. Let $A,B,C\vartriangleleft G$ be normal subgroups such that $B,C$ are disjoint and $A$ is disjoint from $B\vee C$ (in particular $A,B,C$ are disjoint). Then$$(A\vee B)\wedge (A\vee C)= A.$$

Proof. Let $g$ be an element of the LHS. Since $A$ is normal, $A\vee B=AB,A\vee C=AC$ where juxtaposition denotes the subset product. Thus $g\in AB\cap AC$. Hence we may write $$g=a_1b=a_2c.$$ From the equality on the right we obtain $$a_1^{-1}a_2=bc^{-1}.$$ In particular, this element belongs to $A$ and $BC$. Since $B$ is normal, $BC=B\vee C$. Thus $$a_1^{-1}a_2=bc^{-1}\in A\wedge (B\vee C).$$ By assumption the RHS is trivial, so $b=c\in B\wedge C$. By assumption $B,C$ are disjoint so $b=c=1_G$. Coming back to the first equation for $g$ we see $g\in A$, proving the $\leq $ direction of the proposition. The $\geq $ is always true.

Question. How can I prove the proposition above for a sufficiently nice protomodular category?

Update. Some possibly relevant information.

In a finitely complete pointed protomodular category, the poset of normal subobjects is isomorphic to the poset of equivalence relations. Hence we may equivalently deal with the desired identity in the poset (in fact lattice) of equivalence relations.

For this, the following two papers by Bourn seem relevant.

Congruence distributivity in Goursat and Mal'cev categories and A categorical genealogy of the congruence distributive property.

In particular, Theorem 2.1 of the former paper characterizes congruence distributivity in Goursat categories via the preservation of binary infima by the direct image functor associated to every regular epi $f:A\to B$. $$\mathrm{Rel}_{\mathsf{C}}(A)\to \mathrm{Rel}_{\mathsf{C}}(B)$$

What does the $\pi$ in $\pi$-system stand for?

Math Overflow Recent Questions - Wed, 06/07/2017 - 14:06

In measure theory, what does the $\pi$ in $\pi$-system stand for? Also, what about the $\lambda$ in $\lambda$-system? I want to know why Dynkin chose these names, and why these names make sense.

The formal theory of monads on $\bf PDer$

Math Overflow Recent Questions - Wed, 06/07/2017 - 08:38

I have two questions on the 2-category of prederivators $\bf PDer$:

  1. Does $\bf PDer$ "admit the construction of algebras" (ATCOA) in the sense of Street's Formal theory of monads? I recall that by ATCOA for a 2-category $\cal K$ I mean that the inclusion functor ${\cal K} \to {\bf Mnd}({\cal K})$ has a right 2-adjoint. One can show by hand (see below) that there are well-behaved objects of algebras for a monad $T : \mathbb D \to \mathbb D$, but I wouldn't be able to guess if something goes wrong when trying to glue these objects to a 2-adjoint ${\bf Mnd}({\bf PDer})\to \bf PDer$...

  2. Regarding a monad as a lax functor $1\to \cal K$ its "object of EM-algebras" is its lax limit (dually, the Kleisli object is its lax colimit). Is it known that given a monad $T$ on a prederivator $\mathbb D$ there are adjunctions $$ \text{Alg}_T(\mathbb D) \leftrightarrows \mathbb D \quad\text{and}\quad \text{Kl}_T(\mathbb D) \leftrightarrows \mathbb D $$ obtained gluing the various categories of algebras and free algebras $\text{Alg}_{T_J}(\mathbb D(J))$ and $\text{Kl}_{T_J}(\mathbb D(J))$ on the monads $T_J : \mathbb D(J) \to \mathbb D(J)$ induced by the components of $T$, in order to form the prederivator of EM-algebras and of free algebras.

    Are these two prederivators still characterized by the universal property of the lax co/limit of $T : 1\to \bf PDer$?

17 camels trick

Math Overflow Recent Questions - Wed, 06/07/2017 - 07:52

The following popular mathematical parable is well known. A father left 17 camels to his three sons, and according to the will the eldest son should be given a half of all camels, the middle son the one-third part and the youngest son the one-ninth. This is hard to do, but a wise man helped the sons: he added his own camel, the oldest son took 18/2=9 camels, the second son took 18/3=6 camels, the third son 18/9=2 camels and the wise man took his own camel and went away.

I ask for applications of this method: when something is artificially added, somehow used, and after that taken away (as this 18-th camel of a wise man).

Let me start with two examples from graph theory.

1) We know Hall's lemma: if any $k=1,2,\dots$ men in a town like at least $k$ women in total, then all the men may get married so that each of them likes his wife. How to conclude the following generalized version? "If any $k$ men like at least $k-s$ women in total, then all but $s$ men may get married." Proof. Add $s$ extra women (camel-women) liked by all men. Apply usual Hall lemma, after that say pardon to the husbands of extra women.

2) This is due to Noga Alon, recently popularized by Gil Kalai. How to find a perfect matching in a bipartite $r$-regular multigraph? If $r$ is a power of 2, this is easy by induction. Indeed, there is an Euler cycle in every connected components, take edges alternatively, so we partition our graph onto two $r/2$-regular multigraphs. Moreover, we get a partition of edges onto $r$ perfect matchings. Now, if $r$ is not a power of 2, take large $N$ and write $2^N=rq+t$, $0<t<r$. Replace each edge of our multigraph onto $q$ edges, also add extra edges formed by arbitrary $t$ perfect matchings. This new multigraph may be partitioned onto $2^N$ perfect matchings, and if $N$ is large enough, some of them do not contain extra edges.


Subscribe to curious little things aggregator