2... 1/2 THEN 3... 1/6 THEN 5 ....1/15 and so on. And So On?

The excellent graphic novel

Prime Suspects: The Anatomy of Integers and Permutations

by Andrew Granville and Jennifer Granville,  illustrated by Robert J Lewis,

(I wrote a review of this graphic novel, for SIGACT News, here.)

has an appendix, which is not in graphic-novel form, where they describe some of the math talked about in the graphic novel. 

Here is a quote that intrigued me for two reasons

2 is the smallest prime factor of half of the integers,

3 is the smallest prime factor of one-sixth of the integers,

5 is the smallest prime factor of one-fifteenth of the integers,

and so forth.

Intrigue One: and so fourth ? Really? That would indicate that it is easy to know what the next fraction is.  Is it easy? That depends on your definition of easy.

Intrigue Two: What is the next fraction? What is the fraction asymptotically? I worked  both of these out fairly fast; however, I  don't think  and so forth is appropriate.

We derive the 1/15 for 5.  1/5 of all numbers have a factor of 5. Of those, only those that are \(\equiv 1,5 \pmod 6\) have 5 as the smallest  prime factor.  Hence \(2/6=1/3\) of those numbers have 5 as the smallest  prime factor. Hence the fraction is \(1/5 \times 1/3 = 1/15\). 

More generally: For all \(i\in N\) let  \(p_i\) be the \(i\)th  prime. What fraction of numbers have \(p_n\) as the smallest factor? \(1/p_n\) of all numbers have a factor of \(p_n\). If a number that is divisible by \(p_n\) is also  \(\equiv x \pmod {p_1p_2\cdots p_{n-1}}\) where \(1\le x\le p_1\cdots p_n\) and \(x\) is rel prime to \(p_1\cdots p_n\), then that number has  \(p_n\) as the smallest factor. Hence the fraction is 

\(\frac{1}{p_n} \times \frac{\phi(p_1\cdots p_{n-1})}{p_1\cdots p_n}=\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}= \frac{1}{p_n}\prod_{i=1}^{n-1} (1-\frac{1}{p_i})\)

where \(\phi\) is the Euler-phi function which, on input \(x\), returns the number of naturals in [1,n] that are relatively prime to \(n\). We have used the following well known facts: (a) if \(a,b\) are rel prime then \(\phi(ab)=\phi(a)\phi(b)\), and (b) if \(p\) is prime then \(\phi(p)=p-1\) (this is obvious).  

The expression

\(\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}\)

is good for exact calculation. Let's do one!

The fraction of numbers that have 7 as their least prime factor is

\( \frac{1}{7}\times  \frac{1\times 2\times 4}{2\times 3\times 5}= \frac{4}{105} \)

From the first three terms  \( \frac{1}{2}, \frac{1}{3}, \frac{1}{15} \) I do not think that and so fourth would make anyone think the next term was \(\frac{4}{105}\).

 But what is the fraction asymptotically? 

ChatGPT tells me (and I believe it) that

 \( \prod_{i=1}^{n} (1-\frac{1}{p_i})   \sim \frac{e^{-\gamma}}{\ln p_n} \) 

where \(\gamma\) is the Euler-Mascheroni constant, roughly 0.5772 (see here for the Wikipedia entry on that constant).

Hence we get that the fraction of numbers that have \(p_n\) as their smallest prime factor is 

 \(\frac{1}{p_n} \prod_{i=1}^{n-1} (1-\frac{1}{p_i})   \sim\frac{1}{p_n} \frac{e^{-\gamma}}{\ln p_{n-1}} \) 

Wolfram Alpha tells me (and I believe it) that

 \(e^{-0.5772}\sim 0.56146\).

 Hence we give our final approx for the fraction of numbers that have \(p_n\) as their least prime factor as

\(\frac{0.56146}{p_n\ln(p_{n-1})}\)   

I don't think this qualifies as and so forth.

Wither/Whither the ACM

Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the organization itself.

Jim Larus, editor-in-chief of the CACM, writes Wither ACM? Publish and Perish?

