On sub-harmonic bifurcations

Under fairly general hypotheses, we investigate by elementary methods the structure of the p-periodic orbits of a family $h_u$ of transformations near $(u_0,x_0)$ when $h_{u_0}(x_0)=x_0$ and $\mathrm{d}{h}_{u_0}(x_0)$ has a simple eigenvalue which is a primitive p-th root of unity. To cite this article: M. Chaperon et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

The coloring complex and cyclic coloring complex of a complete k-uniform hypergraph

In this paper, we study the homology of the coloring complex and the cyclic coloring complex of a complete k-uniform hypergraph. We show that the coloring complex of a complete k-uniform hypergraph is shellable, and we determine the rank of its unique nontrivial homology group in terms of its chromatic polynomial. We also show that the dimension of the $(n?k?1)\text{st}$ homology group of the cyclic coloring complex of a complete k-uniform hypergraph is given by a binomial coefficient. Further, we discuss a complex whose r-faces consist of all ordered set partitions $[B_1,\dots ,B_{r+2}]$ where none of the $B_i$ contain a hyperedge of the complete k-uniform hypergraph H and where $1\in B_1$. It is shown that the dimensions of the homology groups of this complex are given by binomial coefficients. As a consequence, this result gives the dimensions of the multilinear parts of the cyclic homology groups of $\mathbb{C}[x_1,\dots ,x_n]/\{x_{i_1}\dots x_{i_k}|i_1\dots i_k\text{is a hyperedge of}H\}$.     

On the longest common increasing binary subsequence

Let $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ be two independent sequences of iid Bernoulli random variables with parameter 1/2. Let ${\mathit{LCI}}_n$ be the length of the longest increasing sequence which is a subsequence of both finite sequences $X_1,\dots ,X_n$ and $Y_1,\dots ,Y_n$. We prove that, as n goes to infinity, $n^{?1/2}({\mathit{LCI}}_n?n/2)$ converges in law to a Brownian functional that we identify. To cite this article: C. Houdré et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Gorenstein injective complexes of modules over Noetherian rings

A complex C is called Gorenstein injective if there exists an exact sequence of complexes $?\to I_{\mathrm{?1}}\to I_0\to I_1\to ?$ such that each $I_i$ is injective, $C=\mathrm{Ker}(I_0\to I_1)$ and the sequence remains exact when $\mathrm{Hom}(E,?)$ is applied to it for any injective complex E. We show that over a left Noetherian ring R, a complex C of left R-modules is Gorenstein injective if and only if $C^m$ is Gorenstein injective in R-Mod for all $m\in \mathbb{Z}$. Also Gorenstein injective dimensions of complexes are considered.     

On low-dimensional cancellation problems

A well-known cancellation problem of Zariski asks when, for two given domains (fields) $K_1$ and $K_2$ over a field k, a k-isomorphism of $K_1[t]$ ($K_1(t)$) and $K_2[t]$ ($K_2(t)$) implies a k-isomorphism of $K_1$ and $K_2$. The main results of this article give affirmative answer to the two low-dimensional cases of this problem:1. Let K be an affine field over an algebraically closed field k of any characteristic. Suppose $K(t)?k(t_1,t_2,t_3)$, then $K?k(t_1,t_2)$.2. Let M be a 3-dimensional affine algebraic variety over an algebraically closed field k of any characteristic. Let $A=K[x,y,z,w]/M$ be the coordinate ring of M. Suppose $A[t]?k[x_1,x_2,x_3,x_4]$, then $\mathrm{frac}(A)?k(x_1,x_2,x_3)$, where $\mathrm{frac}(A)$ is the field of fractions of A.In the case of zero characteristic these results were obtained by Kang in [Ming-chang Kang, A note on the birational cancellation problem, J. Pure Appl. Algebra 77 (1992) 141–154; Ming-chang Kang, The cancellation problem, J. Pure Appl. Algebra 47 (1987) 165–171]. However, the case of finite characteristic is first settled in this article, that answered the questions proposed by Kang in [Ming-chang Kang, A note on the birational cancellation problem, J. Pure Appl. Algebra 77 (1992) 141–154; Ming-chang Kang, The cancellation problem, J. Pure Appl. Algebra 47 (1987) 165–171].     

