User mra - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T11:48:58Z http://mathoverflow.net/feeds/user/3919 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18352/theorem-versus-proposition Theorem versus Proposition MRA 2010-03-16T10:23:54Z 2013-02-24T21:31:02Z <p>As a non-native English speaker (and writer) I always had the problem of understanding the distinction between a 'Theorem' and a 'Proposition'. When writing papers, I tend to name only the main result(s) 'Theorem', any auxiliary result leading to this Theorem a 'Lemma' (and, sometimes, small observations that are necessary to prove a Lemma are labeled as 'Claim'). I avoid using the term 'Proposition'.</p> <p>However, sometimes a paper consists of a number important results (which by all means earn to be called 'Theorem') that are combined to obtain a certain main result. Hence, another term such as 'Proposition' might come in handy, yet I don't know whether it suits either the main or the intermediate results.</p> <p>So, my question is: When to use 'Theorem' and when to use 'Proposition' in a paper?</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18732#18732 Answer by MRA for Finding all paths on undirected graph MRA 2010-03-19T12:44:47Z 2010-03-19T12:44:47Z <p>If I'm not mistaken, I think an adaptation of a dynamic programming all-pairs-shortest-path algorithm (like the Floyd-Warshall algorithm, considering edge weights of 1) might find all paths. Consider the following scheme to find the <em>total number</em> of all paths leading from <em>u</em> to <em>v</em> (or, in fact, from any start node to any destination):</p> <p>A matrix $M_1$ is initialized as the adjacency matrix of the graph. That is, $M_1[u,v]$ containes the number of simple paths of length at most 1 from <em>u</em> to <em>v</em>. After that, for all $i$ from 2 to the number of nodes the matrix $M_i$ is updated as follows: $M_i[u,v]$ equals the sum of the entries $M_{i-1}[u,w]$ for all nodes <em>w</em> adjacent to <em>v</em>. Hence, $M_i[u,v]$ containes the number of simple paths of length at most <em>i</em> from <em>u</em> to <em>v</em>. This scheme runs in time polynomial in the input size, and it can also be modified easily to also store the actual paths in time (and space) polynomial in the output size.</p> http://mathoverflow.net/questions/18593/what-are-the-worst-notations-in-your-opinion/18629#18629 Answer by MRA for What are the worst notations, in your opinion ? MRA 2010-03-18T17:06:55Z 2010-03-18T19:13:23Z <p>Physicist will hate me for this, but I never liked Einstein's summation convention, nor the famous bra ($\langle\phi|$) and ket ($|\psi\rangle$) notation. Both notations make easy things look unnecessarily complicated, and especially the bra-ket notation is no fun to use in LaTeX.</p> http://mathoverflow.net/questions/14796/primes-p-for-which-p-1-has-a-large-prime-factor/14833#14833 Answer by MRA for Primes p for which p - 1 has a large prime factor MRA 2010-02-10T00:22:54Z 2010-02-10T00:22:54Z <p>John A. Gordon introduced the notion of <em>strong primes</em> (try Wikipedia) which, beside other requirements, are primes $p$ satisfying $p \equiv 1 \mod r$ for some large prime $r$ of about the same size as $p$. In the following paper, it has been shown how to construct strong primes of arbitrary bit size efficiently and with high probability:</p> <ul> <li>John A. Gordon: <a href="http://link.springer.de/link/service/series/0558/bibs/0209/02090216.htm" rel="nofollow">"Strong Primes Are Easy to Find"</a>, Proceedings of EUROCRYPT '84, LNCS 209, Springer, 1985.</li> </ul> http://mathoverflow.net/questions/33046/arent-oracle-machines-unsound-concepts/33064#33064 Comment by MRA MRA 2010-07-23T08:45:45Z 2010-07-23T08:45:45Z If I understand correctly, there is no problem with using undecidable languages like the halting problem H as oracles. Using an H oracle introduces a new halting problem, i.e., a halting problem for TMs using an H oracle. This eventually leads to the notion of the arithmetical hierarchy. http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph Comment by MRA MRA 2010-03-19T16:53:22Z 2010-03-19T16:53:22Z @rgig: Ok, I see. But wouldn't you then loose the &quot;time linear in the total length of all the output paths&quot; property Suresh aims for? Consider the following counterexample: The graph consists of $n+1$ nodes, more precisely, a $K_n$ containing the start node, and the single target node which is only adjacent to the start node. Then the number (and length) of all output paths is 1, while the backtracking has to search through all the exponentially many paths within the $K_n$. http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18732#18732 Comment by MRA MRA 2010-03-19T13:26:15Z 2010-03-19T13:26:15Z Ok, this does not seem to work. See the post by Sangxia Huang. http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18738#18738 Comment by MRA MRA 2010-03-19T13:23:05Z 2010-03-19T13:23:05Z I agree. Thanks for pointing out the flaw. http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph Comment by MRA MRA 2010-03-19T12:50:40Z 2010-03-19T12:50:40Z @Suresh: Are you sure a DFS will find <i>all</i> paths? Asssume two $K_n$ connected by a single bridge edge, with the source node in one $K_n$ and the target node in the other. DFS will traverse the bride edge exactly once, while there is certainly a much larger number of distinct paths from source to target that are crossing this edge. http://mathoverflow.net/questions/18593/what-are-the-worst-notations-in-your-opinion/18611#18611 Comment by MRA MRA 2010-03-18T17:01:18Z 2010-03-18T17:01:18Z Please don't confuse the residue-class ring ${\mathbb Z}_q$ (aka ${\mathbb Z}/q{\mathbb Z}$) with a Galois field of $q$ elements, conveniently denoted by ${\mathbb F}_q$ (or $GF(q)$). It is one of the most popular fallacies of our students to assume that both symbols denote the same mathematical object, even if $q$ is not a prime. http://mathoverflow.net/questions/18352/theorem-versus-proposition/18409#18409 Comment by MRA MRA 2010-03-17T09:47:21Z 2010-03-17T09:47:21Z In fact, in German I would use &quot;Satz&quot; for a minor theorem and &quot;Theorem&quot; for a major, fundamental theorem. However, I think it will be regarded as hubris to call a theorem of your own a &quot;Theorem&quot;.