Interpreting Random Hypergraphs in Pseudofinite Fields

Özlem Beyarslan University of Illinois at Chicago

December 31, 2006

1 Introduction

This article gives a positive answer to a question posed by D. Macpherson (Ravello 2002 [B.et al], Question 14):

“Can we interpret the random n-ary hypergraph in a pseudofinite field?”

A pseudofinite field is an infinite field that satisfies all first-order sentences that hold in every finite field. An example of a pseudofinite field is an infinite ultraproduct of finite fields. The theory of pseudofinite fields was first studied by J. Ax in his 1968 article “The elementary theory of finite fields”. In this article, among other results, Ax proves that a field F is pseudofinite if and only if it is perfect, has a unique extension of degree n for every n ∈ ℕ^{>0} and is pseudo algebraically closed (PAC), that is, every absolutely irreducible variety defined over F has an F -rational point.

In 1980 J. L. Duret showed [Du] that the theory of pseudofinite fields is unstable, as the random graph is definable: given a pseudofinite field F of characteristic different from 2, put an edge between any two distinct points in F in case their sum is a square in F.

During the early 1990’s Hrushovski [H] showed that the theory of pseudofinite fields, although unstable, is not so “bad” in the sense that, some of the methods from stability theory can still be applied here.

An n-hypergraph is a graph whose edges, instead of connecting just two vertices, connect n distinct vertices. A random n-hypergraph on a set A is a tuple (A, H) where H is a subset of A^{[n]} satisfying the following sentence for every m and k: for all a_{1}, …, a_{m} and b_{1}, …, b_{k} in A^{[n−1]}, distinct, there is an element c ∈ A, such that a_{1}∪{c}, …, a_{m}∪{c} ∈ H and b_{1} ∪ {c}, …, b_{k} ∪ {c} ∉ H.

Hrushovski proved in [H] that it is not possible to interpret a random (n + 1)-ary hypergraph in a random n-ary hypergraph. This proves that the complexity of the random n-ary graphs strictly increases with n.

Acknowledgements. Many thanks to Zoé Chatzidakis and Ehud Hrushovski for their extremely valuable contributions. They suggested some of the approaches and ideas on which this paper is built. I am truly grateful to both of them for their hospitality and support during my stays in Paris and Jerusalem. Also thanks to my advisor David Marker for his continuous support during my years as a graduate student at UIC. Finally, many thanks to Matthias Aschenbrenner and Rahim N. Moosa for their comments on a preliminary version of this paper.

2 Preliminaries

Throughout the article all the fields we will consider will be contained in a fixed algebraically closed field Ω and K will stand for a field contained in Ω.

Let K̃ denote the algebraic closure of K in Ω and we will denote Aut(K̃/K) as Gal(K). We call a field extension L of K a regular extension if K is algebraically closed in L, i.e. if K̃ ∩ L = K.

By a valuation we will mean a real discrete valuation. A valuation of a function field K(x) whose maximal ideal is generated by f(x) will be denoted by v_{f}. In addition to the valuations on K(x) given by the maximal ideals of K[x], there is one more valuation v_{∞} of K(x) which is defined by: v_{∞}(f/g) = deg(g) − deg(f) for f and g in K[t] where deg(f) denotes the degree of the polynomial f. We will denote valuations by the letters v and w.

Let K′ be a finite algebraic field extension of K and v̂ be an extension of v to K′, i.e. v̂ is a valuation of K′ whose valuation ring intersected with K gives the valuation ring of v. By r(v̂ : v) we denote the ramification index of v̂ over v i.e. r(v̂ : v) is the unique positive integer such that for all a ∈ K we have v̂(a) = r(v̂ : v)v(a). The residue degree of v̂ over v is the field degree of the residue field of v̂ over the residue field of v and it is denoted by d(v̂ : v). Note that if the residue field of v is algebraically closed d(v̂ : v) = 1 for every extension v̂ of v.

Let v̂ be one of the (finitely many) valuations on K′ that extend v. Then v̂ is said to be ramified over v (or over K) if r(v̂ : v) > 1 and v is ramified in K′ if it has at least one ramified extension v̂ to K′.

For a polynomial f(X) ∈ K[X] and one of its roots x ∈ Ω, we will call the field extension K(x) of K a root field of f(X).

We call an element σ of the absolute Galois group Gal(K), a topological generator of Gal(K) if σ satisfies one of the following equivalent conditions: (i) For any finite Galois extension L of K, σ|_{L} generates Gal(L/K). (ii) The subfield of K̃ fixed by σ is K. (iii) ⟨σ⟩ is dense in Gal(K).

It is easy to prove that K has a unique extension of degree n for every n if and only if Gal(K) ≃ ℤ̂, the profinite completion of ℤ, and hence Gal(K) has a topological generator. In particular the absolute Galois group of a pseudofinite field is the profinite cyclic group ℤ̂.

Proposition 1. Suppose K is a perfect field with exactly one extension of degree n for every positive integer n. Let σ be a topological generator of Gal(K) ≃ ℤ̂. Suppose L is a regular extension of K. Let τ ∈ Gal(L) be an automorphism of L̃ extending σ. Let M be the subfield of L̃ fixed by τ. Then τ is a topological generator of Gal(M) ≃ ℤ̂ and K is algebraically closed in M.

Proof: Since τ extends σ, K is algebraically closed in M. From this it follows that if K_{n} is the unique field extension of K of degree n then MK_{n}, the join of the fields M and K_{n} is the unique field extension of M of degree n. This proves the proposition. □

The next theorem characterizes the concept of elementary equivalence of pseudofinite fields. (For model theoretical concepts we refer to [Ma]).

Theorem 2 ([Ax]). Let E and F be two pseudofinite fields containing a common subfield K. Then E and F are elementarily equivalent over K if and only if the algebraic closures of K in E and F are isomorphic over K. In particular, if E is algebraically closed in F then E is an elementary extension of F.

The following proposition follows from Lemma 20.2.2 of [FJ].

Theorem 3 ([FJ]). Let E be a perfect field with at most one extension of degree n for every n. Then there exists a pseudofinite field F containing E in which E is algebraically closed.

2.1 Linearly Disjoint Extensions

