most recent 30 from http://mathoverflow.net 2013-05-18T10:44:55Z http://mathoverflow.net/feeds/user/3237 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14057/convert-a-confusion-matrix-to-a-distance-covariance-matrix Mitch Harris 2010-02-03T21:19:49Z 2012-09-27T09:25:53Z

<p>Suppose I have a confusion matrix $A$ for a set of points: entry $i,j$ is the fraction of time over all $j$ (and similarly over all $i$) that when $i$ is present then $j$ is recognized (This means doubly stochastic. I don't think there are any other mathematical restrictions.).</p> <p>This setup (from psychometric data about stimuli that are miscoded) leads one to think of a subset that has elements that are mutually more confusable within the subset than between pairs of elements where one is inside and the other outside the subset.</p> <p>This is vaguely reminiscent of a distance (or covariance) matrix where a subset may have mutually small distances but distances outside the subset are larger. </p> <p>Except, among other substantive mathematical differences, a distance/covariance matrix is symmetric but a confusion matrix is in general not.</p> <p>Is there a 'meaningful' (coherent, not totally crazy) mapping from a doubly stochastic matrix to a distance matrix? That somehow preserves a vague notion of clustering?</p> <p>This is the application motivation for the question in <a href="http://mathoverflow.net/questions/13987/distance-measure-on-weighted-directed-graphs" rel="nofollow">Distance measure on weighted directed graphs</a>. I think they are separable questions, but they can inform each other.</p>

http://mathoverflow.net/questions/51989/equational-logic/52103#52103 Mitch Harris 2011-01-14T18:38:35Z 2011-01-14T18:38:35Z

<p>Look up:</p> <ul> <li>Term Rewriting systems and Knuth-Bendix completion</li> <li>theory of equations and solving systems of multivariate polynomials (Groebner Bases)</li> </ul> <p>Though the latter subject, solving systems of equations over more concrete domains like fields, sounds very different from the purely syntactic manipulation in rewrite systems, the similarities are very astounding.</p>

http://mathoverflow.net/questions/51698/is-finitism-an-extreme-form-of-constructivism/51731#51731 Mitch Harris 2011-01-11T03:50:16Z 2011-01-11T03:50:16Z

<p>There are two kinds of thinking in foundations/reverse mathematics that could be called finitism. </p> <p>One is Hilbert's program, which is associated with finitistic reasoning (proofs themselves are finite even though infinite objects may be allowed). </p> <p>Another is a subset of PA which allows only finite objects, as in bounded arithmetic where all variables are implicitly bounded, which is often associated with constructivism. </p> <p>Though the second concept is not necessarily a strict subset of contructivism (itself a term that is not particularly strict), I feel that the term 'finitism' usually refers to the restriction to finite objects.</p>

http://mathoverflow.net/questions/51132/algorithm-for-summing-certain-sums-involving-the-floor-function/51150#51150 Mitch Harris 2011-01-04T19:16:11Z 2011-01-04T19:16:11Z

<p>General hints to generalization:</p> <ul> <li>don't generalize too many things at once (e.g. just stick with $k_0 = 0$ for now as noted)</li> <li>start with trying to solve with small nontrivial constants, e.g. $k_1 = 2$. That'll probably be complex enough.</li> </ul> <p>Specific hints to this problem</p> <ul> <li>let $N = Q-1$ or $N = m Q - 1$. By the link you gave, all sorts of things are easier (telescoping, switching quantifiers, fewer 'inscrutables') when you go complete cycles.</li> </ul>

http://mathoverflow.net/questions/42298/the-use-of-the-word-model-in-mathematical-logic-vs-the-same-word-in-natural-sci/42397#42397 Mitch Harris 2010-10-16T18:42:59Z 2010-10-16T18:42:59Z

<ul> <li><p>yes, it is strange, because one expects words to have similar meaning even in different contexts (but as others have noted, whether this is strange or not, there are all sorts of words that have multiple meanings, and even contradictory ones).</p></li> <li><p>yes, I agree in your assessment of how model has two, not contradictory, just oppositely directed meanings. In common language, natural sciences, and statistics, a model is an abstraction, where incidental details are removed, leaving just the bare bones abstract thing of what you care about (a model airplane, a model of population dispersal, a regression model predicting a value from a small set of variables). In mathematical logic, it is the other way around; a model is an -example- of the syntactically presented axioms (the permutations of 3 items is a model of the group axioms, a valuation (an assignment of boolean values) is a model for a propositional statement.</p></li> </ul> <p>In short, in mathematical logic, there is the abstract theory that has a model as an example, the model fits the theory. In the rest, the model -is- the theory and the phenomena of the world are the examples (which the theory/model are trying to fit).</p> <p>When this divergence of use started and by who, I can't say. But the logical use is certainly later. Who first started using the concept (but not necessarily the usage) in logic? Was it Goedel? How about Hilbert in 'Foundations of Geometry' where he shows independence of individual axioms by giving different models satisfying the rest (i don't know what terms he uses in the original or if they were common usage at that time for the concept).</p>

http://mathoverflow.net/questions/38278/enumerative-algorithm-through-inclusion-exclusion/38312#38312 Mitch Harris 2010-09-10T14:21:02Z 2010-09-10T14:21:02Z

<p>Consider the smallest nontrivial inclusion-exclusion situation:</p> <p>$$|A \cup B| = |A| + |B| - |A \cap B|$$</p> <p>(removing one set of the double counting of $A\cap B$).</p> <p>In the species interpretation, </p> <p>$$A \cup B = A \oplus B - A \cap B$$</p> <p>the $\oplus$ corresponds to disjoint union, but there is no accepted intepretation of $-$ (yes, it is the complement, but there is no systematic way to say which items are being removed.</p> <p>But one can transform the above equation using grade school arithmetic to get a reasonable correspondence:</p> <p>$$A \cup B \oplus A \cap B= A \oplus B$$</p> <p>Form an isomorphism from one side to the other. Then generate and test, that is, assuming you want $A \cup B$, generate $A \oplus B$ sequentially (by unranking, Gray code, whatever), then check if in $A \cap B$ (use a ranking procedure and the isomorphism) and repeatedly try the next one if a member (this is the exclusion step).</p> <p>Of course, this is not as clean as what one would want (a 'direct' construction of only those items wanted. Also, if the desired set is small or the overlapping is complicated, then lots will need to be excluded and so lots will need to be excluded before reaching the next one. However, you don't need to keep around a list of 'items so far' or ' items to avoid' as long as you have a mapping function (the isomorphism) between the two sides and needed ranking/unranking procedures.</p>

http://mathoverflow.net/questions/36471/facts-from-algebraic-geometry-that-are-useful-to-non-algebraic-geometers/36573#36573 Mitch Harris 2010-08-24T17:53:37Z 2010-08-24T17:53:37Z

<p>Grobner basis calculation is very practical for engineering, but also theoretically, in combinatorics (e.g. to prove colorability of given graph classes) and theoretical computer science (e.g. for polynomial interpretations to prove termination of programs).</p>

http://mathoverflow.net/questions/36532/is-there-a-simple-inductive-procedure-for-generating-labeled-trees-uniformly-at-r/36571#36571 Mitch Harris 2010-08-24T17:42:31Z 2010-08-24T17:42:31Z

<p>I think what you're asking for is a uniform random distribution of trees on $n$ nodes, and not really a (randomizing) function from trees to trees. Consider permutations: does it matter whether you take a given permutation and perturb it, or if you just generate a random permutation.</p> <p>That said, I see no need to use direct graph manipulation. Just generate a sequence of $n-2$ integers from ${1..n}$ (i.e. a uniformly random Prüfer sequence) and then make a tree out of it. Here you have the generation algorithm and proof immediately. For a perturbing algorithm you'd have to show that you perturbation will result in any possible tree with equal probability.</p>

http://mathoverflow.net/questions/32923/how-do-proof-verifiers-work/32983#32983 Mitch Harris 2010-07-22T17:49:04Z 2010-07-22T17:49:04Z

<p>You said: <Blockquote> The Wikipedia pages on <em>blah blah blah</em> give some idea, but these pages contain limited/unclear information, and there are rather few specific high-level resources elsewhere.</blockquote></p> <p>Wikipedia is great for subjects you know nothing about, but if you actually know something, all you see is incoherence, misdirection, and sometimes, when lucky, actual errors.</p> <p>As to actual proof verifiers, it's just the case that each verifier has a different philosophy and different mechanism behind it (there is no one foundation that they all use). So it is difficult to answer your questions (the answer itself will be too broad).</p> <p>A comment though: category theory itself is not really a foundation for proof verification. It is definitely a conceptual foundation for mathematics in that it creates analogies (and analogies of analogies) -formally- between different domains of mathematics. However there is the subdiscipline of category theory called topos theory which -does- purport to be an alternative foundation (when 'foundation' is intended to be about provability). To bounce back and forth...I don't think there is a verifier based on topos theory.</p>

http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order/32581#32581 Mitch Harris 2010-07-20T02:57:40Z 2010-07-20T02:57:40Z

<p>See:</p> <p>Combinatorial algorithms: an update, Herbert S. Wilf, Albert Nijenhuis SIAM, 1989. Chapter 8: Generating Random Graphs.</p> <p>The chapter gives an algorithm for producing an undirected graph uniformly over all graphs of size $n$. It is based on Polya counting. Computing the enumerating polynomial depends on some group theory that is time consuming (I don't know the complexity class, but I'll just conjecture it is most likely exponential space on $n$). But it is a guarantee of uniform distribution. Unfortunately I don't know of a way (I haven't heard of a way) to derandomize this to create an unranking algorithm (to give a mapping from the naturals to the set of unlabeled graphs). </p> <p>The algorithm presented in your link (by de Wet) is cute (I mean that in the sense that it is cleverly simple, does not lie, but doesn't really give the meat of it, what it means to have a list of non-isomorphic graphs). The graphs created there have a very particular structure (two paths with an arbitrary subset of edges between the paths, plus some small widgets on one end of each path to break symmetry. All subsets is a good trick but having two paths is pretty uncommon and $\sqrt{T_n}\over T_n$ goes to 0 as $n$ grows.</p> <p>As to practicality, in addition to the suggestions of nauty and Sage, there's also Mathematica (commercial) which has a list (that you can manipulate) of graphs up to size 11. </p>

http://mathoverflow.net/questions/32442/how-to-generate-a-net-on-a-8-dimensional-sphere/32513#32513 Mitch Harris 2010-07-19T16:56:03Z 2010-07-19T16:56:03Z

<p>Forgetting Matlab, the 'best' way to...hold on, do you mean -in- the sphere or -on- the sphere?</p> <p>For -in- the sphere, create 8-tuples where each element is from the uniform distribution from 0 to 1. Ignore those tuples whose Euclidean norm $\sqrt{\sum x_i^2} $ is greater than 1. Do this until you have $3^{10}$ points. This is a uniform distribution over the sphere.</p> <p>For -on- the sphere, create 8-tuples as before, but then divide each point by the norm (of course throw out $\langle 0,0,0,0,0,0,0,0\rangle$ ). This will place a point on the surface. Do this $3^{10}$ times. This is not an exact uniform distribution but is a very good approximation to one, and is very easy to do.</p>

http://mathoverflow.net/questions/13987/distance-measure-on-weighted-directed-graphs Mitch Harris 2010-02-03T15:53:51Z 2010-02-03T18:10:36Z

<p>There is a simple and well-defined distance measure on weighted undirected graphs, namely the least sum of edge weights on any (simple) path between two vertices.</p> <p>Can one devise a meaningful distance metric for weighted <i>directed</i> graphs? (assume non-negative weights and that the distance must be symmetric and have the triangular property)</p>

http://mathoverflow.net/questions/19325/most-striking-applications-of-category-theory/103334#103334 Mitch Harris 2012-07-30T15:25:44Z 2012-07-30T15:25:44Z

This would be an excellent example if only it were followed up with some detail and references.

http://mathoverflow.net/questions/54068/laser-paradox-a-dot-restricted-to-moving-across-an-infinite-plane Mitch Harris 2011-02-02T15:02:32Z 2011-02-02T15:02:32Z

This is an excellent question...but not for mathoverflow (which is for research level mathematics). The mathematical difficulties you discuss are not at the forefront of mathematics nowadays. Please re-ask this at <a href="http://math.stackexchange.com/" rel="nofollow">math.stackexchange.com</a>

http://mathoverflow.net/questions/53884/can-a-polynomial-size-cfg-describe-the-finite-language-w-piw-piw-is Mitch Harris 2011-01-31T16:22:44Z 2011-01-31T16:22:44Z

polynomial size in what? $n$? And is $n$ encoded in binary? It seems the CNF grammar is what you're seeking given the permutation $\pi$ and the length of the strings $n$.

http://mathoverflow.net/questions/53498/nontrivial-circular-arguments Mitch Harris 2011-01-27T18:13:28Z 2011-01-27T18:13:28Z

Every circular proof is also a proof of equivalence. That is, the unsatisfying circular proof, using an assumption that ends up depending on the thing to be proved, is also a proof the assumption is equivalent to the conclusion (they both imply each other). The hard part is to extract from the disappointment the bidirection or circle of implication.

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51233#51233 Mitch Harris 2011-01-05T19:30:07Z 2011-01-05T19:30:07Z

Computer architecture (a la Patterson and Hennessey) as interesting and useful and having mathematical underpinnings and relevant to understanding motivations for TCS as it is, is in no way TCS and is not mathematics.

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51229#51229 Mitch Harris 2011-01-05T19:15:30Z 2011-01-05T19:15:30Z

@Igor - I was about to say the same thing, but it certainly is a text about mathematics that is inspired by thinking about writing programs...well, those programs that Don Knuth was thinking about in 1960.

http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/51220#51220 Mitch Harris 2011-01-05T19:00:18Z 2011-01-05T19:00:18Z

Intro to Automata Theory, Languages, and Computation, Hopcroft, Ullman, Motwani <a href="http://infolab.stanford.edu/~ullman/ialc.html" rel="nofollow">infolab.stanford.edu/~ullman/ialc.html</a> is a good alternative.

http://mathoverflow.net/questions/51124/collatz-conjecture-for-numbers-of-th-form-2n-1 Mitch Harris 2011-01-04T21:38:06Z 2011-01-04T21:38:06Z

If you plot the numbers, some interesting patterns emerge (mostly increasing but with scattered outliers, and longer and longer incremental sequences). A very different pattern from the usual Collatz 'number of steps' function A006577.

http://mathoverflow.net/questions/51124/collatz-conjecture-for-numbers-of-th-form-2n-1 Mitch Harris 2011-01-04T21:34:10Z 2011-01-04T21:34:10Z

The sequence has been submitted to OEIS (not yet approved) with links here.

http://mathoverflow.net/questions/51013/unpopular-elementary-theorems-identities-to-impress-an-audience-of-mathematici Mitch Harris 2011-01-03T16:58:05Z 2011-01-03T16:58:05Z

+1 simply for pointing out Marden's theorem.

http://mathoverflow.net/questions/50739/the-mystic-rose/50740#50740 Mitch Harris 2010-12-30T17:23:53Z 2010-12-30T17:23:53Z

The function given there is for equally spaced points on a circle, and links there go to explanations and formulas. One link on that OEIS page is to: <a href="http://oeis.org/A005732" rel="nofollow">oeis.org/A005732</a> for general position points on a circle, and gives the formula C(n+3,6)+C(n+1,5)+C(n,5) surely equivalent to a formula at your relevant blog posting.

http://mathoverflow.net/questions/49056/is-pattern-recognition-np-complete Mitch Harris 2010-12-11T20:06:45Z 2010-12-11T20:06:45Z

'Pattern Recognition' seems too general a name for this problem. It sounds more like interpolation.

http://mathoverflow.net/questions/38551/equivalence-of-families-of-objects-with-the-same-counting-function Mitch Harris 2010-09-13T15:31:23Z 2010-09-13T15:31:23Z

This can be also answered philosophically. Surely we can define 'by accident' formally, and then arbitrarily construct sets of objects that have the same counting function but with is no -meaningful- isomorphism. But then such a construction is most likely not between anything interesting combinatorially. That is, we -act- like every pair of sets with a bijection has a meaningful bijection, just that we may not have found one yet. On the other hand, this may just be motivation to look at those numerical identities that don't yet have a satisfying combinatorial interpretation.

http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/36595#36595 Mitch Harris 2010-08-25T16:19:17Z 2010-08-25T16:19:17Z

&quot;Is chromatic number of the plane ordinary mathematics?&quot;... How is it not? The question was not created by motivations from logic, if by 'ordinary' you mean 'not motivated by concerns outside the domain of interest (usually logic)'.

http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every Mitch Harris 2010-08-04T14:22:13Z 2010-08-04T14:22:13Z

How do you expect answers to this question to be different from what Lance did? Do you want also things not on his lists? Do you want extra 'votes' for things already mentioned by him? (I find his lists pretty comprehensive: his favorites ~ results complexity theorists should know)