Recent MathOverflow Questions

Who wins infinite Hex?

Math Overflow Recent Questions - Wed, 09/27/2017 - 14:58

In this game, you start with a square. Alice tries to connect the top side to the bottom side, and Bob tries to connect the left side to the right side, like in Hex. Unlike in Hex, Alice and Bob use points instead of hexagons.

Now you might say that neither Alice nor Bob can win, since it is impossible to form a line using only finitely many points. Not so, for Alice and Bob can move infinitely many times!

In particular, let $S_\alpha$ be the state of the board, where $n$ is an ordinal. Then:

• If $\alpha=0$, then $S_n=\emptyset$.
• If $\alpha$ is a successor ordinal, then Alice adds $(n,p,Alice)$, where $p$ is some point in $[0,1] \times [0,1]$ that has not already been played, to $S_{\alpha-1}$, unless $S_{n-1}=[0,1] \times [0,1]$. She can use $S_{\alpha-1}$ to inform her discussion (in other words, Alice has a strategy function that given $S_{\alpha-1}$, gives her move). Bob does likewise.
• If $n$ is a limit ordinal, then $S_\alpha = \bigcup_{\beta<\alpha}S_\beta$.

We say Alice has won if there for some $\alpha$, there is a path in $[0,1] \times [0,1]$, composed of points corresponding to Alice's moves, connecting the top and bottom. Bob wins likewise, (connecting the left and right side of the boards).

Since there are ordinals $\alpha$ such that $|\alpha| > |[0,1]\times[0,1]|$, the board must eventually be filled (in particular, it will happen before such an ordinal).

One thing to note is that Alice and Bob can not both win, due to the Jordan curve theorem. On the other hand, it is possible for neither of them to win. In this case, Alice would have no curve connecting the top and bottom, and Bob would have no curve connecting the sides.

My question is:

• Does Alice have a winning strategy? (Bob doesn't, due to a strategy stealing argument.)
• Does Alice or Bob have a drawing strategy (a strategy that guarantees either a win or a draw)? (If Bob does, so does Alice.)

Fong's Causal Theories: Is he also describing a Monad structure? Is the causal category also a bimonad?

Math Overflow Recent Questions - Wed, 09/27/2017 - 13:36

Fong's paper Causal Theories: A Categorical Perspective on Bayesian Networks talks about causal theories. He describes words of random variables at the top of page 42:

For the objects of CG we take the set N V of functions from V to the natural numbers. These may be considered collections of elements of the set of variables V , allowing multiplicities, and we shall often just write these as strings w of elements of V . Here the order of the symbols in the string is irrelevant, and we write Ø for empty string, which corresponds to the zero map of N V . We view these objects as the variables of the causal theory, and we further call the objects which are collections consisting of just one instance of a single element of V the atomic variables of the causal theory.

Is he not just describing something like the List monad? A single element of V, the atomic variable, is the unit map $\mu : 1_C \rightarrow T$?

He explicitly states that objects have a comonoid map for copying. I get the feeling this causal category is a bimonad. Is this correct?

Some supporting evidence includes the following. This is taken from Coecke's paper, section 1.5.1.

Recall from [31] that the internal commutative (co)monoid structures over an object X in a monoidal category C are in one-to-one correspondence with commutative (co)monad structures on the functor X ⊗ − : C → C .

That functor is a comonad, according to the same paper.

So, Fong describes a comonoid, which has an associated comonad and I am pointing out the monad structure.

If it works, please describe the interaction of the monad and comonad (mixed distributive law?). I think Fong's examples are all on SET. So the Monad and Comonad would be on SET.

"There's a relationship between the monad structure and the comonad structure, or more exactly a mixed distributive law between them. In the terminology that some people use, this makes the monad into a "bimonad"."

Can these sequences stay integer-valued as many times as we want and then fail?

Math Overflow Recent Questions - Wed, 09/27/2017 - 12:14

Edit:

Suppose that we choose some integer $d$ and some natural number $c=c_2$. Then if we plug those values into $$c_{n+1}=\frac{c_n(c_n+n+d)}n$$ and observe the behavior of this recursively defined sequence ($n \geq 2$) then it can happen that it will produce integers up to some point and then fail. If we observe the space of tuples $(c_2,d) \in \mathbb N \times \mathbb Z$ then we can partition that set in the following way:

In $A_1$ go tuples for which only $c=c_2$ is an integer and $c_3$ is not, in $A_2$ go tuples for which $c_2$ and $c_3$ are integers and $c_4$ is not, ..., in $A_m$ go tuples for which $c_2,c_3,...c_{m+1}$ are integers and $c_{m+2}$ is not, ... , in $A_{\infty}$ go tuples for which every $c_n$ is an integer.

The question is: Is $A_m$ non-empty for every $m \in \mathbb N$?

Below is the question that I originally asked, and it is not the thing that I wanted to ask, I just wrongly formulated my thoughts. I will leave it as for the record, if someone knows how to cross it with some lines then I allow that to be done. Thank you.

Is it true that for every $m \in \mathbb N$ there exists integer $d$ and sequence $i \to c_i$ of positive integers which satisfies reccurence relation $$c_{n+1}=\frac{c_n(c_n+n+d)}n$$ in a way that the the first $m$ values of the sequence $c_i$ are integers and $(m+1)$-st value is not an integer?

Here are some related questions:

1

2

How to check if a box fits in a box?

Math Overflow Recent Questions - Wed, 09/27/2017 - 09:31

How could I calculate if a rectangular cuboid fits in an other rectangular cuboid, it may rotate or be placed in any way inside the bigger one.

For example would, (650,220,55) fit in (590,290,160), they are all mm.

Lagrangian up to Hamiltonian in cotangent bundle

Math Overflow Recent Questions - Wed, 09/27/2017 - 09:13

I want to understand the folklore conjecture that, in a CY manifold, Lagrangians up to Hamiltonian isotopies are represented by special Lagrangians by examining cotangent bundle and Hodge theory.

For a manifold $M$, its cotangent bundle $T^*M$ is naturally a symplectic manifold. Then a section of $\pi:T^*M \rightarrow M$ is Lagrangian if and only if it is a closed $1$-form. Here are my questions:

1. It is true that two Lagrangian sections are Hamiltonian isotopic iff their difference is exact? If not under what assumption is it true?

2. Given a Riemannian metric on $M$ that satisfies the real Monge-Ampere equation, it is possible to put a "nice" CY structure on $T^*M$? I know this is true when M is an affine manifold.

Assume they are true, we seem to be able to show the above conjecture by the Hodge theory that de Rham cohomology has harmonic representatives. Any comments and suggestions are welcome!

Simple recurrence that fails to be integer for the first time at the 44th term

Math Overflow Recent Questions - Wed, 09/27/2017 - 08:34

The sequence defined by $a_0=a_1 =1$ and $$a_n = \frac{1}{n-1}\sum_{i=0}^{n-1}a_i^2, \quad n > 1$$ fails to be integer for the first time at $a_{44}$. Why??

You can verify the statement by computing the sequence mod 43 (see more commentary here (day 5, problem 3)). That's not a very satisfying answer though. Is there a good reason for this behavior?

Recursion formula for analogue of Catalan numbers

Math Overflow Recent Questions - Wed, 09/27/2017 - 08:31

Let $C_n = {2n \choose n}\frac{1}{n+1} = \frac{(2n)!}{n!(n+1)!}$ be the $n$th Catalan number. Then there is a recursion formula: $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$. Now let $C_{n,k} = {2n+k-1 \choose n}\frac{k}{n+k}$. Then $C_{n,1}=C_n$. Are there some recursion formulas known for $C_{n,k}$? Thank you very much.

Finding modules to check for finite global dimension

Math Overflow Recent Questions - Wed, 09/27/2017 - 02:58

Given a finite dimensional algebra $A$ and a generator-cogenerator $M$ and let $B:=End_A(M)$. $B$ has finite global dimension iff every $A$-module has finite $add(M)$-resolution dimension, which is usually hard to check.

But $B$ also has finite global dimension iff every simple module $S_i$ has finite projective dimension iff $\Omega^2(S_i)$ has finite projective dimension.

Now $\Omega^2(S)$ is in the image of the functor $F:=Hom_A(M,-)$.

Can one somehow find $A$-modules $N_i$ such that $F(N_i)=\Omega^2(S_i)$? Here I mean a more or less explicit description in terms of $M$. Having those $N_i$, $B$ has finite global dimesnion iff all $N_i$ have finite $add(M)$-resolution dimension.

Advection reaction mixing equation converging to a Burgers type equation

Math Overflow Recent Questions - Tue, 09/26/2017 - 16:37

I am looking for references for the following notion. Suppose $\rho_1,\rho_2:[0,T]\times\mathbb R$ satisfy the following system of PDE: \begin{align} \frac{\partial \rho_1}{\partial t} &= -\kappa c_1 (\rho_1 - \rho_2) - u \frac{\partial \rho_1}{\partial x} \\ \frac{\partial \rho_2}{\partial t} &= \kappa c_2 (\rho_1 - \rho_2) \\ \end{align} Then as $\kappa \to \infty$, the solutions should converge to a common solution $\rho := \rho_1 \approx \rho_2$, which satisfies an advection equation $$\frac{\partial \rho}{\partial t} = - \frac{c_2 u}{c_1 + c_2} \frac{\partial \rho}{\partial x} \tag1$$ I would like to make this statement rigorous. I am particularly interested in the case when $c_1$ and $c_2$ depend upon $\rho_1$ and $\rho_2$, in which case equation (1) will be like the Burgers equation, see for example Section 3.4 of "Partial Differential Equations, 2nd Ed" by Lawrence Evans. Thus the solutions are susceptible to shocks, and I want to be sure that equation (1) should more properly be written in the weak form given in Evans, so that I can properly compute the speed of the shocks.

I am guessing someone has done this before, and I don't want to reinvent the wheel.

Containment of minimal 2-Ramsey-graphs in minimal 3-Ramsey-graphs

Math Overflow Recent Questions - Tue, 09/26/2017 - 13:58

Let $G$ be a minimal $2$-colour Ramsey-graph for $H$.

Must there exist a minimal $3$-colour Ramsey-graph $F$ for $H$ with $G\subset F$?

I am wondering if anything is known about this, particularly in the case $H=K_n$, at least for $n=3$.

(By G being an $r$-Ramsey-graph for $H$ I mean the property that every colouring of the edges of $G$ with $r$ colours admits a monochromatic copy of $H$. By minimal I mean minimal wrt. the subgraph relation.)

How close $k$-sums of a random set of numbers are on average?

Math Overflow Recent Questions - Tue, 09/26/2017 - 08:24

Consider a set of random iid variables $x_1, \ldots x_n$ uniformly distributed on $[0, 1]$. For each $S \subset [n]$ with $1 \leq |S| = k < n$ take $\sigma_S = \sum_{i \in S}x_i$. Obviously $\sigma_S$ are distinct with probability 1. What is the expectation of $\Delta = \min_{|S| = |S'| = k, S \neq S'} |\sigma_S - \sigma_{S'}|$, at least asymptotically? Can we say something about concentration of $\Delta$?

Countable graph that is "as non-traceable as it gets"

Math Overflow Recent Questions - Tue, 09/26/2017 - 06:27

If $\omega$ denotes the natural numbers, and if $E\subseteq\binom{\omega}{2}$ is any subset, we call a map $f\colon\omega\to\omega$ a walk in the graph $(\omega,E)$ if and only if $\{f(k),f(k+1)\}\in E$ for all $k\in\omega$.

We call $f$ a walk a Hamiltonian walk1 if and only if it is surjective.

Question.

Is there $E \subseteq \binom{\omega}{2}$ such that

1. there is at least one Hamiltonian walk in $(\omega,E)$,
2. every Hamiltonian walk in $(\omega,E)$ visits every vertex infinitely-often?

Remarks.

• A walk need not be injective, nor need it be surjective.

• Condition 1. implies that $(\omega,E)$ is a connected graph.

• In graph theory, an injective walk is called a path. (This is accidentally different from the usual convention in topology, where the term 'path' signals that self-intersections are permitted.)

• In graph theory, a graph admitting an injective and surjective walk into it is called traceable. (For finite graphs, the term Hamiltonian most often means that there exists a Hamilton path whose end-vertices are adjacent, i.e., a Hamilton circuit. For infinite graphs, this does not make sense (simply because then a Hamilton path does not have two "end-vertices"), which necessitates either (0) keeping to the study of Hamilton-paths only, or (1) using definitions involving some kind of 'convergence'.) This explains the focus of this question on Hamilton-paths, and the title of the OP.

1This terminology harmonizes rather well with e.g. the book Futaba Fujie, Ping Zhang: Covering Walks in Graphs. SpringerBriefs in Mathematics, 2014.

Is the sum of digits of $3^{1000}$ divisible by $7$?

Math Overflow Recent Questions - Tue, 09/26/2017 - 06:13

Is the sum of digits of $3^{1000}$ a multiple of $7$?

The sum of the digits of $3^{1000}$ can be computed using a computer. It is equal to $2142$, so the answer is positive.

Is there a short proof that the sum of the digits of $3^{1000}$ is a multiple of $7$ without using a computer?

Do you have any advice to solve this type of problem (without programming of course!)?

All the results below are mathematically proved:

• $3^{1000}$ has $478$ digits, and so the sum is at most $4302$ ($9\cdot478$).

• This sum is a multiple of $3$ and $9$.

• The last digits of $3^{1000}$ are $0001$ (math proof not a result of a computer calculation).

Context: We are a group of 3 French people working on it since 2007. It's a little exercise I found in my high school book (printed in 2007) which is pretty complicated. The one who created this exercise doesn't know the answer.

This question was previously asked here on Math.SE.

Easy proof that reflections generate $N(T)/T$ for connected compact group?

Math Overflow Recent Questions - Tue, 09/26/2017 - 04:16

I'm teaching a course on Coxeter groups and I'd like to provide an overview of the connection to compact Lie groups. Let $G$ be a compact connected Lie group, $T$ a maximal torus and $N(T)$ the normalizer. Then we can define the Weyl group $W$ as $N(T)/T$. Since $G$ is compact, the conjugation action preserves an inner product on $\mathfrak{g}$, so $W$ preserves an inner product on $\mathfrak{t}$.

Each root pair $(\pm \alpha)$ gives a map $\phi: SU(2) \to G$, and $\phi\left( \begin{smallmatrix} 0&-1 \\ 1&0 \end{smallmatrix} \right)$ lands in $N(T)$ and gives the reflection in $\alpha$. So we have a lot of orthogonal reflections inside $W$.

Is there an easy way to see that these orthogonal reflections generate $W$ defined as $N(T)/T$? I'm glad to use structural properties of reflection groups, since this is the actual topic of the course, but I certainly don't have time to develop the full Lie structure theory.

Problems reducing to a graph-theory algorithm

Math Overflow Recent Questions - Tue, 09/26/2017 - 03:35

This is essentially a question in pedagogy -- the answers could be useful to teach (or rather, motivate) graph theory, and especially the algorithmic side of it.

I have been very impressed with this example:

Question: What is the maximum size of a set of integers between 1 and 100 such that for any pair (a,b), the difference a-b is not a square ?

The first, naive algorithms that spring to mind to solve this (finite) problem are awkward. However, let me quote: " This problem can be defined as a Graph problem : we create a vertex for each integer, and link two integers if their difference is a square. We but have to find a maximal independent set in this graph ! "

Using this, a few trivial lines of Sage code give the answer (see the link). Sooo much time is saved for the coder!

Are there more examples like this one?

To be more precise, I'm looking for problems which:

• do not immediately involve graph theory, on the surface,
• reduce, after a little translation, into a common problem in graph theory (find a matching, find a colouring...).
• there should be a "haha!" effect for the mathematician, and a sigh of relief for the programmer.

I heard another nice one in a talk by Tim Gowers. A university wants to organize its exams. Some students take several exams. Some rooms and some time slots are available. Help them. Solution: each exam (maths, physics, etc) is a vertex; place one edge between exams if there is one student taking both; define "colours" to be pairs (room, time). Now you have to colour the graph such that adjacent vertices are in different colours.

There is a fine line between these great examples, and the articifial ones which I find disappointing, such as "$n$ couples having each $k$ children all want to shake hands on different days such that...". In fact, I should add that I'm certain to have a preference for problems involving maths (like the first one above) rather than "real life" (like the second).

Usual precaution: if this is not appropriate for MO, let me know and I will not be offended!

Towers of induced functions

Math Overflow Recent Questions - Mon, 09/25/2017 - 17:16

Suppose $\mathbb{X}$ and $\mathbb{Y}$ are classes, and $f:\mathbb{X}\rightarrow\mathbb{Y}$. It seems like pretty standard course to consider an 'induced function' $f:\mathcal{P}\mathbb{X}\rightarrow\mathcal{P}\mathbb{Y}$ defined by $f(U)=\{f(u):u\in U\}$ for all $U\in\mathcal{P}\mathbb{X}$, and $f=\langle f(U):U\in\mathcal{P}\mathbb{X}\rangle$ (where we have abused the symbol $f$ in a safe way since the former function induces the latter and vice-verse by the image of singletons).

This is done when considering the continuity of a function in topology, for example, since we actually want to consider the preimage of open sets of $\mathbb{Y}$ under the mapping $f:\mathcal{P}\mathbb{X}\rightarrow\mathcal{P}\mathbb{Y}$ instead of individual elements.

I was wondering if this behaviour had been formalized and studied, particularly the suggested inductive tower of functions defined by $$f_0=f:\mathbb{X}\rightarrow\mathbb{Y},$$ $$f_{n+1}=\langle f_n(U):U\subseteq dmn f_n\rangle,$$ so $dmnf_0=\mathbb{X},\ dmnf_1=\mathcal{P}\mathbb{X},\dots,dmnf_n=\mathcal{P}^n\mathbb{X}=\mathcal{P}\dots\mathcal{P}\mathbb{X}$. I believe we could further define $$\mathcal{P}^\omega\mathbb{X}=\bigcup_{n<\omega}\mathcal{P}^n\mathbb{X},$$ or perhaps $$\mathcal{P}^\omega\mathbb{X}=\{\mathcal{U}:\mathcal{U}\subseteq\bigcup_{n<\omega}\mathcal{P}^n\mathbb{X}\},$$ and then define $f_\omega:\mathcal{P}^\omega\mathbb{X}\rightarrow\mathcal{P}^\omega\mathbb{Y}$ in the same fashion as above and extend the recursion on $\omega$ to a recursion on all of $O_n$ where we repeat the above step each time we encounter a limit ordinal. This would allow for the construction of an inductive tower of functions $\{f_\alpha\}_{\alpha\in O_n}$, where each successor function $f_{n+1}$ is, in general, much more complicated than $f_n$ (for example if $f_n$ is defined on a countable set then $f_{n+1}$ will be defined on an uncountable set, so on and so forth, and it also seems like $f_{n+1}$ carries the 'topological information' about $f_n$ in some sense), but all members of the tower are faithfully induced by some single base function.

I thought that perhaps a model theorist or a set theorist had written something about this somewhere that I could read to enlighten myself, or that perhaps one of the members here could see some obvious connection to a more well-known area of mathematics.

EDIT: Another place where it appears we are implicitly thinking in this manner is fibrations -- the Hopf fibration $p:S^3\rightarrow S^2$ seems to be the unique function from $S^3$ to $S^2$ whose induced function $p_1:\mathcal{P}S^3\rightarrow\mathcal{P}S^2$ has the property that $p_1^{-1}(U)$ is a circle in $S^3$ iff $U$ is a singleton. I believe that higher geometrical thinking can also be done in this fashion, since all the 'shapes' in $\mathbb{R}^n$ are elements of $\mathcal{P}\mathbb{R}^n$, so functions to lower dimensional spaces whose induced functions map certain kinds of subsets onto singletons should be fibrations of some type.

My question is really whether or not there are books/articles/papers already written which explore this approach, understanding higher order properties of functions in terms of induced functions on higher order powersets rather than considering the action of a element-wise function on a subset/collection of subsets etc.

Covering a circle with small balls centered at nodes on a tiling

Math Overflow Recent Questions - Mon, 09/25/2017 - 09:43

In $\mathbb{R}$, we have $n$ finite sets, namely $\{A_1,A_2,\dots, A_n\}$. From them, we define a tiling: $$T := \{x\in \mathbb{R}^n: \forall i \in \{1,2,\dots,n\}, ~x_i\in A_i\} = \prod_{i=1}^nA_i$$ By difinition, there are $\prod_{i=1}^n|A_i|$ elements in $T$. For example, if $n=2$, $A_1 = \{1,2\}$ and $A_2=\{0\}$, then $T = \{(1,0),(2,0)\}$.

Define size of tiling as $\sigma(T) = \sum_{i=1}^n|A_i|$. Unit circle is denoted as $C =\{x\in \mathbb{R}^n: ||x||_2=1\}$. Given a small value $\epsilon$, we say tiling $T$ induces a $\epsilon$-covering of $C$ if $$C \subseteq \cup_{x\in T}B(x,\epsilon)$$ where $B(x,\epsilon)$ is a ball centered at $x$ with radius $\epsilon$.

Question 1: find $T_{min}$ such that $\sigma(T_{min})$ = $\min \{\sigma(T)$: $T$ induces a $\epsilon$-covering of $C\}$ and $T_{min}$ induces a $\epsilon$-covering of $C$.

Question 2: if it is hard to find an explicit expression of $T_{min}$ or $\sigma(T_{min})$, can we find a good estimation for $\sigma(T_{min})$?

Is "weakly good" series in a finite-dimensional Banach space "good"?

Math Overflow Recent Questions - Mon, 09/25/2017 - 03:14

Let us call a series $\sum_n x_n$ is a Banach space "good" if there exists a permutation $\sigma:\mathbb N\to\mathbb N$ such that the rearranged series $\sum_n x_{\sigma(n)}$ converges.

Find a simple proof of the following theorem (which was proved by E.Steinitz in 1913 according to V.Kadets).

Theorem. A series $\sum_n x_n$ in a finite-dimensional Banach space $X$ is "good" if and only if for every linear function $f:X\to\mathbb R$ the series $\sum_n f(x_n)$ is "good".

(This problem was posed in Lviv Scottish Book by Vaja Tarieladze from Tbilisi on 24.09.2017, see page 72 of http://www.math.lviv.ua/szkocka/view.php).

Maximal degree and chromatic number

Math Overflow Recent Questions - Sun, 09/24/2017 - 23:50

Given a positive integer $n\in \mathbb{N}$, is there a positive integer $k\in{\mathbb N}$ such that

for every finite, simple, undirected graph $G$ with $\Delta(G) = n$ we have $\chi(G) \leq k$

?

Morrey space is Banach space

Math Overflow Recent Questions - Sun, 09/24/2017 - 23:41

I'm working with Morrey spaces, which are the spaces $$L^{p,\lambda}(\Omega):= \left\{ u \in L^1_{loc}(\Omega): \sup_{x \in \Omega, r > 0} r^{-\lambda}\int_{B(x,r)\cap \Omega}|u(y)|^pdy< \infty\right\},$$ equipped with the norm $$\left\|u\right\|_{p,\lambda} = \left(r^{-\lambda}\int_{B(x,r)\cap\Omega}|u(y)|^p\right)^{1/p}.$$ Some notes (for example http://w3.ualg.pt/~ssamko/dpapers/files/251_Morrey_overview.pdf) said that they are Banach spaces with above norms. However, I cannot find a reference for proof of the case $\Omega$ is unbounded.

I want to ask for a book or a publish, where I can find the proof. Thanks for your help.