text:
# Classical Radiation Processes in the Weizsäcker-Williams Approximation

## I The Weizsäcker-Williams Approximation

Following an earlier discussion by Fermi , Weizsäcker  and Williams  noted that the electromagnetic fields of an electron in uniform relativistic motion are predominantly transverse, with $`𝐄𝐁`$ (in Gaussian units). This is very much like the fields of a plane wave, so one is led to regard a fast electron as carrying with it a cloud of virtual photons that it can shed (radiate) if perturbed.

The key feature of the frequency spectrum of the fields can be estimated as follows. To an observer at rest at distance $`b`$ from the electron’s trajectory, the peak electric field is $`E=\gamma e/b^2`$, and the field remains above half this strength for time $`b/\gamma c`$, so the frequency spectrum of this pulse extends up to $`\omega _{\mathrm{max}}\gamma c/b`$. The total energy of the pulse (relevant to this observer) is $`UE^2\mathrm{Vol}\gamma ^2e^2/b^4b^2b/\gamma \gamma e^2/b`$.

If the electron radiates all of this energy, the energy spectrum would be

$$\frac{dU(\omega )}{d\omega }\frac{U}{\omega _{\mathrm{max}}}\frac{e^2}{c}.$$
(1)
This result does not depend on the choice of impact parameter $`b`$, and is indeed of general validity (to within a factor of $`\mathrm{ln}\gamma `$). The number of photons $`n_\omega `$ of frequency $`\omega `$ is thus

$$dn_\omega =\frac{dU(\omega )}{\mathrm{}\omega }\frac{e^2}{\mathrm{}c}\frac{d\omega }{\omega }=\alpha \frac{d\omega }{\omega },$$
(2)
where $`\alpha =e^2/\mathrm{}c1/137`$ is the fine structure constant.

The quick approximation (1)-(2) is not accurate at high frequencies. In general, additional physical arguments are needed to identify the maximum frequency of its validity, called the characteristic or critical frequency $`\omega _C`$, or equivalently, the minimum relevant impact parameter $`b_{\mathrm{min}}`$. A more detailed evaluation of the high-frequency tail of the virtual photon spectrum shows it to be

$$dn_\omega \alpha \frac{d\omega }{\omega }e^{2\omega b_{\mathrm{min}}/\gamma c}\text{(high frequency)}.$$
(3)
From this, we see the general relation between the critical frequency and the minimum impact parameter is

$$\omega _C\gamma \frac{c}{b_{\mathrm{min}}},b_{\mathrm{min}}\gamma \lambda _C.$$
(4)
The characteristic angular spread $`\theta _C`$ of the radiation pattern near the critical frequency can be estimated from eq. (4) by noting that the radiation is much like that of a beam of light with waist $`b_{\mathrm{min}}`$. Then, from the laws of diffraction we conclude that

$$\theta _C\frac{\lambda _C}{b_{\mathrm{min}}}\frac{1}{\gamma }.$$
(5)
This behavior is also expected in that a ray of light emitted in the electron’s rest frame at $`90^{}`$ appears at angle $`1/\gamma `$ to the laboratory direction of the electron.

### A The Formation Length

To complete an application of the Weizsäcker-Williams method, we must also know over what interval the virtual photon cloud is shaken off the electron to become the radiation detected in the laboratory. Intense (and hence, physically interesting) radiation processes are those in which the entire cloud of virtual photons is emitted as rapidly as possible. This is usefully described by the so-called formation time $`t_0`$ and the corresponding formation length $`L_0=vt_0`$ where $`vc`$ is the velocity of the relativistic electron.

The formation length (time) is the distance (time) the electron travels while a radiated wave advances one wavelength $`\lambda `$ ahead of the projection of the electron’s motion onto the direction of observation. The wave takes on the character of radiation that is no longer tied to its source only after the formation time has elapsed. That is,

$$\lambda =ct_0vt_0\mathrm{cos}\theta L_0(1\beta \mathrm{cos}\theta )L_0\left(\frac{1}{2\gamma ^2}+\frac{\theta ^2}{2}\right),$$
(6)
for radiation observed at angle $`\theta `$ to the electron’s trajectory. Thus, the formation length is given by

$$L_0\frac{2\lambda }{\theta ^2+1/\gamma ^2}$$
(7)
If the frequency of the radiation is near the critical frequency (4), then the radiated intensity is significant only for θ

<

θC1/γ

<

𝜃subscript𝜃𝐶1𝛾\theta\mathrel{\vbox{\kern 0.0pt\hbox{$<$} \kern 0.0pt\hbox{$\sim$} }}\theta_{C}\approx 1/\gamma, and the formation length is

$$L_0\gamma ^2\lambda (\lambda \lambda _C).$$
(8)
A good discussion of the formation length in both classical and quantum contexts has been given in ref. .

### B Summary of the Method

A relativistic electron carries with it a virtual photon spectrum of $`\alpha `$ photons per unit frequency interval. When radiation occurs, for whatever reason, the observed frequency spectrum will closely follow this virtual spectrum. In cases where the driving force for the radiation extends over many formation lengths, the spectrum of radiated photons per unit path length for intense processes is given by expressions (2)-(3), which describe the radiation emitted over one formation length, divided by the formation length (7):

