User henry cohn - MathOverflow

Answer by Henry Cohn for Quantum algorithms for dummies

2013-05-03T12:22:37Z

Since you understand Grover's algorithm and Shor's algorithm, you're a lot closer to being up to speed than you might guess. Specifically, the field of quantum algorithms is fairly narrow, much more so than classical algorithms, so getting caught up is not as daunting. Aside from generalities like using quantum computers to simulate quantum systems, there are only three or four main types of quantum algorithms (at a broad level like "quantum Fourier sampling").

The right place to start is books like Mermin or Nielsen and Chuang, as in the other answers, but after that you'll have to move to papers. Stephen Jordan has compiled a pretty comprehensive list of about two hundred quantum algorithms papers in the Quantum Algorithms Zoo, organized by problem. Browsing through this list is a good way to get an overview of what's out there and choose some papers relevant to your interests.

Answer by Henry Cohn for Which hard mathematical problems do you have to solve to earn bitcoins ?

2013-04-20T03:53:32Z

Bitcoin mining is based on hash functions. Specifically the SHA-256 hash function, which maps arbitrary bit strings to 256-bit outputs in such a way that nobody knows how to find a collision (two inputs with the same output), although the pigeonhole principle implies collisions exist. Bitcoin mining doesn't involve finding collisions, which would be way too hard. Instead, one has to find inputs that lead to outputs with special properties, namely a lot of consecutive zeros. This is a scaled-down version of inverting the hash function. Of course there's no proof that any of this is actually computationally difficult, and some earlier hash functions have turned out to be weaker than expected (for example, MD5 and SHA-1), but it certainly seems to be.

SHA-256 is not a nice or simple function - it was designed to be hard to analyze - so I'd say this is a devilish problem.

Answer by Henry Cohn for Is there a "mathematical" definition of "simplify"?

2013-04-04T14:19:35Z

In full generality, there provably isn't any method for complete simplification (i.e., bringing an expression into a canonical simplest form). Simplifying should have two key properties: it should be algorithmic, and simplifying two different expressions for the same thing should give the same simplified form. If you have a simplification method with these properties, then it gives an algorithm for deciding whether two expressions are equivalent. However, Richardson proved that there is no algorithm to decide whether two closed-form expressions define the same function. (Of course you have to specify what you consider "closed-form". See D. Richardson, Some Undecidable Problems Involving Elementary Functions of a Real Variable, Journal of Symbolic Logic 33 (1968), 514-520, http://www.jstor.org/stable/2271358.)

Of course simplifying becomes easy if you give up on these properties. If you don't care about algorithms, just choose a representative for each equivalence class arbitrarily and declare it simplified. If you don't care whether equivalent expressions simplify to the same result, then just declare everything is already simplified.

This argument rules out only a very general notion of simplification. It still makes sense in many important special cases, and as Joel David Hamkins observes in the comments, one could still define a notion of simplicity even if there is no full simplification method.

Added in response to comments: Let's state things more precisely. Let the class $E$ of closed-form expressions contain $\log 2$, $\pi$, $e^x$, $\sin x$, and $|x|$ and be closed under addition, subtraction, multiplication, and composition of functions. These expressions all define continuous functions that are numerically computable (in the sense that one can algorithmically compute arbitrarily close approximations to their values at any given points). Call expressions $e_1$ and $e_2$ equivalent if they define the same function.

Richardson proved that there is no algorithm that can test whether two expressions in $E$ are equivalent. It follows immediately that no algorithm can bring elements of $E$ into any canonical form. I.e., there is no computable function $f$ from $E$ to $E$ such that $f(e_1)=f(e_2)$ iff $e_1$ and $e_2$ are equivalent.

