format: text

text:
# Obstacles to the Collisional Growth of Planetesimals

## 1. Introduction

Solid planets and gas giant cores form in a hierarchical growth process spanning some 13 orders of magnitude in radius from interstellar dust grains to spectacular giant impacts. An important demarcation occurs at kilometer sizes, where coupling to the gas disk is weak and substantial escape speeds of $`1`$ m/s allow growth by inelastic binary collisions. Two theories aim to explain the origin of planetesimals from smaller solids with negligible surface gravity and strong gas couplings. This paper examines what we will call the Collisional-Chemical Sticking Hypothesis (hereafter CCSH), that km-sized bodies arise from a long chain of agglomerative growth, due to chemical forces during inelastic collisions. The gravitational instability (hereafter GI) hypothesis appeals the collective self-gravity of a dense midplane layer to collect small solids into larger planetesimals (Goldreich & Ward 1973, Youdin & Shu 2002, hereafter YS). The characteristic wavelength of GI predicts planetesimal sizes $`>`$ few km for disks with enough mass to produce a solar system like our own. Leapfrogging intermediate sizes by direct assembly from $`<`$ cm solids avoids most problems associated with sticking and rapid radial drift (see §2.1.).

The main obstacle to GI is that turbulence opposes the settling required to create a dense midplane layer. Even an otherwise laminar disk generates midplane turbulence, since particle settling introduces destabilizing vertical shear (Weidenschilling & Cuzzi 1993, hereafter WC). Sekiya (1998) overcame this obstacle by appealing to the enhanced buoyancy of stratified, high metallicity disks. YS showed that turbulent motions can only suspend a finite surface density of solids, $`\mathrm{\Sigma }_{\mathrm{p},\mathrm{crit}}`$. GI occurs in a dense midplane layer when the actual $`\mathrm{\Sigma }_\mathrm{p}`$ exceeds this saturation threshold. However the required surface density ratio of solids to gas, $`\mathrm{\Sigma }_{\mathrm{p},\mathrm{crit}}/\mathrm{\Sigma }_\mathrm{g}`$, i.e. the disk metallicity, is about an order of magnitude over solar abundances. Various enrichment mechanisms were described in YS. A particularly robust finding is that aerodynamic radial drift has the global consequence of enhancing $`\mathrm{\Sigma }_\mathrm{p}`$ as the particle disk shrinks in radius. Youdin & Chiang (2003) explored these “particle pileups” in detail, including inertial effects and self-consistently generated turbulent stresses in the particle layer.

Since GI can overcome the heretofore fundamental obstacle of vertical shear, we assess the problems facing the CCSH. YS argue against the plausibility of the CCSH with evidence based on micro-gravity experiments, the size distribution of meteoritic inclusions, the limited sticking ability of icy planetary ring debris, and “intuition.” Our goal here is to physically explain the “intuitive” notion that collisions between macroscopic solids with weak surface gravity, at speeds characteristic of freeway driving, are not cohesive.

The most fundamental obstacle to sticking is energetic: the *entire* relative kinetic energy of two bodies at large distances, $`K_{\mathrm{}}=mv_{\mathrm{}}^2/2`$, must be dissipated, where $`m`$ is the reduced mass and $`v_{\mathrm{}}`$ is the relative speed at large distances. This requires some combination of (a) efficient energy loss, and (b) binding energies, $`U_{\mathrm{bind}}<0`$, which increase kinetic energy on impact: $`K_{\mathrm{imp}}=K_{\mathrm{}}+|U_{\mathrm{bind}}|`$. The dissipative efficiency needed for sticking, $`K_{\mathrm{}}/K_{\mathrm{imp}}=1/(1+\theta )`$, drops appreciably below unity when the focusing factor $`\theta |U_{\mathrm{bind}}|/K_{\mathrm{}}>1`$. Gravitational focusing, which scales as $`\theta R^2/v_{\mathrm{}}^2`$, affects bodies with sufficiently large radius, $`R`$. For small bodies, surface energies, such as van der Waals interactions, give $`\theta R^w/v^2`$, where the size falloff ranges from $`w=1`$, for a maximal contact area $`R^2`$, to $`w=5/3`$, for elastic compression (see §3.1.). Over a large size range, extending from mm — 10 m, no relevant binding energy exists. Until an incredibly efficient, yet non-destructive, dissipation mechanism is identified, the CCSH will lack a solid physical foundation.

This proceeding is organized as follows: §2. investigates collisional speeds expected from laminar flow (§2.1.) and turbulent fluctuations (§2.2.). Section 3. explores collisional binding mechanisms including elastic (§3.1.) and plastic (§3.2.) deformation as well as restructuring within “rubble piles” and the role of organic matter (§3.3.). Section 4. contains concluding remarks.

## 2. Collision Speeds

Before planetesimals form, gravitational scattering is negligible. Particle random velocities arise from frictional coupling to the gas, including kicks from turbulent fluctuations, drift induced by the gas disk’s sub-Keplerian rotation, and vertical settling, which becomes small near the midplane as vertical gravity vanishes.

### 2.1. Laminar Drift

Aerodynamic gas drag gives particles radial, $`v_r`$, and azimuthal, $`v_\varphi `$, deviations from Keplerian circular speeds, $`v_K=\mathrm{\Omega }r`$ (Nakagawa, Sekiya, & Hayashi 1986):

$`v_r`$ $`=`$ $`{\displaystyle \frac{2\tau _{\mathrm{stop}}\eta v_K}{(\rho /\rho _g)^2+\tau _{\mathrm{stop}}^2}},`$ (1)
$`v_\varphi `$ $`=`$ $`{\displaystyle \frac{\eta v_K}{\rho /\rho _\mathrm{g}+\rho _\mathrm{g}\tau _{\mathrm{stop}}^2/\rho }},`$ (2)
where $`r`$ is the disk radius, $`\mathrm{\Omega }`$ the Keplerian frequency, $`\eta P/r/(2\rho _\mathrm{g}\mathrm{\Omega }^2r)`$ measures centrifugal pressure ($`P`$) support; $`\rho \rho _\mathrm{p}+\rho _\mathrm{g}`$ is the spatial mass density of solid particles, $`\rho _\mathrm{p}`$, plus gas, $`\rho _\mathrm{g}`$; and $`\tau _{\mathrm{stop}}\mathrm{\Omega }t_{\mathrm{stop}}`$ measures the coupling of solids to gas, with $`\tau _{\mathrm{stop}}1`$ ($`1`$) implying strong (weak) coupling. The stopping time, $`t_{\mathrm{stop}}`$, depends on the drag law (e.g. Epstein or Stokes) that applies for given particle sizes and gas properties (Weidenschilling 1977).

The velocity scale, $`\eta v_K54\mathrm{m}/\mathrm{s}`$, is independent of $`r`$ in the minimum solar nebula model (see YS), hereafter MSN. Different temperature profiles, $`Tr^q`$, give $`\eta v_Kr^{1/2q}`$. Our discussion ignores the inertial scaling factor $`\rho _\mathrm{g}/\rho <1`$, which is $`𝒪(1)`$ unless $`\rho _\mathrm{p}>\rho _\mathrm{g}`$, in which case GI should develop (YS). Particles with $`\tau _{\mathrm{stop}}1`$ experience the fastest radial drift, $`v_{r,\mathrm{max}}\eta v_K`$. These marginally coupled particles have a size $`R_{\tau 1}1`$ m, at 1 AU in the MSN, giving the well-known and problematic drift timescale: $`\mathrm{AU}/(\eta v_K)100`$ yr. Elsewhere a meter is less significant. At larger $`r`$, $`\rho _\mathrm{g}`$ decreases giving weaker coupling and smaller $`R_{\tau 1}`$ values. Beyond about $`3`$ AU, $`\tau _{\mathrm{stop}}=1`$ particles lie in the Epstein regime (size less than the gas mean free path) and obey $`R_{\tau 1}=\mathrm{\Sigma }_\mathrm{g}/(\sqrt{2\pi }\rho _\mathrm{s})10\mathrm{cm}(r/10\mathrm{AU})^{3/2}`$. Note that as any particle tries to grow past the local $`R_{\tau 1}`$ value, to slow its radial drift, it continually moves to regions where $`R_{\tau 1}`$ is even larger. This struggle could be more futile, if shorter lived, than Sisyphus’s since all motion is downhill (radially inward).

Figure 1 (generalized from figure 3 of WC) plots the relative velocity, arising from $`v_r`$ and $`v_\varphi `$ drift, between particles with a range of stopping times, and thus sizes. Only similarly sized particles avoid $`𝒪(\eta v_K)`$ relative motions. Impacts above a threshold speed, $`v_{\mathrm{cr}}`$ will not give coagulation. While $`v_{\mathrm{cr}}`$ uncertain and size dependent, $`v_{\mathrm{cr}}50\mathrm{m}/\mathrm{s}`$ is reasonable (as discussed in §3.). Thus collisional growth requires maintaining a narrow size distribution. This is a difficult proposition since many processes; e.g. collisional cascades, radial migration, and vertical settling, broaden the size dispersion.

### 2.2. Turbulent Fluctuations

