# Andy's Math/CS page

## Friday, September 14, 2007

### Be Rational

Today, enjoy a home-baked puzzle in real analysis--a somewhat old-fashioned subject that I can't help but love (much like automata theory).

We know that pi = 3.1415... is transcendental, i.e., it is not a zero of any nontrivial univariate polynomial with rational coefficients. Is it possible we could generalize this result?

Part I. Is there a continuous function f: R --> R, such that

a) f takes rational numbers to rational numbers,

b) f(x) is zero if and only if x = pi?

Part II. If you think no such f exists, then for which values (in place of pi) does such an f exist?
On the other hand, if f as in Part I does exist (I reveal nothing!), can it be made infinitely differentiable?

For those new to real analysis, 'weird' objects like the desired f above generally have to be created gradually, through an iterative process in which we take care of different requirements at different stages. We try to argue that 'in the limit', the object we converge to has the desired properties. (Does this sound like computability theory? The two should be studied together as they have strong kinships, notably the link between diagonalization/finite extension methods and the Baire Category Theorem.)

Passing to the limit can be subtler than it first appears; for example, a pointwise limit of continuous functions need not be continuous. Here is a pretty good fast online introduction to some central ideas in studying limits of functions.

Labels: ,

#### 15 Comments:

• Imre Leader calls this the "just do it" approach.

By  gareth.rees, at 3:04 PM

• Exactly--just do it!

Thanks, Gareth--I'd read that article once before, but thanks for pointing out its aptness here.

A favorite just-do-it problem: R^3, or 3-dimensional space, can be expressed as the disjoint union of unit circles!

(Believe I saw this in 'Problems and Theorems in Classical Set Theory', which is where I learned the ropes of transfinite inductive constructions. Very fun book for puzzle fans.)

By  Andy D, at 5:05 PM

• I wouldn't call real analysis an old-fashioned subject like automata theory. There are relatively few first-rate computer scientists working on automata theory nowadays, and it is possible to get through graduate school in theoretical CS without ever learning more automata theory than is covered in the basic undergraduate complexity course. By contrast, there are many active researchers in real analysis and it is an important part of the education of any mathematician.

By  Anonymous, at 12:20 AM

• Agreed, anon, although I don't know enough to pass judgment on automata theory in this way. Real analysis continues to be centrally important--but its charms are often distinctly old-fashioned.

Or perhaps more accurately: the parts of real analysis that aren't old-fashioned, I don't have a clue about.

By  Andy, at 10:44 AM

• Agreed, too, that automata theory is much less frequently applicable in current research, and less taught. I just hold open the possibility that there are plenty of talented people working in it.

By  Andy, at 10:59 AM

• Hi Andy, could you give references for:

> the link between diagonalization/finite extension methods and the Baire Category Theorem

?

Thanks!

By  Anonymous, at 1:02 PM

• anon-
I don't know of a good online reference, but as far as books this connection is covered in Odifreddi's "Classical Recursion Theory, vol. I". I believe it's also touched on in Cooper's "Computability Theory".

The basic idea is pretty simple: if we are trying to construct an infinite string (or language, or real number) meeting a countable list of requirements {R_i}, we can succeed if each R_i is 'generic' in the following sense:

-for all finite prefixes x, there exists an extension x' of x such that for all infinite strings x'' extending x', R_i is satisfied.

If each such R_i satisfies this condition, then we iteratively build up our infinite string, guaranteeing at the ith stage that R_i will be met by our construction.

This procedure is completely analogous to the standard proof in real analysis that the union of countably many nowhere-dense sets cannot cover [0, 1].

As the simplest (and I believe first) examples from each domain, consider the 'diagonalization' proof by Cantor that the reals are uncountable, and the proof by Turing of the existence of undecidable languages.

More advanced constructions in either domain can no longer rely on the finite extension method strictly speaking, since we often want our constructions to have positive properties that cannot be ensured by finite prefixes.

For instance, take Ladner's theorem that P != NP implies there exists a non-NP-complete problem in NP. The property of being in NP cannot be finitely ensured and so has to be carefully maintained as the construction proceeds. Still, the finite extension method is a bedrock idea whose modifications drive a lot of research, and having both a computational and an elegant real-analytic model of the technique in hand can be helpful in both domains.

By  Andy, at 10:25 PM

• Also, re the previous discussion, I believe automata theory is more actively pursued in Europe than here in the States; see Lance's post http://weblog.fortnow.com/2003/03/theory-and-theory-b.html

or check out EATCS, a prominent European theory bulletin, to get a sense of this divide.

By  Andy, at 10:31 PM

• Sorry, EATCS is the association which publishes the bulletin. It's got a Puzzle Column which, naturally, I recommend.

By  Andy, at 10:32 PM

• Great problem, Andy! You came up with this yourself? I'll def. give it some thought!

By  Leo, at 5:38 PM

• GIun3g Your blog is great. Articles is interesting!

By  OnlinePharmacy, at 5:54 AM

• 91GVP0 Thanks to author.

• Hello all!

• Good job!

• Hello all!

By  name, at 3:22 PM