The field with one element

Two weeks ago I was at the British Combinatorial Conference in Exeter. It was smaller than many recent BCCs, but a really good conference: the invited talks were uniformly excellent. I want to focus here on one talk, that of Koen Thas. He covered a lot of ground, mentioning for example the conjecture that finite projective planes necessarily have prime power order, and the conjecture (due to Jacques Tits, on which I inadvertently made a contribution) that there is no generalised quadrangle with a finite number (greater than 2) of points on a line and an infinite number of lines through a point. (I settled the first case, where there are three points on a line; the case of four points on a line was done by Kantor and independently Brouwer, and five points on a line by Cherlin, and that is the limit of our knowledge.)

I will focus even more narrowly, on the last part of his talk, and the last of seventeen sections in his paper, concerning “the field with one element”.

Some explanation for non-mathematicians is in order. A field is an algebraic system in which addition and multiplication are defined, and “the usual rules apply”: addition and multiplication are commutative and associative, there are identity elements and inverses for both operations, and the distributive law (a.k.a. expanding brackets) holds. In a field, we can’t divide by zero. An absolutely standard part of the definition is that the additive identity element 0 and the multiplicative identity 1 are unequal: 0≠1. So, by definition, there is no “field with one element”: every field has at least two elements. Thus, the field with one element is essentially a poetic concept (I am not sure which figure of speech best describes it). But, undaunted, I will try to explain.

A tale of three qs

The Gaussian, or q-binomial, coefficient, which I will write here as Gauss(n,k)_q, is given by the formula

(qⁿ−1)(q^n-1−1)…(q^n-k+1−1)/(q^k−1)(q^k-1−1)…(q−1).

Despite appearances, it is a polynomial in q, of degree k(n−k). This can be seen by showing, from the definition, that the Gaussian coefficients can also be specified by Gauss(n,0)_q = Gauss(n,n)_q = 1 and the “Pascal-like” recurrence

Gauss(n,k)_q = Gauss(n−1,k−1)_q+q^kGauss(n−1,k)_q.

For example,

Gauss(4,2)_q = q⁴+q³+2q²+q+1.

A simple property is that, if we substitute q=1 in the Gaussian coefficient Gauss(n,k)_q, we obtain the corresponding binomial coefficient Bin(n,k). The easiest way to see this is from the recurrence; alternatively, use the fact that the limit of (qⁿ−1)/(q^k−1) as q→1 is n/k (either by l’Hôpital’s rule, or by simply dividing top and bottom by q−1).

Fixed sets for powers of a cycle

So are the Gaussian coefficients nothing more than polynomials which happen to take interesting values when q=1? To see that this is not so, turn to another of the invited speakers at the BCC, Bruce Sagan, who talked about a recent discovery which has produced a lot of activity, the cyclic sieving phenomenon. Incidentally, Bruce used remarkably well the opportunity given by the publication of the main speakers’ talks in advance: his talk was slow and beautifully clear, while his paper is densely packed with interesting mathematics.

The binomial coefficient Bin(n,k) counts the k-element subsets of an n-element set. Now suppose we have a cyclic permutation σ of the set, and we wish to count its orbits on k-subsets. By the Orbit-counting Lemma, we have to count the subsets fixed by any power of σ. Now it turns out that the number of sets fixed by a power of σ of order d is the result of substituting a primitive dth root of unity for q in Gauss(n,k)_q.

This fact is only the tip of a very large iceberg, for which see Bruce’s paper. But I want to speak of two other, completely different, occurrences of the Gaussian coefficients, discovered much earlier. In both cases, the letter q is traditionally used: is this just coincidence? (A question for a historian, maybe.)

Finite vector spaces

A finite field necessarily has a prime power number of elements; Galois showed that for any prime power q there is a unique field with q elements, up to isomorphism. This is now called a Galois field, and denoted by GF(q), or F_q.

Now let V be an n-dimensional vector space over GF(q). Then V can be identified with the set of all n-tuples of coordinates (relative to a basis), so |V|=qⁿ.

