Consistency and P=NP
Can we at least show that is consistent?
[ From personal page ] 
Jan Krajicek is an expert on linking computational complexity and mathematical logic. He has authored four books on this area including the often cited text Bounded Arithmetic and Complexity Theory. Moreover, he has studied the consistency of various of theories and whether they can prove and related questions.
Today I thought we would discuss consistency proofs in general.
Mathematics of COVID19
Its not just
[ Sir Francis Galton by Charles Wellington Furse ] 
Francis Galton is a perfect example of a Victorian era scientist. Sir Galton, he was knighted in 1909, had many roles: a statistician, a sociologist, a psychologist, an anthropologist, a tropical explorer, a geographer, a meteorologist, a geneticist, and an inventor. He coined the phrase “nature versus nurture” and more.
Today we trade in jokes for some mathematics of the virus.
Proof and Cake Envy
Our proofs can be big too
[Mackenzie and Aziz] 
Haris Aziz and Simon Mackenzie are computer scientists at UNSW and CMU respectively. Of course UNSW is the University of New South Wales and CMU is the Carnegie Mellon University.
Today we will discuss cake cutting and more.
Aziz and Mackenzie have solved an open problem concerning how to cut cakes. Their paper is in the April issue of the CACM: “A Bounded and EnvyFree Cake Cutting Algorithm.”
Why Cake Cutting?
Before we talk about cake cutting from a theory viewpoint let’s take a look at why it is interesting. The real answer probably is it is a beautiful math problem. It is easy to state without lots of background. It is simple like Fermat’s Last Theorem:
has no solutions over the integers with and . Cake cutting is hard. We like problems that strike back: problems that are not easy to solve. This is a strange view. In real life we might prefer problems that we can easily solve. But not in math. We like problems that are not trivial. The cake cutting problem is hard, so we like it.
Cutting Cakes
We are theorists so our cakes are onedimensional line segments. The problem involves a finite set of agents, say Alice, Bob, and so on. They want to divide the cake, the line segment, into a finite number of pieces. The pieces are then allocated to the agents. The goal is to get a fair division of the cake.
The notion of “fair” is what makes the problem interesting. Often agents will not have the same tastes: Some like icing more than others, some like the end pieces, while others do not. The fact that the agents assign different values to a piece of the cake is what makes the problem challenging.
If there are two agents the problem has long been solved. Let Bob divide the cake into two pieces, so that he is happy to get either of these pieces. Then have Alice chose which piece she wants. It is easy to see that both Bob and Alice are happy. Both are envyfree: neither would exchange their piece for the others piece.
There is a large literature on the cakecutting problem. Its creator, Hugo Steinhaus, noted:
Interesting mathematical problems arise if we are to determine the minimal numbers of “cuts” necessary for fair division.
We have taken the quote from an article on Medium that neatly conveys details on various protocols. Some main results are:
 The SelfridgeConway discrete procedure produces an envyfree division for people using at most cuts.
 The BramsTaylorZwicker moving knives procedure produces an envyfree division for people using at most cuts.
 Three different procedures produce an envyfree division for people. Both algorithms require a finite but unbounded number of cuts. That is to say, the number of cuts may depend on details of their preference functions.
 The procedure by Aziz and Mackenzie finds an envyfree division for people in a bounded number of cuts.
The last is the result in the CACM paper. Note, the number of cuts can be large:
Even for this is immense, galactic. This should be compared to the best lower bound that is order . This gap is even larger than the usual gaps we find in complexity theory. The P=NP question is only one exponential not five.
This has started me thinking: what exactly is the relationship between this and proof complexity? The latter has wellestablished relationships to complexityclass questions. The link from proofs in various systems of bounded arithmetic goes through the heart of P=NP. See for instance these slides by Sam Buss and notes that were scribed by Ken and others. What I am puzzled by is that in most cases the blowup is only one or two exponentials. The setting with cakecutting is different, but how different?
Easy Cases
The Aziz and Mackenzie algorithm takes a long time. It is a nontrivial result, but not one that applies in any practical case. It always takes way too long. The cake will be stale by the time the agents have agreed on their pieces.
This raises a question, that also applies to many computational problems. Is there a way cut a cake faster on some interesting examples? We can explain this by the analogy to sorting. The fastest sorting algorithms run in time where there are objects. But what happens if the objects are already in sorted order? Or at least close to sorted order? The answer is it depends:
 Some sorting algorithms always take the same time, independent of the input structure.
 There are other sorting algorithms that can take advantage of the nature of the input.
