Recent MathOverflow Questions

What makes Graph invariants so useful/important?

Math Overflow Recent Questions - Sun, 04/07/2019 - 12:22

What makes Graph invariants so useful/important? If I were trying to create a useful graph invariant, what principles should I follow?

My understanding is that they allow one to isolate and study specific properties of graphs algebraically or to classify graphs up to isomorphism (although, it seems to me that canonical labellings are the right tool for this).

However, important graph invariants are constructed from counting proper colorings of a graph, for an appropriate definition of proper. A priori, why do we know that those graph invariants isolate and study specific properties or is there some other key motivation for graph invariants?

Hooks, monomers, dimers and Young diagrams: Part II

Math Overflow Recent Questions - Sun, 04/07/2019 - 11:40

As promised, I've upgraded my last question.

Consider the $k$-by-$n$ partition $\lambda_n=(n,\dots,n)$ and its corresponding Young diagram $Y_{n,k}$, which is a $k\times n$ rectangle of cells. Now, start tiling $Y_{n,k}$ using monomers ($1\times1$ squares) and dimers ($1\times2$ and $2\times1$ rectangles).

Next, insert the hook-lengths $h(\square)$ into each cell $\square\in Y_{n,k}$. Associate a weight: a monomer at $\square$ receives $h(\square)$, a dimer sitting on $\square$ and $\square'$ gets the product $h(\square)\cdot h(\square')$. Each tiling $T$ will have weight assigned as the sum of the weights of its monomers and dimers. Let $b_{n,k}$ be the entire sum of the weights of all possible tiltings of $Y_{n,k}$. For example, if $n=3, k=1$ then we get $$b_{3,1}=(3+2+1)+(3\cdot2+1)+(3+2\cdot1)=6+7+5=18.$$ The first few values are: $b_1=1, b_2=5, b_3=18, b_4=59, b_5=162$.

QUESTION. Are these generating function $G_k(x)=\sum_nb_{n,k}x^n$ rational functions? Or, can you verify this for small $k$, such as $k=2,3,4$, etc?

Remark. Fedor's comment led to $G_1(x)=\frac{x(1+x+5x^3-3x^4)}{(1-x-x^2)^4}$. A rational function.

Symplectic equivalent of commuting matrices

Math Overflow Recent Questions - Sun, 04/07/2019 - 11:05

It is well known what happens if two real symmetric matrices commute, i.e. if we have two matrices $A$ and $B$ such that $A=A^T$, $B=B^T$ and $AB=BA$. The answer is given in terms of diagonalization: there is a unitary matrix $M$ such that $A$ and $B$ are transformed into $A'=M^TAM$ and $B'=M^TBM$, and both $A'$ and $B'$ are diagonal.

Here I'm asking if any analogous property holds in the following case.

$A$ and $B$ are symmetric, i.e. $A=A^T$ and $B=B^T$. The following property holds:

$$A\Omega B=B\Omega A$$ (1)

where $\Omega$ is the matrix defining the symplectic bilinear form (skew-symmetric, nonsingular, and hollow), e.g.:

$$\Omega = \begin{bmatrix}0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\ -1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \end{bmatrix}$$

The allowed transformations are the symplectic matrices $M$, i.e. matrices for which the following holds:

$$M^T\Omega M=\Omega$$

The transformed matrices are $A'=M^TAM$ and $B'=M^TBM$.

My question is if there is a form into which $A'$ and $B'$ can be put, by means of a suitable $M$, provided that Eq.1 holds.

When does the dual to the space $K(X)$ of compact operators consist of nuclear functionals?

Math Overflow Recent Questions - Sun, 04/07/2019 - 10:54

Let $X$ be a Banach space and $B(X)$ be its space of all (bounded) operators. A nuclear functional on $B(X)$ is a linear functional $u:B(X)\to{\mathbb C}$ that can be represented in the form $$ u(A)=\sum_{n=1}^\infty \lambda_n\cdot f_n(Ax_n),\qquad A\in B(X), $$ where $\lambda_n\in{\mathbb C}$, $x_n\in X$, $f_n\in X^*$ are such that $$ \sum_{n=1}^\infty |\lambda_n|<\infty,\quad \sup_{n}||x_n||\le 1,\quad \sup_{n}||f_n||\le 1. $$ Let us denote by $N(X)$ the space of all nuclear functionals on $B(X)$.

