most recent 30 from http://mathoverflow.net 2013-05-22T22:41:29Z http://mathoverflow.net/feeds/user/3737 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22009/random-walk-anecdote Ross Snider 2010-04-21T03:17:26Z 2010-04-21T09:43:27Z

<p>I'm looking for an anecdote about a mathematician who studied random walks. I'm attempting to write an article and hope to include the story (but only if I can get the details correct). I'll try to do my best describing it in hopes someone else has heard it and knows a name or the full story.</p> <p>A mathematician was walking through the park and entertaining mathematical whims. He noticed that he kept running into this same couple as he wandered around aimlessly. He wasn't sure if this behaviour was expected by chance or whether perhaps the female of the couple thought that he was cute. He rushed home to analyse the situation in terms of random walks in two dimensions.</p>

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix Ross Snider 2010-03-18T06:02:39Z 2010-04-16T02:53:51Z

<p>I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore won't have a determinant. While it might also be interesting to ask what number of NxN (0,1)-matrices are singular or non-singular, I'd like to ignore singular matrices altogether in this question.<br><br> To get a better grasp on the problem I wrote a computer program to search for the values given an input N. The output is below:<br> 1x1: 2 possible determinants<br> 2x2: 3 ...<br> 3x3: 5 ...<br> 4x4: 9 ...<br> 5x5: 19 ...<br><br></p> <p>Because the program is simply designed to just a brute force over every possible matrix the computation time grows with respect to $O(2^{N^2})$. Computing 6x6 looks like it is going to take me close to a month and 7x7 is beyond hope without access to a cluster. I don't feel like this limited amount of output is enough to make a solid conjecture.</p> <p>I have a practical application in mind, but I'd also like to get the bounds to satiate my curiosity.</p>

http://mathoverflow.net/questions/19824/the-limits-of-parallelism/19863#19863 Ross Snider 2010-03-30T18:41:30Z 2010-03-30T18:41:30Z

<p>The general consensus here is that a problem can't be solved efficiently in parallel unless it can be solved efficiently by a single computer. Imagine instead of having n computers working on a problem for X time you gave one computer n*X time. Without factoring in the overhead of communication, you can get an n times speedup by using n processors.</p> <p>Since you are asking about an infinite number of processors, you're asking a question which is equivalent to what a single computer can compute if we don't concern ourselves with time at all. This question got its first few answers from Kleene, Godel, Turing and several other giants. We still don't know everything that a computer can and can not compute to this day - but we do know some things that can not be computed (like the Halting Problem) even with infinite parallel computation.</p> <p>For the record, if your limitation is infinite processors for an O(n!) problem, I could assign each of the processors to compute one single permutation each and have plenty of computers to spare [;-)]. What we're really interested in is knowing what's computable in an efficient amount of time <em>and</em> an efficient amount of physical resources.</p>

http://mathoverflow.net/questions/18893/analog-to-the-chinese-remainder-theorem-in-groups-other-than-z-n Ross Snider 2010-03-21T01:49:19Z 2010-03-21T17:47:42Z

