User marcin kotowski - MathOverflow

Expected rank - computable approximations

2013-03-23T21:36:24Z

I'm interested in finding the expected rank of some random matrix $A$ (I don't want to specify its distribution right now, since my question makes sense in general).

Computing $\mathbb{E} \ \mathrm{rk}(A)$ is usually infeasible, as rank is a rather awful function to consider or optimize etc. Are there quantities which could serve as proxies for the rank, but whose averages would be easier to compute in this setting? In other words, I'm looking for functions $f(A)$ such that $\mathbb{E}f(A)$ can be computed and $f(A)$ is a reasonable approximation to $\mathrm{rk}(A)$. An example would be $\mathrm{tr}(A)$, which would be close to the rank if the eigenvalues of $A$ are close to $1$.

Since replacing rank with some nicer (e.g. convex) function seems to be a common approach e.g. in optimization, I'd be also interested in references.

Largest number of k-arithmetic progressions without a (k+1)-arithmetic progression

2013-03-04T03:17:11Z

Suppose $A \subseteq \{1,\dots,n\}$ does not contain any arithmetic progressions of length $k+1$. What is the largest number of $k$-term arithmetic progressions that $A$ can have? (one may also wish to put some lower or upper on the size of $A$) We can work over $\mathbb{Z}_p$ if it makes the answer any easier. The "degenerate" case $k=2$ asks for the largest size of the set without arithmetic progressions and it is known that there exist $A$'s with this property of almost linear size.

Bounds on difference sets of relatively dense A \subseteq {1, ..., n}

2013-02-07T03:38:45Z

Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta < 1$? If not, can something like this hold for a "generic" $A$ (say, with high probability if $A$ is chosen at random)? What about $2A-A$ or similar sets? (as you can guess, interest in $2A-A$ comes from arithmetic progressions)

Of course only the case $|A| = \Omega(\sqrt{n})$ is nontrivial, and perhaps we have to assume also an upper bound on $|A|$ (e.g. $|A| \leq n^{\gamma}$ for some $\gamma <1$), since of course we could have $A = \{1, \dots, n\}$.

Spectral properties of Cayley graphs

2010-03-14T22:01:42Z

Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good invariant, but maybe something interesting can still be said here?

In the case of an infinite group, can Cayley graph be replaced by some suitable infinite-dimensional object (say, linear operator, a generalization of the graph's adjacency matrix) so that the object's spectral properties may carry some algebraic data about the group?

Ising model - phase transition vs rapid mixing

2012-10-29T18:06:59Z

Consider a graph $G=(V,E)$ and Ising model on that graph, i.e. configuration space is $\Omega=${$-1,+1$}$^V$ and energy of a configuration $s \in \Omega$ is given by: $H(s) = -\beta \sum_{u \sim v}s(u)s(v)$

Consider:

a) the phase transition between the ordered and disordered phase

b) transition in a Markov chain simulating the dynamics (e.g. Glauber/Metropolis dynamics), from rapid mixing ($N\log N$) to exponentially slow mixing

It is generally "known" that often phase transition as in a) is accompanied by phase transition in b) ("critical slowdown" in physics parlance). Is there any formal result capturing this knowledge (e.g. theorem of the form: physical phase transitions is equivalent to critical slowing down of the appropriate Markov chain)? Or, at least, a nonrigorous argument going beyond "this seems to hold for all systems that physicists are interested in" (proving tight results about critical points is usually difficult, so a heuristic would be OK).

Answer by Marcin Kotowski for Another question about amenability and Følner sequences

2012-09-27T15:59:27Z

Yes - see Lemma 5.1 of Gabor Pete's book on probability and groups: http://www.math.bme.hu/~gabor/PGG.html (by the way, these are excellent lecture notes)

Expected values of traces of products of random matrices

2012-05-15T14:29:23Z

Suppose I want to compute a quantity of the type:

$\mathbb{E}\mathrm{tr}(AUBU^{\ast})$

where averaging is over Haar measure on the unitary group $\mathcal{U}(n)$ (one can of course consider higher order polynomials or other matrix ensembles etc.) and $A$, $B$ are some fixed matrices. Is there any standard technique for computing such averages? I'd guess people in random matrix theory or free probability compute such traces all the time, but I've been unable to find a reference. If it makes matters easier, I'm really interested in computing something for random projections (e.g. something of the form $\mathbb{E}\mathrm{tr}(APBP)$, where $P$ is a projection onto a random subspace), which of course reduces to computation of polynomials in $U$.

