Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from 2019-06-17T01:18:19Z

Magnitude and distribution of largest prime factor?

Sun, 06/16/2019 - 19:06

Erdos-Kac law state a typical number of magnitude $n$ has $\log\log n$ primes.

What is magnitude and distribution of largest prime factor of typical magnitude $n$ natural number?

Explicit bivariate quadratic polynomials where Coppersmith is better than standard solver?

Sun, 06/16/2019 - 18:29 gives a general method to solve quadratic bivariate diophantine equation while Coppersmith introduced a method to solve bivariate polynomials which work provably and have been shown to break $RSA$ system if half of low significant bits of either $P$ or $Q$ are known.

The equation that comes out is $$(2^ku+v)(2^ku'+v')=PQ$$ where if we assume $v$ is known. Then $vv'\equiv PQ\bmod 2^k$ gives $v'$.

So we have a quadratic diophantine equation $$2^kuu'+(uv'+u'v)=\frac{PQ-vv'}{2^k}.$$

Why do I need Coppersmith's method to solve this? Can't a regular diophantine solver work here and so are there explicit polynomials where Coppersmith is better than standard solver in bivariate quadratic case?

Deligne's Mixed Hodge Theory

Sun, 06/16/2019 - 17:04

Deligne constructs Mixed Hodge Structures (MHS) on the cohomology, $H^{*}(X)$, of an algebraic variety $X$, in his papers Hodge II and Hodge III. Really the question below is rather vague, and is motivated by my desire to separate the construction into two parts, the linear algebraic and the geometric.

Much of the input is subtle linear/ homological algebra, ie deals with the target category of the construction (namely MHS). The geometric content, ie that dealing with the source category, seems to be really about approximating varieties by smooth projective such, and it's this I'd like to focus on.

If $U$ is a smooth variety the construction proceeds via an embedding $U\rightarrow X$ into a smooth projective $X$, so that the complement $D$ is normal crossings. One might imagine that this then determines what the MHS should be, at least if we demand Gysin sequences, however $D$ need not be smooth itself, and so we don't have a construction in this case. The construction for something of the form $D$ is gotten by taking a simplicial resolution of $D$, basically by taking the Cech nerve of the resolution of $D$ given by the disjoint union of its components.

I'd like then to say very roughly that the construction suggests that we should replace the category of varieties, $Var_{\mathbb{C}}$, with something like the category of simplicial objects in "closed inclusions of smooth projective varieties" ie level wise closed inclusions of simplicial smooth projective varieties. I'll call this category $C$ for now. I would love if there was a notion of weak equivalence in $C$, such that there was an inclusion of categories $Var_{\mathbb{C}}\rightarrow C_{loc} $, where the RHS denotes the localized category. I believe objects of $C$ should give rise to chain complexes of MHS and I want the weak equivalences to be taken to quasi-isomorphisms. Nb one must still check that the MHS corresponding to a variety is in the abelian categroy of MHS.

Eigenvalues of cyclic stochastic matrices

Sun, 06/16/2019 - 16:32

Let's consider the following $n \times n$ cyclic stochastic matrix

$$ M= \begin{pmatrix} 0 & a_2 & & & &b_n \\\ b_1 & 0& a_3& &&& \\\ & b_2 & 0& \ddots & & \\\ & &\ddots&\ddots &a_{n-1} & \\\ & && &0 &a_n \\\ a_1 & & & &b_{n-1} &0 \end{pmatrix} $$

such that $\forall i$, $a_i,\,b_i$ are positive real number, $a_i+b_i = 1$ and all other component of the matrix are zeros. This is a cyclic matrix in the sense that the associated graph is cyclic.

From the Perron-Frobenius theorem, the eigenvalues $\lambda$ of such matrix all belong to the unit circle. $$(\Re \lambda )^2 + (\Im \lambda )^2 \leq 1 $$

From numerical explorations, I believe that all eigenvalues of $M$ belong to the ellipse $$(\Re \lambda )^2 + \frac{(\Im \lambda )^2}{(\tanh p)^2} \leq 1 $$

where $p$ denote $p = \frac{1}{2}\ln \frac{\sqrt[n]{\prod_i a_i}}{\sqrt[n]{\prod_i b_i}}$, assumed to be positive, otherwise inverse $a_i$ and $b_i$.

One of the extremal case is the symmetric case $a_i=b_i$ where $p=0$ and all eigenvalues are real. The equality is reached in the uniform case of all $a_i$ to being equal to some value and all $b_i$ being equal to another value, the matrix being then a circulant matrix.

I can already prove that the imaginary part of the eigenvalue is bounded by $\tanh p$ (see below), but I am unable to extend the prove to include the real part. I also try to play with the Brauer theorem about oval of Cassini exposed into [Horn & Johnson, Matrix Analysis], but it did not get me anywhere

