Recent MathOverflow Questions

Variant of Kneser hypergraph with elements appearing more than once

Math Overflow Recent Questions - Sun, 04/23/2017 - 23:38

A Kneser hypergraph is a hypergraph with the vertices being the subsets of $M=\{1,2,\dots,m\}$ of size $l$ and the edges being the collections of size $r$ of these subsets such that any two subsets are disjoint. The Alon-Frankl-Lovasz theorem gives the chromatic number of this graph.

Has a variant of this been considered, where instead of any two subsets of the collection having to be disjoint (or equivalently, any element $m\in M$ appears in at most one subset of the collection), we require that any element $m\in M$ appears in at most $d$ subsets of the collection for some value $d>1$? If so, is there a corresponding result on the chromatic number?

$\frac{|t_n^{j}- t_n^{l}|}{(\lambda_n^{j})^2} \to \infty \implies t_n^{l}- t_n^{j} \left( \frac{\lambda_n^{j}}{\lambda_n^{l}} \right)^2 \to \infty$

Math Overflow Recent Questions - Sun, 04/23/2017 - 22:45

Fix indices $j\neq l \in \mathbb N.$ Let $\{t_n^{l}, t_n^{j} \} \subset \mathbb R, \{\lambda_n^{j}, \lambda_n^{l} \} \subset (0, \infty).$

Assume that $\frac{|t_n^{j}- t_n^{l}|}{(\lambda_n^{j})^2} \to \infty$ as $n\to \infty$ and $\frac{\lambda_n^{j}}{\lambda_n^{l}} \to \lambda_0 \in (0, \infty)$ as $n\to \infty.$

Question: Can we expect: $t_n^{l}- t_n^{j} \left( \frac{\lambda_n^{j}}{\lambda_n^{l}} \right)^2 \to \infty$ as $n\to \infty?$

Treat Directed Graph as Undirected Graph

Math Overflow Recent Questions - Sun, 04/23/2017 - 21:59

Suppose there is a directed graph of which every two nodes have connections to each other but with DIFFERENT WEIGHTS. In this case, this is a strong connected digraph (cycle), but it also looks like a undirected graph since the connections between every two nodes are bidirectional (but with different weights).

Actually I think those theorems or properties that apply to undirected graph CANNOT apply to this kind of digraph as discussed above. Am I right?

For example, does the following theorem apply to the directed graph mentioned above?

For a connected graph $G$ that is undirected, we have: $$\min_{x \ne 0, ~ > 1^Tx=0}\frac{x^TLx}{||x||^2}=\lambda_2(L)$$ wherer $L$ is the Laplacian matrix of graph $G$ and $\lambda_2$ is the Fiedler eigenvalue of $L$, i.e., the second smallest nonzero eigenvalue.

Fixed point iteration using derivatives

Math Overflow Recent Questions - Sun, 04/23/2017 - 20:42

Let $g(x)= \mathrm{\lim_{n \rightarrow \infty}}\,f^{\circ n} (x)$, where $f^{\circ n} (x)$ is the repeated application of $f$ to $x$, $n$ times. Why doesn't the following procedure work for determining $g(x)$:

Since $g(x)=f(g(x))$, we have

$g'(x) = f'(g(x)) g'(x)$ [chain rule]

The $g'(x)$ functions cancel, leaving:

1=f'(g(x)).

For example, if $f(x)=\sin (x)$, this equation gives $1=\cos(g (x))$. So $g(x)=2\pi m$, which is correct when m=0.

But if if $f(x)=\cos (x)$, this equation gives $-1=\sin(g (x))$. So $g(x)=-\pi/2+2\pi m$, which is not correct for any integer $m$, since $g(x) \approx 0.739$

Minimax solution but game has no value

Math Overflow Recent Questions - Sun, 04/23/2017 - 19:09

Fix convex sets $\Delta,\Pi$ and let $r: \Pi \times \Delta \in [0,\infty]$ be linear (i.e., concave and convex) in its first parameter for every fixed second parameter.

I'm looking for a situation where 1) the corresponding zero-sum game has no value, i.e., $$\sup_{\pi \in \Pi} \inf_{\delta \in \Delta} r(\pi,\delta) \neq \inf_{\delta \in \Delta} \sup_{\pi \in \Pi} r(\pi,\delta)$$ but 2) there exists a minimax solution, i.e., there exists $\delta_0 \in \Delta$ such that $$\sup_{\pi \in \Pi} r(\pi,\delta_0) = \inf_{\delta \in \Delta} \sup_{\pi \in \Pi} r(\pi,\delta).$$ (Note that I've swapped the order of variables from the usual game presentation to match the statistical setting when $r$ is interpreted as (average) risk.)