If $X$ is a Hilbert space, then it is well known (see G.J.Murphy, C*-Algebras and Operator Theory, Theorem 4.2.1) that the dual space $K(X)^*$ to the space of all compact operators $K(X)$ coinsides with the space of all nuclear functionals: $$ K(X)^*=N(X) $$ (this is an isomorphism of Banach spaces, but for me it is important that this is an equality of sets).

Is the same true for all Banach spaces $X$? Or at least for all Banach spaces with the (classical) approximation property?

I am mostly interested in the case when $X=C(T)$, the space of continuous functions on a compact topological space $T$.

Set-theoretical foundations of Mathematics with only bounded quantifiers

Math Overflow Recent Questions - Sun, 04/07/2019 - 10:40

It seems that outside of researchers in Mathematical Logic, mathematicians use almost exclusively bounded quantifiers instead of unbounded quantifiers. In fact, I haven't observed any other practice from the very first day on when I was a student.

For example, a logician would write

$\forall a : ( a \in \mathbb R ) \rightarrow ( a^2 \geq 0 )$

whereas most working analysists and algebraists write

$\forall a \in \mathbb R : a^2 \geq 0$

On the other hand, most mathematicians I know accept the idea that all of mathematics can be built up from set-theoretical foundations alone (starting the natural numbers).

So there seems to be a set of assumptions, almost universally agreed upon, which most working mathematicians assume implicitly for their practice. These assumptions start with set theory but apparently exclude unbounded quantifiers. In fact, unless you attend a class in formal logic you might never encounter unbounded quantifiers.

It seems that most mathematicians use a subset of human language enhanced with a subset of mathematical language (avoiding universal quantifiers) as their working language.

Question: Have there been attempts at precisely identifying this mathematical sublanguage and the rules that it governs?

A question about pdfs with likelihood ratio order

Math Overflow Recent Questions - Sat, 04/06/2019 - 22:07

Suppose $f_1,f_2,\dots$ are pdfs of absolutely continuous random variables with the same support (say an interval). Assume that $\{f_i\}$ are strictly positive in their support. Furthermore, $\frac{f_i(x)}{f_j(x)}$ is increasing in $x$ for any $i<j$. This is sometimes called the likelihood ratio order.

Let $t_i= \arg\max_p F^{-1}_{i+1}(p) - F^{-1}_i(p)$. Here $F^{-1}_i$ is the inverse function of the CDF associated with random variable i.

Is $\{t_i\}$ an increasing/decreasing sequence? If not, can you provide counterexamples?

When does nuclear norm mininimization give rank $1$ solution when we have at most one solution?

Math Overflow Recent Questions - Sat, 04/06/2019 - 20:27

We have a quadratic system of equations

$$A(X\otimes Y)=b$$ where $A\in\mathbb Z^{m\times n^2}$ and $b\in\mathbb Z^m$ are known and $X,Y\in\mathbb Z^{n}$ are unknown. $A$ and $b$ have at most $b$ bit entries in magnitude.

Suppose we know the there is at most one $X$ and $Y$ that satisfy the system is it possible to solve it to get the rank $1$ solution in $poly(mnb)$ time with nuclear norm minimzation or other convex techniques if $A$ behaves 'randomly'?

Note $A$ does not have Gaussian or bernoulli behavior since it is integer entried.

Is there a general polynomial time recovery criterion?

Milnor immersion of circle, disks, and a ball

Math Overflow Recent Questions - Sat, 04/06/2019 - 11:32

Milnor surprisingly found an immersion of a circle in the plane which bounds two "incompatible" immersed disks (see [1] for example, picture included). I think I can glue these two disks together to define an immersion of a sphere $f:S^2\to\mathbb{R}^3$ where Milnor's immersed circle (the equator) sits in the $xy$-plane and contracts to a point (in the $\pm z$ directions) by running along either immersed disk.

Does $f(S^2)$ bound an immersed ball, i.e. does $f$ extend to an immersion of a 3-ball?