Do you have any hints or suggestions to prove the inclusion of the eigenvalue into the ellipse?

Proof for the imaginary part:

Denote $z$ the left eigenvector associated with eigenvalue $\lambda$, we have from the eigenvalue equation $\lambda z = z M $, $$\forall i,\quad \lambda = a_i \frac{z_{i-1}}{z_i} + b_i\frac{z_{i+1}}{z_i} = \frac{a_i}{a_i+b_i} \frac{z_{i-1}}{z_i} + \frac{b_i}{a_i+b_i} \frac{z_{i+1}}{z_i} $$, where $i+1$ and $i-1$ ar evaluated modulo $n$, ad the second equality follow from $a_i+b_i=1$.

By taking the product of the imaginary part of all previous equation and denoting $p_i= \ln \sqrt{\frac{a_i}{bi}}$ , we get $$ \Im \lambda = \sqrt{\prod_i \,a_i b_i \Im \frac{z_{i-1}}{z_i} \Im \frac{z_{i+1}}{z_i} }\prod_i \frac{\sinh (p_i+\frac{1}{2}\ln \Im\frac{ z_{i+1} }{z_{i}} \Im\frac{z_{i} }{z_{i-1}} )}{\cosh p_i} \leq \prod_i \frac{\sinh (p_i+\frac{1}{2}\ln \Im\frac{ z_{i+1} }{z_{i}} \Im\frac{z_{i} }{z_{i-1}} )}{\cosh p_i}$$ The inequality use that $ \prod_i \Im \frac{z_{i-1}}{z_i}\leq 1$. The concavity of $\ln \sinh$ and the convexity of $\ln \cosh$, give the result $$ \Im \lambda \leq \tanh p.$$

About $K$-rectification of increasing Tableaux

Sun, 06/16/2019 - 15:37

Let $T$ be a standard Young Tableaux on $[n]$. Denote the RSK algorithm $\text{RSK}(w)=(P(T),Q(T))$ for $w\in\mathfrak{S}_n$, where $P(T)$ is the Schencted insertion Tableaux.

For $1\leq i\leq j\leq n$. Let $T_{[i,j]}$ be the skew SYT by restricting $T$ to the segament $[i,j]$. For a skew shape $Y$, define the rectification of Y, $\text{Rect}(Y)$ to be applying jeu de taquin on $Y$ to obtain a standard shape. See section 2.1 of this paper, in which $\text{Rect}$ is denoted as $\text{std}$.

It is well known that

For $w\in \mathfrak{S}_n$, $T\in \text{SYT}_n$. If $P(w)=T$, then $$\text{Rect}(T_{[i,j]})=P(w_{[i,j]})$$ for all $[i,j]\subseteq [n]$, where $w_{[i,j]}$ means restricting the permutation to the subalphabet $[i,j]$, e.g. $126534_{[2,5]}=2534$.

My question is: is there a $K$-theoretic analog of this property, in terms of Hecke insertion, $K$-jeu-de-taquin of increasing tableaux?

Specifically. We define $K$-rectification by replacing jdt with $K$-jdt, and denote $K$-$P(w)$ the Hecke-insertion tableau of the word $w$.

Let $T$ be an increasing Tableau (of alphabet $[n]$) and $Y=T_{[1,i]}$ such that $Y$ is an SYT and $1\cdots i\notin T\backslash Y$ (so that there is no ambiguity). Then is it always true that: $$K\text{-Rect}(T\backslash Y)=K\text{-}P(w_{[i+1,n]})$$? where $w$ is the row-reading word of $T$, or even all words such that $K\text{-}P(w)=T$.

For example, Let $T=\begin{matrix}1&2&4\\3&5&6\\4&6&9 \end{matrix},Y=\begin{matrix}1&2\\3&\end{matrix}$. We have $$K\text{-Rect}\left(\begin{matrix}*&*&4\\*&5&6\\4&6&9 \end{matrix} \right)=\begin{matrix}4&5&6\\5&9&\\6&& \end{matrix}$$ The row reading word of $T$ is $w=\mathfrak{row}(T)=469356124$, and $$K\text{-}P(w_{[4,9]})=K\text{-}P(469564)= \begin{matrix}4&5&6\\5&9&\\6&& \end{matrix}$$


An explicit formula for characteristic polynomial of matrix tensor product

Sun, 06/16/2019 - 14:31

Consider two polynomials P and Q and their companion matrices. It seems that char polynomial of tensor product of said matrices would be a polynomial with roots that are all possible pairs product of roots of P,Q.

I guess its coefficients could be expressed through coefficients of P and Q. But I don't know the explicit formula and I cannot find it. I also failed to find it out myself -- I tried different approaches. Maybe it should be that characteristic polynomial, maybe resultant of some form, but..

I hope this is done by someone already.

