Finding and answer to a math question: 1983 vs 2023.

In 1983, as a grad student, I knew that HALT \( \le_T \) KOLG but didn't know how to prove it. I asked around and A MONTH later through a series of connections I got the proof from Peter Gacs.

 See here  for the full story and see here for a write up of the proof

In 2023, as professor, I heard about a pennies-on-a-chessboard problem and wanted to know what was known about it. I blogged about it and AN HOUR later I found what I wanted. 

See here for my blog post asking about and see here for my write up of all that's known. 

Why the difference from a MONTH to an HOUR. 

1) In 1983 there was no Google. I don't recall if there were other search engines, but even if there were there wasn't much to search. I do note that in 2023 Googling did not help me, though it may have helped my readers who pointed me to the information I wanted. 

2) In 1983 email wasn't even that common. So the notion of  just email such-and-such for the answer did not occur to me. (Also note that I am a last-blocker, see here.) 

3) Here is a factor that should have been in my favor: the community of theorists was smaller so we kind of knew each other and knew who was doing what. AH- but who is this  we ? I started at Harvard in 1980 but really only began doing theory in 1981 and didn't really know the players yet. However, I think the smallness of the community DID help Mihai Gereb (a grad student at Harvard) to know to contact Peter Gacs to help  me find the proof. Contrast- today the community is so large that I might not know the players (I didn't for the penny-chess problem) though with email and the blog (next item) I can reach out to people who Do know the players.

4) The Blog- I have the ability to ASK several people at one time, and one of them might know. That worked in this case and in other cases, but it does not always work. 

5) People without a blog can do something close to what I did- ask several people. And that can be more targeted. (ADDED LATER- a commenter pointed out that I should point out that Math Overflow and Stack exchange and sites like that are also options. Often when I Google a question I have been taken to those sites. I have had less luck asking them directly, but that could just be me.) 

QUESTION: Is it easier to find things out NOW or 40 years ago? I think NOW by far, but I do see some possibly counterarguments. There is a balance- there were less places to look back then. Indeed, the answer to my question was NOT a journal article or a conference paper, it was another blog.

Lastly THANKS to my readers for pointing me to the sources I needed! Kudos! 

ADDED  LATER -a link to the Erdos-Guy paper that I need to put here to aid one of my comments is here

 

Whither Twitter

Twitter tells me it's my twitterversary, 15 years since I first started tweeting. Not sure I'll make it to sweet sixteen.

No longer do tweets show up on this blog page. Twitter can't tell the difference between some AI engine slurping up tweets and their own display widget showing tweets on a weblog. Bill complains that he can no longer follow my Twitter as he refuses to set up an account on the site and you can't read tweets without one. Also I will soon lose access to TweetDeck without paying the $8/month that wouldn't solve the other problems. This is ignoring that fact that since Elon has taken over Twitter, the site has just become far less fun.

I have accounts on Mastodon and now Threads. The two combined have less that 100 followers compared to the 5400 I have on Twitter. Not sure how many of those 5400 are bots or people who no longer read twitter regularly. 

For now my tweets get imported into Mastodon which now appear on this blog page. Eventually once Threads gets proper web support and APIs I expect that will become the new twitter and I'll move there. We'll have to see.

A further 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. 

Quantifiers: To Parenthesize or not to Parenthesize? Matrix of Formula: To Bracket or not to Bracket?

 For the book 

Computational  Intractability: A Guide to Algorithmic Lower Bounds

by Demaine-Gasarch-Hajiaghayi 

(See  here for a link to a first draft.) 

we had to make some choices about which notation to use. One of the least important ones was the following: 

When defining NP, and in a few other places should we use: 

                                                  (\exists y)(\forall y)[B(x,y)]

or 

                                                   \exists x : \forall y : B(x,y)

or 

                                                    something else.

We ended up doing it the second way.  But I wondered, which, if either, is standard. So I looked in many math and theoretical CS books looking for places they used quantifiers. Here is what I found

a) Most papers and books really don't use quantifiers at all!  This surprised me. 

b) When quantifiers are used, they are used in definitions, not theorems. 

c) One exception is in logic when they deal with formulas as objects onto themselves.  For example, the inductive definition of a formula will have a step:

                       If f(x_1,...,x_n) is a formula then (\exists x_i)[f(x_1,...,x_n)] is a formula. 

