Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For every natural number $r$ I wish to construct a family of sets $\mathcal{F}$ such that

  1. Every set in $\mathcal{F}$ has cardinality $r$ and is a subset of $\{1,2,\ldots,r^2-r+1\},$
  2. For every distinct $X,Y \in \mathcal{F}$ we have $|X\cap Y| = 1,$
  3. $|\mathcal{F}| = r^2-r+1$

Now I know $\mathcal{F}$ can be obtained from the theory of projective planes, but I would like to see a more explicit way to construct $\mathcal{F}.$

Could someone provide a direct construction of $\mathcal{F}$ that involves as little concepts/theory as possible?

share|improve this question
    
Why do you say "resembling the projective plane"? I will do some further checking, but I believe a system of sets satisfying your conditions must be a projective plane. The Bruck-Ryser theorem implies that there are natural numbers $r$ for which such a construction is impossible - for example, $r-1=6$ and $r-1=14$. There is also a computer proof, due to Clement Lam and collaborators, that $r-1=10$ is impossible. (I keep using "$r-1$" since it is usual to characterize projective planes by their order rather than by the cardinality of the sets.) –  Will Orrick Mar 4 '13 at 18:13
    
So I've done the further checking, and indeed, conditions 1, 2, and 3 together imply that your system is a finite projective plane. This result is due to Ryser and is proved as Theorem 10.2.3 in Marshall Hall's Combinatorial Theory, 2nd edition. It follows by encoding the conditions in terms of incidence matrices and performing some linear algebra manipulations to show that all of the conditions in the definition of a finite projective plane are satisfied. –  Will Orrick Mar 4 '13 at 20:22
1  
As mentioned in my first comment, such a system of sets cannot exist for all natural numbers $r$. When $r-1$ is a power of a prime, however, a finite field of order $r-1$ exists, and the projective plane over that field satisfies your requirements. This appears to be the construction that you are dissatisfied with. I believe that when $r-1$ is prime, very little theory is needed to follow the construction. If you let me know what it is that you find non-explicit in the usual construction, I may have a go at writing up an answer. –  Will Orrick Mar 4 '13 at 20:28
    
@WillOrrick Yes! This part was somehow suggested in the book that I am currently studying. The thing I would like to see is a direct construction of such a system! –  Jernej Mar 4 '13 at 20:28
    
I concur with WillOrrick in asking the question “What is it you find non-explicit in the usual construction”? In my humble opinion, it would be hard to find a mathematical construction more explicit than this one. It uses only basic linear algebra and basic properties of finite fields. –  Ewan Delanoy Mar 5 '13 at 16:44
show 1 more comment

1 Answer

up vote 6 down vote accepted
+50

As discussed in the comments, your three conditions imply that the system of sets is a finite projective plane. First I'll give a construction of projective planes of prime order. The explanation follows.

Construction. Let $p$ be a prime. The finite field $\mathbf{F}_p$ is the set $\{0,1,2,\ldots,p-1\}$ with arithmetic performed modulo $p$. Let $v=p^2+p+1$. The projective plane of order $p$ has $v$ points and $v$ lines. Both points and lines are encoded by non-zero elements of $\mathbf{F}_p^3.$ If two such elements differ by a multiplicative constant, they are considered equivalent, that is, they represent the same point or line. In order that each point and line have a unique encoding, we require that the the rightmost non-zero element of each ordered triple be 1. For example, the element $(1,2,3)$ of $\mathbf{F}_5^3$ does not have rightmost non-zero element equal to $1,$ but it is equivalent to $2(1,2,3)=(2,4,1)$ which does. Similarly, $(0,4,0)$ does not have rightmost non-zero element equal to $1,$ but it is equivalent to $4(0,4,0)=(0,1,0)$ which does. Observe that there are $p^2$ triples with third element $1$, $p$ triples with second element $1$ and third element $0$, and one triple with first element $1$ and second and third elements $0$. Hence, up to equivalence, there are $p^2+p+1=v$ triples.

We think of the lines of the projective plane as sets of points. The line encoded by the triple $(a,b,c)$ consists of the points encoded by those triples $(x,y,z)$ for which $(a,b,c)\cdot(x,y,z)=0$ in $\mathbf{F}_p.$ That's all there is to the construction. As an example, the line encoded by $(3,1,0)$ in the projective plane of order $5$ consists of the six points encoded by $(0,0,1),$ $(1,2,1),$ $(2,4,1),$ $(3,1,1),$ $(4,3,1),$ and $(3,1,0).$