This question was sparked by glancing at Gromov's book [1] and a related paper of Eliashberg-Mishachev which argues that the projection $S^2\to\mathbb{R}^2$ (composing $f$ above with projection onto $xy$-plane) is not homotopic through folded maps to the "standard" folded map $(x,y,z)\mapsto (x,y)$ on the unit 2-sphere (the fold being the equator).

A group of all whose elements are distorted

Math Overflow Recent Questions - Sat, 04/06/2019 - 10:49

Does there exist a finitely presented group, not torsion, all of whose infinite-order elements are distorted?

An infinite-order element $g$ of a finitely generated group $G$ is undistorted if there exist constants $A,B \geq 1$ such that $\|g^n\|_S \geq \frac{n}{A} -B$ for every $n \in \mathbb{Z}$, where $\| \cdot \|_S$ denotes the word length associated to a fixed finite generating set $S$ of $G$. An element which is not undistorted is distorted.

I am mainly interested in the finitely presented case, but a finitely generated example would be interesting as well.

Edit: I realised that a finitely generated example exists as a consequence of Osin's paper Small cancellations over relatively hyperbolic groups and embedding theorems. (Since an infinite-order element which is conjugate to its square is necessarily distorted.)

Hard implications that become easy with the right intermediate step

Math Overflow Recent Questions - Sat, 04/06/2019 - 08:07

I’m interested in examples of theorems of the form “If $P$ then $Q$“ that were either unsolved or thought to require difficult arguments until someone came up with an $X$ for which “If $P$ then $X$” and “If $X$ then $Q$” are significantly easier to prove.

[Can someone make this post community-wiki for me (I don’t know how to do it with the browser I’m using) and then delete this paragraph for me? Thanks!]

Ends of finitely generated torsion groups

Math Overflow Recent Questions - Sat, 04/06/2019 - 07:23

It is known that the number of ends of a finitely generated group is 0,1, 2 or $\infty$.

Problem 1. What is known about the number of ends of infinite finitely generated torsion groups?

In particular,

Problem 2. Is there any description of finitely generated torsion groups with 1 end?

PD model for CDGA over the integers

Math Overflow Recent Questions - Sat, 04/06/2019 - 05:44

Lambrechts and Stanley constructed PD model for cdga over a field with simply connected cohomology. Are there construction of PD model for CDGA over integer coefficients?

A few questions on possible relationship between Goldbach's conjecture and ABC conjecture [on hold]

Math Overflow Recent Questions - Sat, 04/06/2019 - 02:17

Definition: A triplet ($a,b,c$) of natural numbers is called a Goldbach-ABC triplet iff:

  • $a, b$, are odd primes,
  • $a, b, c$ are co-primes
  • $a + b = c$

Q1: If Goldbach's conjecture is true, would there be infinitely many Goldbach-ABC triplets?

