Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Statements
A finite polynomial condition consists of finitely many equations and finitely many clauses, each clause requiring at least one polynomial in a specified finite list to be nonzero. In particular, inequality of two vectors is such a clause.
The following two facts hold for every field .
- If is infinite and , some extension field contains points compatible with , with one coordinate selected from each point so that the selected coordinates are algebraically independent over . Here compatibility means that all polynomial identities on hold at the point, and every finite collection of polynomial equations holding at the point holds simultaneously at some point of .
- Fix a finite polynomial condition in parameter variables and a finite tuple of fiber variables , with coefficients in . If every fiber is finite in every extension field of , then the fibers over have a common finite bound on their sizes.
These are field-extension statements. They are not assertions that finite fields contain transcendental elements.
Ultrafilter construction
For an ultrafilter on , identify functions when they agree on a set in . The quotient is a field: a nonzero class is nonzero on a set in , so taking its pointwise reciprocal there gives an inverse. Constant functions embed in this field.
Polynomial evaluation commutes with passing to classes, because a polynomial uses only finitely many additions and multiplications. Thus finitely many equations true on a set in remain true in the quotient. Finite nonvanishing clauses also remain true. If all members of one clause vanished in the quotient, their zero sets would have a common intersection in , contradicting that clause on the same set.
We use the usual ultrafilter extension principle: a proper filter extends to an ultrafilter. This is a choice principle, also used by the formal source. No point-counting theorem is being assumed.
Proof of compatible independent points
Because the coordinate set is finite, some coordinate has infinite image on ; otherwise lies in a finite product of finite sets. Let be that infinite image and choose with the selected coordinate equal to , for each . Take an ultrafilter extending the cofinite filter on and form the tuple of classes of the coordinates of . All polynomial identities on hold at this tuple.
If a finite collection of equations holds at the tuple, each equation holds on an ultrafilter-large set of indices. Their intersection is nonempty, providing an actual satisfying them all. This proves compatibility. The selected coordinate is transcendental over : any nonzero one-variable polynomial has only finitely many roots, whereas the chosen coordinate takes each value of once, so its class cannot be a root of that polynomial.
Repeat the construction over the field obtained at the preceding stage, using the embedded original set . That set remains infinite. Each new selected coordinate is transcendental over a field containing all previous ones, so the selected coordinates are algebraically independent over . Previously constructed points and their compatibility persist under an injective field extension. For the new point, compatibility over the larger field implies compatibility over by mapping polynomial coefficients along the field embedding. This proves the first assertion by induction.
A compatible point preserves any finite polynomial condition satisfied by every member of . Equations follow from polynomial identities. If all polynomials in a required nonzero clause vanished at the compatible point, compatibility would supply a member of where they all vanish, a contradiction. This observation preserves injectivity conditions in the application to graph copies.
Proof of a uniform fiber bound
Suppose the sizes over were unbounded. For each , choose a parameter tuple and distinct points in its fiber. Extend the cofinite filter on the positive integers to an ultrafilter. In its field quotient, let be the class of the parameter tuples. For each fixed , use when and any default tuple otherwise; let be its class.
Every lies in the fiber over , by transfer of the finite equations and clauses. Distinct give distinct . Indeed, equality of the two quotient tuples would imply equality in every coordinate on a common ultrafilter-large set, since there are only finitely many fiber coordinates. On its intersection with , this contradicts the chosen distinctness of . The extension field therefore has an infinite fiber, contrary to the hypothesis.
Source and dependencies
The exposition, Proposition 2.1,
p. 2, suppresses this compactness argument. The pinned formal source
proves it in UltrafilterField, GenericPoint, and IndependentPoints,
lines 1943–2212, and UniformFiberBound.uniform_bound, lines 3087–3140.
Only elementary field operations, the finite root bound for a nonzero
one-variable polynomial, algebraic independence, and the stated ultrafilter
extension principle are used.
Bears on. #571.