Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from 2019-05-17T22:14:05Z

Minimize number of lattice paths below a given path

Sat, 05/11/2019 - 05:05

Every north-east lattice path (NE-path) $v$ from $(0,0)$ to $(k, a)$ can be identified with a sequence $0 \le \lambda_1 \le \lambda_2 \le . . . \le \lambda_k\le a$, that represent the hight of each step. There is a well known formula for the number of NE-paths from $(0,0)$ to $(k, a)$ below the $v$, namely $$ \ell(v)= \det_{1 \le i,j \le k} \left( \binom{\lambda_i+1}{j-i+1} \right).$$ Now my question is, for a fixed endpoint $(k,a)$, and a fixed number $n>a$, is it known which shape $0 \le \lambda_1 \le \lambda_2 \le . . . \le \lambda_k$ with $\lambda_1+ \dots + \lambda_k+a=n$ that gives the smallest value for $\ell(v)$? I. e. which shape should I give my path, so that there is as few paths below it as possible?

Coloring cliques of a clique decomposition of the complete graph

Sat, 05/11/2019 - 03:01

Let $G=K_k$, the complete graph on $k$ vertices. Consider the cliques induced by the sets of edges of a clique decomposition of $G$. Can you $k$-color the edges of $G$ so that each of the cliques in question is monochromatic, and so that if two distinct cliques share a vertex, their edges receive different colors? If the answer is yes, how do you prove it?

Methods of solving linear system of equations, how to select the appropriate method

Sat, 05/11/2019 - 00:37

A linear system of equations Ax=b can be solved using various methods, namely, inverse method, Gauss/Gauss-Jorden elimination, LU factorization, EVD (Eigenvalue Decomposition), and SVD (Singular Value Decomposition).
I know that there are several disadvantages of using inverse method; for example, with ill conditioned matrix A the solution can not be computed with inverse method. Moreover, I am know that with changing vector b LU factorization has advantage over Gauss/Gauss-Jorden elimination.
How to decide between LU, SVD, and EVD?
Is there any scenario where Gauss/Gauss-Jorden elimination has advantage over LU, SVD, and EVD?

A question about positivity preserving property of semigroup of Laplacian

Fri, 05/10/2019 - 23:57

Sry this the second question from the following article, I am asking in this week.

At page 6 (126), 3th line, of the following article.


the authors say by positivity preserving property of the semigroup $\{e^{t \Delta}\}$, we have:

$$ e^{\delta (\Delta+ V_n)}v_0 = \lim_{m \to \infty} (e^{\delta \Delta/m } e^{(\delta/m) V_n})^m v_0 \leq e^{\delta \lambda} e^{\delta \Delta} v_0$$

Here $\delta >0$, $V_n$ is a non-negative bounded function, $\| V_n\|_{\infty}\leq \lambda$ and $v_0$ is an initial value.

I can't understand this inequality. Why this limiting procedure is necessary and where the positivity preserving property is used?

Which interesting characterestic zero field $E$ (e.g a pseudofinite field) can support a Weil cohomology?

Fri, 05/10/2019 - 21:02

Let's consider the category of smooth projective varieties over a fixed characteristic $p>0$ algebraically closed field $k$. For a Weil cohomology theory with coefficient field $E$, by definition it shall satisfy finiteness property, Poincare duality, Kunneth formula, existence of cycle maps, weak and hard Lefschetz theorem.

Consider the class $\mathcal {C}$ of characterestic zero fields $E$ that support a Weil cohomology. Not all fields of zero characteristic can be a coeffiecient field, as is discussed in Serre’s example of a supersingular elliptic curve over $k$. We know

  • $\mathbb R, \mathbb Q_p \notin \mathcal{C}$.
  • For $E_1 \hookrightarrow E_2$, $E_1 \in \mathcal {C} \Rightarrow E_2 \in \mathcal {C}$ .

  • $\mathbb Q_l \in \mathcal {C}$ $(l \not = p)$ .

  • $W(k)[1/p] \in \mathcal {C}$.

More interestingly, we also know some pseudofinite field lie in $\mathcal C$, namely the ultraproduct of $\mathbb F_l$ $(l \not =p)$ using a non-principal ultrafilter, see "a new Weil cohomology theory" by Ivan Tomasic. And there is a dicussion of Weil II for such Weil cohomology theory, see

