SYMMETRIC FUNCTIONS AND THE PHASE PROBLEM IN CRYSTALLOGRAPHY

J. BUHLER AND Z. REICHSTEIN

Abstract. The calculation of crystal structure from X-ray diffraction data requires that the phases of the “structure factors” (Fourier coefficients) determined by scattering be deduced from the absolute values of those structure factors. Motivated by a question of Herbert Hauptman, we consider the problem of determining phases by direct algebraic means in the case of crystal structures with n equal atoms in the unit cell, with n small. We rephrase the problem as a question about multiplicative invariants for a particular finite group action. We show that the absolute values form a generating set for the field of invariants of this action, and consider the problem of making this theorem constructive and practical; the most promising approach for deriving explicit formulas uses SAGBI bases.

1. Introduction

If the unit cell of a crystal has n atoms, located at positions r_{j}, 1 ≤ j ≤ n, then the structure factor associated to a reciprocal lattice vector v is

E_{v} := ∑_{j=1}^{n} a_{j} exp(2πiv · r_{j}) ,

where the a_{j} are the scattering amplitudes determined by the electron charge distribution in the j-th atom. This is, in effect, a Fourier transform coefficient, and the structure of the crystal can be determined from the E_{v} by an inverse Fourier transform. However, in standard diffraction experiments, it is impossible to measure the E_{v} – only their absolute values are observable. The “phase problem” of crystallography is to determine the phases of the E_{v} given magnitudes |E_{v′}| for sufficiently many v′; this problem is fundamental in the subject, and has received considerable attention ([Gia], [Ha2]). The problem of retrieving phase information from absolute values, together with other physical constraints, occurs in several other areas of physics, astronomy, and engineering.

1991 Mathematics Subject Classification. 05E05, 13A50, 13P99, 20C10. Key words and phrases. Crystallography, structure factor, phase problem, symmetric

function, group action, field of invariants, SAGBI basis, algorithmic computation, multiplicative invariant, rational invariant field.

Z. Reichstein was partially supported by NSF grant DMS-901675 and by an NSERC research grant.

In the crystallographic context, the phases can be determined in principle only up to an additive constant, which is equivalent, via a Fourier transform, to the indeterminacy of the origin of the crystal. It is natural to consider “structure invariants,” which are multiplicative combinations of structure factors that are invariant under change of origin, i.e., additive translation of the phase. In addition, structure invariants play an important role in commonly used stochastic methods for phase retrieval. The function

(1)  E_{v_{1}}E_{v_{2}} … E_{v_{m}}

is easily seen to be a structure invariant when the reciprocal lattice vectors v_{i} sum to zero. The most common case is m = 3, i.e., the “triplet-structure invariant”

E_{v_{1}}E_{v_{2}}E_{−v_{1}−v_{2}}.

Exact formulas for phases of triplet structure invariants are known in terms of magnitudes for n = 1, 2, 3 [Ha1]. Herbert Hauptman asked one of us for a formula for arbitrary n, and the purpose of this paper is to show that, at least in the case in which all atoms in the crystal have the same a_{j}, such a formula exists, and to explore techniques for finding such formulas explicitly.

In this paper we shall only consider crystals with equal atoms (or equal polyatomic clumps); we will set the identical scattering factors a_{j} equal to 1. In addition, it is convenient to assume that the space group is the most basic group P1 (isomorphic to the group ℤ^{3} of translations); see [Ha1, Appendix 1] for a description of how to generalize to arbitrary space groups.

Under these assumptions the triplet phase determination problem can be converted to a question about multiplicative invariant functions. Somewhat to our surprise, this question seems to be new.

To express the triplet phase problem to a problem in symmetric functions, start by noting that the phase ϕ_{v_{1},v_{2}} of the triplet structure factor E_{v_{1}}E_{v_{2}}E_{−v_{1}−v_{2}} satisfies

E_{v_{1}}E_{v_{2}}E_{−v_{1}−v_{2}} = |E_{v_{1}}| |E_{v_{2}}| |E_{−v_{2}−v_{2}}| exp(iϕ_{v_{1},v_{2}}) .

Thus the cosine of the phase can be expressed in terms of absolute values and the sum of the triplet-structure invariant and its complex conjugate.

We want to express the phase ϕ_{v_{1},v_{2}} in terms only of absolute values

|E_{av_{1}+bv_{2}}|^{2} = E_{av_{1}+bv_{2}}E_{av_{1}+bv_{2}}^{∗} = E_{av_{1}+bv_{2}}E_{−av_{1}−bv_{2}}

corresponding to reciprocal lattice vectors av_{1} + bv_{2}, where a and b are integers.

Fix v_{1} and v_{2} and let

x_{j} = exp(2πiv_{1} · r_{j}),  y_{j} = exp(2πiv_{2} · r_{j}), 1 ≤ j ≤ n
X = (x_{1}, ⋯, x_{n}),  Y = (y_{1}, ⋯, y_{n}) .

Then

E_{v_{1}} = ∑_{j=1}^{n} x_{j} and E_{v_{2}} = ∑_{j=1}^{n} y_{j} .

Using the fact that z + z^{∗} = 2|z| cos(ϕ) if z is a complex number with absolute value |z| and argument ϕ, we see that we need to express

E_{2}(X, Y) := E_{v_{1}}E_{v_{2}}E_{−v_{1}−v_{2}} + E_{−v_{1}}E_{−v_{2}}E_{v_{1}+v_{2}}
= |E_{v_{1}}| |E_{v_{2}}| |E_{−v−v_{2}}| 2 cos(ϕ_{v_{1},v_{2}})
= ∑_{j=1}^{n} x_{j} ∑_{k=1}^{n} y_{k} ∑_{l=1}^{n} \frac{1}{x_{l}y_{l}} + ∑_{j=1}^{n} \frac{1}{x_{j}} ∑_{k=1}^{n} \frac{1}{y_{k}} ∑_{l=1}^{n} x_{l}y_{l}

= ∑_{j,k,l=1}^{n} \frac{x_{j}y_{k}}{x_{l}y_{l}} + ∑_{j,k,l=1}^{n} \frac{x_{l}y_{l}}{x_{j}y_{k}}

in terms of the magnitudes

q_{a,b}(x_{1}, …, x_{n}, y_{1}, …, y_{n}) := E_{v}E_{−v}
= ∑_{j=1}^{n} x_{j}^{a}y_{j}^{b} · ∑_{j=1}^{n} x_{j}^{−a}y_{j}^{−b} = ∑_{i,j=1}^{n} \frac{x_{i}^{a}y_{i}^{b}}{x_{j}^{a}y_{j}^{b}} ,

for suitable integers a and b; here v = av_{1} + bv_{2} is an arbitrary reciprocal lattice vector.

We will call q_{a,b} an “observable” since it is (the square of) an absolute value and therefore it is possible to observe it physically. Thus our goal is to express E_{2} as a rational function of the observables q_{a,b}. From now on we will treat this as a question about variables x_{i} and y_{i}, ignoring the fact that they are complex numbers of absolute value one. A simple Zariski density argument shows that this does not change the underlying problem, i.e., we are not going to “miss” any identities by assuming that x_{i} and y_{i} are arbitrary complex numbers, rather than just those of absolute value one.

Example 1.1. The reader can easily verify that for n = 2 the triplet phase invariant is a polynomial in three observables:

E_{2}(X, Y) = 2(q_{1,0} + q_{0,1} + q_{1,1}) − 8.

Example 1.2. The formula for n = 3 is considerably more elaborate, and was discovered by Hauptman [Ha1]; it takes the form E_{2}(X, Y) = N/D, where

D := q_{0,1} + q_{1,0} + q_{1,1} − 3 = −3 + ∑_{i,j=1}^{3} (\frac{x_{i}}{x_{j}} + \frac{y_{i}}{y_{j}} + \frac{x_{i}y_{i}}{x_{j}y_{j}} )

and

N := 135 − 31D + D^{2} + 2(q_{1,0}q_{0,1} + q_{1,0}q_{1,1} + q_{0,1}q_{1,1})
+(q_{0,1}q_{2,1} + q_{1,0}q_{1,2} + q_{1,−1}q_{1,1})
−5(q_{1,2} + q_{2,1} + q_{1,−1}) − 2(q_{0,2} + q_{2,2} + q_{2,0}) .

(For another formula, see Example 6.5.)

Higher order generalizations of triplet structure invariants are defined as a product of structure factors E_{v} where the v sum to 0. If a structure invariant is the product of m factors (1) for arbitrary m, then this gives rise, in a similar manner, to the problem of expressing

(2) E_{m}(X_{1}, ⋯, X_{m}) := ∑_{j,j_{1},...,j_{m}=1}^{n}( \frac{x_{1j_{1}}x_{2j_{2}} … x_{mj_{m}}}{x_{1j} … x_{mj}} + \frac{x_{1j} … x_{mj}}{x_{1j_{1}}x_{2j_{2}} … x_{mj_{m}}} )

as a rational function in observables

(3)  q_{r_{1},...,r_{m}} := ∑_{i,j=1}^{n} \frac{x_{1i}^{r_{1}} … x_{mi}^{r_{m}}}{x_{1j}^{r_{1}} … x_{mj}^{r_{m}}} ,

where r_{1}, …, r_{m} are integers.

Note that the rational function f = E_{m} has the following invariance properties.

a: f is of weight 0 in each n-variable vector

X_{1} = (x_{11}, …, x_{1n}), …, X_{m} = (x_{m1}, …, x_{mn}) .

That is, f(c_{1}X_{1}, …, c_{m}X_{m}) = f(X_{1}, …, X_{m}) for any non-zero scalars c_{1}, …, c_{m}, or, more succinctly: f(c_{j}x_{ij}) = f(x_{ij}).

b: f is self-reciprocal in the sense that it remains unchanged if every variable x_{ij} is simultaneously replaced by x_{ij}^{−1}, i.e., f(x_{ij}^{−1}) = f(x_{ij}). c: f is multi-symmetric in the sense that it remains unchanged if the variables in each array X_{i} are (simultaneously) permuted by the same permutation σ ∈ S_{n}, i.e., f(x_{iσ(j)}) = f(x_{ij}).

Our main results are summarized in the following theorem. Both parts answer questions posed by H. Hauptman. Theorem 1.3. (1) (Theorem 5.1 or Theorem 6.1) Every rational function f(x_{ij}) in mn variables, satisfying the invariance properties a, b, c, can be expressed as a rational function of the observables q_{c_{1},...,c_{m}}. In particular, E_{m} can be expressed as a rational function of the observables q_{c_{1},...,c_{m}} for any m ≥ 1.