d) Here is a list of the few places I saw quantifiers used and if they used parenthesis or not. I say if it has parenthesis (abbreviated Parens)  or not, and if the matrix of the formula is in square brackets, no brackets, or something ese. 

Cook's classic paper . Page 154 Parens, no Brackets (1971) 

Stockmeyer's paper where he defines PH.  Page 6 Parens and Brackets  (1976)

Computers and Intractability by Garey & Johnson. Page 164. Parens and Brackets (1979)

Morass-like construction of aleph_2 trees in L by Devlin.  Page 2 Parens and matrix in Parens (1979)

Descriptive Complexity by Immerman. Page 38 Parens no Brackets (1999) 

Bounded Queries in Recursion Theory by Gasarch and Martin. Parens and Brackets  Throughout the book.  (1999)

Complexity Theory from Godel to Feynman by Rudich. No Parens, No Brackets in Def of PH. (2003) 

Parameterized Complexity Theory by Flum & Grohe. Page 81 no Parens and no Brackets. 

Computational Complexity: A Modern Approach by Arora & Barak. Page 40. No Parens No Brackets.(2007) 

Computational Complexity: A Conceptual Prospective by Goldreich.  Page 114 no parents, no brackets (2008) 

On Quantifer Rank Equivalence between linear orders by Siders. On page 417 they use quantifiers to state a theorem, which is unusual. Parens no brackets.

Presburger arithmetic, Rational Generating Functions, and quasi polynomials by Woods. Parens no  Brackets. (2012) 

Who witness's the Witness by Abel et al. On Page 69 (which the pointer takes you to) No Parens, no brackets. Colons between quantifiers (2018).

e) What to make of all this?

First off- the RARITY of the use of quantifiers really surprised me. The only place I saw them used a lot was my book, co-authored with Georgie Martin,  Bounded Queries in Recursion Theory. Perhaps it would have sold better if I didn't use so many quantifiers. Oh well. 

Second off- Later works don't use parens and brackets. This is most clear if you just look at Complexity Theory Books 

Garey & Johnson - 1979- parens and brackets

Flun & Grohe- 1998- no parens and no brackts

Immerman- 1999 - parens but no brackets (this is the one exception) 

Arora & Barack- 2007 no parens and  no brackets

Goldreich-2008- no parens and no brackets

If you have a complexity theory book around that is not on this list, look up the definition of NP and the definition of the Poly Hierarchy and see (a) if they use parens around the quantifiers, and (b) if they use square brackets or no brackets of something else. Please leave a comment about it so I test the conjecture that parenthesis are just so 1979. 

On Nov 10, 2014 the TV show Scorpion mentions Software that is like ChatGPT for Music

Scorpion is a TV show that ran from 2014 to 2018. It involves a group of brilliant (to say the least) but socially awkward (to say the least) people who help the government battle threats and/or solve crimes. 

The episode Risky Business aired on Nov 10, 2014 (episode 8). 

In the episode someone wrote a program that (in todays terminology) scrapes the web for all pop songs that were hits for the last 50 years and creates hits that share those properties and hence will be popular. And it works! 

1) The episode says that if the fans of group X find out that they didn't create their own music, but its computer generated, then sales will drop. This may be true but I am not quite sure WHY its true. If I LIKE  listening to a song, I will still like it even if I know it was computer generated. 

2) While they didn't go into any detail about what the program does, it SOUNDS a lot like ChatGPT to me. 

3) Could ChatGPT do that now? Has it already? Lance happened to read an earlier version of this post and emailed me a link which says this is already happening to some extent. The link is here but might be behind a paywall. (Note- My spellchecker DOES think paywall is a word. Yeah! It also thinks that spellchecker is a word. Yeah!)

4) Is it impressive that the shows writers predicted this kind of technology way back in 2014? 

5) In the real world would someone be murdered because they are going to reveal that group X's songs were not authentic? Either TV has far more murders than the real world OR on TV they just get caught more often. I would like to think that TV has far more murders (see here). It certainly has far more interesting murders. 

Finding Primes Pseudodeterministically

In 2003, Agrawal, Kayal and Saxena showed that primality testing is in P, i.e., you could test for primes without using any randomness.

What if you want to find a prime? Specifically given a number m in binary, can you find a prime p > m in time polynomial in the length of m. In 2009 I posted about a polymath project to find a deterministic algorithm for finding primes and the problem remains open today. 

