text:
# astro-ph/0209232 Kinematical solution of the UHE-cosmic-ray puzzle without a preferred class of inertial observers

## I Introduction

Over the last few years there has been a large number of studies concerning the emerging “cosmic-ray puzzle.” UHECRs (ultra-high-energy cosmic rays) should interact with the Cosmic Microwave Background Radiation (CMBR) and produce pions. Based on the typical energies of CMBR photons, and on a straightforward special-relativistic analysis of the kinematics of the process $`p+\gamma p+\pi `$ (assuming the UHECR is a proton), one is led to the conclusion that photopion production should render observations of UHECRs with $`E>510^{19}`$eV (the GZK cutoff)  extremely unlikely. Above $`10^{20}`$eV the cosmic-ray mean free path should be only of a few Mpc, and there are no astrophysical sources capable of accelerating particles to such energies within a few tens of Mpc from us. Still, more than a dozen UHECRs have been reported by AGASA with nominal energies at or above $`10^{20}`$ eV. It is plausible that these UHECRs, the highest-energy particles we have access to, may be providing us a window on a new realm of fundamental physics. Proposed solutions extend from the idea that previously unknown particles play one or another role in evading the GZK cutoff to the idea, which is the main focus of the study here reported, that the description of these UHECRs as protons coming from cosmological distances is correct but the GZK analysis requires modifications due to new (“quantum”) properties of spacetime (and the associated laws of kinematics). Of course, the simplest (and perhaps most likely) explanation is that these preliminary experimental results may be misleading: that for example AGASA might have overestimated the energies of the observed UHECRs.

For what concerns the experimental side the situation will become much clearer in the not-so-distant future: especially the Pierre Auguer Observatory  should definitely clarify whether violations of the GZK limit are a reality. In the meantime it is legitimate to take as working assumption that we are (or may be) confronted with a “cosmic-ray puzzle”. In this paper I propose a new solution for the puzzle. My solution can be seen as a third example of “kinematical solution” of the cosmic-ray puzzle. I describe as “kinematical solutions” the solutions that are based on the assumption that the description of these UHECRs as protons coming from cosmological distances is correct and that the GZK analysis requires modifications due to a failure of Lorentz symmetry in the realm of the relevant photopion-production processes. At first this possibility was examined at a purely phenomenological level: in the studies  a general parametrization of possible deviations from Lorentz symmetry was introduced, and choices of parameters that would shift upward the GZK limit were found. Then, motivated by the proposal put forward in Ref. , there has also been work  on a specific idea and scheme***There appears to be a certain tendency in the literature to confuse the proposals based on particle-physics models with a general parametrization of possible deviations from Lorentz symmetry with the proposals based on quantum-spacetime models with deviations from Lorentz symmetry. For example, in Ref.  the Coleman-Glashow model of Ref.  is described as a model of Planck-scale deviations from Lorentz symmetry, whereas in Ref.  there is no mention of the Planck scale, quantum gravity, and quantum spacetime. A phenomenology of Planck-scale deviations from Lorentz symmetry was only proposed later in Ref. , and found its way in the cosmic-ray-puzzle literature only starting with the studies reported in Refs. . for the breakup of Lorentz symmetry, in which the GZK limit is shifted upward by Planck-scale effects, reflecting some new quantum properties of spacetime.

While very different on many levels, the two previous kinematical solutions of the cosmic-ray puzzle, the general particle-physics phenomenology of Refs.  and the class of quantum-spacetime phenomenological models of Refs. , have a common feature: the assumed deviations from Lorentz symmetry require the emergence of a preferred class of inertial observers (often, without any conceivable justification, identified with the natural frame for the description of the CMBR). The primary objective of the study I am here reporting is to show that this feature, which may be perceived as unactractive by some colleagues, is not a necessary ingredient of kinematical solutions of the cosmic-ray puzzle: I will discuss a Planck-scale deformation of Lorentz symmetry which evades the GZK limit kinematically, but does not require a preferred class of inertial observers.

My scheme is a new example of a class of relativistic theories, the so-called “DSR” or “doubly-special-relativity” theories, which I proposed in Ref. , motivated by a certain perspective on the quantum-gravity problem, and have already been studied extensively over the last two years \[11-20\] DSR theories are relativistic theories that describe the laws of transformation between inertial observers in such a way that the Planck scale, $`E_p`$, acquires a role completely analogous to the one of the speed-of-light constant $`c`$: in DSR both $`c`$ and $`E_p`$ are observer-independent scales of the transformation laws. It is indeed plausible  that we might discover the need for this type of relativistic theories in ultra-high-energy physics just in the same sense that we discovered the need for special relativity in the study of processes involving high velocities.

In the specific type of DSR theory that I propose as a solution of the cosmic-ray puzzle there are no deviations from special relativity for massless particles, while for particles with finite mass, $`m`$, the deviations from special relativity are negligble at low energies but become significant when the particle’s energy $`E`$ is large enough that $`m/E<E/E_p`$. For a proton the condition $`m/E<E/E_p`$ requires $`E>310^{18}eV`$, and therefore the GZK cutoff happens to occur when the deviations from special relativity are predicted to be rather large. In general I observe that the ratio $`E/m`$ sets the magnitude of the boost, while $`E/E_p`$ will set the magnitude of Planck-scale effects, and that in a large class of DSR theories one should expect that the deviations from ordinary Lorentz symmetry become significant when $`E/m`$ is large enough to compensate for the smallness of $`E/E_p`$.

In the next section I review the previously-proposed mechanism, based on Lorentz-symmetry breaking, for a quantum-gravity solution of the cosmic-ray puzzle. In Section 3 I give a brief review of results in DSR theories, in which Lorentz symmetry is deformed rather than broken. In Section 4 I propose my DSR-based solution of the cosmic-ray puzzle. Section 5 offers some closing remarks.

## II Previous Planck-scale solutions of the cosmic-ray puzzle

It is plausible that the unification of general relativity and quantum mechanics will involve some sort of spacetime quantization, e.g. noncommutative geometry or spacetime discreteness. If spacetime is fundamentally discrete or noncommutative then this should in particular apply to the spacetimes that low-energy probes perceive as Minkowski (flat classical and continuous). From the point of view of experimental tests a key point is that spacetime discreteness or noncommutativity are likely to require departures from Lorentz symmetry (see, e.g., Refs. ).

As a starting point for a phenomenology aimed at exploring this type of possible quantum-gravity effects, Refs.  proposed the investigation of a scenario predicting violations of Lorentz symmetry set by the Planck scale and characterized by the emergence of a modified dispersion relation of the type

$$m^2=E^2\stackrel{}{p}^2+f(E,\stackrel{}{p}^2;E_p)E^2c^2\stackrel{}{p}^2+\eta \left(\frac{E}{E_p}\right)^nE^2,$$
(1)
where $`\eta `$ is a dimensionless coefficient of order 1. The function $`f(E,\stackrel{}{p}^2;E_p)`$ is only specified in leading order in $`1/E_p`$ since anyway experiments could at best find some evidence of the leading contribution due to $`f`$.

This type of quantum-gravity scenarios is seen in analogy with the deformed dispersion relations that apply to the description of collective modes (such as phonons) in certain materials, whose propagation satisfies a relativistic dispersion relation only up to corrections governed by the scale of atomic structure of the material. Similar considerations apply to the decription of the propagation light in water. Intuitively one can indeed attempt to introduce in quantum gravity the (however vague) concept of “spacetime foam” and spacetime foam may affect particle propagation in a way that to some extent can be viewed in analogy with the way that the presence of other media affects particle propagation.

One of the phenomenologically significant consequences of deformed dispersion relations of the type (1) is the associated deformation of the thresholds for certain particle-production processes. Let me illustrate this effect in the specific example of photopion production, $`p+\gamma p+\pi `$, which is relevant for the cosmic-ray puzzle. The kinematic condition for photopion production is obtained by imposing conservation of energy and momentum and by applying the dispersion relation (which in this case is deformed). Denoting with $`E`$ the energy of the incoming proton and denoting with $`ϵ`$ the energy of the incoming photon, one finds that photopion production is only possible if

$$Eϵ\eta \frac{E^{2+n}}{4E_p^n}\left(\frac{m_{prot}^{1+n}+m_\pi ^{1+n}}{(m_{prot}+m_\pi )^{1+n}}1\right)\frac{(m_{prot}+m_\pi )^2m_{prot}^2}{4}.$$
(2)
The $`E_p\mathrm{}`$ limit, in which the second term on the left-hand side is neglected, of course reproduces the standard special-relativistic result for the photopion-production threshold condition. In the processes we study in laboratory experiments the $`E_p`$-dependent term is completely negligible, because of the large value of the scale $`E_p`$. But in the analysis of the cosmic-ray puzzle one must consider an incoming proton of very high energy, of order $`10^{20}eV`$, while the photon is a CMBR photon with typical energy roughly of order $`10^3eV`$, and therefore one finds that $`Eϵ10^{17}eV^2`$, $`E^3/E_pϵ10^{32}eV^2`$, $`E^4/E_p^2ϵ10^{24}eV^2`$. From these estimates one concludes  that, for $`n=1`$ and $`n=2`$, the formula (2) predicts a significant shift upward of the GZK cutoff, and provides a solution of the cosmic-ray puzzle.

This striking observation has motivated several follow-up quantum-gravity studies based on the proposal (2). More recently, other forms of Planck-scale modifications of the dispersion are also being considered  in relation with the cosmic-ray puzzle.

These quantum-gravity-motivated solutions of the cosmic-ray puzzle, just like the mentioned non-quantum-gravity solutions that are also based on a breakup of Lorentz symmetry, necessarily require the existence of a preferred class of inertial observers. In fact, assuming that the Lorentz transformations maintain their familiar form, the only invariant dispersion relation is $`m^2=E^2p^2`$. All deviations from this special-relativistic form of the dispersion relation will necessarily not be invariant: at least the values of the coefficients that characterize the modified dispersion relation (such as $`\eta `$ in (1)) will be different for different inertial observers and can be used to identify a preferred class of inertial observers. This is after all consistent with the mentioned quantum-gravity intuition based on “spacetime foam”, which would indeed be suitable for identifying a preferred class of inertial observers.

## III Previous doubly-special-relativity theories

The fact that the quantum-gravity scenarios mentioned in the preceding section require a preferred class of inertial observers is not necessarily a disappointment. As mentioned certain quantum-gravity ideas, notably some perspectives on the spacetime-foam picture, can provide motivation for exploring this possibility. Moreover, in the study of particle physics the concept of spontaneous breaking of a symmetry has proven very useful, and it is conceivable that quantum gravity would host a similar mechanism for the spontaneous breaking of Lorentz symmetry at the Planck scale. For example, in string theory, the most popular approach to the quantum-gravity problem, mechanisms for the spontaneous braeking of Lorentz symmetry have been extensively investigated (see, e.g., Ref. ).