That is some sorting algorithms can run say in linear time if the input is almost sorted. For the cake cutting problem we ask:
Is there a way to cut cakes that is envyfree when the agents have some property ?
We do not know the answer, but we think it is an interesting question. Here is an example. Suppose that the agents have the same measures. That is, they evaluate every piece of cake in the same way.
If we know this—and if we continue our supposition above that Bob can cut with exact precision—then there is an easy answer: Have Bob do the cuts. Then all agents will be equally happy since they have the same measures. The question is, what if we do not know? I believe there should be some theorem like this:
Theorem 1 (Conjecture) There is an envyfree algorithm that operates in time the algorithm so that either:
 It yields an envyfree solution, or
 It determines that some agents have different measures.
In the second case the cake will be cut as before.
Open Problems
I originally planned on discussing size and complexity of proofs. This is driven by the complexity of the cake cutting algorithms. They tend to have lots of cases and are difficult to understand.
They are also difficult to find—this is why cake cutting questions have been resistance to progress. More on this in the future.
[Edit in Fermat example]
John Horton Conway 1937–2020
An appreciation
Names for large numbers source 
John Horton Conway just passed away from complications of COVID19. We are all saddened by this news, and we hope you all are doing your best to stay safe and help others cope.
Today Ken and I thought we would reflect on some of Conway’s many contributions and emphasize three in which we see connections to computational complexity.
Conway was a Fellow of the Royal Society, and was the first recipient of the London Mathematical Society’s Pólya Prize. His nomination to the Royal Society reads:
A versatile mathematician who combines a deep combinatorial insight with algebraic virtuosity, particularly in the construction and manipulation of “offbeat” algebraic structures which illuminate a wide variety of problems in completely unexpected ways. He has made distinguished contributions to the theory of finite groups, to the theory of knots, to mathematical logic (both set theory and automata theory) and to the theory of games (as also to its practice).
A Life Force
Conway may be most noted for his game of Life. This is a twodimensional cellular automaton. Conway invented it in 1970, which he rounded up from 1969. The game—and Martin Gardner’s 1970 column on it in Scientific American—made him famous in the wider community. The website conwaylife.com and several others link to more information than we could digest in a lifetime.
We want to emphasize instead how Conway was a special force in mathematics. He applied an almost elementary approach to deep hard problems of mathematics. This is a unique combination. There have been mathematicians who worked on deep problems and also on recreational math, but few who established integral flows across the boundary between them. Conway infused both with magic in a way conveyed by an iconic photograph of his Princeton office in 1993:
Guardian via Dith Pran, NY Times source 
What Ken remembers is how accessible Conway was outside his office. “I know I met him at least once while I was an undergraduate at Princeton in 1979 or 1980, though this is overlaid by a memory of finding just him and a few others in the Fine Hall tea room when I was there for my tenth reunion in 1991. My most evocative memory is when Conway gave an evening talk to the undergraduate mathematics club at Oxford when I was there sometime after 1981. It was relatively sparsely attended, perhaps because it was literally a dark and stormy winter night. But after his lecture we all got to huddle around him for another hour in the tea room as he regaled us with stories and mathematical problems.”
We also remember that Conway was one of Andrew Wiles’s main confidants during the months before Wiles announced his proof of Fermat’s Last Theorem in June 1993. Here is a transcript of a PBS Nova documentary on the proof in which Conway appears prominently. Ken has picked out two of Conway’s other contributions that we feel may have untapped use for research in complexity theory.
Conway’s Numbers
One of this blog’s “invariants” is firstname lastname style, thus “Godfrey Hardy” not “G.H. Hardy.” But we make an exception in Conway’s case. Partly this owes to how his initials were amplified by Donald Knuth in his novella Surreal Numbers:
In the beginning, everything was void, and J.H.W.H. Conway began to create numbers.
Besides the void (that is, ), the creation uses the idea of a left set and a right set . Every number has the form . The initial number is
Once a number is generated, it can be in the or of other numbers. Thus, next come
You might think of next, but it violates the invariant
which defines an form to be a number.
The relation is inductively defined for and by
That is, no member of the leftset of “bumps” (in the sense of rowing races) and does not bump any member of the rightset of . Note that and are not involved—they already behave correctly owing to the invariant. The numbers are equal if and both hold. The rule for addition is
where and so on. The logical rule for any makes the definition of addition wellfounded. This yields the numerical fact
It is immediate that is commutative. There is also a rule for multiplication but addition gives us enough to talk about here.
Redundancy and Simplicity
It is straightforward to compute that and . Now consider:
This is a legal number. You can check that the relations and both hold. Thus—as a number rather than a “form”—the number equals .
That seems to make sense since is the average of and , but now compute as a formal Conway number and consider . This also satisfies the relations and , so must likewise equal . Thus is not some kind of numerical interpolation between and . The interpretation that grabbed my imagination as a teenager in 1976 is that:
equals the simplest number that is between and .
This is especially evocative in cases like , which is what one gets by computing . In general, is the simplest number between and . Conway made this a theorem by giving each number a settheoretic ordinal for its “time of generation” and proved that always equals a (the) leastordinal number such that for every and .
Conway’s rules allow and to be infinite sets—any sets of numbers built by the rules of set theory. Then not only do all real numbers emerge at ordinal times, so do infinitesimals and further richness of structure. We should remember that Conway began as a set theorist with a dissertation under Harold Davenport titled Homogeneous ordered sets. All Conway numbers with finite creation times are dyadic rational numbers, which may seem trivial from the standpoint of set theory, but those are akin to binary strings.
What became magic was how Conway’s rules characterize games. Through games we can also interpret forms like that are not numbers. I did not know about complexity when I purchased Conway’s book On Numbers and Games around 1980, let alone the connections between games and complexity. The book has a lot of depth that might be useful to complexity theory. To quote Peter Sarnak, per this article by Conway’s biographer Siobhan Roberts on Conway’s meeting with Kurt Gödel:
The surreal numbers will be applied. It’s just a question of how and when.
Modular Programming
Most of us know that the conditionaljump instruction
if (x == 0) goto k
where k is the label of another instruction, creates a universal programming language when added to the usual programming primitives of assignment, sequencing, and simple arithmetic. Conway was a maven of the “modularjump”:
if (x == 0 mod m) goto k.
In complexity theory we know that mod gates having 01 inputs define the idea of circuits, with denoting problems solved by families of these circuits having fixed depth and polynomial size. If we don’t insist on fixed depth and unary inputs, we get modular programs. They are more complex than circuits, but we can learn from what can be done concretely with them.
Conway created a particular form of modular programs in a language he called FRACTRAN. A program is just a list of positive fractions in lowest terms. The input is an integer held in a separate register. Each fraction represents the code line
In other words, each iteration takes the first fraction such that is an integer and updates to ; if there is no such fraction then the program exits and outputs .
For example, the following FRACTRAN program given in Wikipedia’s article implicitly computes integer division:
The notation is unary: The input has the form and the ouput is where with remainder . This already hints the fact that FRACTRAN is a universal programming language. Powers of primes serve as memory registers. The following program computes the Hamming weight of the binary expansion of a natural number encoded as , returning the value :
This might help bridge to our notions of . The Wikipedia article does a good job of demystifying the fractions in terms of their actions on the primepower registers under the unarystyle encoding. We wonder what happens when we try to work directly with binary encodings.
The Collatz Example
The famous “” problem of Lothar Collatz is a case in point. It iterates the function
The following FRACTRAN program given by Kenneth Monks iterates under the unary encoding :
Note that since the last fraction is an integer the program runs forever. If so that the input is , it would go and thus cycle, unless we stop it. The powers of that appear in its output give the desired sequence.
More natural to us, however, is the following modular program—which can use binary or any notation:
start: if (n == 1) { halt; }
if (n == 0 mod 2) { goto div; }
n = 3*n + 1;
div: n = n/2;
goto start;
One can generalize the Collatz problem to moduli . For each we have a linear transformation that always gives an integer value when . We want to know about the orbits of numbers under this iteration.
In fact, this is exactly what FRACTRAN does. Take to be the least common multiple of the denominators in a FRACTRAN program . Then for each we can list the remainders that are multiples of and we get , with . The Turinguniversality of FRACTRAN then proves a general theorem Conway stated in 1972:
Theorem 1 Generalized Collatztype problems for moduli are undecidable.
Several followup papers have proved stronger and more particular forms of the undecidability. The paper by Monks linked above leverages the unary encoding to show that having is essentially without loss of generality for universality; it is titled “ Minus the .”
Having digested universality, it is natural to wonder about complexity. Can we use modular programming to achieve stronger connections between number theory and complexity classes—classes above the level of , say? One possible mode of connection is exemplified by this paper from STACS 1994, which both Dick and I attended. We wonder whether the kind of connection noted by Terry Tao in his tribute to Conway can also smooth the way to understanding .
Open Problems
Conway posed many open problems himself. Here is a list of five for which he posted cash rewards in the manner of Paul Erdős. The fifth was recently solved. The fourth can be stated in one sentence:
If a set of points in the plane intersects every convex region of area 1, then must it have pairs of points at arbitrarily small distances?
Our condolences go out to his family and all who were enthralled by him in the mathematical world. We could talk endlessly about his impact on mathematics education—even about simple things like how to prove that is irrational—or try to tangle with his applications of the “Monster” group to modular forms, but those must be for another time. Also see Scott Aaronson’s tribute and its comments section for many more stories and items.
[some small word and format changes, added link to Scott and may add others as time allows]
Nina Balcan Wins
Congrats and More
[ CMU ] 
Nina Balcan is a leading researcher in the theory of machine learning. Nina is at CarnegieMellon and was previously at Georgia Tech—it was a major loss to have her leave Tech.
Today we applaud her winning the ACM Hopper Award.
Read more…
Not As Easy As ABC
Is the claimed proof of the ABC conjecture correct?