Does the isometry group of a closed simple smooth curve in the plane constrain its perimeter^2/area ratio?

Sun, 06/16/2019 - 14:04

Let $C$ be a simple closed smooth curve delimitating a bounded domain $D$ in the euclidean plane of isometry group $G$ and of given area $A$. Does the minimal possible ratio $\dfrac{P^{2}}{A}$ where $P$ is the perimeter hence the total length of $C$ decrease when $G$ runs over a sequence $(G_{i})_{i>0}$ of groups such that $i<j$ implies $G_{i}$ is a strict subgroup of $G_{j}$?

Edit: as exposed in comments, even a tiny perturbation of the circle provides a counter example. So suppose further that the ratios of the lengths of any two mutually orthogonal symmetry axes are integers less than a given positive constant $K$. Does the modified question have an affirmative answer?

Identifying a determinantal condition

Sun, 06/16/2019 - 13:02

Has the following condition already been studied and, if so, is there a known class of functions that satisfy it?

Condition. For a fixed $n > 0$, all the $2 \times 2$ minors of the matrix $$ \begin{bmatrix} 1 & x & \dotsm & x^n \\\ 1 & f & \dotsm & f^n \end{bmatrix} $$ are linearly independent over $\Bbb{Z}$, where $f: \Bbb{R} \to \Bbb{R}$ and $f \neq 0,x$.

In other words, I would like to characterise the functions $f$ for which $x^if^j - x^jf^i$, with $0 \leq i < j \leq n$, are linearly independent over $\Bbb{Z}$.

A conjecture concerning symmetric convex sets

Sun, 06/16/2019 - 12:33

Let's suppose that $S \subset \mathbb{R}^n$ is convex and symmetric so:

\begin{equation} x \in S \iff -x \in S \tag{1} \end{equation}

Now, if we define the radius of $S$ as $R$ such that:

\begin{equation} R = \sup_{x \in S} \lVert x \rVert \tag{2} \end{equation}

and use (2) to define:

\begin{equation} V = \{x \in S: \lVert x \rVert = R\} \tag{3} \end{equation}

then I conjecture that:

\begin{equation} S = \text{conv}(V) \tag{*} \end{equation}

I have worked out special cases of this problem within the context of high-dimensional probability but I suspect that it's generally true.

Might there be a theorem which guarantees this result?

Limitations on method of Lagrange multipliers

Sun, 06/16/2019 - 11:14

My general question is this:

What are the conditions (if any) such that the method of Lagrange multipliers will NOT find all the critical points of a differentiable function?

To give some context to this very general question, for

$$f(x, y, z) = 600xy + 900xz + 900yz \text{ subject to } xyz = 486$$

I confirmed a minimum at (9, 9, 6) using a Lagrange multiplier. That method also indicated that was the only critical point. However, Wolfram found an approximation to an additional minimum, which looks valid.

So I am confused. My best guess at an explanation is that although the function is everywhere differentiable, the constraint is not continuous everywhere. But that is a pure guess.

To get the full context behind my question, please look at the following thread at a math homework site where I volunteer:

What is the probability that $X_i$ is the $k^{th}$ order statistic in consecutive trials?

Sun, 06/16/2019 - 10:11

Consider $n$ r.vs ${X_1, X_2,...,X_n}$. Each is i.i.d drawn from some distribution $f(.)$. What is the probability that $X_i$ is the $k^{th}$ order statistic in any two consecutive trials?

Large-n limit of the distribution of the normalized sum of Cauchy random variables

Sun, 06/16/2019 - 08:37

What is the large-n limit of a distribution of the following sample statistic:$$x\equiv\displaystyle\frac{\sum^{n}X_{i}}{\,\sqrt{\,\sum^{n}X_{i}^{2}\,}\,}$$ when sampling the Cauchy(0,1) distribution? Monte Carlo simulation indicates that convergence to this limit is quite fast, and that the resulting (symmetric) PDF has very sharp cusps at -1 and +1, but of course does not yield an analytic expression for this PDF - would anyone be able to find it?
Here is how the positive half of the PDF looks like:

Lambda calculus as set-theoretic operations

Sun, 06/16/2019 - 07:32

It is possible to interpret typed lambda calculus a-la Church as logical operations (because of Curry-Howard correspondence). Also, there is a isomorphism between logical and set-theoretic operations. So, is it possible to direct interpret lambda application as union of sets, and lambda abstraction as subset relation or something like this? Which set-theoretic operations corresponds to lambda application and abstraction?

A small embedding result on Besov space

Sun, 06/16/2019 - 07:21

I have seen the following result $$B_{p,q_1}^{s+\delta}\subset B_{p,q_2}^{s}$$ for $0<p,q_1,q_2\leq\infty$,$\delta>0$. I know how to show that if $q_1\leq q_2$. It just follows from $l_{q_1}\subset l_{q2}$ if $q_1\leq q_2$. But how about the case of $q_1>q_2$? Thanks in advance!

