Some Mathematical Gifts

December 20, 2010

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 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}$ or ${1}$ .

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 ${f(x)}$ be a boolean function. Suppose that the number of ${x}$ so that ${f(x) = 1}$ is odd. Then the function ${f(x)}$ is elusive.

The proof is really wonderful. Consider a decision tree for ${f(x)}$ that is not elusive. For a leaf ${l}$ define ${N(l)}$ 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 ${N(l)}$ 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 ${y}$ are ${0}$ . The proof is based on the magic number ${3}$ , not ${2}$ , 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 ${3}$ .
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 ${n-1}$ 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 ${n}$ is not divisible by ${3}$ , then the statement is true. If ${3}$ divides ${n}$ , then ${n=3m}$ , 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 ${y}$ 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 ${y}$ 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 ${z}$ 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 ${m = 2k-2l> 0.}$ Then ${z/3^{2l}}$ is an integer congruent to ${-1}$ modulo ${3}$ . 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 ${m = 2l - 2k > 0}$ . Again ${z/3^{2k}}$ is an integer congruent to ${2}$ modulo ${3}$ . 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?

37 Comments leave one →

Amir Michail permalink

December 20, 2010 9:45 am

Going beyond TeX/LaTeX, check out TeXmacs:

http://www.texmacs.org/tmweb/home/screenshots.en.html

It’s easy to install:

http://www.texmacs.org/tmweb/download/macosx.en.html
http://www.texmacs.org/tmweb/download/windows.en.html

TeXmacs doesn’t use TeX. It has its own high quality real-time WYSIWYG typesetter.

Loading...

Reply
Petter permalink

December 20, 2010 10:55 am

There’s also a nice iPhone app for the LaTeX symbol finder.

Loading...

Reply
Allen Knutson permalink

December 20, 2010 11:32 am

For III, once you assume the coefficients are rational, then *one* evaluation is enough; plug any transcendental into the machine, say e.

While stated this way, it sounds extremely theoretical, my understanding (from Macaulay 2’s Mike Stillman) is that this is actually the basis for some approximate algorithms in numerical algebraic geometry. Actually finding the coefficients is somehow based on LLL-reduction.

Loading...

Reply
- rjlipton permalink*
  
  December 20, 2010 12:11 pm
  
  Allen,
  
  I like the idea but not sure works. The trouble is this: suppose the polynomial is Ax+B. So you get Ae+B. But A,B can be HUGE, there is no limit on their size. So how does LLL recover?
  
  Loading...
  
  Reply
  - Allen Knutson permalink
    
    December 20, 2010 4:48 pm
    
    That’s why I said “approximate”. In an actual application, like decomposing an ideal in a polynomial ring as an intersection of prime ideals, you expect that the coefficients in the answer aren’t actually going to be outrageously large.
    
    Put another way, you would obviously believe the problem to be solvable (in one evaluation) if you knew a bound on the degree of the polynomial and on its coefficients. The LLL-based algorithm I’ve been told of is essentially making that assumption. I presume that when it doesn’t work out well, it starts over with the bound set larger.
    
    Loading...
  - Morong permalink
    
    December 21, 2010 5:34 am
    
    Hah, of course you would bring up computational feasibility.
    
    Loading...
  - Josh Jordan permalink
    
    January 8, 2011 7:49 pm
    
    You can do it with one evaluation. Simply iterate over all the polynomials with nonnegative integer coefficients — after all, there are only a countable number of them — and evaluate each one at e. Stop when you get an exact match with the output from the black box. (This idea is due to Fred Henle.)
    
    Loading...
Alan Kay permalink

December 20, 2010 12:17 pm

Bertrand Russell pointed out long ago that if a rational number in lowest terms is not an integer then its square can’t be either (squaring doesn’t add any primes that will divide out).

I’ve always liked this approach much better since it is generative and general — and much easier than arguing from the other direction.

Cheers,

Alan

Loading...

Reply
Sean Hunter permalink

December 20, 2010 12:29 pm

Sorry to be so boring, but you have an apostrophe in the wrong place in the Tim Gowers reference. His name includes the ‘s’, so it should be “Tim Gowers’s”

Loading...

Reply
- Kenneth W. Regan permalink
  
  December 20, 2010 8:13 pm
  
  Oops, your copy-edit team missed that one. By my book it should be Gowers’ with apostrophe after s.
  
  Loading...
  
  Reply
Ulrik permalink

December 20, 2010 1:40 pm

