Search

The spectral gap conjecture of M. van den Berg [2, formula (65)] asserts that λ2 − λ1 ≥ 3π for all convex euclidean domains of diameter 1, where λ1 and λ2 denote the first two eigenvalues of the Dirichlet Laplacian. Notice that equality holds for the 1-dimensional unit interval, which can be regarded also as a degenerate n-dimensional rectangular box. The gap estimate is conjectured to hold more generally for Schrodinger operators with convex potentials, under Dirichlet boundary conditions; see the work of S.-T. Yau and collaborators [9, 11]. This Schrodinger gap conjecture was proved some time ago in 1 dimension by R. Lavine [8], and more recently in all dimensions by B. Andrews and J. Clutterbuck [1]. The proof in this journal by H. Donnelly [3] of the original gap conjecture in 2 dimensions (for the Dirichlet Laplacian with zero potential) is not correct. The Editors of Mathematische Zeitschrift have asked us to describe the flaws in the proof, in order to clarify the state of the literature. Donnelly’s approach to the problem is a natural one: first perform a shape optimization to rule out a non-degenerate minimizing domain, and then analyze the spectral gap for a sequence of domains degenerating to an interval, with the help of results by D. Jerison [5]. (For some history on this approach, and on the gap conjecture more generally, see the report on the AIM meeting “Low Eigenvalues of Laplace and Schrodinger Operators” [10], especially page 12 of the open problems list.) The error lies in the proof of the shape optimization step, as we now explain. Donnelly wishes to prove that no minimizing domain can exist for

In 1967, Schmidt wrote a seminal paper (Schmidt in Ann Math 85:430–472, 1967) on heights of subspaces of $$\mathbb {R}^n$$ or $$\mathbb {C}^n$$ defined over a number field K, and diophantine approximation problems. The going-down Theorem— one of the main theorems he proved in his paper—remains valid in two cases depending on whether the embedding of K in the complex field $$\mathbb {C}$$ is a real or a complex non-real embedding. For the latter, and more generally as soon as K is not totally real, at some point of the proof, the arguments in Schmidt (Ann Math 85:430–472, 1967) do not exactly work as announced. In this note, Schmidt’s ideas are worked out in details and his proof of the complex case is presented, solving the aforementioned problem. Some definitions of Schmidt are reformulated in terms of multilinear algebra and wedge product, following the approaches of Laurent (Analytic number theory, essays in honour of Klaus Roth. Cambridge University Press, Cambridge, pp 306–314, 2009), Bugeaud and Laurent (Mathematische Zeitschrift 265(2):249–262, 2010) and Roy (Journal de theorie des nombres de Bordeaux 27:591–603, 2015), Roy (Mathematische Zeitschrift 283(1–2):143–155, 2016). In Laurent (Analytic number theory, essays in honour of Klaus Roth. Cambridge University Press, Cambridge, pp 306–314, 2009) Laurent introduces in the case $$K=\mathbb {Q}$$ a family of exponents and he gives a series of inequalities relating them. In Sect. 5 these exponents are defined for an arbitrary number field K. Using the going-up and the going-down Theorems Laurent’s inequalities are generalized to this setting.

International audience; In this paper we show that if $A$ is a subset of the primes with positive lower relative density $1/k$ then $A + A$ must have positive lower density at least $C_1 / [k\log \log(3k)]$ in the natural numbers. Our argument uses the techniques developed by the author and I.Ruzsa in their work on additive properties of dense subsequences of sufficiently sifted sequences. The result is optimal and improves on recent work of K.Chipeniuk & M.Hamel. We continue by proving several similar results, by successively replacing the sequence of primes by the sequence of sums of two squares, by the sequence of those integers n that are such that $n$ and $n + 1$ are both a sum of two squares and finally by the sequence of primes $p$ that are such that $p + 1$ is a sum of two squares. The second part of this paper contains a heuristical argument that leads to several conjectures concerning the existence of $k$-term arithmetic progressions within these sequences. We conclude with some conjectures belonging to the Ramsey part of additive number theory.

In a recent paper, the authors proved that, under natural assumptions on the first marginal, the Monge problem in $ {\mathbb{R}^d} $ for the cost given by a general norm admits a solution. Although the basic idea of the proof is simple, it involves some complex technical results. Here we will give a proof of the result in the simpler case of a uniformly convex norm, and we will also use very recent results by Ahmad, Kim, and McCann. This allows us to reduce the technical burdens while still giving the main ideas of the general proof. The proof of the density of the transport set in the particular case considered in this paper is original. Bibliography: 22 titles.

