Results where complexity bounds implies finite number of test cases

Question

We have all been there, when a formula works for the first 30 parameters, but it is not sufficient for a proof. My question is where one can actually just check a finite number of cases, to conclude that a formula is correct.

That is, let $f,g : S \to \mathbb{N}$ be two functions from some (infinite) set $S$, say the natural numbers, or permutations, graphs, etc. Assume that $f$ and $g$ are not too complicated (some measure of complexity here is needed, or they belong to some special family).

What types of theorems are there of the form $f(S_k)=g(S_k)$ for $k=1,2,\dots,\max \{ C(f), C(g) \}$ implies $f \equiv g$? Here, the $S_k$ are members of $S$ in some natural order, and $C$ is some measure of complexity.

Example: If $f,g$ are polynomials with integer coefficients, then we can take $C$ to be the degree of the polynomial.

Another example (which is a conjecture) is the following: Let $p,q$ be permutation patterns of length $k$. Then, is there some $N(k)$ such that if $|S_n(p)|=|S_n(q)|$ for all $n\leq N(k)$, such that $|S_n(p)|=|S_n(q)|$ for all $n$? It is conjectured that $N(k)=2k+1$ works.

Here, $S_n(p)$ is all permutations avoiding the pattern $p$.

A third example, I think, is Zeilbergers algorithm, which proves combinatorial identities by testing a finite number of cases. (Zeilberger is a big fan of this type of proofs, if I am to believe his opinions on his personal web page.)

Answer 1

I think that most of the answers to this MO question are examples that you are looking for. I'll rehash my own answer there in your language so that you can see what I mean.

Let $f$ be the function which maps finite graphs to $\{0,1\}$, where $f(G)=1$ if and only if $G$ has no $K_{t+1}$-minor but $G$ is not $t$-colourable. That is, $G$ is a counterexample to Hadwiger's Conjecture for $t$. Let $g$ be the function which is identically 0 for all finite graphs.

Reed and Kawarabayashi proved that for every fixed $t$, there is a computable function $C(t)$, such that every minimal counterexample to Hadwiger's Conjecture for $t$ has at most $C(t)$ vertices. You can think of this as the complexity of $f$. Now just sort the set of graphs according to the number of vertices, and stop when you have tested all graphs up to $C(t)$ vertices. If $f(G)=0$ for all such graphs, you can conclude that $f=g$.