Let E and F be two field extensions of K. The fields E and F are said to be linearly disjoint over K if any e_{1}, …, e_{n} ∈ E which are linearly independent over K are also linearly independent over F. Although not obvious from the definition, this concept is symmetric in E and F [FJ, Lemma 2.5.1].

Fact 4 (Lemma 2.5.2 of [FJ]). Let E and F be two field extensions of K with F/K Galois. Then E and F are linearly disjoint over K if and only if E ∩ F ≠ K.

Corollary 5. Let E and F be two nontrivial finite extensions of K with F/K Galois and Gal(F/K) simple. Then F and E are linearly disjoint over K if and only if F is not contained in the Galois closure of E over K.

Proof: Suppose E and F are not linearly disjoint over K. Then by Fact 4, E ∩ F > K. Let F_{1} be the Galois closure over K of E ∩F. Clearly F_{1} is contained in the Galois closure of E over K. Also, since F is Galois over K, F_{1} ≤ F. Then Gal(F/F_{1}) is a proper normal subgroup of G. Since G is simple, Gal(F/F_{1}) = {Id} and so F = F_{1}. That is, F = F_{1} is contained in the Galois closure of E over K.

The other direction is clear from Fact 4. □

Field extensions E_{1}, …, E_{n} of K are said to be linearly disjoint over K if each E_{i} is linearly disjoint over K from the join of the others, equivalently if E_{i} is linearly disjoint from E_{1} ⋯ E_{i−1} over K for every i = 2, …, n.

Fact 6 (Lemma 2.5.6 of [FJ]). Let L_{1}, …, L_{n} be a linearly disjoint family of Galois

extensions of K. Then Gal(L_{1} … L_{n}/K) ≃ n ; ∏_{i=1} Gal(L_{i}/K).

Lemma 7. Finitely many distinct Galois extensions of K whose Galois groups over K are nonabelian finite simple groups are linearly disjoint over K.

Proof: Let E_{i} (i = 1, …, n) be the Galois extensions as in the statement of the Lemma and let Gal(E_{i}/K) = S_{i}. It is enough to show that E_{i} is linearly disjoint from E_{1} … E_{i−1} for 1 < i ≤ n. The claim for i = 2 follows from Fact 4. Assuming that the claim holds for i = n − 1, we will show that it holds for i = n.

Gal(E_{1} ⋯ E_{n−1}/K) = S_{1} ×…×S_{n−1} by induction hypothesis and Fact 6. Suppose for a contradiction that E_{1} ⋯ E_{n−1} and E_{n} are not linearly disjoint over K. Since Gal(E_{n}/K) is simple, by Corollary 5, E_{n} is contained in E_{1} ⋯ E_{n−1}.

Now consider Gal(E_{1} ⋯ E_{n−1}/E_{n}), which is a normal subgroup of S_{1} × … × S_{n−1}. By an elementary lemma on the product of simple groups,

Gal(E_{1} ⋯ E_{n−1}/E_{n}) = T_{1} × … × T_{n−1},

where T_{i} is either {1} or S_{i} for all i = 1, … n − 1. Then

S_{1}/T_{1} ×…×S_{n−1}/T_{n−1} ≃ Gal(E_{1} ⋯ E_{n−1}/K)/ Gal(E_{1} ⋯ E_{n−1}/E_{n}) ≃ Gal(E_{n}/K) = S_{n}.

Simplicity of S_{n} implies that S_{k} ≃ S_{n}, T_{k} = 1 for some k = 1, …, n − 1 and that S_{i} = T_{i} for all i ≠ k, n. Thus

\begin{aligned}Gal(E_{1} ⋯ E_{n−1}/E_{n}) & = & T_{1} × … × T_{n−1} = S_{1} × … × S_{k−1} × \{1\} × S_{k+1} × … × S_{n−1} \\ & = & Gal(E_{1} ⋯ E_{n−1}/E_{k}). \end{aligned}

and therefore, by the fundamental theorem of Galois theory, E_{n} = E_{k}, contradicting the assumption. □

The lemma above still holds (with the same proof) if one of the extensions is still simple but abelian. Observe that the only abelian quotients of a non-abelian simple group are trivial.

2.2 Regular Extensions

Notation: Let f(X) be a polynomial in K[X]. For a field F containing K, let L be the splitting field of the polynomial f(X) over F, the Galois group Gal(L/F) is sometimes denoted as Gal(f(X), F).

Lemma 8 (2.6.11 of [FJ]). Let f(X, T) ∈ K[X, T] be a polynomial over K and Gal(f(X, T), K(X)) be its Galois group over K(X). Then the polynomial f(X, T) is absolutely irreducible over K if and only if L is a regular extension of K, and in this case Gal(L/K(X)) acts transitively on the roots of f(X, T) over K(X).

Lemma 9. Let G be a finite group acting transitively on a finite set A, |A| ≥ 2. Then there is an element g ∈ G such that g(x) ≠ x for every x ∈ A.

Proof: For x ∈ A let G_{x} be the stabilizer of x. Since G acts transitively on A, [G : G_{x}] = |A| and all stabilizers are conjugate. Any two subgroups of G contain at least the identity in their intersection, hence the cardinality of ⨆_{x∈A} G_{x} is less than |G|. Any g ∈ G\ ⨆_{x∈A} G_{x} will satisfy the desired condition. □

By Lemma 9 and Fact 8 we obtain the following corollary.

Corollary 10. Let f(X, T) be absolutely irreducible over K. Let L be the splitting field of f(X, T) over K(X). Then there is an element μ in the Galois group Gal(L/K(X)) that moves all the roots of f(X, T).

Fact 11 (2.3.11 of [FJ]). Let g(T) ∈ K[T] be a polynomial and X an indeterminate. Then h(X, T) = g(T) − X ∈ K(X)[T] is absolutely irreducible over K. Therefore a root field of h(X, T) over K(X) is a regular extension of K.

Fact 12 ([FJ]). Let f(X, T) be a polynomial in K[X, T], separable in T. Suppose Gal(f(X, T), K(X)) ≃ Gal(f(X, T), K_{s}(X)) where K_{s} is the separable closure of K. Then for any field extension F of K we have Gal(f(X, T), K(X)) ≃ Gal(f(X, T), F (X)) and the splitting field L of f(X, T) over F (X) is regular over F.