ACM no longer has broad appeal as a professional organization, does not advance many members’ careers, and may not be a valuable affiliation in a more diverse technical world...It is time to recognize that ACM has shifted from functioning as a professional society for the academic computing community to a professional publisher....It is time for ACM members to debate what kind of organization ACM should be and how to remake it into the society they want to belong to!

Vardi writes Whither Computing? starting with the concerns of PhD students whether they made the right choice by going into computer science and ending with a call for ACM to lead the conversation.

A new team will assume the leadership of ACM on July 1, 2026, following the current general election and search for a new chief executive officer. I believe this team will have to grapple with existential questions about the future of computing as a science and a profession...If ACM is about “advancing computing as a science and profession,” then we need to engage in a deep conversation about what this phrase means today for education, research, the profession, and ACM, and about how to truly advance computing as a science and profession.

ACM hasn't served as a true professional society for a long time. Unlike in other fields, ACM doesn't hold annual meetings for the whole community, and shares the spotlight with IEEE-CS, USENIX, AAAI, CRA and others. CRA takes the lead in research and organizes the CS department chairs meetings. ACM has focused on journals, conferences through its SIGS and awards.

This worked well while computing went through tremendous growth from after the financial crisis until a couple of years ago. But now artificial intelligence is making us rethink how we do research, publish and educate. What does it even mean to be a computer scientist in the AI era?

So good luck to incoming president Elisa Bertino and her team. Computing is changing. How will ACM change with it?

Extreme cases of clickbait!

I recently read Alan Alda's first memoir Never have your dog stuffed which was pretty good. Hence I began looking for more information about him on the web. I came across a YouTube video  At 89, Alan Alda reveals the seven actors he HATED the most.  Gee, in the book he didn't hate anyone. So I was curious what this was about. This could be interesting. It was not. The title was extremely deceptive. (More than most clickbait?)  Here is the list and what was said about them:

Wayne Rogers (Trapper John on MASH): The YouTube video said Wayne Rogers felt he didn't have a big enough role on MASH. 

Maclean Stevenson (Henry Blake on MASH): Same as Wayne Rogers.

Gary Burghoff (Radar O'Reily on MASH). The YouTube video said that Gary had emotional outbursts on set, or isolated himself. He felt trapped in the role, unable to grow. 

Robert Duvall (Played Frank Burns in the Movie MASH). The YouTube video said that Robert Duvall   had a different take on the role of Frank Burns in the movie than that Alan Alda had for the TV show. Note that this was not the role Alan Alda played. Also note that  Robert  D and Alan A have never met.

Edward Winter (Played Colonel Flagg on MASH): The YouTube video said that Winter was only in  7 of the 251 episodes. 

David Ogden Stiers (Played Charles Winchester on MASH): The YouTube video said that  David did not socialize with the crew.

Larry Linville (Played Frank Burns on MASH): The YouTube video said that Larry L did not like that his role was one-dimensional. 

Quote:

Did Alan Alda hate these actors? Probably not.

Also a common line was 

Alan has always spoken of X in positive terms.

The clickbait worked in that I read it, and indeed, I am blogging about it. But I won't fall for clickbait for another 5 years (the last time I fell for click bait before this was 5 years ago.)

Lesson of the day: do not fall for clickbait. 

Points:

1)  Since it is well known that clickbait is deceptive, does it still work. Well... I fell for it. 

2)  Is this clickbait more deceptive than usual or not?

3) The term clickbait was coined in 2008 by Jay Geiger in a blog post. The word was added to the Oxford English Dictionary in 2016. For more on the word see here.

4) Is the title of this blog  post, Extreme cases of clickbait!, itself clickbait? 

5) Could an AI be trained to classify videos as Clickbait or Not? In general no since one person's clickbait is another person's  HMMM- what is the opposite of clickbait? (Google said  anti-clickbait and honest-headline, neither of which really works.) Perhaps AI could be trained on what (say) Lance thinks is clickbait. 

Request

If you have an extreme example of clickbait, please leave a comment about it. 

The True Method

