Skip to content

A Simple Fact

January 21, 2019


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 {a \cdot b = 0} then {a = 0} or {b = 0}.

Given a ring {R} with this property, how easy is it to prove? If {R} has inverses then it is immediate, else multiplying both sides of {a\cdot b = 0} by {a^{-1}} in front and {b^{-1}} in back would yield the contradiction {1 = 0}. And we know if {R} 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 {x,y} the elements of this ring are

\displaystyle  \sum_{i,j} c_{ij}x^{i}y^{j}.

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 {f(x,y) \cdot g(x,y) = 0}. Then let

\displaystyle  f(x,y) = \sum_{k} f_{k}(x) y^{k},

and

\displaystyle  g(x,y) = \sum_{k} g_{k}(x) y^{k}.

Assume that the maximum degree in {y} for {f(x,y)} is {df} and is {dg} for {g(x,y)}. Then {f_{df}(x)} and {g_{df}(x)} are both non-zero polynomials in one variable. It is clear by induction that {f_{df}(x) \cdot g_{dg}(x)} 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 {F(x,y,\dots)} and {G(x,y,\dots)} are two integral polynomials. Suppose further that

\displaystyle  F(a,b,\dots) \cdot G(a,b,\dots) = 0,

for all integers {a,b,\dots}. Then it clearly must be the case that either {F=0} identically or {G=0} 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 {F} and {G} are polynomials. The fact is not true for more complex functions. For example,

\displaystyle  \cos(\pi x) \cdot \sin(\pi x) = 0,

for all integers {x}. But neither the function {\cos(\pi x)} nor {\sin(\pi x)} 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 {P} be in {\mathbb{F}[x_1,x_2,\ldots,x_n]} be a non-zero polynomial of total degree {d} over a field {\mathbb{F}}. Let {S} be a finite subset of {\mathbb{F}} and let {r_{1},\dots,r_{n}} be selected at random independently and uniformly from {S}. Then

\displaystyle  \Pr[P(r_1,r_2,\ldots,r_n)=0] \leq \frac{d}{|S|}.

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

\displaystyle  F(a,b) \cdot G(a,b) = 0,

for all integers {a \in S} and {b \in S} for some finite set. Now either {F(a, b)=0} or {G(a, b)=0} must be true for at least one half of the values in {S \times S}. Assume that it is {F}. Then by the S-Z theorem it must be that {F=0} always if the set {S} 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s