The sum of aΩ(n) over integers n ≤ x with all prime factors between a and y

For a > 0 let $\text{ψ}{}_{\mathrm{a}}\text{(x, y) =}\text{Σ}\text{a}{}^{\mathrm{\Omega (n)}}$, the sum taken over all n, 1 ≤ n ≤ x such that if p is prime and p|n then a < p ≤ y. It is shown for u < about ($\text{log log}\text{x}\text{log log log}\text{x}$) that $\text{ψ}{}_{\mathrm{a}}\text{(x, x}{}^{\mathrm{<mtext>1</mtext><mtext>u</mtext>}}\text{) ? x(}\text{log}\text{x)}{}^{\mathrm{a?1}}\text{p}{}_{\mathrm{a}}\text{(u)}$, where p_a(u) solves a delay differential equation much like that for the Dickman function p(u), and the asymptotic behavior of p_a(u) is worked out.     

The probability that k positive integers are relatively r-prime

If r, k are positive integers, then $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ denotes the number of k-tuples of positive integers (x₁, x₂, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r = 1. An explicit formula for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ is derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}\text{n}{}^{\mathrm{k}}\text{=}\text{1}\text{ζ(rk)}$.If S = {p₁, p₂, …, p_a} is a finite set of primes, then 〈S〉 = {p₁^a₁p₂^a₂…p_s^a_s; p_i ∈ S and a_i ≥ 0 for all i} and $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ denotes the number of k-tuples (x₁, x₃, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r ∈ 〈S〉. Asymptotic formulas for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ are derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}\text{n}{}^{\mathrm{k}}\text{=}\text{(p}{}_1\text{… p}{}_{\mathrm{a}}\text{)}{}^{\mathrm{rk}}\text{ζ(rk)(p}{}_1{}^{\mathrm{rk}}\text{? 1) … (p}{}_{\mathrm{s}}{}^{\mathrm{rk}}\text{? 1)}$.     

An asymptotic evaluation of the cycle index of a symmetric group

Let $\text{Z(S}{}_{\mathrm{n}}\text{;?(x))}$ denote the polynomial obtained from the cycle index of the symmetric group Z(S_n) by replacing each variable s_i by f(x¹). Let f(x) have a Taylor series with radius of convergence ? of the form f(x)=x^k + a_k+1x^k+1 + a_k+2x^k+2+? with every a₁?0. Finally, let 0<x<1 and let x??. We prove that

This limit is used to estimate the probability (for n and p both large) that a point chosen at random from a random p-point tree has degree n + 1. These limiting probabilities are independent of p and decrease geometrically in n, contrasting with the labeled limiting probabilities of $\text{1}\text{n!e}$.In order to prove the main theorem, an appealing generalization of the principle of inclusion and exclusion is presented.     

A transformation theorem for one-dimensional F-expansions

If f is a monotone function subject to certain restrictions, then one can associate with any real number x between zero and one a sequence {a_n(x)} of integers such that

$\text{x=f(a}{}_1\text{(x) + f(a}{}_2\text{(x) +f(a}{}_3\text{(x) +…)))}$

. In this paper properties of the function F defined by

$\text{Fx=g(a}{}_1\text{(x) + g(a}{}_2\text{(x) +g(a}{}_3\text{(x) +…)))}$

, where g is any function satisfying the same restrictions as f, are discussed. Principally, F is found to be useful in finding stationary measures on the sequences {a_n(x)}.     

Transcendence order over Qp in Cp

Let (K, ∥ · ∥) be a valued transcendence degree 1 extension of $\text{Q}$_p. An element x ∈ K transcendental over $\text{Q}$_p is said to have order ≤a (a > 0) if there exists C_x > 0 such that every polynomial P(X) ∈ $\text{Q}$_p [X] satisfies

$\text{?}\text{log;}\text{(P(x))? ?}\text{log}\text{∥P∥+c}{}_{\mathrm{x}}\text{(}\text{deg}\text{P)}{}^{\mathrm{a}}$

when ∥ · ∥ is the Gauss norm on $\text{Q}$_p[X]. No x ∈ $\text{C}$_p can have order ≤α if α < 1 but we construct some x ∈ $\text{C}$_p with order ≤ 1. Furthermore, we prove order ≤α is stable by algebraic extension.     

La valeur optimale des programmes entiersThe optimal value of integer programs

