User mra - MathOverflow

Theorem versus Proposition

2010-03-16T10:23:54Z

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'.

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.

So, my question is: When to use 'Theorem' and when to use 'Proposition' in a paper?

Answer by MRA for Finding all paths on undirected graph

2010-03-19T12:44:47Z

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 total number of all paths leading from u to v (or, in fact, from any start node to any destination):

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 u to v. 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 w adjacent to v. Hence, $M_i[u,v]$ containes the number of simple paths of length at most i from u to v. 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.

Answer by MRA for What are the worst notations, in your opinion ?

2010-03-18T17:06:55Z

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.

Answer by MRA for Primes p for which p - 1 has a large prime factor

2010-02-10T00:22:54Z

John A. Gordon introduced the notion of strong primes (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:

John A. Gordon: "Strong Primes Are Easy to Find", Proceedings of EUROCRYPT '84, LNCS 209, Springer, 1985.

Comment by MRA

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.

Comment by MRA

2010-03-19T16:53:22Z

@rgig: Ok, I see. But wouldn't you then loose the "time linear in the total length of all the output paths" 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$.

Comment by MRA

2010-03-19T13:26:15Z

Ok, this does not seem to work. See the post by Sangxia Huang.

Comment by MRA

2010-03-19T13:23:05Z

I agree. Thanks for pointing out the flaw.

Comment by MRA

2010-03-19T12:50:40Z

@Suresh: Are you sure a DFS will find all 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.

Comment by MRA

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.

Comment by MRA

2010-03-17T09:47:21Z

In fact, in German I would use "Satz" for a minor theorem and "Theorem" for a major, fundamental theorem. However, I think it will be regarded as hubris to call a theorem of your own a "Theorem".