Protostellar disks must be at least intermittently turbulent for stars to accrete. This turbulence is often modeled as an anomalous viscosity, $`\nu _\mathrm{T}=\alpha c_\mathrm{g}^2/\mathrm{\Omega }`$, where $`c_\mathrm{g}`$ is the gaseous sound speed and the uncertain viscosity parameter takes values $`10^4<\alpha <10^2`$ to reproduce T Tauri accretion rates. Solids couple to available turbulent eddies, augmenting the particulate velocity dispersion, $`c_\mathrm{p}`$.

Assume a Kolmogorov spectrum whose largest eddies have a turnover time $`t_01/\mathrm{\Omega }`$, and thus a typical speed $`v_0\sqrt{\alpha }c_\mathrm{g}30\sqrt{\alpha _3}(r/\mathrm{AU})^{1/4}`$ m/s, where $`\alpha _3\alpha /10^3`$. Particles with $`t_{\mathrm{stop}}/t_0\tau _{\mathrm{stop}}<1`$ acquire $`c_\mathrm{p}v_0`$ relative *to the gas*. Larger particles, with $`\tau _{\mathrm{stop}}1`$, couple poorly to all eddies, and proceed with $`c_\mathrm{p}v_0`$ on nearly Keplerian orbits. The dispersion of particles relative *to each other* is as large as $`v_0`$ only when one of the particles is marginally coupled, $`\tau _{\mathrm{stop}}1`$ (or when the two particles have $`\tau _{\mathrm{stop},1}1\tau _{\mathrm{stop},2}`$). Pairs of small particles, both with $`\tau _{\mathrm{stop}}1`$, remain so tightly coupled to eddies that they have little motion relative to each other (Markiewicz, Mizuno, & Völk 1991).

Turbulence, unlike laminar drift, imparts relative motion to particles with identical stopping times. These motions are the largest, $`v_0`$, near $`\tau _{\mathrm{stop}}1`$. This closes the narrow “bridge” of low speed collisions in Figure 1 (also see Figure 4 in WC), which we already noted would be difficult to cross by collisional growth. The difficulties facing the CCSH escalate further in a turbulent disk.

Small grains, on the other hand, can coagulate in turbulent disk, especially those with $`t_{\mathrm{stop}}`$ less than the eddy turnover time at the dissipation scale, $`t_\mathrm{D}=t_0/\sqrt{Re_0}`$, where $`Re_0`$ is Reynolds number for the largest eddies. This regime, where the flow is laminar and Brownian motion determines $`c_\mathrm{p}`$, corresponds to sizes,

$$R<(2\pi )^{1/4}\frac{\mathrm{\Omega }t_0}{\rho _\mathrm{s}}\sqrt{\frac{\mathrm{\Sigma }_\mathrm{g}\mu }{\sigma \alpha }}100(r/\mathrm{AU})^{3/4}\alpha _3^{1/2}\mu \mathrm{m},$$
(3)
where $`\sigma `$ is the atomic cross section and $`\mu `$ is the mean molecular weight.

## 3. Contact Mechanics

To evaluate the CCSH, we need to understand the aftermath of collisions at speeds up to $`v_{\mathrm{}}50`$ m/s. Do they result in coagulation (mass gain), fragmentation (mass loss), or restitution (no change in mass)? We consider identical spheres with radius $`R`$ and density $`\rho _\mathrm{s}`$, unless otherwise noted. Collisional outcomes depend on material properties, the most relevant are probably Young’s modulus, $`E`$; the yield strength, $`Y`$; and the binding energy per unit area, $`\gamma `$. Other influential factors include impact parameter, non-sphericity, surface roughness, and viscoelastic creep, and are considered only briefly.

At low impact speeds, materials deform elastically, i.e. reversibly. In this regime, the ratio of applied stress (force per unit area) to induced strain (relative compression) remains constant at $`E`$. When imposed stresses exceed $`Y`$, deformation becomes plastic, or permanent, resulting for instance in dents. Elastic and plastic deformation during impacts generates a contact area, $`A<\pi R^2`$. Chemical forces, mainly van der Waals interactions, generate a surface binding energy, $`U_{\mathrm{bind}}=\gamma A`$, where $`\gamma `$ varies from $`30`$$`300`$$`3000`$ ergs/cm2 for quartz, ice, and iron grains, respectively.

We argued in §1. that sticking is problematic (requires very efficient energy dissipation) for $`\theta <1`$. Assuming a maximal contact area, $`A\pi R^2`$, the upper limit on $`\theta `$ due to surface forces is:

$$\theta _{\mathrm{max}}=\frac{\gamma \pi R^2}{K_{\mathrm{}}}10^2\frac{\gamma _{300}}{\rho _{\mathrm{s},3}}\frac{\mathrm{cm}}{R}\left(\frac{v_{\mathrm{rel}}}{\mathrm{m}/\mathrm{s}}\right)^2,$$
(4)
with $`\rho _{\mathrm{s},3}\rho _\mathrm{s}/(3\mathrm{g}\mathrm{cm}^3)`$ and $`\gamma _{300}=\gamma /(300\mathrm{erg}\mathrm{cm}^2)`$. This suggests that coagulation between cm-sized solids at speeds above 10 cm/s is difficult. Moreover, surface roughness reduces effective binding forces by factors $`>3`$ because only crests of asperities come in contact (Johnson 1985).

### 3.1. Elastic Collisions

Elastic sticking is an oxymoron if one defines an elastic collision as having a coefficient of restitution, $`ϵ=1`$. However, kinetic energy is lost during elastic deformation since elastic waves (EWs) absorb kinetic energy ($`K_{\mathrm{imp}}`$) during compression, but do not perfectly return deformation energy during rebound. These wayward EWs, which one can think of as wandering from the impact region, eventually dissipate, though not necessarily during the abrupt collision.

An elastic theory of coagulation was developed by Chokshi, Tielens & Hollenbach 1993 (hereafter CTH) who were mainly interested in the coagulation of small ($``$ mm) grains for which surface binding energies are significant. They calculate a critical approach speed, $`v_{\mathrm{cr}}`$, above which sticking will not occur:

$$v_{\mathrm{cr}}4\frac{\gamma ^{5/6}}{E^{1/3}R^{5/6}\rho _\mathrm{s}^{1/2}}<1\left(\frac{R}{\mathrm{mm}}\right)^{5/6}\frac{\mathrm{cm}}{\mathrm{s}}.$$
(5)
Equation (5) is physically plausible since $`v_{\mathrm{cr}}`$ increases with surface binding energy, $`\gamma `$; decreases with $`R`$, as the surface area-to-volume ratio falls; and decreases with Young’s modulus, $`E`$, since stiffer materials share smaller contact areas and place less energy into elastic waves. The threshold speed is quite low. Equation (5) gives numerical values for ice, while speeds for graphite and quartz are lowered by factors of $`6.5`$ and $`30`$, respectively. Thus elastic effects cannot explain growth beyond mm-sizes which have drift speeds $`v_r1(r/\mathrm{AU})^{3/2}\mathrm{cm}/\mathrm{s}`$.

Nevertheless, an order-of-magnitude “derivation” of (5) is instructive. Pressing a flattened area, $`A`$, on a surface with radius of curvature, $`R`$, requires a displacement, $`\delta A/R`$, perpendicular to the surface. Young’s modulus relates stresses, $`F/A`$, imposed by a static force, $`F`$ to the local strain, $`\delta /\sqrt{A}`$, giving $`A(FR/E)^{2/3}`$ and $`\delta [F^2/(RE^2)]^{1/3}`$. We treat compression statically because elastic wave periods are short compared to the collisional duration.

The force that interests us is the surface binding force, which is equal and opposite to the force needed to separate two spheres, $`F_{\mathrm{sep}}=3\pi \gamma R`$ (Johnson, 1985, p. 127). This result, surprisingly independent of $`E`$, follows from the fact that $`U_{\mathrm{bind}}`$ induces a finite contact area between spheres in the absence of external forces. Equating this surface energy, $`\gamma A`$, to the work required to separate the bodies, $`F_{\mathrm{sep}}\delta `$, and recalling $`\delta A/R`$, reproduces $`F_{\mathrm{sep}}\gamma R`$. We can also estimate equilibrium values for $`\delta (\gamma ^2R/E^2)^{1/3}`$, $`A(\gamma R^2/E)^{2/3}`$, and, most importantly, $`U_{\mathrm{bind}}\gamma ^{5/3}R^{4/3}E^{2/3}`$.

Our heuristic argument that sticking needs $`K_{\mathrm{}}<|U_{\mathrm{bind}}|`$ (unless dissipation is very efficient, which should not be the case for elastic deformation) reproduces equation (5) to order unity. CTH achieved their result differently. They estimated the amount of energy lost to EWs, $`U_{\mathrm{lost}}`$, by numerically evolving a spectrum of EWs in response to time-varying collisional stresses. They found that $`U_{\mathrm{lost}}`$ is a fixed fraction of the binding energy, $`U_{\mathrm{lost}}.4|U_{\mathrm{bind}}|`$, and $`K_{\mathrm{}}U_{\mathrm{lost}}`$ gives equation (5).

