A Simple Fact

Can we find a simplest proof?

Composite crop from src1, src2

Joseph Wedderburn and Leonard Dickson proved Wedderburn’s “Little” Theorem: that every finite ring with the zero-product property is a field. Which of them proved it first is hard to tell.

Today we discuss the issue of finding simple proofs for simple facts—not just Wedderburn’s theorem but the zero-product property on which it leans.

Dickson was a professor at the University of Chicago when Wedderburn visited on a Carnegie Fellowship in 1904–05. To judge from several sources, what happened is that Wedderburn first claimed a proof. Dickson did not believe the result and tried to build a counterexample. Instead he found a lemma that convinced him it was true and used it to give a simpler proof. They gave back-to-back presentations on 20 January, 1905, Wedderburn wrote up his paper with his proof and two more based on the lemma, which Wedderburn ascribed to an earlier paper by George Birkhoff and Harry Vandiver. Dickson wrote a paper with his approach, saying in a footnote:

First proved by Wedderburn … Following my simpler proof above, and using the same lemma, Wedderburn constructed two further simpler proofs.

However, Wedderburn’s first proof was found to have a gap. As detailed by Michael Adam and Birte Specht, the gap was a statement that was not false per se but whose vague argument used only properties from a class of weaker structures in which it can fail. So:

Who first proved the theorem?

Other Proofs, Other Properties

Our sources linked above differ on whether the gap was noticed at the time or anytime before Emil Artin remarked on it in 1927. Artin didn’t discuss the gap but gave his own proof instead. There seems to be consensus that the “proof from the Book” was given by Ernst Witt four years later in 1931. But two other proofs, by Israel Herstein and by Hans Zassenhaus, receive prominent mention.

As our sources attest, interest in finding other proofs continues. The surprise in the theorem, which is that finiteness and the zero-product property force the multiplication to be commutative, informs what happens in other mathematical structures. Proofs that draw on results about these structures create connections among many areas. The shortest proof drawing on deeper results was a two-page paper in the summer 1964 Monthly by Theodore Kaczynski (of ill note). We won’t try to compare all these proofs, but will try to flip the question by focusing on the other property involved—the zero-product property:

If then or .

Given a ring with this property, how easy is it to prove? If has inverses then it is immediate, else multiplying both sides of by in front and in back would yield the contradiction . And we know if is finite then this property makes it a field. So our quest for a different angle leads us to thinking about infinite rings.

Incidentally, a ring with the zero-product property is called a domain. If the multiplication is commutative then it is an integral domain, though Serge Lang preferred the term entire ring. Our example goes beyond the integers though.

No Zero-Divisors I

A natural example that arises is the ring of integer polynomials over multiple variables. Thus for two variables the elements of this ring are

It is easy to see that they form a ring with the usual high school rules for adding and multiplying polynomials. The ring is an integral domain in general.

To show this, we claim that it has no zero-divisors. Suppose that it does: let . Then let

and

Assume that the maximum degree in for is and is for . Then and are both non-zero polynomials in one variable. It is clear by induction that is not zero. This proves the claim.

No Zero-Divisors II

The trouble with the above property of polynomials is that it is only about formal objects. In many applications to computer science we want to view polynomials as objects that can be evaluated. So a natural issue is a slightly different property: Suppose that and are two integral polynomials. Suppose further that

for all integers . Then it clearly must be the case that either identically or identically. Right?

The trouble is that this seems to be obvious but how do we prove that it is true? Note, it must be the case that some use of the fact that and are polynomials. The fact is not true for more complex functions. For example,

for all integers . But neither the function nor is identically zero for all integers.

A Proof

Here is a relatively simple proof of the fact. It uses the famous Schwarz-Zippel (SZ) Theorem. See here for our discussion of the theorem.

Theorem 1 Let be in be a non-zero polynomial of total degree over a field . Let be a finite subset of and let be selected at random independently and uniformly from . Then

The S-Z lemma of course has manifest applications throughout complexity theory. Often it is used in design of randomized algorithms. What we found interesting is that here we use it for a different purpose: to prove a structural property of polynomials.

Back to our fact. Assume that

for all integers and for some finite set. Now either or must be true for at least one half of the values in . Assume that it is . Then by the S-Z theorem it must be that always if the set is large enough. Therefore, the fact is proved.

Open Problems

Is there a simpler proof of this key fact? Is it possible to find an easier reference in the literature of this basic fact of polynomials? We have yet to discover one—any help would be appreciated.

Advertisements

Jean Bourgain 1954–2018 and Michael Atiyah 1929–2019

A tribute to two premier analysts

From Flanders Today src1 and Ryle Trust Lecture src2

Baron Jean Bourgain and Sir Michael Atiyah passed away within the past three weeks. They became mathematical nobility by winning the Fields Medal, Atiyah in 1966 and Bourgain in 1994. Bourgain was created Baron by King Philippe of Belgium in 2015. Atiyah’s knighthood did not confer nobility, but he held the dynastic Order of Merit, which is limited to 24 living members and has had fewer than 200 total since its inception in 1902. Atiyah had been #2 by length of tenure after Prince Philip and ahead of Prince Charles.