Harry Lewis pointed Bill and me to Gottfried Leibniz's 1677 treatise The True Method (translated from the original French). I highly recommend taking the time to read this three page document where he talks about formalizing all human knowledge.

The second paragraph has some of the intuition for P v NP three centuries before Cook, Levin and Gödel. 

But knowledge depends on proof, and discovering proofs requires a certain method that is not known to everyone. Every person is capable of judging a proof, since it would not deserve to be called a proof unless everyone who considered it carefully found it convincing. Nevertheless, not everyone is capable of discovering proofs independently or of presenting them clearly once they have been found, whether for lack of time or for lack of method. 

Though by "not everyone" he might have excluded himself.

Every investigation that depends on reasoning would be carried out by manipulating these symbols, through a kind of calculation. This would make the discovery of important results entirely straightforward. We would no longer have to rack our brains as much as we do today, while still being certain that we could accomplish everything that was possible from the information given.

Though not clear if "that was possible" took computational time into account. Is he claiming P = NP?

The article as a whole talks about a project to develop a fully logical language to cover not just mathematics, but the sciences like physics and medicine and even morality, politics and law. Here he was just being too ambitious and missing complexity issues, for example that you can't create laws that fully cover all potential futures.

Leibniz does give himself an out, a nod to the scientific method that was being developed during that time.

Some experiences will always be needed as the foundation for reasoning. But once those experiences have been supplied, we could derive from them everything that anyone could ever derive. We could even determine which further experiments still needed to be performed in order to clear up all remaining doubts.

He even gives a nod to probability. 

This would be of extraordinary assistance even in politics and medicine, where we must reason consistently and correctly from given symptoms and circumstances. Even when there are not enough facts to form an infallible judgment, it would still be possible to determine what is most probable from the information available. That is everything reason can do.

Sort of how machine learning works now.

Guest Post by Peter Brass on the new NSF guidelines

Peter Brass is a prior NSF theory director. He has written an intelligent guest post on the new NSF guidelines that we present here.

---

You have received many mails regarding the proposed OMB Uniform Guidance for federal grant making. It is a very long document. So far the OMB has received more than 32,000 comments, which nominally all will be read and taken into account, but actually most are general comments along the lines of “this will destroy scientific research,” and unspecific comments will achieve nothing. You can sample the comments, they are public, and you will be disappointed: much heat but no illumination.

It is my aim to bring a bit more content to the debate, and encourage you to file comments, but on specific issues, in my opinion primarily on the passage against “promoting anti-American Values,” which might indeed be a catch-all for political pressure on research. Otherwise there is little new: reviews were always only advisory.

The relevant section is https://www.federalregister.gov/d/2026-10817/p-amd-155, the revision of section 200.205, especially section (b) “pre-issuance review,” which states (underline and boldface mine):

(b) Pre-issuance review. As part of the merit review process, Federal agencies must perform pre-issuance reviews to ensure that Federal award proposals selected for funding are consistent with applicable law, Federal agency priorities, and the national interest. In doing so, Federal agencies heads must designate one or more senior appointees to conduct a pre-issuance review of all discretionary awards. As part of this pre-issuance review for discretionary awards, senior appointees (or their designee) must, as relevant and to the extent consistent with applicable law, apply the following principles when reviewing Federal award proposals:

This is followed by a list of criteria, but to summarize this: The agency head (a presidential appointment) designates a senior appointee (possibly a presidential appointment) who might designate another person inside the agency, who checks all intended awards that certain criteria are satisfied. This is not really different from the state before 2025: any proposal I proposed for award needed to be checked by the division director.

So if there is a problem, it must be in the criteria. It turns out there might be, depending on the interpretation.

1. Discretionary awards must, where applicable, demonstrably advance the President’s policy priorities.
   Whether this is applicable is the agency’s decision.
2. Discretionary awards must not be used to fund, promote, encourage, subsidize, or facilitate:
   • (i) Racial preferences or other forms of racial discrimination by the recipient, including activities where race or intentional proxies for race will be used as a selection criterion for employment or program participation;
   • (ii) Denial by the recipient of the sex binary in humans or the notion that sex is a chosen or mutable characteristic;
   • (iii) Illegal immigration; or
   • (iv) Any other initiatives that compromise public safety or promote anti-American values.
   That last one is a catch-all, which can indeed be used by politics to suppress research. This is the passage against which we should protest.