However, the existence of a preferred class of inertial observers is anyway not simple conceptually. At present we can only make wild guesses about this preferred class of observers. Many studies attempt to identify this preferred class of inertial observers with a natural class of observers for the CMBR, but this conjecture (although it cannot be excluded a priori) appears to lack any justification, since there is no connection between the classical physics responsible for CMBR physics and the Planck-scale realm. Moreover, in any case, even if one is not troubled by the possibility of a preferred class of inertial observers, it is natural to wonder  whether there are other alternatives in addition to the cases in which Lorentz symmetry is exactly preserved at the Planck scale and the case in which Lorentz symmetry is broken, with associated emergence of a preferred class of inertial observers. The so-called “doubly-special relativity” (“DSR”) theories that I proposed in Ref.  are scenarios in which ordinary Lorentz symmetry is not exactly preserved at the Planck scale, but there is no special class of inertial observers. Using a terminology which is popular in the mathematics community, my proposal can be described as a “deformation” of Lorentz symmetry, without any true loss of symmetry. This proposal can be motivated  from the observation that some quantum-gravity scenarios, notably a certain type of scenarios based on noncommutative geometry, appear to require it. It has also been conjectured  that DSR theories may be applicable to the popular “loop quantum gravity” theory.

Here, since I am focusing on the cosmic-ray puzzle, I can motivate DSR theories following an analogy with the developments which led to the replacement of Galileian relativity with special relativity. In Galileian relativity there is no observer-independent scale, and in fact the dispersion relation is written as $`E=p^2/(2m)`$ (whose structure fulfills the requirements of dimensional analysis without the need for dimensionful coefficients). As experimental evidence in favour of Maxwell equations started to grow, the fact that those equations involve a special velocity scale appeared to require (assuming the Galilei symmetry group should remain unaffected) the introduction of a preferred class of inertial observers (the “ether”). However, in the end we discovered that the Maxwell theory does not require a preferred class of inertial observers. It was wrong to assume that Galileian relativity should apply in all regimes. In the high-velocity regime it must be replaced by special relativity. Special relativity introduces the first observer-independent scale, the velocity scale $`c`$, and its dispersion relation takes the form $`E^2=c^2p^2+c^4m^2`$. As interest in dispersion relations of the type $`c^4m^2=E^2c^2\stackrel{}{p}^2+f(E,\stackrel{}{p}^2;E_p)`$ is starting to grow within the quantum-gravity community, also because of the analysis of cosmic-ray observations, the fact that these dispersion relations involve a special energy scale, $`E_p`$, is leading, as mentioned, to the assumption that a preferred class of inertial observers might have to be introduced. Could it be that this assumption is wrong? Could it be that once again we do not need a preferred class of inertial observers, but rather we need to deform once more the laws of transformation between inertial observers? DSR theories modify special relativity in the exact same sense in which special relativity modified Galileian relativity.

In Ref. , in proposing the idea of DSR theories, I also derived the key features of a first illustrative example (sometimes called “DSR1”) of these theories. This example, whose key characteristic is the dispersion relation

$$2E_p^2\left[\mathrm{cosh}(\frac{E}{E_p})\mathrm{cosh}(\frac{m}{E_p})\right]=\stackrel{}{p}^2e^{E/E_p},$$
(3)
has been analyzed in detail in a series of papers  and is at this point reasonably well understood.

More recently, Maguejio and Smolin proposed  a second example of DSR theory, sometimes called “DSR2”, whose key characteristic is the dispersion relation

$$m^2=\frac{E^2p^2}{(1E_p)^2},$$
(4)
For both of these theories we have now several results \[10-20\] The deformed Lorentz generators that implement (3) (respectively (4)) as observer-independent laws have been explicitly contructed. It has been established that the laws of composition of energy-momentum (needed, for example, when we implement energy-momentum conservation in a collision process) must be Planck-scale modified, just in the same sense that the law of composition of velocity (which is scale-independent in Galileian relativity) must be speed-of-light-scale modified in special relativity. A description of the deformed-boost action in terms of a dependence of energy-momentum on the rapidity parameter $`\xi `$ (the coefficient of a boost generator $`N`$ in the exponentiation $`e^{\xi N}`$ that implements a finite boost transformation) has also been derived.

The relations involving rapidity are particularly useful for a characterization of a DSR theory. It is most convenient to focus on the amount of rapidity needed to take a particle from its rest frame to a frame in which its energy is $`E`$ (and its momentum is $`p(E)`$, which is fixed, once $`E`$ is known, using the dispersion relation and the direction of the boost). In the DSR1 theory one finds

$$\mathrm{cosh}(\xi )=\frac{e^{E/E_p}\mathrm{cosh}\left(m/E_p\right)}{\mathrm{sinh}\left(m/E_p\right)},\mathrm{sinh}(\xi )=\frac{pe^{E/E_p}}{E_p\mathrm{sinh}\left(m/E_p\right)},$$
(5)
while in DSR2 one finds

$$\mathrm{cosh}(\xi )=\frac{E(1m/E_p)}{m(1E/E_p)},\mathrm{sinh}(\xi )=\frac{p(1m/E_p)}{m(1E/E_p)}.$$
(6)
Of course, in the $`E_p^10`$ limit these relations reproduce the corresponding special relativistic relations

$$\mathrm{cosh}(\xi )=\frac{E}{m},$$
(7)
$$\mathrm{sinh}(\xi )=\frac{p}{m}.$$
(8)
These rapidity relations are extremely useful in the analysis of DSR theories. On the basis of these relations one can introduce some useful functions of the physical energy, momentum, mass of a DSR theory. In DSR1 one introduces

$$\frac{(E,m)}{\mu (m)}=\frac{e^{\lambda E}\mathrm{cosh}\left(\lambda m\right)}{\mathrm{sinh}\left(\lambda m\right)},\frac{𝒫(E,p,m)}{\mu (m)}=\frac{pe^{E/E_p}}{E_p\mathrm{sinh}\left(m/E_p\right)},$$
(9)
while in DSR2 one introduces

$$\frac{(E,m)}{\mu (m)}=\frac{E(1m/E_p)}{m(1E/E_p)},\frac{𝒫(E,p,m)}{\mu (m)}=\frac{p(1m/E_p)}{m(1E/E_p)}.$$
(10)
The condition $`\mu ^2=^2𝒫^2`$ is understood everywhere. It is easy to show that in DSR1 and DSR2 the functions $``$ and $`𝒫`$ defined, as described, on the basis of the rapidity relations, transform under the deformed Lorentz boosts (which act on their arguments $`E,p`$) just like special-relativistic energy and momentum would transform under ordinary Lorentz boosts. This allows to obtain most results in DSR1 or DSR2 following a very simple strategy: one does the analysis using the auxiliary momenta $``$ and $`𝒫`$, which are easily handled because they transform under rotations and boosts in the familiar way, and then the DSR result is obtained by substituting in the final formula $``$ and $`𝒫`$ with their expressions as functions $`𝒫(E,p,m)`$, $`(E,m)`$ of the $`E`$ and $`p`$ which describe the physical energy and momentum in the DSR theory.

These useful properties of the functions $`𝒫(E,p,m)`$, $`(E,m)`$ are a consequence of the fact that the symmetries implemented in the schemes DSR1 and DSR2 are actually a nonlinear realization of the Lorentz symmetry group. This simplicity is actually only present in the Lorentz sector: studies of Poincaré-like symmetries that would extended the Lorentz sectors of DSR1 and DSR2 are showing  that this simplifications do not apply to the full Poincaré sector of the theory. The simplifications only apply to the descriptions of Lorentz transformations of energy-momentum space. This is rather obvious from the perspective of applications of the DSR framework in certain types of noncommutative spacetimes: the fact that the spacetime coordinates do not commute introduces (unless the commutators are themselves coordinate-independent) complications for what concerns the description of the product of plane waves (and the associated composition of momenta) and the description of translations. Rotations and boosts are not in a priori conflict with noncommutativity of the coordinates, but they are affected by this noncommutativity through the fact that their action of energy-momentum variables must reflect the new properties of energy-momentum.

Looking further ahead in the research programme on DSR theories one can conceive ways to introduce the second observer-indepedent scale $`E_p`$ such that even the Lorentz sector is affected by severe complexity. However, this possibility goes beyond the scope of the present study. Here I intend to show that exactly a DSR theory of the type described in this section, which in particular relies on a nonlinear realization of the Lorentz group, can be used to avoid the GZK cutoff.

## IV A new DSR theory that solves the cosmic-ray puzzle

In Section II I have discussed how quantum-gravity scenarios with Lorentz-symmetry breaking can solve the cosmic-ray puzzle, at the “price” of introducing a preferred class of inertial observers. In the previous section, Section III, I have discussed the first two examples, DSR1 and DSR2, of DSR theories. Since the DSR framework does not introduce a preferred class of inertial observers, if DSR1 and/or DSR2 were to solve the cosmic-ray puzzle, the solution would indeed not require a preferred class of inertial observers. However, the analysis of the threshold conditions for photopion production in DSR1 and DSR2 does not lead to a solution of the cosmic-ray puzzle. This analysis is actually very simple, because of the properties described above of the functions $`𝒫(E,p,m)`$, $`(E,m)`$. In DSR1 and DSR2 the special relativistic condition for photopion production

$$Eϵ\frac{(m_{prot}+m_\pi )^2m_{prot}^2}{4},$$
(11)
is simply replaced by the condition

$$(E,m_{prot})ϵ\frac{[\mu (m_{prot})+\mu (m_\pi )]^2[\mu (m_{prot})]^2}{4}.$$
(12)
This result is valid to sufficient accuracy for the analysis of the cosmic-ray puzzle; in particular, for the energy of the CMBR photon I have not even introduced the deformation function because CMBR photons have such low energies that (as one can verify explicitly) their description in DSR1 and DSR2 is basically identical to the familiar special relativistic description.

As shown by Eqs. (9),(10), DSR1 and DSR2 do not give the same prediction for the form of the function $`(E,m_{prot})`$, but in both cases one can easily verify that the difference between (12) and (11) leads to a negligibly small modification of the GZK cutoff.

This observation about DSR1 and DSR2 has already been known for some time  and it has led to the expectationSome authors  have given up so completely on the hope of finding a DSR solution for the cosmic-ray puzzle that they arrived at proposing that solutions of the cosmic-ray puzzle would necessarily require two length/energy scales, rather than the single one available in DSR theories. The results I report in this paper provide counterexamples to this conjecture. that DSR theories would in general not provide solutions for the cosmic-ray puzzle, and therefore a kinematical solution of the cosmic-ray puzzle would require the emergence of a preferred class of inertial observers.

I will show here that instead there is a rather rich class of DSR theories that does provide a solution to the cosmic-ray puzzle. My analysis takes off from two related observations:

$``$ The data that presently are at the basis of the cosmic-ray puzzle concern protons with energies in the range from $`10^{19}eV`$ to $`10^{20}eV`$. Taking into account that the proton has mass of $`m_{prot}10^9eV`$ (and the Planck scale is of about $`E_p10^{28}eV`$) it is noteworthy that the paradox emerges just above the scale $`\sqrt{m_{prot}E_p}310^{18}eV`$.