Lemma 13 (Ch.III Corr.6, p.58 [La2]). Let X ∈ Ω be transcendental over K. Let L_{1} and L_{2} be two algebraic extensions of K(X) which are linearly disjoint over K(X) and which are regular extensions of K. Then L_{1}L_{2} is also a regular extension of K.

2.3 Random Graphs and Hypergraphs

The theory of the random graph is axiomatized by the statements that express the following for all natural numbers n and m: “for all distinct (n+m) elements x_{1}, …, x_{n}, y_{1}, …, y_{m} there is a z such that R(z, x_{i}) for i = 1, …, n and ¬R(z, y_{j}) for j = 1, …, m. This theory is ω-categorical and has quantifier elimination.

For any set X, let X^{[n]} denote the set of subsets of X whose elements have precisely n members. Then an n-hypergraph over X is a tuple (X, R) where R is a subset of X^{[n]}. A n-hypergraph (X, R) is called random if for every distinct a^{1}, …, a^{m} ∈ X^{[n−1]} and for every subset I of {1, ..., m} there is an element c ∈ X such that a^{i} ∪ {c} ∈ R if and only if i ∈ I.

The countable random n-hypergraph can be constructed as the Fraissé limit of finite n-hypergraphs, hence its fist order theory is ω-categorical and has quantifier elimination by [Ho, Thm 7.4.1 ].

Note that one can define a random m-hypergraph in a random n-hypergraph by setting the first n − m entries of the random n-hypergraph to be equal to a constant c. On the contrary, it was proved in [H] that if (ω, R) is isomorphic to the random n-hypergraph, then R is not a finite Boolean combination of (n − 1)-ary relations. This, together with the elimination of quantifiers, implies that we cannot interpret a random n-hypergraph in a random (n − 1)-hypergraph.

2.4 Symmetric Polynomials

Throughout this subsection we let A denote a commutative ring with identity and t_{1}, …, t_{n} algebraically independent elements over A. Let s_{n,1}, …, s_{n,n} be the elementary symmetric polynomials in t_{1}, …, t_{n} of degree 1, …, n respectively. Thus

(1)  ∏_{i=1}^{n}(X − t_{i}) = X^{n} − s_{n,1}X^{n−1} + s_{n,2}X^{n−2} − … + (−1)^{n}s_{n,n}.

It is well known that s_{n,1}, …, s_{n,n} form an algebraically independent basis for the ring of symmetric polynomials in A[t_{1}, …, t_{n}].

We now define S_{n,i} to be the sum of all monomials of degree i over the variables t_{1}, …, t_{n}:

S_{n,i}(t_{1}, …, t_{n}) = ∑_{r_{1}+...+r_{n}=i} t_{1}^{r_{1}} … t_{n}^{r_{n}}.

The polynomials S_{n,i} are called the complete symmetric polynomials in t_{1}, …, t_{n}. The next fact is from [Fu, Section 6.1].

Fact 14. For every k ≤ n, t = (t_{1}, …, t_{n}),

S_{n,k}(t) − s_{n,1}(t)S_{n,k−1}(t) + s_{n,2}(t)S_{n,k−2}(t) − … + (−1)^{k}s_{n,k}(t) = 0.

Lemma 15. The polynomials S_{n,1}, …, S_{n,n} form a basis for the ring of symmetric polynomials in A[t_{1}, …, t_{n}], that is A[s_{n,1}, …, s_{n,n}] = A[S_{n,1}, …, S_{n,n}].

Proof: Obviously A[S_{n,1}, …, S_{n,n}] ≤ A[s_{n,1}, …, s_{n,n}]. To prove the converse we will show that for every k < n, A[s_{n,1}, …, s_{n,k}] ≤ A[S_{n,1}, …, S_{n,k}] by induction on k. For k = 1 there is nothing to prove. Assume A[s_{n,1}, …, s_{n,k−1}] ≤ A[S_{n,1}, …, S_{n,k−1}]. It is enough to show that s_{n,k} ∈ A[S_{n,1}, …, S_{n,k}]. By Fact 14 we see that s_{n,k}(t) can be written in terms of S_{n,1}(t), …, S_{n,k}(t) and s_{n,1}(t), …, s_{n,k−1}(t). The desired result follows by the induction hypothesis. □

Notation: Since the polynomial S_{n,n−1}(t_{1}, …, t_{n}) = ∑_{r_{1}+...+r_{n}=n−1} t_{1}^{r_{1}} … t_{n}^{r_{n}} will be used several times, we will shorten it as S.

Lemma 16. If a = {a_{1}, …, a_{n−1}}, b = {b_{1}, …, b_{n−1}} are in F^{[n−1]}, then

S(a_{1}, …, a_{n−1}, X) = S(b_{1}, …, b_{n−1}, X)

if and only if a = b.

Proof: Note that S(a_{1}, …, a_{n−1}, X) = ∑_{i=0}^{n−1} S_{n−1,i}(a_{1}, …, a_{n−1})X^{n−1−i}. Therefore S(a_{1}, …, a_{n−1}, X) = S(b_{1}, …, b_{n−1}, X) if and only if S_{n−1,i}(a_{1}, …, a_{n−1}) = S_{n−1,i}(b_{1}, …, b_{n−1}) for all i ≤ n − 1. By Lemma 15, each of s_{n−1,1}, …, s_{n−1,n−1} can be expressed uniquely in terms of the basis S_{n−1,1}, …, S_{n−1,n−1}. This implies that s_{n−1,i}(a_{1}, …, a_{n−1}) = s_{n−1,i}(b_{1}, …, b_{n−1}) for all i ≤ n − 1. Hence by the fundamental equality for the symmetric functions given in (1) above, we conclude that {a_{1}, …, a_{n−1}} = {b_{1}, …, b_{n−1}}. □

Notation: Let f(X_{1}, …, X_{n}) be a symmetric polynomial in k[X_{1}, …, X_{n}]. Let a = {a_{1}, …, a_{n}} be in K^{[n]}. Since f(a_{1}, …, a_{n}) = f(a_{σ(1)}, …, a_{σ(n)}) for any σ ∈ Sym(n), we are allowed to denote f(a_{1}, …, a_{n}) by f(a).

