User peter shor - MathOverflow

Answer by Peter Shor for Existence of unknowable algorithms ?

2013-04-06T16:53:56Z

Yes.

We take a fixed diophantine equation in variables $y,x_1, x_2, \ldots, x_k$. Task: for an input $n \in \mathbb{Z}$, output either

Five values of $y$ for which solutions exist to the equation.
A solution to the equation for which $y=n$.
"No", in which case there must be no solution with $y=n$.

It is clear that for any diophantine equation, there is a program which performs this task. If there are five values of $y$ for which solutions exist, you need only have the program output these for all inputs. If there are fewer than four values of $y$ for which solutions exist, once you know the solutions, then writing the program is trivial.

However, telling whether a solution exists to a diophantine equation is undecidable.

Answer by Peter Shor for Do names given to math concepts have a role in common mistakes by students?

2010-07-19T01:41:17Z

It's not just students who get confused by terminology. I was recently puzzled for quite a while until I realised that finite von Neumann algebras can be infinite-dimensional.

A = B (but not quite); 3-d arrays with multiple recurrences

2010-11-04T12:57:24Z

Many years ago, I discovered the remarkable array (apparently originally discovered by Ramanujan)

 1
 1    3
 2   10   15
 6   40  105  105
24  196  700 1260  945

which is defined by $S(i,j) = i\ S(i-1,j) + (i+j)\ S(i-1,j-1)$ and $S(0,1)=1$, and $S(i,j)=0$ if $j<1$ or $j>i+1$ . This array has the remarkable property that the sum of the numbers in the $i$'th row is $(i+1)^{i+1}$. This is not easy to prove. There are three approaches I know to proving this

Generating functions.
Counting subclasses of labeled trees.
Generalizing to a 3-dimensional array of numbers. There are recurrences on two sets of parallel planes, which intersect in the rows. One set of parallel planes contains the array above, and the other set contains a recurrence from which one can immediately deduce the row sums. Proving that these two different sets of recurrences give the same array is straightforward (albeit tedious without computer algebra) using induction.

(See SIAM Review, Problems and Solutions column, Vol. 21, pp. 258-260 (1979).)

The third approach is reminiscent of Wilf and Zeilberger's A = B theory of combinatorial identities, except there you have 3-dimensional arrays with recurrences on three sets of parallel planes. Wilf and Zeilberger's theory does not appear to shed any light on this recurrence.

My question is: does anybody know any other 3-dimensional arrays which have recurrences on two sets of parallel planes, but which do not fall under the A = B theory (so you cannot find a recurrence on a third set of parallel planes)? I would especially be interested in recurrences whose coefficients are polynomials in the coordinates $i,j,k$.

For more information about the connection with labeled trees, although this isn't directly connected with my question, see the papers Chen and Guo, Bijections behind the Ramanujan polynomials and Guo and Zeng, A generalization of the Ramanujan polynomials and plane trees, as well as the references in them.

Answer by Peter Shor for What are some correct results discovered with incorrect (or no) proofs?

2011-08-27T17:32:25Z