Likely you could just try m+1,m+2, ... until you find a prime but whether that is bounded by a polynomial number of steps is a big open question in number theory. You can choose random numbers between m and 2m and find one in expected polytime given the prime number theorem. This algorithm will likely output a different prime every time you run it.

There's a new paper by Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren and Rahul Santhanam that solves this problem pseudodeterministically for infinitely many inputs. This is a randomized polynomial-time algorithm B that for infinitely many n, there is a specific prime p between 2ⁿ and 2ⁿ⁺¹ such that B(1ⁿ) outputs p with high probability. With high probability you will get the same prime every time you run the algorithm!

The proof uses a win-win kind of argument, if a certain algorithm fails to work you can use that to derandomize. Making that argument work requires bootstrapping on variants of previous pseudorandom generator and hitting sets constructions. 

Almost surely there is a deterministic polytime algorithm for finding primes. But for now the new result of Chen et al. is a nice stop in that direction. 

Logic and lack of Logic of Anti Vaxers

I wrote the  post below the dotted line a long time ago but never got around to posting it. Now that 

                                        WHO says COVID emergency is over.

(When I first saw I misread it as a question: 

                                        Who says COVID emergency is over? 

) 

I decided to post it (with one update that has an ADDED LATER on it). 

If you didn't know , WHO is World Health Organization. Actually, that is true whether or not you know it.

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

Some of the reasons anti-vaxers give are better than others. Some are consistent, some are not. 

We list some of them and invite the comments to list more. Our point is- which ones have something interesting to say? 

I am PRO VAX but I often seek out intelligent opposing views on any of my opinions. Did I find any here? I leave that as an exercise for the reader. 

Reasons anti-vaxxers give or could give. 

a) FREEDOM! That's not quite a reason. I am reminded of asking a neighbor why he flies a confederate flag and he said

FREEDOM!

I was hoping he would say either

To honor my great grandfather who died for the south in the civil war.

or

Because I don't like black people.

or

To honor those many people, black and white, who died in the civil war fighting for the south. 

or

SOMETHING with content to it. 

Any of those answered would tell me something could be discussed. Just the word FREEDOM does not. 

b) Bill Gates put microchips in the vaccine so he can keep track of where you are. Why? Bill Gates and Mark Zuckerberg can ALREADY keep track of where you are. I do wonder if this is a common anti-vax viewpoint or if its VERY RARE and the media plays it up to make anti-vaxers look stupid. Same with the notion that the vaccine makes you magnetic (that sounds cool!)

c) I want to wait and see its effects since it was rushed out. That might have made sense  X months ago, but by now its very well established.

d) I haven't gotten around to it yet. These are a very good target for the mandates or at least to be talked into doing it. It may be more fun to talk about the radical anti-vaxers; however, if the haven't gotten around to it group all got vaccinated we would be closer to herd immunity.

e) I've got COVID so I am immune. This is true for Y months (I am not sure what Y is); however, the person I know who told me this had COVID about 3 years ago.  But at least its an attempt at an argument. 

f) The medical community has been bad to (i) me, (ii) my people, (iii) some other people that I care about hence I do not trust them. The premise is actually true, so this is an attempt at an intelligent argument. 

g) Big Pharma is making a mint on this and ripping us off. This is a view of, not the extreme left but the fringe left. Robert Kennedy is a big voice here, see here. On a right-wing relatives' urging I listened to an hour-long interview with him. Mostly a rambling incoherent argument. Much of it was anti-business which got no pushback from the usually-pro-business republican's. Are there any mainstream democrats who are anti-vax? I do not think so. Also, is it true that Big Pharma is is making a mint? Ripping us off? Ripping someone off? This could be an interesting question if asked more coherently. But its not a good reason to be anti-vax. 

h) Trump said it was a hoax to get him out of office. Taking a vaccine now would be to admit its not a hoax. Such people should take Karl Popper's view of science: Conjecture that, as Ted Cruz said, if Biden wins then COVID will go away since it was a hoax made up to get Biden to win. If Biden wins and COVID does not go away then you must reject your conjecture. (ADDED LATER: Odd point- Trump has sometimes said, though not lately, that people should get the Vax that HE invented. If we called it a Trumpzine then would people take it? As of now Trump and DeathSantos are trying to anti-vax each other.) 

