Balanced Incomplete Block Designs

Posted on by John

Suppose you have n different fertilizers you want to test. The simplest experiment would be to take a big plot of land, divide it into n sections, and apply each fertilizer to a section. That’s fine if you have one big enough plot of land, and the land itself doesn’t matter.

If the fertilizer supplies a nutrient that is already abundant in a particular soil, you won’t see as much benefit from that fertilizer on that soil. Plots of land will vary in other ways besides soil composition—some may receive more sun than others, some may have better drainage, etc.—that may interact with the effect of the fertilizer. So you’d like to test your fertilizers on several different plots of land. Call the number of plots b.

Suppose each of your plots is large enough to test q < n fertilizers, i.e. the plots are not large enough to test every fertilizer on every plot. You would like to design your experiment so that each fertilizer is tested the same number of times, and so that every pair of fertilizers is tested somewhere on the same plot of land for a direct comparison.

The resulting experimental design is called a balanced incomplete block design or BIBD. The blocks are the plots of land. The design is incomplete because you cannot test everything on every plot. The design is balanced because every pair of fertilizers is tested together the same number of times. BIBDs are important in the design of experiments.

A BIBD is a special case of the combinatorial designs discussed in the previous post with parameters (n, q, 2, λ), i.e. the parameter r is set to 2 because you want every pair to appear in some number of blocks.

A design with parameters (n, q, r, λ) is sometimes called an r-(n, q, λ) design [1]. Steiner systems correspond to λ = 1 and BIBDs correspond to r = 2.

While the number of blocks b is of interest, it is not an independent parameter. For combinatorial designs in general the number of blocks is determined by the other parameters:

b = \lambda \frac{\binom{n}{r}}{\binom{q}{r}}

Similarly, you may see the number of blocks each treatment appears in given as a parameter, but this count is also determined by the other parameters, namely

\lambda \frac{\binom{n-1}{r-1}}{\binom{q-1}{r-1}}

Examples

Here is a design to test n = 6 treatments on b = 10 plots, testing q = 3 treatments on each plot, with each pair of treatments (i.e. r = 2) appearing in λ = 2 plots, i.e. a (6, 3, 2) design.

    0000011122
    1123423433
    2345554545

The way to read this is that each treatment is a number 0 through 5, and each column indicates the treatments tested in a particular block (plot).

Here is another example, an (8, 4, 3) design: n = 8 treatments, blocks of size q = 4, with each pair of treatments being tested in λ = 3 blocks.

    00000001111222
    11123342334334
    22554666455455
    34675777677766

[1] Combinatorial designs are sometimes called t-designs, which makes sense if you denote the size of the set you’re looking for in each block by t but not if you denote it by r. You’ll see both conventions. And while we’re mentioning notational variations, the number of treatments is sometimes denoted v for variety, going back to agricultural applications, testing crop varieties.

Combinatorial designs

Posted on by John

The last several posts have been building up to this one, moving from tangible to more abstract.

The posts on finite geometry gave examples of Steiner triples and more generally Steiner systems, introduced in the previous post. Combinatorial designs take this one step further.

The previous post gave the following definition:

A Steiner triple system, written STS(n), is a collection of three-element subsets, called blocks, of a set X with n elements, such that every two-element subset of X belongs to exactly one block.

The post pointed out that the smallest projective plane is STS(7) and the smallest affine plane is STS(9).

The post then defined a general Steiner system:

A Steiner system S(t, k, n) is a collection of k-element subsets, called blocks, of a set X with n elements, such that every t-element subset of X belongs to exactly one block.

Moving from Steiner triples to Steiner systems we generalized the size of the blocks from 3 to k, and generalized the size of sets contained in a unique block from 2 to t.

Combinatorial designs take this one step further by generalizing the number of blocks that a set of t elements falls in from 1 to λ.

Unfortunately when we go from Steiner systems to combinatorial designs the notation changes and the order of the parameters changes.

A design with parameters (n, q, r, λ) is a collection of q-element subsets of an n-element set X such that every r-element subset of X is contained in exactly λ blocks.