Clearly, such a situation cannot arise when both $\Pi,\Delta$ are compact and $r : \Pi \times \Delta$ is concave-convex because such games always have values by the minimax theorem. When I've come across counterexamples to a game having a value, this usually also results in there being no minimax solution.

Am I missing an obvious obstruction, or can someone point me to an example, or to where I can read more about existence of minimax solutions when the game has no value?

Roots of unity with square in the image of a Dirichlet character

Math Overflow Recent Questions - Sun, 04/23/2017 - 18:17

Let $\chi$ a Dirichlet character modulo $N$. Can we find explicitly the cardinality of the following set: $$\{\ \zeta\; \text{root of unity}\; : \; \zeta^2\in\text{Im}(\chi)\}$$

How do you factor x out of sin(x)? [on hold]

Math Overflow Recent Questions - Sun, 04/23/2017 - 18:14

im a rookie comp sci student and as part of agame algorithim i need to factor out x out of the equation ax+sin(x). I dont know how itll be help if i get any direction how to solve thia.Thabka in advance

Range of the coheight of the maximal ideal of a non-trivial, Dedekind-finite, commutative, reduced monoid $H$ (as a fnc of $H$)

Math Overflow Recent Questions - Sun, 04/23/2017 - 18:01

Let $H$ be a multiplicatively written, commutative monoid with identity $1_H$, and set $M := H \setminus \{1_H\}$. It is not difficult to show that for $M$ to be an ideal of $H$ it is necessary that $H$ is Dedekind-finite, and it is sufficient that $H$ is non-trivial, Dedekind-finite, and reduced (for the sufficient part, see Edit 2 in Question #267943). Remarkably, the following are equivalent:

1. $M$ is an ideal of $H$.
2. $M$ is a prime ideal of $H$.
3. $M$ is the maximum element of the poset of proper ideals of $H$ with respect to $\subseteq$.

With this in mind, we denote by $\mu(H)$ the supremum of all $n \in \mathbf N^+$ for which there exist prime ideals $\mathfrak p_1, \ldots, \mathfrak p_n$ of $H$ such that $\mathfrak p_{i-1} \subsetneq \mathfrak p_i$ for each $i \in [\![1, n]\!]$, where $\sup \emptyset := 0$ and $\mathfrak p_0 := M^2 := \{xy: x, y \in M\}$. To wrap it in buzzwords, $\mu(H)$ is the coheight of $M^2$ relative to the fundamental ideal system of $H$. My question is the following:

Q. What about the set of values attained by $\mu_H$ as $H$ ranges over the class of all non-trivial, Dedekind-finite, commutative, reduced monoids (that are small relative to a given non-empty universe $\mathscr U$)? More specifically, is it a bounded set? If not, is it the entire $\mathbf N^+$?

A positive answer to the first of these questions would provide a negative answer to the related question linked in the above (with the advantage that the questions of this thread are much more "localized", so they will hopefully attract more attention).

Notes. We say that $H$ is reduced if the only unit (or invertible element) of $H$ is the identity, and Dedekind-finite if $xy = 1_H$, for some $x, y \in H$, implies $yx = 1_H$. A set $I \subseteq H$ is called an ideal if $IH = I$. Then a prime ideal of $H$ is an ideal $I \ne H$ such that $H \setminus I$ is a subsemigroup of $H$.

Decomposition of finitely generated algebras

Math Overflow Recent Questions - Sun, 04/23/2017 - 17:19

Let $k$ be a field and $A$ a finitely generated algebra over $k$. I know that if $A$ is finite dimensional as a vector space over $k$, then $A$ can be decomposed as a product of indecomposable $k$-algebras: $$A=A_1\times\ldots\times A_n$$ My question is if there is a similar decomposition of an arbitrary $k$-algebra.

I'm not sure how to approach this problem because of the existence of descending chains, for example in $k[x]$ there is a chain: $$\langle x\rangle\supseteq\langle x^2\rangle\supseteq\langle x^3\rangle\supseteq\ldots$$ and the existence of idempotents with arbitrary degrees. I also tried to show the existence of an $N\in\mathbb{N}$ such that every idempotent in $k[x_1\ldots,x_n]/\langle f_1,\ldots,f_m\rangle$ can be seen as a sum of idempotents in $k[x_1\ldots,x_n]/\langle f_1,\ldots,f_m,x_1^N,\ldots,x_n^N\rangle$. But I have not had luck, so any help would be appreciated.

Thanks, Luis

Comparing the growth of $f\circ g$ and $g\circ f$

Math Overflow Recent Questions - Sun, 04/23/2017 - 14:36

I asked this Question on Math.StackExchange without success. Then I learned, that this might be the better place to ask. So, sorry for crossposting. I would agree on deleting my old question.

Let $\mathbb R_0^+:=\{x\in\mathbb R\mid x\geq 0\}$. Further let $f:\mathbb R_0^+\rightarrow \mathbb R_0^+$ and $g:\mathbb R_0^+\rightarrow \mathbb R_0^+$ two strictly increasing continuous functions (this can be weakened if necessary).

Is there anything that can be said about which of the functions $f\circ g$ and $g\circ f$ grows asymptotically faster (in some sense) with only assuming something about the asymptotic growth behavior of $g$ and $f$?

I want to discuss this in a very general context. So I am open for all kinds of useful definitions of "grows faster" and "growth behavior". E.g. one can consider the usual $\mathcal O$-notation and ask for whether

$$f\circ g\in\Omega(g\circ f)$$

whenever $f\in\Omega (g)$ or $g\in\Omega(f)$. But neither seems to hold in general. For example, conider $$f(x)=\log(x)\quad\text{and}\quad g(x)=x^\alpha.$$ Which of $f\circ g$ and $g\circ f$ grows faster depends on $\alpha$, while $g\in\Omega(f)$ regardless of $\alpha$. Also possible: we can call $f$ growing faster than $g$ if $f(x)>g(x)$ for all sufficiently large $x$.

I was not abled to proof anything remotely useful for the connection between the "growth" of $f$ and $g$ and the connection between the "growth" of $f\circ g$ and $g\circ f$. So this is a soft question because I hope for input from no specific branch of math.

Further useful assumptions might be

• $f$ and $g$ are convex functions.
• $f(x)>x$ and $g(x)>x$.

I tried to prove

If $f>g^n$ for all $n\in\mathbb N$ ($g^n$ means $g$ iterated $n$ times), it holds $g\circ f< f\circ g$.

For example, use $g(x)=x^2$ and $f=\exp$. I have not succeeded for any definition of growth so far but it seems plausible to me, at least for convex functions $f$ and $g$ strictly greater than identity.

How to braid a ribbon knot

Math Overflow Recent Questions - Sun, 04/23/2017 - 09:03

Is there any algorithm known for braiding ribbon knots? More specifically I need to braid a generic ribbon knot presented as boundary of a ribbon surface= union of two 0-handles and one 1-handle. (Unfortunately MO did not allow me to add a picture).

A problem about normal distribution, independent random variables

Math Overflow Recent Questions - Sun, 04/23/2017 - 04:59

Suppose $\alpha_1, ..., \alpha_n$ are independent identically distributed random variables, $a_1, ..., a_n,b_1,...,b_n$ are non-zero constants. Is it true that if $\sum_{i=1}^{n}a_i\alpha_i$ and $\sum_{i=1}^{n}b_i\alpha_i$ are independent, then $\alpha_1, ..., \alpha_n$ are normal variables?

On minimal solutions to a family of linear diophantine equations?

Math Overflow Recent Questions - Sun, 04/23/2017 - 00:36

Let $a,b>0$ be coprime with $p=a+b$ and $q=a-b>0$ primes and let $L=pp'-qq'$ where $0<p'<q$ and $0<q'<p$ satisfy $pp'\equiv1\bmod q,\quad qq'\equiv1\bmod p$.

What is the least $|n|\in\Bbb Z\backslash\{0\}$ at which both $|x|<a$ and $|y|<b$ hold in $$x(a-bL)+y(b-aL)=n(a^2-b^2)$$ family parametrized by $n$ with integer $n\neq0$?

When are $\mathbb{R}^n$ and $\mathbb{R}^m$ essentially similar?

Math Overflow Recent Questions - Sat, 04/22/2017 - 16:59

Here is a rather vague and subjective question: for which $n$ and $m$ are $\mathbb{R}^n$ and $\mathbb{R}^m$ essentially similar''? The answer depends partly on what type of mathematician is answering it.

Of course, in a certain technical sense, $\mathbb{R}^n$ and $\mathbb{R}^m$ are different for any $n\neq m$ since they are not homeomorphic (or linearly isomorphic); thus they by definition differ in some describable topological (or algebraic) way. But qualitatively all Euclidean spaces, especially ones of large dimension, seem to be similar.'' The question is really: how large does $n$ have to be for Euclidean spaces of dimension $\geq n$ all to behave essentially the same way?

I have included my own discussion of some possible answers in my Real Analysis manuscript at http://wolfweb.unr.edu/homepage/bruceb/Meas.pdf (Section XI.18.3). I invite comments on this discussion.

"Ergodicity" of non-invariant product measures (with respect to the shift)

Math Overflow Recent Questions - Sat, 04/22/2017 - 07:00

Let $(X_n)$ be a sequence of independent but not necessarily identically distributed random variables with $\mathbb{E}X_n = 0$ for all $n$. If the $X_n$ are uniformly bounded, Kolmogorov's strong Law of Large Numbers implies that $(1/n)\sum_{i=1}^n X_i \rightarrow 0$ almost surely.

Now let $S$ be a metric space and let $T$ be the shift operator on $S^\mathbb{N}$, that is $T(x_0,x_1,\dots) = (x_1, x_2,\dots)$. Consider a product probability measure $\mu = \prod_{i=0}^\infty \mu_i$ on $S^\mathbb{N}$ (thus $\mu$ is generally not invariant unless $\mu_i = \mu_0$ for all $i$).

For a given bounded, continuous function $f$ on $S^\mathbb{N}$ of the form $f = g \circ \pi$, where $g$ is a continuous bounded function on $S$ and $\pi(x_0,x_1,\dots) = x_0$, let $$X^f_n(\boldsymbol{x}) := f\circ T^n(\boldsymbol{x}) - \int f\circ T^n(\boldsymbol{y})\,\mu(\mathrm{d}\boldsymbol{y}).$$ On the probability space $(\Omega, \mathbb{P}) := (S^\mathbb{N}, \mu)$, we have that $(X_n^f)$ is a sequence of independent random variables with $\mathbb{E}X_n^f = 0$ for all $n$, with $\sup_{\boldsymbol{x},n}X_n^f(\boldsymbol{x}) < \infty$. Thus by the SLLN we have $(1/n)\sum_{i=0}^{n-1}X_n^f \rightarrow 0$ ($\mu$ a.e.).

Therefore, given a product probability measure on $S^\mathbb{N}$, a property analogous to ergodicity (w.r.t. $T$) holds when we restrict ourselves to continuous bounded maps of the form $f = g\circ\pi$ as above.

My question is: does this property still hold for the general $f\in C_b(S^\mathbb{N})$?

Supremum of a stochastic process

Math Overflow Recent Questions - Thu, 04/20/2017 - 22:14

Let $(x_1,...,x_N)$ be points in $R^d$, and $\sigma=(\sigma_1,...,\sigma_N)$ are i.i.d. Rademacher variables (+1 or -1 with probability 0.5 each). (Or alternatively, $\sigma$ could be a standard Gaussian vector.) Also let $z$ in some subset of $R^d$, and $\|\cdot\|_2$ will denote the Euclidean norm. I am looking for a good upper estimate of:

$E_{\sigma} \sup_z \| \sum_{n=1}^N \sigma_n \frac{x_n-z}{\|x_n-z\|_2} \|_2$.

So far I only got the upper bound of $N$ (by triangle inequality), and the lower bound $\sqrt{N}$ by Jensen inequality, and I would like to know if there is a way to improve on the upper estimate? Are there any conditions under which the upper bound would reduce to ${\mathcal O}(\sqrt{N})$?

Quotient of complex manifold by a free and locally proper action (difficulty with reading German)

Math Overflow Recent Questions - Thu, 04/20/2017 - 21:31

Let $X$ be a complex manifold with an action of $G=GL(V)$ which is free and locally proper (each point of $X$ has a $G$-invariant neighborhood on which $G$ acts properly.)

Satz 24 of the paper

H. Holmann, Quotienten komplexer Ra ̈ume, Math. Ann., 142 (1961), pp. 407–440

asserts that $X/G$ is a complex manifold.

Why is it true?

The biggest issue is, since I cannot read German, I don't know if by "free" he means set-theorecial free or scheme-theoretical free (the latter is in the sense of Mumford's GIT book.)