We prove that in the Wasserstein space built over R the subset of measures that does not charge the non-differentiability set of convex functions is not displacement convex. This completes the study of Gigli on the geometric structure of measures meeting the sharp hypothesis of the refined version of Brenier’s Theorem. Optimal transport is nowadays a central tool in many fields of analysis, differential geometry and probability theory (see e.g. the books by Villani [11, 12]). It takes its origin in the problem of Monge, asking for the shortest way to displace an amount of soil from one place of the Euclidean space to a heap of soil at another place. This problem induces a very natural distance between probability measures – the Wasserstein distance – where the measures represent the heaps of soil. Wasserstein distance is somewhat complementary with the Lebesgue L norms because it corresponds to an “horizontal” displacement: in first approximation, for two localized probability measures on R, the Wasserstein distance is the distance between their barycenters. Brenier’s Theorem [4] on monotone rearrangement of maps of R has become the very core of the theory of optimal transport. It gives a representation of the optimal transport map in term of gradient of convex functions. A very enlightening heuristic on (P2(R ),W2) is proposed in [7] where it appears with an infinite differential structure and the Wasserstein distance is seen as a Riemannian-like distance. This point of view has raised a lot of developments, among which the gradient flow theory presented in [2]. In [6], Gigli explores the Riemannian-like structure and proposes to think of the measures meeting the hypothesis of a refined version of Brenier’s Theorem as the regular points of the Wasserstein space. In this paper we show that the set of those transport-regular measures is not geodesically convex (Theorems 2.2 and 2.5). It is quite surprising because it is well-known that the subset made of absolutely continuous measures (the most notorious transport-regular measures) is geodesically convex. It answers a question suggested by Gigli [6, Remark 2.12]. The paper is built as follows: we first recall some main results on the quadratic Monge(-Kantorovich) problem. The key idea of our result can be found in Lemma 1.6 while Proposition 1.8 gives a way, together with Proposition 1.7, to characterize transport-regular measures. In the second (and last) part, we prove the main theorem (Theorem 2.2) and its generalization (Theorem 2.5) thanks to explicit constructions. 2010 Mathematics Subject Classification. Primary 28A75.

We characterize the polynomial decay of orbits of Hilbert space $C_0$-semigroups in resolvent terms. We also show that results of the same type for general Banach space semigroups and functions obtained recently in the paper by C.J.K.Batty and T.Duyckaerts, Non-uniform stability for bounded semi-groups on Banach spaces (J. Evol. Eq. 2008), are sharp. This settles a conjecture posed in the paper by C.J.K.Batty and T.Duyckaerts., 21 pages, to appear in Matematische Annalen

Let R be a real closed field. The Pierce–Birkhoff conjecture says that any piecewise polynomial function f on Rn can be obtained from the polynomial ring R[x1,..., xn] by iterating the operations of maximum and minimum. The purpose of this paper is threefold. First, we state a new conjecture, called the Connectedness conjecture, which asserts, for every pair of points \({{\alpha,\beta\in\,{\rm {Sper}}\ R[x_1,\ldots,x_n]}}\) , the existence of connected sets in the real spectrum of R[x1,..., xn], satisfying certain conditions. We prove that the Connectedness conjecture implies the Pierce–Birkhoff conjecture. Secondly, we construct a class of connected sets in the real spectrum which, though not in itself enough for the proof of the Pierce–Birkhoff conjecture, is the first and simplest example of the sort of connected sets we really need, and which constitutes the first step in our program for a proof of the Pierce–Birkhoff conjecture in dimension greater than 2. Thirdly, we apply these ideas to give two proofs that the Connectedness conjecture (and hence also the Pierce–Birkhoff conjecture in the abstract formulation) holds locally at any pair of points \({{\alpha,\beta\in\,{\rm {Sper}}\ R[x_1,\ldots,x_n]}}\) , one of which is monomial. One of the proofs is elementary while the other consists in deducing this result as an immediate corollary of the main connectedness theorem of this paper.