The Alternating Sign Matrix Conjecture in combinatorics was discovered (by researchers in the National Security Agency, so we don't know the motivation) in the late 1970s, but not proved for nearly 20 years. There is a wonderful book about it: Proofs and Confirmations, by David Bressoud.

Answer by Peter Shor for Defining a canonical ordering of matrix rows/columns

2011-06-16T20:42:31Z

What you want to do is presumably to find an efficient way to solve the graph isomorphism problem. Good luck on this; computer scientists have been trying to do it for decades.

If you don't care about efficiency in terms of finding the ordering relation, there are lots of things you can do. For example, you could choose the lexicographically first matrix of the form $PMP^T$. This definitely is canonical; the problem is that nobody knows of any efficient algorithm for finding it.

Answer by Peter Shor for If you break a stick at two points chosen uniformly, the probability the three resulting sticks form a triangle is 1/4. Is there a "nice" proof of this fact?

2011-06-03T05:18:48Z

Consider an equilateral triangle with altitude 1. It is not hard to show that if you choose a point randomly in this triangle, the distances to the three sides gives the same distribution of lengths that you obtain by breaking a stick at two random points. Now, the locus of points for which no distance is longer than 1/2 is the smaller equilateral triangle formed by joining the midpoints of the edges, which has area 1/4 that of the original triangle.

Can a mathematical definition be wrong?

2010-07-11T04:18:27Z

This question originates from a bit of history. In the first paper on quantum Turing machines, the authors left a key uniformity condition out of their definition. Three mathematicians subsequently published a paper proving that quantum Turing machines could compute uncomputable functions. In subsequent papers the definition of quantum Turing machine was revised to include the uniformity condition, fixing what was clearly a mathematical error the original authors made.

It seems to me that in the idealized prescription for doing mathematics, the original definition would have been fixed, and subsequent papers would have needed to use a different term (say uniform quantum Turing machine) for the class of objects under study. I can think of a number of cases where this has happened; even in cases where, in retrospect, the original definition should have been different.

My question is: are there other cases where a definition has been revised after it was realized that the first formulation was "wrong"?

Answer by Peter Shor for Mathematical ideas named after places

2011-05-11T15:54:46Z

Las Vegas algorithms.

Answer by Peter Shor for How to construct a maximally difficult NxN labyrinth ?

2011-03-27T16:10:59Z

UPDATE: the answer below works fine for tree-like labyrinths. The previous last paragraph (now struck out) is wrong, though, because the tree-like labyrinth you simulate depends on the random coins you flip.

Suppose the labyrinth is a tree. Further, suppose you do a random depth-first search on a tree, and stop when you reach a specific leaf called Ω. I claim that the expected number of times you traverse each edge is exactly once.

Proof: suppose you're at a node which is an ancestor Ω. There is one subtree of this node that contains Ω, and possibly several other subtrees that don't. For each subtree that doesn't, you explore it with probability ½, and if you do explore it, you traverse every edge twice (this is a property of depth-first-search). There is also one edge leading out of this node that leads to Ω. You will only go down this edge once. QED

Now, for any labyrinth that has a dead-end path, you need never go down the last segment of that path; thus the strategy of depth-first search, and turning back when you see a dead end, takes time strictly less than n². Thus, there is only one type of tree-like labyrinth that requires maximum expected time to traverse: the type where there are no choices, but just a single path that takes you to from the start to the goal.

If the labyrinth is not tree-like, I believe you can pretend that it is tree-like by pretending there are walls whenever a step will take you back to a section you've already visited, so the expected n² time upper bound will hold for this kind of labyrinth as well. I don't have a solution.

Answer by Peter Shor for Can a complex non-skew Hermitian matrix have purely imaginary eigenvalues?

2011-03-21T21:46:58Z

Take $$ L = \left( \begin{array} {rrrr} 7&-2&-2&-3\\ -2 & 4 & 0 & -2 \\ -2 & 0 &4 & -2 \\ -3 & -2 & -2 & 7 \end{array} \right).$$ Remove the last row and first column. The remaining matrix has two purely imaginary eigenvalues. Does this answer your question?

UPDATE:

Can I point out that, even though this matrix has imaginary eigenvalues, there is no value of $\omega$ such that $(j\omega I + L)_{(k,\ell)}$ has determinant zero, where $j = \sqrt{-1}$. This is because the operations of adding the identity and removing row $k$ and column $\ell$ do not commute. You may want to rethink your question.

Answer by Peter Shor for Expected Degree of a vertex in Delaunay Triangulations

2011-03-26T12:39:07Z

The expected degree for the Delaunay triangulation on hyperbolic space will depend on the density of the points. With low enough density points, you should get arbitrarily high degree. You should be able to get the expected degree as high as you want for a point distribution in the plane by taking the conformal representation of the hyperbolic plane as a varying metric in a unit disc (the Poincare disc), and placing the points with density proportional to this metric. Then the density goes to infinity at the boundary of the circle.

Note that since the Poincare disc model takes circles in the hyperbolic plane to circles in the disc, the Delaunay triangulation of a set of points (which is characterized by the fact that the circumcircle of every triangle does not contain another point) is the same in the disc and the hyperbolic plane. Thus, the expected average degree of the Delaunay triangulation should be the same in both of these scenarios.

The above construction satisfies the conditions stated in your question, but I don't know if you'll be satisfied. Did you want the points to be distributed on the entire plane? If so, I expect it's impossible because there's no way to put a conformal metric on all of $\mathbb{R}^2$ that gives the hyperbolic plane (although note that this isn't quite a proof).

Answer by Peter Shor for Which mathematical ideas have done most to change history?

2011-03-15T23:04:10Z

Error correcting codes. Without these, digital communications would be orders of magnitude more inefficient, and the internet, CD's, HDTV, and so on would not be possible.

Answer by Peter Shor for Random points in a rectangular grid defining a closed path

2011-03-03T12:51:12Z

Having screwed up the answer by getting the wrong answer for a really simple calculation the first time, I'm now going to try to redeem myself.

First, to make things easier, let each point be present with probability $h/(mn)$, and let these random variables be independent. This won't change the probabilities much.

You can calculate explicitly the expected number of squares. The expected number of squares is ${m \choose 2}{n \choose 2}(h/mn)^4$, since there are ${m \choose 2}{n \choose 2}$ possible squares, and each point is present with probability $h/mn$. This is roughly $1/4 (h^2/mn)^2$ (for large $mn$, and fixed $h^2/mn$).

Now, let's calculate the expected number of six-cycles. You can assume a $2k$-cycle lies in $k$ different columns and $k$ different rows (otherwise there is a smaller cycle), so we have ${m \choose 3}{n \choose 3}\alpha_3 (h/(mn))^6$ ways of getting a six-cycle. Here, $\alpha_3$ is the ways of getting a six-cycle in a 3 by 3 square, and it is easy to check that there are six of them.

There are four ways that it can look like this:

1.1
.11
11.

and two ways it can look like this:

11.
1.1
.11

Now, if we can compute $\alpha_k$, where $\alpha_k$ is the number of ways we can get a minimal $2k$-cycle in a $k\times k$ grid, we can get an infinite series for the expected number of cycles. For $\alpha_k$, we need to find a cycle which covers every row twice and every column twice. Let $\pi_1$ be the order that we visit the rows, and $\pi_2$ the order we visit the columns. We can assume that $\pi_1$ starts with $1$, and we can traverse each cycle in $2$ directions. This means that there are $(k-1)!$ possible $\pi_1$, $k!$ possible $\pi_2$, and we have to divide by $2$ because otherwise we count each cycle twice. Thus, the expected number of cycles when $m,n\rightarrow \infty$ is $$ \sum_{k=2}^\infty \frac{1}{2}(k-1)! k!{m \choose k}{n \choose k}\left(\frac{h}{mn}\right)^{2k},$$ which simplifies in the limit to $$ \sum_{k=2}^\infty \frac{1}{2k}\left(\frac{h^2}{mn}\right)^k,$$ or $$-1/2 \ln(1 - x) - x/2, \mathrm{\ \ where\ }x=h^2/(mn).$$ If objects are distributed with a Poisson distribution with expectation $r$, then the probability that there is an object is $1-e^{-r}$. Thus, if we assume that the closed paths are distributed according to the Poisson distribution, the probability that a closed path exists is $$1-(1-x)^{1/2}e^{x/2}.$$ As Kevin Costello remarks in the comments, you may be able to use Janson's theorem (also covered in Alon and Spencer's book) to prove that these closed paths obey Poisson statistics.

And below, another argument that the probability of a closed path rises to 1 when $h^2 =mn$, salvaged from my first attempt at solving the problem.

Let's start at a single point $P_0$, and look at the tree of paths that results. The tree of paths is obtained by looking for points in the same row as $P_0$, then points in the same column as these points, and then rows, etc. (Also do the same procedure, but starting with columns.) If any two points in this tree are equal (that is, there are two distinct paths leading from the starting point to the same point) then there is a closed path. So we want to know the probability that this tree of paths is fairly large. In particular, if the tree of paths has size $\sqrt{h}$, then by the birthday paradox there should be a reasonable chance that two of these points are equal.

But, assuming all the points are different, this tree of paths is a Galton-Watson branching process, and we can calculate the probability that it's large. (You can calculate lots of properties of Galton-Watson branching processes.) In particular, if the expected number of children is greater than 1, there is a finite probability that the tree is infinite. Using this is a rough criterion, you will start to get closed paths when $mn \approx h^2$. You should be able to a much better approximation by analyzing the associated Galton-Watson branching process more carefully.

The Galton-Watson tree has two branches. On the first branch, the number of children on odd levels are distributed approximately as a Poisson process with expectation $h/m$, and the number of children on even levels as a Poisson process with expectation $h/n$. On the second branch, distributions on the odd and even levels are reversed.

Answer by Peter Shor for Generalized Euclidean TSP

2011-03-01T22:23:51Z

You should be able to get $O(\sqrt{n/k})$ by choosing a smaller square of area $1/k$, which will contain one point from most of the point sets, and use the BHH theorem to find a TSP tour of this. Now, you have to show that adding the points from the point sets you left out doesn't increase the length of the tour much. It certainly won't increase it by more than a $\sqrt{\log n}$ factor, because a square $\log n$ times larger in area will with high probability contain a point from all the point sets, and choosing one point randomly from each of the point sets in that square gives points uniform in this square. I'd guess the tour length will still be $O(\sqrt{n/k})$, but you may have to do some work to prove this. On the other hand you certainly can't do better than this, because you need $n$ points in your tour, and the typical distance from one point to its nearest neighbor is $O(1/\sqrt{nk})$.

Here's a strategy for a proof of $O(\sqrt{n/k})$. First take a square of area $\alpha /k$, with $\alpha$ chosen so that this contains $9/10\, n $ of the classes of points. The BHH theorem shows you can find a TSP tour of this square with length $O(\sqrt{n/k})$. Now, we need to show adding the rest of the points doesn't increase the tour length very much.

We'll find subsquares $S_1$, $S_2$, $S_3$, $\ldots$, $S_{\log n}$ where the $i$'th square is big enough that the expected number of classes of points it contains is $(1-1/10^{i})n$. The area of the $i$'th square will be $\alpha i /k$ for some constant $\alpha$. To get a TSP of the $9/10^in$ new classes of points in the $i$'th square takes length $O\left(\sqrt{i 9/10^i n/k}\right)$. The series sums to $O(\sqrt{n/k})$.

Answer by Peter Shor for Large subgroups of the Hamming cube

2011-03-01T00:00:31Z

You can get half of the elements small. Let $e_k$ be the element $(0,0,\ldots,0,1,0, \ldots 0)$ with a single $1$ in the $k$th position. Let $v$ be the element $(1,1,1,1,1,\ldots,1)$. Now, consider the $t+1$ generators $v$ and $v+e_k$, $k = 1 \ldots t$. The subgroup generated contains the subgroup with $1$'s in any subset of the first $t$ positions, all of whose elements have Hamming weight at most $t$. The subgroup has order $2^{t+1}$, and there are $2^t$ small elements.

Unless $R$ is fairly big, you can't do better, because if you add an element with large Hamming weight to one with small Hamming weight, the result has large Hamming weight.

Answer by Peter Shor for Exponential bounds for the number of lattice animals with a given boundary.

2011-02-16T23:56:58Z

EDIT: I see that Steve has more or less the same construction above. I should have read his answer more carefully before I posted.

I don't believe it's true. Let's say you have a square polyomino with $n/2$ perimeter (so also $n/2$ site-perimeter) and you remove $n/2$ sites from its interior. Not all ways of doing this will give you a lattice animal with site-perimeter $n$, but if you just remove sites where both coordinates are even, you get a lattice animal (i.e., the polyomino will still be connected). The number of ways of doing this are roughly $cn^2 \choose n/2$, which grows as $e^{O(n \log n)}$.

ADDED MATERIAL:

There is an $e^{C n \log n}$ upper bound as well. Again, let's think about polyominos with site perimeter $n$. If we can specify the boundary of such a polyomino with $O(n \log n)$ bits, this gives a $e^{O(n \log n)}$ bound on how many of these there are. We will specify the boundary in two stages. First, let's look at the exterior edges (all the edges which can be connected to $\infty$ by a path of squares not in the polyomino). We can specify these exterior edges by a list of directions: e.g., EESENESSW$\ldots$, which is only $O(n)$ bits.

Now, let's look at the interior boundary edges. There are at most $cn$ of these for some constant $c$, and there are at most $n^2$ edges in the interior of the polynomial (the biggest it can be is an $n/4 \times n/4$ square), so we can specify these by creating some canonical list of the interior edges, and specifying which ones we have. This takes at most $\log_2 \sum_{k=0}^{cn} {n^2 \choose k} = O(n \log n)$ bits, and thus we get an $e^{C n \log n}$ upper bound on the number of these lattice animals.

This leaves the question open of what is $$C=\lim_{n\rightarrow \infty} \frac{\log f(n)}{n \log n}$$ (although it might even be difficult to prove rigorously that this limit exists).

Answer by Peter Shor for Optimally directing switches for a random walk

2011-02-08T22:15:10Z

This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorithms for Simple Stochastic Games." Look in this paper for the linear programming algorithm for SSG's with no min vertices. In one of her papers on simple stochastic games, Condon does indeed prove that the setting of the switches is independent of the start node, and that in the optimal strategy, the switch settings never need to change.

Answer by Peter Shor for Mathematical "urban legends"

2011-01-24T22:22:54Z

I've heard the following story (I don't know if it is true). A math professor gave his PhD student this journal paper, and asked him what consequences he could derive from it. The student started proving more and more interesting results based on this paper, until finally he proved a result that the professor knew was false. This led them to look more closely at the original journal paper, and upon close inspection, they discovered that it was wrong, rendering all the research the student had done so far worthless.

