Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from mathoverflow.net 2018-10-17T02:59:20Z

A commuting pair of functions with no common bijective part

Thu, 07/12/2018 - 03:44

Let $X$ be set. Let $f$ be a function from $X$ into $X$. For a given set $E\subseteq X$, we say $E$ determines a $U$-part of $f$ if $f(E)\subseteq E$ and the restriction $f:E\to E$ is a bijection.

I am looking for a commuting pair of injective functions $f:X\to X$ and $g:X\to X$ (I mean $fg=gf$) such that both $f$ and $g$ have $U$-parts but not common $U$-part.

Is there a function from a Suslin tree to itself which send compatible elements to incompatible elements?

Thu, 07/12/2018 - 03:43

Given a Suslin tree $S$, I would like to know wether it is possible or impossible to define a function $f:S\to S$ such that for every $x,y\in S$ with $x<y$ we have $f(x)\perp f(y)$ and a proof or reference to a proof.

Notice $S$ is not required to have a single root.

Would the same result holds for a $S$ non-special Aronszajn trees which is not necessarily Suslin?

Matrix and Sparse Matrix Addition

Thu, 07/12/2018 - 03:31

I am a student of computer science. I have problem of some basic mathematics computation. I want to clarify it. I have a project which based on addition of a normal matrix and a Sparse matrix. I just want to know that if this addition problem. My normal matrix have a dimension 4*4 and my sparse matrix have only two non zero element in cell(0,0) and (1,1). How can I performed addition? Is that necessary to mention the dimension of sparse matrix?

It is very helpful to me if someone suggest some tutorial link of sparse matrix consist of sparse matrix operations.

Looking for positive reply.

Thank you in advance

Small modules over finite group with large cohomology

Thu, 07/12/2018 - 03:15

Looking at this Example of group cohomology not annihilated by exponent of $G$? I stumbled upon one question I couldn't solve (probably because it's hard), so I post it here.

Using Lyndon resolvent, we can always find $G$-module $M$ of rank equal to number of relators in some presentation such that $H^2(G, M)$ has maximal exponent (and is equal to $\Bbb Z/|G|$). Because one-relator finite group is cyclic, I asked myself

  1. Is it true that if there's ideal $R$ with $H^2(G, \Bbb Z[G]/R)$ of exponent $|G|$, then $G$ cyclic?

  2. If there's $2$-generated $G$-module $M$ with $H^2$ of exponent $|G|$, what can we say about $G$?

Of course, we can look not only on second cohomology, and obtain series of filtrations on category of finite groups: $G \in BC_{n, k}$ (BC for "big cohomology") if exists a $k$-generated module s. t. $exp(H^n(G, M) = |G|$. (or maybe $H^{\leq n}$, or $H^{\geq n}$,..). Looks interesting.

Example of a Non-double commuting pair of isometric operators with no common shift part

Thu, 07/12/2018 - 02:54

Before to state the problem, let us mention the Wold decomposition theorem.

Theorem. Every isometric operator is a direct sum of a unitary and shift.

Let $(T_1,T_2)$ be a commuting pair (I mean $T_1T_2=T_2T_1$) of isometric operators on the Hilbert space $H$.

I am looking for such a pair satisfying the followings properties:

1) Neither $T_1$ nor $T_1$ is unitary.

2) $T_1T_2^*$ is not the same as $T_2^*T_1$.

3) If $P$ is a projection commuting with both $T_1$ and $T_2$ such that the restrictions $T_n:PH\to PH$ are both shifts, then $P=0$.

Remark. By a shift, I mean a direct sum of unilateral shifts.

Argmax of weighted sum of binomials

Thu, 07/12/2018 - 02:32

(Writing my thesis, I encountered the following problem. It is secondary to the topic of the thesis and I have the solution that is enough for the purposes of the thesis—but inner perfectionist is still not happy.)

Fix two positive integers $n$ and $2 \leq \ell \leq n$ and define a discrete function $F : \{ 1, 2, \dotsc, n-\ell+1\} \rightarrow \mathbb N$ in the following way: $$ F(w) = F_{n,\ell}(w) = w \sum_{i=0}^{\ell-1} \binom{n-w}{i} \,. $$

