User salvo tringali - MathOverflow

Applications of Riesz's lemma for the unit ball

2013-04-21T17:33:43Z

I should give a talk on something I'm working on, and I'd like to have a list, as complete as possible, of applications, in and out of functional analysis, of the following classical result by F. Riesz:

Riesz's lemma. Let $\mathcal V = (\mathbb V, \|\cdot\|)$ be a normed space over the normed field, $\mathcal K = (\mathbb K, |\cdot|)$, of real/complex numbers, $W$ a closed proper subspace of $\mathcal V$, and $\delta$ a real number with $0 < \delta < 1$. There then exists $x \in \mathcal V$ with $\|x\| = 1$ such that $\|x - y\| \ge \delta$ for all $y \in W$.

Classical applications of which I'm already aware:

That the unit ball of a real/complex normed space $\mathcal V$ is compact iff $\mathcal V$ is finite-dimensional.
The non-existence of certain measures for infinite-dimensional normed spaces.
The spectral theorem for compact operators on a (complex) Banach space.

By the way, where can I find some focused discussion on the 2nd point of the above list? It seems to me that I read an excellent paper on the topic, some time ago, but I can't remember either the author(s), the journal, or other useful details, and I've started thinking that I dreamed of it.

Thanks in advance.

Answer by Salvo Tringali for problem related to airy function

2013-04-09T21:57:50Z

The Airy function can be expressed in terms of a modified Bessel function of the 2nd kind; this amounts to Exercise 20, Ch. IV of Andrews, Askey and Roy's red book on special functions (for which the authors refer the reader to Watson's 1944 treatise on Bessel functions), and an asymptotic formula for modified Bessel functions of the 1st and 2nd kind is given on p. 223 (ed. 1999).

Answer by Salvo Tringali for Minimal size of subsets $A,B$ in a finite group $G$ such that $AB=G$

2013-04-09T12:34:54Z

I don't know how interesting my answer can be after a comment by Ben Green, but this would be too long for a comment, and I hope it can be helpful, somehow.

Your question is tightly related to the behavior of a function first introduced, afaik, by the late M. Kervaire, and studied to some extent by the same author (and his students) and A. Plagne (and his students); see, e.g., the references in É. Balandraud, The isoperimetric method in non-abelian groups with an application to optimally small sumsets, IJNT, Vol. 4, No. 6 (2008), 927-958. To wit, for a group $\mathbb G$ let $\mu_\mathbb{G}$ be the function

$\mathbb N^2 \to \mathbb N \cup \{\infty\}: (s,t) \mapsto \min\{|AB|: A, B \in\mathcal P(\mathbb G), |A| = s, |B| = t\}$.

Now, if $\mathbb G_1, \mathbb G_2, \ldots$ is a sequence of finite groups with $|\mathbb G_n| = n$ for each $n$, your question does essentially refer, if I'm not missing anything, to the asymptotic behavior of the restriction of $\mu_n := \mu_{\mathbb G_n}$ to a subset $S_n \times T_n$ of $\mathbb N^2$ such that $\min(S_n, T_n) = O(1) + \sqrt{n}$ and $\max(S_n, T_n)= O(1) + \sqrt{n}$ for $n \to \infty$, for which you'd like to have $\mu_n(S_n,T_n) = n$ for all sufficiently large $n$, and "uniformly" with respect to the actual choice of the sequences $(S_n)_{n \in \mathbb N}$ and $(T_n)_{n \in \mathbb N}$.

This in turn has a seemingly intimate, but still unclear relation with the classical Cauchy-Davenport theorem and its generalizations, which is something that I myself am trying to investigate with the aid of Alain and Éric.

Edit. As pointed out by quid in the comments below, it is better, with respect to the question raised by the OP, to re-write the above in terms of the "dual" of $\mu_\mathbb{G}$, namely the function

${\rm M}_\mathbb{G}: \mathbb N^2 \to \mathbb N: (s,t) \mapsto \max\{|AB|: A, B \in\mathcal P(\mathbb G), |A| = s, |B| = t\}$.

But now you would rather check out if, for a certain sequence $\mathbb G_1, \mathbb G_2, \ldots$ of groups, it holds $\limsup_n (n - \max_{s \in S_n, t \in T_n} {\rm M}_{\mathbb G}(s,t)) \ne 0$, "uniformly" with respect to $(S_n)_{n \in \mathbb N}$ and $(T_n)_{n \in \mathbb N}$.

Answer by Salvo Tringali for Elementary cases of Mihailescu theorem

2013-04-08T14:02:55Z

Of course, you can just consider the case when $p$ and $q$ are primes. A good reference for your question is, I think, Schoof's monograph on Catalan's equation. The case $q = 2$ is solved in Ch. II, and it involves some arithmetic in the ring of Gaussian integers (the argument goes back to V.A. Lebesgue). The case $p = 2$ is discussed in Chs III, for $q \ge 5$ (basic algebra in the ring $\mathbb Z[\sqrt{y}]$), and IV, for $q = 3$ (some arithemtic in the ring $\mathbb Z[\sqrt[3]{2}]$): This is just a little bit more laborious than the case $q = 2$, but still rather "elementary". In the appendix, you can also find Euler's original proof for $(p,q) = (2,3)$, which is essentially based on the same descent argument, though in a disguised form, used to prove that the group of rational points on the elliptic curve $x^2-y^3=1$ is finite and has order $6$. Some others of your cases follow at once from Cassel's theorem (Ch. VI), whose proof in the book relies on Runge's method (Ch. V).

"Augmenting" a category by an associative binary operation

2013-04-06T20:45:23Z

Let ${\bf C}$ be a category, and $\zeta$ an associative binary operation on a set $I$. Define a $5$-tuple $(D_o,D_h,u,v,d)$ as follows: $D_o$ is just the object class of $\bf C$, while $D_h$ is the quotient of $\coprod_{i \in I} \hom({\bf C})$ by the equivalence $\mathcal R$ that amalgamates two pairs $(f,i)$ and $(g,j)$ iff $f=g={\rm id}_{\bf C}(A)$ for some $A \in {\rm Ob}({\bf C})$; $u$ and $v$ are the functions $D_h \to D_o$ taking the equivalence class $(f,i) \bmod \mathcal R$ to $s(f)$ and $t(f)$, respectively; and $d$ is the mapping $D_h \times_{v,u} D_h \to D_h$ sending a pair $((f,i)\bmod \mathcal R,(g,j) \bmod \mathcal R)$ to $(f,i) \bmod \mathcal R$, respectively to $(g,j) \bmod \mathcal R$ , if $g$, respectively $f$, is an identity of $\bf C$, and to $(fg,\zeta(i,j)) \bmod \mathcal R$ otherwise.