3. All else being equal, preference for discretionary awards should be given to institutions with lower indirect cost rates.
   All else is never equal, but it is in the program director’s discretion to consider how much funding actually reaches science.
4. Discretionary awards should be given to a broad range of recipients. Research grants should be awarded to a mix of recipients likely to produce immediately demonstrable results and recipients with the potential for potentially longer-term, breakthrough results, in a manner consistent with the notice of funding opportunity.
   I am quite happy about this explicit recognition of the importance of basic research.
5. In performing activities under Federal awards, applicants should commit to complying with administration policies, procedures, and guidance respecting Gold Standard Science.
   It is fairly unclear what Gold Standard Science is, but that seems to affect only lab or simulation sciences with results that are advisory to politics.
6. Discretionary awards should include benchmarks for measuring success and progress towards relevant goals and, as relevant for awards pertaining to scientific research, a commitment to achieving Gold Standard Science.
   Same. For us the benchmark measuring success is publication, so no news.
7. To the extent institutional affiliation is considered in making discretionary awards, agencies should prioritize an institution’s commitment to rigorous, reproducible scholarship over its historical reputation or perceived prestige. For science grants, agencies should prioritize institutions that have demonstrated success in implementing Gold Standard Science.
   No news either. We should not give extra credit to a proposal coming from a famous institution. Of course that is in the discretion of the program director.

(c) Procedure for pre-issuance review. When conducting a pre-issuance review, senior appointees (or their designee) must not ministerially ratify or routinely defer to the recommendations of others, but must instead use their independent judgment when evaluating Federal award proposals.

(so the designee should actually look at the proposal before approving the award)

(d) Use of peer review. Nothing in this part must be construed to discourage or prevent the use of peer review methods to evaluate proposals for discretionary awards or otherwise inform agency decision making, provided that peer review recommendations remain advisory and are not ministerially ratified, routinely deferred to, or otherwise treated as de facto binding by senior appointees or their designees. Further, nothing in this part must be construed to create any rights to any particular level of review or consideration for any funding applicant except as consistent with applicable law.

(good news: nothing changes)

(e) Agency discretion to reissue funding opportunities. A Federal agency is not required to issue a discretionary award as a result of a NOFO if doing so would fund low-quality proposals or be inconsistent with the principles of this part. The agency may, at its discretion, repost a funding opportunity.

(so the agency can decide not to make any award)

This is the entire section which causes so much outcries. I believe that the proposed budget cuts are a much larger danger to research than these recommended OMB rules.

The Zone

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working on an open problem, you have no idea how difficult a solution may be, or if a solution exists at all. Most of the time you will fail (if not you need to try harder problems). Failure is not wasted time. You may find a counterexample, a partial solution and always you will come out with a better understanding of the problem. Then days, months or years later, some new proof idea comes from a paper, a talk or just the back of your head, and back in the zone you go. And when you do succeed you get a feeling not unlike scoring a goal in a soccer game. You should see my proof dance.

With AI generated and assisted proofs, we may think of outsourcing the zone to ChatGPT and Claude. We may prove more and stronger theorems, but you'll understand the results just a little bit less and mathematics will become a little less fun. 

The New Result on Off-diagonal Ramsey Numbers

(All references in this blog post can be found in the main article the post is about which is here.)

Recall that \(R(s,k)  \) is the least \(n\) so that, for all 2-colorings of the edges of \(K_n\), there is either a RED \(s\)-clique or a BLUE \(k\)-clique.

\(R(k,k)\) has been well studied and is often called \(R(k)\).

However, today we are concerned with \(R(s,k)\) \(s\) is fixed and \(k\) goes to infinity.

1) In 1995 Jeong Han Kim showed \(R(3,k)\) is asy \(\Theta(\frac{k^2}{\log k})\). At the workshop In Ramsey Theory: Yesterday, Today, and Tomorrow, Edited by Alexander Soifer, 2011, Joel Spencer gave a great talk titled

