Un analogue elliptique du théorème de Roth

We present here quantitative versions, in dimension one, of Faltings' theorem according to which the set of K-rational points (where K is a given number field) of an Abelian variety A defined over K, which are close (with respect to a v-adic distance on K) to some K-subvariety X of A, but do not belong to X, is finite. More precisely, we treat the case where A is an elliptic curve and X is reduced to a point of A and we give (in this case) explicit bounds for the cardinal of the exceptional finite set. We consider also, more generally, not only one place v of K, but also a finite set S of places of K and the distance from the point of A to X, which takes into account all the places of S. To cite this article: B. Farhi, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Relative uniform completeness and order-convex representations of archimedean ?-groups and f-rings

Results of Henriksen and Johnson, for archimedean f-rings with identity, and of Aron and Hager, for archimedean ?-groups with unit, relating uniform completeness to order-convexity of a representation in a D(X) (the lattice of almost real continuous functions on the space X) are extended to situations without identity or unit. For an archimedean ?-group, G, we show: if G admits any representation G?D(X) in which G is order-convex, then G is divisible and relatively uniformly complete. A converse to this would seem to require some sort of canonical representation of G, which seems not to exist in the ?-group case. But for a reduced archimedean f-ring, A, there is the Johnson representation A?D(XA), and we show: A is divisible, relatively uniformly complete and square-dominated if and only if A is order-convex in D(XA) and square-root-closed. Also, we expand on the situation with unit, where we have the Yosida representation, G?D(YG): if G is divisible, relatively uniformly complete, and the unit is a near unit, then G is order-convex in D(YG).     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

Sphere coverings and identifying codes