Q2: If the answer to Q1 is Yes and if Goldbach's conjecture is true but it's impossible to know/verify it so (there's no proof to it), would such impossibility imply it'd be invalid to claim there's a proof for the ABC conjecture?

Footnote: Fwiw, the intention for asking the questions (especially Q2) would be to cast the ABC conjecture problem entirely in the framework of FOL language structures in which relevant language expressions, terminologies, and concept definitions would be less convoluted compared to those in IUTT framework.

Asymptotics for the sums from the inclusion-exclusion principle

Math Overflow Recent Questions - Fri, 04/05/2019 - 20:03

What is a method to compute the asymptotics of a sum resulting from the inclusion-exclusion principle? Each term of the sum can be approximated perhaps by Stirling's formula or the Gaussian distribution. However the alternating sign should effect some cancellation. As an example, the answer to this combinatorial problem generates a probability $$p=\frac c{n\choose j},$$ where $$c=\sum_{k=w}^j(-1)^{k-w}(j-k+1){n-k+1\choose j-k+1}.$$ What is the asymptote of $p$ for $\big|\frac jn-a\big|=o(n)$ and $\big|\frac wn-b\big|=o(n)$ for some positive numbers $a$ and $b$ as $n\rightarrow\infty$?

Sobolev functions on $\mathbb{R}^N$ cannot be discontinuous on a $(N-1)$-dimensional submanifold

Math Overflow Recent Questions - Fri, 04/05/2019 - 16:47

How can one prove (or where can I find a proof) that if $u \in W^{1,p}(\Omega)$, where $\Omega \subset \mathbb{R}^N$, then $u$ cannot have a $(N-1)$-manifold of discontinuity points?

Upper bound ratio of integration over matrix domain

Math Overflow Recent Questions - Fri, 04/05/2019 - 16:17

Let $$\Delta_a=\{A\in\mathbb{R}^{n\times n}:0\leq A\leq I, \operatorname{trace}(A)\leq a\}$$ I'm interested in a clean and nontrivial upper bound of the ratio of the following: $$\frac{\int_{\Delta_a}|A|^{\alpha-\frac{n+1}{2}}|I-A|^{-1/2}\,dA}{\int_{\Delta_b}|A|^{\alpha-\frac{n+1}{2}}|I-A|^{-1/2}\,dA}$$ where $n/2>a>b>0,\alpha>\frac{n+1}{2}$, $|\cdot|$ is the determinant.

If we perform spectral decomposition as a change of variable $A=Q\Lambda Q^T$ where $\Lambda=diag\{\lambda_1,...,\lambda_n\}$ and $Q$ is orthogonal and let $$\tilde{\Delta}_a=\{(\lambda_1,...,\lambda_n):\sum_{i=1}^n\lambda_i\leq a,0<\lambda_i<1\forall i\}$$ The ratio becomes: $$\frac{\int_{\tilde{\Delta}_a}(\prod_{i=1}^n\lambda_i)^{\alpha-\frac{n+1}{2}}(\prod_{i=1}^n(1-\lambda_i))^{-1/2}\prod_{i<j}|\lambda_i-\lambda_j|d\lambda}{\int_{\tilde{\Delta}_b}(\prod_{i=1}^n\lambda_i)^{\alpha-\frac{n+1}{2}}(\prod_{i=1}^n(1-\lambda_i))^{-1/2}\prod_{i<j}|\lambda_i-\lambda_j|d\lambda}$$

Homology of spectra vs homology of infinite loop spaces

Math Overflow Recent Questions - Fri, 04/05/2019 - 13:03

Let $X$ be a CW complex and let $\Sigma^\infty X$ denote its suspension spectrum. By definition, the $n$th singular homology group of $\Sigma^\infty X$ with coefficients in $\mathbb{Z}$ is $\pi_n(\Sigma^\infty X \wedge H\mathbb{Z})$.

Now, connective spectra are in bijection with infinite loop spaces. The infinite loop space corresponding to $\Sigma^\infty X$ is $QX := \Omega^\infty \Sigma^ \infty X = \lim_{n \to \infty} \Omega^n \Sigma^n X$. Is the homology of $\Sigma^\infty X$ (as a spectrum) isomorphic to the homology of $QX$ (as a CW complex)? I would expect this.

But what confuses me is a theorem is Rudyak's On Thom spectra, orientability, and cobordism (Theorem 7.11.(i)). Rudyak states that for every rational spectrum $E_\mathbb{Q}$ the Hurewicz map $\pi_\ast(E_\mathbb{Q}) \rightarrow H_\ast(E_\mathbb{Q})$ is an isomorphism. This seems to prove that the homotopy/homology groups of spectra do not agree with homotopy/homology groups of their corresponding infinite loop spaces.

First, $\pi_\ast(Q X) \otimes \mathbb{Q}$ is isomorphic to the stable rational homotopy $\pi_\ast^S(X) \otimes \mathbb{Q}$ of $X$. Then, by the Milnor-Moore theorem, $H_\ast(QX,\mathbb{Q}) \cong \mathbb{Q}[\pi_\ast^S(X) \otimes \mathbb{Q}]$. So we'd have that $H_\ast(X,\mathbb{Q})$ is the free commutative-graded algebra on the rational stable homotopy groups of $X$ for any CW complex $X$. But it is easy to write down examples of CW complexes whose rational homology is not free e.g. projective spaces. So what, then, is the relationship between $\pi_\ast(\Sigma^\infty X \wedge H\mathbb{Z})$ and $H_\ast(QX, \mathbb{Z})$?

uniform approximation by a particular set of functions

Math Overflow Recent Questions - Fri, 04/05/2019 - 07:04

Consider the interval $[0,1]$ and let $\mu_k(t)$ with $k=1,\ldots,n$ be continuous functions such that they are all strictly increasing on the interval $[0,1]$ and such that $\mu_1(t)<\mu_2(t)<\ldots<\mu_n(t)$ for all $t \in [0,1]$.

Consider for each $k \geq 0$, the functions $$f_k(t)=\sum_{j=1}^n (\mu_j(t))^k$$

Is it true that any continuous function on $[0,1]$ can be approximated uniformly by linear combinations of the functions $f_0,f_1,f_2,f_3,\ldots$?

The case $n=1$ clearly holds due to the Stone-Weierstrass theorem but I can't see the general case. Thanks for your help.

Theorems that impeded progress

Math Overflow Recent Questions - Thu, 04/04/2019 - 17:30

It may be that certain theorems, when proved true, counterintuitively retard progress in certain domains. Lloyd Trefethen provides two examples:

  • Faber's Theorem on polynomial interpolation
  • Squire's Theorem on hydrodynamic instability

Trefethen, Lloyd N. "Inverse Yogiisms." Notices of the American Mathematical Society 63, no. 11 (2016). Also: The Best Writing on Mathematics 2017 6 (2017): 28. Google books link.

In my own experience, I have witnessed the several negative-results theorems in

Marvin Minsky and Seymour A. Papert. Perceptrons: An Introduction to Computational Geometry , 1969. MIT Press.

impede progress in neural-net research for more than a decade.1

Q. What are other examples of theorems whose (correct) proofs (possibly temporarily) suppressed research advancement in mathematical subfields?

1 Olazaran, Mikel. "A sociological study of the official history of the perceptrons controversy." Social Studies of Science 26, no. 3 (1996): 611-659. Abstract: "[...]I devote particular attention to the proofs and arguments of Minsky and Papert, which were interpreted as showing that further progress in neural nets was not possible, and that this approach to AI had to be abandoned.[...]" RG link.

A version of weak approximation with S-integers

Math Overflow Recent Questions - Thu, 04/04/2019 - 17:29

Let $k$ be a finite field. Let $K$ a finite extension of $k(t)$. Let $S$ be a finite set of places of $K$. Let $$K_S = \prod_{v\in S} K_v$$ where $K_v$ is the completion of $K$ at $v$. For $v\in S$, let $\mathfrak{m}_v\subset\mathcal{O}_{K_v}$ be the maximal ideal of the valuation ring $\mathcal{O}_{K_v}$ of $K_v$. Let $$\mathcal{O}_{K,S} = \{\alpha\in K : v(\alpha)\geq 0, \forall v\not\in S\}\subset K$$ be the $S$-integers and embed $\mathcal{O}_{K,S}$ into $K_S$ diagonally. Let $\mathfrak{m}_S = \prod_{v\in S}\mathfrak{m}_v$. By the product formula, $\mathcal{O}_{K,S}\cap \mathfrak{m}_S = \{0\}$, so we get an embedding $$\mathfrak{m}_S\hookrightarrow \frac{K_S}{\mathcal{O}_{K,S}}.$$ My question is, is this embedding surjective?

The reason why I stated weak approximation in the title is because this question can be restated as follows: Given $\alpha = (\alpha_v)_{v\in S}\in K_S$, does there exists $\beta\in \mathcal{O}_{K,S}$ such that for all $v\in S$, $\alpha_v - \beta\in \mathfrak{m}_v$? If $\mathcal{O}_{K,S}$ is replaced by $K$ in this question, then the answer is yes by weak approximation (and we can replace the $\mathfrak{m}_v$'s by any power of the $\mathfrak{m}_v$'s).

My intuition says the answer to the question is yes, but after trying for a while I cannot prove it or find a reference. The most trivial example is the fact that $$k((t^{-1})) = k[t] \oplus t^{-1}k[[t^{-1}]]$$ where the direct sum is as abelian groups. In this example, $K = k(t)$ and $S = \{v\}$ where $v$ is the valuation with uniformizer $t^{-1}$. Then $\mathcal{O}_{K,S} = k[t]$ and $K_S = k((t^{-1}))$.

Any hint, answer, or reference would be appreciated!


Subscribe to curious little things aggregator