Answer by Marcin Kotowski for Expected values of traces of products of random matrices

2012-05-31T23:21:23Z

Answering my own question, there is a closed formula for such traces, given in: http://arxiv.org/abs/math-ph/0402073 (the formula involves representation theory of $S_n$ and gets ugly as $n$ gets bigger, but can be written down explicitly at least for small $n$)

Diophantine elements in SU(2)

2012-02-29T02:39:11Z

Following notions from [1], call a set of elements $g_1, \dots, g_k \in G = SU(2)$ Diophantine if it satisfies the following property: there exists a constant $D$ such that for every word $W_m$ of length $m$ in $g_1, \dots, g_k$, if $W_m \neq \pm e$ (identity element), then $\Vert W_m \pm e\Vert \geq D^{-m}$. It can be proved that elements with algebraic entries are Diophantine.

Bourgain and Gambrud prove that a certain property (spectral gap) holds for $g_1, \dots g_k$ that: a) generate a free subgroup of $SU(2)$, b) are Diophantine. The first property is generic in measure. The second is not known to be generic in measure, but sets of Diophantine elements are dense in $G^k$ (since all rational-entry elements are). Does it follow that set of elements that a) generate free subgroup, b) are Diophantine, is dense in $G^{k}$?

Maybe it's almost obvious, since the set of elements generating a free subgroup is a complement of a countable union of proper subvarieties, but somehow one must rule out the possibility that being Diophantine and freeness are "anticorrelated" (a priori, we only know that elements with algebraic elements are Diophantine, and this is a countable set). Or maybe in fact Diophantine elements form a much larger set?

[1] Jean Bourgain, Alex Gamburd, "On the spectral gap for finitely-generated subgroups of SU(2)"

Mixing time of unitary Brownian motion

2012-02-15T18:43:06Z

Let $B_t$ be the unitary Brownian motion, i.e. Brownian motion on the unitary group $U(N)$. What is known about the mixing time of $B_t$, that is, how fast does the measure $B_t(\delta_{{Id}})$ converge to the Haar measure? (the question is motivated by trying to say something about mixing times for some discrete approximations of unitary Brownian motion)

Answer by Marcin Kotowski for Short Course Suggestions For High School Students

2011-12-22T23:31:26Z

I have successfully taught a course for gifted high school students (somewhat shorter than yours, about 9 hours) devoted to the probabilistic method (based, naturally, on Alon and Spencer + some other material). I managed to cover the basics, second moment method, some random graphs, games and derandomization. With a little more time I would have squeezed in the Lovasz Local Lemma.

There was a lot of problem solving, but I was also able to show them some more advanced techniques. In general, combinatorics seems to be a good context to introduce some nontrivial probabilistic tools (say, Chernoff-type bounds).

Another probability-based course in the similar format was "random walks and electrical networks". Very nice topic, quite elementary^1, lots of physical intuition - and at the same time, points at the more advanced math beneath (Markov chains, spectral graph theory)

1 - until the kids ask you "wait, how is this probability on the set of infinite trajectories defined? ;) Luckily, I managed to avoid invoking the Kolmogorov extension theorem.

Quantitative versions of ergodic theorem

2009-11-06T18:36:47Z

Are there any general theorems similar to Birkhoff's ergodic theorem, but giving quantitative estimates on the rate of convergence or average time of recurrence (perhaps with additional assumptions)? Take the example of an "irrational rotation" on the unit circle - are there any estimates on the average time it takes for a point to hit a certain interval?

I know there are such theorems for very special systems (e.g. for Markov chains we have exponential convergence) - what can be said about a "generic" ergodic system?

Answer by Marcin Kotowski for How to make a lecture series useful

2011-11-20T04:43:59Z

If possible, it might be a good idea to organize a problem session, with problems/exercises given to participants in advance (say, a day before) and the session devoted to presenting the solution. The problems needn't be difficult, but have to solve actual exercises forces you to understand the definitions and concepts in enough detail to be able to use them, not only on vague "big picture" level. I've attended schools/workshops where this idea was implemented and the feedback was overwhelmingly positive.

Simultaneous diophantine approximation with polynomial bound

2011-10-15T23:04:19Z

For a given number $\alpha$ continued fractions expansion $(p_n, q_n)$ of $\alpha$ has the remarkable property that not only $|\alpha - \frac{p_n}{q_n}| < \frac{1}{q_n^2}$, but the converse holds - if $|\alpha - \frac{p}{q}| < \frac{1}{2q^2}$, then $\frac{p}{q}$ will appear in the expansion of $\alpha$.