Explanation. Let's first remember how the projective plane is constructed over the field of real numbers. As motivation, consider an algebraic curve like the parabola described by the equation $y-x^2-x+3=0$. This describes a locus of points in the $x$-$y$ plane. Projectivizing means multiplying by powers of $z$ as appropriate so that every term has the same total degree: $$yz-x^2-xz+3z^2=0.$$ The original equation is obtained by setting $z=1$. Any solution, $(x,y,z),$ to this new equation has the property that $(cx,cy,cz)$ is also a solution, for any real number $c$. Because of this, it makes sense to consider solutions that differ only by a non-zero multiplicative constant to be equivalent. From this point of view, the important elements are the lines through the origin in $\mathbf{R}^3$, which have the form $\{c(x,y,z)\mid c\in\mathbf{R}\},$ where $(x,y,z)\ne(0,0,0).$ These lines through the origin are the "points" of the projective plane. A pair of distinct lines through the origin determines a plane through the origin. So planes through the origin are the "lines" of the projective plane. A plane through the origin can be described either in terms of a basis of linearly independent vectors, $\{(x_1,y_1,z_1),(x_2,y_2,z_2)\}$, as $$\{c(x_1,y_1,z_1)+d(x_2,y_2,z_2)\mid c, d\in\mathbf{R}\},$$ or by means of a normal vector, $(n_1,n_2,n_3)\ne(0,0,0),$ as $$\{(x,y,z)\mid (x,y,z)\cdot(n_1,n_2,n_3)=0\}.$$ Observe that both the "points" and the "lines" of the projective plane are characterized by non-zero vectors in $\mathbf{R}^3$ with vectors that are non-zero multiples of each other identified. This produces a kind of symmetry, called duality between "points" and "lines". The "point" characterized by $(x,y,z)$ lies on - we say "is incident on" - the "line" characterized by $(n_1,n_2,n_3)$ when $(x,y,z)\cdot(n_1,n_2,n_3)=0.$ From now on, I will drop the scare quotes around "point" and "line".

A point $(x,y)$ in the usual Cartesian plane - called the affine plane - that solves an algebraic equation corresponds to the point $\{c(x,y,1)\mid c\in\mathbf{R}\setminus\{0\}\}$ in the projective plane that solves the projectivized equation. Likewise, a solution $(x,y,z)$ of the projectivized equation, which is equivalent to $(x/z,y/z,1),$ corresponds to the solution $(x/z,y/z)$ of the original equation, provided that $z\ne0$. Hence the projectivized equation has all of the solutions of the original equation. But solutions with $z=0$ represent additional solutions - solutions at infinity. For the algebraic curve of our example, there is one solution at infinity, the point $\{c(0,1,0)\mid c\in\mathbf{R}\}$.

The projective plane augments the affine plane by adding points at infinity. These are the points of the form $\{c(x,y,0)\mid c\in\mathbf{R}\}$ with $(x,y)\ne(0,0).$ There is one point at infinity for each family of parallel lines in the $x$-$y$ plane. The points at infinity lie on a common line, the line at infinity, characterized by the normal vector $(0,0,1)$.

One reason for looking at the projectivized equation instead of the original equation is that the counting of solutions common to two algebraic curves, as occurs, for example, in Bézout's theorem, comes out more nicely when points at infinity are included. Another is that the points and lines of the projective plane satisfy the properties

  1. two distinct points lie on a unique line;
  2. two distinct lines intersect in a unique point;

which are more symmetrical -here's another example of duality! - than the corresponding properties of the affine plane:

  1. two distinct points lie on a unique line;
  2. two distinct non-parallel lines intersect in a unique point.

For example, the parallel lines $x-y+4=0$ and $x-y+6=0$ in the affine plane have no intersection, but the corresponding lines $x-y+4z=0$ and $x-y+6z=0$ in the projective plane (which can be written $(x,y,z)\cdot(1,-1,4)=0$ and $(x,y,z)\cdot(1,-1,6)=0$) intersect in the point at infinity $\{c(1,1,0)\mid c\in\mathbf{R}\}.$