$``$ The relativistic theories DSR1 and DSR2 are deformations of ordinary special relativity which are governed by a single dimensionless ratio, $`E/E_p`$, but this cannot be assumed as a generic feature of DSR theories. Already in ordinary special relativity the ratio $`E/m`$ plays a central role (see, e.g., Eq. (7)), and it is therefore plausible (even natural) that in DSR theories the scales $`E/m`$ and $`E/E_p`$ would combine in such a way that the deformation would be also strongly characterized by the dimensionless quantity $`E^2/(mE_p)`$.

From these two observations the careful reader will be already guessing which type of DSR theories should be able to provide a solution of the cosmic-ray puzzle: theories in which the dimensionless quantity $`E^2/(mE_p)`$ is a strong characteristic of the deformation and that are constructed in such a way that for $`E\sqrt{mE_p}`$ the effects induced by the deformation are negligibly small, while for $`E\sqrt{mE_p}`$ the effects are such that the GZK cutoff is shifted significantly upward with respect to the prediction of ordinary special relativity.

Even just within the simple type of DSR theory reviewed in the previous section (DSR theories in which the rotation/boost generators act on the energy-momentum sector in a way that can be codified through functions of the type $`𝒫(E,p,m)`$, $`(E,m)`$), one can easily find deformations of the action of rotation/boost generators on the energy-momentum space that satisfy these conditions. It is useful to focus on a couple of explicit examples. Let me denote by DSR3a a DSR theory in which the special-relativistic relation (7) is replaced by

$$\mathrm{cosh}(\xi )=\frac{E}{m}\frac{E^3}{m^2E_p}.$$
(13)
and denote by DSR3b a DSR theory in which (7) is replaced by

$$\mathrm{cosh}(\xi )=\frac{E}{m}(2\pi )^{E^2\mathrm{tanh}[m^2E_p^4/E^6]/(mE_p+E^2)}.$$
(14)
These conditions define implicitly the functions $`(E,m)`$ for DSR3a and DSR3b. I don’t even specify here the functions $`𝒫(E,p,m)`$, since their implications for the GZK threshold are negligible. The functions $`𝒫(E,p,m)`$ can be chosen, for example, in such a way as to impose the condition that $`c`$ remains the maximum attainable velocity.

Both in DSR3a, (13), and in DSR3b, (14), one finds an upward shift of the GZK cutoff that is large enough to provide a solution of the cosmic-ray puzzle. In fact, in DSR3a the special-relativistic photopion-production threshold condition (11) is replaced by

$$\left(E\frac{E^3}{m_{prot}E_p}\right)ϵ\frac{(m_{prot}+m_\pi )^2m_{prot}^2}{4},$$
(15)
in which I have neglected other correction terms which are subleading with respect to the term $`E^3/(mE_p)`$, and in DSR3b on finds that, for $`10^{19}eV<E<10^{21}eV`$,

$$\left(E\frac{(2\pi 1)E}{2\pi }\right)ϵ\frac{(m_{prot}+m_\pi )^2m_{prot}^2}{4},$$
(16)
in which I have omitted again some negligibly small $`E_p`$-dependent corrections. The data reported by AGASA provide support for an upward shift of the GZK cutoff which is at least of a factor $`6`$. This shift is clearly realized in (16), which predicts a shift by a factor $`2\pi `$, and in (15), which actually predicts that there cannot be any photopion production involving CMBR photons (for $`E>10^{19}eV`$ the quantity $`E^2/(m_{prot}E_p)`$ is greater than 1).

My two examples, DSR3a and DSR3b, of DSR deformations with dependence on $`E^2/(mE_p)`$ only serve the purpose of illustrating some mechanisms by which the dependence of the DSR deformation on $`E^2/(mE_p)`$ may lead to a relativistic theory that solves the cosmic-ray puzzle (without a preferred class of inertial observers). If this type of scenario is actually adopted by Nature it may well make use of some other type of dependence on $`E^2/(mE_p)`$.

The example DSR3a was chosen in order to show that a deformation with very simple structure can do the required task. A natural modification of the DSR3a scheme could be obtained by adopting a deformation function such that

$$\mathrm{cosh}(\xi )=f(E,m;E_p)\frac{E}{m}\frac{E^3}{m^2E_p},$$
(17)
where $`f`$ is a function such that the approximation described in (17) holds at least for $`10^{19}eV<E<10^{21}eV`$.

The example DSR3b was chosen in order to show that a deformation that leads to a solution of the cosmic-ray puzzle could also be structured in such a way that the new effects are confined in a relatively narrow range of scales. The DSR3b scheme automatically leads to negligible effects for massless particles (at all energies) while for particles with finite mass $`m`$ the effects are nonnegligible only for $`\sqrt{mE_p}<E<(mE_p^2)^{1/3}`$.

The (however ad hoc) deformation adopted in DSR3b also has the property that, even if one assumed that these formulas are applicable also to macroscopic bodies, the structure of the deformation function is such that the new effects are negligible for macroscopic bodies (the effects vanish in the $`m\mathrm{}`$ limit). In the general research programme on DSR theories a key open problem  concerns the DSR description of macroscopic bodies. The available data on macroscopic bodies allow us to exclude that deformations characterized by the dimensionless quantity $`E/E_p`$ be applicable to these macroscopic bodies. Since all DSR theories considered before the present paper were based on $`E/E_p`$ deformations, a key assumption is that the deformation only applies to microscopic particles. One can find  arguments to justify this assumption within DSR theories, but a satisfactory description is still lacking. When the deformation is governed, as here proposed, by the dimensionless quantity $`E^2/(mE_p)`$ and if the deformation is such that it can be neglected in the $`E^2/(mE_p)\mathrm{}`$ limit, as in the DSR3b case, then the deformation is automatically confined to the realm of microscopic particles (for a macroscopic body inevitably $`E^2/(mE_p)1`$), even before taking into account the DSR arguments that may hint at some fundamental reasons for confining the deformation to microscopic physics.

## V Closing remarks

I have shown here that there exist relativistic theories in which the GZK cutoff is shifted significantly upward (enough to explain the cosmic-ray puzzle) but there is no preferred class of inertial observers. My proposal is a new type of DSR theory, and it is therefore based on the idea that, just like a speed-of-light deformation of Galileian transformations turned out to be necessary when we acquired the capability of exploring contexts involving ultra-high velocities, we might need a Planck-scale deformation of Lorentz transformations in order to describe data obtained in ultra-high-energy contexts.

Of course, the fact that it is possible to find a solution of the cosmic-ray puzzle of the type here considered (kinematical, and without a preferred class of inertial observers) should not in any way reduce interest in the other kinematical solutions of the cosmic-ray puzzle. My analysis shows that a kinematical solution is also possible through a deformation of Lorentz symmetry, and therefore without a preferred class of inertial observers, but the ultimate answer will come from observations, and it may well be that Nature hosts a kinematical mechanism of violations of the GZK limit, based on a violation of Lorentz symmetry, and therefore requiring a preferred class of inertial observers. If indeed Planck-scale physics is responsible for the violations of the GZK limit, it is difficult to favour one or the other scenario: we still know very little about quantum gravity, and at present one appears to find equally plausible arguments that favour a Planck-scale violation of Lorentz symmetry  and arguments that favour a Planck-scale deformation of Lorentz symmetry .

In this paper, which is mainly intended for the astrophysics community, I have given a brief overview of DSR concepts and techniques and I have described my new DSR proposal only to the extent that is of interest for the cosmic-ray puzzle. In a paper now in preparation , which will be primarily intended for the quantum-gravity community, I will describe the proposal in detail, working out all aspects of a couple of DSR theories with deformation governed by the quantity $`E^2/(mE_p)`$.

The element of analysis provided here should be sufficient for DSR novices to get started in the task of attempting to figure out if there is a particularly compelling example of the type of DSR theories here proposed, with deformation governed by the dimensionless quantity $`E^2/(mE_p)`$. The deformations DSR3a and DSR3b that I discussed here should be seen only as the starting point for these studies, since, of course, I cannot argue in any way in favour of a special compellingness of those proposals. I needed to formulate some specific proposals in order to illustrate the fact that $`E^2/(mE_p)`$ deformations of DSR type are possible and that they can provide solutions for the cosmic-ray puzzle.

While the search of a conceptually compelling proposal for a $`E^2/(mE_p)`$ deformation of DSR type may prove insightful, of course the ultimate task is to test the idea experimentally. As discussed in detail elsewhere , some planned observations can provide important input for this type of research endeavor. Clearly the key input will come from the Pierre Auger Observatory , which should establish whether or not there are indeed violations of the GZK cutoff and should provide important hints concerning the possibility that the violations be due to deformed kinematics. Concerning the specific structure of the DSR deformation, studies such as the ones planned by the GLAST space telescope  should provide important hints, since they are sensitive  to deformations of the $`E(p)`$ dispersion relation, which is a key feature of a DSR theory .

Among the possible avenues for extending the number of contexts in which the class of DSR theories here proposed may find applications it is worth mentioning, in closing, the scenario for dark energy considered in Refs. . That scenario is based on a specific assumption concerning the structure of the dispersion relation. On the basis of the assumed deformation of the dispersion relation it is also assumed that Lorentz invariance should be broken at the Planck scale, with the associated emergence of a preferred class of inertial observers. The type of structure of the dispersion relation which is adopted in these dark-energy scenarios appears to be well suited for description within the type of DSR theories here proposed. If such a description is achieved one would then have a dark-energy scenario with phenomenological motivation analogous to the one advocated in the studies , but without the assumption of the existence of a preferred class of inertial observers.

## References


format: text

text:
# Intensity-dependent dispersion under conditions of electromagnetically induced transparency in coherently prepared multi-state atoms.

## I Acknowledgements

One of the authors (AG) would like to acknowledge useful discussions with Dr A.B. Matsko (Jet Propulsion Laboratory) and financial support from the EPSRC (UK).

## II Appendix

In this appendix we present the density matrix equations of motion for the 5-state Chain $`\mathrm{\Lambda }`$ atom (M scheme). The equations to be solved are:

$`\dot{\rho }`$ $`=`$ $`{\displaystyle \frac{i}{\mathrm{}}}[,\rho ]+,`$
$`1`$ $`=`$ $`\rho _{g_1g_1}+\rho _{g_2g_2}+\rho _{g_3g_3}+\rho _{e_1e_1}+\rho _{e_2e_2}.`$
For reasons of space we split the Hamiltonian superoperator into smaller sub-blocks, thus

$$=\frac{i}{\mathrm{}}\left(\begin{array}{ccccc}_{11}& _{12}& 0& 0& 0\\ _{21}& _{22}& _{23}& 0& 0\\ 0& _{32}& _{33}& _{34}& 0\\ 0& 0& _{43}& _{44}& _{45}\\ 0& 0& 0& _{54}& _{55}\end{array}\right),$$

where $`_{2j,2j+1}=C_jI\left(5\right)`$, $`_{2j1,2j}=P_j`$ and $`_{ij}=_{ji}`$. $`I\left(5\right)`$ is the $`5\times 5`$ identity matrix and