We present a formula for the optimal value f_c(y) of the integer program $\text{max}\text{{c′x∣x∈}\text{Ω}\text{(y)∩}\text{N}{}^{\mathrm{n}}\text{}}$ where $\text{Ω}\text{(y)}$ is the convex polyhedron $\text{{x∈}\text{R}{}^{\mathrm{n}}\text{∣Ax=y,}\text{x?0}}$. It is a consequence of Brion and Vergne's formula which evaluates the sum . As in linear programming, f_c(y) can be obtained by inspection of the reduced-costs at the vertices of the polyhedron. We also provide an explicit result that relates f_c(ty) and the optimal value of the associated continous linear program, for large values of $\text{t∈}\text{N}$. To cite this article: J.B. Lasserre, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 863–866.     

Arnold's canonical matrices and the asymptotic simplification of ordinary differential equations

Let A(x,ε) be an n×n matrix function holomorphic for |x|?x₀, 0<ε?ε₀, and possessing, uniformly in x, an asymptotic expansion $\text{A(x,ε)?Σ}{}^{\mathrm{\infty }}{}_{\mathrm{r=0}}\text{A}{}_{\mathrm{r}}\text{(x) ε}{}^{\mathrm{r}}$, as ε→0⁺. An invertible, holomorphic matrix function P(x,ε) with an asymptotic expansion $\text{P(x,ε)?Σ}{}^{\mathrm{\infty }}{}_{\mathrm{r=0}}\text{P}{}_{\mathrm{r}}\text{(x)ε}{}^{\mathrm{r}}$, as ε→0⁺, is constructed, such that the transformation y = P(x,ε)z takes the differential equation $\text{ε}{}^{\mathrm{h}}\text{dy}\text{dx}\text{= A(x,ε)y,h}$ a positive integer, into $\text{ε}{}^{\mathrm{h}}\text{dz}\text{dx}\text{= B(x,ε)z}$, where B(x,ε) is asymptotically equal, to all orders, to a matrix in a canonical form for holomorphic matrices due to V.I. Arnold.     

A comparison result related to Gauss measureUn résultat de comparaison relatif à la mesure de Gauss

In this paper we prove a comparison result for weak solutions to linear elliptic problems of the type

where $\text{Ω}$ is an open set of $\text{R}{}^{\mathrm{n}}$ (n?2), ?(x)=(2π)^?n/2exp(?|x|²/2), a_ij(x) are measurable functions such that a_ij(x)ξ_iξ_j??(x)|ξ|² a.e. $\text{x∈Ω}$, $\text{ξ∈}\text{R}{}^{\mathrm{n}}$ and f(x) is a measurable function taken in order to guarantee the existence of a solution $\text{u∈}\text{H}{}^1{}_0\text{(?,Ω)}$ of (1.1). We use the notion of rearrangement related to Gauss measure to compare u(x) with the solution of a problem of the same type, whose data are defined in a half-space and depend only on one variable. To cite this article: M.F. Betta et al., C. R. Acad. Sci. Paris, Ser. I 334 (2002) 451–456.     

On the number of groups of a given order

Letting G(n) denote the number of nonisomorphic groups of order n, it is shown that for square-free n, G(n) ≤ ?(n) and G(n) ≤ (log n)^c on a set of positive density. Letting F_k(x) denote the number of n ≤ x for which G(n) = k, it is shown that $\text{F}{}_2\text{(x) =}\text{O(x(}\text{log}{}_4\text{x)}\text{(}\text{log}{}_3\text{x)}{}^2\text{)}$, where log_rx denotes the r-fold iterated logarithm.     

Weak and strong extensions of ordinary differential operators

Let A be a second order differential operator with positive leading term defined on an interval J of R. In this paper we study conditions for the equality D₀(A) = D₁(A) to hold. Here D₀(A) and D₁(A) are the domains of the minimal and maximal extensions of A respectively. Under the general assumption that $\text{A(1)}\text{and}\text{A}{}^1\text{(1)}$ are bounded above it is proven that under certain conditions D₀(A) = D₁(A) if functions which are constant near the boundaries of J are in $\text{D}{}_0\text{(A) ∩ D}{}_0\text{(A}{}^1\text{)}$ whenever they are in $\text{D}{}_1\text{(A) ∩ D}{}_1\text{(A}{}^1\text{)}$. In particular if A is formally selfadjoint and 1 ?D₁(A) then D₁(A) = D₀(A) if and only if 1 ?D₀(A). When the measure of J is infinite at both ends D₀(A) is always equal to D₁(A). This fact is used to show that the leading term of A as well as its terminal coefficient can be chosen arbitrarily (although not independently of one another) in such a way that the equality D₀ = D₁ holds.     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

