# German Beams
The Story of Particle Accelerators in Germany

Volker Ziemann, Uppsala University, Uppsala, Sweden

###### Abstract

Even though many of the experiments leading to the standard model of particle
physics were done at large accelerator laboratories in the US and at CERN,
many exciting developments happened in smaller national facilities all over
the world. In this report we highlight the history of accelerator facilities
in Germany.

In Beams111V. Ziemann, Beams—the Story of Particle Accelerators and the
Science they Discover, Copernicus Books, Springer 2024. I describe the co-
evolution of particle accelerators and the standard model of elementary
particles. The majority of these experiments were done at the large
laboratories in the US and at CERN. There are, however, so many other
accelerators doing important experiments that it would be a shame not to
briefly talk about them as well. In the coming sections I will tell the story
of accelerators in Germany.

## Prehistory

The first particle accelerator in Germany was the linear accelerator that
Wideroe built for his PhD thesis (Chapter 4)222All references to chapters,
sections, and figures refer to “Beams” mentioned in footnote 1. in 1927.
Around 1936, rather than a linear accelerator, Gentner and Bothe333Walther
Bothe (1891-1957) received the Nobel Prize in Physics in 1954 “for the
coincidence method and his discoveries made therewith.” See also
https://www.nobelprize.org/prizes/physics/1954/. constructed a van de Graaff
accelerator (Figure 4.1) at the Kaiser-Wilhelm Institute of Medical Science in
Heidelberg. Once completed they used it for experiments in nuclear physics.
Assembling the machine had progressed very quickly and encouraged them to
think about a bigger accelerator—a cyclotron (Figure 4.4). Already in 1938
Wolfgang Gentner traveled to Berkeley and established contact with the group
of Lawrence, the inventor of the cyclotron. As a result he obtained blueprints
for many parts needed to construct his cyclotron. By 1941—the Second World War
had already broken out—Gentner and Bothe had secured funding. Immediately they
started designing the new cyclotron and ordered the main components. During
the spring of 1943 the 70-ton magnet arrived and by the end of the year the
cyclotron produced deuterons with an energy of 12 MeV. It operated into the
1970s.

The cyclotron in Heidelberg was not the only one. Several others were planned
in Berlin, Leipzig, and Bonn.

## Bonn

In Bonn, a smaller 1.5 MeV cyclotron was constructed at about the same time as
Gentner’s machine in Heidelberg. Sadly it was destroyed during an allied bomb
raid in October 1944.

It took until 1952, after having learned about alternating-gradient focusing
(Chapter 6), that Wolfgang Paul444Wolfgang Paul (1913-1993) received the Nobel
Prize in Physics in 1989 “for the development of the ion trap technique.” See
also https://www.nobelprize.org/prizes/physics/1989/. applied for funds to
build a 100 MeV electron synchrotron (Chapter 8) in Bonn. Remarkably, the
funding agency suggested to increase the energy to 500 MeV. After suitably
adapting the application, the project was approved and resulted in the first
alternating-gradient synchrotron in Europe555For the history of this machine
see: B. Mecking, Das Bonner 500 MeV Elektronensynchrotron, Bonn-IR-85-02 (in
German).. After designing the machine with its 16 m circumference throughout
the following years, often with the help of young students, construction
commenced in 1955. It took three years until all components were delivered and
installed. But then a crisis struck because it was realized that the magnetic
field was unsuitable for stable operation. The problem was eventually solved
by sandwiching plywood sheets between magnets which sufficiently changed the
fields to allow stable operation. By the spring of 1958, first beams were
available and even synchrotron radiation was observed. In the following years
the beams were directed onto tungsten targets in order to produce
“bremsstrahlung” which are just highly energetic gamma rays. By directing
these gamma rays onto protons or deuterons and observing the scattering
products (Chapter 2) much was learned about the structure of atomic nuclei.
The experimental program continued until 1984, when the 500 MeV synchrotron
was dismantled to make space for ELSA, discussed below.

Already a few years after the 500 MeV synchrotron produced beams, the need for
a larger electron synchrotron, reaching 2500 MeV, became apparent. Towards the
end of 1963, the state government provided funds, such that design of the
accelerator could start666K. Althoff et al., The 2.5 GeV Electron Synchrotron
of the University of Bonn, Nuclear Instruments and Methods 61 (1968) 1.. With
a circumference of almost 70 m it became substantially larger than its smaller
brethren. Four years later the first electrons were injected from a 25 MeV
linear accelerator into the new synchrotron and accelerated up to the design
energy. After a while the beams could even be extracted and directed towards a
number of experimental stations, where they impinged on a variety of targets,
often containing protons or deuterons. The machine operated in this mode until
1984, at which point the ELectron-Stretcher-Accelerator ELSA was constructed
adjacent to the larger synchrotron.

Synchrotrons provide a short burst of beams, typically 50 times per second,
but many experiments desire a continuous stream of electrons. One solution is
to inject the short burst into a larger so-called stretcher ring. In this ring
one or several pulses from the synchrotron are collected before the stored
electrons are slowly extracted and guided to experiments. The project already
went under way in the early 1980s, but it took until 1989 to complete the
construction of ELSA777For an account of the history leading to construction
of ELSA, see: W. Hillert, The Bonn Electron Stretcher Accelerator ELSA: Past
and future, Eur. Phys. J. A 28, s01 (2006) 139. with its circumference of 164
m and to connect it to the larger synchrotron that was used as an injector.
Once the electrons were inside ELSA, they could be slowly extracted, just as
was initially planned. Even accelerating the beams and extracting them at
higher energies became possible. Finally, beams could be accumulated in ELSA
and stored for several hours to provide synchrotron radiation. In this way,
ELSA doubled up as a synchrotron light source (Section 13.1).

Much expertise was generated by constructing the smaller synchrotron, being
the first of its kind. And that competence came handy when a larger
synchrotron was planned in Hamburg.

## DESY

By 1955 Germany had regained part of its sovereignty and was permitted to
create a ministry for nuclear energy. Moreover, this new ministry was willing
to fund an institute for research in particle physics; the creation of CERN in
Geneva the previous year served as a inspiration. Incidentally, at that time
Hamburg University offered a professorship to the US-based Austrian scientist
Willibald Jentschke, who accepted after being granted substantial funds to
create a new department, which served as the nucleus for what would later
become DESY888For a comprehensive account of DESY’s first fifty years, see: E.
Lohrmann, P. Söding, Von schellen Teilchen und hellem Licht, Wiley-VCH
Weinheim, 2009 (in German). The second edition from 2013 is available online
from https://bib-pubdb1.desy.de/record/374686..

The type of accelerator was settled at a conference in Geneva the following
year. Instead of a proton synchrotron, which would be in direct competition
with the accelerator at CERN (Chapter 6), Jentschke decided to build an
electron synchrotron (Chapter 8) with the unprecedented energy of 6 GeV, more
than ten times the energy of the first synchrotron in Bonn. During the
following years negotiations between federal and state agencies led to the
constitution of the “Deutsches Elektronen SYnchrotron” DESY in December 1959.
An abandoned airfield in the suburb of Bahrenfeld was selected as the site to
house a 40 MeV linear accelerator, used as injector, and the 300 m long
synchrotron. It took until 1964 for the first beams to be accelerated. Fifty
times per second a new batch reached top energy, was ejected from the
synchrotron, and directed towards experimental stations.

The first experiments pointed the electrons onto hydrogen-rich targets and
analyzed the scattering products in spectrometers, conceptually similar to
Hofstadter’s experiments discussed in Chapter 7. A second group of experiments
directed the electrons onto a target where they produce gamma-ray photons that
are then impinged onto protons. Subsequently the photon-induced reactions and
scattering products are analyzed. A third group of experiments directed the
electrons into a bubble chamber (Figure 5.5), photographing the tracks, and
analyzing the reactions that show up. Right after beams became available, the
copious synchrotron radiation emitted by the 6 GeV electrons was characterized
and used for first experiments.

Figure 1: Sketch of the accelerators at DESY.

Already a few years after the synchrotron started to operate, ideas were
discussed to build a second accelerator in which electrons and positrons would
circulate in opposite directions and collide head-on (Figure 8.1). In this way
much more energy would become available for new particles to emerge from the
fireball at the collision points. There detectors stood by to record the
escaping particles. At the time it was deemed advantageous to store electrons
and positrons in separate rings, mounted on top of each other. This new
storage ring was given the name DORIS (derived from the German “DOppel-RIng
Speicher”). It had a circumference of 288 m and initially stored electrons and
positrons with energies of up to 3 GeV.

Towards the end of 1974, the two detectors PLUTO and DASP were placed in their
respective collision points. At just this time SLAC and Brookhaven discovered
the very sharp resonance made of charm and anticharm quark (Chapter 8), an
event later referred to as the “November revolution.” DORIS verified these
discoveries within a very short time and then successfully searched for mesons
consisting of one charm and one other quark. Later it engaged in the detailed
analysis of many bound states, an activity that was dubbed “charmonium
spectroscopy.” Just as upgrading DORIS to higher energies was under way, the
Upsilon as a bound state of two bottom quarks was discovered at Fermilab in
1977 (Chapter 9). Luckily the magnets were already somewhat over-designed from
the beginning and could handle the higher energies. Nevertheless, additional
components and smart ideas were asked for to eventually reach close to 5 GeV
per beam which made the production of Upsilons possible. Observing their decay
into muon and electron pairs were important ingredients to determine the
charge of the bottom quark. DORIS then embarked on a campaign to determine
other properties of the quarks and the strong interaction.

In order to consolidate operating at higher energies DORIS was upgraded in
1982 to reemerge as DORIS II. It now stored electrons and positrons in a
single ring, rather than the “Doppel-ring” that gave DORIS its name. The
higher energies of 5.6 GeV per beam allowed the two new detectors, ARGUS and
Crystal Ball, to investigate pairs of $B$-mesons and their antiparticles
$\bar{B}$, each containing a bottom quark and one other quark. This led to the
first observation of $B$-$\bar{B}$-mixing, a process closely linked to the
prevalence of matter over antimatter in our universe that is referred to as
CP-violation (Chapter 10).

