Every power of x that draws a hyperoval

The curve that no three points in line define asked how large a set of points in a finite plane can be with no three on a line, and found a split by parity. In a plane of odd order the largest such sets have one more point than the order and every one of them is a conic — Segre’s theorem. In a plane of even order — the order of the seven-point plane is the first — they can have two more, and they stop being forced: these hyperovals include a conic with one extra point, and in planes of order sixteen and beyond they include sets that are the zeros of no quadratic at all.

It ended on the sharpest special case of that freedom. Take the plane over the field of order $q = 2^h$, and the $q$ points $(x, x^k)$, one for each field element $x$. Add the two points at infinity in the vertical and horizontal directions. For which exponents $k$ is the result a hyperoval? It checked the orders up to nine. This essay carries the search to order $4096$ and sorts what it finds.

The table’s middle column is the count of exponents that work, and its right-hand chips are the classes they fall into. In orders sixteen, sixty-four, two hundred and fifty-six and so on — the even powers of two in the exponent — the count is always small and the classes are always the conic and at most one more. In the odd powers the count jumps: eleven exponents at thirty-two, twenty-three at one hundred and twenty-eight, forty-five at two thousand and forty-eight. Every class in every row belongs to a family someone had already found.

A test that costs one pass over the field #

Testing whether $q + 2$ points have no three in line looks like a search over triples, about $q^3/6$ of them — for order $4096$, eleven billion per exponent. The structure of the curve cuts it to a single pass of $q$ steps, and the reduction is worth following, because it is where the characteristic two does its work.

First, the points at infinity. Every vertical line holds exactly one point $(c, c^k)$ and the vertical point at infinity, which is two, so vertical lines are never a problem. Every horizontal line $y = b$ holds the horizontal point at infinity, so it may hold at most one affine point: $x^k = b$ may have at most one solution, which means $x \mapsto x^k$ is a permutation of the field. For a power map that is the condition that $k$ shares no factor with $q - 1$. The line at infinity holds the two points at infinity and nothing else.

Next, lines through the origin, which is on the curve. The line $y = m x$ meets $(x, x^k)$ with $x \neq 0$ exactly where $x^{k-1} = m$, and at most one such $x$ is allowed: so $k - 1$ must also share no factor with $q - 1$.

Last, lines through a general point $(s, s^k)$ of the curve. In characteristic two, subtraction is addition, and the slope from $(s, s^k)$ to $(s + x, (s + x)^k)$ is $((s + x)^k + s^k)/x$. No three points in line means no two of these slopes are equal. For a power map, factoring out $s^k$ gives

$$\frac{(s + x)^k + s^k}{x} = s^{k-1} \cdot \frac{(1 + x/s)^k + 1}{x/s},$$

so the slopes from $s$ are the slopes from $1$, rescaled and relabelled. One base point stands for all of them. The whole test is: $k$ and $k - 1$ prime to $q - 1$, and the $q - 1$ values $((x + 1)^k + 1)/x$ all different. That is one pass through the field for each exponent, and the census to $4096$ takes a moment.

Six ways to write the same curve #

The raw count overstates how many different curves there are, because each hyperoval can be written as the graph of a power map in several ways.

The curve consists of the points $(1 : x : x^k)$ in homogeneous coordinates, together with $(0 : 1 : 0)$ and $(0 : 0 : 1)$. Permuting the three coordinates is a symmetry of the plane, and it carries the curve to another curve of the same kind. Swapping the second and third coordinates gives the points $(1 : x^k : x)$, which is the graph of the inverse power, $x^{1/k}$ — the reflection the slope of the mirror image made in the real plane, now read modulo $q - 1$. Swapping the first two gives $(x : 1 : x^k)$, which after dividing by $x$ and renaming $1/x$ is the graph of $x^{1-k}$.

Those two substitutions generate a group of six, the six permutations of three coordinates, and it acts on exponents modulo $q - 1$:

$$k, \quad \frac1k, \quad 1 - k, \quad \frac{1}{1-k}, \quad \frac{k}{k-1}, \quad \frac{k-1}{k}.$$

Two exponents in the same orbit draw the same curve in different coordinates. The census groups every exponent that works into its orbit, and checks along the way that every member of the orbit works too — a consistency test on the search itself, since an orbit containing a failure would mean either the substitutions or the test was wrong.

The classes in order thirty-two #

In the plane of order thirty-two the eleven exponents fall into three classes. The conic, $x^2$, has only three members because one substitution fixes it: $k \mapsto k/(k - 1)$ sends $2$ to $2$. The second class contains $x^4$, a translation hyperoval: for $k = 2^i$ the power map is additive in characteristic two, $(x + y)^{2^i} = x^{2^i} + y^{2^i}$, the difference quotient loses its dependence on the base point entirely, and the test reduces to $i$ sharing no factor with $h$. The third is Segre’s $x^6$, which he showed in 1962 is a hyperoval whenever $h$ is odd, and which has an orbit of two because a substitution of order three fixes it.

