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 name take 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.