$`_{11}`$ $`=`$ $`\left(\begin{array}{ccccc}0& P_1& 0& 0& 0\\ P_1& \mathrm{\Delta }_p& C_1& 0& 0\\ 0& C_1& \mathrm{\Delta }_{cp}& P_2& 0\\ 0& 0& P_2& 2\mathrm{\Delta }_p\mathrm{\Delta }_c& C_2\\ 0& 0& 0& C_2& 2\mathrm{\Delta }_{cp}\end{array}\right),`$
$`_{22}`$ $`=`$ $`\left(\begin{array}{ccccc}\mathrm{\Delta }_p& P_1& 0& 0& 0\\ P_1& 0& C_1& 0& 0\\ 0& C_1& \mathrm{\Delta }_c& P_2& 0\\ 0& 0& P_2& \mathrm{\Delta }_{cp}& C_2\\ 0& 0& 0& C_2& \mathrm{\Delta }_p2\mathrm{\Delta }_c\end{array}\right),`$
$`_{33}`$ $`=`$ $`\left(\begin{array}{ccccc}\mathrm{\Delta }_p& P_1& 0& 0& 0\\ P_1& 0& C_1& 0& 0\\ 0& C_1& \mathrm{\Delta }_c& P_2& 0\\ 0& 0& P_2& \mathrm{\Delta }_{cp}& C_2\\ 0& 0& 0& C_2& \mathrm{\Delta }_p2\mathrm{\Delta }_c\end{array}\right),`$
$`_{44}`$ $`=`$ $`\left(\begin{array}{ccccc}2\mathrm{\Delta }_p+\mathrm{\Delta }_c& P_1& 0& 0& 0\\ P_1& \mathrm{\Delta }_{cp}& C_1& 0& 0\\ 0& C_1& \mathrm{\Delta }_p& P_2& 0\\ 0& 0& P_2& 0& C_2\\ 0& 0& 0& C_2& \mathrm{\Delta }_c\end{array}\right),`$
$`_{55}`$ $`=`$ $`\left(\begin{array}{ccccc}2\mathrm{\Delta }_{cp}& P_1& 0& 0& 0\\ P_1& \mathrm{\Delta }_p+2\mathrm{\Delta }_c& C_1& 0& 0\\ 0& C_1& \mathrm{\Delta }_{cp}& P_2& 0\\ 0& 0& P_2& \mathrm{\Delta }_c& C_2\\ 0& 0& 0& C_2& 0\end{array}\right).`$
where $`\mathrm{\Delta }_{cp}=\mathrm{\Delta }_P\mathrm{\Delta }_C`$. The loss operator is

$$=\left(\begin{array}{ccccc}_{11}& _{12}& 0& 0& 0\\ 0& _{22}& 0& 0& 0\\ 0& _{32}& _{33}& _{34}& 0\\ 0& 0& 0& _{44}& 0\\ 0& 0& 0& _{54}& _{55}\end{array}\right),$$

where the off-diagonal blocks $`_{ij}`$ $`\left(ij\right)`$ have all elements zero except the $`\left(ij\right)^{\text{th}}`$ which is $`\mathrm{\Gamma }/2`$. The $`_{ii}`$’s are all diagonal matrices, with non-zero elements

$`_{11}`$ $`=`$ $`(0,\mathrm{\Gamma }/2,\mathrm{\Gamma }_2,\mathrm{\Gamma }_3,\mathrm{\Gamma }_4),`$
$`_{22}`$ $`=`$ $`(\mathrm{\Gamma }/2,\mathrm{\Gamma },\mathrm{\Gamma }/2,\mathrm{\Gamma },\mathrm{\Gamma }_3),`$
$`_{33}`$ $`=`$ $`(\mathrm{\Gamma }_2,\mathrm{\Gamma }/2,0,\mathrm{\Gamma }/2,\mathrm{\Gamma }_2),`$
$`_{44}`$ $`=`$ $`(\mathrm{\Gamma }_3,\mathrm{\Gamma },\mathrm{\Gamma }/2,\mathrm{\Gamma },\mathrm{\Gamma }/2),`$
$`_{55}`$ $`=`$ $`(\mathrm{\Gamma }_4,\mathrm{\Gamma }_3,\mathrm{\Gamma }_2,\mathrm{\Gamma }/2,0),`$
where $`\mathrm{\Gamma }_n`$ is the $`n`$ photon dephasing and $`\mathrm{\Gamma }=\mathrm{\Gamma }_{e_1}=\mathrm{\Gamma }_{e_2}`$ is the total decay rate from either excited state.

A three-dimensional plot showing $`\mathrm{}(\chi )`$ as a function of probe detuning, $`\mathrm{\Delta }_p/\mathrm{\Gamma }`$ and probe Rabi frequency, $`P/\mathrm{\Gamma }`$ for $`P_1=P_2=P`$, $`C_1=C_2=C=\mathrm{\Gamma }/4`$, $`\mathrm{\Gamma }=5.6\mathrm{MHz}`$ and other parameters as above, for the five-state Chain $`\mathrm{\Lambda }`$ system is presented in Fig. 7.


text:
# Quantum transport properties of ultrathin silver nanowires

## Abstract

The quantum transport properties of the ultrathin silver nanowires are investigated. For a perfect crystalline nanowire with four atoms per unit cell, three conduction channels are found, corresponding to three $`s`$ bands crossing the Fermi level. One conductance channel is disrupted by a single-atom defect, either adding or removing one atom. Quantum interference effect leads to oscillation of conductance versus the inter-defect distance. In the presence of multiple-atom defect, one conduction channel remains robust at Fermi level regardless the details of defect configuration. The histogram of conductance calculated for a finite nanowire (seven atoms per cross section) with a large number of random defect configurations agrees well with recent experiment.

PACS: 73.63.Nm, 73.22.-f, 61.46.+w

In recent years, metallic nanowires are of great interest as building blocks for nanoelectronic devices. Since the dimension of the metallic nanowires is comparable to the electron Fermi wavelength, the conductance is quantized in units of $`G_0=2e^2/h`$ . The number of conductance channels is determined by the number of electronic bands crossing the Fermi level ($`E_F`$) and sensitively depends on the nanowire geometry. The effect of conductance quantization and the related high sensitivity lead to potential applications such as single-atom switch , conductor , and chemical sensor .

Most earlier works on the quantum conductance of metallic nanowires are based on the point contacts formed between metal electrodes . With mechanically controllable break junctions  or tip-surface contact  techniques, the statistical histograms of the conductance value for large number of contacts have been recorded. However, the metallic nanowires obtained from nanoscale contact are limited by the short length and structural instability for practical applications. Other fabricating methods, such as reduction of metal compounds , ions irradiation , carbon nanotubes capillary growth , and template-aid synthesis  have been introduced to generate much longer nanowires with well-defined structures. Understanding the transport properties of these long and nearly freestanding metallic nanowires are important for their future applications in nanoelectronics. Recently, Kim’s group has successfully obtained ultrathin single-crystalline silver nanowire arrays . The silver nanowires with 0.4 nm width (only four atoms on the cross section) and $`\mu `$m-scale length are grown inside the pores of organic templates. In this letter, we investigate the transport properties of the ultrathin silver nanowires and discussed the effect of defects on the conductances.

The geometry optimization for the silver nanowires are performed by using ab initio plane-wave ultrasoft pseudopotential method . Both atomic positions and cell parameters for the nanowires (perfect crystalline or with structural defects) were fully relaxed at level of local density approximation (LDA). We adopt the initial configurations proposed in Ref., that is, fcc-like crystalline structure with wire axis along the  crystal direction. The equilibrium structures of a perfect silver nanowire are illustrated in Fig.1. The calculated atomic layer spacing along the wire axis (2.75 Å) agree well with the experimental result . In this one-dimensional periodic structure, the four atoms in the unit cell belong to two inequivalent sites ($`h`$ and $`l`$). Two atoms have lower coordination number ($`l`$: $`Z=6`$); the other two atoms have higher coordination ($`h`$: $`Z=7`$) (see Fig.1(b)).

It is known that the $`4d`$ orbitals in Ag atom act almost like innershell core orbitals . Our ab initio LDA band structure calculations also show that the $`d`$ bands are low-lying and have little influence on the $`s`$ electron bands around Fermi level. Therefore, the conduction electrons in silver should be reasonably described by a $`s`$-orbital tight-binding (TB) model, which had been used to describe the silver clusters up to Ag68 . The $`s`$-orbital TB Hamiltonian is written as

$$H=\underset{i}{}ϵ_i+\underset{<ij>}{}t_{ij}$$

where the on-site energy $`ϵ_i=ϵ_0+\alpha Z_i`$ depends on the site coordination number $`Z_i`$. The hopping integrals $`t_{ij}`$ depend on the interatomic distance $`r_{ij}`$ between site $`i`$ and $`j`$, $`t_{ij}=t_0(d_0/r_{ij})^2`$ where $`d_0`$ is the bulk nearest neighboring distance (2.89 Å), $`t_0`$ is the $`s`$-orbital hopping parameter at the bulk distance $`d_0`$. It was found that parameter set $`t_0`$=0.89 eV and $`\alpha `$=0.26 eV can describe the silver clusters well . The same parameters are used in this work. In Fig.2, the electronic band structures of perfect silver wires near Fermi level by the $`s`$-orbital TB model are compared with those from accurate LDA calculations. Fig.2 clearly shows that the TB model can describe the electronic structures of silver wire within 1 eV of $`E_F`$ reasonably well.

We use the TB Hamiltonian to study the transport properties of silver nanowires via the surface Green’s function matching method . The conductance $`G`$ is given by Landauer-Büttiker formula with the transmission coefficient $`T`$ calculated from the surface Green’s function. To mimic the nanowire of $`\mu `$m-scale length, the length of central nanowire section is chosen to be sufficient long such that the results are independent of the choice of length. The perfect crystalline nanowires of the same size were used as leads in the two sides. Similar tight-binding based surface Green’s function methods have been successfully applied to the transport properties of metallic nanowires and carbon nanotubes .

The calculated conductance of the perfect crystalline silver nanowire with four atoms per unit cell is shown in Fig.3. Three conduction channels at the Fermi level are found, corresponding to the three $`s`$ electronic bands crossing the Fermi level as predicted by both TB and LDA calculations (see Fig.2). As the ultrathin silver nanowire has only few atoms on the cross section, it is inevitable that there will be some structural defects on the wire. Two type of defects, vacancy or adatom are considered in present work. In the case of vacancy, the missing atom can be from either the low-coordination ($`l`$) sites or high-coordination ($`h`$) sites (see Fig.1). Our results (Fig.3) clearly show that one conduction channel is disrupted by a single-atom defect (either vacancy or adatom), independent of the details of defect configurations. This effect can be understood by the scattering of conduction electrons by the defect-induced potential. Similar effect was found in the carbon nanotube .

In addition to the effect of individual defect, we have also considered the situation of two separated single-atom defects. Oscillation of conductance with the defect distance is observed. An example as shown in Fig.4 is the 2-D contour plot of conductance versus defect distance and energy. The oscillation behavior can be understood by quantum interference of the conduction electronic states with oscillation scale related to Fermi wavelength. From our ab initio calculations, the density of conduction electrons in the silver wire shows similar oscillation with the same periodicity. Such quantum interference effects were also found in the carbon nanotubes .