(2) (Proposition 7.1(b)) Suppose n ≥ 4. Then E_{m} is not a polynomial in the observables q_{c_{1},...,c_{m}} for any m ≥ 2.

Our proof of Theorem 1.3 requires the consideration of all f satisfying the invariance properties a, b, c, even if one is only interested in the structure invariants E_{m}. This is true of most of our other proofs and algorithms.

The overall outline of the paper is as follows. In Section 2 we prove (a slightly more precise version of) Theorem 1.3(2) for m = 1 using basic Galois theory and some combinatorial arguments; the proof is not obviously constructive. In Section 3 we consider two possible approaches to making the argument constructive. In the subsequent section we give a fast algorithm for n ≤ 4, based on SAGBI bases. In Section 5 we turn our attention to the multi-array case, i.e., m > 1. In Section 6 we reduce the problem of computing the invariant E_{m} to that of expressing certain invariant functions in terms of observables in the single array case (m = 1). We then use the SAGBI basis algorithm of Section 4 to obtain new expressions for E_{2} in the case where n = 3 and 4; see Examples 6.5 and 6.6. In Section 7 we prove Theorem 1.3(2). Finally, in Section 8 we study the structure of the field of rational functions f satisfying the invariance properties (a) - (c) as an abstract field, without reference to the observables.

In the course of our work on this paper, we have encountered a phenomenon that often arises in the interstices between mathematics and its applications. Depending on the context, solving a mathematical problem can mean many different things, e.g.,

(a) proving a theorem,

(b) giving a constructive proof, or

(c) giving an algorithmic proof, suitable for practical computations. As one moves down this list, the problem can become more difficult, requiring different techniques and ways of thinking. However, there is usually a subtle but important interplay between these different modes of solution.

Acknowledgments

The authors would like to thank H. Hauptman for bringing this problem to their attention, M. Lorenz for contributing Proposition 8.1, and D. Eisenbud, N. Elkies, J. Friedman, I. Laba, H. Lenstra, G. Martin, D. Peterson, C. Procesi, I. Swanson, and R. Thomas for helpful conversations.

2. One set of variables

Fix a field k of characteristic 0. Let X = (x_{1}, …, x_{n}) be an n-tuple of independent variables over k. We will operate on n-tuples as if they were diagonal matrices, so X^{−1} = (x_{1}^{−1}, …, x_{n}^{−1}), tr(X) = x_{1} + ⋯ + x_{n}, etc.

Let k(X)_{0} ⊂ k(x_{1}, ⋯, x_{n}) be the field of rational functions in the x_{i} of total degree 0; in other words, an element f ∈ k(X)_{0} is a quotient of homogeneous polynomials of the same degree. Equivalently, k(X)_{0} is the field generated by the x_{i}/x_{j}:

k(X)_{0} = k(x_{i}/x_{j} : 1 ≤ i, j ≤ n, i ≠ j) .

We note that the field k(X)_{0} can also be viewed as the function field of the projective space ℙ^{n−1}.

The symmetric group S_{n} acts on k(X)_{0} = k(x_{1}, ⋯, x_{n})_{0} by permuting the variables x_{1}, ⋯, x_{n} in the natural way. In addition, we let τ denote the automorphism that takes X to X^{−1}, i.e.,

τ(x_{i}) = \frac{1}{x_{i}} , 1 ≤ i ≤ n.

This automorphism is obviously of order two, and we let T = {1, τ} denote the corresponding group. The actions of S_{n} and T commute so that the group

G := S_{n} × T

acts on k(X)_{0}. This action is faithful for n ≥ 3. If n = 2, G = S_{2} × T has order 4, and the kernel of its action on k(x_{1}, x_{2})_{0} is the subgroup of order 2 generated by (σ, τ), where σ is the nontrivial element of S_{2}.

The main theorem of this section is that the observables

(4)  q_{r} := tr(X^{r})tr(X^{−r}) = ∑_{i,j=1}^{n} (\frac{x_{i}}{x_{j}} )^{r}

generate the invariant field k(X)_{0}^{G}. (Note that here m = 1, so that the observables (3) have only one subscript.) Theorem 2.1.

k(X)_{0}^{G} = k(q_{r} | 1 ≤ r ≤ n(n − 1)/2) .

Before proving the theorem, we prove two lemmas, one combinatorial and the other algebraic.

Let n ≥ 2 be an integer, N = n(n − 1), and Λ be the N-element set

(5)  Λ = {(i, j) | i, j = 1, …, n and i ≠ j}.

When convenient we will sometimes omit the comma and write (ij) instead of (i, j). In addition, we tend to visualize the elements of Λ as the offdiagonal positions in an n by n matrix.

There is a natural action of G = S_{n}×T on Λ, where τ acts by transposition

τ(i, j) = (j, i)

and the symmetric group S_{n} acts simultaneously on the rows and columns:

σ(i, j) = (σ(i), σ(j)), σ ∈ S_{n}.

This gives a map from G to the symmetric group S_{N} = S_{n^{2}−n} = Sym(Λ) of all permutations of Λ, and this map is an injection for n ≥ 3, in which case we will usually just choose to regard G as a subgroup of S_{N}. In the case n = 2 the map is surjective with kernel of order two as described earlier.

We will say that elements x = (i, j) and x′ = (i′, j′) of Λ are opposite if x is the transpose of x′, i.e., i = j′ and j = i′. If exactly one of these equalities holds, i.e., x′ is not opposite to x, but it lies in the same row or column as the transpose of x, then we say that x and x′ are adjacent. Note that opposite pairs are not also adjacent.

We will say that g ∈ S_{N} preserves adjacency (respectively opposition) if for any adjacent (respectively, opposite) elements x, x′ ∈ Λ, the images g(x) and g(x′) are also adjacent (respectively, opposite). Our combinatorial lemma says that for n > 2, G = S_{n} × T is precisely the subgroup of S_{N} that preserves both of these relations.

We note that for n = 2 the situation is simple: G maps onto S_{N} = S_{2} and the nontrivial element of S_{N} preserves both adjacency and opposition. So from now on we consider n ≥ 3.

Lemma 2.2. Let n ≥ 3. Then h ∈ S_{N} preserves both adjacency and opposition if and only if h ∈ G ⊂ S_{N}.

Proof. It is immediate from the definition that every h in G preserves both adjacency and opposition, so we only need to prove that any element preserving these relations lies in G.

Suppose h ∈ S_{N} preserves both adjacency and opposition. To show that h ∈ G, we will multiply h by elements of G until we arrive at the identity permutation of Λ.

It is easy to see that S_{n} acts transitively on Λ. Thus, after composing h with an element of S_{n} ⊂ G, we may assume h(12) = (12).

We claim that we may also assume that h(13) = (13). Indeed, since h preserves opposition, h(12) = (12) implies h(21) = (21). Suppose h(13) = (ij). Since (21) and (13) are adjacent, so are (21) and (ij), i.e., either i = 1 or j = 2. If i = 1 then j ≥ 3; thus after replacing h by [3, j]h, we obtain h(12) = (12) and h(13) = (13), as desired. (Here [3, j] denotes the transposition in S_{n} that interchanges 3 and j.) On the other hand, if j = 2 then i ≠ 1, 2 and, after replacing h by [3, i][1, 2]τh, we once again obtain h(12) = (12) and h(13) = (13). This proves the claim.

Since h preserves opposition, h(13) = (13) implies that h(31) = (31). Now, since (23) is the unique pair adjacent to both (31) and (12), and h(23) is the unique pair adjacent to both h(31) = (31) and h(12) = (12), we conclude that H(23) = (23). Since h preserves opposition, we also have h(32) = (32). Thus h fixes (ij) for 1 ≤ i, j ≤ 3. This completes the proof of Lemma 2.2 for n = 3; from now on we will assume that n ≥ 4.

Suppose h(1i) = (ab) for some i ≥ 4. Since (21) and (1i) are adjacent, so are (21) and (ab). That is, either a = 1 or b = 2. Repeating this argument with (31) in place of (21), we see that either a = 1 or b = 3. Since b cannot be equal to both 2 and 3, we conclude that a = 1. In other words, h(1i) = (1σ(i)), where σ is a permutation of 4, 5, …, n. After replacing h by σ^{−1}h, we reduce to the case where h fixes (1i) (and thus (i1)), for every i = 2, …, n.

We claim that h is the identity permutation, i.e., that h(ab) = (ab) for every (ab) ∈ Λ. Since we know this in the cases where a = 1 or b = 1, we may assume a, b ≥ 2. In this case (ab) is the unique element of Λ that is adjacent to both (1a) and (b1). Hence, h(ab) = (ab), as claimed. □

Next, we prove an algebraic lemma from which the theorem will follow easily. Let

f(t) = ∏_{\begin{matrix}i, j = 1 \\ i ≠ j \end{matrix}}^{n} (t − \frac{x_{i}}{x_{j}} ) = ∑_{i=0}^{N}(−1)^{i}c_{i}t^{N−i}

be the polynomial of degree N = n(n − 1) whose roots are the x_{i}/x_{j}, i ≠ j. The coefficients c_{i} are the elementary symmetric functions in those roots, and since the reciprocals of roots are themselves roots, the polynomial f satisfies t^{N}f(1/t) = f(t), which is equivalent to

c_{i} = c_{N−i}, 0 ≤ i ≤ N.

The elements q_{r} = tr(X^{r})tr(X^{−r}) are symmetric functions of the x_{i}/x_{j} are hence polynomials in the c_{i}; we let

K := k(q_{r} | r = 1, 2, ⋯)

be the field generated by the observables q_{r}.

As we will see, the proof of Theorem 2.1 basically comes down to determining the Galois group of f over the field K. Lemma 2.3. With the above notation,

(a) k[c_{1}, …, c_{r}] = k[q_{1}, … q_{r}] for any r, 1 ≤ r ≤ N.

(b) K = k(c_{1}, …, c_{N/2}) = k(q_{1}, …, q_{N/2}).

(c) k(X)_{0} is the splitting field of f(t) over K.

Proof. Since

q_{r} − n = tr(X^{r})tr(X^{−r}) − n = ∑_{i≠j}(x_{i}/x_{j})^{r}

is the sum of the m-th powers of the roots of f(t), part (a) follows from Newton’s formulas that express the symmetric polynomials c_{1}, ⋯, c_{r} in terms of the power sums q_{1}, ⋯, q_{r}.

Part (b) follows from part (a) and the symmetry of the c_{i}. Part (c) follows from (b) and the fact that k(X)_{0} = k(x_{i}/x_{j}). □

