Three-Fold Closure Forces Two-Fold Closure
Field: Algebra (semigroups) ยท Putnam 1995 A1
Problem. Let be a set of real numbers that is closed under multiplication: if , then . Let and be disjoint subsets of whose union is . Suppose:
- the product of any three elements of (not necessarily distinct) is in , and
- the product of any three elements of (not necessarily distinct) is in .
Show that at least one of and is closed under multiplication of two elements.
Warm-up sanity check. Take , and .
- The product of three negatives is negative, so satisfies the hypothesis.
- The product of two negatives is positive, so is not closed under multiplication of two elements.
- , however, is closed.
So the conclusion "at least one" cannot be strengthened to "both".
Why it's interesting: The statement sounds like it needs structure theory, such as sign characters or homomorphisms to . In fact it falls to a single product of four elements that you are allowed to bracket in two different ways. It is a good example of using associativity as a weapon.
Estimated difficulty: 2 / 5
Reference: 56th Putnam (1995), Problem A1; solution following Kiran Kedlaya's writeup (materials: putnam/1995s.pdf).
Answer: Three-Fold Closure Forces Two-Fold Closure
Key Idea / Intuition
Suppose both and fail to be closed. Then some pair from "leaks" into , and some pair from leaks into . Multiply both leaky pairs together to get four numbers. The same product can be bracketed as "one element of times two elements of " or as "two elements of times one element of ." The three-fold rule then forces this single number to lie in both and , which is impossible because they are disjoint.
The whole proof is: one product, two bracketings, two incompatible verdicts.
Formal Proof / Solution
Step 1: Assume both fail. Suppose, for contradiction, that neither nor is closed under multiplication. Then:
- there exist with ;
- there exist with .
Step 2: Locate the leaked products. Since is closed under multiplication, and . Since , it follows that
Step 3: Bracket the same product two ways. Consider
- First bracketing. Write . Each of the three factors lies in . By the three-fold hypothesis for , we get .
- Second bracketing. Write . Each of the three factors lies in . By the three-fold hypothesis for , we get .
Both bracketings are legitimate because multiplication of real numbers is associative.
Step 4: Contradiction. We have found , but and are disjoint. Hence our assumption was false, and at least one of , is closed under multiplication.
Remarks
- What was actually used. We used only that multiplication is associative. Commutativity was not needed, and neither was the fact that we are working with real numbers. The same argument works in any semigroup .
- The model example. Positives versus negatives is the prototype. There, behaves like the "odd" coset of a -grading. Three-fold closure is exactly what an odd coset satisfies, since odd + odd + odd is odd. The theorem says that two such "odd-like" pieces cannot coexist.
- The general lesson. When a hypothesis is about -fold products and the conclusion is about -fold products, try building a single product that can be read as a -fold product in two different ways.
Source: 56th William Lowell Putnam Competition (1995), Problem A1; solutions by Kiran Kedlaya (materials/putnam/1995s.pdf)