We further investigate the other defect configurations such as multiple-atoms vacancies. In the cases of two-atoms vacancy (either both on the $`h`$ sites or both on the $`l`$ sites), substantial difference is found between different defect configurations (see Fig.5). At Fermi level, one to two conduction channels are disrupted by the two-atoms vacancy defect, sensitively depending on the local coordination environment of the defect site. It is reasonable to find that removing two atoms on the high-coordination site disrupts two conduction channels, while the absence of two atoms on the low-coordination site only reduce one conduction channel at Fermi energy. For individual defect with two adatoms, the result is between the case of two $`h`$ and two $`l`$ vacancy. Further removing one more atom will create a three-atoms vacancy with one atom link. Our calculations show that there is still one conduction channel open. In the earlier experimental studies on metallic contacts, it was usually found that the nanowire retain one conduction channel before breaking . Our results indicate that at least one conduction channel in the silver nanowire is rather robust. Hence, the ultrathin silver wire might serve as good interconnctor in nanoelectronics even with some structural defects formed during the fabrication process.

So far, there is no direct experimental measurement on the conductance of very long ultrathin silver nanowire. Our current studies can be related to a recent experiment on the quantum conductance of short silver nanowires generate by mechanical elongation . Similar to that in Ref., rodlike nanowires along the  direction were observed. The global histogram recorded for the conductance of silver nanowires shows large peaks at 1 $`G_0`$, $``$2.4 $`G_0`$, and $``$4 $`G_0`$ . One possible atomic structure for the nanowire in their experiment is shown in Fig.1(c) with seven atoms per cross section, which can be built from the thinner wire in Fig.1(b). Using the same computational scheme, we have calculated the quantum conductance of such finite nanowire with seven unit cells in the central section ($``$ 2nm, comparable to experimental length). Without any defect, the nanowire has five conduction channels. The conductance drops to 4 $`G_0`$ with one single-atom defect, similar to that in the case of 4-atoms cross section nanowire discussed above. Our LDA calculations show four robust $`s`$ bands crossing the Fermi level, in consistent with TB results.

To compare with experimental conductance histogram, we generate a large number ($``$ 500) of random defect configurations for the finite 7-atom cross section wire and calculate the conductance at Fermi level. For each configuration, the defects are created by randomly selecting the location of the vacancies. Normalized counts of conductance are shown in Fig.6. Three major peaks at 1 $`G_0`$, 2.6 $`G_0`$, and 4 $`G_0`$ are found, in agreement with the experimental results. We find that the locations of these three peaks are insensitive to the length of finite nanowire length and total number of defect configurations. These features can be understood by the above discussions on the effects of various defects on crystalline nanowire. The peak at 4 $`G_0`$ corresponds to the case of one or few singe-atom defects that disrupt only one conduction channel from the perfect wire. The dominant peak at 1 $`G_0`$ could be associated with the presence of several multi-atoms defects, which disrupt the quantum conductance so dramatically that only one conduction channel is left. Between the two extreme cases, a peak at $``$ 2.5 $`G_0`$ is found both experimentally and theoretically. In our calculations, four less pronounced peaks around 1.5 $`G_0`$ and 3.4 $`G_0`$ are also obtained, which were not observed experimentally . These peaks may correspond to the energetically less-favorate configurations.

In summary, three conduction channels are obtained for the crystalline silver nanowire with four atoms per cross section, corresponding to three $`s`$ bands crossing the Fermi level. One conductance channel is easily disrupted by an individual single-atom defect (vacancy or adatom), independent of the defect configurations. With two separated single-atom defects, quantum interference leads to oscillation of conductance versus the defect distance. In the presence of multiple-atoms defects, one conduction channel (at Fermi energy) remains robust. The calculated histogram of conductance for a finite silver nanowires (seven atoms per cross section, 2 nm long) with random defect configurations compares well with experiment. Our results show that the ultrathin silver wires, even with some structural defects, are excellent candidates in nanoelectronics.

This work is supported by the University Research Council of University of North Carolina at Chapel Hill, Office of Naval Research Grant No. N00014-98-1-0597 and NASA Ames Research Center. We acknowledge computational support from the North Carolina Supercomputer Center.
E-mail: jpl@physics.unc.edu


text:
# The Catalan matroid.

## 1 Introduction