All the time, the number of synchrotron-radiation users increased. A large
laboratory building housing their experiments was completed by 1982 and was
dubbed “Hasylab,” derived from “HAmburger SYnchrotron LABoratory.” Increasing
demands led to yet another upgrade to DORIS III in 1991, now equipped with an
outward-bulging no-longer-straight section. There five wigglers and undulators
(Section 13.1) were installed to increase the flux and the quality of the
emitted synchrotron radiation. By that time most particle physics activities
concentrated on the next-generation colliders PETRA and HERA such that from
1993 until 2012 DORIS operated solely to produce synchrotron radiation.
Research highlights include Ada Yonath’s studies999Ada Yonath (b. 1939)
received the Nobel prize in Chemistry “for studies of the structure and
function of the ribosome.” See also
https://www.nobelprize.org/prizes/chemistry/2009/. of ribosomes, the engines
that produce proteins in cells.

Already by the time DORIS was starting up, discussions about the next
generation of accelerators were picking up speed and converged towards the
electron-positron collider PETRA (from the German “Positron-Electron Tandem
RingbeschleunigerAnlage”). With a circumference of 2.3 km it was the largest
ring that would fit onto the DESY site. It should reach more than 20 GeV per
beam and provide four collision points for experiments housing the detectors
TASSO, MARK J, JADE, and PLUTO; the latter was later replaced by CELLO.
Approval came in 1975 and less than three years later the beams were
colliding. The hope to find the sixth quark, called top, remained unfulfilled.
It turned out to be much too heavy for PETRA and other rings of similar size.
Instead, the highlight of research on PETRA was the discovery of gluons
through the observation of three-jet events (Figure 8.7), already mentioned
towards the end of Chapter 8. Many careful measurements revealed intricate
details of subatomic interactions and contributed to establishing quantum
chromodynamics as a valid theory of the strong interaction (Chapter 7).
Moreover, many aspects of the electroweak interaction (Chapter 6) were
explored. The experimental program continued until the end of 1986. At that
time PETRA was needed as injector for an even larger ring, the “Hadron-
Electron Ring Accelerator” HERA.

After plans to add a proton ring inside the PETRA tunnel were abandoned, a
proposal to build a new 6.3 km long underground tunnel was put forward. This
tunnel would house HERA comprising a 820 GeV proton and a 30 GeV electron
ring. Head-on collisions of electrons and protons at these energies would
allow the experimenters to probe the inside of the proton much more accurately
than was possible in the deep-inelastic scattering experiments at SLAC
(Chapter 8). After a period of negotiations the project was approved in 1984
and construction could start. A large tunnel-boring machine, similar to the
one that dug the tunnel of LEP (Chapter 10) drilled the 6.3 km long tunnel 10
m to 20 m below the surface. The DESY synchrotron, rebuilt and called DESY II,
as well as PETRA were used to accelerate the electrons. Accelerating protons,
on the other hand, was new for DESY and a second synchrotron for protons,
called DESY III, was installed alongside the venerable electron synchrotron.
Additional components were added to PETRA, now called PETRA II, that allowed
it to accelerate protons. The electron ring of HERA is fairly conventional,
but the magnets for the proton ring had to be superconducting in order to fit
the high-energy beams into the tunnel, just as the Tevatron needed
superconducting magnets at Fermilab (Chapter 9). After meticulous development
work at DESY the manufacture of the 750 up to 9 m long magnets was transferred
to industry, half in Germany, the other half in Italy. The magnets were cooled
to low temperatures by the, at the time, largest Helium liquefaction plant in
Europe. After installing and testing many more components, HERA was
inaugurated towards the end of 1990. Commissioning all subsystems, including
the detectors H1 and ZEUS, took more time but by 1992 first collisions were
observed. Later even two additional detectors, HERA-B and HERMES, were
installed.

The detectors extended the deep-inelastic scattering results, pioneered at the
SLAC linac, to much smaller distances inside the proton, thereby validating
the standard model. In particular, the momentum distribution of the quarks
inside protons was measured with unprecedented accuracy. Moreover, there
appeared to be additional quark-antiquark pairs bouncing around inside
protons. Even previously unseen reactions that have their origin in the weak
interaction were found; only a single shower of hadrons appeared besides an
unobservable neutrino. Its existence was inferred by balancing the energy and
the momentum of the observed ejectiles. Experiments in HERA continued until
2007, when the accelerator was turned off, because DESY started to build the
European XFEL, a large free-electron laser (Section 13.2) to produce X-rays.
With HERA turned off, PETRA was no longer needed as injector and one octant
was be refurbished to house undulators that generate copious amounts of high-
quality synchrotron radiation. The rebuilt machine was called PETRA III. As of
2024, even a further upgrade, called PETRA IV, to improve the amount and
quality of the emitted radiation, is actively discussed.

The work towards the XFEL started from designing a linear electron-positron
collider (Chapter 12) called TESLA, that would use superconducting
accelerating structures (Chapter 10). In order to broaden the number of users
beyond the particle physics community, an X-ray free-electron laser was added
to the proposal; it would serve the community of synchrotron radiation users.
In order to test the concept—both the accelerating structures and the free-
electron laser—a 100 m long superconducting linac accelerated beams to about
250 MeV and passed them through a 13 m long undulator magnet. With all
parameters tuned just right, the machine would emit a high-intensity free-
electron laser pulse (Section 13.2). This Tesla-Test Facility (TTF) was
constructed on the DESY site and produced very short-wavelength light pulses
in 2000. Shortly afterwards the machine, renamed FLASH101010For a
comprehensive review see: J. Rossbach, J. Schneider, and W. Wurth, 10 years of
pioneering X-ray science at the Free-Electron Laser FLASH at DESY, Physics
Reports 808 (2019) 1. (for “Free-Electron LASer in Hamburg”), was rebuilt to
increase the energy to 1000 MeV. Moreover, a new undulator, now 30 m long, led
to first lasing at much shorter wavelengths by 2004. Continued upgrades and an
additional undulator have vastly enhanced the capabilities of FLASH. In one of
the many experimental highlights the scattered light from a microscopic sample
was processed to reconstruct the sample with high fidelity; a precursor to
determine the structure of many otherwise inaccessible biomolecules.

But originally TTF was constructed to develop the superconducting accelerating
structures that were successfully used in TTF and FLASH. Despite this success
the application to build TESLA was turned down. Instead, based on the success
of the free-electron laser program, the funding agencies supported the
construction of a much larger version of FLASH, the European XFEL. About two
thirds of this 3.2 km long machine is filled with superconducting structures
to reach beam energies close to 20 GeV. The last third is filled with several-
hundred-meter-long undulator magnets that produce ultra-short and super-
intense pulses of X-rays. Since the completion of the facility in 2017, this
radiation permits experimenters to investigate the structure of proteins, make
time-resolved measurements (“movies”) of chemical reactions, and explore
matter under extreme conditions.

At DESY, a particle physics lab was slowly converted to one that pursues
synchrotron radiation research. In Berlin, on the other hand, a facility
dedicated to the generation of this radiation right from the start was
constructed.

## BESSY in Berlin

By 1975, both the accelerators in Bonn and Hamburg were producing synchrotron
radiation, quasi on the side, but the demand was growing. As a consequence a
review was conducted and found that two storage rings, dedicated to the
production of synchrotron radiation, were needed. A larger one for the
production of X-rays that turned out to be DORIS and a smaller machine to
generate radiation with lower energies. The formal decision to build the
latter came in 1979 and construction of BESSY (derived from “Berliner
ElektronenSpeicherring Gesellschaft für SYnchrotronstrahlung”) soon
commenced111111D. Einfeld, G. Mühlhaupt, Choice of the Principal Parameters
and Lattice of BESSY, an 800 MeV Dedicated Light Source, Nuclear Instruments
and Methods 172 (1980) 55.. Less than three years later, beams, accelerated in
a small pre-accelerator, and an injector synchrotron to 800 MeV, were injected
into the BESSY storage ring having a circumference of 62 m. Throughout the
1980s and 1990s the beam quality and intensity were improved and with it the
quality of the synchrotron radiation that escaped the beam pipe through 35
windows. Highlights of the instrumental developments are new types of
undulator magnets121212Of particular interest are so-called Apple undulators
that allow to adjust the polarization of the emitted radiation. Today they are
used in practically every synchrotron light source. (Section 13.1) and methods
to ensure the quality of optical components that guide and focus the
synchrotron light on its way to the experimental stations.

Highlights of the experimental program are Peter Grünberg’s experiments on
what was later called giant magnetoresistance. This effect led the way to
vastly increased storage capacities of hard drives in our computers and was
honored with a Nobel Prize in Physics131313Peter Grünberg (1939-2018) received
the Nobel Prize in Physics in 2007 “for the discovery of giant
magnetoresistance.” See also https://www.nobelprize.org/prizes/physics/2007/..
Surface physics and catalysis are other fields of endeavor that were pursued
at BESSY. These phenomena are tremendously important to facilitate difficult
chemical reactions, such as converting toxic gases in car exhausts to more
benign chemicals. The high impact of this research contributed to Gerhard
Ertl’s Nobel Prize in Chemistry141414Gerhard Ertl (b.1936) received the Nobel
Prize in Chemistry in 2007 “for his studies of chemical processes on solid
surfaces.” See also https://www.nobelprize.org/prizes/chemistry/2007/..

The distribution of wavelengths—the spectrum—and the intensity of the emitted
radiation can be calculated from first principles and only depends on very few
beam parameters. Since those quantities can be very accurately measured, the
emitted radiation is known with high confidence and can be used to calibrate
other measurement devices, such as spectrometers. These activities were driven
under the auspices of the German authority for measurements, abbreviated
PTB151515PTB is a acronym, derived from “Physikalisch Technische
Bundesanstalt.”. In particular, they were responsible for the calibration of
instruments for two space-telescopes, SOHO and Chandra. The accelerator
operated until 1999 and was then packed up and shipped to Jordan, where it was
reassembled and now serves as injector for SESAME, the first synchrotron light
source in the middle-east.