It is clear that $(D_o,D_h,u,v,d)$ is a category, let me denote it by $\zeta \ast \bf C$. Since I don't know if $\zeta \ast \bf C$ has already a name, I'm calling it the augmentation of $\bf C$ by $\zeta$: While looking forward to finding something more "natural", I'm using it as a toy example in reference to the idea of a generalized notion of limit which, on the one hand, can make sense in more abstract settings than categories (e.g., Mitchell's semicategories, or even Ehresmann's neocategories [1]), and on the other hand, may perhaps be an effective surrogate of limits in situations where limits do not exist and neither weak limits nor sublimits (see note 2) are likely to represent, for some reason, a satisfactory alternative. So, here are my questions:

Q1. Is $\zeta \ast \bf C$, up to equivalence, a disguised form/a special instance of anything familiar to you? Q2. Does it satisfy any "obvious" universal property? Q3. Is it maybe a particular colimit (see note 2)?

Thanks in advance, as always, for any hint.

Notes. (1) Sublimits are the same as weak limits, save for the fact that we replace "at least" with "at most". (2) Say, as an object of ${\bf Cat}(\mathcal U)$, for a sufficiently large universe $\mathcal U$.

Bibliography.

[1] A. Bastiani and C. Ehresmann, Categories of sketched structures, Cahiers Topologie Géom. Différ. Catégoriques, Vol. 13, No. 2 (1972), 104-214.

Embedding a semigroup into a divisible semigroup

2013-04-04T10:40:51Z

The following is motivated by the fact that I'd like to have a way, much better if canonical, to isometrically embed a normed group into a normed divisible group. But semigroups are a much more natural setting for posing the question.

Q1. What is known about the embeddability of a (possibly non-commutative) semigroup into a divisible semigroup? Q2. What are some relevant references for the question?

EDIT (05/04/2013). As pointed out by Benjamin Steinberg below, that every semigroup can be embedded into a divisible semigroup was proved by B.H. Neumann; see [1, Theorem 6.2] and [2, Sect. 3]. However, I'm not really happy with Neumann's construction, and this is why I'd like to add the following:

Q3. Is there a functorial way to embed an arbitrary semigroup into a divisible semigroup?

On a related note:

Q4. What is known about the existence of adjoints to the inclusion of $\bf DivSgrp$ into $\bf Sgrp$?

Here, $\bf Sgrp$ is the usual cat of small semigroups (say, with respect to a fixed universe $\mathcal U$, in TG), and $\bf DivSgrp$ the full subcat of $\bf Sgrp$ of divisible semigroups. Feel free to switch questions from semigroups to groups if answers are known for the latter (since then it is likely that they can be adapted to the former).

Thanks in advance for any hint.

References.

[1] B.H. Neumann, Adjunction of elements to groups, JLMS, 18 (1943), 4-11.

[2] B.H. Neumann, Some remarks on semigroup presentations, Canad. J. Math., 19 (1967), 1018–1026.

On the existence of certain seminormed groups

2013-03-25T15:00:43Z

Let us define a seminormed group as a triple $\mathcal G = (\mathbb G, \|\cdot\|, \phi)$ consisting of a group $\mathbb G$, a function $\|\cdot\|: \mathbb G \to \mathbb R_0^+$, here termed a (group) seminorm (on $\mathbb G$), and a homomorphism $\phi$ of monoids with zero from $(\mathbb Q, \cdot)$ to $(\mathbb R_0^+, \cdot)$, here called a "monoidal absolute value", such that $\|x+y\| \le \|x\| + \|y\|$ for $x,y \in \mathbb G$ and $\|nx\| = \phi(n) \cdot \|x\|$ for $n \in \mathbb Z$ and $x \in \mathbb G$. Note that $\phi(-n) = \phi(n)$ for all $n \in \mathbb Z$, while $\phi(n) \le |n|$ unless $\|\cdot\|$ is identically zero.

Now, while Ostrowski's theorem tells us that there are, in some sense, "few" absolute values on the rational field, and proves that, up to a certain equivalence, just one of these has dense range, things are quite, quite different for monoidal absolute values (after all, we are almost completely disregarding the additive structure of $\mathbb Q$).

In particular, if $\mathcal W = (w_p)_{p \in \mathbb P}$ is a set of real "weights" indexed by the primes $\mathbb P$, it is clear that the function $\phi_\mathcal{W}: \mathbb Q \to \mathbb R_0^+$ defined by $\phi_\mathcal{W}(0) := 0$ and $\phi_\mathcal{W}(q) := \prod_p 2^{w_p e_p(q)}$ for $q \in \mathbb Q \setminus \{0\}$ , where $e_p$ is the usual $p$-adic valuation on $\mathbb Q$, is a monoidal absolute value (yes, the base 2 in this definition has nothing special, and can be replaced by any other positive real number).

We say that $\mathcal W$ is a dense system of weights (shortly, DSW) if the function $\mathbb Q \setminus \{0\} \to \mathbb R: q \mapsto \sum_p w_p e_p(q)$ has dense range, in which case it is trivial to check that $\phi_\mathcal{W}(\mathbb Q)$ is dense. Example: $\mathcal W$ is a DSW if it is not eventually constant and $w_p \to 0$ as $p \to \infty$. Note that $\phi_\mathcal{W}$ includes the trivial absolute value and the $p$-adic absolute values as special cases, but neither of these has dense range. So here is my question:

Question. Does there exist any seminormed group of the form $\mathcal G = (\mathbb G, \|\cdot\|, \phi_\mathcal{W})$ for which $\mathcal W$ is a DSW?

On the divisibility of the special linear group of degree $n$ over an algebraically closed field

2013-03-21T10:12:19Z