i) The first few days after you take it it hurts and you feel tired or get chills or other reactions. This is actually true, though one has to balance that against getting COVID.

j) The Ford Administration really messed up on the Swine Flu so why trust the government now? This is true- The Ford Admin DID mess up. Oddly enough, I have never (or perhaps rarely) heard this as a reason. This puzzles me- Why claim Bill Gates microchip stuff (which is absurd) or Vax causes autism (debunked)  and  NOT use arguments are are more reasonable?

k) Vaccines cause autism. That study was debunked a long time ago, but it still lives on.

l) Kamala Harris said she was hesitant since it was rushed.  I've only heard this one as Republicans  try to blame her for Vaccine Hesitancy. The problem with that argument is that you are claiming that the anti-vaxers, who are mostly republicans, are listening to Kamala Harris for advice.

l) If many people get Vaxed and COVID goes away then Biden will look good, and we can't have that.

m) COVID was invented by the Chinese to cripple us. Uh- even if true (which it is not, though the leaked lab hypothesis might be) that's a reason to TAKE it to thwart their plans. For that matter, Trump could have been Trumpian and PRO-MASK and  PRO-VAX by blaming the Chinese and George Soros and the Deep State and Biden and Obama and of course Hillary,  but using this to say WEAR THE MASK! TAKE THE VAX! to DEFEAT these ENEMIES who want to destroy America. Would that have worked to slow the spread of COVID? If so then would he have won re-election? 

Community Guidelines that Ignore History

Last week I got the following email from Blogger:

As you may know, our Community Guidelines (https://blogger.com/go/contentpolicy) describe the boundaries for what we allow-- and don't allow-- on Blogger. Your post titled "Mysteries of the Seventies" was flagged to us for review. This post was put behind a warning for readers because it contains sensitive content; the post is visible at http://blog.computationalcomplexity.org/2005/06/mysteries-of-seventies.html. Your blog readers must acknowledge the warning before being able to read the post/blog.

So let me describe what happened carefully so this post doesn't also get flagged. First a history lesson. In 1972, five men were arrested for breaking into the Democratic National Committee (DNC) headquarters at the Watergate complex in Washington, D.C. They were found with bugging devices and cameras, attempting to wiretap the DNC offices. One of them had ties to the Committee to Re-Elect the President (CREEP), which supported Richard Nixon's re-election campaign.

Two Washington Post reporters, Bob Woodward and Carl Bernstein, broke the story of the coverup that would eventually lead to Nixon's resignation in 1974. I highly recommend both the book and the film All the President's Men about their investigation. Woodward and Bernstein got help from a then anonymous source. The identity of the source was subject to huge speculation and remained a mystery for three decades. In 2005 Mark Felt, associate director of the FBI, outed himself as the source.

After the announcement I wrote a short post (would have been a tweet today) mentioning that while we learned the solution of one mystery from the 1970s, another remained.

So why was this post flagged as sensitive eighteen years later? Because I used the pseudonym the Washington Post reporters gave to Mark Felt, a title from a popular adult movie at the time. 

Take a number and map it to the number of letters in its name

Let f: N--> N map a number to the number-of-letters in its name in English (we will consider other languages later).

So for example 14 is fourteen so it maps to 7. Let's iterate

14 --> 7 --> 5 --> 4-->4-->4 ...

It is known (perhaps well-known) that, given any starting point, the sequence eventually is all 4's. 

I recently got an email asking if this was PROVEN.  I could not find a proof on the web so I did it myself. My writeup of a proof is here. 

1) So now there IS a proof on the web. It may be hard to find. Does this problem have a well known name that I should add to this blog post so that it is easier to find?

2) My next thought was

For which functions f: N-->N is it the case that every sequence a, f(a), f(f(a)), ... is eventually constant. I leave that for you to ponder.

3) The asker of the question is of a more real-world bent and emailed me what happens in other languages:

Spanish has one number whose name is its own length: 5 is cinco. I leave it to the reader to show that in Spanish the sequence always becomes all 5's. (NOTE- a commenter says NO, you an have a 4-6 cycle. Cool!) 

French seems to have no such numbers, so it cannot have this behavior.

Norwegian has three such numbers: 2 is to, 3 is tre, 4 is fire. So I suspect every such sequence either is constant-2, constant-3 or contant-4.

See this article here for more the numbers 1-10 in several languages.