Is there any analogue of this fact in simultaneous Diophantine approximation with polynomial bound? More precisely, I want to think of this procedure as allowing me to recover unknown ${ \frac{p_i}{q}}$ with $q$ being exponential in $n$, from known $\alpha_i = \frac{s_i}{r}$ with $r$ only polynomial in $n$ and $|\alpha_i - \frac{p_i}{q}| < \frac{1}{poly(n)}$. Is such a procedure even possible, maybe given some additional constraints? (note that doing 1-dimensional continued fractions component-by-component will not do, as it requires resources exponential in $n$ for each component)

(motivation for the problem comes from considering an unknown $n$-dimensional rational lattice and trying to recover their vectors using some polynomial sampling procedure; I want to think of $q$ as the determinant of this lattice, which is reasonably to assume to be exponential in $n$)

Pointwise bounds for Dirichlet kernel over truncated lattice

2011-09-28T02:28:38Z

In 1 dimension, a "one-sided" Dirichlet kernel $D_N(x)=\sum_{k=0}^{k=N}e^{\frac{2\pi}{N}ikx}$ has its module sharply peaked around points corresponding, roughly, to the "dual lattice" $N\cdot\mathbb{Z}$ (which area really integer points in this case).

Now consider a lattice $\Lambda \subseteq \mathbb{Z}^2$. Let $\Lambda_N = \Lambda \cap [0,N]^2$ and a Dirichlet kernel restricted to this truncated lattice: $D_{\Lambda_N}(x)=\sum_{v \in \Lambda_N}e^{i\langle x,v\rangle}$.

We would expect that $|D_{\Lambda_N}|$ will be peaked around points from $N\cdot\Lambda^{\ast}$, where $\Lambda^{\ast}$ is the dual lattice. However, there is no direct way to perform the summation and obtain a compact formula as in 1D case. Is there any way to estimate $|D_{\Lambda_N}(w)|$ from below, for $w \approx N\cdot\Lambda^{\ast}$?

Second eigenvalue of suspension of a graph

2011-09-11T22:08:19Z

Suppose I have some $d$-regular graph $G$. Let $\lambda = \max{\lambda_2(G), |\lambda_n(G)|}$ be the second largest eigenvalue of the adjacency matrix of $G$. Now take $\tilde{G}$, the suspension of $G$, obtained by adding a new vertex $v$ and connecting $v$ to all vertices of $G$. Is it true that $\lambda(\tilde{G}) \leq \lambda(G)$? (or more generally, is it true if instead of suspending with one vertex we suspend with a clique of size $n$)

The intuition is that $\tilde{G}$ should exhibit better mixing (hence, smaller $\lambda$), since it's easier for a random walk to get from one vertex to any other.

Quantum analogue of Wiener process

2010-02-21T14:54:53Z