Glynn’s two formulas, from 1983, also produce exponents here — and both land in the translation class. At thirty-two the families are not yet separate. That is the first instance of a phenomenon the whole table shows: the named families coincide in small orders and separate only as $h$ grows, and a census that stopped at thirty-two would have seen three hyperovals and no reason for five names.

Why a translation exponent needs i prime to h #

The translation curves are the one family whose membership can be decided in a line, and the line is Euclid’s algorithm applied to exponents.

For $k = 2^i$ the map $x \mapsto x^{2^i}$ is additive — it is the $i$-th power of the squaring map, which in characteristic two respects sums, as the field with four elements already shows in miniature. So $(x + 1)^k + 1 = x^k$, the difference quotient is simply $x^{k-1}$, and the test becomes: $x^{2^i - 1}$ must take every non-zero value once. That happens exactly when $2^i - 1$ shares no factor with $2^h - 1$.

And the common factor of $2^i - 1$ and $2^h - 1$ is $2^{d} - 1$, where $d$ is the common factor of $i$ and $h$. The reason is that dividing $2^h - 1$ by $2^i - 1$ leaves remainder $2^{h \bmod i} - 1$, so the oldest algorithm run on the numbers $2^h - 1$ and $2^i - 1$ performs the same steps as Euclid’s algorithm run on $h$ and $i$, and ends at $2^{\gcd(i, h)} - 1$. So the translation curve $x^{2^i}$ is a hyperoval exactly when $\gcd(i, h) = 1$. That is why the even rows of the table are thin: when $h$ is even, $i$ must be odd and prime to $h$, and the six substitutions identify $i$ with $h - i$, so few classes survive.

The classes in order one hundred and twenty-eight #

At order one hundred and twenty-eight the picture is richer. Two translation classes appear, from $2^2$ and $2^3$ — $h = 7$ is prime, so every $i$ from $2$ to $5$ qualifies, and $i$ and $7 - i$ give the same class. Segre’s $x^6$ now shares its class with Glynn’s second family, whose exponent $3\sigma + 4$ is $52$ with $\sigma = 16$. And Glynn’s first family, whose exponent is $\sigma + \gamma$ for $\sigma$ and $\gamma$ the powers of two with $\sigma^2 \equiv \gamma^4 \equiv 2$ in the exponent arithmetic, gives $20$: a class of only two members, $20$ and $108$, and a hyperoval that appears in no smaller plane.

The coincidences are not accidents of the search; they are arithmetic. Glynn’s exponents are built from powers of two whose exponents solve $2e \equiv 1$ and $4f \equiv 1$ modulo $h$, and for small $h$ those solutions are small enough that the resulting $k$ falls into an orbit that already has a name. As $h$ grows, the solutions spread out and the families separate — at order two thousand and forty-eight all five are distinct, alongside four translation classes, eight classes in all.

The counts are predicted by the families #

The middle column of the census is not only consistent with the named families; it is exactly what they predict, and checking the arithmetic is a second test of the search.

Each class has six members unless a substitution fixes it. The conic’s class always has three, since $k \mapsto k/(k - 1)$ fixes $2$. A translation class has six. Segre’s class has six in large orders, and Glynn’s first has two in order one hundred and twenty-eight, where a substitution of order three fixes it. In order two thousand and forty-eight, $h = 11$ is prime, every $i$ from $2$ to $9$ gives a translation curve, and pairing $i$ with $11 - i$ leaves four translation classes; with the conic, Segre’s and Glynn’s two, the total is $3 + 4 \cdot 6 + 3 \cdot 6 = 45$ — the census’s number. In order four thousand and ninety-six, $h = 12$ allows only $i = 5$ and $i = 7$, one class, and $3 + 6 = 9$.

A search that found an exponent outside the families would break that arithmetic — the count and the families could not both be right — and in every row they agree. The same bookkeeping is what made a plane in a list of numbers checkable: a structure with a symmetry group predicts its own counts, and a census that matches them has left no room for anything unaccounted.

Three hyperovals, and every line checked #

The census trusts the reduction above. The drawings do not: for each curve drawn, every line of the plane is tested directly.

The conic in the plane of order sixteen looks nothing like a parabola. The points are placed by the binary codes of their field elements, and squaring is additive in characteristic two, so the pattern is a scatter with a linear structure the eye cannot find. What the figure establishes is the count: all $273$ lines were tested, $153$ meet the curve twice, $120$ miss it, and none touches it once. For a set of $q + 2$ points with no three in line those numbers are forced — every pair of the $18$ points spans its own line, $18 \cdot 17 / 2 = 153$, and the other $q(q-1)/2 = 120$ lines miss — and a hyperoval has no tangents at all, which is the even-order phenomenon that the nucleus explained in the curve that no three points in line define.