The number of k-dimensional subspaces of V is the Gaussian coefficient Gauss(n,k)_q. The standard proof of this fact involves noticing that the number of linearly independent k-tuples of vectors in V is (qⁿ−1)(qⁿ−q)…(qⁿ−q^k-1), while each k-dimensional subspace contains (q^k−1)(q^k−q)…(q^k−q^k-1) such tuples; dividing these numbers gives the Gaussian coefficient.

There is an alternative counting proof. Take V=Fⁿ, where F=GF(q), the space of all n-tuples. Now every k-dimensional subspace has a unique basis consisting of k vectors in reduced echelon form with no zero vectors: this means that, if the vectors are the rows of a k×n matrix, then

• the first non-zero entry in each row is a 1;
• these “leading 1s” occur further to the right as we go down the matrix;
• all other entries in the column of a “leading 1” are zero.

Now it is easy to verify the Pascal-like recurrence for the number of matrices in reduced echelon form: the two terms on the right correspond to matrices where the leading 1 in the last row is in the last position (so deleting the last row and column gives a reduced echelon matrix) or in an earlier position (so the last column is arbitrary, and deleting it gives a reduced echelon matrix).

Indeed the definition of “reduced echelon form” makes sense over any alphabet containing elements called 0 and 1; and the argument shows that the number of k×n matrices in reduced echelon form is the Gaussian coefficient, where q is the alphabet size (not necessarily a prime power).

Area under lattice paths

Consider lattice points (with integer coordinates) in the plane. You are standing at the origin, and have to move to the point (n−k,k); you are allowed to step from any point to its neighbour to the right or above.

Clearly you must take n steps, of which k should be vertical. The vertical steps can be chosen anywhere in the sequence of moves. So the number of possible walks is Bin(n,k).

Now suppose that we are interested in the area under such a path. This can take any value between 0 (for the path that takes all the horizontal steps first) to k(n−k) (for the path that takes the vertical steps first). A solution to this problem could be a generating function, a polynomial in an indeterminate q where the coefficient of q^m is the number of paths with area m.