3 Main Theorem

Theorem 17. Let F be a pseudofinite field, F (x) a field extension of F with x transcendental over F and H a nonabelian simple group. Let

g(T, Y_{1}, …, Y_{n−1}, Y_{n}) ∈ F [T, Y_{1}, …, Y_{n−1}, Y_{n}]

be a polynomial over F symmetric in the indeterminates Y_{1}, …, Y_{n}. For every a = {a_{1}, …, a_{n−1}} ∈ F^{[n−1]}, let L_{a} denote the splitting field of g(T, a, x) ∈ F (x)[T]. Suppose that for every a, b in F^{[n−1]} the following properties are satisfied:

i. Gal(L_{a}/F (x)) ≅ H.

ii. L_{a} is a regular extension of F.

iii. L_{a} ≠ L_{b} for a ≠ b.

If R ⊂ F^{[n]} is defined by the condition

(1)  “{a_{1}, …, a_{n}} ∈ R if and only if g(T, a_{1}, …, a_{n−1}, a_{n}) has a root in F ”

then (F, R) is a random n-hypergraph.

We will construct polynomials satisfying the conditions stated in the hypothesis after giving the proof of the theorem. This will allow us to conclude that we can realize a random n-hypergraph in a pseudofinite field F.

Proof: Let a^{1} = {a_{1}^{1}, …, a_{n−1}^{1}}, …, a^{m} = {a_{1}^{m}, …, a_{n−1}^{m}} be in F^{[n−1]} for 1 ≤ i ≤ m and let I ⊆ {1, ..., m} and J = {1, ..., m} \ I. To prove that R is a random n-hypergraph we need to find c ∈ F such that {a_{1}^{i}, …, a_{n−1}^{i}, c} ∈ R for every i ∈ I, and {a_{1}^{j}, …, a_{n−1}^{j}, c} ∉ R for every j ∈ J.

Unwinding the definition (1), this says that we need to find an element c of F such that the polynomial g(T, a_{1}^{i}, …, a_{n−1}^{i}, c) will have a root in F for i ∈ I and the polynomial g(T, b_{1}^{j}, …, b_{n−1}^{j}, c) will have no roots in F for j ∈ J.

The strategy of the proof is as follows: we will construct an elementary extension of F containing an element x satisfying the conditions required for c. We can then conclude that such an element exists in F as well.

Let L_{1}, …, L_{m} be the splitting fields of the polynomials

g(T, a_{1}^{1}, …, a_{n−1}^{1}, x), …, g(T, a_{1}^{m}, …, a_{n−1}^{m}, x) ∈ F (x)[T]

over F (x) respectively. These splitting fields are distinct extensions with non abelian simple Galois groups by hypothesis, therefore they are linearly disjoint by lemma 7. Denote by L = L_{1} … L_{m} the join of the extensions L_{1}, …, L_{m}. By Fact 6,

Gal(L/F (x)) ≃ H × H × … × H

is the product of m copies of H.

By Lemma 9 there is an element μ_{j} of Gal(L_{j}/F (x)) which moves all the roots of g(T, a_{1}^{i}, …, a_{n−1}^{i}, x) for every j ∈ J. Take μ in Gal(L/F (x)) so that μ_{|L_{i}} = Id for every i ∈ I and μ_{|L_{j}} = μ_{j} for every j ∈ J.

Let σ be a topological generator of the absolute Galois group Gal(F̃/F) ≃ ℤ̂ of the pseudofinite field F. By the hypothesis of the theorem, the fields L_{i} are regular extensions of F. Since L_{1}, …, L_{m} are linearly disjoint over F (x), this implies that L is a regular extension of F by Lemma 13. Therefore there is an automorphism τ ∈ Gal({ \atop F (x)}/F (x)) extending both σ and μ. Denote the fixed field of τ by M.

Proposition 1 implies that M is a regular extension of F and that it has a unique extension of degree n for every n ∈ ℕ. This condition with Theorem 3 imply that there is a pseudofinite field E containing M which is a regular extension of M, i.e. M̃ ∩ E = M. Therefore E is a regular extension of F and so, by Theorem 2, E is an elementary extension of the pseudofinite field F containing x.

Now we claim that

E ⊧ ∃c([⋀_{i∈I} ∃T g(a_{1}^{i}, …, a_{n−1}^{i}, c, T) = 0] ∧ [⋀_{j∈J} ∀T g(a_{1}^{j}, …, a_{n−1}^{j}, c, T) ≠ 0]).

Taking x ∈ F (x) < E for the variable c in the above sentence, we will prove,

[⋀_{i∈I} ∃T g(a_{1}^{i}, …, a_{n−1}^{i}, x, T) = 0] ∧ [⋀_{j∈J} ∀T g(a_{1}^{j}, …, a_{n−1}^{j}, x, T) ≠ 0]

holds in the pseudofinite field E.

Let i ∈ I, L_{i} contains all roots of g(a_{1}^{i}, …, a_{n−1}^{i}, x, T). μ is the identity on L_{i} and τ extends μ, therefore M the fixed field of μ, contains all the roots of g(a_{1}^{i}, …, a_{n−1}^{i}, x, T). The pseudofinite field E contains M, so

E ⊧ ⋀_{i∈I} ∃ T g(a_{1}^{i}, …, a_{n−1}^{i}, x, T) = 0.

We will show that c = x satisfies the second part of the conjunction. Suppose for a contradiction that for some j ∈ J there exists a t ∈ E such that g(a_{1}^{j}, …, a_{n−1}^{j}, x, t) = 0. Since t is a root of the polynomial g(a_{1}^{j}, …, a_{n−1}^{j}, x, T), t is in L_{j} < L, an algebraic extension of F (x), t is also in E. Hence t ∈ E ∩{ \atop F (x)} = M therefore t ∈ M ∩L_{j} = Fix(μ).

But we chose μ so that it does not fix any root of g(a_{j}^{1}, …, a_{j}^{n−1}, x, T), a contradiction. We conclude that g(a_{1}^{j}, …, a_{n−1}^{j}, x, T) does not have any root in E for all j ∈ J. This proves our claim.

Hence,

