Computational Complexity

Carmichael Numbers are the bane of probabilistic primality algorithms. You have to go through extra steps just to handle these relatively rare numbers. But did you know that the Miller-Rabin algorithm not only determines the compositeness of Carmichael numbers but can actually find non-trivial factors? Apparently none of the AI models I tried did either. Feel free, Google, OpenAI and Anthropic, to train on this blog post.

Let's start with Fermat's little theorem, not as big as his "last" one but one where we know he had a proof. It states that for any prime \(p\), \(a^p \equiv a\bmod p\) for all integers a. That suggests a primality test, if you can find an \(a\) such that \(a^m \not\equiv a\bmod m\) then you know \(m\) is not a prime. For example, since \(29^{143}\equiv 35\bmod 143\) then \(143\) is not prime.

The set of \(a\) such that \(a^m \equiv a\bmod m\) forms a subgroup of \(Z_m^*\) (the numbers \(b\) less than \(m\) with gcd\((b,m)=1)\), if there are any integers \(a\) that fail the test then at least half of the \(a\) will. So you could just choose a random \(a\) and check if \(a^m \equiv a\bmod m\). That would work for all the composites where there is an \(a\) such that \(a^m \not\equiv a\bmod m\). Alas there is a relatively rare set of composites, known as Carmichael numbers, for which \(a^m \equiv a\bmod m\) for all \(a\) co-prime to \(m\). The first few Carmichael numbers are \(561\), \(1105\), \(1729\) and \(2465\). For example \(29^{561}\equiv 29\bmod 561\).

So probabilistic primality tests need to account for these Carmichael numbers. Let's look at the Miller-Rabin test.

• If \(m\) is even, output "prime" if \(m=2\), composite otherwise.
• Pick \(s\) and odd \(d\) such that \(m-1=2^sd\).
• Pick random \(a\) between 2 and \(m-2\). If gcd\((a,m) \neq 1\) return composite.
• Let \(x = a^d\bmod m\)
• Repeat s times
• Let \(y=x^2\bmod m\)
• If \(y=1\) and \(x\not\in\{1,m-1\}\) then composite.
• Let \(x=y\)
• If \(y=1\) output "probably prime" otherwise "composite"
  

