\section*{2D Photonic System and Quantum Spin Hall Hamiltonian}

As illustrated in Fig.~\ref{fig:coupled_resonators}, our system comprises optical ring microresonators that support
degenerate clockwise and counter-clockwise modes, restricted to one
pair per resonator.  We consider these modes as two components of a
pseudo-spin, i.e., clockwise ($\sigma=-1$, or psuedo-spin down) and
counter-clockwise ($\sigma=+1$, pseudo-spin up) circulation.
Resonators are evanescently coupled to each other and have been
studied in the context of 1D CROW \cite{Yariv:1999}, where the coupling leads to a tight-binding
model for photons and the corresponding photonic band structure.  By
coupling these modes in a two-dimensional arrangement, as we show below under appropriate
conditions, the dynamics of such photonic system is described by a
Hamiltonian for charged bosons on a square lattice (tight-binding),
but with the addition of a
perpendicular, spin-dependent effective magnetic field:

\begin{eqnarray}
  H_{0} & = & -\kappa \Big( \sum_{\sigma,x,y}\hat{a}_{\sigma x+1,y}^{\dagger}\hat{a}_{\sigma x,y}e^{-i2\pi\alpha y \sigma }+\hat{a}_{\sigma x,y}^{\dagger}\hat{a}_{\sigma x+1,y}e^{i2\pi\alpha y \sigma }\nonumber \\
  & + & \hat{a}_{\sigma x,y+1}^{\dagger}\hat{a}_{\sigma x,y}+\hat{a}_{\sigma x,y+1}^{\dagger}\hat{a}_{\sigma x,y} \Big) \label{eq:magnetic_tight_binding}\end{eqnarray}
where $\kappa$ is the tunneling rate of optical modes and $\hat{a}_{\sigma x,y}^{\dagger}$ is the
photon creation operator at resonator at site (x,y) with different
spin componenets ($\sigma=\pm1$). Specifically, photons acquire a
$2\pi\alpha \sigma$ phase when they go around a plaquette--equivalent
to having $\alpha$ quanta of magnetic flux penetrating each unit
plaquette \cite{Langbein:1969,hofstadter}.

\begin{center}

\begin{figure}
\includegraphics[width=0.90\textwidth]{coupled_resonators}

\caption{\textbf{Schematics of the photonic system with a synthetic magnetic field: }(a) The dynamics of two coupled resonators is governed by a magnetic-type Hamiltonian (equation 3). The lengths of the upper and lower branch differ from each other so that the phase difference is $4\pi \alpha$ and m is an integer. (b) A magnetic tight-binding model can be implemented in a 2D lattice of coupled resonators. Only the waveguide phase differences are shown.  (c) By introducing scatterer in resonators and waveguides, one can induce in-plane magnetic field (Zeeman) and spin-flip hopping terms, in analogy to quantum spin Hall models.\label{fig:coupled_resonators}}

\end{figure}
\end{center}

First, we show how the description of our system using such a Hamiltonian is derived.  We
start by considering two coupled resonators
(Fig.~\ref{fig:coupled_resonators}(a)), focusing only on the
counter-clockwise modes inside each resonator.  The length of
connecting waveguides is chosen such that photons destructively
(constructively) interfere inside the waveguide loop (resonator),
respectively, and therefore, they will be confined in the resonators
rather than waveguides.  Moreover, the lengths of the upper and lower
branches of the waveguide differ from each other, so when a photon hops from the left
to the right resonator, it acquires a  different phase than when it
hops in the opposite direction. This can be formally verified using
the standard input-output formalism \cite{Gardiner:1985}. In
particular, the boundary condition at the left resonator can be
written as
\begin{equation}
\hat{E}^{out}_x=\hat{E}^{in}_x+\sqrt{2\kappa}\hat{a}_x,
\end{equation}
where $\hat{E}_x$'s are waveguide field operators at the vicinity of
the $x$-th resonator and $\hat{a}_x$ is the resonator field operator,
as shown in Fig.~\ref{fig:coupled_resonators}(a).  The resonator field
equation of motion is:
$\partial_t\hat{a}_x=-\kappa\hat{a}_x-\sqrt{2\kappa}\hat{E}^{in}_x$,
and similarly for the right resonator. Photons propagate freely
between the resonators, so for the upper branch we have
$E_{x+1}^{in}=-iE_x^{out} \exp({-2\pi i \alpha})$, and similarly for
the lower branch. By eliminating the waveguide fields, the left and
right resonator fields dynamics will be given by $\partial_t
\hat{a}_{x(x+1)}=i\kappa \exp{(\pm 2\pi i\alpha)}
\hat{a}_{x+1(x)}$, consistent with tunneling between resonators. Therefore, the effective Hamiltonian of the two
resonators takes the form:
\begin{equation}
H_{two-res}=-\kappa \hat{a}_{x+1}^\dagger\hat{a}_x e^{-2\pi i\alpha}-\kappa \hat{a}_{x}^\dagger\hat{a}_{x+1} e^{2\pi i\alpha}.
\end{equation}

The above analysis for counter-clockwise modes (pseudo-spin up $\hat{a}_{\uparrow x,y}$) in the resonators shows that, in the absence of backscattering, they are decoupled from their time-reversed counterpart, i.e., the clockwise mode of the resonator (pseudo-spin down $\hat{a}_{\downarrow x,y}$).  At the same time, the pseudo-spin down component will experience a magnetic field similar to the pseudo-spin up component, where only the sign of magnetic field is changed ($\alpha \rightarrow -\alpha)$. Now,  by connecting resonators in a lattice structure and tuning the phase of the connecting waveguides, we can arrange  the acquired phase around each plaquette to be uniform and equal to $2\pi\alpha$. The phase can be tuned either by changing the length (or the index of refraction) of the connecting waveguides or by coupling ring resonators to the sides of the waveguides (similar to a Mach-Zender configuration \cite{Heebner:2004,Xia:2006}). The implementation of a Landau-type gauge is shown in Fig.~\ref{fig:coupled_resonators}(b) where the corresponding Hamiltonian is the form of equation (\ref{eq:magnetic_tight_binding}). Indeed, this is the trivial form of Hamiltonians with
QSHE in an analogy to time-reversal invariant
spin-orbit interactions in solid state
systems \cite{Haldane:1988,Kane1:2005,Bernevig:2006p27579}, where the magnetic field has
opposite orientations for the two pseudo-spin components.
Furthermore, one can control the coupling between different pseudo-spin component and exploit a wider class of QSHE Hamiltonians on a square lattice.  In particular,  semi-transparent scatterers inside the resonators or
the connecting waveguides can be engineered to mix different
pseudo-spin components with each other.

\section*{Generalized pseudo-spin-orbit interaction}