We are now ready to finish the proof of Theorem 2.1. Clearly, K ⊂ k(X)_{0}^{G}. Consider the tower

\begin{matrix}k(X)_{0} \\ | \\ k(X)_{0}^{G} \\ | \\ K \end{matrix}

of field extensions. By the lemma, k(X)_{0} is a Galois extension of K. Identify the set of roots of f(t) with the set Λ = {(i, j) | i ≠ j}, letting x_{i}/x_{j} ↔ (i, j). The action of G = S_{n} × T on the set of roots is the same as its action on Λ described earlier.

The notions of adjacency and opposition in Λ have a natural interpretation in this context. If x = (ab) and x′ = (cd) are elements of Λ let r = x_{a}/x_{b} and r′ = x_{c}/x_{d} be the corresponding roots of f(t). Then x and x′ are adjacent if and only if rr′ is again a root of f(t) and opposite if and only if rr′ = 1. Thus any Gal(k(X)_{0}/K) acts on the set of roots in a way that preserves both adjacency and opposition. Lemma 2.2 now tells us that Gal(k(X)_{0}/K) = G. Thus k(X)_{0}^{G} = K. This completes the proof of Theorem 2.1. Remark 2.4. Since S_{n} ⊂ G acts transitively on the roots of f(t), we conclude that f(t) is irreducible over k(X)_{0}^{G}.

3. Constructive proofs

The proof in the last section ultimately relies on a fundamental and beautiful result in Galois theory: anything fixed by all elements of a Galois group lies in the ground field. We will now discuss a constructive proof, which could be viewed as the result of tracing through the argument of the previous section, rendering the underlying Galois theory explicit at each step. We note that both proofs rely on Lemma 2.2.

We begin by letting k[X^{±1}]_{0} be the k-algebra whose elements are k-linear combinations of Laurent monomials x_{1}^{a_{n}} … x_{n}^{a_{n}} of total degree 0, i.e., where the a_{i} are integers whose sum is 0. Note that k[X^{±1}]_{0} is generated, as a k-algebra, by elements of the form x_{i}/x_{j}; in particular, the field k(X)_{0} is the field of fractions of k[X^{±1}]_{0}. Note also that k[X^{±1}]_{0} is a G-invariant subring of k(X)_{0}.

Let z_{ij} be a set of N = n(n − 1) algebraically independent variables over k, where i and j are distinct integers between 1 and n. For notational convenience, we also set z_{ii} = 1 for every i = 1, …, n. We now define a surjective k-algebra homomorphism

ϕ: k[z_{ij}] ⟶ k[X^{±1}]_{0}

by ϕ(z_{ij}) = x_{i}/x_{j}. Let s_{r} be the rth elementary symmetric polynomial in the N variables z_{ij} and p_{r} = ∑_{i≠j} z_{ij}^{r} be the sum of the rth powers of these variables. Here s_{0} = 1 and ϕ(s_{r}) is the element of k[X^{±1}]_{0} we called c_{r} in the statement of Lemma 2.3. We let S_{N} denote the group of all permutations of {z_{ij} : i ≠ j}, and identify G = S_{n} × T with the subgroup that acts on the z_{ij} by σ(z_{ij}) = z_{σ(i)σ(j)}, for σ ∈ S_{n}, and τ(z_{ij}) = z_{ji}.

Define three polynomials D_{1}, D_{2}, D ∈ k[z_{ij}] of N variables by

D_{1}(z_{ij}) = ∏_{(ab) and (cd) ∈ Λ are not opposite}(z_{ab}z_{cd} − 1) ,

D_{2}(z_{ij}) = ∏_{(ab) and (cd) ∈ Λ are not adjacent}(z_{ab}z_{cd} − z_{ef}) .

and D = D_{1}D_{2}. As we shall see below, ϕ(D) is a “universal denominator”, such that if f ∈ k[X^{±1}]_{0}^{G} then ϕ(D)f is a polynomial in the observables.

Lemma 3.1. (a) Suppose g ∈ G. Then ϕ(gD) = ϕ(D) ≠ 0 (b) Suppose g ∉ G. Then ϕ(gD) = 0.

Proof. (a) Clearly gD_{1} = D_{1} and gD_{2} = D_{2}, because g preserves both adjacency and opposition. Thus gD = D, so that ϕ(gD) = ϕ(D). To show that ϕ(D) ≠ 0, note that if the image under ϕ of a factor of D_{1} is zero then

\frac{x_{a}}{x_{b}} \frac{x_{c}}{x_{d}} = 1 .

This implies that (ab) and (cd) are opposite elements of Λ, which is excluded by the definition of D_{1}. This shows that ϕ(D_{1}) ≠ 0. Similarly, ϕ(z_{ab}z_{cd} − z_{ef}) = 0 if and only if (ab) and (cd) are adjacent in Λ. Thus ϕ(D_{2}) ≠ 0, and consequently, ϕ(D) ≠ 0.

(b) If g ∈ S_{n} is not in G then by Lemma 2.2 at least one of the following holds: (i) g does not preserve opposition or (ii) g does not preserve adjacency.

If (i) holds then g^{−1} does not preserve opposition either. In other words, there exists a pair of non-opposite elements (ab) and (cd) such that g(ab) and g(cd) are opposite, say, b_{1} = c_{1}. Then z_{ab}z_{cd} − 1 is a factor of D_{1} and ϕ(g(z_{ab}z_{cd} − 1)) = 0. Hence, ϕ(g(D_{1})) = 0 and thus ϕ(g(D)) = 0.

Similarly, if (ii) holds then there exists a pair of non-adjacent elements (ab) and (cd) such that g(ab) = (a_{1}b_{1}) and g(cd) = (c_{1}d_{1}) are adjacent, say, b_{1} = c_{1}. Now

ϕ(g(z_{ab}z_{cd} − z_{g^{−1}(a_{1}d_{1})})) = ϕ(z_{a_{1}b_{1}}z_{c_{1}d_{1}} − z_{a_{1}d_{1}})) = \frac{x_{a_{1}}}{x_{b_{1}}} \frac{x_{c_{1}}}{x_{d_{1}}} − \frac{x_{a_{1}}}{x_{d_{1}}} = 0

so that ϕ(g(D_{2})) = 0 and thus ϕ(g(D)) = ϕ(g(D_{1}))ϕ(g(D_{2})) = 0, as claimed. □

With the universal denominator ϕ(D) in hand, we can now state our algorithm. Algorithm 3.2.

Input: A function f(x_{1}, …, x_{n}) in k(X)_{0}^{G}.

Output: A rational function in the q_{r} representing f.

Step 1: Write f = f_{1}/f_{2} of a quotient of elements f_{i} that are in k[X^{±1}]_{0}^{G}; apply each of the subsequent steps to f_{1} and f_{2} (to simplify the notation we just assume from now on that f ∈ k[X^{±1}]_{0}^{G}).

Step 2: Find an element F ∈ k[z_{ij}] such that ϕ(F) = f.

Step 3: Set A = ∑_{g∈S_{N}} g(DF), write the numerator and denominator of

\frac{ϕ(A)}{2n! ϕ(D)}

as polynomials in the q_{r} and output the result. We comment on each step in turn. Step 1: To express an invariant degree 0 rational function f as a quotient of invariant polynomials, recall that f is a quotient of two polynomials of equal degree, say of degree d. Dividing top and bottom by x_{1}^{d}, we can write f in the form f_{1} = a/b, where a and b are in K[X^{±1}]_{0} (but a and b may not be G-invariant). Since f is G-invariant,

f = \frac{1}{2n!} ∑_{g∈G} g(f) = \frac{1}{2n!} ∑_{g∈G} \frac{g(a)}{g(b)} = \frac{f_{1}}{f_{2}}

where the numerator and denominator f_{i} are G-invariant polynomials in k[X^{±1}]_{0}^{G}. It suffices to express f_{1} and f_{2} as rational functions in the q_{r}, and we can therefore assume that f is in k[X^{±1}]_{0}^{G} from now on. Step 2: To lift f to an element F ∈ k[z_{ij}], write f(x_{1}, …, x_{n}) as a k-linear combination of degree-0 Laurent monomials x_{1}^{a_{1}} … x_{n}^{a_{n}}, with a_{1} + ⋯ + a_{n} = 0. Any such monomial is a product of a finite number of terms of the form \frac{x_{i}}{x_{j}}. Write all of the monomials in f in this form and replace each \frac{x_{i}}{x_{j}} by z_{ij} to obtain the desired F ∈ k[z_{ij}]. Step 3: By Lemma 3.1 the only non-zero terms in the sum

ϕ(A) = ∑_{g∈S_{N}} ϕ(g(D))ϕ(g(F))

correspond to g ∈ G. Thus

ϕ(A) = ∑_{g∈G} ϕ(g(D))ϕ(g(F)) = ∑_{g∈G} ϕ(D)g(ϕ(F)) = 2n! ϕ(D) f ,

as claimed.

The only remaining thing that needs to be done is to explain how to write ϕ(A) and ϕ(D) as polynomials in the q_{r}. Clearly A is a symmetric polynomial in the z_{ij}, where 1 ≤ i, j ≤ n. It is therefore a polynomial in the elementary symmetric functions s_{i}, 1 ≤ i ≤ N, and a polynomial in the power sums p_{r} = ∑ z_{ij}^{r} by Newton’s formulas. Since ϕ(p_{r}) = q_{r} − n it follows that ϕ(A) can be written as a polynomial in the q_{r}, as desired.

From the formula

2n!ϕ(D) = ∑_{g∈G} ϕ(g(D)) = ∑_{g∈S_{N}} ϕ(g(D)) = ϕ ( ∑_{g∈S_{N}} g(D))

it follows that, once D is symmetrized over S_{N}, the same procedure can be used to express 2n!ϕ(D) in terms of the observables. Remark 3.3. The above procedure can be modified to produce polynomials in the q_{r} with r ≤ N/2. Indeed, recall that ϕ(s_{N−i}) = c_{N−i} = c_{i} = ϕ(s_{i}). Thus the image under ϕ of a polynomial P (s_{1}, ⋯, s_{N}) in the elementary symmetric functions is unchanged if s_{i} is replaced by s_{N−i} for i > N/2.

Note also that if one only wants to express f(x_{1}, …, x_{n}) as a rational function in q_{r} for 1 ≤ r ≤ N, rather than 1 ≤ r ≤ N/2, then the algorithm of [St_{1}, Proof of Proposition 1.1.2] can be used to write A and the symmetrization of D directly as polynomials in the power sums p_{i} without going through elementary symmetric polynomials.

4. Initial terms and SAGBI bases