Furthermore, one cannot even do it in the gradual sense described in the comments: there is no computable function $f$ from $\mathbb{N} \times E$ to $E$ with the following property: $f(n,e)$ is always equivalent to $e$, and if $e_1$ and $e_2$ are equivalent, then for all sufficiently large $n$ we have $f(n,e_1)=f(n,e_2)$ (of course how large $n$ needs to be may depend on $e_1$ and $e_2$). Think of $n$ as describing how hard you have tried to simplify your input, with the idea being that you eventually reach the canonical simplest form when $n$ is large enough, but you won't know when you've reached it (so you'll always be left wondering whether increasing $n$ would lead to further simplifications).

This observation requires a different proof, but it is not difficult. If such an $f$ existed, you could computably enumerate all the equivalent pairs $(e_1,e_2)$: to do so, loop through all triples $(e_1,e_2,n) \in E \times E \times \mathbb{N}$ and output $(e_1,e_2)$ whenever $f(n,e_1)=f(n,e_2)$. However, it is easy to computably enumerate the inequivalent pairs: loop through all expressions $e_1$ and $e_2$, rational numbers $x$, and natural numbers $k$, and output $(e_1,e_2)$ if numerically computing the corresponding functions at $x$ to within error less than $1/k$ shows that these functions differ at $x$. All inequivalent pairs will occur in this list, so if we could separately enumerate all the equivalent pairs (using the magic simplification function $f$), then we could solve the equivalence problem by seeing which list $(e_1,e_2)$ turned up in. That would contradict Richardson's theorem, and consequently $f$ does not exist.

What makes this tricky is that it's tempting to think the equivalent pairs should be computably enumerable. Can't you write down a list of all the expressions equivalent to $e$ by manipulating $e$ in all possible ways? Richardson's theorem implies that you cannot (for example, high school algebra manipulations are insufficient to get all equivalences, so high school classes give entirely the wrong impression). Proving two functions are different is easy, but proving two functions are the same is not, and there is no systematic way to do it.

Answer by Henry Cohn for Kissing Number of Spheres in Non-Euclidean Geometry

2013-03-01T08:32:12Z

To understand the cases of spherical or hyperbolic geometry, it is helpful to think in terms of spherical codes. A Euclidean kissing configuration is equivalent to an arrangement of points on a sphere with all angles between them at least 60 degrees (these are the points of tangency with the surrounding spheres). The same construction works in any sphere or hyperbolic space $X$, because the induced geometry on spheres in $X$ is itself spherical geometry. The only thing that varies is the minimal angle, which will generally no longer be 60 degrees. Instead, it will depend on the radius of the kissing spheres, and it can be calculated using the (spherical or hyperbolic) law of cosines.

So the kissing problem in spaces of constant curvature amounts to looking at spherical codes with differing angles. I don't know what happens in the other Thurston geometries. There has been some study of packings in these geometries (see, for example, http://arXiv.org/abs/1210.2202 by Szirmai), but I don't know offhand about optimal kissing numbers.

Answer by Henry Cohn for Attack on CRT-RSA

2013-01-29T01:50:35Z

It's a good question, since it looks like Boneh's paper doesn't give a reference. It's not actually a man-in-the-middle attack, at least not the attack I've seen. Instead, it's reminiscent of baby-step giant-step but with an extra twist. Here's how it works.

Suppose we are given $N$ and $e$, where $N=pq$ with $p$ and $q$ distinct primes and $ed \equiv 1 \pmod{p-1}$ with $0 < d < D^2$. We are not given $p$, $q$, or $d$, but we know the bound $D$. We want to factor $N$ in roughly $D$ steps (up to log factors). For what I'm about to do, we'll have to assume that the inverse of $e$ modulo $q-1$ isn't $d$, and in fact isn't anything like $d$, but this assumption holds for CRT RSA.

For a random value of $x$, $\gcd(x^{ed}-x,N)$ will be $p$ with good probability (this is where we need the assumption). If we write $d = a + bD$ with $0 \le a,b < D$, then $\gcd(x^{ea}x^{ebD}-x,N)$ will be $p$, and in fact the gcd of $\prod_{i=0}^{D-1} (x^{ei}x^{ebD} - x)$ and $N$ will also be $p$ with good probability. (Note that if the inverse of $e$ modulo $q-1$ were of the form $i+bD$ with $0 \le i < D$, then this would fail since we would pick up a factor of $q$ in the product. This is what I meant by "anything like $d$" above.)

Now consider the polynomial $\prod_{i=0}^{D-1} (x^{ei}y - x)$ in the variable $y$. In a number of steps nearly linear in $D$, we can compute this polynomial modulo $N$ and then we can evaluate it at any $D$ given points. (This requires special algorithms, since for example multiplying the factors one by one would require about $D^2$ operations. See Chapter 10 of von zur Gathen and Gerhard's book Modern Computer Algebra for background on fast evaluation and interpolation algorithms.)

Given these fast algorithms, the final steps are easy: we compute the polynomial, compute the $D$ evaluation points $y = x^{ebD}$ with $0 \le b < D$, compute the evaluations of the polynomial at these points, and take their gcds with $N$. All of this is nearly linear-time in $D$, and one of the gcds will give us the factor $p$.

Answer by Henry Cohn for Role of statistical estimation in formal proof

2012-12-30T14:29:42Z

It's not clear to me what you mean by "valid rigorous reasoning". A statistical argument is certainly worse than a rigorous proof, and there are big philosophical differences between them. For example, a statistical argument depends on having a good source of randomness, and the quality of that source is difficult to verify after the fact, so independent replication becomes important. One might in principle be able to convert a statistical argument into a rigorous proof using a high-quality pseudorandom generator, but that's a different question. (Of course the generator would have to satisfy strong restrictions, and we generally don't yet know enough about complexity theory to make this kind of argument work.)

On the other hand, principled statistical arguments are certainly convincing, and they are the next best thing to rigorous proofs. People use them all the time, for example with probabilistic primality tests. In theoretical computer science, there's a theory of probabilistic proof systems, which explores what can or can't be demonstrated efficiently using this kind of statistical reasoning. (This only really makes sense in a computationally-bounded framework, since if you have unlimited time you can simply check all the possible random choices by brute force and thereby remove randomness from the picture.) See http://www.wisdom.weizmann.ac.il/~oded/pps.html for some surveys and references.

Answer by Henry Cohn for Last term of repeating continued fraction expansion

2012-09-03T05:28:32Z

It's known that a quadratic irrational has a purely periodic continued fraction expansion if and only if it is greater than $1$ and its conjugate is between $-1$ and $0$. Your observation amounts to proving that $r+2 + (-3+\sqrt{D})/2$ has this property (note that adding $r+2$ makes it start with $2r+1$). That amounts to checking that $-1 < (2r+1 - \sqrt{D})/2 < 0$, which is equivalent to your assumption that $(2r+1)^2 < D < (2r+3)^3$.

Answer by Henry Cohn for How should an analytic number theorist look at Bessel functions?

2012-08-30T20:28:32Z

Radial Fourier transforms provide a good, consistent perspective on most of the theory. The Fourier transform $\widehat{f}(t)$ of a function $f \colon \mathbb{R}^n \to \mathbb{R}$ is given by the integral of $f(x) e^{2\pi i \langle x,t \rangle} \, dx$ over $x \in \mathbb{R}^n$. If $f$ is a radial function (i.e., $f(x)$ depends only on $|x|$), then we can radial symmetrize everything and the exponential function averages out to a radial function. Specifically, we get $$ \widehat{f}(t) = 2\pi |t|^{-(n/2-1)} \int_0^\infty f(r) J_{n/2-1} (2 \pi r |t|) r^{n/2} \, dr. $$ The precise factors are a little annoying, but basically this just means $J_{n/2-1}$ is what you get when you radially symmetrize an exponential function in $n$ dimensions. It's easy to see that if you symmetrize $e^{2\pi i \langle x,t \rangle}$ by averaging over all $x$ on a sphere, then you get a radial function of $t$, and furthermore as you vary the radius of the sphere you just rescale the function. So the one function $J_{n/2-1}$ captures all of this, modulo scaling.

One consequence is that Bessel functions inherit the orthogonality of the exponential functions (i.e., the different scalings are orthogonal), so they also inherit all the consequences of orthogonality. For example, this is really where the differential equation comes from. There's a strong analogy between Bessel functions and orthogonal polynomials, where rescaling the Bessel function corresponds to varying the degree of the polynomial.

You also get certain qualitative results for free: for example, the product of two Bessel functions should be an integral of Bessel functions with positive coefficients, since this corresponds to saying the product of two radial, positive-definite functions remains positive definite. You can write down the coefficients explicitly, but sometimes all you need is nonnegativity, and in any case this point of view makes it easy to believe that there should be an explicit formula.

This is basically a low-brow version of the representation theory approach. Basically, ordinary Fourier analysis studies $L^2(\mathbb{R}^n)$ under the action of the translation group $\mathbb{R}^n$. If you look at the full group of isometries of $\mathbb{R}^n$ (including the orthogonal group), then it's just a little more elaborate, and the Bessel functions arise as zonal spherical functions. It's worthwhile working through this perspective, but in practice just thinking about radial Fourier analysis gives you most of the benefits with less machinery.

Answer by Henry Cohn for Euler Mascheroni Constant, Curious?

2012-08-14T11:59:47Z

In his 1887 paper Table des valeurs des sommes $S_k = \sum_{1}^\infty n^{-k}$ (Acta Mathematica 10 (1887), 299-302; volume available online), Stieltjes used almost exactly this formula to compute Euler's constant to 33 decimal places. Of course as quid points out you need to know the zeta values to do this, but the main point of this paper was to compute those values, so he was just getting Euler's constant as a corollary. He uses a slight variant of the formula, with $\zeta(2k+1)-1$ in place of $\zeta(2k+1)$ for faster convergence (and a corresponding adjustment in the other term, which becomes $1+\log 2 - \log 3$). He derives the formula by taking the Taylor series expansion of $\log \Gamma(1+x)$ and using it to compute $\log \Gamma(1+1/2) - \log \Gamma(1-1/2)$.

Answer by Henry Cohn for Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

2012-07-24T13:28:34Z

Yes. Without loss of generality, we can assume $p(x)$ is not divisible by $x$. Then $p(x)(x^2+1)$ and $p(x)(x^2+x+1)$ both have constant term $1$, so the combined Hamming weight is at least $4$ from the constant and leading terms. The only way it could be $4$ is if they were $x^n+1$ and $x^m+1$ for some $n$ and $m$. However, $p(x)(x^2+1)$ and $p(x)(x^2+x+1)$ have the same degree and are not equal to each other, so this cannot be the case.

Answer by Henry Cohn for How fast can we really multiply matrices?

2012-07-06T21:43:37Z

There are currently no practical implications of any fast matrix multiplication algorithms besides Strassen's. The Coppersmith/Winograd algorithm and its descendants (Stothers, Williams) are very complex, depend on probabilistic constructions, etc. There's no theoretical obstacle to implementing them in the sense you're asking about, and it's something that's humanly possible, but there's little point to it and I don't believe anyone has ever actually done it. It would be complicated and painful, and the only purpose would be really learning how the algorithm works, since the cross-over point for where it would improve on the naive cubic-time algorithm is enormous (so you'll never actually see any improvement). There are other algorithms that would be somewhat easier to implement, at the cost of worse asymptotic performance, but they are also utterly impractical.

There's also a deeper issue if you try to use algebraic algorithms in practice. The algebraic complexity model typically used for these problems counts only arithmetic operations and considers memory access to be free. This made sense way back when, since a single floating point operation was comparatively expensive, but nowadays memory management can be the real bottleneck in practice. Algebraic complexity is beautiful and theoretically important, but it ignores important practical issues.

If you want to do fast matrix multiplication in practice, it will presumably be on a parallel computer. That introduces further issues of communication complexity; see http://arxiv.org/abs/1202.3173 for an analysis of the Strassen case (both theoretically and in practice).

Answer by Henry Cohn for Are isospectral manifolds necessarily homeomorphic?

2012-05-16T04:30:30Z

There's an example due to Doyle and Rossetti ("Tetra and Didi, the cosmic spectral twins"; http://arxiv.org/abs/math.DG/0407422) of 3-manifolds that are isospectral but not even homeomorphic. I don't know if this was the first such example.

Answer by Henry Cohn for Do you use the Mathematics Subject Classification (MSC) when searching for literature?

2012-05-11T16:21:53Z

At first, I thought this was a silly question, and it seemed highly implausible that searching by MSC code could actually be good for anything. Certainly it's a terrible way to find specific information, but I just gave it a try and it's quite a bit more useful than I thought. I put 52C17 in MathSciNet and got a list of 731 papers, and I've just been browsing through them and learning about a number of interesting papers I was unaware of. I should do this more often.

So my answer is that it's a waste of time if you're looking for anything in particular, but it can actually be a good way to get an overview of what's been happening recently in an area.

Answer by Henry Cohn for The gimbal lock shows up in my quaternions

2012-05-03T19:42:22Z

There's no paradox here: you did the same calculation in two different ways and got the same answer, as you should. The issue is how to think about gimbal lock.

How should you represent a rotation in three dimensions? You can try using Euler angles to represent it using three rotation angles, but there's something fishy about this. That naturally parametrizes a three-dimensional torus, but the rotation group is not a torus (rather, it's a projective space). It doesn't even have a torus as a covering space, but rather a 3-sphere. So the problem is that the naive coordinates just don't give the right topology, and therefore something must go wrong in degenerate cases to fix the topology. Gimbal lock is essentially a name for what goes wrong.

When people say quaternions avoid gimbal lock, they mean the unit quaternions naturally form a 3-sphere, so there are no topology issues and they give a beautiful double cover of the rotation group (via a very simple map). Keeping track of a unit quaternion is fundamentally a more natural way to describe a rotation than keeping track of three Euler angles.

On the other hand, if you describe your quaternion via Euler angles, then gimbal lock shows up again, not in the quaternions themselves but in your coordinate system for them. That's what you are seeing in your calculations: you are doing a standard calculation to see the effects of gimbal lock, and then redoing the same calculation using quaternions.

Some explanations of gimbal lock don't distinguish clearly between the underlying geometry/topology and the choice of coordinates, which has always annoyed me, since that's essential for understanding what's going on mathematically.

Answer by Henry Cohn for What is the largest possible thirteenth kissing sphere?

2012-04-21T17:02:53Z

Pietro's version of this question is answered in a paper by Oleg Musin and Alexey Tarasov (to appear in Discrete & Computational Geometry, http://dx.doi.org/10.1007/s00454-011-9392-2, http://arxiv.org/abs/1002.1439). The configuration found by Schütte and van der Waerden (see Joseph O'Rourke's answer) is optimal and unique up to isometries.

The other version of the problem amounts to asking for the largest possible hole in a packing of 12 identical disks of radius $30^\circ$ on the 2-sphere. I don't know the answer offhand. One could certainly figure out what it must be by numerical optimization, but finding a rigorous proof would be difficult. (It might be possible using variants of the Musin-Tarasov approach, which is an enormous brute force search over small planar graphs.) I am sure someone must have looked at this problem, but I don't know of a place where the answer might be recorded.

Integrability of the Cohen map

2012-04-12T22:51:20Z

In the 1990's, Henri Cohen asked whether the map $(x,y) \mapsto (\sqrt{1+x^2}-y,x)$ from $\mathbb{R}^2$ to itself is integrable. In other words, are the orbits confined to the level curves of some nice function? It certainly looks like they are if you make plots (the postscript file at http://www.math.washington.edu/~cohn/cohen.ps shows some orbits and is easy to modify), [Image (rotated) added by O'Rourke:]

