Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from 2017-12-12T17:39:16Z

Complexity of fixed variable integer program with OR condition (or equivalently on disjoint polytopes)

Mon, 08/28/2017 - 16:43

In Integer programming we seek to find $x\in\Bbb Z^n$ when $A\in\Bbb Z^{m\times n}$ and $B\in\Bbb Z^m$ are given and $Ax\leq B$ holds and we known an $O(n^nmL)$ arithmetic operation on $O(L)$ sized words complexity algorithm where $L$ is number of bits in any entry of $A$ and $B$.

Supposing we are given $A\in\Bbb Z^{m\times n}$ and $B_1,B_2\in\Bbb Z^m$ and if we are asked to find $x\in\Bbb Z^n$ such that $Ax\leq B_1$ or $Ax\leq B_2$ holds and $n$ is fixed and $L$ is number of bits in any entry of $A$ and $B_1,B_2$ then what is the best known complexity?

Vopěnka cardinals

Mon, 08/28/2017 - 16:43

A cardinal $\kappa$ is a Vopěnka cardinal just in case Vopěnka's principle holds in $V_\kappa$.

Suppose that $\kappa$ and $\lambda$ are both Vopěnka cardinals with $\lambda > \kappa$. Must it be the case that $V_\lambda \vDash$ "$V_\kappa$ is a Vopěnka cardinal"?

(Understand the predicate "… is a Vopěnka cardinal" after the turnstile as standing for a schema, since the informal claim is not directly expressible in $\mathsf{ZFC}$.)

Quotient of polynomial ring over a Dedekind domain

Mon, 08/28/2017 - 16:11

Let $A$ be a Dedekind domain and let $B:=A[X]/(f(X))$, where $f(X)\in A[X]$ is some monic polynomial such that $B$ is a domain. If I take the canonical map $A\longrightarrow B$, then it nduces a continuos map $\phi\colon \mathsf{Spec} \: B\longrightarrow \mathsf{Spec} \: A$. Now let us consider a maximal ideal $\mathfrak{p}\subset A$ and and let $\mathfrak{q}\in \phi^{-1}(\mathfrak{p})$. My question is:

Q. What is a necessary and sufficient condition on $f(X)$ such that the localization $B_\mathfrak{q}$ is a regular ring?

I just posted, without results, the question on MSE, but maybe this is the most suitable place.

Implication from an equality in terms of expectations for uniqueness proof

Mon, 08/28/2017 - 15:51

I have shown that a solution to a nonlinear equation exists, and I am trying to show it is unique. Let Y > 0 be a continuous non-constant random variable, and $a_1$, $a_2$ real parameters. I have determined that if

$${E(Y^{a_1+1})\over E(Y^{a_1})}={E(Y^{a_2+1})\over E(Y^{a_2})}\Rightarrow a_1=a_2$$

then the solution is unique. But I have not been able to make much progress in establishing whether the implication is correct, or whether it would be correct under some weak assumptions about Y (beyond finite mean and variance). If it helps, Y may be assumed to have finite support and the parameters may be assumed to be positive.

Any comments or suggestions would be greatly appreciated.

Equations satisfied by finite modular lattices

Mon, 08/28/2017 - 14:39

I found this very interesting paper by Freese, The Variety of Modular Lattices is Not Generated by its Finite Members, which shows that finite modular lattices satisfy an identity that is not satisfied by arbitrary modular lattices. Is more known about this? For example, is a complete list of identities satisfied by finite modular lattices but not general modular lattices known?

Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position

Mon, 08/28/2017 - 13:52

I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees.