$$\frac{dn_\omega }{dl}\frac{\alpha }{L_0(\omega )}\frac{d\omega }{\omega }\times \{\begin{array}{cccc}1\hfill & & & (\omega <\omega _C),\hfill \\ e^{\omega /\omega _C}\hfill & & & (\omega \omega _C).\hfill \end{array}$$
(9)
Synchrotron radiation, undulator radiation, transition radiation, and Čerenkov radiation are examples of processes which can be described within the context of classical electromagnetism, but for which the Weizsäcker-Williams approximation is also suitable. Čerenkov radiation and transition radiation are often thought of as rather weak processes, but the Weizsäcker-Williams viewpoint indicates that they are actually as intense as is possible for radiation by a single charge, in the sense that the entire virtual photon cloud is liberated over a formation length.

In this paper, we emphasize a simplified version of the Weizsäcker-Williams method with the goal of illustrating the principle qualitative features of various radiation processes. A more detailed analysis can reproduce the complete forms of the classical radiation, as has been demonstrated for synchrotron radiation by Lieu and Axford .

## II Synchrotron Radiation

Synchrotron radiation arises when a charge, usually an electron, is deflected by a magnetic field. For a large enough region of uniform magnetic field, the electron’s trajectory would be a complete circle. However, synchrotron radiation as described below occurs whenever the magnetic field region is longer than a formation length. The radiation observed when the magnetic field extends for less than a formation length has been discussed in refs. .

### A The Critical Frequency

An important fact about synchrotron radiation is that the frequency spectrum peaks near the critical frequency, $`\omega _C`$, which depends on the radius $`R`$ of curvature of the electron’s trajectory, and on the Lorentz factor $`\gamma `$ via

$$\omega _C\gamma ^3\frac{c}{R}.$$
(10)
Since $`\omega _0=c/R`$ is the angular velocity for particles with velocity near the speed of light, synchrotron radiation occurs at very high harmonics of this fundamental frequency. The wavelength at the critical frequency is then

$$\lambda _C\frac{R}{\gamma ^3}.$$
(11)
For completeness, we sketch a well-known argument leading to eq. (10). The characteristic frequency $`\omega _C`$ is the reciprocal of the pulselength of the radiation from a single electron according to an observer at rest in the lab. In the case of motion in a circle, the electron emits a cone of radiation of angular width $`\theta =1/\gamma `$ according to eq. (5) that rotates with angular velocity $`\omega =c/R`$. Light within this cone reaches the fixed observer during time interval $`\delta t^{}=\theta /\omega R/\gamma c`$. However, this time interval measures the retarded time $`t^{}`$ at the source, not the time $`t`$ at the observer. Both $`t`$ and $`t^{}`$ are measured in the lab frame, and are related by $`t^{}=tr/c`$ where $`r`$ is the distance between the source and observer. When the source is heading towards the observer, we have $`\delta r=v\delta t^{}`$, so $`\delta t=\delta t^{}(1v/c)\delta t^{}/2\gamma ^2R/\gamma ^3c`$, from which eq. (10) follows.

### B The Formation Length

The formation length $`L_0`$ introduced in eq. (7) applies for radiation processes during which the electron moves along a straight line, such as Čerenkov radiation and transition radiation. But, synchrotron radiation occurs when the electron moves in the arc of a circle of radius $`R`$. During the formation time, the electron moves by formation angle $`\theta _0=L_0/R`$ with respect to the center of the circle. We now reconsider the derivation of the formation time, noting that while the electron moves on the arc $`R\theta _0=vt_0`$ of the circle, the radiation moves on the chord $`2R\mathrm{sin}(\theta _0/2)R\theta _0R\theta _0^3/24`$. Hence,

$`\lambda `$ $`=`$ $`ct_0\text{chord}{\displaystyle \frac{cR\theta _0}{v}}R\theta _0+{\displaystyle \frac{R\theta _0^3}{24}}`$ (12)
$``$ $`R\theta _0(1\beta )+{\displaystyle \frac{R\theta _0^3}{24}}{\displaystyle \frac{R\theta _0}{2\gamma ^2}}+{\displaystyle \frac{R\theta _0^3}{24}},`$ (13)
for radiation observed at small angles to the chord.

For wavelengths longer than $`\lambda _C`$, the formation angle grows large compared to the characteristic angle $`\theta _C1/\gamma `$, and the first term of eq. (13) can be neglected compared to the second. In this case,

$$\theta _0\left(\frac{\lambda }{R}\right)^{1/3}\frac{1}{\gamma }\left(\frac{\lambda }{\lambda _C}\right)^{1/3}(\lambda \lambda _C),$$
(14)
and

$$L_0R^{2/3}\lambda ^{1/3}\gamma ^2\lambda _C\left(\frac{\lambda }{\lambda _C}\right)^{1/3}(\lambda \lambda _C),$$
(15)
using eq. (11).

The formation angle $`\theta _0(\lambda )`$ can also be interpreted as the characteristic angular width of the radiation pattern at this wavelength. A result not deducible from the simplified arguments given above is that for $`\lambda \lambda _C`$, the angular distribution of synchrotron radiation falls off exponentially: $`dU(\lambda )/d\mathrm{\Omega }e^{\theta ^2/2\theta _0^2}`$. See, for example, sec. 14.6 of .

For wavelengths much less than $`\lambda _C`$, the formation length is short, the formation angle is small, and the last term of eq. (13) can be neglected. Then, we find that

$$\theta _0\frac{\lambda }{\gamma \lambda _C},L_0\gamma ^2\lambda (\lambda \lambda _C),$$
(16)
the same as for motion along a straight line, eq. (8). In this limit, our approximation neglects the curvature of the particle’s trajectory, which is an essential aspect of synchrotron radiation, and we cannot expect our analysis to be very accurate. But for $`\lambda \lambda _C`$, the rate of radiation is negligible.

Of greater physical interest is the region $`\lambda \lambda _C`$ where the frequency spectrum begins to be exponentially damped but the rate is still reasonably high. The cubic equation (13) does not yield a simple analytic result in the region. So, we interpolate between the limiting results for $`\theta _0`$ at large and small wavelengths, eqs. (14) and (16), and estimate that

$$\theta _0\frac{1}{\gamma }\sqrt{\frac{\lambda }{\lambda _C}}(\lambda \lambda _C),$$
(17)
which agrees with a more detailed analysis . The corresponding formation length $`R\theta _0`$ is then

$$L_0\gamma ^2\sqrt{\lambda \lambda _C}(\lambda \lambda _C).$$
(18)
### C Transverse Coherence Length

The longitudinal origin of radiation is uncertain to within one formation length $`L_0`$. Over this length, the trajectory of the electron is curved, so there is an uncertainty in the transverse origin of the radiation as well. A measure of the transverse uncertainty is the sagitta $`L_0^2/8R`$, which we label $`w_0`$ anticipating a useful analogy with the common notation for the waist of a focused laser beam. For $`\lambda \lambda _C`$, we have from eq. (15),

$$w_0\frac{L_0^2}{R}R^{1/3}\lambda ^{2/3}\gamma \lambda _C\left(\frac{\lambda }{\lambda _C}\right)^{2/3}(\lambda \lambda _C).$$
(19)
The sagitta (19) is larger than the minimum transverse length (4), so we expect that the full virtual photon cloud is shaken off over one formation length.

For $`\lambda \lambda _C`$, the characteristic angular spread (14) of the radiation obeys

$$\theta _0\frac{\lambda }{w_0},$$
(20)
consistent with the laws of diffraction. Hence, the distance $`w_0`$ of eq. (19) can also be called the transverse coherence length  of the source of synchrotron radiation.

The analogy with laser notation is also consistent with identifying the formation length $`L_0`$ with the Rayleigh range $`z_0=w_0/\theta _0`$, since we see that

$$L_0\frac{\lambda }{\theta _0^2}\frac{w_0}{\theta _0}.$$
(21)
A subtle difference between the radiation of a relativistic charge and a focused laser beam is that the laser beam has a Guoy phase shift  between its waist and the far field, while radiation from a charge does not.

For $`\lambda \lambda _C`$, the sagitta is $`L_0^2/R\gamma ^2\lambda `$, using eq. (18). When $`\lambda <\lambda _C`$, the characteristic angle $`\theta _0`$ given by eq.(17) is less than $`\lambda `$/sagitta, and the sagitta is no longer a good measure of the transverse coherence length, which is better defined as $`\lambda /\theta _0\gamma \sqrt{\lambda \lambda _C}`$.

### D Frequency Spectrum

The number of photons radiated per unit path length $`l`$ during synchrotron radiation is obtained from the Weizsäcker-Williams spectrum (9) using eqs. (15) and (18) for the formation length:

dnωdl{αωC2/3dω/γ2cω2/3(λλC),αωC1/2eω/ωCdω/γ2cω1/2(λ

<

λC).𝑑subscript𝑛𝜔𝑑𝑙cases𝛼superscriptsubscript𝜔𝐶23𝑑𝜔superscript𝛾2𝑐superscript𝜔23missing-subexpressionmissing-subexpressionmuch-greater-than𝜆subscript𝜆𝐶𝛼superscriptsubscript𝜔𝐶12superscript𝑒𝜔subscript𝜔𝐶𝑑𝜔superscript𝛾2𝑐superscript𝜔12missing-subexpressionmissing-subexpression

<

𝜆subscript𝜆𝐶{dn_{\omega}\over dl}\approx\left\{\begin{array}[]{llll}\alpha\omega_{C}^{2/3}d\omega/\gamma^{2}c\omega^{2/3}&&&(\lambda\gg\lambda_{C}),\\
\alpha\omega_{C}^{1/2}e^{-\omega/\omega_{C}}d\omega/\gamma^{2}c\omega^{1/2}&&&(\lambda\mathrel{\vbox{\kern 0.0pt\hbox{$<$} \kern 0.0pt\hbox{$\sim$} }}\lambda_{C}).\end{array}\right. (22)
We multiply by $`\mathrm{}\omega `$ to recover the energy spectrum:

dU(ω)dl{e2ωC2/3ω1/3dω/γ2c2(λλC),e2ωC1/2ω1/2eω/ωCdω/γ2c2(λ

<

λC).𝑑𝑈𝜔𝑑𝑙casessuperscript𝑒2superscriptsubscript𝜔𝐶23superscript𝜔13𝑑𝜔superscript𝛾2superscript𝑐2missing-subexpressionmissing-subexpressionmuch-greater-than𝜆subscript𝜆𝐶superscript𝑒2superscriptsubscript𝜔𝐶12superscript𝜔12superscript𝑒𝜔subscript𝜔𝐶𝑑𝜔superscript𝛾2superscript𝑐2missing-subexpressionmissing-subexpression

<

𝜆subscript𝜆𝐶{dU(\omega)\over dl}\approx\left\{\begin{array}[]{llll}e^{2}\omega_{C}^{2/3}\omega^{1/3}d\omega/\gamma^{2}c^{2}&&&(\lambda\gg\lambda_{C}),\\
e^{2}\omega_{C}^{1/2}\omega^{1/2}e^{-\omega/\omega_{C}}d\omega/\gamma^{2}c^{2}&&&(\lambda\mathrel{\vbox{\kern 0.0pt\hbox{$<$} \kern 0.0pt\hbox{$\sim$} }}\lambda_{C}).\end{array}\right. (23)
Thus, the Weizsäcker-Williams method shows that the energy spectrum varies as $`\omega ^{1/3}`$ at low frequencies, and as $`\sqrt{\omega }e^{\omega /\omega _C}`$ at frequencies above the critical frequency $`\omega _C=\gamma ^3c/R`$.

The total radiated power is estimated from eq. (23) using $`\omega d\omega \omega _C\gamma ^3c/R`$, and multiplying by $`vc`$ to convert $`dl`$ to $`dt`$:

$$\frac{dU}{dt}\frac{e^2\gamma ^4c}{R^2}.$$
(24)
This well-known result is also obtained from the Larmor formula, $`dU/dt=2e^2a^2/3c^2`$, where the rest-frame acceleration is given by $`a^{}=\gamma ^2a\gamma ^2c^2/R`$ in terms of lab quantities.

## III Undulator Radiation

An undulator is a device that creates a region of transverse magnetic field that whose magnitude oscillates with spatial period $`\lambda _0`$. This field is constant in time, and is usually lies in a transverse plane (although helical undulators have been built, and are actually somewhat easily to analyze). As an electron with velocity $`v`$ traverses the undulator, its trajectory involves transverse oscillations with laboratory wavelength $`\lambda _0`$, and laboratory frequency $`\omega _0=c/\mathrm{\lambda ̄}_0`$. The oscillating electron then emits undulator radiation.

This radiation is usefully described by first transforming to the average rest frame of the electron, which is done by a Lorentz boost of $`\gamma =1/\sqrt{1(v/c)^2}`$ in the first approximation. The undulator wavelength in this frame is $`\lambda ^{}=\lambda _0/\gamma `$, and the frequency of the oscillator is $`\omega ^{}=\gamma \omega _0`$. The electron emits dipole radiation at this frequency in its average rest frame. The laboratory radiation is the transform of this radiation.

Thus, undulator radiation is readily discussed as the Lorentz transform of a Hertzian dipole oscillator, and the Weizsäcker-Williams approximation does not offer much practical advantage here. However, an analysis of undulator radiation can validate the Weizsäcker-Williams approximation, while also exploring the distinction between undulator radiation and wiggler radiation.

### A A First Estimate

The characteristic angle of undulator radiation in the laboratory is $`\theta _C1/\gamma `$, this being the transform of a ray at $`\theta ^{}=90^{}`$ to the electron’s lab velocity. The radiation is nearly monochromatic, with frequency

$$\omega _C2\gamma \omega ^{}=2\gamma ^2\omega _0,$$
(25)
and wavelength

$$\lambda _C\frac{\lambda _0}{2\gamma ^2}.$$
(26)
The formation length, defined as the distance over which radiation pulls one wavelength ahead of the electron, is $`L_0\gamma ^2\lambda \lambda _0`$, the undulator period. But when the electron advances one period, it continues to oscillate, and the amplitude of the radiation emitted during the second period is in phase with that of the first. Assuming that the radiation from successive period overlaps in space, there will be constructive interference which continues over the entire length of the undulator. In this case, the radiation is not clearly distinct from the near zone of the electron until it leaves the undulator. Hence, the formation length of undulator radiation is better defined as

$$L_0=N_0\lambda _0,$$
(27)
where $`N_0`$ is the number of periods in the undulator.

The frequency spread of undulator radiation narrows as the number of undulator periods increases, and

$$\frac{\mathrm{\Delta }\omega }{\omega _C}\frac{1}{N_0}$$
(28)
We now try to deduce the radiated photon spectrum from the Weizsäcker-Williams approximation (9). The constructive interference over the $`N_0`$ undulator periods implies that the radiated energy will be $`N_0^2`$ times that if there were only one period. So we multiply eq. (9) by $`N_0^2`$ to obtain

$$\frac{dn_\omega }{dl}\frac{N_0^2\alpha }{L_0}\frac{d\omega }{\omega }\frac{\alpha }{\lambda _0},$$
(29)
in the narrow band (28) around the characteristic frequency (25). The radiated power is $`v\mathrm{}\omega _Cc\mathrm{}\omega _C`$ times eq. (29):

$$\frac{dU}{dt}\frac{e^2c\gamma ^2}{\lambda _0^2},$$
(30)
using eq. (25).

This estimate proves to be reasonable only for that part of the range of undulator parameters. To clarify this, we need to examine the electron’s trajectory through the undulator in greater detail.

### B Details of the Electron’s Trajectory

A magnetic field changes the direction of the electron’s velocity, but not its magnitude. As a result of the transverse oscillation in the undulator, the electron’s average forward velocity $`\overline{v}`$ will be less than $`v`$. The boost to the average rest frame is described by $`\overline{\gamma }`$ rather than $`\gamma `$.

In the average rest frame, the electron is not at rest, but oscillates in the electric and magnetic fields $`\stackrel{~}{E}\stackrel{~}{B}=\overline{\gamma }B_0`$, where we use the symbol $`\stackrel{~}{}`$ to indicate quantities in the average rest frame. The case of a helical undulator is actually simpler than that of a linear one. For a helical undulator, the average-rest-frame fields are essentially those of circularly polarized light of frequency $`\stackrel{~}{\omega }=\overline{\gamma }\omega _0`$. The electron moves in a circle of radius $`R`$ at this frequency, in phase with the electric field $`\stackrel{~}{E}`$, and with velocity $`\stackrel{~}{v}`$ and associated Lorentz factor $`\stackrel{~}{\gamma }`$, all related by

$$\frac{\stackrel{~}{\gamma }m\stackrel{~}{v}^2}{R}=\stackrel{~}{\gamma }m\stackrel{~}{v}\stackrel{~}{\omega }=e\stackrel{~}{E}.$$
(31)
From this we learn that

$$\stackrel{~}{\gamma }\stackrel{~}{\beta }=\frac{e\stackrel{~}{E}}{m\stackrel{~}{\omega }c}\frac{eB_0}{m\omega _0c}\eta ,$$
(32)
and hence,

$$\stackrel{~}{\gamma }=\sqrt{1+\eta ^2},\stackrel{~}{\beta }=\frac{\eta }{\sqrt{1+\eta ^2}},$$
(33)
and

$$R=\frac{\stackrel{~}{\beta }c}{\stackrel{~}{\omega }}=\frac{\eta \stackrel{~}{\mathrm{\lambda ̄}}}{\sqrt{1+\eta ^2}}=\frac{\eta \mathrm{\lambda ̄}_0}{\overline{\gamma }\sqrt{1+\eta ^2}}$$
(34)
Thus, the dimensionless parameter $`\eta `$ describes many features of the transverse motion of an electron in an oscillatory field. It is a Lorentz invariant, being proportional to the magnitude of the 4-vector potential.

For a linear undulator, $`\eta `$ is usefully defined as

$$\eta =\frac{eB_{0,\mathrm{rms}}}{m\omega _0c},$$
(35)
where the root-mean-square (rms) average is taken over one period. With the definition (35), the rms values of $`\stackrel{~}{\beta }`$, $`\stackrel{~}{\gamma }`$ and $`R`$ for a linear undulator of strength $`\eta `$ are also given by eqs. (33)-(34).

We can now display a relation for $`\overline{\gamma }`$ by noting that in the average rest frame, the electron’s (average) energy is $`\stackrel{~}{\gamma }mc^2=m\sqrt{1+\eta ^2}c^2`$, while its average momentum is zero there. Hence, on transforming back to the lab frame, we have $`\gamma mc^2=\overline{\gamma }\stackrel{~}{\gamma }mc^2`$, and so

$$\overline{\gamma }=\frac{\gamma }{\sqrt{1+\eta ^2}}.$$
(36)
The transverse amplitude of the motion is obtained from eqs. (34) and (36):

$$R=\frac{\eta \mathrm{\lambda ̄}_0}{\gamma }=2\eta \gamma \mathrm{\lambda ̄}_C,$$
(37)
recalling eq. (26).

### C $`\eta >1`$: Wiggler Radiation

The pitch angle of the helical trajectory is

$$\theta \mathrm{tan}\theta =\frac{R}{\mathrm{\lambda ̄}_0}=\frac{\eta }{\gamma }.$$
(38)
Since the characteristic angle of the radiation is $`\theta _C1/\gamma `$, we see that the radiation from one period of the oscillation does not overlap the radiation from the next period unless

η

<

1.

<

𝜂1\eta\mathrel{\vbox{\kern 0.0pt\hbox{$<$} \kern 0.0pt\hbox{$\sim$} }}1. (39)
Hence, there is no constructive interference and consequent sharpening of the frequency spectrum unless condition (39) is satisfied.

For $`\eta >1`$, the radiation is essentially the sum of synchrotron radiation from $`N_0`$ separate magnets each $`\lambda _0`$ long, and this case is called wiggler radiation.

The laboratory frequency of the radiation is now

$$\omega _C2\overline{\gamma }^2\omega _0,$$
(40)
rather than eq. (25). However, in the regime of undulator radiation, (39), there is little difference between the two expressions.

Another aspect of wiggler radiation is that for η

>

1

>

𝜂1\eta\mathrel{\vbox{\kern 0.0pt\hbox{$>$} \kern 0.0pt\hbox{$\sim$} }}1 the motion of the electron in its average rest frame is relativistic, as can be see from eq. (33). In this case, higher multipole radiation becomes important, which appears at integer multiples of frequency $`\omega ^{}`$ in the average rest frame, and at the corresponding Lorentz transformed frequencies in the lab frame. The total radiated power is still given by eq. (30), so the amount of power radiated any particular frequency is less than when $`\eta 1`$.

### D $`\eta <1`$: Weak Undulators

The estimate (30) for the power of undulator radiation holds only if essentially the whole virtual photon cloud around the electron is shaken off. This can be expected to happen only if the amplitude of the electron’s transverse motion exceeds the minimum impact parameter $`b_{\mathrm{min}}\gamma \lambda _C`$ introduced in eq. (4). From eq. (37) we see that the transverse amplitude obeys

$$R\eta b_{\mathrm{min}}.$$
(41)
Thus, for $`\eta `$ less than one, the undulator radiation will be less than full strength. We readily expect that the intensity of weak radiation varies as the square of the amplitude of the motion, so the estimate (30) should be revised as

dUdtη2e2cγ2λ02,(η

<

1).𝑑𝑈𝑑𝑡superscript𝜂2superscript𝑒2𝑐superscript𝛾2superscriptsubscript𝜆02

<

𝜂1{dU\over dt}\approx{\eta^{2}e^{2}c\gamma^{2}\over\lambda_{0}^{2}},\qquad(\eta\mathrel{\vbox{\kern 0.0pt\hbox{$<$} \kern 0.0pt\hbox{$\sim$} }}1). (42)
The radiated power can be calculated exactly via the Larmor formula,

$$\frac{dU}{dt}=\frac{2e^2a^2}{3c^3},$$
(43)
where $`a^{}=eE^{}/m`$ is the acceleration of the electron in its instantaneous rest frame. The electron is moving in a helix with its velocity perpendicular to $`𝐁_0`$, so the electric field in the instantaneous rest frame is $`E^{}=\gamma \beta B_0\gamma B_0`$. Hence,

$$\frac{dU}{dt}\frac{2e^2\gamma ^2}{3c}\left(\frac{eB_0}{mc}\right)^2=\frac{2e^2c\gamma ^2\eta ^2}{3\mathrm{\lambda ̄}_0^2},$$
(44)
in agreement with the revised estimate (42).

In practice, $`\eta 1`$ is the region of greatest interest as it provides the maximum amount of radiation at the fundamental frequency $`\omega _C`$.

## IV Transition Radiation

As a charged particle crosses, for example, a vacuum/metal boundary, its interaction with charges in the material results in their acceleration and hence radiation, commonly called transition radiation. The formation zone extends outwards from each boundary, with formation length given by eq. (7). The number of photons emitted as the particle crosses each boundary is given by eq. (2) as $`\alpha `$ per unit frequency interval. If two boundaries are separated by less than a formation length, interference effects arise that will not be considered here.

The minimum relevant transverse scale, $`b_{\mathrm{min}}`$, is the plasma wavelength $`\mathrm{\lambda ̄}_p=c/\omega _p`$, so the critical frequency is $`\omega _C\gamma \omega _p`$, according to eq. (4). This is well into the x-ray regime. While the characteristic angle of transition radiation is $`1/\gamma `$, there is only a power-law falloff at larger angles, and the optical transition radiation from an intense beam of charged particles can be used to measure the spot size to accuracy of a few $`\lambda `$ .

## V Čerenkov Radiation

When a charged particle moves with velocity $`v`$ in a dielectric medium, Čerenkov radiation is emitted at those wavelengths for which $`v>c/n`$, where $`n(\lambda )`$ is the index of refraction. As the particle approaches lightspeed in a medium, its electric field is compressed into a “pancake”, which deforms into a cone when the the particle velocity exceeds lightspeed. The particle outruns its electric field, which is freed as the Čerenkov radiation. The fields become identifiable as radiation after the particle has moved a formation length, $`L_0=vt_0`$, which is the distance over which the electron pulls one wavelength ahead of the projection of the wave motion onto the electron’s direction. The Čerenkov angle $`\theta _C`$ is defined by the direction of the radiation, which is normal to the conical surface that contains the electric field. As usual, $`\mathrm{cos}\theta _C=c/nv=1/n\beta `$. The formation length is then

$$\lambda =vt_0\frac{c}{n}t_0\mathrm{cos}\theta _C=L_0\mathrm{sin}^2\theta _C.$$
(45)
Thus $`L_0=\lambda /\mathrm{sin}^2\theta _C`$, and the photon spectrum per unit path length from eq. (2) is

$$\frac{dn_\omega }{dl}\frac{\alpha }{L_0}\frac{d\omega }{\omega }\frac{\alpha \mathrm{sin}^2\theta _C}{\lambda }\frac{d\omega }{\omega }\alpha \mathrm{sin}^2\theta _C\frac{d\omega }{c},$$
(46)
as is well-known.

The characteristic angle $`\theta _C`$ of Čerenkov radiation is essentially independent of the Lorentz factor $`\gamma `$ of the charged particle, unlike that for the other radiation processes considered here. Correspondingly, the characteristic transverse length $`b`$ associated with Čerenkov radiation is also largely independent of $`\gamma `$. Rather, the region over which the Čerenkov radiation develops has radius roughly that of the Čerenkov cone after one formation length, i.e., $`b=L_0\mathrm{cos}\theta _C\mathrm{sin}\theta _C\lambda /\mathrm{tan}\theta _C`$. This is large only near the Čerenkov threshold where the radiated intensity is very small.

That the formation radius for Čerenkov radiation is of order $`\lambda `$ is supported by an analysis  of a particle moving in vacuum along the axis of a tube inside a dielectric medium; the calculated Čerenkov radiation is negligible at wavelengths larger than the radius of the tube.

Čerenkov radiation is a form of energy loss for a particle passing through a medium, and is related to so-called ionization loss (see, for example, secs. 13.1-4 of ). The latter is important for frequencies higher than the ionization potential (divided by $`\mathrm{}`$) of the medium, for which the index of refraction is typically less than one. At frequencies that can cause ionization, the Čerenkov effect is insignificant. The transverse scale of the ionizing fields grows with $`\gamma `$ due to relativistic flattening, but shielding due to the induced dielectric polarization of the medium results in an effective transverse scale $`b\sqrt{\gamma }`$ for these fields when $`\gamma 1`$.


format: text

text:
# Computing with Highly Mixed States

## 1 Introduction

Ideally, a quantum computation is a sequence of local unitary transformations applied to a register of qubits which are initially in the state $`|0^n`$; followed by a measurement. Initializing the state of the quantum register is the biggest challenge in NMR quantum computing (which is perhaps the most advanced technology in terms of the scale of experiments performed to date ). The difficulty is that the register is actually initially in (approximately) the binomial distribution over pure states $`|x`$, in which each qubit is independently in the state $`|0`$ with probability $`\frac{1+ϵ}{2}`$; the currently achievable polarization $`ϵ`$ is quite small. There are currently two ways of implementing quantum computation in this technology. The first is used in current experiments , but does not scale beyond several qubits — the output signal decreases exponentially in the number of qubits in the quantum register.111 The exponential decay in signal to noise ratio in any scheme that embeds virtual pure states on an $`n`$-qubit quantum computer with one clean qubit is unavoidable, due to the result . The second does scale, but is not feasible at the currently achievable values of polarization in liquid NMR . An intriguing third possibility was raised in . Suppose we start with one qubit in the pure state $`|0`$ in tensor product with $`n1`$ qubits in a maximally mixed state (i.e. in a uniform distribution over basis states $`|x`$). Is it possible to simulate general quantum computation by effecting a sequence of elementary quantum operations on this register? If the answer were affirmative, this would yield a procedure that would both scale and be currently feasible using the scalable initialization procedure to convert the initial binomial state to a state where the last $`n1`$ qubits are maximally mixed and the first bit has high polarization (the strength of the output signal is now proportional to this polarization). This is the question we focus on in this paper.

It is easy to see that if all $`n`$ qubits are in the maximally mixed state then no computation is possible. This is because applying any unitary transformation to this mixture leaves it invariant. This simple argument stands in striking contrast to the difficulty of the seemingly very similar case, in which just a single qubit is in a pure state, while all the others are maximally mixed. Since the initial state of the register is completely specified, the only real input in this model is the sequence of elementary quantum operations. So, given a quantum circuit $`C`$ which we would like to simulate on an input $`x`$, we wish to know whether there is a sequence of elementary quantum operations on the $`n`$ qubit register, which first prepares a quantum (mixed) state which encodes $`x`$, and then simulates $`C`$ on it. Of course, we will require that these mixed state encodings of basis states $`x`$ be distinguishable by some measurement with non-trivial probability.

Our main result shows that the above is impossible unless $`|x|O(\mathrm{log}n)`$, showing that the simulation is no more efficient than an exhaustive classical calculation. The technique used to show this uses some information about the representations of the symmetric group. The appendix 6 provides some necessary notions from representation theory.

We also show that using a 3-bit register it is possible to compute every language in NC1. This should give some indication of why the impossibility result is so much harder than for the case when all $`n`$ qubits are maximally mixed.

## 2 NC1

We begin by showing that in this model, even using a 3-bit register, we can compute every language in NC1.

Recall that the initial state of the register is a uniform distribution over the four $`3`$-bit strings starting with a $`0`$. In our simulation of NC1, all our operations will simply permute basis states.

###### Proposition 1

A $`3`$-bit quantum computer initialized with one clean qubit can recognize every language in NC1.

Our simulation is based on Barrington’s result that NC1 can be simulated by a width $`5`$ permutation branching program . The main idea is quite simple: let the $`5`$ states of the permutation branching program be represented by the states $`|000`$ through $`|100`$ of the $`3`$-qubit register. Without loss of generality assume that the permutation branching program accepts if the permutation it effects is the identity, and rejects if the permutation it effects is the transposition $`(000,100)`$. It is easy to simulate the permutation branching program by a sequence of elementary quantum operations. Now if we measure the first qubit in the register, then in the case that the permutation branching program accepts – i.e. the permutation effected is the identity – then measuring the first qubit in the register yields a $`0`$ with probability $`1`$. On the other hand, if the permutation branching program rejects, then measuring the first qubit in the register yields a $`1`$ with probability $`1/4`$.   $`\mathrm{}`$

It is illuminating to try to extend this simulation to QNC1. First notice that in Barrington’s procedure for simulating NC1, each wire in the NC1 circuit is simulated at some stage in the branching program. In the case of a QNC1 circuit, the state of a wire is given by a qubit, which is, in general, entangled with the qubits carried by the other wires in the circuit. Therefore the state of this wire cannot be expressed in isolation, and there appears to be no alternative to creating that entangled state as part of any simulation. Thus the entire approach breaks down. One way to carry out such a construction, might be to apply a superposition of operations at each step: this extends the state space of the quantum computer and effectively provides many more clean qubits, making the model meaningless. Moreover all proposed implementations of quantum computation involve a classical, time-varying sequence of operations, applied to a quantum register. Since the control is classical, in any oblivious simulation the entangled quantum state of the simulated circuit must be encoded within the quantum register.

## 3 Limit on Computability

We are given a quantum computer with an $`n`$ qubit register, with one bit initialized to $`|0`$ and the rest of the $`n1`$ qubits in a maximally mixed state. We would like to simulate an $`m`$ qubit quantum circuit $`C`$ on input string $`x`$ using this model. If we wish to do an oblivious simulation, as sketched in the previous section, we must encode an arbitrary $`m`$ qubit state into the uninitialized $`n`$ qubit register. To do so, it is sufficient to consider the $`2^m`$ basis states of the $`m`$ wires, and encode them as distinguishable states of the uninitialized $`n`$ qubit register (for this to be an efficient encoding, we should have $`nO(poly(m))`$). The states must be distinguishable in the following sense: since we can prepare several copies of any state by repeating the simulation, we only require that there be a sequence of measurements on $`O(poly(n))`$ many copies of the state, that (with high probability) uniquely identify the state. Indeed, it is possible to do this with $`n=m`$, as follows: take the subspaces, spanned by the basis vectors in the sets $`A_b=\{x\{0,1\}^n:xb=0\mathrm{mod}\mathrm{\hspace{0.33em}2}\}`$ for $`b\{0,1\}^n`$.

However, to perform an oblivious simulation, the encoding must satisfy another property – permutability. The quantum circuit $`C`$ might carry out any unitary operation on its quantum state, and in particular an arbitrary permutation on its classical states. Again it is not hard to demonstrate an efficient encoding that satisfies this permutability condition, without distinguishability: take the subspaces spanned by the basis vectors in the sets $`A_b=\{x=(x_1\mathrm{}x_n)\{0,1\}^n:x_1=0\text{ or }(x_2\mathrm{}x_n)=b\}`$ for $`b\{0,1\}^{n1}`$.

However, it is not possible to construct an efficient encoding that satisfies both conditions simultaneously. This is the content of the following theorem.

Let $`M=2^m`$ be the total number of basis states of the ideal quantum computer which is being simulated. Note that each $`X𝒳`$ encoding one of these, is a subspace of dimension $`2^{n1}`$ within the Hilbert space $`^{2^n}`$ of the computer. If the computer has $`k`$ clean qubits, then $`X`$ is of dimension $`2^{nk}`$.

###### Theorem 2

Suppose that computations on $`m`$ qubits can be obliviously simulated in an $`n`$-qubit, $`k`$-clean-qubit computer in our model, and that $`dim(XY)/dim(X)<1\frac{1}{\text{poly}(m)}`$ for every pair of input encodings $`X,Y𝒳`$. Then $`m(2k+\mathrm{log}n)(1+o(1))`$.

This incidentally implies that the computation of an $`n`$-qubit, $`k`$-clean-qubit computer can be simulated by a classical computer with a $`\text{poly}(n2^k)`$ computational overhead.

It may be illuminating to consider a simpler, classical analogue of our problem. A classical circuit (taking inputs in $`\{0,1\}^n`$) composed of reversible gates executes a permutation of $`\{0,1\}^n`$. The analogous problem (just considering the case $`k=1`$) is that we can only represent inputs as uniform probability distributions over a set of half the elements of $`\{0,1\}^n`$. (In the quantum case this corresponds to axis-parallel subspaces of dimension $`2^{n1}`$.) The question is, what is the largest number of such subsets (probability distributions) which such a circuit can permute at will. It is also essential that the probability distributions be readily distinguishable by sampling, in other words the subsets must have small intersection. It is possible (though we omit it in this extended abstract) to provide a strictly combinatorial argument expressing the fact that this task is impossible for more than $`\text{poly}(n)`$ subsets, because of the tension between the two requirements (permutability and distinguishability). The large size of the subsets means that we have far more constraints than we have degrees of freedom. The combinatorial argument shows that if the requirement of full permutability is imposed, and we have a superpolynomial (in $`n`$) number of subsets, then the symmetric difference of every two sets must be a vanishing fraction of the size of the sets. The two types of sets $`\{A_b\}`$ described above, however, separately achieve distinguishability and permutability.

In the quantum case we have arbitrary subspaces in place of “subsets” (or correspondingly axis-parallel subspaces). And the circuit of course can perform not just permutations of the basis, but general unitary operations. In sharp contrast with the classical case, two subspaces of half the dimensionality of the space typically will not intersect. Nevertheless, the large dimension of the subspaces imposes strict constraints on an operator which must permute them; the difficulty is in formulating the incompatibility of these requirements when the number of subspaces is large and the subspaces are required to be very distinct.

Proof:

By assumption, there are unitary operators (each corresponding to some sequence of steps in the computer) permuting $`𝒳`$ in all ways. Let $`f_\pi `$ be the unitary operator corresponding to a permutation $`\pi S_M`$. If we have $`f_{\pi \sigma }=f_\pi f_\sigma `$ for all $`\pi `$ and $`\sigma S_M`$, then the operators $`f_\pi `$ form a representation of $`S_M`$ and we can apply the representation theory of the symmetric group.

Actually, the situation is slightly more complicated.

Let $`U`$ be the unitary group on $`^{2^n}`$. Let $`H`$ be the subgroup of $`U`$ acting on $`𝒳`$, i.e. carrying any $`X𝒳`$ to some $`Y𝒳`$. Let $`G`$ be the subgroup of $`H`$ that fixes all of $`𝒳`$; thus $`G`$ is normal in $`H`$.

It is apparent that $`H/GS_M`$, but although this means that $`H`$ can permute the subspaces $`𝒳`$ in arbitrary ways, it is different from saying that there is a subgroup of $`H`$ isomorphic to $`S_M`$ (or in other words that we can pick elements of $`H`$ so as to have these operators compose properly).

## 4 Proof of Theorem 2: the simple case

First, we show how to prove Theorem 2 if we can select transformations $`f_\pi `$ so that they form a representation ($`f_\pi f_\sigma =f_{\pi \sigma }`$). The more general case will be handled in the next section. Appendix (section 6) explains the notions of representation theory used in this and the next section.

We show that every pair $`X,Y\widehat{𝒳}`$ have a substantial intersection. Consider the decomposition of $`^{2^n}`$ into irreducible representations $`\rho _1\mathrm{}\rho _k`$. Let $`N=2^n`$.

###### Lemma 3

Either the first row or the first column of the Young diagram of each $`\rho _i`$ is of length more than $`Mcn`$.

Proof:

This results follows from a theorem by Rasala:

###### Theorem 4

\[10, pp.151-152\]

1. Let $`AM/2`$ and $`\rho `$ be an irreducible representation of $`S_M`$ such that the first row of the Young diagram of $`\rho `$ is of length exactly $`MA`$. Then,

$$dim\rho \phi _A(M)$$

where $`\phi _A(M)=\left(\genfrac{}{}{0pt}{}{M}{A}\right)\left(\genfrac{}{}{0pt}{}{M}{A1}\right)=\frac{M2A1}{MA1}\left(\genfrac{}{}{0pt}{}{M}{A}\right)`$ is the dimension of the irreducible representation corresponding to the partition $`(MA,A)`$.
2. If $`\rho `$ is an irreducible representation with both the first row and the first column of length at most $`M/2`$, then

$$dim\rho \phi _{M/2}(M).$$

This theorem means that any representation with the first row of the Young diagram having length at most $`Mk`$, $`kM/2`$ has dimension at least

$$\underset{B:ABM/2}{\mathrm{min}}\phi _B(M).$$

Simple algebra shows that this expression is minimized by $`B=A`$ if $`AM/2c\sqrt{M}`$ for some constant $`c`$ and $`B=M/2`$ if $`A>M/2c\sqrt{M}`$.222In the second case, the lowest-dimensional representation actually has the first row less than $`MA`$. It is quite surprsing because, in most cases, removing a square from the first row of a Young diagram and adding a square somewhere else increases the dimension.

To deduce our lemma, assume that the Young diagram of an irreducible representation of $`S_M`$ has both first row and column of length at most $`MA`$. We show that $`N2^A`$. Consider two cases:

Case 1: $`AM/2c\sqrt{M}`$.

Notice that $`AM\sqrt{M}`$ because otherwise the Young diagram would fit into a square with a side less than $`\sqrt{M}`$ and area less than $`M`$. Theorem 4 implies that

$$dim\rho \phi _{M/2}(M)=\mathrm{\Omega }\left(\frac{2^M}{M\sqrt{M}}\right)=2^{M\frac{3\mathrm{log}M}{2}O(1)}>2^A.$$

Case 2: $`AM/2c\sqrt{M}`$. Then,

$$dim\rho \phi _A(M)=\frac{M2A+1}{MA+1}\left(\genfrac{}{}{0pt}{}{M}{A}\right)\frac{1}{M}\left(\frac{M}{A}\right)^A$$

$$=\frac{1}{M}\left(\frac{M}{2A}\right)^A2^A2^A.$$

$`\mathrm{}`$

Another lower bound on the longest row or column of a low dimension representation (for a different range of parameters) was given by Mischenko.

Next consider the stabilizer of $`X`$ in $`S_M`$, which is isomorphic to $`S_{M1}`$, and which we will denote $`S_{M1}^X`$. $`X`$ decomposes into irreducible representations $`V_1,\mathrm{}V_{\mathrm{}}`$ of $`S_{M1}^X`$. $`V_1`$ is carried by $`S_M`$ into each $`Y\widehat{𝒳}`$, and all these copies of $`V_1`$ are contained within some irreducible $`W`$ of $`S_M`$ in $`^{2^n}`$.

By the previous lemma, the Young diagram of $`W`$ has a long first column or row. We use the following fact from the representation theory of the symmetric group: when we restrict an irreducible representation0 $`\rho _\lambda `$ of $`S_M`$ of shape $`\lambda `$ to a subgroup $`S_{M1}S_M`$, it decomposes into irreducibles of $`S_{M1}`$ in the following way:

$$\rho =\underset{\lambda ^{}}{}\rho _\lambda ^{}$$

where $`\lambda ^{}`$ ranges over all shapes of size $`M1`$ that can be obtained by deleting an “inside corner” from $`\lambda `$. (An inside corner is simply a point of the shape whose deletion leaves a legal shape.)

We now use:

###### Lemma 5

Suppose the shape $`\lambda `$ has a first row (column) of length $`|\lambda |\mathrm{}`$ for $`\mathrm{}<|\lambda |/2`$. Let $`\lambda _1`$ denote the “$`\lambda ^{}`$” obtained by deleting the last element of the first row (column). Then $`dim(\rho _{\lambda _1})\frac{|\lambda |2\mathrm{}}{|\lambda |}dim(\rho _\lambda )`$.

Proof: Consider the ratio $`\frac{dim\rho _{\lambda _1}}{dim\rho _\lambda }=\frac{1}{|\lambda |}\frac{_{x\lambda }|x|}{_{x\lambda _1}|x|}`$. In the last ratio, points $`x`$ outside of the last row (column) appear identically in the numerator and denominator. Moreover for each $`x`$ in the first row (column) in the numerator other than the very last point (which contributes a factor of $`1`$ in the numerator and is absent in the denominator), the ratio between its contributions in the numerator and denominator is $`\frac{|x|}{|x|1}`$. Just examining the $`|\lambda |2\mathrm{}1`$ points of the first row furthest from the upper-left corner (and excepting the last point), we obtain a lower bound on these contributions of $`_{i=1}^{|\lambda |2\mathrm{}1}\frac{i+1}{i}=|\lambda |2\mathrm{}`$. Overall therefore $`\frac{dim\rho _{\lambda _1}}{dim\rho _\lambda }\frac{|\lambda |2\mathrm{}}{|\lambda |}`$.   $`\mathrm{}`$

###### Lemma 6

Let $`f_\pi `$ be an $`N`$-dimensional representation of $`S_M`$ that acts as a permutation representation on a collection of $`M`$ subspaces $`\widehat{𝒳}`$. Then, for any $`X,Y\widehat{𝒳}`$,

$$dimXdimXY\frac{2cn}{M}N.$$

(We write $`n=\mathrm{lg}N`$ and $`m=\mathrm{lg}M`$.)

Proof: We decompose $`f_\pi `$ into irreducible representations. Let $`W`$ be one of these irreducible representations. We show that $`dimXWdimXYW\frac{2cn}{M}dimW`$.

We look at $`W`$ as a representation of $`S_{M1}^X`$. Let $`V`$ be the highest dimensional irreducible representation of $`S_{M1}^X`$ within $`W`$. If $`M<2cn`$ then the assertion is trivial. Otherwise $`Mcn>M/2`$ and the hypothesis of lemma 5 is satisfied, implying that $`dimV\frac{M2cn}{M}dimW`$. Consider two cases:

Case 1: $`VX`$.

Take $`\pi S_M`$ such that $`Y=f_\pi (X)`$. Then, $`YW=f_\pi (XW)`$. Therefore, $`dim(YW)=dim(XW)dimV\frac{M2cn}{M}dimW`$ and

$$dimXWdimXYW\frac{2cn}{M}dimW.$$

Case 2: $`VX`$.

Then, $`VX=0`$ because $`VX`$ is invariant under $`S_{M1}^X`$ and $`V`$ is irreducible. $`VX=0`$ implies

$$dimV+dimXWdimW.$$

Together with $`dimV\frac{M2cn}{M}dimW`$, this implies

$$dimXWdimXYWdimXW\frac{2cn}{M}dimW.$$

The lemma follows by summation over all irreducible $`W`$.   $`\mathrm{}`$

If $`f_\pi `$ form a representation, Lemma 6 almost immediately implies Theorem 2. Namely, we have

$$\frac{dimXY}{dimX}=\frac{dimX(dimXdimXY)}{dimX}$$

$$\frac{2^{nk}\frac{2cn}{M}2^n}{2^{nk}}=1\frac{2^{k+1}cn}{M}.$$

If this is at most $`1\frac{1}{\text{poly}(m)}`$, then $`m(k+\mathrm{log}n)(1+o(1))`$.   $`\mathrm{}`$

## 5 Proof of Theorem 2: the difficult case

### 5.1 Proof outline

Next, we deal with the case when $`f_\pi f_\sigma f_{\pi \sigma }`$ for some $`\pi `$ and $`\sigma S_M`$. Let $`G`$ be the group of transformations that map every subspace $`X\widehat{𝒳}`$ to itself. Then, $`f_\pi f_\sigma f_{\pi \sigma }^1`$ is an element of $`G`$ for any $`\pi ,\sigma S_M`$. We would like to modify $`f`$ so that this element becomes identity for all $`\pi `$ and $`\sigma S_M`$. Then, $`f_\pi f_\sigma =f_{\pi \sigma }`$, i.e., $`f_\pi `$ would form a representation of $`S_M`$ and we would be able to analyse this representation similarly to the previous section.

To achieve this, we look at $`\text{ }\mathrm{C}^{2^n}`$ as a representation of $`G`$ and express $`\text{ }\mathrm{C}^{2^n}`$ as $`V_1V_2\mathrm{}V_k`$, with $`V_i`$ corresponding to different types of irreducible representations of $`G`$.

Then, we compose each $`f_\pi `$ with an appropriate $`g_\pi G`$. The resulting transformation $`f_\pi ^{}=g_\pi f_\pi `$ still implements the same permutation $`\pi `$ of $`\widehat{𝒳}`$ because $`g_\pi `$ maps every $`X\widehat{𝒳}`$ to itself. We can choose the transformations $`g_\pi `$ so that, on every $`V_i`$, $`f_\pi ^{}f_\sigma ^{}`$ is the same as $`f_{\pi \sigma }^{}`$ up to a phase ($`f_{\pi \sigma }^{}=c_{\pi ,\sigma ,i}f_\pi ^{}f_\sigma ^{}`$ for some unit $`c_{\pi ,\sigma ,i}\text{ }\mathrm{C}`$).

The next step is eliminating the phase factors $`c_{\pi ,\sigma ,i}`$. This is done by considering a larger space $`V_1V_1^{}+\mathrm{}+V_kV_k^{}`$ and transformations $`f_\pi ^{\prime \prime }=f_\pi ^{}(f_\pi ^{})^{}`$ on this larger space. Then, the phase factors $`c_{\pi ,\sigma ,i}`$ (from $`f^{}`$) and $`c_{\pi ,\sigma ,i}^{}`$ (from $`(f^{})^{}`$) cancel out and we get $`f_{\pi \sigma }^{\prime \prime }=c_{\pi ,\sigma ,i}c_{\pi ,\sigma ,i}^{}f_\pi ^{\prime \prime }f_\sigma ^{\prime \prime }=f_\pi ^{\prime \prime }f_\sigma ^{\prime \prime }`$. Thus, $`f_\pi ^{\prime \prime }`$ form a representation of $`S_M`$ on the linear space $`V_1V_1^{}+\mathrm{}+V_kV_k^{}`$. This representation can be analysed similarly to section 4, obtaining lower bounds on intersections of invariant subspaces.

### 5.2 Representation up to phases $`c_{\pi ,\sigma ,i}`$

Let $`G`$ be the group of unitary transformations that fix every one of the subspaces $`X\widehat{𝒳}`$.

Then, $`^{2^n}`$ is a representation of $`G`$ and all $`h\widehat{𝒳}`$ are invariant subspaces. (They are fixed by every element of $`G`$ according to the definition of $`G`$.) These invariant subspaces decompose into irreducible invariant subspaces.

Consider all the irreducible invariant subspaces of $`^{2^n}`$. Split them into equivalence classes consisting of isomorphic irreducible subspaces. Let $`E_1,\mathrm{},E_k`$ be these equivalence classes. Let $`V_1`$ be the subspace of $`^{2^n}`$ spanned by all the irreducible subspaces in $`E_1`$ (i.e., the subspace spanned by all the vectors belonging to at least one subspace in $`E_1`$). Let $`V_2`$, $`\mathrm{}`$, $`V_k`$ be defined similarly.

###### Claim 1

If $`i,j\{1,\mathrm{},k\}`$ and $`ij`$, then $`V_iV_j`$.

Therefore, $`^{2^n}=V_1V_2\mathrm{}V_k`$. Next, we show that transformations $`f_\pi `$ map each $`V_i`$ to some (possibly different) $`V_i^{}`$.

###### Claim 2

Let $`V`$ be an invariant subspace. Then, $`f_\pi (V)`$ is invariant as well. If $`V`$ is irreducible, $`f_\pi (V)`$ is irreducible. Moreover, if $`V`$ and $`V^{}`$ are two isomorphic irreducible subspaces, $`f_\pi (V)`$ and $`f_\pi (V^{})`$ are isomorphic as well.

Proof: The map $`gf_\pi gf_\pi ^1`$ is an automorphism of $`G`$. If $`V`$ is invariant under the action of $`g`$, $`f_\pi (V)`$ is invariant under the action of $`f_\pi gf_\pi ^1`$. Therefore, if $`V`$ is invariant under $`G`$, so is $`f_\pi (V)`$.

If $`f_\pi (V)`$ is not irreducible, it decomposes into two or more invariant subspaces: $`f_\pi (V)=W_1W_2`$. Then, $`f_\pi ^1(W_1)`$ is invariant as well, implying that $`V`$ is not irreducible.

Finally, let $`h:VV^{}`$ be a $`G`$-isomorphism of $`V`$ and $`V^{}`$ (an isomorphism that commutes with the action of $`G`$). Let $`h^{}:f_\pi (V)f_\pi (V^{})`$ be defined by $`h^{}=f_\pi hf_\pi ^1`$. Then, for any $`g=f_\pi g^{}f_\pi ^1`$, we have

$$h^{}g=(f_\pi hf_\pi ^1)(f_\pi g^{}f_\pi ^1)=f_\pi hg^{}f_\pi ^1=f_\pi g^{}hf_\pi ^1=gh^{}$$

and every $`gG`$ can be expressed in the form $`f_\pi g^{}f_\pi ^1`$. Therefore, $`h^{}`$ is a $`G`$-isomorphism of $`f_\pi (V)`$ and $`f_\pi (V^{})`$.   $`\mathrm{}`$

Remark. $`V`$ does not have to be isomorphic to $`f_\pi (V)`$ as a representation of $`G`$. $`f_\pi `$ establishes the isomorphism of $`g`$ on $`V`$ with $`f_\pi gf_\pi ^1`$ on $`f_\pi (V)`$, but $`f_\pi gf_\pi ^1`$ does not have to equal $`g`$ on $`f_\pi (V)`$.

###### Claim 3

For every $`i\{1,\mathrm{},k\}`$ there is an $`i^{}`$ such that $`f_\pi (V_i)=V_i^{}`$.

Proof: By Claim 2, every two isomorphic irreducible subspaces get mapped to isomorphic irreducible subspaces. Therefore, all subspaces in $`E_i`$ get mapped to subspaces in the same $`E_i^{}`$ and $`f_\pi (V_i)V_i^{}`$. Similar reasoning applied to $`f_\pi ^1`$ implies $`f_\pi ^1(V_i^{})V_i`$.   $`\mathrm{}`$

For each $`i\{1,\mathrm{},k\}`$, $`V_i`$ is the direct sum of some number of isomorphic irreducible subspaces: $`V_i=V_{i1}V_{i2}\mathrm{}V_{ij_i}`$. We fix $`G`$-isomorphisms $`h_{ijj^{}}`$ between $`V_{ij}`$ and $`V_{ij^{}}`$ so that $`h_{ij^{}j^{\prime \prime }}h_{ijj^{}}=h_{ijj^{\prime \prime }}`$. (By Schur’s lemma, each of these isomorphisms is unique up to a multiplicative constant. The isomorphisms can be made to compose properly by adjusting these constants. Note of course that $`h_{ijj}`$ is the identity.)

###### Claim 4

$`WV_i`$ is an irreducible invariant subspace if and only if

$$W=\{a_jx+a_{j+1}h_{ij(j+1)}(x)+\mathrm{}+a_{j_i}h_{ijj_i}(x)|xV_{ij}\}$$

for some $`j\{1,\mathrm{},j_i\}`$ and $`a_j,\mathrm{},a_{j_i}\text{ }\mathrm{C}`$.

Proof: “If” part:

Invariance:

$$g(\underset{\mathrm{}=j}{\overset{j_i}{}}a_{\mathrm{}}h_{ij\mathrm{}}(x))=\underset{\mathrm{}=j}{\overset{j_i}{}}a_{\mathrm{}}g(h_{ij\mathrm{}}(x))=\underset{\mathrm{}=j}{\overset{j_i}{}}a_{\mathrm{}}h_{ij\mathrm{}}(g(x))$$

because each $`h_{ij\mathrm{}}`$ is a $`G`$-isomorphism.

$`W`$ is irreducible because, if $`W_1W`$ and $`W_1`$ is invariant, then

$$\{x|a_jx+a_{j+1}h_{ij(j+1)}(x)+\mathrm{}+a_{j_i}h_{ijj_i}(x)W_1\}$$

is an invariant subspace of $`V_{ij}`$; but $`V_{ij}`$ is irreducible and $`dim(W)=dim(V_{ij})`$.

“Only if” part:

Let $`W`$ be an irreducible invariant subspace of $`V_i`$. Let $`x^{}W`$. Then, we can write $`x^{}`$ as $`x_1^{}+\mathrm{}+x_{j_i}^{}`$, $`x_1^{}V_{i1}`$, $`\mathrm{}`$, $`x_{j_i}^{}V_{ij_i}`$. If $`x^{}x^{\prime \prime }W`$, then for any index $`j`$, $`x_j^{}x_j^{\prime \prime }`$ or $`x_j^{}=x_j^{\prime \prime }=0`$. (Otherwise, $`W_\mathrm{}jV_i\mathrm{}`$ is a nontrivial subspace of $`W`$. It is invariant because $`V_i`$ and $`V_{ij}`$ are invariant. Contradiction with the irreducibility of $`W`$.)

Let $`j`$ be the smallest index for which there is an $`x^{}W`$ with $`x_j^{}0`$. Then, for every $`xV_{ij}`$, there is an $`x^{}W`$ with $`x_j^{}=x`$. (For, if $`A`$ and $`B`$ are invariant subspaces of a unitary representation, the projection of $`A`$ onto $`B`$ is invariant. Apply this with $`A=W`$ and $`B=V_{ij}`$, then use the irreducibility of $`V_{ij}`$.)

The above considerations allow us to define the mapping $`h_{jj^{}}:V_{ij}V_{ij^{}}`$ by $`h_{jj^{}}(x_j^{})=x_j^{}^{}`$. By the definition, $`h_{jj^{}}(g(x_j^{}))=h_{jj^{}}((g(x^{}))_j)=(g(x^{}))_j^{}=g(x_j^{}^{})=g(h_{jj^{}}(x_j^{})`$, so $`h_{jj^{}}`$ is a $`G`$-isomorphism. By Schur’s lemma, this implies that $`h_{jj^{}}=a_j^{}h_{ijj^{}}`$ for some $`a_j^{}\text{ }\mathrm{C}`$.   $`\mathrm{}`$

In general, if $`W`$ is any irreducible invariant subspace of $`^{2^n}`$, then $`W`$ must be in the form described by claim 4 for some $`i`$. ($`W`$ belongs to some equivalence class $`E_i`$ and therefore is contained in the corresponding $`V_i`$.)

For each $`V_{i1}`$ ($`i\{1,\mathrm{},k\}`$), we fix an orthonormal basis $`v_{i1},\mathrm{},v_{it}`$. This also fixes a related basis $`h_{i1j}(v_{i1})`$, $`\mathrm{}`$, $`h_{i1j}(v_{it})`$ for each $`V_{ij}`$. Moreover, we also get a similar basis

$$\underset{\mathrm{}=j}{\overset{j_i}{}}a_{\mathrm{}}h_{i1\mathrm{}}(v_{i1}),\mathrm{},\underset{\mathrm{}=j}{\overset{j_i}{}}a_{\mathrm{}}h_{i1\mathrm{}}(v_{it})$$

for every invariant irreducible $`WV_i`$ because any such $`W`$ can be written in the form given by claim 4. We call these bases designated.

This designated basis is exactly the basis for $`W`$ that can be obtained by applying the isomorphism between $`V_{i1}`$ and $`W`$ to the basis for $`V_{i1}`$. Moreover, if $`W,W^{}`$ are two isomorphic irreducible subspaces, the designated basis for $`W`$ is mapped to the designated basis for $`W^{}`$ by the isomorphism between $`W`$ and $`W^{}`$.

We are going to impose the following condition on $`f_\pi ^{}`$:

Condition. Let $`W`$ be an irreducible representation of $`G`$ and $`w_1,\mathrm{},w_l`$ be the designated basis of $`W`$. Let $`w_1^{},\mathrm{},w_l^{}`$ be the designated basis of $`f_\pi ^{}(W)`$. Then, there exists $`c`$, $`|c|=1`$ such that $`f_\pi ^{}(w_1)=cw_1^{}`$, $`\mathrm{}`$, $`f_\pi ^{}(w_l)=cw_l^{}`$.

Next, we show that this condition suffices to guarantee $`f_\pi ^{}f_\sigma ^{}=c_{\pi ,\sigma ,i}f_{\pi \sigma }^{}`$ on every $`V_i`$ and that any $`f_\pi `$ that permutes $`X\widehat{𝒳}`$ without satisfying this condition can be transformed into $`f_\pi ^{}`$ that satisfies the condition and still permutes the subspaces in the same way.

First, we show that it is enough to ensure that the designated basis of $`V_{i1}`$ is mapped correctly for every $`i\{1,\mathrm{},k\}`$.

###### Claim 5

Assume that the condition is true for $`W=V_{i1}`$. Then, it is also true for any irreducible $`WV_i`$.

Proof: Let $`h`$ be the isomorphism between $`V_{i1}`$, $`W`$. Note that $`h`$ maps the designated basis of $`V_{i1}`$ to the designated basis of $`W`$.

Then (by claim 2) $`f_\pi ^{}h(f_\pi ^{})^1`$ is an isomorphism between $`f_\pi ^{}(V_{i1})`$ and $`f_\pi ^{}(W)`$. We know that there is an isomorphism between these two irreducibles that maps the designated basis of one of them to the designated basis of the other. By Schur’s lemma, any two isomorphisms of irreducible subspaces can differ only by a multiplicative constant $`c`$. The unitarity of $`f_\pi ^{}h(f_\pi ^{})^1`$ implies that $`|c|=1`$.

Therefore, $`f_\pi ^{}h(f_\pi ^{})^1`$ maps the designated basis of $`f_\pi ^{}(V_{i1})`$ to $`c`$ times the designated basis of $`f_\pi ^{}h(f_\pi ^{})^1(f_\pi ^{}(V_{i1}))=f_\pi ^{}h(V_{i1})=f_\pi ^{}(W)`$. We know that $`(f_\pi ^{})^1`$ maps the designated basis of $`f_\pi ^{}(V_{i1})`$ to the designated basis of $`V_{i1}`$ and that $`h`$ maps the designated basis of $`V_{i1}`$ to the designated basis of $`W`$. This implies that $`f_\pi ^{}`$ maps the designated basis of $`W`$ to $`c`$ times the designated basis of $`f_\pi ^{}(W)`$.   $`\mathrm{}`$

Next, we show how to transform $`f_\pi `$ into $`f_\pi ^{}`$ that performs the same permutation $`\pi `$ of $`\widehat{𝒳}`$ and maps the designated basis of every $`V_{i1}`$ as required.

Let $`W_1`$, $`\mathrm{}`$, $`W_k`$ be $`f_\pi (V_{11})`$, $`\mathrm{}`$, $`f_\pi (V_{k1})`$. Each of $`W_i`$ lies within one of $`V_1,\mathrm{},V_k`$. Denote this subspace $`V_i^{}`$. Then, for $`ij`$, $`V_i^{}V_j^{}`$. For each $`i\{1,\mathrm{},k\}`$, we define a unitary transformation $`g_{\pi ,i}`$ on $`V_i`$ such that $`g_{\pi ,i^{}}f_\pi `$ maps the designated basis of $`V_{i1}`$ to the designated basis of $`f_\pi (V_{i1})`$.

By Claim 4, the irreducible subspace $`W_i=f_\pi (V_{i1})`$ is just

$$\{a_{i^{}j}x+a_{i^{}(j+1)}h_{i^{}j(j+1)}(x)+\mathrm{}+a_{i^{}j_i^{}}h_{i^{}jj_i^{}}(x)|xV_{i^{}j}\}$$

for some $`j`$. Moreover, the mapping that maps each $`vW_i`$ to its $`V_{i^{}j}`$-component is an isomorphism of $`W_i`$ and $`V_{i^{}j}`$ w.r.t. $`G`$ (similarly to proof of Claim 4).

Let $`v_1,\mathrm{},v_l`$ be the designated basis of $`V_{i1}`$, $`v_1^{},\mathrm{},v_l^{}`$ be $`f_\pi (v_1),\mathrm{},f_\pi (v_l)`$ and $`v_1^{\prime \prime }`$, $`\mathrm{}`$, $`v_l^{\prime \prime }`$ be the $`V_{i^{}j}`$ components of $`v_1^{}`$, $`\mathrm{}`$, $`v_l^{}`$.

Let $`w_1`$, $`\mathrm{}`$, $`w_l`$ be the designated basis of $`V_{i^{}j}`$ and $`g_{\pi ,i^{}j}`$ be the unitary transformation on $`V_{i^{}j}`$ that maps $`v_1^{\prime \prime },\mathrm{},v_l^{\prime \prime }`$ to $`w_1`$, $`\mathrm{}`$, $`w_l`$. We define a unitary transformation $`g_{\pi ,i^{}j^{}}`$ (for every $`j^{}j`$) on $`V_{i^{}j^{}}`$ to be $`h_{i^{}jj^{}\mathrm{`}}g_{\pi ,i^{}j}h_{i^{}jj^{}}^1`$. Finally, we take the transformation $`g_{\pi ,i^{}}`$ of $`V_i^{}`$ that is equal to $`g_{\pi ,i^{}j}`$ on each $`V_{i^{}j}`$. Then, $`g_{\pi ,i^{}}`$ maps

$$v_1^{}=a_{i^{}j}v_1^{\prime \prime }+a_{i^{}(j+1)}h_{i^{}j(j+1)}(v_1^{\prime \prime })+\mathrm{}+a_{i^{}j_i^{}}h_{i^{}jj_i^{}}(v_1^{\prime \prime })$$

to

$$a_{i^{}j}g_{\pi ,i^{}j}(v_1^{\prime \prime })+a_{i^{}(j+1)}g_{\pi ,i^{}(j+1)}h_{i^{}j(j+1)}(v_1^{\prime \prime })+\mathrm{}=$$

$$a_{i^{}j}g_{\pi ,i^{}j}(v_1^{\prime \prime })+a_{i^{}(j+1)}h_{i^{}j(j+1)}g_{\pi ,i^{}j}(v_1^{\prime \prime })+\mathrm{}$$

$$=a_{i^{}j}w_1+a_{i^{}(j+1)}h_{i^{}j(j+1)}(w_1)+\mathrm{}$$

which is exactly the first vector of the designated basis for $`W_i`$. The same is true for $`v_2^{}`$, $`\mathrm{}`$, $`v_l^{}`$, implying that $`g_{\pi ,i^{}}f_\pi `$ maps the designated basis of $`V_{i1}`$ to the designated basis of $`W_i`$.

Now, we take $`g_\pi `$ that is equal to $`g_{\pi ,i}`$ on each $`V_i`$ and take $`f_\pi ^{}=g_\pi f_\pi `$.

###### Claim 6

$`g_\pi `$ preserves all $`X\widehat{𝒳}`$.

Proof: By definition, the restriction $`g_\pi |_{V_i}`$ is equal to $`g_{\pi ,i}`$, and $`g_{\pi ,i}`$ clearly preserves $`V_{i1},\mathrm{},V_{ij_i}`$. Moreover, $`g_{\pi ,i}`$ (and, hence, $`g_\pi `$) preserves any irreducible subspace $`WV_i`$ because any such subspace is in the form of claim 4.

Every $`X\widehat{𝒳}`$ is invariant under $`G`$. Therefore, it decomposes into a direct sum of irreducible subspaces. Each of these subspaces is in one of the classes $`E_1`$, $`\mathrm{}`$, $`E_k`$ and, therefore, lies in one of $`V_1`$, $`\mathrm{}`$, $`V_k`$. This means that it is preserved by $`g_\pi `$. Therefore, $`X`$ which is a direct sum of such irreducible subspaces is preserved by $`g_\pi `$ as well.   $`\mathrm{}`$

Hence, $`f_\pi ^{}=g_\pi f_\pi `$ realizes the same permutation $`\pi `$ of $`X\widehat{𝒳}`$ as $`f_\pi `$.

###### Claim 7

On every $`V_i`$, $`f_\pi ^{}f_\sigma ^{}=c_{\pi ,\sigma ,i}f_{\pi \sigma }^{}`$ for some $`c_{\pi ,\sigma ,i}`$.

Proof: This is equivalent to showing that $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}`$ is equal to $`c_{\pi ,\sigma ,i}`$ times the identity. To show that, notice that $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}`$ maps every subspace $`X\widehat{𝒳}`$ to itself because $`(f_{\pi \sigma }^{})^1`$ performs the inverse of the permutation $`\pi \sigma `$ on $`\widehat{𝒳}`$. Therefore, $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}G`$. This means that $`V_{ij}`$ are all preserved by $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}`$.

Moreover, $`f_\sigma ^{}`$, $`f_\pi ^{}`$ and $`f_{\pi \sigma }^1`$ all map the designated bases to $`c`$-times designated bases (Claim 5). Therefore, $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}`$ maps the designated basis of $`V_{ij}`$ to $`c`$ times the designated basis of $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}(V_{ij})=V_{ij}`$.

It remains to show that $`c`$ is the same for all irreducible subspaces $`V_{ij}`$ contained in $`V_i`$. Let $`c_j`$ and $`c_j^{}`$ be the values of $`c`$ for $`V_{ij}`$ and $`V_{ij^{}}`$. Consider the subspace

$$W=\{x+h_{ijj^{}}(x)|xV_{ij}\}.$$

By Claim 4, this is an irreducible invariant subspace. Now, $`(f_{\pi \sigma }^{})^1f_\pi ^{}f_\sigma ^{}`$ maps it to

$$W^{}=\{c_jx+c_j^{}h_{ijj^{}}(x)|xV_{ij}\}=$$

$$\{x+\frac{c_j}{c_j^{}}h_{ijj^{}}(x)|xV_{ij}\}.$$

The invariance of $`W`$ means that $`W^{}=W`$ and $`c_j=c_j^{}`$.

Therefore, $`c_j`$ are all equal. This means that $`(f_{\pi \sigma }^{})^1(x)=c_jx`$ for all $`xV_i`$ because the designated bases of $`V_{ij}`$ together form a basis for entire subspace $`V_i`$.

Unfortunately, arguments of this type (composing $`f_\pi `$ with an appropriate transformation that fixes all $`U_i`$) cannot be used to eliminate phases $`c_{\pi ,\sigma ,i}`$.

The reason for this is that there exist so-called projective representations. A projective representation is a set of maps $`f_\pi `$ such that $`f_\pi f_\sigma =c_{\pi ,\sigma }f_{\pi \sigma }`$, $`c_{\pi ,\sigma }\text{ }\mathrm{C}`$. It is known that the symmetric group has projective representations which are not equivalent to any of the usual representations.

One possible solution would be to use the standard forms of projective representations which are quite well studied. However, to be able to use them, we would need to show that the multiplicative constants $`c_{\pi ,\sigma ,i}`$ are the same for all $`V_i`$ (or show that we can split all $`V_i`$ in several groups so that $`c_{\pi ,\sigma ,i}`$ is the same within one group) and we do not know if this is possible.

Our solution is to replace $`f_\pi ^{}`$ by transformations $`f_\pi ^{\prime \prime }`$ on a larger space $`V_1V_1^{}+\mathrm{}V_kV_k^{}`$ so that $`f_\pi ^{\prime \prime }f_\sigma ^{\prime \prime }=f_{\pi \sigma }^{\prime \prime }`$. Then, $`f_\pi ^{\prime \prime }`$ form a representation in the usual sense and we can analyse them similarly to section 4.

### 5.3 Solving the problem with phases

We split $`V_1,\mathrm{},V_k`$ into equivalence classes $`𝒱_1,\mathrm{}𝒱_l`$. $`V_i`$ and $`V_j`$ are in one class if there is a $`\pi S_M`$ such that $`f_\pi (V_i)=V_j`$. Let $`W_i`$ be the union of all $`V_j`$ that belong to $`𝒱_i`$. Then, $`f_\pi (W_i)=W_i`$ for any $`\pi S_M`$ (because $`f_\pi `$ maps every $`V_j𝒱_i`$ to some $`V_j^{}𝒱_i`$). Therefore, we can look at each $`W_i`$ separately.

###### Lemma 7

Let $`X,Y\widehat{𝒳}`$. Then, for any $`t`$,

$$dimXW_tdimXYW_t\sqrt{\frac{4cn}{M}}dimW_t.$$

Proof: To simplify the notation, assume that $`W_t=V_1V_2\mathrm{}V_l`$.

Consider the linear space $`W_t^{}=V_1V_1^{}\mathrm{}V_lV_l^{}`$ and the linear transformations $`f_\pi ^{\prime \prime }=f_\pi ^{}f_\pi `$. These linear transformations form a representation because

$$f_{\pi \sigma }^{}(f_{\pi \sigma }^{})^{}=c_{\pi ,\sigma ,i}f_\pi ^{}f_\sigma ^{}c_{\pi ,\sigma ,i}^{}(f_\pi ^{})^{}(f_\sigma ^{})^{}=$$

$$f_\pi ^{}f_\sigma ^{}(f_\pi ^{})^{}(f_\sigma ^{})^{}=f_\pi ^{\prime \prime }f_\sigma ^{\prime \prime }$$

on every $`V_iV_i^{}`$.

Let

$$X^{}=_{i=1}^l(XV_i)(XV_i)^{}$$

be the subspace of $`W_t^{}`$ corresponding to $`X`$. Then, $`f_\pi ^{}(X)=Y`$ implies $`f_\pi ^{\prime \prime }(X^{})=Y^{}`$. (To see this, consider one of $`(XV_i)(XV_i)^{}`$. Assume that $`f_\pi ^{}`$ maps $`V_i`$ to $`V_i^{}`$. Then, $`f_\pi ^{}(X)=Y`$ implies $`f_\pi ^{}(XV_i)=YV_i^{}`$ and

$$f_\pi ^{\prime \prime }((XV_i)(XV_i)^{})=(YV_i^{})(YV_i^{})^{}.$$

Combining these equalities for all $`V_i`$ gives $`f_\pi ^{\prime \prime }(X^{})=Y^{}`$.)

In particular, $`f_\pi ^{\prime \prime }(X^{})=Y^{}`$ means that $`X^{}`$ is invariant under all $`\pi S_M`$ satisfying $`\pi (X)=X`$. Therefore, by Lemma 6,

$$dimX^{}dimX^{}Y^{}\frac{4cn}{M}dimW_t^{}.$$
(1)
We use this inequality to derive a bound on $`dimXW_tdimXYW_t`$. To do this, we relate the dimensions of $`XV_i`$ and $`X^{}(V_iV_i^{})`$. First, notice that we have

$$XW_t=_{i=1}^l(XV_i)$$
(2)
because $`X`$ is invariant under $`G`$ and, therefore, can be written as a sum of irreducible invariant subspaces (and each of these irreducibles is contained in some $`V_i`$). The same is true about $`Y`$ and $`XY`$:

$$XYW_t=_{i=1}^l(XYV_i)$$
(3)
Let $`d_i`$ and $`d_i^{}`$ be the dimensions of $`XV_i`$ and $`XYV_i`$. Then, (2) and (3) imply that $`dimXW_t=_{i=1}^ld_i`$, $`dimXYW_t=_{i=1}^ld_i^{}`$ and

$$dimXW_tdimXYW_t=\underset{i=1}{\overset{l}{}}(d_id_i^{}).$$

If we look at $`V_iV_i^{}`$, then

$$X^{}(V_iV_i^{})=(XV_i)(XV_i)^{}.$$

This implies $`dimX^{}(V_iV_i^{})=d_i^2`$ and $`dimX^{}=_id_i^2`$. Similarly, $`dimX^{}Y^{}=_{i=1}^ld_{i}^{}{}_{}{}^{2}`$.

Let $`d`$ be the dimension of $`V_1`$. Then, the dimensions of $`V_2`$, $`\mathrm{}`$, $`V_l`$ are $`d`$ as well because, for every $`i\{2,\mathrm{},l\}`$, there is a unitary $`f_\pi `$ such that $`f_\pi (V_1)=V_i`$. Therefore, $`dimW_1=ld`$. Also, $`dimW_t^{}=ld^2`$ because $`dimV_iV_i^{}=d^2`$ for every $`i\{1,\mathrm{},l\}`$. Hence, we have

$$\frac{dimXW_tdimXYW_t}{dimW_t}=\frac{_{i=1}^m(d_id_i)}{md}=$$

$$\frac{1}{m}\underset{i=1}{\overset{m}{}}\sqrt{\frac{(d_id_i^{})^2}{d^2}}\frac{1}{m}\underset{i=1}{\overset{m}{}}\sqrt{\frac{(d_id_i^{})(d_i+d_i^{})}{d^2}}=$$

$$\frac{1}{m}\underset{i=1}{\overset{m}{}}\sqrt{\frac{(d_i^2d_i^{}_{}{}^{}2)}{d^2}}.$$

Convexity of the square root implies that this is at most

$$\sqrt{\frac{_{i=1}^m(d_i^2d_i^{}_{}{}^{}2)}{md^2}}=\sqrt{\frac{dimX^{}dimX^{}Y^{}}{dimW_t^{}}}.$$

Equation 1 implies that this is at most $`\sqrt{(4cn)/M}`$. This completes the proof of lemma.   $`\mathrm{}`$

With Lemma 7, we can finish the proof similarly to the simple case (section 4). By summing over $`W_t`$’s, we get

$$dimXdimXY\sqrt{\frac{2cn}{M}}\underset{t}{}dimW_t=\sqrt{\frac{2cn}{M}}2^n.$$

Therefore,

$$\frac{dimXY}{dimX}\frac{2^{nk}\sqrt{\frac{2cn}{M}}2^n}{2^{nk}}=1\frac{2^{k+1}\sqrt{cn}}{\sqrt{M}}.$$

If $`\frac{2^{k+1}\sqrt{cn}}{\sqrt{M}}\frac{1}{\text{poly}(m)}`$, then $`m=(2k+\mathrm{log}n)(1+o(1))`$. This completes the proof of Theorem 2.   $`\mathrm{}`$

## 6 Representation theory

A representation $`\rho `$ of a group $`G`$ is a homomorphism $`\rho `$ from $`G`$ to the group of linear transformations $`GL(V)`$ of a vector space $`V`$. This means that, for any $`g,hG`$, $`\rho (gh)=\rho (g)\rho (h)`$. If the mapping $`\rho `$ is clear from the context, we often call the space $`V`$ itself representation of $`G`$.

We say that a subspace $`W`$ is an *invariant* subspace of a representation $`\rho `$ if $`\rho (g)WW`$ for all $`gG`$. In order for $`W`$ to be an invariant subspace for $`\rho `$, it must be simultanously fixed under all $`\rho (g)`$. The zero subspace and the subspace $`V`$ are always invariant. If no nonzero proper subspaces are invariant, the representation is said to be *irreducible*.

Two representations $`\rho :GGL(V)`$ and $`\rho ^{}:GGL(W)`$ are isomorphic if there is a bijective linear map $`\phi :VW`$ such that $`\phi \rho (g)=\rho ^{}(g)\phi `$ for any $`gG`$.

If $`\rho `$ and $`\rho ^{}`$ are two irreducible representations and $`\phi `$ is an isomorphism between them, then any other isomorphism $`\phi ^{}`$ between $`\rho `$ and $`\rho ^{}`$ is $`c\phi `$ for some constant $`c\text{ }\mathrm{C}`$.

Schur’s lemma is usually stated for finite groups. However, if the representation is unitary (as in this paper), it is also true for infinite groups.

When a representation *does* have a nonzero proper invariant subspace $`V_1V`$, it is always possible to find a complementary subspace $`V_2`$ (so that $`V=V_1V_2`$) which is also invariant. Since $`\rho (g)`$ fixes $`V_1`$, we may let $`\rho _1(g)`$ be the linear map on $`V_1`$ given by $`\rho (g)`$. It is not hard to see that $`\rho _1:GGL(V_1)`$ is in fact a representation. Similarly define $`\rho _2(g)`$ to be $`\rho (g)`$ restricted to $`V_2`$. Since $`V=V_1V_2`$, the linear map $`\rho (g)`$ is completely determined by $`\rho _1(g)`$ and $`\rho _2(g)`$, and in this case we write $`\rho =\rho _1\rho _2`$.

Repeating the process described above, a representation $`\rho `$ may be written $`\rho =\rho _1\rho _2\mathrm{}\rho _k`$, where each $`\rho _i`$ is irreducible.

In this paper, we use representations of the symmetric group $`S_M`$. The irreducible representations of $`S_M`$ may be placed into one-to-one correspondence with the partitions of $`n`$. A *partition* of $`M`$ is a sequence $`(\lambda _1,\mathrm{},\lambda _k)`$ of positive integers, with $`\lambda _1\mathrm{}\lambda _k`$ for which $`\lambda _i=M`$. It is customary to identify the partition $`\lambda =(\lambda _1,\mathrm{},\lambda _k)`$ with a diagram consisting of $`k`$ rows of boxes, the $`i`$th row containing $`\lambda _i`$ boxes. We will let $`\lambda `$ stand for both the partition and the associated diagram. For example, the diagram corresponding to the partition $`\lambda =(4,4,2,1)`$ is shown in figure 1.

The irreducible representation associated with $`\lambda `$ is denoted $`\rho _\lambda `$. There is an explicit formula for the dimension of $`\rho _\lambda `$. This involves the notion of a *hook*: for a cell $`(i,j)`$ of a Young tableau $`\lambda `$, the $`(i,j)`$-hook $`h_{i,j}`$ is the collection of all cells of $`\lambda `$ which are beneath $`(i,j)`$ (but in the same column) or to the right of $`(i,j)`$ (but in the same row), including the cell $`(i,j)`$. The *length* of the hook $`\mathrm{}(h)`$ is the number of cells appearing in the hook. With this notation, the dimension of $`\rho _\lambda `$ may be expressed:

$$dim\rho _\lambda =\frac{n!}{_{i,j}\mathrm{}(h_{i,j})},$$
(4)
this product being taken over all hooks $`h`$ of $`\lambda `$. Figure 2 shows the hook lengths for the partition $`\lambda =(4,4,3,1)`$. Formula (4) implies that the dimension of corresponding representation is

$$\frac{11!}{75326423}=1320.$$

A representation $`\rho `$ of a group $`G`$ is also automatically a representation of any subgroup $`H`$. Note that even if a representation is irreducible over $`G`$, it may no longer be irreducible when restricted to $`H`$.

In particular, we will be considering the restrictions of irreducible representations of $`S_M`$ to $`S_{M1}`$. Let $`\lambda `$ be a partition of $`M`$ and $`\rho _\lambda `$ be the corresponding irreducible representation. Then, when we restrict to $`S_{M1}`$, $`\rho _\lambda `$ decomposes into irreducible representations of $`S_{M1}`$ in the following way:

$$\rho =\underset{\lambda ^{}}{}\rho _\lambda ^{}$$

where $`\lambda ^{}`$ ranges over all shapes of size $`M1`$ that can be obtained by deleting an “inside corner” from $`\lambda `$. (An inside corner is simply a point of the shape whose deletion leaves a legal shape.)

For example, the representation $`\rho _\lambda `$, $`\lambda =(4,4,2,1)`$ of $`S_{11}`$ decomposes into 3 irreducible representations of $`S_{10}`$. The Young diagrams of these representations are shown in Fig. 3.