It is natural to try to apply Gröbner bases to our problem. Although Gröbner bases are usually applied to rings, they can be adapted to solve problems in function fields. This was first noticed in detail by Sweedler [Sw], and has since been extended in several theoretical and practical ways; see, e.g., [M]. In our context we would have a G-invariant polynomial f(X) in x_{i}/x_{j} that, by Theorem 2.1, lies in the field k(q_{k}) ⊂ k(X)_{0}. By introducing extra variables and calculating the Gröbner basis of a suitably chosen ideal, an explicit expression can be found for f as a rational function in the q_{i}.

Unfortunately, all of our implementations of this idea suggest that it has the same trouble as implementations of the constructive algorithm given in the previous section: they are far too slow. The purpose of this section is to introduce a faster algorithm, for n ≤ 4, using a variant of Gröbner bases called SAGBI bases.

We shall always assume that f ∈ k[X]_{0}^{G}; the general case reduces to this one (cf. Algorithm 3.2, Step 1).

The subduction algorithm. Given an element

p(x_{1}, …, x_{n}) = ∑ c_{a}x^{a} ∈ k[X^{±1}] = k[x_{1}^{±1}, …, x_{n}^{±1}] ,

where a = (a_{1}, …, a_{n}) ∈ ℤ^{n}, x^{a} = x_{1}^{a_{1}} … x_{n}^{a_{n}} and c_{a} ∈ k. We will write in(p) for the initial exponent p, i.e., the lexicographically largest exponent a such that c_{a} ≠ 0. If R is a subalgebra of k[X^{±1}] then {in(p) | p ∈ R} is clearly a subsemigroup of ℤ^{n}; this semigroup is usually denoted by in(R). We are interested in the case where R = k[X^{±1}]_{0}^{G}; in this case in(R) consists of elements a = (a_{1}, …, a_{n}) ∈ ℤ^{n} satisfying the following conditions:

(6)

(i) a_{1} + ⋯ + a_{n} = 0,
(ii) a_{1} ≥ ⋯ ≥ a_{n}, and
(iii) (a_{1}, …, a_{n}) ⪰ (−a_{n}, …, −a_{1}).

Here and in the sequel, ≻ denotes the lexicographic order on ℤ^{n}. Proposition 4.1. Suppose B is subset of R = k[X^{±1}]_{0}^{G} chosen so that the elements in(b) generate in(R) as a semigroup, as b ranges over B. Then R = k[B].

Our proof below is based on the subduction algorithm of Robbiano-Sweedler [RS] and Kapur-Madlener [KM] for expressing a given element α ∈ R as a polynomial in elements of B.

Proof. We want to write α ∈ R as a polynomial in elements of B. If α = 0, we are done. Otherwise write in(α) = e_{1}in(b_{1}) + ⋯ + e_{r}in(b_{r}), where b_{1}, …, b_{r} ∈ B and e_{1}, …, e_{m} are non-negative integers. Then α and b_{1}^{e_{1}} … b_{r}^{e_{r}} have the same leading exponent; thus for some c ∈ k,

α_{1} = α − cb_{1}^{e_{1}} … b_{r}^{e_{r}}

has a lexicographically smaller leading monomial than α. If α_{1} = 0, we are done. If not, we can replace α by α_{1} and apply the same procedure. That is, after subtracting a monomial in elements of B from α_{1}, we obtain α_{2} ∈ R with a smaller initial exponent, etc.

In order to complete the proof of the proposition, it is enough to show that the resulting sequence α = α_{0}, α_{1}, α_{2}, … in R will terminate, i.e., α_{r} = 0 for some r ≥ 0. This is a very special case of [Re, Proposition 6.5]; for the sake of completeness we give a direct proof below.

By our construction in(α_{0}) ≻ in(α_{1}) ≻ in(α_{2}) ≻ . . .. Thus it suffices to prove that for any given a = (a_{1}, …, a_{n}) ∈ in(R) there are only finitely many a′ = (a′_{1}, …, a′_{n}) ∈ in(R) such that a ⪰ a′. Indeed, if a ⪰ a′ then 0 ≤ a′_{1} ≤ a_{1}. Now condition (iii) says that a′_{n} ≥ −a′_{1} ≥ −a_{1}, and condition (ii) says that −a_{1} ≤ a′_{n} ≤ a′_{i} ≤ a′_{1} ≤ a_{1}. Thus a′_{i} may assume only finitely many values for every i = 1, …, n. This completes the proof of Proposition 4.1.

□

For computational purposes, we are interested in those cases, where the set B in Proposition 4.1 can be chosen to be finite, i.e., in(R) is a finitely generated semigroup. In such cases we shall refer to B as a SAGBI basis of G; cf. [Re, Introduction]. (Here SAGBI stands for “subalgebra analog to Gröbner bases for ideals”; this term is due to Robbiano and Sweedler [RS].)

Unfortunately, by [Re, Theorem 1.6] k[X^{±1}]_{0}^{G} has a SAGBI basis only for n = 2, 3 and 4; see also [Re, Example 7.3]. Moreover, the situation cannot be remedied by replacing the lexicographic order with a different term order. On the other hand, for n ≤ 4 the subduction algorithm is much faster than Algorithm 3.2.

Explicit SAGBI bases. Let c_{i} be the ith elementary symmetric polynomial in x_{i}/x_{j}, as in Lemma 2.3. (Here i and j are distinct integers ranging from 1 to n.) Recall that c_{1} = q_{1} − n = tr(X)tr(X^{−1}) − n. Lemma 4.2. The following elements form a SAGBI basis of k[X^{±1}]_{0}^{G}.

(a) c_{1}, if n = 2.

(b) c_{1} and c_{2}, if n = 3.

(c) c_{1}, c_{2}, c_{3} and p, if n = 4. Here p = s_{2}(X)s_{2}(X^{−1}), where

s_{2}(X) = x_{1}x_{2} + x_{1}x_{3} + ⋯ + x_{3}x_{4}

is the second symmetric polynomial in X = (x_{1}, …, x_{4}).

Proof. Let S = in(k[X^{±1}]_{0}^{G}) be the subsemigroup of ℤ^{n} given by (6). (a) If n = 2 then S is clearly generated by (1, −1) = in(c_{1}) as a semigroup.

(b) For n = 3, S is generated, as a semigroup, by the elements λ_{1} = (1, 0, −1) = in(c_{1}) and λ_{2} = (2, −1, −1) = in(c_{2}). Indeed, every element of μ ∈ S is of the form μ = (a, −c, −b), where b ≥ c ≥ 0 and a = b + c. Thus μ = cλ_{1} + (b − c)λ_{2} lies in the semigroup generated by λ_{1} and λ_{2}.

(c) We want to show that any μ = (a, b, c, d) ∈ S can be written as a non-negative integer linear combination of

λ_{1} = (1, 0, 0, −1) = in(c_{1}) ,
λ_{2} = (2, 0, −1, −1) = in(c_{2}) ,
λ_{3} = (3, −1, −1, −1) = in(c_{3}) and
λ_{4} = (1, 1, −1, −1) = in(p) .

If b ≤ 0 then the desired linear combination is given by

μ = (c − d)λ_{1} + (b − c)λ_{2} + (−b)λ_{3} .

If b > 0 then, after replacing μ by μ − bλ_{4}, we can assume b = 0 and apply the above formula. □

Corollary 4.3. (a) If n = 2 then k[X^{±1}]_{0}^{G} = k[c_{1}] = k[q_{1}].

(b) If n = 3 then k[X^{±1}]_{0}^{G} = k[c_{1}, c_{2}] = k[q_{1}, q_{2}].

(c) If n = 4, k[X^{±1}]_{0}^{G} = k[c_{1}, c_{2}, c_{3}, p] = k[q_{1}, q_{2}, q_{3}, p].

Proof. Immediate from Lemma 4.2, Proposition 4.1 and Newton’s formulas; cf. Lemma 2.3(a). □

Example 4.4. Let n = 3. Corollary 4.3 tells us that c_{1} and c_{2} form a SAGBI basis for k[X^{±1}]_{0}^{G}. For instance, applying the subduction algorithm, we obtain:

E_{2}(X, X) = 2(c_{1}^{2} + c_{1} − c_{2}) .

Similarly,

E_{2}(X, X^{2}) = 2c_{1}^{3} + 5c_{1}^{2} − 5c_{1}c_{2} + 9c_{1} − 12c_{2} + 18 .

These identities will be used in Section 6. Example 4.5. n = 4. Using the subduction algorithm of Proposition 4.1 to express c_{2}^{2} and c_{4} in terms of the SAGBI basis c_{1}, c_{2}, c_{3}, p, we obtain the following relations in the ring k[X^{±}]_{0}^{G}:

c_{2}^{2} = 2c_{1}^{2}p − 16c_{1}^{2} − 8c_{1}c_{2} − c_{1}p^{2} + 15c_{1}p − 48c_{1} +
3c_{2}p − 12c_{2} + c_{3}p − 2p^{2} + 18p − 36
c_{4} = 3c_{1}^{2} + c_{1}c_{2} − 3c_{1}p + 17c_{1} + c_{2} − 3c_{3} + p^{2} − 10p + 21 .

Eliminating p^{2} and solving for p gives

p = \frac{6 + 7c_{1} + 7c_{1}^{2} + 3c_{1}^{3} − 10c_{2} − 5c_{1}c_{2} + c_{1}^{2}c_{2} − c_{2}^{2} − 6c_{3} − 3c_{1}c_{3} − 2c_{4} − c_{1}c_{4}}{2 + c_{1} + c_{1}^{2} − 3c_{2} − c_{3}} .

This shows that p ∈ k(c_{1}, c_{2}, c_{3}, c_{4}) or, equivalently, p ∈ k(q_{1}, …, q_{4}). Thus by Corollary 4.3 k(X)_{0}^{G} = k(q_{1}, q_{2}, q_{3}, q_{4}). Recall that Theorem 2.1 asserts only that k(X)_{0}^{G} = k(q_{1}, …, q_{6}); we have thus shown that the last two of these generators are not needed.

To obtain explicit expressions for c_{5} and c_{6} as rational functions in c_{1}, …, c_{4}, we use the subduction algorithm once again:

c_{5} = c_{1}^{3} − 6c_{1}^{2} − 5c_{1}c_{2} + 7c_{1}p − 38c_{1} + c_{2}p − 7c_{2} + 6c_{3} − 2p^{2} + 20p − 42
c_{6} = −2c_{1}^{3} + c_{1}^{2}p + 6c_{1}c_{2} − 5c_{1}p + 27c_{1} − 2c_{2}p + 9c_{2} − 7c_{3} +
2p^{2} − 18p + 34 ,