In 2016, in the pre-transformer times, Georgia Tech professor Ashok Goel gave a prescient TEDx Talk on an AI teaching assistant for his large online Artificial Intelligence course. Students would ask questions to an online forum, and fellow students and TAs would answer these question. Unbeknownst to the students, Ashok had an AI system answer questions from the forum with the moniker Jill Watson (it was built on technology used for Watson's Jeopardy win). Jill answered questions about administrative issues in the class, so well that most students were surprised it was an AI system. Goel still needed human TAs to handle questions about course content.

In the talk Goel made comments ahead of his time.

Today, we have classes with a hundred or more students, and few get personal attention. We even have massive open online courses, where students learn from prerecorded video lessons. Some of these classes attract 100,000 students, but only 10 percent or fewer complete them—because of the lack of teaching assistance and personal attention.

This raises a fundamental issue: can we have personal attention at scale? What if we could give personal attention to every student, when and how they needed it? That would create an educational revolution—because learning and teaching would become personal again...I envision a future where everyone has access to AI teaching assistants like Jill Watson—anytime, anywhere, for any task. A future where education is affordable and accessible to all, yet still personal and fun.

Fast forward to today and AI assistants can answer questions about course content pretty well for nearly every undergraduate course in all disciplines. A well-trained AI tutor outperformed in-class active learning. While I haven't seen formal studies, students seem to go to ChatGPT before reaching out to TAs, instructors or their fellow students. AI can grade assignments and exams.

Teaching assistants still have an important role to play. They teach recitation sections and run student labs. A great TA can provide a human connection with a student that no computer could. A teaching assistantship gives important training to students who might become academics, as well as providing an important funding mechanism, especially in the humanities and social science which has limited grant support for graduate students. But in a time of budget constraints at many institutions, how can we argue for the same TA support at the levels we had back in 2016?

A friend of mine told me that in the last six months, the last grandchild of one of our former presidents (who had already passed away) died.

I tried to deduce who it was without checking the web directly. For example, I looked up when various presidents were born to narrow it down, but try not to search for the answer itself.

I could look this up easily. However, by spending time thinking about it and exploring related questions, I might learn things I didn’t know before.

Things I care about? Maybe.

I now have a lot of white space, so you can think about the answer yourself and perhaps make a guess, then my reasoning process and the answer.

Before answering, I’ll walk through the reasoning I used for my educated guess.
Assume the president was born in year x.

ADDED LATER: In the original version of this post (and its still there) I would make comments like:

Warren G. Harding- why is the G always mentioned.

A commenter pointed out that middle names and initials are an American thing. This made me wonder why some of them didn't use their middle initial. Hence I have ADDED information about that. I won't bother writing ADDED LATER for those late adds.

END OF ADDED LATER

Assume the president’s youngest child is born in approximately year x+35.

Assume that child’s youngest child is born in approximately year x+70.

Assume the grandchild lives 80 years, so dies in approximately year x+150.

Then x+150=2025, so x=1875.

Since this is an approximation, I looked at all presidents born between 1850 and 1900. The website I consulted tells us the answer. What would we do without the internet? (Maybe spend more time offline tightening our bounds on the polynomial van der Waerden numbers.)
Here are all the presidents who were born in a year in [1850,1900].

Theodore Roosevelt — born 1858. Formal name: Theodore Roosevelt Jr. No middle name.

William Howard Taft — born 1857. He seems to have his full name mentioned. Why?

Woodrow Wilson — born 1856. Formal name: Thomas Woodrow Wilson. So it would be impossible to use a middle initial unless you do what David Dwight Eisenhower did and swith the two names, so then he would be Woodrow T. Wilson.

Warren G. Harding — born 1865

Calvin Coolidge — born 1872. Formal name: John Calvin Coolidge Jr. Similar to Woodrow Wilson. Cal's dad was John Calvin Coolidge Sr. Naming your kid after yourself, including the middle name, coud be a mistake, see here.

Herbert Hoover — born 1874. Formal name: Herbert Clark Hoover. I am surprised he wasn't called Herbert C. Hoover. Maybe Herbert Hoover was better because its alliterative.

Franklin D. Roosevelt — born 1882

Harry S Truman — born 1884 (There really is no period after the S. Both chatty and Wikipedia get that wrong.)

Dwight D. Eisenhower — born 1890 (born David Dwight Eisenhower; he preferred to be called Dwight).

When I was asked the question, I guessed Harry S. Truman. I was wrong.

In fact, none of the presidents on that list is the one.

The correct answer is John Tyler, who was born in 1790.

My rule-of-thumb assumptions (35 years to have a child; an 80-year lifespan) were large underestimates for this case. John Tyler had sixteen children. The third-to-last was Lyon Tyler, born in 1853 — John Tyler was 63 at the time, which is 28 years more than my estimate of 35. Lyon Tyler had six children; the second-to-last was Harrison Tyler, born in 1928 — Lyon was 75, which is 40 years more than my estimate of 35.

(In 1840 William Henry Harrison and John Tyler were elected Prez and Veep. WHH died after giving his inaugural speech in the cold rain, and Tyler became president. Lyon Tyler names his son Harrison. My thought was: Did Lyon name his son after WHH? I asked Google

Why did Lyon Tyler name his son Harrison?

The AI Overview said:

Lyon Tyler named his son Harrison because his own mother, Julia Gardiner, was a member of the Harrison family of Virginia, making Harrison a great-grandson of both President John Tyler and William Henry Harrison, the president whom John Tyler succeeded. Naming his son Harrison was a way for Lyon Tyler to honor the family connection to both presidents, particularly the presidential connection.

Thats not quite right- Harrison is John Tyler's grandson, not great-grandson.

I didn't know that John Tyler's grandchild was named Harrison.

I didn't know that John Tyler's grandchild was also related to WHH.

)


Harrison Tyler died in 2025 at the age of 96, which is 16 years more than my estimate of 80.

So my point (do my posts need a point?) is that I made an approximation but was still way off. John Tyler is an outlier, which is hard to account for.

Let’s say I assumed 60-year-old fathers and the grandson lives to 90. Then we would have:

x + 210 = 2025
x = 1815

This is an approximation, so I would look at presidents born between 1790 and 1840:

John Tyler: 1790. No middle name.

James K. Polk: 1790. Why is the K always mentioned?

Zachary Taylor: 1784. No middle name.

Millard Fillmore: 1800. No middle name.

James Buchanan: 179. He never had kids. That’s just as well, since his children would have had the stigma of their father being one of the worst presidents of all time by most accounts.

Abraham Lincoln: 1809. Born February 12, 1809 — the same day and year Charles Darwin was born. No middle name.

Andrew Johnson: 1808. No middle name.

Ulysses S. Grant: 1822. Born Hiram Ulysses Grant, but he didn’t like that the initials were H.U.G.

Rutherford B. Hayes: 1822. Why is the B always mentioned?

James Garfield: 1831. James Abram Garfield. I sometimes see the A initial and sometimes not.

Chester Arthur: 1829. My Darling’s favorite president — really! Formal name Chester Arthur which I have seen written, though not as much as the others. Perhaps I just didn't notice him as much as my Darling did.

Grover Cleveland: 1837. Formal name: Stephen Grover Clevelant.

Three points:

1) When I picked 60–60–90, I did not know that John Tyler would actually make it onto the list.