Today we discuss how they ennobled mathematics by their wide contributions.

Bourgain was affiliated to IAS by the IBM John von Neumann Professorship. He had been battling cancer for a long time. Here is the middle section of the coat of arms he created for his 2015 investiture:

Detail from IAS source

The shield shows the beginning of an Apollonian circle packing, in which every radius is the reciprocal of an integer. This property continues as circles are recursively inscribed in the curvilinear regions—see this 2000 survey for a proof. To quote Bourgain’s words accompanying his design:

The theory of these [packings] is today a rich mathematical research area, at the interface of hyperbolic geometry, dynamics, and number theory.

Bourgain’s affinity to topics we hold dear in computing theory is shown by this 2009 talk titled, “The Search for Randomness.” It covers not only PRNGs and crypto but also expander graphs and succinctness in quantum computing. He has been hailed for diversity in other mathematical areas and editorships of many journals. We will talk about a problem in analysis which he helped solve not by analytical means but by connecting the problem to additive combinatorics.

From Analysis to Combinatorics

Sōichi Kakeya posed the problem of the minimum size of a subset of in which a unit-length needle can be rotated through 360 degrees. Abram Besicovitch showed in 1928 that such sets can have Lebesgue measure for any . He had already shown that one can achieve measure zero with a weaker property, which he had used to show a strong failure of Fubini’s theorem for Riemann integrals:

For all there is a measure-zero subset of that contains a unit line segment in every direction.

The surprise to many of us is that such strange sets would have important further consequences in analysis. A 2008 survey in the AMS Bulletin by Izabella Łaba, titled “From Harmonic Analysis to Arithmetic Combinatorics,” brings out breakthrough contributions by Bourgain to conjectures and problems that involve further properties of these sets, which seem to retain Kakeya’s name:

Conjecture: A Kakeya set in must have Hausdorff dimension .

This and the formally weaker conjecture that the set must have Minkowski dimension are proved in but open for all . Bourgain first proved that the restriction conjecture of Elias Stein, which is about extensions of the Fourier transform from certain subspaces of functions from to to operators from to functions on , implies the Kakeya conjecture. It is likewise open for . As Łaba writes, associated estimates “with require deeper geometrical information, and this is where we find Kakeya sets lurking under the surface.”

What Bourgain showed is that the restriction estimates place constraints on sets of lower Hausdorff dimension that force them to align “tubes” along discrete directions that can be approximated via integer lattices. This led to the following “key lemma”:

Lemma 1 Consider subsets of , where and are finite subsets of , and define

For every there is such that whenever , where , we have .

To quote Łaba: “Bourgain’s approach, however, provided a way out. Effectively, it said that our hypothetical set would have structure, to the extent that many of its lines would have to be parallel instead of pointing in different directions. Not a Kakeya set, after all.” She further says:

Bourgain’s argument was, to this author’s knowledge, the first application of additive number theory to Euclidean harmonic analysis. It was significant, not only because it improved Kakeya bounds, but perhaps even more so because it introduced many harmonic analysts to additive number theory, including [Terence] Tao who contributed so much to the subject later on, and jump-started interaction and communication between the two communities. The Green-Tao theorem [on primes] and many other developments might have never happened, were it not for Bourgain’s brilliant leap of thought in 1998.

Among many sources, note this seminar sponsored by Fan Chung and links from Tao’s own memorial post.

Michael Atiyah

Michael Atiyah was also much more than an analyst—indeed, he was first a topologist and algebraic geometer. He was also a theoretical physicist. Besides all these scientific hats, he engaged with society at large. After heading Britain’s Royal Society from 1990 to 1995, he became president of the Pugwash Conferences on Science and World Affairs. This organization was founded by Joseph Rotblat and Bertrand Russell in the 1950s to avert nuclear war and misuse of science, and won the 1995 Nobel Peace Prize.

The “misuse of science” aspect comes out separately in Atiyah’s 1999 article in the British Medical Journal titled, “Science for evil: the scientist’s dilemma.” It lays out a wider scope of ethical and procedural concerns than the original anti-war purpose. This is furthered in his 1999 book chapter, “The Social Responsibility of Scientists,” which laid out six points including:

• First there is the argument of moral responsibility. If you create something you should be concerned with its consequences. This should apply as much to making scientific discoveries as to having children.

• Scientists will understand the technical problems better than the average politician or citizen and knowledge brings responsibility.

• [T]here is need to prevent a public backlash against science. Self-interest requires that scientists must be fully involved in public debate and must not be seen as “enemies of the people.”

As he says in its abstract:

In my own case, after many years of quiet mathematical research, working out of the limelight, a major change occurred when unexpectedly I found myself president of the Royal Society, in a very public position, and expected to act as a general spokesman for the whole of science.