then substitute the above formula for p.

Note also that for n = 3, Theorem 2.1 says that k(X)_{0}^{G} = k(q_{1}, q_{2}, q_{3}), but q_{3} is not needed by Corollary 4.3(b). We do not know whether or not any of the generators listed in Theorem 2.1 can be left out for n ≥ 5.

5. More sets of variables

The purpose of this section is to generalize Theorem 2.1 to the multi-array case. That is, instead of considering a single array of independent variables X = (x_{1}, …, x_{n}), we shall consider m arrays:

X_{1} = (x_{11}, …, x_{1n}) ,
X_{2} = (x_{21}, …, x_{2n}) ,
. . . . . . . . . . . . . . . . . . . . . .
X_{m} = (x_{m1}, …, x_{mn}) .

We shall view such n-tuples as diagonal n × n-matrices and operate with them as we did in Section 2. For example,

X_{i}X_{j} = (x_{i1}x_{j1}, …, x_{in}x_{jn}) , tr(X_{i}) = x_{i1} + ⋯ + x_{in} ,

the observables (3) can be written as

(7)  q_{r_{1},...,r_{m}}(X_{1}, …, X_{m}) = tr(X_{1}^{r_{1}} … X_{m}^{r_{m}})tr(X_{1}^{−r_{1}} … X_{m}^{−r_{m}})

and the functions E_{m} that arise in the phase transition problem (2) as

E_{m}(X_{1}, …, X_{m}) = tr(X_{1}) … tr(X_{m})tr(X_{1}^{−1} … X_{m}^{−1}) + (8)

tr(X_{1}^{−1}) … tr(X_{m}^{−1})tr(X_{1} … X_{m}) .

Let k(X_{1}, …, X_{m})_{0} be the subfield of k(x_{11}, x_{12}, …, x_{mn}) whose elements are rational functions in x_{ij} homogeneous of degree 0 in each n-tuple of variables X_{i}. In other words, k(X_{1}, …, X_{m})_{0} is the function field of the variety (ℙ^{n−1})^{m}. In Section 2 we studied the action of the group G = S_{n} × T on ℙ^{n−1}; this action extends to an action of G × ⋯ × G = G^{m} on (ℙ^{n−1})^{m}. We shall be interested in the invariants for the action of the diagonal subgroup of G^{m} which we shall also denote by G. In concrete terms, the symmetric group S_{n} acts on the function field k(X_{1}, …, X_{m})_{0} of (ℙ^{n−1})^{m} by simultaneously permuting the variables x_{i1}, …, x_{in} for each i. The 2-element group T = {1, τ} acts on k(X_{1}, …, X_{m})_{0} by

(9)  τ: x_{ij} ⟶ \frac{1}{x_{ij}} for every i = 1, …, m and j = 1, …, n.

These two actions commute and thus induce an action of G = S_{n} × T on k(X_{1}, …, X_{m})_{0}. Theorem 5.1. The field k(X_{1}, …, X_{m})_{0}^{G} is generated (over k) by the following elements:

q_{1,...,1} := tr(X_{1} … X_{m})tr (X_{1} … X_{m})^{−1}

and

q_{r,0,...,0} := tr(X_{1}^{r})tr(X_{1}^{−r}) ,
q_{0,r,...,0} := tr(X_{2}^{r})tr(X_{2}^{−r}) ,
⋮
q_{0,...,0,r} := tr(X_{m}^{r})tr(X_{m}^{−r}) ,

where r ranges from 1 to (n(n − 1))/2.

We will give a proof that generalizes the proof in Section 2, and then discuss the prospects for a more constructive proof. Note that our earlier results for m = 1 will be used in the proof.

We begin by disposing of the case n = 2. This case is anomalous in that G does not act effectively on k(X_{1}, …, X_{m})_{0}; the kernel of this action is the 2-element subgroup of G = S_{2} × T generated by (σ, τ), where σ is the non-trivial element of S_{2} and τ is the non-trivial element of T. Thus for n = 2

k(X_{1}, …, X_{m})_{0}^{G} = k(X_{1}, …, X_{m})_{0}^{τ} ;

here τ acts via the involution (9). Setting

t_{i} = \frac{x_{i1}}{x_{i2}}

we see that k(X_{1}, …, X_{m})_{0} = k(t_{1}, …, t_{m}) and τ acts on this field by taking t_{i} to \frac{1}{t_{i}} for each i = 1, …, m. It is now a simple exercise in Galois theory to show that in this case

k(t_{1}, …, t_{m})^{τ} = k(t_{1} + \frac{1}{t_{1}} , …, t_{m} + \frac{1}{t_{m}} , t_{1} … t_{m} + \frac{1}{t_{1} … t_{m}}) .

Since t_{i} + \frac{1}{t_{i}} = tr(X_{i})tr(X_{i}^{−1}) − 2 and

t_{1} … t_{m} + \frac{1}{t_{1} … t_{m}} = tr(X_{1} … X_{m})tr (X_{1} … X_{m})^{−1} − 2 ,

this proves Theorem 5.1 for n = 2.

From now on we will assume that n ≥ 3. Let K be the field generated over k by the observables listed in the theorem. For h = 1, …, n let

(10)  f_{h}(t) = ∏_{i≠j}(t − \frac{x_{hi}}{x_{hj}}) .

By Lemma 2.3 the coefficients of each f_{h}(t) lie in K. The field k(X_{1}, …, X_{m})_{0} is clearly the splitting field of the product

f(t) := f_{1}(t) … f_{m}(t)

over K. The Galois group of f contains G and is naturally embedded in the product G^{m} of the Galois groups of the f_{i}. Lemma 5.2. Assume n ≥ 3. An element g = (g_{1}, …, g_{m}) of G^{m} fixes

q_{1,...,1} = tr(X_{1} … X_{m})tr (X_{1} … X_{m})^{−1} ∈ k(X_{1}, …, X_{m})_{0}^{G}

if and only if g_{1} = ⋯ = g_{m}.

Proof. One direction is obvious: (g_{1}, …, g_{1}) fixes q_{1,...,1} for every g_{1} ∈ G. For the purpose of proving the converse, we may replace g by (g_{1}^{−1}, …, g_{1}^{−1})g and thus assume g_{1} = id. In other words, we want to prove that if g = (id, g_{2}, …, g_{n}) fixes q_{1,...,1} then g_{2} = … g_{m} = id in G.

For i = 2, …, m, let g_{i} = (σ_{i}, ϵ_{i}) ∈ G = S_{n}×T. Here T = {1, τ} is written multiplicatively, i.e., τ is written as −1 and each ϵ_{i} = ±1. In particular,

(1, g_{2}, …, g_{m}) · (\frac{x_{hi}}{x_{hj}}) = (\frac{x_{hσ_{h}(i)}}{x_{hσ_{h}(j)}} )^{ϵ_{h}} .

Writing out q_{1,...,1} explicitly in terms of the x_{ij} (cf. (3)), we obtain

q_{1,...,1} − n = ∑_{i≠j} \frac{x_{1i}}{x_{1j}} \frac{x_{2i}}{x_{2j}} … \frac{x_{mi}}{x_{mj}} ∈ K ,

and

q_{1,...,1} − n = g(q_{1,...,1} − n) = ∑_{i≠j} \frac{x_{1i}}{x_{1j}} (\frac{x_{2σ_{2}(i)}}{x_{2σ_{2}(j)}} )^{ϵ_{2}} … (\frac{x_{mσ_{m}(i)}}{x_{mσ_{m}(j)}} )^{ϵ_{m}} .

Comparing the terms of the last two equations, we see that for each h = 2, …, m, either (i) ϵ_{h} = 1 and σ_{h}(i) = i for every i = 1, …, n, i.e., σ_{h} = id, or (ii) ϵ_{h} = −1 and σ_{h}(i) = j for every pair of distinct integers i, j between 1 and n. In case (ii), σ(i) assumes every value between 1 and n other than i, which is impossible for n ≥ 3. We conclude that g_{2} = ⋯ = g_{n}, as claimed. □

This shows that G is the Galois group of k(X_{1}, ⋯, X_{m})_{0} over K. Examining the tower

k(X_{1}, …, X_{m})_{0}
|
k(X_{1}, …, X_{m})_{0}^{G}
|
K

we conclude that k(X_{1}, …, X_{m})_{0}^{G} = K, thus completing the proof of the theorem.

We now remark that Algorithm 3.2 (for m = 1) can be extended to the multi-array case by means of a suitable universal denominator. The generalization is not entirely straightforward because of the “new” generator

q_{1,...,1} = tr(X_{1} … X_{m})tr (X_{1} … X_{m})^{−1}

that connects the different X_{i}.

Let k[X_{1}^{±1}, …, X_{m}^{±1}]_{0} be the k-linear combinations of Laurent monomials x_{11}^{a_{11}} … x_{mn}^{a_{mn}} such that a_{i1} + ⋯ + a_{in} = 0 for every i = 1, …, m. Note that k[X_{1}^{±1}, …, X_{m}^{±1}]_{0} is generated, as a k-algebra, by elements of the form \frac{x_{ij}}{x_{il}}; in particular, the field k(X_{1}, …, X_{m})_{0} is the field of fractions of k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}. Note also that k[X_{1}^{±1}, …, X_{m}^{±1}]_{0} is a G-invariant subring of k(X_{1}, …, X_{m})_{0}.

Let z_{hij} be a set of mN algebraically independent variables over k, where N = n(n − 1), i and j are distinct integers between 1 and n, and h ranges from 1 to m. Let t be another independent variable and let

ϕ: k[z_{hij}, t] ⟶ k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}

be the surjective k-algebra homomorphism given by

ϕ(z_{hij}) = \frac{x_{hi}}{x_{hj}} and ϕ(t) = q_{1,...,1} − n.

We note that S_{N}^{m} acts on k[z_{hij}, t] and where the h-th component permutes the z_{hij} and fixes t.

Our universal denominator is a polynomial E ∈ k[z_{hij}, t] that has the property that for σ_{1}, …, σ_{m} ∈ S_{N}

(11)  ϕ((σ_{1}, …, σ_{m})E) = \begin{cases}ϕ(E) & if σ_{1} = ⋯ = σ_{m} ∈ G, \\ 0 & in all other cases. \end{cases}

Here, as before, we view G as a subgroup of S_{N} for n ≥ 3.

The polynomial E is defined by

E(z_{hij}, t) := D(z_{1ij}) · · · · · D(z_{mij}) E_{1}(z_{hij}, t) ,

where D is the polynomial defined in Section 3 and