A maximization problem and its application to canonical correlation

Let Σ be an n × n positive definite matrix with eigenvalues λ₁ ≥ λ₂ ≥ … ≥ λ_n > 0 and let M = {x, y | x?Rⁿ, y?Rⁿ, x ≠ 0, y ≠ 0, x′y = 0}. Then for x, y in M, we have that $\text{x′Σy}\text{(x′Σxy′Σy)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{≤}\text{(λ}{}_1\text{? λ}{}_{\mathrm{n}}\text{)}\text{(λ}{}_1\text{+ λ}{}_{\mathrm{n}}\text{)}$ and the inequality is sharp. If

$\text{∑=}\text{∑}{}_{11}\text{∑}{}_{12}\text{∑}{}_{21}\text{∑}{}_{22}$

is a partitioning of Σ, let θ₁ be the largest canonical correlation coefficient. The above result yields $\text{θ}{}_1\text{≤}\text{(λ}{}_1\text{? λ}{}_{\mathrm{n}}\text{)}\text{(λ}{}_1\text{+ λ}{}_{\mathrm{n}}\text{)}$.     

Minimax estimators for a multinormal precision matrix

Let S_p×p ～ Wishart (Σ, k), Σ unknown, k > p + 1. Minimax estimators of Σ^?1 are given for L₁, an Empirical Bayes loss function; and L₂, a standard loss function (R_i ≡ E(L_i ∣ Σ), i = 1, 2). The estimators are $\text{Σ}\text{?}{}^{\mathrm{?1}}\text{=}\text{a}\text{S}{}^{\mathrm{?1}}\text{+}\text{br}\text{(S)I}{}_{\mathrm{p\times p}}$, a, b ≥ 0, r(·) a functional on $\text{R}{}^{\mathrm{<mtext>p(p+2)</mtext><mtext>2</mtext>}}$. Stein, Efron, and Morris studied the special cases $\text{Σ}{}_{\mathrm{<mtext>a</mtext>}}{}^{\mathrm{?1}}\text{=}\text{a}\text{S}{}^{\mathrm{?1}}\text{(E}\text{Σ}\text{?}{}_{\mathrm{<mtext>k?p?1</mtext>}}{}^{\mathrm{?1}}\text{= Σ}{}^{\mathrm{?1}}\text{)}$ and $\text{Σ}\text{?}{}_1{}^{\mathrm{?1}}\text{=}\text{a}\text{S}{}^{\mathrm{?1}}\text{+ (b/tr S)I}$, for certain, a, b. From their work $\text{R}{}_1\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_1{}^{\mathrm{?1}}\text{; S) ≤ R}{}_1\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_{\mathrm{<mtext>a</mtext>}}{}^{\mathrm{?1}}\text{; S) (?Σ)}$, a = k ? p ? 1, b = p² + p ? 2; whereas, we prove $\text{R}{}_2\text{(Σ}{}^{\mathrm{?1}}\text{Σ}\text{?}{}_{\mathrm{<mtext>a</mtext>}}{}^{\mathrm{?1}}\text{; S) ≤}\text{R}{}_2\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_1{}^{\mathrm{?1}}\text{; S) (?Σ)}$. The reversal is surprising because $\text{L}{}_1\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_1{}^{\mathrm{?1}}\text{; S) →}\text{L}{}_2\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_1{}^{\mathrm{?1}}\text{; S)}$ a.e. (for a particular L₂). Assume $\text{R}$ (compact) ? $\text{S}$, $\text{S}$ the set of p × p p.s.d. matrices. A “divergence theorem” on functions F_p×p : $\text{R}$ → $\text{S}$ implies identities for R_i, i = 1, 2. Then, conditions are given for $\text{R}{}_{\mathrm{i}}\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}^{\mathrm{?1}}\text{; S) ≤}\text{R}{}_{\mathrm{i}}\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_1{}^{\mathrm{?1}}\text{; S) ≤}\text{R}{}_{\mathrm{i}}\text{(Σ}{}^{\mathrm{?1}}\text{,}\text{Σ}\text{?}{}_{\mathrm{<mtext>a</mtext>}}{}^{\mathrm{?1}}\text{; S) (?Σ)}$, i = 1, 2. Most of our results concern estimators with r(S) = t(U)/tr(S), U = p ∣S∣^1/p/tr(S).     