In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S _r (x) = {y ∈ V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.     

Edge-switching homomorphisms of edge-coloured graphs

An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray.     

Abstract Holography

The problem that is presented and investigated is a natural nonlinear extension of the following linear problem. Let H ⊕ H′ and K ⊕ K′ be two orthogonal Hilbert decompositions of a real Hilbert space X. Let P, P′, Q, Q′ and N′ be the operators of orthogonal projection of X onto H, H′, K, K′ and H′ ∩ K′ respectively. Denoting by Z′ the Hilbert space, Z′ = {(a′, b′) ?H′ × K′: N′a′ = N′b′}, let F be the linear mapping of X into Z′, F(x) = (P′x, Q′x). Under the condition ∥PQ∥ < 1, which proves to be equivalent to H ∩ K = {0} and H + K closed, F is bicontinuous. The problem is then to choose a constructive procedure for the calculation of a = (P ° F^?1) · (a′,b′), and to analyse the continuity of P ° F^?1. One may use an iterative technique depending on a real relaxation parameter ω. Let the “separation angle” between H and K be defined by (H, K) = Arc cos ∥PQ∥. The present analysis stresses the fundamental part played by the separation angles α = (H, K), α′ = (H, K′), β = (H, SH) and β′ = (H′, SH) where S (= 2Q ? I) denotes the operator of orthogonal symmetry with respect to K. In the special case where X and H are complex spaces, and K′ = iK, the analysis of the problem is governed by the separation angles β and β′ only. These angles are involved in what may then be called “the conjugate image effect of H with respect to the orthogonal decomposition of X, K ⊕ iK.” Then, $\text{α = α′ =}\text{β}\text{2}$, and the optimal value of ω is known a priori (ω₀ = 2). This particular problem, which proves to be related to the central problem of Holography, defines what we have called “Abstract Holography”. (One of the main objects of our analysis is to show what underlies the principle of “Wavefront Reconstruction,” which is referred to in Classical Holography, and how it is possible to circumvent certain related difficulties by using an optimal iterative procedure).     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.     

Almost Primitive Elements of Free lie Algebras of Small Ranks

Let K be a field, X = {x1, . . . , xn}, and let L(X) be the free Lie algebra over K with the set X of free generators. A. G. Kurosh proved that subalgebras of free nonassociative algebras are free, A. I. Shirshov proved that subalgebras of free Lie algebras are free. A subset M of nonzero elements of the free Lie algebra L(X) is said to be primitive if there is a set Y of free generators of L(X), L(X) = L(Y ), such that M ? Y (in this case we have |Y | = |X| = n). Matrix criteria for a subset of elements of free Lie algebras to be primitive and algorithms to construct complements of primitive subsets of elements with respect to sets of free generators have been constructed. A nonzero element u of the free Lie algebra L(X) is said to be almost primitive if u is not a primitive element of the algebra L(X), but u is a primitive element of any proper subalgebra of L(X) that contains it. A series of almost primitive elements of free Lie algebras has been constructed. In this paper, for free Lie algebras of rank 2 criteria for homogeneous elements to be almost primitive are obtained and algorithms to recognize homogeneous almost primitive elements are constructed.     

The parametrized family of metric Mahler measures

Let M(α) denote the (logarithmic) Mahler measure of the algebraic number α. Dubickas and Smyth, and later Fili and the author, examined metric versions of M. The author generalized these constructions in order to associate, to each point in t∈(0,∞], a metric version Mt of the Mahler measure, each having a triangle inequality of a different strength. We further examine the functions Mt, using them to present an equivalent form of Lehmer?s conjecture. We show that the function t?Mtt(α) is constructed piecewise from certain sums of exponential functions. We pose a conjecture that, if true, enables us to graph t?Mt(α) for rational α.     

Convergence and the length spectrum

The author defines and analyzes the 1/k length spectra, L1/k(M), whose union, over all k∈N is the classical length spectrum. These new length spectra are shown to converge in the sense that limk→∞K1/k(Mi)⊂L1/k(M)∪{0} as Mi→M in the Gromov-Hausdorff sense. Energy methods are introduced to estimate the shortest element of L1/k, as well as a concept called the minimizing index which may be used to estimate the length of the shortest closed geodesic of a simply connected manifold in any dimension. A number of gap theorems are proven, including one for manifolds, Mn, with Ricci?(n−1) and volume close to Vol(Sn). Many results in this paper hold on compact length spaces in addition to Riemannian manifolds.     

Target set reachability criteria for dynamical systems described by inaccurate models

S is taken to be a dynamical system (described by Banach space operators) whose outputy we wish to regulate. The structural complexity ofS (nonlinearities, distributed parameters, etc.) forces us to design a controller forS using an approximate modelM ofS. A convex error bound ? describes the accuracy of the approximation ofS byM. For a prescribed target setY _t , we considered the problem of driving the output ofS toY _t subject to worst possible error excursions betweenM andS. The notion of areconstructed support function is instrumental to the derivation of the main result, Theorem 6.1, which we can paraphrase as follows. IfM is linear (S need not be), then we can describe a finite-dimensional convex programming Problem (P), whose solution tells us whether or notY _t is reachable. Theorem 6.1 is then specialized to differential systems approximated in the norm. The computation of numerical solutions is also discussed.     

Stokes formula on the Wiener space and n-dimensional Nourdin-Peccati analysis

Extensions of the Nourdin-Peccati analysis to Rn-valued random variables are obtained by taking conditional expectation on the Wiener space. Several proof techniques are explored, from infinitesimal geometry, to quasi-sure analysis (including a connection to Stein's lemma), to classical analysis on Wiener space. Partial differential equations for the density of an Rn-valued centered random variable Z=(Z¹,…,Zn) are obtained. Of particular importance is the function defined by the conditional expectation given Z of the auxiliary random matrix (−DL−1Zi|DZj), i,j=1,2,…,n, where D and L are respectively the derivative operator and the generator of the Ornstein-Uhlenbeck semigroup on Wiener space.     

Control problems for parabolic equations on controlled domains

Given the one-dimensional heat equation v_t = v_xx on the controlled domain Q(y) = {(t, x); 0 < x < y(t), 0 < t < T} subject to some initial-boundary conditions, we study the problem of optimally selecting y(·) from some admissible class so as to maximize a given payoff of fixed duration. Q(y) is thus a controlled domain. We also study the problem in which the heat equation holds in Q(y, z) = {z(t) < x < y(t), 0 < t < T}; z minimizing, y maximizing, i.e., the differential game. The principle techniques involved are (i) transforming the controlled domain to an uncontrolled domain and then (ii) using the method of lines for parabolic equations to enable us to use known results for control systems governed by ordinary differential equations. Sufficient conditions for existence in an admissible class is given and the method of lines allows numerical techniques to be applied to determine the optimal control in our class.     

Remarks on large solutions of a class of semilinear elliptic equations

In this paper, we show existence, uniqueness and exact asymptotic behavior of solutions near the boundary to a class of semilinear elliptic equations −Δu=λg(u)−b(x)f(u) in Ω, where λ is a real number, b(x)>0 in Ω and vanishes on ∂Ω. The special feature is to consider g(u) and f(u) to be regularly varying at infinity and b(x) is vanishing on the boundary with a more general rate function. The vanishing rate of b(x) determines the exact blow-up rate of the large solutions. And the exact blow-up rate allows us to obtain the uniqueness result.     

On certain spaces of lattice diagram determinants

The aim of this work is to study some lattice diagram determinants Δ_L(X,Y) as defined in (Adv. Math. 142 (1999) 244) and to extend results of Aval et al. (J. Combin. Theory Ser. A, to appear). We recall that M_L denotes the space of all partial derivatives of Δ_L. In this paper, we want to study the space M_i,j^k(X,Y) which is defined as the sum of M_L spaces where the lattice diagrams L are obtained by removing k cells from a given partition, these cells being in the “shadow” of a given cell (i,j) in a fixed Ferrers diagram. We obtain an upper bound for the dimension of the resulting space M_i,j^k(X,Y), that we conjecture to be optimal. This dimension is a multiple of n! and thus we obtain a generalization of the n! conjecture. Moreover, these upper bounds associated to nice properties of some special symmetric differential operators (the “shift” operators) allow us to construct explicit bases in the case of one set of variables, i.e. for the subspace M_i,j^k(X) consisting of elements of 0 Y-degree.     

The p-adic Gross-Zagier formula for elliptic curves at supersingular primes

Let p be a prime number and let E be an elliptic curve defined over ? of conductor N. Let K be an imaginary quadratic field with discriminant prime to pN such that all prime factors of N split in K. B. Perrin-Riou established the p-adic Gross-Zagier formula that relates the first derivative of the p-adic L-function of E over K to the p-adic height of the Heegner point for K when E has good ordinary reduction at p. In this article, we prove the p-adic Gross-Zagier formula of E for the cyclotomic ? _p -extension at good supersingular prime p. Our result has an application for the full Birch and Swinnerton-Dyer conjecture. Suppose that the analytic rank of E over ? is 1 and assume that the Iwasawa main conjecture is true for all good primes and the p-adic height pairing is not identically equal to zero for all good ordinary primes, then our result implies the full Birch and Swinnerton-Dyer conjecture up to bad primes. In particular, if E has complex multiplication and of analytic rank 1, the full Birch and Swinnerton-Dyer conjecture is true up to a power of bad primes and 2.     

On the complexity of paths avoiding forbidden pairs

Given a graph G=(V,E), two fixed vertices s,t∈V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)∈F we have x?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)∈F satisfy v?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)∈F satisfy u?x?v?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.     

