Examples of proofs by making reduction to a finite set [closed]

Question

This is a very abstract question, I hope this is appropriate.
Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "for every element $a \in A$, the chromatic number of $a$'s dual graph is $\leq 4$" (this is known as "Four-color Theorem"); or, let $A = \mathbb{N}$, and $T$ be the claim "there are no 3 elements $x, y, z \in A$ such that $x^5 + y^5 =z^5$" (a specific case of Fermat's last theorem).
In the first example, it is possible to prove the claim $T$ by testing some claim $T'$ over finite set $A' \subset A$, see proof by computer section. This is done by a series of reductions, showing that if all the elements in some finite set satisfy a property, then the (original) claim holds.
In some sense, mathematical induction is similar: we test a claim on finite set ("the base case"), then proving $a_n \rightarrow a_{n+1}$, which shows the claim is correct for all space.

Are there more known cases like that? i.e. proving (a combinatorial) claim by reduction to finite cases?

Answer 1

Doron Zeilberger has beat the drum rather enthusiastically for this style of argument; see for example his paper The C-finite Ansatz. M. D. Hirschhorn has a paper entitled A Proof in the Spirit of Zeilberger of an Amazing Identity of Ramanujan in which he says,

In this paper I show that in order to prove Ramanujan's statement it is sufficient to check just the first seven cases, and then I do so.

More controversially, Zeilberger goes further and champions the notion of a "semi-rigorous proof," saying that even if we don't have a fully rigorous proof that the finitely many cases we have checked imply the general case, often the finitely many cases are "good enough." However, even if you don't agree with Zeilberger's attitude toward semi-rigorous proofs, he and his collaborators have many examples of fully rigorous proofs of the type you are looking for.

Answer 2

The 15 and 290 theorems are of this form. For example, the 15 theorem says that if a positive definite quadratic form with integer matrix represents all positive integers up to 15, then it represents all positive integers.

Answer 3

It is very common, when finding solutions to Diophantine equations, to use Baker's method of linear forms in logarithms to reduce the problem to a finite computation (that is, to find an upper bound for the solutions).

Answer 4

For the sake of completeness, let me mention the direction which is opposite to the OP's Question.

There are combinatorial optimizations problems which deal with a finite (but large) input set at the start, and the point is to optimize a real function over the input. Such problems are often messy.

Then, some time ago, Hungarian mathematicians started to embed the input set into a Euclidean n-space, and they'd extend the said function to a linear or convex function over the convex hull of the input. Since the optimum over the whole hull is reached at a vertex then... etc.

We see that sometimes situations which are strictly finite (looking for an exact answer) get hm-reduced to infinite situations.

Answer 5

In 1972, I have developed a general theory of isometric embeddings of finite metric spaces into finite-dimensional Banach spaces, in particular, the injective case, i.e. into metrically injective spaces $\mathbb R^n$ with metrics given by $\max$. An announcement has appeared a couple of years later in AMS Notices. One of the theorems fits the present thread:

For every natural $k\ n$, there is an EXPLICIT natural constant $\mu(k\ n)$ such that the following two statements are equivalent:

(i) every $k$-element metric space can be isometrically embedded into $\mathbb R^n$ with the distance given by $\max$;

(ii) every $k$-element metric space with integer distances and of diameter ${\leq} \mu(k\ n)$ can be isometrically embedded into subspace $\{0\ \ldots\ \mu(k, n)\}^n$ of $\mathbb R^n$ with the distance given by $\max$.

For each natural $\ n,\ $ there exists a maximal $\ u(n)=k\ $ as above; and also $\ U(n)\ $ similar to $\ u(n)\ $ but for ALL $n$-dimensional Banach spaces TOGETHER (for each fixed dimension $\ n).\ $ Then in the non-trivial case of $\ n \geq 2\ $ we get

$$ n+2 \leq u(n) \leq U(n) \leq \left\lceil\frac{3\cdot n}2\right\rceil + 1 $$

We see from (i)+(ii) that finding $u(n)$ has been reduced to a finite computation.

Answer 6

Hales' proof of the Kepler conjecture:

"... he embarked on a research program to systematically apply linear programming methods to find a lower bound on the value of this function for each one of a set of over 5,000 different configurations of spheres. If a lower bound (for the function value) could be found for every one of these configurations that was greater than the value of the function for the cubic close packing arrangement, then the Kepler conjecture would be proved. To find lower bounds for all cases involved solving about 100,000 linear programming problems." [Wikipedia]

Answer 7

For a somewhat different class of examples, there are some problems in differential topology that can be solved with bordism:

1. First, show that the quantity you want to compute is a bordism invariant, i.e. a group homomorphism from the appropriate bordism group to an abelian group.
2. Then, determine a finite list of generators of the bordism group. (This step is typically the most difficult.)
3. Check on the generators.

Thus a problem that a priori is about an incredibly large number of manifolds and must be checked in generality is reduced to a finite set of cases.

Here are some examples.

• In dimension 4, the Hirzebruch signature theorem states that if $M$ is a closed, oriented 4-manifold, the first Pontrjagin number of $M$ is three times the signature $\sigma(M)$ of its intersection form. One proves this by showing that both $\sigma(M)$ and $p_1(M)$ are oriented bordism invariants, and that the bordism group $\Omega_4^{\mathrm{SO}}\cong\mathbb Z$, generated by the class of $\mathbb{CP}^2$. It then suffices to compute $\sigma(\mathbb{CP}^2)=1$ and $p_1(\mathbb{CP}^2)=3$.
• Rokhlin's theorem, that the signature of a closed, spin 4-manifold is divisible by 16, can be proven in a similar way: $\Omega_4^{\mathrm{Spin}}\cong\mathbb Z$, and the class of the K3 surface is a generator. Then one computes $\sigma(\mathrm{K3}) = -16$. (However, this isn't the standard proof.)
• An application to mathematical physics: while we don't know rigorously what a quantum field theory is, physical arguments suggest that it should come with data of an anomaly, which generally determines a bordism invariant in one dimension higher. Anomaly cancellation involves proving this bordism invariant vanishes, which can be checked on a set of generators. For example, a recent paper of Freed and Hopkins applies this to M-theory.