The best hope for the CCSH probably involves large bodies sweeping up small grains, which dominate the relative kinetic energy and binding area. However, the large relative velocity between unequal bodies, $`\eta v_K54`$ m/s, implies via equation (5) that only extremely small “grains” could stick: 30 — 3 — 0.5 nm for ice, graphite, and quartz grains, respectively. However, impact speeds might be reduced below $`54`$ m/s as the gas flow is deflected around the larger body. Nevertheless, maintaining a reservoir of small sticky grains requires destructive collisions which limit or even reverse the growth of the “runaway” body. So it remains to be shown whether this growth mechanism has the proper sign.

### 3.2. Plastic Deformation

Car crashes show that plastic deformation can dissipate large amounts of kinetic energy in violent collisions. This may not be directly relevant to planetesimal formation. Only sufficiently ductile materials can permanently change shape in response to large stresses, others simply rupture. The former category includes metallic elements and alloys, while the latter includes glass, bone, and crucially, rock. Of course planetesimals must form prior to segregation of an iron-rich core, and evenly dispersed metallic elements probably cannot sustain plastic flow. Would you feel safe driving a car that was $`1/4`$ metal and $`3/4`$ rock?

Even if planet forming material does deform plastically, we should be aware that the regime of stability is rather narrow. Contact pressures only slightly above $`Y`$ give plastic flow that is confined by similarly large elastic stresses to a small region. Somewhat larger stresses, $`3Y`$, give “uncontained” plastic flow that breaks through the surface allowing displaced material to escape (Johnson 1985). During planetesimal formation, uncontained flow can cause mass loss by sub-sonic cratering and, at high enough energies, shattering, though more study of these outcomes is deserved. Since confined plastic flow requires a narrow regime of contact pressures, its relevance to the CCSH, which exposes solids to orders of magnitude variations in impact stresses, is not clear.

Plastic flow develops at an impact velocity, $`v_Y`$, calculable from elastic Hertz theory (which ignores surface binding) by equating $`K_{\mathrm{}}`$ to the elastic deformation energy, $`F𝑑\delta `$. Requiring the maximum stress to be $`Y`$ gives :

$$\rho _\mathrm{s}v_Y^226Y^5/E^4,$$
(6)
or $`10`$ cm/s for medium soft steel. Thus most collisions between metals do indeed involve plastic deformation (Johnson 1985, p. 361).

### 3.3. Aggregate Restructuring and Viscoelastic Organics

So far, we have implicitly assumed that collisions involve uniform, compact materials. What if sticking relies on the detailed structure of impactors? For instance porosity (i.e. “fluffiness”) should enhance dissipation. However open structures are fragile, and moreover would be compacted by repeated impacts. More plausibly, growing solids might be loosely bound “rubble piles,” i.e. an aggregate composed of many smaller units. Restructuring of the sub-units during impacts could be quite dissipative. By analogy, collisions between bean bags (sacks filled with beans or foam pellets) have a lower coefficient of restitution than collisions between individual large beans or pellets. Of course bean bags have a cloth cover that astrophysical rubble piles lack.

Blum (1990) constructs a model along these lines by assigning low values of $`E=2\times 10^4`$ dyn/cm2 and $`Y=100`$ dyn/cm2 to readily deformable aggregates. A serious problem exists with models of this type. Impact velocities, $`v_{\mathrm{coll}}>v_Y10^3`$ cm/s exceed the yield stress, and the sound speed in this material is only $`\sqrt{E/\rho _\mathrm{s}}2`$ m/s. Impacts in the cm/s — 10 m/s range would be highly disruptive events, inducing “uncontained” plastic flow and possibly driving shock waves into the material. Blum ignores these possibilities and extrapolates results (e.g. for $`ϵ`$) from the moderate speed regime, $`\rho _\mathrm{s}v_{\mathrm{coll}}^2/Y<10^3`$, all the way to the hypervelocity regime, $`\rho _\mathrm{s}v_{\mathrm{coll}}^2/Y>10^3`$, where they do not hold (Johnson 1985, p. 366).

These caveats aside, Blum’s model gives a maximum sticking speed $`0.5<v_{\mathrm{cr}}<5`$ m/s for his mm-sized aggregates, depending on impact parameter. The predicted coagulation velocity limit for ices is quite low, $`v_{\mathrm{cr}}3(R/\mathrm{mm})^1\mathrm{mm}/\mathrm{s}`$ (as read from the graph). Amazingly (since the included physics is quite different) this agrees very with equation (5) as evaluated for ice, including the drop of $`v_{\mathrm{cr}}`$ with $`R`$. Blum developed this model to explain experimental results which showed that mm-sized wax coated spheres (with a glass/wax mass ratio of 2 — 5) have a $`20\pm 12\%`$ sticking probability for $`v_{\mathrm{}}1\mathrm{m}/\mathrm{s}`$. It is a mystery how such results (low sticking probabilities, small sizes and moderate speeds) combined with the theoretically expected decrease in $`v_{\mathrm{cr}}`$ with $`R`$ could be interpreted as supportive of the CCSH. The sizable wax fraction invites skepticism, but it justified by the existence of organics in meteorite falls.

Along these lines, Kouchi et al. (2002) collided 5 mm copper spheres into targets with a mm-thick coating of organics, including PAHs and oxygen- and nitrogen-containing materials. They report temperature-dependent sticking at speeds up to $`v_{\mathrm{cr}}5`$ m/s at 250 K. The threshold fell to $`v_{\mathrm{cr}}<2`$ m/s and $`v_{\mathrm{cr}}1`$ m/s at 300 K and 200 K, respectively. Kouchi et al. offer viscoelastic creep, a time-dependent relation between stress and strain, as an explanation for enhanced stickiness. The role of plastic deformation in the copper is unclear. The observed coagulation speeds are probably insufficient to make planetesimals, in particular due to the expected decrease of $`v_{\mathrm{cr}}`$ with size. Furthermore, the experimental conditions are not likely to be repeated in protostellar disks. The targets had mm-thick layers of pure organics, while carbonaceous chondrites (the most carbon rich meteorites) have a bulk carbon content of only $`3.5\%`$.

## 4. Conclusion

We studied the implications of particle velocity dispersions in protoplanetary disks for the collisional growth of planetesimals. Over a wide range of sizes, mm — 10 m, sticking is strongly inhibited. Available binding energies are negligible compared to kinetic energies, and a suitably efficient, yet non-destructive, dissipation mechanism has not been identified. The most elegant solution to this problem is the Goldreich-Ward hypothesis, which uses collective gravity to avoid this problematic coagulation regime.

Particle concentration mechanisms, such as vortex trapping, secular instabilities, and quiescent nodes in turbulent flow (see YS for details) may play a role in planetesimal formation. Higher densities favor gravitational instability, and could also promote collisional growth if collisional speeds are significantly reduced. Regarding the possibility of long-lived particle-trapping vortices, only marginally coupled particles ($`\tau _{\mathrm{stop}}1`$) are efficiently trapped. Smaller particles remain attached to streamlines and larger bodies can plow through the vortex. This limits the overall reduction in relative velocities.

For many years, supporters of the Goldreich-Ward hypothesis were on the defensive due to valid concerns about the stirring provided by turbulence. Proposed solutions to this problem (Sekiya 1998, YS) should reestablish the viability of particulate gravitational instabilities. To make the debate more productive, coagulation proponents should similarly acknowledge, and explain how to overcome, the considerable energetic obstacles to sticking.

#### Acknowledgments.

I am indebted to my (proto)stellar role models: Frank, Chris, and Dave. I thank Jeremy Goodman, Marc Kuchner, Scott Tremaine, and Bruce Draine for fruitful discussions. This work was partly supported by NASA Origins grant NAG5-1164.

## References

Blum, J. 1990, in Formation of the Stars and Planets, and the Evolution of the Solar System, ed. B. Battrick, (Noordwijk: ESTEC), 87

Chokshi, A., Tielens, A. G. G. M., & Hollenbach, D. 1993, ApJ, 407, 806

Goldreich, P., & Ward W. R. 1973, ApJ, 183, 1051

Johnson, K. L. 1985, Contact Mechanics (Cambridge: Cambridge Univ. Press)

Kouchi, A., Kudo, T., Nakano, H., Arakawa, M., Watanabe, N., Sirono, S., Higa, M., & Maeno, N. 2002, ApJ, 566, L121

Markiewicz, W. J., Mizuno, H., & Völk, H. J. 1991, A&A, 242, 286

Nakagawa, Y., Sekiya, M., & Hayashi, C. 1986, Icarus, 67, 375

Sekiya, M., 1998, Icarus, 133, 298

Weidenschilling, S. J. 1977, MNRAS, 180, 57

Weidenschilling, S. J. & Cuzzi, J. N. 1993, in Protostars and Planets III, ed. E. Levy, J. Lunine, & M. Matthews (Tuscon: Univ. Arizona Press), 1031

Youdin, A. N., & Chiang, E. I. 2003, astro-ph/0309247

Youdin, A. N., & Shu, F. H. 2002, ApJ, 580, 494


text:
# Independent Sets in Association Schemes

