%(If you can read TeX fluently, you may wish to fast-forward to a line
%beginning %file starts here or \frfilename
%if one of these is present.)
%TeXfiles with this heading are designed for processing with AmSTeX,
%accessed through TeXfiles amstex.tex (with amssym.tex and
% amsppt.sty and possibly amsppt.sti) during compilation.
%If these are unavailable, a readable
%version can (I hope) be produced by deleting the % before
% \amstexsupportedfalse below.
%Some special difficulties arise with the importation of .ps files
%in diagrams. Look for \picture below for notes on these.
%The following \count registers are used for special purposes:
% \count1=\stylenumber to specify style
% \count2=\footnotenumber to count footnotes
%AmSTeX declaration
\newif\ifamstexsupported
\amstexsupportedtrue
% \amstexsupportedfalse %use when AMSTeX unavailable
\newif\ifDHFamstexloaded %for detection of a non-standard AMSTeX
\DHFamstexloadedfalse
\newif\ifDHFamspptloaded
\DHFamspptloadedfalse
\newif\iffourteensavailable
\fourteensavailabletrue
\fourteensavailablefalse
\newif\ifathome
\athometrue %to cope with a quirk of my son's Ghostscript
\athomefalse
\newif\iffirstpage
\firstpagetrue
%Style assignments
\countdef\stylenumber=1
\countdef\footnotenumber=2
\def\fullsize{\magnification=\magstep1
\def\pagewidth{390pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=1}
\def\smallprint{\magnification=\magstep0
\overfullrule0pt
\def\pagewidth{468pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=2}
\def\printersize{\magnification=\magstep1
\baselineskip24pt
\overfullrule0pt
\def\pagewidth{330pt}
\def\pageheight{8.5truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=3}
\def\refsize{\magnification=\magstep1
\overfullrule0pt
\def\pagewidth{390pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=4}
\def\rrversion{\magnification=\magstep1
\overfullrule0pt
\def\pagewidth{330pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=5}
\def\bigsize{\magnification=\magstep2
\overfullrule0pt
\def\pagewidth{325pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=6}
\def\bbigsize{\magnification=\magstep3
\overfullrule0pt
\def\pagewidth{271pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=7}
\def\USsmallprint{\magnification=\magstep0
\overfullrule0pt
\def\pagewidth{482pt}
\def\pageheight{8.7truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=8}
\def\halfmagsize{\magnification=\magstephalf
\def\pagewidth{427pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=9}
% register stylenumber is used to control the output format
%addresses, letterheads
\def\deptaddress{\hskip 3truein Department of Mathematical Sciences\par
\noindent e-mail: {\tt fremdh}\hskip 2.9truein\today\par
\medskip}
\long\def\univaddress#1{\hskip 3truein Department of Mathematical Sciences\par
\hskip 3truein University of Essex\par
\hskip 3truein Colchester CO4 3SQ\par
\hskip 3truein England\par
%\hskip 3truein van Vleck Hall\par
%\hskip 3truein 480 Lincoln Drive\par
%\hskip 3truein Madison\par
%\hskip 3truein WI 53706-1388, U.S.A.\par
\hskip 3.2truein#1\par
\noindent e-mail: {\tt fremdh\@essex.ac.uk}
%{\tt fremlin\@math.wisc.edu}
\bigskip}
\long\def\homeaddress#1{\hskip 3truein 25 Ireton Road\par
\hskip 3truein Colchester CO3 3AT\par
\hskip 3truein England\par
\hskip 3.2truein#1\par
\noindent e-mail: {\tt fremdh\@essex.ac.uk}
\bigskip}
\long\def\letterhead#1#2#3{\univaddress{#1}
{\parindent=0pt
#2
}
\medskip
\noindent Dear #3,
}
\def\shortaddress{\noindent Departmentof Mathematical Sciences, University of Essex,
Colchester CO4 3SQ, England\par
\noindent e-mail: fremdh\@essex.ac.uk}
\def\valediction#1#2{\bigskip
\hskip 3truein #1,
\vskip 1truein
\hskip 3.3truein #2
\bigskip}
%picture importation
%It is clear that there is no general standard. The syntax I
%use when calling for a .ps file is
% \def\Caption{<...>}
% \picture{}{}
%which is supposed to import .ps at height ,
%centered, and adding a one-line centered caption <...> .
%The basic macro listed in \def\picture is that which
%used to work at Essex. We now use the macro in
% \def\picturewithpsfig , which requires a previous input
% psfig.tex or psfig.sty ;
%if you interpolate \atUEssex early in your file it will
%give you the latter.
% I find that psfig is erratic in its centering, especially
%under magnification, so I have written a routine
% \centerpicturewithpsfig (which may be called from
% \centerpicture ) with the syntax
% \centerpicture{}{}{}
%the first dimension being width and the second height.
\def\picture#1#2{\bigskip
\bigskip
\immediate\write0{importing diagram #1.ps at height #2
with dvitops}
\vbox{\vskip #2
\special{dvitops: import #1.ps \pagewidth #2}
\Centerline{\Caption}
}
\medskip
\def\Caption{}}
%an alternative version, without caption
\def\centerpicture#1#2#3{\bigskip
\bigskip
\immediate\write0{importing diagram #1.ps at width #2
and height #3 with dvitops}
\vbox{\vskip #3
\special{dvitops: import #1.ps \pagewidth #3}
}}
%to put pictures on same line
\def\sideshiftedpicture#1#2#3#4{\bigskip
\bigskip
\immediate\write0{importing diagram #1.ps at height #4
and width #3 with dvitops}
\vbox{\special{dvitops: import #1.ps #3 #4}}
\hskip #2 plus 0pt minus 0pt
}
\def\startsideshiftedpicture{}
\newcount\scaleup
\newcount\scaledown
\scaleup=1
\scaledown=1
\def\scalesideshiftedpicture#1#2#3#4{
\dimen4=#4
\dimen3=#3
\multiply\dimen4 by\scaleup
\divide\dimen4 by \scaledown
\multiply\dimen3 by\scaleup
\divide\dimen3 by \scaledown
\sideshiftedpicture{#1}{#2}{\dimen3}{\dimen4}}
%alternative picture importation code
\def\atUEssex{
\input psfig.sty
\def\picture##1##2{\picturewithpsfig{##1}{##2}}
\def\sideshiftedpicture##1##2##3##4{
\sideshiftedpicturewithpsfig{##1}{##2}{##3}{##4}}
\def\centerpicture##1##2##3{
\centerpicturewithpsfig{##1}{##2}{##3}}
\def\startsideshiftedpicture{
\sideshiftedpicture{empty}{1pt}{1pt}{1pt}}
}
\def\athome{
\input psfig.sty
\def\picture##1##2{\picturewithpsfig{##1}{##2}}
\def\sideshiftedpicture##1##2##3##4{
\sideshiftedpicturewithpsfig{##1}{##2}{##3}{##4}}
\def\centerpicture##1##2##3{
\centerpicturewithpsfig{##1}{##2}{##3}}
\def\startsideshiftedpicture{
\sideshiftedpicture{empty}{1pt}{1pt}{1pt}}
\voffset=1cm}
\def\atUWMadison{
\fourteensavailablefalse
\input psfig
\def\picture##1##2{\picturewithpsfig{##1}{##2}}
}
\def\picturewithpsfig#1#2{\bigskip
\immediate\write0{importing diagram #1.ps at height #2 with psfig}
\vbox{\hsize\pagewidth
%\centerline{\discrversionA{\hskip1truein}{}\psfig{figure=#1.ps,height=#2
\centerline{\psfig{figure=#1.ps,height=#2
}}
\medskip
\centerline{\Caption}}
\medskip
\def\Caption{}}
\def\centerpicturewithpsfig#1#2#3{
\immediate\write0{importing diagram #1.ps at width #2
and height #3 with psfig}
\dimen 3 = #2
\dimen 4 = #3
\dimen 2 = \pagewidth
\advance\dimen2 by -\dimen3
\divide\dimen2 by 2
\discrversionB{\shrinkonestep}{}
\discrversionH{\shrinkonestep}{}
\discrversionF{\enlargeonestep}{}
\discrversionG{\enlargeonestep\enlargeonestep}{}
\dimen 6 = \dimen4
\divide\dimen6 by 3
\vskip\dimen6
\ifdim\dimen2>0\hskip\dimen2\fi
\vbox{\psfig{file=#1.ps,width=\dimen3,height=\dimen4}}
\discrversionG{\vskip-\dimen6}{}
}
\def\enlargeonestep{\dimen5 = 5truein
\dimen6 = 7truein
\ifdim\dimen3<\dimen5
\ifdim\dimen4<\dimen6
\divide\dimen3 by 5
\multiply\dimen3 by 6
\divide\dimen4 by 5
\multiply\dimen4 by 6
\fi\fi}
\def\shrinkonestep{\divide\dimen3 by 6
\multiply\dimen3 by 5
\divide\dimen4 by 6
\multiply\dimen4 by 5}
\def\sideshiftedpicturewithpsfig#1#2#3#4{
\immediate\write0{importing diagram #1.ps at height #4
and width #3 with psfig}
\dimen 4 = #4
\dimen 3 = #3
\discrversionB{\shrinkonestep}{}
\discrversionH{\shrinkonestep}{}
\discrversionF{\enlargeonestep}{}
\discrversionG{\enlargeonestep\enlargeonestep}{}
% \vbox{\psfig{figure=#1.ps,height=\dimen4,width=\dimen3}}
\psfig{figure=#1.ps,height=\dimen4,width=\dimen3}
\hskip #2 plus 0pt minus 0pt}
%alternative picture importation code; I've been told about this
%but have not used it successfully myself
%\def\Caption{}
%\input epsf
%\epsfverbosetrue
%\def\picture#1#2{\bigskip
% \bigskip
% \immediate\write0{importing diagram #1.ps at height #2 with epsf}
% \epsfysize=#2
% \centerline{\epsffile{#1.ps}}
% \medskip
% \Centerline{\Caption}
% \medskip
% }
%in addition it may be necessary to amend the imported .ps file
%by replacing the %%BoundingBox header by %%BoundingBox:
%special fonts
\def\biggerscriptfonts{\scriptfont0=\eightrm
\scriptfont1=\eighti
\scriptfont2=\eightsy
\scriptfont3=\eightex
\scriptfont\bffam=\eightbf
\scriptfont\msbfam=\eightmsb
\scriptfont\eufmfam=\eighteufm
}
\def\Loadcyrillic{\ifamstexsupported
\input cyracc.def
\font\tencyr=wncyr10
\def\cyr{\tencyr\cyracc} \def\itcyr{\tenitcyr\cyracc}
\else\def\cyr{\smc}\def\cdprime{u\i}\def\Cdprime{UI}\fi}
%http://wkweb3.cableinet.co.uk/linux/LDP/HOWTO/Cyrillic-HOWTO-7.html
%cyrillic.tex
\def\Loadfourteens{\iffourteensavailable
\font\fourteenrm=cmr14
\font\fourteenbf=cmbx14
\font\fourteenit=cmsl14
\else\font\fourteenrm=cmr10 scaled \magstep2
\font\fourteenbf=cmbx10 scaled \magstep2
\font\fourteenit=cmsl10 scaled \magstep2
\fi}
\def\smallerfonts{\eightpoint
\textfont\msbfam=\eightmsb
\textfont\eufmfam=\eighteufm
\textfont\bffam=\eightbf
\textfont\eurmfam=\eighteurm
\textfont\eusmfam=\eighteusm
}
\font\twelveex=cmex10 scaled \magstep1
%Copyright declarations
\newcount\oldcopyrightdate
\newcount\newcopyrightdate
\oldcopyrightdate=0
\def\copyrightdate#1{\newcopyrightdate=#1
\ifnum\newcopyrightdate=\oldcopyrightdate\else
\oldcopyrightdate=#1
\oldfootnote{}{\eightrm \copyright\ #1 D.~H.~Fremlin}
\immediate\write0{Copyright #1}
\fi}
%hyphenation
\hyphenation{equi-ver-id-ical}
%miscellaneous definitions
\def\Aut{\mathop{\text{Aut}}}
\def\backstep#1{\hskip -0.#1em plus 0 pt minus 0 pt}
\def\Bang{\vthsp\hbox{\bf X\hskip0.07em\llap X\hskip0.07em\llap X\rm}}
\def\BanG{\Bang{\hskip 1.111pt plus 3.333pt minus 0pt}}
%\def\BbbN{\mathchoice{\hbox{$\Bbb N$\hskip0.02em}}
% {\hbox{$\Bbb N$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb N$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb N$\hskip0.04em}}}
%\def\BbbQ{\mathchoice{\hbox{$\Bbb Q$\hskip0.02em}}
% {\hbox{$\Bbb Q$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb Q$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb Q$\hskip0.04em}}}
%\def\BbbR{\mathchoice{\hbox{$\Bbb R$\hskip0.02em}}
% {\hbox{$\Bbb R$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb R$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb R$\hskip0.04em}}}
% %do not use with $\Bbb R^X$
%\def\BbbZ{\mathchoice{\hbox{$\Bbb Z$\hskip0.02em}}
% {\hbox{$\Bbb Z$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb Z$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb Z$\hskip0.04em}}}
\def\BbbN{\openBbb{N}}
\def\BbbQ{\openBbb{Q}}
\def\BbbR{\openBbb{R}}
%do not use with $\Bbb R^X$ do not use in $_{\Bbb R^r}$
\def\BbbZ{\openBbb{Z}}
\def\Bbbone{\hbox{1\hskip0.13em\llap{1}}}
\def\biggerint{\textfont3=\twelveex\intop\nolimits}
% you can get this size into a displayed formula with
% $$\hbox{$\biggerint_{\Cal S}\pmb{u}\,d\pmb{v}$}$$
% but it may then seem cramped
\def\biggeriint{\textfont3=\twelveex\iint}
% remarkable fact: this seems to infect all \int within a given
% $..$ ; but $\biggerint$$\int$ seems to leave the $\int$ normal
% really \textfont3=\twelveex is more reliable, since \biggerint
% as written gets turned off rather easily (e.g. by \comment,
% or by an extra {...})
\def\bover#1#2{{{#1}\over{#2}}}
\def\Bover#1#2{\backstep4\hbox{
\biggerscriptfonts${\shortstrut#1}\over{\shortstrut#2}$}}
% when there are superscripts in the denominator, as in \Bover1{2^m}
% or \Bover1{\sqrt{2\pi}^r} , these can sometimes come out with better
% horizontal alignment if you use \Bover1{{\sshortstrut 2}^m} or
% \Bover1{{\sqrt{2\pi}}^r}
\def\bsover#1#2{\textstyle\bover{#1}{#2}}
\def\bsp{/\penalty-100}
\def\bsdot{.\penalty-100}
\def\Caption{}
\def\Center#1{
\Centerline{#1}
\noindent}
\def\Centerline#1{\vskip 5pt
{\def\int{\text{}$$\textfont3=\twelveex\intop\nolimits}
\def\dashint{\text{}$$\textfont3=\twelveex
\mskip2mu\vrule height2.65pt width4.5pt depth-2.35pt\mskip-11mu
\intop\nolimits\mskip-2mu}
\def\idashint{\text{}$$\int\mskip-7mu\dashint}
\def\dashiint{\text{}$$\dashint\mskip-6mu\int}
\def\dashidashint{\text{}$$\dashint\mskip-6mu\dashint}
\def\underlineint{
\text{}$$\textfont3=\twelveex\underline{\intop\nolimits}}
\def\overlineint{
\text{}$$\textfont3=\twelveex\overline{\intop\nolimits}}
\def\iint{\text{}$$\textfont3=\twelveex
\intop\nolimits\hskip-0.5em\intop\nolimits}
\def\sum{\text{}$$\sumop}
\def\prod{\text{}$$\prodop}
\def\bigcap{\text{}$$\bigcapop}
\def\bigcup{\text{}$$\bigcupop}
\centerline{#1}}\vskip 5pt}
\mathchardef\bigcapop="1354
\mathchardef\bigcupop="1353
\mathchardef\prodop="1351
\mathchardef\sumop="1350
%in \Centerline{$\overline{}$, $\cmmnt{}$} must use \sumop etc
\def\cf{\mathop{\text{cf}}}
\def\circumflex#1{{\accent"5E #1}}
\def\closeplus{\hbox{+}}
\long\def\cmmnt#1{\ifresultsonly\else{#1}\fi}
\def\coint#1{\left[#1\right[}
\def\curl{\mathop{\text{curl}}}
\def\dashint{\mathchoice{-\mskip-20mu\intop\nolimits}
{{\vrule height2.75pt width4.5pt depth-2.45pt\mskip-10mu\intop\nolimits}}
{-\mskip-16.5mu\intop\nolimits} %not yet used
{-\mskip-16.5mu\intop\nolimits}} %not yet used
\def\idashint{\mathchoice{\int\mskip-6mu\dashint}
{\int\mskip-5mu\dashint}
{\int\mskip-5mu\dashint} %not yet used
{\int\mskip-5mu\dashint}} %not yet used
\def\dashiint{\mathchoice{\dashint\mskip-10mu\int}
{\dashint\mskip-6mu\int}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\dashidashint{\mathchoice{\dashint\mskip-10mu\dashint}
{\dashint\mskip-6mu\dashint}
{\dashint\mskip-6mu\dashint} %not yet used
{\dashint\mskip-6mu\dashint}} %not yet used
\def\dashidashiint{\mathchoice{\dashint\mskip-8mu\dashint\mskip-10mu\int}
{\dashint\mskip-4mu\dashint\mskip-8mu\int}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\dashiidashint{\mathchoice{\dashint\mskip-10mu\int\mskip-8mu\dashint}
{\dashint\mskip-4mu\dashint\mskip-8mu\int}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\idashidashint{\mathchoice{\int\mskip-8mu\dashint\mskip-8mu\dashint}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\diam{\mathop{\text{diam}}}
\def\discrpage{\ifnum\stylenumber=1{\frnewpage} %redefined in mt.tex
\else\ifnum\stylenumber=3{\frnewpage}
\else\ifnum\stylenumber=5{\frnewpage}
\else\bigskip\fi\fi\fi}
\long\def\discrversionA#1#2{\ifnum\stylenumber=1#1\else#2\fi}
\long\def\discrversionB#1#2{\ifnum\stylenumber=2#1\else#2\fi}
\long\def\discrversionC#1#2{\ifnum\stylenumber=3#1\else#2\fi}
\long\def\discrversionD#1#2{\ifnum\stylenumber=4#1\else#2\fi}
\long\def\discrversionE#1#2{\ifnum\stylenumber=5#1\else#2\fi}
\long\def\discrversionF#1#2{\ifnum\stylenumber=6#1\else#2\fi}
\long\def\discrversionG#1#2{\ifnum\stylenumber=7#1\else#2\fi}
\long\def\discrversionH#1#2{\ifnum\stylenumber=8#1\else#2\fi}
% facility for special interpolations in particular output
% versions
\def\displaycause#1{\noalign{\noindent (#1)}}
\def\diverg{\mathop{\text{div}}}
\def\dom{\mathop{\text{dom}}}
\def\eae{=_{\text{a.e.}}}
\def\esssup{\mathop{\text{ess sup}}}
\mathchardef\Exists="3239
\def\family#1#2#3{\langle#3\rangle_{#1\in#2}}
\def\familyi#1#2{\family{i}{#1}{#2}}
\def\familyiI#1{\familyi{I}{#1}}
\def\frfilename#1{\ifnum\stylenumber=1{\noindent filename #1}
\else\ifnum\stylenumber=6{\noindent{\fiverm filename #1}}
\else\ifnum\stylenumber=7{\noindent{\fiverm filename #1}}
\else\fi\fi\fi}
\def\Footnote#1#2{\footnote"#1"{#2}}
\mathchardef\Forall="3238
\def\frakc{\frak c\phantom{.}}
\def\frnewpage{\vskip \pageheight plus 0pt minus\pageheight
\eject
\gdef\topparagraph{}
\gdef\bottomparagraph{}
}
\def\frsmallcirc{{\hskip 1pt plus 0pt minus 0pt}
{\raise 1pt\hbox{$\smallcirc$}}{\hskip 1pt plus 0pt minus 0pt}}
\def\geae{\ge_{\text{a.e.}}}
\def\grad{\mathop{\text{grad}}}
\def\grheada{{\bf ($\pmb{\alpha}$)}}
\def\grheadb{{\bf ($\pmb{\beta}$)}}
\def\grheadc{{\bf ($\pmb{\gamma}$)}}
\def\grheadd{{\bf ($\pmb{\delta}$)}}
\def\grheade{{\bf ($\pmb{\epsilon}$)}}
\def\grheadz{{\bf ($\pmb{\zeta}$)}}
\def\grv#1{{\accent"12 #1}}
\def\hfillall{\hskip\pagewidth plus0pt minus\pagewidth}
\def\Imag{\mathop{\Cal I\text{m}}}
\long\def\inset#1{{\narrower\narrower{\vskip 1pt plus 1pt minus 0pt}
#1
{\vskip 1pt plus 1pt minus 0pt}}}
\def\Int#1#2{\displaystyle{\int_{#1}^{#2}}}
\def\interior{\mathop{\text{int}}}
\def\leae{\le_{\text{a.e.}}}
\long\def\leaveitout#1{}
\def\LLcorner{\mathchoice{\,\hbox{\vrule height7pt width0.5pt depth0pt
\vrule height0.5pt width5pt depth0pt}\,}
{\,\hbox{\vrule height7pt width0.5pt depth0pt
\vrule height0.5pt width5pt depth0pt}\,}
{\,\hbox{\vrule height5pt width0.3pt depth0pt
\vrule height0.3pt width4pt depth0pt}\,}
{\,\hbox{\vrule height4pt width0.25pt depth0pt
\vrule height0.25pt width3pt depth0pt}\,}
}
\def\Ln{\mathop{\text{Ln}}}
\def\Loadfont#1{\font#1}
\def\loibr{\hbox{\hskip0.1em]\hskip0.05em}}
\def\Matrix#1{\pmatrix#1\endpmatrix}
\def\Mu{\text{M}}
\def\noamslogo{\def\amslogo{}}
\def\normalsubgroup{\vartriangleleft}
\def\Nu{\text{N}}
\def\ocint#1{\left]#1\right]}
\def\ofamily#1#2#3{\langle#3\rangle_{#1<#2}}
\let\oldcases=\cases
\let\oldfootnote=\footnote
\def\On{\mathop{\text{On}}}
\def\ooint#1{\left]#1\right[}
\def\openBbb#1{\Bbb#1\mskip1mu}
\def\pd#1#2{\bover{\partial#1}{\partial#2}}
\def\Pd#1#2{\Bover{\partial#1}{\partial#2}}
\def\pdd#1#2{{{\partial^2#1}\over{\partial#2^2}}}
\def\Pdd#1#2{\Bover{\partial^2#1}{\partial#2^2}}
\def\pde#1#2#3{{{\partial^2#1}\over{\partial#2\partial#3}}}
\def\Pde#1#2#3{\Bover{\partial^2#1}{\partial#2\partial#3}}
\def\Prf{\vthsp\hbox{\bf P\hskip0.07em\llap P\hskip0.07em\llap P\rm}}
\def\pushbottom#1{\hbox{\vrule height0pt depth#1 width0pt}}
\def\Qed{\vthsp\hbox{\bf Q\hskip0.07em\llap Q\hskip0.07em\llap Q\rm}}
\def\QeD{\Qed{\hskip 1.111pt plus 3.333pt minus 0pt}}
\def\Quer{\vthsp\hbox{\bf ?\hskip0.05em\llap ?\hskip0.05em\llap
?\thinspace\rm}}
\def\query{\discrversionA{\immediate\write0{query}
\global\advance\footnotenumber by 1
\oldfootnote{$^{\the\footnotenumber}$}{query}}{}}
\def\Real{\mathop{\Cal R\text{e}}}
\def\restr{\mathchoice
{\hbox{$\restriction$}\mskip 1mu}
{\hbox{$\restriction$}\mskip 1mu}
{\hbox{$\scriptstyle\restriction$}\mskip 1mu}
{\hbox{$\scriptscriptstyle\restriction$}\mskip 1mu}}
\def\restrp{\mathchoice
{\hbox{$\restriction$}\mskip 2mu}
{\hbox{$\restriction$}\mskip 2mu}
{\mskip-1mu\hbox{$\scriptstyle\restriction$}\mskip 2mu}
{\mskip-1mu\hbox{$\scriptscriptstyle\restriction$}\mskip 1mu}}
%use in \restrp V \restrp W \restrp Y
% \restrp\Cal P \restrp\Bbb R \restrp\frak
% \restrp\Omega \restrp\Tau \restrp\Upsilon
% \restrp[ \restrp\widehat{}
\def\Rho{\text{P}}
\def\roibr{\hbox{\hskip0.05em[\hskip0.1em}}
\def\RoverC{\hbox{\biggerscriptfonts${{\Bbb R}\atop{\Bbb C}}$}}
\def\sequence#1#2{\family{#1}{\Bbb N}{#2}}
\def\sequencen#1{\sequence{n}{#1}}
\def\setover#1#2{\overset{#1}\to{#2}}
\def\shortstrut{\hbox{\vrule height7.5pt depth2.5pt width0pt}}
\def\sshortstrut{\hbox{\vrule height5.8pt depth2.5pt width0pt}}
\def\smallcirc{{\scriptstyle\circ}}
\def\ssbullet{{\scriptscriptstyle\bullet}}
\def\symmdiff{\triangle}
\def\thicken#1{#1\hskip0.03em\llap #1\hskip0.03em\llap
#1\hskip0.03em\llap #1}
\def\Tau{{\text{T}}}
\def\tbf#1{\text{\bf #1}}
\def\terror#1#2#3{#1: `#2' for `#3'}
\def\today{\number\day.\number\month.\number\year}
\def\UEMDRR{University of Essex Mathematics Department Research Report}
\def\UEMDWP{University of Essex Mathematics Department Working Paper}
\def\versiondate#1{
\immediate\write0{Version of #1}
\def\vsdate{#1}
\ifnum\stylenumber=1\hfill Version of #1
\medskip
\else\ifnum\stylenumber=2\hfill Version of #1
\medskip
\else\ifnum\stylenumber=6\hfill{\fiverm Version of #1}
\medskip
\else\ifnum\stylenumber=7\hfill{\fiverm Version of #1}
\medskip
\else\ifnum\stylenumber=8\hfill Version of #1
\medskip
\else\fi\fi\fi\fi\fi}
\def\versionhead{\ifnum\stylenumber=3 \hfill PRINTER'S VERSION
\bigskip
\else\ifnum\stylenumber=4 \hfill REFEREE'S VERSION
\bigskip
\else \fi\fi}
\def\versionref{\ifnum\stylenumber=1\workingref
\else\ifnum\stylenumber=2\workingref
\else\ifnum\stylenumber=8\workingref
\else\printerref\fi\fi\fi}
\def\vthsp{\hskip0.001em}
%Missing AmSTeX can be coped with by using the following lines:
\ifamstexsupported\else
\immediate\write0{AmSTeX-unsupported version of fremtex.tex }
\fourteensavailablefalse
\def\@{@}
\def\\{\cr}
\def\AmSTeX{AmS\TeX}
\def\Bbb#1{\underline{\hbox{\bf #1}}}
\def\biggerscriptfonts{}
\def\bumpeq{=_{\text{approx}}}
\def\Cal#1{{\cal#1}}
\def\curlyeqprec{\preceq}
\def\eightit{\it}
\def\eightrm{\rm}
\def\eightsmc{\smc}
\def\eurm#1{\underline{\cal#1}}
\def\Footnote#1#2{\footnote#1#2}
\def\frac#1#2{{#1}\over{#2}}
\def\frak#1{{\hbox{\bf #1\hskip0.1em\llap #1}}}
\def\frnewpage{\vfill\eject}
\def\iint{\int\!\!\!\int}
\def\iiint{\int\!\!\!\int\!\!\!\int}
\def\iiiint{\int\!\!\!\int\!\!\!\int\!\!\!\int}
\def\llcorner{\lfloor}
\def\loadeurm{}
\def\loadeusm{}
% \def\loadeusmx#1{\def\eusm#1{\underline{\cal#1}}}
\def\ltimes{|\hskip-0.5em\times}
\def\eusm#1{\underline{\cal#1}}
\def\ltimes{|\times}
\def\Loadfont#1{}
\def\Matrix#1{\pmatrix{#1}}
\def\noamslogo{}
\def\nrightarrow{\not\rightarrow}
\def\preccurlyeq{\preceq}
\def\query{\discrversionA{\immediate\write0{query}
\footnote{$^*$}{query}}{}}
\def\restriction{|}
\def\rtimes{\times|}
\def\setover#1#2{#2^{#1}}
\def\shortstrut{\strut}
\def\smallerfonts{\eightrm}
\def\smallfrown{\wedge}
\def\smc{}
\def\spcheck{\check{\phantom{x}}}
\def\sphat{\hat{\phantom{x}}}
\def\square{\mathchoice\sqr64\sqr64\sqr43\sqr33}
\def\sqr#1#2{{\vcenter{\vbox{\hrule height.#2pt
\hbox{\vrule width.#2pt height#1pt \kern#1pt
\vrule width.#2pt}
\hrule height.#2pt}}}}
\def\pmb#1{\underline{#1}}
\def\text#1{\hbox{#1}}
\def\therefore{\ssbullet\raise.9ex\hbox{$\ssbullet$}\ssbullet}
\def\twelvebf{\bf}
\def\vartriangleleft{\triangleleft}
\def\Vdash{|\vdash}
\def\vDash{|=}
\fi
%End of lines for missing AmSTeX
\ifamstexsupported\input amstex
% \documentstyle{amsppt}
\input amsppt.sty
\PSAMSFonts
\tenpoint
%\font\eightmsb=msym8
\font\eightmsb=msbm10
\font\eighteufm=eufm10 at 8 pt
\font\eighteurm=eurm8
\font\eighteusm=eusm8
\font\varseveneufm=eufm10 at 7 pt
\scriptfont\eufmfam=\varseveneufm
\def\=#1{{\accent"16 #1}}
\gdef\nopagenumbers{\NoPageNumbers}
\else\fi
\newcount\footmarkcount
\ifDHFamstexloaded
\loadmsBm
\def\eightBbb#1{{\fam\msBfam#1}}
\loadmsFm
\def\eightfrak#1{{\fam\msFfam#1}}
\else
\def\eightBbb#1{{\scriptstyle\Bbb#1}}
\def\eightfrak#1{{\scriptstyle\frak#1}}
\fi
\ifathome\athome\fi
%interword glue (\tenrm standard):
% (space) 3.333 + 1.667 - 1.111
% (,) 3.333 + 2.083 - 0.889
% (.) 4.444 + 5. - 0.370
%very odd fact: \discrversionA{2.}{} doesn't work,
% \discrversionA{ 2.}{} does
%The false line feed introduced by my Fortran programs, leading to
%a surplus ae at the top of the next page, seems to be associated
%with Fk(\032)3081 or something similar in the PostScript file.
%\fullsize
\smallprint
\atUEssex
\frfilename{n03j16.tex}
\versiondate{6.11.03/10.11.08}
%typos corrected from 6.11.03, names of picture files changed
\Centerline{\bf Fair rents}
\Centerline{\smc D.H.Fremlin}
\Centerline{\it University of Essex, Colchester, England}
\medskip
{\bf The problem} Seven students are sharing a house with seven
bedrooms. The total rent is fixed, and they have to agree on (i) the
rent for each bedroom (ii) an allocation of the rooms. Is there a
division of the rent, and an allocation of the rooms, such that every
student is satisfied with what she has, in the sense that (at the given
prices) she doesn't want to move to one of the other rooms?
Subject to appropriate conditions, the answer is `yes'.
\medskip
{\bf The model} Suppose we have $n$ bedrooms, where $n\ge 1$, and $n$
students. The set of possible rent divisions can be represented as a
set of vectors $\tbf{p}=(p_1,\ldots,p_n)$ where each $p_j$ is greater
than or equal to $0$, and $p_1+\ldots+p_n=1$; $p_j$ is the proportion
of the total rent assigned to room $j$. The set of possible room
allocations can be represented by the set $S_n$ of permutations of
$\{1,\ldots,n\}$; $\rho\in S_n$ corresponds to the allocation in which
each student $i$ gets the room $\rho(i)$. For $1\le i,\,j\le n$, let
$C_{ij}$ be the set of prices $\tbf{p}$ under which student $i$ would
find room $j$ acceptable, in the sense that no other room would be
positively preferred at those prices.
\medskip
{\bf The theorem} Let $P$ be the set of all real $n$-vectors $\tbf{p}$
such that $p_1+\ldots+p_n=1$ and $p_j\ge 0$ for every $j$. For
$1\le i,\,j\le n$ let $C_{ij}$ be a subset of $P$. Suppose that
\inset{(i) $C_{i1}\cup\ldots\cup C_{in}=P$ for every $i$;
(ii) every $C_{ij}$ is closed.}
\noindent Then there are $\tbf{p}\in P$ and $\rho\in S_n$ such that
\inset{($\dagger$) $\tbf{p}\in C_{i,\rho(i)}$ for every $i$ such that
$p_{\rho(i)}>0$.}
\medskip
{\bf Interpretation of the clauses (i), (ii) and ($\dagger$)} (i) says
just that for any
student $i$, and for any price vector $\tbf{p}$, there is at least one
acceptable room; the student won't abandon the group and go to live
elsewhere if given her choice of room at those prices.
(ii) says that if you have a price vector $\tbf{p}$ which is {\it not}
in $C_{ij}$, so that student $i$ would definitely resent being given
room $j$ at that price, and you vary $\tbf{p}$ to a nearly identical
vector $\tbf{p}'$, then she will still reject the room at the price
$\tbf{p}'$. As the price vector moves around $P$, we expect the
student's preferred rooms to change; the assumption (ii) is that at
the switch points she will accept any of the rooms which she would have
accepted at prices close to the switch point.
As for the conclusion, ($\dagger$) says that anyone who doesn't like the
result can walk out without the others having to pay extra. If, for
instance, one of the rooms has a dead rat under the floor, there may be no way of making the occupant happy; but we can ensure that at least the paying residents are content with what they've got.
\medskip
{\bf A scrap of notation} It will save space if I write
\Centerline{$C'_{ij}=C_{ij}\cup\{\tbf{p}:\tbf{p}\in P$, $p_j=0\}$}
\noindent for $i$, $j\le n$. Note that $C'_{ij}$ is closed, because
$C_{ij}$ is. Also ($\dagger$) can now be re-phrased as
`$\tbf{p}\in C'_{i,\rho(i)}$ for every $i$'.
\medskip
{\bf Strategy of the proof} The proof is in two main stages. The
first, algebraic-geometric, step is to show (using assumption (i) only) that, for any $\delta>0$, we can find a permutation
$\rho\in S_n$ and price vectors $\tbf{p}^{(1)},\ldots,\tbf{p}^{(n)}$,
all within $\delta$ of each other, such that
$\tbf{p}^{(i)}\in C'_{i,\rho(i)}$ for every $i$. Then a limiting
argument, using assumption (ii), will show that we can find a fixed
$\rho$ and a single vector $\tbf{p}$ such that
$\tbf{p}\in C'_{i,\rho(i)}$ for every $i$.
\medskip
{\bf The distance between two price vectors} I said above that I should
be looking for price vectors `within $\delta$ of each other'. This
doesn't make sense without a notion of distance between members of $P$.
Lots of formulae can be used here, and (for interesting reasons) it
won't matter which we choose; but the pictures will be more helpful,
and the calculations easier, if I say that the
distance $d(\tbf{p},\tbf{q})$ between two price vectors $\tbf{p}$ and
$\tbf{q}$ will be $\sqrt{\sum_{i=1}^n(p_i-q_i)^2}$, matching ordinary
Euclidean distance in two or three dimensions.
\medskip
{\bf Step 1: part A} The set $P$ can be thought of as an
$n-1$-dimensional {\bf simplex} with $n$ {\bf vertices}. The vertices
are the $n$ points at which we have $p_j=1$ for some $j$, that is, all
the rent is loaded onto one of the rooms; opposite each vertex is a
{\bf facet} on which $p_j=0$; the facet is itself an
$n-2$-dimensional simplex. In one dimension, that is, when $n=2$, we
have a line segment; in two dimensions ($n=3$), a triangle; in three
dimensions ($n=4$) a tetrahedron. Our first task is to subdivide $P$
into smaller simplexes, all of diameter at most $\delta$, and
simultaneously to assign each vertex of the subdivision to a student in
such a way that every small simplex has every vertex assigned to a
different
student. (For the moment we are simply ignoring the students'
preferences. Those will turn up in part B.) We can do this by the
following procedure. Start with the subdivision $\Cal K_0$ consisting
of the simplex $P$ alone, and assign each of the vertices of $P$ to a
different student. Next, given a subdivision $\Cal K_r$ in which every
simplex has all its vertices assigned to different students, take (one
of) the longest edge(s) in the complex and divide it in three equal
parts. Suppose the edge runs from $\tbf{v}$ to $\tbf{w}$; let
$\tbf{x}$ and $\tbf{y}$ be the intermediate points, so that $\tbf{v}$,
$\tbf{x}$, $\tbf{y}$ and $\tbf{w}$ are in order along the edge. Assign
the new vertex $\tbf{x}$ to the same student who has vertex $\tbf{w}$,
and the new vertex $\tbf{y}$ to the same student who has vertex
$\tbf{v}$. Take each simplex $Q$ of the subdivision $\Cal K_r$ which
has $\tbf{v}$ and $\tbf{w}$ for two of its vertices and cut it into
three smaller simplexes $Q'$, $Q''$ and $Q'''$; if $Q$ has vertices
$\tbf{v},\tbf{w},\tbf{u}^{(1)},\ldots,\tbf{u}^{(n-2)}$, then
\Centerline{$Q'$ will have vertices
$\tbf{v},\tbf{x},\tbf{u}^{(1)},\ldots,\tbf{u}^{(n-2)}$,}
\Centerline{$Q''$ will have vertices
$\tbf{x},\tbf{y},\tbf{u}^{(1)},\ldots,\tbf{u}^{(n-2)}$,}
\Centerline{$Q'''$ will have vertices
$\tbf{y},\tbf{w},\tbf{u}^{(1)},\ldots,\tbf{u}^{(n-2)}$.}
\noindent In this way we obtain a subdivision $\Cal K_{r+1}$ in which
every student still owns just one vertex of each simplex. So long as
we always split the longest edge at each stage, we can be sure that
every edge will be split, and for large enough $r$ all the simplexes of
$\Cal K_r$ will be very small\footnote{see Appendix 1}.
I give diagrams of a couple of stages in the process if $n=3$, so that
$P$ is an equilateral triangle. I have decorated the vertices to indicate their owners.
\ifdim\pagewidth>400pt
\startsideshiftedpicture
\sideshiftedpicture{n03j16a}{10pt}{200pt}{173pt} %formerly rd2.ps
\sideshiftedpicture{n03j16b}{10pt}{200pt}{173pt} %formerly rd27.ps
\else
\startsideshiftedpicture
\sideshiftedpicture{n03j16a}{10pt}{141pt}{122pt} %formerly rd2.ps
\sideshiftedpicture{n03j16b}{10pt}{141pt}{122pt} %formerly rd27.ps
\fi
\medskip
{\bf Step 1: part B} Having got our subdivision $\Cal K_r$ and an
assignment of each vertex $\tbf{v}$ of $\Cal K_r$ to a {\it student}
$f(\tbf{v})$ where $1\le f(\tbf{v})\le n$, choose a {\it room}
$g(\tbf{v})$ for each vertex, as follows. If $\tbf{v}$ is in the
interior of $P$, that is, if $v_j>0$ for every $j$, then take
$g(\tbf{v})$ such that $\tbf{v}\in C_{f(\tbf{v}),g(\tbf{v})}$; this is
possible by condition (i). Otherwise, there must be at least one
$j\le n$ such that $v_j=0$ but $v_{j^+}>0$, where $j^+=j+1$ if $j1$, $n$ if $j=1$; while
$v_j=0$ so $g(\tbf{v})\ne j^-$.)
At this point I need to call on a remarkable fact which is the key to
the whole proof.
\medskip
{\bf Sperner's Lemma} ({\smc Sperner 28}) Let $P$ be an
$n-1$-dimensional simplex, where $n\ge 2$, and
$\Cal K$ a subdivision of $P$; write $V$ for the set of vertices of
$\Cal K$. Suppose we have a function $g:V\to\{1,\ldots,n\}$ such that
\inset{($\ddagger$) whenever $v^*$ is a vertex of $P$, and $v\in V$ lies
in the facet of $P$ opposite $v^*$, then $g(v)\ne g(v^*)$.}
\noindent Let $\Cal L$ be the set of simplexes $K$ of $\Cal K$ such that
$g$ takes a different value on each vertex of $K$. Then $\Cal L$ has
an odd number of members.
\medskip
\noindent{\bf proof} Induce on $n$.
\medskip
\quad{\bf base step} If $n=2$, so that $P$ is just a line segment, then
$\Cal K$ must be just a dissection of $P$ into intervals, and the
vertices of $\Cal K$ are points spread along $P$.
Now we are told that $g$ takes just the values $1$ and $2$ and
that it takes different values at the two ends, as
\picture{n03j16c}{50pt}
\noindent So $g$ must switch
values an odd number of times (five, in the example here) as we move from one end to the other; and
each switch corresponds to a member of $\Cal L$.
\medskip
\quad{\bf inductive step} Suppose that we know that the result is true
for $n$, and that we are given an $n$-dimensional simplex $P$, with a
subdivision $\Cal K$ and a function from the vertices of $\Cal K$ to
$\{1,\ldots,n+1\}$ satisfying the condition ($\ddagger$). Then
whenever we have two vertices of $P$, each lies in the facet opposite
the other, so $g$ takes a different value on each vertex, and (because
$P$ has $n+1$ vertices) $g$ takes every value just once. Let $v^*$ be
the vertex of $P$ such that $g(v^*)=n+1$, and let $P'$ be the facet of
$P$ opposite $v^*$. Then $\Cal K$ traces out a subdivision $\Cal K'$
of $P'$ (the simplexes of $\Cal K'$ are those facets of the simplexes of
$\Cal K$ which lie in $P'$). The vertices of $\Cal K'$ are just the
vertices of $\Cal K$ which lie in $P'$, and for every such vertex $v$ we
have $g(v)\ne n+1$, that is, $g(v)\le n$. So the restriction of $g$ to
the set $V'$ of vertices of $\Cal K'$ is a function from $V'$ to
$\{1,\ldots,n\}$. Moreover, if $v$ is a vertex of $P'$ and $v'\in V'$
lies in the facet of $P'$ opposite $v$, then $v$ is a vertex of $P$ and
$v\in V$ lies in the facet of $P$ opposite $v$, so $g(v')\ne g(v)$;
thus $g\restr V'$ satisfies ($\ddagger$). By the inductive hypothesis,
the set $\Cal L'$ of simplexes in $\Cal K'$ such that $g$ takes a
different value on each vertex, has an odd number of members.
Now turn back to the subdivision $\Cal K$. Say that a facet of a
simplex in $\Cal K$ is a {\bf door} if $g$ takes all the values
$1,\ldots,n$ on the $n$ vertices of that facet. Consider the set $R$
of pairs $(K,K')$ where $K$ is a simplex of $\Cal K$, $K'$ is a facet of
$K$ and $K'$ is a door. Given a door $K'$,
\inset{----- if it lies in the interior of $P$ there are just two
simplexes $K\in\Cal K$ such that
$(K,K')\in R$, one on each side of $K'$;
----- if it lies in the boundary of $P$ then it is a facet of just one
simplex of $\Cal K$, and belongs to $\Cal L'$. \Prf\ For every vertex
$v$ of $P'$, $g(v)\le n$ is equal to $g(v')$ for some vertex $v'$ of
$K'$, so $v'$ cannot be in the facet of $P$ opposite $v$. Thus the
facet of $P$ including $K'$ must be $P'$, and $K'\in\Cal L'$.\ \Qed}
What this shows is that $\#(R)\equiv\#(\Cal L')$ mod 2, and $\#(R)$ is
odd. On the other hand, looking at the relation $R$ from the other
side, take a simplex $K$ in $\Cal K$. Then
\inset{----- if $g$ takes all the values $1,\ldots,n+1$ on the vertices
of $K$, that is, $K\in\Cal L$, then exactly one facet of $K$ is a door;
----- if $g$ takes the values $1,\ldots,n$ on the vertices of $K$, but
not the value $n+1$, then exactly two facets of $K$ are doors (being the
facets of $K$ opposite the two vertices of $K$ on which $g$ takes the
same value);
----- in all other cases, $K$ has no doors.}
\noindent So $\#(R)\equiv\#(\Cal L)$ mod 2 and $\#(\Cal L)$ is odd. Thus
the induction proceeds.
\medskip
{\bf Step 1: part C} Returning to the main argument, we see that the
function $g$ constructed in part B satisfies the conditions of Sperner's
Lemma. So there must be an odd number of simplexes in $\Cal K_r$ on
whose vertices $g$ takes every value; in particular, there is at least
one; call it $K$. But now observe that (by the construction in part
A) $f$ also takes every value on the set $V_K$ vertices of $K$. So
$f\restr V_K$ and $g\restr V_K$ and
$\rho=g\frsmallcirc(f\restr V_K)^{-1}$ are bijections; and if $i\le n$
and $\tbf{p}^{(i)}\in V_K$ is such that $f(\tbf{p}^{(i)})=i$, then
$\tbf{p}^{(i)}\in C'_{i,\rho(i)}$. Thus we have price vectors
$\tbf{p}^{(1)},\ldots,\tbf{p}^{(n)}$ as called for, and Step 1 is
complete.
\medskip
{\bf Step 2} We can perform Step 1 for any $\delta>0$. In particular,
suppose we have done it for $\delta=2^{-k}$ for each $k$, obtaining
permutations $\rho_k$ and price vectors $\tbf{p}^{(k,i)}$ such that
\Centerline{$\tbf{p}^{(k,i)}\in C'_{i,\rho_k(i)}$,
\quad$d(\tbf{p}^{(k,i)},\tbf{p}^{(k,j)})\le 2^{-k}$}
\noindent whenever $k\in\Bbb N$ and $1\le i\le n$. By the
Bolzano-Weierstrass theorem\footnote{see Appendix 2.} we can find a
strictly increasing sequence $\sequence{l}{k_l}$ such that
\Centerline{$\lim_{l\to\infty}p^{(k_l,i)}_j=p^{(i)}_j$ for all $i$,
$j\le n$,}
\Centerline{$\lim_{l\to\infty}\rho_{k_l}(i)=\rho(i)$ for all $i\le n$.}
\noindent Because
\Centerline{$|p^{(k_l,i)}_j-p^{(k_l,i')}_j|
\le d(\tbf{p}^{(k_l,i)},\tbf{p}^{(k_l,i')})\le 2^{-k_l}\le 2^{-l}$}
\noindent for all $i$, $i'$, $j$ and $l$, $p^{(i)}_j=p^{(i')}_j=p_j$ say
for all $i$, $i'$ and $j$, and we have a single limit price vector
$\tbf{p}$. Because every $\rho_{k_l}(i)$ is an integer, so is every
$\rho(i)$, and there is an $l_0$ such that $\rho_{k_l}(i)=\rho(i)$
whenever $l\ge l_0$ and $i\le n$; that is, $\rho=\rho_{k_l}\in S_n$ for
every $l\ge l_0$. This means that
\Centerline{$\tbf{p}^{(k_l,i)}\in C'_{i,\rho_l(i)}=C'_{i,\rho(i)}$}
\noindent for every $l\ge l_0$ and $i\le n$. But now recall hypothesis (ii) of the theorem: every $C_{ij}$, and therefore every $C'_{ij}$, is closed. So
$\tbf{p}=\lim_{l\to\infty}\tbf{p}^{(k_l,i)}\in C'_{i,\rho(i)}$ for each
$i$, and $\tbf{p}$ and $\rho$ satisfy ($\dagger$).
\medskip
{\bf Practicalities} Unfortunately, while the theorem guarantees that a
solution to the original problem exists, the proof does not give us a
clear idea of how to find it. Step 1 is reasonably `constructive';
that is, given $\delta>0$, and provided that the students can decide what they want at any particular price without dithering, we can follow
doors to find appropriate simplexes by asking at most one question for
each vertex of $\Cal K_r$, and generally much fewer. (We start on the
edge of $P$ joining the vertices at which $p_2=1$ and $p_3=1$, so that
the values of $g$ are $1$ and $2$, and look for a pair of adjacent
vertices of $\Cal K_r$ on which $g$ changes. This now gives us a door
at dimension 1 from which we can look for a triangle in the face
$\{\tbf{p}:p_j=0$ unless $j=2$, $3$ or $4\}$ on which $g$ takes all
three values $1$, $2$ and $3$; this is a door at dimension 2 from which
we look for a tetrahedron which will be a door at dimension 3, and so
on.) The problem is that while this (together with the calculations in
Appendix 1) gives us a way to specify in advance how much data we shall
need in order to get an approximate solution
$\tbf{p}^{(1)},\ldots,\tbf{p}^{(n)}$ of neighbouring vectors with
$\tbf{p}^{(i)}\in C'_{i,\rho(i)}$ for every $i$, it doesn't tell us
anything about how the successive approximate solutions will be spread
around $P$, and leaves open the possibility that the approximation we
get for $\delta=10^{-6}$ is half way across $P$ from any approximation
valid for $\delta=10^{-7}$. So if your friends want to get a computer
to allocate rooms for them, they had better agree in advance that they
don't care about odd pennies, and that close enough will be good enough.
On the other hand, the theorem does assure you that if after an evening
of wrangling you seem nowhere near a solution acceptable to everyone,
it's either because someone is being obstructive (by refusing to name a
preferred room at some price), or because someone is jumping at trifles
(by refusing to accept a limiting solution when they accepted the
approximations), or because you're looking in the wrong part of $P$.
\medskip
{\bf Something you might have noticed} The argument here does {\it not}
suppose that people are consistent in their choices. It allows someone
to say, for instance, that at price vector $\tbf{p}$ only room $j$ will do, but that at price vector $\tbf{q}$, with $q_jp_k$, only room $k$ will do. Ordinarily this would seem very odd. But of course this
is because we are talking of {\it monetary} rents, and (by definition)
money is what you can't have too much of. If payments were in
cabbages, you might feel that under certain circumstances you would be
glad to have the landlord take some more.
For other `envy-free allocation' problems see {\smc Su 99}, from which
most of the ideas above are cribbed.
\bigskip
{\bf Appendix 1: the subdivision process in step 1, part A} I said that
`for large enough $r$ all the simplexes of
$\Cal K_r$ will be very small'. Perhaps a little more explanation is
called for. The problem is that when we move from $\Cal K_r$ to
$\Cal K_{r+1}$, the original edge $(\tbf{v},\tbf{w})$ is divided into
definitely shorter pieces, but we simultaneously introduce many new
edges $(\tbf{u},\tbf{x})$ and $(\tbf{u},\tbf{y})$ without looking at
their lengths, and we had better make sure that they too are usefully
shorter than $(\tbf{v},\tbf{w})$. In fact, if the edge
$(\tbf{v},\tbf{w})$ has length $c$, that is, $d(\tbf{v},\tbf{w})=c$,
then the new edges all have length at most $c\sqrt{\bover79}$. \Prf\
Of course
\Centerline{$d(\tbf{v},\tbf{x})=d(\tbf{x},\tbf{y})=d(\tbf{y},\tbf{w})
=\Bover{c}3\le c\sqrt{\bover79}$.}
\noindent As for $d(\tbf{u},\tbf{x})$, consider the triangle
$(\tbf{u},\tbf{v},\tbf{w})$; set $a=d(\tbf{u},\tbf{v})$,
$b=d(\tbf{u},\tbf{w})$, $B=\widehat{\tbf{u}\tbf{v}\tbf{w}}$ and
$s=d(\tbf{u},\tbf{x})$. Then the cos rule tells us that
\Centerline{$s^2=a^2+\Bover{c^2}9-\Bover{2ac}3\cos B$,
\quad$b^2=a^2+c^2-2ac\cos B$.}
\noindent Eliminating $\cos B$, we get
\Centerline{$s^2=\Bover23a^2+\Bover13b^2-\Bover29c^2$.}
\noindent But $a$, $b\le c$, because $c$ is (one of) the longest edge(s) of $\Cal K_r$, so $s^2\le\bover79c^2$ and $s\le c\sqrt{\bover79}$. Similarly, $d(\tbf{u},\tbf{y})\le c\sqrt{\bover79}$.\ \Qed
For each $r$, let $c_r$ be the length of the longest edge in $\Cal K_r$,
so that $\sequence{r}{c_r}$ is a non-increasing sequence and has a limit
$c^*$ say. Then $c^*\le c_r\sqrt{\bover79}$ for every $r$. \Prf\ Let
$m$ be the number of edges of $\Cal K_r$ of length greater than
$c_r\sqrt{\bover79}$. Then each of the moves
$\Cal K_r\to\Cal K_{r+1}\to\Cal K_{r+2}\to\ldots$ will subdivide one of
these edges until they have all gone (because all the new edges introduced will have length at most $c_r\sqrt{\bover79}$). So after $m$ moves, when we have reached $\Cal K_{r+m}$, they will all have disappeared. Now
$c^*\le c_{r+m}\le c_r\sqrt{\bover79}$.\ \QeD\ As $r$ is arbitrary,
$c^*\le c^*\sqrt{\bover79}$ and $c^*=0$.
\medskip
{\bf Remarks} The following questions arise in this context.
1. The set $P$ of price vectors, as described above, is a regular
$n-1$-dimensional simplex; all its edges are the same length $\sqrt 2$. The simplexes in $\Cal K_r$ come in many different shapes; I believe that, as $r$ increases, we get new shapes at each level (except, of course, in the trivial cases $n=1$ and $n=2$). What restrictions are there on the
shapes of the simplexes which appear? It is easy to see that for any
simplex $K$ in any $\Cal K_r$, the ratio of the longest side to the
shortest side is at most $3$. But is there (for given $n$) a non-zero lower bound to the angles of the triangles which appear?
2. Even if the process described here gives
indefinitely thin triangles as the subdivision proceeds, is there some
alternative way of subdividing a simplex into small simplexes for which
thin triangles do not appear, but there is still a way to assign
ownership of the vertices so that every small simplex is shared between
all $n$ owners? Note that if $n=3$ this is easy, using equilateral
triangles throughout, starting with
\ifdim\pagewidth>400pt
\startsideshiftedpicture
\sideshiftedpicture{n03j16d}{10pt}{200pt}{173pt} %formerly rd2-4.ps
\sideshiftedpicture{n03j16e}{10pt}{200pt}{173pt} %formerly rd2-16.ps
\else
\startsideshiftedpicture
\sideshiftedpicture{n03j16d}{10pt}{142pt}{122pt} %formerly rd2-4.ps
\sideshiftedpicture{n03j16e}{10pt}{142pt}{122pt} %formerly rd2-16.ps
\fi
\medskip
\noindent But this method doesn't work for a tetrahedron.
3. More advanced still, we have the following. Suppose we start with
an equilateral triangle and use the trisection method to generate
subdivisions $\Cal K_r$ as above. For large $r$, we have an abundant
collection of triangles, and we can ask for the {\it distribution} of
their shapes. Here the `shape' of a triangle is most naturally
described by a triple $(\theta,\phi,\psi)$ where
$\theta\ge\phi\ge\psi\ge 0$ and $\theta+\phi+\psi=\pi$; the set of
shapes is itself a triangle $T$ in three-dimensional space.
[Alternatively, we can describe it by a pair $(a,b)$ such that
$0\le b\le a\le 1\le a+b$, taking the side lengths of the triangle to be
$1\ge a\ge b$. This is easier to generalize to higher dimensions.] I
conjecture that there is a well-defined probability measure $\nu$ on $T$
which is the limit, as $r\to\infty$, for the narrow topology, of the
`empirical' measures $\nu_r$, where $\nu_r$ gives a mass to each point
in $T$ equal to the proportion of triangles in $\Cal K_r$ with that
shape.
\medskip
{\bf Appendix 2: the Bolzano-Weierstrass theorem} This is the
following:
\inset{\noindent If $\sequence{k}{\tbf{x}^{(k)}}$ is a sequence in
$m$-dimensional Euclidean space which is {\bf bounded} in the sense that
there is some $M$ such that $|x^{(k)}_i|\le M$ for every $k\in\Bbb N$
and every $i\le m$, then it has a subsequence
$\sequence{l}{\tbf{x}^{(k_l)}}$ which is {\bf convergent} in the sense
that $x_i=\lim_{l\to\infty}x^{(k_l)}_i$ is defined for every $i\le m$.}
\noindent The standard proof is by induction on $m$; see almost any
first course in analysis except my own. In the application here (Step
2 above), we need all the $p^{(k_l,i)}_j$ and all the $\rho_{k_l}(i)$ to
converge, so we are working with $m=n^2+n$.
\bigskip
\noindent{\bf References}
Sperner E.\ [28] `Neue Beweis f\"ur die Invarianz der Dimensionzahl und des Gebietes', Abh.\ Math.\ Sem.\ Univ.\ Hamburg 6 (1928) 265-272.
Su F.E.\ [99] `Rental harmony: Sperner's lemma in fair division',
Amer.\ Math.\ Monthly 106 (1999) 930-942.
\end