commutative Künneth-diagram (using spectral sequences)

Math Overflow Recent Questions - Thu, 04/20/2017 - 21:07

Let $R$ be a principal ideal domain, $C_*$ and $D_*$ chain complexes of free $R$-modules. Then there is a convergent Künneth spectral sequence of the following form:

$$E^2_{p,q} = \bigoplus_{q_1+q_2=q} \mathrm{Tor}_p^R\bigl(H_{q_1}(C_*),H_{q_2}(D_*)\bigr) \Rightarrow H_{p+q}(C_* \otimes D_*).$$ And under the above assumptions this sequence reduced to the Künneth exact sequence $0 \to E^2_{0,n} \to H_n \to E^2_{1,n-1} \to 0$.

Now I am stuck to write down formally using spectral sequences, that If one "just flips the chain-complexes" $C_*\otimes D_*\to D_*\otimes C_*$, that following diagram commutes $$\require{AMScd}\def\Z{\mathbb{Z}} \begin{CD} 0 @>>> \bigoplus_{q_1+q_2=n} H_{q_1}(C_*) \otimes H_{q_2}(D_*) @>>> H_{n}(C_* \otimes D_*) @>>> \bigoplus_{q_1+q_2=n-1} \mathrm{Tor}_1^R\bigl(H_{q_1}(C_*),H_{q_2}(D_*)\bigr) @>>> 0 \\ @. @VVV @VVV @VVV @. \\ 0 @>>> \bigoplus_{q_1+q_2=n} H_{q_1}(D_*) \otimes H_{q_2}(C_*) @>>> H_{n}(D_* \otimes C_*) @>>> \bigoplus_{q_1+q_2=n-1} \mathrm{Tor}_1^R\bigl(H_{q_1}(D_*),H_{q_2}(C_*)\bigr) @>>> 0 \\ \end{CD}$$where the vertical maps are induced by the flip map $C_*\otimes D_*\to D_*\otimes C_*$. The proof should be a naturality argument and symmetry of Tor, but I am stuck to proof the commutativity formmally using spectral sequences, I'm especially the right square in this diagram. My question is: How to prove formally, using spectral sequences, that the right square of this diagram commutes?