Formes homogènes de degré 3 et puissances p-ièmes

In this paper, we are interested in diophantine equations of type F(x,y)=dzp where F is a separable homogeneous form of degree ?3 with integer coefficients, d a fixed integer ?1 and p a prime number ?7. As a consequence of the abc conjecture, if p is sufficiently large and (a,b,c) is a nontrivial proper solution of the above equation, we have c=±1. In the case where F has degree 3, we associate to (a,b,c) an elliptic curve defined over Q called the Frey curve or Hellegouarch-Frey curve. This allows us to deduce our conjecture from another one about elliptic curves attributed to G. Frey and B. Mazur (which is itself a consequence of the abc conjecture). We then applied our construction to the study of an explicit form. We give some results about the set of nontrivial proper solutions of the equation considered for several values of d.     

General decomposition theorems form-convex sets in the plane

A setS inR ^dis said to bem-convex,m≧2, if and only if for everym distinct points inS, at least one of the line segments determined by these points lies inS. Clearly any union ofm?1 convex sets ism-convex, yet the converse is false and has inspired some interesting mathematical questions: Under what conditions will anm-convex set be decomposable intom?1 convex sets? And for everym≧2, does there exist aσ(m) such that everym-convex set is a union ofσ(m) convex sets? Pathological examples convince the reader to restrict his attention to closed sets of dimension≦3, and this paper provides answers to the questions above for closed subsets of the plane. IfS is a closedm-convex set in the plane,m ≧ 2, the first question may be answered in one way by the following result: If there is some lineH supportingS at a pointp in the kernel ofS, thenS is a union ofm ? 1 convex sets. Using this result, it is possible to prove several decomposition theorems forS under varying conditions. Finally, an answer to the second question is given: Ifm≧3, thenS is a union of (m?1)³2 ^m?3 or fewer convex sets.