Recent MathOverflow Questions

Likelihood function to estimate the randomness parameter in Watts and Strogatz's model (1998)

Math Overflow Recent Questions - Mon, 03/04/2019 - 05:42

Consider the Watts and Strogatz's model (W&S, 1998) with randomness parameter $p$, where $0\leq p\leq 1$. Suppose one observes the adjacency matrix of an undirected, unweighted social network after rewiring.

Problem: Derive the likelihood function of $p$ associated with this observed social network to estimate $p$ via maximum likelihood.

Below I propose a solution to obtain this likelihood function. This solution uses arguments provided in Menezes et al. (2017). In this solution, there are two points (labeled as Point 1 and Point 2) where I am not sure whether the rationale is correct or not. I was wondering if you could help me with these two points, please. For each point that is not correct, if any, please let me know where I am wrong and why. Thanks a lot for your help and suggestions.


$N$: size of the social network, i.e. its number of nodes.

$p$: randomness parameter in W&S.

$k$: number of right-side neighbors of any node in the regular lattice, i.e. when $p=0$; therefore, the input of W&S is the regular lattice of size $N$, where each node is connected with its $2\cdot k$ closest neighbors.

$[i$-$j]$: arc that connects nodes $i$ and $j$, with $(i,\,j)\in\{1,\ldots,\,N\}^2$.

$A_{i,\,j}$: binary random variable such that, before rewiring, $A_{i,\,j}=1$ if $[i$-$j]$ exists and $A_{i,\,j}=0$ otherwise, where $\mathbb{P}(A_{i,\,j}=1)=2\cdot k/(N-1)$.

$A_{i,\,j}^{(p)}$: binary random variable such that, after rewiring based on W&S with randomness parameter $p$, $A_{i,\,j}^{(p)}=1$ if $[i$-$j]$ exists and $A_{i,\,j}^{(p)}=0$ otherwise.

In an unweighted, undirected social network, one observes $A_{i,\,j}^{(p)}=a_{i,\,j}^{(p)}$, with $a_{i,\,j}^{(p)}\in\{0,\,1\}$ for all $(i,\,j)$, $A_{i,\,i}^{(p)}=0$ for all $i$, and $A_{i,\,j}^{(p)}=A_{j,\,i}^{(p)}$ for all $(i,\,j)$.

Thus, the likelihood function of $p$ associated with the observed social network is $$\mathcal{L}(p\,|\,\{a_{i,\,j}^{(p)}:\,i<j\})=\prod_{i<j}\mathbb{P}(A_{i,\,j}^{(p)}=a_{i,\,j}^{(p)}),$$ where $a_{i,\,j}^{(p)}\in\{0,\,1\}$ for all $(i,\,j)$, with $i<j$. Note that

$$\mathbb{P}(A_{i,\,j}^{(p)}=0)=\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)\cdot\mathbb{P}(A_{i,\,j}=1)+\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=0)\cdot\mathbb{P}(A_{i,\,j}=0),$$ where $\mathbb{P}(A_{i,\,j}=1)=1-\mathbb{P}(A_{i,\,j}=0)=2\cdot k/(N-1)$.

Point 1: Consider the following rationale to compute $\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)$:

To compute $\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)$, note that one chooses $[i$-$j]$ for rewiring with probability $p$. Next, one chooses one extreme of the arc associated with either node $i$ or node $j$ with probability $1/2$ each. Next, with probability $(N-1-2\cdot k)/N$ one rewires the chosen extreme of the arc to any node in the network except (a) the node associated with the opposite extreme and (b) any of its $2\cdot k$ closest neighbors. Therefore, $$\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)=p\cdot(1/2+1/2)\cdot(N-1-2\cdot k)/N=p\cdot(N-1-2\cdot k)/N.$$ Point 1 question: Is this rationale correct?

Point 2: Consider the following rationale to compute $\mathbb{P}(A_{i,\,j}^{(p)}=1\,|\,A_{i,\,j}=0)$:

To compute $\mathbb{P}(A_{i,\,j}^{(p)}=1\,|\,A_{i,\,j}=0)$, consider a node $u\notin\{i,\,j\}$, such that either $[i$-$u]$ or $[j$-$u]$ exists. Lets consider $[i$-$u]$ (resp., $[j$-$u]$). One chooses this arc for rewiring with probability $p$. Next, with probability $1/N$ one chooses the node $j$ (resp. $i$) to produce $[i$-$j]$. Therefore, $$\mathbb{P}(A_{i,\,j}^{(p)}=1\,|\,A_{i,\,j}=0)=2\cdot p\cdot 1/N.$$ Point 2 question: Is this rationale correct?

Finally, for all $i<j$, $$\mathbb{P}(A_{i,\,j}^{(p)}=0)=2\cdot k/(N-1)\cdot p\cdot (N-1-2\cdot k)/N+(1-2\cdot k/(N-1))\cdot(1-2\cdot p/N)$$ and $\mathbb{P}(A_{i,\,j}^{(p)}=1)=1-\mathbb{P}(A_{i,\,j}^{(p)}=0)$.

As a result, one can obtain the likelihood function to estimate $p$ via maximum likelihood.


Menezes, M. B., Kim, S., & Huang, R. (2017). Constructing a Watts-Strogatz network from a small-world network with symmetric degree distribution. PloS one, 12(6), e0179120.

Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440.

What role do Hecke operators and ideal classes perform in "Quantum Money from Modular Forms?"

Math Overflow Recent Questions - Sun, 03/03/2019 - 21:31

Cross-posted on QCSE

An interesting application of the no-cloning theorem of quantum mechanics/quantum computing is embodied in so-called quantum money - qubits in theoretically unforgeable states. The initial ideas from the landmark work in the '70s/'80s require a bank to verify each transaction. Accordingly public key quantum money was introduced in the late 2000's.

One of the early proposals of a public key quantum money was based on knots. Here, the qubits for the quantum money are in eigenstates corresponding to knot (grid) diagrams. The eigenstates are indexed by Alexander polynomials, which, in addition to being efficiently calculable, are invariant under Reidemeister (Cromwell) moves. Thus, after confirming that the Alexander polynomial of the quantum money is in the mint's publicly accessible list of minted currencies, vendors can verify that the quantum money is legitimate by running a Markov chain $M$ of Reidemeister moves on the money state $\vert\$\rangle$, and confirming


Although I find the knots paper, aided by Farhi's exposition, to be quite accessible, enter the recent paper "Quantum Money from Modular Forms," by Daniel Kane. For me modular forms are much more intimidating than knots; however Kane's exposition is very good and I can see some general relation to the previous work on knots.

Nonetheless, I'm getting hung up on section 3.2 onward. I'm wondering how much of a dictionary we can have between the knots work and modular forms.

That is, I know we can say something like there are $d!\times[\frac{d!}{e}]$ grid diagrams of grid dimension $d$, and a uniform superposition of grid diagrams all with the same Alexander polynomial is an eigenstate of a Markov chain of Cromwell moves; not only that, the Markov chain can be made doubly stochastic and easy to apply, and the Alexander polynomial is efficient to calculate.

Does it even make sense to say something roughly as in "there are $\lfloor N/12\rfloor$ cusp modular forms of weight $2$ and level $N$, and a uniform superposition of modular forms all with a same number of ideal classes is an eigenstate of a Hecke operator; not only that, the Hecke operator is Hermitian and easy to apply and the number of ideal classes is efficient to calculate?"

Have I gotten off track?

Has the Isbell–Freyd criterion ever been used to check that a category is concretisable?

Math Overflow Recent Questions - Sun, 03/03/2019 - 15:01

Isbell gave, in Two set-theoretic theorems in categories (1964), a necessary criterion for categories to be concretisable (i.e. to admit some faithful functor into sets). Freyd, in Concreteness (1973), showed that Isbell’s criterion is also sufficient.

My question is: Has anyone ever used Isbell’s criterion to check that a category is concretisable?