E ⊧ ∃c([⋀_{i∈I} ∃T g(a_{1}^{i}, …, a_{n−1}^{i}, c, T) = 0] ∧ [⋀_{j∈J} ∀T g(a_{1}^{j}, …, a_{n−1}^{j}, c, T) ≠ 0]).

The formula above has parameters from F. Since E is an elementary extension of F it is also true that

F ⊧ ∃c([⋀_{i∈I} ∃T g(a_{1}^{i}, …, a_{n−1}^{i}, c, T) = 0] ∧ [⋀_{j∈J} ∀T g(a_{1}^{j}, …, a_{n−1}^{j}, c, T) ≠ 0]).

And this proves the theorem. □

4 Construction of Extensions

In Section 3 we proved Theorem 17 which states that, if there exists a polynomial g(T, X_{1}, …, X_{n}) over a pseudofinite field F satisfying certain conditions, then using this polynomial we can define a random n-hypergraph on F. Here in this section we will construct polynomials satisfying the conditions of Theorem 17 which will allow us to define a random n-hypergraph on F.

The methods of constructing polynomials satisfying the conditions of the Theorem 17 vary with the characteristic of the given pseudofinite field. We have two cases to consider separately: characteristic 0, and positive characteristic. In both cases we will use tools from the ramification theory of the function fields.

The following lemma describes the extensions of a valuation of a function field K(y) in an integral extension. It is an easy consequence of [St, Theorem III.3.7].

Lemma 18. [St, MM] Let K(y) be a function field, f(X) ∈ K[X] a seperable monic polynomial and g(X) = f(X) − y ∈ K(y)[X]. Let β ∈ K and f(X) − β = ∏ γ_{i}(X)^{r_{i}} where γ_{i} are distinct irreducible polynomials in K[X]. Let x be a root of g(X) = f(X) − y and L = K(y)(x) be a root field of g(X) = f(X) − y over K(y). Then the extensions of the valuation v_{y−β} of K(y) to L are the valuations v_{γ_{i}(x)} and we have r_{i} = r(v_{γ_{i}(x)} : v_{y−β}).

The next lemma is an important result in the theory of valuations, it can be found in [St, Proposition III.8.9] stated in the language of places instead of valuations.

Fact 19 (Abhyankar’s Lemma). Let L = L_{1}L_{2} be the join of two finite algebraic extension fields L_{i} of K. Let v be a valuation of L, whose restriction to L_{i} is ramified over K with ramification index r_{i}. If at least one of r_{i} is not equal to 0 modulo the characteristic of the field L, then the ramification index of v in L/K is lcm(r_{1}, r_{2}).

4.1 Characteristic 0 Case

We will work in characteristic 0 throughout this section.

In [Se] (p. 44) it is shown that the polynomial

h(T, Y) = (m − 1)T^{m} − mT^{m−1} + 1 + (m − 1)Y^{2}

gives rise to a regular Galois extension of ℚ(Y) with Galois group equal to the alternating group on m elements, Alt(m) when m is divisible by 4. Let us denote the splitting field of the polynomial h(T, Y) over ℚ(Y) by L. There are two valuations of ℚ(Y) which ramify in the extension L: valuation v_{∞} of ramification index m/2 and the valuation v_{1+(m−1)Y^{2}} with ramification index m − 1. Over ℚ̃(Y) the valuation v_{1+(m−1)Y^{2}} gives rise to two valuations each with ramification index m − 1.

We apply the linear transformation Y → 1/Y to the polynomial h(T, Y). This is a fractional linear transformation of the base field hence Gal(h(T, Y), ℚ(Y)) = Gal(h(T, 1/Y), ℚ(Y)) Moreover we can multiply the resulting polynomial by Y^{2} to eliminate the denominators, this does not effect the Galois group nor the ramification indices of the valuations. Therefore we obtain the following lemma.

Lemma 20. Let m be a natural number divisible by 4. Let y be transcendental over ℚ. The Galois group of the polynomial

f(T, y) = (m − 1)y^{2}T^{m} − my^{2}T^{m−1} + y^{2} + (m − 1)

over ℚ(y) is the alternating group Alt(m). The polynomial f(T, y) is absolutely irreducible over ℚ. There are two valuations of ℚ(y) which ramify in the splitting field of f(T, y), the valuation v_{y} with ramification index m/2 and the valuation v_{y^{2}+(m−1)} with ramification index m − 1.

We fix a pseudofinite field F of characteristic 0 and let n ≥ 3 be a natural number and x transcendental element over F. For each a ∈ F^{[n−1]} define y_{a} = S(a_{1}, …, a_{n−1}, x), where S(t_{1}, …, t_{n}) = ∑_{r_{1}+...+r_{n}=n−1} t_{1}^{r_{1}} … t_{n}^{r_{n}} is the (n − 1)st complete elementary symmetric polynomial defined in section 2.4. Then y_{a} is transcendental over F, x is a root of the polynomial

(1)  S(a_{1}, …, a_{n−1}, X) − y_{a} ∈ F (y_{a})[X]

and F (x) is a degree n − 1 extension of F (y_{a}). By Fact 11, F (x) is a regular extension of F. We call F (x) the “small” extension of F (y_{a}).

Now we will build a Galois extension of F (y_{a}) with Galois group Alt(m). Let m = 4(n − 1)! and K_{a} be the splitting field of the polynomial

(2)  f(T, y_{a}) = (m − 1)y_{a}^{2}T^{m} − my_{a}^{2}T^{m−1} + y_{a}^{2} + (m − 1)

over F (y_{a}). By Lemma 20 the polynomial f(T, y_{a}) ∈ ℚ(y_{a})[T] is absolutely irreducible over ℚ and its Galois group over ℚ(y_{a}) is Alt(m). Hence by Fact 12, the Galois group of f(T, y_{a}) over F (y_{a}) is Alt(m) and K_{a} is a regular extension of F. We call K_{a} the “large” extension of F (y_{a}).

Note that if m ≥ 5, Gal(K_{a}/F (y_{a})) = Alt(m) is a simple group. Since m = 4(n − 1)!, the degree of the extension [K_{a} : F (y_{a})] = m!/2, is larger than (n − 1)! hence K_{a} cannot be contained in the Galois closure of F (x) over F (y_{a}) which is of degree at most (n − 1)!. Then by Corollary 5, we conclude that K_{a} and F (x) are linearly disjoint over F.

