Fermat’s Ideal Can Be Generated by the First Three Fermat Polynomials

Bruno Buchberger RISC-LINZ —

Research Institute for Symbolic Computation Johannes Kepler University, A4040 Linz, Austria (Europe) Tel: +43 (7236) 3231-41, Fax: +43 (7236) 3338-30

                         Bitnet: k313370 at aearn

—

October 22, 1993

Abstract

We show that the Fermat polynomials F_{n} := X^{n} + Y^{n} − Z^{n} satisfy the identity F_{n+3} = −(S_{0}F_{n} + S_{1}F_{n+1} + S_{2}F_{n+2}), for all n, where the S_{i} are the elementary symmetric polynomials in three variables. A similar relation holds for the “generalized” Fermat polynomials F_{m,n} := X_{1}^{n} + … X_{m−1}^{n} − X_{m}^{n}. The proof of these identities is elementary. The main emphasis of the paper is on explaining a new method, based on the author’s Gröbner bases technique, by which such identities can be generated.

1 The Result

Let F_{n} = X^{n} + Y^{n} − Z^{n} for all n ≥ 1 and let

S_{0} = −XY Z,
S_{1} = XY + XZ + Y Z,
S_{2} = −(X + Y + Z).

We show that, for all n ≥ 1,

F_{n+3} = −(S_{0} · F_{n} + S_{1} · F_{n+1} + S_{2} · F_{n+2}),  (1)

or, with the convention S_{3} = 1,

S_{0} · F_{n} + S_{1} · F_{n+1} + S_{2} · F_{n+2} + S_{3} · F_{n+3} = 0  (2)

This result has some interesting consequences:

• It shows that the “Fermat ideal”, i.e. the ideal generated by all F_{n}(n ≥ 3) can be already generated by F_{3}, F_{4}, F_{5}. This follows from the above relation by inductively concluding that F_{6} ∈ Ideal(F_{3}, F_{4}, F_{5}), that F_{7} ∈ Ideal(F_{4}, F_{5}, F_{6}) and hence F_{7} ∈ Ideal(F_{3}, F_{4}, F_{5}), and so on.

• It is furthermore interesting that the multipliers S_{i} needed in the representation of F_{n+3} in terms of F_{n}, F_{n+1}, F_{n+2} are polynomials with integer coefficients.

• Also, one can see that these multipliers do not depend on n.

• The fact that the multipliers S_{i} are so simple, namely the elementary symmetric polynomials over X, Y, Z, may give some hope to draw conclusions for the solution of Fermat’s problem.

2 Proof

Once the relation (1) is conjectured, the proof is very easy. Just expand the right-hand side of the equation (for indeterminate n) and verify that the result is equal to F_{n+3}.

(If you are lazy you may want to use a symbolic math software system like Mathematica for this easy formula manipulation.)

3 Heuristics How I Was Lead to Conjecture the Result

The interesting methodological problem was how to get to a conjecture of the above kind. Essentially, I used my Gröbner basis technique (see (Buchberger 1985)) for deriving identity (1). In this section I assume that the reader is familiar with this technique.

First, we constructed a Gröbner basis G_{n} for F_{n}, F_{n+1}, F_{n+2} and showed that F_{n+3} reduces to zero w.r.t. G_{n}. For obtaining S_{1}, S_{2}, S_{3} one only has to “collect the multiples of F_{n}, F_{n+1}, F_{n+2}” that occur in the construction of the Gröbner basis and in the reduction of F_{n+3}. For n ≥ 4 we did the “calculation” with indeterminate n. In fact it turns out that for n ≥ 4 it is sufficient to construct the first two polynomials of G_{n}. In the case n = 3 one has to construct the first three polynomials of G_{n}.

(In fact, what I really did was to compute the Gröbner bases for n = 3, 4, 5, 10 with my own Mathematica implementation that allows easy access to all intermediate steps for research purposes. Then I saw a common pattern in the calculations and subsequently came up with the derivation below for indeterminate n, which is valid for the case n ≥ 4. From the general case with indeterminate n one can immediately conjecture identity (1) — even for arbitrary n ≥ 1 — and then, of course, one can forget about the derivation by the Gröbner basis method.)

We document the steps of this derivation by the Gröbner bases method:

Reduction of the S-Polynomial of F_{n} and F_{n+1} yields

K_{n,4} = X · F_{n} − F_{n+1}.

Reduction of the S-Polynomial of F_{n} and F_{n+2} yields

K_{n,5} = X^{2} · F_{n} − F_{n+2}
− X · K_{n,4}
− Y · K_{n,4}.

Reduction of F_{n+3} using F_{n}, F_{n+1}, F_{n+2}, K_{n,4}, K_{n,5} yields

