Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from mathoverflow.net 2017-11-21T15:06:57Z

Diameter of a weighted hamming cube

Fri, 11/17/2017 - 12:07

Let $C=(\mathbb{Z}/2\mathbb{Z})^N$ be the hamming cube with its usual graph structure, and assume each edge $e=(x,x+\epsilon)$ (where $x\in C$ and $\epsilon$ has one $1$ and $N-1$ zeros) is given a length $\ell(x,\epsilon)$ satisfying the constraints $$ \sum_\epsilon \ell(x,\epsilon) \le 1 \qquad \forall x\in C.$$ Denote by $d_\ell$ the distance function induced by these lengths.

Q1: What is the growth of the largest possible diameter $D(N)$ for such $(C,d_\ell)$?

I think I can prove a bound $D(N) \lesssim log(N)$, but I wonder if a constant bound could be true.

In fact, this is not the real question I have, but it seemed a reasonable way to get to it. The real question is about functions $f:C\to \mathbb{R}$ such that $$(1) \qquad \sum_\epsilon \lvert f(x+\epsilon) - f(x) \rvert \le 1 \qquad \forall x\in C$$ and of vanishing average.

Q2: What is the largest possible value $\lVert f\rVert_\infty$ for such a function?

(My motivation is a toy example to test some concentration inequalities for Markov chains. In some cases I figured the semi-norm $\max_x \sum_\epsilon \lvert f(x+\epsilon)-f(x)\rvert$ should be efficient for the Glauber dynamic (aka lazy random walk) on $C$, but I need the above to get a good spectral gap in the corresponding functional space)

Norms of elements in Artin-Schreier extensions

Fri, 11/17/2017 - 09:37

The following is claimed in the proof of Theorem 7.5 of Auslander, Goldman, "The Brauer group of a commutative ring":

Let $k$ be a nonperfect field of positive characteristic $p$, let $K := k(x)$ be the function field in one variable, and let $L := K[y]/(y^{p}-y-x)$ be the Artin-Schreier extension of $K$ associated to $x \in K$. For any $c \in k^{\times} \setminus (k^{\times})^{p}$, there does not exist $\ell \in L$ such that $c = \mathrm{Nm}_{L/K}(\ell)$.

Why is this true?

Remarks:

  1. An arbitrary element of $L$ is of the form $\ell = f(y)$ for some polynomial $$ f(T) = a_{0} + a_{1}T + \dotsb + a_{p-1}T^{p-1} $$ of degree at most $p-1$ with $a_{i} \in K$, and in this case we have norm $\mathrm{Nm}_{L/K}(\ell) = \prod_{i=0}^{p-1} f(y+i)$. However I am not sure if this product simplifies to a nice expression in $x$ and the $a_{i}$. For $p=2$ the product is $(a_{0}^{2} + xa_{1}^{2}) + a_{0}a_{1}$ and for $p=3$ the product is $(a_{0}^{3} + xa_{1}^{3} + x^{2}a_{2}^{3}) + (-a_{0}a_{1}^{2} - a_{0}^{2}a_{2} + a_{0}a_{2}^{2} - xa_{1}a_{2}^{2})$.
  2. See also Example 11.6.9 of Fried, Jarden, "Field Arithmetic" which treats the $p=2$ case.

Keywords: Artin-Schreier extensions, Galois, cyclic, norm

Infinite strongly rigid graphs

Fri, 11/17/2017 - 01:08

Is there an infinite connected simple undirected graph $G=(V, E)$ such that the identity map $\text{id}_V: V\to V$ is the only graph self-homomorphism from $G$ to itself?

(A graph self-homomorphism is a map $f: V\to V$ such that for all $e\in E$ with $e = \{v, w\}$ we have $\{f(v), f(w)\} \in E$.)

Nontrivial lower bound on the sum of matrix norms

Thu, 11/16/2017 - 13:51

Let $X, V\in\mathbb{R}^{n\times r}$ such that $X^\top V$ is symmetric. The central quantity I care about is \begin{equation} \|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2. \end{equation} An easy lower bound for this quantity is given by $2\sigma_{r}(X)^2\|V\|_{F}^2$, where $\sigma_{r}(X)$ is the smallest singular value of $X$.

I'm wondering whether there exists some $c>0$ such that the following holds \begin{equation} \|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2\geq c\|X\|_{F}^2\|V\|_{F}^2. \end{equation}

Original statement of Naimark's dilation theorem

Thu, 11/16/2017 - 08:41

Naimark's dilation theorem in papers and textbooks is usually stated as:

Let $E$ be a regular, positive, $B(\mathcal H)$-valued measure on $X$. Then there exists a Hilbert space $\mathcal K$, a bounded linear operator $V: \mathcal H \rightarrow \mathcal K$, and a regular, self-adjoint, spectral $B(\mathcal K)$-valued measure $F$ on $X$, such that $E(B) = V^*F(B)V$ (from Paulsen's book Theorem 4.6).

What was the original formulation of Naimark's dilation theorem? It seems conceivable that it changed over the 70+ years.

Did he assume regularity, or is this assumption coming from the later version of this theorem proved by Stinespring. Were his operator-valued measures weakly countably additive?

My trouble is that I cannot find the original paper:

Neumark, M. A., On a representation of additive operator set functions, C. R. (Doklady) Acad. Sci. URSS (N.S.), 41, (1943), 359--361

Does anyone know if this paper is legitimately online anywhere, in Russian or an English translation? As Willie Wong mentions in the comments my fall back will be interlibrary loan.

Making images arbitrarily dense under an expanding map

Wed, 11/15/2017 - 22:13

Let $f\colon \mathbb{R}^2 \to \mathbb{R}^2$ be a $C^2$ uniformly expanding diffeomorphism that fixes the origin: that is, $f(0)=0$ and there is $\lambda>1$ such that $d(f(x),f(y)) \geq \lambda d(x,y)$ for all $x,y\in \mathbb{R}^2$. [The original question just asked for a locally expanding map; I've clarified that it should be a globally expanding diffeomorphism.]

Let $X=\{(t,0) : t\in \mathbb{R}\}$ be the $x$-axis in $\mathbb{R}^2$. Is it possible that the images $f^n(X)$ become arbitrarily dense in the unit ball? Or do they satisfy some sort of "uniformly nowhere dense" condition?

More precisely, my first instinct is to expect that the following result is true: for every $f$ as above, there is $\delta>0$ such that for every $n\in \mathbb{N}$, there is some $y\in B(0,1)$ such that $B(y,\delta) \cap f^n(X) = \emptyset$.

After some effort I've been unable to prove this statement. On the other hand, playing around with candidate counterexamples hasn't gotten me anywhere either: the closest I've come is to consider the maps \begin{align*} g(x,y) &= (x, y + A \sin(Rx)), \\ h(x,y) &= (x + A\sin(Ry), y) \end{align*} for some choice of the parameters $A$ and $R$, then choose $c>0$ large enough that $f(x,y) = ch(g(x,y))$ is uniformly expanding. Taking $A=.06$ and $R=100$ gave some interesting pictures, but numerically it seems that I can only make the images $f^n(X)$ continue to get denser in the unit ball if I take $c$ small enough that $f$ is not expanding everywhere.

Which leads me to the question: does every expanding map $f$ as in the first paragraph admit a $\delta$ satisfying the condition in the second paragraph? Or is there a clever counterexample hiding out there somewhere?

Edit: As suggested in the comments, another natural class of maps to consider take the form $f(z) = c e^{ig(|z|)} z$ for $z\in \mathbb{C}$, where $g\colon [0,\infty) \to \mathbb{R}$ must be a $C^2$ function with $g'(0)=0$ to make $f$ be $C^2$. Then $f^n(X)$ spirals around the origin, but we can control the total amount of spiraling by a bounded distortion result: Writing $X^+$ for the positive $x$-axis, then given $r>0$, the point on $f^n(X^+)$ with modulus $r$ has argument given by $h(r) := \sum_{k=0}^{n-1} g(c^{-k} r)$, and we have $$ |h(r) - h(t)| \leq \sum_{k=0}^{n-1} |g(c^{-k}r) - g(c^{-k}t)| \leq \sum_{k=0}^\infty |g|_{\mathrm{Lip}} c^{-k} |r-t| = C|r-t|, $$ which means that $f^n(X^+)$ is the graph in polar coordinates of a function $\theta(r)$ that is $C$-Lipschitz. Then it is not hard to show that there is $\delta>0$ satisfying the condition above.

Name for a Regularity Condition for Triangulations

Wed, 11/15/2017 - 06:56

given $P=\lbrace p_1\dots p_n|p_i\in\mathbb{R}^2\rbrace$, let $t_{ijk}$ be the triangle with corner set $\lbrace p_i,p_j,p_k\rbrace\subset P$ and $T$ some triangulation of $P$, i.e. one of the maximal subsets of $\lbrace t_{ijk}\rbrace$ whose elements have pairwise disjoint interior.

Question:
is there a name for triangulations $T^*$, for which $\cup_{j,k} t_{ijk}$, is convex for every vertex $p_i\in P$ and the set $\lbrace t_{ijk}\rbrace_{T^*}$ of triangles $t_{ijk}$ adjacent to it in $ T^*$?
That question naturally generalizes to higher dimensions.

Additional question:
does such a triangulation exist for every planar point set?

Trapping lightrays with segment mirrors

Wed, 11/15/2017 - 06:11

Q. Is it possible to trap all the light from one point source by a finite collection of two-sided disjoint segment mirrors?

I posed this question in several forums before (e.g., here and in an earlier MO question), and it has remained unsolved. But I've recently become re-interested in it. Let me first clarify the question. It seems best to treat the mirrors as open segments (i.e., not including their endpoints), but insist that they are disjoint as closed segments. And the point source of light should be disjoint from the closed segments.          
          Lightray starts at center, exits (green) after $31$ reflections. Of course a finite number of rays can be trapped periodically, and less obviously a finite number of rays can be trapped nonperiodically. But it seems quite impossible to trap all rays from a single fixed point. Because of segment disjointness, there are paths to $\infty$, and it seems likely that some ray will hew closely enough to some path to escape to $\infty$. So I believe the answer to my question is No.

Perhaps application of Poincaré recurrence could lead to a proof, but I cannot see it. Related: Can we trap light in a polygonal room?.

Some quasi differential equation

Wed, 11/15/2017 - 05:53

The ring of entire holomorphic functions is denoted by $Hol(\mathbb{C})$.

Is there a complete classification of all $f\in Hol(\mathbb{C})$ such that the $Hol(\mathbb{C})$-module generated by $\{f,f',f'',\ldots,f^{(n)},\ldots\}$ would be equal to the whole ring $Hol(\mathbb{C})$?

Is there a complete classification of all $f\in Hol (\mathbb{C})$ such that the $\mathbb{C}$_ module (or $Hol (\mathbb{C})$_ module generated by $\{f^{(n)}, f^{(n+1)}, \ldots\}$ is independent of $n$?

The generalization of commutative property of orthogonal projectors on a subspace to the whole space.

Wed, 11/15/2017 - 05:43

Let for $i\in [n]$, $P_i$ be some orthogonal projectors defined on the vector space $W$ such that they commute on subspace $V < W$ (i.e, for any $i, j \in [n]$ and $v \in V$: $P_iP_j(v) = P_jP_i(v)$). Are there $n$ projectors $\hat{P}_i$ such that they operate the same as $P_i$ on $V$ (i.e, for any $i\in [n]$ and $v\in V$, $\hat{P}_i(v)= P_i(v)$) and they commute on the vector space $W$?

Multiplication on cubic hypersurfaces and partially defined groups

Wed, 11/15/2017 - 05:29

Let $V$ be a general smooth projective cubic hypersurface. Doing literally as in case of cubic curves we define a relation on $V\times V\times V$: $(x,y,z)$ satisfy it iff $x+y+z$ is an intersection of $V$ with a line. Contrary to the one-dimensional case this relation is not a graph of a binary operation ($x^2$ is not defined or two points may lie on the line contained in $V$). From now on let us consider only pairs $(x,y)$ for which $z$ is uniquely defined (that is $(x,y,z)$ are on a line and there is one such $z$, let's denote it by $x\circ z$). Let's chose some $u$ (that will be the 'unit') and define the product as usual $xy=u\circ (x\circ y)$. This partially defined product however may be non-associative in the following sense: there are $x,y,z$ such that $$x(yz)\neq(xy)z$$ where $yz$,$xy$, $x(yz)$ and $(xy)z$ are uniquely defined.

Are there any examples of such non-associative triples?

Continuous map with homeomorphic fibers whose associated $H^{k}_c$ sheaf is not a local system?

Wed, 11/15/2017 - 05:08

Let $ f: X \to Y$ be a continuous map between connected manifolds s.t. for all $y \in Y$ the fiber $f^{-1}(y)$ is homeomorphic to some fixed connected manifold $Z$.

Let $k$ be a ring and for every $j \ge 0$ let $\mathcal{H}^j:=R^{j}f_!(k_X)$, i.e. the shefification of the presheaf on $Y$ given by:

$$U \mapsto H_{c}^{j}(f^{-1}(U),k)$$

Question: Must $\mathcal{H}^j$ be a local system on $Y$? If not what's a counterexample?

Planar polynomial vector field for a harmonic pair of polynomials

Wed, 11/15/2017 - 05:04

Has the system of ODEs $$\frac{dx}{dt}=P(x,y)\\ \frac{dy}{dt}=Q(x,y) $$ been studied for the special case of the polynomials $P$ and $Q$ being a harmonic pair, i.e. the real and imaginary part of a holomorphic polynomial $F=F(z)$, $z=x+iy$?

I am looking to learn a bit about (complex) ODEs and their interplay with algebraic geometry by some examples, but I couldn't find anything on this special case in Ilyashenko's survey on Hilbert 16 (I guess this case is too special and/or not very interesting as far as Hilbert 16 is concerned).

Nontheless, it seems very natural. If we set $\gamma(t)=x(t)+iy(t)$, this amounts to the equation $$ \int_{\gamma_t}\frac{dz}{F(z)}=t $$ where $\gamma_t$ is the curve $\gamma$ "truncated" at $t$ and the RHS is in particular real. This can be taken further, for example by assuming $\gamma$ is closed and using the residue theorem to obtain constraints on (the coefficients of) $F$.

Connection on line bundle over general simplicial toric variety

Wed, 11/15/2017 - 04:53

In https://arxiv.org/pdf/hep-th/0005247.pdf, on page 60 and 61, it is mentioned that the connection of $\mathcal{O}(-n)$ over a (simplicial) toric variety of the form $$ (\mathbb{C}^N \backslash U)/(\mathbb{C}^*) $$ is $$ A= -n{i\over 2}{\displaystyle~\sum \!{}_{i=1}^N (\overline{\phi}_i{d} \phi_i-{d}\overline{\phi}_i \phi_i)~\over \displaystyle \sum \!{}_{i=1}^NQ_i|\phi_i|^2}, $$ in terms of complex homogeneous coordinates $(\phi_i,\overline{\phi}_i)$ which obey the equivalence relation

$$ (\phi_1,\dots,\phi_N)\sim (\lambda^{Q_1} \phi_1, \ldots, \lambda^{Q_N} \phi_N), \\ $$ with the weights $Q_i\in \mathbb Z$ and $\lambda\in \mathbb{C}^* = \mathbb{C}-\{0\}$.

My question is, how does the connection generalize to the case of a general (simplicial) toric variety $$ (\mathbb{C}^N \backslash U)/(\mathbb{C}^*)^m, $$ which contains a set of homogeneous coordinates $(\phi_i,\overline{\phi}_i)$ equipped with a number $m$ of equivalence relations $$ (\phi_1,\dots,\phi_N)\sim (\lambda_r^{Q^{(r)}_1} \phi_1, \ldots, \lambda_r^{Q^{(r)}_N} \phi_N), \\ $$ for $r=1,\dots, m$ with the weights $Q^{(r)}_i\in \mathbb Z$ and $\lambda_r\in \mathbb{C}^* = \mathbb{C}-\{0\}$?

Since the Picard group for a general simplicial toric variety is $\mathbb{Z}^{N-m}$, an arbitrary line bundle on such a variety is of the form $\mathcal{O}(k_1,k_2,\ldots,k_{N-m})$, so I believe the connection should be expressible in terms of the integers $k_1,k_2,\ldots,k_{N-m}$.

Lower bound for the degree of the inverse of a polynomial automorphism

Wed, 11/15/2017 - 04:06

Let $F=(F_1,\dots,F_n)\in\mathbb{C}[X_1,\dots,X_n]^n$ be a polynomial automorphism $\mathbb{C}^n\to\mathbb{C}^n$ with inverse $G=(G_1,\dots,G_n)$. Let $d:=\deg F:=\max_{1\leq i\leq n}\deg F_i$ be the degree of $F$. It is then known that $\deg G\leq C(n,d):=d^{n-1}$.

Is there a known or a conjectured lower bound $c:=c(n,d):=c(n,d,\dots)$, i.e. possibly depending on other parameters and perhaps conditional on some conjecture like the Jacobian one, such that $\deg G\geq c$ ?

Obviously, as soon as $F$ is non-linear, $\deg G\geq 2$. Moreover, the trivial converse gives us that if $\deg F= g = e^{n-1}$ for some $e\in\mathbb{N}$, then $\deg G\geq e$, so one is inclined to conjecture something like $c(n,d)=\lfloor\sqrt[n-1]{d}\rfloor$. But it seems doubtful to be optimal on account of $(n-1)$-powers being rather scarce in $\mathbb{N}$. I wasn't able to locate anything further on a lower bound in van Essen's book.

The Wallman and interval topologies on non-principal ultrafilters with the Rudin-Keisler preorder

Wed, 11/15/2017 - 03:31

If $(P,\leq)$ is a pre-odered set (that is, $\leq$ is a reflexive and transitive relation) and $x\in P$, we set $(\uparrow_{\leq} x) = \{p\in P: p\geq x\}$ and $(\downarrow_{\leq} x) = \{p\in P: p\leq x\}$.

Let $\text{NPU}(\omega)$ be the set of non-principal ultafilters on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by $${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\exists f:\omega\to\omega)(\forall U\in{\cal U}) f^{-1}(U)\in {\cal V} .$$

Question. If ${\cal U}\in \text{NPU}(\omega)$ are $(\downarrow_{\leq_{RK}} {\cal U})$ and $(\uparrow_{\leq_{RK}} {\cal U})$ closed in the Wallman topology on $\text{NPU}(\omega)$?

Note. This would imply that the Wallman topology contains the interval topology of $(\text{NPU}(\omega), \leq_{RK})$.

Every profinite group is a quotient of a profinite free groups?

Wed, 11/15/2017 - 03:28

It is well known that any group is a quotient of two free groups. More precisely if $G$ is a group the exists a short exact sequence of groups $$1\rightarrow F^{'}\rightarrow F\rightarrow G\rightarrow 1 $$ where $F^{'}$ and $F$ are free groups.

Q1: Is any profinite group a quotient of two free profinite groups?

Assuming that the answer to the first question is negative

Q2: what can we say about a profinite group if initially we know that it is a quotient of two free profinite groups?

By the second question I do mean if such profinite group has some cohomological properties.

Cellular-Lindelof: a common generalization of the Lindelof property and the CCC

Wed, 11/15/2017 - 03:12

All spaces are assumed to be Hausdorff. Recall that a cellular family in the space $X$ is a family of pairwise disjoint non-empty open subspaces of $X$. The cellularity of $X$ ($c(X)$) is defined as the supremum of the cardinalities of the cellular families in $X$. CCC means that the cellularity is countable.

We say that a topological space $X$ is cellular-Lindelof if for every cellular family $\mathcal{C}$ there is a Lindelof subspace $Y$ of $X$ such that $U \cap Y \neq \emptyset$, for every $U \in \mathcal{C}$.

Clearly every Lindelof space is cellular-Lindelof and every CCC space is cellular-Lindelof.

The cellular-Lindelof property was introduced in our paper with Bella https://link.springer.com/article/10.1007/s00605-017-1112-4, where we note that:

FACT: Cellular-Lindelof first-countable spaces have cardinality at most $2^{\mathfrak{c}}$.

Indeed, let $X$ be a first-countable cellular-Lindelof space. Then $c(X) \leq \mathfrak{c}$ (this follows from Arhangel'skii's Theorem stating that every Lindelof first-countable space has cardinality at most continuum). Combining that with the Hajnal-Juhasz inequality $|X| \leq 2^{\chi(X) \cdot c(X)}$ (where $\chi(X)$ denotes the character of $X$) we obtain that $|X| \leq 2^{\mathfrak{c}}$.

QUESTION: Let $X$ be a first-countable cellular-Lindelof space. Is $|X| \leq \mathfrak{c}$?

A positive answer would lead to a common generalization of Arhangel'skii's Theorem and the Hajnal-Juhasz theorem stating that first-countable CCC spaces have cardinality at most continuum.

Constructive algebraic geometry

Wed, 11/15/2017 - 02:47

I was just watching Andrej Bauer's lecture Five Stages of Accepting Constructive Mathematics, and he mentioned that in the constructive setting we cannot guarantee that every ideal is contained in a maximal ideal---since that obviously requires Zorn's Lemma---so we need to approach algebraic geometry from a different point of view, such as locales.

I am curious how algebraic geometry looks from this constructive point of view, and if there are any good references on this subject?

I'm fairly new to constructive mathematics, though I have been lured in by Kock's synthetic differential geometry, and I'm starting to read the HoTT book.

Hardy-Littlewood and integers of given $ r_0 $ and $ k_0 $

Wed, 11/15/2017 - 02:46

Under Goldbach's conjecture, let's define for a large enough positive composite integer $ n $ the quantities $ r_{0}(n) : =\inf\{r>0,(n-r,n+r)\in\mathbb{P}^{2}\} $ and $ k_{0}(n) : =\pi(n+r_{0}(n))-\pi(n-r_{0}(n)) $ . Does the reasoning of Hardy and Littlewood used to state their famous $k$-tuple conjecture adapt to suggest that if there exist at least two such composite integers with given values of $r_{0}$ and $k_{0}$, then infinitely many exist?

Pages