The paper introduces the notion of skew-evolution semiflows and presents the concept of pointwise trichotomy in the case of skew-evolution semiflows on a Banach space. The connection with the classic notion of trichotomy presented by us in a previous paper in 2006 for evolution operators, is also emphasized, as well as some characterizations. The approach of the theory is from uniform point of view. The study can also be extended to systems with control whose state evolution can be described by skew-evolution semiflows.

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [R.L Graham, H.Pollak On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495–2519] and Djokovic [D. Djokovic, Distance preserving subgraphs of the hypercubes, J. Combin. Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specially, we deal with the case where this configuration is a connected graph of order 4 on one hand and the case where the configuration is a fan F k ( k ⩾ 3 ) on the other hand. Finally, we conjecture that a subdivision of a complete graph of order n ( n ⩾ 5 ) is a partial cube if and only if this one is isomorphic to S ( K n ) or there exists n − 1 edges of K n adjacent to a common vertex in the subdivision and the other edges of K n contain odd added vertices. This proposition is true when the order n ∈ { 4 , 5 , 6 } .

This paper has been withdrawn by the author due to its publication, This paper has been withdrawn

The paper is devoted to studying the Hoffman global error bound for convex quadratic/affine inequality/equality systems in the context of Banach spaces. We prove that the global error bound holds if the Hoffman local error bound is satisfied for each subsystem at some point of the solution set of the system under consideration. This result is applied to establishing the equivalence between the Hoffman error bound and the Abadie qualification condition, as well as a general version of Wang & Pang's result [30], on error bound of Holderian type. The results in the present paper generalize and unify recent works by Luo & Luo in [17], Li in [16] and Wang & Pang in [30].

In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n > m), and l = m - n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when l/m goes to some positive limit β > 1, the size B1m,l1 of the largest block of consecutive cars satisfies 2(β - 1 - log β)B1m,l - 3 log log m + Ξm, where Ξm converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B1m,l = o(m) and m - B1m,l = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent.

We explain and restate the results from our recent paper arXiv:1503.08000.v3 in standard language for substitutions and $S$-adic systems in symbolic dynamics. We then produce as rather direct application an $S$-adic system (with finite set of substitutions $S$ on $d$ letters) that is minimal and has $d$ distinct ergodic probability measures. As second application we exhibit a formula that allows an efficient practical computation of the cylinder measure $\mu([w])$, for any word $w \in \cal A^*$ and any invariant measure $\mu$ on the subshift $X_\sigma$ defined by any everywhere growing but not necessarily primitive or irreducible substitution $\sigma: \cal A^* \to \cal A^*$. Several examples are considered in detail, and model computations are presented., Comment: 20 pages. See also arXiv:1503.08000.v3

International audience; The main result of this paper, Theorem 1.4, establishes a conjecture of Lyons and Peres: for a determinantal point process governed by a self-adjoint reproducing kernel, the system of kernels sampled at the points of a random configuration is complete in the range of the kernel. A key step in the proof, Lemma 1.9, states that conditioning on the configuration in a subset preserves the determinantal property, and the main Lemma 1.10 is a new local property for kernels of conditional point processes. In Theorem 1.6 we prove the triviality of the tail σ-algebra for determinantal point processes governed by self-adjoint kernels.

21 pages, 2 figures; International audience; Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three rough universality classes, the most studied being the "critical" one. For this class the scaling of the quantity of greatest interest (the critical probability) was determined by Bollobás, Duminil-Copin, Morris and Smith in terms of a simply defined combinatorial quantity called "difficulty", so the subject seemed closed up to finding sharper results. However, the computation of the difficulty was never considered. In this paper we provide the first algorithm to determine this quantity, which is, surprisingly, not as easy as the definition leads to thinking. The proof also provides some explicit upper bounds, which are of use for bootstrap percolation. On the other hand, we also prove the negative result that computing the difficulty of a critical model is NP-hard. This two-dimensional picture contrasts with an upcoming result of Balister, Bollobás, Morris and Smith on uncomputability in higher dimensions. The proof of NP-hardness is achieved by a technical reduction to the Set Cover problem.

A hole in a graph is an induced cycle of length at least $4$, and an antihole is the complement of an induced cycle of length at least $4$. A hole or antihole is long if its length is at least $5$. For an integer $k$, the $k$-prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial time algorithm to solve MWIS in long-hole-free graphs with no $k$-prism (for any fixed integer $k$), and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial time algorithm to find a maximum weight clique in perfect graphs with no long antihole, and no hole of length $6$. The algorithms use the framework of minimal chordal completions and potential maximal cliques.

International audience; In this paper, we shall establish a rather general asymptotic formula in short intervals for a classe of arithmetic functions and announce two applications about the distribution of divisors of square-full numbers and integers representable as sums of two squares.

The problem of extracting a well conditioned submatrix from any rectangular matrix (with normalized columns) has been studied for some time in functional and harmonic analysis. In the seminal work of Bourgain and Tzafriri and many subsequent improvements, methods using random column selection were considered. Constructive approaches have been proposed lately, mainly sparked by the work of Batson, Spielman and Srivastava. The column selection problem we consider in this paper is concerned with extracting a well conditioned submatrix, and more precisely, a matrix with all its singular values being contained in the interval [ 1 − e , 1 + e ] . Such results are known to have far reaching connections with many fields in mathematics and engineering. Our main contribution is a new deterministic method that achieves the same order R for the number of selected columns as in Bourgain and Tzafriri’s original Theorem, up to a log ( R ) multiplicative factor. Our analysis is elementary and shows how a simple eigenvalue perturbation argument can lead to an intuitive and very short proof. We also obtain individual lower and upper bounds for each singular value of the extracted matrix.