Non-level semi-standard graded Cohen–Macaulay domain with h-vector (h0,h1,h2)

Let $\mathbb{k}$ be an algebraically closed field of characteristic 0, and $A={?}_{i\in \mathbb{N}}{A}_i$ a Cohen–Macaulay graded domain with $A_0=\mathbb{k}$. If A is semi-standard graded (i.e., A is finitely generated as a $\mathbb{k}[A_1]$-module), it has the h-vector$(h_0,h_1,\dots ,h_s)$, which encodes the Hilbert function of A. From now on, assume that $s=2$. It is known that if A is standard graded (i.e., $A=\mathbb{k}[A_1]$), then A is level. We will show that, in the semi-standard case, if A is not level, then $h_1+1$ divides $h_2$. Conversely, for any positive integers h and n, there is a non-level A with the h-vector $(1,h,(h+1)n)$. Moreover, such examples can be constructed as Ehrhart rings (equivalently, normal toric rings).     

Measurable sets with excluded distances

For a set of distances $D=\{d_1,\dots ,d_k\}$ a set A in the plane is called D-avoiding if no pair of points of A is at distance $d_i$ for some i. We show that the density of A is exponentially small in k provided the ratios $d_1/d_2,d_2/d_3,\dots ,d_{k-1}/d_k$ are all small enough. We also show that there exists a largest D-avoiding set, and give an algorithm to compute the maximum density of a D-avoiding set for any D.     

Solvable PST-groups,strong Sylow bases and mutually permutable products

A subgroup H of a group G is said to permute with the subgroup K of G if $HK=KH$. Subgroups H and K are mutually permutable (totally permutable) in G if every subgroup of H permutes with K and every subgroup of K permutes with H (if every subgroup of H permutes with every subgroup of K). If H and K are mutually permutable and $H\cap K=1$, then H and K are totally permutable. A subgroup H of G is S-permutable in G if H permutes with every Sylow subgroup of G. A group G is called a PST-group if S-permutability is a transitive relation in G. Let $\{p_1,\dots ,p_n,p_{n+1},\dots ,p_k\}$ be the set of prime divisors of the order of a finite group G with $\{p_1,\dots ,p_n\}$ the set of prime divisors of the order of the normal subgroup N of G. A set of Sylow subgroups $\{P_1,\dots ,P_n,P_{n+1},\dots ,P_k\}$, $P_i\in {\mathrm{Syl}}_{p_i}(G)$, form a strong Sylow system with respect to N if $P_i{P}_j$ is a mutually permutable product for all $i\in \{1,2,\dots ,n\}$ and $j\in \{1,2,\dots ,k\}$. We show that a finite group G is a solvable PST-group if and only if it has a normal subgroup N such that $G/N$ is nilpotent and G has a strong Sylow system with respect to N. It is also shown that G is a solvable PST-group if and only if G has a normal solvable PST-subgroup N and $G/N^{″}$ is a solvable PST-group.     

On a tree-partition problem

If $T=(V,E)$ is a tree then – T denotes the additive hereditary property consisting of all graphs that does not contain T as a subgraph. For an arbitrary vertex v of T we deal with a partition of T into two trees $T_1$, $T_2$, so that $V(T_1)\cap V(T_2)=\{v\}$, $V(T_1)\cup (T_2)=V(T)$, $E(T_1)\cap E(T_2)=\varnothing$, $E(T_1)\cup E(T_2)=E(T)$, $T[V(T_1)\backslash \{v\}]\subseteq E(T_1)$ and $T[V(T_2)\backslash \{v\}]\subseteq E(T_2)$. We call such a partition a $T_v-partition$ of T. We study the following em: Given a graph G belonging to –T. Is it true that for any $T_v$-partition $T_1$, $T_2$ of T there exists a partition $\{V_1,V_2\}$ of the vertices of G such that $G[V_1]\in -T_1$ and $G[V_2]\in -T_2$? This problem provides a natural generalization of Δ-partition problem studied by L. Lovász ([L. Lovász, On decomposition of graphs. Studia Sci. Math. Hungar. 1 (1966) 237–238]) and Path Partition Conjecture formulated by P. Mihók ([P. Mihók, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Góra, 1985, p. 86]). We present some partial results and a contribution to the Path Kernel Conjecture that was formulated with connection to Path Partition Conjecture.     