A few years after the first BESSY storage ring started to produce light in the
early 1980s, proposals for several so-called third-generation light sources
with vastly improved quality and intensities were discussed world-wide. Such
an accelerator would be several times larger than BESSY and would not fit
within the limits of the original site in West-Berlin. With the fall of the
Berlin wall in 1989, however, new options appeared and a site in former East-
Berlin was chosen to become the home of BESSY-II161616For more background on
BESSY-II, see the brochure: 25 Years of BESSY-II: A Success Story in Berlin-
Adlershof, special edition of “Lichtblick” from September 2023; online
available from the following web page
https://www.helmholtz.de/en/newsroom/article/25-years-of-bessy-ii-light-
source-for-the-good-of-society/.. Construction started in 1993 and five years
later an injector synchrotron filled the new BESSY-II storage ring, having a
circumference of 240 m and operating at 1.7 GeV for the first time. A year
later first photons, produced in special undulator magnets but also in the
magnets that keep the beam on its circular path, were served to users. The
photons follow a straight path and escape from the beam pipe to travel via
more than forty so-called synchrotron beam lines towards the experimental
stations.

With higher beam energies, radiation in the X-ray region could be produced. It
was used to analyze the structure of materials and of proteins. Even the
structure of proteins of the Covid virus were determined at BESSY-II. A
further very active field of research addresses materials for new batteries
and for high-temperature superconductors. Both aspects are particularly
relevant to improve the efficiency of energy utilization. Even the PTB
continues to calibrate instruments with the help of BESSY-II, especially at
higher photon energies. The reduced availability of lower-energy photons
caused the PTB to construct a second smaller ring, the “Metrology Light
Source” (MLS) adjacent to the BESSY-II site.

Construction of the MLS171717G. Brandt et al., The Metrology Light Source –
The new dedicated electron storage ring of PTB, Nuclear Instruments and
Methods B258 (2007) 445. started in 2004 and first beams became available in
2008, predominantly for metrology applications, such as calibrating
spectrometers but also other sources of light used in industrial processes or
in scientific applications. The MLS has a circumference of 48 m and stores
electron beams with energies between 105 MeV and 630 MeV. Remarkably, the MLS
reproducibly stores beam intensities ranging from a single electron to several
ten billions of electrons, with the intensity of the emitted radiation
covering the corresponding range. Moreover, the synchrotron radiation covers
the far infrared to the extreme ultraviolet. It thus extends from far below
the visible spectrum to significantly above. Since the properties of the
emitted radiation can be calculated from first principles, the MLS serves as a
“standard candle” to calibrate other sources or spectrometers.

Bessy and DESY were not the only laboratories producing synchrotron radiation.
Towards the end of the millennium, mid-size electron accelerators appeared in
several other places, among them Dortmund.

## Dortmund

Following the decision on the European level to locate the European
Synchrotron Radiation Facility in Grenoble instead of Dortmund, negotiations
on the regional level succeeded to secure funds for building a smaller
accelerator, the “Dortmund ELectron Test Accelerator” DELTA181818D. Nölle et
al., DELTA a new storage-ring-fel facility at the University of Dortmund,
Nuclear Instruments and Methods A296 (1990) 263.. Construction started in 1990
and and by the second half of the 1990s first beams were accelerated in a
linac and a synchrotron to 1.5 GeV before they were stored in the DELTA
storage ring with a circumference of 115 m. The declared purpose of DELTA was
developing and testing of components for larger facilities, preparing
experiments with synchrotron radiation, educating a new generation of
accelerator builders191919I am one of the substantial number of graduates that
emerged from DELTA and populate accelerator labs all over Europe., and a first
free-electron laser experiment called FELICITA202020D. Nölle et al., First
lasing of the FELICITA I FEL at DELTA, Nuclear Instruments and Methods A445
(2000) 128. FELICITA is an acronym for “Free-Electron Laser In a Circular Test
Accelerator.” It also happens to be the middle name of my wife; what a
coincidence..

After the free-electron laser experiment was successfully completed the demand
for synchrotron radiation from the user community increased. As a consequence
the originally foreseen program was ramped down while the production of
photons to serve users was ramped up. The increased demand was then satisfied
by installing additional wigglers and undulators to increase the experimental
capabilities to provide an increasing number of users with synchrotron
radiation.

## Karlsruhe

Before building the first linear accelerator (Chapter 4), Rolf Wideroe had
already conceived the betatron (Chapter 4) while he was a student in
Karlsruhe, though he was advised not to pursue the idea further. Much later,
in the 1980s, ideas of building a much larger accelerator emerged and a
storage ring for industrial applications of synchrotron radiation was
proposed. This proposal was refined throughout the 1990s and led to the
construction of ANKA (from “ÅNgströmquelle KArlsruhe”), an electron storage
ring with a circumference of 110 m and a beam energy of 2.5 GeV212121G. Buth
et al., Status of the 2.5 GeV Light Source ANKA, Proceedings of EPAC 1998 in
Stockholm, p. 635.. It stored the first beams in 1999. The high beam energy
and the large stored currents cause the emission of very intense X-rays that
are directed to multiple experimental stations. Moreover, industry could
simply purchase beam time from ANKA. This differs remarkably from the way how
beam time is allocated in accelerators that operate for pure science. There it
is assigned in a beauty contest—the scientifically most attractive experiments
get beam time.

One of the prime uses of the radiation from ANKA and of particular interest
for the semiconductor industry is the creation of microscopic mechanical
structures—precursors of the accelerometers and gyroscopes found in modern
phones—in a process called LIGA222222LIGA is the acronym derived from the
German phrase “Lithographie, Galvanoforming, und Abformung.”, which is a type
of X-ray lithography. The irradiation transfers the geometrical pattern of a
microscopic mask onto a substrate that is covered by a protective film. In a
second step the irradiated sections of the film are removed, and in a third
step an acid etches the pattern into the substrate, for example, silicon. In
another type of experiment the X-rays determine the structure of samples,
including proteins, on atomic scales. The wavelength of the radiation that is
transmitted to the samples can be adjusted in so-called monochromators to
excite deep-lying energy levels of atoms. Since these levels are specific to
the type of atom, very low concentrations of impurities in materials can be
identified.

Following a restructuring of the laboratory in 2015, access to external users
was limited and this was reflected by changing the name from ANKA to KARA (for
“KArlsruhe Research Accelerator”) and mainly using it for in-house
developments232323A. Papash et al., Different operation regimes at the KIT
Storage Ring KARA, Proceedings of IPAC 2021 in Campinas, p. 163.. After the
reorganization KARA was increasingly used to develop advanced beam diagnostic
equipment such as ultra-fast cameras to explore the dynamics of charged
particle beams on previously inaccessible time scales. Apart from developing
other super-fast electronics components, new technologies, among them
superconductivity, were used to construct undulators (Section 13.1) and other
very compact magnets, important for future accelerators.

In order to complement the very short-wavelength radiation from KARA, in 2017
the 12 m long linear accelerator FLUTE242424M. Nasse et al., FLUTE: A
versatile linac-based THz source, Rev. Sci. Instrum. 84 (2013) 022705.
(derived from the German “Ferninfrarot Linac Und Test Experiment”) started to
operate. It produces radiation with much longer wavelengths than KARA. FLUTE
accelerates electron beams to 50 MeV, compresses them to a very short length,
and then passes them through a thin foil, where ultra-short pulses of so-
called THz radiation are produced. This radiation is immensely useful to study
the dynamics of chemical bonds that bind atoms into molecules, a process of
great importance in biology, as well as material and life sciences.

## Dresden

Already in 1995 ideas were discussed to build a linear accelerator dubbed
ELBE252525ELBE is an acronym derived from “Electron Linear accelerator with
high Brilliance and low Emittance,” certainly inspired by the river Elbe that
flows through Dresden. in Rossendorf near Dresden that would deliver a
continuous stream of electrons for experiments in nuclear and radiation
physics262626A. Büchner et al., The ELBE-Project at Dresden-Rossendorf,
Proceeedings of EPAC 2000 in Vienna, p. 732.. To keep operating costs for this
linac reasonable the accelerator had to be superconducting. Moreover, high
demands on the beam quality stimulated the development of high-performing
electron sources. By 2001 the first 6 m long accelerator stage delivered beams
up to 20 MeV, later a second stage was added and brought the energy to 40 MeV.
A system of beam transport lines directs the electrons to several experimental
areas272727M. Helm et al., The ELBE infrared and THz facility at Helmholtz-
Zentrum Dresden-Rossendorf, Eur. Phys. J. Plus (2023) 138..

There the electrons are used to drive two free-electron lasers producing far-
infrared radiation that is used to probe material-science samples. The
radiation is often used in so-called pump-probe experiments. First a sample is
excited with a pulse from the free-electron laser and then a delayed second
pulse from a conventional laser probes the sample. In this way, the temporal
evolution of very fast processes can be investigated.

A specially developed electron source produces electron bunches that are
shorter than the wavelength of the radiation emitted in a short undulator
magnet. This causes a dramatically increased emission, because all electrons
radiate in phase. The enhanced radiation level makes it possible to explore
the properties of graphene, among other things.

The electrons are used for many other purposes. They are crashed into targets
and produce very high-energy bremsstrahlung to probe the energy levels of
nuclei. Moreover, they are used to produce neutrons by crashing the beam into
a liquid-lead target. Even positrons can be produced. They are used to probe
material defects in metals and in semiconductors.

## Darmstadt

Inspired by Hofstadter’s electron-scattering experiments in Stanford (Chapter
7), the nuclear physics department in Darmstadt purchased a 60 MeV linac from
Varian Associates (Chapter 7). By 1962 the 10 m long linac, called DALINAC,
started to produce beams that impinged on a variety of targets282828F. Gudden
et al., Eine Anordnung für Experimente zur Elektronenstreuung unterhalb 60
MeV, Zitschrift für Physik 181 (1964) 453 (in German).. The escaping particles
were analyzed in spectrometers not unlike the one shown on Figure 7.4. In
particular, details of the nuclear structure were determined by inelastically
scattering electrons (middle image in Figure 7.3) from a large variety of
nuclei, all the way up to uranium. The linac operated well into the 1980s at
which time a more powerful linac with better beam quality was discussed.