I’m interested not only in seeing the theorem is formally invoked in print, to show some category is concretisable — though of course that would be a perfect answer, if it’s happened. What I’m also interested in, and suspect is more likely to have occurred, is if anyone’s found the criterion useful as a heuristic for checking whether a category is concretisable, in a situation where one wants it to be concrete but finding a suitable functor is not totally trivial. (I’m imagining a situation similar to the adjoint functor theorems: they give very useful quick heuristics for guessing whether adjoints exist, but if they suggest an adjoint does exist, usually there’s an explicit construction as well, so they’re used as heuristics much more often than they’re formally invoked in print.)

What I’m not so interested in is uses of the criterion to confirm that an expected non-concretisable category is indeed non-concretisable — I’m after cases where it’s used in expectation of a positive answer.

Classification of algebras of finite global dimension via determinants of certain 0-1-matrices

Math Overflow Recent Questions - Sun, 03/03/2019 - 08:16

I restrict to the elementary problem that is equivalent to give a classification when Morita-Nakayama algebras have finite global dimension (see the end of this post for some background).

A Morita-Nakayama algebra is a tuple $(w,v)$, where $v$ is a non-zero $n$-vector with entries either 0 or 1 and $w$ is a natural number with $2 \leq w \leq n$. We say that two such Morita-Nakayama algebras $(w_1,v_1)$ and $(w_2,v_2)$ are isomorphic in case $w_1=w_2$ and $v_1$ is a cyclic shift of $v_2$. The size $r$ of $v$ is the number of non-zero entries of $v$ and let $x_i$ for $i=1,2,..,r$ be the position of the $i$-th non-zero entry in $v$. For example $[0,1,0,1]$ has size 2 and $x_1=2 , x_2=4$.

Let $T=(w,v)$ be a Morita-Nakayama algebra. We associate 3 matrices to $T$. The first $n \times n$ matrix $A_T=(a_{i,j})$ is defined as follows: We have $a_{i,j}=1$ for $j=i,i+1,...,i+w-1$ modulo $n$ and $a_{i,j}=0$ else.

The second $n \times r$ matrix $B_T$ is defined as having as $l$-th column the 0-1-vector with a 1 in position $x_l$ and zeros else.

The third $r \times n$ matrix $C_T=(c_{i,j})$ is defined by $c_{i,j}=1$, if $j=x_i+w-1$ modulo $n$ and $c_{i,j}=0$ else.

The Cartan matrix $M_T$ of $T$ is then defined as the $(n+r) \times (n+r)$ matrix $M_T:= \left[\begin{matrix} A_T & B_T \\C_T & E_r\end{matrix}\right]$. Here $E_r$ is the identity $r \times r$-matrix.

In general one has $det(M_t)=det(A_T - B_T C_T)$ ,see for example , so the problem to calculate the determinant of $M_T$ is reduced to the calculation of a determinant of an $n \times n$ 0-1-matrix of the form $A_T - B_T C_T$.

Here an example: Let $n=4, w=3$ and $v=[0,1,0,1]$. Then $A_T=\left[\begin{matrix}1 & 1 & 1 & 0\\0 & 1 &1 &1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1\end{matrix}\right]$, $B_T=\left[\begin{matrix} 0 & 0 \\ 1 & 0 \\ 0 & 0 \\ 0 & 1\end{matrix}\right]$ and $C_T=\left[\begin{matrix} 0 & 0 & 0 & 1\\ 0 & 1 & 0 &0 \end{matrix}\right]$. One can check that in this case $M_T$ has determinant equal to one.

We say that $T=(w,v)$ has finite global dimension in case $M_T$ has determinant equal to one. Note that the determinant of $M_T$ is always positive and thus this is equivalent to the condition that $M_T$ is invertible over $\mathbb{Z}$.

Questions: 1. Is there a nice condition/classification when $T=(w,v)$ has finite global dimension for a given $w$? Is there a closed formula for the determinant of $M_T$ in general?

  1. How many such tuples of finite global dimension exist for a given $n$ up to isomorphism?

Here are some partial results:

-For general $v$ and $w=2$ all tuples have finite global dimension and thus we can assume $w>2$.

-For $w>2$ and $v$ having size 1, $(w,v)$ has finite global dimension if and only if $w$ divides $n+1$.

-For $w=n \geq 3$, the only $v$ with finite global dimension are those with exactly one 0 as an entry.

-For $n \geq 5$ and $w=n-1$, there seem to be no $v$ with finite global dimension.

-For $w=3$ the problem seems already more complicated. Here is the list of $v$ for $n=6$ up to isomorphism where the global dimension is finite: [ [ 0, 0, 0, 0, 1, 1 ], [ 0, 0, 0, 1, 0, 1 ], [ 0, 0, 1, 0, 1, 1 ], [ 0, 0, 1, 1, 0, 1 ], [ 0, 1, 0, 1, 0, 1 ], [ 0, 1, 0, 1, 1, 1 ], [ 0, 1, 1, 0, 1, 1 ], [ 0, 1, 1, 1, 1, 1 ] ]

I did not really calculate determinants since I had linear algebra many years ago, so I am not very experienced. Maybe this problem has an easy solution that I miss.

Partial solutions would also be interesting, for example the case $w=3$ in general or a general solution for vectors $v$ having size 2.

Background: I noted that the classification of Morita-Nakayama algebras (=Nakayama algebras that are also Morita algebras in the sense of ) with finite global dimension reduces to a nice problem on determinants of 0-1-matrices using a derived equivalence together with the main result in that the global dimension of such algebras is finite iff their Cartan determinant is equal to one.

The tuple $T=(w,v)$ corresponds to a selfinjective Nakayama algebra algebra $A$ with Loewy length $w$ and the generator $N=A \oplus e_{x_1} J^{w-1} \oplus ... \oplus e_{x_r} J^{w-1}$ when $J$ is the Jacobson radical of $A$. The matrix $M_T$ is then the Cartan matrix of $B=End_A(M)$.

edit: I made a bounty for this question. In case there is no complete answer at the end of the bounty period, I can also award it for some interesting special cases like $w=3$ or $v$ having exactly two non-zero entries.

Birthday problem extension to unequal probabilities and multiple collisions

Math Overflow Recent Questions - Sat, 03/02/2019 - 15:46

Let $p_1, ... ,p_k$ denote the probabilities of drawing bin $1, .. ,k$, where $\sum_{i = 1}^{k} p_i= 1$. My question is if we draw $n$ times, how can I show that the probability that all bins are drawn less than $C$ times is maximized by $p_1 = p_2 = ... = p_k = 1/k$ ?

I've tried using conditional probability to solve inductively such as assuming bin $i$ is drawn $<C$ times and trying to reason about the remaining $k-1$, but no luck so far. Computing explicitly seems to be really difficult.

Calculate Kodaira dimension of a singular hypersurface

Math Overflow Recent Questions - Sat, 03/02/2019 - 09:21

For a smooth projective hypersurface $H \subseteq \mathbb{P}^n$ of degree $d$ one can calculate its Kodaira dimension $\kappa(H)$, and find $$\kappa(H) = \begin{cases} -\infty \qquad &\mbox{if } d < n +1,\\ 0 &\mbox{if } d = n+1,\\ \dim H &\mbox{if } d > n+1. \end{cases}$$

What about if $H$ is not smooth? Can we say anything about its Kodaira dimension, or even sensibly calculate something we can call the ''Kodaira dimension''?

I've only ever seen canonical divisors defined over smooth varieties, so am unsure how to proceed in the singular case.

Mathematical Theory accomodating / tolerating both axiom of regularity and its negation

Math Overflow Recent Questions - Sat, 03/02/2019 - 07:29

Is there a 'set theory' or any other theory in mathematics that accommodates or tolerates both well-founded and non-well-founded relations, thus, accommodates both well-founded sets (sets with no infinite descending membership sequence i.e., accepting axiom of regularity) and non-well-founded sets (finite descending membership sequence on the basis of negation of axiom of regularity) simultaneously?