Estimation of certain exponential sums arising in complexity theory

It is shown that the correlation on ${\{0,1\}}^n$ between parity and a polynomial $p(x_1,\dots ,x_n)\in \mathbb{Z}[X_1,\dots ,X_n](\mathrm{mod}q)$, q a fixed odd number and $p(X)$ of degree d arbitrary but fixed, is exponentially small in n as $n\to \infty$. An application to circuit complexity, from where the problem originates, is given. To cite this article: J. Bourgain, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Estimation du nombre de dérivées d'un processus Gaussien

We consider a real Gaussian process X with unknown smoothness $r_0\in \mathbb{N}$ where the mean-square derivative $X^{(r_0)}$ is supposed to be Hölder continuous in quadratic mean. First, from the discrete observations $X(t_1),\dots ,X(t_n)$, we study reconstruction of $X(t)$, $t\in [0,1]$, with ${\stackrel{?}{X}}_r(t)$, a piecewise polynomial interpolation of degree $r?1$. We show that the mean-square error of interpolation is a decreasing function of r but becomes stable as soon as $r?r_0$. Next, from an interpolation-based empirical criterion, we derive an estimator $\stackrel{?}{r}$ of $r_0$ and prove its strong consistency by giving an exponential inequality for $P(\stackrel{?}{r}\ne r_0)$. Finally, we prove the strong convergence of ${\stackrel{?}{X}}_{\stackrel{?}{r}}(t)$ toward $X(t)$ with a similar rate as in the case ‘$r_0$ known’. To cite this article: D. Blanke, C. Vial, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Regular expression constrained sequence alignment

We introduce regular expression constrained sequence alignment as the problem of finding the maximum alignment score between given strings $S_1$ and $S_2$ over all alignments such that in these alignments there exists a segment where some substring $s_1$ of $S_1$ is aligned to some substring $s_2$ of $S_2$, and both $s_1$ and $s_2$ match a given regular expression R, i.e. $s_1,s_2\in L(R)$ where $L(R)$ is the regular language described by R. For complexity results we assume, without loss of generality, that $n=|S_1|⩾|m|=|S_2|$. A motivation for the problem is that protein sequences can be aligned in a way that known motifs guide the alignments. We present an $\mathrm{O}(nmr)$ time algorithm for the regular expression constrained sequence alignment problem where $r=\mathrm{O}(t^4)$, and t is the number of states of a nondeterministic finite automaton N that accepts $L(R)$. We use in our algorithm a nondeterministic weighted finite automaton M that we construct from N. M has $\mathrm{O}(t^2)$ states where the transition-weights are obtained from the given costs of edit operations, and state-weights correspond to optimum alignment scores we compute using the underlying dynamic programming solution for sequence alignment. If we are given a deterministic finite automaton D accepting $L(R)$ with $t_d$ states then our construction creates a deterministic finite automaton $M_d$ with $t_d^2$ states. In this case, our algorithm takes $\mathrm{O}(t_d^{2}nm)$ time. Using $M_d$ results in faster computation than using M when $t_d<t^2$. If we only want to compute the optimum score, the space required by our algorithm is $\mathrm{O}(t^{2}n)$ ($\mathrm{O}(t_d^{2}m)$ if we use a given $M_d$). If we also want to compute an optimal alignment then our algorithm uses $\mathrm{O}(t^{2}m+t^2|s_1||s_2|)$ space ($\mathrm{O}(t_d^{2}m+t_d^2|s_1||s_2|)$ space if we use a given $M_d$) where $s_1$ and $s_2$ are substrings of $S_1$ and $S_2$, respectively, $s_1,s_2\in L(R)$, and $s_1$ and $s_2$ are aligned together in the optimal alignment that we construct. We also show that our method generalizes for the case of the problem with affine gap penalties, and for finding optimal regular expression constrained local sequence alignments.