What is $\underset{x}{\operatorname{argmax}} F(w)$? I can prove (see below) that $$ \underset{x}{\operatorname{argmax}} F(w) \in \left\{ \left\lfloor \frac{n+1}{\ell} \right\rfloor, \left\lceil \frac{n}{\ell} \right\rceil \right\}. $$ And though this result is efficient and easy to calculate, I somehow still want to see in some sense closed formula. Can you help me?

Proof. First of all, it is easy to see that $$ \left\lfloor \frac{n+1}{\ell} \right\rfloor = \left\lceil \frac{n}{\ell} \right\rceil \quad\text{or}\quad \left\lfloor \frac{n+1}{\ell} \right\rfloor + 1 = \left\lceil \frac{n}{\ell} \right\rceil. $$ Then, to prove the statement, it is sufficient to show that $F(w)$ increases for $w < \left\lfloor \frac{n+1}{\ell} \right\rfloor$ and decreases for $w \geq \left\lceil \frac{n}{\ell} \right\rceil$.

Consider a finite difference: $$ \Delta F(w) = F(w+1) - F(w) \,. $$

It can be expanded as follows: \begin{split} \Delta F(w) &= F(w+1) - F(w) \\ &= (w+1)\sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\binom{n-w}{i} \\ &= (w+1)\sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\left(\binom{n-w-1}{i} + \binom{n-w-1}{i-1}\right) \\ &= \sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\binom{n-w-1}{i-1} \,. \end{split}

We have: \begin{split} \Delta F(w) &= \sum_{i=0}^{\ell-1}\left( \binom{n-w-1}{i} - w\binom{n-w-1}{i-1} \right) \\ &= \sum_{i=0}^{\ell-1} \frac{(n-w-1)!}{i!(n-w-i)!}\left( n-i-w(i+1) \right) \,. \end{split} If we require that $$ w \leq \frac{n-\ell+1}{\ell} = \frac{n+1}{\ell} - 1 \,, $$ then it follows also that $$ w < \frac{n-i}{i+1} \quad \text{ for all } i < \ell-1 \,; $$ hence, each of the terms $(n-i-w(i+1))$ is positive for $i < \ell-1$ and $(n-\ell+1 - w\ell) \geq 0$. Therefore, $$ F(1) < F(2) < \dotsb < F\left(\left\lfloor \frac{n+1}{\ell} - 1 \right\rfloor\right) < F\left(\left\lfloor \frac{n+1}{\ell} \right\rfloor\right) \,. $$

On the other hand, we can write: \begin{split} \Delta F(w) &= \sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\binom{n-w-1}{i-1} \\ &= \sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-2}\binom{n-w-1}{i} \\ &= \binom{n-w-1}{\ell-1} + (1-w)\sum_{i=0}^{\ell-2}\binom{n-w-1}{i} \,. \end{split} And, if $w > 1$, we have: \begin{split} \Delta F(w) &< \binom{n-w-1}{\ell-1} + (1-w)\binom{n-w-1}{\ell-2} \\ &= \frac{(n-w-1)!}{(\ell-1)!(n-\ell-w+1)!} (n-w\ell) \,. \end{split}

If we further require $w \ge \frac{n}{\ell}$, then $\Delta F(w) < 0$ and $$ F\left( \left\lceil \frac{n}{\ell} \right\rceil \right) > F\left( \left\lceil \frac{n}{\ell} \right\rceil +1 \right) > \dots > F(n-\ell+1) \,. $$

Hopcroft-Karp Algorithm

Thu, 07/12/2018 - 01:46

I'm studying Hopcroft-Karp algorithm in bipartite graph.

I can understand the theorems about the algorithm, but I want to find a more specific example.

Can I find a bipartite graph that iterates an algorithm more than three times?

I tried to find it, but most of graphs ended in two iterations. (1 BFS + 1 DFS)

In arbitrary cyclic polygon $\sum_{i<j} A_iA_j^\alpha \ge \sum_{i<j} B_iB_j^\alpha $

Wed, 07/11/2018 - 23:39

I am looking for a proof of the inequality as follows:

Let $A_1A_2....A_n$ be the regular polygon incribed a circle $(O)$. Let $B_1B_2....B_n$ be a polygon incribed the circle $(O)$. I conjecture that:

$$\sum_{i<j} A_iA_j^\alpha \ge \sum_{i<j} B_iB_j^\alpha $$

