A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

Valeurs aux entiers négatifs des séries de Dirichlet associées a un polynôme,I

In this paper, we are studying Dirichlet series Z(P,ξ,s) = Σ_n?$\text{N}$^1rP(n)^?s ξⁿ, where P ∈ $\text{R}$₊ [X₁,…,X_r] and ξⁿ = ξ₁ⁿ¹ … ξ_r^nr, with ξ_i ∈ $\text{C}$, such that |ξ_i| = 1 and ξ_i ≠ 1, 1 ≦ i ≦ r. We show that Z(P, ξ,·) can be continued holomorphically to the whole complex plane, and that the values Z(P, ξ, ?k) for all non negative integers, belong to the field generated over $\text{Q}$ by the ξ_i and the coefficients of P. If, there exists a number field K, containing the ξ_i, 1 ≦ i ≦ r, and the coefficients of P, then we study the denominators of Z(P, ξ, ?k) and we define a $\text{B}$-adic function Z$\text{B}$(P, ξ,·) which is equal, on class of negative integers, to Z(P, ξ, ?k).     

On solutions of “equations in symmetric groups”

Let x?S_n, the symmetric group on n symbols. Let θ? Aut(S_n) and let the automorphim order of x with respect to θ be defined by

$\text{γθ(x)=}\text{min}\text{{k:x xθ xθ}{}^2\text{? xθ}{}^{\mathrm{k?1}}\text{=1}}$