So my question is, can we describe other interesting fields in $C$ ?

For a fixed dominant weight $\lambda$, are almost all dominant weights in the same coset above it?

Fri, 05/10/2019 - 08:32

First some notation as in e.g. the book by Humphreys on Lie Algebras.

Let $E$ be an Euclidean space with inner product $(-,-)$, and denote $\langle v,w \rangle = \frac{2(v,w)}{(w,w)}$. Let $\Phi$ be an irreducible root system on $E$, so $\langle \beta, \alpha \rangle \in \mathbb{Z}$ and $\alpha - \langle \beta, \alpha \rangle \beta \in \Phi$ for all $\alpha, \beta \in \Phi$. Fix a set of simple roots $\alpha_1$, $\ldots$, $\alpha_l$.

Let $\Lambda$ be the set of weights, i.e. the set of $\lambda \in E$ such that $\langle \lambda, \alpha \rangle \in \mathbb{Z}$ for all $\alpha \in \Phi$.

Let $\Lambda^+$ be the set of dominant weights, that is, the set of $\lambda \in \Lambda$ such that $\langle \lambda, \alpha_i \rangle \geq 0$ for all $i$.

We have the usual partial order on $\Lambda$, by defining $\mu \preceq \lambda$ iff $\lambda - \mu = \sum_{i = 1}^k k_i \alpha_i$ for some integers $k_i \in \mathbb{Z}_{\geq 0}$.

It is well known that for a fixed $\lambda \in \Lambda^+$, there are only finitely many $\mu \in \Lambda^+$ such that $\mu \preceq \lambda$ (See for example 13.2 in Humphreys). But is the following true?

Fix $\lambda \in \Lambda^+$. Then for all but finitely many $\mu \in \Lambda^+$ with $\lambda - \mu \in \mathbb{Z}\Phi$, we have $\lambda \preceq \mu$.

If the answer is yes, this could be used to give a different solution to a previous question asked here: link.

Solution of equation on vector field

Thu, 05/09/2019 - 21:00

I have a vector field function $\vec{J}: {\bf R}^3\to {\bf R}^3$ looking like:

$$ \vec{J}(\vec{r}) = (\vec{B} \times \vec{v}(\vec{r}))\rho(\vec{r}) $$

with a (very well behaved) real, positive, differentiable scalar function $\rho: {\bf R}^3\to {\bf R}^+$ and the equation should hold for all non-zero constant ${\bf R}^3$ vectors $\vec{B}\ne\vec{0}$. For physical reasons I am out for the set of vector field functions $\vec{v}(\vec{r})$ such that

$$ \nabla \cdot \vec{J}(\vec{r}) = 0,$$

i.e. $\vec{J}$ gets divergence free in all points $\vec{r}$ in $\bf R^3$ (one specific $\vec{v}(\vec{r})$ should fulfill the condition for all $\vec{B}$). By simplification of the equation (looking at special joices of $\vec{B}$) I could guess a set of solutions

$$ \vec{v}_F(\vec{r})=\nabla F(\rho(\vec{r}))=f(\vec{r}) \nabla(\rho(\vec{r}))$$

i.e. effectively all vector fields that are parallel to $\nabla \rho$.