F_{n+3} − X^{3} · F_{n}
+ X^{2} · K_{n,4}
+ XY · K_{n,4}
+ X · K_{n,5}
+ Y^{2} · K_{n,4}

+ Y · K_{n,5}
+ Z · K_{n,5}
= 0.

¿From the above reductions one obtains the following relations:

K_{n,4} = X · F_{n} − F_{n+1} + 0 · F_{n+2},
K_{n,5} = −XY · F_{n} + (X + Y) · F_{n+1} − F_{n+2},
F_{n+3} = −(S_{0} · F_{n} + S_{1} · F_{n+1} + S_{2} · F_{n+2}),

where

S_{0} = −XY Z,
S_{1} = XY + XZ + Y Z,
S_{2} = −(X + Y + Z).

Note that S_{0}, S_{1} and S_{2} do not depend on n.

4 A Generalization

¿From (1) one may conjecture that a similar relation holds also in the case of more than three variables. In fact, after some experimentation with symmetric polynomials and Fermat polyonomials (for example, using a symbolic math software system like Mathematica) one is lead to conjecture that for m variables one has the following identity:

F_{m,n+m} = −(S_{m,0} · F_{m,n} + S_{m,1} · F_{m,n+1} + … + S_{m,m−1} · F_{m,n+m−1})

where

F_{m,n} = X_{1}^{n} + … + X_{m−1}^{n} − X_{m}^{n}

and S_{m,k} are the elementary symmetric polynomials in m variables, i.e.

S_{m,0} = (−1)^{m}(X_{1}X_{2} … X_{m}),
S_{m,1} = (−1)^{m−1}(X_{1}X_{2} … X_{m−1} + X_{1}X_{2} … X_{m−2}X_{m} +
+ … + X_{2}X_{3} … X_{m}),
⋮
S_{m,m−2} = X_{1}X_{2} + X_{1}X_{3} + … + X_{m−1}X_{m},
S_{m,m−1} = −(X_{1} + X_{2} + … + X_{m}).

This can be shown by elementary induction on m. We only indicate the main steps and leave the elementary intermediate calculations to the reader. With the additional convention S_{m,m} = 1 the general formula can be written in the following compact form:

m ; ∑ ; k=0 S_{m,k} · F_{m,n+k} = 0 (for all m ≥ 1, n ≥ 1).  (3)

First, we remark that the symmetric polynomials S_{m,k} can be generated by the following recursion:

S_{0,0} = 1 ,

and for m ≥ 1 :

S_{m,0} = −S_{m−1,0} · X_{m} (= (−1)^{m} m ; ∏ ; k=1 X_{k}),  (4)
S_{m,k} = S_{m−1,k−1} − S_{m−1,k} · X_{m}, 1 ≤ k ≤ m − 1,
S_{m,m} = 1.

For the F_{m,n} we have the following obvious recursive relation:

F_{m,n} = F_{m−1,n} + 2X_{m−1}^{n} − X_{m}^{n} (for all m ≥ 2, n ≥ 1).  (5)

Furthermore, the following relation holds:

m ; ∑ ; k=0 S_{m,k} · X_{j}^{n+k} = 0 (for all m ≥ 1, n ≥ 1, 1 ≤ j ≤ m). (6)

It suffices to prove (6) for j = m because for arbitrary j we can use the symmetry of the S_{m,k}. We can extract X_{m}^{n} from the sum and, hence, it suffices to prove, for arbitrary m ≥ 1,

m ; ∑ ; k=0 S_{m,k} · X_{m}^{k} = 0.

However, this can easily be established by using the recursion (4) for the S_{m,k}. For m = 1 formula (3) can be easily checked. Let m ≥ 2 arbitrary but fixed and assume now that

m−1 ; ∑ ; k=0 S_{m−1,k} · F_{m−1,n+k} = 0 (for all n).  (7)

4 A GENERALIZATION 6

We have to show that

m ; ∑ ; k=0 S_{m,k} · F_{m,n+k} = 0 (for all n).  (8)

Let n be arbitrary but fixed. The sum (8) can be decomposed into

S_{m,0} · F_{m,n} + m−1 ; ∑ ; k=1 S_{m,k} · F_{m,n+k} + F_{m,n+m}  (9)

and S_{m,k} and F_{m,n+k} can be represented in terms of the S_{m−1,...} and F_{m−1,...} using the above recursion formulae (4) and (5). This yields

S_{m,0} · F_{m,n}+

+ m−1 ; ∑ ; k=1(S_{m−1,k−1} − S_{m−1,k} · X_{m}) · (F_{m−1,n+k} + 2X_{m−1}^{n+k} − X_{m}^{n+k})+

+ F_{m,n+m}.  (10)