## 1 Introduction

Let $`𝒫(3^3)`$ be the graph whose vertices are the partitions of $`\{1,\mathrm{},9\}`$ with three cells of size three, where two such partitions are adjacent if each triple in one partition contains one point from each triple of the other. (We will say that two such partitions are skew.) Elementary arguments yield that $`𝒫(3^3)`$ is a regular graph with valency 36 and with 280 vertices.

In , Meagher and Stevens ask whether this graph is a core; this calls for some definitions. If $`X`$ and $`Y`$ are graphs, a map $`f`$ from $`V(X)`$ to $`V(Y)`$ is a homomorphism if, whenever $`u`$ and $`v`$ are adjacent vertices in $`X`$, their images $`f(x)`$ and $`f(y)`$ are adjacent in $`Y`$. An endomorphism of $`X`$ is a homomorphism from $`X`$ to itself. Any automorphism of $`X`$ is an endomorphism and we say that $`X`$ is a core if all endomorphisms of $`X`$ are automorphisms. For background on these topics, see \[7, Chapter 6\].

In this paper we prove that $`𝒫(3^3)`$ is a core. The central part of our argument is a determination of the independent sets of maximal size. The method we use has other applications; we present two of these.

## 2 Association Schemes

An association scheme is a set of regular graphs whose edge sets partition the edges of the complete graph in a particularly nice way. The precise definition is longer, and is stated in terms of the adjacency matrices of the graphs. An association scheme $`𝒜`$ with $`d`$ classes is a set $`A_0,\mathrm{},A_d`$ of $`01`$-matrices such that

1. $`A_0=I`$.
2. $`_{i=0}^dA_i=J`$.
3. $`A_i^T𝒜`$.
4. $`A_iA_j`$ lies in the span of $`𝒜`$ (over $``$).
5. $`A_iA_j=A_jA_i`$

Here $`J`$ denotes the matrix with all entries equal to 1. If the matrices in $`𝒜`$ are all symmetric, we say that the scheme is symmetric. All the schemes in this paper will be symmetric. In this case the matrices $`A_1,\mathrm{},A_d`$ are adjacency matrices of graphs $`X_1,\mathrm{},X_d`$. Since the matrices in $`𝒜`$ commute and since $`J=A_i`$, we see that $`A_iJ=JA_i`$ for all $`i`$, whence the graphs $`X_i`$ must be regular. We denote the number of vertices of these graphs by $`v`$, and the valency of $`X_i`$ by $`v_i`$.

Let $`[𝒜]`$ denote the span of $`𝒜`$ over $``$. This space is closed under matrix multiplication (by (d) above), and is called the Bose-Mesner algebra of the scheme. Since this algebra is closed under transpose and complex conjugation, the matrices in it can be simultaneously diagonalised. More precisely, if the matrices $`A_i`$ are $`v\times v`$, the theory shows that that are subspaces $`U_0,\mathrm{},U_d`$ whose sum is $`^v`$ and such that $`U_j`$ is contained in an eigenspace of $`A_i`$ for all $`i`$ and $`j`$. It is traditional to denote the eigenvalue of $`A_i`$ on $`U_j`$ by $`p_i(j)`$, and to call the matrix $`P`$ such that

$$P_{i,j}=p_j(i).$$

Thus the $`i`$-th column of $`P`$ gives the eigenvalues of $`A_i`$. The dimension of $`U_j`$ is denoted by $`m_j`$. The modified matrix of eigenvalues is obtained by replacing the first column of $`P`$ with the multiplicities $`m_i`$.

Now let $`E_j`$ denote the orthogonal projection onto $`U_j`$. Then the matrices $`E_j`$ form a second basis for $`[𝒜]`$. (The problem is to show that they lie in $`[𝒜]`$.) We have the following useful result due to Seidel. For a proof, see \[6, Thm. 12.6.1\].

###### 2.1 Theorem.

Suppose the matrices $`A_0,\mathrm{},A_d`$ form an association scheme on $`v`$ vertices with projections $`E_0,\mathrm{},E_d`$. Then for any vector $`x`$,

$$\underset{i}{}\frac{x^TA_ix}{vv_i}A_i=\underset{j}{}\frac{x^TE_jx}{m_j}E_j.$$

## 3 Independent Sets

We start by giving a bound on the size of an independent set. For a proof see, for example \[7, Lemma 9.6.2\]. For graphs from association schemes (which is the only case we need), it follows from work of Delsarte . We call this result the ratio bound for $`\alpha (X)`$.

###### 3.1 Theorem.

Let $`X`$ be a regular graph on $`v`$ vertices with valency $`k`$ and least eigenvalue $`\tau `$. Then

$$\alpha (X)\frac{v}{1\frac{k}{\tau }};$$

if equality holds and $`x`$ is the characteristic vector of an independent set of maximum size, then $`x\frac{\alpha (X)}{v}\mathrm{𝟏}`$ is an eigenvector for $`A(X)`$ with eigenvalue $`\tau `$.

We apply this bound to $`𝒫(3^3)`$. Fortunately the eigenvalues of $`𝒫(3^3)`$ have already been determined.

If $`\pi `$ and $`\sigma `$ are two partitions of $`\{1,\mathrm{},9\}`$ with three cells of size three, then their meet $`\pi \sigma `$ has $`3`$, $`9`$, $`7`$, $`6`$ or $`5`$ cells. Thus we can form four graphs $`X_1,\mathrm{},X_4`$ with these partitions as their vertices, where partitions $`\pi `$ and $`\sigma `$ are adjacent in $`X_1`$, $`X_2`$, $`X_3`$ or $`X_4`$ according as the number of cells of $`\pi \sigma `$ is $`9`$, $`7`$, $`6`$ or $`5`$. Mathon and Rosa  show that these four graphs are the graphs of an association scheme with four classes with modified matrix of eigenvalues:

$$\left(\begin{array}{ccccc}1& 36& 162& 54& 27\\ 27& 12& 6& 6& 11\\ 48& 8& 6& 9& 6\\ 120& 2& 6& 6& 3\\ 84& 4& 12& 6& 3\end{array}\right)$$

The second column of this matrix gives the eigenvalues of $`𝒫(3^3)`$. (For information on the eigenvalues of association schemes see, for example, \[1, Chapter 2\].) We see that $`\tau =12`$, and that its multiplicity as an eigenvalue is 27. We conclude that

$$\alpha (𝒫(3^3))\frac{280}{1+\frac{36}{12}}=70.$$

If $`1i<j9`$, there are exactly 70 partitions of $`\{1,\mathrm{},9\}`$ with three cells of size three in which $`i`$ and $`j`$ lie in the same cell. These 70 partitions form an independent set in $`𝒫(3^3)`$, which we denote by $`S_{i,j}`$. We aim to show that any independent set in $`𝒫(3^3)`$ is of the form $`S_{i,j}`$, for some $`i`$ and $`j`$.

## 4 Eigenvectors

Let $`M`$ be the $`280\times 36`$ $`01`$-matrix with rows indexed by the $`3\times 3`$ partitions, columns indexed by the 2-element subsets of $`\{1,\mathrm{},9\}`$, and with the entry corresponding to the partition $`\pi `$ and the 2-element subset $`ij`$ equal to 1 if and only if $`ij`$ is contained in a cell of $`\pi `$. Thus each row of $`M`$ is the characteristic vector of the set of 2-element subsets of $`\{1,\mathrm{},9\}`$ that are contained in a cell of $`\pi `$. It follows that

$$\frac{1}{9}M\mathrm{𝟏}=\mathrm{𝟏}.$$

If $`B`$ is the incidence matrix for $`K_9`$, the complete graph on nine vertices, then

$$MB^T=2J.$$

Since the rows of $`B`$ are linearly independent, this implies that $`\text{rk}(M)28`$. The columns of $`M`$ are the characteristic vectors of the independent sets $`S_{i,j}`$. We will prove that if $`x`$ is the characteristic vector of an independent set of size $`70`$, then $`x`$ lies in the column space of $`M`$.

###### 4.1 Lemma.

The columns of matrix $`M\frac{1}{4}J`$ are eigenvectors for $`A`$ with eigenvalue $`12`$; they span a space with dimension 27.

Proof. The first claim is an immediate consequence of Theorem 3.1. So we need only determine $`\text{rk}(M)`$. Since $`\frac{1}{9}M\mathrm{𝟏}=\mathrm{𝟏}`$, the vector $`\mathrm{𝟏}`$ lies in the column space of $`M`$. Since

$$\mathrm{𝟏}^T\left(M\frac{1}{4}J\right)=0,$$

it will be enough to prove that $`\text{rk}(M)=28`$.

Recall that $`\text{rk}(M)=\text{rk}(M^TM)`$. Let $`L`$ denote the adjacency matrix of the line graph $`L(K_9)`$. We note that

$$|S_{1,2}|=70,|S_{1,2}S_{1,3}|=10,|S_{1,2}S_{3,4}|=20$$

and hence

$$M^TM=70I+10L+20(JIL)=50I+20J10L.$$

The spectrum of $`L`$ is

$$2^{(27)},5^{(8)},14^{(1)}$$