The Wiener process (say, on $\mathbb{R}$) can be thought of as a scaling limit of a classical, discrete random walk. On the other hand, one can define and study quantum random walks, when the underlying stochastic process is governed by a unitary transform + measurement (for an excellent introduction, see http://arxiv.org/abs/quant-ph/0303081).

My question is - do quantum random walks have a reasonable continuous limit, something which would give a quantum analogue of the Wiener process?

Ising model on groups

2011-01-16T18:01:42Z

Can anything interesting be deduced about the properties of a group from the behavior of the Ising model on its Cayley graph? (i.e. existence and character of phase transitions, critical behavior) I'm not sure, though, if one should expect any general results (link between large-scale geometry and universality class, maybe?), since even very simple geometry of the group (say, $\mathbb{Z^2}$) can give highly nontrivial statistical properties.

Friedman and proof of Hanna Neumann Conjecture

2011-06-03T14:48:13Z

Two years ago, Joel Friedman submitted a paper purporting to prove the Hanna Neumann Conjecture, which eventually turned out to contain a fatal bug and was withdrawn. Quite recently, Friedman repeated his attempt at proof with paper "Sheaves on Graphs and a Proof of the Hanna Neumann Conjecture": http://arxiv.org/abs/1105.0129 . Has this attempt been verified by anyone or is still under review?

What are the applications of immanants?

2011-05-28T14:53:39Z

Definitions of determinant:

$det(A) = \sum_{\sigma \in S_n}(-1)^{\operatorname{sgn} \sigma}\prod_{i}a_{i, \sigma(i)}$

and permanent:

$perm(A) = \sum_{\sigma \in S_n}\prod_{i}a_{i, \sigma(i)}$

admit a generalization in the form of immanant:

$Imm_{\lambda}(A) = \sum_{\sigma \in S_n}\chi_{\lambda}(\sigma)\prod_{i}a_{i, \sigma(i)}$

where $\lambda$ labels irreducible representations of $S_n$ and $\chi_{\lambda}$ is the character. Determinant and permanent are easily seen to be special cases of $Imm_{\lambda}$.

While determinants are ubiquitous in mathematics and permanents also have many application, esp. in combinatorial problems, other kinds of immanants seem to be rarely used. Are there any problems where use of $Imm_{\lambda}$ other than $det$ and $perm$ is natural?

Proving that a combinatorial sequence has no compact formula

2011-05-24T19:59:33Z

Suppose we have a sequence $a_n$ given by some combinatorial formula, e.g. involving a sum of n terms (like ${n \choose k}^{10}3^{-k}$ etc.). Sometimes it is plausible that there is no compact formula for the $a_n$, where one has to adopt a reasonable definition of "compact" (i.e. using a constant, independent of $n$, number of primitive operations). Are there any methods of proving that a certain sequence $a_n$ has no compact formula, in much the same way differential Galois theory allows one to prove that certain integrals are nonelementary? Of course this would relative the choice of "computational primitives" (factorial, ${n \choose k}$ etc.)

Bell polytopes with nontrivial symmetries

2011-04-10T18:19:40Z

Take $N$ parties, each of which receives an input $s_i \in {1, \dots, m_i}$ and produces an output $r_i \in {1, \dots, r_i}$, possibly in a nondeterministic manner. We are interested in joint conditional probabilities of the form $p(r_1r_2\dots r_N|s_1s_2\dots s_N)$. Bell polytope is the polytope spanned by the probability distributions of the form $p(r_1r_2\dots r_N|s_1s_2\dots s_N) = \delta_{r_1, r_{1, s_1}}\dots\delta_{r_N, r_{N, s_N}}$ for all possible choices of numbers $r_{i,s_i}$ (in other words, each input $s_i$ produces a result $r_{i,s_i}$ either with probability 0 or 1, regardless of other players' inputs). Polytopes of this kind are of interest in quantum information theory.

Every Bell polytope has a certain amount of trivial symmetries, like permutation of parties or relabelling of inputs or outputs. Is it possible to give an explicit Bell polytope with nontrivial symmetries? (e.g. transformations of the polytope into itself that takes faces to faces and is not trivial in the above sense)

Bell polytopes in literature are usually characterized by their faces, given by sets of inequalities (Bell inequalities), which, however, usually do not have any manifest symmetry group.

Answer by Marcin Kotowski for Are there any good websites for hosting discussions of mathematical papers?

2011-01-04T11:08:42Z

You can try SciRate (http://scirate.com/), a site that allows you to rate and comment papers from Arxiv (it updates the list of papers automatically). It doesn't seem to be very popular, though (lack of critical mass?).

Answer by Marcin Kotowski for Most memorable titles

2010-12-28T20:41:53Z

"I know I should have taken that left turn at Albuquerque" by Gady Kozma and Ariel Yadin (http://arxiv.org/abs/1008.4258)

Rainbow matchings (in random graphs)

2010-12-11T16:23:35Z

Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) for a random bipartite graph (e.g. that for $k$ colors and more than $f(k,n)$ edges we get a rainbow matching with $p \rightarrow 1$)?

In the noncolored case, Hall's theorem makes proving this kind of results relatively simple, since we are interested in the non-existence of "no matching possible" witness (i.e. a subset that violates Hall condition) and we can use union bound to bound the probability from above (for $A_k$ = "k-th subset is a witness" give bound to $\mathbb{P}(\cup A_k)$). However, there is no simple condition of this kind equivalent to the existence of a rainbow matching.

Answer by Marcin Kotowski for Individual mathematical objects whose study amounts to a (sub)discipline?

2010-12-12T14:00:01Z

The Erdos-Renyi random graph model $G(n,p)$ - a single, concrete model that more or less created the field of random graph theory and is still studied.

Random rotations in SO(3) and free group

2010-11-28T13:17:16Z

Is it true that two random (w.r.t. Haar measure) rotations in $SO(3)$ generate a free group?

Regularity of asymptotic cones

2010-11-14T10:11:56Z

Are there any general conditions guaranteeing that the asymptotic cone of a group/graph is "regular" in some sense? E.g. for $\mathbb{Z}^d$ we get $\mathbb{R}^d$ as the asymptotic cone, which is even a manifold, but for general groups we only get a metric space without additional structure. Does knowing that asymptotic cone is regular (e.g. a manifold) imply any properties of the original group?

Asymptotics for forbidden subwords

2010-11-07T17:06:44Z

Fix an alphabet $A$ and consider words of length $n$ over $A$. Fix a set $B$ of $k$ forbidden subwords (subword is not necessarily connected, i.e. $abb$ is a subword of $abcb$). Can anything be said about the asymptotics of number of permissible words (i.e. words that don't containt any word from $B$ as a subword)? (a particular case - what if $n=k^{1+\epsilon}$ and we let $k \rightarrow \infty$?)

Property (T) and subgroups of finite index

2010-10-25T16:09:42Z

Suppose $G$ is a discrete group and $H \leq G$ a subgroup of finite index. If $H$ has Kazhdan property (T), does it follow that $G$ has property (T)? (I've read somewhere that (T) is preserved by exact sequences, so if $N$ is normal and $G/N$ is finite, then the fact above holds ; here, however, we do not assume $H$ to be normal)

Comment by Marcin Kotowski

2013-03-23T23:09:09Z

I edited that part of the question.

Comment by Marcin Kotowski

2013-03-04T17:25:06Z

Nb. for graphs (i.e. asking for the maximal number of $l$-cliques a graph can contain before it contains a $k$-clique) there are explicit bounds.

Comment by Marcin Kotowski

2013-03-04T16:23:59Z

I upvote the answer, but the conclusion "any subset B⊂A with positive relative density has a k-long arithmetic progression." seems too weak to say anything about the number of such k-progressions in the whole set.

Comment by Marcin Kotowski

2013-02-09T02:38:51Z

For embedding groups into Euclidean spaces, try googling "hilbert compression exponents". But then again, this is very far from isometry, since in this theory you can get, at best, only Lipschitz embeddings. The requirement of embeddings being isometries, rather than some weaker classes of maps, seems very stringent. Is that really what you want?

Comment by Marcin Kotowski

2013-02-07T15:28:03Z

@Anthony: do you have a reference? (although it shouldn't be too difficult to compute $\mathbb{E}|A-A|$ directly)

Comment by Marcin Kotowski

2013-02-07T15:24:47Z

@Seva: maybe you still can get something for |A| between n^alpha and n^gamma for some alpha, gamma < 1 (edited to clarify).

Comment by Marcin Kotowski

2012-10-29T19:51:35Z

I think this question would be more suitable on Math.SE.

Comment by Marcin Kotowski

2012-07-27T16:15:50Z

Where is the question? It seems you already have a proof, and you only need people to verify it?

Comment by Marcin Kotowski

2012-05-15T17:17:22Z

@Mikael: can this observation be generalized to higher order polynomials (e.g. $AUBU^{\ast}CUDU^{\ast}$)? In that case, we can't put E inside the trace for both terms UXU^{\\ast} only by linearity.

Comment by Marcin Kotowski

2012-05-15T15:40:35Z

@IR: yes, edited for clarity.

Comment by Marcin Kotowski

2012-02-29T19:06:50Z

@Suvrit: I guess your A and B are $3 \times 3$ matrices, not $4 \times 4$.

Comment by Marcin Kotowski

2012-02-12T00:35:03Z

In short, the question would be much better if OP cut all the hype about STEM, lions, $100,000 rewards, scalable quantum computing etc. and left the underlying mathematical question clear and well defined (in particular, it should be obvious why the question is not trivial).

Comment by Marcin Kotowski

2012-02-12T00:31:57Z

@Andres Calcedo: the question is simply difficult to comprehend - it either reduces to a trivial linear algebraic fact (see Theo's answer) or involves some unspecified "algebraic constraints" which are not at all clear from the question. Plus, a lot of "background" (thermodynamics, quantum varieties, talk about pullbacks) makes it even more muddled, the relation to quantum computing is completely opaque (even for me, who does research in quantum computing), and frankly speaking, sentences with "STEM" being every other word don't seem to hep.

Comment by Marcin Kotowski

2012-02-08T01:23:57Z

None of the results in the (excellent) paper you reference are ven remotely analytic.

Comment by Marcin Kotowski

2012-02-08T01:23:06Z

How is this an analytic fact?