To illustrate this mixing, we consider the addition of a pair of
scatterers in every vertical connecting waveguide as shown in
Fig.~\ref{fig:coupled_resonators}(c). For simplicity, we assume the
scatterer is weak and loss-less. We characterize the strength of the
scatterer by a parameter $\epsilon$, where the transmission
coefficient is near unity $(t_{s}\simeq1)$ and the reflection
coefficient is $r_{s}=i\epsilon/\sqrt{2}$.  As shown in the
Supplementary Information (SI), the corresponding Hamiltonian of a
single vertical array of resonators will be: \begin{equation}
  H_{flip}=-\kappa\sum_{x,y}(\begin{array}{cc} \hat{a}_{\uparrow
      x,y+1}^{\dagger} & \hat{a}_{\downarrow
      x,y+1}^{\dagger}\end{array})\left(\begin{array}{cc}
      1 & \epsilon\\
      \epsilon & 1\end{array}\right)\left(\begin{array}{c}
      \hat{a}_{\uparrow x,y}\\
      \hat{a}_{\downarrow
        x,y}\end{array}\right)+h.c.\label{eq:spin-flip}\end{equation}
The diagonal terms are identical to the tight-biding terms of equation
(\ref{eq:magnetic_tight_binding}) and the off-diagonal terms represent
hopping between two adjacent sites while undergoing a spin-flip, i.e.,
the scatterers couple clockwise to counter-clockwise photons
(Fig.~\ref{fig:coupled_resonators}(c)). This spin-flip hopping is
similar to the Rashba term in the context of spin-orbit
interaction\cite{Rashba:1984,Kane1:2005}.

Similarly, if we consider a pair of weak scatterers inside the
resonators, then corresponding Hamiltonian takes the form:

\begin{eqnarray}
  H_{mag} & = & -\kappa\sum_{x,,y}(\begin{array}{cc}
    \hat{a}_{\uparrow x,y+1}^{\dagger} & \hat{a}_{\downarrow x,y+1}^{\dagger}\end{array})\left(\begin{array}{cc}
      1 & 0\\
      0 & 1\end{array}\right)\left(\begin{array}{c}
      \hat{a}_{\uparrow x,y}\\
      \hat{a}_{\downarrow x,y}\end{array}\right)+h.c. \nonumber \\
  & - & \frac{4\epsilon\kappa\mathcal{F}}{\pi}\sum_{x,y}(\begin{array}{cc}
    \hat{a}_{\uparrow x,y}^{\dagger} & \hat{a}_{\downarrow x,y}^{\dagger}\end{array})\left(\begin{array}{cc}
      0 & 1\\
      1& 0\end{array}\right)\left(\begin{array}{c}
      \hat{a}_{\uparrow x,y}\\
      \hat{a}_{\downarrow x,y}\end{array}\right).\label{eq:in-plane}\end{eqnarray}
The first term is the usual tight-binding form and the second term
represents the in-plane magnetic field which is enhanced by the finesse of the resonators (i.e., number of photon round trips $\mathcal{F}\simeq \pi/(1-r^2)$). If these vertical arrays replace the vertical
arrays of Fig.~\ref{fig:coupled_resonators}(b), then the overall
Hamiltonian of the system encompasses both an in-plane Zeeman term,
perpendicular to the synthetic magnetic  field (due to
on-site scatters) and a hopping-spin flip
term (similar to Rashba interaction).

\section*{Probing the photonic system}

We now show how optical spectroscopy measurements can be harnessed to analyze the transport properties of our photonic system.  In particular, as shown in Fig.~\ref{fig:coupled_resonators}(b), by
coupling two waveguides to the lattice edges, we evaluate the transmission
and the reflection of an input light field and study their properties
in connection with the magnetic states of the system (localized states and
edge states).

We first consider a trivial case of quantum spin Hall effect where pseudo-spin-flip terms are absent. In this regime, we have two decoupled copies of regular quantum Hall states for opposite pseudo-spin components. We restrict our analysis to a single spin component,  and for brevity, we drop the spin index.  This choice enables us to examine in detail methods for probing the system and
determining its response to errors and disorders, without the additional complexity of spin Hall physics.

