FUN in S&T: Some Mathematical Gifts

Gifts of all kinds: a site, theorems, and proofs

Ron Rivest is one of the most famous computer scientists in the world. While he has done many important things in many aspects of computer theory, he is best known as the “R” in RSA. This is the renowned public key system based on the hardest of factoring created by Ron and Adi Shamir and Len Adleman. They won the Turing Award for this terrific achievement.

Today I thought I would exchange some gifts with you. These are simple mathematical facts that are fun.

One of the “gifts” is from Ron, and the others are from various places and people. It is near the end of the year and the winter solstice is coming up soon: it is on December 21, at 6:38 pm EST. This time of year various cultures also have holidays, festivals, and rituals that celebrate this time. Of course this is the time also for gifts of all kinds, since many holidays involve gifts or celebrations: Chinese New Year, Christmas, Hanukkah, Kwanzaa, New Year, St. Lucia Day, and many others.

In this spirit I hope you enjoy a small number of fun items that I view as gifts from mathematics to all of us.

Gift I

Daniel Kirsch’s gift.

One of the coolest sites I have seen in years is this. Go to the site and then draw with your mouse any symbol at all, anything at all, and magically the site lists a number of LaTeX commands that it thinks are what you want. I drew this

and got this

Very cool. Does everyone know about this great site—am I the last to discover it?

(Let us not forget that TeX itself was a gift. And LaTeX and AMSTeX and all the rest too. That is on a scale beyond the margins of this post.)

Gift II

Ron’s gift.

Ron had a brilliant idea that help solve an important open problem called the Aanderaa-Karp-Rosenberg Conjecture. It is still not completely resolved, but I want to highlight his idea—actually the work was joint with Jean Vuillemin. Suppose that ${f(x_1,\dots,x_n)}$ is a boolean function. There are many ways to define the complexity of such a function:

the size of its smallest formula;

the size of its smallest general circuit;
the size of its smallest circuit of a given constant depth;
and so on.

Another interesting measure is to consider is based on href{bbb}{decision trees} that compute the boolean function. A decision tree starts at a root and at each node branches left or right based on the value of a single variable ${x_i}$ . At a leaf the tree decides whether to accept or reject: each leaf is labelled with {0}

The depth of the decision tree is the length of the longest path in the tree from the root to a leaf. This is the measure that Ron’s idea works on—note the size of the tree is also quite interesting, but that for another day.

Call a boolean function {f(x)}

elusive provided any decision tree for the function, of any size, has some path of depth {n}

. Since it is unnecessary to evaluate a variable more than once on any path, an elusive function has the maximum depth possible.

The natural question is how does one prove that various functions are elusive? In general this can be quite hard, but Ron’s beautiful idea resolves it for many functions.

Theorem: Let be a boolean function. Suppose that the number of so that is odd. Then the function is elusive.

The proof is really wonderful. Consider a decision tree for {f(x)}

that is not elusive. For a leaf {l}

define

to be the number of {x}

‘s so that on that input to the tree the path taken goes to the leaf {l}

. There are two simple observations. Since the tree is not elusive, all paths are less than {n}

, so

is alway even. This follows because some ${x_i}$ was not examined on the path to the leaf {l}

and so the number of inputs that go to this leaf is even.

Next we note that the following identity is true:

$\displaystyle A = \sum_{l \text{ is an accept leaf} } N(l)$

is the total number of inputs that make the boolean function {1}

. we now have a contradiction, since {A}

is even, but by assumption it is odd.

This is one of the most elegant counting arguments, in my opinion. Perhaps in each case there is an alternative proof, perhaps one based on an adversary. But this counting is so nice. As a simple example consider the majority function on {4} inputs: it is {1} when there are two or more {1} ‘s in its input. This happens {9} ways, so the function is elusive.

Gift III

Bettina Richmond’s gift.

Imagine that you are given a black box ${\blacksquare}$ . It has a slot where you can put any real number, after you place one, it makes some sound, vibrates a bit, and returns a value. Inside the box is a secret polynomial {p(x)} : if you put in {x} , you get out {p(x)} .

Your job is to find the exact coefficients of the polynomial, but to make it hard you are only allowed to put in two numbers—one after the other. So far the problem is impossible: it is easy to show that if the black box ${\blacksquare}$ says {0}

each time, you still have no way to get the whole polynomial. So we will restrict the polynomial in a simple way: all the coefficients of the polynomial are natural numbers:

$\displaystyle 0,1,2,3, \dots$