Where $ 1 \leq \alpha \leq 2$.

  • The case $ \alpha = 1 $ was proved in our paper in here

  • The case $ \alpha = 2 $ was proved in here

Example:

  • $n=3$, let $ABC$ be a triangle with sidelength $a, b, c$ then we have the inequality as follows:

$$a^\alpha + b^\alpha+ c^\alpha \leq 3\times 3^{\frac{\alpha}{2}}R^\alpha$$ Where $ 1 \leq \alpha \leq 2$, $R$ is circumradius.

See also:

Floer cohomology from mapping spaces of $\infty$ categories

Wed, 07/11/2018 - 23:03

There's a meta-observation (of Urs Schreiber, who attributes it to Ken Brown and Lurie) that 'cohomology theories come from mapping spaces of infinity categories. This is described in detail at the nlab page on cohomology

I would like to understand if there's any non-contrived way that Floer-theoretic invariants fit into this picture.

I'm far from an expert. I'm aware of a number of works elucidating homotopy-theoretic aspects of Floer theory: for example the construction of Cohen-Jones-Segal, and the infinity category of Lagrangian cobordisms defined by Nadler-Tanaka. Do any of these constructions provide an answer to the question above?

Approximating a ray with an integer lattice point

Wed, 07/11/2018 - 22:56

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$

  • With $\|\cdot \|$ the 2-norm, what is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

  • How can this optimization be performed efficiently?

One idea for performing the optimization is by rounding onto the lattice along the ray $\alpha X$, varying $\alpha$ at each iteration to alter the fewest component's rounding possible. Then choosing the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. I believe this runs in no more than $O(n^2r).$

An inequality in counting formula

Wed, 07/11/2018 - 22:35

While counting I came across the following inequality:

$(x-1)^{n-1}(x+1) > \frac{1}{2}x^n$ when $x>n$.

In fact, I have both $x$ and $n$ integers and $\geq 3$.

For $n=3$ this is equivalent to proving: $x^2+x-1 < x^3/2$ which is true for $x > 3$.

I can easily verify this for $n=4,5$. However, I have not been able to prove this in general. Any help in this would be much appreciated.

The dual relationships between strictly singular operators and strictly cosingular operators

Wed, 07/11/2018 - 21:42

Recall that an operator $T:X\rightarrow Y$ between Banach spaces is called strictly singular if if it is not an isomorphism when restricted to any infinite-dimensional closed subspace of $X$. An operator $T:X\rightarrow Y$ is said to be strictly cosingular provided that for no infinite-dimensional Banach space $Z$ there exist surjective operators $R:X\rightarrow Z$ and $S:Y\rightarrow Z$ such that $R=ST$. It is elementary that an operator $T$ is strictly cosingular (strictly singular) whenever its adjoint $T^{*}$ is strictly singular (strictly cosingular, respectively). My question is the converse to this basic fact. More precisely, for an operator $T:X\rightarrow Y$,

Question 1. Under what conditions on $X$, the adjoint $T^{*}$ is strictly cosingular whenever $T$ is strictly singular?

Question 2. Under what conditions on $Y$, the adjoint $T^{*}$ is strictly singular whenever $T$ is strictly cosingular?

CW Product via Whitehead map

Wed, 07/11/2018 - 18:31

CW-complexes are defined via characteristic maps rather than from attaching maps, so via maps from $\mathbb D^n$ rather than from $\mathbb S^{n-1}$, because we have the propriety that $\mathbb D^n\times\mathbb D^m=\mathbb D^{m+n}$. I want to define products in a synthetic way, only manipulating objetcs up to homotopy so I need to use the spheres. So basically if $X$ and $Y$ are CW-complexes and $Z$ is the product, to attach one new cell to $Z_{p-1}$ means attaching a product of cells $\mathbb S^{n-1}\to X_{n-1}$ and $\mathbb S^{m-1}\to Y_{m-1}$, where $n+m=p$, and this should give a function $\mathbb S^{n+m-1}\to Z_{p-1}$. We actually already have such a map when the CW-complexes $X$ and $Y$ are the spheres $\mathbb S^{n}$ and $\mathbb S^{m}$, which is the Whitehead map. Indeed we have then $Z_{n+m-1}=\mathbb S^{n}\vee\mathbb S^{m}$ and this implies that the function is of type $\mathbb S^{n+m-1}\to \mathbb S^{n}\vee\mathbb S^{m}$. Now I want this bit to be generalizable to every product of finite CW-complex (it can have just a finite number of cells if nedded).