Now let L_{a} be the join of K_{a} and F (x), the small and the large extensions of F (y_{a}). Since K_{a} and F (x) are linearly disjoint over F (y_{a}), Gal(L_{a}/F (x)) ≅ Gal(K_{a}/F (y_{a})) = Alt(m). Also, since both K_{a} and F (x) are regular extensions of F (y_{a}), and since they are linearly disjoint over F (y_{a}), their join L_{a} is a regular extension of F by Lemma 13.

Now consider the extension L_{a}/F (x). Since y_{a} = S(a, x) ∈ F (x) we see that L_{a} is the splitting field of the polynomial

f(T, S(a, x)) = (m − 1)S(a, x)^{2}T^{m} − mS(a, x)^{2}T^{m−1} + S(a, x)^{2} + (m − 1)

over F (x).

Note that f(T, S(a, x)) = g(T, a, x) where g(T, X_{1}, … X_{n}) is a symmetric polynomial in X_{1}, …, X_{n} which is the desired polynomial. Note that for every a ∈ F^{n−1}, the splitting field L_{a} of g(T, a, x) over F (x) (the field constructed above) satisfies the following conditions of the Theorem 17: (i) Gal(L_{a}/F (x)) ≅ Alt(m), a simple non-abelian group since m = 4(n − 1)! > 5 for n ≥ 3 (ii) L_{a} is a regular extension of F. Now we will prove condition (iii):

Claim: (iii) For every a, b in F^{[n−1]} L_{a} ≠ L_{b} if a ≠ b.

Proof: First note that K_{a} and L_{a} are regular extensions of F for every a in F^{[n−1]}. Hence, working over the algebraic closure F̃ of F instead of F will not change the Galois groups we have constructed. We denote the extensions of F̃(x) that corresponds to the extensions K_{a} and L_{a} of F (x) by K̃_{a} and L̃_{a} for every a in F^{[n−1]}. To show that L_{a} and L_{b} are distinct extensions of F (x), it is enough to show that L̃_{a} and L̃_{b} are distinct extensions of F̃(x).

We will find a valuation of the field F̃(x) which has different ramification indices in the Galois extensions L̃_{a} and L̃_{b} hence conclude that L̃_{a} ≠ L̃_{b} for a ≠ b.

Let a ≠ b be in F^{[n−1]}, we know by Lemma 2.4 that S(a, X) ≠ S(b, X). Then there exists a factor (X − α) of the polynomial S(a, X) ∈ F̃[X] such that the multiplicity of (X − α) in S(a, X) is e_{1} > 0 and the multiplicity of (X − α) in the polynomial S(b, X) is e_{2} ≥ 0 where e_{1} ≠ e_{2}.

Recall that by Lemma 20 the valuations of ℚ(y) that ramify in the splitting field of f(T, y) = (m − 1)y_{a}^{2}T^{m} − my_{a}^{2}T^{m−1} + y_{a}^{2} + (m − 1) are v_{y} and v_{y^{2}+(m−1)} . Also recall that we denote the splitting field of f(T, y_{a}) over F̃(y_{a}) by K̃_{a}. Since the constant field F̃ of F̃(y_{a}) is algebraically closed, as a consequence of Lemma 20 the valuations of F̃(y_{a}) that ramify in the extension K̃_{a}/F̃(y_{a}) are v_{y_{a}}, v_{y_{a}−γ} and v_{y_{a}+γ} where γ is (1−m)^{1/2}. Moreover, since we obtained the extension L̃_{a}/F̃(x) by setting y_{a} = S(a, x) the valuations of F̃(x) which ramify in L̃_{a} are exactly the valuations v_{x−β}, where β is a root of S(a, X) = 0, or of S(a, X) = ±γ.

Now we will calculate the ramification index of the valuation v_{x−α} of F̃(x) in L̃_{a} and L̃_{b}.

By Theorem 18, the valuation v_{x−α} of F̃(x) extends the valuation v_{y_{a}} of F̃(y_{a}) with ramification index r(v_{x−α} : v_{y_{a}}) = e_{1} since the multiplicity of X − α in S(a, X) is e_{1} > 0. Also any extension of the valuation v_{y_{a}} to K_{a} has ramification index m/2.

Since e_{1} ≤ n − 1, it divides m/2 = 2(n − 1)! and therefore r(w : v_{x−α}) = m/2e_{1} > 1 for any valuation w on L̃_{a} which extends v_{x−α}.

Now we will calculate the ramification index of the valuation v_{x−α} in the extension L_{b}/F (x).

If e_{2} > 0, the same argument shows that v_{x−α} ramifies in L̃_{b} with ramification index m/2e_{2} ≠ m/2e_{1}.

If e_{2} = 0, then either v_{x−α} does not ramify in L̃_{b}, or else S(b, α) = ±γ, in which case, using Abhyankar’s Lemma, we obtain that the index of ramification of v_{x−α} in L̃_{b} divides m − 1. In that case, since m and m − 1 are relatively prime, and m/2e_{i} > 1 divides m, we also obtain that the indices of ramification of v_{x−α} in L_{a} and in L_{b} are distinct. Since L̃_{a} and L̃_{b} are Galois extensions of F̃(x), this implies that L̃_{a} ≠ L̃_{b}. Hence L_{a} ≠ L_{b}, and the claim is proved. □

We showed that conditions (i),(ii),(iii) of Theorem 17 hold for the polynomial g(T, X_{1}, …, X_{n−1}, X_{n}) for n ≥ 3. Hence, we conclude that one can define a random n-hypergraph in a pseudofinite field of characteristic 0 for n ≥ 3. For n = 2 the same method of constructions can be applied by choosing m = 8 to to satisfy the condition that Alt(m) is simple. This gives formula defining a random graph in a pseudofinite field different from the one given by Duret.

4.2 Positive Characteristic p: Enlarging the Ramification Locus

We will use Abhyankar’s polynomials to build Galois extensions of function fields with Galois group Alt(m) in positive characteristic. The following theorem gives us polynomials over K(y) with Galois group Alt(m) in case the characteristic of the field is greater than 2.