Let $n$ be a positive integer, $p$ a (positive rational) prime, and $\mathbb K$ an algebraically closed field. If ${\rm char}(\mathbb K) = 0$ then ${\rm GL}_n(\mathbb K)$ is divisible (see here). But what about ${\rm SL}_n(\mathbb K)$? Again, the answer is negative if $\mathbb K$ has finite characteristic, and again we may assume that (i) our matrices are in Jordan normal form and (ii) $\mathbb K$ is the complex field, thanks to the Lefschetz principle and the fact that, by Laplace's formula, the determinant of an $n$-by-$n$ "formal matrix" can be expressed as a wff in the first-order language $\mathcal L = (+, \cdot, -, 0, 1)$ of (the theory of) rings. Thus, let us consider a Jordan matrix of size $n \times n$, say $J = {\rm diag}(J_1, \ldots, J_m)$, where $J_i$ is a Jordan block of size $k_i \times k_i$. If $\det(J) = 1$ and $p \nmid \gcd(k_1, \ldots, k_m)$, it is not difficult to prove that there exists $A \in {\rm SL}_n(\mathbb C)$ such that $A^p = J$.

Question 1. What about the other cases?

The problem should be well-known and I feel that the answer is in the negative, but so far I couldn't either get a reference or find a counterexample by myself. EDIT 2. The $2$-by-$2$ Jordan block with eigenvalue $-1$ is a counterexample, and in some sense it is the only one possible for $n = 2$ (see the comments below). Thus, it seems natural to ask the following:

Question 2. (i) Is there any "explicit characterization" of those matrices in ${\rm SL}_n(\mathbb C)$ which fail to have a $p$-th root for each prime $p$? (ii) In particular, is the set of these matrices the union of a finite number of conjugacy classes of ${\rm SL}_n(\mathbb C)$?

Let me rely on your common sense for the actual meaning to give to the expression "explicit characterization". Last but not least:

Question 3. Does anyone know where to find a reference for this kind of questions (concerned with the divisibility of specific subgroups of ${\rm GL}_n(\mathbb K)$ when $\mathbb K$ is an algebraically closed field, either in characteristic zero or not)?

Thanks in advance for any help.

Answer by Salvo Tringali for Non-abelian divisible groups

2013-03-21T10:20:51Z

One often reads that divisible groups are important since they help us understanding the structure of abelian groups, for they are all and the only injectives in the usual category of abelian groups (which is, of course, undeniable). Yet, I find that the non-abelian case is, if possible, even more interesting. A 'natural' example of a non-commutative divisible group is the group of units of Hamilton's quaternions; afak, the result is due to I. Niven [1]. On another hand, it was recently proved on this forum that the general linear group of degree $n$ over an algebraically closed field $\mathbb K$ is divisible iff $\mathbb K$ has zero characteristic (see here), and I've just posed a similar question for ${\rm SL}_n(\mathbb K)$ (see here)

[1] I. Niven, The Roots of a Quaternion, The Amer. Math. Monthly, Vol. 49, No. 6 (Jun. - Jul., 1942), pp. 386-388.

Answer by Salvo Tringali for Are there results in "Digit Theory"?

2013-03-21T10:57:53Z

I don't know if the following qualifies as an "interesting result" in "digit theory", but Carlo Sanna, a student from the Università di Torino, has recently published a paper in elementary number theory [1] which is concerned with properties relating arithmetic progressions and the sum-of-digit function (in an arbitrary base $b$): It includes a few references and a number of questions that you may find at least intruiging.

[1] Carlo Sanna, On Arithmetic Progressions of Integers with a Distinct Sum of Digits, Vol. 15 (2012), Article 12.8.1 (see here).

All and the only algebraically closed fields s.t. any regular n-by-n matrix has a k-th root for every k

2013-03-17T19:14:22Z

The title has it all. I'm looking for a proof/disproof of the fact that an algebraically closed field, say $\mathbb K$, has characteristic zero iff the following property (R) holds: For all $n,k \in \mathbb N^+$, every invertible $n$-by-$n$ matrix with entries in $\mathbb K$ has at least one $k$-th root. The question is certainly well-known, and boils down to the case of Jordan blocks. I myself have a sense, but not a proof, that it must have an answer in the positive. I'm not interested in the discussion of special cases (e.g., the complex case is quite standard, and can be treated even analytically), unless of course the inspection of a finite, small number of them leads to a general conclusion. In case of an affirmative answer, I'd appreciate much a reference to the result in its full generality. As for motivation, the question is 'naturally' related to another that I've recently posted. Thanks in advance for any help.

Extending Riesz' lemma to special classes of normed groups

2013-03-12T10:37:54Z

My question is related, and primarily motivated, by the other one that I've recently posted about the characterization of epimorphisms in the category of normed (left) modules (over a given normed ring) and bounded (module) homomorphisms. Now, I'd like to know if there are extensions of Riesz' lemma (on non-dense subspaces of a normed space over a fixed complete normed field), going in the direction, say, of replacing, on the one hand, "normed spaces" with objects of an appropriate subcategory $\bf G$ of the category of normed groups and bounded (group) homomorphisms, and on the other hand, "subspaces" with subobjects of $\bf G$. If yes, I'd appreciate much some references. Thanks in advance.

Epis in the semicat of normed modules over a normed ring

2013-03-08T10:02:06Z

EDIT. Let me try to improve the question and make it possibly more interesting.

