User erick wong - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:47:13Z http://mathoverflow.net/feeds/user/23373 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119678/sorting-two-paired-lists-of-real-numbers-to-minimize-consecutive-absolute-differe/119697#119697 Answer by Erick Wong for sorting two paired lists of real numbers to minimize consecutive absolute differences Erick Wong 2013-01-23T21:47:37Z 2013-01-23T21:47:37Z <p>This is known in complexity circles as rectilinear TSP. Technically this is a path version TSP rather than the more common tour. In any of these specific settings, this is known to be NP-complete since the 70s (see <a href="http://www.sciencedirect.com/science/article/pii/0304397577900123" rel="nofollow">Papadimitriou's paper</a>).</p> <p>However, unlike some NP-hard problems, Euclidean and rectilinear TSP admit a polynomial-time approximation scheme: one can obtain a tour of cost at most $(1+\epsilon)$ times optimal in time $O(n (\log n)^{O(1/\epsilon)})$. See <a href="http://www.cs.princeton.edu/~arora/publist.html" rel="nofollow">Arora's web page</a> for some of the key papers on this subject. You'll also find there a nice survey on approximation results (<a href="http://www.cs.princeton.edu/~arora/pubs/arorageo.ps" rel="nofollow">postscript link</a>), outlining the key ideas.</p> <p>The survey mentions a subexponential $2^{O(\sqrt{n})}$ exact algorithm for the Euclidean case by Smith (1988). While I would not be surprised if it adapts readily to $L^1$, I don't know enough about it to say for certain.</p> http://mathoverflow.net/questions/100033/interesting-mathematical-documentaries/100431#100431 Answer by Erick Wong for Interesting mathematical documentaries Erick Wong 2012-06-23T08:33:10Z 2012-06-23T08:33:10Z <p>The <a href="http://www.geom.uiuc.edu/video/" rel="nofollow">Geometry Center</a> (formerly of UMN, now apparently defunct) many years ago produced "<a href="http://www.geom.uiuc.edu/video/NotKnot/" rel="nofollow">Not Knot</a>" (about hyperbolic space) and "<a href="http://www.geom.uiuc.edu/docs/outreach/oi/" rel="nofollow">Outside In</a>" (about sphere eversion). There is apparently a more recent third one "The Shape of Space" I'm not familiar with. Apparently you can still order them <a href="http://www.geom.uiuc.edu/video/AKPeters.html" rel="nofollow">here</a>, although copies are now easily found on YouTube.</p> http://mathoverflow.net/questions/99411/sequence-of-permutations-without-a-fixed-point/99412#99412 Answer by Erick Wong for Sequence of permutations without a fixed point Erick Wong 2012-06-13T08:34:23Z 2012-06-13T08:34:23Z <p>Of course such permutations exist if $n > m$ (just take each $A_i$ to be the same $n$-cycle). On the other hand if $m \le n$, a pigeonhole argument should give some pair of $A_1, A_1 A_2, A_1A_2A_3, \ldots$ mapping element $1$ to the same element, inducing a fixed point in the quotient of this pair. Are you sure this question is well-posed?</p> http://mathoverflow.net/questions/99290/are-there-infinite-primes-among-powerful-order-terms-of-dirichlet-arithmetic-prog/99324#99324 Answer by Erick Wong for Are there infinite primes among powerful order terms of Dirichlet arithmetic progressions? Erick Wong 2012-06-11T23:36:46Z 2012-06-12T07:20:46Z <p>I'm sorry this isn't much of an answer, but you might be interested in this <a href="http://www.math.ualberta.ca/~subbarao/documents/Subbarao8.pdf" rel="nofollow">paper</a> of De Koninck, Kátai and Subbarao. Your conjecture is almost strong enough to mean that for any squarefree $a$, there are infinitely many primes $p$ where the squarefree part of $p-d$ is exactly $a$ (the difference being that you do not require $(a,mn)=1$).</p> <p>Section 4 in the cited paper establishes a sort of converse formulation: for any powerful $K$, there are infinitely many primes $p$ where the powerful part of $p-1$ is exactly $K$ (with the expected asymptotics). Of course this is a far denser set in which to look for primes, so this is certainly a much easier problem. Presumably no significant complications arise if we shift this by $d$ rather than $1$.</p> http://mathoverflow.net/questions/120436/representations-with-triangular-numbers Comment by Erick Wong Erick Wong 2013-01-31T18:43:11Z 2013-01-31T18:43:11Z I'm embarrassed to ask, but why am I unable to edit or delete the malformatted comment above? http://mathoverflow.net/questions/120436/representations-with-triangular-numbers Comment by Erick Wong Erick Wong 2013-01-31T18:38:33Z 2013-01-31T18:38:33Z @bn Not quite. $a_1$ will be about $\sqrt{2n}$ not $\sqrt{n}, and similarly for each of the remaining terms. This introduces a multiplicative error as large as$2^{O(\log \log n)}$which is certainly not$O(1)$. http://mathoverflow.net/questions/119786/is-every-positive-multiple-of-6-the-sum-of-two-primes/119787#119787 Comment by Erick Wong Erick Wong 2013-01-25T03:17:55Z 2013-01-25T03:17:55Z @Will Sawin: Less than one year ago, Harald Helfgott uploaded a paper on [arXiv](<a href="http://arxiv.org/abs/1205.5252" rel="nofollow">arxiv.org/abs/1205.5252</a>) with significant technical improvements in estimating the minor arcs of$\sum e(\alpha p)$. The abstract suggests there is only a modest gap between what is known computationally (by very recent work of David Platt) and what is needed to verify ternary Goldbach. I do not know if this has been pursued further. http://mathoverflow.net/questions/118789/proving-a-determinant-0 Comment by Erick Wong Erick Wong 2013-01-15T04:29:33Z 2013-01-15T04:29:33Z @wccanard I agree that (C), taken only as a sufficient condition for$\det A = 0$, doesn't need a name. But Frobenius-K&#246;nig also yields a partial converse, that any configuration of zeros which guarantees a zero determinant necessarily contains this form (at least when working over a large enough field). http://mathoverflow.net/questions/118789/proving-a-determinant-0 Comment by Erick Wong Erick Wong 2013-01-13T08:47:52Z 2013-01-13T08:47:52Z The answer to your minor question is the Frobenius-K&#246;nig theorem. http://mathoverflow.net/questions/102964/convergence-of-moments-implies-convergence-to-normal-distribution Comment by Erick Wong Erick Wong 2012-07-31T04:09:15Z 2012-07-31T04:09:15Z @Igor's link has the same typo. Third time's a [charm](<a href="http://en.wikipedia.org/wiki/Method_of_moments_(probability_theory%29" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a>)? http://mathoverflow.net/questions/102907/automorphisms-of-a-certain-digraph-defined-on-the-set-of-primes-edited/102911#102911 Comment by Erick Wong Erick Wong 2012-07-23T07:25:12Z 2012-07-23T07:25:12Z @David The same heuristic does suggest infinitely many primes of the form$2^m 3^n + 1$, though. These are called Pierpont primes. http://mathoverflow.net/questions/99290/are-there-infinite-primes-among-powerful-order-terms-of-dirichlet-arithmetic-prog/99324#99324 Comment by Erick Wong Erick Wong 2012-06-16T05:42:07Z 2012-06-16T05:42:07Z @Fernando: That is truly nice to hear! I do agree with your interpretation, and I hope you are able to make good use of this result. I'll be interested to see your paper when it is ready. http://mathoverflow.net/questions/99724/central-numbers-and-de-polignacs-conjecture Comment by Erick Wong Erick Wong 2012-06-15T20:25:49Z 2012-06-15T20:25:49Z It follows from a result of Shiu (2000) &quot;Strings of congruent primes&quot; that there are arbitrarily long runs of consecutive primes congruent to a mod q. Taking q to have many small prime factors, this gives infinitely many central numbers of type &gt;k for any k. Can this be sharpened to give exact type k? http://mathoverflow.net/questions/70347/successive-nth-powers-mod-p/70483#70483 Comment by Erick Wong Erick Wong 2012-06-15T00:25:45Z 2012-06-15T00:25:45Z This argument is fixable for prime$n$(granted, the Weil bound is much stronger). First, look for a progression of length$Ck$where$C$is a very large parameter (something like$n^O(nk)$). Suppose the AP you construct has$h$which is not a$n$th power: we try to pass to a subprogression with difference$dh$, where$d \le C$. If no$d \le C$makes$dh$a$n$th power, there can't be many values of$d \le nk$that are not$n$th powers (otherwise some product of these must work). But the alternative is that there are so many small$n$th powers that some$k\$ must be consecutive.