2) He just barely made the list.

3) I would not have picked 60–60–90 unless I had already learned that 35–35–80 was far too small.

We're seeing an attack on capitalism on both ends of the political spectrum with with the election of Democratic Socialist Zhoran Mamdani as mayor of New York, and Donald Trump trying to direct the economy through tariffs, less independency of the Federal Bank and partial government control of companies such as a nearly 10% ownership of Intel and the "golden share" of U.S. Steel.

Now I'm not an economist and there are many arguments for and against socialism and capitalism, especially in their purest forms. I want to focus on the complexity of the economy. Let's start by considering rent control.

It starts with the worthy goal of preventing people from having to leave their apartments because of rising rents due to market demand. So you limit the rent increases and the ability to evict current residents. But this could cause landlords to cut back on improvements, not prioritize service and repairs, or build new properties to increase the supply. So you have to give landlords incentives to do these things, leading to other issues which leads down a rabbit hole. I saw extreme rent control in Berkeley in the 1980s and a lack of available housing forced me to live 13 miles away.

That's just rent control in a single city. Other attempts to control the economy will lead to unexpected inefficiencies and you can't predict markets enough to catch them.

The 1920 essay Economic Calculation in the Socialist Commonwealth by Ludwig von Mises argued that market prices give critical information for companies and individuals to make decisions. I think of it like a circuit, where the prices are values of intermediate gates so that we can have simple operations at every level leading to a very complex behavior in the aggregate, much like a neural net today. Frederick Hayek went further in his 1945 essay The Use of Knowledge in Society that a center planner couldn't adapt with the speed of change in the markets.

Could today's neural nets replace the need for these intermediate pricing and adapt quickly? It's really a combination of the two, many companies are using sophisticated machine learning models that lead to more accurate pricing, adding to the efficiency of markets.

Capitalism has its challenges: Companies can shrink or close, people can lose their jobs and we need good safety nets. Government has a role to protect safety, enforce contracts and provide services and some control where competition doesn't scale, like utilities and pubic transportation. Government also has a role in promoting public goods including education, scientific research and national defense.

While neither Mamdani or Trump want anything close to complete government control of the economy, I still worry that even their limited influences will hurt innovation and in the longer run hurt the very people these policies are meant to help.

