Recent MathOverflow Questions

Packing number of $\ell_1$ ball in $\ell_{\infty}$ metric

Math Overflow Recent Questions - Mon, 10/02/2017 - 12:01

Consider the $d$-dimensional $\ell_1$ ball $\mathbb B_d=\{x\in\mathbb R^d: \|x\|_1\leq 1\}$, where $\|x\|_1=\sum_{i=1}^d{|x_i|}$. I'm interested in the maximum size of the (finite) subset $S\subseteq\mathbb B_d$ such that for any two distinct elements $x,y\in S$, $\|x-y\|_{\infty}\geq \delta$, where $\|z\|_{\infty}=\max_{1\leq i\leq d}|z_i|$. $\delta$ is, of course, strictly between 0 and 1.

My main point of reference is Lemma 5.2 of the following note: https://www.stat.berkeley.edu/~wainwrig/nachdiplom/Chap5_Sep10_2015.pdf

If I understand it correctly, the (lower bound) side of Lemma 5.2 implies that

  1. If $\delta\lesssim 1/d$, then $\log |S|\asymp d\log(1/\delta)$ as $d\to\infty$, and this bound is almost tight;
  2. However, if $d\delta\to\infty$ it seems to me that the lower bound of $\log |S|$ becomes $\Omega(1)$ as $d\to\infty$, which clearly sounds loose to me.

My question is hence the following: What is the asymptotic scaling of $\log |S|$ as $d\to\infty$ in the regime of $\delta\to 0$ and $d\delta\to\infty$? More concretely, if $\delta\asymp d^{-\alpha}$ for some $\alpha\in(0,1)$, how should $\log |S|$ scale with $d$ as $d\to\infty$? And furthermore, what if we consider the general $\ell_p$ ball $\{x\in\mathbb R^d: \|x\|_p\leq 1\}$ for $1\leq p<\infty$?

Average measure of intersection of a convex region with its translate

Math Overflow Recent Questions - Mon, 10/02/2017 - 07:04

Let $\lambda$ denote the Lebesgue-measure on $\mathbb{R}^n$, and let $C\subset\mathbb{R}^n$ be a convex region.

My question is about $$f(C):=\int_{C} \lambda(C \cap (x + C) ) \mathrm{d} x.$$ How large can $f(C)$ be? Of course, there is the trivial bound $f(C)\leq \lambda(C)^2$ but I would expect more something like $f(C) = O( \lambda(C) )$ at least. This question has probably been answered somewhere, and I suspect that the following might be very well known: for regions $C$ of constant measure, the value of $f(C)$ is maximal if $C$ is an $n$-ball (or something similar). I couldn't find any useful references regarding this question. If someone could help me out with some reference, or even a simple solution, I would be very grateful.

Vertex reachability in general random graph

Math Overflow Recent Questions - Mon, 10/02/2017 - 02:27

Given $n$ vertices, we build a tournament as follows. For each pair of vertices $x,y$, draw an edge from $x$ to $y$ with some probability within the range $[c\log n/n,1-c\log n/n]$ for some constant $c$; otherwise, draw an edge from $y$ to $x$. (This probability can differ between different pairs $x,y$.) Let $p_n$ be the probability that the resulting tournament is strongly connected. Does there exist a constant $c$ such that $p_n\rightarrow 1$ as $n\rightarrow\infty$?

If we always pick the probability to be $1/2$, then we do have $p_n\rightarrow 1$. On the other hand, if the probability is allowed to be asymptotically below $1/n$, the statement cannot be true because a vertex can have no outgoing edge with high probability.

Is the Lyness 5-cycle map birationally conjugate to its own square?

Math Overflow Recent Questions - Sun, 10/01/2017 - 22:41

Let $L(x,y) = (y,(y+1)/x)$. On a dense open subset of the plane, $L$ and all its powers are well-defined invertible maps and $L^5$ is the identity ($L$ is sometimes called the Lyness 5-cycle map). $L$ is birationally conjugate to its own inverse via the map that exchanges $x$ and $y$. Is $L$ furthermore birationally conjugate to $L^2$? That is, is there some birational map $f$ satisfying $f^{-1} \circ L \circ f = L^2$?