OBLIGATORY ChatGpt note: Lance saw this post in our blog account and was curious what ChatGpt would do with it. For what he got see here. You can decide if a program can take over the blog anytime soon. 

Winter is Coming

I fear we are heading to a computer science winter. Now why would I say that when CS enrollments are at record levels and AI is driving incredible excitement in the field? Back in 2016 I wrote

We won’t see a decline in demand for computer science students until we automate ourselves out of a job.

With advances in machine learning, especially generative AI, you can now use AI tools with little to no knowledge of computer science and mathematics. You can do quite a bit more with just a basic knowledge of Python programming and APIs. And tools like Github co-pilot make programming that much easier.

In 2005 during the last period computer science saw small enrollments, I suggested computing became a commodity and we lost the excitement in the field, leading to a decrease of interest and students. It didn't help that potential students had a (mostly mistaken) perception that all the computing jobs were being outsourced to India.

We may soon see a time when computing loses its excitement again if everyone can just interact in English (or any other language). Students might now have a perception that computing jobs will be outsourced to AI. The recent tech layoffs don't help. Even the ones interested in computing might focus more on the various low-cost certificate programs instead of a full CS degree.

What can we do? We need to reframe our degrees or create new ones to recognize the move to data-oriented computing. We need to embrace teaching responsible AI but without fighting the future. 

CS is in a great place right now but we have to continually adjust to ensure our future relevance or we may no longer have it.

Other Ramsey's

 I often Google Ramsey stuff to find something. I often end up back on my own collection of Ramsey theory  papers. But I sometimes find OTHER uses of the phrase  Ramsey. 

To tell these Ramsey's apart we will call the math Ramsey guy Frank Ramsey since that was his name. 

1) Frank's brother Arthur Michael Ramsey (usually just Michael Ramsey). He was the Archbishop of Canterbury from 1961 until 1974.   He was ahead of his time in being Ecumenical and supporting women clergy. His Wikipedia page is here. 

2) The Ramsey Effect. Aaron Ramsey is a football player (what Americans call Soccer). There were four time when he scored a goal and soon after an important person died. This was dubbed The Ramsey Effect. This is of course silly, and if he asked Frank about the probabilities (unlikely-Frank died in the 1930's and Aaron was born in 1990) I am sure Frank would tell you that four is too small a number to make anything out of this. The Ramsey Effect is discussed here. There is no Wikipedia page about it, and I found it by accident so, as the kids say, its NOT a think. 

3) Jon Bennett Ramsey. A girl who was murdered when she was six. Case still unsolved. See the Wikipedia page on this here.

4) First name Ramsey: here. The only one I had heard of is Ramsey Clark.

5) Last name Ramsey: here. Lots of people! Most I had not heard of. 

(With regard to 4 and 5: there are so many famous people you can't have heard of all of them)

6) For more Ramsey Stuff see here

Breaking Ground in Isomorphism Testing: A Leap Forward for a Bottleneck Case of Group Isomorphism

Guest post by Josh Grochow and Youming Qiao

There has, quietly, been somewhat of a breakthrough in isomorphism testing. No, not as big as Babai's 2016 Graph Isomorphism in Quasipolynomial Time. But a first foothold in climbing a wall for which no one had gotten much off the ground before. The result, due to Xiaorui Sun in this year's STOC, is an algorithm for testing isomorphism of a certain class of groups - p-groups of class 2 and exponent p if you must know, but we'll get to that - in time \(n^{O(\log^{5/6} n)}\) where n is the order of the group. To understand why we're excited about this we have to tell a bit of a story. 

In the 1970s, when Graph Isomorphism was still a mystery, people also thought more widely about isomorphism testing of other combinatorial and algebraic structures. For finite groups of order n, Robert Tarjan realized that there is an \(n^{\log n+O(1)}\)-time algorithm, simply because a group of order n has a generating set of size \(\log n\). This observation was recorded by Gary Miller in a paper in STOC'78, and independently realized by Felsch and Neubüser. A natural question is then whether Group Isomorphism can be solved in time poly(n) where n is the group order.