The new accelerator was called S-DALINAC and consisted of a 16 m long linac
based on superconducting radio-frequency structures (Chapter 10). Two
recirculation arcs that allowed reusing the same linac three times, at which
point the electrons reached 130 MeV and were directed to experimental areas.
Instead of a pulsed beam, the new linac provided a continuous stream of
electrons. First beams were accelerated in 1987 and henceforth used in nuclear
physics experiments. Early on it was realized that the new linac could be used
for a free-electron laser (Section 13.2) as well292929V. Aab et al., The
Darmstadt near-infrared free-electron laser project, Nuclear Instruments and
Methods A272 (1988) 53.. After installing additional hardware, the laser
started to produce the first photons in 1996. These photons are routed to a
separate room, dedicated to optical experiments.

Apart from experiments for nuclear physics and with the photons from the free-
electron laser, S-DALINAC serves as a test facility to explore advanced
manipulations with the beams themselves. In one of these experiments, the
energy of the beam is recovered inside the structures that were used to
accelerate it in the first place. The original beam is discarded, but its
energy is reused to accelerate new beams, thus the machine becomes a so-called
energy-recovery linac.

Not only electrons can be used in nuclear physics experiments, also
accelerated beams of heavy ions provide suitable projectiles to explore the
inner workings of nuclear matter. Close to Darmstadt, in a nearby village, a
new lab appeared in the late 1960s.

## GSI and FAIR

During the 1960s accelerators for heavy ions were discussed303030For an early
account see: K. Blasche, H Prange, Die GSI in Darmstadt (I), Physikalische
Blätter 33 (1977) 249 (in German). Online available from
https://doi.org/10.1002/phbl.19770330602. The GSI website at
https://www.gsi.de/en/about_us/ provides a wealth of more up-to-date
information. as tools to analyze nuclear matter with methods that were
complementary to those of high-energy proton or electron accelerators that
were used to look inside protons and other sub-nuclear particles at the time.
Instead, the new facility would focus on the collective behavior of large
numbers of protons and neutrons inside heavier nuclei. As a consequence of
these discussions, the “Gesellschaft für SchwerIonenforschung” (GSI) was
founded in 1969 and the construction of the approximately 120 m long linear
accelerator, called UNILAC, soon started. It was based on drift tubes
developed by Wideroe (Figure 4.2) and Alvarez (Figure 5.3). However, with a
diameter of 1.2 m the vacuum vessel is much larger. By 1975 it accelerated
beams up to energies of 11 MeV per nucleon. The total energy of uranium with
238 nucleons (92 protons and 146 neutrons) is therefore in the GeV range. At
these energies the speed of the uranium ions is about 16 % of the speed of
light. Soon experiments in two experimental areas commenced by impinging the
heavy-ion beams onto targets. Detectors then analyze whatever scattering
products escape from the point of impact.

Of particular interest is the distribution of fragments with different numbers
of protons and neutrons (isotopes) that are created in the collision, because
it shows how the nucleons are organized inside the nucleus. Thereby it probes
the organization of nucleons into shells313131Maria Goeppert-Mayer (1906-1975)
and Hans Jensen (1907-1973) received the Nobel Prize for Physics in 1963 “for
their discoveries concerning nuclear shell structure.” See also
https://www.nobelprize.org/prizes/physics/1963/.. These experiments help us to
better understand the stability of nuclei, especially in extreme situations as
they occur in very heavy nuclei. Some of the lighter isotopes feature in the
creation of heavier elements inside stars and supernovae, a process called
“nucleosynthesis”. In particular, measuring their masses and lifetimes helps
us understand the relative abundance of different elements in our universe.

The heaviest naturally occurring element on the periodic table is uranium with
atomic number 92. Since the 1940s heavier elements, so-called transuranium
elements, were created in nuclear reactors and in accelerators. Once the
UNILAC was up and running, it joined the search for previously unseen heavier
elements. And indeed, between 1981 and 1984, the three elements with atomic
numbers 107, 108, and 109323232The transuranium elements 107 to 109 are
nowadays called bohrium, hassium, and meitnerium, respectively. were
discovered at GSI. Bohrium with atomic number 107, for example, was created by
slamming chromium ions into a bismuth target and then filtering the debris to
select particles with a specific mass using an elaborate setup of magnetic and
electric fields, called SHIP, short for “Separator for Heavy Ion Products.”
Other combinations of beams and targets were used to create the other new
elements. And about ten years later, between 1994 and 1996, the team at GSI
repeated their success and found elements 110, 111, and 112333333The
transuranium elements 110 to 112 are nowadays called darmstadtium,
roentgenium, and copernicium, respectively.. In the decade between the element
discoveries, many other experiments were performed and, most importantly, the
facility was upgraded by adding a synchrotron and a storage ring.

Figure 2: Sketch of GSI and the FAIR facility.

Already in the early 1980s, different options to increase the energy of the
beams were discussed and finally converged on a synchrotron (Chapter 5), for
technical reasons called SIS18, and the ESR, short for “Experimentier
SpeicherRing.” SIS18 has a circumference of 216 m and increases the energy of
beams by large factors. At the same time their speed increases from 16 % to 90
% of the speed of light. The accelerated beams are then directed onto a target
and the debris is filtered by a special beam line consisting of magnets and
thin absorbers, called FRS, short for “FRagment Separator.” Only one specific
nucleus containing a particular number of protons and neutrons (a specific
isotope) emerges at the exit of FRS and is injected into the ESR with half the
circumference of SIS18. In the ESR a stochastic cooling system (Figure 9.4)
improves the beam quality of the injected ions. Additionally, an electron
cooler superimposes a high-quality electron beam with the stored ion beam.
This allows the ions to bounce off the electrons and thereby lose some of
their random motion. This process then slowly “cools” the ions and makes it
possible to measure their revolution frequency with very high precision from
which the mass of the injected isotope can be derived. This method was used to
analyze a wide variety of isotopes thus improving our understanding of nuclear
matter.

Since the early 1990s, GSI explored the use of ion beams to treat cancer.
Especially carbon ions showed a distinct advantage over conventional therapy
with X-rays or electrons, because the carbon ions cause much more damage in
deep-seated tumors while causing less harm in surrounding healthy tissue. The
depth of the tumor-damage can be adjusted by adjusting the energy of the SIS18
synchrotron. The extension of the tumor in the sideways directions is covered
by raster-scanning the ion beam with the help of magnets. During the process
that destroys a tumor, positrons are created that annihilate with nearby
electrons and give rise to two characteristic X-ray photons that reveal their
point of origin. In this positron-emission tomographic (PET) process the
deposited dose is verified while the patient is treated. The pilot project at
GSI was such a success that a similar facility comprising synchrotron and
raster-scanning target system was built in Heidelberg and treats patients from
2009 onwards. A few years later similar systems started operating in Marburg,
Shanghai (China), Pavia (Italy), and Vienna (Austria).

Once SIS18 and the ESR were in operation in the mid-1990s, discussions started
about the future needs of the nuclear physics community. It came up with a
proposal for the “Facility for Antiproton and Ion Research” (FAIR)343434See
the online presentation at https://fair-center.eu/ for more information.. The
funding agencies recommended to jointly construct the facility with
international partners. By 2010, all partners signed an agreement and FAIR was
officially founded. It still took several years until construction began.
Unfortunately it was delayed further due to massive increases in the cost, the
covid pandemic, and the Russian war in Ukraine. By the time of writing
construction, albeit on a reduced scope, is ongoing.

For FAIR, all the existing accelerators at GSI are upgraded and will become
part of the injector complex for the large synchrotron SIS100. With a
circumference of 1100 m it is about five times larger than SIS18 and reaches
about five times higher energies. Beams extracted from SIS100 are guided to
several experimental areas; one of them is the Super-FRS, a large fragment
separator to isolate exotic isotopes. The “Collector Ring” CR collects these
isotopes and makes detailed studies of their properties possible, just as the
ESR was used to analyze isotopes produced in the FRS. In parallel to the
Super-FRS, proton beams from SIS100 can be directed to an antiproton-
production ($\bar{p}$) target. Also the antiprotons are collected in the CR.
Once their beam quality is increased, they are directed to the “High-Energy
Storage Ring” (HESR) where they are stored for hours and collide with a
hydrogen target inside the PANDA detector.

The physics program of FAIR comprises four topics, labeled NUSTAR, PANDA, CBM,
and APPA353535These names are acronyms. NUSTAR stands for “Nuclear Structure,
Astrophysics and Reactions,” PANDA stands for “ antiProton ANnihilation at
DArmstadt,” CBM stands for “Compressed Baryonic Matter,” and APPA stands for
“Atomic, Plasma Physics and Applications.”. NUSTAR is focused on exploiting
the Super-FRS and determines the masses and lifetimes of rare isotopes that
play an important role for the creation of heavier elements in stars and
during supernova explosions. PANDA explores the spectrum of hadrons that
include a charm quark and tries to find bound states of gluons, so-called
glueballs. Since the mass of the quarks alone does not account for the mass
of, for example, protons, PANDA tries to find explanations based on quantum
chromodynamics. CBM will crash the full-energy beam coming from SIS100 into a
target inside a dedicated cave. There conditions are recreated that resemble
those immediately after the Big Bang when the primordial quark-gluon plasma
condensed into the first hadrons. APPA explores how high-energy particles
affect matter relevant to life sciences and material sciences. For example the
impinging particles can form nanopores that serve as filters to separate
smaller from larger compounds.

Not far from the FAIR site, in Frankfurt and in Mainz, two institutes pursue
development work that directly contributes to GSI and FAIR. The “Institute for
Applied Physics” at Frankfurt University develops accelerating structures,
especially for the new linear accelerator HELIAC. It will take over the super-
heavy element production from the venerable UNILAC, once the latter is
dedicated to FAIR. The “Helmholtz Institute” in Mainz integrates the
structures into HELIAC and works on a new electron cooler for the HESR to
produce high-quality beams for PANDA.

## Mainz

Long before the work towards FAIR, already since 1963, the university in Mainz
operated a 300 MeV electron linear accelerator for experiments in nuclear
physics. This machine, however, did not work quite as well as was hoped for
and, tongue in cheek, was named MUELL (for “Mainzer Universitäts ELectron
Linac”). About a decade later, an ingenious add-on, dubbed MALAISE (for “MAinz
Linear Accelerator Improving SystEm”)363636The German word “Muell”, if spelled
“Müll,” translates to the English word “garbage.” Malaise, French for
“misery,” is actually a misnomer, because performance of the linac improved
substantially., improved the beam quality significantly, which is essential
when probing nuclear matter with electrons. Experimental highlights comprise a
precise measurement of the mixing of $Z^{0}$-bosons and photons at low
energies. This is a crucial parameter for the standard model, commonly
referred to as Weinberg angle.