E_{1}(z_{hij}, t) := ∏(t − ∑_{i≠j} z_{1ij}z_{2g_{2}(ij)} … z_{mg_{m}(ij)}) ;

the product is taken over all g_{2}, …, g_{m} ∈ G such that at least one g_{i} ≠ 1, and the sum is taken over all pairs of distinct integers i and j between 1 and n.

As in the m = 1 case one can verify that E satisfies (11). The algorithm for expressing invariants in terms of observables is now similar to the m = 1 case, and we leave the details to the reader.

6. Reduction to one set of variables

We now return to the problem of writing a G-invariant multihomogeneous rational function f(x_{11}, x_{12}, …, x_{mn}) of total degree 0 in each group of variables X_{1} = (x_{11}, …, x_{1n}), …, X_{m} = (x_{m1}, …, x_{mn}), as a rational function in the “observables” q_{r_{1},...,r_{m}}.

In principle, the algorithm sketched in the preceding section is a solution to this problem. As one might expect, it is too slow to be of practical significance. On the other hand, the approach we took in Section 4 cannot be extended to m ≥ 2, even for small n, because suitable (finite) SAGBI bases do not exist; see [Re, Theorem 1.6 and Example 7.3]. This motivated our search for an algorithm that would reduce computations in the multiarray case (m ≥ 2) to computations in the single-array case (m = 1). In this section we discuss such an algorithm and use it to generate explicit formulas for E_{2}(X, Y) for n = 3 and 4.

Another generating set of observables. We begin by proving another variant of Theorem 1.3(a). Theorem 6.1. The field k(X_{1}, …, X_{m})_{0}^{G} is generated (over k) by the elements

q_{r} := q_{r}(X_{1}) = q_{r,0,...,0} := tr(X_{1}^{r})tr(X_{1}^{−r})

and

q_{s}^{(2)} := q_{s,1,0,...,0} := tr(X_{1}^{s}X_{2})tr(X_{1}^{−s}X_{2}^{−1}) ,
⋮
q_{s}^{(m)} := q_{s,0...,0,1} := tr(X_{1}^{s}X_{m})tr(X_{1}^{−s}X_{m}^{−1}) .

where r = 1, …, \frac{n(n−1)}{2} and s = 0, …, n(n − 1) − 1.

Informally speaking, the element q_{1,...,1} of Theorem 5.1 ties X_{1}, …, X_{m} together, where as the elements q_{r}^{(i)} of Theorem 6.1 relate X_{i} to X_{1} for each i = 2, …, m.

Proof. Let K = k(X_{1}, …, X_{m})_{0} = k(x_{ij}/x_{il}), and let K^{N} be a vector space of dimension N = n(n − 1) over K. We shall write elements of K^{N} as (z_{ij}), where (i, j) ∈ Λ, i.e., i and j are distinct integers between 1 and n, as in (5). The natural action of G = S_{n} × T on Λ induces a permutation action on K^{N}.

Given an n-tuple A = (a_{1}, …, a_{n}), we will denote the N-tuple of ratios \frac{a_{i}}{a_{j}} by ρ(A). Then ρ: K^{n} ⟶ K^{N} is a G-equivariant map. Finally, for h = 1, …, m let Z_{h} be the N-tuple of variables (z_{hij}), where (i, j) ∈ Λ.

We want to show that any f(X_{1}, …, X_{m}) ∈ k(X_{1}, …, X_{m})^{G} can be written as a rational function in the observables listed in the statement of the theorem. We begin with several reductions. First of all, we may assume without loss of generality that f(X_{1}, …, X_{m}) ∈ k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G}, by writing an invariant rational function as a quotient of invariant polynomials. Secondly, f(X_{1}, …, X_{m}) can be lifted to a G-invariant polynomial F (Z_{1}, …, Z_{m}) in z_{hij} such that

f(X_{1}, …, X_{m}) = F (ρ(X_{1}), …, ρ(X_{m})) .

Thirdly, we may assume without loss of generality that F (Z_{1}, …, Z_{m}) is a homogeneous polynomial in the arrays of variables Z_{1}, …, Z_{m} of multidegree (d_{1}, …, d_{m}). Indeed, any G-invariant F can be written as a sum of G-invariant multihomogeneous components, say, F = F_{1} + ⋯ + F_{r}, and we may replace f by f_{i} = F_{i}(ρ(X_{1}), …, ρ(X_{m})).

Multilinearizing F, we obtain a G-invariant multilinear polynomial M in d = d_{1} + ⋯ + d_{m} N-variable arrays such that

(12) f(X_{1}, …, X_{m}) = M(\underbrace{ρ(X_{1}), …, ρ(X_{1})}_{d_{1} times}, …, \underbrace{ρ(X_{m}), …, ρ(X_{m})}_{d_{m} times}) .

Next we observe that by the Vandermonde argument

(13)  ρ(I), ρ(X_{1}), …, ρ(X_{1}^{N−1})

form a K-basis of K^{N}; here I stands for the identity n-tuple (1, …, 1). In particular, for every 2 ≤ i ≤ m, we can write

(14)  ρ(X_{i}) = λ_{i0}ρ(I) + λ_{i1}ρ(X_{1}) + ⋯ + λ_{i,N−1}ρ(X_{1}^{N−1}) .

for some λ_{i0}, …, λ_{i N−1} ∈ K^{N}. Substituting this into (12) and expanding, we see that f(X_{1}, …, X_{m}) can be written as a sum of terms of the form

(monomial in λ_{ij}) M(ρ(X_{1}^{i_{1}}), …, ρ(X_{1}^{i_{d}})).

(In fact, i_{1} = ⋯ = i_{d_{1}} = 1 in each term, but we shall not use this in the sequel.) Since M is G-invariant, each

M(ρ(X_{1}^{i_{1}}), …, ρ(X_{1}^{i_{d}}))

is an element of k[X_{1}]_{0}^{G}, and thus, by Theorem 2.1, it can be written as a rational function in the observables q_{r} = q_{r}(X_{1}).

Thus it remains to show that each λ_{ij} lies in the field L generated by the elements listed in the statement of the theorem. Note that by Theorem 2.1 the observables q_{r} lie in L for every r (and not just for r = 1, … N/2). Taking the dot product of both sides of (14) with ρ(I), ρ(X_{1}), …, ρ(X_{1}^{N−1}), and remembering that

ρ(X_{1}^{i}) · ρ(X_{1}^{j}) = q_{i+j} − n and ρ(X_{i}) · ρ(X_{1}^{j}) = q_{j}^{(i)} − n,

we obtain the following linear system:

(15)  ∑_{i=1}^{N}(q_{i+j} − n)λ_{i} = q_{j}^{(i)} − n, where i = 0, 1, …, N − 1.

Since ρ(I), ρ(X_{1}), …, ρ(X_{1}^{N−1}) form a basis of K^{N}, the matrix

(16)  Q = (\begin{matrix}q_{0} − n & q_{1} − n & … & q_{N−1} − n \\ q_{1} − n & q_{2} − n & … & q_{N−1} − n \\ … \\ q_{N−1} − n & q_{N} − n & … & q_{2N−2} − n \end{matrix}) .

of this system is non-singular. Solving the linear system (15), we conclude that each λ_{j} lies in L, as claimed. □

Multilinear invariants. Our proof of Theorem 6.1 reduces the computation of a given element f of k(X_{1}, …, X_{m})_{0}^{G} to computing finitely many elements in k[X_{1}]_{0}^{G}. Note that this reduction is constructive. The resulting algorithm is cumbersome in general; however, it simplifies considerably in the case where the polynomial F (Z_{1}, …, Z_{m}) is itself multilinear, i.e., d_{1} = ⋯ = d_{m} = 1 and M = F. This is exactly what happens in that case of greatest interest to us, namely, f = E_{m} (cf. (2)); here

F (Z_{1}, …, Z_{m}) = ∑_{j_{1},...,j_{m},j=1}^{n} z_{1j_{1}j} … z_{mj_{m}j} + z_{1jj_{1}} … z_{mjj_{m}} .

Proposition 6.2.

E_{m}(X_{1}, …, X_{m}) = ∑_{i_{2},...,i_{m}=0}^{N−1} λ_{2i_{1}} … λ_{mi_{m}}E_{m}(X_{1}, X_{1}^{i_{2}}, …, X_{1}^{i_{m}}) ,

where

(\begin{matrix}λ_{i0} \\ λ_{i1} \\ … \\ λ_{i N−1} \end{matrix}) = Q^{−1} (\begin{matrix}q_{0}^{(i)} − n \\ q_{1}^{(i)} − n \\ … \\ q_{N−1}^{(i)} − n \end{matrix}) .

and Q is the N × N-matrix (16).

Proof. The first formula is obtained by substituting (14) into

E_{m}(X_{1}, …, X_{m}) = F (ρ(X_{1}), …, ρ(X_{m}))

and expanding the right hand side. (Note that the specific form of F is not used here; we only use the fact that F is multilinear.) The second formula comes from solving the linear system (15). □

Remark 6.3. Proposition 6.2 remains valid if E_{m} is replaced by any f in k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G} such that f(X_{1}, …, X_{m}) = F (ρ(X_{1}), …, ρ(X_{m})) for some G-invariant multilinear polynomial F (Z_{1}, …, Z_{m}) in m N-variable arrays Z_{1}, …, Z_{m}.

Explicit determination of the triplet phase invariant. For m = 2 the formula of Proposition 6.2 can be rewritten in the matrix form:

(17)  E_{2}(X, Y) = (e_{0}, …, e_{N−1}) Q^{−1} (\begin{matrix}q_{0,1} − n \\ q_{1,1} − n \\ … \\ q_{N−1,1} − n \end{matrix}) ,

where e_{i} = e_{i}(X) = E_{2}(X, X^{i}). Here, as usual, we write X for X_{1} and Y for X_{2}; cf. (2). We have thus reduced the computation of E_{2}(X, Y) to the computation of e_{i} = E(X, X^{i}) for i = 0, …, N − 1. Note that e_{0} = 2nq_{1}, so there are only N − 1 elements e_{1}, …, e_{N−1} we need to compute. We can further reduce this number by using the basis

ρ(X^{−N/2}), ρ(X^{−N/2+1}), …, ρ(X^{N/2−1})

of K^{n} instead of (13). This has the effect of shifting the subscripts in (17) as follows: Proposition 6.4.

E_{2}(X, Y) = (e_{−N/2}, e_{1−N/2}, …, e_{N/2−1}) · R^{−1} · (\begin{matrix}q_{−N/2,1} − n \\ q_{−N/2+1,1} − n \\ … \\ q_{N/2−1,1} − n \end{matrix}) ,