<p>The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise coprime. Applications of this Chinese Remainder Theorem not only include computational speedups (in the case of decryption in RSA) but also stronger cryptographic attacks against $Z_n$ (for example, Pollard Rho factoring exploits this structure). Can we extend these applications into other areas? (Admittedly I don't know many computationaly examples where this could be useful, but can imagine that Mathematica/Maple would find some uses).<br><br></p> <p>So the real question: is this property just a "coincidence" or are there analogs in other groups? If there are, is there some group theory analog that applies equally well to every group? If there are not, what underlying structure in the natural numbers makes this possible?</p>

http://mathoverflow.net/questions/15238/how-to-estimate-the-growth-of-a-recurrence-sequence/15245#15245 Ross Snider 2010-02-14T08:38:41Z 2010-02-14T08:38:41Z

<p>I believe you can create two new recurrence sequences each of whose generating function is known which bound the sequence in question tightly. That gives a really good idea of the growth.</p>

http://mathoverflow.net/questions/13919/finding-the-base-of-exponentiation-subject-to-range-constraints Ross Snider 2010-02-03T03:18:20Z 2010-02-03T06:14:59Z

<p>Given a vector of real numbers $a_0, a_1, ... a_n$ where $a_i > 1$ for all $i$, find an $n \in \mathbb{R}$ where $n > 1$ such that $t_i = n^{a_i}$ and $t_i \in \mathbb{N}$ for every $i$. Trivially, $n = 0$ and $n = 1$ will always work but do not apply to my application, and are part of the reason for the $n > 1$ constraint. I am only hopeful that there will be an $n$ for every set of real numbers $a_0, a_1, ... a_n$, but have no good reason to believe that this is necessarily the case. I would be interested in knowing a method to find the smallest number $n$ that meets these criteria, but would be satisfied to find just any.</p> <p>What general field of mathematics studies problems like this? What methods are typically employed to get an answer? <em>Does</em> every vector admit a solution $n$?</p>

http://mathoverflow.net/questions/40337/ingenuity-in-mathematics/40344#40344 Ross Snider 2010-11-30T17:34:44Z 2010-11-30T17:34:44Z

I barely ever log into this stack exchange; I just browse. But the low score on this answer bugged me. It's a fantastic answer. I roomed with an art major my second and third year of college. He is particularly bright and very multi-talented individual but not trained in mathematics to any capacity. He understood Cantor's Diagonalization easily and declared, &quot;Ross, you just blew my mind!&quot; (as though the proof were my own.) Douglas Hofstadter provides a really simple explanation of all three of these suggestions. I might suggest skipping (the proof of) Godel's Incompleteness Thm., though.

http://mathoverflow.net/questions/22009/random-walk-anecdote/22034#22034 Ross Snider 2010-04-21T13:43:48Z 2010-04-21T13:43:48Z

Ahh, in fact I do plan to use this in the article (I already knew the quote and its author). The article is about the number three and where it shows up as a transition point to more interesting and complex behavior. You know, like the 3-body problem, 3-dimension random walks, 3-colorings of planar maps, 3-SAT and NP-Completeness, FLT, or 3 bubble conjecture. I would post on MO for more but I have a suspicion the question would not be received well. As for this answer, it isn't quite an anecdote, although fantastic nevertheless.

http://mathoverflow.net/questions/22009/random-walk-anecdote/22010#22010 Ross Snider 2010-04-21T04:55:05Z 2010-04-21T04:55:05Z

Thank you. This is exactly what I was looking for.

http://mathoverflow.net/questions/19824/the-limits-of-parallelism/19863#19863 Ross Snider 2010-03-31T20:15:23Z 2010-03-31T20:15:23Z

While each state of the evolving system might be computed in parallel, physical systems can only be computed in parallel and the amount of time it takes for the electron calculations in the antiferromagnet to settle take time exponential in the base (as would be expected). Of course this doesn't count as a proof until we are certain that physics computations DO require serial computations. Right now we only have good reason to believe.

http://mathoverflow.net/questions/19824/the-limits-of-parallelism/19863#19863 Ross Snider 2010-03-31T20:15:20Z 2010-03-31T20:15:20Z

Oh okay. I misunderstood. I have an anecdotal example then... physical calculations can be done in parallel but only to a certain extent. Each &quot;state&quot; of a physical system depends on the full configuration of the previous state. There is a way to encode the partition problem (NP-Complete) into a physics calculation of electron spins in an infinite-range antiferromagnet [due to Stephan Mertens].

http://mathoverflow.net/questions/18893/analog-to-the-chinese-remainder-theorem-in-groups-other-than-z-n Ross Snider 2010-03-21T16:43:17Z 2010-03-21T16:43:17Z

I apologize for the question. I wasn't just looking for just cryptographic applications. I was really interested in whether CRT was a curiousity related to the integers or whether there was something more profound going on. As some comments pointed out this information was on Wikipedia and that I had missed it.

http://mathoverflow.net/questions/18893/analog-to-the-chinese-remainder-theorem-in-groups-other-than-z-n/18913#18913 Ross Snider 2010-03-21T16:40:51Z 2010-03-21T16:40:51Z

This is really interesting. It's a shame I can't accept two answers.

http://mathoverflow.net/questions/18893/analog-to-the-chinese-remainder-theorem-in-groups-other-than-z-n/18894#18894 Ross Snider 2010-03-21T02:03:03Z 2010-03-21T02:03:03Z

Thanks, I removed &quot;simple&quot; from the question. I figured this was legit and interesting enough for research mathematicians, but I could be mistaken. If I am, I apologize in advance.

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix/18554#18554 Ross Snider 2010-03-19T15:52:58Z 2010-03-19T15:52:58Z

I am accepting this answer because it provides an interesting lower bound, even if you haven't proved it rigorously here, and because it seems like the flurry of activity on this question has died out.

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix/18554#18554 Ross Snider 2010-03-18T18:40:52Z 2010-03-18T18:40:52Z

The application isn't fully fleshed out. I was looking into the growth of the number of determinants to see asymptotic behaviour. I am looking to see if comparing determinants of adjacency matrices of simple graphs (after being processed by various transforms) can be used to solve the isomorphism problem probabilistically. I just started looking into the idea - no great progress or insight to be had yet.

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix Ross Snider 2010-03-18T18:36:40Z 2010-03-18T18:36:40Z

Ahh, yes there seems to be a small problem with the determinant calculating code. I grabbed a determinant function that works with libboost online. Should have checked it for accuracy in all cases.

http://mathoverflow.net/questions/13919/finding-the-base-of-exponentiation-subject-to-range-constraints Ross Snider 2010-02-03T03:57:04Z 2010-02-03T03:57:04Z

This is a shame. Thank you for relieving my night of an exhaustive search bound to fail.