where xθ is the image of x under θ. Let α_g? Aut(S_n) denote conjugation by the element g?S_n. Let where s and k are positive integers and $\text{a}\text{b}$ denotes a divides b. Further h(s, k : n) ≡ b(1; s, k : n), where 1 denotes the identity automorphim. If g?S_n let c = f(g, s) denote the number of symbols in g which are in cycles of length not dividing the integer s, and let g_s denote the product of all cycles in g whose lengths do not divide s. Then g_s moves c symbols. The main results proved are: (1) recursion: if n ? c + 1 and t = n ? c ? 1 then $\text{b(g; s, 1:n)=∑}{}_{\mathrm{<mtext>i</mtext><mtext>s</mtext>}}\text{b(g; s, 1:n?1)(}{}^{\mathrm{t}}{}_{\mathrm{i?1}}\text{(i?1)!}$ (2) reduction: b(g; s, 1 : c)h(s, 1 : i) = b(g; s, 1 : i + c); (3) distribution: let D(θ, n) ≡ {(k, b) : k?Z⁺ and b = b(θ; 1, k : n) ≠ 0}; then D(θ, m) = D(φ, m) ∨ m ? N = N(θ, φ) iff θ is conjugate to φ; (4) evaluation: the number of cycles in g_s^s of any given length is smaller than the smallest prime dividing s iff b(g_s; s, 1 : c) = 1. If g = (12 … p^m)^t and $\text{sk}\text{p}{}^{\mathrm{m}}$ then $\text{b(g;s,k:p}{}^{\mathrm{m}}\text{) {}{}^0{}_{\mathrm{\pm 1}}\text{(}\text{mod}\text{p)}$.     

Optimum designs when the observations are second-order processes

Let the process {Y(x,t) : t?T} be observable for each x in some compact set X. Assume that Y(x, t) = θ₀f₀(x)(t) + … + θ_kf_k(x)(t) + N(t) where f_i are continuous functions from X into the reproducing kernel Hilbert space H of the mean zero random process N. The optimum designs are characterized by an Elfving's theorem with $\text{R}$ the closed convex hull of the set {(φ, f(x))_H : 6φ 6_H ≤ 1, x?X}, where (·, ·)_H is the inner product on H. It is shown that if X is convex and f_i are linear the design points may be chosen from the extreme points of X. In some problems each linear functional c′θ can be optimally estimated by a design on one point x(c). These problems are completely characterized. An example is worked and some partial results on minimax designs are obtained.     

Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions

A function f(x) defined on $\text{X}$ = $\text{X}$₁ × $\text{X}$₂ × … × $\text{X}$_n where each $\text{X}$_i is totally ordered satisfying f(x ∨ y) f(x ∧ y) ≥ f(x) f(y), where the lattice operations ∨ and ∧ refer to the usual ordering on $\text{X}$, is said to be multivariate totally positive of order 2 (MTP₂). A random vector Z = (Z₁, Z₂,…, Z_n) of n-real components is MTP₂ if its density is MTP₂. Classes of examples include independent random variables, absolute value multinormal whose covariance matrix Σ satisfies ?DΣ^?1D with nonnegative off-diagonal elements for some diagonal matrix D, characteristic roots of random Wishart matrices, multivariate logistic, gamma and F distributions, and others. Composition and marginal operations preserve the MTP₂ properties. The MTP₂ property facilitate the characterization of bounds for confidence sets, the calculation of coverage probabilities, securing estimates of multivariate ranking, in establishing a hierarchy of correlation inequalities, and in studying monotone Markov processes. Extensions on the theory of MTP₂ kernels are presented and amplified by a wide variety of applications.     

On a generalization of linear independence in finite-dimensional vector spaces

A set X in a vector space V is said to be k-independent (where k is a positive integer) if, for each x?X,X{x} admits a partition into k subsets {χ_gq}_θ=1,…,k such that x ? span χ_θ, θ = 1,…,k. It is proved that if dim V = n and X ? V is k-independent, then X cannot contain more than $\text{(}\text{n+k?1}\text{k}\text{)}$ elements; this bound is sharp for vector spaces over sufficiently large fields. A broader notion (k-independence in degrees) is considered, and similar results are obtained. Several unresolved problems are stated, some involving matroid generalizations of questions answered as yet only within vector space context.     

Smoothness of spectral subbundles and reducibility of quasi-periodic linear differential systems

In this paper we study linear differential systems (1) $\text{x′ =}\text{A}\text{?}\text{(θ + ωt)x,}\text{where}\text{A}\text{?}\text{(θ)}\text{is an}\text{(n × n)}$ matrix-valued function defined on the k-torus T^k and (θ, t) → θ + ωt is a given irrational twist flow on T^k. First, we show that if A ? C^N(T^k), where N ? {0, 1, 2,…; ∞; ω}, then the spectral subbundles are of class C^N on T^k. Next we assume that à is sufficiently smooth on T^k and ω satisfies a suitable “small divisors” inequality. We show that if (1) satisfies the “full spectrum” assumption, then there is a quasi-periodic linear change of variables x = P(t)y that transforms (1) to a constant coefficient system y′ =By. Finally, we study the case where the matrix $\text{A}\text{?}\text{(θ + ωt)}$ in (1) is the Jacobian matrix of a nonlinear vector field $\text{?(x)}$ evaluated along a quasi-periodic solution x = φ(t) of (2) $\text{x′ = ?(x)}$. We give sufficient conditions in terms of smoothness and small divisors inequalities in order that there is a coordinate system (z, ?) defined in the vicinity of $\text{Ω = H(φ)}$, the hull of φ, so that the linearized system (1) can be represented in the form z′ = Dz, ?′ = ω, where D is a constant matrix. Our results represent substantial improvements over known methods because we do not require that à be “close to” a constant coefficient system.     

Definition and characterization of multivariate negative binomial distribution

The probability generating function (pgf) of an n-variate negative binomial distribution is defined to be [β(s₁,…,s_n)]^?k where β is a polynomial of degree n being linear in each s_i and k > 0. This definition gives rise to two characterizations of negative binomial distributions. An n-variate linear exponential distribution with the probability function h(x₁,…,x_n)$\text{exp}\text{(}\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{θ}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}\text{)}\text{f(θ}{}_1\text{,…,θ}{}_{\mathrm{n}}\text{)}$ is negative binomial if and only if its univariate marginals are negative binomial. Let S_t, t = 1,…, m, be subsets of {s₁,…, s_n} with empty ∩_t=1^mS_t. Then an n-variate pgf is of a negative binomial if and only if for all s in S_t being fixed the function is of the form of the pgf of a negative binomial in other s's and this is true for all t.     

A note on the J1-convergence of a first-passage process

Let X₁, X₂, … be a sequence of independent and identically distributed random variables with mean zero such that the common distribution function belongs to the domain of attraction of a stable law G_α,β with 1<α<2 and β=1 or α=2. If S_n=X₁+…X_n and N(ξ)=min{k:S_k>ξ}, ξ>0, then it is shown that $\text{N(nt)}\text{B}{}^1\text{(n)}$, 0<t<1, converges weakly under the Skorohod J₁-topology to a stable subordinator of index $\text{1}\text{α}$, where B¹(n) depends on the norming constant for S_n.     

Monotonicity of permanents of certain doubly stochastic circulant matrices

Let p_k(A), k=2,…,n, denote the sum of the permanents of all k×k submatrices of the n×n matrix A. A conjecture of Ðokovi?, which is stronger than the famed van der Waerden permanent conjecture, asserts that the functions p_k((1?θ)J_n+;θA), k=2,…, n, are strictly increasing in the interval 0?θ?1 for every doubly stochastic matrix A. Here J_n is the n×n matrix all whose entries are equal $\text{1}\text{n}$. In the present paper it is proved that the conjecture holds true for the circulant matrices A=αI_n+ βP_n, α, β?0, α+;β=1, and $\text{A=}\text{(nJ}{}_{\mathrm{n}}\text{?I}{}_{\mathrm{n}}\text{?P}{}_{\mathrm{n}}\text{)}\text{(n?2)}$, where I_n and P_n are respectively the n×n identify matrix and the n×n permutation matrix with 1's in positions (1,2), (2,3),…, (n?1, n), (n, 1).     

Zeros for accretive operators satisfying certain boundary conditions

Let X be a Banach space with the dual space $\text{X}{}^1$ to be uniformly convex, let D ? X be open, and let $\text{T:}\text{D}\text{?}\text{→ X}$ be strongly accretive (i.e., for some k < 1: (λ ? k)∥ u ? v∥ ? ∥(λ ? 1)(u ? v)+ T(u) ? T(v)∥ for all $\text{u, v ?}\text{D}\text{?}$ and λ > k). Suppose T is demicontinuous and strongly accretive and suppose there exists z?D satisfying: T(x) t(x ? z) for all x??D and t < 0. Then it is shown that T has a unique zero in $\text{D}\text{?}$. This result is then applied to the study of existence of zeros of accretive mappings under apparently different types of boundary conditions on T.     

Oscillatory and asymptotic behavior of solutions of differential equations with deviating arguments

The oscillatory and asymptotic behavior of solutions of a class of nth order nonlinear differential equations, with deviating arguments, of the form (E, δ) L_nx(t) + δq(t) f(x[g₁(t)],…, x[g_m(t)]) = 0, where δ = ± 1 and L₀x(t) = x(t), L_kx(t) = a_k(t)(L_{k ? 1}x(t))^., $\text{k = 1, 2,…, n (}{}^{\mathrm{.}}\text{=}\text{d}\text{dt}\text{)}$, is examined. A classification of solutions of (E, δ) with respect to their behavior as t → ∞ and their oscillatory character is obtained. The comparisons of (E, 1) and (E, ?1) with first and second order equations of the form y^.(t) + c₁(t) f(y[g₁(t)],…, y[g_m(t)]) = 0 and (a_{n ? 1}(t)z^.(t))^. ? c₂(t) f(z[g₁(t)],…, z[g_m(t)]) = 0, respectively, are presented. The obtained results unify, extend and improve some of the results by Graef, Grammatikopoulos and Spikes, Philos and Staikos.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

Local asymptotic normality for progressively censored likelihood ratio statistics and applications

Let X_n,1 ≤ X_n,2 ≤ … ≤ X_n,n be the ordered variables corresponding to a random sample of size n with respect to a family of probability measures {P_θ:θ ∈ Θ} where Θ is an open subset of the real line. In many practical situations the X_n,i are the observables and experimentation must be curtailed prior to X_n,n. If τ_n is a stopping variable adapted to the σ-fields {σ(X_n,1,…,X_n,k): 1 ≤ k ≤ n} and P_n,θ the projection of P_θ onto σ(X_n,1,…,X_n,τn), the local asymptotic normality of the stopped progressively censored likelihood ratio statistics is established with θ, $\text{θ}{}_{\mathrm{n}}\text{= θ + un}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{∈ Θ}$ and θ, u held fixed, under certain conditions on the underlying distribution and on τ_n. Conditions are also given to ensure the local asymptotic normality of likelihood ratio statistics where the underlying observations are given in a series scheme.     

The behaviour of (k,…,kn,n−ik)ci/i! is asymptotically normal

Let N(n,i) = (k,…,kⁿ,n?ik)c^i/i, i = O.…,[n/k]. We prove that the random variable X_n such that $\text{P(X}{}_{\mathrm{<mtext>n</mtext>}}\text{= i) =}\text{N(n, i)}\text{Σ}{}_{\mathrm{<mtext>j</mtext>}}\text{N(n, j)}$ has asymptotically (n → ∞) a normal distribution and we give some combinatorial applications of this result.We also improve a result of Godsil [3] dealing with matchings in graph.     

Linear transformations on matrices: the invariance of generalized permutation matrices—III

Let F be a field, F1 be its multiplicative group, and $\text{H}$ = {H:H is a subgroup of F1 and there do not exist a, b?F1 such that Ha+b?H}. Let D_n be the dihedral group of degree n, H be a nontrivial group in $\text{H}$, and τ_n(H) = {α = (α₁, α₂,…, α_n):α_i?H}. For σ?D_n and α?τ_n(H), let P(σ, α) be the matrix whose (i,j) entry is α_iδ_iσ(j) (i.e., a generalized permutation matrix), and

$\text{P(D}{}_{\mathrm{n}}\text{, H) = {P(σ, α):σ?D}{}_{\mathrm{n}}\text{, α?τ}{}_{\mathrm{n}}\text{(H)}}$

. Let M_n(F) be the vector space of all n×n matrices over F and $\text{T}$P(D_n, H) = {T:T is a linear transformation on M_n (F) to itself and T(P(D_n, H)) = P(D_n, H)}. In this paper we classify all T in $\text{T}$P(D_n, H) and determine the structure of the group $\text{T}$P(D_n, H) (Theorems 1 to 4). An expository version of the main results is given in Sec. 1, and an example is given at the end of the paper.     

Potential theory associated with Uhlenbeck-Ornstein process

Some parallel results of Gross' paper (Potential theory on Hilbert space, J. Functional Analysis1 (1967), 123–181) are obtained for Uhlenbeck-Ornstein process U(t) in an abstract Wiener space (H, B, i). Generalized number operator $\text{N}$ is defined by $\text{N}$f(x) = ?lim_∈←0{E[f($\text{U}$(τ^∈_ξ))] ? f(x)}/E[τ^∈_ξ, where τ_x^? is the first exit time of U(t) starting at x from the ball of radius ? with center x. It is shown that $\text{N}$f(x) = ?trace D²f(x)+〈Df(x),x〉 for a large class of functions f. Let r_t(x, dy) be the transition probabilities of U(t). The λ-potential G_λf, λ > 0, and normalized potential Rf of f are defined by G_λf(X) = ∫₀^∞e^?λtr_tf(x) dt and Rf(x) = ∫₀^∞ [r_tf(x) ? r_tf(0)] dt. It is shown that if f is a bounded Lip-1 function then trace D²G_λf(x) ? 〈DG_λf(x), x〉 = ?f(x) + λG_λf(x) and trace D²Rf(x) ? 〈DRf(x), x〉 = ?f(x) + ∫_Bf(y)p₁(dy), where p₁ is the Wiener measure in B with parameter 1. Some approximation theorems are also proved.     

Concrete model theory for a class of operators with unitary part

Let m and v_t, 0 ? t ? 2π be measures on T = [0, 2π] with m smooth. Consider the direct integral $\text{H}$ = ⊕L²(v^t) dm(t) and the operator $\text{(L?)(t, λ) = e}{}^{\mathrm{?i\lambda }}\text{?(t, λ) ? 2e}{}^{\mathrm{?i\lambda }}\text{∫}{}_{\mathrm{t}}{}^{\mathrm{2\pi }}\text{∫}{}_{\mathrm{T}}\text{?(s, x) e(s, t) dv}{}_{\mathrm{s}}\text{(x) dm(s)}$ on $\text{H}$, where e(s, t) = exp ∫_s^t ∫_Tdv_λ(θ) dm(λ). Let μ_t be the measure defined by $\text{∫}{}_{\mathrm{T}}\text{?(x) dμ}{}_{\mathrm{t}}\text{(x) = ∫}{}_0{}^{\mathrm{t}}\text{∫}{}_{\mathrm{T}}\text{?(x) dv}{}_{\mathrm{s}}\text{dm(s)}$ for all continuous ?, and let ?_t(z) = exp[?∫ (e^iθ + z)(e^iθ ? z)^?1dμ_t(gq)]. Call {v_t} regular iff for all $\text{t, ¦?}{}_{\mathrm{t}}\text{(e}{}^{\mathrm{i\theta }}\text{)¦ = ¦?}{}_{\mathrm{2\pi }}\text{(e}{}^{\mathrm{i\theta }}\text{)¦}$ for 1 a.e.     

Un lemme de Mañé bilatéralA bilateral version of Mañé's lemma

We prove that, assuming some hyperbolicity on the dynamical system T:X→X and some regularity on $\text{f:X→}\text{R}$, there exists $\text{θ:X→}\text{R}$ in the same regularity class and such that α(f)?f?θ+θ°T?β(f), where α(f), β(f) are the infimum and the supremum of the averages of f along periodic orbits. To cite this article: T. Bousch, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 533–536.     

Some Remarks on the Number of Solutions to the Equation f(X1) + … + f(Xn) = 0

Let S, T be finite sets, and let f be a function from S to T. Fix an element t in T, and let c_n denote the number of n-tuples (X₁,…,X_n) satisfying f(X₁) + … + f(X_n) = t here + denotes any binary operation on T. The sequence c₁, c₂,… satisfies a linear recurrence relation of degree at most |T|.