Segre’s curve in the plane of order thirty-two passes the same test: $1{,}057$ lines, $561$ secants, $496$ lines that miss. It is not a conic in any coordinates — it is in its own class — and it is still a set that no line meets three times.

Glynn’s $x^{20}$ in the plane of order one hundred and twenty-eight is the most striking of the three, because it is the smallest instance of its family: $130$ points among $16{,}384$, placed so that each of $16{,}513$ lines meets them twice or not at all. Nothing in the drawing hints at the property. The structure is entirely in the arithmetic, and the only way to see it in a picture is to test the lines, which is what the figure did.

A conjecture checked where it can be #

The census is the experimental side of a conjecture. David Glynn and others conjectured in the 1980s that the monomial hyperovals are exactly the ones in the table’s families: the conic, the translation curves $x^{2^i}$ with $i$ prime to $h$, Segre’s $x^6$ for odd $h$, and Glynn’s two families for odd $h$ — no others, in any order.

In every order from four to four thousand and ninety-six the census agrees. Every exponent that works lies in a class containing a named exponent, and the figure refuses to draw if any does not. That is evidence of the usual computational kind: complete for the orders searched and silent beyond them. It has been pushed much further by others, and partial proofs exist — for exponents that are small compared with the order of the plane, the conjecture has been proved by methods from algebraic geometry that count points on curves over finite fields. The full statement is not proved.

The monomials are also only the simplest case. Hyperovals given by polynomials that are not single powers exist — found by Payne in 1985, Cherowitzo in 1988, and the Subiaco and Adelaide families in 1996 and 2003 — and the first hyperoval that is not a conic at all, in the plane of order sixteen, was found by Lunelli and Sce in 1958 by one of the earliest computer searches in geometry. A census of monomials sees none of them.

The smallest hyperovals build a famous object #

The hyperovals of the smallest even plane, of order four, have a life far outside this question.

That plane has $21$ points and its hyperovals have six points each; there are $168$ of them, and they fall into three classes of $56$ under the plane’s symmetries that preserve its arithmetic. Add three new points to the plane’s twenty-one, one for each class, and form sets of eight: each line with all three new points, each hyperoval with two of them and each seven-point subplane with one, the choice made by the class it belongs to, and each pair of lines with its intersection removed. There are $759$ such sets, and every five of the twenty-four points lie in exactly one of them. That is the Steiner system discovered by Ernst Witt, whose symmetry group is the Mathieu group $M_{24}$ and whose sets of eight are the codewords of weight eight in the binary Golay code — the code whose perfection the best a code can be turns on.

So the same condition — no three in a line — that this essay tests exponent by exponent in large planes is, in the plane of order four, one of the ingredients of the most exceptional finite object in combinatorics. The hyperovals there are not a curiosity about power maps; they are the extra structure that makes twenty-four points behave like nothing else.

What exhaustion in these planes does not reach #

The census covers one family of candidates. It tests every exponent, so every monomial hyperoval in these planes is found; it says nothing about hyperovals given by other polynomials, which exist from order sixteen on and are not drawn.

The equivalence is by coordinate permutations only. Two exponents in different classes could in principle give hyperovals that are equivalent under some other symmetry of the plane. For the monomials this does not happen in any known case, and the classes shown are the standard ones, but the figure does not test every symmetry of each plane.

The pictures carry no geometry. A hyperoval drawn on the grid of binary codes is a scatter; the property that defines it is certified by testing all the lines, which the figures do, and cannot be seen.

Still open: whether the list is complete #

Is every monomial hyperoval in a plane of order $2^h$ one of the conic, the translation curves, Segre’s curve and Glynn’s two? The census confirms it to order $4096$ and beyond it the evidence is computational and the partial proofs cover only small exponents.

Behind it stands the question the curve that no three points in line define left: a classification of all hyperovals, monomial or not. Complete lists exist for the planes of order up to sixty-four, each obtained by a search harder than the last, and no general pattern is known. In odd order Segre’s theorem ends the story in one line; in even order the story has been growing new families for sixty years.

A search that confirms a list #

The habit worth keeping is how the search was made small enough to be complete.

A property of sets — no three points in line — became, for a power map, three conditions on one pass through the field, because the curve’s equation is homogeneous and because in characteristic two the difference of two powers is their sum. Then six coordinate permutations collapsed hundreds of exponents into a handful of classes. Symmetry turned an unmanageable search into a short table, and the short table could be compared, class by class, with a list of families assembled over forty years by hand.

That comparison is what a census is for. It does not prove the list complete. It measures how far the list has been confirmed, and in the orders it reaches it leaves no gap for a missing family to hide in.