Theorem 21 ([Ab], [Ab1]). Let K be a field of characteristic p > 2, y transcendental over K and L the splitting field of the polynomial f_{t,p}(T, y) = T^{m} − yT^{t} + 1 over K(y) where t ≢ 0(mod p) and m = t + p. Then Gal(f_{p,t}(T, y), K(y)) ≃ Alt(m). Additionally the valuation v_{∞} of K(y) splits into the valuations v̂_{s} and v̂_{∞} with ramification indices t and p in the extension K(s) of K(y) where s is a root of f_{p,t}(T, y) = 0 over K(y).

The following theorem is extracted from [Ab2] where the above result is extended for fields of characteristic two.

Theorem 22 ([Ab], [Ab2]). Let K be a field of characteristic p = 2, y transcendental over K and L the splitting field of the polynomial f_{t,q}(T, y) = T^{m} − yT^{t} + 1 over K(y) where m = t + q and t and q satisfy the following conditions:

i. q = p^{l} for some l

ii. t ≢ 0(mod p)

iii. t > q > p

iv. t + q ≡ 1(mod 8) or t + q ≡ 7(mod 8)

Then Gal(f_{t,q}(T, y), K(y)) ≃ Alt(m). Additionally the valuation v_{∞} of K(y) splits into the valuations v̂_{0} and v̂_{∞} with ramification indices t and q in the extension K(s) of K(y) where s is a root of f_{p,t}(T, y) = 0 over K(y).

Next, we apply the fractional linear transformation y ↦ 1/y of K(y) to the polynomial f_{t,q}(T, y) = T^{m} − yT^{t} + 1 to get the polynomial h_{t,q}(T, y) = yT^{m} − T^{t} + y. Under this transformation the valuation v_{∞} is sent to the valuation v_{0}. Combining Theorems 21 and 22 with this transformation we have the following corollary.

Corollary 23. Let K be a field of characteristic p > 0, y transcendental over K and L the splitting field of the polynomial h_{t,q}(T, y) = yT^{m} − T^{t} + y over K(y) where t ≢ 0(mod p) and m = t + q. Take q = p in case the characteristic of the field K is p > 2 and take q = p^{l}, t > q > p and m ≡ 1(mod 8) or m ≡ 7(mod 8) if the characteristic is p = 2. Then Gal(h_{t,q}(T, y), K(y)) ≃ Alt(m). Additionally, v_{y} is the only valuation of K(y) which ramifies in L and the ramification index of any extension of the the valuation v_{y} of K(y) to L is divisible by t.

Let F be a pseudofinite field of positive characteristic p. Let n > 1 be such that p ∤ n − 1. Let x ∈ Ω be transcendental over F. We will construct polynomials satisfying the conditions of Theorem17.

For every a = {a_{1}, …, a_{n−1}} ∈ F^{[n−1]}, let z_{a} be equal to S(a_{1} …, a_{n−1}, x) where x is the transcendental element we fixed at the beginning. Then F (x) is the field extension of F (z_{a}) given by the polynomial S(a_{1} …, a_{n−1}, X) − z_{a} of degree n − 1 and z_{a} ∈ Ω is transcendental over F.

For k > n − 1, let p_{1}, …, p_{k} be k distinct primes greater than n − 1, not equal to the characteristic of F, each of which is congruent to 1 or 7 modulo 8. This condition is possible by Dirichlet’s theorem on arithmetic progression of primes. Also choose p_{1}, …, p_{k} such that p_{1} + ⋯ + p_{k} is not congruent to 0 modulo the characteristic of the field.

Fix distinct β_{1}, …, β_{k} ∈ F, we set u_{a} = ∏_{i=1}^{k}(z_{a} − β_{i})^{p_{i}}. Then F (z_{a}) is a separable extension of F (u_{a}) of degree p_{1} + … + p_{k} and z_{a} is a root of

∏_{i=1}^{k}(Z − β_{i})^{p_{i}} − u_{a} ∈ F (u_{a}).

Now take t to be t = p_{1} … p_{k}. Since p_{i}’s were chosen to be congruent to 1 or 7 modulo 8, the product t = p_{1} … p_{k} is congruent to 1 or 7 modulo 8. Define q by:

i. q = p if characteristic of F is p > 2,

ii. q = 8 if the characteristic of F is 2.

Let m = q+t and M_{a} be the splitting field of the polynomial f_{t,q}(T, u_{a}) = u_{a}T^{m}−T^{t}+u_{a} over F (u_{a}). Note that, if char(F) = 2 then m = 8 + t so m is congruent to 1 or 7 modulo 8 and if char(F) = p ≠ 2 then m = p + t. Hence by Theorem 23, we have Gal(M_{a}/F (u_{a})) ≃ Alt(m) for both cases, char(F) = 2 and char(F) > 2. Also by Lemma 8, M_{a} is a regular extension of F since f_{t,q}(T, u_{a}) is absolutely irreducible over F.

Note that M_{a} is not contained in the Galois closure of F (z_{a}) over F (u_{a}) because (t + q)!/2 = (p_{1} · . . . · p_{k} + q)!/2 > (p_{1} + … + p_{k})! and Gal(M_{a}/F (u_{a})) is a simple group. Thus, by Corollary 5, M_{a} is linearly disjoint from F (z_{a}) over F (u_{a}).

Let K_{a} be the join of the extensions M_{a} and F (z_{a}). Then Gal(K_{a}/F (z_{a})) = Alt(m) since M_{a} and F (z_{a}) are linearly disjoint over F (u_{a}). Note that K_{a} is the splitting field of the polynomial

f_{t,q}(T, (∏_{i=1}^{k}(z_{a} − β_{i})^{p_{i}})) = (∏_{i=1}^{k}(z_{a} − β_{i})^{p_{i}})T^{m} − T^{t} + ∏_{i=1}^{k}(z_{a} − β_{i})^{p_{i}} ∈ F (z_{a})[T]

over F (z_{a}). And K_{a} is a regular extension of F by Fact 11.