A lower bound on the expected sum of Bernoulli random variables given a constraint on its distribution

Sat, 06/15/2019 - 19:31

Given a set of Bernoulli random variables $x_1, \dots, x_n$ (not necessarily identical) with $X= \sum_{0<i\leq n} x_i$, I am intrested in finding a lower-bound for $\frac{\mathbb{E} [ \min (X,k) ]}{\mathbb{E} [X]}$ in terms of $k$ and $\alpha$ where $\alpha > \Pr[X>k]$. For example, I want to show that this ratio is a large enough constant for $\alpha=0.2$ and $k=4$.

Turning injection of homotopy groups to an isomorphism

Sat, 06/15/2019 - 19:02

Assume we have a connected CW-complex $Y$ and $X\hookrightarrow Y$ a connected sub-complex. We know that the inclusion induces injection on all homotopy groups. Is it true (or under what conditions it can be true) that we can attach cells to $Y$ so that the inclusion induces isomorphism on homotopy groups? (This will subsequently imply that $X$ is a deformation retract of the enlarged $Y$.)

You can further more assume that the inclusion of $X$ is a map of infinite loop spaces. If that helps. Edit: The inclusion is also injective on the homologies.

Integration of Euler class of blow up of a complex surface at a point

Sat, 06/15/2019 - 18:18

let X be a product of two Riemann surface of genus $\geq1$ and p be a point of X. If X' is the blow up of X at p. Let E denote the exceptional divisor I am aware that the the second Chern number of X' since it's the euler characteristic. I would to verify this by integration of the second chern class. Up to now I try as follows:

Let W be a tubular neighborhood of the exceptional divisor E. Let N be the normal bundle of E $c_2(X') = p^*(c_2(X))+c_2(TN)=p^*(c_2(X))+ c_1(TE)c_1(N)$ Now I am not sure how to proceed. $\int_{X'}p^*(c_2(X))+ c_1(TE)c_1(N)$ This reduces to $\int_{X'}c_1(TE)c_1(N)$ which I tend to understand as the intersection number. But usually one performs this computation in $\mathbb{C}P^n$, which is not the case here. Could anybody give me some help? Thanks.

A generalization of bicharacters

Sat, 06/15/2019 - 18:11

Let $G,\, H$ be groups and let $F$ be a field. A bicharacter $A: G \times H \to F^\times $ is a map that satisfies $$ A(xy, z) = A(x,z)A(y,z),\quad A(x,zw)=A(x,z)A(z,w),\quad x,y\in G,\, z,w\in H. $$ I came across a map $B: G \times H \to F^\times$ that satisfies a weaker condition: $$ (*) \quad \quad B(xy, zw) B(x,z)B(x,w)B(y,z)B(y,w) =\\ B(xy, z) B (xy,w) B(x, zw) B(y, zw) $$ as well as $B(x, 1)= B(1,z)=1$.

A bicharacter satisfies (*) but not vice versa (e.g., for $G=H= \mathbb{Z}_2=\{1,x\}$ one can have $B$ with $B(x,x)$ $=$ a $4$th root of $1$).

Do maps satisfying (*) occur somewhere? Is there a name for such maps? Is there a good description of the quotient of the group of such maps by the group of bicharacters?

Hashed coupon collector

Sat, 06/15/2019 - 14:14

The story:

A sport card store manager has $r$ customers, that together wish to assemble a $n$-cards collection. Every day, a random customer arrives and buys his favorite card (that is, each customer is associated with a single card), even if it has purchased the same card before. How many days will past before the customers complete their collection?

Formally, let $n\le r$ be integer parameters, and let $h:[r]\to [n]$ be a random projection from $[r]$ to $[n]$ (i.e., it maps every element uniformly and independently). How many random samples (with replacement) $(x,h(x))$ to we need to get before we see all $n$ values possible for $h$?

Clearly, there is some chance that $h$ is not onto and thus the expectation of the required number is not bounded.

I'm interested in a bound of the form:

  • After $T(r,n,\delta)$ samples, with probability at least $1-\delta$, we have seen all possible $n$ values.

For example, if $r=3,n=2$, we have a probability of $1/4$ that $h$ is not onto, and if it is, then after collecting $4$ cards, the chance of not seeing both values is $(1/3)^4+(2/3)^4\le 0.21$. This means that $T(3,2,0.46)=4$ is a correct upper bound.

Reference request: complex K-theory as a commutative ring spectrum

Sat, 06/15/2019 - 13:53

Does anyone know of a point-set level model for complex K-theory as a commutative ring spectrum?

For real $K$-theory I know of "A symmetric ring spectrum representing KO-theory" by Michael Joachim (Topology, 40(2) 2001).