Conjugates of minimal parabolic subgroups for relative semisimple rank 1 reductive groups

Math Overflow Recent Questions - Sat, 03/02/2019 - 07:13

Let $G$ be a connected reductive algebraic group over a field $k$, $S$ be a maximal $k$-split torus of $G$, $Z$ (resp. $N$) be the normalizer (resp. centralizer) of $S$ in $G$, and $W=N/Z$ be the Weyl group. Assume that $G$ has relative semisimple rank 1 so that $W=\{1,s\}$ and let $B=ZU$ be a minimal parabolic subgroup of $G$ containing $S$.

Now my question is the following. Does every conjugate of $B$ apart from $B$ and $sBs$ (i.e. those conjugates of the form $\overline{u}B\overline{u}^{-1}$ for some $\overline{u} \in \overline{U}(k) \backslash \{1\}$ where $\overline{U}$ is the unipotent radical of the opposite parabolic subgroup) contains a representative of $s$?

I am interested in the case where $k$ is a local field, but this is maybe just a question about Tits systems.

Compatible algebraic Spanier-Whitehead duality

Math Overflow Recent Questions - Sat, 03/02/2019 - 05:47

Let me first ask an intuitive version of the question:

Let $Sp$ be the homotopy category of spectra. Let $E$ be a ring spectrum. Let $$D:Sp \to Sp$$ be the Spanier-Whitehead dual functor (maybe we need to restrict ourselves to compact object and that's fine). I want to define an algebraic Spanier-Whitehead duality functor $$ D_E: E_*E\text{-}coMod \to E_*E\text{-}coMod $$ such that it commutes with the $E$-hurewicz map $h_E$, i.e. $$ h_E \circ D = D_E \circ h_E $$.

The question under what conditions on $E$ there exists $D_E$? For example, when $E = H\mathbb{F}_p$ we know that $D_E = Hom_{\mathbb{F}_2}(M, \mathbb{F}_2)$.

Now let me make this question a little more precise. Maybe we need to replace $E_*E\text{-}coMod$ with finite objects in its derived category.

My gut feeling says, that if $E$ satisfies

  1. Flatness: $E_*E$ is flat over $E_*$,
  2. Adams Condition: Check out Definition 3.1, pg 16 of

then it might just be enough to construct $D_E$. Is it though? If so can someone sketch a proof? If not do I need additional conditions?

So now the question is how to define dual objects in the (derived) category of $E_*E$ comodule and under what conditions on $E$ is it compatible with the Hurewicz map.

Who first drew attention to the duality theory for finite groups?

Math Overflow Recent Questions - Sat, 03/02/2019 - 05:27

A.A.Kirillov in section 12.3 of his "Elements of the Theory of Representations" writes that the first "symmetric" duality theory for non-commutative groups was the theory for finite groups. In short what he writes can be explained as follows: the operation $G\mapsto{\mathbb C}_G$ that assigns to each finite group $G$ its group algebra ${\mathbb C}_G$ over ${\mathbb C}$, embeds the category of all finite groups into the category of finite dimensional Hopf algebras, so that the Pontryagin duality functor $G\mapsto\widehat{G}$ (for Abelian finite groups) turns into the operation $H\mapsto H^{*}$ of taking the dual vector space (which is a duality functor in the category of finite dimensional Hopf algebras).

This observation is used as a key example in different modern duality theories. I wonder

who first noticed this?

Kirillov does not specify this.

Reference on complex cobordism

Math Overflow Recent Questions - Sat, 03/02/2019 - 04:00

I am trying to study a little of algebraic cobordism and I lack background from the classic setting. Hence, I am looking for a textbook or expository writing covering the basics of complex cobordism.

Do you know any suitable reference for the basics of complex cobordism?

If possible, I would like the reference to cover a particular result. Let $E$ be a spectrum representing a cohomology theory and $MU$ the spectrum representing complex cobordism. As an analogy with the algebraic case, it should hold that $$ E^*(MU)\simeq E^*(pt)[[c_1,c_2, \ldots]] $$ where $c_i$ are the universal Chern classes. In other words, $E^*(MU)\simeq E^*(Gr)$ where $Gr$ denotes the infinite Grassmanian. If possible, I would like the reference to cover such result and its surroundings.

On infinite combinatorics of ultrafilters

Math Overflow Recent Questions - Sat, 03/02/2019 - 03:56

Let $\mathcal{U}$ be (selective) ultrafilter and $\omega = \coprod_{i<\omega}S_i$ be partition of $\omega$ with small sets $S_i\notin\mathcal{U}$. All $S_i$ are infinite. Does there exist a system of bijections $\varphi_i:\omega\to S_i$ such that for any big set $B\in\mathcal{U}$ and any system of big sets $\{B_i\}_{i\in B}$ the set $\cup_{i\in B}\varphi_i(B_i)$ is big?

Is residual finiteness a quasi isometry invariant for f.g. groups?

Math Overflow Recent Questions - Sat, 03/02/2019 - 03:48

A "residually finite group" is group for which the intersection of all finite index subgroups is trivial. Suppose $G$ and $G'$ are two quasi-isometric finitely generated groups. Does the residual finiteness of $G$ implies the same property for $G'$?

About integral of a convergent sequence

Math Overflow Recent Questions - Sat, 03/02/2019 - 03:47

Let $\{f_n:[a,b]\to\mathbb{R}\}$ an a.e. convergent sequence to $f$. That is, we know that for every $x$ we have $\lim_{n\to\infty}f_n(x)=f(x)$ a.e.

If $f_n$ and $f$ are integrables,is it true that $\int_a^b\lim f_n(x)dx=\int_a^bf(x)dx$?

Please, note that this is not "a question" about $\int_a^b\lim f_n(x)dx=\lim\int_a^b f_n(x)dx$.

Are two "perfectly dense" hypergraphs on $\mathbb{N}$ necessarily isomorphic?

Math Overflow Recent Questions - Sat, 03/02/2019 - 02:19

We say that a hypergraph $(\mathbb{N}, E)$ where $E\subseteq {\cal P}(\mathbb N)$ is perfectly dense if

  1. $\mathbb{N}\notin E$,
  2. all $e\in E$ are infinite,
  3. $e_1, e_2 \in E$ implies $|e_1\cap e_2| = 1$, and
  4. for all $m\neq n\in \mathbb{N}$ there is $e\in E$ such that $\{m,n\}\subseteq e$.

If $(\mathbb{N}, E_i)$ are perfectly dense for $i=1,2$, are these hypergraphs necessarily isomorphic? If not, how large can a collection of perfectly dense, pairwise non-isomorphic hypergraphs be?

(Will also accept posts answering the first question only, but I am curious about the second, too.)

For each $n$ is it possible to have $\mathrm{crit}(x^{[n]}*y)>\mathrm{crit}(x^{[n-1]}*y)>\dots>\mathrm{crit}(x*y)$?

Math Overflow Recent Questions - Fri, 03/01/2019 - 22:14

Suppose that $(X,*,1)$ satisfies the following identities: $x*(y*z)=(x*y)*(x*z),1*x=x,x*1=1$. Define the Fibonacci terms $t_{n}(x,y)$ for $n\geq 1$ by letting $$t_{1}(x,y)=y,t_{2}(x,y)=x,t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$$ for $n\geq 1$. We say that $(X,*,1)$ is permutative if for each $x,y\in X$, there is some $n$ where $t_{n}(x,y)=1$. If $(X,*,1)$ is permutative, then we say that $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ if there is some $n\geq 0$ where $x^{n}*y=1$ where we define $x^{0}*y=y$ and $x^{n+1}*y=x*(x^{n}*y)$. We say $\mathrm{crit}(x)=\mathrm{crit}(y)$ if $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ and $\mathrm{crit}(y)\leq\mathrm{crit}(x)$ and $\mathrm{crit}(x)<\mathrm{crit}(y)$ if $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ and $\mathrm{crit}(x)\neq\mathrm{crit}(y)$. The ordering $\{\mathrm{crit}(x)\mid x\in X\}$ is always a linear ordering.

Define $x^{[1]}=x$ and $x^{[n+1]}=x*x^{[n]}$ for $n\geq 1$. Then it is easy to show that $x^{[n+1]}=x^{[n]}*x^{[n]}$ for all $n\geq 1$.

Suppose that $n$ is a natural number. Then does there exist a permutative algebra $(X,*,1)$ along with some $x,y\in X$ where $$\mathrm{crit}(x*y)<\mathrm{crit}(x^{[2]}*y)<\dots<\mathrm{crit}(x^{[n]}*y)?$$ What if we also require $(X,*,1)$ to be finite?

$\textbf{Remark:}$ From an affirmative answer, we can easily conclude that the free self-distributive algebra on arbitrary number of generators embeds into an inverse limit of finite self-distributive algebras, a fact whose only known proof requires very large cardinals. However, permutative algebras $(X,*,1)$ where $\mathrm{crit}(x*y)<\mathrm{crit}((x*x)*y)$ cannot arise from large cardinals.

Is $PSL(2,13)$ a chief factor of the automorphism group of a $\{2,3\}$-group?

Math Overflow Recent Questions - Fri, 03/01/2019 - 22:08

Does there exists a group $H$ of order $2^7\cdot 3^4$, such that $\mathrm{PSL}(2, 13)$ is a chief factor of $\mathrm{Aut}(H)$?

Groups acting on trees

Math Overflow Recent Questions - Fri, 03/01/2019 - 15:54

Assume that X is a tree such that every vertex has infinite degree. And a discrete group G acts on this tree properly (with finite stabilizers) and transitively. Is it true that G contains a non- abelian free subgroup?

Does the symmetric group $S_{10}$ factor as a knit product of symmetric subgroups $S_6$ and $S_7$?

Math Overflow Recent Questions - Fri, 03/01/2019 - 15:05

By knit product (alias: Zappa-Szép product), I mean a product $AB$ of subgroups for which $A\cap B=1$. In particular, note that neither subgroup is required to be normal, thus making this a generalization of the semidirect product.

Synopsis of questions (in order):

(1) Can someone provide subgroups $A,B$ of $S_{10}$ for which $S_{10}=AB$, $A\cong S_6$, and $B\cong S_7$? (Note that by cardinality considerations, necessarily $A\cap B=1$ if this happens, in which case $S_{10}$ really is the knit product of the two.)

(2) Can it be proven, without a computer exhaust, that $S_{10}$ does not have such a decomposition?

(3) How would one go about, with a computer exhaust, showing $S_{10}$ does not have such a decomposition? This has as a subquestion: how would we know we captured all the weird ways each $S_k$ with $k=6,7$ embeds as a subgroup of $S_{10}$?

For reference, this is similar to the question here, but even there it was pointed out there were additional ways the embeddings could occur.

History: Once upon a time (i.e., a number of years ago), I was contemplating ways one could factor a symmetric group $S_n$ as a knit product of two symmetric subgroups $A\cong S_a$ and $B\cong S_b$ with positive integers $a,b$. Obviously, a necessary condition for this to happen is that $n! = a!b!$, so a natural question to ask is the corresponding number theory problem: when is it possible to write $c!$ as a product $a!b!$ ? Via computer runs, I quickly discovered two infinite families (breaking the symmetry between $a$ and $b$, I'll only write triples with $a\leq b$), which are $(a,b,c) = (1,n,n)$ over integers $n\geq 1$ and $(a,b,c)=(n,n!-1,n!)$ over integers $n\geq 3$, and an outlier example $(a,b,c)=(6,7,10)$.

Returning these examples to the motivating group theory question, the first family obviously corresponds to the (extremely trivial) product of $1=S_1$ and $S_n$. Meanwhile, a Frattini argument applied to the right regular action of $S_n$ on itself can be used to show $\mathrm{Sym}(S_n)$ is the knit product of $\mathrm{Sym}(S_n\smallsetminus \langle1\rangle)$ with the group $H$ which is the image of the Cayley embedding $S_n\hookrightarrow\textrm{Sym}(S_n)$. This then yields the second family of factorizations.

All of this leads to the question: is there a factorization of $S_{10}$ as a product of $S_6$ and $S_7$, thus providing group theoretic reason for the triple $(6,7,10)$? I seem to recall, but cannot find the e-mail, that a friend of mine did a computer run to verify there is no copy-of-$S_6$, copy-of-$S_7$ pair for which the product is $S_{10}$ and which intersect trivially.

If I'm wrong in my recollection, and there does exist a decomposition of $S_{10}$ as a knit product of a copy-of-$S_6$ times a copy-of-$S_7$, I would appreciate enough details to be convinced it is true, including knowledge about which copy of each $S_k$ is being considered (e.g., generating set of the $S_k$-copy, or a monomorphism $S_k\rightarrow S_{10}$).

If I do recall correctly that there is no such factorization, then can someone provide a proof of that fact (directly or via reference)?

Barring the first being true and the second being fulfilled, my fallback position is that I would like to reproduce that computation for myself, except I don't have a solid feel for how many different ways each $S_k$, $k=6,7$ can embed into $S_{10}$. Therefore, a necessary step in an algorithmic process is coming up with a full list of copies-of-$S_k$.

Likely the best way to gather that information would be to provide a representative for each conjugacy class. (If there is a better way to perform the computation, I am all ears.)

As to the conjugacy classes of which I am aware:

$\bullet$ The symmetric groups that move exactly $k$ letters among the $10$ letters are the conjugates of the usual subgroup interpretation of $S_k$.

$\bullet$ There is, generally speaking, an embedding $S_k$ into $A_{k+2}$ given by mapping members of $A_k$ to themselves and mapping $\sigma(1\;2)$ in the coset $A_k(1\;2)$ to $\sigma(1\;2)(k+1\;k+2)$. This yields the conjugacy class representative $A_k\cup \bigl(A_k(1\;2)(k+1\;k+2)\bigr)$.

As an aside for anyone who might be interested, while I have been given reason to believe $10! = 6!7!$ does not come up as a symmetric group factorization (via the aforementioned, now lost e-mail), it does come up as a permutation group factorization. Via a Frattini argument applied to the sharply $3$-transitive action of the Mathieu group $M_{10}$ on $10$ letters, the symmetric group $S_{10}$ is the knit product of $S_7$ and $M_{10}$, and $|M_{10}|=720=6!$. This makes me think that the sporadic example really is sporadic, in that it (likely) arises through similar ``happy accidents'' of small numbers that allows $A_6$ to have nontrivial outer automorphisms. I am very curious if the two families and this sporadic example really do represent the only solutions $(a,b,c)$ to $c!=a!b!$, but even if true a proof of that fact is not likely to materialize any time soon.

On Total Coloring of Regular graphs

Math Overflow Recent Questions - Fri, 03/01/2019 - 10:22

Consider a regular graph of order $n$ and degree $\Delta$. Now, by Brooks' theorem, we can partition the vertices into at least $\Delta+1$ independent sets and at most $\frac{n}{2}$ independent sets. The extreme case of $n$ independent sets is only for complete graphs and would be a degenerate case. Now, to perform total coloring, we need to partition the edge sets independently of the vertices. Now, this is accomplished by expanding the already partitioned set of vertices by adding disjoint edge elements which are in turn disjoint from the vertices. After adding the maximum possible number of such edge elements, we partition the remaining edge elements into independent sets. Now, if we are able to prove that the sum total of the totally indepndent sets is less than $\Delta+2$, the total coloring conjecture is proved.

Can we use the fact that when we partition the edge elements, we are actually forming disjoint pair of all the vertices such that sum of such pairs is $n\frac{\Delta}{2}$ in the above construction of total independent sets? Maybe this would help simplify the construction. Any light on this approach? Thanks beforehand.


Subscribe to curious little things aggregator