%(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\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\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
}}
\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}
\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}
\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}$}}
\def\Caption{}
\def\Center#1{
\Centerline{#1}
\noindent}
\def\Centerline#1{\vskip 5pt
{\def\int{\text{}$$\textfont3=\twelveex\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{}$, $\comment{}$} must use \sumop etc
\def\cf{\mathop{\text{cf}}}
\def\circumflex#1{{\accent"5E #1}}
\def\closeplus{\hbox{+}}
\def\coint#1{\left[#1\right[}
\def\curl{\mathop{\text{curl}}}
\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{\,\hbox{\vrule height7pt width0.5pt depth0pt
\vrule height0.5pt width5pt 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\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}
\PSAMSFonts
%\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.
%\input fremtex
%\fullsize
\smallprint
\frfilename{n05725.tex}
\versiondate{29.7.05}
\def\zz{}
\Centerline{\bf A protocol for machine-based voting}
\Centerline{\smc D.H.Fremlin}
\Centerline{\it University of Essex, Colchester, England}
\medskip
{\bf\zz{1} Introduction} In this note I describe a protocol for
machine-based voting which is relatively immune to incompetent or
dishonest operation and to voter fraud. It is a minor development of the
protocol described in {\smc Vernitski 05}.
It is assumed that a democratic tradition or aspiration gives
real power to public opinion, to the point that a sufficient
scandal can force a new election, but that individual officials may not
always be honest and that unscrupulous local party organizers are to be
expected.
Five organizations A, B, C, D and E are required; it is
assumed that each individually may be untrustworthy but that the risk of
corrupt collaboration between any two organizations can be ignored. E is
responsible for organizing electoral rolls, communicating with voters and
administering polling stations;
B is responsible for the machines collecting votes;
A, C and D act in the background as coders.
\bigskip
{\bf\zz{2} The protocol}
Let $C=\{c_1,\ldots,c_m\}$ be the set of candidates
in (say) alphabetical order, and $N$ a set of
identifiers (I will speak as if it is a set of numbers) with
$\#(N)\gg\max(\#(V),m!)$ where $V$ is the set of voters. $V$ and
$c_1,\ldots,c_m$
are publicly known before the electoral process begins,
but $N$ is known only to A, B, C and D.
\quad{\it step 1}\quad A chooses an injective function $\phi:N\to N$ and a
set $N'\subseteq N$ with $\#(N')=\#(V)$, B
chooses a bijective function $\beta:N\to N$, C chooses a
bijective function $\gamma:N\to N$ and D chooses
a function $\delta:N\to S_m$, the set of permutations of
$\{1,\ldots,m\}$; none of these functions are divulged to anyone else
except as detailed below. All should be `random'; in particular,
$\delta^{-1}[\{\pi\}]$ should be large for every $\pi\in S_m$.
\quad{\it step 2}\quad B tells A what the function $\beta$ is;
C tells D what
the function $\gamma$ is; D tells A what the function $\delta\gamma$ is
(but {\it not} what the function $\gamma$ is); D tells B what the function
$\delta$ is; A tells B what $N'$ is. A opens a website which will
provide the list $(c_{\pi_n(1)},\ldots,c_{\pi_n(m)})$ to any enquirer
submitting a correct pair $(n,\phi(n))$.
\quad{\it step 3}\quad For each $n\in N'$, A calculates
$\pi_n=\delta\gamma\beta(n)\in S_m$ and sends the triplet
$(n,\phi(n),\pi_n)$ to E.
\quad{\it step 4}\quad E sends each voter a different triplet
$(n,\phi(n),\pi_n)$ in the form of the `voter number' $n$, a `check number'
$\phi(n)$ and
a list of the candidates in the order $c_{\pi_n(1)},\ldots,c_{\pi_n(m)}$.
\quad{\it step 5}\quad The actual election now takes place; each voter
sends B the pair $(n,j)$ where his voter number is $n$ and his
chosen candidate is $c_{\pi_n(j)}$.
\quad{\it step 6}\quad B collects the pairs
$(n,j)\in N'\times\{1,\ldots,m\}$ received from voters and
for each such pair sends the pair $(\beta(n),j)$ to C.
\quad{\it step 7}\quad C collects the pairs $(n',j)$ received from B and
for each such pair openly publishes the pair $(\gamma(n'),j)$.
\quad{\it step 8}\quad D reviews the pairs $(n'',j)$ published by C and for
each such pair publishes the pair $(n'',c_k)$ where
$k=\delta(n'')(j)$.
\quad{\it step 9}\quad The votes for each candidate
can now be calculated from D's published list,
since if the voter with number $n$ chooses candidate $c_i$ then
\qquad B receives $(n,\pi_n^{-1}(i))$
\qquad C receives $(\beta(n),\pi_n^{-1}(i))$
\qquad D receives $(\gamma\beta(n),\pi_n^{-1}(i))$ and publishes
$(\gamma\beta(n),c_k)$ where
\Centerline{$k=(\delta\gamma\beta(n))(\pi_n^{-1}(i))
=\pi_n\pi_n^{-1}(i)=i$.}
\bigskip
{\bf\zz{3} The basic defensive structure} Since nobody knows both the
functions $\beta$ and $\gamma$, nobody can associate a published result
$(n'',j,c)$ with any particular voter $v$, even if they have induced $v$ to
divulge his voter number.
C does not know the functions $\delta$ and $\beta$, so can affect the
output only by random distortions which will, on average, do no more than
narrow the gap between candidates. D's output at the critical step 8 will
be checked by B, and if he has given false values for
$\delta\gamma$ at step 2 this also will
merely add noise. B can bias the result, since he will know
the physical location of voters and can disenfranchise selected groups by
randomising or deleting their votes. He does not know the
permutation $\pi_n$ associated with a voter, so cannot know for sure what
the effect of his malfeasance is. (This is the reason for the
`checking number' $\phi(n)$; B should not be able to search A's website
systematically without it being obvious that something is going on.)
A has more scope, since he knows $\delta\gamma$ and can
arrange that votes for favoured candidates are correctly treated while
others are randomised, by providing false values of the $\pi_n$.
E can use the traditional methods of losing voter forms in the post or
blocking polling stations, but these are immediately detectable by voters.
He can send false values of $\pi_n$; but any suspicious voter
can detect this from A's website. He can duplicate voter forms, so that
opposition supporters appear to be voting twice, but this is picked up in
real time by B.
Concerning voter fraud,
attempts to vote twice and attempts to vote with home-made voter numbers
can be detected in real time by B.
\bigskip
{\bf\zz{4} Further checks (a)} Candidates will ordinarily know where their
support is concentrated. For this reason, it might be right to require A
to give each voter a `location' tag $l$, so that B
receives a triplet $(n,c',l)$, and C
receives the triplet $(\beta(n),c',l)$. As B will usually know the
location and time at which a vote was cast, he is getting little new
information from the tag. Actual publication of the
tag should be done by D, ordinarily publishing triplets $(n'',c_k,l)$,
but omitting tags in cases where the pair $(c_k,l)$ is repeated by too few
other votes. Candidates will then be able to see the locations from which
most of their votes
were gained, and can organize a protest if they feel cheated.
If it is felt undesirable for C to be told where voters live, a code
shared by B and D (e.g., a bijection from $L\times M$ to $N$,
where $L$ is the set of locations
and $M$ is a large set) can be used to isolate him from this information.
\medskip
{\bf (b)} There must be no mechanism for any voter to obtain official
confirmation that his individual vote was correctly handled, since any such
mechanism would open a method of coercion. However, a {\it block} of
voters, of sufficient size (at least 100 in each location from which they
come), could ask for a re-run of the process on their votes. The basic
method of protest against an apparently rigged election would be
to organize such a block of voters willing to repeat their votes in public.
B would be able to declare a
figure for the number who had changed their votes, and the same number
should appear from the final output.
If there were many of these, there would then be an ordinary row
about whether the voters were dishonest, or intimidated, or forgetful,
or whether B or C was cooking the result. If the declared vote derived
from D's output was different from the input, then it would be clear that
something had gone wrong with the system.
\medskip
{\bf (c)} If E were to send duplicate papers out, half of these would be
detected at voting time by B, and the voters notified. Complainants would
be able to advertise their numbers, so that if E has sent two identical
papers to members of opposition groups both will be presented, and he will
be reduced to claiming that one is a forgery. Similarly, if a voting
paper fails the test of A's website there will be something for an
opposition newspaper to publish.
\bigskip
{\bf\zz{5} General elections} No new ideas are needed to handle general
elections. If (as in the UK at present) electoral rolls are administered
locally, the part of E in the scheme here becomes divided between many
authorities; there is much to be said for them all following the same
format. The functions $\beta$, $\gamma$ and $\delta$ now
become functions of two variables, voter number and constituency;
only A and D really have to take any notice,
since the different constituencies
may have different numbers of candidates.
\bigskip
{\bf\zz{6} Practicalities} The following details are suggested as a minimal
change on the present UK system, but the ideas would I think be generally
applicable.
\medskip
{\bf (a)} The `polling card' each voter is sent before the election,
currently carrying name, address, polling station and electoral roll
number, would now have also have to have the voter's
numbers $n$ and $\phi(n)$, his list of candidates and (if applicable)
constituency and location tag. These should be
delivered in sealed envelopes. To avoid large numbers of
mistyped voter numbers, the voter number, constituency and
location tag should be in machine-readable form,
e.g., as a barcode, as well as in human-readable form.
\medskip
{\bf (b)} At present,
no identification beyond a declaration of name and address is
required in UK elections; even the polling card is not essential, as the
polling officers have the electoral register before them, and mark the
names of those who have voted. On the system described in this note,
electors would need to take polling cards to vote.
They would no longer be issued with ballot papers.
The voter would approach a machine with a screen, a
barcode reader and a number-pad, pass the barcode on the polling card over
the reader, and key in the number of the chosen candidate. The pair
$(n,j)$ would be displayed on the screen with a `confirm/cancel' option.
It would in my view be right to allow a `null' vote,
corresponding to a spoilt
ballot paper; this would pass through the system and be finally published
as $(n'',-)$ in both C's and D's lists.
\medskip
{\bf (c)} At present, ballot papers are punched, in the presence of the
voter, with an identifying code; this is I suppose a precaution against
forged ballot papers being slipped into the box under cover of a genuine
one. This would no longer be a concern. But a real danger in present UK
conditions is of an individual pressuring others to allow him to cast their
votes. Once he is in the polling booth it may be difficult for the
polling officers to be sure that a voter is voting only once. Some
mechanism - e.g., a plastic disk to tell the voter which machine to use,
and a button to tell the machine that one and only one vote is expected -
could, and probably should, be in place to check this.
\medskip
{\bf (d)} There would have to be provision for correcting misread barcodes.
Depending on the sophistication of the electorate, this could either be
open to ordinary voters, or require the intervention of a polling officer.
The polling officer would be responsible to the organization E, so there
would be no great breach of security in his seeing the voting number, as
long as he did not see the vote.
\medskip
{\bf (e)} If B detects double-voting, the natural response would be to put
both votes into limbo, and send the voter number and the times and
locations of the votes to E (but not, of course, the votes themselves).
E would then be
in a position to contact the voter and ask which, if either, of the votes
(identified by place and time) should be counted. I am suggesting this
only for the purpose of maintaining the morale of electors who are told
that they have already voted. If there were enough such cases to make a
difference enough people would know to make a scandal of it.
This is not quite the same as the phenomenon considered in \zz{4}c, where a
voter is protesting and E knows, or ought to know, that there is more than
one voter with that number.
\medskip
{\bf (f)} In the last couple of years, the UK has experimented with postal
voting. The results have not been satisfactory, and there have been many
accusations of stolen votes and mild coercion. In my view all voting
should be done in the presence of an official polling officer; in
particular, no form of on-line electronic voting should be considered.
We could, however, allow away-from-home voting, in ordinary polling
stations, subject to a tightening of the identification process; e.g.,
requiring driving licence or passport with name and address matching the
polling card. Even embassies and consulates abroad could be equipped with
voting machines to accept the votes of expatriates. Similarly, one can
imagine a travelling voting machine, accompanied by a polling officer,
for the use of those physically unable to attend a polling station.
\bigskip
{\bf\zz{7} Further remarks (a)}
Since the functions of A, C and D are purely
computational, they can easily be
performed by organizations which are independent to the point of being in
different continents. Because they have very little actual work to
do, organizations could be found
for which their reputations matter more than
the profit to be gained by repeat business from the same authorities.
\medskip
{\bf (b)} There is a greater vulnerability in the organization B. B would
have a local investment to protect, and local employees who might be
partisan. In one way, machines would be easier to guard than ballot boxes
because greater expertise would be required to manipulate them. On the
other hand, since they would (on the scheme suggested here) be on-line
during voting, there would in principle be a danger of interference from a
distance, and they had better have non-standard firewalls.
\medskip
{\bf (c)} In preparing these notes I have had in mind not just the UK
experience but what I have read recently about such places as the
Philippines and the Ukraine. Some of the original interest in improved
designs for machine voting came from the experience of the US presidential
election in 2000. But while a scheme such as this might have reduced the
time wasted and the bitterness engendered by court proceedings, it would
only by chance have made that result any more representative of the
people's will, as the margin between Bush and Gore in Florida
was less than the change to be expected if the vote had been held one day
earlier or later.
\bigskip
\noindent{\bf Reference}
Vernitski A.\ [05] `A simple protocol for voting', Technical Report 2005-2, Department of Mathematical Sciences, University of Essex, July 2005.
\end