Compositions of singular integral operators

The composition of two Calderón-Zygmund singular integral operators is given explicitly in terms of the kernels of the operators. For φ?L¹(Rⁿ) and ε = 0 or 1 and ∝ φ = 0 if ε = 0, let Ker(φ) be the unique function on R^{n + 1} homogeneous of degree ?n ? 1 of parity ε that equals φ on the hypersurface x₀ = 1. Let Sing(φ, ε) denote the singular integral operator , which exists under suitable growth conditions on ? and φ. Then Sing(φ, ε₁) Sing(ψ, ε₂)f = ?2π²(∝ φ)(∝ ψ)f + Sing(A, ε₁, + ε₂)f, where

(with notation $\text{¦t¦}{}_0{}^{\mathrm{a}}\text{= ¦t¦}{}^{\mathrm{a}}\text{and}\text{¦t¦}{}_1{}^{\mathrm{a}}\text{= ¦t¦}{}^{\mathrm{a}}\text{sgn}\text{t}$). This result is used to show that the mapping ψ → A is a classical pseudo-differential operator of order zero if φ is smooth, with top-order symbol

$\text{ω}{}_0\text{(x,?)=?πiθ(?)∫θ(x?y)}\text{sgn}\text{y·?dy}\text{if}\text{?}{}_1\text{=1}$

,

$\text{=?2θ(?)∫θ(x?y)}\text{log}\text{|y·?|dy}\text{if}\text{?}{}_1\text{=0}$

where θ(ξ) is a cut-off function. These results are generalized to singular integrals with mixed homogeneity.     

Deterministic version of Wigner's semicircle law for the distribution of matrix eigenvalues

It is proved that Wigner's semicircle law for the distribution of eigenvalues of random matrices, which is important in the statistical theory of energy levels of heavy nuclei, possesses the following completely deterministic version. Let A_n=(a_ij), 1?i, ?n, be the nth section of an infinite Hermitian matrix, {λ⁽ⁿ⁾}_1?k?n its eigenvalues, and {u_k⁽ⁿ⁾}_1?k?n the corresponding (orthonormalized column) eigenvectors. Let $\text{v}{}^1{}_{\mathrm{n}}\text{=(a}{}_{\mathrm{n1}}\text{,a}{}_{\mathrm{n2}}\text{,?,a}{}_{\mathrm{n,n?1}}\text{)}$, put

$\text{X}{}_{\mathrm{n}}\text{(t)=[n(n-1)]}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{∑}\text{k=1}\text{[(n-1)t]}\text{|v}{}_{\mathrm{n}}{}^1\text{u}{}_{\mathrm{f}}{}^{\mathrm{(n-1)}}\text{|}{}^2\text{,}\text{0?t?1}$

(bookeeping function for the length of the projections of the new row v¹_n of A_n onto the eigenvectors of the preceding matrix A_n?1), and let finally

$\text{F}{}_{\mathrm{n}}\text{(x)=n}{}^{-1}\text{(}\text{number of}\text{λ}{}_{\mathrm{k}}{}^{\mathrm{(n)}}\text{?x}\text{n}\text{,1?k?n)}$