I think any proof of a “negative” property like being irrational necessarily will be by contradiction (in the sense of assuming the positive counter-property and deriving a contradiction–this is of course constructively valid, as mention on Gower’s blog). In your argument, how do you conclude that $\sqrt2$ is irrational? Only by saying that if it was rational, you would have a non-trivial root of $f$, right?

Only if we could rephrase irrationality as an essentially positive property could we hope for a direct proof. But since the irrationals are uncountable that seems impossible.

Loading...

Reply
- Arne permalink
  
  December 20, 2010 5:30 pm
  
  I think the irrationality-proof is ok. You can simply define the irrational numbers as those $p$ where no $n,m \in \mathbb{Z}$ exist such that $p = \frac{n}{m}$ . This is equivalent to (rewriting rule of quantors)
  $\forall n,m \in \mathbb{Z} : p \neq \frac{n}{m}$
  and that’s precisely what the proof shows.
  
  But actually this thing as “proof by contradiction” is quite a high-level thing, I think. I checked the axioms used by metamath, and there doesn’t seem to be an axiom that directly relates to “proof by contradiction”. Hence you could probably transform any proof into a proof that does not use “proof by contradiction” just by going down to the axioms of logic.
  
  Loading...
  
  Reply
divesh permalink

December 20, 2010 6:25 pm

why do it modulo 3? The same can be done modulo 2 and it is much easier…

x = 2^k \cdot a, y= 2^l \cdot b.

Then there are two cases k >= l and k < l. In the first case, write z as 2^{2l} (2 \cdot 2^{2k – 2l} – 1) and in the second case, as 2^{2k+1} (1 – 2^{2l – 2k -1})

and the term in the paranthesis is odd, i.e. 1 mod 2 in both cases.

Loading...

Reply
- rjlipton permalink*
  
  December 20, 2010 6:48 pm
  
  divseh,
  
  Perhaps but what if k=l? Then after factor out get 2^{kl} (2a^2 – b^2). So let a be odd and b even. Then what?
  
  Loading...
  
  Reply
  - Divesh permalink
    
    December 21, 2010 7:22 am
    
    b cannot be even… you have already taken the power of 2 out..
    
    Loading...
lifeofpi permalink

December 20, 2010 7:13 pm

Love the gifts! Thanks!!

Loading...

Reply
atri permalink

December 20, 2010 8:03 pm

Dick: Thanks for the gifts, esp the polynomial one!

I had a followup question: the solution says that you can determine the polynomial if you use two *adaptive* queries. What about *non-adaptive* queries? Can one do something similar in say constant number of non-adaptive queries? (Hopefully, I’m not missing a simple solution here…)

Loading...

Reply
- Greg permalink
  
  December 21, 2010 9:32 am
  
  I don’t see how a constant number of non-adaptive queries could ever guarantee finding the coefficients of the hidden polynomial. After all, the number of terms in the secret polynomial can increase without limit – whereas a constant number of queries is, of course, constant.
  
  Therefore a constant number of queries can determine only a limited number of coefficients, whereas there is no limit to the actual number of coefficients that need to be found.
  
  Loading...
  
  Reply
  - rjlipton permalink*
    
    December 21, 2010 11:30 am
    
    Greg,
    
    Let $p(x) = ax^{1000} + bx + c$ , for example. You get $p(1) = a + b + c$ . Assume that this is
    $9$ . Then you get $p(10)$ . This will be $a 0 0 0 \dots b c$ as a decimal number. Then read off the coefficients.
    
    Loading...
  - rjlipton permalink*
    
    December 21, 2010 11:31 am
    
    Greg,
    
    The queries are adaptive, the second depends on the first. Sorry for the confusion.
    
    Loading...
  - atri permalink
    
    December 21, 2010 9:38 pm
    
    Greg: As Dick pointed out below just talking about the number of queries is not enough. However, maybe I’m missing the part of your argument which makes use of non-adaptivity.
    
    I think I have an argument to show that non-adaptive case is hosed *if* all the query points are integers. Note that the adaptive solution just queries the secret polynomials at two integers.
    
    In fact, let us consider the case where in addition to the black-box, you are also given an upper bound $d$ on the degree of the secret polynomial. I claim one needs to make $d+1$ non-adaptive queries (aka the usual polynomial interpolation algorithm). If not, let us assume that the non-adaptive queries are at (distinct) points $a_1,\dots,a_d$ . Consider the polynomial $\Delta(X)=\prod_{i=1}^d (X-a_i)$ . Now any pair of polynomial $p(X), r(X)=p(X)+\Delta(X)$ cannot be distinguished by the $d$ queries $a_1,\dots,a_d$ . The issue is that some of the coefficients of $\Delta(X)$ can be negative. However, since the queries are *non-adaptive*, one can easily compute the magnitude of the smallest negative coefficient in $\Delta(X)$ and make sure that all the coefficients of $p(X)$ are large enough positive integers so that both $r(X)$ and $p(X)$ have natural numbers as coefficients.
    
    However, if the queries are reals, then the coefficients of $\Delta(X)$ are no longer guaranteed to be integers and the argument above fails.
    
    Loading...
  - Ørjan Johansen permalink
    
    December 21, 2010 9:53 pm
    
    Allen Knutson pointed out that testing with a single transcendental number is enough. On the other hand no finite number of fixed/non-adaptive algebraic numbers suffices:
    
    Let p1, …, pn be integer polynomials that have the test numbers as roots. Take their product and split it up into a difference p1p2…pn = q1-q2 of polynomials with natural coefficients. Then q1 and q2 are not distinguished by the test.
    
    Loading...