where q_{r} = q_{r,0}, e_{i} = E_{2}(X, X^{i}), and R is the N × N-matrix

R = (\begin{matrix}q_{−N} − n & q_{−N+1} − n & … & q_{−1} − n \\ q_{−N+1} − n & q_{−N+2} − n & … & q_{0} − n \\ … \\ q_{−1} − n & q_{0} − n & … & q_{N−2} − n \end{matrix}) .

□

Keeping in mind the identities e_{i} = e_{−1−i} and e_{0} = 2nq_{1}, we see that the formula of Proposition 6.4 reduces the computation of E_{2}(X, Y) to the computation of e_{i} = E_{2}(X, X^{i}) for i = 1, …, (N/2) − 1. We also note that since q_{−r} = q_{r}, the matrix R involves q_{r} only for r = 1, …, N, as opposed to r = 1, …, 2N − 2 for the matrix (16).

The calculation of the e_{i} involves only one set of variables. For n = 3 we have the following explicit results. Example 6.5. Let n = 3. Then N = 6, q_{0} = 9, and Proposition 6.4 gives

E_{2}(X, Y) = (e_{2}, e_{1}, 6q_{1}, 6q_{1}, e_{1}, e_{2}) R^{−1} (\begin{matrix}q_{−3,1} − 3 \\ q_{−2,1} − 3 \\ … \\ q_{2,1} − 3 \end{matrix}) ,

where R is the 6 × 6-matrix

R = (\begin{matrix}q_{6} − 3 & q_{5} − 3 & q_{4} − 3 & q_{3} − 3 & q_{2} − 3 & q_{1} − 3 \\ q_{5} − 3 & q_{4} − 3 & q_{3} − 3 & q_{2} − 3 & q_{1} − 3 & 6 \\ q_{4} − 3 & q_{3} − 3 & q_{2} − 3 & q_{1} − 3 & 6 & q_{1} − 3 \\ q_{3} − 3 & q_{2} − 3 & q_{1} − 3 & 6 & q_{1} − 3 & q_{2} − 3 \\ q_{2} − 3 & q_{1} − 3 & 6 & q_{1} − 3 & q_{2} − 3 & q_{3} − 3 \\ q_{1} − 3 & 6 & q_{1} − 3 & q_{2} − 3 & q_{3} − 3 & q_{4} − 3 \end{matrix}) .

Recall that e_{1} and e_{2} were computed in Example 4.4 by using SAGBI basis techniques:

e_{1} = 2c_{1}^{2} + 2c_{1} − 2c_{2}
e_{2} = 2c_{1}^{3} + 5c_{1}^{2} − 5c_{1}c_{2} + 9c_{1} − 12c_{2} + 18 .

These can be easily expressed in terms of q_{1} and q_{2} by using Newton’s identities, which here amount to

c_{1} = q_{1} − 3  and  c_{2} = ((q_{1} − 3)^{2} − (q_{2} − 3))/2.

The explicit formula for E_{2} that results is quite different from, and considerably more elaborate than, the formula given in Example 1.2.

Example 6.6. Let n = 4. Then N = 12, q_{0} = 16, and the formula of Proposition 6.4 reduces to

E_{2}(X, Y) = (e_{5}, e_{4}, e_{3}, e_{2}, e_{1}, 8q_{1}, 8q_{1}, e_{1}, e_{2}, e_{3}, e_{4}, e_{5}) · R^{−1} · (\begin{matrix}q_{−6,1} − 4 \\ q_{−2,1} − 4 \\ … \\ q_{5,1} − 4 \end{matrix}) ,

where R is the 12 × 12-matrix

R = (\begin{matrix}q_{12} − 4 & q_{11} − 4 & … & q_{3} − 4 & q_{2} − 4 & q_{1} − 4 \\ q_{11} − 4 & q_{10} − 4 & … & q_{2} − 4 & q_{1} − 4 & 12 \\ q_{10} − 4 & q_{9} − 4 & … & q_{1} − 4 & 12 & q_{1} − 4 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ q_{1} − 4 & 12 & … & q_{9} − 4 & q_{10} − 4 & q_{11} − 4 \end{matrix}) .

The elements e_{1}, …, e_{5} can again be explicitly determined using the SAGBI basis subduction algorithm; the result is:

e_{1} = 2c_{1}^{2} + 8c_{1} − 2c_{2} − 4p + 20
e_{2} = 2c_{1}^{3} + 4c_{1}^{2} − 5c_{1}c_{2} − c_{1}p + 7c_{1} − 5c_{2} + 3c_{3} + 2p + 2
e_{3} = 2c_{1}^{4} + 4c_{1}^{3} − 7c_{1}^{2}c_{2} + 3c_{1}^{2}p − 41c_{1}^{2} − 31c_{1}c_{2}

+7c_{1}c_{3} − 2c_{1}p^{2} + 40c_{1}p − 154c_{1} + 8c_{2}p − 28c_{2} +2c_{3}p + 24c_{3} − 8p^{2} + 72p − 136

e_{4} = 2c_{1}^{5} + 4c_{1}^{4} − 9c_{1}^{3}c_{2} + 13c_{1}^{3}p − 131c_{1}^{3} − 80c_{1}^{2}c_{2} + 9c_{1}^{2}c_{3}

−7c_{1}^{2}p^{2} + 144c_{1}^{2}p − 651c_{1}^{2} + 24c_{1}c_{2}p − 186c_{1}c_{2} + 7c_{1}c_{3}p +43c_{1}c_{3} − 29c_{1}p^{2} + 379c_{1}p − 1136c_{1} − 5c_{2}c_{3} + 21c_{2}p −120c_{2} + 3c_{3}p + 78c_{3} − 34p^{2} + 334p − 688

e_{5} = 2c_{1}^{6} + 4c_{1}^{5} − 11c_{1}^{4}c_{2} + 27c_{1}^{4}p − 243c_{1}^{4} − 142c_{1}^{3}c_{2}

+11c_{1}^{3}c_{3} − 14c_{1}^{3}p^{2} + 289c_{1}^{3}p − 1317c_{1}^{3} + 46c_{1}^{2}c_{2}p −429c_{1}^{2}c_{2} + 14c_{1}^{2}c_{3}p + 53c_{1}^{2}c_{3} − 66c_{1}^{2}p^{2} + 892c_{1}^{2}p −2830c_{1}^{2} − 17c_{1}c_{2}c_{3} + 81c_{1}c_{2}p − 471c_{1}c_{2} + 19c_{1}c_{3}p +135c_{1}c_{3} + 2c_{1}p^{3} − 137c_{1}p^{2} + 1286c_{1}p − 3039c_{1} − 2c_{2}^{3} −35c_{2}c_{3} + 27c_{2}p − 167c_{2} + 3c_{3}^{2} − 2c_{3}p^{2} − c_{3}p +171c_{3} + 8p^{3} − 150p^{2} + 856p − 1402 Then we eliminate p, by using the formula in Example 4.5. to express e_{1}, …, e_{5} as rational functions in c_{1}, c_{2} and c_{3}. Finally, we use Newton’s identities to rewrite each e_{i} as a rational function of q_{1}, q_{2} and q_{3}. Remark 6.7. The SAGBI basis algorithms were implemented explicitly in magma [BCP], and are very efficient, though of course they are limited to n ≤ 4.

7. Regular invariants

Theorems 5.1 and 6.1 tell us that if we allow r_{1}, …, r_{m} to range over the integers then the observables q_{r_{1},...,r_{m}}(X_{1}, …, X_{m}) generate k(X_{1}, …, X_{m})_{0}^{G} as a field extension of k. H. Hauptman asked us whether the functions E_{m} in (8) that arise in the phase determination problem (2) can be written as polynomials, rather than rational functions in the q_{r_{1},...,r_{m}}. More generally, we can ask whether the the observables q_{r_{1},...,r_{m}} generate the k-algebra k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G}. In this section, we will show that the answer is generally “no.” Proposition 7.1. Assume n ≥ 4.

(a) The function

f(X) = E_{2}(X, X) = tr^{2}(X)tr(X^{−2}) + tr^{2}(X^{−1})tr(X^{2})

cannot be written as a polynomial in the observables q_{r}, as r ranges over the integers.

(b) Suppose m ≥ 2. Then function E_{m}(X_{1}, …, X_{m}) given by (8) cannot be written as a polynomial in the observables q_{r_{1},...,r_{m}}, as r_{1}, …, r_{m} range over the integers.

(c) For any m ≥ 1 the k-algebra k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G} is not generated by the observables q_{i_{1},...,i_{m}}, as i_{1}, …, i_{m} range over the integers.

By Corollary 4.3(a) and (b), f can be written as a polynomial in the observables if n = 2 or 3; i.e., part (a) is not true for n = 2 or 3. Also, part (b) is not true for m = 1 (indeed, E_{1} is itself an observable).

Curiously, as we saw in the Section 5, the observables q_{i_{1},...,i_{m}} come close to generating the k-algebra k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G} in the following sense: every α ∈ k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G} can be written in the form

α = \frac{β}{ϕ(E)}

for some β ∈ k[q_{i_{1},...,i_{m}}]. Here ϕ(E) is a fixed nonzero element of k[q_{i_{1},...,i_{m}}], independent of α.

Proof. Part (b) is easily deduced from part (a) by specializing X_{1} and X_{2} to a single array of indeterminates X = (x_{1}, …, x_{n}), and X_{3}, …, X_{m} to the “identity array” I = (1, …, 1). Part (c) is a consequence of parts (a) (for m = 1) and (b) (for m ≥ 2), since f ∈ k[X]_{0}^{G} and E_{m} ∈ k[X_{1}^{±1}, …, X_{m}^{±1}]_{0}^{G} for every m ≥ 2.

Thus we only need to prove (a). Let

ρ: 𝔸^{n} − {x_{1} … x_{n} = 0} ⟶ 𝔸^{N}

be the map given by

(18)  ρ(x_{1}, …, x_{n}) = (\frac{x_{1}}{x_{2}} , \frac{x_{1}}{x_{3}} , …, \frac{x_{n−1}}{x_{n}}) .

To prove part (a), we claim that it suffices to exhibit n-tuples x and y with nonzero coordinates such that

(i) f(x) ≠ f(y) and (ii) ρ(x) ∼ ρ(y),

where two N-tuples u and v are equivalent, written u ∼ v, if one is a permutation of the other.