Accordingly $`0`$ is an eigenvalue of $`M^TM`$ with multiplicity eight (the eigenspace is spanned by the eigenvectors of $`L`$ with eigenvalue $`5`$), and therefore

$$\text{rk}(M^TM)=28.$$

Hence $`\text{rk}(M)=28`$.

###### 4.2 Corollary.

If $`x`$ is the characteristic vector of an independent set of size 70 in $`𝒫(3^3)`$, then $`x`$ lies in the column space of $`M`$.

Proof. Set $`z=x\frac{1}{4}\mathrm{𝟏}`$. By the lemma, $`z`$ lies in the column space of $`M`$. Since $`\mathrm{𝟏}`$ also lies in the column space of $`M`$, it follows that $`x`$ does as well.

## 5 Structure of Independent Sets

As noted earlier, the matrix $`A`$ lies in an association scheme with four classes. Suppose that $`A_1`$, $`A_2`$, $`A_3`$ and $`A_4`$ are the matrices corresponding to the last four columns of the matrix of eigenvalues shown in Section 3. Then $`A_1=A`$ and

$$MM^T=9I+2A_2+3A_3+5A_4.$$
(1)
(The number of 2-element subsets of the cells of $`\pi \sigma `$ is determined by the number of cells of $`\pi \sigma `$.) If the matrix idempotents of the Bose-Mesner algebra of the association scheme are $`E_0,\mathrm{},E_4`$, then

$$MM^T=630E_0+70E_1.$$
(2)
Here $`E_0=\frac{1}{280}J`$ and $`E_1`$ represents orthogonal projection onto the column space of $`M\frac{1}{4}J`$. (One way to prove the above identity is to note that $`MM^T`$ and $`M^TM`$ have the same non-zero eigenvalues with the same multiplicities; alternatively this can be read off the matrix of eigenvalues of the scheme.)

###### 5.1 Lemma.

Suppose $`x`$ is the characteristic vector of an independent subset $`S`$ of $`𝒫(3^3)`$ with size 70. Then

$$\underset{i=0}{\overset{4}{}}\frac{x^TA_ix}{vv_i}A_i=\frac{1}{4}I+\frac{1}{18}A_2+\frac{1}{12}A_3+\frac{5}{36}A_4=\frac{70}{4}E_0+\frac{70}{36}E_1.$$

Proof. We use Seidel’s identity, Theorem 2.1. Let $`x`$ be the characteristic vector of an independent set with size 70. Then

$$x^TE_0x=\frac{70\times 70}{280}=\frac{70}{4}.$$

We also have

$$E_1\mathrm{𝟏}=0,E_1\left(x\frac{1}{4}\mathrm{𝟏}\right)=x\frac{1}{4}\mathrm{𝟏}$$

and therefore

$$x^TE_1x=\left(x\frac{1}{4}\mathrm{𝟏}\right)^T\left(x\frac{1}{4}\mathrm{𝟏}\right)=70\frac{70}{4}\frac{70}{4}+\frac{280}{16}=\frac{210}{4}.$$

Next

$$E_2x=E_3x=E_4x=0$$

and so for our particular values, the right side of Seidel’s identity is

$$\frac{70}{4}E_0+\frac{70}{36}E_1.$$

Referring to (2), we see this equals $`\frac{1}{36}MM^T`$. Using (1), we then find that

$$\frac{70}{4}E_0+\frac{70}{36}E_1=\frac{1}{36}(9I+2A_2+3A_3+5A_4)$$

and the lemma follows from this.

The valencies $`v_1,\mathrm{}v_4`$ appear in the first row of the modified matrix of eigenvalues, the multiplicities $`m_i`$ are in the first column.

###### 5.2 Corollary.

Let $`S`$ be an independent set of size 70 on $`𝒫(3^3)`$. If $`\pi S`$, then there are 36 partitions $`\sigma `$ in $`S`$ such that $`|\pi \sigma |=7`$, a further 18 such that $`|\pi \sigma |=6`$ and $`15`$ such that $`|\pi \sigma |=5`$.

## 6 The Characterisation

We prove that an independent set of size 70 in $`𝒫(3^3)`$ must be one of the sets $`S_{i,j}`$.

Let $`S`$ be some independent set of size $`70`$ in $`𝒫(3^3)`$, and $`z`$ its characteristic vector. By Theorem 3.1 we know that $`z\frac{1}{4}\mathrm{𝟏}`$ lies in the eigenspace of $`X`$ with eigenvalue $`12`$ and, from Corollary 4.2, it follows that $`z`$ lies in the column space of $`M`$. From Lemma 5.1 we see that $`S`$ must contain two vertices $`a`$ and $`b`$ whose meet has exactly seven cells—two pairs and five singletons.

We have $`z_a=z_b=1`$ and $`z_t=0`$ for all vertices $`t`$ that are adjacent to $`a`$ or $`b`$. Let $`M_1`$ be the submatrix of $`M`$ composed of the rows corresponding to the vertices adjacent to $`a`$ or $`b`$. There is a vector $`h`$ such that $`z=Mh`$, and we then have $`M_1h=0`$. Let $`N`$ be a matrix whose columns are a basis for the null space of $`M_1`$, so $`h`$ lies in the column space of $`N`$ and $`z`$ lies in the column space of $`MN`$. Let $`C`$ be the matrix formed by the non-zero columns of the reduced column-echelon form of $`MN`$. Then there is a vector $`y`$ such that $`z=Cy`$. Since $`C`$ is in reduced column form and has full column rank, it has a set of rows that form an identity matrix of order $`\text{rk}(C)\times \text{rk}(C)`$. Since $`z`$ is a $`01`$-vector, this implies that $`y`$ is a $`01`$-vector.

We now actually compute $`C`$ using Maple, and find that its rank is six. Therefore $`y`$ is one of $`2^6`$ $`01`$-vectors and, using Maple again, we find that only three of these choices for $`y`$ have the property that $`Cy`$ is a $`01`$-vector: one of these is the zero vector, and the other two are the characteristic vectors of the two $`S_{ij}`$ that contain $`a`$ and $`b`$.

The second Maple computation can be somewhat elided, as we now describe. It suffices to identify a submatrix $`C_0`$ corresponding to a subset of the rows of $`C`$ such that whenever $`y`$ and $`C_0y`$ are $`01`$-vectors then $`Cy`$ is the characteristic vector of one of the two $`S_{ij}`$ that contain $`a`$ and $`b`$, or the zero vector. We made no serious attempt to find an “optimal” $`C_0`$, but a casual glance at $`C`$ reveals examples with $`m=3`$.

## 7 A Core

We show that, if the sets $`S_{i,j}`$ are the only maximum independent sets in $`𝒫(3^3)`$, then $`𝒫(3^3)`$ is a core.

Let $`X`$ denote $`𝒫(3^3)`$ and suppose $`\psi :XX`$ is a homomorphism. By \[7, Lemma 7.5.4\], the preimage $`\psi ^1(S_{i,j})`$ is a maximum independent set in $`X`$, and hence is equal to $`S_{k,\mathrm{}}`$ for some $`k`$ and $`\mathrm{}`$. Each maximal independent set is determined by a 2-element subset of $`\{1,\mathrm{},9\}`$. The independent sets corresponding to disjoint pairs have exactly 20 partitions in common, the sets corresponding to distinct overlapping pairs have 10 elements in common. It follows that $`\psi ^1`$ determines a map from the vertex set of $`L(K_9)`$ to itself. We show first that this mapping is an endomorphism of $`L(K_9)`$.

To this end, consider the sets

$$\psi ^1(S_{1,2}S_{1,i}),i\{3,\mathrm{},9\}.$$

If $`\alpha `$ is a partition in $`\psi ^1(S_{1,2}S_{1,i})`$, then $`\psi (\alpha )`$ contains the cell $`\{1,2,i\}`$. It follows that the six preimages above are pairwise disjoint. Since

$$\psi ^1(S_{1,2}S_{1,i})=\psi ^1(S_{1,2})\psi ^1(S_{1,i})$$

each of the preimages has size 10 or 20. However the union of these preimages is $`\psi ^1(S_{1,2})`$, with size 70. We conclude that if $`i\{3,\mathrm{},9\}`$, then

$$|\psi ^1(S_{1,2}S_{1,i})|=10$$

and so we see that $`\psi ^1`$ determines an endomorphism of $`L(K_9)`$.

We will show below that $`L(K_9)`$ is a core. It follows from this that $`\psi ^1`$ in fact determines an automorphism of $`L(K_9)`$. Therefore

$$|\psi ^1(S_{i,j}S_{k,\mathrm{}})|$$

is equal to 70, 10 or 20 according as the pairs $`ij`$ and $`k\mathrm{}`$ are equal, distinct and overlapping or disjoint.

To complete the argument, consider the partition $`\alpha `$ with cells

$$\{1,2,3\},\{4,5,6\},\{7,8,9\}.$$

Then

$$\{\alpha \}=S_{1,2}S_{1,3}S_{4,5}S_{4,6}$$

and

$$\psi ^1(\alpha )=\psi ^1(S_{1,2})\psi ^1(S_{1,3})\psi ^1(S_{4,5})\psi ^1(S_{4,6}).$$