Answer by Peter Shor for An optimization problem

2011-01-06T22:49:21Z

I tried calculus of variations. It's been a while since I've done calculus of variations, so I could be messing it up completely. Also, this isn't completely rigorous. There are ways of making calculus of variations rigorous, but I don't know them, and they're a lot harder than just doing calculations.

By my comment above, the $Q(\frac{1}{2})=0$ constraint is worthless, so we will ignore it.

Assume $Q$ is the minimum function (this is the first, and most important, non-rigorous step, since we are assuming a minimum exists). Now, let's plug in $Q+\epsilon$, where $Q$ and $\epsilon$ are both functions of $x$. We have

$$M=\frac{1}{12} + \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right)^2 (Q+\epsilon)^2 \ dx - 4 \left[ \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) (Q+\epsilon) \ dx\right]^2 .$$

Extracting the first-order terms in $\epsilon(x)$, we get

$$\Delta M = 2\int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right)^2 Q \epsilon \ dx -8 \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) Q \ dx \ \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) \epsilon \ dx .$$

If we change $Q$ by adding an infinitessimal $\epsilon$, and keeping the normalization condition on $Q$, then $\Delta M$ has to be 0, or otherwise $Q$ wouldn't be a minimum. We still have to take care of the normalization condition $\int_0^\frac{1}{2} Q(x)^2 \ dx = 1$. We do this using Lagrange multipliers, and so we get the expression