We want some function $\mathbb S^{n+m-1}\to Z_{p-1}$ and we would like to do the same thing as in the construction of the map $\mathbb S^{n+m-1}\to \mathbb S^{n}\vee\mathbb S^{m}$, so look a the pushout $\mathbb S^{n-1}\leftarrow \mathbb S^{n-1}\times\mathbb S^{m-1}\to \mathbb S^{m-1}$ but then the attaching maps of the cells are not trivial like they were for products of sphere. This looks very closely like the Whitehead product but I guess there is some non trivial things to consider at this point and I feel like I can't find the good way to tackle the problem.

I would like to know if some work about this had already be done, I'd be very glad that you have some synthetic reference about this problem.

Thank you very much

Insights from disproofs after counterexamples have been given

Wed, 07/11/2018 - 17:57

Some conjectures are disproved by a single counter-example and garner little or no further interest or study, such as (to my knowledge) Euler's conjecture in number theory that at least $n$ $n^{th}$ powers are required to sum to an $n^{th}$ power, for $n>2$ (disproved by counter-example by L. J. Lander and T. R. Parkin in 1966). But other conjectures retain interest, even after being disproved by counter-example, and lead to analytic disproofs and insights.

Question

What are some conjectures, first known to be false through counter-example, but whose subsequent analytic disproofs shed novel insights into the problem? More generally, what are the properties of known false conjectures that nevertheless garner significant interest and efforts of mathematicians to produce analytic disproofs?

Expected time of distinguishability of a series of Poisson processes bounded by each other

Wed, 07/11/2018 - 14:45

Consider a system of $n$ "bounded" Poisson processes over the integers, $X_1, \ldots X_n$, all incrementing at rate $\lambda$. Initially all the processes begin at $0$. The process $X_i$ is inactive until $X_{i+1} - X_i > 1$, at which point it begins incrementing itself at rate $\lambda$. Whenever $X_{i+1} - X_i \leq 1$, the process $X_i$ stops, waiting for $X_{i+1}$ to increment itself, before becoming active again. ($X_n$ is always active.)

We can see that eventually every $X_i$ will have a unique value. My question is regarding the expected time $E[\mathcal{T}]$ of the first time this event occurs: what is the first time all processes have a unique value?

A simple bound seems to be $E[\mathcal{T}] = O(n^2)$. However, my simulations indicate that this takes linear time in $n$. I'd love to see an analysis that shows something along the lines of $E[\mathcal{T}] = O(n)$, or any other asymptotic analysis for this system.

Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

Wed, 07/11/2018 - 11:21

Given two digraphs $G$ and $H$, I want a method for creating a bijection between all non-simple cycles of for all $n \le |V(G)|$. That means, given $C_G(n)$ and $C_H(n)$ being the sets of all non-simple cycles of length $n$ in $G$ and $H$ respectively, there is a bijection between these two sets. Here, non-simple cycles refers to a closed walk on the graph where we are allowing repeated vertices and edges.

First, it is known that tr$(A^n)$ where $A$ is the adjacency matrix of a graph gives the number of non-simple cycles of length $n$. So, in polynomial time, it is possible to determine whether such a bijection can exist between graphs $G$ and $H$. The question is how to find this bijection without simply enumerating all the possible cycles and pairing them off one by one which is at least an exponential algorithm.

My first thought was to use a cycle basis. However, when considering non-simple cycles, there isn't a unique vector representation in $\mathbb{Q}^{|E(G)|}$ since edges can repeat.

Are there any other representations of the cycles in a graph besides a cycle basis that could reduce the number of cycles to be considered to a polynomial amount?

Why should we study derivations of algebras?

Wed, 07/11/2018 - 08:05

Some authors have written that derivation of an algebra is an important tools for studying its structure. Could you give me a specific example of how a derivation gives insight into an algebra's structure? More generally: Why should we study derivations of algebras? What is the advantage of knowing that an algebra has a non-trivial derivation?

planar shapes of numbers respect to an optimal circle dartboard [on hold]

Wed, 07/11/2018 - 07:02