So a Steiner system S(t, k, n) corresponds to a (n, k, t, 1) design.

Existence of designs

Given a set of parameters (n, q, r, λ) there may or may not exist a design with these parameters. It’s easy to show that a few consistency conditions are necessary. It was long conjectured that these conditions were sufficient, except possibly for a finite number of values of n. Peter Keevash proved in 2024 that the conjecture is correct.

Theorem [1]: Fix q > r ≥ 1 and λ ≥ 1. There is an N, depending on q, r, and λ, such that for every n > N with

\left. \binom{q-i}{r-i} \;\middle|\; \lambda\binom{n-i}{r-i} \right.
for all 0 ≤ i ≤ r, a design with parameters (n, q, r, λ) exists.

[1] Peter Keevash. The existence of designs. https://arxiv.org/abs/1401.3665v4

Steiner Systems

Posted on by John

Steiner triples

Several examples from the recent posts on finite geometry are special cases of Steiner triples.

A Steiner triple system, written STS(n), is a collection of three-element subsets, called blocks, of a set X with n elements, such that every two-element subset of X belongs to exactly one block.

STS(7) is the smallest finite projective plane, the Fano plane, and STS(9) is the smallest finite affine plane. In both cases you interpret the elements of S as points and the blocks as lines.

Several questions come up naturally. First, for which values of n does an STS(n) exist? A necessary and sufficient condition for existence is that n = 1 or 3 mod 6.

For a given n, can there be more than one STS(n), i.e. are there Steiner triple systems of the same size that are not isomorphic? Yes indeed. The number of non-isomorphic instances grows rapidly with n.

When does (some instance of) STS(n) correspond to a projective or affine space? When n = 2k − 1 for k ≥ 3. For n ≥ 13 there are multiple isomorphism classes of STS(n), so for k > 3 there will be an instance of STS(2k − 1) that corresponds to a projective space and other instances that do not. The instance that does correspond to a projective plane will be isomorphic to a finite field analog of the real projective plane.

Steiner systems

Steiner triple systems are a special case of Steiner systems.

A Steiner system S(t, k, n) is a collection of k-element subsets, called blocks, of a set X with n elements, such that every t-element subset of X belongs to exactly one block. Steiner triples are S(2, 3, n) systems.

Steiner systems often correspond to finite geometries with the blocks interpreted as lines. As with the special case of triples, there can be non-isomorphic instances of Steiner systems, and so when I say below that S(t, k, n) corresponds to a certain geometry, I mean that at least one instance corresponds to that geometry.

Projective

The Steiner system

S(2, q + 1, (qd + 1 − 1)/(q − 1))

with q a prime power greater than 2 is a d-dimensional projective space.

Affine

The space

S(2, q, qd)

is an affine space. Again q > 2 is a prime power.

Hyperbolic

The finite hyperbolic plane given as an example in an earlier post corresponds to S(2, 2, 6). Many other Steiner systems are hyperbolic, but I’m not aware of a tidy classification similar to the ones above.

Steiner systems outside geometry

Steiner systems were named after Swiss mathematician Jakob Steiner because he published a highly cited article asking questions about what we now call Steiner triples. His interest in these systems was combinatorial. Others developed the connections to geometry later.

Steiner systems arise in several areas of mathematics outside of geometry, including coding theory, design of experiments, and graph theory.

Finite hyperbolic planes

Posted on by John

Euclid’s fifth postulate says that given a line ℓ and a point P not on ℓ , there is a unique line through P parallel to ℓ. In the projective plane there are no parallel lines, and in the hyperbolic plane there are at least two lines through P parallel to ℓ.

Recent posts have looked at finite projective and affine planes. This post will look at finite hyperbolic planes.

Finite projective planes come up far more often in application than finite hyperbolic planes. I’ve seen several resources on finite geometries that don’t mention the hyperbolic case. Finite hyperbolic geometries have less structure than their projective or affine counterparts and so are less useful.