It was mentioned in a previous thread (click me) that the epis of the (Mitchell's) semicat of real/complex normed spaces and compact (linear) operators are all and the only compact operators with dense range. My proof of this, which is essentially the same as the one given by @Martin in the comments to the other question, is based on (a well-known corollary of) the Hahn-Banach theorem. It's then "natural" to ask, as far as I'm concerned, if one can get rid of HB, particularly in view of the following:

Question. Is it true that [Is it known whether] the epis of the semicat of normed (left) modules over a fixed normed ring $\mathcal R = (R, |\cdot|)$ and compact ($R$-linear) operators are all and the only compact operators with dense range?

Here, a normed ring is, say, a (unital) commutative ring endowed with an absolute value; a normed (left) module over a normed ring is accordingly defined in the expected way.

Now, fix a normed ring $\mathcal R = (R, |\cdot|)$ and denote by ${\bf NMod}(\mathcal R)$ the category of normed (left) modules over $\mathcal R$ and bounded (module) homomorphisms between them, where source, target and composition are the obvious ones (I'm assuming that all structures are small wrt a given uncountable universe $\mathcal U$, in TG). There then exists a canonical faithful functor from ${\bf NMod}(\mathcal R)$ to the usual category ${\bf HausTop}$ of (small) Hausdorff spaces and continuous functions, which proves that every morphism of ${\bf NMod}(\mathcal R)$ with dense range is epic (for faithful functors reflect left/right cancellative arrows, and the epis of ${\bf HausTop}$ are well-known). And this would like to serve as a motivation for my question.

The point of view of semicats in functional analysis

2013-02-26T16:43:16Z

I'm completing a paper about (Mitchell's) semicats (well, not exactly, but let's say so for simplicity), and as a motivational example I'd like to mention at some point that the monic/epic morphisms of the semicat of real/complex normed spaces and (linear) compact operators between them (with the obvious source and target maps and the equally obvious composition) are exactly those that one is expected to get. So my question is:

Is there anything in the literature taking the point of view of semicats in the study of compact operators, in such a way that I can cite it (at least for the sake of comparison)?

Feel free to extend the same question to other objects of interest in functional analysis such as real/complex normed spaces and (strictly) contractive linear operators or (topological) pointed spaces and compactly supported base maps. I don't expect anything like Helemskii's Lectures and Exercises on Functional Analysis, but on the other hand I find it a little bit surprising that nobody has already tried to pursue this line of thought, and arguing that the reason for this "gap" may be due to the fact that "semicats are not really more general than cats", since "there exists a functorial way to turn them into a category", is just another instance of the principle of explosion.

Added later. [1] Loosely speaking, a semicat is a not-necessarily-unital category. For what it is worth, and to the best of my knowledge, the notion was first introduced by B. Mitchell in The dominion of Isbell, TAMS, Vol. 167 (1972), 319-331. [2] Monic and epic arrows in a semicat are defined in the very same way as monic and epic arrows in categories. [3] If necessary (though I don't think so): By a compact operator between $\mathcal K$-normed modules, where $\mathcal K = (\mathbb K, |\cdot|)$ is a normed rng (here, just a rng endowed with an absolute value), I mean a triple $f: \mathcal M_1 \to \mathcal M_2$ for which $\mathcal M_i = (\mathbb M_i, \|\cdot\|_i)$ is a normed (left) module over $\mathcal K$ and $f: \mathbb M_1 \to \mathbb M_2$ is a homomorphism of (left) $\mathbb K$-modules such that the image of any bounded subset of $\mathcal M_1$ under $f$ is relatively compact in $\mathcal M_2$.

On the notion of partial semigroup

2013-03-05T12:47:17Z

A partial binary operation on a set $X$ is just a (partial) function $\varphi: X \times X \rightharpoonup X$ (I'm using \rightharpoonup for partial maps), and a partial magma is a pair $\mathbb M = (M, \star)$ such that $M$ is a set and $\star$ is a partial binary operation on $M$ (I say that $\mathbb M$ is a magma if $\star$ is total). But what about partial semigroups? At least in principle, many alternative definitions are possible: The only thing I would take for certain is that a partial semigroup must be a partial magma $\mathbb M = (M, \star)$ for which $\star$ satisfies some kind of associativity, and of course I've my personal list. Specifically, I say that $\mathbb M$ is

(properly) associative if for all $x,y,z \in M$ such that $(x \star y) \star z$ and $x \star (y \star z)$ are defined, it holds $(x \star y) \star z = x \star (y \star z)$.
left pre-associative if for all $x,y,z \in M$ such that $x \star y$ and $y \star z$ is defined, it holds that "$(x \star y) \star z$ is defined" implies "$x \star (y \star z)$ is defined and $(x \star y) \star z = x \star (y \star z)$".
right pre-associative if the dual of $\mathbb M$ is left pre-associative.
pre-associative if it is both left and right pre-associative.
strongly associative if for all $x,y,z \in M$ it holds that "$x \star y$ and $y \star z$ are defined" implies "$(x \star y) \star z$ and $x \star (y \star z)$ are defined, and also $(x \star y) \star z = x \star (y \star z)$".
left dissociative if for all $x,y,z \in M$ it holds that "$(x \star y) \star z$ is defined" implies "$x \star (y \star z)$ is defined and $(x \star y) \star z = x \star (y \star z)$".
right dissociative if the dual of $\mathbb M$ is left dissociative.
dissociative if it is both left and right dissociative.

In this taxonomy (which doesn't aim to be complete by any means), "being (propertly) associative" corresponds to the weakest possible form of associativity, in the sense that it is implied by all the others. Moreover, all of the above properties collapse into each other if $\mathbb M$ is a magma. So, the (somewhat philosophical) question is:

What should a partial semigroup be? Do you envisage any "higher logic" advocating for one instead of another choice?

My own answer is that a partial semigroup should be a strongly associative partial magma, in the sense of the above condition 5. But, on the one hand this doesn't seem to be the "standard" definition in the literature (see, e.g., R.H. Schelp, A partial semigroup approach to partially ordered sets, Proc. London Math. Soc. (1972), s3-24 (1), 46-58, where partial semigroups are pre-associative partial magmas, in the sense of the above condition 4), and on the other hand I can't give myself a reason why this should be better or worse than something different (which bothers me much...).

The semicat of morphisms which are neither right nor left invertible

2013-03-01T16:35:18Z

Given a cat $\bf C$, the class $\mathcal{S}$ of all $\mathbf{C}$-morphisms that are neither left nor right invertible, generates a "genuine" subsemicat $\bf S$ of $\bf C$ (if necessary, see here for the relevant terminology), by which I mean that $\bf S$ is not, in general, a cat in its own right (even though, of course, it can in some cases). To my eyes, this gives another interesting example of a kind of "natural" structures encountered in the everyday practice which, on the other hand, fail to be categories in any (apparent) "natural" way. Then, I'd like to mention it at some point in my current work, all the more that it looks like "the" appropriate way to go for introducing other (and possibly more significant) notions like that of irreducible arrow (say, in the sense of Auslander and Reiten) or almost irreducible arrow (say, in the sense of Margolis and Steinberg). Note that similar considerations can be repeated for the class $\mathcal P$ of all $\bf C$-morphisms that are neither left nor right cancellative (which in turn don't ever generate a category). Then my questions are:

Q1. Is there any standard name for the class $\mathcal{S}$ and its members? Q2. Is there any standard name for the class $\mathcal{P}$ and its members? Q3. Is anybody aware of any paper, book, or whatever else taking a similar point of view for laying out (the rudiments of) an abstract theory of factorizations subsuming aspects of the factorization theory, say, of monoids (as presented, for instance, by Geroldinger and Halter-Kock in the first chapters of their book, though only in the commutative case)?

For the record, I'm referring to the elements of $\mathcal S$ as singular arrows and to the elements of $\mathcal P$ as promiscuous arrows, but I'm not very happy with either of these...

Generalizations and relative applications of Fekete's subadditive lemma

2012-06-08T14:08:47Z

Fekete's (subadditive) lemma takes its name from a 1923 paper by the Hungarian mathematician Michael Fekete [1]. A historical overview and references to (a couple of) generalizations and applications of the result are found in Steele's book on probability and combinatorial optimization [2, Section 1.10], where a special mention is made to the work of Pólya and Szegő on the structure of real sequences and series [3, Ch. 3, Sect. 1] and that of Hammersley [4], motivated by percolation theory, on subadditive functions, the continuous analogue of subadditive sequences, whose systematic study was initiated, as far as I know, by Hille and Phillips in the 1957 edition of their beautiful monograph on functional analysis and semigroups [5, Ch. VII]. The same Steele acknowledges that his own 1989 proof of Kingman's subadditive ergodic theorem [6], of which Birkoff's celebrated theorem is a corollary, was eventually inspired by Fekete's lemma. Now, my question is:

Can you point out further generalizations (and corresponding (interesting) applications) of Fekete's lemma?

Added later. Fekete's lemma can be used to prove that the limit occurring in the spectral radius formula does actually exist. And this counts (to me) as an (interesting) application.

Bibliography.

[1] M. Fekete (1923), Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten, Math. Zeit., Vol. 17, pp. 228-249.

[2] M.J. Steele, Probability theory and combinatorial optimization, SIAM, Philadelphia, 1997.

[3] G. Pólya and G. Szegő, Problems and Theorems in Analysis, Vol. I, Springer-Verlag, Berlin, 1998 (reprint of the 1978 Edition).

[4] J.M. Hammersley (1962), Generalization of the fundamental theorem of subadditive functions, Proc. Cambridge Philos. Soc., Vol. 58, pp. 235-238.

[5] E. Hille and R.S. Phillips, Functional analysis and semi-groups, American Math. Soc., 1996 (revised edition).

[6] J.M. Steele (1989), Kingman's subadditive ergodic theorem, Annales de l'I.H.P., Section B, Vol. 25, No. 1, pp. 93-98.

An extension of Lagrange's theorem to semigroups?

2012-06-15T11:21:37Z

The question is fairly dry: Is there any semigroup analogue of Lagrange's theorem for groups (counting as a generalization of the latter)? Let me guess the answer: Obviously yes. So the real question is: Any reference? Thank you in advance.

P.S.: I've notice of a Lagrange's theorem for Smarandache semigroups, but I would like to hear of different extensions, if possible (I don't think this is quite standard, but somebody defines a Smarandache semigroup to be any semigroup $(A, \star)$ for which there exist a proper subset $G$ of $A$, a unary operation $u: G \to G$ and a distinguished element $e \in G$ such that $(G, \star, u, e)$ is a group).

Edit. This is basically a comment to the subsequent answer of Vladimir Dotsenko. Let me highlight that I'm not asking for (possible) extensions to arbitrary semigroups. And I don't expect that, if any non-trivial extension is possible, it looks exactly like Lagrange's theorem for groups.

I'm just asking for any possible non-trivial extension that is already there, in the literature. Say, for instance, an extension to some interesting classes of semigroups (apart from groups and those where the theorem sounds true by definition, e.g. Smarandache lagrangian semigroups).

I know, non-trivial and interesting are not well-defined terms. But I have faith in your common sense.

A question of terminology - Unitizations of semigroups

2013-01-16T10:11:18Z

There are at least two standard ways of unitizing a (small) semigroup $\mathbb A$:

(i) We add an identity regardless that $\mathbb A$ is already unital.

(ii) We add an identity only if none is already available.

In the former case, the unitization process is functorial, as it amounts to the existence of a left adjoint to the canonical forgetful functor from the category of small categories to the category of small semicategories (in the sense of B. Mitchell).

Question. Is there any standard terminology to differentiate (i) from (ii)? I would be content with something like "(i) is occasionally called the unitization à la X" or "(ii) is referred to by some authors as Y's unitization".

Thanks in advance.

A linearly orderable monoid which does not embed into a linearly orderable group

2012-10-13T23:34:09Z

It is known (after an example of A.I. Mal'cev) that there exist cancellative semigroups which do not embed into a group. On the other hand, it is not difficult to see that every linearly orderable semigroup (is cancellative and torsion-free, and) embeds into a linearly orderable monoid (see here for terminology and motivations). Then, my question is:

Is it known whether or not a linearly orderable monoid embeds into a linearly orderable group?

The answer is surely yes in the commutative setting (by the construction of the Grothendieck group). But I've no clue about the non-commutative case. Thank you in advance for any hint.

Historical questions on the term "general abstract nonsense"

2012-10-29T15:30:59Z

Saunders Mac Lane reports that the contents of his 1942 paper (joint with Samuel Eilenberg), that first introduced categories, were then referred to (in the words of prominent representatives of the mathematical community of that time?) as "general abstract nonsense''. While today the term is mostly used, especially by practitioners, as an implicit recognition of deep mathematical perspectives (rather than in a derogatory sense), is it correct that the tone was actually sarcastic, to say the least, in the early days of the subject? Or is it a falsehood? Could you point me out some references (more focused on this than Mac Lane's article from the above link) in support of one or other of the two versions? Thanks in advance for any help.

Added later. According to the bibliography included in the Wiki article linked by Robert Israel in his answer below, the term general abstract nonsense is believed to have been coined by Norman Steenrod - and surely it was not intended by him as a putdown (in spite of what happens today, in some fringes of the mathematical community). On the other hand, I'm now particularly intrigued (and, I must really confess, a little bit puzzled) by P.A. Smith's, let's say, warm comments about Eilenberg and Mac Lane's General Theory of Natural Equivalences, as they are reported by Michael Barr in an old thread from the Category Theory mailing list (dating back to May 1998).

Does anybody know if Smith's comments are taken from a letter, review, or anything else appearing in a journal, book, etc.? If so, have they ever been "revised" by Smith?

Graphs, multiplicative graphs and composition graphs (à la Ehresmann)

2012-10-20T16:21:24Z

Introduction. Allow me to use the NBG axiomatic system as a foundation (*). Charles Ehresmann is acknowledged as the first one to have introduced the idea of multiplicative graphs as a further level of abstraction in the study of categories. Unfortunately, I don't have a copy of his Categories et structures on my shelves, thus I'm writing to ask for experts' advice on the subject.

I learnt from uncle Google that Lutz Schröder, in his 1999 PhD thesis (in German), has slightly further abstracted Ehresmann's original ideas by extending multiplicative graphs to composition graphs. But Schröder's thesis is not apparently available for free consultation through the web and, in addition, I cannot read German. Now, the point is that I would like to see a completely formal definition of Schröder's composition graphs, for the sake of comparison with something on which I'm currently working. So, this post is definitely another question about terminology and references.

Definitions. As far as I can understand, a graph (in the sense of Ehresmann) is a 5-tuple $\mathbf C = (\mathcal C_{\rm o}, \mathcal C_{\rm h}, s, t, i)$, consisting of two classes $\mathcal C_{\rm o}$ and $\mathcal C_{\rm h}$ (of objects and arrows, respectively), and functions $s,t: \mathcal C_{\rm h} \to \mathcal C_{\rm o}$ and $i: \mathcal C_{\rm o} \to \mathcal C_{\rm h}$ such that $s(i(A)) = t(i(A)) = A$ for all $A \in \mathcal C_{\rm o}$. Thus, if I'm not missing anything, Ehresmann's graphs have identities. The same should be true with a composition graph (in the sense of Schröder), which seems to be a pair $(\mathbf C, c)$, where $\mathbf C = (\mathcal C_{\rm o}, \mathcal C_{\rm h}, s, t, i)$ is a graph (in the sense of Ehresmann) and $c$ is a partial function from $\mathcal C_{h} \times \mathcal C_{h}$ to $\mathcal C_{\rm h}$ such that $(f,g) \in {\rm dom}(c)$ only if $t(f) = s(g)$. This should be indeed called

a multiplicative graph (in the sense of Ehresmann) if the 'if' in the latter statement is replaced with an 'if and only if';
an identitive composition graph if for $f \in \mathcal C_{\rm h}$ one has $c(f,i(t(f))) = f$ whenever $(f,i(t(f))) \in {\rm dom}(c)$ and $c(i(s(f)),f) = f$ whenever $(i(s(f)),f) \in {\rm dom}(c)$;
a strongly identitive composition graph if it is identitive and $(f,i(t(f))), (i(s(f)),f) \in {\rm dom}(c)$ for all $f$;
a semicategory if it is an associative composition graph, viz $c(c(f,g),h),c(f,c(g,h)) \in {\rm dom}(c)$ and $c(c(f,g),h) = c(f,c(g,h))$ whenever $(f,h),(g,h) \in {\rm dom}(c)$ (which is slightly more general than the homonymous notion of a semicategory given by nLab).

Questions. (1) Do these definitions reflect the actual ones of graphs, composition graphs (by Schröder) and multiplicative graphs (by Ehresmann)? (2) Do you know of any significant development of these topics, especially in relation to categorical logic?

See here something related and motivations.

(*) Yeah, I know. Some of you feel disgusted by the NBG stuff, for diverse and diverse reasons. But, please, refrain yourselves from annoying comments on this hand, since the personal taste of Mr Banana is not really the point, here. Thank you so much.

Looking for a paper of Kemperman on semigroups

2012-10-17T15:19:17Z

I like Shakespeare and Greek tragedy, so let me word it as I'm doing: I desperately need J.H.B. Kemperman's 1956 paper On complexes in a semigroup, but the online archive of Indagationes Mathematicae, where it was originally published (Vol. 18, pp. 247-254), goes back until 1990. Are you aware of any comparatively recent reprint or something like that? Thank you much in advance for any help you can provide.

A categorical framework for Freiman s-morphisms

2012-10-16T14:16:02Z

Let $\mathfrak A_i$ be groups ($i = 1, 2$), written multiplicatively, and $s$ a non-negative integer (here, as usual, I am abusing notation and denoting the operations of $\mathfrak A_1$ and $\mathfrak A_2$ with the same symbols as the ones in the standard multiplicative signature of the first-order algebraic theory of groups).

A Freiman $s$-morphism from $X_1 \subseteq \mathfrak A_1$ to $X_2 \subseteq \mathfrak A_2$ is then any function $\phi: X_1 \to X_2$ such that: $\prod_{i=1}^s x_i^{\varepsilon_i} = \prod_{i = 1}^s y_1^{\varepsilon_i}$ for some $x_1, \ldots, x_s, y_1, \ldots, y_s \in X_1$ and $\varepsilon_1, \ldots, \varepsilon_s \in \{\pm 1\}$ implies $\prod_{i=1}^s \phi(x_i)^{\varepsilon_i} = \prod_{i=1}^s \phi(y_i)^{\varepsilon_i}$, where I am using $\phi(\cdot)^\varepsilon$ in place of $(\phi(\cdot))^\varepsilon$, as expected.

The subject is fascinating, as far as I'm concerned, but any presentation of it which I'm aware of looks redundant (in the basics) to my eyes. This motivates me to ask the following:

Question. Is there any previous attempt of categorifying the theory of Freiman's morphisms, at least to the degree, say, of defining a category where objects are something and arrows "Freiman $s$-morphisms"? In the case of a positive response, could you provide explicit references and a sketchy account of this early work on the subject?

Terminology question relating to magmoidal semicategories

2012-10-13T23:12:50Z

Suppose that $\mathfrak C = (\mathbf C, \otimes)$ is a magmoidal semicategory and let $\mathcal P := \{{\rm P_n}\}_{n=1}^\infty$ be a set of parenthesizations such that ${\rm P}_n$ has length $n$ for each $n$. It is then possible to recursively define long tensor products parenthesized by $\mathcal P$, simply mimicking what we would do in a magma. Thus, one can safely handle stuff like $\blacksquare_1 \otimes \blacksquare_2 \otimes \cdots \otimes \blacksquare_n$, the black squares being either objects or arrows from the lovely $\mathfrak C$, by implicitly referring to the parenthesized tensor product ${\rm P}_n(\blacksquare_1, \blacksquare_2, \ldots, \blacksquare_n)$. If $\mathfrak C$ is [weakly] associative, as in the case of monoidal (or simply semigroupal) categories, then we are freely given the existence of natural isomorphisms making all parenthesized tensor products look like each other. Thus, my question is:

Question. Is there any (possibly standard) naming for a long parenthesized (tensor) product? If not, how would you call it, were you in my place?

Thank you in advance for any suggestion. If relevant, my motivations are linked to this.

References for semicategories

2012-09-11T11:26:26Z

I am struggling with the notion of structure (for reasons related to Freiman's theory and normed rings), which is the main motivation for my question:

Could you suggest some (good) surveys or books with a systematic development of the theory of semicategories (starting from the basics), in the same spirit, say, of CWM and ACC?

I already checked nLab, and there is not really much about semicategories: The only reference given (click) doesn't provide background on the subject.

Thank you in advance,

Salvo

On the notion of torsion-freeness in semigroup theory

2012-09-02T18:45:47Z

The following seems to be the "official" notion of torsion-freeness in the context of semigroups:

TF1. A (multiplicatively written) semigroup $\mathfrak A$ is torsion-free if there do not exist $a,b \in \mathfrak A$ and $n \in \mathbb N^+$ such that $a \ne b$ and $a^n = b^n$.

On another hand, I recently ended up with the following alternative idea:

TF2. A semigroup $\mathfrak A$ is torsion-free if, given $a \in \mathfrak A$, $a^m = a^n$ for some $m,n \in \mathbb N^+$ with $m \ne n$ only if $a$ is idempotent.

Both of these generalize the usual notion of torsion-freeness for groups. Also, it is not difficult to check that TF1 implies TF2, but not viceversa. So, my questions are:

Q1. What about existing literature concerning torsion-free semigroups in the sense of the second definition? Q2. Could you point out some reasons why the former definition should be preferred to the latter?

For the record, this is somehow related to question 105851.

Strictly totally ordered semigroups - Looking for references

2012-08-29T15:08:52Z

Let $\mathfrak A = (A, \cdot)$ be a semigroup (written multiplicatively). We say that $\mathfrak A$ is linearly orderable if there exists a total order $\le$ on $A$ such that $ac < bc$ and $ca < cb$ for all $a,b,c \in A$ with $a < b$ (note strict inequalities).

Some examples of linearly orderable semigroups are: the real numbers with the usual addition; the positive integers divisible only for the members of a given set $S$ of (natural) primes with the usual multiplication; every abelian torsion-free cancellative semigroup (see Proposition 2 below); the polynomials in finitely many variables with nonnegative real coefficients with the usual Cauchy multiplication; the upper [lower] triangular matrices with positive real entries and the usual row-by-column multiplication; the free monoid on an alphabet $X$; subsemigroups and direct products of the previous ones.

Now, denote by $\mathfrak A^{(1)}$ the (canonical) unitization of $\mathfrak A$. As a byproduct of something that I've just finished to write, I happened to prove the following:

Proposition 1. $\mathfrak A$ is linearly orderable (if and) only if the same holds true with $\mathfrak A^{(1)}$.

Proposition 2. Every abelian torsion-free (*) cancellative semigroup $\mathfrak A$ is linearly orderable.

Proposition 2 has a kind of (trivial) converse: Every linearly orderable semigroup is torsion-free and cancellative (indeed, something stronger can be proved; i.e., none of the elements of the semigroup has finite order unless the semigroup is unital and such an element is the identity).

I am reasonably sure that both results are nothing new, but I wasn't able to find any reference. In particular, I checked Clifford's 1958 survey, but this seems focused more on totally ordered semigroups (there referred to simply as ordered semigroups) than on linearly ordered semigroups (there called strictly ordered semigroups). On another hand, I am aware of a 1913 result by F.H. Levi (Arithmetische Gesetze im Gebiete diskreter Gruppen, Rend. Circ. Mat. Palermo, Vol. 35 (1913), pp. 225-236), where it is proved that every torsion-free abelian group is linearly orderable (as a group). On another hand, I have no clue about Proposition 1. Then, here are my questions:

Question 1. Do you know of any paper, book, comic strip (I'm damned serious) with a published proof of Propositions 1 and/or 2?

Question 2. Any hint on how to retrieve Levi's original paper? It seems impossible to find it, and there is no copy of it in my local library.

Thank you in advance.

Salvo.

(*) To avoid misunderstandings due to terminology, I say that a semigroup $\mathfrak A$ is torsion-free if an element $a$ has finite order, that is, $a^m = a^n$ for some $m,n \in \mathbb N^+$ with $m \ne n$, if and only if $a$ is idempotent.

Extra contents. For what it is worth, my proof of Proposition 2 does not really add any significant new idea; it is based on Levi's result and use nothing but well-known basic facts: (i) $\mathfrak A$ embeds in its unitization $\mathfrak A^{(1)}$; (ii) $\mathfrak A$ is abelian/cancellative/torsion-free iff the same holds true with $\mathfrak A^{(1)}$; (iii) the inverse image of a linearly orderable semigroup under a semigroup embedding is linearly orderable; (iv) every subsemigroup of a linearly orderable semigroup is itself linearly orderable; (v) as a consequence of (i)-(iv), we can assume wlog that $\mathfrak A$ is an abelian torsion-free cancellative monoid and construct its Grothendieck group, say $\mathfrak A_\mathcal{G}$; (vi) $\mathfrak A_\mathcal{G}$ is torsion-free (and obviously abelian); (vii) $\mathfrak A$ embeds in $\mathfrak A_\mathcal{G}$, by cancellativity; (viii) we can use (iii), (iv), (vii) and Levi's result to conclude. Nonetheless, I think that it may deserve a little place in the paper (e.g., as a reference for future work). But I would feel better if I could have a pointer to a previously published proof. It goes the same with Proposition 1.

Motivation (if it matters; if not, ignore it all). Freiman, Herzog and coauthors have recently proved some results on sum-sets/produc-sets in linearly ordered groups (which they refer to simply as ordered groups), accordingly extending some parts of Freiman's previous work on small doubling on integers; see G. Freiman, M. Herzog, P. Longobardi, and M. Maj, Small doubling in ordered groups, J. Austral. Math. Soc., to appear. Even more recently, I myself extended some of their results from the setting of linearly ordered groups to linearly ordered semigroups. And this is where my questions come from.

Answer by Salvo Tringali for Applications of Liouville's theorem

2012-06-27T09:35:18Z

The first published proof of the Mazur-Gelfand theorem, due to Gelfand himself (though previously announced without proof by Mazur), is based on the vector-valued version of the Liouville theorem, which was further extended by Arens to cover a more general situation (see [1] and references therein).

[1] R. Arens (1947), Linear topological division algebras, Bull. AMS, Vol. 53, pp. 623-630.

Idempotent semigroups: Are they all residually finite?

2012-06-21T09:15:33Z

As pointed out by Mark Sapir in his answer to a related question, every residually finite divisible semigroup is idempotent (hence uniquely divisible). On another hand, it is not difficult to prove that any idempotent Abelian semigroup is residually finite. So it is natural to ask whether or not the same holds even in the case where the semigroup operation is not commutative. Does it happen to be a well-established result? Is there a trivial counterexample that I can't see?

Comment by Salvo Tringali

2013-05-07T23:13:48Z

I'm afraid that you missed the sign at the entrance.

Comment by Salvo Tringali

2013-05-05T18:38:08Z

That said, your question is not suited for this place. Maybe you should try with math.stackexchange.com or artofproblemsolving.com/Forum/index.php.

Comment by Salvo Tringali

2013-05-05T18:31:21Z

$f$ is multiplicative, and $\sigma(p^n) = p^n+(p^n−1)/(p−1) \le \frac{1}{2}(n+1)(p^n+1) = \frac{1}{2} d(p^n) \cdot (p^n + 1)$ for each prime $p$ and each $n \in \mathbb N^+$, with equality iff $n=0$ or $n=1$.

Comment by Salvo Tringali

2013-04-09T17:23:40Z

@quid. You're right. Replacing min with max is certainly closer to the spirit of the OP. I guess this is what you meant by the term "dual".

Comment by Salvo Tringali

2013-04-07T09:48:56Z

Thanks, Theo, for your comment. Yes, sorry, I forgot to say that $\zeta$ must be associative, in the categorial case. Let me edit and fix it.

Comment by Salvo Tringali

2013-04-05T12:32:53Z

Well, I don't know about Šutov's paper (my Russian doesn't go beyond the alphabet), but I read Neumann's, and strictly speaking Neumann doesn't prove, not in the paper referred to in the above answer, that any given sgrp can be embedded into a divisible sgrp. However, he mentions that this can be done (p. 1021), and addresses the reader to [1, Theorem 6.2], where an analogous result is established for groups. But his construction doesn't look very canonical, so let me edit the OP and add another question. References: [1] B.H. Neumann, Adjunction of elements to groups, JLMS, 18 (1943), 4-11.

Comment by Salvo Tringali

2013-04-04T17:18:15Z

Thanks, Benjamin, I've just retrieved Neumann's paper. For the record, the manuscript comes with a corrigendum (cms.math.ca/cjm/a145888), for "an error in the first proof, p. 1020, of Theorem 3.1", and an addendum addressing the reader to Šutov's work for an alternative proof.

Comment by Salvo Tringali

2013-03-21T23:09:30Z

@Misha. I agree, but my point is that I don't know, among the many things that I don't know, who was the first to address the question explicitly (just to have a trustful reference for all practical purposes). However, I guess that I would be better to give up with this, for it seems hard, and perhaps even pointless, to track back the paternity of the result. Thank you, in any case, for sharing your thoughts.

Comment by Salvo Tringali

2013-03-21T21:26:19Z

Clear and very nice. I really wonder if one can cluster all the matrices in ${\rm SL}_n(\mathbb C)$ which don't have a $p$-th root for some prime $p \le n$ in a finite number of conjugacy classes: Your example is still very particular, which tempts me to think that there may be only "few" exceptions.

Comment by Salvo Tringali

2013-03-21T18:58:23Z

OK, I've finally given a look at Niven's 1941 paper. It deals with a more general question, i.e. sort of a fundamental theorem of algebra for polynomials with coefficients in the skew-field of Hamilton's quaternions. And Niven reports a remark of Jacobson according to which this result is a consequence of previous work by Ore, dating back to 1933, on non-commutative polynomials.

Comment by Salvo Tringali

2013-03-21T18:01:54Z

From the paper mentioned in my answer: "The existence of an $m$-th root of a quaternion $a$ is known", and then a note refers the reader to: I. Niven, Equations in quaternions, AMM, Vol. 48, 1941, pp. 654-661. Maybe you're right, but this is the only reference that I've found so far, and it dates back to 1941.

Comment by Salvo Tringali

2013-03-21T13:31:06Z

Ehr... Yes, but somehow I missed this "limit case" while working to something slightly more general: If $J = \left[\begin{array}{cc} \lambda & \mu \\ 0 & \lambda^{−1}\end{array}\right]$ for some $\lambda \in \mathbb C^\times\setminus\{−1\}$ and $\mu \in \mathbb C$, then $\left[\begin{array}{cc} a & c \\ 0 & b\end{array}\right]^2=J$ for $a=|\lambda|^{1/2}e^{i\frac{\theta}{2}}$, $b=a^{−1}$ and $c=(a+b)^{−1} \mu$, where $\theta$ is (the principal value of) the complex argument of $\lambda$. I edited the OP, fixed my mistake, and updated Q2. Thanks!

Comment by Salvo Tringali

2013-03-21T11:17:10Z

To clarify: This doesn't count as an answer to the specific question in the OP, but it is an attempt to suggest a direction, and it was too long for a comment.

Comment by Salvo Tringali

2013-03-17T21:18:38Z

I had a look at Higham's Functions of Matrices - Theory and Applications, before asking. And even if the 7th chapter of the book is entirely focused on $k$-th roots of complex matrices, nothing like your (absolutely brilliant) proof seems to be there. And the 3rd edition of the classical Matrix Computations by Golub and Van Loan spends no word for arbitrary $k$-th roots, while square roots are just mentioned in relation to the Cholesky and polar decompositions (and again, there's nothing in the lines of your slick argument).

Comment by Salvo Tringali

2013-03-17T20:56:19Z

You're absolutely right! I had completely overlooked the Lefschetz principle.