It turns out that this generating function is Gauss(n,k)_q. This can be seen most easily from the recurrence relation. The first term accounts for paths with the last step vertical (this step adds nothing to the area); the second counts paths with the last step horizontal (the last step adds k to the area, so multiplies the generating function by q^k.

Remarkably, we have seen three occurrences of the Gaussian coefficient: in the first, q is typically a root of unity; in the second, a prime power; and in the third, an indeterminate.

Geometry over the one-element field, 1

In 1957, Jacques Tits suggested an analogy between the combinatorics of sets and subsets and the geometry of vector spaces and subspaces: roughly speaking, the combinatorics was the case q=1 of the geometry, where q is the order of the field.

The (n−1)-dimensional projective space over a field F is the geometry whose points, lines, planes, … are the subspaces of dimension 1, 2, 3, … of an n-dimensional vector space over F. (Caution: dimension shift!)

Axiomatically, the geometries are very similar. According to the Veblen–Young axioms, the projective space is characterised by the properties

• Two points lie on a unique line.
• If a line meets two sides of a triangle, not at their intersection, then it also meets the third.
• A subspace is a set of points containing the line through any two of its points.

We have to make some low-dimensional exceptions: a 1-dimensional projective space (according to these axioms) is just an arbitrary set of points forming a line, with no algebraic structure; and there are non-Desarguesian projective planes which are not obtained from vector spaces. But the correspondence is exact for higher dimensions, assuming that any line has at least three points. (If the lines are finite, then the number of points on a line is q+1, where q is the size of the coordinatising field.)

By contrast, if every line has just two points, then an arbitrary set trivially satisfies the axioms, with the lines being all the 2-element subsets and the subspaces arbitrary subsets.

Thus, the subsets of an arbitrary set “are” the projective spaces over the “field with one element”.

What is an affine space? The number qⁿ of points in an n-dimensional affine space reduces to 1 when q=1; so the affine space is a single point; but it has n ghostly directions through the point (lines with only one point). Recall that we obtain a projective space from an affine space by adding a point at infinity on each parallel class of lines; thus to get from the n-dimensional affine space to the projective space, we add n points, obtaining n+1 altogether, in agreement with our previous description.

If this analogy is to be fruitful, it should suggest new insights; and indeed this one does. The “general linear group” in n dimensions over the field of one element is the symmetric group S_n; this reflects the BN-pair structure of the general linear group. Indeed, this extends to the other groups of Lie type: the group over the field of one element is the Weyl group of the BN-pair.

There is interesting combinatorics too. In fact, one of my earliest papers exploited this analogy. A theorem of Fisher (for t=1), Petrenjuk (for t=2), and Ray-Chaudhuri and Wilson (in general) says that a 2t-design on v points with block size at most v−t has at least Bin(v,t) blocks. (Such a design is a collection of k-subsets, with 2t≤k≤v−t, such that any 2t-set is contained in a constant number of these sets.) I extended the result by replacing “set” and “subset” by “vector space over finite field” and “subspace”; the binomial lower bound is replaced by Gauss(v,t)_q, where q is the field order. This result was almost immediately superseded by the much more general results of Philippe Delsarte.

Several similar results exist. Probably the most famous is the vector space Ramsey theorem of Graham, Leeb and Rothschild, an exact translation of the classical Ramsey theorem.

Geometry over the field of one element, 2

In recent years, this enterprise has become much more serious. In 2009, Javier Lopez talked about this in our Pure Mathematics seminar: I wish I had got more out of it than I did. (The abstract is here.)

Enough to say that, if a geometer wants to make sense of the field with one element, it is necessary to be able to define varieties, schemes, etc. over it. For some particular varieties, we know how to proceed: we have already dealt with projective and affine spaces over the 1-element field, and for algebraic groups we just get the Weyl group. The situation for other varieties is more complicated. Soulé proposed a definition, which led to some results disagreeing with the naive interpretation. A revised version due to Connes and Consani seems to have fared better.

Manin took things even further, proposing a particularly simple form for the zeta function of a variety over the 1-element field F₁. (This presupposes that we have a notion of an extension of degree n of F₁; even though this is another 1-element field, it is not the same as F₁ itself!) Soulé proposed a zeta-function associated with any suitable counting function: for the Gaussian coefficient, the result is in agreement with Manin’s suggestion.

So what is the one-element field?

It seems that the 1-element field should have multiplication but not addition. But addition has been restored with the concept of a hyperfield.

An abelian hypergroup is a set H with a “hyperoperation” +: this means that u+v is a non-empty subset, rather than an element, of H, and an appropriate collection of axioms is satisfied. A typical hypergroup is the set of orbits of an automorphism group of an abelian group, the hyperoperation giving the set of all orbits hit by sums of elements in the chosen orbits. Now a hyperfield is a set with operations of addition and multiplication, so that addition is a hypergroup, multiplication is a group on the non-zero elements, and the distributive laws hold.

The Krasner hyperfield has elements 0 and 1: hyperaddition is given by 1+1 = {0,1} (all other instances follow from the axioms), and multiplication is obvious. This is the algebraic object which might play the role of the 1-element field.

There is more to the story: the adèle ring of a global field modulo multiplication by non-zero field elements forms a hyperfield which is an extension of the Krasner hyperfield.

Moreover, one can do geometry over the Krasner hyperfield, in a way which seems more satisfying than the hints and guesses we have had hitherto. Connes and Consani show that finite commutative hyperfield extensions of the Krasner hyperfield corresond to “incidence groups” of finite projective spaces, together with some low-dimensional extensions (including projective planes with sharply point-transitive groups, a notorious problem).

Clearly a very productive analogy, when we have made sense of it! See Thas’ paper for more insights.