% -*- Mode:TeX -*-

%NOTE: THERE ARE NUMEROUS COMMENTS HERE
%THAT WILL NOT APPEAR WHEN THE .DVI
%FILE IS CREATED, I.E., COMMENTS 
%MADE BY USE OF THE `%' CHARACTER.

% THE FOLLOWING FILE REPRESENTS THE SECOND BIG DRAFT OF
% THE PAPERTW.TEX PAPER (I.E., THE `TRAVELING WAVE' PAPER),
% THIS THEN IS THE `EXTRA TRAVELING WAVE PAPER).
% ITS COMPANION PAPER IS THE EXTRA PAPER1.TEX, VIZ. PAPER1E.TEX

% 1 em \approx 11 pt
% 1 ex \approx  4 pt
% 72.72 pt = 1in
%









\documentstyle[macpsfig]{article}

\input{hx/noteform.tex}
%\input{/a/aviary/psfig/lib/psfig.tex}
\def\sec#1{{{\partial^2}\over{\partial {#1}^2}}}                                      

\begin{document}
\input{hx/notecomm.tex}

\newcommand{\ram}{{\sc ram}}
\newcommand{\rom}{{\sc rom}}
\newcommand{\eprom}{{\sc eprom}}
\newcommand{\eeprom}{{\sc eeprom}}
\newcommand{\sci}{{\sc sci}}
\hyphenation{one-di-men-sion-al 
di-men-sion-al % 
wave-pack-et wave-pack-ets %
Klein-Gor-don}

%\title{ The Traveling Wave Decomposition of the $n$-Dimension\-al %
%  Discrete Wave Equation}
%\title{ Random Walk and Traveling Wave Decomposition of
%the $n$-Dimension\-al Wave Equation}
%The Traveling Wave Decomposition of the 
%$n$-Dimensional Discrete Wave Equation


\title{Discrete Representations of Wave Phenomena}


\author{Hrvoje Hrgov\v ci\'c}
\address{{\em Dept. of Physics}\\%
{\em  Massachusetts Institute of Technology}\\%
{\em Cambridge, Massachusetts 02139}}
\date{}

\maketitle

%\beginabstract}
{\begin{center}

\rule{.0ex}{0ex}
\end{center}}
{\sl Abstract:} A system of first order difference
equations on a rectangular $n$-di\-men\-sion\-al
lattice is presented, which
reduces to the wave equation in the continuum limit.
Because the $2n$ functions
correspond to motions in  positive and negative directions along
axes of the space, this system can be seen as
the  $n$-di\-men\-sion\-al generalization of 
the one-dimensional wave equation, whose solution may
be written as the sum of two traveling waves.
This approach allows solutions of the discrete wave equation
to be written as a surprisingly elementary summation over paths, 
suitable for implementation as a
cellular automaton (and in non-Euclideanized time), 
in analogy with the relationship
between random walks and the diffusion
equation.
Applications
to physics are discussed.
%\vspace{.6\baselineskip}
%\noindent{PACS number: 11.10.Qr}
\vspace{1.5\baselineskip}

Consider an $n$-di\-men\-sion\-al orthonormal lattice. One may
define functions on the {\it links\/} connecting
a point to its $2n$ nearest neighbors. 
For the purpose of the system of equations presented here,
the lattice points may be viewed as ``black boxes''
into which enter and from which exit $2n$ flows.
With this in mind,
let  $f^{\rm in}_{x_{i\pm}}({\bf x},t)$ denote
a link function defined on the link leading into
the point ${\bf x}$ at time $t$ from the
point $(\ldots, x_i\mp1,\ldots)$, and similarly,
let  $f^{\rm out}_{x_{i\pm}}({\bf x},t)$ denote
the function  defined on the links leading out of
the point ${\bf x}$ and into the point 
$(\ldots, x_i\pm1,\ldots)$. Obviously,
%
\begin{equation}
f^{\rm out}_{i\pm}(\ldots,x_i,\ldots,t)%
=f^{\rm in}_{i\mp}(\ldots,x_i\pm 1,\ldots,t)\ \ .
\label{eq:in-out}
\end{equation}

%
One can impose a dynamics on these functions.
In particular, consider the following system of equations:
\begin{equation}
\label{eq:two-dim-ass-2}
 f_\sigma^{\rm{out}} = \sum_{\sigma'}c_{\sigma,\sigma'}%
     f_{\sigma'}^{\rm{in}}\ {\rm ,}
\end{equation}
where $   \sigma,\sigma' \in \left\{x_{1_{+}}, {x_{1_{-}}}, %
        {x_{2_{+}}},{x_{2_{-}}},\ldots,{x_{n_{+}}},{x_{n_{-}}} \right\} $.
The coefficients of the 
transition matrix $c_{\sigma,\sigma'}$
are taken to be $1/n$ for all entries
except for those for which the indices represent opposing
directions, for which the coefficients
are set to $(1-n)/n$. For example, in three dimensions,
\begin{equation}
\left(\rule{-.5ex}{0ex}
\begin{array}{c} 
f_{x_{+}} \\
f_{x_{-}} \\                      
f_{y_{+}} \\ 
f_{y_{-}} \\
f_{z_{+}} \\ 
f_{z_{-}}%
\end{array}\rule{-.5ex}{0ex} %
\right)^{\rule{-.8ex}{0ex}\rm{out}}
\rule{-2.5ex}{0ex} ={1\over3}
\left(\rule{-1.2ex}{0ex}
\begin{array}{r@{\hspace{.7ex}}r@{\hspace{.7ex}}%
r@{\hspace{.7ex}}r@{\hspace{.7ex}}r@{\hspace{.7ex}}r} 
       1 & -2 &  1 &  1 &  1 &   1 \\
      -2 &  1 &  1 &  1 &  1 &   1 \\
       1 &  1 &  1 & -2 &  1 &   1 \\
       1 &  1 & -2 &  1 &  1 &   1 \\
       1 &  1 &  1 &  1 &  1 &  -2 \\
       1 &  1 &  1 &  1 & -2 &   1 %
\end{array}\rule{-.6ex}{0ex}
\right) 
\left(\rule{-.5ex}{0ex}
\begin{array}{c}
f_{x_{+}}\\
f_{x_{-}}\\
f_{y_{+}}\\
f_{y_{-}}\\
f_{z_{+}} \\ 
f_{z_{-}}%
\end{array}\rule{-.5ex}{0ex}
\right)^{\rule{-.8ex}{0ex}\rm{in}}\ {\rm .}
\rule{-1.2ex}{0ex} 
\end{equation}
%
It is easy to see that in any number of
dimensions, the transition matrix  is unitary and real.
%so that it is its own inverse. 
Furthermore,
all the coefficients in a given row add
up to one.
Thus, we are justified in referring to
the link functions as {\it flows\/} 
on the lattice.

Next, define the {\it point} function $\psi({\bf x},t)$ 
to bethe sum of flows
entering (or exiting) a given lattice point, that is,
\begin{equation}
\label{eq:two-dim-ass-1}
\psi({\bf x},t)\equiv \sum_\sigma f_{\sigma}^{\rm{in}}({\bf x},t) %
           = \sum_\sigma f_{\sigma}^{\rm{out}}({\bf x},t)\ . 
\end{equation}
Note that $\psi({\bf x},t)$  is defined as a function on the
{\it points\/} of the lattice
(i.e., not the links).
It is a matter of straightforward algebra
to show that  $\psi({\bf x},t)$ satisfies the
discrete wave equation,$^{1,3}$
%
\begin{equation}
{1\over c^2}\sec{t}\psi  = %
\left(\sec{x_1} + \sec{x_2} +\cdots+\sec{x_n}\right)\psi\ {\rm ,} \label{eq:wave}
\end{equation}
where the second order partial derivatives
of time and space appearing in the
D'Alembertian are replaced by their finite-difference analogues
$$
\sec{x_i}\psi(\ldots,x_i,\ldots) \equiv 
     \psi(\ldots,x_i + 1,\ldots)\rule{10ex}{0mm}\phantom{\ ,}$$
\begin{equation}
\label{eq:op-def} 
 - 2\psi(\ldots,x_i,\ldots)
 + \psi(\ldots,x_i - 1,\ldots)\ ,
\end{equation}
and where the speed of light is
given the value $c=\sqrt{1/n}$.  Note the cancellation of
all terms in the above equation 
corresponding to the central term
of the right-hand side of
(\ref{eq:op-def}). The result of
this cancellation is that
the spacetime is split into two 
causally separate lattices, even and odd,
%(Fig.~{\ref{fi:checkered-space}}).
with a spacetime point $({\bf x}, t)$ in the even (odd) sublattice
having the property that
$ t+ \sum_{i=1}^{n}x_i$
is even (odd). 


Recall that the general solution of the
one-di\-men\-sion\-al wave equation
may be written as a sum of
two functions, or traveling waves. The equations of motion
of these traveling waves, first-order in time and space, 
are simple translations in opposite directions with a constant speed.
The above system is thus seen as a discrete generalization of
this decomposition to higher dimensions,
since each link function implies a motion (positive or negative)
along the axes of the space.  Unlike the one-dimensional
case, where the traveling waves propagate independently of
one another, in higher dimensions there is a mixing, or
interaction,
among these modes of propagation.

A solution of the wave equation is completely determined
by fixing the values on the lattice
points at two successive time steps.
As shall now be shown, any point
solution
of the discrete wave equation may be
expressed in terms
of flows on the links between points.
It is useful in the present discussion
to think of the space as a torus of
period $4N$ in all directions,
with  the additional property that
%Assume for convenience that the lattice in question is actually
%a torus of length $4N$ in all spatial
%dimensions.
\begin{equation}
 \psi(\ldots,x_i,\ldots) =
        - \psi(\ldots,x_i + 2N,\ldots)\ {\rm .}
\end{equation}
(This
restriction is
imposed merely to remove the
zero-frequency and
other 
physically
uninteresting
solutions, e.g., linear polynomials
in space and time.)
%where the `$+$' sign in the expression
%$ x_i + 2N $ implies addition modulo $2N$.
%That is, the lattice space in question
%is toroidal, and
%a solution is completely determined
%by its boundary conditions on the subspace of points
%for which the $r_i$ range from 0 to $N-1$;
By making $N$ as large as necessary, 
the desired
generality is retained. 