The claim now is the problem is solvable: only two numbers need be evaluated by the black box ${\blacksquare}$ .

The proof of this is quite neat. Ask the black box ${\blacksquare}$ for the value {R= p(1)} . Then ask it for the value at {R+1} . A moments thought will show that this essentially yields the coefficients of the polynomial: one just converts the answer to radix {R+1} and reads off the coefficients. Note it works precisely because the coefficients are all non-negative natural numbers.

This is from the article called: On a Perplexing Polynomial Puzzle . By the way I have seen this puzzle elsewhere on the Web, and some sites ask money for the solution. No regrets here—it’s a gift.

Gift IV

Pythagoras’ gift.

Well not quite. There is an interesting discussion on MathOverflow whether or not there is a proof that ${\sqrt 2}$ is not rational that does not use “proof by contradiction.” See also Tim Gowers’ interesting discussion on this and more.

Our goal is to try and get such a proof. A proof that ${\sqrt 2}$ is not rational—without using proof by contradiction. Suppose we examine the polynomial

$\displaystyle f(x,y) = 2 \cdot x^2 - y^2.$

We will show that this polynomial over the natural numbers is only zero if both {x}

and

are

. The proof is based on the magic number {3}

, not

, and is unfortunately a series of cases. Well its a gift—if you do not like it, then return it.

I need two basic facts about integers:

Any integer is congruent to one of {0,1,2}

modulo

.
Any non-zero integer is of the form ${3^k w}$ where ${k \ge 0}$ is a natural number and {w}

is a non-zero integer than is not divisible by {3}

.
I claim these both are provable by induction. To prove (1) use simple induction. It is clearly true for {0}

. Suppose that {n>0}

. Then

is congruent to one of {0,1,2}

. By case analysis we can show the same is true for {n}

. For example, if ${n-1 \equiv 2 \bmod 3}$ , then ${n \equiv 0 \bmod 3}$ . To prove (2) use complete induction and prove it for positive integers, which is enough. It is clearly is true for {1}

. Suppose that {n>1}

. If

is not divisible by {3}

, then the statement is true. If {3}

divides

, then

, and the proof follows again by induction.

Let’s start the proof. Fix {x} and {y} , not both zero and let {z = f(x,y)} . Our goal is to show {z} is not zero.

${\bullet }$ Suppose {x=0}

and ${y \neq 0}$ . Then {z}

is clearly non-zero.

${\bullet }$ Suppose ${x \neq 0}$ and {y=0} . Then {z} is clearly non-zero.

So we can assume that both {x}

and

are not zero. So far no proof by contradiction—right? Now on to the more interesting cases.

${\bullet }$ Suppose that both {x} and {y} are not divisible by {3} . Then {z} modulo {3} is ${2 \cdot 1 - 1}$ which is not zero. Thus {z} is not zero. This uses (1) and the fact that ${1^2 \equiv 2^2 \equiv 1 \bmod 3}$ .

The above really is the main part of the proof. The rest of the cases have to do with one or both of {x}

and

being divisible by some power of {3}

${\bullet }$ Suppose that ${x = 3^k \cdot a}$ and ${y = 3^l \cdot b}$ by (2) above. Then,

$\displaystyle z = 2 \cdot 3^{2k} \cdot a^2 - 3^{2l} \cdot b^2.$

There are three cases. If {k=l}

then

is equal to ${3^{2k} \cdot (2\cdot a^2 - b^2)}$ . Thus ${z/3^{2k}}$ is an integer which is congruent modulo {3}

to ${2 \cdot 1 - 1}$ . This shows that {z}

is non-zero.

So assume that {k>l} . Then {z} is equal to

$\displaystyle 3^{2l} \cdot ( 2 \cdot 3^m a^2 - b^2 ),$

where

Then ${z/3^{2l}}$ is an integer congruent to {-1}

modulo

. This again shows that {z}

is non-zero.

The last sub-case is {k<l} . Then {z} is equal to

$\displaystyle 3^{2k} \cdot ( 2 \cdot a^2 - 3^m \cdot b^2),$

where

. Again ${z/3^{2k}}$ is an integer congruent to {2}

modulo

. This again shows that {z}

is non-zero.

Open Problems

Is the proof of irrationality of ${\sqrt 2}$ without contradiction? Can it be simplified? Are there other gifts that you would like to share this time of year?

FUN in S&T

Saturday, December 25, 2010

Some Mathematical Gifts

No comments:

Post a Comment