but no algebraic function could play this role (a result of Rychlik and Torgerson; http://nyjm.albany.edu/j/1998/4-5.html). Years ago, someone told me it was unlikely that it was really integrable, because careful investigation identified hyperbolic periodic orbits, but I never learned more and I didn't see this in my crude plots. Unfortunately, I don't remember who told me.

Is the map actually integrable? This may well be an open problem: I looked at the papers that cite the Rychlik and Torgerson paper, except for one I couldn't access, but I found no evidence that this question has been resolved. On the other hand, there don't seem to be many papers on this topic, and perhaps that's because the conjecture turned out to be false, with a disproof that was never published.

If it isn't integrable, then what could explain the near integrability? From my naive perspective, a simple system like this that looks integrable but isn't would be really amazing. Are such things more common than I realize?

Answer by Henry Cohn for Cryptography and iterations

2012-04-13T16:11:14Z

What makes Diffie-Hellman work is that the secret maps $x \mapsto x^n$ and $x \mapsto x^m$ commute with each other and are both easy to compute (even if $n$ and $m$ are huge), but knowing $g^n$ doesn't let you easily raise other numbers to the $n$-th power.

Your scheme achieves the commutativity by making both maps powers of a given function $T$, but generically it won't make them easy enough to compute, so it doesn't offer any computational advantage for the participants compared with an attacker. Without some special structure, computing $T^n(x)$ will take about $n$ operations, since you'll have to compute each of $T^1(x)$, $T^2(x)$, etc. in turn. Breaking the scheme by computing $n$ from $T^n(x)$ will be just as fast.

Diffie-Hellman would have the same problem if you had to compute $g^n$ naively (using $n$ operations), but you can use repeated squaring to handle much larger values of $n$. You can certainly use repeated squaring to compute powers of $T$, too, but the underlying set $X$ will be huge, so you'll need a more efficient way to represent powers of $T$ than just as permutations of $X$. This will depend on having some structure, for example knowing that $T$ is in some smaller group, and then the question becomes whether this structure helps break the system.

In principle, I don't see why this shouldn't be secure, because Diffie-Hellman is a special case:

Typically, $g$ will be chosen to have prime order $p$. If $h$ is a primitive root modulo $p$, then all exponentiation maps mod $p$ are powers of $x \mapsto x^h$, so Diffie-Hellman becomes isomorphic to your scheme with $T(x) = x^h$. Maybe I'm overlooking something, but I don't see offhand why knowing a primitive root modulo $p$ would let one break Diffie-Hellman. In that case, your scheme can be as secure as Diffie-Hellman.

However, the security would depend delicately on how you choose $T$, and I wouldn't trust other choices without a lot of thought and cryptanalysis.

Answer by Henry Cohn for Mathematical modeling of voting/rating (e.g. political elections, questions on MO, gadgets on amazon,...)

2012-03-20T17:07:11Z

Unfortunately, I don't expect that there's any clear-cut mathematical solution to this problem. The modelling issues are rather subtle, and different people will make very different assumptions in the framework they are using. I think there's a lot of value to exploring these possibilities, but it's likely to lead to a lot of competing, somewhat useful approaches, rather than a definitive or widely accepted solution.

Social choice theory deals with aggregating opinions from a lot of voters, and this is a huge field. (Donald Saari has written some great books on this topic.) The drawback is that it doesn't deal with the "ideal choice" aspect of your question, but rather just with which choice is most popular or representative in some way, which becomes subtle when there are more than two choices. Is it better for everyone to be lukewarm, or for some people to love a choice and others hate it?

There's been a lot of work in machine learning on learning from expert advice, where the experts may have different levels of expertise, which you don't know in advance and which can even change over time. Under certain assumptions, multiplicative weight algorithms and boosting are excellent ways to solve this problem, and they are quite simple and practical. (See http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf and http://cseweb.ucsd.edu/~yfreund/papers/adaboost.pdf, for example.) This can be viewed as a reputation-based system, which rewards experts for good performance.

However, the assumptions are really critical. For example, these methods apply to cases where you get periodic objective feedback that can be used to judge the experts. In some cases, like journal ranking, you just don't: you learn something from measures like citation counts, but nobody thinks they are the best measure of quality, and you don't want the whole system to degenerate into a contest over who can best predict citation counts. On the other hand, a contest over who can predict repair rates for cars is not so crazy.

This is where the modelling gets tricky. People may not even agree on what they are trying to measure, let alone how to measure it. For example, which is more impressive: a relatively shallow paper that excites and inspires many people to do better work on the topic, or a deeper paper that plays a critical role in a smaller and arguably less important area? If we can't even settle that informally, it's hard to build a model.

There are also nontrivial issues of incentives. For example, the U.S. News & World Report college rankings are partly based on reputation surveys. Some university administrators have deliberately rated their institution highly and all others as inferior, to boost their rankings. (Clemson admitted this publicly; see http://www.insidehighered.com/news/2009/06/03/rankings.) The subfield of mechanism design within game theory addresses this issue of figuring out how to elicit information without giving anyone an incentive to lie. It can be done in some cases, but it's a hard problem, especially in cases like product reviews where, say, the manufacturer or a competitor may be hiring people behind the scenes to provide biased reviews. (I don't know of good statistics for this, but it is widely believed to be a serious problem.)

Overall, there are a lot of important ideas out there that are relevant to this topic, and I expect further progress. However, the modelling issue is a huge obstacle.

Answer by Henry Cohn for Can ZFC prove "false theorems", and still be consistent? (was "Junk Theorems" follow up)

2012-03-13T04:04:15Z

Here's an argument for why the answer is no:

First, let's formulate the question as follows. Is there a meaningful mathematical statement that can be disproved in ordinary mathematical practice but that's a theorem of ZFC under the standard definitions? We need to rule out type mismatches (is $2 \in \pi$?) and abuse of notation (whether $\mathbb{N}$ is actually a subset of $\mathbb{Z}$ or merely canonically isomorphic to a subset of $\mathbb{Z}$), but then there won't be any such statements, of course assuming ZFC is consistent.

The reason is that the ordinary mathematical arguments will have to be based on certain axioms, and the set-theoretic constructions have been designed to satisfy those axioms. For example, you want $\mathbb{N}$ to satisfy the Peano axioms, and indeed ZFC proves that it does. Assuming ZFC is consistent, you therefore can't use the Peano axioms to disprove anything ZFC proves about $\mathbb{N}$.

Similarly, when you construct $\mathbb{R}$ you prove that it's a complete ordered field (i.e., every nonempty subset that is bounded above has a least upper bound). This is enough to do elementary analysis, so our theory isn't going to contradict calculus unless ZFC is inconsistent.

In practice, when people build up mathematics within set theory, there are only two gaps in what they care about. First, there's the behavior of $\in$: ZFC assumes everything is a set, so you always have the potential for unexpected things to be elements of each other, but this is the type mismatch issue and is easily ignored. (You might worry that what if, for example, these sentences have consequences that conflict with the Peano axioms? Then ZFC would be inconsistent, since it can prove the Peano axioms.) Second, there's the abuse of notation. The von Neumann definition of $\mathbb{N}$ is beautiful and pleasant to use, but it's not literally going to be a subset of most other constructions. If you want to be super careful, you should either harmonize all your constructions or explicitly write out inclusion maps, but a little sloppiness does no harm.

The argument I've just outlined really isn't a mathematical theorem, because we haven't defined ordinary mathematical reasoning (ZFC is the closest thing we have to a definition, but that would make this whole argument vacuous). However, it's still true in a philosophical sense.

What it comes down to is that the $\mathbb{N}$ vs. $\mathbb{Z}$ abuse of notation is harmless, and that incorrectly typed statements are never used in ordinary mathematics. (If people proved everyday theorems using $2 \not\in \pi$ as an axiom, then we would have to worry about whether that axiom was compatible with our set-theoretic constructions. However, as long as ZFC is consistent, including incorrectly typed statements together with the usual axioms cannot cause problems.)

Answer by Henry Cohn for What would be some major consequences of the inconsistency of ZFC?

2012-03-11T05:39:59Z

I'm confident that ZFC is consistent, but one can imagine an inconsistency. Like François said, it would probably be handled pretty well. I'd divide the possibilities into four cases:

A technicality, like separation vs. comprehension in ZFC. This would be an important thing to get right, but it would have little impact on the theorems mathematicians prove. (For example, Frege's system was inconsistent, but his mistake didn't propagate.)
A topic requiring serious clarification, like infinitesimals in the 1600's. The intution was right, but it took some genuine work to turn this intuition into actual theorems with rigorous proofs.
A topic that fundamentally cannot be clarified, where some part of mathematics just turns out to be defective. For example, imagine if cardinals beyond $\aleph_0$ were inherently self-contradictory, and no clarification could save them. This would require huge modifications to set theory.
It could turn out that we have no idea what any of mathematics really means. For example, if Peano Arithmetic were inconsistent, then it would call into question the whole axiomatic approach to mathematics. It would be tantamount to saying that the natural numbers as we understand them do not exist. (Some parts of the axiomatic approach could still survive, but I don't think it would be wise to trust anything if we couldn't even get the consistency of PA right.)

My feeling is that 1 is very unlikely, 2 would be among the biggest shocks in the history of mathematics, 3 is difficult to imagine, and 4 is so extreme that if I read a proof of the inconsistency of PA, I'd be more likely to decide that I had gone crazy than that PA was actually inconsistent.

Answer by Henry Cohn for How to make the move to a research university from a liberal arts school?

2012-02-10T02:22:14Z

I hope someone will supply a better answer, but here are some thoughts, based on one case in which I wrote a letter for someone who successfully moved from a teaching-oriented to a research-oriented job. It was before tenure, and I really don't know a strategy for doing it post-tenure.

My impression is that there are two tricky issues. One is that it's difficult to develop one's research abilities to their full potential in an environment not optimized for that. It's therefore important to have letters that say you have the potential to do even better work in the right environment. On the other hand, they also need to emphasize the quality of your current work (if not its quantity), since if they just focus on your potential you will come across as a big risk. This takes some balancing, and it's not likely to happen unless the recommender thinks about it. That should always happen, and it usually does, but some people just don't know how to write a good letter of recommendation, and others may be too busy to do a good job. Unfortunately, choosing the right letter writers can be difficult, since you don't have the information you need to judge this. I'd recommend talking over the possibilities with a trusted mentor, trying to choose recommenders who are really supportive, and then explicitly strategizing with them about your circumstances. However, that's easier said than done.

The other issue is that you may be quickly eliminated based on superficial criteria, just because there are so many applicants that they can't each get more than a quick reading. What you need is a mentor who can e-mail people at various universities and let them know that even though your application may not fit their preconceived notions of what they are looking for, they should examine it carefully.

Answer by Henry Cohn for When can a family of polynomials get a weight function to be made orthogonal?

2012-01-27T23:13:08Z

Favard's theorem characterizes this in terms of the three-term recurrence. Suppose the polynomials $P_n$ are normalized so that they are monic. Then they are orthogonal polynomials with respect to some Borel measure if and only if there are constants $\alpha_n$ and $\beta_n$ such that $P_n(x) = (x+\alpha_n) P_{n-1}(x) + \beta_n P_{n-2}(x)$ and $\beta_n < 0$. (The sign condition on $\beta_n$ is needed to get a positive measure. I think you still get a signed measure if you have a three-term recurrence with $\beta_n \ge 0$, but I'm not certain offhand.)

This is pretty easy to test for in practice if you are given a sequence of polynomials numerically. Strictly speaking, it doesn't guarantee a weight function as specified in your question, since the measure may not be absolutely continuous with respect to Lebesgue measure, but I assume that's not what you really care about. If it is, then I'm not sure offhand how to characterize that case.

Answer by Henry Cohn for polynomials and electrostatics

2012-01-25T22:00:50Z

For certain orthogonal polynomials, there is an electrostatic interpretation that goes back to Stieltjes. For example, suppose we put charges of $(1+\alpha)/2$ and $(1+\beta)/2$ at $1$ and $-1$, respectively, and put $n$ particles with charge $1$ in between them. Then the minimal energy configuration of the $n$ particles is at the roots of the $n$-th degree Jacobi polynomial with parameters $(\alpha,\beta)$. See http://arxiv.org/abs/math/0512293 for a survey of related results.

Answer by Henry Cohn for Delaunay triangulations and convex hulls

2012-01-23T05:08:36Z

It's known; for example, my coauthors and I used this characterization in http://arxiv.org/abs/math.MG/0611451. However, we certainly weren't the first, and I don't know the earliest reference. I think it is well known among those who think about spherical codes, and it has probably been known for a long time, but it ought to be more broadly known.

The duality between nearest and furthest does occur even in this framework, however. It amounts to the distinction between looking at outer and inner facet normals:

If $V$ is a full-dimensional, finite subset of a sphere, then the outer normal vectors for the facets of its convex hull are the holes in $V$, i.e., the points on the sphere whose nearest neighbors in $V$ are as far away as possible. The inner normal vectors are the points for which the furthest points in $V$ are as close as possible. (It's easy to verify that multiplying by $-1$ interchanges these two conditions.)

Answer by Henry Cohn for convex polytopes with many faces and edges but few cells and vertices

2012-01-20T18:51:35Z

As of 2003, I don't think it was known whether $f(P)$ is bounded. See Fat 4-polytopes and fatter 3-spheres by Eppstein, Kuperberg, and Ziegler (http://front.math.ucdavis.edu/0204.5007), which contains a beautiful construction that achieves $f(P)>5.048$, and shows that it is not bounded for strongly regular CW decompositions of the 3-sphere (instead of polytopes). I don't know whether there has been more recent progress.

Answer by Henry Cohn for Enumerating Perfect Lattices

2012-01-06T02:18:54Z

The algorithm stops when you don't get any more perfect forms. Specifically, at each step you determine all the contiguous forms $Q_i$ and test whether they are equivalent to forms you already knew. For all the ones that aren't, you add them to the list and iterate to determine all the forms contiguous to them, etc., so your list keeps getting longer and longer. At some point all of the contiguous forms will already be on the list, and then you are done.

Theorem 3.1.3.2 shows that there are only finitely many perfect forms, so the algorithm must eventually terminate, but the specific bound is not used in the algorithm.

You are right that finding extreme rays of polytopes in high dimensions is the bottleneck. To deal with the 8-dimensional case, you need to take advantage of all available symmetries (see Appendix A), and 9 dimensions has not been completed.

Answer by Henry Cohn for Minimize Energy for Charge Distributions

2011-11-12T04:54:49Z

The behavior for continuous charge distributions amounts to classical potential theory; for discrete charges, you get this behavior in the continuum limit.

It is true that the distribution is uniform for a sphere. On other manifolds things can be more complicated. See http://www.ams.org/notices/200410/fea-saff.pdf for a very nice exposition and further references. For example, Figure 5 from that paper (included here thanks to Joseph O'Rourke) shows the limiting distribution for particles on a torus under an inverse $s$-th power law:

In this example, for $s \ge 2$ you get a uniform distribution, which is the default behavior when the energy for a continuous charge distribution diverges. For $s < 2$ the particles converge to the continuous distribution that minimizes energy. When $s<1$, this distribution is not even supported on the entire torus.

You don't see these phenomena for the sphere, because of its symmetry, but they are typical for less symmetric manifolds.

Incidentally, the behavior of 1 and 2 dimensions is not so strange. The charges do indeed end up on the boundary, if one uses a harmonic potential function (for example, a logarithmic potential in $\mathbb{R}^2$). The difficulty is that the Coulomb potential is not harmonic in $\mathbb{R}^1$ or $\mathbb{R}^2$. One way of thinking about it is that if you view the needle or disk as sitting inside $\mathbb{R}^3$, then the charges do all end up on the boundary, because the boundary in $\mathbb{R}^3$ is the entire set.

More generally, in $\mathbb{R}^n$, if you use an inverse $s$-th power law for the potential function, then all the charge will be on the boundary if $s \le n-2$ (because the potential function is superharmonic and therefore satisfies the minimum principle). When $s > n-2$, that does not happen.

Answer by Henry Cohn for Evidence for integer factorization is in $P$

2011-10-28T14:15:01Z

I don't think there is any compelling evidence that integer factorization can be done in polynomial time. It's true that polynomial factoring can be, but lots of things are much easier for polynomials than for integers, and I see no reason to believe these rings must always have the same computational complexity. (Strangely, if you do believe that, it means the shortest lattice vector problem should also be efficiently solvable, but it doesn't seem to tell you anything about discrete logarithms. This puzzles me, since the parallels between factoring and discrete logs are also strong.) It's also true that primality testing can be done in polynomial time, but that is a fundamentally different problem: when a modulus is prime, it has enormous consequences for modular arithmetic, and it is not difficult to test for primality by looking for those consequences, but the actual methods shed no light on factoring.

On the other hand, there is also no compelling evidence that factoring can't be done in polynomial time (see http://research.microsoft.com/~cohn/Thoughts/factoring.html for a little more detail about this).

At our current level of knowledge, I view the complexity of factoring as a matter of opinion, speculation, and wishful thinking, not principled arguments. By contrast, there are exceedingly good reasons why the Riemann hypothesis should be true, and good reasons why P shouldn't equal NP. I'm certainly open to arguments that fall far short of rigorous proof; I've just never heard a convincing one about the complexity of factoring.

My interpretation of Sarnak's belief isn't that he sees some good reasons other people don't appreciate. Rather, it just feels plausible to him, and he's perhaps a little annoyed that lots of people firmly believe the opposite for no good reason, so he makes a point of stating a strong opinion.

Answer by Henry Cohn for What items MUST appear on a mathematician's CV?

2011-10-26T15:56:17Z

From my perspective, the critical question isn't what must be included on your CV, but rather what mustn't, since that seems to be the more common problem (judging by the ones I see). What I'm about to describe is based on my experience at a U.S. research lab; I imagine it generalizes quite a bit beyond that, but I can't say how far, and it is certainly country-specific.

I'll discuss five rules below, with some overlap between them. Of course these rules are not absolute (except for the last one), but you certainly shouldn't break them without thinking carefully about it and deciding there's a good reason to do so.

(1) Your CV should represent you as a professional mathematician. Anything that is not relevant to your professional life should be left out. For example, you should generally not describe non-math-related summer or part-time jobs, hobbies, side interests outside of mathematics and related fields, etc. If there's something unusually interesting or impressive (you published a novel or are a chess champion) or that displays relevant skills (you write free software in your spare time), it's OK to mention it, but just briefly and not in a prominent position.

I've seen some hair-raising violations of this rule, in which applicants devoted considerable space to things that have nothing to do with working as a mathematician. Nobody is going to reject your application just because you put something weird in your CV, but it's not good for your image as a professional.

(2) Your CV shouldn't include anything unless you think the search committee might need or want to know it. For example, contact information is valuable, as is anything that can legitimately help judge your application. However, in the U.S. you should not list your age or birthdate, your marital status, information about your children, or your religion (unless you are applying to a religious institution). I realize this is common in some countries, and of course people will be understanding about that, but it comes across strangely to give people information they don't want and shouldn't be influenced by.

(3) You should try not to seem desperate to impress, particularly with awards and distinctions. Some people provide enormous lists of very minor distinctions, sometimes with no relevance to research/teaching/service (for example, a college scholarship from a local business club). Coming across as insecure can make you seem less attractive: an ambitious department wants to hire people who are marginally too good for them, not people who are trying hard to be good enough. As a rule of thumb, when you get your Ph.D. and apply for your first job, it's OK to list any substantive distinction from grad school. You can list a few undergraduate honors, but only if they are impressive (Putnam fellow or major university-wide prize, yes; random scholarship, no). You shouldn't list high school honors at all (well, just maybe an IMO medal, but be careful not to look like you consider it your proudest achievement).

(4) Be sure not to give the impression you are trying to obfuscate anything. I don't just mean you should tell the truth, but also that you should be clear and straightforward. For example, people sometimes feel bad about not having enough items to list in their publication or talk sections, and it can be tempting to reorganize the CV to try to obscure this. For example, you could replace the "publications" section with a "research" section in which you list not just publications but also talks and poster presentations, or even current/future research topics. This is a bad idea, since it can look like you are trying to make the information less accessible, and then everything on your CV will be looked at more skeptically. Instead, you want to make it easy to understand your CV and easy to see that you aren't doing anything tricky.

(5) Don't lie. Don't say a paper will appear in a journal until it has been accepted, even if you are sure it will be. Don't say a paper is submitted until it is, even if you plan to submit it by the time the committee meets. Don't call something a preprint until it is written down and ready to distribute (you can say "in preparation" before then, but many people will ignore this since it is unverifiable). Don't say you have received a fellowship or prize if you haven't. You'd think all these things go without saying, but I've seen a couple of people get caught on one of them. You really don't want to be the person who gets asked for a copy of their preprint and can't produce one.

Answer by Henry Cohn for Simple basis for Barnes-Wall lattices in dimension `$2^n$`

2011-10-24T00:43:49Z

Nebe, Rains, and Sloane have a beautiful paper called "A simple construction for the Barnes-Wall lattices" (http://www2.research.att.com/~njas/doc/bw.pdf). Their construction is great: consider two vectors of norm $2$ with inner product $\sqrt{2}$, and let $L$ be the $\mathbb{Z}[\sqrt{2}]$ lattice they span. Then up to scaling, the Barnes-Wall lattice of dimension $2^n$ is the sublattice of the $n$-th tensor power $L^{\otimes n}$ fixed by conjugation (i.e., fixed under interchanging $\sqrt{2}$ and $-\sqrt{2}$).

Slightly more explicitly, take $(\sqrt{2},0)$ and $(1,1)$ as a basis of $L$, and then the Barnes-Wall lattice is the intersection of $L^{\otimes n}$ with $\mathbb{Q}^{2^n}$.

Comment by Henry Cohn

2013-05-17T13:51:45Z

This is also the same problem as mathoverflow.net/questions/130897, which was asked and closed three hours earlier.

Comment by Henry Cohn

2013-05-17T03:52:00Z

The diagonal argument that fails is the explanation from pages 36-37 of Soare's book Recursively enumerable sets and degrees, right? I like that explanation, but I find the way Sipser approaches it in Introduction to the theory of computation even more compelling.

Comment by Henry Cohn

2013-05-16T00:57:30Z

@Steven Landsburg: For each fixed $n$ it is, but you can't quantify over $n$ in the first-order language of fields.

Comment by Henry Cohn

2013-05-14T20:39:52Z

I think the issue is what "structure" means. Loosely interpreted, all research on the Goldbach conjecture deals with the structure of a hypothetical non-Goldbach number, where existence/non-existence is considered the most basic structural property of all. Of course that doesn't sound like what you're looking for, but saying more requires pinning down what really counts as structure. I agree with Johan that the answer to your question is probably "no", and structure of specific numbers probably just isn't relevant. However, it's not clear whether we're talking about the same thing.

Comment by Henry Cohn

2013-05-14T18:25:33Z

I don't know of a name for this phenomenon, but it's true and follows from standard techniques. The reason it is off topic here is because mathoverflow is devoted to research mathematics, but you might get more information/explanation on math.stackexchange.com.

Comment by Henry Cohn

2013-05-14T00:25:05Z

The English translation was published in Soviet Math. Dokl. 11 (1970), 354–358. I don't know of an online version, but if it's not in your library you can ask a librarian how to get it by interlibrary loan.

Comment by Henry Cohn

2013-05-05T23:24:02Z

Regarding the 290-theorem, the proof is not accessible to undergraduates. (As written, it uses the Ramanujan conjecture for weight 2 cusp forms. There might be an undergraduate-accessible proof, but the one Bhargava and Hanke wrote up isn't it.) For the 15-theorem, I don't recall anything nearly as high-powered, so I think you could teach it to undergraduates, but you'd have to spend some time teaching them about genera of quadratic forms first.

Comment by Henry Cohn

2013-05-05T16:12:50Z

I can't think of anything so far that isn't shallow. Certainly given $H$ you can construct a $\pi$ for which you can find a permuted collision, and given any $\pi$ other than the identity you can modify $H$ (by composing it with another permutation) to produce a collision-resistant hash function that has a $\pi$-collision. So if $H$ or $\pi$ is chosen adversarially, you're in trouble. Presumably for most hash functions this works in practice if $H$ and $\pi$ are chosen independently in some sense, but I don't see how to formalize this offhand. For example, what if $\pi$ is chosen at random?

Comment by Henry Cohn

2013-05-04T02:29:05Z

It looks to me like this is exactly the same system studied by Varadharajan and Odoni.

Comment by Henry Cohn

2013-05-04T00:50:03Z

Mathoverflow is intended for research questions, so this question would be more appropriate for another site (see the FAQ list for suggestions).

Comment by Henry Cohn

2013-05-03T21:19:10Z

Irrationality proofs generally aren't useful in any practical sense, but they can certainly be enlightening.

Comment by Henry Cohn

2013-05-03T13:22:47Z

This question doesn't make sense as stated, since "nonnegative definite" and "Hermitian" aren't defined for a general field. (Even if your field is the complex numbers, do you want to assume $A$ and $B$ commute, so you can take $P$ to be unitary?) See mathoverflow.net/questions/118680 for information about which fields have the property that every symmetric matrix is diagonalizable.

Comment by Henry Cohn

2013-05-03T13:07:10Z

I'm not sure what you mean by "generally correct". Fitting simple functions to points in plots can work pretty well, but it depends on the circumstances. You can certainly come up with cases where it fails dramatically; how likely these sorts of cases are to arise in practice depends on where your problems are coming from. In any case, Mathoverflow is aimed at mathematical research, so this question would be more appropriate at math.stackexchange.com.

Comment by Henry Cohn

2013-05-03T13:00:18Z

P.S. Jordan also links to several survey papers in the navigation bar on the right.

Comment by Henry Cohn

2013-05-03T12:57:58Z

Of course it's easy to write down the answer as the integral of $\log(1+e^x)$ times the density of the distribution. This lets you compute to much greater precision than you can get by simulation, but offhand I don't see any reason to think the integral can be evaluated in closed form. I'd recommend asking about this at math.stackexchange.com instead.

User henry cohn - MathOverflow

Answer by Henry Cohn for Quantum algorithms for dummies

Answer by Henry Cohn for Which hard mathematical problems do you have to solve to earn bitcoins ?

Answer by Henry Cohn for Is there a "mathematical" definition of "simplify"?

Answer by Henry Cohn for Kissing Number of Spheres in Non-Euclidean Geometry

Answer by Henry Cohn for Attack on CRT-RSA

Answer by Henry Cohn for Role of statistical estimation in formal proof

Answer by Henry Cohn for Last term of repeating continued fraction expansion

Answer by Henry Cohn for How should an analytic number theorist look at Bessel functions?

Answer by Henry Cohn for Euler Mascheroni Constant, Curious?

Answer by Henry Cohn for Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

Answer by Henry Cohn for How fast can we *really* multiply matrices?

Answer by Henry Cohn for Are isospectral manifolds necessarily homeomorphic?

Answer by Henry Cohn for Do you use the Mathematics Subject Classification (MSC) when searching for literature?

Answer by Henry Cohn for The gimbal lock shows up in my quaternions

Answer by Henry Cohn for What is the largest possible thirteenth kissing sphere?

Integrability of the Cohen map

Answer by Henry Cohn for Cryptography and iterations

Answer by Henry Cohn for Mathematical modeling of voting/rating (e.g. political elections, questions on MO, gadgets on amazon,...)

Answer by Henry Cohn for Can ZFC prove "false theorems", and still be consistent? (was "Junk Theorems" follow up)

Answer by Henry Cohn for What would be some major consequences of the inconsistency of ZFC?

Answer by Henry Cohn for How to make the move to a research university from a liberal arts school?

Answer by Henry Cohn for When can a family of polynomials get a weight function to be made orthogonal?

Answer by Henry Cohn for polynomials and electrostatics

Answer by Henry Cohn for Delaunay triangulations and convex hulls

Answer by Henry Cohn for convex polytopes with many faces and edges but few cells and vertices

Answer by Henry Cohn for Enumerating Perfect Lattices

Answer by Henry Cohn for Minimize Energy for Charge Distributions

Answer by Henry Cohn for Evidence for integer factorization is in $P$

Answer by Henry Cohn for What items MUST appear on a mathematician's CV?

Answer by Henry Cohn for Simple basis for Barnes-Wall lattices in dimension `$2^n$`

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Comment by Henry Cohn

Answer by Henry Cohn for How fast can we really multiply matrices?