Denote by$\mathbb{P}$the set of all prime numbers and by$P(n)$the largest prime factor of positive integer$n\geq 1$with the convention$P(1)=1$. In this paper, we prove that, for each$\unicode[STIX]{x1D702}\in (\frac{32}{17},2.1426\cdots \,)$, there is a constant$c(\unicode[STIX]{x1D702})>1$such that, for every fixed nonzero integer$a\in \mathbb{Z}^{\ast }$, the set$$\begin{eqnarray}\{p\in \mathbb{P}:p=P(q-a)\text{ for some prime }q\text{ with }p^{\unicode[STIX]{x1D702}}has relative asymptotic density one in$\mathbb{P}$. This improves a similar result due to Banks and Shparlinski [‘On values taken by the largest prime factor of shifted primes’,J. Aust. Math. Soc.82(2015), 133–147], Theorem 1.1, which requires$\unicode[STIX]{x1D702}\in (\frac{32}{17},2.0606\cdots \,)$in place of$\unicode[STIX]{x1D702}\in (\frac{32}{17},2.1426\cdots \,)$.

Let $\mathcal{X}$ be a complex projective manifold of dimension $n$ defined over the reals and let $M$ be its real locus. We study the vanishing locus $Z\_{s\_d}$ in $M$ of a random real holomorphic section $s\_d$ of $\mathcal{E} \otimes \mathcal{L}^d$, where $\mathcal{L} \to \mathcal{X}$ is an ample line bundle and $\mathcal{E} \to \mathcal{X}$ is a rank $r$ Hermitian bundle, $r \in \{1,\dots, n\}$. We establish the asymptotic of the variance of the linear statistics associated with $Z\_{s\_d}$, as $d$ goes to infinity. This asymptotic is of order $d^{r-\frac{n}{2}}$. As a special case, we get the asymptotic variance of the volume of $Z\_{s\_d}$. The present paper extends the results of [20], by the first-named author, in essentially two ways. First, our main theorem covers the case of maximal codimension ($r = n$), which was left out in [20]. And second, we show that the leading constant in our asymptotic is positive. This last result is proved by studying the Wiener--It{\=o} expansion of the linear statistics associated with the common zero set in $\mathbb{RP}^n$ of $r$ independent Kostlan--Shub--Smale polynomials., Comment: Final version, published in Indiana Math. Univ. J

In the present paper, we generalize the well-known Hensel’s lifting lemma to any continuous function f : Z p → Z p . This answers a question posed by Axelsson and Khrennikov (2016) who showed the validity of Hensel’s lemma for 1- and for p α -Lipschitz functions. For the statement and the proof, we introduce a suitable generalization of the original van der Put series. We use the concept of approximability of continuous functions to give numerical examples.

International audience; In this paper we define and study a filtration (G_s) on the algebra of values at algebraic points of analytic continuations of G-functions: G_s is the set of values at algebraic points in the disk of convergence of all G-functions sum_n a_n z^n for which there exist some positive integers b and c such that d_{s b}^n c^{n+1} a_n is an algebraic integer for any n, where d_n = lcm(1, 2,. .. , n). We study the situation at the boundary of the disk of convergence, and using transfer results from analysis of singularities we deduce that constants in G_s appear in the asymptotic expansion of such a sequence (a_n).

Let $\mathcal H$ be the class of algebras verifying Han's conjecture. In this paper we analyse two types of algebras with the aim of providing an inductive step towards the proof of this conjecture. Firstly we show that if an algebra $\Lambda$ is triangular with respect to a system of non necessarily primitive idempotents, and if the algebras at the idempotents belong to $\mathcal H$, then $\Lambda$ is in $\mathcal H$. Secondly we consider a $2\times 2$ matrix algebra, with two algebras on the diagonal, two projective bimodules in the corners, and zero corner products. They are not triangular with respect to the system of the two diagonal idempotents. However, the analogous result holds, namely if both algebras on the diagonal belong to $\mathcal H$, then the algebra itself is in $\mathcal H$., Comment: To appear in Indiana University Mathematics Journal 28 pages

The model of FCFS infinite bipartite matching was introduced in caldentey-kaplan-weiss 2009. In this model there is a sequence of items that are chosen i.i.d. from $\mathcal{C}=\{c_1,\ldots,c_I\}$ and an independent sequence of items that are chosen i.i.d. from $\mathcal{S}=\{s_1,\ldots,s_J\}$, and a bipartite compatibility graph $G$ between $\mathcal{C}$ and $\mathcal{S}$. Items of the two sequences are matched according to the compatibility graph, and the matching is FCFS, each item in the one sequence is matched to the earliest compatible unmatched item in the other sequence. In adan-weiss 2011 a Markov chain associated with the matching was analyzed, a condition for stability was verified, a product form stationary distribution was derived and the rates $r_{c_i,s_j}$ of matches between compatible types $c_i$ and $s_j$ were calculated. In the current paper, we present several new results that unveil the fundamental structure of the model. First, we provide a pathwise Loynes' type construction which enables to prove the existence of a unique matching for the model defined over all the integers. Second, we prove that the model is dynamically reversible: we define an exchange transformation in which we interchange the positions of each matched pair, and show that the items in the resulting permuted sequences are again independent and i.i.d., and the matching between them is FCFS in reversed time. Third, we obtain product form stationary distributions of several new Markov chains associated with the model. As a by product, we compute useful performance measures, for instance the link lengths between matched items., Comment: 33 pages, 12 figures

The simple $GL(n,\mathbb {C})$ -modules are described by using semistandard Young tableaux. Any semistandard skew tableau can be transformed into a well defined semistandard tableau by a combinatorial operation, the Schutzenberger jeu de taquin. Associated to the classical Lie groups $SP(2n,\mathbb {C})$ , $SO(2n+1,\mathbb {C})$ , there are other notions of semistandard Young tableaux and jeux de taquin. In this paper, we study these various jeux de taquin, proving that each of them has a simple and explicit formulation as a step-by-step sliding. Any of these jeux de taquin is the restriction of the orthogonal one, associated to $SO(2n+1,\mathbb {C})$ .

International audience; We describe all boundedly finite measures which are invariant by Cartesian powers of an infinite measure preserving version of Chacon transformation. All such ergodic measures are products of so-called diagonal measures, which are measures generalizing in some way the measures supported on a graph. Unlike what happens in the finite-measure case, this class of diagonal measures is not reduced to measures supported on a graph arising from powers of the transformation: it also contains some weird invariant measures, whose marginals are singular with respect to the measure invariant by the transformation. We derive from these results that the infinite Chacon transformation has trivial centralizer, and has no nontrivial factor. At the end of the paper, we prove a result of independent interest, providing sufficient conditions for an infinite measure preserving dynamical system defined on a Cartesian product to decompose into a direct product of two dynamical systems.

International audience; In this paper, we prove a functorial aspect of the formal geometric quantization procedure of non-compact spin-c manifolds.

We call shifted power a polynomial of the form $(x-a)^e$. The main goal of this paper is to obtain broadly applicable criteria ensuring that the elements of a finite family $F$ of shifted powers are linearly independent or, failing that, to give a lower bound on the dimension of the space of polynomials spanned by $F$. In particular, we give simple criteria ensuring that the dimension of the span of $F$ is at least $c.|F|$ for some absolute constant $c, 25 pages

A single qubit may be represented on the Bloch sphere or similarly on the 3-sphere S 3 . Our goal is to dress this correspondence by converting the language of universal quantum computing (UQC) to that of 3-manifolds. A magic state and the Pauli group acting on it define a model of UQC as a positive operator-valued measure (POVM) that one recognizes to be a 3-manifold M 3 . More precisely, the d-dimensional POVMs defined from subgroups of finite index of the modular group P S L ( 2 , Z ) correspond to d-fold M 3 - coverings over the trefoil knot. In this paper, we also investigate quantum information on a few &lsquo, universal&rsquo, knots and links such as the figure-of-eight knot, the Whitehead link and Borromean rings, making use of the catalog of platonic manifolds available on the software SnapPy. Further connections between POVMs based UQC and M 3 &rsquo, s obtained from Dehn fillings are explored.

In this paper, we explore the fixed point theory of $n$-valued maps using configuration spaces and braid groups, focussing on two fundamental problems, the Wecken property, and the computation of the Nielsen number. We show that the projective plane (resp.\ the $2$-sphere ${\mathbb S}^{2}$) has the Wecken property for $n$-valued maps for all $n\in {\mathbb N}$ (resp.\ all $n\geq 3$). In the case $n=2$ and ${\mathbb S}^{2}$, we prove a partial result about the Wecken property. We then describe the Nielsen number of a non-split $n$-valued map $\phi\colon\thinspace X \multimap X$ of an orientable, compact manifold without boundary in terms of the Nielsen coincidence numbers of a certain finite covering $q\colon\thinspace \widehat{X} \to X$ with a subset of the coordinate maps of a lift of the $n$-valued split map $\phi\circ q\colon\thinspace \widehat{X} \multimap X$., Comment: To appear in Science China Math

Finding the exact integrality gap $$\alpha $$ for the LP relaxation of the metric travelling salesman problem (TSP) has been an open problem for over 30 years, with little progress made. It is known that $$4/3 \le \alpha \le 3/2$$ , and a famous conjecture states $$\alpha = 4/3$$ . It has also been conjectured that the integrality gap is achieved for half-integer basic solutions of the linear program. For this problem, essentially two “fundamental” classes of instances have been proposed. This fundamental property means that in order to show that the integrality gap is at most $$\rho $$ for all instances of the metric TSP, it is sufficient to show it only for the instances in the fundamental class. However, despite the importance and the simplicity of such classes, no apparent effort has been deployed for improving the integrality gap bounds for them. In this paper we take a natural first step in this endeavour, and consider the 1 / 2-integer points of one such class. We successfully improve the upper bound for the integrality gap from 3 / 2 to 10 / 7 for a superclass of these points for which a lower bound of 4 / 3 is proved. A key role in the proof of this result is played by finding Hamiltonian cycles whose existence is equivalent to Kotzig’s result on “compatible Eulerian tours”, and which lead us to delta-matroids for developing the related algorithms. Our arguments also involve other innovative tools from combinatorial optimization with the potential of a broader use.

We provide two examples of smooth projective surfaces of tame CM type, by showing that any parameter space of isomorphism classes of indecomposable ACM bundles with fixed rank and determinant on a rational quartic scroll in projective 5-space is either a single point or a projective line. For surfaces of minimal degree and wild CM type, we classify rigid Ulrich bundles as Fibonacci extensions. For the rational normal scrolls S(2,3) and S(3,3), a complete classification of rigid ACM bundles is given in terms of the action of the braid group in three strands., This version is meant to amend two inaccurate statements appearing in the published paper

In this paper, we study Abelian and metabelian quotients of braid groups of oriented surfaces with boundary components. We provide group presentations and we prove rigidity results for these quotients arising from exact sequences related to (generalised) Fadell–Neuwirth fibrations.

Let \(\Omega \) be an arbitrary set, equipped with an algebra \({\mathcal {A}}\subseteq 2^{\Omega }\) and let \(f: B({\mathcal {A}}) \rightarrow {\mathbb {R}}\) be a functional defined on the set \(B({\mathcal {A}}) \) of bounded measurable functions \(x:\Omega \rightarrow {\mathbb {R}}\). We provide necessary and sufficient conditions for a submodular functional f to be representable as a Choquet integral. From standard properties of the Choquet integral the functional f should be positively homogeneous and constant additive. Our first result shows that these two properties, together with submodularity, characterize a subadditive Choquet integral, when \(\Omega \) is finite. In the general case, f is a subadditive Choquet integral if and only if it satisfies the three previous properties, together with sup-norm continuity. This result provides another characterization of subadditive Choquet integrals different from the seminal paper by Schmeidler (Proc Am Math Soc 97(2):255–261, 1986) that relies on comonotonic additivity.

The Linear Independence hypothesis (LI), which states roughly that the imaginary parts of the critical zeros of Dirichlet L-functions are linearly independent over the rationals, is known to have interesting consequences in the study of prime number races, as was pointed out by Rubinstein and Sarnak. In this paper, we prove that a function field analogue of LI holds generically within certain families of elliptic curve L-functions and their symmetric powers. More precisely, for certain algebro-geometric families of elliptic curves defined over the function field of a fixed curve over a finite field, we give strong quantitative bounds for the number of elements in the family for which the relevant L-functions have their zeros as linearly independent over the rationals as possible.

Let $$\mathcal S$$ be an abelian group of automorphisms of a probability space $$(X, {\mathcal A}, \mu )$$ with a finite system of generators $$(A_1, \ldots , A_d).$$ Let $$A^{{\underline{\ell }}}$$ denote $$A_1^{\ell _1} \ldots A_d^{\ell _d}$$ , for $${{\underline{\ell }}}= (\ell _1, \ldots , \ell _d).$$ If $$(Z_k)$$ is a random walk on $${\mathbb {Z}}^d$$ , one can study the asymptotic distribution of the sums $$\sum _{k=0}^{n-1} \, f \circ A^{\,{Z_k(\omega )}}$$ and $$\sum _{{\underline{\ell }}\in {\mathbb {Z}}^d} {\mathbb {P}}(Z_n= {\underline{\ell }}) \, A^{\underline{\ell }}f$$ , for a function f on X. In particular, given a random walk on commuting matrices in $$SL(\rho , {\mathbb {Z}})$$ or in $${\mathcal M}^*(\rho , {\mathbb {Z}})$$ acting on the torus $${\mathbb {T}}^\rho $$ , $$\rho \ge 1$$ , what is the asymptotic distribution of the associated ergodic sums along the random walk for a smooth function on $${\mathbb {T}}^\rho $$ after normalization? In this paper, we prove a central limit theorem when X is a compact abelian connected group G endowed with its Haar measure (e.g., a torus or a connected extension of a torus), $$\mathcal S$$ a totally ergodic d-dimensional group of commuting algebraic automorphisms of G and f a regular function on G. The proof is based on the cumulant method and on preliminary results on random walks.

International audience; We study rational functions admitting a continuous extension to the real affine space. First of all, we focus on the regularity of such functions exhibiting some nice properties of their partial derivatives. Afterwards, since these functions correspond to rational functions which become regular after some blowings-up, we work on the plane where it suffices to blow-up points and then we can count the number of stages of blowings-up necessary. In the latest parts of the paper, we investigate the ring of rational continuous functions on the plane regular after one stage of blowings-up. In particular, we prove a Positivstellensatz without denominator in this ring.

Toward a partial classification of monomial ideals with $d$-linear resolution, in this paper, some classes of $d$-uniform clutters which do not have linear resolution, but every proper subclutter of them has a $d$-linear resolution, are introduced and the regularity and Betti numbers of circuit ideals of such clutters are computed. Also, it is proved that for given two $d$-uniform clutters $\mathcal{C}_1, \mathcal{C}_2$, the Castelnuovo-Mumford regularity of the ideal $I(\bar{\mathcal{C}_1 \cup \mathcal{C}_2})$ is equal to the maximum of regularities of $I(\bar{\C}_1)$ and $I(\bar{\C}_2)$, whenever $V(\mathcal{C}_1) \cap V(\mathcal{C}_2)$ is a clique or ${\rm SC}(\mathcal{C}_1) \cap {\rm SC}(\mathcal{C}_2)=\emptyset$. As applications, alternative proofs are given for Fr\"oberg's Theorem on linearity of edge ideal of graphs with chordal complement as well as for linearity of generalized chordal hypergraphs defined by Emtander. Finally, we find minimal free resolutions of the circuit ideal of a triangulation of a pseudo-manifold and a homology manifold explicitly., Comment: 16 pages

259-280; International audience; In the present paper we extend Champernowne's construction of normal numbers to provide sequences which are generic for a given invariant probability measure, which need not be the maximal one. We present a construction together with estimates and examples for normal numbers with respect to Lüroth series expansion, continued fractions expansion or $\beta$-expansion.

We consider a continuum percolation model on $$\mathbb {R}^d$$ , $$d\ge 1$$ . For $$t,\lambda \in (0,\infty )$$ and $$d\in \{1,2,3\}$$ , the occupied set is given by the union of independent Brownian paths running up to time t whose initial points form a Poisson point process with intensity $$\lambda >0$$ . When $$d\ge 4$$ , the Brownian paths are replaced by Wiener sausages with radius $$r>0$$ . We establish that, for $$d=1$$ and all choices of t, no percolation occurs, whereas for $$d\ge 2$$ , there is a non-trivial percolation transition in t, provided $$\lambda $$ and r are chosen properly. The last statement means that $$\lambda $$ has to be chosen to be strictly smaller than the critical percolation parameter for the occupied set at time zero (which is infinite when $$d\in \{2,3\}$$ , but finite and dependent on r when $$d\ge 4$$ ). We further show that for all $$d\ge 2$$ , the unbounded cluster in the supercritical phase is unique. Along the way a finite box criterion for non-percolation in the Boolean model is extended to radius distributions with an exponential tail. This may be of independent interest. The present paper settles the basic properties of the model and should be viewed as a springboard for finer results.

We consider in this paper the family of exponential Lie groups $G_{n,\mu}$, whose Lie algebra is an extension of the Heisenberg Lie algebra by the reals and whose quotient group by the centre of the Heisenberg group is an $ax+b$-like group. The C*-algebras of the groups $G_{n,\mu}$ give new examples of almost $C_0({\cal K})$-C*-algebras.

International audience; The asymptotic behaviour of a cellular automaton iterated on a random configuration is well described byits limit probability measure(s). In this paper, we characterise measures and sets of measures that can be reached aslimit points after iterating a cellular automaton on a simple initial measure. In addition to classical topological constraints, we exhibit necessary computational obstructions. With an additionalhypothesis of connectivity, we show these computability conditions are sufficient by constructing a cellular automatonrealising these sets, using auxiliary states in order to perform computations. Adapting this construction, we obtain asimilar characterisation for the Ces\`aro mean convergence, a Rice theorem on the sets of limit points, and we are ableto perform computation on the set of measures, i.e. the cellular automaton converges towards a set of limit points thatdepends on the initial measure. Last, under non-surjective hypotheses, it is possible to remove auxiliary states fromthe construction.

A key ingredient in the Taylor–Wiles proof of Fermat’s last theorem is the classical Ihara lemma, which is used to raise the modularity property between some congruent Galois representations. In their work on Sato and Tate, Clozel, Harris and Taylor proposed a generalisation of the Ihara lemma in higher dimension for some similitude groups. The main aim of this paper is to prove some new instances of this generalised Ihara lemma by considering some particular non-pseudo-Eisenstein maximal ideals of unramified Hecke algebras. As a consequence, we prove a level-raising statement.

International audience; We generalize to Hilbert spaces a theorem of Glaeser concerning minimal Lipschitz extensions of m-jets of one variable with range in R. The results contained in this paper can be seen as a small contribution to the general problem of the minimal Lipschitz extensions from m-jets for a Hilbert space to another Hilbert space.

In this paper, we obtain almost sure invariance principles with rate of order $$n^{1/p}\log ^\beta n$$ , $$2< p\le 4$$ , for sums associated with a sequence of reverse martingale differences. Then, we apply those results to obtain similar conclusions in the context of some non-invertible dynamical systems. For instance, we treat several classes of maps of the interval (for possibly unbounded observables) or smooth dynamical systems under a very weak regularity condition on the observables.

The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SICOMP'13] have characterised a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and Zivny from [CP'11/SICOMP'13] on types of weightings necessarily contained in every nontrivial weighted clone. This result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not., To appear in SIAM Journal on Discrete Mathematics (SIDMA)

In this paper, we investigate three problems concerning the toric ideal associated to a matroid. Firstly, we list all matroids $\mathcal M$ such that its corresponding toric ideal $I_{\mathcal M}$ is a complete intersection. Secondly, we handle with the problem of detecting minors of a matroid $\mathcal M$ from a minimal set of binomial generators of $I_{\mathcal M}$. In particular, given a minimal set of binomial generators of $I_{\mathcal M}$ we provide a necessary condition for $\mathcal M$ to have a minor isomorphic to $\mathcal U_{d,2d}$ for $d \geq 2$. This condition is proved to be sufficient for $d = 2$ (leading to a criterion for determining whether $\mathcal M$ is binary) and for $d = 3$. Finally, we characterize all matroids $\mathcal M$ such that $I_{\mathcal M}$ has a unique minimal set of binomial generators., Comment: 9 pages

Euclid’s lemma can be derived from the algebraic gcd property, but it is not at all apparent that Euclid himself does this. We would be quite surprised if he didn’t use this property because he points it out early on and because we expect him to make use of the Euclidean algorithm in some significant way. In this paper, we explore the question of just how the algebraic gcd property enters into Euclid’s proof, if indeed it does. Central to Euclid’s development is the idea of four numbers being proportional: a is to b as c is to d. Euclid gives two different definitions of proportionality, one in Book VII for numbers (“Pythagorean proportionality”) and one in Book V for general magnitudes (“Eudoxean proportionality”). We will discover that it is essential to keep in mind the difference between these two definitions and that many authorities, possibly including Euclid himself, have fallen into the trap of believing that Eudoxean proportionality for numbers is easily seen to be the same as Pythagorean proportionality. Finally, we will suggest a way to make Euclid’s proof good after 2300 years.

This paper is devoted to Markov-Bernstein and Landau-Kolmogorov type inequalities in several variables in L 2 norm. The measures which are used, are the Hermite measure and some closely connected measures in such a way that the partial derivatives of the orthogonal polynomials are also orthogonal. These orthogonal polynomials in several variables are built by tensor product of the orthogonal polynomials in one variable. These inequalities are obtained by using a variational method and they involve the square norms of a polynomial p and at most those of the partial derivatives of order 2 of p .It is also proved that the sequences of polynomials in several variables, orthogonal with respect to the Hermite and Laguerre-Sonin measures, are closed in a certain Sobolev space regarding its natural inner product and the inner product linked to the bilinear functional which is used in the variational method. This result shows us that the given Landau-Kolmogorov type inequalities are satisfied not only for polynomials, but also for functions belonging to this Sobolev space.

In this paper, explicit auxiliary functions are used to get upper and lower bounds for the Mahler measure of monic irreducible totally positive polynomials with integer coefficients. These bounds involve the length and the trace of the polynomial.