$$2\int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right)^2 Q \epsilon \ dx -8 \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) Q \ dx \ \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) \epsilon \ dx + \lambda \int_0^\frac{1}{2} Q \epsilon\ dx .$$

This has to be zero for all functions $\epsilon(x)$. To simplify things further, let

$$C = \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) Q \ dx,$$

since it's a constant independent of $\epsilon$. Now, we have

$$2 \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right)^2 Q \epsilon \ dx -8 C \ \int_0^\frac{1}{2} \left( \tfrac{1}{2}-x \right) \epsilon \ dx + \lambda \int_0^\frac{1}{2} Q \epsilon\ dx $$

or, putting everything in the same integral sign,

$$ \int_0^\frac{1}{2} 2 \left( \tfrac{1}{2}-x \right)^2 Q \epsilon -8 C \left( \tfrac{1}{2}-x \right) \epsilon + \lambda Q \epsilon\ dx $$

and for this to be $0$ for all functions $\epsilon$, we must have

$$Q = \frac{ (\frac{1}{2}-x)}{\alpha(\frac{1}{2}-x)^2+\beta}$$

for some $\alpha$, $\beta$.

Note that, if $\beta \neq 0$, we get $Q(\frac{1}{2}) = 0$, as desired.

A Maple or Mathematica program should at least let you calculate $\alpha$ and $\beta$ numerically.