The definition of a finite hyperbolic plane isn’t entirely standardized. We will use the following axioms for this post.

  1. Any two distinct points lie on exactly one line.
  2. Given a line ℓ and a point P not on ℓ, there exist at least two lines through P parallel to ℓ.
  3. There exist four points, no three collinear.
  4. Every line contains at least two points.

An example of a system satisfying these axioms is the complete graph of six vertices. The nodes are the points and the edges are the lines. In set-theoretic terms, the points are the one-element subsets of {1, 2, 3, 4, 5, 6} and the lines are all possible two-element subsets.

Complete graph K6

Note that lines in the finite hyperbolic plane are two element sets. The lines {5, 6} and {1, 3}, for example, are parallel because they do not intersect, even though the representations of {5, 6} and {1, 3} in the visualization above are not parallel in the Euclidean sense.

There are many other examples of system satisfying the hyperbolic plane axioms. Too many in some sense. You could say finite hyperbolic systems are less common in application because they are more common in count.

Discrete geometry posts

Finite Affine Planes

Posted on by John

The previous post was on finite projective planes. This post will look at finite affine planes and the next will look at finite hyperbolic planes.

Affine geometry is essentially what remains of Euclidean geometry if you keep the incidence properties, e.g. wanting to know whether things intersect, and forget about metric properties such as segment lengths and angle measurements. As with projective planes, affine planes can be finite.

The axioms of an affine plane are as follows.

  1. Any two distinct points lie on exactly one line.
  2. For any line ℓ and point P not on ℓ, there is exactly one line through P that doesn’t intersect ℓ.
  3. There exist three points that are not collinear.

The second axiom says that affine geometry is Euclidean, or maybe Euclidean-lite. It lacks features of Euclidean geometry, but it doesn’t contradict Euclidean geometry.

To construct an example of a finite affine plane, let p be an odd prime and construct a p × p grid with x– and y-coordinates 0, 1, 2, …, p − 1. The affine lines are essentially the Euclidean lines that pass through the grid points, if lines can wrap around the sides, i.e. you’re working on a discrete torus. Algebraically, lines are the solutions to x = c and y = mx + b mod p.

A finite affine plane always has n² points and n² + n lines. The number n can be an odd prime, or any prime power greater than 2. It is unknown whether there are examples in which n is not a prime power. There are no affine planes of order 6 or 10, and the case of n = 12 is open.

Finite Projective Planes

Posted on by John

The idea of finite geometries sounds like an oxymoron the first time you hear of it, something like dry water or cold fire, but the axioms of some kinds of geometry can indeed be satisfied by finite models.

The axioms of projective plane geometry are as follows.

  1. Any two distinct points lie on exactly one line.
  2. Any two distinct lines meet in exactly one point.
  3. There exist four points, no three of which are collinear.

The most famous example of a finite projective plane is the Fano plane.

Fano plane illustrtation

It helps to switch back and forth between thinking of finite geometries geometrically and in terms of set theory. The fact that the Fano plane has an easy-to-understand illustration is fortunate, but not to be taken for granted. Also, it could be misleading to lean to heavily on the fact that the lines and points of finite geometry can, in this case, be represented by points and line segments (and a circle) in the Euclidean plane.

The set-theoretic perspective is that the points are the one-element sets {1}, {2}, …, {7}, and the lines are the sets listed in the legend of the graph: {1, 2, 5}, {1, 3, 7}, …, {5, 6, 7}. It’s simple to confirm that any pair of points lines in exactly one of the three-element sets, that the intersection of any pair of the three-element sets is a one-element set, and that there are three points—1, 2, 3, and 4 will do—such that no three lie on the same line, i.e. no three belong to the same three-element set.

The Fano plane is the unique projective plane with 7 points, but there are four non-equivalent projective planes with 10 points.

There are many other examples of non-isomorphic finite projective planes with the same number of points, but there are also many unsettled conjectures, at least as of an hour ago, regarding the existence of finite projective planes of various orders.

