User rgrig - MathOverflow

Answer by rgrig for How Does My Radio Work?

2012-06-26T10:05:01Z

I've been trained as an engineer, and I can tell you that engineers have a somewhat simplified view of the matter. (But, not only a simplified view, of course.) The other answers fill in some detail, but I think a higher-level view is useful.

There is no such thing as perfect recovery of the transmitted signal. The best you can hope is to bound the error.

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| < 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$, …, $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 rectangular function in the frequency domain, meaning convolution with a sinc in the time domain). See also this related question.

There are broad-spectrum modulation techniques, which are used for example in fourth generation mobile-phone networks, that do not rely on the assumption that the signal covers a narrow band. The two main ones are frequency hoping (use some narrow-band modulation technique but change $f_0$ often in some pseudorandom sequence) and spread spectrum (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)| < c$ for some $c$ for all $f$. This way they behave as background noise as far as demodulating any narrow-band signal is concerned.

Answer by rgrig for Deriving the complete set of "non-redundant" true statements in disjunctive form in propositional logic

2010-07-29T19:34:02Z

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

You will find in the paper A Knowledge Compilation Map many references to papers that discuss variants of this problem. For example, the paper Algorithms for Selective Enumeration of Prime Implicants focuses on the case when $\phi$ is given in DNF or CNF (and also has many good references). Another interesting paper is Implicit and Incremental Computation of Primes and Essential Primes of Boolean Functions 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.)

In short, there are lots of algorithms, none works fast all the time, but some might be fast enough in practice.

(Note: Knuth uses the term conjunctive prime form for the conjunction of prime clauses. This appears in fascicle 0 of volume 4 of TAoCP from 2005-2009. But the name didn't yet caught on.)

Answer by rgrig for How do proof verifiers work?

2010-07-23T10:07:10Z

I do not have any general answer, but I do have an example of a proof checker that is small enough. The accompanying paper 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 not 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.)

Answer by rgrig for Digraph intermediate connectivity

2010-07-05T12:08:10Z

Just `connected' is fine. For example, Wikipedia and Tutte 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.

Answer by rgrig for Math puzzles for dinner

2010-06-24T15:59:13Z

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.

Answer by rgrig for Math puzzles for dinner

2010-06-24T15:52:07Z

When they came to diner some shook hands. Ask them to prove that that two of them shook hands the same number of times.

How do you approach your child's math education?

2010-03-31T15:20:52Z

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: 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?

(This a community wiki, so please give one advice per answer, as usual.)

Background

I ask here because I believe that the challenges a mathematician faces in educating a child are special. For example, at least some websites and books 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.

Christos Papadimitriou said 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.)

Timothy Gowers (in Mathematics, a very short introduction) 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. (Update. 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 no 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. [...]")

There is a somewhat related Mathoverflow question. 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 online book that seems to give particularly good generic advice. Here I'm looking more for advice geared towards parents that are mathematicians.

In short, I'm looking for specific advice on how a mathematician should approach his/her child's math education, especially for the 1 to 10 age range.

Answer by rgrig for How do they verify a verifier of formalized proofs?

2010-03-30T10:17:35Z

Many pointed out the essential: Provers like Coq and HOL have a very small core that checks the proofs.

I want to add that there are other provers, the 'automatic' ones, which do indeed tend to be complicated. For example, most SMT solvers 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 this article.)

Answer by rgrig for What is convolution intuitively?

2010-03-21T11:40:52Z

The two things that first come to mind when I think 'convolution' are:

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).
Imagine a black box that receives one number $x_n$ every second and must output a number $y_n$ every second. (DSP 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 k inputs and output some function of those k 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 $0\le i<k$ . 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.

As an example of combining these two points, if the filter always outputs the average of the last k 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 k 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 completely filtered out.)

Answer by rgrig for Finding all paths on undirected graph

2010-03-18T18:31:29Z

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

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

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}$.

Push s on the path stack and call search(s):

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

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

Answer by rgrig for Computer Algebra Errors

2010-03-18T09:31:19Z

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 http://mathoverflow.net/questions/18483/an-elementary-number-theoretic-infinite-series

Is the Jaccard distance a distance?

2010-03-13T18:37:59Z

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book 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.)

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.

Do you need to say what left-unique and right-unique means?

2010-03-11T13:11:42Z

I am talking about a relation that is what Wikipedia describes as left-unique and right-unique. I never heard these terms before, but I have heard of the alternatives (injective and functional). The question is, which terminology do you recommend? Should I include short definitions? (The context is a text in the area of formal methods. I'm not sure if this helps.)

These are some trade-offs that I see:

I think that left-unique and right-unique are not widely known, but I'm not sure at all.
functional is overloaded
injective sounds too fancy (subjective, of course)
left-unique and right-unique are symmetric (good, of course)

Edit: It seems the question is unclear. Here are more details. I describe sets X and Y and then say:

now we must find an injective and functional relation between sets X and Y such that...
now we must find a left-unique and right unique relation between sets X and Y...

Which one do you recommend? What other information would you add? The relation does not 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?

Answer by rgrig for Why do so many textbooks have so much technical detail and so little enlightenment?

2010-02-17T18:58:51Z

This is a quote from a beautiful little book by D. Knuth called Surreal Numbers.

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.

A: Yes, I remember having a tough time staying awake. But look, wouldn't our beautiful discoveries be just about the same?

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 so impressed.

A: Or bored.

B: Yes, there's that. I guess the excitement and the beauty comes in the discovery, not the hearing.

A: But it is beautiful. And I enjoyed hearing your discoveries at most as much as making my own. So what's the real difference?

B: I guess you're right at that. I was able to really appreciate what you did, because I had already been struggling with the same problem myself.

... and so on.

Answer by rgrig for Definition of longest common subsequences

2009-10-28T10:47:16Z

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.

Comment by rgrig

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.

Comment by rgrig

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

Comment by rgrig

2011-11-25T13:08:07Z

Shoenfield, Mathematical Logic also uses the "appropriate" version. Do I understand correctly that you are saying there are reasons to prefer the "usual" version?

Comment by rgrig

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.

Comment by rgrig

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?

Comment by rgrig

2010-08-14T14:10:29Z

Talk to people working on hittheroad.ie

Comment by rgrig

2010-07-30T11:05:27Z

Carl, please note that your argument works for many reasonable representations of P, such as boolean circuits or CNF, but not for all. As an example, if P is represented as a (reduced ordered) BDD, then checking satisfiability is a constant time operation. Using this representation may be seen as "cheating" 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.

Comment by rgrig

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 "something" from reals to integers, the question being what would be a sensible characterization of "something"?

Comment by rgrig

2010-07-27T14:29:53Z

Sorry, I forgot to mention that.

Comment by rgrig

2010-07-21T09:19:08Z

You can do the 'shopping' for the next 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.

Comment by rgrig

2010-07-08T14:13:07Z

Is it true that "if there is a good coloring then any minimum coloring is good"? (where 'good coloring' = 'proper vertex coloring with no solitary color' as required in the question)

Comment by rgrig

2010-07-08T09:53:06Z

But there's no requirement for minimality here.

Comment by rgrig

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?

Comment by rgrig

2010-06-24T16:01:01Z

Also, Rustan Leino tends to entertain people with puzzles that end up on this list: research.microsoft.com/en-us/um/people/leino/…

Comment by rgrig

2010-06-22T15:57:57Z

Balanced ternary doesn't seem redundant. en.wikipedia.org/wiki/Balanced_ternary Do you have a (counter)example?