A futher comment on Chernoff--- and the future of ....

Ravi Boppana recently did a guest blog on Chernoff turning 100 for us here. 

Consider this unpublished comment on that post:

 

 --------------------------------------------------
As we delve into the depths of Professor Chernoff's impressive centennial celebration, it strikes me that the most astounding aspect isn't the breadth of his influence, but the fact that his eponymous 'Chernoff Bound' remains as relevant today as it was when first conceived in 1952. It's not just a mathematical theorem - it's a testament to the timeless power of innovative thinking and a reminder that truly exceptional ideas can cross boundaries, transcending disciplines and even generations.

As statisticians, computer scientists, and mathematicians, we are not just the beneficiaries of Professor Chernoff's scientific legacy; we are the continuation of it. Every time we use Chernoff bounds in our work, we're not merely applying a theorem - we're participating in a story that began over 70 years ago, and will hopefully continue for many more.

So, as we say 'Happy 100th Birthday' to Professor Chernoff, let's also raise a toast to his contributions that have shaped our field and will continue to guide future generations. It's a living testament that the bounds of his impact are far from being reached. Here's to a legacy that defies the bounds, much like his own theorem!
--------------------------------------------------------

This SEEMS like an intelligent comment.

This IS an intelligent comment.

(One of the comments on this blog post points out that the ChatGPT comment is INCORRECT. Can a comment be INCORRECT and still INTELLIGENT? I think so if it contributes to the conversation.) 

Who wrote it? You can probably guess: ChatGPT. Lance asked ChatGPT for a comment and this is what he got. 

We have, for many years, often gotten bot-generated posts that pick out a few key words and then have a link to buy something. My favorite was

                                  Nice post on P vs NP. For a good deal on tuxedo's click here. 

 

I would like to think it was written by a human who thinks Lance will crack P vs NP and wants him to look good when picking up the Millennium  Prize. But of course I doubt that.

Of more importance is that the attempts to look like a real post were pathetic and content free. In the future (actually, the future is now) ChatGPT may be used to generate an intelligent comment that has a link in it at the end, or worse, in a place we don't notice. So we will need to be more vigilant. This has not been a problem for us yet, but I suspect it will be. 

Automating Mathematicians

The New York Times published an article with the ominous title A.I. Is Coming for Mathematics, Too. We know by the work of Gödel and Turing that we can't automate mathematics. But can we automate mathematicians? Is AI coming for us?

Reading the article I'm not immediately scared. The focus is on logical systems like like the Lean theorem prover and SAT solvers. 

Developed at Microsoft by Leonardo de Moura, a computer scientist now with Amazon, Lean uses automated reasoning, which is powered by what is known as good old-fashioned artificial intelligence, or GOFAI — symbolic A.I., inspired by logic. So far the Lean community has verified an intriguing theorem about turning a sphere inside out as well as a pivotal theorem in a scheme for unifying mathematical realms, among other gambits.

So Lean is being used mainly to logically verify known theorems. This could actually make life harder for mathematicians, if journals start requiring formal verification for submitted papers.

I'd love a higher-level AI. One that takes a journal-style proof and verifies it, or even better takes a proof sketch and fills in the details (and write it up in LaTeX) . In other words, let me think of high level ideas and leave the messiness to AI. 

I'm won't be holding my breath. Right now, generative AI has limits in its ability to reason, and reasoning is at the heart of mathematics. 

On the other hand, AI now plays a mean game of chess and go, which we also think of reasoning. So maybe automating mathematicians is closer than we think. It might go further and start suggesting new theorems and proving them on their own.

Ultimately like most other fields AI won't eliminate the need for mathematicians. But like nearly every career moving forward, those who will succeed will not be the ones that push back on AI but those who work smarter and harder to use AI as a tool to do even greater things. Best to think about how to do that now before it's too late.

Chernoff Turns 100

Guest post by Ravi Boppana

Herman Chernoff celebrates a milestone today: he turns 100 years old. 

We in theoretical computer science know Professor Chernoff primarily for his ubiquitous Chernoff bounds.  The Chernoff bound is an exponentially small upper bound on the tail of a random variable, in terms of its moment generating function.  This bound is particularly useful for the sum of independent random variables.   

Many, many results in theoretical computer science use Chernoff bounds.  For one set of examples, Chernoff bounds are employed in the analysis of algorithms such as Quicksort, linear probing in hashing, MinHash, and a randomized algorithm for set balancing.  For another example, Chernoff bounds are used to reduce the error probability in complexity classes such as BPP.  These examples merely scratch the surface of the wide-ranging impact that Chernoff bounds have had. 

Professor Chernoff introduced the Chernoff bound in his seminal paper from 1952.  Chernoff credits another Herman (Herman Rubin) for the elegant proof of the bound in this paper.  Similar bounds had been established earlier by Bernstein and by Cramér. 