Finite geometry might seem like a technicality, spaces that satisfy the axioms but are not what anyone had in mind when the axioms were codified. So why care about finite geometries? For one thing, unexpected examples are quite valuable since they help separate the consequences of a set of axioms from common expectations.

For another, finite geometries come up in applications, such as combinatorics and cryptography. These discrete applications take advantage of intuition from traditional geometry. This intuition is an imperfect guide, so conclusions need to be verified by concrete calculations, but geometric intuition suggests what one ought to verify.

Related posts

Fraction comparison trick revisited

Posted on by John

A few years ago I wrote about a curious result: a/b is usually greater than c/d when a + d is greater than b + c. And “usually” means with probability 11/12.

As stated in the post, you can make this statement rigorous by choosing integers up to size N at random and taking the limit as N goes to infinity.

We can also choose a, b, c, and d uniformly from [0, 1]. This is similar to choosing four integers up to N and dividing all the integers by N, which doesn’t change the probabilities.

Now a/b > c/d if and only if ad > bc, so another way to state the theorem is that

Prob(ad > bc | a + d > b + c) = 11/12.

Or to state it yet another way, pick two pairs of numbers at random. The probability that the pair with the larger sum also has the larger product is 11/12. That seems more intuitive to me than the original statement.

If a + d is greater than b + c, it’s likely that a/b is greater than c/d. It seems plausible that if a + d is much greater than b + c, it’s more likely that a/b is greater than c/d. Or in terms of cross products, the more the sum of one pair is bigger than the sum of the other, the more likely the product of the former is to be greater than the latter. That is

f(r) = Prob(ad > bc | (a + d)/(b + c) ≥ r)

should be an increasing function of r. We know the probability above equals 11/12 when r = 1. We expect that the probability should approach 1 as r goes to infinity.

This is indeed the case, as shown in the plot below.

In particular, f(2) ≈ 0.99 and f(6) ≈ 0.999. So if a + d is two (or six) times bigger than b + c, there is a 0.99 (or 0.999) probability that ad is larger than bc.

You can calculate f(r) analytically or estimate it by simulation. I had Claude do both and they produce comparable results. There is a closed-form expression for f(r) but it’s really complicated.

Euclidean, Spherical, and Projective Geometry

Posted on by John

Spherical geometry is very tangible because we live on a sphere. Projective geometry seems much more exotic, and yet they’re closely related. To show how they’re connected, let’s go back to the origins of non-Euclidean geometry.

Euclidean geometry

Here are Euclid’s five postulates, statements about what geometric objects can be constructred.

  1. To draw a straight line from any point to any point.
  2. To produce (extend) a finite straight line continuously in a straight line.
  3. To describe a circle with any centre and distance (radius).
  4. That all right angles are equal to one another.
  5. That, if a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which the angles are less than two right angles.

Clearly there’s something different about the fifth postulate, the parallel postulate. It’s much longer and more complicated than the other postulates. There was speculation from ancient times that the parallel postulate might be unnecessary, that it could be derived as a theorem rather than stated as an axiom.

Non-Euclidean geometry

Giovanni Girolamo Saccheri (1667–1733) tried to prove the fifth postulate by contradiction, and in the process began the study of non-Euclidean geometry. He wasn’t the first to try to prove the fifth postulate. Ptolemy, for example, tried to prove the fifth postulate as a theorem in the second century AD. But Saccheri was the first to try a proof by contradiction, or at least the first to extensively explore contradictions to the parallel postulate.

A more modern formulation of the parallel postulate says

Given a line ℓ and a point P not on ℓ, there is exactly one line through P parallel to ℓ.

Non-Euclidean geometry replaces this axiom with an alternative, such as saying there are multiple lines parallel to ℓ or that there are no lines parallel to ℓ.

Note that non-Euclidean geometry is not an arbitrary tinkering with the axioms of geometry just to see what happens. It tinkers with one specific axiom for motivated reasons.

Spherical geometry

You can create models of non-Euclidean geometry using Euclidean geometry. For example, spherical geometry is constructed by defining a (spherical) point as a (Euclidean) point on a sphere, and defining a (spherical) line to be a great circle, the intersection of a (Euclidean) plane with the sphere. In spherical geometry there are no parallel lines: all lines intersect.