- atri permalink
  
  December 22, 2010 8:28 am
  
  Ørjan: thanks! I guess that settles the question.
  
  Loading...
  
  Reply
iconjack permalink

December 21, 2010 7:53 pm

Wouldn’t the majority function on 4 inputs yield 1 either 11 times (if you count two 1’s as a majority), or 5 times (if you don’t)?

Loading...

Reply
joro permalink

December 23, 2010 10:55 am

10x for the gifts. Merry Christmas!

Loading...

Reply
Gilbert Bernstein permalink

December 25, 2010 3:29 am

Thanks for the gifts. The proof of irrationality reminded me of a neat approach using inequalities. I read about it here first (4th proof):

http://researchinpractice.wordpress.com/2010/06/02/five-proofs-of-the-irrationality-of-root-5/

Loading...

Reply
John Sidles permalink

December 25, 2010 2:02 pm

erennially welcome year-end mathematical gift are ChessBase News Christmas puzzles. This year they are composed by the algebraic topologist and chess grandmaster John Nunn.

Unusually, however, this year’s holiday chess puzzles lead-off with a (seemingly unrelated) link to a YouTube video titled A Christmas Food Court Flash Mob.

Hmmmm … what link (if any) might A Christmas Food Court Flash Mob have to mathematics broadly, and to chess problems in particular? Why post it on ChessBase? Why does this video speak to us so broadly and profoundly (2.6×10^7 views so far)?

In searching my quotation database, I found an answer by Paul Dirac:

“A Golden Age is a time when ordinary people can make extraordinary contributions.”

Attributed to Paul Dirac by Valentine Telegdi

Perhaps a A Christmas Food Court Flash Mob speaks to us because we all appreciate that a world filled with many billions of people—and hopefully, many millions of mathematicians—makes sense only if the 21st century unfolds as a Dirac-style Golden Age … and the ordinary people of A Christmas Food Court Flash Mob show us what such a world could be like.

My thanks go to ChessBase, to John Nunn, and especially, to everyone who contributed in the past year to making Gödel’s Lost Letter and P=NP such a wonderful place. Happy holidays to all! 🙂

Loading...

Reply
MPF permalink

January 12, 2011 8:56 am

Regarding the irrationality proof, I also believe it is ok with modulo 2 calculations…
Not using “proof by contradiction” can be done thru clever presentation of the demonstration…

Loading...

Reply
MPF permalink

January 12, 2011 9:59 am

I check it again, and in fact, working modulo 2, you can only prove that x is even and y is odd.
My suggestion is that you may freely set additional conditions on x and y: for example, they have no common factor, and they are non-zero integers.
Then, working modulo 3, you easily prove that z cannot be zero (the ‘no common factor’ condition helps very much).

Loading...

Reply

	T.D. Nguyen on Just Jim
	joe12361 on Just Jim
	T Nguyen on COMPUTATION, LOGIC, AND INFORM…
	Umayr on 1968 vs 2024
	javaid aslam on 1968 vs 2024
	Ian Z aka nobrowser on 1968 vs 2024
	Enough is enough on 1968 vs 2024
	rjlipton on An Open Problem
	Jordan on An Open Problem
	Jon Awbrey on An Open Problem
	Blog Runner on An Open Problem
	William Gasarch on An Open Problem
	DL on An Open Problem
	Jon Awbrey on An Open Problem
	An Open Problem \| Gö… on Cargo Cult Redo

a personal view of the theory of computation

Some Mathematical Gifts

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

Some Mathematical Gifts

Share this:

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

Discover more from Gödel's Lost Letter and P=NP