Figure 3: Sketch of a microtron.

But in the mid 1970s the experimenters demanded higher energies and better
beam quality, which would allow them to increase the precision of their
experiments. But most of all, they asked for a continuous stream of electrons.
The accelerator to provide these beams was dubbed MAMI373737H. Herminghaus et
al., The Design of a Cascaded 800 MeV Normal Conducting C.W. Race Track
Microtron, Nuclear Instruments and Methods 138 (1976) 1., derived from “MAinz
MIcrotron.” In microtrons a short linear accelerator is reused multiple times
by recirculating the electron beam with magnets. This provides a much more
compact way of reaching higher energies than would be possible by traversing a
longer linac only once. Nevertheless, accelerating electrons from very low
energies all the way to the full energy in only one microtron would be
technically impossible; therefore MAMI had to be constructed as a cascade of
three microtrons. The first one brought the energy up to 14 MeV and by 1983
the second microtron produced electrons with 213 MeV. Constructing the much
larger third stage took more time, but by 1990 a continuous stream of
electrons with energies up to 855 MeV was available. Most experiments used
these electrons to probe the structure of nuclei. And the continuously
available beam made it possible to probe very rare events. One just had to
accumulate data for a long time. Other experiments first crashed the electrons
into a heavy target to produce so-called bremsstrahlung composed of high-
energy photons and then using the photons to probe various nuclei.

After running the facility for about a decade the experimentalists once again
requested higher beam energies. That stimulated the construction of a fourth
accelerator stage. Since the magnets for this large microtron would be too
massive, the accelerator builders came up with an ingenious proposal383838A.
Jankowiak, The Mainz Microtron MAMI—Past and Future, Eur. Phys. J A 28, s01
(2006) 149.. They proposed to split the large magnets into smaller ones and
adjust ancillary components such as the acceleration system appropriately. By
2006 the fourth stage was up and running and produces 1500 MeV beams ever
since.

Already the four MAMI stages could produce electrons with a well-defined
orientation of their spin, but certain measurements require much higher beam
intensities to achieve results in a reasonable time. To accommodate this type
of experiment a new accelerator, called MESA393939MESA is an acronym derived
from “Mainz Energy recovering Superconducting Accelerator.” See also
https://www.mesa.uni-mainz.de/eng/., was proposed. In a second mode of
operation, the accelerated electrons would be passed through the same
structures that accelerated them, thereby recovering the energy of the beam
and reusing it to accelerate a fresh beam of electrons with better quality.
This mode of operation makes much higher beam intensities possible and thereby
enables the experimenters to probe much rarer processes than previously
possible. In particular, searches for the hypothetical dark matter (Chapter
14) are planned once MESA becomes operational in 2024.

## Heidelberg

Even before the previously mentioned cancer therapy center was built in
Heidelberg, an ion storage ring was constructed at the Max-Planck Institute
for Nuclear Physics in close collaboration with GSI. By 1988 the “Test Storage
Ring” TSR404040 P. Baumann et al., The Heidelberg Heavy Ion Test Storage Ring
TSR, Nuclear Instruments and Methods A268 (1988) 531. with a circumference of
55 m stored beams of ionized atoms and molecules. An electron cooler, similar
to the one installed in the ESR at GSI, was used to reduce the beam sizes and
allowed the experimenters to analyze the behavior of beams with very high
charge densities. Moreover, the cooler was used as an electron target to
investigate atomic and molecular recombination processes. In these processes
an atom picks up an additional electron from the cooler. They are important to
understand the creation of complex molecules in outer space. Moreover, the
accelerated and cooled ion beams were used for high-resolution experiments in
nuclear physics. The ring was operated until 2012 when construction of a new
storage ring in Heidelberg started.

Rather than using magnetic fields to guide the beams, the new ring with a
circumference of 35 m uses electric fields, which is advantageous for slow and
very heavy particles or molecules. Moreover, in order to permit very delicate
measurements, the ring is cooled down to extremely low temperatures and is
therefore dubbed CSR414141R. von Hahn et al., The cryogenic storage ring CSR,
Rev. Sci. Instrum. 87, (2016) 063115., an acronym derived from “Cryogenic
Storage Ring.” Like in the earlier ring, an electron cooler serves as an
electron target for high-resolution recombination reactions.

## Jülich

Already 1968 the JULIC424242L. Aldea et al., Status of JULIC, Proceedings of
Cyclotrons 1981 in Caen, p. 103. cyclotron in Jülich accelerated protons and
other light ions with energies up to 45 MeV that were mostly used for nuclear
physics experiments. A number of transfer lines brought these beams to several
different target stations, among them a large detector called BIG KARL. Other
stations were used to produce radioactive isotopes for medical applications.

Already in the early 1980s, ideas appeared to add a synchrotron to the
facility that would increase the energy of the protons substantially. In order
to produce high-quality beams, an electron cooler was planned, which gave the
synchrotron the name COSY434343U. Bechstedt et al., The cooler synchrotron
COSY in Jülich, Nuclear Instruments and Methods B113 (1996) 26., for “COoler
SYnchrotron.” It has a circumference of 184 m and accelerates protons, which
could be prepared with their spins aligned, to energies of up to 2300 MeV.
Besides the electron cooler, elaborate stochastic cooling systems (Figure 9.4)
improve the quality of beams that are delivered to the experiments. Three of
them are part of the ring where the beam continuously interacts with a target
such as a gas jet or a very thin carbon filament. Later a stream of frozen
hydrogen spheres, so-called pellets, served as a target to explore nuclear
interactions. Apart from using these internal targets, the beam was extracted
from the ring and directed to external detectors, among them the venerable BIG
KARL.

The nuclear physics program continued until 2014, at which time the focus
switched to precision experiments to understand various aspects of CP-
violation (Chapter 10). In the “Time Reversal Invariance at COSY” (TRIC)
experiment, a specially prepared proton beam with spins aligned collided with
a likewise prepared deuteron target. A second experimental program, called
EDM, aims at measuring the “Electric Dipole Moment” of protons and deuterons
by observing the precession of the spin of beam particles in the presence of
strong electric fields. Any non-zero value would give strong indications about
“new physics” beyond the standard model. At the same time, COSY was used to
develop the next-generation accelerator technology needed for the FAIR
facility in Darmstadt, in particular the electron coolers and stochastic
cooling systems.

## And there is more

Besides the larger accelerators covered in this report, there are many smaller
ones. Many hospitals operate small cyclotrons to produce radioactive isotopes
that are used for diagnostic purposes, such as positron-emission tomography
(Section 13.4). They also operate small, often less than one meter long
electron linear accelerators to irradiate tumors.

Several universities operate electrostatic accelerators of the type devised by
van der Graaff (Figure 4.1). They are used for dating artefacts using the
carbon-14 method (Section 13.5) and to analyze specimen by impinging the beams
onto the sample. Subsequently observing the emitted X-rays, specific to the
material composition of the specimen, allows the experimenters to identify
even minute quantities of constituents.

Accelerating very heavy ions to a few hundred of kV implants the ions inside
the irradiated substrate, which is used in industry and academia. These
machines are up-to-date versions of Cockroft and Walton’s accelerator (Figure
4.1) used to split Lithium atoms in 1930.

## Acknowledgements

I benefitted greatly from helpful discussions with Christian Jung, Roger
Ruber, Detlev Schirmer, Wolfgang Hillert, Daniel Elsner, Andreas Lehrach, Kurt
Aulenbacher, and Jörg Rossbach.


# Gray Codes and Overlap Cycles for Restricted Weight Words

Victoria Horan
Air Force Research Laboratory
Information Directorate

Glenn Hurlbert
School of Mathematical and Statistical Sciences
Arizona State University victoria.horan.1<EMAIL_ADDRESS>
###### Abstract

A Gray code is a listing structure for a set of combinatorial objects such
that some consistent (usually minimal) change property is maintained
throughout adjacent elements in the list. While Gray codes for $m$-ary strings
have been considered in the past, we provide a new, simple Gray code for
fixed-weight $m$-ary strings. In addition, we consider a relatively new type
of Gray code known as overlap cycles and prove basic existence results
concerning overlap cycles for fixed-weight and weight-range $m$-ary words.

††Approved for public release; distribution unlimited: 88ABW-2014-0956, 07 Mar
2014

##  1 Introduction

Gray codes were originally developed by Frank Gray [4] as a method of listing
binary $n$-tuples so that successive words differ in only one position. The
term Gray code has now come to mean a listing of a set $\mathcal{C}$ of
combinatorial objects in which successive words differ in some predefined
manner, usually a consistent minimal change. Since Gray’s original code, these
listings have been studied extensively and have seen use in many different
applications such as rotary encoders [1] and error detection and correction
[6].

Define the set of all strings of length $n$ over the alphabet
$\\{0,1,\ldots,m-1\\}$ to be $\mathcal{B}(m,n)$, the set of all $m$-ary
strings of length $n$. Given a string $x=x_{1}x_{2}\ldots x_{n}$, the weight
of $x$ is defined to be $wt(x)=\sum_{i=1}^{n}x_{i}$. Then the set of all
weight $k$ $m$-ary strings of length $n$ is denoted $\mathcal{B}_{k}(m,n)$. We
are interested in two kinds of Gray codes. The first kind requires the set of
fixed-weight strings to be ordered such that they change in exactly two
positions (Section 2), and the second kind are $s$-overlap cycles, which
require that adjacent strings overlap in a specific way (Section 3).

##  2 Gray Codes

Gray codes for $m$-ary words have been studied extensively in the past. The
first main theorem considers all $m$-ary words of length $n$.

######  Theorem 2.1.

_[2]_ For every $n,m\in\mathbb{Z}^{+}$, there exists a Gray code listing for
$\mathcal{B}(m,n)$ so that each word differs from its successor in exactly one
position.

For fixed-weight $m$-ary words of length $n$, the following theorem is known
and published in [8], however we provide a new and simpler algorithm.

######  Theorem 2.2.