Within physics and mathematics, he also ventured into a debate that comes closer to the theory-as-social-process topic we have discussed on this blog. In 1994 he led a collection of community responses to a 1993 article by Arthur Jaffe and Frank Quinn that began with the question, “Is speculative mathematics dangerous?” Atiyah replied by saying he agreed with many of their points, especially the need to distinguish between results based on rigorous proofs and heuristic arguments,

…But if mathematics is to rejuvenate itself and break exciting new ground it will have to allow for the exploration of new ideas and techniques which, in their creative phase, are likely to be as dubious as in some of the great eras of the past. …[I]n the early stages of new developments, we must be prepared to act in more buccaneering style.

Now we cannot help recalling his claim last September of heuristic arguments that will build a proof of the Riemann Hypothesis, which we covered in several posts. As we stated in our New Year’s post, nothing more of substance has come to our attention. We do not know how much more work was done on the promised longer paper. We will move toward discussing briefly how his most famous work is starting to matter in algorithms and complexity.

Indexes and Invariants

We will not try to go into even as much detail as we did for Kakeya sets about Atiyah’s signature contributions to topological K-theory, physical gauge theory, his celebrated index theorem with Isadore Singer, and much else. But we can evoke reasons for us to be interested in the last. We start with the simple statement from the essay by John Rognes of Oslo that accompanied the 2004 Abel Prize award to Atiyah and Singer:

Theorem 2 Let be a system of differential equations. Then

Here the analytical index equals the dimension of the kernel of minus the dimension of the co-kernel of , which (again quoting Rognes) “is equal to the number of parameters needed to describe all the solutions of the equation, minus the number of relations there are between the expressions .” The topological index has a longer laundry list of items in its definition, but the point is, those items are usually all easily calculable. It is further remarkable that in many cases we can get without knowing how to compute and individually. The New York Times obituary quotes Atiyah from 2015:

It’s a bit of black magic to figure things out about differential equations even though you can’t solve them.

One thing it helps figure out is satisfiability. Besides cases where knowing the number of solutions does help in finding them, there are many theorems that needed only information about the number and the parameterization.

We have an analogous situation in complexity theory with the lower bound theorem of Walter Baur and Volker Strassen, which we covered in this post: The number of multiplication gates needed to compute an arithmetical function is bounded below by a known constant times the log-base-2 of the maximum number of solutions to a system formed from the partial derivatives of and a certain number of linear equations, over cases where that number is finite. Furthermore, both theorems front on algebraic geometry and geometric invariant theory, whose rapid ascent in our field was witnessed by a workshop at IAS that we covered last June. That workshop mentioned not only Atiyah but also the further work in algebraic geometry by his student Frances Kirwan, who was contemporaneous with Ken while at Oxford. Thus we may see more of the kind of connections in which Atiyah delighted, as noted in current tributes and the “matchmaker” label which was promoted at last August’s ICM.

Open Problems

Our condolences go out to their families and colleagues.

[more tribute links]

Predictions For 2019

The problem of predicting ‘when’ not just ‘what’

Cropped from Toronto Star source

Isaac Asimov was a prolific writer of science fiction and nonfiction. Thirty-five years ago, on the eve of the year 1984, he noted that 35 years had passed since the publication of George Orwell’s 1984. He wrote an exclusive feature for the Toronto Star newspaper predicting what the world would be like 35 years hence, that is, in 2019.

Today we give our take on his predictions and make our own for the rest of 2019.

ACM Great Results

A Puck-ish take on promised technological advances

Wikimedia Commons source

Knecht Ruprecht accompanies Santa Claus in Germany. He brings gifts to good children but lumps of coal to naughty ones. He is regarded more generally as the German counterpart to England’s Robin Goodfellow, aka. Puck. The Simpsons’ dog “Santa’s Little Helper” is named “Knecht Ruprecht” in the show’s German edition.

Today we do a nice-or-naughty riff on technological gifts suggested by yesterday’s ACM TechNews mailing.

Explanations and Explorations

Comparing proofs for the Jaccard metric

BetterExplained source

Kalid Azad is the founder of the website Better Explained. It is devoted to explaining mathematical concepts. He also has written two books.

Today we discuss how some proofs provide a concise explanation whereas others promote exploration of related concepts.

Explaining The Jaccard Metric

Why is it a metric?

Composite of source 1, source 2

Paul Jaccard was a botanist who worked at ETH in Zurich during much of the first half of the 20th century. He created, or discovered, the similarity notion that became the Jaccard metric. Very neat having a metric named after you.

Today we discuss proofs and explanations that the metric is indeed a metric.

Transposing

On the arithmetic complexity of the matrix transpose

[ KKB ]

Michael Kaminski, David Kirkpatrick, and Nader Bshouty are complexity theorists who together and separately have proved many wonderful theorems. They wrote an interesting paper recently—well not quite—in 1988 about the transpose operation.

Today we want to discuss an alternative proof of the main result of that paper.