My past MO post Conjugating the Lyness 5-cycle into a rotation of the plane is relevant, and Brunault's reply would give me affirmative answer to my question if I knew that the rotation map of the projective plane associated with $L$ is birationally conjugate to its own square. (I briefly thought Galois theory would bridge this gap, but it smells too much like the problem of extending automorphisms of finite extensions of ${\bf Q}$ to automorphisms of ${\bf C}/{\bf Q}$.)

In their article "On Cremona transformations of prime order" (https://arxiv.org/pdf/math/0402037.pdf), Beauville and Blanc (summarizing the state of knowledge prior to their work) write "The linear transformations of a given order are contained in a unique conjugacy class." And apart from these, among other conjugacy classes: " ... As for conjugacy classes of order 5, there is at least one family, given by automorphisms of a special Del Pezzo surface of degree 1." Then they state their main result (Theorem 1): In the group of birational automorphisms of the projective plane, every conjugacy class of order 5 is either "of the above type" or is the class containing the linear automorphisms.

It is not clear to me whether this is asserting that there are exactly two conjugacy classes of order-5 automorphisms (one containing all the Del Pezzo automorphisms of order 5 and one containing all the linear automorphisms of order 5).

What subsets of a set of integers can compute it?

Math Overflow Recent Questions - Sun, 10/01/2017 - 12:00

For $x, y \subseteq \omega$,

(a) We write $x \leq_T y$ if $x$ is Turing reducible to $y$.

(b) We write $x \leq_L y$ if $x \in L(y)$ where $L(y)$ is the smallest model of ZFC that contains all ordinals and $y$. Let $L = L(\emptyset)$.

Note that $x \leq_T y \implies x \in L(y)$.

I have two questions.

(1) Is there an infinite $x \subseteq \omega$ such that for every $y \subseteq x$, if $x \leq_T y$ then $x \setminus y$ is finite?

If the answer to (1) is yes, then

(2) Assume $\mathbb{R} \cap L \neq \mathbb{R}$. Does there exist an infinite $x \subseteq \omega$ such that for every $y \subseteq x$, if $x \leq_L y$ then $x \setminus y$ is finite?

Under what conditions does an Integer Programming problem run in polynomial time?

Math Overflow Recent Questions - Sun, 10/01/2017 - 09:38

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in polynomial time ($(mn)^c$ arithmetic operations on $(mn)^c$ sized words suffices).

Supposing we have the promise that the number of feasible solutions is polynomial then under what conditions can the problem be solved in polynomial time using Kannan's and Barnivok's algorithm (other than total unimodularity)?

  1. It may be possible that naturally defining IP with poly # solutions is in P unless somehow defined by Unique-SAT.

  2. Is it possible that if perfect basis reduction for given problem is in P then Kannan's algorithm is in P?

  3. Is there necessary and sufficient conditions on categories of inputs on which the algorithms run in poly time?

    It is unlikely that Kannan's algorithm or Barnivok's algorithm runs uniformly in $n^{O(n)}$ time for all inputs.

There is no evidence whatsoever that Kannan's or Barnivok's algorithm ever runs in poly time for any non-trivial class of inputs which is why the query. It seems unbelievable that there cannot be input families for which these terminate in poly time.

By non-trivial class of inputs I mean an exponential set of inputs.

https://cstheory.stackexchange.com/questions/37777/under-what-conditions-does-an-integer-programming-problem-run-in-polynomial-time

Proofs of some combinatorial identities

Math Overflow Recent Questions - Sun, 10/01/2017 - 00:01

Just wondering if anyone knows any references in the literature to bijections corresponding to the following simple generating function identities. Let $B(z)=\frac{1}{\sqrt{1-4z}}$ and $C(z)=\frac{1-\sqrt{1-4z}}{2z}$, the generating functions of the central binomial coefficients and Catalan numbers, respectively. I'm looking for bijections corresponding to the following identities: $$B(z)B(-z)=B(4z^2),$$ $$\frac{C(z)+C(-z)}{2}=B(z)(1-2zC(4z^2))=B(-z)(1+2zC(4z^2))$$ and, taking the product of the last two expressions in the second identity and using the first identity and the fact that $1-zC^2=C/B$, $$\left(\frac{C(z)+C(-z)}{2}\right)^2=C(4z^2).$$ Thanks.

Convergent net in a quasi-uniform space which is not Cauchy

Math Overflow Recent Questions - Sat, 09/30/2017 - 23:18

The proof of the result that every convergent net in a uniform space is Cauchy, employs symmetry of the uniform space. A quasi-uniform space lacks that symmetry. Is it possible then to find a convergent net in a quasi-uniform space which is not Cauchy?

Coproducts of weak equivalences

Math Overflow Recent Questions - Sat, 09/30/2017 - 21:19

In a model category $\mathcal{C}$ admitting a forgetful functor to simplicial sets, is the coproduct of weak equivalences a weak equivalence? Say even just coproducts indexed by $\mathbf{N}$. A reference?

For example, the model category of simplicial bi-modules over a commutative rings with fibrations and weak equivalences defined to be those that are fibrations/weak equivalences of underlying simplicial sets, satisfies this, because homology of chain complexes commutes with coproducts.

However, just as an example, what about simplicial commutative monoids with analogous model structure, for instance?

Extension of Cauchy Integral

Math Overflow Recent Questions - Sat, 09/30/2017 - 20:15

Let $f$ be holomorphic in the closure of an unbounded Jordan domain. Suppose that $f$ has a limit $f_{\infty}$ as $\left| z \right| \to \infty$. In other words, $$\forall \epsilon > 0 \exists R >0 : \left| z \right| > R \implies \left| f(z) - f_{\infty} \right| < \epsilon.$$ My supervisor made the claim that $f$ can be written as $$f(z) = \frac{1}{2\pi i} \int_{\partial D} \frac{f(\zeta)}{\zeta - z}d\zeta + f_{\infty}.$$

There seems to be no reference online about holomorphic functions and their representations on unbounded domains. Can anyone lend a hand? Cheers.

The Prime impossibility [on hold]

Math Overflow Recent Questions - Sat, 09/30/2017 - 20:09

Im working on a formula to generate prime numbers (i KNOW ITS supossed to be IMPOSSIBLE) and I need to figure out what symbols to use for the following terms:

A natural number that is NOT prime, an specific set of numbers.

Thank you for your help.

I know its not really possible but there's no harm in trying.

Evaluate complex integral [migrated]

Math Overflow Recent Questions - Sat, 09/30/2017 - 19:33

I want to evaluate the integral $$\int_{\left| z \right| =2} \frac{1}{z^{741} +1}dz.$$ It is clear that all singularities of this function are contained in the region of integration. Therefore, the residue theorem would give us that $$\int_{\left| z \right| =2} \frac{1}{z^{741} +1}dz = 2\pi i \sum_{k=1}^{741} \text{Res}_{z_k}.$$ I can't calculate the residues however, can someone assist me?

Pointwise bound on the gradient of solution of poisson equation

Math Overflow Recent Questions - Sat, 09/30/2017 - 19:25

I posted this question on SE .I got stack on this problem for a long time. I hope that someone can help me. This is the problem :

Consider the poisson problem with Dirichlet data :

$-\Delta (u) = f\quad\quad u = u_{d}\quad on\quad\partial \Omega $

Let $u_{h}$ be the finite element solution to this problem relative to a fixed riangulation of a plygonal domain $\Omega\subset R^{2}$

Can i exploit the gradient of $u_{h}$ solution to get informations about the exact solution, more exacly can i have an estimate of the form :

$|\nabla(u-h_{h})(x)|\leq c$

(c must be an explicit computable constant) the following is one try : i write

$-\Delta (u-u_{h}) = f\quad B_{1}\quad\quad u-u_{h} = u_{d}-u_{d,h}\quad on\quad\partial B_{1}$

Note that $f\in H^{-1}$ since $u_{h}$ is only $H^{1}$ and then i used a green representation formula on the unit ball B

Any idea is welcomed

Vladimir Voevodsky's works

Math Overflow Recent Questions - Sat, 09/30/2017 - 19:19

Vladimir Voevodsky has made several contributions in abstract algebraic geometry, focused on the homotopy theory of schemes, algebraic K-theory, and interrelations between algebraic geometry, and algebraic topology. .

Voevodsky was awarded the Fields Medal in 2002. Sadly, he died September 30, 2017.

Can one draw a general picture of him works?

(Any expository reference will be appreciated).

Are there universities who take your mathoverflow score seriously [on hold]

Math Overflow Recent Questions - Sat, 09/30/2017 - 19:19

When being considered for a position at a university as a post doc or phd or professor, does your math overflow account mean anything. Are there any universities that take this seriously when looking at your application?

Internal category in an endofunctor category (possible examples)

Math Overflow Recent Questions - Sat, 09/30/2017 - 18:54

A while ago, I asked this question about internal categories in an endofunctor category. The comment that was posted stated that it was not possible because the particular functors don't preserve equalizers. I am not sure if he meant any functors, or specifically frobenius monads. I am currently interested in bimonads (monad/comonad with a mixed distributive law), and especially those bimonads on SET. I am wondering if we can find a bimonad that preserves equalizers and thus becomes an internal category for the reasons I have suggested (See the link).

$2$ dimensional foliations of space whose leaves contain the trajectories of a given vector field

Math Overflow Recent Questions - Sat, 09/30/2017 - 17:12

Assume that $X$ is a non-vanishing vector field on $\mathbb{R}^3$.

Is there a $2$-dimensional foliation of space such that every trajectory of $X$ is contained in a leaf of the $2$-dimensional foliation?

As a related question:

Is there a classification of all $1$-dimensional foliations of space tangent to the unit speed vector field $t$ for which the distributions $\{t,n\}$ and $\{t,b\}$ are integrable? Here $\{t,n,b\}$ is the associated Frenet frame.

Is there a name for this set of vectors?

Math Overflow Recent Questions - Sat, 09/30/2017 - 14:10

Given full rank system of vectors $v_1,\dots,v_n\in\Bbb Z^n$, vector $w\in\Bbb Z^n$ and integers $a,b\in\Bbb Z^n$ such that $$\langle v_i,w\rangle=a$$ at every $1\leq i\leq n$ is there a name for the set of vectors $v\in\Bbb Z^n$ such that $$\langle v',w\rangle=b$$ where $v'=(\langle v_1,v\rangle,\langle v_2,v\rangle,\dots,\langle v_n,v\rangle)\in\Bbb Z^n$?

The category of elements corresponding to a coend as a higher colimit

Math Overflow Recent Questions - Sat, 09/30/2017 - 13:56

Let $D: \mathcal{C} \to \mathbf{Set}$ be a diagram of sets, then we can obtain the colimit of $D$ as the set of connected components of the category of elements of $F$, which we denote by $\mathrm{el}(F)$. The category $\mathrm{el}(F)$ in turn is the oplax colimit of the composition of $F$ and the inclusion $\mathbf{Set} \hookrightarrow \mathbf{Cat}$.
Now let us consider a functor $F: \mathcal{C}^{\mathrm{op}} \times \mathcal{C} \to \mathbf{Set}$, then the coend of $F$ can again be constructed as the set of connected components of a category $\mathrm{el}^\wedge(F)$ which we now describe:

  • The objects are pairs $(X,x)$ with $X \in \mathcal{C}$ and $x \in F(X,X)$.
  • A morphism $(X,x) \to (Y,y)$ is given by a pair $(f,a)$, where $f: X \to Y$ is morphism in $\mathcal{C}$, and $a \in F(X,Y)$ such that $f_*(x) = f^*(y) = a$.
  • Finally composition of two morphisms $(X,x) \xrightarrow{(f,a)} (Y,y) \xrightarrow{(g,b)} (Z,z)$ is given by $(g \circ f, g_*(a)) = (g \circ f, f^*(b))$.

Does the category $\mathrm{el}^\wedge F$ satisfy a similar universal property as $\mathrm{el}F$?

The above description of the colimit of $D$ feels very natural to me, and I was hoping that this perspective may shed some light on the nature of coends*.

Finally I would like to note that it may be that there are other categories $\mathcal{E}$ than $\mathrm{el}^\wedge F$ such that $\pi_0(\mathcal{E})$ corresponds to the coend of $F$, which are more natural than my construction. If this is the case, I would be grateful for these to be pointed out.

*It is like first taking the quotient of a set by a discrete group in the $(\infty,1)$-category of spaces (or in this case equivalently in the $(2,1)$-category of groupoids) and then applying the left adjoint to $\mathbf{Set} \hookrightarrow \mathbf{Spaces}$ (resp. $\mathbf{Set} \hookrightarrow \mathbf{Groupoids}$).

The supplement of an angle is 40 more than the supplement of the complement of the angle. Find the measure of the angle [on hold]

Math Overflow Recent Questions - Sat, 09/30/2017 - 13:25

Angle = x Comp = 90-x Supp = 180-x

I tried 180-x = 40+180-x(90-x), but did not get the right answer. How would you solve this equation?

Pages

Subscribe to curious little things aggregator