In his distinguished career, Chernoff was a professor for decades at Stanford, MIT, and ultimately Harvard.  In May, Harvard proudly hosted a symposium in honor of Professor Chernoff's centenary, which he attended.  The photo above shows him at the symposium, looking as cheerful as ever (photo credit: Professor Sally Thurston). 

Beyond his remarkable research accomplishments, Professor Chernoff has passionately guided an entire generation of exceptional statisticians.  According to the Mathematical Genealogy Project, he has advised 26 PhD students, leading to a lineage of 288 mathematical descendants.  Chernoff himself earned his PhD at Brown University in 1948 under the supervision of Abraham Wald.  

Professor Chernoff and his wife, Judy Chernoff, have been married for more than 75 years.  A Boston TV news story said that the Chernoffs are believed to be the oldest living couple in Massachusetts.  At the symposium in May, Professor Chernoff doubted the claim, though he had previously acknowledged that it might be true.  Maybe his cherished field of statistics can be used to estimate the likelihood of the claim.   

On this extraordinary milestone day, we extend our heartfelt congratulations and warmest wishes to Professor Chernoff.  Happy 100th birthday, Professor Chernoff!  Mazel tov. 

Can you put n pennies on an n x n chessboard so that all of the distances are distinct/how to look that up?

 In Jan 2023 I went to the Joint Math Meeting of the AMS and the MAA and took notes on things to look up later. In one of the talks they discussed a problem and indicated that the answer was known, but did not give a reference or a proof. I emailed the authors and got no response. I tried to search the web but could not find it. SO I use this blog post to see if someone either knows the reference or can solve it outright, and either leave the answer in the comments, point to a paper that has the answer in the comments, or email me personally. 

--------------------------------------------------------------------

A chessboard has squares that are 1 by 1. 

Pennies have diameter 1.

QUESTION: 

For which n is there a way to place n pennies on squares of the n x n chessboard so that all of the distances between centers of the pennies are DIFFERENT?

-----------------------------------------------------------

I have figured out that you CAN do this for n=3,4,5. I THINK the talk said  it cannot be done for n=6. If  you know or find a proof or disproof then please tell me. I am looking for human-readable proofs, not computer proofs.  Similar for higher n.

I have a writeup of the n=3,4,5 cases here (ADDED LATER- I will edit this later in light of the very interesting comments made on this blog entry.) 

----------------------------------------------------------------------

With technology and search engines it SHOULD be easier to find out answers to questions then it was in a prior era. And I think it is. But there are times when you are still better off asking  someone, or in my case blog about it, to find the answer. Here is hoping it works!

ADDED LATER: Within 30 minutes of posting this one of my readers wrote a program and found tha tyou CAN do it for n=6 and gives the answer. Another commenter pointed to a website with the related quetion of putting as many pawns as you can on an 8x8 board.

ADDED LATER: There are now comments on the blog pointing to the FULL SOLUTION to the problem, which one can find here. In summary: 

for n=3,...,7  there IS a way to put n pennies on a chessboard such that all distances are distinct.

for n=8,...,14 a computer search shows that there is no such way.

for n=15 there is an INTERESTING PROOF that there is no such way (good thing - the computer program had not halted yet. I do not know if it every did.) 

for n\ge 16 there is a NICE proof that there IS such way. 

I am ECSTATIC!- I wanted to know the answer and now I do and its easy to understand!

Don't Negotiate with Logic

Computer science and mathematicians often try to use logic to negotiate whether it be at a university or life in general. I've tried it myself and it doesn't usually work. Even if you have that (rare) perfect argument, remember Upton Sinclair's words: It is difficult to get a man to understand something, when his salary depends on his not understanding it.

So make sure their salary depends on them understanding it. Or more to the point, in a world with limited resources, why it makes sense for them to help you. 

1. Ideally go for the win-win. Why a certain decision helps the department/college/university as well as yourself. Asking for a small investment as a seed towards a large grant for example.
2. How would the decision make you or your students more successful? The success of a department is measured by the success of the faculty and students. On the other hand, why would a different decision hold you and your students back.

Even outside the university, make your objectives in line with the objectives of the person you are negotiating with to lead to a better outcome.

Of course sometimes you are haggling over a price or a salary when it really is a zero-sum game. There it's good to know the BATNA, Best Alternative To a Negotiated Agreement, for yourself and the other entity. In other words, if they aren't selling to you what other options do you and they have?

There are whole books written about negotiating strategies. Mostly it comes down to making it work for both parties. That's what matters, not the logic.

Ted Kaczynski was at one time the worlds most famous living mathematician

(This post is inspired by the death of Ted Kaczynski who died on June 10, 2023.) 

From 1978 until 1995 23 mailbombs were sent to various people. 3 caused deaths, the rest caused injuries. The culprit was nicknamed The Unabomber (I wonder if he liked that nickname.) For more on his story see here.

The culprit was Ted Kaczynski. He had a BS in Math from Harvard in Mathematics in 1962, and a PhD in Math from The Univ of Michigan in 1967. He got a job in the Berkeley math dept but resigned in 1969. He soon thereafter moved to a shack in the woods (I wonder if his prison accommodations were better) and began sending out the mailbombs. 