Indeed, assume that (i) and (ii) are true. Since the observables q_{r} are symmetric functions in {x_{i}/x_{j}}, where i, j = 1, …, n, i ≠ j, the fact that ρ(x) ∼ ρ(y) implies that q_{r}(x) = q_{r}(y) for every integer r. Thus q(x) = q(y) for every q ∈ k[q_{1}, q_{2}, …]; given that f(x) ≠ f(y), we immediately deduce that f ∉ k[q_{1}, q_{2}, …] as desired. Note that it is sufficient if the coordinates of x and y lie in the algebraic closure of the field k.

First consider the case n > 4. Let z be a primitive n-th root of unity. (Recall that we are assuming that char (k) = 0, so that z exists in the algebraic closure of k.) We claim that the points

x = (1, 1, z^{3}, z^{3}, z^{4}, ⋯, z^{n−1})
y = (z, z, z^{2}, z^{2}, z^{4}, ⋯, z^{n−1})

satisfy conditions (i) and (ii). Here x is obtained from the point (1, z, z^{2}, ⋯, z^{n−1}) by replacing z by 1, and z^{2} by z^{3}, and y is obtained from (1, z, z^{2}, ⋯, z^{n−1}) by a similar alteration of two coordinates. Note that

(19)  tr(x^{i}) + tr(y^{i}) = 2(1^{i} + z^{i} + z^{2i} + ⋯ + z^{(n−1)i}) = 0

for any i ≢ 0 (mod n). In particular, tr(x^{i}) = −tr(y^{i}) for i = ±1, ±2 and consequently, f(x) = −f(y). Thus, in order to check (i), we only need to verify that f(x) ≠ 0. This is easily done; substituting

tr(x^{i}) = 1 − z^{i} − z^{2i} + z^{3i} = (1 − z^{i})(1 − z^{2i})

into f(x) = tr^{2}(x)tr(x^{−2}) + tr^{2}(x^{−1})tr(x^{2}), we see that

f(x) = 2z^{−6}(1 − z)^{2}(1 − z^{2})^{3}(1 − z^{4}) ≠ 0

for any n > 4.

Now we have to show that ρ(x) ∼ ρ(y). To do this let G_{x}(t) denote the formal generating function

G_{x}(t) = 2 + 2t^{3} + t^{4} + ⋯ + t^{n−1} ∈ ℤ[t]/(t^{n} − 1)

in which the coefficient of t^{i} is the number of times that z^{i} appears as a coordinate in x. Then G_{x}(t)G_{x}(t^{−1}) ∈ ℤ[t]/(t^{n} − 1) is the formal generating function of ρ(x). Thus (ii) is equivalent to

(20)  G_{x}(t)G_{x}(t^{−1}) = G_{y}(t)G_{y}(t^{−1}) in ℤ[t]/(t^{n} − 1).

Using the factorization t^{n}−1 = (t−1)(t^{n−1}+⋯+1), we get an isomorphism

ℤ[t]/(t^{n} − 1) ≃ ℤ ⊕ R, where R := ℤ[t]/(t^{n−1} + ⋯ + 1).

Here t maps to 1 in the first summand. We see that in order to prove (20) it suffices to check that the two sides have the same images in ℤ and in R. The image in ℤ is obtained by evaluating at 1, and G_{x}(1) = G_{y}(1) = n, so the desired identity is immediate in ℤ. If g_{x} and g_{y} denote the images of G_{x} and G_{y} in R, then a calculation similar to (19) show that g_{y}(t) = −g_{x}(t).

It follows immediately that g_{x}(t)g_{x}(t^{−1}) = g_{y}(t)g_{y}(t^{−1}) as desired. This finishes the proof for n > 4.

For n = 4 we have to consider a more carefully crafted example. Let z be a primitive 13-th root of unity, and set

(21)  x = (1, z, z^{4}, z^{6}),  y = (1, z, z^{4}, z^{11}) .

An easy calculation, which we will leave to the reader, shows that f(x) = −f(y) ≠ 0, and a generating function argument shows that ρ(x) ∼ ρ(y). (This choice of x and y is based on the fact that {0, 1, 4, 6} and {0, 1, 4, 11} are inequivalent planar difference sets for the cyclic group ℤ/13ℤ; cf. [Ry, Chapter 9].)

This completes the proof of Proposition 7.1. □

8. Rationality

In this section we investigate the structure of the field k(X_{1}, …, X_{m})_{0}^{G}, without specific reference to the observables. The main result, Proposition 8.1 below, was communicated to us by M. Lorenz.

Recall that a field extension K/k is called rational (or equivalently, K is said to be rational over k) if K = k(t_{1}, …, t_{r}) for some elements t_{1}, …, t_{r} ∈ K, algebraically independent over k. The extension K/k is called stably rational if there exists a field L, containing K, which is rational over both K and k. In other words, for some finite collection of indeterminates s_{1}, …, s_{r} the field L = K(s_{1}, …, s_{r}) is rational over k. Proposition 8.1. (a) For m = 1, k(X)_{0}^{G} is rational over k.

(b) For any m ≥ 1, k(X_{1}, …, X_{m})_{0}^{G} is stably rational over k.

Proof. (a) First assume n = 2. Then k(X)^{G} ⊂ k(X)_{0} = k(x_{1}/x_{2}), and the desired conclusion follows from Lüroth’s theorem. For n ≥ 3, part (a) is a special case of a theorem of N. Lemire; see [L, Theorem 7.7]. To see how Lemire’s theorem applies, note that the elements x_{i}/x_{j} (viewed additively, with the natural S_{n}-action) form the root system A_{n−1}. The group G = S_{n} × T is the automorphism group of this root system, and k(X)_{0} = k(M), where M is the lattice (i.e., the multiplicative subgroup of k(X)_{0}^{∗}) generated by {x_{i}/x_{j} | i, j = 1, …, n}.

(b) We argue by induction on m. The base case, m = 1, is part (a). For the induction step, assume m ≥ 2. Let K_{m} = k(X_{1}, …, X_{m})_{0} and L = K_{m−1}(x_{1}, …, x_{n}), where X_{m} = (x_{1}, …, x_{n}). By the induction assumption, K_{m−1}^{G} is stably rational over k; thus it is enough to show that K_{m}^{G} is stably rational over K_{m−1}^{G}. We will do this by proving that L^{G} is rational over both K_{m}^{G} and K_{m−1}^{G}.

Note that since L = K_{m}(x_{1}) = K_{m−1}(x_{1}, …, x_{n}) and the G-action on K_{m−1} is faithful, the desired conclusion would follow from the no-name lemma, if G-acted linearly (or, more precisely, semi-linearly) on the variables x_{1}, …, x_{n}; see e.g., [EM, Proposition 1.1] or [Sh, Appendix 3]. However, the no-name lemma cannot be used directly in this setting because our G-action is not semi-linear (τ acts by inversion!).

Fortunately, our action can be easily linearized, following an argument of Hajja and Kang [HK, Lemma 2.3(i)]. Let y_{i} = \frac{1−x_{i}}{1+x_{i}}. Then S_{n} permutes y_{1}, …, y_{n} and τ sends each y_{i} to −y_{i}. Since x_{i} = \frac{1−y_{i}}{1+y_{i}}, we have

L = K_{m}(y_{1}) = K_{m−1}(y_{1}, …, y_{n}) .

Now the no-name lemma tells us that L^{G} is rational over both K_{m}^{G} and K_{m−1}^{G}, as claimed. □

Remark 8.2. Let H be the subgroup of index 2 in G = S_{n} × T consisting of pairs of the form (σ, τ^{sign σ}). Hajja and Kang [HK, Theorem 3.2] have shown that k(X_{1}, …, X_{m})_{0}^{H} is rational over k.

References

[BCP] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The user language, Computational algebra and number theory (London, 1993). J. Symbolic Comput. 24 (1997), no. 3-4, 235–265.

[Da] J. Dalbec, Multisymmetric Functions, Beiträge zur Algebra und Geometrie, 40 (1999), 27-51.

[EM] S. Endô, T. Miyata, Quasi-permutation modules over finite groups, J. Math. Soc. Japan, 25, no. 3, (1973), 397–421.

[F] D. R. Farkas, Reflection groups and multiplicative invariants, Rocky Mountain J. Math, 16, no. 2 (1986), 215-222.

[Gia] C. Giacovazzo, Direct Phasing in Crystallography, Oxford University Press, 1998.

[Ha1] H. Hauptman, D. Y. Guo, H. Xu, R. H. Blessing, Algebraic Direct Methods for Few-Atom Structure Models, Acta Crystallographica A58 (2002), 361–369.

[Ha2] H. Hauptman, The phase problem of x-ray crystallography, Rep. Prog. Phys. (1991), 1427-1454.

[HK] M. Hajja, M.-C. Kang, Twisted actions of symmetric groups, J. Algebra 188 (1997), no. 2, 626–647.

[KM] D. Kapur, K. Madlener, A completion procedure for computing a canonical basis for a k-subalgebra, Computers and mathematics (Cambridge, MA, 1989), 1–11, Springer, New York, 1989.

[L] N. Lemire, Reduction in the rationality problem for multiplicative invariant fields, J. Algebra 238 (2001), no. 1, 51–81.

[M] J. Müller-Quade, R. Steinwandt, Gröbner bases applied to finitely generated field extensions, J. Symbolic Comput. 30 (2000), 469–490.

[Re] Z. Reichstein, SAGBI bases in rings of multiplicative invariants, Comment. Math. Helv. 78 (2003), no. 1, 185–202.

[RS] L. Robbiano, M. Sweedler, Subalgebra bases, Commutative algebra (Salvador, 1988), Lecture Notes in Math., 1430, Springer, Berlin, 1990, 61–87.

[Ry] H. J. Ryser, Combinatorial mathematics, The Carus Mathematical Monographs, No. 14, published by the Mathematical Association of America, 1963.

[Sh] I. R. Shafarevich, Basic Algebraic Geometry, vol. 1, second edition, Springer-Verlag, 1994.

[St_{1}] B. Sturmfels, Algorithms in Invariant Theory, Texts and Monographs in Symbolic

Computation, Springer-Verlag, 1993. [St_{2}] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series,

vol. 8, Amer. Math. Soc., 1995.

[Sw] M. Sweedler, Using Groebner Basis to Determine the Algebraic and Transcendental Nature of Field Extensions: Return of the Killer Tag Variables, in Applied algebra, algebraic algorithms and error-correcting codes (San Juan, PR, 1993), Lecture Notes in Comput. Sci., 673, Springer, Berlin, 1993, 66–75.

[vW] B. L. van der Waerden, Algebra, 8th edition, Springer-Verlag, 1971.

Reed College, Portland, OR 97202

E-mail address: jpb@@reed.edu

Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada

   E-mail address: reichst@@math.ubc.ca