A Dyck path of length $`2n`$ is a path in the plane from $`(0,0)`$ to $`(2n,0)`$, with steps $`(1,1)`$ and $`(1,1)`$, that never passes below the $`x`$-axis. It is a classical result (see for example \[8, Corollary 6.2.3.(iv)\]) that the number of Dyck paths of length $`2n`$ is equal to the Catalan number $`C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$.

Each Dyck path $`P`$ defines an *up-step set*, consisting of the integers $`i`$ for which the $`i`$-th step of $`P`$ is $`(1,1)`$. The starting point of this paper is Theorem 2.1. It states that the collection of up-step sets of all Dyck paths of length $`2n`$ is the collection of bases of a matroid. Most of this paper is devoted to the study of this matroid, which we call the *Catalan matroid*, and denote $`𝐂_n`$.

Section 2 starts by proving Theorem 2.1. As we know, there are many equivalent ways of defining a matroid: in terms of its rank function, its independent sets, its flats, and its circuits, among others. The rest of Section 2 is devoted to describing some of these definitions for $`𝐂_n`$.

In Section 3, we compute the Tutte polynomial of the Catalan matroid. We find that it enumerates Dyck paths according to two simple statistics. Some nice enumerative results are derived as a consequence.

In Section 4, we generalize our construction of $`𝐂_n`$ to a wider class of matroids, which we call *shifted matroids*. Their name is justified by a result of Klivans, who discovered them independently, proving that they are precisely those matroids whose independence complex is a shifted complex. We then generalize our construction in a different direction to obtain, for any finite poset $`P`$ and any order ideal $`I`$, a shifted family of sets. This family is not always the set of bases of a matroid.

Finally, in Section 5 we address the question of representability of the matroids we have constructed. We show that the Catalan matroid, and more generally any shifted matroid, is representable over $``$. In the opposite direction, we show that $`𝐂_n`$ is *not* representable over the finite field $`𝔽_q`$ if $`qn2`$.

Throughout this paper, we will assume some familiarity with the basic concepts of matroid theory. For instance, Chapter 1 of  should be enough to understand most of the paper. We also highly recommend Section 6.2 and exercises 6.19-6.37 of  for an encyclopedic treatment of Catalan numbers and related topics.

## 2 The matroid

Let $`n`$ be a fixed positive integer. Consider all paths in the plane which start at the origin and consist of $`2n`$ steps, where each step is either $`(1,1)`$ or $`(1,1)`$. We will call such steps *up-steps* and *down-steps*, respectively. From now on, the word *path* will always to refer to a path of this form.

Such paths are in bijection with subsets of $`[2n]`$. To each path $`P`$, we can assign the set of integers $`i`$ for which the $`i`$-th step of $`P`$ is an up-step. We call this set the *up-step set* of $`P`$. Conversely, to each subset $`A[2n]`$, we can assign the path whose $`i`$-th step is an up-step if and only if $`i`$ is in $`A`$.

To simplify the notation later on, we will omit the brackets when we talk about subsets of $`[2n]`$. We will also use subsets of $`[2n]`$ and paths interchangeably. For example, for $`n=3`$, the path $`13`$ will be the path with up-steps at steps $`1`$ and $`3`$, and down-steps at steps $`2,4,5`$ and $`6`$.

A useful statistic to keep track of will be the *height of path $`P`$ at $`x`$*; *i.e.*, the height of the path after taking its first $`x`$ steps. We shall denote it $`ht_P(x)`$; it is equal to $`2|P_x|x`$, where $`P_x`$ denotes the set of elements of $`P`$ which are less than or equal to $`x`$. Also, let $`minht_P`$ and $`maxht_P`$ be the minimum and maximum heights that $`P`$ achieves, respectively.

###### Theorem 2.1

Let $`_n`$ be the collection of up-step sets of all Dyck paths of length $`2n`$. Then $`_n`$ is the collection of bases of a matroid.

*Proof.* We need to check the two axioms for the collection of bases of a matroid:

1. $`_n`$ is non-empty.
2. If $`A`$ and $`B`$ are members of $`_n`$ and $`aAB`$, then there is an element $`bBA`$ such that $`(Aa)b_n`$.

The first axiom is satisfied trivially, so we only need to check the second one. Let $`A`$ and $`B`$ be members of $`_n`$, and let $`aAB`$. First we will describe those $`k`$ not in $`A`$ for which $`Aak_n`$, and then we will show that the smallest element of $`BA`$ is one of them.

For $`kA`$, consider the path $`Aak`$, which is a very slight deformation of the path $`A`$. It still consists of $`n`$ up-steps and $`n`$ down-steps; to determine if it is a Dyck path, we just need to check whether it goes below the $`x`$-axis. There are two cases to consider.

The first case is that $`k<a`$. In this case, for $`kc<a`$, we have that $`ht_{Aak}(c)=ht_A(c)+\mathrm{\hspace{0.17em}2}`$. For all other values of $`c`$, we have that $`ht_{Aak}(c)=ht_A(c)`$. Hence the path $`Aak`$ stays above the path $`A`$, so it is Dyck.

The second case is that $`a<k`$. Here, for $`ac<k`$, we have that $`ht_{Aak}(c)=ht_A(c)\mathrm{\hspace{0.17em}2}`$. For all other values of $`c`$, we have that $`ht_{Aak}(c)=ht_A(c)`$. Therefore, the path $`Aak`$ is Dyck if and only if $`ht_A(c)2`$ for all $`ac<k`$.

With that simple analysis, we can show that $`Aab_n`$, where $`b`$ is the smallest element of $`BA`$. If $`b<a`$, then we are done by the first case of our analysis. Otherwise, consider an arbitrary $`c`$ with $`ac<b`$. There are no elements of $`BA`$ less than or equal to $`c`$; so up to the $`c`$-th step, every step which is an up-step in $`B`$ is also an up-step in $`A`$. Furthermore, the $`a`$-th step is a down-step in $`B`$ and an up-step in $`A`$. Therefore, $`ht_A(c)ht_B(c)+\mathrm{\hspace{0.17em}2}2`$. This concludes our proof.

A matroid is uniquely determined by its collection of bases. Therefore Theorem 2.1 defines a matroid, which will call *the Catalan matroid of rank $`n`$* (or simply *the Catalan matroid*), and denote by $`𝐂_n`$. This paper is mostly devoted to the study of this matroid.

###### Proposition 2.2

The rank function of $`𝐂_n`$ is given by

$$r(A)=n+minht_A/2$$

for each $`A[2n]`$.

*Proof.* Fix a subset $`A[2n]`$, and let $`minht_A=y`$, where $`y`$ is a non-negative integer. Also, let $`x`$ be the smallest integer such that $`ht_A(x)=minht_A`$.

Recall that the rank of a subset $`A`$ of $`[2n]`$ is equal to the largest possible size of an intersection $`AB`$, where $`B`$ is a basis of $`𝐂_n`$.

The path $`A`$ is at height $`y`$ after taking $`|A_x|`$ up-steps and $`x|A_x|`$ down-steps, so $`|A_x|=(xy)/2`$. Also, for any basis $`B`$, we have that $`|B_{>x}|nx/2`$, since $`ht_B(x)0`$. Hence

$`|AB|`$ $`=`$ $`|(AB)_x|+|(AB)_{>x}|`$
$``$ $`|A_x|+|B_{>x}|ny/2.`$
We conclude that $`r(A)n+minht_A/2`$.

Now we need a basis $`B`$ with $`|AB|=n+minht_A/2`$. We construct it as follows. First, add to $`A`$ the smallest $`a=y/2`$ numbers that it is missing, to obtain the set $`A^{}`$. Then $`ht_A^{}(x)=2ay0`$; in fact, it is clear that the path $`A^{}`$ never crosses the $`x`$-axis. Let $`|A|=n+h`$ for some integer $`h`$; then $`ht_A(2n)=2h`$ and $`ht_A^{}(2n)=2h+2a`$. Now remove from $`A^{}`$ the largest $`h+a`$ numbers that it contains, to obtain the set $`B`$. It is again easy to see that the path $`B`$ never crosses the $`x`$-axis, and ends at $`(2n,0)`$. So $`B`$ is Dyck, and

$$|AB|=|AA^{}|(h+a)=|A|(h+a)=na$$

as desired.

Now that we know the rank function of $`𝐂_n`$, we can describe several important classes of subsets of the matroid. We will only provide a proof for the description of the class of flats; the remaining proofs are similar in flavor. The interested reader may want to complete the details to get better acquainted with the matroid $`𝐂_n`$.

###### Proposition 2.3

The flats of $`𝐂_n`$ are the subsets $`A[2n]`$ such that

1. $`minht_A`$ is odd, and
2. if $`ht_A(x)=minht_A`$, then $`\{x+1,\mathrm{},2n\}A`$.

*Proof.* Let $`A`$ be a flat of $`𝐂_n`$, and let $`x`$ be such that $`ht_A(x)=minht_A`$. If some integer $`y`$ with $`x+1yn`$ was not in $`A`$, then we would clearly have $`minht_{Ay}=minht_A`$ and thus $`r(Ay)=r(A)`$, contradicting the assumption that $`A`$ is a flat. Therefore, any flat must satisfy condition *(ii)*.

Also, if we had a flat $`A`$ with $`minht_A=2h`$ achieved at $`ht_A(x)`$, then we would have $`xA`$, and $`minht_{Ax}=2h+1`$ would be achieved at $`ht_{Ax}(x1)`$. We would then have $`r(Ax)=r(A)`$, again a contradiction. So any flat $`A`$ must also satisfy condition *(i)*.

Conversely, assume that $`A`$ satisfies conditions *(i)* and *(ii)*. Let $`minht_A=(2k+1)`$, which can only be achieved once, say at $`ht_A(x)`$. Any $`y`$ which is not in $`A`$ must be less than or equal to $`x`$; and we have $`minht_{Ay}=(2k1)`$ if $`y<x`$, or $`minht_{Ay}=2k`$ if $`y=x`$. In either case, $`r(Ay)=r(A)+1`$. This completes the proof.

###### Proposition 2.4

The independent sets of $`𝐂_n`$ are the subsets $`A[2n]`$ such that $`minht_A=ht_A(2n)`$.

###### Proposition 2.5

The spanning sets of $`𝐂_n`$ are the subsets $`A[2n]`$ such that $`minht_A=0`$.

###### Proposition 2.6

The circuits of $`𝐂_n`$ are the subsets $`A[2n]`$ of the form $`A=\{2k,2k+b_1,\mathrm{},2k+b_{nk}\}`$, for some positive integer $`kn`$ and some Dyck path $`\{b_1,\mathrm{},b_{nk}\}`$ of length $`2(nk)`$.

###### Proposition 2.7

The bonds of $`𝐂_n`$ are the subsets $`A[2n]`$ such that

1. $`maxht_A=1`$, and
2. if $`ht_A(x)=1`$, then $`A`$ has no elements greater than $`x`$.

We complete this section with an observation which is interesting in itself, and will also be important to us in section 3.

###### Proposition 2.8

The Catalan matroid is self-dual.111We follow Oxley  in calling a matroid $`M`$ *self-dual* if $`MM^{}`$. It is worth mentioning, however, that some authors reserve the term ‘self-dual’ for matroids $`M`$ such that $`M=M^{}`$.

*Proof.* Say $`B=\{b_1,\mathrm{},b_n\}`$ is a basis of $`𝐂_n`$, and let $`[2n]B=\{c_1,\mathrm{},c_n\}`$ be the corresponding basis of the dual matroid $`𝐂_n^{}`$. Then $`\{2n+1c_n,\mathrm{},2n+1c_1\}`$ is a Dyck path; in fact, it is the path obtained by reflecting the Dyck path $`B`$ across a vertical axis. So the bases of $`𝐂_n^{}`$ are simply the up-step sets of all Dyck paths of length $`2n`$, under the relabeling $`x2n+1x`$. Thus $`𝐂_n^{}𝐂_n`$.

## 3 The Tutte polynomial

Given a matroid $`M`$ over a ground set $`S`$, its Tutte polynomial is defined as:

$$T_M(q,t)=\underset{AS}{}(q1)^{r(S)r(A)}(t1)^{|A|r(A)}.$$

For our purposes, it is more convenient to define the Tutte polynomial in terms of the internal and external activity of the bases. We recall this definition now.

We first need to fix an arbitrary linear ordering of $`S`$.

For any basis $`B`$ and any element $`eB`$, the set $`Be`$ contains a unique circuit. If $`e`$ is the smallest element of that circuit with respect to our fixed linear order, then we say that $`e`$ is *externally active* with respect to $`B`$. The number of externally active elements with respect to $`B`$ is called the *external activity* of $`B`$; we shall denote it by $`e(B)`$.

Dually, for any basis $`B`$ and any element $`iB`$, the set $`SBi`$ contains a unique bond. If $`i`$ is the smallest element of that bond, then we say that $`i`$ is *internally active* with respect to $`B`$. The number of internally active elements with respect to $`B`$ is called the *internal activity* of $`B`$; we shall denote it by $`i(B)`$.222The internally active elements with respect to a basis $`B`$ of $`M`$ are precisely the externally active elements with respect to the basis $`SB`$ of the dual matroid $`M^{}`$. That is why we say that internal activity and external activity are dual concepts.

###### Proposition 3.1

(Crapo, ) For any matroid $`M`$ and any linear order of its ground set,

$$T_M(q,t)=\underset{B\mathrm{basis}}{}q^{i(B)}t^{e(B)}.$$

We will use Proposition 3.1 to study the Tutte polynomial of the Catalan matroid. The first thing to do is to fix a linear order of its ground set, $`[2n]`$. We will use the most natural choice: $`1<2<\mathrm{}<2n`$. Now we compute the internal and external activity of each basis of $`𝐂_n`$.

###### Lemma 3.2

The internal activity of a Dyck path $`B`$ is equal to the number of up-steps that $`B`$ takes before its first down-step.

*Proof.* Let $`iB`$. The path $`[2n]B`$ never goes above height $`0`$; the path $`[2n]Bi`$ goes up to height $`2`$. Let $`j`$ be the smallest integer such that $`ht_{[2n]Bi}(j)=1`$. Clearly $`ji`$.

Let $`D`$ be the unique bond of $`𝐂_n`$ which can be obtained by deleting some elements of $`[2n]Bi`$. We cannot delete any element less than or equal to $`j`$, or else the resulting path will not reach height $`1`$. We must delete any element larger than $`j`$ by Proposition 2.7. So $`D=([2n]B)_j`$.

Therefore, $`i`$ is the smallest element of $`D`$ if and only if $`B`$ contains all of $`1,2,\mathrm{},i1`$. This completes the proof.

###### Lemma 3.3

The external activity of a Dyck path $`B`$ is equal to the number of positive integers $`x`$ for which $`ht_B(x)=0`$.

*Proof.* Let $`eB`$. The path $`Be`$ ends at height $`2`$; let $`2k1`$ be the largest integer such that $`ht_{Be}(2k1)=1.`$ Clearly $`2k1<e`$.

We start by showing that the unique circuit $`C`$ of $`𝐂_n`$ contained in $`Be`$ is $`(Be)_{2k}`$.

Since $`CBe`$, we have that $`ht_C(2n)ht_C(2k1)ht_{Be}(2n)ht_{Be}(2k1)=1`$. Equality holds if and only if every up-step of $`Be`$ after the $`(2k1)`$-th is also an up-step of $`C`$; *i.e.*, when $`(Be)_{2k}=C_{2k}`$.

But it is clear from Proposition 2.6 that $`ht_C(2n)minht_C=1`$, and that $`minht_C`$ is only achieved at $`ht_C(\mathrm{min}C1)`$. So the above inequality can only hold if $`\mathrm{min}C=2k`$. Thus $`C=C_{2k}=(Be)_{2k}`$ as desired.

Now we know that $`\mathrm{min}C=2k`$, so $`e`$ is externally active if and only if $`e=2k`$. If $`ht_B(e)=0`$, this is clearly the case. On the other hand, if $`ht_B(e)1`$, then $`ht_{Be}(e1)=ht_B(e1)2`$, so this is not the case. This completes the proof.

###### Theorem 3.4

For a Dyck path $`P`$, let $`a(P)`$ denote the number of up-steps that $`P`$ takes before its first down-step, and let $`b(P)`$ denote the number of positive integers $`x`$ for which $`ht_P(x)=0`$

Then the Tutte polynomial of the Catalan matroid $`𝐂_n`$ is equal to

$$T_{𝐂_n}(q,t)=\underset{P\mathrm{Dyck}}{}q^{a(P)}t^{b(P)},$$

where the sum is over all Dyck paths of length $`2n`$.

*Proof.* This follows immediately from Proposition 3.1 and Lemmas 3.2 and 3.3.

###### Corollary 3.5

The polynomial

$$\underset{P\mathrm{Dyck}}{}q^{a(P)}t^{b(P)},$$

is symmetric in $`q`$ and $`t`$.

*Proof.* It is well-known that, for any matroid $`M`$, we have $`T_M^{}(q,t)=T_M(t,q)`$. The result follows from Proposition 2.8 and Theorem 3.4.

It is a known fact that the statistics $`a(P)`$ and $`b(P)`$ are equidistributed over the set of Dyck paths of length $`2n`$. The number of paths with $`a(P)=k`$ and the number of paths with $`b(P)=k`$ are both equal to $`\frac{k}{2nk}\left(\genfrac{}{}{0pt}{}{2nk}{n}\right)`$. For the first equality, see for example ; for the second, see \[5, equation (7)\].

Corollary 3.5 was also discovered independently by James Haglund . It is not difficult to prove it directly; in fact, it will be an immediate consequence of our next theorem.

###### Theorem 3.6

Let $`C(x)=\frac{1\sqrt{1\mathrm{\hspace{0.17em}4}x}}{2}=C_0+C_1x+C_2x^2+\mathrm{}`$ be the generating function for the Catalan numbers. Then

$$\underset{n0}{}T_{𝐂_n}(q,t)x^n=\frac{1+(qtqt)xC(x)}{1qtx+(qtqt)xC(x)}.$$

*Proof.* A Dyck path $`P`$ of length $`2n2`$ can be decomposed uniquely in the standard way: it starts with an up-step, then it follows a Dyck path $`P_1`$ of length $`2r`$, then it takes a down-step, and it ends with a Dyck path $`P_2`$ of length $`2s`$, for some non-negative integers $`r,s`$ with $`r+s=n1`$. More precisely, and necessarily more confusingly,

$$P=\{1,1+p_1,1+p_2,\mathrm{},1+p_r,2r+2+q_1,2r+2+q_2,\mathrm{},2r+2+q_s\}$$

for some Dyck paths $`\{p_1,\mathrm{},p_r\}`$ and $`\{q_1,\mathrm{},q_s\}`$ with $`r+s=n1`$.

It is clear that in this decomposition we have $`a(P)=a(P_1)+1`$ and $`b(P)=b(P_2)+1`$. Therefore

$`T_{𝐂_n}(q,t)`$ $`=`$ $`{\displaystyle \underset{r+s=n1}{}}{\displaystyle \underset{P_1_r}{}}{\displaystyle \underset{P_2_s}{}}q^{a(P_1)+1}t^{b(P_2)+1}`$
$`=`$ $`qt{\displaystyle \underset{r+s=n1}{}}T_{𝐂_r}(q,1)T_{𝐂_s}(1,t)`$
for $`n1`$; so if we write $`𝐓(q,t,x)=_{n0}T_{𝐂_n}(q,t)x^n`$, we have

$$𝐓(q,t,x)=1+qtx𝐓(q,1,x)𝐓(1,t,x).$$
(1)
Now observe that $`𝐓(1,1,x)=C(x)`$. Setting $`q=1`$ in (1) gives a formula for $`𝐓(1,t,x)`$, and setting $`t=1`$ gives a formula for $`𝐓(q,1,x)`$. Substituting these two formulas back into (1), we get the desired result.

## 4 Shifted matroids

We now generalize our construction of $`𝐂_n`$ to a larger family of matroids, which we call *shifted matroids*. There is one shifted matroid for each non-empty set $`S=\{s_1<\mathrm{}<s_n\}`$ of positive integers, which we shall denote $`\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$