Using a formalism similar to the quantum scattering theory, we
investigate the problem of scattering of light field in optical
waveguides connected to our photonic system and evaluate transmission
and reflection coefficient under various conditions.  The waveguides only couple to
co-propagating modes in the resonators (counter-clockwise in
Fig.~\ref{fig:coupled_resonators}(b)), and thus under our assumption, the reflection in the input
channel and also transmission in the output channel is zero
(i.e., $R,T'=0$ shown in Fig.~\ref{fig:coupled_resonators}(b)).  The input-output probing waveguides are coupled to two resonators in the systems denoted by $|in\rangle$ and $|out\rangle$, respectively. As shown in SI, the self-energy of these resonators can be written as
 $\Sigma=-i\frac{\nu}{2}|in\rangle \langle in|-i\frac{\nu}{2}|out\rangle \langle out|$, where the coupling strength is
defined as $\nu$. Using Lippman-Schwinger equation, one can deduce different
reflection/transmission coefficients \cite{Fan:1999,Xu:2000}.  In
particular, the reflection coefficient is given by

\begin{equation}
r'(\omega)=-i\nu\sum_{i\in in,j\in out} \left \langle i \left | \frac{1}{\omega-H_0-\Sigma} \right |  j \right \rangle\end{equation}
which means  an appreciable reflection should be observed when the frequency of an incoming photon becomes resonant with the energy of a photonic state inside the system. Note that if the photonic system is a single resonator, equation (6) reduces to the familiar form of: $r'(\omega)=\frac{-\nu}{\nu-i(\omega-\omega_0)}$.

The energy spectrum of the Hamiltonian of equation (\ref{eq:magnetic_tight_binding})
for an \emph{infinite} lattice is the well-known Hofstadter butterfly \cite{hofstadter}. We consider a $N_x \times N_y$ lattice with torus boundary condition
(i.e., coupling top-bottom and left-right edge together) to simulate
the effect of an infinite lattice. According to Hofstadter spectrum, for rational magnetic fluxes ($\alpha=p/q$), each magnetic band has many states ($\frac{N_{x}N_{y}}{q}$-fold),
which is the reminiscent of the Landau degeneracy in the continuum. The result of our numerical solution is shown in Fig.~\ref{fig:Hofstadter-butterfly} where the reflectivity $(R'=|r'(\omega)|^{2})$ is evaluated for different frequencies and magnetic field ($\alpha$), by the formalism described above. High reflectivity occurs when the
lower waveguide light is coupled to the system and completely transferred
to the reflection output channel (the second waveguide), similar to a channel drop filter.
We can readily see that the energy spectrum of the uncoupled system
(Hofstadter butterfly) can be obtained by measuring the system reflectivity.
We note that in order to to resolve different energy levels in the
spectrum, $\nu$ should be chosen to be sufficiently narrow ($\lesssim 8\kappa/(N_xN_y)$).

\begin{figure}
\includegraphics[width=0.5\textwidth,height=0.40\textwidth]{butterfly_reflection}
\caption{\textbf{Hofstadter butterfly spectrum:} Each point represents a reflectivity greater than 0.005, for a 10x10 lattice with torus boundary condition and the coupling $\nu/\kappa=.02$. The green line shows the spectrum at the magnetic field of interest ($\alpha$) for the rest of the figures in the article.}
 \label{fig:Hofstadter-butterfly}

\end{figure}

\section*{Photonic edge states}

In a direct analogy to 2D electrons
in a magnetic field (quantum Hall physics) \cite{Halperin:1982,Rammal:1983,Hatsugai:1993PRB},
we recognize quasi-one dimensional states that are localized at the
perimeter of the system which carry current and are immune to disorders in form of random potential.
In contrast to toroidal boundary conditions where only magnetic bands
are present, in a finite square lattice, there exist states between magnetic bands
which are known as ``edge states''. These edge states carry a chiral current around the system
perimeter, as shown in Fig.~\ref{fig:prob-current:pure/impure}(a).
For each edge state, there is a similar edge state with an opposite
chirality which has the same energy magnitude but with the opposite sign.

So far we have considered a perfect system. To illustrate the robustness of the system to disorder, we consider a resonator that is detuned from its neighbors provides a model for ``non-magnetic'' disorder. This disorder can be readily characterized by an on-site potential at that site ($U\hat{a}_{x,y}^\dagger \hat{a}_{x,y}$). The main source of such frequency mismatch is small variations of the waveguide widths and the perimeters of the microrings during the fabrication process. Such imperfections are a common problem in photonics and prevents coupling large number of resonators \cite{Barwicz:2006,Xia:2007}.

In electronic quantum Hall systems, the edge states are immune to disorder \cite{prange:BOOK}. We find that such robustness applies to our photonics system. In particular, when such a disorder is located `inside' the edge state, the edge state is obviously not affected. However, when the disorder is
located on the edge, the edge state routes around it, as shown in Fig.~\ref{fig:prob-current:pure/impure}(b). More precisely, scattering which would reverse the current is prevented due to the lack of additional states with appropriate energy and momentum.

\begin{figure}[h]
\includegraphics[width=0.5\textwidth]{edge-state-current}
\caption{\textbf{Edge states and their dispersion:} Probability current for an edge state in the absence
(a) and in the presence of a disorder (b). The location of the disorder is shown by the black dot, and $U/\kappa=5$. (c) shows the dispersion relation, a wave number is evaluated for each energy eigenstate at the lower (red) and upper edge (blue), i.e., $K\Lambda$ is the phase difference between two consecutive resonator at the edges. Magnetic bands state do not have well-defined wavenumber and are shown in the yellow area. The dashed line shows the state corresponding to (a).  In these plots, a 10x10 square lattice with $\alpha=\frac{1}{4}$ is considered. \label{fig:prob-current:pure/impure}}

\end{figure}

\section*{Application to delay lines}

The transport properties of edge states provide a robust alternative to conventional CROW in photonic delay lines.  In particular, we compare the transport properties of our photonic quantum Hall system to CROW, as illustrated in Fig.~\ref{fig:transport}.  In the quantum Hall system, there is a robust transfer band provided by edge states which carry photons from the input waveguide to the output waveguide (Fig.~\ref{fig:transport} inset), in a direct analogy to electronic edge state in the context of the integer quantum Hall effect \cite{Halperin:1982}.

In both systems, the operational bandwidth is given by smooth, linear part of the dispersion relation. In the quantum Hall system, the edge state band (Fig.~\ref{fig:prob-current:pure/impure}), is located between two Hofstadter bands (Fig.~\ref{fig:Hofstadter-butterfly}), while in the CROW configuration, the operational bandwidth is in the middle of the tight-binding dispersion to avoid the group velocity dispersion \cite{Yariv:1999}. Moreover, in both systems, the delay time is proportional to the number of resonators involved in the transport.  In the quantum Hall system, the transport can be either performed along the long or short edge of the system, depending on the input frequency, as shown schematically in Fig.~\ref{fig:transport} inset. Therefore,  in both systems in the absence of disorder, the bandwidth-delay product increases by the length (perimeter) of the system. However, in the presence of disorder, CROW and edge state behave differently as the system size increases. In particular,  in 1D systems (e.g. CROW) the disorder leads to localization \cite{Anderson:1958,Kramer:1993,Mookherjea:2008} and therefore, the transmission is impeded. In contrast,  the transport of edge states is topologically protected against disorder \cite{TKNdN,prange:BOOK} and the transmission is not affected (as discussed above for Fig.~\ref{fig:prob-current:pure/impure}).

\begin{figure}
\includegraphics[width=.97\textwidth]{transport}
\caption{\textbf{Edge states vs. CROW:}  This figure compares the quantum Hall system (left panels, 10x10 lattice) and CROW (right panels, array of 40) performances as delay lines. Blue curves show the average time delay (output reflectivity) in a(b), respectively, and the gray area highlights the standard deviations in the presence of  non-magnetic disorder (a gaussian disorder with a width $U/\kappa=0.4$ for 500 realizations). While the transport  is quite noisy in the magnetic bands and CROW (tight-binding band), the edge state bands exhibit noiseless transport with delays comparable to CROW. Depending on the input frequency, different edge states participate in the transport which leads to shorter or longer delays, as shown in the insets. In the presence of magnetic disorder  (the strength is a gaussian with a width $\epsilon\mathcal{F}=0.1$ and the phase is random $[0,2\pi)$) and loss ($\kappa_{in}=0.02\kappa$), the transport properties are more degraded for CROW than edge state bands.  While the counter-clockwise modes of the resonators is excited through an input field, the onsite scatterers backscatter photons in the clockwise modes. These modes leak out into $R$ and $T'$ channels which are non-zero in these plots. The coupling between input-output waveguides and the system is chosen to optimize the transport (for edge states $\nu=6 \kappa$ and for CROW $\nu=2\kappa$). In the quantum Hall system, the input and output waveguides are coupled to ($x=2,y=1$) and ($x=N_x-1,y=1$) resonators, respectively.\label{fig:transport}}

\end{figure}

\begin{figure}
\includegraphics[width=.4\textwidth]{localization}
\caption{\textbf{Transmission in 1D CROW and 2D quantum Hall system:}  For 1D CROW (2D quantum Hall), the transmission ($R'$) is evaluated at the center frequency $\omega=0$ ($\omega=1.5 \kappa$), where the group velocity dispersion is minimum, respectively. A gaussian disorder is assumed with a width $U/\kappa=0.4$ and the transmission is  averaged over an ensemble of 500 realizations. Gray shades show the standard deviation. By increasing the bandwidth-delay product (x-axis), the transmission for 1D CROW decreases  and the noise increases, while both the transmission and the noise in the 2D quantum Hall system remains constant.}  \label{fig:localization}

\end{figure}

To confirm that our edge states provide a robust transport, we numerically study the effect of disorder, by assigning a random frequency mismatch to the resonators. Taking average over many different disorder realizations, we observe that by increasing the size of the system and consequently the bandwidth-delay product, the transmission in CROW  decreases while the transmission with edge states is unaffected, as shown in Fig.~\ref{fig:localization}. Furthermore, we  observe that while magnetic band states and CROW depend sensitively on the disorder (position/strength), from one realization to another, the edge states are insensitive to the specific parameters, as shown in the standard deviation of the reflectivity and delay time in Fig. \ref{fig:transport}(a,b). The effect of the disorder on edge states is simply a shift of energies, which is manifested in a frequency shift in the edge states transfer band.

We note that as time-reversal symmetry is not broken in our
system, we can not utilize such edge states as a one-way waveguide
similar to Ref.\cite{Wang:2009p16784}. More precisely, when we input
a light field in the backward direction into the system (by swapping
the input and output channel), the waveguides couple to the opposite
rotating field in the resonators (opposite pseudo-spin) and experience a magnetic field with
an opposite sign. Therefore, the system is reciprocal and the transport properties of the forward and backward feed are identical to each other.

Finally, we  investigate the effect
of loss in the resonators and other imperfections. Loss can be represented by a non-hermitian term in the Hamiltonian:
$-i\kappa_{in}\hat{a}_{x}^{\dagger}\hat{a}_{x}$ where the dissipation rate is given as the product of loss per roundtrip, number of roundtrips per decay time and the photon decay rate ($\kappa_{in}=\mu (\frac{\mathcal{F}}{2\pi}) (4\kappa)$) (see SI). The photonic loss can attenuate the reflection in the edge state transfer band due to the propagation around perimeter (Fig.~\ref{fig:transport}(c)). Silicon-on-insulator technology, where up to 100 micro-ring resonators have  been successfully coupled to
each other \cite{Xia:2007}, is a promising candidate for implementation of our scheme (see SI for experimental relevant parameters).

Other types of imperfection such as surface roughness can cause undesired backscattering which mixes  pseudo-spin up and down, acting as ``magnetic disorder''. As show in the SI,  these imperfections can be modeled by a magnetic disorder Hamiltonian. The backscattering effect manifests in the reduction of signal in $R',T$ channels and some leakage in $R,T'$ channels.  Fig.~\ref{fig:transport}(c) shows different transport coefficients. We observe that although the transport properties of magnetic bands states are affected by such magnetic disorder, edge state transport is robust, which is due the suppression of backscattering events. In particular, the scattering of a forward-going spin-up into forward (backward) -going spin-down is inhibited due to energy (momentum) mismatch.

\section*{Outlook}
Optical signals might be a promising alternative to electronic signals in the future circuits \cite{semi_roadmap:2010}. One of the key requirements is the ability to filter and slow down light on-chip over a large bandwidth (several Gbps)  for  various  time-domain processing such as optical buffering and multiplexing \cite{Baba:2008}. However, the effect of disorder in the millimeter size footprint is detrimental, e.g.  unwanted signal modulation in transmission spectrum \cite{Xia:2007}. Our system provides a platform to realize photonic system immune to disorder. Potentially, one can envisage using other types of topological properties to improve photonic technologies.

In addition, our photonic system enables a new approach for exploration of various fundamental quantum Hall phenomena.  This photonic system not only
enables investigations of quantum Hall
physics by simulating different types of Hamiltonians at room temperature, but it also taps into topological features to provide robust  devices for photonics. In the non-interacting regime (which was the topic of this article), one can
explore the Hofstadter butterfly of photons, and photonic edge
states as delay lines immune to disorders and also localization in 2D for non-interacting particles \cite{Huckestein:1995}. Furthermore, with the addition of interaction between photons, this system opens up exciting
prospects for exploring many-body topological state of light.  Although the ground state properties of such systems have been  extensively studied, the suitable characterization and measurement of strongly interacting photons is still an open question. In particular,  the chemical energy is absent for photons and the relevant conditions to study photons involves an externally driven system which leads to non-equilibrium situations \cite{Hafezi:2009a}. Another advantage of photons is their flexibility to form various system topologies (torus with different genera) by simply connecting waveguides to each other and manipulate such states for topological quantum computation. Intriguing additional applications of these ideas await further exploration.

\bibliographystyle{apsrev}


\section{Introduction}
\label{sec:introduction}

Let $\cA$ be an abelian group and let $\cD = \{ a_1 , a_2 , \ldots
, a_m \} \subseteq \cA$ be a subset of $m$ distinct elements of
$\cA$. $\cD$ is a \emph{Sidon sequence} (or a $B_2$-sequence) over
$\cA$ if all the sums $a_{i_1} + a_{i_2}$ with $1 \leq i_1 \leq
i_2 \leq m$ are distinct (if $i_1 < i_2$ in the definition the
sequence is called a \emph{weak Sidon sequences}). Sidon sequences
have found many applications in coding and communication. For
example, weak Sidon sequences are used for construction of
constant weight codes with minimum Hamming distance 6~\cite{BSSS},
and constructions of location-correcting codes~\cite{RoSe96}.
Sidon sequences were used in constructions of two-dimensional
synchronization patterns~\cite{BEMP1,Etz11}. There is a
generalization to $B_h$ sequences (all sums of $h$ elements are
distinct) and they applied for example in multihop paths related
to wireless sensor networds~\cite{BEMP2} and error-correcting
codes for rank modulation~\cite{BaMa10}. A comprehensive survey on
$B_2$-sequences and their generalizations was given by
O'Bryant~\cite{Bry04}. Even so in a Sidon sequence all sums of
pairs of elements from $\cD$ (not necessarily distinct elements)
are distinct there is a trivial connection to a set in which all
differences of ordered pairs of elements are distinct.

\begin{theorem}
\label{thm:diff} A subset $\cD = \{ a_1 , a_2 , \ldots , a_m \}
\subseteq \cA$ is a Sidon sequence over $\cA$ if and only if all
the differences $a_{i_1} - a_{i_2}$ with $1 \leq i_1 \neq i_2 \leq
m$ are distinct in $\cA$.
\end{theorem}

A Sidon sequence with $m$ elements over an abelian group with $n$
elements is called \emph{optimal} if all Sidon sequences over an
abelian group with $n$ elements have at most $m$ elements. In view
of Theorem~\ref{thm:diff} bounds on the size of a Sidon sequence
(on the number of elements $m$) can be derived by considering
difference and not sums. This is important since the number of
distinct sums is $\binom{m}{2} +m = \frac{m^2 +m}{2}$ while the
number of distinct differences is considerably higher, $m(m-1) =
m^2 -m$. This yields a better upper bound on $m$. A Sidon sequence
$\cD$ is a set of $m$ elements. If the abelian group is $\Z_n$
then $\cD$ can be represented as a binary cyclic sequence $s=[s_0
s_1 , \cdots , s_{n-1} ]$, where $s_i =1$ if $i \in \cD$.

One-dimensional synchronization patterns were first introduced by
Babcock in connection with radio interference~\cite{Bab}. Other
applications are discussed in details in~\cite{BlGo77} and some
more are given in~\cite{ASU,LaSa88}. The two-dimensional
applications and related structures were first introduced
in~\cite{GoTa82} and discussed in many papers,
e.g.~\cite{GoTa84,Rob85,Games87,BlTi88,Rob97}. Recent
new application in keys predistribution for wireless sensor
networks~\cite{BEMP} led to new related two-dimensional problems
concerning these patterns~\cite{BEMP1,BEMP2}. Difference pattern and
Sidon sequences have an important role in the construction of synchronization patterns.

Some of the applications of Sidon sequence is due to the
difference properties implied by Theorem~\ref{thm:diff}. This
property is also the basis of the applications to two-dimensional
synchronization patterns. There are various papers,
e.g.~\cite{BEMP1,Etz11,Rob97} in which an one-dimensional sequence
(as a Sidon sequence or a ruler) is transformed into a
two-dimensional synchronization pattern. The main goal of this
paper is to establish the inverse transformation, in which a
two-dimensional synchronization pattern is transformed into a
Sidon sequence, which is a one-dimensional sequence.

The rest of this paper is organized as follows. In
Section~\ref{sec:period} we define what is a period in a
two-dimensional array and as a result we obtain a definition for a
cyclic two-dimensional array. In Section~\ref{sec:DDCs} we discuss
various types of two-dimensional synchronization patterns. In
particular we discuss periodic two-dimensional synchronization
patterns. In Section~\ref{sec:folding} we present two operations,
namely, folding and unfolding. Folding generates a two-dimensional
array from an one-dimensional sequence. Unfolding is the inverse
operation and it generates an one-dimensional sequence from a
two-dimensional array. In particular we will prove that these
operations relate periodic sequences to periodic two-dimensional
arrays and vice-versa. Moreover, they relate an one-dimensional
synchronization sequence to a two-dimensional synchronization
array and vice-versa, if the two-dimensional array is periodic. As
a consequence we obtain the main result of the paper that
two-dimensional periodic synchronization arrays which can be
unfolded are equivalent to Sidon sequences over $\Z_n$, where $n$
is the size of one period in the array. In Section~\ref{sec:new}
we present a construction of optimal Sidon sequences with $q-1$
elements over a group with $q(q-1)$ elements, where $q$ is a power
of a prime. This generalizes a similar result where $q$ is a
prime. Section~\ref{sec:conclude} contains conclusions and
problems for further research.

\section{Periodicity of Two-Dimensional Arrays}
\label{sec:period}

\subsection{periodic sequences and arrays}

It is very simple to define the periodicity for one-dimensional
sequences. An infinite sequence $S= \ldots s_{-1} , s_0 , s_1 ,
s_2 , \ldots$ is periodic if there exists an integer $\pi$ such
that $s_{i+\pi} = s_i$ for each $i \in \Z$. If $\pi$ is the
smallest integer for which the sequence has this property then we
say that $\pi$ is the \emph{period} of the sequence and write the
sequence as $[s_0 , s_1 ,\ldots , s_{\pi -1}]$, and say that the
sequences is a \emph{cyclic sequence} or a \emph{cycle}. It is
well known that
\begin{theorem}
\label{thm:period_one} If $\pi$ is the period of a sequence $S$,
and there exists an integer $\rho$ such that $s_{i+\rho} = s_i$
for each $i \in \Z$, then $\pi$ divides $\rho$.
\end{theorem}

Usually, an infinite two-dimensional array $\cA$ is said to be
doubly periodic if there exists two integers $\kappa$ and $\eta$
such that for each $i,j \in \Z$ we have $\cA(i+\kappa
,j)=\cA(i,j+\eta)=\cA(i,j)$. But, it appears that this definition
is too restricted. A generalized definition, which give more
information, is as follows. An infinite two-dimensional array $A$
is \emph{doubly periodic} if there exists two linearly independent
integer vectors $(\pi_1 , \pi_2 )$ and $(\xi_1 , \xi_2 )$ such
that each $i,j \in \Z$ satisfy $\cA(i+\pi_1 ,j+\pi_2 )=\cA(i+\xi_1
,j+\xi_2 )=\cA(i,j)$. How we can define the smallest vectors with
this property? What is the period of the array? and what is a
cyclic two-dimensional array? These questions will be answered
after two necessary definitions, of tiling and lattices, will be
presented.

\subsection{Tiling}

Tiling is one of the most basic concepts in combinatorics. We say
that a two-dimensional shape $\cS$ tiles the two-dimensional
square grid $\Z^2$ if disjoint copies of $\cS$ cover $\Z^2$. This
cover of $\Z^2$ with disjoint copies of $\cS$ is called a {\it
tiling} of $\Z^2$ with $\cS$. For each shape $\cS$, in the tiling,
we distinguish one of the points of $\cS$ to be the {\it center}
of $\cS$. Each copy of $\cS$ in a tiling has the center in the
same related point. The set $\cT$ of centers in a tiling defines
the tiling, and hence the tiling is denoted by the pair
$(\cT,\cS)$. Given a tiling $(\cT,\cS)$ and a grid point
$(i_1,i_2)$ we denote by $c(i_1,i_2)$ the center of the copy of
$\cS$, $\cS'$, for which $(i_1,i_2) \in \cS'$. We will also assume
that the origin is a center of a copy of $\cS$. The first lemma
given in~\cite{Etz11} can be easily verified.
\begin{lemma}
\label{lem:center} For a given tiling $(\cT,\cS)$ and a point
$(i_1,i_2)$ the point
$(i_1,i_2)-c(i_1,i_2)$ belongs to the shape
$\cS$ whose center is in the origin.
\end{lemma}

\subsection{Lattices and Lattice Tiling}

One of the most common types of tiling is a {\it lattice tiling}.
A two-dimensional {\it lattice} $\Lambda$ is a discrete, additive subgroup of the
real two-dimensional space $\R^2$. W.l.o.g., we can assume that

\begin{equation}
\label{eq:lattice_def} \Lambda = \{ u_1 v_1 + u_2v_2 ~:~ u_1, u_2 \in \Z \}
\end{equation}
where $v_1, ~v_2$ are two linearly independent
vectors in $\R^2$. A lattice $\Lambda$ defined by
(\ref{eq:lattice_def}) is a sublattice of $\Z^2$ if and only if
$\{ v_1,v_2\} \subset \Z^2$. We will be interested
solely in sublattices of $\Z^2$. The vectors $v_1,v_2$
are called {\it basis} for $\Lambda \subseteq \Z^2$, and the $2
\times 2$ matrix
$$
{\bf G}=\left[\begin{array}{cc}
v_{11} & v_{12} \\
v_{21} & v_{22} \end{array}\right]
$$
having these vectors as its rows is said to be the {\it generator
matrix} for $\Lambda$. Note, that it is always possible to use a
generator matrix ${\bf G}$ in which all the four entries are
nonzeroes. It is also always possible to have in ${\bf G}$ exactly
one {\it zero} entry.

The {\it volume} of a lattice $\Lambda$, denoted $V( \Lambda )$,
is inversely proportional to the number of lattice points per unit
volume. More precisely, $V( \Lambda )$ may be defined as the
volume of the {\it fundamental parallelogram} $\Pi(\Lambda)$ in
$\R^2$, which is given by
$$
\Pi(\Lambda) \deff\ \{ \xi_1 v_1  + \xi_2 v_2 ~:~ 0 \leq \xi_i < 1, ~ ,i=1,2 \}
$$
There is a simple expression for the volume of $\Lambda$, namely,
$V(\Lambda)=| \det {\bf G} |$.

We say that $\Lambda$ induces a {\it lattice tiling} of $\cS$ if
the lattice points can be taken as the set $\cT$ to form a tiling
$(\cT,\cS)$.

\subsection{Cyclic Arrays and Periods}

We are now in a position to define the period of a doubly periodic
array and to define cyclic two-dimensional arrays. Let $\cA$ be a
doubly periodic two-dimensional array. Let $(\pi_1 , \pi_2 )$ and
$(\xi_1 , \xi_2 )$ two linearly independent vectors such that each
$i,j \in \Z$ satisfy $\cA(i+\pi_1 ,j+\pi_2 )=\cA(i+\xi_1 ,j+\xi_2
)=\cA(i,j)$. Let $s$ be the volume of the lattice formed from
$(\pi_1 , \pi_2 )$ and $(\xi_1 , \xi_2 )$. Let $(\pi_3 , \pi_4 )$
and $(\xi_3 , \xi_4 )$ be two linearly independent vectors for
which, each $i,j \in \Z$ satisfy $\cA(i+\pi_3 ,j+\pi_4
)=\cA(i+\xi_3 ,j+\xi_4 )=\cA(i,j)$. Let $s'$ be the volume of the
lattice formed from $(\pi_3 , \pi_4 )$ and $(\xi_3 , \xi_4 )$. If
$s' \geq s$ for each such pair of linearly independent vectors
then we say that $\{ (\pi_1 , \pi_2 ) , (\xi_1 , \xi_2 ) \}$ is
the \emph{period} of $\cA$ and $s$ is the \emph{volume} of $\cA$.
The period in the one-dimensional case has the role of the period
and the volume in the two-dimensional case.

Clearly, the period of a two-dimensional array is not unique. The
volume of the array is unique and can be calculated
from the given period. We have a
theorem in the two-dimensional case which is akin to Theorem~\ref{thm:period_one}.

\begin{theorem}
Let $\cA$ be a doubly periodic array with period $\{ (\pi_1 ,
\pi_2 ) , (\xi_1 , \xi_2 ) \}$. Let $(\pi_3 , \pi_4 )$ and $(\xi_3
, \xi_4 )$ be two linearly independent vectors for which, each
$i,j \in \Z$ satisfy $\cA(i+\pi_3 ,j+\pi_4 )=\cA(i+\xi_3 ,j+\xi_4
)=\cA(i,j)$. Let $s'$ be the volume of the lattice formed from
$(\pi_3 , \pi_4 )$ and $(\xi_3 , \xi_4 )$. If $s$ is the volume of
the lattice formed from $(\pi_1 , \pi_2 )$ and $(\xi_1 , \xi_2 )$
then $s$ divides $s'$.
\end{theorem}

A shape $\cS$ will be called \emph{cyclic} if there is a lattice
tiling $\Lambda$ for $\cS$. In a cyclic sequence the order of the
elements, in the sequence, is obvious. It is less obvious for a
two-dimensional shape. We will discuss this order in
Section~\ref{sec:folding}.

\section{Two-Dimensional Synchronization Arrays}
\label{sec:DDCs}

Several types of two-dimensional synchronization arrays are
defined in the literature. We start we a general definition which
was given in~\cite{BEMP1,BEMP2}. Let $\cS$ be a given shape, on
the square grid, with $m$ dots on grid points. $\cS$ is called a
\emph{distinct difference configuration} (DDC) if the
$\binom{m}{2}$ lines connecting dots are distinct either in their
length or in their slope. Several types of DDCs were defined in
the literature. The main focus of research which was done on this
topic is related to Costas arrays. A {\it Costas array} is an $m
\times m$ permutation array having exactly one dot in each row and
each column. Some results on Costas arrays are given
in~\cite{GoTa82,GoTa84,Gol84,Dra06,GoGo07}.

We now present a definition for a doubly periodic DDC. A
\emph{doubly periodic $\cS$-DDC} is a doubly periodic
two-dimensional array $\cA$ with period $\{ (\pi_1 , \pi_2 ) ,
(\xi_1 , \xi_2 ) \}$ such that the following three properties are
satisfied.

\begin{itemize}
\item The lattice formed by $(\pi_1 , \pi_2 )$ and $(\xi_1 , \xi_2
)$ is a lattice tiling for $\cS$.

\item Each copy of $\cS$ on the two-dimensional arrays $\cA$ is a
DDC.

\item In each two copies of $\cS$ in the tiling, the positions of
the dots are the same.
\end{itemize}

Doubly periodic DDCs and in particular Costas array were
considered in the past, e. g.~\cite{Etz11,MGC97,MoGo06}. There are
two essential constructions for Costas arrays, both of them form
doubly periodic DDCs. The first construction is due to Welch and
the second Construction is due to Golomb (with a variant of
Lempel)~\cite{GoTa82,GoTa84,Gol84}. We will present both of them
in their doubly periodic version.

\noindent {\bf The periodic Welch Construction:}

Let $\alpha$ be a primitive root modulo a prime $p$ and let $\cA$
be the square grid. For any integers $i$ and $j$, there is a dot
in $\cA(i,j)$ if and only if $\alpha^i \equiv j \bmod p$.

\begin{theorem}
Let $\cA$ be the array of dots from the Periodic Welch
Construction. Then $\cA$ is a doubly periodic $\cS$-DDC with
period $\{ (0,p),(p-1,0) \}$ and $\cS$ is a $p \times (p-1)$
rectangle.
\end{theorem}

\vspace{1mm} \noindent {\bf The periodic Golomb Construction:}

Let $\alpha$ and $\beta$ be two primitive elements in GF($q$), where
$q$ is a prime power. For any integers $i$ and $j$, there is a dot in
$\cA(i,j)$ if and only if $\alpha^i + \beta^j =1$.

\begin{theorem}
\label{thm:periodicGolomb} Let $\cA$ be the array of dots from the
Periodic Golomb Construction. Then $\cA$ is a doubly periodic
$\cS$-DDC with period $\{ (0,q-1),(q-1,0) \}$ and $\cS$ is a
$(q-1) \times (q-1)$ square.
\end{theorem}

There are many important questions concerning Costas arrays. A few
of them are related to the periodicity of the arrays. In
particular we have the following two question:

\begin{enumerate}
\item Is the Welch construction generates all singly periodic
Costas arrays? where a singly periodic Costas array of order $n$
is an $n \times \infty$ array in which each $n \times n$ sub-array
is a Costas array. Welch Construction has this property for
$n=p-1$.

\item Are there more constructions for Costas arrays with
periodicity property?
\end{enumerate}

The conjecture is NO for both questions. Some evidence that this
conjecture is true is given in~\cite{EGT89}. In fact it should be
said that is very likely that most if not all Costas arrays are
known since they derived from the known
constructions~\cite{DIR10}. In what follows we will throw more
evidence for the difficulty to produce new doubly periodic
$\cS$-DDCs with many dots, different from those constructed by
folding~\cite{Etz11}.

Costas arrays are only one family of DDCs, and doubly periodic
DDCs. Two other families which were considered in the literature,
are the sonar sequences~\cite{GoTa82,Games87,MGC97,EGRT92}, and
the Golomb rectangles~\cite{Rob85,Rob97}.

\section{The Folding and Unfolding Methods}
\label{sec:folding}

This section is devoted to with a transformation of a periodic
sequence into a doubly periodic array and a transformation of a
doubly periodic array into a periodic sequence. The two
transformations will be called folding and unfolding,
respectively, and as one might expect these two transformations
are inverse of each other. As a consequence of the definition of
folding we will be able to define the order of the elements in a
cyclic shape. We will give the known theorems on the necessary and
sufficient conditions that a folding exists. Based on these
results we will define the inverse operation of unfolding. This
will lead to the main theorem which will state when a doubly
periodic two-dimensional DDC (or a cyclic DDC) is unfolded into a
Sidon sequences.

The definition of folding involves a lattice tiling $(\cT,\cS)$,
where $\cS$ is the shape on which the folding is performed. A {\it
direction} is a nonzero integer vector $(d_1,d_2)$, where $d_1 ,
d_2 \in \Z$.

Let $\cS$ be a two-dimensional shape and let $\delta=(d_1,d_2)$ be
a direction. Let $\Lambda$ be a lattice tiling for a shape $\cS$,
and let $\cS_1$ be the copy of $\cS$, in the related tiling, which
includes the origin. We define recursively a \emph{folded-row}
starting in the origin. If the point $(i_1,i_2)$ is the current
point of $\cS_1$ in the folded-row, then the next point on its
folded-row is defined as follows:
\begin{itemize}
\item If the point $(i_1+d_1,i_2+d_2)$ is in
$\cS_1$ then it is the next point on the folded-row.

\item If the point $(i_1+d_1,i_2+d_2)$ is in $\cS_2 \neq \cS_1$
whose center is in the point $(c_1,c_2)$ then
$(i_1+d_1-c_1,i_2+d_2-c_2)$ is the next point on the folded-row
(by Lemma~\ref{lem:center} this point is on $\cS_1$).
\end{itemize}

The definition of folding is based on a lattice $\Lambda$, a
shape $\cS$, and a direction $\delta$. The triple
$(\Lambda,\cS,\delta)$ defines a folding if the definition yields
a folded-row which includes all the elements of $\cS$. It appears
that only $\Lambda$ and $\delta$ determines whether the triple
$(\Lambda,\cS,\delta)$ defines a folding. The role of $\cS$ is
only in the order of the elements in the folded-row; and of course
$\Lambda$ must define a lattice tiling for $\cS$.

The first two lemmas proved in~\cite{Etz11} are an immediate
consequence of the definitions and provide us concise conditions
whether the triple $(\Lambda,\cS,\delta)$ defines a folding.

\begin{lemma}
Let $(\cT,\cS)$ be a lattice tiling defined by the two-dimensional
lattice $\Lambda$ and let $\delta = (d_1,d_2)$ be a direction.
$(\Lambda,\cS,\delta)$ defines a folding if and only if the set
$\{ (i \cdot d_1,i \cdot d_2)-c(i \cdot d_1,i \cdot d_2) ~:~ 0
\leq i < | \cS | \}$ contains $| \cS |$ distinct elements.
\end{lemma}

\begin{lemma}
Let $(\cT,\cS)$ be a lattice tiling defined by the two-dimensional
lattice $\Lambda$ and let $\delta = (d_1,d_2)$ be a direction.
$(\Lambda,\cS,\delta)$ defines a folding if and only if $(|\cS|
\cdot d_1,\cS| \cdot d_2)-c(|\cS| \cdot d_1,|\cS| \cdot
d_2)=(0,0)$ and for each $i$, $0 < i < |\cS|$ we have $(i \cdot
d_1,i \cdot d_2)-c(i \cdot d_1,i \cdot d_2) \neq (0,0)$.
\end{lemma}

The next theorem determine precisely when the triple
$(\Lambda,\cS,\delta)$ defines a folding.

\begin{theorem}
\label{thm:new_cond_fold2D} Let $\Lambda$ be a lattice whose
generator matrix is given by
$$
{\bf G}=\left[\begin{array}{cc}
v_{11} & v_{12} \\
v_{21} & v_{22}
\end{array}\right]~,
$$
where all the entries of ${\bf G}$ are nonzeroes.
Let $d_1$ and $d_2$ be two positive integers and $\tau =
\text{g.c.d.}(d_1 , d_2)$. If $\Lambda$ defines a lattice tiling
for the shape $\cS$ then the triple $(\Lambda,\cS,\delta)$ defines
a folding

\begin{itemize}
\item with the direction $\delta =(+d_1,+d_2)$ if and only if
$\text{g.c.d.}(\frac{d_1 v_{22}-d_2 v_{21}}{\tau},\frac{d_2
v_{11}-d_1 v_{12}}{\tau})=1$ and $\text{g.c.d.}(\tau , | \cS
|)=1$;

\item with the direction $\delta =(+d_1,-d_2)$ if and only if
$\text{g.c.d.}(\frac{d_1 v_{22}+d_2 v_{21}}{\tau},\frac{d_2
v_{11}+d_1 v_{12}}{\tau})=1$ and $\text{g.c.d.}(\tau , | \cS
|)=1$;

\item with the direction $\delta =(+d_1,0)$ if and only if
$\text{g.c.d.}(v_{12},v_{22})=1$ and $\text{g.c.d.}(d_1 , | \cS
|)=1$;

\item with the direction $\delta =(0,+d_2)$ if and only if
$\text{g.c.d.}(v_{11},v_{21})=1$ and $\text{g.c.d.}(d_2 , | \cS
|)=1$.
\end{itemize}
\end{theorem}

A direction $\delta$ for which $(\Lambda,\cS,\delta)$ defines a
folding also defines the order of the elements in a cyclic shape
$\cS$. This order is exactly the order of the elements in the
folded-row. It is easy to verify that only $|\cS|-1$ directions
should be considered for the existence of a folding. The order of
elements on $\cS$ is clearly not unique as it was proved
in~\cite{Etz11} that if one direction defines a folding then $\phi
(| \cS |)$ directions define a folding (and they come in pairs of
reverse order), where $\phi$ is the Euler totient function.

The unfolding operation is defined directly from the folding
operation. Let $\Lambda$ be a lattice tiling for a two-dimensional
shape $\cS$ and a let $\delta$ be a direction, for which
$(\Lambda,\cS,\delta)$ defines a folding. Then the folded-row is
the \emph{unfolded sequence} generated from the shape $\cS$. In
the folding, the folded-row indicates to which position of the
array, each element of a given one-dimensional sequence will be
assigned. In the unfolding, the folded-row is actually an
unfolded-row and it indicates to which position of the sequence,
each element of the array is assigned. These definitions are
completely natural and there is no surprise. What is more
interesting is the following theorem which connects
two-dimensional doubly periodic $\cS$-DDCs with Sidon sequences.

\begin{theorem}
\label{thm:2DtoSidon}
Let $\cA$ be a two-dimensional doubly periodic $\cS$-DDC with
period $\{ (\pi_1 , \pi_2 ) , (\xi_1 , \xi_2 ) \}$. Let $\Lambda$
be the lattice tiling of $\cS$ formed from $(\pi_1 , \pi_2 )$ and
$(\xi_1 , \xi_2 )$. If $\delta$ is a direction for which
$(\Lambda,\cS,\delta)$ defines a folding then the folded-row
generated by the unfolding of $\cS$ is a Sidon Sequence.
\end{theorem}
\begin{proof}
We will give a sketch of the proof. A proof with all the details
will appear in the full version of this work. We assign colors to
the points of the square grid as follows. The points of the shape
$\cS$ whose center is in the origin (say $\cS_0$) are assigned
colors by the order of the folded-row, where the origin is
assigned with a \emph{zero}. Each other copy of $\cS$ in the
tiling is assigned with the same colors as $\cS_0$ in the same
related positions.

Assume the contrary, that the folded-row is not a Sidon sequence.
It follows that there exists two distinct pairs of integers $(i_1
, i_2 )$ and $(i_3,i_4)$, where $i_1$, $i_2$, $i_3$, and $i_4$,
are positions with dots on the folded-row, such that $i_4 - i_3
\equiv i_2 - i_1 ~ (mod~n)$, where $n=|\cS|$. Let $\cS_j$, $1 \leq
j \leq 4$, a copy of $\cS$ on the grid in which a point colored
with $i_j$ is the center. It can be shown that in one of these
four copies the two pair of lines which connects the points
colored with $i_1$ and $i_2$ ad those colored with $i_3$ and $i_4$
are equal in length and slope. A contradiction to the assumption
that $\cA$ is
 a two-dimensional doubly periodic $\cS$-DDC.
\end{proof}

In~\cite{Etz11} the following theorem was proved.
\begin{theorem}
\label{thm:Sidonto2D} Let $\Lambda$ be a lattice tiling for a
two-dimensional shape $\cS$, $n=|\cS|$, and let $\delta$ be a
direction. Let $\cB$ be a Sidon sequence with $m$ elements over
$\Z_n$. If $(\Lambda,\cS,\delta)$ defines a folding then there
exists a two-dimensional doubly periodic $\cS$-DDC $\cA$ with $m$
dots in each copy of $\cS$ of $\cA$.
\end{theorem}

In view of Theorems~\ref{thm:2DtoSidon} and~\ref{thm:Sidonto2D} it
is tempting to prove that "a Sidon sequence over $\Z_n$ with $m$
elements exists if and only if a two-dimensional doubly periodic
$\cS$-DDC with $m$ dots in each copy of $\cS$ exists". But, this
claim is not correct. As we will conclude from the following
discussion, which applies Theorem~\ref{thm:2DtoSidon} on the known
doubly periodic constructions for Costas Arrays.

\begin{example} The following $7 \times 6$ array was obtained by
the periodic Welch Construction for $p=7$ and the primitive root 3
modulo 7.
$$
\begin{array}{|c|c|c|c|c|c|} \hline
&&&&&\\
\hline
&&&\bullet&&\\
\hline
&&&&&\bullet\\
\hline
&&&&\bullet&\\
\hline
&\bullet&&&&\\
\hline
&&\bullet&&&\\
\hline
\bullet&&&&&\\
\hline
\end{array}
$$
By using unfolding with direction $(1,1)$, where the lower left
dot is taken on the origin we obtain the Sidon sequence $\{
0,8,10,11,33,37\}$ modulo 42.
\end{example}
\begin{remark}
A construction such as the periodic Golomb Construction cannot
produce any Sidon sequence since the shape $\cS$ is a square and
the is no direction which defines a folding when $\cS$ is a
square.
\end{remark}

\section{New Optimal Sidon Sequences}
\label{sec:new}

The two celebrating constructions of optimal Sidon sequences are
the ones of Singer~\cite{Sin38} and Bose~\cite{Bose42}. Let $q$ be
a power of a prime number. Singer's construction, which is based
on projective planes, produces a Sidon sequence with $q+1$
elements over $\Z_{q^2 +q+1}$. Bose's construction, which is based
on affine planes, produces a Sidon set with $q$ elements over
$\Z_{q^2-1}$. The construction of Ruzsa~\cite{Ruz93} generates
optimal Sidon sequences with $p-1$ elements taken modulo $p^2 -p$,
where $p$ is a prime number. In this section we generalize this
construction to obtain a Sidon sequence with $q-1$ elements taken
over $(q-1) \times$GF($q$), where $q$ is any power of a prime.
Given a power of a prime $q$ and a primitive element $\alpha$ in
GF($q$), we construct the set $A_{q,\alpha}$ defined by
$$
A_{q,\alpha} = \{ (i, \alpha^i ) ~:~ 0 \leq i \leq q-2 ~ \}
$$

\begin{theorem}
The set $A_{q,\alpha}$ is an optimal Sidon sequence.
\end{theorem}
\begin{proof}
We have to prove that given four integers $i_1$, $i_2$, $i_3$, and
$i_4$, $0 \leq i_1 ,i_2 ,i_3 ,i_4 \leq q-2$, such that $i_1 \neq
i_3$ and $i_2 \neq i_3$ then the two pairs $(i_1 +i_2 ,
\alpha^{i_1} + \alpha^{i_2})$ and $(i_3 +i_4 , \alpha^{i_3} +
\alpha^{i_4})$ are not equal. Assume the contrary, that for four
such integers we have \vspace{-0.19cm}
\begin{equation}
\label{eq:base} i_1 + i_2 \equiv i_3 + i_4 ~(\text{mod}~q-1),~~~~
\alpha^{i_1} + \alpha^{i_2} = \alpha^{i_3} +\alpha^{i_4} ~.
\vspace{-0.1cm}
\end{equation}
Let $t \equiv i_1 - i_3 \equiv i_4 - i_2 ~(\text{mod}~q-1)$, where
clearly we can assume that $0 < t < q-1$. Hence, we replace
(\ref{eq:base}) with the equations \vspace{-0.19cm}
\begin{equation}
\label{eq:newbase} i_1 - i_3 \equiv i_4 - i_2
~(\text{mod}~q-1),~~~~ \alpha^{i_1} - \alpha^{i_3} = \alpha^{i_4}
-\alpha^{i_2} \vspace{-0.1cm}
\end{equation}
We can substitute $i_1 \equiv i_3 +t ~(\text{mod}~q-1)$ and $i_4
\equiv i_2 +t ~(\text{mod}~q-1)$ in (\ref{eq:newbase}) to obtain
the equation \vspace{-0.19cm}
\begin{equation*}
\alpha^{t+i_3} - \alpha^{i_3} = \alpha^{t+i_2} - \alpha^{i_2},
\vspace{-0.1cm}
\end{equation*}
which is equivalent to the equation \vspace{-0.19cm}
\begin{equation}
\label{eq:last} \alpha^{i_3} (\alpha^t -1) = \alpha^{i_2}
(\alpha^t -1) ~. \vspace{-0.1cm}
\end{equation}
Since $0 < t < q-1$, it follows that $\alpha^t -1 \neq 0$ and
hence from (\ref{eq:last}) we have that $\alpha^{i_3} =
\alpha^{i_2}$, i.e., $i_3 = i_2$ which contradicts the original
choice of $i_2$ and $i_3$. Therefore, $A_{q,\alpha}$ is a Sidon
sequence. The optimality of the sequence is a straight forward
enumeration.
\end{proof}

\begin{remark}
The new construction of Sidon sequences does not help in constructing new
doubly periodic $\cS$-DDC since the abelian group is not $\Z_n$.
\end{remark}

\section{conclusions and Future Research}
\label{sec:conclude}

Sidon sets have many applications in coding theory and in
communication problems. Constructions of optimal Sidon sequences
are rare. We defined periodicity and cyclic arrays in the
two-dimensional case. We proved that unfolded optimal doubly
periodic two-dimensional synchronization patterns are optimal
Sidon sequences. Thus, forming some equivalence between the two
structures. All the results concerning two-dimensional arrays are
generalized readily to higher dimensions. We presented a new
construction of optimal Sidon sequences, with $q-1$ elements, over
an alphabet with $q(q-1)$ elements, where $q$ is a power of a
prime. The main problem for future research in this direction is
to find new constructions for optimal doubly periodic DDCs and new
constructions for optimal Sidon sequences.

\section*{Acknowledgment}
This work was supported in part by the United States-Israel
Binational Science Foundation (BSF), Jerusalem, Israel, under
Grant No. 2006097.