So far we have constructed two extensions K_{a} and F (x) of F (z_{a}); K_{a}/F (z_{a}) Galois with Galois group Alt(m) and F (x) a finite algebraic extension of F (z_{a}) given by the polynomial ∏_{i=1}^{k}(Z − β_{i})^{p_{i}} − u_{a}. Let L_{a} be the join of F (x) with M_{a}. Note that L_{a} is the splitting field of

f_{t,q}(T, ∏_{i=1}^{k}(S(a, x) − β_{i})^{p_{i}}) = ∏_{i=1}^{k}(S(a, x) − β_{i})^{p_{i}}T^{m} − T^{t} + ∏_{i=1}^{k}(S(a, x) − β_{i})^{p_{i}}

over F (x).

Now let g_{1}(T, a, x) = f_{t,q}(T, ∏_{i=1}^{k}(S(a, x) − β_{i})^{p_{i}})). Then g_{1}(T, X_{1}, …, X_{n−1}, X_{n}) is a symmetric polynomial in X_{1}, …, X_{n}. Note that (i) for every a ∈ F^{[n−1]}, the Galois group of the polynomial g_{1}(T, a, x) over F (x) is the simple group Alt(m), (ii) L_{a} is a regular extension of F. That is, the first two conditions for the main theorem are satisfied. We also need to prove that

(iii) L_{a} ≠ L_{b} if a ≠ b. Proof: The valuation v_{u_{a}} of F (u_{a}) extends to the valuations w_{z_{a}−β_{i}} of F (z_{a}) with ramification indices r(w_{z_{a}−β_{i}} : v_{u_{a}}) = p_{i} for i = 1 …, k by Lemma 18. Also the ramification index of the valuation v_{u_{a}} in the Galois extension M_{a} is s where t|s. Since p_{i} divides t, and p_{i} is not divisible by the characteristic of the field F, the valuations w_{z_{a}−β_{i}} of F (z_{a}) have extensions in M_{a} which ramify with index s/p_{i} over w_{z_{a}−β_{i}} for i = 1, …, k by Abhyankar’s Lemma.

Again by Lemma 18, the valuation w_{z_{a}−β_{i}} of F (z_{a}) extends to the valuations v_{γ_{1}}, …, v_{γ_{h}} of F (x) according to the decomposition of the polynomial S(a_{1} …, a_{n−1}, X) − β_{i} = ∏_{i=1}^{h} γ_{i}(X) in F [X].

Since the characteristic of the pseudofinite field F does not divide n − 1, the extension F (x)/F (z_{a}) has at most n − 1 ramification points. Therefore one of the valuations w_{z_{a}−β_{i}} does not ramify in F (x) as k was chosen to be greater than n − 1, fix one such β_{i} and let γ_{1}(x), …, γ_{h}(x) be the irreducible factors of S(a, X) − β_{i} over F. Then the valuations v_{γ_{j}(x)} for 1 ≤ j ≤ h are the only valuations of F (x) extending w_{z_{a}−β_{i}} and they do not ramify over w_{z_{a}−β_{i}} by our assumption on β_{i}.

The ramification indices of the extensions v_{γ_{j}(x)} of v_{z_{a}−β_{i}} in L_{a} are s/p_{i}, by Abhyankar’s Lemma. If j ≠ i, then the ramification indices over F (x) of the extensions of v_{z_{a}−β_{j}} to L_{a} divide s/p_{j} and are therefore different from s/p_{i}. It follows that we can retrieve the polynomial S(a, X) from the ramification locus of L_{a} over F (x): choose i such that the valuations of F (x) ramifying with index s/p_{i} in L_{a} are precisely v_{γ_{1}(x)}, …, v_{γ_{r}(x)}, and ∏_{j=1}^{r} γ_{j}(X) has degree n − 1 (such an i exists by the discussion above). Then S(a, X) = ∏_{j=1}^{k} γ_{j}(X) − β_{i}.

From this it follows that if S(a, X) ≠ S(b, X), then L_{a} ≠ L_{b}. This gives us the conclusion. □

We have showed the conditions of the main theorem are satisfied in a pseudofinite field of characteristic p where p does not divide n − 1. Therefore we can interpret a random n-ary hypergraph in F when the characteristic p of F is positive and p ∤ n − 1. But if we can realize a random m-hypergraph, by restricting it to n < m many parameters, then we can realize random n-hypergraph as well. Thus we can realize a random n-hypergraphs for every n.

References

[Ab] S. Abhyankar, Galois theory on the line in nonzero characteristic, Bulletin of American Mathematical Society 27 no 1 (1992) 68-133.

[Ab1] S. Abhyankar, Alternating group coverings of the affine line for characteristic greater than two , Ann. Math. 296 (1993) 63-68.

[Ab2] S. Abhyankar, Alternating group coverings of the affine line for characteristic two, Discrete Mathematics 133 (1994) 25-46.

[Ax] J. Ax, The elementary theory of finite fields, Ann. Math. 88 (1968) 239-271. [B.et al] L. Bélair et al., Model theory and Applications, Quadranti di Mathematica,

2003.

[Du] J.-L. Duret, Les corps faiblement algébriquement clos non séparablement clos ont la propriété d’indépendence, in Model theory of Algebra and Arithmetic, Lect. Notes Math. 843 (1980), 135-157.

[FJ] M. Fried, M. Jarden, Field Arithmetic, Erg. Math. 11, Berlin-Heidelberg-New York, 1986.

[Fu] W. Fulton, Young Tableaux, Oxford University Press, 1992.

[Ho] W. Hodges, Model Theory, Cambridge University Press, 1993.

[H] E. Hrushovski, Pseudo-finite fields and related structures, Model Theory and Applications (eds. L. Blair, et al.), 2003, page

[La1] S. Lang, Algebra, Adisson Wesley Publishing Company, 1993.

[La2] S. Lang, Introduction to Algebraic Geometry, Adisson Wesley Publishing Company, 1972.

[MM] G. Malle, B. H. Matzat, Inverse Galois Theory, Springer-Verlag, Berlin, Heidelberg, New York, 1999.

[Ma] D. Marker, Model Theory: An Introduction, Graduate texts in mathematics, Springer-Verlag, Berlin, Heidelberg, New York, 2002.

[Se] J.P. Serre, Topics in Galois Theory, Jones and Bartlett Publishers, 1992.

[St] H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag , 1993.