For every $n,m,k\in\mathbb{Z}^{+}$, there exists a Gray code listing for
$\mathcal{B}_{k}(m,n)$ in which successive words differ in at most two
positions.

Note that a change in two positions is best possible, as a change in just one
would alter the weight of the word. In this section we will first present our
algorithm, then provide an example, and finally will prove that our algorithm
is correct.

###  2.1 The New Algorithm

We would like to produce a Gray code for the set of fixed-weight $m$-ary
strings in which successive elements differ in at most two positions. First,
we define a few simple functions that will be used in the algorithm. Given a
list $L$, Rev$(L)$ produces the list in reversed order. The second function
needed is the exponent function, defined as follows.

$\hbox{{Expo}}(L,e)=\left\\{\begin{array}[]{ll}L,&\hbox{if $e\equiv 0\bmod
2$;}\\\ \hbox{{Rev}}(L),&\hbox{otherwise.}\end{array}\right.$

Finally, the function Pref$(a,L)$ adds the prefix $a$ to every string in list
$L$. This operation will also be denoted $a\oplus L$. Now we can provide the
following algorithm, borrowing the reflection idea from Gray’s original
algorithm for binary words [4]. Our algorithm is presented in Figure 1.

1:procedure FWM($m,n,k$)$\triangleright$ $m$-ary words of length $n$ and
weight $k$

2: $L\leftarrow[\hbox{ }]$

3: if $(m-1)n\geq k$ and $k\geq 0$ then

4: if $(m-1)n=0$ then

5: $L\leftarrow[[\hbox{ }]]$

6: end if

7: for $i=0:\min(m-1,k)$ do

8: $M\leftarrow$ Pref($i,\hbox{{Expo}}(FWM(m,n-1,k-i),i))$

9: $L\leftarrow L,M$ $\triangleright$ Append $M$ to $L$

10: end for

11: end if

12: return $L$

13:end procedure

Figure 1: Fixed-Weight $m$-ary Gray Code Algorithm

###  2.2 Example

We will work through an example of the algorithm when we run FWM$(3,4,5)$.

  * •

We begin with $L$, an empty list.

  * •

Starting with $i=0$, we need to determine

$M=0\oplus\hbox{FWM}(3,3,5)=\hbox{{Pref}}(0,\hbox{{Expo}}(\hbox{FWM}(3,3,5),0)).$

    * –

We begin by determining the sublist, FWM$(3,3,5)$.

$\hbox{FWM}(3,3,5)=[0\oplus\hbox{FWM}(3,2,5),1\oplus\hbox{{Rev}}(\hbox{FWM}(3,2,4)),2\oplus\hbox{FWM}(3,2,3)].$

    * –

For these sublists, we have the following.

$\begin{array}[]{c|cc}\hline\cr 1&2&2\\\ \hline\cr 2&1&2\\\ 2&2&1\end{array}$

  * •

Now we must precede this sublist by $0$ to determine $M$.

$\begin{array}[]{c||c|cc}\hline\cr 0&1&2&2\\\ \hline\cr 0&2&1&2\\\ 0&2&2&1\\\
\hline\cr\hline\cr\end{array}$

  * •

When $i=1$, we have the following sublist.

$\begin{array}[]{c||c|cc}\hline\cr\hline\cr 1&2&2&0\\\ 1&2&1&1\\\ 1&2&0&2\\\
\hline\cr 1&1&1&2\\\ 1&1&2&1\\\ \hline\cr 1&0&2&2\\\
\hline\cr\hline\cr\end{array}$

  * •

When $i=2$, our list finishes with the following sublist.

$\begin{array}[]{c||c|cc}\hline\cr\hline\cr 2&0&1&2\\\ 2&0&2&1\\\ \hline\cr
2&1&2&0\\\ 2&1&1&1\\\ 2&1&0&2\\\ \hline\cr 2&2&0&1\\\ 2&2&1&0\end{array}$

These sublists combine to produce our final list, shown in Figure 2.

$\begin{array}[]{c||c|cc}0&1&2&2\\\ \hline\cr 0&2&1&2\\\ 0&2&2&1\\\
\hline\cr\hline\cr 1&2&2&0\\\ 1&2&1&1\\\ 1&2&0&2\\\ \hline\cr 1&1&1&2\\\
1&1&2&1\\\ \hline\cr 1&0&2&2\\\ \hline\cr\hline\cr 2&0&1&2\\\ 2&0&2&1\\\
\hline\cr 2&1&2&0\\\ 2&1&1&1\\\ 2&1&0&2\\\ \hline\cr 2&2&0&1\\\
2&2&1&0\end{array}$ Figure 2: List Produced by FWM$(3,4,5)$

In this example, double lines indicate changes in our outer loop, while single
lines indicate changes in the secondary loop.

###  2.3 Proof of Correctness

First, we describe more clearly what is happening in Algorithm FWM. The
algorithm is clearly recursive, and the strings are organized so that every
string beginning with $i$ comes before every string beginning with $i+1$.
However, within these subsets of our list the ordering is not so simple. When
we consider a sublist of strings that all begin with the same prefix
$w_{1}w_{2}\ldots w_{\ell}$, we can determine whether the list is reversed or
not by considering $\sum_{i=1}^{\ell}w_{i}$. If the sum is odd then the list
is reversed, and if the sum is even then it is not. This immediately tells us
the ordering of the $(\ell+1)$st elements in this sublist.

######  Lemma 2.3.

The first element of the list FWM$(m,n,k)$ is $0\cdots 0r(m-1)\cdots(m-1)$
where $k=q(m-1)+r$ for some $q,r\in\mathbb{Z}$ where $0\leq r<m-1$. Define
$u_{1}=\min\\{m-1,k\\}$ and $k-u_{1}=q^{\prime}(m-1)+r^{\prime}$ for some
$q^{\prime},r^{\prime}\in\mathbb{Z}$ with $0\leq r^{\prime}<m-1$. Then the
last element of the list is

$\mathbf{u}=\left\\{\begin{array}[]{ll}u_{1}(m-1)\cdots(m-1)r^{\prime}0\cdots
0,&\hbox{if $u_{1}$ is even;}\\\ u_{1}0\cdots
0r^{\prime}(m-1)\cdots(m-1),&\hbox{if $u_{1}$ is odd.}\end{array}\right.$

###### Proof.

It is clear from the algorithm that any list always starts with the minimum
string in lexicographic order. Thus the list must start with

$0\cdots 0r(m-1)\cdots(m-1).$

To find the last element of the list, we proceed by induction on $n$. For the
base case, we consider when $n=1$. When $n=1$, clearly there is only one
string: $k$. Note that this agrees with our definition of $\mathbf{u}$.

Before considering the two cases of $u_{1}$ either odd or even, we note that
if $u_{1}=k$ then the string must be $u_{1}0\cdots 0$ and the lemma is
satisfied. So we may now assume the $u_{1}=m-1$.

When $u_{1}$ is even, we are searching for the last element of the list

$u_{1}\oplus\hbox{FWM}(m,n-1,k-u_{1}).$

Note that $u_{1}$ even implies that $m-1$ is even. In this case, we know that
the second letter is $u_{2}=\min\\{m-1,k-(m-1)\\}$. As before, if
$u_{2}=k-(m-1)$, then the only string possible is $(m-1)(k-m+1)0\cdots 0$,
which meets the requirements. So we assume that $u_{2}=m-1$, which is even. So
now we know that the last element of the list must be

$u_{1}\oplus(m-1)\cdots(m-1)r^{\prime\prime}0\cdots
0=(m-1)\cdots(m-1)r^{\prime}0\cdots 0,$

where $q^{\prime\prime},r^{\prime\prime}\in\mathbb{Z}$ with $0\leq
r^{\prime\prime}<m-1$ so that
$k-2(m-1)=q^{\prime\prime}(m-1)+r^{\prime\prime}$.

When $u_{1}$ is odd, we are searching for the last element of the list

$u_{1}\oplus\hbox{{Rev}}(\hbox{FWM}(m,n-1,k-u_{1})),$

which is the same as searching for the first element of the list

$u_{1}\oplus\hbox{FWM}(m,n-1,k-u_{1}).$

By the first part of the claim this is given by $u_{1}0\cdots
0r(m-1)\cdots(m-1)$ where $k-u_{1}=q(m-1)+r$ for $0\leq r<m-1$. ∎

Using this lemma, we are able to deduce the following pair of corollaries.

######  Corollary 2.4.

For all $m,n,k$, the first element of FWM$(m,n,k)$ and the first element of
FWM$(m,n,k-1)$ differ in exactly one position.

###### Proof.

By Lemma 2.3, we know that the first element of FWM$(m,n,k-1)$ is

$0\cdots 0r(m-1)\cdots(m-1)$

with $0\leq r<m-1$. Then the first element of FWM$(m,n,k)$ must be

$0\cdots 0(r+1)(m-1)\cdots(m-1)$

where $1\leq r+1<m$. These clearly only differ in one position. ∎

######  Corollary 2.5.

For all $m,n,k$, the last element of FWM$(m,n,k)$ and the last element of
FWM$(m,n,k-1)$ differ in exactly one position.

###### Proof.

We proceed by induction on $n$. If $n=1$, then the two strings must differ in
exactly one position. We now assume that $n>1$. Define
$u_{1}=\min\\{m-1,k\\}$. By Lemma 2.3, the last element of FWM$(m,n,k)$ is

$\mathbf{u}=\left\\{\begin{array}[]{ll}u_{1}(m-1)\cdots(m-1)r^{\prime}0\cdots
0,&\hbox{if $u_{1}$ is even;}\\\ u_{1}0\cdots
0r^{\prime}(m-1)\cdots(m-1),&\hbox{if $u_{1}$ is odd.}\end{array}\right.$

As before, if $u_{1}=k$ then this string is $\mathbf{u}=k0\cdots 0$ and the
last element of FWM$(m,n,k-1)$ is $(k-1)0\cdots 0$, which clearly only differs
in one position. If $u_{1}=(m-1)\neq k$, then we consider the last element of
FWM$(m,n,k-1)$, which we will call $\mathbf{v}$. In this case we must have
$u_{1}=v_{1}$, and so we consider the two substrings $u_{2}u_{3}\ldots u_{n}$
and $v_{2}v_{3}\ldots v_{n}$. If $u_{1}$ is even, these are the last elements
of the lists FWM$(m,n-1,k-u_{1})$ and FWM$(m,n-1,k-u_{1}-1)$, respectively. By
the induction hypothesis these must differ in exactly one position, and we are
done. If $u_{1}$ is odd, then our two substrings are the first elements of the
lists FWM$(m,n-1,k-u_{1})$ and FWM$(m,n-1,k-u_{1}-1)$, which by Corollary 2.4
differ in exactly one position. ∎

Using the lemma and corollaries, we are able to show that Algorithm FWM is
correct in the following theorem.

######  Theorem 2.6.

There is a Gray code for $\mathcal{B}_{k}(m,n)$, the set of $m$-ary words of
length $n$ with weight $k$, in which adjacent words differ in exactly two
positions.

###### Proof.

We will show by induction that Algorithm FWM produces the desired Gray code.
For the base cases, when $n=1$ the lists are easily constructed. If $m-1\geq
k$, then we get the list $[k]$, otherwise we have an empty list.

For $n>1$, suppose we want to construct the desired Gray code for
$\mathcal{B}_{k}(m,n)$. We will show that FWM$(m,n,k)$ is correct. By the
induction hypothesis, for each $i$ from $0$ to $\min\\{m-1,k\\}$, our sublist
$M$ has adjacent elements differing in exactly two positions. All that remains
is to check that this minimal change property is maintained as $i$ increases.

First, when $i$ increases from an odd to an even number, we have the following
transition.

$\displaystyle i$ $\displaystyle\oplus$
$\displaystyle\hbox{{Rev}}(\hbox{FWM}(m,n-1,k-i))$ $\displaystyle i+1$
$\displaystyle\oplus$ $\displaystyle\hbox{FWM}(m,n-1,k-i-1)$

By Corollary 2.4, the adjacent elements of these two sublists differ in
exactly one position, which together with the leftmost position gives exactly
two positions.

When $i$ increases from an even number to an odd number, we have the following
transition.

$\displaystyle i$ $\displaystyle\oplus$ $\displaystyle\hbox{FWM}(m,n-1,k-i)$
$\displaystyle i+1$ $\displaystyle\oplus$
$\displaystyle\hbox{{Rev}}(\hbox{FWM}(m,n-1,k-i-1))$

Clearly the adjacent elements of these two sublists differ in the first
coordinate, so we must check that they only differ in one other position at
their meeting point - that is, that the last element of FWM$(m,n-1,k-i-1)$
differs from the last element of FWM$(m,n-1,k-i)$ in at most one position. To
prove this, we use Corollary 2.5. ∎

##  3 Overlap Cycles

For a set $S$ of strings of length $n$ and an integer $s$ with $1\leq s\leq
n-1$, an $s$-overlap cycle, or $s$-ocycle, is an ordering of $S$ such that
string $x_{1}x_{2}\ldots x_{n}$ is followed by string $y_{1}y_{2}\ldots y_{n}$
only if $x_{n-s+i}=y_{i}$ for $i\in[s]$. Note that this definition requires
that each element of $S$ appear exactly once, and the ordering is cyclic, i.e.
the last element of $S$ and the first element of $S$ must overlap in the
specified manner. In other words, an $s$-overlap cycle is a cyclic Gray code
that allows string $x$ to follow string $y$ if and only if the last $s$
letters of $y$ (the $s$-suffix) are the same as the first $s$-letters of $x$
(the $s$-prefix).

Given a set $S$ of strings, the standard approach for proving the existence of
such an ordering is to use a transition digraph. The vertices of the
transition digraph represent strings of length $s$ (the overlaps), while the
edges represent strings of length $n$ (the objects). For a given string
$x=x_{1}x_{2}\ldots x_{n}$, the $s$-prefix of $x$ is $x^{s-}=x_{1}x_{2}\ldots
x_{s}$ and the $s$-suffix is $x^{s+}=x_{n-s+1}x_{n-s+2}\ldots x_{n}$. Let $D$
be the digraph defined by setting

$V=\\{w\mid w=x^{s-}\hbox{ or }w=x^{s+}\hbox{ for some }x\in S\\}$

and

$E=\\{(w,v)\mid w=x^{s-}\hbox{ and }v=x^{s+}\hbox{ for some }x\in S\\}.$

Then an Euler tour (closed walk that contains every edge exactly once) in $D$
corresponds to an $s$-ocycle for $S$. To prove the existence of an Euler tour,
we use the following well-known result from graph theory.

######  Theorem 3.1.

_([9], p. 60)_ A directed graph $G$ is eulerian if and only if it is both
balanced and weakly connected.

###  3.1 Existence of Overlap Cycles

In the paper introducing overlap cycles, Godbole, et al, prove the following
general theorem.

######  Theorem 3.2.

_[3]_ For all $n,m,s\in\mathbb{Z}^{+}$, $1\leq s\leq n-1$, there exists an
$s$-ocycle for $\mathcal{B}(m,n)$.

If instead of considering all words over an alphabet of size $M$ we consider
words over a fixed multiset, we have the following theorem.

######  Theorem 3.3.

_[5]_ Let $n,s\in\mathbb{Z}^{+}$ with $1\leq s\leq n-1$ and let $M$ be a
multiset of size $n$. There exists an $s$-ocycle on permutations of $M$ if and
only if $n-s>\hbox{gcd}(n,s)$.

In order to find some middle ground between Theorems 3.2 and 3.3, we consider
fixed-weight $m$-ary words. That is, words over the alphabet
$\\{0,1,\ldots,m-1\\}$ such that the sum of the letters is some predetermined
constant. For fixed-weight $m$-ary words, we note that the following sets
contain only one string or a set of strings with the same fixed multiset,
hence by Theorem 3.3 there always exists an $s$-ocycle for:

  * •

$\mathcal{B}_{0}(m,n)=\\{0^{n}\\}$,

  * •

$\mathcal{B}_{1}(m,n)=\\{0^{t}10^{n-t-1}\mid t\in[n]\\}$,

  * •

$\mathcal{B}_{2}(2,2)=\\{11\\}$,

  * •

$\mathcal{B}_{(m-1)n}(m,n)=\\{(m-1)^{n}\\}$, and

  * •

$\mathcal{B}_{(m-1)n-1}(m,n)=\\{(m-1)^{t}(m-2)(m-1)^{n-t-1}\mid t\in[n]\\}$.

######  Theorem 3.4.

Fix $n,m,k,s\in\mathbb{Z}^{+}$ such that:

  * •

$1\leq s\leq n-1$, and

  * •

$1<k<(m-1)n-1$.

Then there is an $s$-ocycle for $\mathcal{B}_{k}(m,n)$ if and only if
$n-s>\hbox{gcd}(n,s)$.

###### Proof.

Suppose that $n-s>d$ where $d=\hbox{gcd}(n,s)$. Construct the transition graph
$G=G_{s}(m,n)$ with vertices representing $s$-prefixes and $s$-suffixes of
elements in $\mathcal{B}_{k}(m,n)$ and edges representing elements of
$\mathcal{B}_{k}(m,n)$, traveling from prefix to suffix. First, at each vertex
$X$ in $G$, for each $(n-s)$-suffix $Y$ for $X$ we have an out-edge
representing the string $XY\in\mathcal{B}_{k}(m,n)$. Note that also
$YX\in\mathcal{B}_{k}(m,n)$, and is represented by an in-edge to $X$. This
gives a bijection between in- and out-edges at $X$, and hence $G$ is balanced.

There exist some $r,q\in\mathbb{Z}$ such that $0\leq r<m-1$ with $k=q(m-1)+r$.
Define the minimum element $V$ of $\mathcal{B}_{k}(m,n)$ to be the minimum
lexicographically, i.e. $V=0\cdots 0r(m-1)\cdots(m-1)$. Then the minimum
vertex in $G$, call it $V^{s-}$, is the $s$-prefix of $V$. Let
$X^{s-}=x_{1}x_{2}\ldots x_{s}$ be an arbitrary vertex in $G$. Let
$X\in\mathcal{B}_{k}(m,n)$ be an $m$-ary string with $s$-prefix $X^{s-}$. We
will prove that $G$ is connected by illustrating a path from $X^{s-}$ to
$V^{s-}$.

Using Theorem 3.3, all permutations of the string $X$ are connected in $G$, so
we may assume that $X=x_{1}x_{2}\ldots x_{n}$ is ordered so that $x_{1}\leq
x_{2}\leq\ldots\leq x_{n}$. Compare $X$ with $V$, and let $i$ be the left-most
index in which they disagree. In other words, we have $x_{1}=v_{1}$,
$x_{2}=v_{2}$, and so on until $x_{i-1}=v_{i-1}$, but $x_{i}\neq v_{i}$. Since
$V$ is the minimum string lexicographically, this implies that $x_{i}>v_{i}$.
Since $X$ and $V$ both have weight $k$, there must be some index $j>i$ such
that $x_{j}<v_{j}$. Using Theorem 3.3 again, we find a path to the $s$-prefix
of the string

$X^{\prime}=x_{1}x_{2}\ldots x_{i-1}x_{i+1}x_{i+2}\ldots
x_{j-1}x_{j+1}x_{j+2}\ldots x_{n}x_{i}x_{j}.$

Note that this $s$-prefix does not contain the last two letters, namely
$x_{i}$ and $x_{j}$, so the $s$-prefix also has an out-edge representing the
string

$X^{\prime\prime}=x_{1}x_{2}\ldots x_{i-1}x_{i+1}x_{i+2}\ldots
x_{j-1}x_{j+1}x_{j+2}\ldots x_{n}(x_{i}-1)(x_{j}+1).$

Applying Theorem 3.3 again, we can find a path to the $s$-prefix of the string

$x_{1}x_{2}\ldots x_{i-1}(x_{i}-1)x_{i+1}x_{i+2}\ldots
x_{j-1}(x_{j}+1)x_{j+1}x_{j+2}\ldots x_{n}.$

This $s$-prefix is now closer to the minimum vertex, and repeating the process
we will eventually arrive at $V^{s-}$. Since $X^{s-}$ was an arbitrary
starting vertex in $G$, $G$ is connected and hence eulerian by Theorem 3.1.

For the converse, suppose that $n-s=\hbox{gcd}(n,s)$. Then, as discussed in
[5], rotations of a string $X$ partition it into blocks of length
$d=\hbox{gcd}(n,s)$. Since $X$ has fixed weight and we may only reorder
elements within blocks but not swap elements between blocks, each block has a
fixed weight. In other words, if $X=Y_{1}Y_{2}\ldots Y_{\ell}$ is $X$
partitioned into $d$-blocks with block $Y_{i}$ having weight $w_{i}$, then no
manipulation of $X$ can alter the values $w_{i}$ corresponding to each
$Y_{i}$. Hence if we can always produce two strings
$X,Z\in\mathcal{B}_{k}(m,n)$ so that the block sequences for $X$ and $Z$ are
not simply rotations of each other, then we are done.

First note that $k\geq 2$. There are integers $q,r$ such that $0\leq r<m-1$
and $k=(m-1)q+r$. Define two strings:

$A=0^{n-q-1}r(m-1)^{q}\hbox{ and }B=10^{n-q-2}r(m-1)^{q-1}(m-2),$

with block sequences $A_{1}A_{2}\ldots A_{\ell}$ and $B_{1}B_{2}\ldots
B_{\ell}$ respectively. We will show through several cases that these two
block sequences are distinct and are not identical or rotations of each other.

  1. 1.

If $n-q-1\geq d$ and $q\geq d$:

In this case we know that:

     * •

$w(A_{1})=0$,

     * •

$w(A_{\ell})=(m-1)d$,

     * •

$w(B_{1})=1$, and

     * •

$w(B_{\ell})=(m-1)d-1$.

In this case our two block weight sequences are as follows, where $x=(m-1)d$
and $y=r+(m-1)j$ for some $j\leq d$.

$\begin{array}[]{lc|ccc|c|ccc|c}A=&0&0&\cdots&0&y&x&\cdots&x&x\\\ \hline\cr
B=&1&0&\cdots&0&y&x&\cdots&x&x-1\end{array}$

Note that if the weight sequence for $A$ contains a string of $\alpha$
consecutive 0’s, then the sequence for $B$ contains a string of $\alpha-1$
consecutive 0’s. Thus these two strings can only be rotations of each other if
$\alpha=1$ (or only the first block has weight $0$) and $x-1=0$. Thus our
block weight sequences are as follows.

$\begin{array}[]{lc|c|ccc|c}A=&0&1&1&\cdots&1&1\\\ \hline\cr
B=&1&1&1&\cdots&1&0\end{array}$

Hence we have $(m-1)d=1$, which implies that $m=2$ and $d=1$, so given the
block sequences we must have $k=n-1$ in order for the sequences to be
rotations of each other. However the initial conditions require that $k<n-1$,
so these two sequences will never be rotations.

  2. 2.

If $n-q-1\geq d$ and $q<d$:

In this case we know that:

     * •

$w(A_{i})=0$ for $1\leq i<\ell$,

     * •

$w(A_{\ell})=k$,

     * •

$w(B_{1})=1$,

     * •

$w(B_{i})=0$ for $2\leq i<\ell$, and

     * •

$w(B_{\ell})=k-1$.

In this case our two block weight sequences are as follows.

$\begin{array}[]{lc|ccc|c}A=&0&0&\cdots&0&k\\\ \hline\cr
B=&1&0&\cdots&0&k-1\end{array}$

These two block weight sequences are only rotations of each other if $k=1$,
which is not allowed by the hypotheses.

  3. 3.

If $n-q-1<d$ and $q\geq d$:

In this case we know that:

     * •

$w(A_{1})=r+j(m-1)$ for some $0\leq j<d$,

     * •

$w(A_{i})=d(m-1)$ for $2\leq i\leq\ell$,

     * •

$w(B_{1})=r+j(m-1)+1$ for some $0\leq j<d$,

     * •

$w(B_{i})=d(m-1)$ for $2\leq i<\ell$, and

     * •

$w(B_{\ell})=d(m-1)-1$.

In this case our two block weight sequences are as follows, where $x=(m-1)d$
and $y=r+(m-1)j$ for some $j\leq d$.

$\begin{array}[]{lc|ccc|c}A=&y&x&\cdots&x&x\\\ \hline\cr
B=&y+1&x&\cdots&x&x-1\end{array}$

These two block weight sequences are only rotations of each other if
$y=(m-1)d-1$. However in this case we must have $k=(m-1)n-1$, which is not
allowed by the initial conditions.

  4. 4.

If $n-q-1<d$ and $q<d$:

In this case we have that $A=0^{n-q-1}r(m-1)^{q}$, but then we must have
$(n-q-1)+1+q\leq 2d-2$, or $n\leq 2d-2$, which is not possible since we must
have $d\leq\frac{n}{2}$.

∎

Next we consider $m$-ary words with weights belonging to some fixed range.
That is, we consider $s$-ocycles on the set of weight-range $m$-ary words,
defined as ($p<q$):

$\mathcal{B}_{p}^{q}(m,n)=\\{x=x_{1}x_{2}\ldots x_{n}\in\mathcal{B}(m,n)\mid
p\leq\hbox{wt}(x)\leq q\\}.$

This small amount of room in weights allows us to prove a much stronger
result.

######  Theorem 3.5.

For $m,n,s,p,q\in\mathbb{Z}$, with $1\leq s<n$ and $0\leq p<q\leq(m-1)n$,
there exists an $s$-ocycle for $\mathcal{B}_{p}^{q}(m,n)$.

###### Proof.

Construct the transition digraph $\overrightarrow{T}$. First, note that any
$s$-prefix is also an $s$-suffix, so $\overrightarrow{T}$ is balanced.

To show connectivity, we denote a minimum vertex and show a path always exists
from an arbitrary vertex to the minimum vertex. We will define the minimum
vertex of the digraph as follows. Write $p=a(m-1)+b$ for some $0\leq b<m-1$.
Then the minimum vertex $v$ is defined to be the $s$-prefix of the string
$0\cdots 0b(m-1)\cdots(m-1)$. In other words, $v$ is the $s$-prefix of the
minimum lexicographic string in the set.

Now we will prove that the digraph is weakly connected. Let
$x=x_{1}x_{2}\ldots x_{n}$ and consider the vertex given by the $s$-prefix,
$x_{1}x_{2}\ldots x_{s}$. As usual, rotations of $x$ in the digraph correspond
to a partition of $x$ into blocks of size $d=\hbox{gcd}(n,s)$. Note that
through rotations, we can always “hide” at least one block of $x$ in the
$(n-s)$-suffix of the string. Thus we can modify at least one block at a time;
however, as seen in the previous proof we cannot always assume it is possible
to modify more than one block at a time without additional requirements.
Through this process, we may assume that a valid operation is one that
modifies exactly one block in each step. Thus our path construction consists
of the following two parts.

  1. 1.

If $\hbox{wt}(x)>p$:

Consider the block partition of $x$, given by $x=X_{1}X_{2}\ldots X_{\delta}$
where $\delta=n/d$. Suppose that block $X_{i}$ has maximum weight. Then since
$\hbox{wt}(x)>p$, we must have $\hbox{wt}(X_{i})>0$, so we rotate until block
$X_{i}$ is in the $(n-s)$-prefix of $x$ (i.e. $X_{i}$ does not appear in the
$s$-prefix). At this point we can modify the block $X_{i}$ and replace it with
some block $X_{i}^{\prime}$ with smaller weight. If we are now considering an
$n$-string with weight $p$ continue to step 2. Otherwise, repeat step 1.

  2. 2.

If $\hbox{wt}(x)=p$:

Compare the block weights of $x$ and $v$. If the block weight sequences are
equal (i.e. $\hbox{wt}(X_{i})=\hbox{wt}(V_{i})$ for all $i\in[\delta]$), then
repeatedly sort one block of $x$ at a time to arrive at $v$. Otherwise, the
block weight sequences differ in at least two positions. That is, there exists
$i,j$ such that $\hbox{wt}(X_{i})<\hbox{wt}(V_{i})$ and
$\hbox{wt}(X_{j})>\hbox{wt}(V_{j})$. Then we first increase the weight of
$X_{i}$ by one (which must be possible since $V_{i}$ is on the same $m$-ary
alphabet), and afterwards we decrease the weight $X_{j}$ by one (which must be
possible since $\hbox{wt}(X_{j})>\hbox{wt}(V_{j})$). Now either the block
weight sequences for $x$ and $v$ are identical and we are done, or we repeat
step 2 until that happens. Note that at each step we are decreasing the
measure $\sum_{i=1}^{\delta}|\hbox{wt}(X_{i})-\hbox{wt}(V_{i})|$ by two, and
so the process will terminate when that measure reaches zero.

∎

##  4 Future Work

We leave the following question as a possible future direction for this area
of research. Is there a Gray code for weight-range $m$-ary strings such that
the strings differ in exactly one position? Note that this would solve the
famous middle-levels problem [7].

## References

  * [1] E.A. Ragland and H.B. Schultheis, Jr., _Direction-Sensitive Binary Code Position Control System_ , U.S. Patent 2823345 A, Filed October 16, 1953, Issued February 11, 1958.
  * [2] M.C. Er, _On Generating the $n$-ary Reflected Gray Codes_, IEEE Trans. Comput. C-33(8) (1984), 739-741.
  * [3] A. Godbole, D. Knisley, and R. Norwood, _On $\alpha$-Overlap Graphs_, Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 204 (2010), 161-171.
  * [4] F. Gray, _Pulse Code Communications_ , U.S. Patent 2632058, Filed November 13, 1947, Issued March 1953.
  * [5] V. Horan, _Overlap Cycles for Permutations: Necessary and Sufficient Conditions_ , submitted.
  * [6] J.E. Ludman, _Gray Code Generation for MPSK Signals_ , IEEE Trans. Commun., COM-29(10) (1981), 1519-1522.
  * [7] C.D. Savage, _Monotone Gray Codes and the Middle Levels Problem_ , J. Combin. Theory Ser. A, 70 (1995), 230-248.
  * [8] T.R. Walsh, _Loop-Free Sequencing of Bounded Integer Compositions_ , J. Combin. Math. Combin. Comput. 33 (2000), 323-345.
  * [9] D. B. West, _Introduction to Graph Theory_. Prentice Hall, Second Edition, 2001\.