Now,

m−1 ; ∑ ; k=1 S_{m−1,k−1} · F_{m−1,n+k} =

\underbrace{m−1 ; ∑ ; k=0 S_{m−1,k} · F_{m−1,(n+1)+k}}_{= 0_{by induction hypothesis (7)}} − \underbrace{S_{m−1,m−1}}_{1} ·F_{m−1,n+m} ,

and

− m−1 ; ∑ ; k=1 S_{m−1,k} · F_{m−1,n+k} =

\underbrace{− m−1 ; ∑ ; k=0 S_{m−1,k} · F_{m−1,n+k}}_{= 0_{by induction hypothesis (7)}} +S_{m−1,0} · F_{m−1,n} ,

Hence, (10) becomes

S_{m,0} · F_{m,n} − F_{m−1,n+m} + S_{m−1,0} · X_{m} · F_{m−1,n} +

+ m−1 ; ∑ ; k=1(2S_{m,k} · X_{m−1}^{n+k} − S_{m,k} · X_{m}^{n+k}) + F_{m,n+m} =
S_{m,0}[F_{m,n} − F_{m−1,n} − 2X_{m−1}^{n} + X_{m}^{n}] +
+[F_{m,n+m} − F_{m−1,n+m} − 2X_{m−1}^{n+m} + X_{m}^{n+m}] +
+2S_{m,0} · X_{m−1}^{n} − S_{m,0} · X_{m}^{n} + 2X_{m−1}^{n+m} − X_{m}^{n+m} +
+ m−1 ; ∑ ; k=1(2S_{m,k} · X_{m−1}^{n+k} − S_{m,k} · X_{m}^{n+k}) =
2 m ; ∑ ; k=0(S_{m,k} · X_{m−1}^{n+k}) − m ; ∑ ; k=0(S_{m,k} · X_{m}^{n+k}) = 0  (11)

because the terms in the brackets vanish by the recursive relation (5). However, the two sums in the last expression are zero by the relation (6). Hence, the sum (11) is zero, q.e.d.

An alternative proof of our main formula (3) can also be given by using generating functions.

It is interesting to note that, in fact, the Fermat polynomials F_{m,k} satisfy exactly the same identity as the “exponential polynomials”

E_{m,n} := X_{1}^{n} + ... + X_{m}^{n}.

The identity

m ; ∑ ; k=0 S_{m,k} · E_{m,n+k} = 0 (for all m ≥ 1, n ≥ 1)

is a well known classical identity in the theory of symmetric polynomials. It seems to have gone unnoticed that the same identity holds also for the (non-symmetric) Fermat polynomials.

It would be interesting to study the class of all polynomials that satisfy the above identity. This might be possible also by means of the Gröbner bases method but we have not yet undertaken this study.

5 Conclusion

Our main identity (3) for (generalized) Fermat polynomials seems to be a nice addition to well known identities for symmetric polynomials and similar objects. In the special case m = 3 our identity might give some information about Fermat’s problem.

The main point of the paper, however, is the demonstration of a method based on our Gröbner bases technique for finding new identities in this area. This method may well be applicable to a broad class of problems.

6 References

The motivation for dealing with the above problem came from reading (Elias 1990), where it is shown that Ideal(F_{3}, F_{4}, F_{5}) = Ideal({F_{n} | n ≥ 3}). However, in (Elias 1990) the explicit identity (1) is not obtained and, also, there is no indication that the representation of F_{n} w.r.t. F_{3}, F_{4}, F_{5} can be achieved with integer polynomials. The argument there is based on a computation of the Hilbert function of Ideal(F_{2}, F_{3}, F_{4}) and other ideals by means of the computer algebra software system Macaulay. (Elias 90) does not seem to be aware of the fact that Hilbert functions, in Macaulay, are computed by first computing Gröbner bases of these ideals and then using the known (Buchberger 65) formulae for Hilbert functions of Gröbner bases. Of course, it is much easier to work directly with the Gröbner bases in the way shown in this paper and, also, one can draw much more information from the derivation presented in this paper.

B. Buchberger (1965), An Algorithm for Finding a Basis for the Residue Class Ring for a Zero-Dimensional Polynomial Ideal. Ph.D. Thesis, Math. Inst., Univ. of Innsbruck, Austria, 1965.

B. Buchberger (1985), Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory. Chapter 6, pp. 184-232 in: N.K. Bose: Multidimensional Systems Theory, D. Reidel Publishing Company.

J. Elias (1990), On Fermat’s Ideal, Manuscript, Dept. Algebra i Ge-

6 REFERENCES 9

ometria, Universitad de Barcelona.

Acknowledgement: I would like to thank my student W. Windsteiger for his help in preparing the manuscript.