The following excerpt from Abrahim Ladha's comment on Lance's post about
AI and intro theory caught my attention:


---------------------------
BEGIN EXCERPT

Not just with AI, but in theory and math courses, there have always been Bart Simpson
level questions by students of the form

"Why do I need to know this?

like

Why do I need to know my times tables when the calculator does this for me?

There has never been a good answer because these students already do not have an open mind.
Euclid was asked such a question once and said something like

give him a penny so he may feel like he earned something for what he learned.

END EXCERPT
-----------------------------------

He gives a quote by Euclid.

1) I have heard that Euclid might not have really existed.

2) I have never heard that quote.

I asked Abrahim Ladha if he had a source for the Euclid quote.

I never go a response.

I asked chatty:

What is the historical evidence that Euclid existed?

and also

Did Euclid say give him a penny so he may feel like he earned something for what he learned?

The answer to both questions are below. The bottom line is that

1) Euclid might not have existed.

2) The idea underlying the quote is attributed to him. The exact quote is modern rendering.

Should Abrahim have consulted chatty before making his comment.

1) YES, it's important to make sure your facts are correct.

2) NO, his point is still valid. (That is a slippery slope.)

----------------------------------------
BILL: What is the historical evidence that Euclid existed?

That’s a great question — and a surprisingly tricky one.

Short answer

There is no direct historical evidence that Euclid (often called Euclid of Alexandria) existed
as an individual in the way we can verify the existence of, say, Archimedes. What we “know”
about Euclid comes almost entirely from later sources, not from contemporary records.

The evidence we do have

1)
Type: Ancient testimonies

Source: Proclus, Commentary on the First Book of Euclid’s Elements

Date: ca. 450 CE

Note: Written about 700 years after Euclid’s supposed lifetime. Proclus says Euclid lived
in the time of Ptolemy I (reigned 323–283 BCE) and taught in Alexandria. This is our main source.

2)
Type: Mentions by other ancient authors

Source: Pappus of Alexandria (4th century CE), Diogenes Laërtius (possibly), and others

Date: 200–600 years later

Note: These references repeat information similar to Proclus’s account — that Euclid compiled
the Elements and worked in Alexandria.

3)
Type: Mathematical evidence

Source: The Elements and other works attributed to Euclid (Data, Optics, Phaenomena, etc.)

Date: ca. 300 BCE?

Note: These texts show a unified style and method, suggesting a single organizing mind
(or school). But there is no personal or biographical detail inside them.

4)
Type: Absence of contemporary evidence

Note: There are no letters, inscriptions, or administrative records naming Euclid. No ancient
biography (unlike Archimedes or Apollonius).

Scholarly interpretation

Traditional view: There was a historical Euclid, a mathematician who worked in Alexandria
around 300 BCE and compiled earlier Greek geometry into the Elements.

Skeptical or revisionist view: “Euclid” may have been a collective name for a team or a
school of mathematicians in early Hellenistic Alexandria, much like “Hippocrates” in medicine.

The Elements itself is consistent in style, so even if multiple people contributed, it was
edited or systematized by someone with extraordinary coherence and rigor.

In summary

There is no direct documentary or archaeological proof that Euclid existed as an individual,
only later testimony and internal evidence from the mathematical works. Historically, most
scholars accept that there was a person — or at least a leading mathematician — behind the
name “Euclid,” but his life remains almost entirely unknown.
---------------------

BILL: Did Euclid say

