FiniteProjectivePlanesHaveQ2q1PointsAndQ2q1Lines 2005-04-11 19:12:38 2005-04-11 19:12:38 Proof finite projective plane 0 \usepackage{amssymb} % \usepackage{amsmath} % \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % portions from % makra.sty 1989-2005 by Marijke van Gans % % ^ ^ \catcode`\@=11 % o o % ->*<- % ~ %%%% CHARS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % code char frees for \let\Para\S % \Para § \S \scriptstyle \let\Pilcrow\P % \Pilcrow ¶ \P \mathchardef\pilcrow="227B \mathchardef\lt="313C % \lt < < bra \mathchardef\gt="313E % \gt > > ket \let\bs\backslash % \bs \ \let\us\_ % \us _ \_ ... %%%% DIACRITICS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %let\udot\d % under-dot (text mode), frees \d \let\odot\. % over-dot (text mode), frees \. %let\hacek\v % hacek (text mode), frees \v %let\makron\= % makron (text mode), frees \= %let\tilda\~ % tilde (text mode), frees \~ \let\uml\" % umlaut (text mode), frees \" %def\ij/{i{\kern-.07em}j} %def\trema#1{\discretionary{-}{#1}{\uml #1}} %%%% amssymb %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \let\le\leqslant \let\ge\geqslant %let\prece\preceqslant %let\succe\succeqslant %%%% USEFUL MISC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %def\C++{C$^{_{++}}$} %let\writelog\wlog %def\wl@g/{{\sc wlog}} %def\wlog{\@ifnextchar/{\wl@g}{\writelog}} %def\org#1{\lower1.2pt\hbox{#1}} % chem struct formulae: \bs, --- / \org{C} etc. %%%% USEFUL INTERNAL LaTeX STUFF %%%%%%%%%%%%%%%%%%%%%%%% %let\Ifnextchar=\@ifnextchar %let\Ifstar=\@ifstar %def\currsize{\@currsize} %%%% KERNING, SPACING, BREAKING %%%%%%%%%%%%%%%%%%%%%%%%% \def\comma{,\,\allowbreak} %def\qqquad{\hskip3em\relax} %def\qqqquad{\hskip4em\relax} %def\qqqqquad{\hskip5em\relax} %def\qqqqqquad{\hskip6em\relax} %def\qqqqqqquad{\hskip7em\relax} %def\qqqqqqqquad{\hskip8em\relax} %%%% LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %let\addtoreset\@addtoreset %{A}{B} adds A to list of counters reset to 0 % when B is \refstepcounter'ed (see latex.tex) % %def\numbernext#1#2{\setcounter{#1}{#2}\addtocounter{#1}{\m@ne}} %%%% EQUATIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% LEMMATA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% DISPLAY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% MATH LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \let\D\displaystyle \let\T\textstyle \let\S\scriptstyle \let\SS\scriptscriptstyle % array: %def\<#1:{\begin{array}{#1}} %def\>{\end{array}} % array using [ ] with rounded corners: %def\[#1:{\left\lgroup\begin{array}{#1}} %def\]{\end{array}\right\rgroup} % array using ( ): %def\(#1:{\left(\begin{array}{#1}} %def\){\end{array}\right)} %def\hh{\noalign{\vskip\doublerulesep}} %%%% MATH SYMBOLS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %def\d{\mathord{\rm d}} % d as in dx %def\e{{\rm e}} % e as in e^x %def\Ell{\hbox{\it\char`\$}} \def\sfmath#1{{\mathchoice% {{\sf #1}}{{\sf #1}}{{\S\sf #1}}{{\SS\sf #1}}}} \def\Stalkset#1{\sfmath{I\kern-.12em#1}} \def\Bset{\Stalkset B} \def\Nset{\Stalkset N} \def\Rset{\Stalkset R} \def\Hset{\Stalkset H} \def\Fset{\Stalkset F} \def\kset{\Stalkset k} \def\In@set{\raise.14ex\hbox{\i}\kern-.237em\raise.43ex\hbox{\i}} \def\Roundset#1{\sfmath{\kern.14em\In@set\kern-.4em#1}} \def\Qset{\Roundset Q} \def\Cset{\Roundset C} \def\Oset{\Roundset O} \def\Zset{\sfmath{Z\kern-.44emZ}} % \frac overwrites LaTeX's one (use TeX \over instead) %def\fraq#1#2{{}^{#1}\!/\!{}_{\,#2}} \def\frac#1#2{\mathord{\mathchoice% {\T{#1\over#2}} {\T{#1\over#2}} {\S{#1\over#2}} {\SS{#1\over#2}}}} %def\half{\frac12} \mathcode`\<="4268 % < now is \langle, \lt is < \mathcode`\>="5269 % > now is \rangle, \gt is > %def\biggg#1{{\hbox{$\left#1\vbox %to20.5\p@{}\right.\n@space$}}} %def\Biggg#1{{\hbox{$\left#1\vbox %to23.5\p@{}\right.\n@space$}}} \let\epsi=\varepsilon \def\omikron{o} \def\Alpha{{\rm A}} \def\Beta{{\rm B}} \def\Epsilon{{\rm E}} \def\Zeta{{\rm Z}} \def\Eta{{\rm H}} \def\Iota{{\rm I}} \def\Kappa{{\rm K}} \def\Mu{{\rm M}} \def\Nu{{\rm N}} \def\Omikron{{\rm O}} \def\Rho{{\rm P}} \def\Tau{{\rm T}} \def\Ypsilon{{\rm Y}} % differs from \Upsilon \def\Chi{{\rm X}} %def\dg{^{\circ}} % degrees %def\1{^{-1}} % inverse \def\*#1{{\bf #1}} % boldface e.g. vector %def\vi{\mathord{\hbox{\bf\i}}} % boldface vector \i %def\vj{\mathord{\,\hbox{\bf\j}}} % boldface vector \j %def\union{\mathbin\cup} %def\isect{\mathbin\cap} \let\so\Longrightarrow \let\oso\Longleftrightarrow \let\os\Longleftarrow % := and :<=> %def\isdef{\mathrel{\smash{\stackrel{\SS\rm def}{=}}}} %def\iffdef{\mathrel{\smash{stackrel{\SS\rm def}{\oso}}}} \def\isdef{\mathrel{\mathop{=}\limits^{\smash{\hbox{\tiny def}}}}} %def\iffdef{\mathrel{\mathop{\oso}\limits^{\smash{\hbox{\tiny %def}}}}} %def\tr{\mathop{\rm tr}} % tr[ace] %def\ter#1{\mathop{^#1\rm ter}} % k-ter[minant] %let\.=\cdot %let\x=\times % ><— (direct product) %def\qed{ ${\S\circ}\!{}^\circ\!{\S\circ}$} %def\qed{\vrule height 6pt width 6pt depth 0pt} %def\edots{\mathinner{\mkern1mu % \raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu % .shorter % \raise4pt\hbox{.}\mkern1mu % . % \raise1pt\hbox{.}\mkern1mu}} % . %def\fdots{\mathinner{\mkern1mu % \raise7pt\vbox{\kern7pt\hbox{.}} % . ~45° % \raise4pt\hbox{.} % . % \raise1pt\hbox{.}\mkern1mu}} % . \def\mod#1{\allowbreak \mkern 10mu({\rm mod}\,\,#1)} % redefines TeX's one using less space %def\int{\intop\displaylimits} %def\oint{\ointop\displaylimits} %def\intoi{\int_0^1} %def\intall{\int_{-\infty}^\infty} %def\su#1{\mathop{\sum\raise0.7pt\hbox{$\S\!\!\!\!\!#1\,$}}} %let\frakR\Re %let\frakI\Im %def\Re{\mathop{\rm Re}\nolimits} %def\Im{\mathop{\rm Im}\nolimits} %def\conj#1{\overline{#1\vphantom1}} %def\cj#1{\overline{#1\vphantom+}} %def\forAll{\mathop\forall\limits} %def\Exists{\mathop\exists\limits} %%%% PICTURES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %def\cent{\makebox(0,0)} %def\node{\circle*4} %def\nOde{\circle4} %%%% REFERENCES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %def\opcit{[{\it op.\,cit.}]} \def\bitem#1{\bibitem[#1]{#1}} \def\name#1{{\sc #1}} \def\book#1{{\sl #1\/}} \def\paper#1{``#1''} \def\mag#1{{\it #1\/}} \def\vol#1{{\bf #1}} \def\isbn#1{{\small\tt ISBN\,\,#1}} \def\seq#1{{\small\tt #1}} %def\url<{\verb>} %def\@cite#1#2{[{#1\if@tempswa\ #2\fi}]} %%%% VERBATIM CODE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %def\"{\verb"} %%%% AD HOC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% WORDS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \hyphenation{pre-sent pre-sents pre-sent-ed pre-sent-ing % re-pre-sent re-pre-sents re-pre-sent-ed re-pre-sent-ing % re-fer-ence re-fer-ences re-fer-enced re-fer-encing % ge-o-met-ry re-la-ti-vi-ty Gauss-ian Gauss-ians % Des-ar-gues-ian} %def\oord/{o{\trema o}rdin\-ate} % usage: C\oord/s, c\oord/. % output: co\"ord... except when linebreak at co-ord... %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ^ ^ \catcode`\@=12 % ` ' % ->*<- % ~ \PMlinkescapeword{covers} \PMlinkescapeword{Z} {\bf Given} a finite projective plane that contains a quadrangle OXYZ (i.e.\ no three of these four points are on one line). {\bf To prove}: the plane has $q^2+q+1$ points and $q^2+q+1$ lines for some integer $q$, and there are $q+1$ points on each line and $q+1$ lines through each point. Let $x$ and $y$ be the lines OX and OY, which must exist by the axioms. By the assumption OXYZ is a quadrangle these lines are distinct and Z is not on them. Let there be $p$ points X$_i$ on $x$ other than O, for each of them one line ZX$_i$ exists, and is distinct (one lines cannot pass through two X$_i$ unless it is $x$ but that's not a line through Z). Conversely every line through Z must intersect $x$ in a unique point (two lines intersecting in Z cannot intersect at another point, and Z is not a point on $x$). So there are $p+1$ lines through Z (OZ is one of them). By the same reasoning, using $y$, there are $q+1$ lines through Z so $p=q$. We also found $q+1$ points (including O) on $y$ and the same number on $x$. Intersecting the $q+1$ lines through Z with XY (on which Z does not lie, the quadrangle again) reveals at least $q+1$ distinct points there and at most $q+1$ because for each point there there is a line through it and Z. The lines not through O intersect $x$ in one of the $q$ points X$_i$ and $y$ in one of the $q$ points Y$_j$. There are $q^2$ possibilities and each of them is a distinct line, because there is only one line through a given X$_i$ and Y$_j$. The lines that do pass through O intersect XY in one of the $q+1$ points there, again one line for each such point and vice versa. That's $q+1$ lines through O and $q^2$ not through O, $q^2+q+1$ in all. There are $q+1$ lines through X (to each of the points of $y$) and $q+1$ lines through Y (to each of the points of $x$). Intersect the $q$ lines through X other than XY with the $q$ lines through Y other than XY, these $q^2$ intersections are all distinct because for any P there's only one line PX and one line PY. Note we did not use the line XY. Conversely for any P not on XY there must be some PX and some PY, so there are exactly $q^2$ points not on XY. Add the $q+1$ points on XY for a total of $q^2+q+1$. The constructions above already showed $q+1$ lines through some points (X, Y and Z), by the same games as before that implies for each of them $q+1$ points on every line not through that point. We also saw $q+1$ points on some lines ($x$, $y$, XY) which implies for each of them $q+1$ lines through every point not on that line. Such reasoning covers $q^2$ items on first application and rapidly mops up stragglers on repeated application. Some form of this proof is standard math lore; this version was half remembered and half reconstructed.