Not only is this question natural from the perspective of studying groups computationally, it is also natural from the perspective of Graph Isomorphism. For Group Isomorphism reduces to Graph Isomorphism in polynomial-time (as does the isomorphism problem for any finite algebraic or relational structure, see Zemlyachenko, Korneenko, & Tyshkevich). While this has been known for a long time, Babai’s result on Graph Isomorphism brings the running times quite close: \(n^{O(\log^2 n)}\) for graphs, and \(n^{O(\log n)}\) for groups. So not only does Group Isomorphism stand in the way of getting Graph Isomorphism into P, but in our current state of knowledge, it even stands in the way of shaving off more than a single log in the exponent of the runtime.

Since the general Group Isomorphism problem seems difficult, attention turned to special classes of groups. It was not hard to see that isomorphism of Abelian groups could be computed in polynomial time. However, a group class that is just “one step away” from Abelian - groups G where, when you mod out by the center Z(G), what’s left is Abelian -  turned out to be difficult. Such groups are called class-2 nilpotent, and in one sense, their  group-theoretic structure is relatively straightforward: both G/Z(G) and Z(G) are Abelian. Yet, to devise an efficient isomorphism testing procedure turned out to be extremely difficult (see e.g. Garzon-Zalcstein, Rosenbaum-Wagner, O’Brien, Wilson), to the point that this is usually considered as a bottleneck for putting Group Isomorphism in P. 

Among class-2 nilpotent groups, the “key case” to resolve is widely believed, for several reasons, to be p-groups of class 2 and exponent p. In such groups, both the center Z(G) and quotient G/Z(G) are elementary abelian, i.e., of the form \((Z_p)^d\). Despite having an even simpler group-theoretic structure, this group class still turns out to be difficult! For a long time, the asymptotic growth of the exponent of the runtime for solving this restricted problem has not improved over the \(n^{\log n+O(1)}\)-time algorithm, which works for all groups.¹

Xiaorui Sun’s result represents the first substantial improvement, cracking open this decades-old quest. His algorithm runs in time \(n^{O(\log^{5/6} n)}\), and its techniques are indeed novel. The starting point of this algorithm is to consider the following equivalent problem in (multi)linear algebra: let \(f, g:Z_p^d \times Z_p^d \rightarrow Z_p^e\) be two skew-symmetric bilinear maps. Do there exist change of bases A in \(GL(d, p)\) and B in \(GL(e, p)\), such that for all \(u, v\) in \(Z_p^d\), \(f(A(u), A(v))=B(g(u, v))\)?

Baer’s Correspondence sets up an equivalence of categories between p-groups of class 2 and exponent p, and skew-symmetric bilinear maps over \(Z_p\). This viewpoint allows Xiaorui to use multilinear algebra to study the structure of these bilinear maps. He also crucially depends on a result of Ivanyos and Qiao, which built on Wilson’s use of involutive algebras in this context. He also uses the individualization-and-refinement technique (but for matrix spaces, not graphs!), a characterization of spaces of matrices of low rank, and reducing a tensor to a “semi-canonical” form part of which is somewhat reminiscent of the Tucker decomposition.

All this results in an algorithm which solves the above problem on bilinear maps in time \(p^{(d+e)^{1.8} \log p}\). For groups of order \(p^n\) with \(\log_p(n)\) larger than \(\log^5 p\), Baer’s Correspondence then says that this algorithm does it; when \(\log_p n\) is smaller than \(log^5 p,\) he can fall back on the generator-enumerator algorithm, since the number of generators is at most \(log_p n\).

For us, who have been working on Group Isomorphism for more than a decade, Xiaorui’s result represents an exciting development on this classic algorithmic problem, and we look forward to seeing more progress in this direction in the near future. 

---

¹Rosenbaum & Wagner improved the exponent to \(\frac{1}{2}\log {p(n)} + O(1)\), and later improved to \(\frac{1}{4}\log {p(n)} + O(1)\) for all groups, see p.5 of Le Gall & Rosenbaum. In 2014, at a conference on Groups, Computation, and Geometry organized by Wilson, Brooksbank, Hulpke, Kantor, and Penttila, it was concluded that modern practical methods, such as those used in GAP and MAGMA, still take \(n^{O(\log n)}\) steps in the worst case.

There are an infinite number of proofs that there are an infinite number of primes

In the last few years there have been four papers that prove the primes are infinite using some number theory and some Ramsey Theory. The papers are:

Van der Waerden and the primes by Alpoge. See here or here.

Squares in arithmetic progression and infinitely many primes by Granville. See here or here.