[ Photo courtesy of Kyodo University ] 
Shinichi Mochizuki is about to have his proof of the ABC conjecture published in a journal. The proof needs more than a ream of paper—that is, it is over 500 pages long.
Today I thought we would discuss his claimed proof of this famous conjecture.
The decision to published is also discussed in an article in Nature. Some of the discussion we have seen elsewhere has been about personal factors. We will just comment briefly on the problem, the proof, and how to tell if a proof has problems.
The Problem
Number theory is hard because addition and multiplication do not play well together. Adding numbers is not too complex by its self; multiplication by its self is also not too hard. For those into formal logic the theory of addition for example is decidable. So in principle there is no hard problem that only uses addition. None. A similar point follows for multiplication.
But together addition and multiplication is hard. Of course Kurt Gödel proved that the formal theory of arithmetic is hard. It is not complete, for example. There must be statements about addition and multiplication that are unprovable in Peano Arithmetic.
The ABC conjecture states a property that is between addition and multiplication. Suppose that
for some integers . Then
is trivial. The ABC conjecture says that one can do better and get
for a function that is sometimes much smaller than . The function depends not on the size of but on the multiplicative structure of . That is the function depends on the multiplicative structure of the integers. Note, the bound
only needed that were numbers larger than . The stronger bound
relies essentially on the finer structure of the integers.
Roughly operates as follows: Compute all the primes that divide . Let be the product of all these primes. Then works:
The key point is: Even if , for example, divides , we only include in the product . This is where the savings all comes from. This is why the ABC conjecture is hard: repeated factors are thrown away.
Well not exactly, there is a constant missing here, the bound is
where is a universal constant. We can replace by a smaller number—the precise statement can be found here. This is the ABC conjecture.
The point here is that in many cases is vastly smaller than and so that inequality
is much better than the obvious one of
For example, suppose that one wishes to know if
is possible. The ABC conjecture shows that this cannot happen for large enough. Note
for positive integers .
Is He Correct?
Eight years ago Mochizuki announced his proof. Now it is about to be published in a journal. He is famous for work in part of number theory. He solved a major open problem there years ago. This gave him instant credibility and so his claim of solving the ABC conjecture was taken seriously.
For example, one of his papers is The Absolute Anabelian Geometry of Canonical Curves. The paper says:
How much information about the isomorphism class of the variety is contained in the knowledge of the étale fundamental group?
A glance at this paper shows that it is for specialists only. But it does seem to be math of the type that we see all the time. And indeed the proof in his paper is long believed to be correct. This is in sharp contrast to his proof of the ABC conjecture.
Indicators of Correctness
The question is: Are there ways to detect if a proof is (in)correct? Especially long proofs? Are there ways that rise above just checking the proof line by line? By the way:
The length of unusually long proofs has increased with time. As a rough rule of thumb, 100 pages in 1900, or 200 pages in 1950, or 500 pages in 2000 is unusually long for a proof.
There are some ways to gain confidence. Here are some in my opinion that are useful.
 Is the proof understood by the experts?
 Has the proof been generalized?
 Have new proofs been found?
 Does the proof have a clear roadmap?