Let $h_{x_{j\pm}}({\bf x}-{\bf x}_0)$
stand for the 
traveling wave (point) solutions 
that at $t = t_0$ 
are respectively zero everywhere except on the links
going out from the point $x_0$
to the points ${\bf x}_0\pm {\bf e}_j$, where they are 1, and where
the $i^{th}$ component of the vector ${\bf e}_j$ is equal to
$\delta_{ij}$, the Kronecker delta.
Such solutions, which will be called {\sl hodotic\/}
solutions (from the Greek word for ``path''), have many unusual 
properties, especially in higher dimensional systems.$^3$
%some of which will be discussed below.
For purposes of clarity, 
their time dependence has been suppressed.

A moment's thought will show
that these link solutions
correspond to the point solutions
which at $t=0$ are
equal to $\delta_{x,x_0}$
and at $t=1$ are respectively equal to $\delta_{x,x_0\pm1}$.
%where $\delta_{x,x'}$
%is the Kronecker delta.
%(Fig.~\ref{fi:one-dim-greens-function}). 
\begin{figure}
%\rule{.2pt}{13em}
\psfig{file=hx/twfig/twf-1d-gr-2.ps,height=.72in,width=3.0in}
$$\phantom{some  {\large empty} chatter fill}$$
%box is 7 1/4" by 3 1/4", lower left corner 1/4" 7 1/4"
%                         upper right corner 7 1/2" 10 1/2"
%Shows an arrangement of positive and negative flows that
%collectively yields a Green's function.
\caption{An arrangement of hodotic solutions that yields a
one-dimensional Green's function $G_{1}(x)$ for the discrete wave equation.
For higher dimensions, the above boundary conditions can
simply be imbedded in the higher dimensional space, with
zero values being assigned to all other points.}
\label{fi:one-dim-greens-function}
\end{figure}
%\begin{figure}
%\rule{.2pt}{13em}
%\caption{The boundary conditions corresponding to
%a hodotic solution.}\label{fi:mak-hod}
%\end{figure}
 On the
spaces in question, any solution of
the discrete wave equation
may be written as a sum of hodotic solutions.
In particular, it is easy to verify
that  in one dimension, the two functions
\begin{eqnarray}
\label{eq:gre-fun}
  G_{0}(x-x_{0}) ={1\over{2}}\sum_{x' = 0,2,\ldots}^{2N-2}
	\left\{ h_{+}(x - x_{0} - x'){\rm Sgn}(x-x_0)\right.\nonumber \\
\phantom{ G_{0}(x-x_{0}) ={1\over{2}}a} - %
\left.h_{-}(x- x_{0} - x'){\rm Sgn}(x-x_0-1)\right\} \nonumber 
\end{eqnarray}
and
\begin{eqnarray}
  G_{1}(x-x_{0}) ={1\over{2}}\sum_{x' = 0,2,\ldots}^{2N-2}
	\left\{-h_{+}(x - x_{0} - x'){\rm Sgn}(x'-x_0)\right.\nonumber \\
\phantom{ G_{0}(x-x_{0}) ={1\over{2}}a} + %
\left. h_{-}(x- x_{0} - x'){\rm Sgn}(x'-x_0)\right\}\ {\rm ,} \nonumber
\end{eqnarray}
where
$${\rm Sgn}(x)=\left\{\begin{array}{ll}
                       \phantom{-} 1& \mbox{if $x\geq 0$}\\
                       -1& \mbox{otherwise} {\rm ,} 
\end{array}\right. $$
have the property (Fig.~\ref{fi:one-dim-greens-function}) that at $t=0,1$,
\begin{eqnarray}
\label{eq:gre-fun-a}
  G_{0}(x-x_{0}) = & \delta_{x,x_0}\delta_{t,t_0}\nonumber\\
\\
  G_{1}(x-x_{0}) = & \delta_{x,x_0}\delta_{t,t_1}\nonumber
\end{eqnarray}
$$x, x_0=0,1,\ldots 2N-1\ {\rm .}$$
Again,  the time dependence has been suppressed.

It is clear that any solution of the 
one-dimensional discrete wave equation 
may be expressed as a linear combination
of the $G_0$ and $G_1$. 
These solutions
may simply be imbedded in higher dimensional
spaces to yield their higher dimensional analogues.
The hodotic solutions
are overcomplete, since in the above
expansion of the Green's functions, one
may increase all the $h_+(x - x_{0} - x')$ by some quantity $\alpha$,
decrease the $h_-(x - x_{0} - x')$ by the same quantity, and
obtain the same result.  This overcompleteness
is even more pronounced in higher dimensions.




Note that the Green's
functions require nonzero flows
across the entire space. Therefore, even
if the solution one wishes to simulate is initially
nonzero only in some localized subset
of the space, say, one that
can be covered by a line segment, or
in $n$ dimensions, an $n$-cube,  its expression 
in terms of the Green's functions
involves nonzero flows in a region
extending across the entire space. However,  
if this solution has the additional property
that 
the (discrete) integral of the amplitude over
the entire space is the same two successive times, then one can find an
arrangement of hodotic solutions that is also
nonzero only in that localized subspace.



%if desired, put in stuff labeled by ``GENERALIZED LATTICES'', below


The above results can be used to construct
a random walk model of wave phenomena for  which
a probabilistic cellular automaton or Monte Carlo
routine is used  to compute the solutions to the wave equation.$^{2,3}$

For example, the above results may be given a lattice
gas implementation. Suppose the lattice gas particles are
in one of two states, call them  positive and negative.
The transition matrix can then be interpreted
as a scattering matrix, whose
coefficients $c_{\sigma, \sigma'}$ give the probability
that a  lattice particle will be found in the $\sigma$
link 
given the presence of a single  particle in the $\sigma'$
link in the previous time step.
Negative matrix elements are taken to mean that the outgoing
particles have a state  opposite to that of
the corresponding incoming particles, whereas
positive matrix elements mean that the
output particles have the same phase as the
corresponding input particle. For convenience, the dynamics
may be such that positive and negative particles
created in any link mutually annihilate each other until particles
of only one state remain.
The outputs are to be generated independently
for each incoming particle, although other schemes will suffice
as well.

Just as in the case of diffusion,  where one can use the expected  number of
randomly walking particles found at a certain place and
time to simulate the diffusion equation, one may
use similar averaging methods over properly initialized
ensembles in order to obtain solutions of the
wave equation. Initial configurations of lattices
are assigned so that in any region of the space where the
amplitude of the solution is negative, only negative
particles will be found, with a  probability that is
proportional to the (suitably normalized) magnitude
of the wave solution.  The expected number of
`positive' particles minus the expected number of
`negative' particles then yields the desired solution.
Note that in contrast  to the case of diffusion,
the number of particles on the lattice
in this latter case is not constant, and given
the duplication of states,
negative as well as positive quantities are
obtained. However, just as in the diffusion
case, the amplitude may be written as a summation
over particle paths.

 This approach
is particularly well suited to the study of
quantum mechanics, and may be used to
construct a discrete model of quantum mechanics with
a dynamics that
has the advantage of being local in ordinary three-dimensional
space, regardless of the number
of single particle states being simulated.  In
fact, a simple modification of
the above dynamics allows one to simulate the
Klein-Gordon wave equation as well.$^3$
Moreover, time is nowhere Euclidianized.

Just as any solution of the
aforementioned wave equations may be written
as  summations over paths, the absolute squares of
these wave solutions can be written as a summation over
pairs of such paths.
Though the the terms in the latter summation
are in general nonpositive,
for any large simulation of events, the contribution
of the positive terms predominates.
The formalism is thus similar in some respects to
Wigner functions and other
generalized probability distributions$^4$.  In the
present case the resulting model of quantum mechanics is faithful
in the sense that any macroscopic individual who is himself
internal to the model  perceives events
just as the individuals in our universe do.






Support was provided in part by the National
Science Foundation, grant no. 8618002-IRI,
and in part by the Defense Advanced Research
Projects Agency, grant no. N00014-89-J-1988.




\vspace{.6\baselineskip}{\obeylines
\noindent {\large \bf References}\nopagebreak
\vspace{.3\baselineskip}\nopagebreak
}

\noindent$^1$R.~Courant, K.~Lewy, and O.~Friedrichs,
``On the Partial Difference Equations of Mathematical Physics'', originally
published in {\em Mathematische Annalen}, 1928, and translated into
English in the {\em IBM Journal}, March, 1967. 

\medskip
%
\noindent$^2$D.~Farmer, T.~Toffoli, S.~Wolfram, {\sl Cellular Automata\/},
(North-Holland, Am\-ster\-dam, 1984). 
T.~Toffoli and N.~Margolus,
{\sl Cellular Automata Machines, A New Environment for
Modeling\/}, MIT Press, Cambridge, Massachusetts, 1987.


\medskip

\noindent$^3$H.~Hrgov\v ci\'c, ``Random Walks and Traveling
Waves of the $n$-Dimensional Wave Equation'', and
``The Local Interpretation of Quantum Mechanics'',
MIT-LCS Technical Reports 440--441.




\medskip

\noindent$^4$M.~Hillery,
R.~F.~O'Connell, M.~O.~Scully, and E.~P.~Wigner,
{\it Physics Reports\/} (Review Section of Physics Letters) {\bf 106}, 121 (1984);
P.~A.~M.~Dirac, {\it Reviews of Modern Physics}, {\bf 17}, 195 (1945);  
R.~P.~Feynman, `Negative Probability'  in B.~J.~Hiley and F.~David Peat (eds.),
{\it Quantum Implications} (Routledge \& Kegan Paul, London, 1987).





\end{document}





























%********label 5

In closing, we mention that the hodotic solutions of
the wave equation possess several curious properties,
which may
easily established by
resorting to summations over paths.
Let $\sum_{\bf x} f({\bf x},t)$, be the
sum over all space of some function $f({\bf x},t)$ 
at some instant of time.  That is, it is a sum over
the point values (not the values on the links) of a given solution
of the wave equation.

It is easy to show from the equations
of motion that the hodotic solutions have the property
that $\sum_{\bf x} h_{\sigma}({\bf x};t)$ is equal to one for all time,
where $$\sigma \in \{ x_{1+},x_{1-},x_{2+},\ldots,x_{n-}\}\ \ .$$ 
This is a trivial consequence of the unitarity of the transition
matrix.
What is more remarkable is
that on any $n$-di\-men\-sion\-al torus whose
lengths along any of the coordinate axes are the same,
the quantity $\sum_{\bf x} h^2_{\sigma}({\bf x};t)$ over only
the lattice points is also equal to one for
all time.  In general, a sum of hodotic solutions,
does not possess this property. The proof is given elsewhere$^3$.

Also, an $n$-dimensional hodotic solution has
the  property
that at any time,
the support of the solution may
be imbedded in an $m$-dimensional
lattice (with $m>n$ and with zero values assigned everywhere
outside the $m$-dimensional hyperplane) and then
iterated in this higher dimensional space according
to the $m$-dimensional wave equation.
%, where the speed of light is now $\sqrt{1/m}$.  
All the while,
the discrete integral of the square of the solution
over all {\it points\/} (not links) of the
will remain 
equal to one.   Subsequently, the solutions
may be promoted to still higher dimensions,
all the while conserving the latter quantity.
In general, this latter
result does not hold for
a torus of any finite 
 length.

Note that
the $n$-di\-men\-sion\-al
hodotic solutions,
are simply the imbeddings
of one-di\-men\-sion\-al hodotic solutions 
to the appropriate higher dimension.




Support was provided in part by the National
Science Foundation, grant no. 8618002-IRI,
and in part by the Defense Advanced Research
Projects Agency, grant no. N00014-89-J-1988.




\vspace{.6\baselineskip}{\obeylines
\noindent {\large \bf References}\nopagebreak
\vspace{.3\baselineskip}\nopagebreak
}

\noindent$^1$R.~Courant, K.~Lewy, and O.~Friedrichs,
``On the Partial Difference Equations of Mathematical Physics'', originally
published in {\em Mathematische Annalen}, 1928, and translated into
English in the {\em IBM Journal}, March, 1967. 

%
\noindent$^2$T.~Toffoli and N.~Margolus,
{\sl Cellular Automata Machines, A New Environment for
Modeling\/}, MIT Press, Cambridge, Massachusetts, 1987.
D.~Farmer, T.~Toffoli, S.~Wolfram, {\sl Cellular Automata\/},
(North-Holland, Am\-ster\-dam, 1984). 

\medskip

\noindent$^3$H.~Hrgov\v ci\'c, ``Random Walks and Traveling
Waves of the $n$-Dimensional Wave Equation'', and
``The Local Interpretation of Quantum Mechanics'',
MIT-LCS Technical Reports 440--441.



\medskip

\noindent$^4$M.~Hillery,
R.~F.~O'Connell, M.~O.~Scully, and E.~P.~Wigner,
{\it Physics Reports\/} (Review Section of Physics Letters) {\bf 106}, 121 (1984);
P.~A.~M.~Dirac, {\it Reviews of Modern Physics}, {\bf 17}, 195 (1945);  
R.~P.~Feynman, `Negative Probability'  in B.~J.~Hiley and F.~David Peat (eds.),
{\it Quantum Implications} (Routledge \& Kegan Paul, London, 1987).



\end{document}















That is, without regard to the  {\it link\/} solutions
(whose integral of their squares is immediately seen to
be conserved due to the unitarity of the above transition
matrix),
it is the integral of the square of the {\it point\/}-solutions of the
wave equation that is conserved.  
This property does not hold, in general, for an arbitrary
sum of the hodotic solutions.
The proof of this is somewhat tedious, but it will be outlined 
briefly for the two-di\-men\-sion\-al case.  

Since  $h_{x_{+}}(x,y,T)$, for example,
may be written as a sum over all walks of length $T$, leading from
the point $(1,0)$ to the point $(x,y)$, one can see that $h^2_{x_{+}}(x,y,T)$
may be written as a sum of terms, each of which represents a
{\sl pair\/} of such paths.  Let $h^{x_{+}}_{\sigma}(x,y,T)$ represent
the contribution to $h_{\sigma}(x,y,T)$ of paths
whose  $T^{th}$ (i.e., whose final) step is along the $x_{+}$ direction,
so that 
\begin{equation}h_{x_{+}}(x,y,T)=\sum_{\sigma} h_{x_{+}}^{\sigma}(x,y,T)\ {\rm .}\end{equation}
Then
\begin{equation}
\sum_{\bf x} h_{x_{+}}^{\sigma}= \sum_{\bf x}\sum_{\sigma} \left(h_{x_{+}}^{\sigma}\right)^2
+ 2\sum_{\bf x}\sum_{\sigma \neq \sigma'}h_{x_{+}}^{\sigma}h_{x+}^{\sigma'}\ {\rm ,}
\end{equation}
where the functional dependence on $x$, $y$, and $T$, has
been suppressed.
Now the first (double) sum on the right is equal to one.
This is because
it represents the discrete integral of the sum of the squares of the
traveling wave components for this solution of the
wave equation. This quantity, due to the unitarity of
the transition matrix, is always conserved (and therefore
equal to its initial value of one).  Therefore, it remains only to
show that the second sum on the right vanishes.

First suppose that the two-di\-men\-sion\-al torus under
consideration is of
infinite length along either axis.
Unlike the first sum, the second contains
no terms representing pairs of 
walks that are identical. This is because  if the two paths in such a term were identical,
they would obviously have their $T^{th}$ step along
the same direction and therefore would belong in
the first sum.  It is easy to see graphically, 
that any such pair of nonidentical paths may
be related in a one-to-one way to another
pair of paths (belonging to the
same summation) whose cumulative number
of reversals differs by one.
\begin{figure}
\psfig{file=twf-pat-op-2.ps,height=1.75in,width=3.0in}
%box is 7" by 3 3/8", lower left corner 1/4" 7 1/8"
%                         upper right corner 7 1/8" 10 1/2"
%show two side by side photos; on the left, a
%pair of paths of length T starting at origin,
%being identical for the first two or three steps
%then making a loop at the point (x,y)
%(each end of the path terminates at this point).
%on the right, the manipulated graph with
%one additional reversal, and therefore
%a  contribution that negates the first.
$\phantom{two paths some{\rm{\large{(a)}}}}%
\phantom{two paths that are paths{\rm{\large{(b)}}}}%
$
\caption{Two paths (a) that are identical 
except for their final $m$ steps, where
$m\ne0$, but arrive at the same place at
$t=T$, may by a symmetry operation
% rotation of the
%nonidentical portions of the path 
%(in 
%this case, a rotation of $\pi/4$ about 
%the point $P$) 
be related to another pair 
of paths (b) such that the total number 
of reversals in the latter pair differs 
by one, so that the net contribution of 
these two pairs  is zero.}
\label{fi:pat-ope}
\end{figure}
Since
the value of the contribution of any pair of paths
depends only on the number of reversals involved,
the 
contributions to the summation of these two sets of paths
therefore cancels (Fig.~\ref{fi:pat-ope}).
The same result can of course be obtained without resorting to
graphical methods by representing each
path as a string of $T$ choices from the
set of possible directions, and then showing
that the contributions from certain
classes of strings cancel.

To extend these results to a torus of finite length, it is 
also  necessary to consider terms in the
sum representing pairs of paths that, when connected and
considered as one path, 
describe a loop that
is not homotopic to a point.
(The reference here is of course to the continuous paths
that can be obtained from the discrete ones by
imbedding the lattice in a Euclidean space, and
by likewise transforming any steps between two
lattice points into
a continuous path along the straight line
segment joining those points.)

If the two axes of the torus are of equal length,
then the contributions from those pairs of paths
that wrap around the torus along one direction,
may be seen to cancel the contributions of
those that wrap in the perpendicular direction.  However,
suppose the lengths of the lattice along the two axes
are unequal.  Then at some time, there will be
a pair of paths describing a loop around the shorter
length of the torus that is
not cancelled by a pair of paths along the other axis, since
only pairs of paths that compose closed loops enter into
the summation (Fig.~\ref{fi:axi-neq}).
\begin{figure}
%Show a torus that looks exactly like an
%inner tube resting stably on the floor.
%Show the two paths as arrows that,
%when taken together (they will
%emanate from the same point in
%opposite directions and meet at
%the point 180 degrees north or south,)
%define a sub-great circle of the torus,
%i.e., the path of shortest length
%that cannot be homeomorphically 
%shrunk to a point.
%\rule{.2pt}{13em}
\psfig{file=twf-torus-2.ps,height=2.286in,width=3.0in}
%box is 2 3/4" by 6 3/8", lower left corner 5/8" 6 3/4"
%                         upper right corner 6 7/8" 10 1/2"
\vspace{2\baselineskip}
\caption{If the two axes of the %
torus are of unequal  length, % 
say, $L_y > L_x$, then at %
$t = L_{x}/2$,  a pair of paths
forming a loop along the $x$-axis
will not be cancelled by a
corresponding
loop along the $y$-direction, since
such loops could only be made of paths
of length greater than $t$.}
\vspace{2.0\baselineskip}
\label{fi:axi-neq}
\end{figure}

In $n>2$
dimensions, the proof is more tedious, because
the coefficients in the transition matrix no longer have the same modulus. A 
pair of nonidentical
paths, that diverge with one of them making a reversal,
must be added to the contributions of $n-1$
pairs of nonidentical paths that diverge
without either member of the pair making a reversal
\begin{figure}
%Show on the left two paths that terminate at same point
%but diverge with one of them making a reversal;
%show on the right two paths that diverge without either
%making a reversal.  In each case
%distinguish the two paths involved by marking
%them with different lines, say, dotted and dashed.
%\rule{.2pt}{13em}
\psfig{file=twf-div-pat-2.ps,height=1.23in,width=3.0in}
\vspace{2\baselineskip}
%box is 2 3/4" by 6 3/8", lower left corner 1/2" 6 3/4"
%                         upper right corner 6 7/8" 9 1/2"
\caption{The pair of paths on the left diverges with 
one path making a reversal; the pair on the right
diverges with neither of the paths making a reversal.
(The solid line indicates
the portions of the two paths that are identical.)}
\vspace{2.0\baselineskip}
\label{fi:div-pat}
\end{figure} 
(Fig.~\ref{fi:div-pat}) in 
order to obtain a cancellation.
(Adding pairs of paths together means of course,
adding the terms in the summation that may be related to
the path pairs in question.)
Similarly, in extending the result
to an $n$-di\-men\-sion\-al torus,
a given number of 
pairs representing traversals
in one direction will in general
cancel a contribution from
some unequal number of
terms representing traversals
along some other direction,
but only if the axes of the torus are of equal length.
Otherwise, the proof is similar
to the two-di\-men\-sion\-al case.

%Note again that the proof holds only
%for a single hodotic solution.
%In general, any combination of
%two or more hodotic solutions			
%produces a wave solutions such that the square of the
%amplitude  summed over the whole 
%space is not conserved.

We turn next to another curious
property of the ho\-do\-tic solutions, that
becomes useful in decomposing solutions of the
wave equation into components other than the
$2n$ traveling waves discussed above.
Let {\it promotion} of an $m$-di\-men\-sion\-al
solution of (\ref{eq:wave}) to an $n$-di\-men\-sion\-al
space, with $n > m$,  denote
the following procedure:
\begin{quote}
take the ($m$-di\-men\-sion\-al) hodotic
solution at any two successive
time values and imbed it in a space of
dimension $n$. That is, use the solution as the boundary
conditions on a hyperplane of dimension $m$
in an $n$-di\-men\-sion\-al space, with
the solution being 0 everywhere outside
the hyperplane. Afterwards, iterate according
to (\ref{eq:wave}), (the speed of light
becoming $\sqrt{1/n}$).
\end{quote}

%As a concrete example, 
%suppose that in a four-di\-men\-sion\-al
%space at time $t = 0$ and 1,
%we assign the value of 0 to all points
%outside of a two-di\-men\-sion\-al
%plane intersecting the origin.
%On this plane, the function at
%time 0 will be identical to
%the two-di\-men\-sion\-al hodotic solution
%described above at say $t = 14$,
%while the function at $t = 1$
%will be identical to the 
%two-di\-men\-sion\-al hodotic solution
%at $t = 15$.  
%We have thus promoted
%the two-di\-men\-sion\-al hodotic
%solution (at time 15) to
%a four-di\-men\-sion\-al space.

The hodotic solutions
have the interesting property
that they may be iterated
an arbitrary number of times,
promoted to a higher dimension,
iterated again for some
other arbitrary number of times,
promoted to a still 
high\-er\-di\-men\-sion\-al subspace, and
so on, all the while producing a
solution whose discrete integrals
over the corresponding space
of the point-so\-lu\-tion, as well as its square,
are constant. The proof is
similar to the one outlined previously;
classes of pairs of nonidentical
paths can again be shown to cancel,
although for the purposes of
the proof, the number of classes
to which a pair of paths may belong
varies according to the time at which
the two members of the pair diverged
(more precisely, according to
whether they diverged before or after the given imbedding
in the higher-di\-men\-sion\-al space).
Note
that in general, this
result does not hold for
a torus of any finite 
 length.

Finally, note that
the $n$-di\-men\-sion\-al
hodotic solutions,
are simply the promotions
of one-di\-men\-sion\-al hodotic solutions 
to the appropriate higher dimension.



Support was provided in part by the National
Science Foundation, grant no. 8618002-IRI,
and in part by the Defense Advanced Research
Projects Agency, grant no. N00014-89-J-1988.
\end{document}



\vspace{.6\baselineskip}{\obeylines
\noindent {\large \bf References}\nopagebreak
\vspace{.3\baselineskip}\nopagebreak
}

\noindent$^1$R.~Courant, K.~Lewy, and O.~Friedrichs,
``On the Partial Difference Equations of Mathematical Physics'', originally
published in {\em Mathematische Annalen}, 1928, and translated into
English in the {\em IBM Journal}, March, 1967. 

\medskip

%
\noindent$^2$T.~Toffoli and N.~Margolus,
{\sl Cellular Automata Machines, A New Environment for
Modeling\/}, MIT Press, Cambridge, Massachusetts, 1987.
D.~Farmer, T.~Toffoli, S.~Wolfram, {\sl Cellular Automata\/},
(North-Holland, Am\-ster\-dam, 1984). 

\medskip

\noindent$^3$This
approach is also well suited to the study of quantum mechanics.
See H.~Hrgov\v ci\'c, ``Random Walks and Traveling
Waves of the $n$-Dimensional Wave Equation'', and
``The Local Interpretation of Quantum Mechanics'',submitted
to {\it Phys.~Rev.}}

\medskip

\noindent$^4$M.~Hillery,
R.~F.~O'Connell, M.~O.~Scully, and E.~P.~Wigner,
{\it Physics Reports\/} (Review Section of Physics Letters) {\bf 106}, 121 (1984);
P.~A.~M.~Dirac, {\it Reviews of Modern Physics}, {\bf 17}, 195 (1945);  
R.~P.~Feynman, `Negative Probability'  in B.~J.~Hiley and F.~David Peat (eds.),
{\it Quantum Implications} (Routledge \& Kegan Paul, London, 1987).



\end{document}







%******label 5

Consider again the hodotic solutions.  In higher dimensions,
there are, up to translation, $2n$ different kinds of hodotic
solutions, depending on the direction of the initially
nonzero flow.
The hodotic solutions $h_{\sigma}({\bf x}-{\bf x}_0)$ 
at any spacetime point can easily be written as a summation over
paths on a lattice.  All such paths begin at 
the lattice point ${\bf x}_0$. In the successive
time step move in the direction indicated by $\sigma$.
They move in each successive time step to a nearest neighbor
of the previous lattice point, and finally arrive at
the point ${\bf x}$ at the time $T$.

If $\phi({\bf x}, T)$ is some indexing of the above paths,
and if $R(\phi({\bf x}, T)$ gives the number of reversals in a path, and
then
%
\begin{equation}
h_{\sigma}({\bf x}, T)= ({1\over n})^T \sum_{\{\phi({\bf x}, T)\}} (1-n)^{R(\phi({\bf x}, T))}\ .
\end{equation}
%






% GENERALIZED LATTICES section, deleted for reasons of space.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

It is possible to formally extend
the notions of traveling waves
to non-or\-tho\-nor\-mal 
lattices, generalizing the discrete wave equation
to hexagonal, tetragonal, indeed
to any set of points where each point $j$ has
some privileged subset ${\cal N} (j)$
of generalized nearest neighbors;
the ``wave equation''
then becomes
\begin{equation}
\psi(j,t+1) + \psi(j,t-1)  = {2\over{\left| {\cal N}(j)\right|}}\sum_{j' \in N(j)}\psi(j',t)\ {\rm ,}
\end{equation}
where $\left| {\cal N}(j) \right|$ is the number of
nearest neighbors corresponding to point $j$, and
which may vary throughout the space.
Again, each pair of neighbors will
induce a flow, with
an interaction among flows that may
be determined by studying the behavior
of the
associated hodotic solutions.$^3$  As before,
there will be a
conservation of the sum of the 
flows, as well as the sum of their squares.
Of course, how well, if at all, the resultant
system mimics  the 
continuum wave equation in some limit depends on
the particular lattice employed and,
if definable, the
associated dispersion relation.

%%%%%%%%%%%%%%%%%%%%% end of GENERALIZED LATTICES section.