Fermat's last theorem implies the infinitude of primes by Elsholtz. See here or here.

Fermat's last theorem, Schur's theorem (in Ramsey Theory), and the infinitude of the primes by Gasarch See here and here.

(I included the arxiv version and the doi pointer.)

We also note that

1) Mestrovic has collected up 183 proofs that the primes are infinite, see here. Some of them are similar so if you mod out by similarity you would get fewer proofs. How many you get depends on your criteria for similarity. This comment applies to other theorems that have many proofs. 

2) Quanta recently published an article about the fact that there are an so many proofs, though highlighting the four mentioned above. See here. (This might be behind a paywall.) 

This raises the obvious question:

Why are there so many proofs that the primes are infinite? 

Some thoughts

1) Which other theorems have many proofs?

a) The Pythagorean Theorem. See here for the claim that there are 371 proofs. There is a recent claim of a proof using trigonometry here (this was thought to be impossible since it would involve a circular argument). 

b) According to Wikipedia (see here) The law of quadratic reciprocity has 240  proofs.  This paper here has some of them. That paper also shows 

QR IMPLIES primes infinite.

 Actually more: QR IMPLIES  primes \(\equiv 4 \pmod 5\) is infinite.

c) \(\sqrt 2\) is irrational has many proofs. I can't find a clean reference that states there are many proofs---if you know one, leave a comment. Wikipedia (see here) has five proofs, though there are many more. 

d) There is a mathoverflow post about theorems with many proofs here. I had thought only easy theorems had many proofs; however, there are several hard ones on this list. 

2) Primes are so basic that many parts of math can be used to proof they are infinite.

3) WHY do people do these proofs? For the four papers listed above, and likely for many of the other proofs,  the proof that primes are infinite is  a springboard to other questions or concepts. We look at those four papers: 

a) Alpoge's showed Van Der Waerden's theorem and Unique factorization IMPLIES primes infinite. Alpoge didn't use this as a springboard to other questions, but is amused that VDW can be used to prove primes infinite. I will note that the proof made me realize (a)  the proof of Unique Factorization does NOT use that primes are infinite, and (b) ANY integral domain with Unique Factorization has an infinite number of primes. 

b) Granville's showed VDW's Theorem and also a result of Fermat that there cannot be four squares in arithmetic progression IMPLIES primes infinite. He then uses this as a springboard to talk  about other interactions between Ramsey Theory and Number Theory.  Let Q(N) be the max number of squares in arithmetic sequence of length N. Find upper and lower asy bounds on Q(N). From Szemeredi's theorem (which is part of Ramsey theory) Szemeredi himself showed that for all \(\delta>0, Q(N) < \delta N\). Granville's paper shows how to get this result from a corollary to Faltings theorem. He also notes that better is known: \(Q(N) < N^{3/5 + \epsilon}\). 

c) Elsholtz showed Schur's theorem (for all c there is an S=S(c) such that for all c-colorings of {1,...,S} there exists x,y,z the same color such that x+y=z) and FLT (the n=3 case or n=4 case) IMPLIES primes infinite. He then looks at various INFINITE Ramsey Theorems that imply the primes are infinite.

d) Gasarch's proof is identical to Elsholtz. He then looks at (1) for domains with a finite number of primes, what goes wrong? (2) when does the proof apply to other integral domains? The last question involves looking at variants of FLT some of which are open questions. 

4) Gasarch also wondered about the following (though its not in his paper). The four papers above, and also other proofs that the primes are infinite, are of the form 

A  IMPLIES Primes are infinite

Are we really using A? How to pin this down? Find a logical system L such that 

1) From L one can show A IMPLIES Primes are infinite

2) From L one CANNOT prove Primes are infinite. (You may need some hardness assumption)

One can also examine this kind of question for other theorems like sqrt(2) is irrational. 

I have shown this to several people and am told its not doable. Oh well. 

I had a prior blog on this, after I saw Alpoge's proof,  see here.

ADDED LATER: a commenter left a link to a math overflow page that has information on the reverse mathematics of Euclid's theorem that the primes are infinite. The link is here.

5) USUALLY mathematicians want to (or should want to) find EASIER proofs of HARD theorems. 

For some of the proofs that primes are infinite, QR, \(\sqrt 2\) irrational, some other theorems that have many proofs, mathematicians want to find HARD proofs of EASY theorems.