Now $`\{12,13\}`$ and $`\{45,46\}`$ are vertex-disjoint edges in $`L(K_9)`$; since $`\psi ^1`$ induces an automorphism of $`L(K_9)`$, their images under $`\psi ^1`$ are vertex-disjoint edges too. Therefore $`\psi ^1(\alpha )\mathrm{}`$, and we have shown that $`\psi `$ is onto. We conclude that $`𝒫(3^3)`$ is a core.

It remains to show that $`L(K_9)`$ is a core.

###### 7.1 Lemma.

$`L(K_{2m+1})`$ is a core.

Proof. Let $`Y`$ be the core of $`L(K_{2m+1})`$. Then $`Y`$ is vertex- and arc-transitive, and $`\omega (Y)=2m`$. Since $`Y`$ is an induced subgraph of $`X`$, it is a line graph and therefore it is the line graph of an edge-transitive graph $`W`$ with at least one vertex of valency $`2m`$. If $`W`$ is not bipartite, it is vertex-transitive and hence regular; therefore $`W=K_{2m+1}`$. If $`W`$ is bipartite it is semi-regular. If $`W`$ has two vertices of degree $`2m`$ they must be adjacent and therefore, since $`W`$ is edge-transitive, each edge joins two vertices of degree $`2m`$ and $`W=K_{2m+1}`$. The only remaining case is when $`W`$ has a unique vertex of degree $`2m`$, whence $`W=K_{1,2m}`$ and $`Y=K_{2m}`$. But $`|V(Y)|`$ divides $`|L(K_{2m+1})|`$. Since $`2m`$ does not divide $`m(2m+1)`$, we conclude that $`L(K_{2m+1})`$ is its own core.

We note that the edge set of $`L(K_{2m})`$ can be partitioned into $`2m1`$ perfect matchings. It follows that the core of $`L(K_{2m})`$ is $`K_{2m1}`$.

## 8 $`q`$-Kneser Graphs

Let $`V`$ be a set of size $`v`$. The vertices of the Kneser graph $`K_{v:k}`$ are the $`k`$-subsets of $`V`$ and two $`k`$-subsets are adjacent if they are disjoint. The Erdős-Ko-Rado theorem asserts that an independent set in $`K_{v:k}`$ has size at most $`\left(\genfrac{}{}{0pt}{}{v1}{k1}\right)`$, and that an independent set of this size consists of the $`k`$-subsets that contain a fixed element of $`V`$.

We consider an analogous class of graphs. Let $`V`$ be a vector space of dimension $`v`$ over the field of order $`q`$. The vertices of the $`q`$-Kneser graph are the $`k`$-subspaces of $`V`$, and two $`k`$-subspaces are adjacent if their intersection is the zero subspace. We denote this graph by $`qK_{v:k}`$. Our aim is to determine the independent sets of maximum size in $`qK_{v:k}`$.

Let $`q`$ be a fixed positive integer. We define

$$[n]:=\frac{q^n1}{q1}.$$

We then define $`[n]!`$ inductively by setting $`[0]!=1`$ and

$$[n+1]!:=[n+1][n]!.$$

With this in hand we define the $`q`$-binomial coefficient $`\left[\genfrac{}{}{0.0pt}{}{v}{k}\right]`$ by

$$\left[\genfrac{}{}{0.0pt}{}{v}{k}\right]:=\frac{[v]!}{[k]![vk]!}.$$

One reason the $`q`$-binomial coefficient is important is that $`\left[\genfrac{}{}{0.0pt}{}{v}{k}\right]`$ is the number $`k`$-dimensional subspaces of a $`v`$-dimensional vector space over a field with $`q`$ elements.

Suppose $`V`$ is a vector space of dimension $`v`$ over a field with $`q`$ elements. Let $`W_{1,k}(v)`$ be the 01-matrix with rows indexed by the 1-dimensional subspaces, columns by the $`k`$-dimensional subspaces of $`V`$ and with $`ij`$-entry equal to 1 if and only if the $`i`$-th subspace of dimension $`1`$ is contained in the $`j`$-th subspace of dimension $`k`$. Thus $`W_{1,k}(v)`$ is a $`[v]`$ by $`\left[\genfrac{}{}{0.0pt}{}{v}{k}\right]`$ matrix. It is a standard result that the rows of $`W_{1,k}(v)`$ are linearly independent. (See, e.g., .) The rows of $`W_{1,k}(v)`$ are characteristic vectors of independent sets, namely the $`k`$-spaces that contain a given 1-dimensional subspace.

###### 8.1 Lemma.

If $`v2k`$, the maximum size of an independent set in $`qK_{v:k}`$ is

$$\left[\genfrac{}{}{0.0pt}{}{v1}{k1}\right].$$

If $`S`$ is an independent set of this size, its characteristic vector lies in the column space of $`W_{1,k}(v)^T`$.

Proof. The least eigenvalue $`\tau `$ of $`qK_{v:k}`$ is

$$q^{k(k1)}\left[\genfrac{}{}{0.0pt}{}{vk1}{k1}\right],$$

and the corresponding eigenspace has dimension $`[v]1`$. This can be read off the matrix of eigenvalues of the Johnson scheme, which is given in . The valency of $`qK_{v:k}`$ is

$$q^{k^2}\left[\genfrac{}{}{0.0pt}{}{vk}{k}\right]$$

and hence the ratio bound applied to $`qK_{v:k}`$ yields that

$$\alpha (qK_{v:k})\left[\genfrac{}{}{0.0pt}{}{v1}{k1}\right].$$

It follows that the rows of $`W_{1,k}(v)`$ are characteristic vectors of independent sets from $`qK_{v:k}`$ with maximal size. Now $`\text{rk}(W_{1,k}(v))=[v]`$ and $`\mathrm{𝟏}^T`$ lies in the row space of $`W_{1,k}(v)`$. Therefore the subspace of the column space of $`W_{1,k}(v)^T`$ orthogonal to $`\mathrm{𝟏}`$ is the eigenspace of $`qK_{v:k}`$ with eigenvalue $`\tau `$, and so the lemma follows.

The following result is due to Hsieh  (his proof does not cover the case $`v=2k+1,q=2`$). Our proof is new, and considerably simpler. It is related to the methods of Frankl and Wilson , but they do not give a proof of the characterization.

###### 8.2 Theorem.

If $`v>2k`$, then an independent set of maximum size in $`qK_{v:k}`$ consists of the $`k`$-subspaces of $`V`$ that contain a given 1-dimensional subspace of $`V`$.

Proof. Let $`M`$ denote $`W_{1,k}(v)^T`$ and let $`z`$ be the characteristic vector of an independent set $`S`$ in $`qK_{v:k}`$ with maximal size. Then $`z`$ lies in the column space of $`M`$, and therefore there is a vector $`h`$ such that

$$z=Mh$$

If $`\alpha `$ is a $`k`$-subspace in $`S`$ and $`\beta `$ is $`k`$-subspace such that $`\beta \alpha =0`$, then $`\beta S`$ and $`z_\beta =0`$. Hence $`M_\beta h=0`$ for all $`k`$-subspaces $`\beta `$ skew to $`\alpha `$.

Let $`B`$ be a complement to the $`k`$-subspace $`\alpha `$, and let $`M_B`$ be the submatrix of $`M`$ formed by the rows $`M_\beta `$, where $`\beta B`$. The columns of $`M_B`$ corresponding to the 1-dimensional subspaces not in $`B`$ are zero; the non-zero columns form the matrix $`W_{1,k}(vk)^T`$, and therefore they are linearly independent. Since $`M_Bh=0`$, it follows that the entries of $`h`$ indexed by the 1-dimensional subspaces of $`B`$ must all be zero. Our choice of the complement $`B`$ was arbitrary, and consequently the entries of $`h`$ indexed by a 1-dimensional subspace not in $`\alpha `$ are zero. Therefore the support of $`h`$ consists of 1-dimensional subspaces of $`\alpha `$ and so the $`k`$-subspaces in $`S`$ have a 1-dimensional subspace in common.

It is not difficult to modify the above argument to obtain a proof of the Erdős-Ko-Rado theorem. The resulting proof is similar in its underlying ideas to the original proof by Wilson in .

## 9 The Witt Graph on 77 Vertices

Let $`𝒟`$ be the well-known $`3`$-$`(22,6,1)`$ design, with 77 blocks. The Witt graph $`W`$ has the 77 blocks of this design as its vertices; two blocks are adjacent if they are disjoint. There are 21 blocks on each point of the design, and thus we find 22 independent sets of size 21. The Witt graph is strongly regular, with eigenvalues and multiplicities

$$(6)^{(21)},2^{(55)},16^{(1)}.$$

The ratio bound yields

$$\alpha (W)\frac{77}{1+\frac{16}{6}}=21.$$

Thus the independent sets given above have maximum size. We aim to show that these are all the independent sets of maximum size in the graph.

Let $`M`$ be the $`77\times 22`$ matrix with the characteristic vectors of our 22 independent sets as its columns. (So $`M^T`$ is the usual incidence matrix of the design.) Each pair of distinct points lies in exactly five blocks and consequently