(empirical distribution function of the eigenvalues of $\text{A}{}_{\mathrm{n}}\text{n}$. Suppose (i) $\text{lim}{}_{\mathrm{n}}\text{a}{}_{\mathrm{nn}}\text{n}\text{=0}$, (ii) lim_nX_n(t)=Ct(0<C<∞,0?t?1). Then

$\text{F}{}_{\mathrm{n}}\text{?W(·,C)}\text{(n→∞)}$

,where W is absolutely continuous with (semicircle) density

$\text{w(x,C)=}\text{(2Cπ)}{}^{-1}\text{(4C-x}{}^2{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{for}\text{|x|?2}\text{C}\text{0}\text{for}\text{|x|?2}\text{C}$

     

Diagonal forms over finite fields

We shall establish for all finite fields GF(pⁿ) the following result of Chowla: given a positive integer m greater than one and the finite field GF(p), p a prime, such that x^m = ?1 is solvable in GF(p), then there exists an absolute positive constant c, $\text{c ≤}\text{10}\text{ln}\text{2}$, such that for each set of s nonzero elements a_i of GF(p), $\text{a}{}_1\text{x}{}_1{}^{\mathrm{m}}\text{+ ? + a}{}_{\mathrm{s}}\text{x}{}_{\mathrm{s}}{}^{\mathrm{m}}$ has a non-trivial zero in GF(p) if s ≥ c ln m.     

A new normal form of Boolean functions

A new normal form of Boolean functions based on the sum (mod 2), product and negation is presented. Let n = {1, 2,…, n}, let A_s be the family of s-element subsets of a set A and let π_a?φx_a = 1. Then every Boolean function ?(x₁,x₂,…,x_n) has a normal form

$\text{?(x}{}_1\text{,x}{}_2\text{,…,x}{}_{\mathrm{n}}\text{=}\text{∑}\text{s=0}\text{n}\text{⊕}\text{Π}\text{A∈n}{}_{\mathrm{s}}\text{1⊕d}{}_{\mathrm{A}}\text{Π}\text{a∈A}\text{x}{}_{\mathrm{a}}$

with unique coefficients d_A? {0, 1}. A transformation of Galois normal form into the present normal form is also shown.     

Fractional part sums and divisor functions

Elementary methods are used to study sums of the form $\text{Σ}{}_{\mathrm{d\le x}}\text{{}\text{x}\text{d}\text{}}{}^{\mathrm{t}}$ for integers p and t, t > 0, where {x} denotes the fractional part of x. These sums are then used to study sums of the form $\text{Σ}{}_{\mathrm{d\le x}}\text{d}{}^{\mathrm{p}}\text{P}{}_{\mathrm{t}}\text{(}\text{x}\text{d}\text{)}$ for integers p and t, t > 0, where P_t(x) = B_t({x}) and B_t(x) are Bernoulli polynomials. some general results on sums of error terms are used to study sums of the form Σ_n≤xn^tσ_a(n) and Σ_n≤xE_t(n) for integers t and a, a ≥ 0, where σ_a(n) is the sum of the ath powers of the divisors of n and E_t(x) is the error term in the sum Σ_n≤xn^tσ_a(n).     

A global genericity theorem for bifurcations in variational problems

Let C be a Banach space, H a Hilbert space, and let F(C,H) be the space of C^∞ functions f: C × H → R having Fredholm second derivative with respect to x at each (c, x) ?C × H for which $\text{D?}{}_{\mathrm{c}}\text{(x) = 0}$; here we write $\text{?}{}_{\mathrm{c}}\text{(x)}$ for $\text{?(c, x)}$. Say ? is of standard type if at all critical points of ?_c it is locally equivalent (as an unfolding) to a quadratic form Q plus an elementary catastrophe on the kernel of Q. It is proved that if f?F (A × B, H) satisfies a certain ‘general position’ condition, and dim B ? 5, then for most a?A the function f_o?F(B,H) is of standard type. Using this it is shown that those f?F(B,H) of standard type form an open dense set in F(B,H) with the Whitney topology. Thus both results are Hilbert-space versions of Thom's theorem for catastrophes in $\text{R}$ⁿ.     

Measuring flatness in linear spaces

Let L be a finite-dimensional normed linear space and let M be a compact subset of L lying on one side of a hyperplane through 0. A measure of flatness for M is the number $\text{D(M) =}\text{inf}\text{{}\text{sup}\text{f(x)}\text{f(y)}\text{: x, y ? M}}$, where the infimum is over all f in $\text{L}{}^1$ which are positive on M. Thus D(M) = 1 if M is flat, but otherwise D(M) > 1. On the other hand, let E(M) be a second measure on M defined as follows: If M is linearly independent, E(M) = 1. If M is linearly dependent, then (1) let Z be a minimal, linearly dependent subset of M; (2) partition Z into mutually exclusive subsets U = {u₁, …, u_p} and V = {v₁, …, v_q} such that there exist positive coefficients a_i and b_i for which Σ_{i = 1}^pa_iu_i = Σ_{i = 1}^qb_iv_i; (3) let $\text{r =}\text{max}\text{{}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{p}}\text{a}{}_{\mathrm{i}}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{q}}\text{b}{}_{\mathrm{i}}\text{,}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{p}}\text{b}{}_{\mathrm{i}}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{q}}\text{a}{}_{\mathrm{i}}\text{}}$; (4) let E(M) be the supremum of all ratios r which can be formed by steps (1), (2) and (3). The main result of this paper is that these two measures are the same: D(M) = E(M). This result is then used to obtain results concerning the Banach distance-coefficient between an arbitrary finite-dimensional normed linear space and Hilbert space.