Answer by Peter Shor for Forbidden mirror sequences

2010-12-27T18:54:10Z

Here is a possible way of producing such forbidden configurations. Suppose you have $(ab)^k$ for some large $k$. Then I'd like to claim that $a$ and $b$ must be nearly parallel (see Thurston's answer). So produce a sequence with three mirrors containing $(ab)^k$, $(bc)^k$, $(ac)^k$ and a forbidden configuration for parallel mirrors such as the one you gave above (which you then have to prove also is forbidden for nearly parallel mirrors).

Answer by Peter Shor for Question about Banach's matchbox problem.

2010-12-22T23:02:54Z

What you're doing wrong is stopping when the first matchbox runs out. You have to allow $k=0$ to get the probabilities sum to 1, so you have to stop the simulation the first time an empty matchbox is pulled from a pocket (at which point the other pocket might have an empty matchbox in it as well).

Answer by Peter Shor for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T17:17:40Z

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} -\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles in a derangement is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$.

One can check this formula by noting that it gives the expected number of $n-1$ cycles as 0 and the expected number of $n$-cycles as approximately $e/n$ (this is correct, since the probability that a permutation is a derangement is approximately $1/e$).

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.

Answer by Peter Shor for Most intricate and most beautiful structures in mathematics

2010-12-17T18:10:30Z