This example shows that non-Euclidean geometry need not be non-physical. If you leave general relativity out of the picture and think of physical space as undeniably Euclidean, it can still be useful to think of different geometries to describe objects in Euclidean space.

Projective geometry

In projective geometry, all distinct lines intersect at one point.

In spherical geometry, all distinct lines intersect at two points, on opposite sides of a great circle. If you consider antipodal pairs of points on a sphere to be a single point in the projective plane, now all lines intersect at a single point. Projective geometry is just one step away from spherical geometry.

The recent thread of posts started with a post a couple weeks ago about two versions of the law of cosines on a sphere, one for sides and one for angles. You can go from one to the other by going from a spherical triangle to its polar triangle. That started me going down the rabbit hole of poles and polars, first in spherical geometry, then in plane geometry, then in projective geometry, culminating here.

Now we have two ways of producing poles and polars on a sphere: the original construction in terms of spherical geometry, and the projective construction. They are consistent: you can do spherical geometry, then identify antipodal points, or you can identify antipodal points, then do projective geometry. You end up at the same place by either path.

One theme in the last few posts has been that projective geometry is not an arbitrary exercise in abstraction but a framework that can simplify how we think about things. For example, when I defined the polar triangle of a spherical triangle here, I said that the vertices of the polar triangle are the poles of the sides of the original triangle. Imagine the side as the equator of the sphere and take one of the poles; that’s where the abstract concept of “pole” comes from. But which pole do you take? There is a convention for answering this question, but in projective geometry it doesn’t matter: both (spherical) poles constitute one (projective) point.

Posts in this series

How a programming might reinvent the projective plane

Posted on by John

This post will show how a graphic programmer’s hack could lead to a rigorous definition of the projective plane.

As mentioned in the previous post, we start by adding some “points at infinity” to Euclidean plane to take care of exceptional situations. For example, instead of saying most pairs of lines intersect at a single point but some don’t intersect at all, you could say all pairs of lines intersect at a point, but for some pairs of lines, namely parallel lines, that intersection point is “at infinity.”

Suppose you need to write a program to find the intersection of two lines. The usual way of doing this would be to implement a partial function that takes two lines as input, and sometimes returns a point of intersection and sometimes does something else: it crashes, or throws an exception, or hangs. But if we add in points at infinity, our program could always return a point.

But how are you going to represent points at infinity? It’s not enough to use a floating point infinity, because different lines intersect at different points at infinity. For example, the lines y = 1 and y = 2 intersect at the point at infinity in the horizontal direction, but the lines x = 1 and x = 2 intersect at the point at infinity in the vertical direction. You could say the former lines intersect at (o, inf) and the latter at (inf, 0), but that won’t work in general.

The lines y = 3x + 1 and y = 3x + 1 intersect at the point at infinity with slope 3, but the lines y = 5x + 1 and y = 5x + 1 intersect at the point at infinity with slope 5. If you say both pairs of lines meet at (inf, inf) you’ve lost information.

So you come up with a hack. You represent points not as (x, y) pairs but as (x, y, f) where x and y are real numbers but f is a Boolean flag. Now (x, y, true) represents the ordinary point (x, y) and (x, y, false) represents the point at infinity in the direction of the line from the origin to (x, y). Problem solved!

After a while, you realize that this hack can be useful for more than just finding the intersection of lines. You discover that if you use a real number instead of a Boolean for the last coordinate, you can implement translations and rotations using matrix multiplication. So you replace true and false with 1 and 0, do your matrix calculation, then divide by the last coordinate so the result ends in 1 or 0 again. And this works really well.

This last coordinate is starting to act more like the other coordinates. You treat it as a peer when you multiply triples by a matrix, but only temporarily. You immediately normalize at the end to get back to more familiar territory.

