Massive 10^6-10^10 Msun black holes (BHs) are ubiquitous in local galactic nuclei. They were common by the time the Universe is several Gyr old, and many of them were in place within the first 1~Gyr after the Big Bang. Their quick assembly has been attributed to mechanisms such as the rapid collapse of gas into the nuclei of early protogalaxies, accretion and mergers of stellar-mass BHs accompanying structure formation at early times, and the runaway collapse of early, ultra-dense stellar clusters. The origin of the early massive BHs remains an intriguing and long-standing unsolved puzzle in astrophysics. Here we discuss strategies for discerning between BH seeding models using electromagnetic observations. We argue that the most direct answers will be obtained through detection of BHs with masses M<10^5 Msun at redshifts z>10, where we expect them to first form. Reaching out to these redshifts and down to these masses is crucial, because BHs are expected to lose the memory of their initial assembly by the time they grow well above 10^5 Msun and are incorporated into higher-mass galaxies. The best way to detect 10^4-10^5 Msun BHs at high redshifts is by a sensitive X-ray survey. Critical constraining power is augmented by establishing the properties and the environments of their host galaxies in deep optical/IR imaging surveys. Required OIR data can be obtained with the JWST and WFIRST missions. The required X-ray flux limits (down to 10^{-19} erg/s/cm^2) are accessible only with a next-generation X-ray observatory which has both high (sub-1) angular resolution and high throughput. A combination of deep X-ray and OIR surveys will be capable of probing several generic markers of the BH seed scenarios, and resolving the long-stanging puzzle of their origin. These electromagnetic observations are also highly synergistic with the information from LISA on high-z BH mergers.
Download