Only the usual arithmetic operations of addition, subtraction, multiplication, and division were used in setting up the real projective plane. This means that nothing in the construction changes if we switch to another field, such as the rational numbers or the complex numbers.

Now there are fields of only finitely many elements. The simplest of these finite fields are obtained when one performs arithmetic modulo a fixed prime $p.$ For example, modulo 5, we have $3+4=7=2$, $3-4=-1=4$, and $3\times4=12=2.$ Furthermore, every non-zero element has a multipicative inverse: $1\times1=1$, $2\times3=6=1$, $3\times2=6=1$, $4\times4=16=1$. This implies that division can be performed: $3/2=3\times3=9=4.$ (Check: $2\times4=8=3.$)

If we perform the construction over one of these finite fields, we obtain a projective plane with only finitely many points and lines. There is a finite field of each prime power order. For powers greater than 1, some additional ideas are needed to construct the finite field. But once one has constructed the finite field, the construction of the projective plane over that field goes exactly the same way as described above.

Note that the $r$ in your question corresponds to $p+1$ in the construction described above. It was explained already why there are $v=p^2+p+1=r^2-r+1$ points and lines. To see why each line contains $p+1=r$ points, remember that a line is a set $$\{c(x_1,y_1,z_1)+d(x_2,y_2,z_2)\mid c, d\in\mathbf{F}_p\},$$ where $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$ are linearly independent. The points on the line are one-dimensional subspaces obtained by fixing $c$ and $d,$ not both zero. There are $p^2-1$ choices of the pair $(c,d)$, but non-zero scalar multiples of $(c,d),$ of which there are $p-1,$ describe the same point. Hence there are $(p^2-1)/(p-1)=p+1$ points on each line. To see that two lines intersect in a unique point, observe that the intersection of the lines characterized by linearly independent normal vectors $(n_1,n_2,n_3)$ and $(m_1,m_2,m_3)$ is the set of solutions to the equation $$\begin{bmatrix}n_1 & n_2 & n_3\\ m_1 & m_2 & m_3\end{bmatrix}\begin{bmatrix}x\\ y\\ z\\\end{bmatrix}=\begin{bmatrix}0\\ 0\\ 0\\\end{bmatrix}.$$ The set of solutions is a one-dimensional subspace of $\mathbf{F}_p^3,$ that is, a point.

(Added later) To make explicit that the set of points lying on a given line can be obtained by ordinary linear algebra, let's see how the six points lying on the line encoded by $(3,1,0)$ were produced in our example. The condition $(3,1,0)\cdot(x,y,z)=0$ implies $3x=-y,$ or $x=-2y=3y$ with $y$ and $z$ arbitrary. Hence a basis for the set of solutions is $a=(3,1,0),$ $b=(0,0,1)$. To satisfy our requirement that the rightmost non-zero element be $1,$ the cefficients $\alpha,$ $\beta$ in the general solution $\alpha a+\beta b$ must be chosen in one of two ways:

  1. $\beta=1,$ $\alpha$ arbitrary, giving the five solutions $(0,0,1),$ $(1,2,1),$ $(2,4,1),$ $(3,1,1),$ $(4,3,1),$
  2. $\beta=0,$ $\alpha=1,$ giving the solution $(3,1,0)$.

This pattern is general: the two basis vectors for the set of points lying on a given line can be written so that their rightmost elements equal $1$ and correspond to different arbitrary parameters. Let $a$ be the basis vector whose rightmost element lies farther to the left, and $b$ the basis vector whose rightmost element lies farther to the right. Then there are $p$ points of the form $\alpha a+b$ and one point $a,$ for a total of $p+1$ points. (End added later)

There do exist finite projective planes that are not obtained by the construction above. Such planes are called non-Desarguesian. The smallest non-Desarguesian planes are of order 9. If a plane were to exist of non-prime-power order, it would have to be non-Desarguesian, but no such plane has been constructed so far. The least order in which such a plane might exist is 12. No non-Desarguesian plane is known of prime order, but there is no proof that this couldn't happen.

share|improve this answer
    
Took me quite some time to go through this excellent post! Thank you Will! –  Jernej Mar 13 '13 at 20:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.