I reviewed a paper recently and I had to agree not to use AI in any aspect of the reviewing process. So I didn't but it felt strange, like I wouldn't be able to use a calculator to check calculations in a paper. Large language models aren't perfect but they've gotten very good and while we shouldn't trust them to find issues in a paper, they are certainly worth listening to. What we shouldn't do is have AI just write the review with little or no human oversight, and the journal wanted me to check the box probably to ensure I wouldn't just do that, though I'm sure some do and check the box anyway.
I've been playing with OpenAI's o3 model and color me impressed especially when it comes to complexity. It solves all my old homework problems and cuts through purported P v NP proofs like butter. I've tried it on some of my favorite open problems where it doesn't make new progress but it doesn't create fake proofs and does a good job giving the state of the art, some of which I didn't even know about beforehand.
We now have AI at the level of new graduate students. We should treat them as such. Sometimes we give grad students papers to review for conferences but we need to look over what they say afterwards, the same way we should treat these new AI systems. Just because o3 can't find a bug doesn't mean there isn't one. The analogy isn't perfect, we give students papers to review so they can learn the state of the art and become better critical thinkers, in addition to getting help in our reviews.
We do have a privacy issue. Most papers under review are not for public consumption and if uploaded into a large-language model they could become training data and be revealed if someone asks a relevant question. Ideally we should use a system that doesn't train on our inputs if we use AI for reviewing but both the probability of leakage and amount of damage is low, so I wouldn't worry too much about it.
If you are an author, have AI review your paper before you submit it. Make sure you ask AI to give you a critical review and make suggestions. Maybe in the future we'd required all submitted papers to be AI-certified. It would make the conference reviewers jobs less onerous.
For now, humans alone or AI alone is just not the best way to do conference reviews. For now when you do a review, working with an AI system as an assistant will lead to a stronger review. I suspect in the future, perhaps not that far, AI alone might do a better job. We're not there yet, but we're further than you'd probably expect.
In a recent post by Scott (see here or just read my post which includes his post) he listed topis that he conjectured would NOT cause an outrage.
I was going to write a long comment in his comments section, which would only be read by people who got to comment 100 or so. OR I could comment on it in my blog.
SO, here is his blog post and my comments on it.
------------------------------
A friend and I were discussing whether there’s anything I could possibly say, on this blog, in 2025, that wouldn’t provoke an outraged reaction from my commenters. So I started jotting down ideas. Let’s see how I did.
1) Pancakes are a delicious breakfast, especially with blueberries and maple syrup.
BILL: Pancakes have a terrible ratio of health to enjoyment.
2) Since it’s now Passover, and no pancakes for me this week, let me add: I think matzoh has been somewhat unfairly maligned. Of course it tastes like cardboard if you eat it plain, but it’s pretty tasty with butter, fruit preserves, tuna salad, egg salad, or chopped liver.
BILL: UNFAIRLY MALIGNED. That's an interesting concept in itself since there are so many opinions on the internet there is not really a consensus on.... anything. My 2 cents: I like the taste of cardboard and hence I like the taste of matzoh.
3) Central Texas is actually really nice in the springtime, with lush foliage and good weather for being outside.
BILL: I WILL DEFER to Scott, who is now a Texan, on this one.
4) Kittens are cute. So are puppies, although I’d go for kittens given the choice.
BILL: PETS are a waste of time and energy. My opinion shows something more important: Scott and I disagree on this but we are not OUTRAGED at each other.
5) Hamilton is a great musical—so much so that it’s become hard to think about the American Founding except as Lin-Manuel Miranda reimagined it, with rap battles in Washington’s cabinet and so forth. I’m glad I got to take my kids to see it last week, when it was in Austin (I hadn’t seen it since its pre-Broadway previews a decade ago). Two-hundred fifty years on, I hope America remembers its founding promise, and that Hamilton doesn’t turn out to be America’s eulogy.
BILL: Agree. Also lead to the best math novelty song of all time, See here.
6) The Simpsons and Futurama are hilarious.
BILL: The cliche The Simpsons was better in its first X seasons is true, but it can still crank out an excellent episode once in a while. The episode Treehouse of Horrors: Simpsons Wicked This Way Comes (from 2024--Wikipedia entry here) is a microcosm of the series: Two okay satires of two okay stories by Ray Bradbury and then a BRILLIANT satire of Fahrenheit 451. (Spell check thinks Treehouse is not a word .I looked it up to see what the geat God Google would say. The Treehouse of Horror episodes of the Simpsons use Treehouse. I googled Is Treehouse One word and got a YES. This is a rare time when spellcheck is just wrong.)
BILL: I think Futurama benefited from being on the air, then off, then on, then off, then on (is it on now?) since it came back with new stories.
7) Young Sheldon and The Big Bang Theory are unjustly maligned. They were about as good as any sitcoms can possibly be.
BILL: AGREE though again, some malign, some praise, some just watch it and laugh. I've had 5 blog posts inspired by these shows, and a few more that mention them in passing. I recently saw TBBT on a list of OVERRATED shows so someone must be liking it to cause it to be on that list.
BILL: In an earlier era it would be hard to watch every episode of a TV show since they were on once, and then maybe some reruns but maybe not. I've seen every episode of both TBBT and YS without even trying to.
BILL: (Added later inspired by a comment) For the entire run of the series YS the actress who played Missy, Raegan Revod did not have a Wikipedia page. I noted this in two prior blog posts. I am happy to say that she finally does, see here. It is a long overdue honor. (Is it an honor?)
8) For the most part, people should be free to live lives of their choosing, as long as they’re not harming others.
BILL: TRICKY- the For the most part causes arguments and outrage. Example: Helmet laws for motorcyclists. Should they be free to get brain injuries that the rest of society must pay for? I ask non-rhetorically as always.
9) The rapid progress of AI might be the most important thing that’s happened in my lifetime. There’s a huge range of plausible outcomes, from “merely another technological transformation like computing or the Internet” to “biggest thing since the appearance of multicellular life,” but in any case, we ought to proceed with caution and with the wider interests of humanity foremost in our minds.
BILL: I doubt it's the biggest thing since the appearance of multicellular life. My blog on AI here. I agree that caution is needed, though in two ways:
a) Programs are written that we don't understand and might be wrong in serious ways. (You can replace programs with other things.)
b) The shift in the job market may be disruptive. People point to that farmers stopped farming and moved to factory work, but there was an awful transition time. And the AI-shift might be much faster. Fortunately for me, ChatGPT is terrible at solving problems in Ramsey Theory. For now.
10) Research into curing cancer is great and should continue to be supported.
BILL: This one seems obvious but one has to ask the broader question: Which medical things should be funded and why? More generally, what should the government fund and why? These require careful thought.
11) The discoveries of NP-completeness, public-key encryption, zero-knowledge and probabilistically checkable proofs, and quantum computational speedups were milestones in the history of theoretical computer science, worthy of celebration.
BILL: Of course I agree. But the following questions haunt me:
a) What is a natural problem and do we spend too much time on unnatural ones. Even Graph Isom which seems like a natural problem does not have any applications (see my blog posts here and a ChatGPT generated post on this topic here).
b) Darling has asked me IF WE PROVE P NE NP THEN HOW WILL THAT HELP SOCIETY? Good question.
12) Katalin Karikó, who pioneered mRNA vaccines, is a heroine of humanity. We should figure out how to create more Katalin Karikós.
BILL: Cloning?
BILL: This raises the general question of how much ONE PERSON is responsible for great scientific discoveries.
13) Scientists spend too much of their time writing grant proposals, and not enough doing actual science. We should experiment with new institutions to fix this.
BILL: Also writing up papers and waiting for referees reports. A paper I submitted with students 3 years ago was accepted (Yeah) with many helpful comments (Yeah) but way too late to help those students get into grad school (they did anyway- Yeah). We had forgotten what we wrote and why we cared. (Boo) We did get the corrections done and resubmitted it. So I could say it will be out soon. But that's the weird thing-we posted it to arxivs three years ago so its been out for a while.
14) I wish California could build high-speed rail from LA to San Francisco. If California’s Democrats could show they could do this, it would be an electoral boon to Democrats nationally.
BILL: This seems fine but seems like an arbitrary thing to want as opposed to other pairs of cities and other achievement.
15) I wish the US could build clean energy, including wind, solar, and nuclear. Actually, more generally, we should do everything recommended in Derek Thompson and Ezra Klein’s phenomenal new book Abundance, which I just finished.
BILL: You inspired me to recommend the book Abundance to my book club. This is the second time that's happened- I also had them read the Stephen Pinker Book Enlightenment Now based on your blogs recommendation.
BILL: Some of the problem is political and some is technical. I don't know how much of each.
16) The great questions of philosophy—why does the universe exist? how does consciousness relate to the physical world? what grounds morality?—are worthy of respect, as primary drivers of human curiosity for millennia. Scientists and engineers should never sneer at these questions. All the same, I personally couldn’t spend my life on such questions: I also need small problems, ones where I can make definite progress.
BILL: Indeed-I like well defined questions that have answers, even if they are hard to answer. The questions you raise are above my pay grade.
17) Quantum physics, which turns 100 this year, is arguably the most metaphysical of all empirical discoveries. It’s worthy of returning to again and again in life, asking: but how could the world be that way? Is there a different angle that we missed?
BILL: I can either have an opinion on this or defer to one of the worlds leading authorities on the topic.
18) If I knew for sure that I could achieve Enlightenment, but only by meditating on a mountaintop for a decade, a further question would arise: is it worth it? Or would I rather spend that decade engaged with the world, with scientific problems and with other people?
BILL: If that enlightenment includes obtaining a proof that P NE NP then sign me up!
19) I, too, vote for political parties, and have sectarian allegiances. But I’m most moved by human creative effort, in science or literature or anything else, that transcends time and place and circumstance and speaks to the eternal.
BILL: I find myself less interested in politics and more interested in math. Non-partisan example: I read many articles about who Trump will pick for his VP. Then he picked one. I then read many articles about who Harris will pick for her VP.Then she picked one. I WISH I HAD SPENT THAT TIME ON THE POLYNOMIAL-HALES-JEWITT THEOREM INSTEAD!
20) As I was writing this post, a bird died by flying straight into the window of my home office. As little sense as it might make from a utilitarian standpoint, I am sad for that bird.
BILL: If we could ,without too much effort, make this not happen in the future, that would be good. There were some suggestions for that in your blog comments.
As someone who has literally written a book on the topic, I have had many people over the years send me their attempts at P v NP proofs. On average, I receive about one a month, but I've had seven in the last two weeks. And not just the usual email with a PDF attachment. A DM in X. A phone call with a baby in the background. Via Linkedin, in Spanish. One with forty-one follow up emails.
P v NP is still the most important problem in theoretical computer science and perhaps all of mathematics, and not that difficult to understand, at least on an intuitive level. I can see the fascination in wanting to solve it, much the way my teenage self dreamed of being the first to prove Fermat's last theorem (damn you Wiles).
But why the spate of "proofs" right now? Maybe it's an artifact of the crazy world we live in.
In one sense, I appreciate the continued interest in this great question, even though these papers rarely (really never) provide new insights into the P v NP problem. Most of my colleagues just ignore these emails, I usually try to respond once, but most authors will come back and I just don't have time for those continued conversations.
These papers come in three categories.
Claiming to prove P ≠ NP by arguing that a polynomial-time machine must search a large space of solutions. To truly prove P ≠ NP, one cannot make assumptions about how the machine might work.
Giving an algorithm for an NP-complete problem which works on some small test case. I'd usually ask for them to solve SAT competition problems, solve RSA challenge problems or mine themselves some bitcoin.
Giving a new philosophical or physical spin on the P v NP problem and claiming that tells us about whether P = NP. But P v NP is at its heart a mathematical question, and no amount of philosophy or physics will help settle it.
I have a new suggestion for those who think they've settled P v NP: Run your paper through an AI system, preferably a reasoning model, using the prompt "Give me a critical review of this paper". If you can't convince AI, you're not likely to convince me.
I wrote this about a month ago but wanted to wait until after the REU PI conference (which was April 21-22-23) to post it. I add a few comments based on what has happened since, which I preface with ADDED.
I agree with their posts and do not have anything to add about the general situation.
Hence I give you a personal view. While not as important as the general problem, what is happening to me may be considered one of many canaries in the coal mines. (Do my readers know that expression and where it came from? If not then see here.)
Random points about my NSF-REU grant.
1) I got my REU grant, REU-CAAR (Combinatorics and AI for Real problems--that's not what it stood for then but its what it stands for now) in 2013 for 2013-14-15. (To see what REU grants are either go to my post about them here or goto my current website about it here.)
2) It has been renewed for 2016-17-18 and 2019-2020-2021 and 2022-2023-2024 and 2025-26-27. The last one with a caveat.
3) In all but the last one, being recommended for a grant was equivalent to getting the funding. But for the 2025-2026-2027 I have not seen a dime and I assume I will not get funding in time for a Summer 2025 program to be run normally. (ADDED: I was correct on this.)
4) I am running the program anyway- mostly local students (don't need housing) who don't need stipends. There may be a little (not much) money for a few stipends, from other sources.
ADDED: Here is a list of approaches people who have been promised money but haven't gotten it are doing
a) Run a program with very little money and have the students come WITHOUT stipend, WITHOUT housing, WITHOUT transportation, WITHOUT food. Mostly local students. The program can still run but is against the whole point of REU grants which is broadening of students and giving students from non-research schools a chance to do research. (Only 3 of my students are from Non Research Schools. Another 4 are from High Schools, so not sure how that counts for this.) One odd pro: In my case I have 25 students- I can make more offers since I am not paying anything.
b) Run a program with some money you have lying around. You may decide to give stipends but NOT housing.You may (like approach (a)) hence take mostly local students. But all students get stipends.
c) You assume you will get money by (say) May 15). So you take applicants, accept and reject as appropriate. PRO-if the money comes in, you run a normal program. CON- you may end up cancelling in (say) Mid May leaving students in the lurch.
d) Do not begin trying to run a program UNTIL you get funding. If you get funded late then run a small program of mostly local students.
e) There are probably other approaches or combinations of the above.
5) I've heard that the reason I won't see money in time is NOT that REU grants are DEI but because of the staff cuts at NSF make it harder to get funds out the door.
6) Will I get funded in time for 2026? I'd be surprised either way. Is it possible for both A and NOT(A) to be surprising? I'll make that an REU project in 2026 if I get funded by then.
7) One of the original motivations for the REU program was to give students at non-research schools a chance to do research. Hence I use comes from a non-research school as a non-merit criteria. Is using that criteria DEI? I doubt Elon has thought that through. (HE MIGHT HAVE- see comment 9.5 that I added after I posted this.)
8) Another non-merit criteria I use is how many students want to work on which projects. For example, if 10 very qualified applicants want to work on Ramsey Theory, I can't take all of them. I urge the applicants to specify at least 3 projects they are happy to work on, though many do not do that. Is using the distribution of projects, a non-merit criteria, DEI? I doubt Elon has thought that through. (HE MIGHT HAVE- see comment 9.5 that I added after I posted this.)
9) Another non-merit criteria I use is veterans. It is rare that a veteran applies to my program, but it does happen and they get a preference (we've had 3 veterans). Is that non-merit criteria DEI? I doubt Elon has thought that through. (HE MIGHT HAVE- see comment 9.5 that I added after I posted this.)
9.5) An astute reader emailed me that comments 7-8-9 may be unfair.
The guidelines on NSF grants are here. I quote an FAQ question
4. Can I still propose broadening participation activities (e.g.,
outreach) in fulfillment of the Broader Impacts criterion?
Investigators should prioritize the first six broader impacts goals as
defined by the America COMPETES Reauthorization Act of 2010 (see here)
Investigators wishing to address goal seven — expanding participation
in STEM for women and underrepresented groups — must ensure that all
outreach, recruitment, or participatory activities in NSF projects are
open and available to all Americans. Investigators may conduct these
types of engagement activities to individuals, institutions, groups,
or communities based on protected characteristics only as part of
broad engagement activities. Investigators may also expand
participation in STEM based on non-protected characteristics,
including but not limited to institutional type, geography,
socioeconomic status, and career stage. However, engagement activities
aimed at these characteristics cannot indirectly preference or exclude
individuals or groups based on protected characteristics.
Instutitional type can be interpreted as non-research schools being okay. Career stage can be interpreted as returning students. Not sure about veterans of too-many-ramsey-theorists.
10) One of the things that made America great in the past was our scientific achievement. Hence we need a president who wants to Make America Great Again. We can abbreviate that to MAGA.
11) A good Popperian scientist would STUDY the NSF (and other programs) SEE what is wasteful and what is not and ACCEPT what they find. Had they done this it would have lead to some minimal changes at the NSF and the NIH and other organizations. But instead they just asserted that the NSF and NIH waste money. (Spellcheck thinks that Popperian is not a word. Oh well. For those who don't know what that means, see Karl Popper's Wikipedia entry here.)
12) Is the overhead on grants too high? That is a fair question to ask. But cutting overhead from 50% to 15% overnight is disruptive and does not get into the issue of how high overhead should be.
13) Will industry step in and fund research? I doubt it will be enough.
Right after the election I wrote a post predicting what would happen to higher education under Trump, most of which is coming true, but I had a massive failure of imagination missing the direct attacks on major universities. I won't detail all the challenges to higher ed, which change daily with every new executive order and court ruling. The Chronicle has a good tracker of these changes.
But often lost in all the news are the actual people who aren't making the news hurt by these actions, through no fault of their own: A student who had his visa cancelled while out of the country so he can't get back in. PhD students who just lost their funding when their advisor's grant was cancelled. A postdoc in a similar situation just months before he starts an academic job. A young faculty member who had to hold off submitting a Career award proposal until a TRO restored the indirect cost. A recently tenured professor at a good US university interviewing outside of the country. Potential students in other countries trying to decide if they should still go to school and build a life in the US.
The number of people, grants and universities affected is still on the low end, nearly all students continue to study, graduate and work without any problems, and many universities have offered legal and financial support to affected students and faculty. In my humble opinion, the strong educational opportunities inside the US still greatly exceed those outside. Universities have weathered many challenges before: McCarthyism in the 50s, campus occupations and protests in the 60s, and budget challenges from the great depression, to the fiscal crisis and covid. Trump's time as president has an end date and we'll get through all of this, but it requires all of us to push back and remind the administration and the public about the important role our universities play in the health of the country.
And as much as it pains me to say this as a Cornell alum, I'm rooting for Harvard.
I'm short on time time this week so I thought it would be good to look back, some 64 years ago, to Dwight Eisenhower's farewell address. It calls for balance between the industrial-military Complex and the scientific-technological elite. While written for a different time, it's well worth taking the time to watch or read the full speech and think what is says about today's complex world.
Dwight D. Eisenhower — Farewell
Address
The White House,
January 17, 1961
I. The American Experience
Good evening, my fellow Americans.
First, I should like to express my gratitude to the radio
and television networks for the opportunities they have given me over the years
to bring reports and messages to our nation.
My special thanks go to them for the opportunity of
addressing you this evening.
Three days from now, after half a century in the service of
our country, I shall lay down the responsibilities of office as, in traditional
and solemn ceremony, the authority of the Presidency is vested in my successor.
This evening I come to you with a message of leave-taking
and farewell, and to share a few final thoughts with you, my countrymen.
Like every other citizen, I wish the new President, and all
who will labor with him, Godspeed. I pray that the coming years will be blessed
with peace and prosperity for all.
Our people expect their President and the Congress to find
essential agreement on issues of great moment — the wise resolution of which
will better shape the future of the nation.
My own relations with the Congress, which began on a basis
of mutual confidence and ended on the same note, have been throughout marked by
a spirit of co-operation. In the councils of government, we must guard against
the acquisition of unwarranted influence, whether sought or unsought, by the
military-industrial complex.
The potential for the disastrous rise of misplaced power
exists and will persist.
We must never let the weight of this combination endanger
our liberties or democratic processes.
We should take nothing for granted.
Only an alert and knowledgeable citizenry can compel the
proper meshing of the huge industrial and military machinery of defense with
our peaceful methods and goals, so that security and liberty may prosper
together.
II. The Balance in Government
Akin to, and largely responsible for the sweeping changes in
our industrial-military posture, has been the technological revolution during
recent decades.
In this revolution, research has become central; it also
becomes more formalized, complex, and costly.
A steadily increasing share is conducted for, by, or at the
direction of the Federal government.
Today, the solitary inventor, tinkering in his shop, has
been overshadowed by task forces of scientists in laboratories and testing
fields.
In the same fashion, the free university, historically the
fountainhead of free ideas and scientific discovery, has experienced a
revolution in the conduct of research.
Partly because of the huge costs involved, a government
contract becomes virtually a substitute for intellectual curiosity.
The prospect of domination of the nation’s scholars by
Federal employment, project allocations, and the power of money is ever present
— and is gravely to be regarded.
Yet, in holding scientific research and discovery in
respect, as we should, we must also be alert to the equal and opposite danger
that public policy could itself become the captive of a
scientific-technological elite.
It is the task of statesmanship to mold, to balance, and to
integrate these and other forces, new and old, within the principles of our
democratic system — ever aiming toward the supreme goals of our free society.
III. Peace and Responsibility
Another factor in maintaining balance involves the element
of time.
As we peer into society’s future, we — you and I, and our
government — must avoid the impulse to live only for today, plundering for our
own ease and convenience the precious resources of tomorrow.
We cannot mortgage the material assets of our grandchildren
without risking the loss also of their political and spiritual heritage.
We want democracy to survive for all generations to come,
not to become the insolvent phantom of tomorrow.
Down the long lane of the history yet to be written, America
knows that this world of ours, ever growing smaller, must avoid becoming a
community of dreadful fear and hate, and be, instead, a proud confederation of
mutual trust and respect.
Such a confederation must be one of equals. The weakest must
come to the conference table with the same confidence as do we, protected as we
are by our moral, economic, and military strength.
That table, though scarred by many past frustrations, cannot
be abandoned for the certain agony of the battlefield.
Disarmament, with mutual honor and confidence, is a
continuing imperative.
Together we must learn how to compose differences, not with
arms, but with intellect and decent purpose.
Because this need is so sharp and apparent, I confess that I
lay down my official responsibilities in this field with a definite sense of
disappointment.
As one who has witnessed the horror and the lingering
sadness of war — as one who knows that another war could utterly destroy this
civilization which has been so slowly and painfully built over thousands of
years — I wish I could say tonight that a lasting peace is in sight.
Happily, I can say that war has been avoided.
Steady progress toward our ultimate goal has been made.
But so much remains to be done.
As a private citizen, I shall never cease to do what little
I can to help the world advance along that road.
IV. Final Thoughts
So — in this my last good night to you as your President — I
thank you for the many opportunities you have given me for public service in
war and peace.
I trust that in that service you find some things worthy; as
for the rest of it, I know you will find ways to improve performance in the
future.
You and I — my fellow citizens — need to be strong in our
faith that all nations, under God, will reach the goal of peace with justice.
May we be ever unswerving in devotion to principle,
confident but humble with power, diligent in pursuit of the nation’s great
goals.
To all the peoples of the world, I once more give expression
to America’s prayerful and continuing aspiration:
We pray that peoples of all faiths, all races, all nations,
may have their great human needs satisfied — that those now denied opportunity
shall come to enjoy it to the full — that all who yearn for freedom may
experience its spiritual blessings.
Those who have freedom will understand, also, its heavy
responsibilities — that all who are insensitive to the needs of others will
learn charity — that the scourges of poverty, disease and ignorance will be
made to disappear from the earth, and that, in the goodness of time, all
peoples will come to live together in a peace guaranteed by the binding force
of mutual respect and love.
Now, on Friday noon, I am to become a private citizen. I am
proud to do so. I look forward to it.
Def: A semigroup is a pair \((G,*)\) where \(G\) is a set and * is a binary operation on \(G\) such that * is associative. NOTE: we do not require an identity element, we do not require inverses, we do not require commutative. We DO require that G is closed under *.
Theorem: Let (G,*) be a finite semigroup. There exists x in G such that \(x*x=x\).
Proof: Let \(x_1,x_2,\ldots,x_r\) be a sequence of elements of G (repetition is allowed---indeed required since we will need \( r >|G| \).) Let \(r\) be such that any |G|-coloring of \(K_r\) has a mono triangle.
Such an \( r\) exists by Ramsey's Theorem \((|G| \) colors, seek mono \(K_3\)).
Consider the following coloring: for \(i<j\), \(COL(i,j) = x_i* \cdots* x_{j-1} \).
By the choice of \(r\) there exists \(i<j<k\) such that
\(x_i* \cdots * x_{j-1} = x_j *\cdots *x_{k-1} = x_i* \cdots *x_{k-1} \). We call this \(x\).
Since \(x_i *\cdots * x_{k-1} = x_i *\cdots *x_{j-1} * x_j \cdots *x_{k-1}\) we have \(x*x=x\).
End of Proof
Great! Lets find some semigroups to apply this to.
1) If G has an identity element \(e\) then the Theorem is trivial, take \(x=e\). So we seek a semigroup without identity.
2) Can't we just take a group and remove its identity element? No- then it won't be closed under *.
3) Can't we just take the set of N that are \ge 1, under addition. No good- that's infinite. Note that the theorem does not hold there.
4) Can't we just google. I kept getting infinite examples or being told that I can ADD the identity to a semigroup to get an identity.
5) Can't we just ask AI. I used Claude which gave me a trivial 2-element example. I then asked for an example with more than 10 elements. It DID give me one:
\(G=\{1,\ldots,12\} \)
\(x*y=\min\{x,y,10\}\)
For this semigroup (and similar one) the theorem is trivial since \(\forall x\le 10, x*x=x\).
I asked Claude for an example with more than 10 elements that does not use MIN and it said
Due to capacity constraints NO CAN DO.
6) SO what I really want is the following:
Give me a FINITE semigroup G WITHOUT identity for which the statement
is there an \(x\) with \(x*x=x\)
is not obviously true- so that the Theorem above is interesting.
In the recent Signalgate scandal, several senior Trump administration appointees used the Signal app on their phones to discuss an attack on the Houthis. People discussed the risk of the phones being compromised or human factors, such as adding a prominent journalist to the group chat by mistake. But mostly no one had concerns about the cryptography itself on this widely-available app.
It wasn't always this way--cryptography used to be a cat and mouse game, most notably the breaking of the German Enigma machine dramatized in the movie The Imitation Game. Then Diffie and Hellman in their classic 1976 paper stated
Theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.
And in recent memory we've had several successful cybersecurity attacks, but never because the encryption was broken.
We've made incredible progress in solving problems once thought unsolvable, including language translation, chess, go, protein folding and traveling salesman. We have great SAT and Mixed-Integer Programming algorithms. We've blown through the Turing test. None of these algorithms work all of the time but no longer do hard problems seem so hard. Yet cryptography remains secure. Why? How did we get to this Optiland, where only the problems we want to be hard are hard? Quantum computers, if we have them can attack some cryptographic protocols, but we're a very long way from having those capabilities.
My latest theory involves compression. Machine learning works by finding a representation of a function in a neural net or other form that gives an imperfect compressed version of that function, removing the random components to reveal the structure inside. You get a smaller representation that, through Occam's Razor, is a hopefully mostly accurate version of that data. For example, we learn the representation of a Go player by training a neural net by having the computer play itself over and over again.
Cryptography is designed to look completely random. No compression. If you remove the randomness you have nothing left. And thus modern algorithms have no hook to attack it.
This is just the beginnings of a theory. I don't have a good formalization and certainly not even the right questions to ask of it.
So to me it's still a big mystery and one that deserves more thought, if we really want to understand computational complexity in the world we actually live in.