`give him a penny so he may feel like he earned something for what he learned.'

ChatGPT said:

The quote you’re referring to — something like “Give him a penny so he may feel he has learned
something” — is attributed to Euclid, but not in those exact modern words.

It comes from an ancient anecdote recorded by Proclus (a 5th-century commentator on Euclid) in
his Commentary on Euclid’s Elements. The story goes like this:

A student, after learning the first theorem of geometry, asked Euclid,

“What shall I get by learning these things?”

Euclid called his slave and said,

“Give him a penny, since he must make gain out of what he learns.”

In Greek, it’s roughly:

“Δός αὐτῷ ὀβολόν, ἐπειδὴ κερδαίνειν δεῖται ἀπὸ τῶν μαθημάτων.”

So your paraphrase captures the spirit of the anecdote — Euclid was mocking the idea of
studying geometry for material reward — but the exact wording

“give him a penny so he may feel he earned something for what he learned”

is a modern retelling, not a direct quotation.

I sometimes give the following advice for research which I label Bill's Bad Advice. We will later see who it might be good advice for. Spoiler alert: the number of people for whom it is good advice is shrinking but might include Lance especially now (see his post about stepping down from admin, here).

When you come across a possible research topic or problem, or have some idea, and are wondering if you want to pursue it, here is my bad advice:

1) DON"T CARE if anyone else cares. If YOU care then that is enough to at least get started.

2) DON"T CARE if it has the potential for a published paper. FIRST do the work then, if you feel like it, look for a good venue. You might not bother if posting to arxiv or making an open problems column out of it or a (guest) blog post out of it is a good endpoint. (I run the SIGACT News Open Problems Column- feel free to contact me if you want to submit one.)

3) DON"T CARE if it has practical implications.

4) DON"T CARE if you can get a grant for it. With the current state of the NSF this advice may soon become irrelevant.

5) DON"T CARE if someone else already did it (though at a later stage you should check on this). Even if you work on it and find someone else did it, you will have LEARNED about the problem through your efforts. You might then want to do a survey for your own benefit to consolidate your knowledge.

Why should you NOT CARE about any of these things? Because they get in the way of actually DOING something.

Here are two examples of when this approach WORKED and one where it DID NOT WORK, though both classifications might depend on your definition of WORKED.

WORKED: My work on Muffins. All I wanted was to get some High School and Undergraduate Projects out of it. I ended up with a book on it which made me twenty dollars last year! More to the point, I learned a lot, as did my co-authors and I am happy with the book. The co-authors were Undergraduates so my dept put me up for a mentoring award (I have other credentials as well). I did not win, but I got a nice letter saying they had many qualified applicants. OH- it didn't say if I was one of them.

WORKED: I have had many Ramsey Projects where a High School Student codes stuff up and learns some Ramsey, some coding, and gets the experience of research. Sometimes they do a survey paper or open problems column. We both learn A LOT from this and the student gets a good letter from me. Do they do something NEW? Publishable? No, though some surveys and open problems columns have come out of this. I DO tell them ahead of time that the work is unlikely to lead to original results (and hence unlikely to be good for a science competition).

DID NOT WORK: See this blog post here about the math and here about finding out that the problem we were working on was already known and more was known than we thought. I didn't mind this, but one of the authors did.

Note that WORKED and DID NOT WORK also depend on your goals.

For whom is this bad advice? Good advice?

1) It was always bad advice for young assistant professors who need to get papers and grants to get tenure.

2) Hypothetically, once you get tenure you have job security and hence can change fields or follow my bad advice without consequences. But with grants and salary and teaching load issues, this is less the case. Perhaps I am nostalgic for a time that never was.

3) High School Students were my main audience for bad advice. It's not as important for them to get papers out as for (say) assistant professors. But even this is changing. Colleges are getting more competitive. And HS students may well want a project that can lead to Science competitions. I am not going to say things were better when I was a kid but instead pose non-rhetorical questions:

a) Are high school students getting into research earlier than they used to? I am sure the answer is yes.

b) Are we losing the safe space where a high school student can just learn things and do things and not worry so much about if it's publishable? Yes, but I am not sure how widespread that is.

c) If we are losing that safe space, is that a bad thing?

d) Points a,b,c apply to ugraduates who want to go to graduate school more than for high school students who want to go to college.

4) Full Professors may have more freedom to follow my bad advice. Lance is looking for things to do now that he is no longer a dean, and indeed, is back to being a teaching-and-research professor. So he might follow my advice. However, he actually cares if people care about his work. He does not have to follow all of my advice, but he can follow some of it.