80 years of \(R(3,k)\).

The title implies that the problem was open for 80 years, but 40 years is a better estimate.

The general sense I got from both Joel and the audience is that \(R(4,k)\) is a much harder problem.

2) In 2023 there was substantial progress on \(R(4,k)\). Sam Mattheus and Jacques Verstraete showed

\(R(4,k) = \Omega(\frac{k^3}{\log^4 k})\)

Combined with prior results this yields

\( c_1 \frac{k^3}{\log^4 k} \le R(4,k) \le c_2 \frac{k^3}{\log^2 k} \)

The prior lower bound had been \(\Omega(\frac{k^{2.5}}{\log^2 k })\) so this was a big improvement.

3) The following was known for \(R(s,k)\) for fixed \(s\) and asy \(k\):

\( k^{(s+1)/2 + o(1)} \le R(s,k) \le O(k^{s-1}) \)

There were polylog improvements to this which we omit.

Surely improving the lower bound to \(\Omega(k^{s-1+o(1)})\) would be hard.

4) Domagoj Bradac showed the following (posted on May 27, 2026, and pointed to at the beginning of this post):

\(R(s,k) =\Omega(\frac{k^{s-1}}{(\log k)^{2s-4}}).\)

Combining this with the known best upper bounds yields (ignoring constants) 

\( \frac{k^{s-1}}{(\log k)^{2s-4}} \le R(s,k) \le (1+o(1))\frac{k^{s-1}}{(\log k)^{s-2}} \)

So the bounds are now only a polylog apart!

Random Notes.

1) I am not surprised by the results.

2) I am very surprised that the results were obtained.

3a) In 2011 most people thought that \(R(4,k)\) would be hard.

3b) After the progress on \(R(4,k)\) I still thought that \(R(5,k)\) would be hard, though I don't know what others thought.

4) Why such fast progress?

4a) AI? Some was used but not that much. See comment on page 4 of the paper.

4b) More people working on the problem?

4c) More advanced tools developed over time? Surely yes.

5) What other problem that seems like its solution is long in coming will be solved much faster than we think?

The Tech of Silk Road

Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road, a network of trading routes across Asia active from the second century BCE until the mid-15th century. I knew of the Silk Road but was surprised by how much it used and fostered various technologies. 

It started with a technology that allowed for traveling long distances with limited access to water, better known as a camel. Travel was slow, it could take nearly two years to get from one end (modern day Turkey) to the other (China). Cities grew along the way for travelers and their protection, and for trading.

The travelers did not just carry silk and other materials for trade, the routes became an information superhighway of a sort. Religions spread including Buddhism, early Christianity and Manichaeism, an old religion that mostly divided the world into good and evil. Artistic style and influences spread as well with motifs like halos and winged figures appearing across widely separated cultures. Traders needed to converse in several languages, and documents could have several translations. 

The roads carried knowledge about technology itself from astronomy, calendars, medical information, geography and mathematical methods in text translated among the many languages. Travelers brought scribes that created a written language for Mongolian among others. Chinese papermaking made its way west reducing the cost of recording and transmitting information. Gunpowder technology also made its way into Europe from the east. 

A confluence of technologies helped hasten the end of the Silk Road. Marco Polo wrote about his travels along the Silk Road at the end of the 13th century but the account spread more widely with the advent of the printing press in the 15th century. The book inspired explorers who used advances in ship building and navigation to find water routes to the East (and Christopher Columbus to try a western route). These water routes would prove a faster cheaper way to ship goods between Europe and East Asia. The technological revolution shrunk or shuttered cities that used to host traders on the Silk Road. On the other hand, wealthy European traders would help fund and usher in the Renaissance. 

The Silk Road harkens to a time where, for the most part, people, goods and information travelled along the same routes at the same speed. Large cargo still moves fastest by ship, people by airplanes and information via wires and satellite nearly instantaneously.

When we think of technological disruption we think of the industrial revolution or even what's happening today, but the Silk Road reminds us that disruption has always been a part of the world's history, for bad and for good.