{'fraction_non_alphanumeric': 0.02937893467875162, 'fraction_numerical': 0.022681609144081797, 'mean_word_length': 4.819173811379579, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evidence for an accretion origin for the outer halo globular cluster system of M31

We use a sample of newly-discovered globular clusters from the Pan-Andromeda Archaeological Survey (PAndAS) in combination with previously-catalogued objects to map the spatial distribution of globular clusters in the M31 halo. At projected radii beyond ~30 kpc, where large coherent stellar streams are readily distinguished in the field, there is a striking correlation between these features and the positions of the globular clusters. Adopting a simple Monte Carlo approach, we test the significance of this association by computing the probability that it could be due to the chance alignment of globular clusters smoothly distributed in the M31 halo. We find the likelihood of this possibility is low, below 1%, and conclude that the observed spatial coincidence between globular clusters and multiple tidal debris streams in the outer halo of M31 reflects a genuine physical association. Our results imply that the majority of the remote globular cluster system of M31 has been assembled as a consequence of the accretion of cluster-bearing satellite galaxies. This constitutes the most direct evidence to date that the outer halo globular cluster populations in some galaxies are largely accreted.


INTRODUCTION
It has long been suspected that a significant fraction of the Milky Way's globular clusters formed in smaller 'protogalactic fragments' that were subsequently accreted into the Galactic potential well. First proposed in the seminal paper by Searle & Zinn (1978), there has since been gradual accumulation of indirect evidence in support of this hypothesis -modern data suggest that the abundances, ages, velocities, horizontal-branch morphologies and sizes of many globular clusters at Galactocentric radii 10 kpc are consistent with an external origin (e.g., Zinn 1993; Mackey & Gilmore 2004;Marín-Franch et al. 2009). Even so, it has proven problematic to unambiguously identify indvidual clusters as having been accreted into the Galaxy. The only direct observation of this process is the disrupting Sagittarius dwarf (Ibata et al. 1994) which is depositing at least five globular clusters into the Milky Way halo (Da Costa & Armandroff 1995;Martínez-Delgado et al. 2002;Bellazzini et al. 2003); more controversially, the putative Canis Major dwarf may also be responsible for several new arrivals (Martin et al. 2004). The extent to which the observed properties of sub-groups 1 Based on observations obtained with MegaPrime/MegaCam, a joint project of CFHT and CEA/DAPNIA, at the Canada-France-Hawaii Telescope (CFHT) which is operated by the National Research Council (NRC) of Canada, the Institut National des Science de l'Univers of the Centre National de la Recherche Scientifique (CNRS) of France, and the University of Hawaii.
within the Milky Way globular cluster system reflect the assembly history of the Galactic halo thus remains a critical unresolved question.
As the nearest large spiral galaxy, M31 is an attractive alternative target for studying this problem. Its globular cluster system is several times larger than that of the Milky Way, and observational investigation of its halo is less prone to the vagaries of projection and extinction that plague Galactic surveys. It is known that globular clusters projected near its central regions exhibit some evidence for sub-clustering in position-velocity space that may signal an accretion origin (Ashman & Bird 1993;Perrett et al. 2003), although interpretation is difficult because of the complex nature of the inner M31 system. Potentially less confusing are halo regions at projected radii R p 15 kpc, where dynamical times are also longer; however, it is only relatively recently that these remote areas have been targeted by deep wide-field surveys. Various such studies have shown the M31 halo to be littered with coherent tidal debris features indicative of one or more accretion events (Ferguson et al. 2002;Ibata et al. 2007), and have also facilitated the discovery of significant samples of remote M31 globular clusters (Huxor et al. 2008) so that it is now possible to begin assessing how these objects relate to the stellar halo in this galaxy. Huxor et al. (2010a) have derived the first radial surfacedensity profile for M31 globular clusters to extend into the far outer halo (R p ≈ 100 kpc). Their profile exhibits a distinct flattening beyond R p ≈ 30 kpc, very similar to that observed for the metal-poor field halo, and has been interpreted as evidence that accretion processes have played a role in building up both components.
In this Letter we use new results from the Pan-Andromeda Archaeological Survey (PAndAS; McConnachie et al. 2009) to provide the most extensive map to date of globular clusters in the M31 halo, and explore the implications for the origin of this system. PAndAS is an ongoing large program on the Canada-France-Hawaii Telescope, utilising the MegaCam imager to obtain a deep panoramic view of M31 and M33. First-semester imaging and data reduction was completed in mid-2009, revealing in exquisite new detail the abundance of low surface brightness substructure present in the M31 halo (McConnachie et al. 2009, see also Fig. 1).

THE M31 GLOBULAR CLUSTER SAMPLE
We consider a globular cluster ensemble defined by confirmed objects in V3.5 of the Revised Bologna Catalogue (RBC; e.g., Galleti et al. 2007) 1 plus newly-discovered clusters from the first semester of PAndAS imaging.
In this work we are primarily interested in globular clusters lying outside R p = 30 kpc (see below). The RBC list of confirmed globular clusters includes 41 objects discovered in our pre-PAndAS M31 surveys (Martin et al. 2006;Huxor et al. 2008), of which 31 fall beyond 30 kpc. The RBC also contains three clusters outside 30 kpc not discovered by us. We retain all RBC entries defined as "extended clusters" (Huxor et al. 2005(Huxor et al. , 2008. At present there is little evidence that these are anything other than bona fide globular clusters with peculiarly diffuse structures (Huxor et al. 2010a), at least in terms of their constituent stellar populations (Mackey et al. 2006) and internal dynamics (Collins et al. 2009).
The extension provided by first-semester PAndAS imaging over the region previously surveyed for globular clusters by Huxor et al. (2008) consists of nearly complete coverage of the inner parts of M31 together with a large halo area to the west and north-west. We have searched all fields at R p ≥ 30 kpc as well as many fields interior to this, using procedures similar to those described by Huxor et al. (2008). This has resulted in a catalogue of 43 previously unknown globular clusters, the properties of which will be detailed in a forthcoming paper (Huxor et al. 2010b, in prep.). For now it is sufficient to note that 33 of these objects fall at projected radii beyond 30 kpc, including 12 between 50 − 100 kpc and four outside 100 kpc. Sixteen of our newly-discovered clusters appear to be of the extended variety.
In summary, our sample contains 67 clusters with R p ≥ 30 kpc, although only 61 of these lie within the present PAndAS footprint.
All PAndAS imaging is taken during dark sky conditions with seeing better than 0.7 ′′ . Under such circumstances globular clusters in the M31 halo partially resolve into stars, meaning that identification is straightforward and unambiguous (see Fig. 1). Following the analysis of Huxor et al. (2010a), we believe our search procedure does not lead to significant bias or incompleteness in the overall cluster selection function down to M V ≈ −5. Furthermore, away from the very innermost M31 fields where crowding is non-negligible we expect no significant spatial variation in completeness. Figure 1 shows the positions of all globular clusters in our sample overlaid on the PAndAS metal-poor ([Fe/H] −1.4) stellar density map. In the outer parts of the M31 halo where large tidal debris streams are readily distinguished (R p 30 kpc), there is a striking correlation between these features and the positions of many globular clusters. Indeed, close inspection of Fig. 1 reveals very few remote clusters that do not project onto some kind of underlying field overdensity, even though these substructures clearly occupy only a relatively small fraction of the overall survey footprint.

ANALYSIS AND RESULTS
In order to put this result on more quantitative ground we undertake several calculations aimed at estimating the probability that the apparent association between clusters and debris streams could be due to chance alignment. That is, we aim to compute the level of significance at which similar substructures exist in both the globular cluster and field star distributions beyond R p ≈ 30 kpc.

Mock M31 globular cluster systems
We base our analysis on a simple Monte Carlo methodology utilizing a set of 1.5 × 10 5 random realizations of a smoothly-distributed M31 globular cluster system. These represent the null case where globular clusters constitute a wellmixed, unstructured halo population. Comparing the properties of these mock systems to those of the real M31 system then allows us to assess whether the observed globular clusters are indeed spatially correlated with underlying field overdensities, or whether the apparent association can be ascribed to stochastic effects.
In each mock system we randomly generated cluster galactocentric radii between R p = 30 − 130 kpc using a probability distribution function defined by the observed globular cluster radial surface-density profile, and selected position angles randomly from a uniform distribution such that each individual cluster fell within the PAndAS footprint. Our outer limit is the maximum radius with nearly complete coverage over the presently-observed area, while our inner limit is the approximate radius interior to which there are many overlapping halo features (e.g., Ferguson et al. 2002) and it becomes meaningless to associate clusters with field substructure via spatial coincidence alone. We set the total number of clusters in each mock system equal to the size of the known M31 sample between R p = 30 − 130 kpc within the PAndAS area (61 objects). Our derived cluster surface-density profile closely matches that obtained by Huxor et al. (2010a).

Direct comparison with the stellar density map
We utilized a FITS version of the PAndAS stellar density map to test whether the observed M31 globular clusters are preferentially projected against regions with higher densities of metal-poor red giant stars. The FITS map has an embedded World Coordinate System, which allowed us to easily calculate the mean value in a 7 × 7 pixel box about the position of each cluster. The clusters themselves are not generally visible on the map since they are usually unresolved by the cataloguing software. To be sure, we omitted the central (cluster) pixel from the average (one pixel ≈ 350 pc). Our box corresponds to a ∼ 2.5 × 2.5 kpc region on the sky, representing an adequate compromise in obtaining enough pixels without considering an unreasonably broad area about each cluster. It is also sufficiently larger than the ∼ 2.5 pixel Gaussian smoothing kernel used while generating the map. We considered the mean value in each box, rather than all pixels individually, because this smoothing means that adjacent pixel values are not independent.
We repeated this process for all real and mock globular clusters, and formed the results into two cumulative distributions (Fig. 2). These have quite different shapes -in particular, that for the real cluster system clearly contains fewer low values than does the distribution for the mock systems. In other words, the observed M31 globular clusters do preferentially project onto regions of higher field star density than would be expected if they constituted an unstructured halo  population. A simple Kolmogorov-Smirnov test provides an estimate of the significance of this result: the probability that the two distributions were drawn from the same parent distribution is only ≈ 1.3%.
This straightforward calculation provides a clear quantitative demonstration that the global spatial coincidence between globular clusters and tidal debris streams visible in Fig. 1 is almost certainly not due to chance alignment.

Stream-by-stream analysis
Further inspection of Fig. 1 suggests a more complicated picture: some streams apparently possess more clusters for their size than do others, while several are devoid of clusters altogether. To investigate this in more detail we considered each major halo overdensity individually. For now, we restrict ourselves to only those stellar substructures previously published in the literature. These are highlighted in Fig. 1: the giant stellar stream (Ibata et al. 2001); the northeast structure (Zucker et al. 2004;Ibata et al. 2005); the four minor-axis tangent streams A-D (Ibata et al. 2007), the latter of which extends to a coherent arc to the east of M31; and the southwest cloud and northwest stream (McConnachie et al. 2009). Ibata et al. (2007) also describe the "major-axis diffuse structure", an ill-defined feature extending to the southwest of M31 (region 1 in Fig. 1). Although there is evidently an overdensity along the major axis here, unlike the other streams it is not easily identifiable as a single structure; indeed there are additional faint overdensities extending east and north of this feature. We defer analysis of this region until it has been properly characterized, but note that numerous globular clusters (≈ 8 − 10) clearly project onto it.
We utilized FITS versions of both our metal-poor stellar density map, and an additional map including stars with photometric metallicities −1.4 [Fe/H] −0.7, to delineate the edges of each substructure. These more metal-rich stars alter the appearance of several of the overdensities (e.g., Ibata et al. 2007;McConnachie et al. 2009): most notably the giant stream, which increases in radial extent and fans westward; the southwest cloud, which becomes more prominent; and stream C, which is considerably broadened -indeed, this feature is known to consist of two distinct overlapping components (Chapman et al. 2008).
For each substructure we measured the mean and standard deviation of pixels in numerous nearby regions, and defined the edge of the structure by following a contour level ≈ 3.5σ above the local background. No globular clusters were over- plotted during this process. Our results are shown in Fig. 3. Although the edges of these substructures are by nature difficult to define, they are all sufficiently unambiguous not to alter the conclusions we draw below.
We next counted the fraction of mock systems in which N gc or more globular clusters overlap spatially with a given substructure, where N gc is the number of clusters observed to project onto that feature in the real M31 halo. We also considered the system globally, grouping together all the identified substructures.
Our results are summarized in Table 1. Taking all substructures together, we find it very unlikely that the observed spatial overlap of 27 clusters with these features can be explained by random alignment: the probability sits at just ∼ 0.25%. This strongly reinforces the result of our previous calculation involving the average local stellar densities.
Individually, the northwest stream and eastern arc are particularly well endowed with clusters. The fraction of mock systems in which ≥ 6 clusters fall within the northwest stream is ∼ 2.7%; this falls to below 1% if the additional boundarystraddling cluster to the south is included. Similarly, the frequency with which at least the 11 observed clusters fall within the eastern arc is ∼ 0.5% in the mock systems.
For the southwest cloud our calculated probability sits at ∼ 2.5%, while for stream C it is less significant at ∼ 7.8%. Notably however, stream C is the only case where velocity information exists for both the field substructure and an associated cluster (EC4), unambiguously linking the two (Collins et al. 2009).
The giant stream is notable as the only structure where the observed number of globular clusters approximately matches the number expected in a smoothly-distributed system. Since this stream is by far the most luminous stellar substructure in the M31 halo, it appears significantly underabundant in clusters compared with the streams described above. This is perhaps not too surprising: globular clusters located in the outskirts of the giant stream progenitor may well have been stripped away on earlier orbits about M31. Furthermore, the globular cluster specific frequencies 2 of dwarf galaxies span a large range ∼ 0 − 30 (e.g., Miller & Lotz 2007;Peng et al. 2008), so the progenitor might have possessed comparatively few globulars to start with. What about the three stellar substructures not associated with any globular clusters? Although this occurs commonly in the mock systems for all three features, we have already assembled ample evidence that clusters are not smoothly distributed in the outer parts of M31. Therefore, these three substructures simply demonstrate that not all field overdensities are necessarily associated with clusters. Streams A and B may be remains of low-mass satellites, or they may be 'shells' due to the impact of a relatively large accreted galaxy (Fardal et al. 2008;Mori et al. 2008). Either way, their intrinsic low luminosity likely explains their paucity of clusters. It is also perhaps unremarkable that no members of the halo cluster population are associated with the northeast structure, which observations suggest is a transient feature in the M31 extended disk (e.g., Ibata et al. 2005;Richardson et al. 2008).

Globular cluster overdensities
Finally, we highlight two globular cluster overdensities that are evident in Figs. 1 and 3 but not obviously coincident with underlying substructures. One sits to the west of M31 at R p ≈ 35 kpc, and the other to the northwest at R p ≈ 105 kpc. They represent the two groupings with the largest ratio of local cluster density to the azimuthal average at given radius (a factor ≈ 10 enhancement). The grouping with the third-highest ratio (≈ 7.5) overlaps the upper portion of the eastern arc.
We recognize the a posteriori nature of our identification of these two overdensities, and attempt to quantify their significance fairly by searching the mock systems for aggregations at similar radii but unconstrained azimuth, and with local enhancement ratios 5. With these relaxed constraints, indicative probabilities sit at ≈ 5% for both ensembles. This is again fully consistent with globular clusters not being smoothly distributed in the outer M31 halo, although here we cannot identify any corresponding field substructures. We hypothesize that these two cluster groups may trace underlying substructures that fall below the PAndAS low surface brightness limit; confirmation of the nature of these cluster overdensities will hence require radial velocity measurements. It is intriguing that the very massive globular cluster G1, thought to be the stripped core of a former nucleated dwarf (e.g., Bekki & Chiba 2004), is a prominent member of the western group.

DISCUSSION
Put together, our results provide strong evidence that globular clusters in the outer halo of M31 are anisotropically spatially distributed, and preferentially associated with underlying tidal debris features. Of the 61 clusters in the PAndAS footprint with R p 30 kpc, at least 27 lie on the major substructures outlined in Section 3.3; if the complex major-axis region is also included, this number rises to ≈ 37. A further 13 objects are members of the two cluster overdensities described in Section 3.4, leaving just 11 of the sample unaccounted for. Figure 1 reveals only a handful of these lie away from field overdensities altogether.
These numbers imply that the majority ( 80%) of the outer globular cluster system of M31 has been built up via the accretion of satellite host galaxies. This fraction matches closely that inferred for the outer Galactic system (e.g., Mackey & Gilmore 2004;Forbes & Bridges 2010). Our work provides a striking direct illustration of the Searle & Zinn (1978) paradigm; along with the disrupting Sagittarius dwarf, it represents the most clear-cut observation to date of the assembly of a globular cluster system in action, and does so on a grand scale -across an entire galactic system and a huge population of clusters.
We note that all but one of the extended clusters in our sample with R p 30 kpc are projected onto stellar substructure or are members of a cluster overdensity. This observation is consistent with the idea that these puzzling objects may predominantly originate in lower-mass galaxies (e.g., Da Costa et al.

2009).
Intriguingly, streams without clusters are seemingly in the minority in the outer M31 halo. With the caveat that there may be very low-luminosity features falling below the PAndAS surface-brightness limit, this could imply that most substructure in the outer M31 halo is due to the accretion of just a few larger cluster-bearing satellites. This would be in qualitative agreement with the results of cosmologically-motivated simulations, which suggest that the haloes of large spiral galaxies are predominantly assembled via the accretion of a handful ( 5) of significant progenitors (e.g., Bullock & Johnston 2005;Cooper et al. 2010).
Owing to their recent discovery, little is yet known about most of the remote M31 clusters described in this paper. However, a few have published colour-magnitude diagrams and/or spectra, which reveal them as almost exclusively metal-poor with −2.3 [Fe/H] −1.6 (Mackey et al. 2006(Mackey et al. , 2007(Mackey et al. , 2010Alves-Brito et al. 2009). Others exhibit a small dispersion in integrated colour, further supporting this assertion (Huxor et al. 2010a). This might imply that a significant fraction of metal-poor globular clusters in large galaxies are accreted objects, as suggested by a variety of models (e.g., Côté et al. 1998Côté et al. , 2000Prieto & Gnedin 2008;Muratov & Gnedin 2010). Our present results raise the exciting imminent prospect of characterizing, for the first time, the individual properties of multiple accreted families of globular clusters in a galactic halo.