###### Theorem 4.1

Let $`S=\{s_1<\mathrm{}<s_n\}`$ be a set of positive integers, and let $`_S`$ be the collection of sets $`\{a_1<\mathrm{}<a_n\}`$ such that $`a_1s_1,\mathrm{},a_ns_n`$. Then $`_S`$ is the collection of bases of a matroid $`\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$.

*Proof.* Once again, as in the proof of Theorem 2.1, axiom (B1) is trivial, since $`SB_S`$. We need to check axiom (B2). Let $`A=\{a_1<\mathrm{}<a_n\}`$ and $`B=\{b_1<\mathrm{}<b_n\}`$ be in $`B_S`$, and let $`a_xAB`$. We claim that, if $`b_y`$ is the smallest element in $`BA`$, then $`Aa_xb_y_S`$.

Let $`i`$ be the integer such that $`a_i<b_y<a_{i+1}`$. (If $`b_y<a_1`$ then the claim is trivially true, since we are replacing $`a_x`$ in $`A`$ with a number smaller than it. If $`b_y>a_n`$ then set $`i=n`$.) We may assume that $`ix`$; if that was not the case, then we would have $`b_y<a_{i+1}a_x`$, and the claim would be trivial. We then have

$$Aa_xb_y=\{a_1<\mathrm{}<a_{x1}<a_{x+1}<\mathrm{}<a_i<b_y<a_{i+1}<\mathrm{}<a_n\}$$

and we have $`n`$ inequalities to check.

The first $`x1`$ and the last $`ni`$ of these do not require any extra work: we already know that $`a_ks_k`$ for $`1kx1`$ and for $`i+1kn`$.

For each value of $`k`$ with $`xki1`$, we need to check that $`a_{k+1}s_k`$. If $`ky`$, we have $`a_{k+1}a_i<b_yb_ks_k`$. Otherwise, if $`k<y`$, proceed as follows. Since $`b_y`$ is the smallest element of $`B`$ which is not in $`A`$, and $`a_x`$ is not in $`B`$, the numbers $`b_1,\mathrm{},b_k`$ must all be somewhere in the list $`a_1,\mathrm{},a_{x1},a_{x+1},\mathrm{}a_i`$. Therefore the $`k`$-th smallest number of this list, $`a_{k+1}`$, must be less than or equal to $`b_k`$, which is less than or equal to $`s_k`$.

Finally, we need to check that $`b_ys_i`$. Since the numbers $`b_1,\mathrm{},b_{y1}`$ all appear in the list $`a_1,\mathrm{},a_{x1},a_{x+1},\mathrm{},a_k,\mathrm{},a_i`$, we have $`y1i1`$. Therefore $`b_ys_ys_i`$.

A path $`\{a_1<\mathrm{}<a_n\}`$ is Dyck if and only if, for each $`i`$ with $`1in`$, the $`i`$-th up-step comes before the $`i`$-th down-step; that is, if and only if $`a_i2i+1`$. Therefore, the Catalan matroid $`𝐂_n`$ is exactly the shifted matroid $`\mathrm{𝐒𝐌}(1,3,5,\mathrm{},2n1)`$, with an additional loop $`2n`$.

Recall that an *abstract simplicial complex* $`\mathrm{\Delta }`$ on $`[n]`$ is a family of subsets of $`[n]`$ (called *faces*) such that if $`G\mathrm{\Delta }`$ and $`FG`$, then $`F\mathrm{\Delta }`$. A simplicial complex $`\mathrm{\Delta }`$ is *shifted* if, for any face $`F\mathrm{\Delta }`$ and any pair of elements $`i<j`$ such that $`iF`$ and $`jF`$, the subset $`Fji`$ is also a face of $`\mathrm{\Delta }`$.

The family of independent sets of a matroid $`M`$ is always a simplicial complex, called the *independence complex* of $`M`$. For shifted matroids, we have the following simple observation.

###### Proposition 4.2

The independence complex of a shifted matroid $`\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$ is a shifted complex.

*Proof.* If $`F[s_n]`$ is independent, it is contained in some basis $`B`$. Now assume that we have two elements $`i<j`$ such that $`iF`$ and $`jF`$, and let $`G=Fji`$. If the basis $`B`$ contains $`i`$, then it contains $`G`$. Otherwise, $`Bji`$ is also a basis: for any $`1kn`$, its $`k`$-th smallest is less than or equal to the $`k`$-th smallest element of $`B`$, which is less than or equal to $`s_k`$. This basis contains $`G`$. In both cases, we conclude that $`G`$ is independent.

In , Klivans characterizes *shifted matroid complexes*: shifted complexes which are the independence complex of a matroid. Her result and ours were discovered almost simultaneously. When we sat down to discuss them, we realized that the matroids that arise in her characterization are precisely the ones in our construction. This is why they were baptized “shifted matroids”.

###### Proposition 4.3

(Klivans, ) If the independence complex of a loop-less matroid $`M`$ is a shifted complex, then $`M\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$ for some positive integers $`s_1<\mathrm{}<s_n`$.

Theorem 4.1 and Propositions 4.2 and 4.3 have a nice application to Young tableaux. Recall that a *partition* $`\lambda =(\lambda _1,\mathrm{},\lambda _k)`$ of $`n`$ is a weakly decreasing sequence of positive integers which add up to $`n`$. We associate to it a *Young diagram*: a left-justified array of unit squares, which has $`\lambda _i`$ squares on the $`i`$-th row from top to bottom.333This is the English way of drawing Young diagrams; francophones draw them with $`\lambda _i`$ squares on the $`i`$-th row from bottom to top. A *standard Young tableaux* is a placement of the integers $`1,\mathrm{},n`$ in the squares of the Young diagram, in such a way that the numbers are increasing from left to right and from top to bottom.

These definitions will be sufficient for our purposes. For a much deeper treatment of the theory of Young tableaux, we refer the reader to .

###### Corollary 4.4

Let $`\lambda `$ be a partition. Define the *first row set* of a standard Young tableau $`T`$ of shape $`\lambda `$ to be the set of entries which appear in the first row of $`T`$. Then the collection of first row sets of all standard Young tableaux of shape $`\lambda `$ is the collection of bases of a shifted matroid.

*Proof.* Let $`\lambda ^{}=(\lambda _1^{},\mathrm{},\lambda _n^{})`$ be the conjugate partition of $`\lambda `$, so $`\lambda _i^{}`$ is the number of squares on the $`i`$-th column of the Young diagram of $`\lambda `$. Let $`s_i=1+\lambda _1^{}+\mathrm{}+\lambda _{i1}^{}`$ for $`1in`$.

Let $`\{b_1<\mathrm{}<b_n\}`$ be the first row set of a standard Young tableau $`T`$ of shape $`\lambda `$. The first entry on the $`i`$-th column of $`T`$ is $`b_i`$; it is smaller than every entry to its southeast. There are only $`\lambda _1^{}+\mathrm{}+\lambda _{i1}^{}`$ cells which are not to its southeast, so $`b_is_i`$.

Conversely, if $`B=\{b_1<\mathrm{}<b_n\}`$ is such that $`b_is_i`$ for $`1in`$, then we can construct a standard Young tableau with first row set $`B`$. To do it, we first put the elements of $`B`$ in order on the first row of $`\lambda `$. Then we put the remaining numbers from $`1`$ to $`|\lambda |`$ on the remaining cells going in order down the columns, starting with the leftmost column. The inequalities $`b_is_i`$ guarantee that this process does indeed give a Young tableau $`T`$.

It follows that the collection in question is simply the collection of bases of the matroid $`\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$.

We might try to generalize Corollary 4.4, replacing the first row of $`\lambda `$ by any partition $`\mu \lambda `$. Define the *$`\mu `$-set* of a standard Young tableau $`T`$ of shape $`\lambda `$ to be the set of entries which appear in the sub-shape $`\mu `$ in $`T`$.

It is not too difficult to see that we do not always get the collection of bases of a matroid with this construction. However, we can still say something interesting.

###### Proposition 4.5

Let $`\mu \lambda `$ be partitions. Then the collection $`_{\lambda \mu }`$ of $`\mu `$-sets of all standard Young tableau of shape $`\lambda `$ is a shifted family.

*Proof.* In fact, we prove something more general. Let $`P`$ be a partially ordered set, or *poset*, of $`n`$ elements. Recall that a subset $`I`$ of $`P`$ is an *order ideal* of $`P`$ if, for any pair of elements $`x,yP`$ with $`x<_Py`$ and $`yI`$, we also have $`xI`$. Also recall that a *linear extension* of $`P`$ is a bijection $`f:P[n]`$ such that $`i<_Pj`$ implies that $`f(i)<f(j)`$. For more information on posets, we refer the reader to \[7, Chapter 3\].