Exploiting symmetries to speed up Groebner basis calculation?

Math Overflow Recent Questions - Thu, 04/20/2017 - 20:43

Take a collection $F$ of homogeneous polynomials in $\mathbb{C}[x_1,\ldots,x_n]$, along with a finite group $G$ of linear operators over $\mathbb{C}^n$ such that for every $f\in F$ and $g\in G$, we have $f\circ g\in F$. Can one exploit these symmetries to produce speedups in computing a Groebner basis for $\langle F\rangle$?

Faugère and Rahmany's work suggests that speedups are available when $G$ is a group of permutations, but the applications I have in mind do not use such groups.

University-level topics appropriate for entering high-school contest preparation

Math Overflow Recent Questions - Thu, 04/20/2017 - 20:39

This is a re-post of this math.SE question which seems to be getting no answers.

I occasionally teach high-school students to prepare them for various math olympiads (with the final goal being the International Math Olympiad, IMO. It's my impression that over time the "curriculum" of the IMO and math olympiads more broadly (admittedly a vaguely defined concept) has been gradually shifting towards some of the more advanced and technical topics traditionally associated with university-level mathematics education. To name a few examples, we've already seen applications of linear algebra in combinatorics, the combinatorial Nullstellensatz, and the probabilistic method.

However, in mathematics we often value generality above accessibility (and for good reasons), which leads to some very beautiful ideas being inaccessible to the olympiad community until the person with the right intuition, examples and exposition comes along at the right time to transmit those ideas.

Thus, I've been wondering if we can compile a list of such ideas (together with illuminating accessible examples and expositions) which have recently entered the olympiad culture, or which are now becoming ripe for entering it.

Just one example that comes to mind: Fourier analysis on cyclic groups is a very accessible tool which has some rather deep consequences, such as Roth's theorem on arithmetic progressions (a self-contained proof can be found in these notes from a course taught by Tim Gowers). Thus, I wonder whether there might be nice examples of the use of Fourier-analytic ideas of this flavor in math competitions.