When he was caught in 1995 he was (a) famous and (b) a mathematician. That last point is debatable in that I doubt he was doing math while living in his shack. But we will ignore that point for now. Would you call him a famous mathematician? If so then he was, in 1995, the most famous living mathematician. 

In  1995 Andrew Wiles proved Fermat's Last theorem (this is not quite right- there was a bug and it was fixed with help from Richard Taylor) and he was, for a brief time, the world's most famous living mathematician, though perhaps Wiles and Kaczinski were tied. Wiles made People magazine's 25 most intriguing people of the year! (NOTE- I originally had, incorrectly that Wiles had proven it in 1986. A comment alerted me to the error which makes the story MORE interesting since Ted and Andrew were competing for Most Famous Living Mathemticians!)

Terry Tao won the Fields medal (2006) AND the MacArthur Genius award (2006) AND the breakthrough award (2015). The last one got him a spot on  The Colbert Report (2014) (See here,) For those 15 minutes he might have been the most famous living mathematician. He did not have much competition for the honor.  

And then there is Grigori Perelman who solved the Ponicare Conjecture and declined the Fields Medal and the Millennium prize (Colbert commented on this, see here.) For a very brief time Perelman may have been the most famous living mathematician. He did not have much competition for the honor. 

The most famous mathematicians of all time: Pythagoras of Samos, Euclid, Lewis Carroll. 

1) Pythagoras might not count since its not clear how much he had to do with his theorem.

2) Lewis Carroll is the most interesting case. He IS famous. He DID do Mathematics. He DID mathematics while he wrote the books that made him famous. So he is a famous mathematician but he is not famous for his math. But that does not quite seem right. 

3) The Math version of AND and the English version of AND are different. Lewis Carroll is FAMOUS and Lewis Caroll is A MATHEMATICIAN but it doesn't seem quite right to call him a FAMOUS MATHEMATICIAN. Same for Ted K.  Andrew W was, for a short time, a legit FAMOUS MATHEMATICIAN. 

3) Stephen Hawkings has appeared on ST:TNG and his voice on The Simpsons, Futurama, The Big Bang Theory. He is famous for a combination of his disability, his expository work, and his Physics. Is he a famous actor? 

4) Science expositors like Carl Sagan and Neil deGrasse Tyson are famous for being expositors of science, not quite for their science. How do Professor Proton and Bill Nye the Science Guy fit into this?

5) Looking at Ted K, Andrew W, Terry T, Grigori P one other point comes up: All of them were famous for a short time but it faded QUICKLY. So- fame is fleeting!

Randomized Acceptances

NeurIPS recently released their 2021 consistency report, a sequel to the 2014 experiment. While the conference has grown dramatically, the results remain "consistent", about 23% disagreement from two separated program committee groups. As before I don't find this too surprising--different committee members have different tastes.

Roughly conference submissions fall into three categories

1. Clearly strong papers
2. Clear rejects
3. A bunch that could go either way.

A typical program committee quickly sorts out the first two groups and then painfully spends considerable time arguing over the others.

What if instead we took a different approach. Accept all the strong papers and reject the weak ones. Choose the rest randomly, either with a uniform or weighted distribution based on the ranking. Maybe reduce the probability of those who submit multiple papers.

Choosing randomly reduces biases and can increase diversity, if there is diversity in submissions. Knowing there is randomness in the process allows those with rejected papers to blame the randomness and those whose papers gets in claim they were in the first group. Randomness encourages more submissions and is fair over time.

Note we're just acknowledging the randomness in the process instead of pretending there is a perfect linear order to the papers that only a lengthy program committee discussion can suss out.

We should do the same for grant proposals--all worthy proposals should get a chance to be funded.

I doubt any of this will ever happen. People would rather trust human decisions with all their inconsistencies over pure randomness. 

Posting a book online with a password- that you broadcast.

 Recently Lance, at the request of  Vijay Vazirani, tweeted the following (I paraphrase)

---------------------------------------------------------------------------------------

Online and Matching-based Market Design book now available as free PDF 

cambridge.org/files/9216/848  

The password is OMBMD_CUP

---------------------------------------------------------------------------------------------

This tweet raises two questions.

1) When a book is put online, does it cut into sales? I've heard that people still like paper so the posting on line might be like an ad for the book. Also, for academic books, the authors WANT it to be out there and don't care so much about sales.  If Gasarch & Martin's Bounded Queries in Recursion Theory was available for illegal download I would be delighted. And surprised. 

2) SO, they post it to make it more available and generate buzz. So why have a password? Was this a compromise: 

a) We want people to BUY the book so we'll post it with a password and limit access. 

b) We want people to SEE the book since as academics we don't care about sales, and it might generate buzz, so we don't want a password

c) COMPROMISE: Have a password but tell everyone what it is. 

If you can think of a more plausible scenario, leave a comment.