Define the *I-set* of a linear extension $`f`$ of $`P`$ to be the set $`\{f(i):iI\}`$.

###### Proposition 4.6

Let $`P`$ be a poset of $`n`$ elements, and let $`I`$ be an order ideal of $`P`$ . Then the collection $`_{P,I}`$ of $`I`$-sets of all linear extensions of $`P`$ is a shifted family.

*Proof of Proposition 4.6.* We need to check that if we have a set $`B_{P,I}`$ and a pair of numbers $`a<b`$ such that $`aB`$ and $`bB`$, then $`Bba_{P,I}`$. It is enough to show this for $`a=b1`$; the general case will then follow by induction on $`ba`$.

So let $`f`$ be a linear extension of $`P`$ with $`I`$-set $`B`$, and let $`bB`$ be such that $`b1B`$. Let $`b=f(i)`$ and $`b1=f(p)`$ where $`iI`$ and $`pPI`$. Let $`g:P[n]`$ be defined by switching the values of $`f`$ at $`i`$ and $`p`$ ; *i.e.*,

$$g(x)=\{\begin{array}{cc}f(x)\hfill & \text{if }x\{i,p\}\hfill \\ b1\hfill & \text{if }x=i\hfill \\ b\hfill & \text{if }x=p\hfill \end{array}$$
(2)
We claim that $`g`$ is also a linear extension for $`P`$. An important observation is that $`i`$ and $`p`$ are incomparable in $`P`$. If we had $`i<p`$, then we would have $`b=f(i)<f(p)=b1`$. If we had $`i>p`$, then $`iI`$ would imply $`pI`$.

To check that $`f`$ is a linear extension, we need to check that $`f(i)=b`$ satisfies several inequalities: it must be greater than all the values that $`f`$ takes on $`P_{<i}`$, and less than all the values that $`f`$ takes on $`P_{>i}`$. But $`b`$ is never compared to $`b1`$ here, since $`p`$ and $`i`$ are incomparable. Therefore, $`b1`$ also satisfies all those inequalities that $`b`$ needs to satisfy.

Similarly, $`b1`$ must be greater than all the values that $`f`$ takes on $`P_{<p}`$ and less than all the values that $`f`$ takes on $`P_{>p}`$. The number $`b`$ also satisfies these inequalities.

So we can switch the values of $`f(i)`$ and $`f(p)`$, and the resulting function $`g`$ will also be a linear extension of $`P`$. Also, the $`I`$-set of $`g`$ is $`Bb(b1)`$. This concludes the proof.

Now, to prove Proposition 4.5, partially order the cells of $`\lambda `$: cell $`i`$ is less than cell $`j`$ in $`P_\lambda `$ if and only if cell $`i`$ is northeast of cell $`j`$ in $`\lambda `$. The cells of $`\mu `$ define an order ideal $`I_\mu `$ of this poset $`P_\lambda `$, and $`_{\lambda \mu }=_{P_\lambda ,I_\mu }.`$ Now use Proposition 4.6.

## 5 Representability

A natural question to ask is whether the Catalan matroid can be represented as the vector matroid of a collection of vectors. We answer that question in this section.

Given a collection of real numbers $`x_1,\mathrm{},x_k`$, let $`x_S=_{iS}x_i`$ for each subset $`S[k]`$. Form all the $`2^{2^k}`$ possible sums of some of the $`x_S`$’s. If these sums are all distinct, we will say that the initial collection of numbers is *generic*. Most collections of real numbers are generic. A specific example is a set of algebraically independent real numbers. Another example is any sequence of positive integers which increases quickly enough; for instance, one that satisfies $`x_i>(1+x_1)(1+x_2)\mathrm{}(1+x_{i1})`$ for $`1<ik`$.

###### Theorem 5.1

Let $`v_1,\mathrm{},v_{2n}`$ be the columns of a matrix

$$A=\left(\begin{array}{ccccccccc}a_{11}& 0& 0& 0& 0& 0& \mathrm{}& 0& 0\\ a_{21}& a_{22}& a_{23}& 0& 0& 0& \mathrm{}& 0& 0\\ a_{31}& a_{32}& a_{33}& a_{34}& a_{35}& 0& \mathrm{}& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ a_{n1}& a_{n2}& a_{n3}& a_{n4}& a_{n5}& a_{n6}& \mathrm{}& a_{n,\mathrm{\hspace{0.17em}2}n1}& 0\end{array}\right)$$

where the $`a_{ij}`$’s with $`1in`$ and $`1j2i1`$ are generic integers. Then the vector matroid of $`\{v_1,\mathrm{},v_n\}`$ is isomorphic to the Catalan matroid $`𝐂_n`$.

*Proof.* Let $`M`$ be the vector matroid of $`V`$. Let $`1b_1<\mathrm{}<b_n2n`$. The set $`B=\{v_{b_1},\mathrm{},v_{b_n}\}`$ is a basis for $`M`$ if and only if it is independent; that is, if and only if the determinant of the matrix $`A_B`$ with columns $`v_{b_1},\mathrm{},v_{b_n}`$ is non-zero.

This determinant is a sum of $`n!`$ terms, with plus or minus signs attached to them. Since the $`a_{ij}`$’s are generic, this sum can only be zero if all the terms are $`0`$. So $`B`$ is a basis as long as at least one of the $`n!`$ terms in this determinant is non-zero.

The question is now whether it is possible to place $`n`$ non-attacking rooks on the non-zero entries of $`A_B`$; that is, to choose $`n`$ non-zero entries with no two on the same row or column. The marriage theorem \[10, Theorem 5.1\] would be the standard tool to attack this kind of question. However, $`A_B`$ is such that any entry below or to the left of a non-zero entry is also non-zero. This fact will make our argument shorter and self-contained.

If $`b_i2i1`$ for all integers $`i`$ with $`1in`$, then the $`(i,i)`$ entry of $`A_B`$ is $`a_{i,b_i}0`$. Therefore we can place $`n`$ non-attacking rooks on non-zero entries of $`A_B`$ by putting them on the main diagonal.

Conversely, suppose that we have a placement of $`n`$ non-attacking rooks on non-zero entries of $`A_B`$. Let $`i`$ be any integer between $`1`$ and $`n`$. Then the rooks on the first $`i`$ rows must be on $`i`$ different columns. From the shape that the non-zero entries of $`A_B`$ form, we conclude that the $`i`$-th row must contain $`i`$ different non-zero entries. Thus the $`(i,i)`$ entry of $`A_B`$, which is precisely $`a_{i,b_i}`$, must be non-zero. Therefore $`b_i2i1`$.

The above proof generalizes immediately to any shifted matroid $`\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$.

###### Theorem 5.2

Let $`s_1<\mathrm{}<s_n`$ be arbitrary positive integers. Let $`v_1,\mathrm{},v_{s_n}`$ be the columns of a matrix $`A=(a_{ij})_{1in,\mathrm{\hspace{0.17em}1}js_n}`$, where the $`a_{ij}`$’s with $`1in`$ and $`1js_i`$ are generic, and the remaining $`a_{ij}`$’s are equal to $`0`$. Then the vector matroid of $`\{v_1,\mathrm{},v_{s_n}\}`$ is isomorphic to the shifted matroid $`\mathrm{𝐒𝐌}(s_1,\mathrm{},s_n)`$.

Theorem 5.1 shows that the Catalan matroid is representable over $``$, or even over a sufficiently large finite field. In the other direction, we now show a negative result about representing $`𝐂_n`$ over finite fields.

###### Proposition 5.3

The Catalan matroid $`𝐂_n`$ is *not* representable over the finite field $`𝔽_q`$ if $`qn2`$.

*Proof.* It is known (, Proposition 6.5.2) and easy to show that the uniform matroid $`U_{2,k}`$ is $`𝔽_q`$-representable if and only if $`qk1`$. A matroid containing it as a minor is not representable over $`𝔽_q`$ for $`qk2`$. This suggests that we should find the largest $`k`$ for which $`U_{2,k}`$ is a minor of $`𝐂_n`$.

We can use the Scum theorem (Higgs, , Proposition 3.3.7), which essentially says that, if a matroid has a certain minor, then it must have that minor hanging from the top of its lattice of flats. Our question is then equivalent to finding the largest $`k`$ for which there exists a rank - $`(n2)`$ flat which is contained in $`k`$ rank - $`(n1)`$ flats.

###### Lemma 5.4

Let $`A`$ be a rank - $`(n2)`$ flat, and let $`x`$ be the smallest integer such that $`ht_A(x)=1`$. Then there are exactly $`\frac{x+3}{2}`$ rank - $`(n1)`$ flats containing $`A`$.

*Proof of Lemma 5.4.* We know from Propositions 2.2 and 2.3 that $`minht_A=3`$ and that, once the path $`A`$ reaches height $`3`$, say at $`ht_A(y)`$, it only takes up-steps. We want to add elements to $`A`$ to obtain a path which reaches a minimum height $`1`$, and only takes up-steps after that.

Say that we add one element $`a`$ to $`A`$. This new up-step at $`a`$ comes before the $`y`$-th, so $`ht_{Aa}(y)=1`$. If we don’t want to add any more elements to $`A`$, we have to make sure that $`Aa`$ only reaches height $`1`$ at $`y`$. For this to be true, we need the new up-step $`a`$ to occur on or before the $`x`$-th step. In $`A`$, there are $`\frac{x+1}{2}`$ down-steps up to the $`x`$-th to choose from. Each one of these gives a rank - $`(n1)`$ flat containing $`A`$

On the other hand, if we are to add more elements to $`A`$ to obtain a rank-$`(r1)`$ flat $`B`$, they will all be less than $`y`$ so we will have $`ht_B(y)>0`$. The minimum height in $`B`$ must then be achieved at some $`z`$ for which $`ht_A(z)=1`$. In fact, for this $`z`$ to be unique, it must be the leftmost one, *i.e.*, it must be $`x`$. So the only possibility is that $`B=A_x\{x+1,\mathrm{},2n\}`$, which is indeed a rank - $`(n1)`$ flat. This concludes the proof of Lemma 5.4.

Having shown Lemma 5.4, the rest is easy. The rank - $`(n2)`$ flat which is contained in the largest number of rank - $`(n1)`$ flats, is the latest one to arrive to height $`1`$. This flat is clearly $`\{1,2,\mathrm{},n3,n2,2n\}`$, which arrives to height $`1`$ after $`2n3`$ steps. It is contained in exactly $`n`$ rank - $`(n1)`$ flats.

Therefore $`𝐂_n`$ contains $`U_{2,n}`$ as a minor, and thus it is not representable over a field $`𝔽_q`$ with $`qn2`$.

## 6 Acknowledgements

I would like to thank Nantel Bergeron, James Haglund, Carly Klivans and Richard Stanley for helpful discussions. In particular, Richard Stanley pointed out that Proposition 4.5 is true at the level of generality of Proposition 4.6.