Consider a 1D random walk on the integers, starting at the origin, each step going either $+1$ or $-1$ (the bias is irrelevant to the conditional probability I have in mind, but say it's probability $1/2$ either way). What I want to know is that, conditional on the walk ending up at point $N$ at time $T$, what is the probability that the walk never revisited the origin (other than the very first time point)? One could, of course, write out recurrences to compute such a probability algorithmically, but I'm hoping for some good closed form approximation.

The bias doesn't matter because ending up at point $N$ at time $T$ fixes the number of $+1$s and $-1$s in the walk, so really I'm asking for the proportion of the permutations of $\pm 1$s that do not revisit the origin.


When is the rank 2 free metabelian group of exponent $n$ center free?

Mon, 08/28/2017 - 13:10

Let $M_n$ be the rank 2 free metabelian group of exponent $n$. For which $n$ is $M_n$ center-free?

The abelianization $M_n^{ab}\cong C_n\times C_n$, so the commutator subgroup $M_n'$ is a cyclic $(\mathbb{Z}/n)[C_n\times C_n]$-module (generated by the commutator of a generating pair of $M_n$), and one can show using the Magnus embedding that $M_n'$ can be identified with the quotient ring $$R_n := (\mathbb{Z}/n)[x,y]/\langle 1+a+a^2+\cdots+a^{n-1}\rangle_{a=x^iy^j}$$ where $a$ ranges over all elements of the form $x^iy^j$ for all $i,j$ (essentially, $a$ is the image of an element of $C_n\times C_n$ in the quotient map $(\mathbb{Z}/n)[C_n\times C_n]\rightarrow R_n$)

For $M_n$ to be center free, we first need to check that

  1. No element outside $M_n'$ can act trivially on $M_n'$. This translates into $x^iy^j-1 = 0$ in $R_n$ if and only if $i\equiv j\equiv 0\mod n$.
  2. No element in $M_n'$ is centralized by all elements of $M_n^{ab}$ (or equivalently a generating pair). This translates into $Ann_{R_n}(x-1)\cap Ann_{R_n}(y-1) = 0$

I'm having some difficulty analyzing this ring $R_n$.

Certainly if $n = p^r$, then $M_n$ is a $p$-group, and hence cannot be center-free. My feeling is that for "large enough $n$" which are sufficiently far from being prime powers, $M_n$ should be center-free. Is this true? If not, can we give conditions on $n$ for which $M_n$ is center-free? Preferably, for every integer $m$, I would like to find an $n$ with $m\mid n$ such that $M_n$ is center-free.

Non-constructively Proving Existence of a Polynomial Time Algorithm

Mon, 08/28/2017 - 12:47

This is a fairly simple question related to the $P=NP$ problem:

Suppose that against all odds and expectation $P=NP$ were true, but the exponent of the polynomial were astronomically high and the shortest algorithm would require more instructions than there are atoms in the universe, so there were no chance of actually finding such an algorithm.


would it, under the hypothetical scenario as described above, be possible to prove that an $NP$ problem has a polynomial time solution and what would be the most promising ideas in that direction?

The reason for this question is my impression, that proofs for membership of problems in $P$ are always based on being able to find a polynomial time algorithm, or put differently, on proofs that can be readily converted into an algorithm, albeit an inefficient one.

On the other hand, attempts to decide the $P=NP$ question in the negative way are based on trying to prove the non-existence of polynomial time algorithms for $NP$-complete problems.

I am however not aware of the described possibility, that polynomial time algorithms exist, that will be out of reach of mankind forever, whereas proving the existence of such algorithms (e.g. by contradiction) might be possible.


obviously someone is aware of a proof that there is a fairly low bound on either the exponents or on the number of maximal instructions of polynomial time algorithms; may I kindly ask that person for sharing that knowledge?

Field extensions (non-algebraic)

Mon, 08/28/2017 - 12:15

Let k be a field, and L/k a finitely generated field extensions. I would like to know if one can classify intermediate extensions L/K/k such that K/k has transcendence degree one.

This question comes from geometry, where given a birational class of a variety X over k (with function field L), one considers pencils on X parametrized by a curve C over k (with function field K).

On independence and large cardinal strength of physical statements

Mon, 08/28/2017 - 11:48

The present post is intended to tackle the possible interactions of two bizarre realms of extremely large and extremely small creatures, namely large cardinals and quantum physics.

Maybe after all those paradoxes and uncertainty phenomena among weird tiny particles, which follow their own weird quantum logic, and after all those controversies surrounding the right interpretation of what is going on in the sub-atomic universe, the last straw that would break the camel's back could be the discovery of a series of statements in quantum theory which are independent or have large cardinal strength set theoretically. The fact that will send such physical statements beyond the realm in which the so-called usual mathematical tools can afford us a solution.

Not to mention that inspired by Hilbert's sixth problem and Godel's incompleteness theorems, some prominent physicists already brought up discussions concerning the possibility of obtaining independence results or existence of undecidable facts/theories in physics. In this direction see Stephen Hawking's lecture, Godel and the end of universe. [The corresponding post on MSE might be of some interest as well].

Anyway the bad (good?) news is that the intersection of large cardinal theory and quantum physics is non-empty (if not potentially large). For example one may consider the following theorem of Farah and Magidor in the Independence of the existence of Pitowsky spin models which contains an assumption of consistency strength of measurable cardinals. [cf. R. Solovay, Real-valued measurable cardinals, Axiomatic Set Theory, 1971.]

Theorem (Farah - Magidor): If the continuum is real-valued measurable then Pitowsky's kind spin function does not exist. The same holds in the model one gets from any universe of $ZFC$ by adding $(2^{\aleph_0})^+$-many random reals.

See also some related philosophical discussions regarding this result in:

One also might be interested in taking a look at the following papers which shed some light on the way forcing, Cohen reals, ultrafilters and various set theoretic concepts and tools play role in connection with some problems of quantum physics including hidden variables:

Inspired by Farah-Magidor's theorem and the other mentioned papers, the following question arises:

Question: What are some other examples of the statements in (quantum) physics which are mathematically independent or have some large cardinal strength (or at least make use of large cardinal assumptions in their formulation)?

Please provide references if you are aware of any such result.

Is any geodesic in the tangent cone of an Alexandrov space a limit geodesic?

Mon, 08/28/2017 - 11:38

If $X$ is an Alexandrov space of curvature bounded below by a real number $k$, is it true that any geodesic in the tangent cone $T_pX$ can be realized as a limit of geodesics when we view $T_pX$ as the Gromov-Hausdorff limit of rescalings of neighborhoods of $p$?

More generally, if $X_i$ is a sequence of Alexandrov spaces with curvatures bounded below uniformly by $k$ and $\dim X_i=n$, such that $X_i$ converges in the Gromov-Hausdorff sense to an Alexandrov space $X$ with $\dim X=n$ (i.e., the sequence is non-collapsing), is it true that any geodesic in $X$ is the limit of a sequence of geodesics in $X_i$?

First eigenfunction of $p=3$-Laplacian of a square domain in $\Bbb R^2$ : reference for any work on this?

Mon, 08/28/2017 - 08:17

In the last few decades, lots of work on first eigenfunction of $p$-Laplace with Dirichlet and other boundary conditions. But I couldn't find much on periodic boundary conditions. I have computed the first eigenfunction for $p=3$, square domain in $\Bbb R^2$. I have shown it as a grey scale image below. One period I tiled in the plane ($4\times 4$ tiles) to illustrate its meeting periodic boundary conditions.

I wonder such a simple structure not have a closed form expression. Can we guess anything on its closed form expression? Any reference to work in this direction (especially in dimension greater than $1$.)

Color picture :

Closest vertex in a 3D fcc lattice

Mon, 08/28/2017 - 07:54

The 3D fcc (face-centered-cubic) lattice, which has the same packing ratio as the 3D hexagonal close packed lattice, has the following 12 vectors connecting each vertex with its neighbors:

$(1,-1,0), (-1,1,0), (-1,-1,0), (1,1,0)$

$(1,0,-1), (-1,0,1), (-1,0,-1), (1,0,1)$

$(0,1,-1), (0,-1,1), (0,-1,-1), (0,1,1)$

If I have an arbitrary point $(x,y,z)$, I need a piecewise formula for finding which vertex in the lattice is the closest to it. I do not want an "algorithmic" solution, i.e. calculating distances to many vertices or computing voronoi cells.

Thank You!

spectral norm on sub-blocks of Hessian

Sun, 08/27/2017 - 22:12

Let $~f(x_1,\ldots,x_p) : \mathbb{R}^n \rightarrow \mathbb{R}$, $x_i \in \mathbb{R}^{d_i}$ for all $i=1,\ldots,p$ and $n=\sum_{i=1}^p d_i$. Suppose that for the $i$-th block varialbes $x_i,x_i' \in \mathbb{R}^{d_i}$, we have $$\| \nabla_i f(x_1,\ldots,x_{i-1},x_i,x_{i+1},\ldots,x_p) - \nabla_i f(x_1,\ldots,x_{i-1},x_i',x_{i+1},\ldots,x_p) \|_2 \leq L_i \| x_i - x_i'\|_2$$ and for the entire varialbes $x,x' \in \mathbb{R}^{n}$, we have $$\| \nabla f(x) - \nabla f(x') \|_2 \leq L \|x - x'\|_2,$$ then is it correct that for the Hessian of $f$, defined as $$\nabla^2 f(x) = H = \left[ \begin{array}{cccc} H_{11} & H_{12} & \cdots & H_{1p} \\ H_{21} & H_{22} & \cdots & H_{2p} \\ \vdots & \vdots & \vdots & \vdots \\ H_{p1} & H_{p2} & \cdots & H_{pp} \end{array} \right],$$ where $H_{ij} \in \mathbb{R}^{d_i \times d_j}$, the spectral norms satisfy$$\| H_{ij} \|_2 \leq \sqrt{L_i \cdot L_j}$$ and $$\| H_{*j} \|_2 \leq \sqrt{L \cdot L_j},$$ where $H_{*j} = \left[ \begin{array}{c} H_{1j} \\ H_{2j} \\ \vdots \\ H_{pj} \end{array} \right] \in \mathbb{R}^{n \times d_j}?$ Why? If not, what are the tight upper bounds of $H_{ij}$ and $H_{*j}$ in terms of $L_i,L_j$ and $L$?

Estimate of number of boundary components of a compact Riemannian 2-surface

Sun, 08/27/2017 - 10:07

Let $X$ be a compact smooth 2-dimensional Riemannian manifold with boundary. Assume that the Gauss curvature of $X$ is at least $-1$ and the diameter is at most $D$. Assume that near the boundary the surface is locally geodesically convex.

Is it true that the number of connected components of the boundary is bounded above by a constant depending on $D$ only?

Remark. I am not a specialist, but if I understand correctly the answer should be positive and follow from very general results in the Alexandrov geometry. Indeed due to local convexity, $X$ is an Alexandrov space of curvature at least $-1$. Each boundary component is an extremal subset in the sense of Perelman-Petrunin. In general the number of extremal subsets of a compact $n$-dimensional Alexandrov space of curvature at least $-1$ and diameter at most $D$ is bounded above by a constant depending on $n,D$ only. Is this argument correct? Anyway I would prefer to have a more direct argument in my case.

Isochronousation of quadratic vector fields with center

Sun, 08/27/2017 - 06:25

What is a classification of all quadratic vector fields

$$\begin{cases} x'=P(x,y)\\ y'=Q(x,y) \end{cases}\;\;\;\; (V)$$ with a center at origin such that $(\frac{x^2+y^2}{yP(x,y)-xQ(x,y})V$ has an isochronous center at $(0,0)$.

Here $P,Q$ are degree $2$ polynomials.

In particular does $y\partial_x-(x+x^2)\partial_y$ satisfy the above property?

The motivations is mentioned in the following two posts:

A curvature description for center condition for quadratic vector field

An explicit formula for a flat metric compatible to certain polynomial vector field with center

Is there winning strategy in Tetris ? What if Young diagrams are falling?

Sat, 08/26/2017 - 14:43

Question 1 Is there winning strategy (algorithm to play infinitely) in Tetris, or there is a sequence of bricks which is impossible to pack without holes ?

Consider generalized Tetris with Young diagrams ( for some "n") are falling down.

Question 2 is there winning strategy ? If not - consider some probability measure on Young diagrams ( e.g. uniform ) What will be "losing speed" ? I.e. how fast the height of uncancelled rows will grow for best possible algorithm ?

Question can one relate such Tetris like questions on Young diagrams with some conceptual/conventional theories where Young diagrams appear - representation theory of symmetric group or something else ?

On the sum $\sum_{n=1}^N z^{H(n)}$

Fri, 08/25/2017 - 19:16

Let $z$ be complex with $|z|=1$, $H(n)=\sum_{k=1}^n \frac{1}{k}$ be the $n$-th harmonic number, denote $$S=\sum_{n=1}^N z^{H(n)}$$ then what can we say about $S$? Does there exist a good upper bound on this sum?

What surreal numbers are representable by Red-Blue Hackenbush games?

Fri, 08/25/2017 - 19:03

Every game of Red-Blue Hackenbush represents a surreal number. Is the converse true? Assuming that it is false, what can be said about the class of surreal numbers that are representable by such games?

For instance, it is obvious that this class is a group under addition, but I can't visualize why it should even be closed under multiplication.

Does $R$ is dedekind-finite imply $\mathbb{M}_n(R)$ is dedekind-finite

Fri, 08/25/2017 - 18:55

Following Lam's notation, a ring (with identity) $R$ is called dedekind-finite if $ab=1\iff ba=1$ in $R$.

There are a lot of result about left invertible implies right invertible. But the results all require some finiteness property on the ring or the matrix ring. I am asking a proof or a couterexample of that that $R$ is dedekind-finite impies that the matrix ring $\mathbb{M}_n(R)$ is dedekind-finite.