User rgrig - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T03:10:11Z http://mathoverflow.net/feeds/user/840 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99549/how-does-my-radio-work/100669#100669 Answer by rgrig for How Does My Radio Work? rgrig 2012-06-26T10:05:01Z 2012-06-26T10:05:01Z <p>I've been trained as an engineer, and I can tell you that engineers have a somewhat simplified view of the matter. (But, not <em>only</em> a simplified view, of course.) The other answers fill in some detail, but I think a higher-level view is useful.</p> <p>There is no such thing as perfect recovery of the transmitted signal. The best you can hope is to bound the error.</p> <p>For most modulation techniques the basic idea is that the spectrum $X$ of a signal $x$ is nearly 0 outside a narrow band: $X(f)\approx0$ when $|f \pm f_0| &lt; B$. Both AM and FM are essentially means of transforming a spectrum centered around $0$ into one centered around $f_0$. So, in order to recover a signal, the main concern is to make sure that the spectrums $X_1$, $X_2$, &hellip;, $X_n$ do not overlap. This is achieved in a rather uninteresting way: regulation. Then you can extract one signal by shifting $f_0$ to $0$ (convolution with a Dirac impulse in frequency domain, meaning multiplication with a harmonic signal in the time domain), and then applying a low pass filter (multiplication with a <a href="http://en.wikipedia.org/wiki/Rectangular_function" rel="nofollow">rectangular function</a> in the frequency domain, meaning convolution with a sinc in the time domain). See also <a href="http://mathoverflow.net/questions/5892/what-is-convolution-intuitively" rel="nofollow">this related question</a>.</p> <p>There are broad-spectrum modulation techniques, which are used for example in fourth generation mobile-phone networks, that do <em>not</em> rely on the assumption that the signal covers a narrow band. The two main ones are <em>frequency hoping</em> (use some narrow-band modulation technique but change $f_0$ often in some pseudorandom sequence) and <em>spread spectrum</em> (multiply the signal with a pseudorandom sequence before using a narrow-band modulation technique). The signals obtained thru such methods have a wide band, but are bounded $|X(f)| &lt; c$ for some $c$ for all $f$. This way they behave as background noise as far as demodulating any narrow-band signal is concerned.</p> http://mathoverflow.net/questions/29347/deriving-the-complete-set-of-non-redundant-true-statements-in-disjunctive-form/33835#33835 Answer by rgrig for Deriving the complete set of "non-redundant" true statements in disjunctive form in propositional logic rgrig 2010-07-29T19:34:02Z 2010-07-29T20:32:24Z <p>I believe your problem is: Given a boolean function $\phi$, find the set of its prime clauses (aka prime implicates). This is equivalent to finding all the prime implicants of $\lnot\phi$.</p> <p>You will find in the paper <a href="http://scholar.google.co.uk/scholar?cluster=4020517321592725796" rel="nofollow">A Knowledge Compilation Map</a> many references to papers that discuss variants of this problem. For example, the paper <a href="http://scholar.google.co.uk/scholar?cluster=3018518818059820501" rel="nofollow">Algorithms for Selective Enumeration of Prime Implicants</a> focuses on the case when $\phi$ is given in DNF or CNF (and also has many good references). Another interesting paper is <a href="http://scholar.google.co.uk/scholar?cluster=9792089307967946883" rel="nofollow">Implicit and Incremental Computation of Primes and Essential Primes of Boolean Functions</a> that represents the resulting set as a BDD, which may be much smaller than a simple list. (Though a ZBDD, invented later, might work even better.)</p> <p>In short, there are lots of algorithms, none works fast all the time, but some might be fast enough in practice.</p> <p>(Note: Knuth uses the term conjunctive prime form for the conjunction of prime clauses. This appears in fascicle 0 of volume 4 of <a href="http://www-cs-faculty.stanford.edu/~uno/taocp.html" rel="nofollow">TAoCP</a> from 2005-2009. But the name didn't yet caught on.)</p> http://mathoverflow.net/questions/32923/how-do-proof-verifiers-work/33074#33074 Answer by rgrig for How do proof verifiers work? rgrig 2010-07-23T10:07:10Z 2010-07-23T10:07:10Z <p>I do not have any general answer, but I do have an example of <a href="http://bitbucket.org/michal.moskal/fx7/src/tip/trew/main.ml" rel="nofollow">a proof checker</a> that is small enough. The <a href="http://scholar.google.com/scholar?cluster=12587486752114072031" rel="nofollow">accompanying paper</a> should make it easier to understand and it should give some idea of how the proof system was designed. I should mention that it does <em>not</em> handle HO proofs. One interesting feature is that it dumps HO proof obligations that essentially say "the calculus rules I use are sound." (And most of those proof obligations are handled by some tactics in Coq automatically.)</p> http://mathoverflow.net/questions/30529/digraph-intermediate-connectivity/30615#30615 Answer by rgrig for Digraph intermediate connectivity rgrig 2010-07-05T12:08:10Z 2010-07-05T12:08:10Z <p>Just connected' is fine. For example, <a href="http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29" rel="nofollow">Wikipedia</a> and <a href="http://books.google.com/books?id=uTGhooU37h4C&amp;lpg=PP1&amp;dq=graph%2520theory&amp;pg=PA132#v=onepage&amp;q&amp;f=false" rel="nofollow">Tutte</a> agree. However, since "the number of systems of terminology presently used in graph theory is equal, to a close approximation, to the number of graph theorists," (R.P. Stanley, 1986) you might want to include the definition anyway.</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29397#29397 Answer by rgrig for Math puzzles for dinner rgrig 2010-06-24T15:59:13Z 2010-06-24T15:59:13Z <p>Start with four beads placed at the corners of a square. You are allowed to move a bead from position x to position y if one of the other three beads is at position (x+y)/2. In other words, you may reflect a bead with respect to another bead.' Find a sequence of such moves that places the beads at the corners of a bigger square, or show that the task is impossible.</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29394#29394 Answer by rgrig for Math puzzles for dinner rgrig 2010-06-24T15:52:07Z 2010-06-24T15:52:07Z <p>When they came to diner some shook hands. Ask them to prove that that two of them shook hands the same number of times.</p> http://mathoverflow.net/questions/19957/how-do-you-approach-your-childs-math-education How do you approach your child's math education? rgrig 2010-03-31T15:20:52Z 2010-04-03T21:56:34Z <p>My son is one year old, so it is perhaps a bit too early to worry about his mathematical education, but I do. I would like to hear from mathematicians that have older children: <i>What do you wish you'd have known early? What do you think you did particularly well? What do you think would be particularly bad? Is there a book (for children or parents) that you recommend?</i></p> <p>(This a community wiki, so please give <em>one</em> advice per answer, as usual.)</p> <h3>Background</h3> <p>I ask here because I believe that the challenges a mathematician faces in educating a child are special. For example, at least <a href="http://www.bbc.co.uk/schools/parents/work/primary/numeracy_and_science/maths_at_home_primary.shtml" rel="nofollow">some websites</a> and <a href="http://books.google.com/books?id=6GxoPgAACAAJ" rel="nofollow">books</a> address the parents' fear of not knowing how to solve homework, which keeps them from becoming involved. On the contrary, I fear I might get too involved and either bore my son or make him think he likes math when in fact his skills are elsewhere.</p> <p>Christos Papadimitriou <a href="http://linkinghub.elsevier.com/retrieve/pii/S1574013709000185" rel="nofollow">said</a> in an interview that, even though his father was teaching math in high-school, they never discussed math. I wonder if that means his father didn't teach him how to count and I wonder if it's a good strategy. (It certainly turned out well in one case.)</p> <p>Timothy Gowers (in <a href="http://books.google.com/books?id=DBxSM7TIq48C" rel="nofollow">Mathematics, a very short introduction</a>) says that it was inappropriate to explain to his son, who was six, the concept 'zero' using the group axioms. (Or something to this effect, I don't have the book near to check.) That was surprising to me, because I wouldn't have thought that I need to restrain myself from mentioning abstract concepts. (<strong>Update.</strong> Here's the quote: "[The non-abstract] way of thinking makes it hard to answer questions such as the one asked by my son John (when six): how can nought times nought be nought, since nought times nought means that you have <em>no</em> noughts? A good answer, though not one that was suitable at the time, is that it can be deduced from the [field axioms] as follows. [...]")</p> <p>There is a <a href="http://mathoverflow.net/questions/5139/how-have-mathematicians-been-raised" rel="nofollow">somewhat related Mathoverflow question</a>. This one is different, because I'm looking for advice (rather than statistics/anecdotes) and because my goal is to give my son a good math education (rather than to make him a mathematician). I also found an <a href="http://www.math.com/parents/articles/helpmath.html" rel="nofollow">online book</a> that seems to give particularly good generic advice. Here I'm looking more for advice geared towards parents that are mathematicians.</p> <p>In short, I'm looking for <em>specific</em> advice on how a mathematician should approach his/her child's math education, especially for the 1 to 10 age range.</p> http://mathoverflow.net/questions/18421/how-do-they-verify-a-verifier-of-formalized-proofs/19813#19813 Answer by rgrig for How do they verify a verifier of formalized proofs? rgrig 2010-03-30T10:17:35Z 2010-03-30T10:17:35Z <p>Many pointed out the essential: Provers like Coq and HOL have a very small core that checks the proofs.</p> <p>I want to add that there are other provers, the 'automatic' ones, which do indeed tend to be complicated. For example, most <a href="http://www.smtcomp.org/2010/" rel="nofollow">SMT solvers</a> are like that. The route taken there is exactly the one mentioned in the question. Instead of trying to verify the proof 'finder', they modify it to generate proofs that can be checked by a very small proof checker. (See <a href="http://scholar.google.com/scholar?cluster=12587486752114072031" rel="nofollow">this article</a>.)</p> http://mathoverflow.net/questions/5892/what-is-convolution-intuitively/18923#18923 Answer by rgrig for What is convolution intuitively? rgrig 2010-03-21T11:40:52Z 2010-03-21T11:40:52Z <p>The two things that first come to mind when I think 'convolution' are:</p> <ol> <li><p>It's the thing that corresponds to multiplication on the other side of the Fourier transform. (This was already mentioned by John D. Cook) It works both ways, of course, $\mathcal F (f*g)=\mathcal F f\cdot \mathcal F g$ and $\mathcal F (f\cdot g)=\mathcal F f* \mathcal F g$. This fact is useful when used in combination with other simple facts about the Fourier transform (such as the fact that a rectangular function corresponds to sinc and, in the limit, a Dirac impulse corresponds to a constant function).</p></li> <li><p>Imagine a black box that receives one number $x_n$ every second and must output a number $y_n$ every second. (<a href="http://en.wikipedia.org/wiki/Digital_signal_processing" rel="nofollow">DSP</a> people call it a 'filter' and it's used, for example, to process audio signals in a mobile phone in real-time.) The simplest thing the box could do is to output some function of the current input. The natural next step is to remember the last <em>k</em> inputs and output some function of those <em>k</em> values. One of the simplest functions is a linear combination $$y_n=\sum_i c_i x_{n-i}$$ where $c_i$ is non-zero only for <code>$0\le i&lt;k$</code>. That's a convolution! To generalize, you make the filter remember all previous values and even be clairvoyant. That is, you extend the support of $[c_n]$. Then, if you want, you replace digital circuits with analog ones. That is, you go from summing to integration.</p></li> </ol> <p>As an example of combining these two points, if the filter always outputs the average of the last <em>k</em> inputs then that's a convolution with the rectangular function in the time domain so it must be a multiplication with a sinc in the frequency domain. Therefore, averaging the last <em>k</em> values attenuates high frequencies. (Hardly surprising, but at least you see immediately that the frequency response is not monotonic and there are only a few frequencies that are <em>completely</em> filtered out.)</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18634#18634 Answer by rgrig for Finding all paths on undirected graph rgrig 2010-03-18T18:31:29Z 2010-03-19T19:21:16Z <p>Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)</p> <p>The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.</p> <p>Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.</p> <p>Push s on the path stack and call search(s):</p> <pre><code>path // is a stack (initially empty) seen // is a set def stuck(x) if x == t return False for each neighbor y of x if y not in seen insert y in seen if !stuck(y) return False return True def search(x) if x == t print path seen = set(path) if stuck(x) return for each neighbor y of x push y on the path search(y) pop y from the path </code></pre> <p>Here <em>search</em> does the exhaustive search and <em>stuck</em> could be implemented in DFS style (as here) or in BFS style.</p> http://mathoverflow.net/questions/11517/computer-algebra-errors/18563#18563 Answer by rgrig for Computer Algebra Errors rgrig 2010-03-18T09:31:19Z 2010-03-18T09:31:19Z <p>Mathematica 7.0.1 says that Sum[1/(k*Length[Divisors[k]]), {k, 1, n}] is the harmonic number $H_n$, which is clearly wrong. The correct answer is at <a href="http://mathoverflow.net/questions/18483/an-elementary-number-theoretic-infinite-series" rel="nofollow">http://mathoverflow.net/questions/18483/an-elementary-number-theoretic-infinite-series</a></p> http://mathoverflow.net/questions/18084/is-the-jaccard-distance-a-distance Is the Jaccard distance a distance? rgrig 2010-03-13T18:37:59Z 2010-03-14T11:35:12Z <p>Wikipedia defines the <a href="http://en.wikipedia.org/wiki/Jaccard_index" rel="nofollow">Jaccard distance</a> between sets <em>A</em> and <em>B</em> as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a <a href="http://books.google.com/books?id=DGjbibiS-S0C&amp;pg=PA38&amp;dq=jaccard+similarity&amp;as_brr=3&amp;ei=iNGbS96kNYfIywTVjZ2cCg&amp;cd=1#v=onepage&amp;q=jaccard%20similarity&amp;f=false" rel="nofollow">book</a> claiming that this is a metric. However, I couldn't find any explanation of why $J_\delta$ obeys the triangle inequality. The naive approach of writing the inequality with seven variables (e.g., $x_{001}$ thru $x_{111}$, where $x_{101}$ is the number of elements in $(A\cap C) \backslash B$) and trying to reduce it seems hopeless for pen and paper. In fact it also seems hopeless for Mathematica, which is trying to find a counterexample for 20 minutes and is still running. (It's supposed to say if there isn't any.)</p> <p>Is there a simple argument showing that this is a distance? Somehow, it feels like the problem shouldn't be difficult and I'm missing something.</p> http://mathoverflow.net/questions/17854/do-you-need-to-say-what-left-unique-and-right-unique-means Do you need to say what left-unique and right-unique means? rgrig 2010-03-11T13:11:42Z 2010-03-11T20:18:25Z <p>I am talking about a relation that is what Wikipedia describes as <a href="http://en.wikipedia.org/wiki/Relation_%28mathematics%29#Special_types_of_binary_relations" rel="nofollow">left-unique and right-unique</a>. I never heard these terms before, but I have heard of the alternatives (injective and functional). The question is, <em>which terminology do you recommend</em>? Should I include short definitions? (The context is a text in the area of formal methods. I'm not sure if this helps.)</p> <p>These are some trade-offs that I see:</p> <ul> <li>I think that <em>left-unique</em> and <em>right-unique</em> are not widely known, but I'm not sure at all.</li> <li><em>functional</em> is overloaded</li> <li><em>injective</em> sounds too fancy (subjective, of course)</li> <li><em>left-unique</em> and <em>right-unique</em> are symmetric (good, of course)</li> </ul> <p><strong>Edit:</strong> It seems the question is unclear. Here are more details. I describe sets <em>X</em> and <em>Y</em> and then say:</p> <ol> <li>now we must find an injective and functional relation between sets <em>X</em> and <em>Y</em> such that...</li> <li>now we must find a left-unique and right unique relation between sets <em>X</em> and <em>Y</em>...</li> </ol> <p>Which one do you recommend? What other information would you add? The relation does <em>not</em> have to be total. For example, various different ranges correspond to different 'feasible' relations. Technically I should not need to say that the relation does not have to be total, but will many people assume that it has to be total if I don't say it?</p> http://mathoverflow.net/questions/13089/why-do-so-many-textbooks-have-so-much-technical-detail-and-so-little-enlightenmen/15608#15608 Answer by rgrig for Why do so many textbooks have so much technical detail and so little enlightenment? rgrig 2010-02-17T18:58:51Z 2010-02-17T18:58:51Z <p>This is a quote from a beautiful little book by D. Knuth called Surreal Numbers.</p> <blockquote> <p>B: I wonder why this mathematics is so exciting now, when it was so dull in school. Do you remember old Professor Landau's lectures? I used to really hate that class: Theorem, proof, lemma, remark, theorem, proof, what a total drag.</p> <p>A: Yes, I remember having a tough time staying awake. But look, wouldn't <em>our</em> beautiful discoveries be just about the same?</p> <p>B: True. I've got this mad urge to get up before a class and present our results: Theorem, proof, lemma, remark. I'd make it so slick, nobody would be able to guess how we did it, and everyone would be <em>so</em> impressed.</p> <p>A: Or bored.</p> <p>B: Yes, there's that. I guess the excitement and the beauty comes in the discovery, not the hearing.</p> <p>A: But it <em>is</em> beautiful. And I enjoyed hearing your discoveries at most as much as making my own. So what's the real difference?</p> <p>B: I guess you're right at that. I was able to really appreciate what <em>you</em> did, because I had already been struggling with the same problem myself.</p> </blockquote> <p>... and so on.</p> http://mathoverflow.net/questions/2983/definition-of-longest-common-subsequences/3029#3029 Answer by rgrig for Definition of longest common subsequences rgrig 2009-10-28T10:47:16Z 2009-10-28T10:47:16Z <p>This is a strange issue to be stuck on: Just try to solve your problem for each definition, starting with the one that feels easier.</p> http://mathoverflow.net/questions/120536/is-the-empty-graph-a-tree/120544#120544 Comment by rgrig rgrig 2013-02-28T11:46:54Z 2013-02-28T11:46:54Z In computer science, (ordered) binary trees are usually defined as a (least) fixed point of $1+T\times T=T$. The empty tree is a binary tree by definition. Binary trees seem to be rather different from connected acyclic graphs. http://mathoverflow.net/questions/81815/is-the-axiom-of-union-independent-of-the-rest-of-zf/81831#81831 Comment by rgrig rgrig 2011-11-25T17:06:52Z 2011-11-25T17:06:52Z @Tct: Well, I'm asking if there is a reason to choose the usual one, which is not the same as asking if there is a reason not to choose the appropriate one. :P http://mathoverflow.net/questions/81815/is-the-axiom-of-union-independent-of-the-rest-of-zf/81831#81831 Comment by rgrig rgrig 2011-11-25T13:08:07Z 2011-11-25T13:08:07Z Shoenfield, <i>Mathematical Logic</i> also uses the &quot;appropriate&quot; version. Do I understand correctly that you are saying there are reasons to prefer the &quot;usual&quot; version? http://mathoverflow.net/questions/38051/a-problem-from-the-book-concrete-mathematics Comment by rgrig rgrig 2010-09-08T12:33:48Z 2010-09-08T12:33:48Z The book Concrete Mathematics has full answers for most exercises (except those marked as research problems), so it's hardly needed to ask on MO. http://mathoverflow.net/questions/740/co-induction-understanding/833#833 Comment by rgrig rgrig 2010-09-08T12:06:08Z 2010-09-08T12:06:08Z If you take the minimum solution of (Nat = Z | S Nat) then the argument by induction is (add Z Z = Z) and (add (S b) Z = S (add b Z) = S b). That is, it looks exactly the same as your argument by coinduction! Does this always happen? Often? http://mathoverflow.net/questions/35563/best-algorithm-to-use-for-a-bus-train-transport-route-planner Comment by rgrig rgrig 2010-08-14T14:10:29Z 2010-08-14T14:10:29Z Talk to people working on <a href="http://hittheroad.ie" rel="nofollow">hittheroad.ie</a> http://mathoverflow.net/questions/29347/deriving-the-complete-set-of-non-redundant-true-statements-in-disjunctive-form Comment by rgrig rgrig 2010-07-30T11:05:27Z 2010-07-30T11:05:27Z Carl, please note that your argument works for many reasonable representations of <i>P</i>, such as boolean circuits or CNF, but not for all. As an example, if <i>P</i> is represented as a (reduced ordered) BDD, then checking satisfiability is a constant time operation. Using this representation may be seen as &quot;cheating&quot; because there are known explicit functions for which the BDD representation is exponential in the number of variables. However, I'd say it is an interesting variant of the problem, that may well be useful in practice. http://mathoverflow.net/questions/33629/what-happens-when-we-print-the-digits-of-a-real-number Comment by rgrig rgrig 2010-07-28T11:56:38Z 2010-07-28T11:56:38Z I'm trying to understand the question. You define a function from Cauchy sequences to integers and you want to see it as &quot;something&quot; from reals to integers, the question being what would be a sensible characterization of &quot;something&quot;? http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29394#29394 Comment by rgrig rgrig 2010-07-27T14:29:53Z 2010-07-27T14:29:53Z Sorry, I forgot to mention that. http://mathoverflow.net/questions/29297/undergraduate-approach-to-learning-math/32688#32688 Comment by rgrig rgrig 2010-07-21T09:19:08Z 2010-07-21T09:19:08Z You can do the 'shopping' for the <i>next</i> year. Like Pete Clark, I'm against taking advice from fellow undergrads, since I found that my preferences were radically different from those of the majority. http://mathoverflow.net/questions/31003/a-decision-problem-in-graph-coloring/31014#31014 Comment by rgrig rgrig 2010-07-08T14:13:07Z 2010-07-08T14:13:07Z Is it true that &quot;if there is a good coloring then any minimum coloring is good&quot;? (where 'good coloring' = 'proper vertex coloring with no solitary color' as required in the question) http://mathoverflow.net/questions/31003/a-decision-problem-in-graph-coloring/31014#31014 Comment by rgrig rgrig 2010-07-08T09:53:06Z 2010-07-08T09:53:06Z But there's no requirement for minimality here. http://mathoverflow.net/questions/30543/building-optimal-rewriting-rules Comment by rgrig rgrig 2010-07-05T12:14:08Z 2010-07-05T12:14:08Z Are you really looking for rewrite rules or are you looking for some sort of `approximate dictionary' that works in bounded space but doesn't necessarily have to be implemented with rewrite rules? http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29397#29397 Comment by rgrig rgrig 2010-06-24T16:01:01Z 2010-06-24T16:01:01Z Also, Rustan Leino tends to entertain people with puzzles that end up on this list: <a href="http://research.microsoft.com/en-us/um/people/leino/puzzles.html" rel="nofollow">research.microsoft.com/en-us/um/people/leino/&hellip;</a> http://mathoverflow.net/questions/29090/direct-construction-of-the-integers Comment by rgrig rgrig 2010-06-22T15:57:57Z 2010-06-22T15:57:57Z Balanced ternary doesn't seem redundant. <a href="http://en.wikipedia.org/wiki/Balanced_ternary" rel="nofollow">en.wikipedia.org/wiki/Balanced_ternary</a> Do you have a (counter)example?