How about the Leech lattice. This is a 24-dimensional packing of unit spheres where each one touches 196560 others. It is the densest 24-dimensional lattice packing (and very likely the densest 24-dimensional sphere packing, although this has not been proved). It has a remarkable amount of symmetry, and most of the densest sphere packings known in dimensions < 24 are derived from it (and known sphere packings in dimensions > 24 are nowhere near as dense when normalized for the dimension).

Maybe this is already implicitly included in the list, as it is closely related to the monster vertex algebra.

Answer by Peter Shor for Examples of non-rigorous but efficient mathematical methods in physics

2010-12-13T03:33:16Z

The replica method and the cavity method have been used by physicists to calculate thermodynamic quantities in various statistical mechanics settings (including quite a few classes of random combinatorial objects). The results are often exactly right, even though the method is not at all rigorous. Michel Talagrand has recently proven rigorously some of the results that have been obtained by these methods.

Answer by Peter Shor for Rainbow matchings (in random graphs)

2010-12-13T02:43:34Z

Isn't this very much related to the problem of a transversal in a Latin square? Suppose we have an $(n,n)$ bipartite graph with $n$ edge colors, such that every vertex has one edge of each color. This is equivalent to an $n\times n$ Latin square. A rainbow matching is a transversal of the Latin square. There is a conjecture (due to Ryser) that every Latin square with $n$ odd has a transversal, that is, a perfect rainbow matching. For even $n$, the conjecture (due to Brualdi) is that it has a partial transversal of length $n-1$ (i.e., a rainbow matching of cardinality $n-1$). To indulge in a little self-promotion, the best known result is that there exists a partial transversal of length $n -O(\log^2 n)$. There are also a number of results about transversals and partial transversals in near-Latin squares, which will probably be relevant to rainbow matching questions.