Maybe it occurs to you after a while that you’re doing something analogous the introduction of imaginary numbers. At first the square root of −1 was seen as a hack that produced correct answers. It wasn’t really a number but something imagined to be a number as an aid to calculation. Over time mathematicians got more comfortable with these imaginary numbers and explored what would happen if they were treated as first class citizens. Maybe you should do the same with this third coordinate that started out as a hack.

This leads you to homogenous coordinates. A point in the extended plane you’ve created is represented by a triple (x, y, z) with the understanding that given a number λ ≠ 0, (x, y, z) and (λx, λy, λz) represent the same point. This is the natural extension of always dividing by the last coordinate, if it’s not zero, so that the triple always ends in 1. And you discover after a while that you need to add in the requirement that not all the coordinates can be zero at the same time.

You show this to a mathematician friend and he puts your construction in fancier language. He says you’re extended plane is ℝ³ minus the origin, modulo non-zero scalar multiplication. In other words, the points in your extended plane are equivalence classes of points in ℝ³.

Now if you think about this geometrically, your equivalence classes are lines through the origin because that’s what you get when you look at all scalar multiples of a given vector. What started out as the plane with extra points added is now the set of all lines though the origin. That’s one way to define the projective plane: a point in the projective plane corresponds to a line through the origin in ℝ³. Furthermore, a line in the projective plane corresponds to a plane through the origin in ℝ³.

Lines through the origin are determined by where they cross the unit sphere, so you could think of the projective plane as a sphere with one modification: because a line through the origin crosses the sphere in two antipodal points, we consider those two points in ℝ³ to be a single point in the projective plane.

Making peace with the projective plane

Posted on by John

In my newsletter I give an introduction to the latest few posts and occasionally give some additional commentary. In my latest newsletter I wrote

Projective space and homogeneous coordinates seemed like arbitrary abstractions when I was a student because they were presented without any motivation. Much later I came to realize that they’re natural, almost inevitable. Exceptional cases and hand-wavy references to objects “at infinity” go away when moving to projective space.

My mathematics education was very top-down: abstractions first, specifics later (if ever). I was OK with that for a while, until I hit my abstraction tolerance sometime in grad school. Now I would advocate more of a bottom-up approach, motivating abstractions first rather than presenting them as a fait accompli.

The first time I saw the projective plane was probably in a topology class where someone said you could construct the plane by starting with a square and gluing opposite edges in a physically impossible way. This seemed like a gimmick, a way to construct a non-orientable manifold but not anything practical. Another construction is to say the projective plane is an ordinary sphere with antipodal points identified. I found that a little more satisfying, but it still unmotivated.

What I would have appreciated was someone saying that the projective plane was invented to make geometry more elegant by eliminating exceptional cases and making rigorous the idea of things “at infinity.” For example, geometric calculations often have to treat vertical lines specially, but vertical lines are not special in projective geometry.

You could start by saying we’re going to represent points in the plane not simply as (x, y) but as (x, y, 1) and use (x, y, 0) for the point at infinity in the direction (x, y). That may seem like a hack, but it’s certainly motivated. It’s exactly the sort of thing a graphics programmer would do. In fact, I imagine many programmers have done just that, independently bumping into projective geometry.

After having introduced this extra coordinate, it’s natural to ask what would it mean if the last coordinate were something other than 0 or 1. You’ll quickly run into this when you start doing calculations on these extended coordinates. You could have a rule that you always normalize by dividing by the last coordinate, if it’s not zero, and then you have essentially discovered homogeneous coordinates. (Update; I develop this idea in more detail in the next post.)

You’ll see something like the approach above in elliptic curve cryptography. Programmers wanting to implement encryption algorithms are thinking concretely in terms of (x, y) points, until they have to worry about a mysterious “point at infinity” and handle it correctly. Then homogenous coordinates appear as a tool for getting out of a bind.

***

I thought about titling this post something like “Dr. Strangelove, or: How I Learned to Stop Worrying and and Love the Projective Plane” but I wasn’t sure how well that would go over. I doubt many readers have seen the 1964 movie this is alluding to, but the trope “How I Learned to Stop Worrying and Love …” is more widely known than the movie itself.