I conjecture that there are no other fields than $\vec{v}_F(\vec{r})$ such that the continuity is fulfilled. I like to proof that but fail. A "systematic" solution involves a singular linear equation system which seems to be a bit above my humble abilities to really handle with full oversight properly in a systematic manner (praying to god that this won't disqualify me to ask here), but I thought of trying something like a proof by contradiction by inserting a (scaled) component $\vec{v}_c{(\vec{r})}$ that is orthogonal to $\nabla \rho$ and assumed to be non-zero at least somewhere $(\vec{r}_0)$ and for all $\vec{B}$:

$$\vec{v}_c(\vec{r}_0) = \nabla \rho(\vec{r}_0) \times (\nabla \rho(\vec{r}_0) \times \vec{v}(\vec{r}_0))$$

But I fail to bring that to an happy end, since I end with three terms that might be non-zero but I do not know how to show that they eventually can't get zero when added up. A solution would be greatly appreciated.

(I feel that this is a border line case between MSE and MO, however since I am mostly out for the solution and since its a little but important puzzle stone in bigger research project, I finally decided to post it here)

Computability-theoretic results relevant to realizability

Wed, 05/08/2019 - 15:39

This may be a very naive question which only reflects my failure at literature search, but:

Although realizability (in its original form at least) is grounded in computability, the details of computability theory itself don't seem too relevant for realizability as far as I can tell. For example, I don't know of any result in realizability which relies on (say) the Low Basis Theorem or on the solution to Post's problem. Basic computability of course plays a role - e.g. whipping up realizability semantics appropriate for computability notions which lack universal machines, such as the primitive recursive functions, is difficult and interesting - but (to my practically-nonexistent knowledge) the deeper results don't seem to play a role.

My question is whether this is accurate. In particular, I'd be extremely interested in any significant role played by priority arguments in realizability.

The most relevant thing I've found is Charles McCarty's paper "Realizability and recursive set theory", which established a connection between isols/recursive equivalence types and realizability. There are many results about isols, of course, which are proved via complicated priority arguments. However, unless I'm missing something this seems to be a situation where realizability sheds light on the isols, rather than results about isols being relevant to realizability.

'Algebraic Skolemization' of (neo-)stable theories

Wed, 05/08/2019 - 14:48

A slightly obtuse way to say that a first-order theory $T$ has Skolem functions is to say that for any $M\models T$ and $A\subseteq M$, $\mathrm{dcl}(A)\preceq M$.

This suggests a similar condition with algebraic closure replacing definable closure, namely the condition that for any $M \models T$ and $A \subseteq M$, $\mathrm{acl}(A)\preceq M$. I'm sure this condition has a name and I feel like I've seen it before, but I couldn't find it, so I'll just call this property $(\ast)$.

In a paper of Kruckman and Ramsey they showed that under certain conditions it's possible to Skolemize an $\mathrm{NSOP}_1$ theory without breaking $\mathrm{NSOP}_1$. They also allude to a result of Nübling that makes it seem unlikely you can do much better.

In an extremely nice case, namely that of strongly minimal theories, it's always possible to expand the theory to satisfy $(\ast)$ without breaking strong minimality, specifically by adding constants naming the elements of the prime model.

So a specific initial question would be this:

Given a stable theory $T$ can you always expand $T$ to satisfy $(\ast)$ while preserving stability? If $T$ is $\kappa$-stable can you ensure that the expansion is also $\kappa$-stable?

And then of course you can ask similar questions about other neo-stability theoretic dividing lines, such as $\mathrm{NIP}$.

Quotient of $S^1$ by dense subgroups

Wed, 05/08/2019 - 14:31

I am trying to compute the quotients of the circle group $S^1$ by its various subgroups. So far, I have a rough classification of subgroups, namely that all finite subgroups of order $n$ are the $n$-th roots of unity $\Gamma_n$, and all other subgroups are dense in $S^1$.

For the case of finite subgroups, the group homomorphism sending $a \mapsto a^n$ gives an isomorphism between $S^1/\Gamma_n$ and $S^1$ by the first isomorphism theorem.

I am somewhat lost when it comes to a dense subgroup $H$; Is it even possible to determine the quotient $S^1/H$ knowing only that $H$ is a dense subgroup, or would one require a more specific classification of subgroups? How could I proceed to better classify the subgroups, or compute the quotient?

Bounds for integral of square root of rational function

Wed, 05/08/2019 - 13:41

Are there any upper and lower bounds for the following integral: $$f_n(x)=\int_{x}^{+\infty}\sqrt{\frac{t^n}{\prod_{i=1}^n(t-a_i)}}\exp(-t)dt$$ where $n$ is a positive integer, $a_1>a_2>...>a_n>0$ are given real numbers and $x>a_1$?

I conjecture the upper and lower bounds should look like $$\approx x^{n/2}\exp(-x)\prod_{i=2}^n\frac{1}{\sqrt{x-a_i}}$$

The crucial feature of the bounds should be that when we set $x=a_1$ and any $a_i=a_1,i\neq1$ in the bounds, both bounds should diverge to infinity.

I have found something shocking, a function that factors semiprimes,with virtually 0 computation time, how? [on hold]

Wed, 05/08/2019 - 13:03

I wont share the function here, but if you want to know im telling the truth, give me a semiprime k = pq, where p>q-p.(also up to 256 bits and base 10).I have tested this function with semiprimes up to 256 bits. I can share more details, or even the function itself, for a price. For now all i want to know is if this can help solve the Riemann hypothesis.

set theory question that also regards independent and dependent events [on hold]

Wed, 05/08/2019 - 12:17

It is given that for some events A and B, we have P(A) = 0.2, P(B) = 0.1 and P(A ∩ B) = 0.02. Find P(B|A). Are the events A and B independent? Why or why not?

A set, product of any two elements minus one is a perfect square

Wed, 05/08/2019 - 11:17

The first problem of IMO 1986 asks the following:

Prove that, one can find two distinct $a,b$ in the set $\{2,5,13,d\}$ such that $ab-1$ is not a perfect square.

Note that, this proves, for the set $S=\{2,5,13\}$, and for any distinct $x,y\in S$, $xy-1$ is a perfect square, and that, adding any other element to $S$ violates the condition.

Now, the natural question is the following. What is the largest $n$, for which, there exists a set $\{x_1,\dots,x_n\}$ of distinct positive integers, for which, $x_ix_j -1$ is always a perfect square? Clearly, $n\geq 3$, due to the argument above.

Remark : This problem arised as a post in AoPS forums, currently having no (useful) replys.

How to use probability to find a matching in a family of graphs?

Wed, 05/08/2019 - 11:16

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references to such examples?

$\int_{-\infty}^\infty \frac{e^{-y^2/2}}{((y+y_0)^2+x_0^2)^r} dy$

Wed, 05/08/2019 - 11:15

I have to estimate the integral $$\int_{-\infty}^\infty \frac{e^{-y^2/2}}{((y+y_0)^2+x_0^2)^r} dy,$$ for $r\in \mathbb{R}^+$. I am a little amazed that Sage and Wolfram Alpha have nothing to say about it, and that Gradshteyn-Ryzhik doesn't seem to have anything on it either; it feels like a rather natural integral, the denominator being a distance function.

Of course I realize that, if I just expand $1/((y+y_0)^2+x_0^2)^r$ into a Taylor series around $y=-y_0$ and integrate term-by-term, I am not going to get something convergent; what I get is an asymptotic formula. But what is the right order of magnitude of the error term when the formula gets cut off at the $k$th term?

For instance: let $f(y)=1/((y+y_0)^2+(x_0^2))^r$ and write $$f(y) = f(y_0) + \frac{(y-y_0)^2}{2} O^*(\max_t f''(t)).$$ Then we get an error term of size $O(1/x_0^{2 r + 3})$. If we go up to a higher-order approximation, we obtain an error term of the form $O(1/x_0^{2(r+k)+1})$ for higher $k$. But can one also give an error term that depends on $y_0$ and not just on $x_0$, and thus is better when $x_0$ is large and $y_0$ is much larger still?

Note also asked on MSE.

Reference Request: Carnot Groups over Complexes

Wed, 05/08/2019 - 11:13

Is there a theory of complex (analytic) Carnot groups and Caratheodory metrics?

Distribution of combining teams of beginning size 1

Wed, 05/08/2019 - 10:14

Let there be k initial teams of size 1. For j steps, at each step pick two teams at random and merge them. After j steps what is the distribution of X_i, the size of team i? What can we say about how the variance of team sizes changes at each step? At step 1 it increases and at the k-1 step it goes to 0.

Extension: Let the initial team sizes be s_1, ..., s_k, where they sum to 1. They follow Dirichlet distribution with parameter 1,...,1. What can we say about how the variance of team sizes changes at each step?

Algebra Question [on hold]

Wed, 05/08/2019 - 09:41

3x=15 Can you help me with this question please So ,we did it in class but I need a help with them, because I don't know what to do next.Can anybody explain the method so I know it the next time.

Method to draw 3-connected planar graph on a sphere

Wed, 05/08/2019 - 05:58

The Tutte embedding is a way to create a "nice" drawing of a 3-connected planar graph in the plane, after having chosen an outer face.

Is there a similar method to draw such a graph on a sphere? Steinitz's theorem suggests that such a drawing is possible.

Of course, we could just map the planar coordinates to a sphere with some arbitrary projection, but this does not produce a "nice" drawing, e.g. it will not reflect the natural symmetries of the graph, and will not produce a dodecahedron for a dodecahedral skeleton. While "nice" is not a very well defined term, I assume there must be some existing work on this topic.