I guess the relevant Latin square question would be: does a random Latin square have a transversal with high probability? I know extensive calculations have been done which suggest that the answer is yes. I don't know whether anybody has proven this.

Answer by Peter Shor for how to find vector $(\pm 1, \pm 1, \pm 1, ... \pm 1)$ which is most close to given vector (r_1,...r_l) ? Is it NP-problem ? What algorithms are available ?

2010-12-01T15:59:39Z

Let the $R_i$ be $\pm 1$ vectors and the $V_i$ be a linear space over GF(2). This then becomes the problem of maximum likelihood decoding of binary linear codes, which is known to be an NP-hard problem. It thus seems likely (although it doesn't follow rigorously) that there's no good way of doing this better than brute force.

Answer by Peter Shor for An Alternative to the Cook-Levin Theorem

2010-09-04T13:26:21Z

In his infamously short paper "Average-case complete problems," Leonid Levin uses a tiling problem as the master ("first") NP-complete average-case problem (which means he also automatically uses it as a master NP-complete problem).

UPDATE: Contrary to what I was speculating in my answer previously, in his original paper on the Cook-Levin theorem (I found an English translation linked to from the Wikipedia Cook-Levin theorem article), it's not clear whether Levin uses the tiling problem as a master problem. He lists six NP-complete problems (SAT is number 3, and the tiling problem is number 6), but leaves out the proofs, so it's not completely clear which one is the master problem. Very likely, it was SATISFIABILITY, and so Levin found essentially the same proof as Cook.

Answer by Peter Shor for Quantum Error Correction

2010-11-24T01:26:49Z

The quantum channel capacity is the asymptotic amount of quantum information that can be carried by a quantum channel. There is a formula for it: it is given by the maximization of the regularization of the coherent information, as discussed in this paper by Graeme Smith which is a recent, short survey article. No single-letter formula (the Holy Grail of information theorists) is known.

If there is a density matrix on the input space of a channel for which the coherent information is positive, then there is an asymptotic sequence of quantum codes whose rate approaches this coherent information. Because coherent information is not additive, you can sometimes (although explicit examples are quite rare) improve the rate by using input states on the tensor product of $n$ copies of the channel.

Unlike classical information, which can be carried by any channel whose output is not independent of the input, there are some channels (such as classical channels) which are too noisy to carry quantum information. For these, for any input density matrix, the coherent information formula is always non-positive.

As for the OP's question, as best as I can interpret it, if the channel is not too noisy to carry quantum information, then for any $\epsilon$ there are codes (with block length going to $\infty$) for which the output quantum state is within $\epsilon$ of the input quantum state, although you cannot generally ensure perfect transmission of the input quantum state. Otherwise, the channel cannot be used to establish near-pure-state entanglement between the sender and the receiver, which means that any quantum information sent through the channel will always be degraded by some fixed amount.

Answer by Peter Shor for Relativistic Cellular Automata

2010-11-17T15:32:43Z

What Willie's answer shows is that, for some non-trivial Lorentz-translatable cellular automaton, every cell would need an infinite number of neighbors, a contradiction. There's a way of getting around this, though. You could make each cell correspond to a point in space-time and also a boost (a boost is essentially a velocity in the Lorentz group). Then, cells would interact with cells both close to them in space-time and also close in boost. I don't know whether anybody has considered cellular automata like this.

In order for this to have a correspondence to realistic quantum field theories, it would have to be the case that when two particles interact at a high boost, the interaction strength goes to 0 as the boost goes to infinity. I don't know whether this is true, although the thought experiment of considering particles falling into a black hole through a sea of Hawking radiation makes it seem like it might be.

Answer by Peter Shor for What is your favorite "strange" function?

2010-11-13T01:57:07Z

How about the function given by the Banach-Tarski paradox? This maps a ball into two copies of the same size ball, and is composed of isometries on subsets of $\mathbb{R}^3$.

Comment by Peter Shor

2013-05-10T12:23:17Z

Are turbo codes, LDPC codes, or polar codes the best choice for presentation to undergraduates? I think they're all possible, although you probably need a couple of hours to do it well. Turbo codes seem to have the disadvantage that you need more background; in particular, you need to go over convolutional codes first. Does anybody have any comments from experience?

Comment by Peter Shor

2013-05-06T01:07:30Z

How about Moser's recent constructive proof of the Lovasz Local Lemma? It's the first which actually gives an effective algorithm for finding the object that Lovasz proved existed, and it's accessible for undergrads.

Comment by Peter Shor

2013-04-20T21:57:37Z

Can you just say: the shortest piecewise linear path from the origin to the desired point where all the segments start and end on discs, and don't path through other discs. It's clear that there are such paths. Now, can we show that there is a shortest one by using compactness?

Comment by Peter Shor

2013-04-19T21:05:09Z

Aren't there exact formulas for all the quantities above? Why do we need any estimation?

Comment by Peter Shor

2013-04-09T20:11:54Z

It's too bad that I don't see how to make an algorithm like this based on the Mordell Conjecture (Falting's Theorem), as that would be quite a bit more natural.

Comment by Peter Shor

2013-04-06T18:11:22Z

@Michael: that's right ... the diophantine equation is fixed. Let me fix the variables.

Comment by Peter Shor

2013-04-06T16:25:56Z

In fact, I believe there are fairly simple problems with no known algorithms: for example, can this graph be embedded into three-dimensional space so that it does not contain any knotted cycles? (There were certainly no explicit algorithms known for this a few years ago.)

Comment by Peter Shor

2013-03-16T15:51:50Z

Thanks. This is exactly the kind of case I was looking for when I asked the question.

Comment by Peter Shor

2012-09-07T12:29:41Z

Even with your clarification, you still haven't completely specified the probability model for your random self-avoiding walk. I assume that your model is that, at every time step, the walk is equally likely to go to any unvisited adjacent vertex.

Comment by Peter Shor

2012-03-28T23:17:48Z

This is a question, not an answer.

Comment by Peter Shor

2011-12-24T00:33:40Z

Sure. There are lots of solids where finding the exact ground state is an NP-hard. These are called spin glasses(en.wikipedia.org/wiki/Spin_glass), and have interesting statistical mechanics and thermodynamic properties.

Comment by Peter Shor

2011-11-30T03:03:31Z

@D. Strong: it's not well-defined because you didn't include the information in the comment above in your original posting.

Comment by Peter Shor

2011-11-28T14:16:05Z

-1: Surely if the original paper is a dog's breakfast, and you can simplify it greatly, the mathematical community deserves to have the simplification available to it. And of course, you should give full credit to the original author, but if other people cite the simplified paper and not the original, it's really in part the original author's fault for not writing it up better in the first place.

Comment by Peter Shor

2011-11-06T20:51:02Z

Is this homework?

Comment by Peter Shor

2011-10-28T22:33:17Z

@Squark: Doesn't that article impose an extra locality condition?