The answer to the first question (1) seems to be no for the ABC proof. At least two world experts have raised concerns—see this article in Quanta—that appear serious. The proof has not yet been generalized. This is an important milestone for any proof. Andrew Wiles famous proof that the Fermat equation
has no solutions in integers for and a prime has been extended. This certainly adds confidence to our belief that it is correct.
Important problems eventually get other proofs. This can take some time. But there is almost always success in finding new and different proofs. Probably it is way too early for the ABC proof, but we can hope. Finally the roadmap issue: This means does the argument used have a nice logical flow. Proofs, even long proofs, often have a logic flow that is not too complex. A proof that says: Suppose there is a object with this property. Then it follows that there must be an object so that Is more believable than one with a much more convoluted logical flow.
Open Problems
Ivan Fesenko of Nottingham has written an essay about the proof and the decision to publish. Among factors he notes is “the potential lack of mathematical infrastructure and language to communicate novel concepts and methods”—noting the steep learning curve of trying to grasp the language and framework in which Mochizuki has set his proof. Will the decision to publish change the dynamics of this effort?
[Fixed typo]
Research at Home
An idea for humaninterest interviews
Pixabay free src 
Dr. Lofa Polir is, like many of us, working from home. When we last wrote about her two years ago, she had started work for the Livingston, Louisiana branch of LIGO. They sent her and the rest of the staff home on March 19 and suspended observations on the 26th. Since Polir’s duties already included public outreach, she is looking to continue that online.
Today we helped Dr. Polir interview another pandemicaffected researcher.
We liked her idea of interviewing young people just starting their careers, who are facing unexpected uncertainties. Her first choice was a new graduate of Cambridge University doing fundamental work related to LIGO. Unfortunately, he had been unable to install a current version of Zoom on his handheld device, or maybe afraid owing to security issues. So she requested the special equipment we have used to interview people in the past.
He replied at the speed of light that he was willing to do the interview so long as we respected some privacy measures. As for what name to use, he said we could just call him Izzy—Izzy Jr., in fact. So Dick, I, and Dr. Polir all used our own Zoom to port into our machine’s console room. The connection worked right away as Izzy’s head glimmered into view.
Starting The Interview
At first glimpse, all we could see was his long, lightbrown hippie hair. This really surprised us—not the image we had of Cambridge—and we gasped about it before even saying hello. He replied that it was fashion from the Sixties. We asked how his family was doing and he said his fathers had passed on but mother and young siblings were at home and fine. We think he said “fathers” plural—the machine rendered him in a drawl like Mick Jagger and he was hard to follow.
Izzy picked up on our discomfort and immediately assured us he hadn’t been doing any drugs: “You can’t get them anyway because they’re all being diverted to treat the sick.” But he did open up to us that he was in some kind of withdrawal. He confessed that he had resorted to looking at the sun with one eye. “It was ecstasy but bad—I still can see only reds and blues with that eye, and I need to use an extralarge rectangular cursor to read text.” We were curious what brand of handheld device he was using because of his problems with Zoom, and he told us it was a Napier 1660 by Oughtred, Ltd. We hadn’t heard of that model but he said he’d connected three of them into a good home lab setup.
We asked how he was coping with distance teaching, but he said he hadn’t yet started his faculty position at Trinity College. We were surprised to learn that lecture attendance at Cambridge University is optional. “I shall be required to give the lectures but nobody will come to them so that’s all the same now—at least here I’ll have a cat for audience. No dogs and not my mother or siblings—I’d sooner burn the house down.” He quickly added, “Oh, my mother and I get along fine now and I love playing teatime with my little sisters.”
We really didn’t want to go into Izzy’s personal life, and I tried to shift the smalltalk by noting a little chess set on a shelf behind him. He snapped that he shouldn’t have spent money on it and he was a poor player anyway. We thought, wow, either this guy’s really down on himself or the cabin fever of the pandemic is getting to him. So Dick, always quick to pick up on things and find ways of encouragement, said:
“Dr. Polir here works on gravity and we’re told you have some great new ideas about it. We’d love to hear them.”
“Yes, I do—or did. But something happened yesterday that is making me realize that it’s all wrong, rubbish really…”
In the Garden
Izzy started by explaining that it’s a basic principle of alchemy that all objects have humors that can manifest as kinds of magnetism. (“Alchemy”? did we hear him right?) If you realize that the Earth and Sun are objects just like any other then you can model gravity that way. You just need to assign each object a number called its “mass” and then you get the equation
for the force of attraction, where is the distance between the objects with masses and is a constant that depends on your units.
“We understand all that,” said Dr. Polir.
Izzy said the point is that depends only on your units and is the same regardless of where you are on Earth or on the Moon or wherever. It is very small, though. Then he went into his story of yesterday.
“I was in our garden by the path to the neighbor’s farm. I was supposed to be watching my little brother Benjamin who wanted to help harvest squash but I hate farming so I let him go without me. I was lying under an apple tree for shade when an apple fell and I realized all my mistakes.”
“What?,” we thought silently. We didn’t need to speak up—Izzy launched right into his litany of error:
“First, I’d thought the force was in what made the apple fall, but that’s nonsense. The apple would fall naturally because down is the shortest path it would be on if the tree branch were not holding it back. The only force is the tensile strength of the branch which was restraining it. I think that the tensile force really is magnetism, by the way.”
“Second, it’s ridiculous to think the force is coming from the Earth. On first principles, it could come from the ground, but that’s not what the equations say. They could have it all coming from one point in the center of the Earth. Just one point—four thousand miles deep!”
“Third and worst, though, is when you apply it to the Sun and the Earth. My equation means they are exerting force on each other instantaneously. But they are millions of miles apart. Whereas, the tree was touching the apple. Force can work only by touch, not by some kind of spooky action at a distance.”
We realized what he was driving at. Dick again always likes to encourage, so he said:
“But the math you developed for this force theory—surely it is good for calculations…?”
“No it’s not—it’s the Devil’s own box. I can calculate two bodies—the Earth and the Sun, or the Moon and the Earth if you suppose there is no Sun, but as soon as you have all three bodies it’s a bog. Worst of all, I can arrange five bodies so that one of them gets accelerated to infinite velocity—in finite time. This is a clear impossibility, a contradiction, so by modus tollens… it can all go in the bin.”
We didn’t think it would help to tell him that his math was good enough to calculate a Moon landing but not to locate a friend’s house while driving. He supplied his own coupdegrâce anyway:
“And even the twobody calculations are tainted. I can calculate the orbits of the planets but the equations I get aren’t stable. I would wind up having to postulate something like God keeps the planets on their tracks. Yes, you need an intelligent Agent to start the planets going—all in one plane, basically—but to need such intervention all the time defeats the point of having equations.”
Inklings
We asked Izzy what he was going to do. He said that the one blessing of enforced solitude is that one gets time to reflect on things and deepen the foundations. And he said he’d had an idea later that afternoon.
“Toward supper I realized I needed to get Benjamin home. The path to the farm is straight except it goes over a mound. I was sauntering along and when I got to the hill I realized that if I didn’t watch it I’d have fallen right into it. So that got me thinking. First, what I thought was straight on the path was really a curve—the Earth is after all a ball. We think space is straight, but maybe it too is curved. So when I’m standing here, perhaps I would really be moving in a diagonally down direction, but the Earth is stopping me. The Irish blessing says, ‘may the road rise up to meet you.’ Perhaps it does.”
“So are you doing math to work that out?,” I ventured.
“I started after supper. One good thing is that it allows light to be affected by gravity—which I was already convinced of—even if light has no mass. But a problem is that it appears Time would have to be included as curved. That does not make sense either.”
We asked when he might write up all this. He said he didn’t want to be quick to publish something so flawed on the one hand, or incomplete on the other, “unless someone else be about to publish the same.” We noted that there weren’t going to be any inperson conferences to present papers at for awhile anyway.
“Besides, that’s not what I’m most eager to do. What the respite is really giving me time for is to start writing up my work on Theology. That’s most important—it could have stopped thirty years of war. For one thing, homoiousios, not homoousios, is the right rendering. There will be a time and times and the dividing of times in under 400 years anyway.”
That last statement somehow did not reassure us. We thanked Izzy Jr. for the interview and he gave consent to publish it posthumously.
Open Problems
We hope that your April Fool’s Day is such as to allow a time to laugh. But also seriously, would you be interested in the idea of our interviewing people during these times? Is there anyone you would like to suggest?
Logic and StarFree, Part Deux
A visual proof with no abstractalgebra overhead
Composite crop of src1, src2 
Dominique Perrin and JeanÉric Pin are French mathematicians who have done significant work in automata theory. Their 1986 paper “FirstOrder Logic and StarFree Sets” gave a new proof that firstorder logic plus the relation characterizes starfree regular sets.
Today we present their proof in a new visual way, using “stacked words” rather than their “marked words.” We also sidestep algebra by appealing to the familiar theorem that every regular language has a unique minimal deterministic finite automaton (DFA).
Read more…
StarFree Regular Languages and Logic
Part 1 of a twopart series
Daniel Winton is a graduate student in mathematics at Buffalo. He did an independent study with me last semester on descriptive complexity.
Today we begin a twopart series written by Daniel on a foundational result in this area involving firstorder logic and starfree languages.