$$M^TM=16I_{22}+5J_{22},$$

which is invertible. Therefore $`\text{rk}(M)=22`$. Each column of

$$M\frac{3}{11}J$$

is an eigenvector for $`W`$, and the columns of this matrix span the eigenspace with eigenvalue $`6`$. We conclude that if $`x`$ is the characteristic vector of an independent set of size 21, it lies in the column space of $`M`$.

Suppose $`x`$ contains the block $`\alpha `$, that is, $`x_\alpha =1`$ and assume $`x=Mh`$. If $`\beta `$ is a block disjoint from $`\alpha `$, then $`x_\beta =0`$. Let $`M_1`$ be the submatrix of $`M`$ formed by the rows corresponding to the blocks disjoint from $`\alpha `$. Then $`M_1h=0`$. Now $`M_1`$ is $`16\times 22`$

$$M_1=\left(\begin{array}{cc}0& N\end{array}\right),$$

where $`N`$ is $`16\times 16`$. We show that $`N`$ is the incidence matrix of a $`2`$-$`(16,6,2)`$-design, whence it follows that $`N`$ is invertible.

Let $`\alpha `$ be a block of the Witt design and suppose $`x,y`$ are two points not in $`\alpha `$. There are five blocks that contain $`x`$ and $`y`$ and, since any two distinct blocks have at most two points in common, these five blocks partition the 20 points other than $`x`$ and $`y`$. It follows that three of these five blocks meet $`\alpha `$ in two points, and the remaining pair of blocks are disjoint from $`\alpha `$. Hence the blocks disjoint from $`\alpha `$ form a 2-design on 16 points with block size six and with $`\lambda =2`$. From this we deduce that there are exactly 16 blocks disjoint from $`\alpha `$ and so $`N`$ is the incidence matrix of a symmetric design.

Therefore $`N`$ is invertible and so it follows that $`\text{supp}(h)\alpha `$. Therefore each block in $`\text{supp}(x)`$ contains $`\text{supp}(h)`$, and consequently these 21 blocks have a point in common.

Since the Witt graph is the graph induced by the vertices not adjacent to a given vertex in the Higman-Sims graph, our result leads to a determination of all independent sets of size $`22`$ in the Higman-Sims graph. It is well known that the maximal independent sets of the Witt graph are as shown above: see for example , where the maximal independent sets in the Higman-Sims graph are determined by computer. However our proof is new and gives further evidence that our method has a wide range of application.


text:
# Search For Exospheric Signatures From Transiting Planets

## 1. Introduction

The He I feature at 10 830 Å is predicted to be one of the deepest absorption lines of the diffuse and extended exosphere in the optical and near-IR transmission spectrum The goal of the present study is to search for exospheric signatures in the spectrum of HD209458, during transits of the planet. Shkolnik et al. (2003) suggested that a chomospheric activity can be induced by the planet orbit. We searched for such a signature in stellar chromospheric lines.

## 2. Search for spectral signatures from the exospheric components

We performed observations of HD209458 in the UV with VLT/UVES in the 0.33-0.67 $`\mu `$m region at high spectral resolution. 1 transit was covered with R=70000 in December 1999 in two spectral range: Blue (0.328-0.4562 $`\mu `$m) and Red (0.4583-0.6686 $`\mu `$m). 6 transits were covered with R=100000: 1 in June 2000 in Blue and Red and June to September 2002 in Red (0.475-0.680 $`\mu `$m). We searched for ions and neutral molecules originating in the planet’s exosphere and located in the evaporated material around the planet. Observations of 1 transit in the infrared was also performed with VLT/ISAAC at medium resolution (R=10000) around the He I line at1.083 $`\mu `$m (1.06-1.1 $`\mu `$m). A sample of these spectra centered around this feature is shown is Fig. 1a.

From observations during one full transit with ISAAC in June 2001 of the spectral region around 1.083 $`\mu `$m, no detection of He was obtained due to strong instrumental fringing affecting the data. An 3 $`\sigma `$ upper limit of 0.5% deep absorption feature was derived.

## 3. Search for planet-induced chromospheric activity on HD209458

Following the suggestion of Shkolnik et al.(2003), we searched signatures of a chromospheric activity induced by the (magnetic more probably than tidal) heating of the star’s outer atmosphere by the planet.

We have recovered high-resolution UVES spectra in the blue arm during one transit (and its off-transit) period in 2000. The Ca II K at 3933Å, Ca II K at 3968Å and Al I at 3944Ålines can be related to chromospheric activity. A sample of these spectra centered around the Ca II K feature is shown is Fig. 1b. Our spectra show emission enhancement observed in the Ca II H band but we found nothing significant in the two otherbands. The variations could be indicative of the stellar chromospheric activity with the planet’s magnetic field.

## 4. Perspectives

UVES data from the 5 transits in June-September 2002 are currently being analysed to look for exospheric planetary signature of other constituents. Further and improved observations are required. We have time allocation this year.

## 5. References

Moutou, C., Coustenis, A., Schneider, J., Queloz, D. & Mayor, M., 2003, in A&A, 405, 341 and references therein
Shkolnik, E., Walker, G. A. H, & Bohlender, D. A., 2003, submitted to ApJ


text:
# Cryptanalyzing a discrete-time chaos synchronization secure communication system

## 1 Introduction

In recent years, a growing number of cryptosystems based on chaos have been proposed , many of them fundamentally flawed by a lack of robustness and security . In , a secure communication system based on chaotic modulation using discrete-time chaos synchronization is proposed. Two different schemes of message encoding are presented. In the first scheme, the binary message ($`m(i)=\pm 1`$) is multiplied by the chaotic output signal of the transmitter and then sent to drive the receiver system. In the second scheme, the binary message is modulated by multiplication with the chaotic output signal and then is fed back to the transmitter system and simultaneously sent to the receiver system.

Discrete-time chaotic systems are generally described by a set of nonlinear difference equations. The first communication system based on modulation by multiplication can be described by:

$$\mathrm{transmitter}\{\begin{array}{c}\mathrm{x}_1(\mathrm{i}+1)=1\alpha \mathrm{x}_1^2(\mathrm{i})+\mathrm{x}_2(\mathrm{i})\hfill \\ \mathrm{x}_2(\mathrm{i}+1)=\beta \mathrm{x}_1(\mathrm{i})\hfill \\ \mathrm{s}(\mathrm{i})=\mathrm{x}_1(\mathrm{i})\mathrm{m}(\mathrm{i})\hfill \end{array}$$
(1)
$$\mathrm{receiver}\{\begin{array}{c}\widehat{\mathrm{x}}_1(\mathrm{i}+1)=1\alpha \mathrm{s}^2(\mathrm{i})+\widehat{\mathrm{x}}_2(\mathrm{i})\hfill \\ \widehat{\mathrm{x}}_2(\mathrm{i}+1)=\beta \widehat{\mathrm{x}}_1(\mathrm{i})\hfill \\ \widehat{\mathrm{m}}(\mathrm{i})=\mathrm{s}(\mathrm{i})/\widehat{\mathrm{x}}_1(\mathrm{i})\hfill \end{array}$$
(2)
The communication scheme using modulation by multiplication and feedback, with a modification to avoid divergence due to feedback, is described by:

$$\mathrm{transmitter}\{\begin{array}{c}\mathrm{x}_1(\mathrm{i}+1)=1\alpha (\mathrm{s}(\mathrm{i})\frac{\mathrm{s}(\mathrm{i})+\mathrm{P}}{2\mathrm{P}}2\mathrm{P})^2+\mathrm{x}_2(\mathrm{i})\hfill \\ \mathrm{x}_2(\mathrm{i}+1)=\beta \mathrm{x}_1(\mathrm{i})+0.05\mathrm{x}_1(\mathrm{i})(\mathrm{m}(\mathrm{i})1)\hfill \\ \mathrm{s}(\mathrm{i})=\mathrm{x}_1(\mathrm{i})\mathrm{m}(\mathrm{i})\hfill \end{array}$$
(3)
$$\mathrm{receiver}\{\begin{array}{c}\widehat{\mathrm{x}}_1(\mathrm{i}+1)=1\alpha (\mathrm{s}(\mathrm{i})\frac{\mathrm{s}(\mathrm{i})+\mathrm{P}}{2\mathrm{P}}2\mathrm{P})^2+\widehat{\mathrm{x}}_2(\mathrm{i})\hfill \\ \widehat{\mathrm{x}}_2(\mathrm{i}+1)=\beta \widehat{\mathrm{x}}_1(\mathrm{i})+0.05(\mathrm{s}(\mathrm{i})\widehat{\mathrm{x}}_1(\mathrm{i}))\hfill \\ \widehat{\mathrm{m}}(\mathrm{i})=\mathrm{s}(\mathrm{i})/\widehat{\mathrm{x}}_1(\mathrm{i})\hfill \end{array}$$
(4)
with $`P=(1+\sqrt{6.6})/2.8`$.

Although the authors seemed to base the security of their cryptosystems on the chaotic behavior of the output of the Henon non-linear dynamical system, no analysis of security was included. It was not considered whether there should be a key in the proposed system, what it should consist of, what the available key space would be, what precision to use, and how the key would be managed.

In the next section we discuss the weaknesses of this secure communication system using the Henon attractor and make some suggestions to improve its security.

## 2 Attacks on the proposed system

### 2.1 The key space

Although it is not explicitly stated in , it is assumed that the key is formed by the two parameters of the map, $`\alpha `$ and $`\beta `$. Thus, in , the key is fixed to $`k=\{\alpha ,\beta \}=\{1.4,0.3\}`$. However, in  there is no information given about what the key space is. The key space is defined by all the possible valid keys. The size of the key space $`r`$ is the number of encryption/decryption key pairs that are available in the cipher system.

In this chaotic scheme the key space is nonlinear because all the keys are not equally strong. We say that a key is *weak* or *degenerated* if it is easier to break a ciphertext encrypted with this key than breaking a ciphertext encrypted with another key from the key space.

The study of the chaotic regions of the parameter space from which valid keys, i.e., parameter values leading to chaotic behavior, can be chosen is missing in . A possible way to describe the key space might be in terms of positive Lyapunov exponents. According to \[17, p. 196\], let $`𝐟`$ be a map of $`^m`$, $`m1`$, and $`\{𝐱_0,𝐱_1,𝐱_2,\mathrm{}\}`$ be a bounded orbit of $`𝐟`$. The orbit is chaotic if

1. it is not asymptotically periodic,
2. no Lyapunov exponent is exactly zero, and
3. the largest Lyapunov exponent is positive.

The largest Lyapunov exponent can be computed for different combinations of the parameters. If it is positive, then the combination can be used as a valid key. In Fig. 1, the chaotic region for the Henon attractor used in  has been plotted. This region corresponds to the keyspace. In general, parameters chosen from the lower white region give rise to periodic orbits, undesirable because the ciphertext is easily predictable. Parameters chosen from the upper white region give rise to unbounded orbits diverging to infinity, and hence the system can not work. Therefore, both regions should be avoided to get suitable keys. Only keys within the black region are good. And even within this region, there exist periodic windows, unsuitable for robust keys.

This type of irregular and often fractal chaotic region shared by most secure communication systems proposed in the literature is inadequate for cryptographic purposes because there is no easy way to define its boundary. And if the boundary is not mathematically and easily defined, then it is hard to find suitable keys within the key space. This difficulty in defining the key space discourages the use of the Henon map. Instead, complete chaoticity for any parameter value should be preferred. Piecewise linear (PWL) maps are a good choice because they behave chaotically for any parameter value in the useful interval .

### 2.2 Insensitivity to parameter mismatch

Both communication systems, the one based on modulation by multiplication and the one using modulation by multiplication and feedback, can only have valid keys carefully chosen from the chaotic region plotted in Fig. 1 to avoid periodic windows and divergence. Due to low sensitivity to parameter mismatch, if the system key is fixed to $`k=\{\alpha ,\beta \}=\{1.4,0.3\}`$ as in , then any key $`k^{}`$ chosen from the same key space will decrypt the ciphertext into a message $`m^{}`$ with an error rate which is well below 50%. Fig. 2 plots the bit error rate (BER) when the ciphertext encrypted with $`k=\{\alpha ,\beta \}=\{1.4,0.3\}`$ is decrypted using keys $`k^{}`$ from the valid key space at a distance $`d`$ from $`k`$. For this experiment the Euclidean distance was chosen:

$$d=\sqrt{(\alpha \alpha ^{})^2+(\beta \beta ^{})^2}$$
(5)
This insensitivity to parameter mismatch due to the coupling between transmitter and receiver renders the system totally insecure when the Henon map is used. A different map more sensitive to small differences in the parameter values should be used to grant security.

### 2.3 Brute force attacks

A brute force attack is the method of breaking a cipher by trying every possible key. The quicker the brute force attack, the weaker the cipher. Feasibility of brute force attacks depends on the key space size $`r`$ of the cipher and on the amount of computational power available to the attacker. Given today’s computer speed, it is generally agreed that a key space of size $`r<2^{100}`$ is insecure.

However, this requirement might be very difficult to meet by this cipher because the key space does not allow for such a big number of different strong keys. For instance, Fig. 1 was created using a resolution of $`10^3`$, i.e., there are $`1400\times 3000`$ different points. To get a number of keys $`r>2^{100}10^{30}`$, the resolution should be $`10^{15}`$. However, with that resolution, thousands of keys would be equivalent, unless there is a strong sensitivity to parameter mismatch, which is usually lost by synchronization, even when using a different chaotic map.

### 2.4 Statistical analysis

Fig. 2a shows that the error is upper bounded: BER$`0.33`$. This is a consequence of the fact that the orbit followed by any initial point in the Henon attractor is not uniformly distributed, because in average it spends two thirds of the time above $`x=0`$. As a consequence, mixing the cleartext with the output of a function whose probability density is not uniform will result in a weak cryptosystem. In Fig. 3 the Henon attractor is plotted. It can be observed that the distribution is far from flat because the orbit visits more often the region $`x>0`$. In average, two thirds of the iterates lie to the right of $`x=0`$ (depicted as a dashed line). This fact allows the attacker to guess in average two thirds of the encrypted bits, even with no knowledge about the transmitter/receiver structure.

To get a balanced distribution, the threshold should be moved to the right . Let $`x_m`$ denote the real value such that

$$P(x_ix_m)=P(x_i>x_m)=0.5.$$
(6)
A good estimation presented in  is $`\widehat{x}_m=0.39912`$, depicted as a dotted line in Fig. 3. However, this result is difficult to apply provided the way in which the Henon attractor is used by the cryptosystem. Therefore, it is seen again that the Henon map is a bad choice as a chaotic map for this communication scheme. A different map with a balanced distribution, i.e., whose orbit visits with equal frequency the regions above and below a certain level $`x=0`$, should be chosen to prevent statistical attacks.

### 2.5 Plaintext attacks

In the previous sections we showed that the use of the Henon map is not advisable because of its inability to define a good key space, of its low sensitivity to parameter mismatch, and of its non uniformly distributed orbits. We are to show next that if a different map is used, the security of the communication system will not improve if the same key is used repeatedly for successive encryptions.

According to \[20, p. 25\], it is possible to differentiate between different levels of attacks on cryptosystems. In a known plaintext attack, the opponent possesses a string of plaintext, $`p`$, and the corresponding ciphertext, $`c`$. In a chosen plain text, the opponent has obtained temporary access to the encryption machinery, and hence he can choose a plain text string, $`p`$, and construct the corresponding cipher text string, $`c`$.

The cipher under study behaves as a modified version of the one-time pad \[20, p. 50\]. The one-time pad uses a randomly generated key of the same length as the message. To encrypt a message $`m`$, it is combined with the random key $`k`$ using the exclusive-OR operation bitwise. Mathematically,

$$c(i)=m(i)+k(i)mod2,$$
(7)
where $`c`$ represents the encrypted message or ciphertext. This method of encryption is perfectly secure because the encrypted message, formed by XORing the message and the random secret key, is itself totally random. It is crucial to the security of the one-time pad that the key be as long as the message and never reused, thus preventing two different messages encrypted with the same portion of the key being intercepted or generated by an attacker.

Eq. (1) and Eq. (3) are used to generate a keystream $`\{x_1(1)=k(1),x_1(2)=k(2),x_1(3)=k(3),\mathrm{}\}`$. This keystream is used to encrypt the plain text string according to the rule

$$c(i)=k(i)m(i)$$
(8)
Therefore, if the attacker possesses the plaintext $`m(i)`$ and its corresponding ciphertext $`c(i)`$, he will be able to obtain $`k(i)`$. If the same key, i.e. the same parameter values, is used to encrypt any subsequent message in the future, it will generate an identical chaotic orbit, which is already known. As a consequence, when $`c(i)`$ and $`k(i)`$ are known in Eq. (8), $`m(i)`$ is readily obtained by the attacker.

Obviously, when using this cryptosystem, regardless of the choice of the chaotic map, the key can never be reused. A slight improvement to partially enhance security even when the key is reused consists of randomly setting the initial point of the chaotic orbit at the transmitter end. Synchronization will guarantee that the message is correctly decrypted by the authorized receiver. However, an eavesdropper would have more difficulty in using past chaotic orbits because they will diverge due to sensitivity to initial conditions.

## 3 Conclusions

The proposed cryptosystem using the Henon map is rather weak, since it can be broken without knowing its parameter values and even without knowing the transmitter precise structure. However, the overall security might be highly improved if a different chaotic map with higher number of parameters is used. The inclusion of feedback makes it possible to use many different systems with non symmetric nonlinearity as far as the whole space is folded into a bounded domain to avoid divergence. However, to rigorously present future improvements, it would be desirable to explicitly mention what the key is, how the key space is characterized, what precision to use, how to generate valid keys, and also to perform a basic security analysis. For the present work , the total lack of security discourages the use of this algorithm as is for secure applications.

This work is supported by Ministerio de Ciencia y Tecnología of Spain, research grant TIC2001-0586. Our thanks to Moez Feki for his comments and source code.

## Figures