In recent work, we formalized the theory of optimal-size sorting networks with the goal of extracting a verified checker for the large-scale computer-generated proof that 25 comparisons are optimal when sorting 9 inputs, which required more than a de
cade of CPU time and produced 27 GB of proof witnesses. The checker uses an untrusted oracle based on these witnesses and is able to verify the smaller case of 8 inputs within a couple of days, but it did not scale to the full proof for 9 inputs. In this paper, we describe several non-trivial optimizations of the algorithm in the checker, obtained by appropriately changing the formalization and capitalizing on the symbiosis with an adequate implementation of the oracle. We provide experimental evidence of orders of magnitude improvements to both runtime and memory footprint for 8 inputs, and actually manage to check the full proof for 9 inputs.
Since the proof of the four color theorem in 1976, computer-generated proofs have become a reality in mathematics and computer science. During the last decade, we have seen formal proofs using verified proof assistants being used to verify the validi
ty of such proofs. In this paper, we describe a formalized theory of size-optimal sorting networks. From this formalization we extract a certified checker that successfully verifies computer-generated proofs of optimality on up to 8 inputs. The checker relies on an untrusted oracle to shortcut the search for witnesses on more than 1.6 million NP-complete subproblems.
We consider several aspects of the generalized multi-plane gravitational lens theory, in which light rays from a distant source are affected by several main deflectors, and in addition by the tidal gravitational field of the large-scale matter distri
bution in the Universe when propagating between the main deflectors. Specifically, we derive a simple expression for the time-delay function in this case, making use of the general formalism for treating light propagation in inhomogeneous spacetimes which leads to the characterization of distance matrices between main lens planes. Applying Fermats principle, an alternative form of the corresponding lens equation is derived, which connects the impact vectors in three consecutive main lens planes, and we show that this form of the lens equation is equivalent to the more standard one. For this, some general relations for cosmological distance matrices are derived. The generalized multi-plane lens situation admits a generalized mass-sheet transformation, which corresponds to uniform isotropic scaling in each lens plane, a corresponding scaling of the deflection angle, and the addition of a tidal matrix (mass sheet plus external shear) to each main lens. We show that the time delay for sources in all lens planes scale with the same factor under this generalized mass-sheet transformation, thus precluding the use of time-delay ratios to break the mass-sheet transformation.
Strong gravitational lensing of sources with different redshifts has been used to determine cosmological distance ratios, which in turn depend on the expansion history. Hence, such systems are viewed as potential tools for constraining cosmological p
arameters. Here we show that in lens systems with two distinct source redshifts, of which the nearest one contributes to the light deflection towards the more distant one, there exists an invariance transformation which leaves all strong lensing observables unchanged (except the product of time delay and Hubble constant), generalizing the well-known mass-sheet transformation in single plane lens systems. The transformation preserves the relative distribution of mass and light, so that a `mass-follows-light assumption does not fix the MST. All time delays (from sources on both planes) scale with the same factor -- time-delay ratios are therefore invariant under the MST. Changing cosmological parameters, and thus distance ratios, is essentially equivalent to such a mass-sheet transformation. As an example, we discuss the double source plane system SDSSJ0946+1006, which has been recently studied by Collett and Auger, and show that variations of cosmological parameters within reasonable ranges lead to only a small mass-sheet transformation in both lens planes. Hence, the ability to extract cosmological information from such systems depends heavily on the ability to break the mass-sheet degeneracy.
Previous work identifying depth-optimal $n$-channel sorting networks for $9leq n leq 16$ is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits th
e problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until $n=40$.
To investigate and specify the statistical properties of cosmological fields with particular attention to possible non-Gaussian features, accurate formulae for the bispectrum and the bispectrum covariance are required. The bispectrum is the lowest-or
der statistic providing an estimate for non-Gaussianities of a distribution, and the bispectrum covariance depicts the errors of the bispectrum measurement and their correlation on different scales. Currently, there do exist fitting formulae for the bispectrum and an analytical expression for the bispectrum covariance, but the former is not very accurate and the latter contains several intricate terms and only one of them can be readily evaluated from the power spectrum of the studied field. Neglecting all higher-order terms results in the Gaussian approximation of the bispectrum covariance. We study the range of validity of this Gaussian approximation for two-dimensional non-Gaussian random fields. For this purpose, we simulate Gaussian and non-Gaussian random fields, the latter represented by log-normal fields and obtained directly from the former by a simple transformation. From the simulated fields, we calculate the power spectra, the bispectra, and the covariance from the sample variance of the bispectra, for different degrees of non-Gaussianity alpha, which is equivalent to the skewness on a given angular scale theta g. We find that the Gaussian approximation provides a good approximation for alpha<0.6 and a reasonably accurate approximation for alpha< 1, both on scales >8theta g. Using results from cosmic shear simulations, we estimate that the cosmic shear convergence fields are described by alpha<0.7 at theta g~4. We therefore conclude that the Gaussian approximation for the bispectrum covariance is likely to be applicable in ongoing and future cosmic shear studies.
Aims. The predictions of the ellipticity of the dark matter halos from models of structure formation are notoriously difficult to test with observations. A direct measurement would give important constraints on the formation of galaxies, and its effe
ct on the dark matter distribution in their halos. Here we show that galaxy-galaxy flexion provides a direct and potentially powerful method for determining the ellipticity of (an ensemble of) elliptical lenses. Methods. We decompose the spin-1 flexion into a radial and a tangential component. Using the ratio of tangential-to- radial flexion, which is independent of the radial mass profile, the mass ellipticity can be estimated. Results. An estimator for the ellipticity of the mass distribution is derived and tested with simulations. We show that the estimator is slightly biased. We quantify this bias, and provide a method to reduce it. Furthermore, a parametric fitting of the flexion ratio and orientation provides another estimate for the dark halo ellipticity, which is more accurate for individual lenses Overall, galaxy-galaxy flexion appears as a powerful tool for constraining the ellipticity of mass distributions.
Cosmic shear is considered one of the most powerful methods for studying the properties of Dark Energy in the Universe. As a standard method, the two-point correlation functions $xi_pm(theta)$ of the cosmic shear field are used as statistical measure
s for the shear field. In order to separate the observed shear into E- and B-modes, the latter being most likely produced by remaining systematics in the data set and/or intrinsic alignment effects, several statistics have been defined before. Here we aim at a complete E-/B-mode decomposition of the cosmic shear information contained in the $xi_pm$ on a finite angular interval. We construct two sets of such E-/B-mode measures, namely Complete Orthogonal Sets of E-/B-mode Integrals (COSEBIs), characterized by weight functions between the $xi_pm$ and the COSEBIs which are polynomials in $theta$ or polynomials in $ln(theta)$, respectively. Considering the likelihood in cosmological parameter space, constructed from the COSEBIs, we study their information contents. We show that the information grows with the number of COSEBI modes taken into account, and that an asymptotic limit is reached which defines the maximum available information in the E-mode component of the $xi_pm$. We show that this limit is reached the earlier (i.e., for a smaller number of modes considered) the narrower the angular range is over which $xi_pm$ are measured, and it is reached much earlier for logarithmic weight functions. For example, for $xi_pm$ on the interval $1le thetale 400$, the asymptotic limit for the parameter pair $(Omega_m, sigma_8)$ is reached for $sim 25$ modes in the linear case, but already for 5 modes in the logarithmic case. The COSEBIs form a natural discrete set of quantities, which we suggest as method of choice in future cosmic shear likelihood analyses.
In weak gravitational lensing, the image distortion caused by shear measures the projected tidal gravitational field of the deflecting mass distribution. To lowest order, the shear is proportional to the mean image ellipticity. If the image sizes are
not small compared to the scale over which the shear varies, higher-order distortions occur, called flexion. For ordinary weak lensing, the observable quantity is not the shear, but the reduced shear, owing to the mass-sheet degeneracy. Likewise, the flexion itself is unobservable. Rather, higher-order image distortions measure the reduced flexion, i.e., derivatives of the reduced shear. We derive the corresponding lens equation in terms of the reduced flexion and calculate the resulting relation between brightness moments of source and image. Assuming an isotropic distribution of source orientations, estimates for the reduced shear and flexion are obtained; these are then tested with simulations. In particular, the presence of flexion affects the determination of the reduced shear. The results of these simulations yield the amount of bias of the estimators, as a function of the shear and flexion. We point out and quantify a fundamental limitation of the flexion formalism, in terms of the product of reduced flexion and source size. If this product increases above the derived threshold, multiple images of the source are formed locally, and the formalism breaks down. Finally, we show how a general (reduced) flexion field can be decomposed into its four components: two of them are due to a shear field, carrying an E- and B-mode in general. The other two components do not correspond to a shear field; they can also be split up into corresponding E- and B-modes.