First this question came to my mind when I was contemplating on the numbers 1-20 arranged interestingly around a regular dartboard, then I proposed it on mathexchange here about 15 days ago and after some tuning by helps of @Ross Millikian ,it finished in this way:

QUESTION: Can we divide a circle with radius of $\sqrt{3}\sigma$ on a plain into 3 optimal pieces with equal areas assigned by $1,2,3$ as score ,which an ambitious dart player with density probability function of $f(r;\sigma )={\frac {r}{\sigma > ^{2}}}e^{-r^{2}/(2\sigma ^{2})}$[(Rayleigh distribution)][2]as probability of dart hitting in distance of $r$ from his aim point, achieves least score from the designed dartboard plane in his throw (guaranty getting minimum equal score from each point on board he may aim to shoot)?

Are the shapes unique?what are they look like?

Note1: if dart goes out of the board player will get $0$ score. $\sigma$ is standard deviation in Rayleigh distribution and dart hits in circle of radius $\sigma$ around player's aim point by probability of about $0.39$.

Note2: At first I proposed a generalized form of this problem stating to find $n$ connected regions in a plain which totally shape a connected closed board without any hole, assigned by $n$ natural numbers as score and the goal was to find optimal shape of each number ,But I found this simpler state of the problem as hard as enough to contemplate.

---Another Generalization can be considered: setting a desired predefined score probability function over the dartboard plane domain and the challenge is to design a dartboard which give us that predefined function as score probability in each point, like to design a deceiving dartboard which the score probability be least for points of region assigned by score $3$ and be highest for points of region assigned by score $1$. for easing the problem I have considered a constant function with minimum value which still finding its minimum value is challenging.

Eckmann-Hilton argument / Grothendieck

Wed, 07/11/2018 - 02:26

In terse terms, the “Eckmann-Hilton argument” says that a monoid in the category of monoids is commutative. It is essentially used, for example, to prove that homotopy groups of topological groups are commutative — more generally, that homotopy groups of H-spaces are commutative, in particuler, higher homotopy groups are commutative.

This argument takes its name from its appearance in a 1962 Eckmann-Hilton paper (Group-like structures in general categories, I. Multiplications and comultiplications, Mathematische Annalen, June 1962, Volume 145, Issue 3, pp 227–255) but stems, it seems, from previous work from the same authors (Homotopy and duality, 1959).

It also appears explicitly in algebraic geometry, in Grothendieck's 1961 SGA 1 seminar Revêtements étales et groupe fondamental, devoted to the theory of the fundamental group of schemes. Namely, in Exposé XI (Examples and complements), Section 2 (Abelian varieties), Grothendieck writes (bottom of page 287 of the Springer-Verlag edition) : “On the other hand, since the functor $X\mapsto \pi_1(X)$ from pointed schemes $X$ to groups commutes with produtct, it transforms a group in the first category to a group in the category of groups, i.e., a commutative group.”

Does anybody know whether the two groups of people were aware the one of the other? Was this categorical argument already clear at that time ?

Random $\beta$-transformation and its limit theorem

Tue, 07/10/2018 - 23:20

given probability space $ (\Omega, T, \mu), \mu$ is ergodic and $ T $ is invertible ( can regard $T$ as two sides shift)

define random $\beta$-transformations: random variable $\beta:\Omega \to (1,\infty)$. random $\beta$-transformations $ f_{\omega}: S^1\to S^1: x\to \beta_{\omega}\cdot x \mod(1) $.( it is in fact random Lasota Yorke maps)

let $ f_{\omega}^n=f_{T^{n-1}\omega} \circ f_{T^{n-2}\omega}\circ \circ \circ f_{T^{1}\omega}\circ f_{\omega}$, $ \phi \in BV[0,1]$.

consider the limit behavior of $ \frac{\sum_{i \le n} \phi \circ f_{\omega}^i}{n^{1/2}}$, can we prove it converges(in distribution) to Gaussian distribution a.s. $ \omega$ ( it is called quenched Central Limit Theorem)?

if $ \inf_{\omega}{\beta_{\omega}} >1$, then it is uniformly hyberbolic, the quenched Central Limit Theorem has been understood very well. what about the case $ \inf_{\omega}{\beta_{\omega}}=1$?

Many Thanks!

Pages