On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

On the density of various classes of groups

Let $\text{T}$ be a subset of the set of all isomorphism classes of finite groups. We consider the number F_$\text{g}$(x) of positive integers n≤x such that all groups of order n lie in $\text{T}$. When $\text{T}$ consists of the isomorphism classes of all finite groups of any of the following types, we obtain an asymptotic formula for F_$\text{g}$(x): cyclic groups, abelian groups, nilpotent groups, supersolvable groups, and solvable groups. In the course of the arguments, we also obtain, for almost all n, a lower bound for the number of groups of a given order n.     

Diophantine problems in variables restricted to the values 0 and 1

Let $\text{F}$x₁,…,x_s be a form of degree d with integer coefficients. How large must s be to ensure that the congruence $\text{F}$(x₁,…,x_s) ≡ 0 (mod m) has a nontrivial solution in integers 0 or 1? More generally, if $\text{F}$ has coefficients in a finite additive group G, how large must s be in order that the equation $\text{F}$(x₁,…,x_s) = 0 has a solution of this type? We deal with these questions as well as related problems in the group of integers modulo 1 and in the group of reals.     

Unbounded derivations tangential to compact groups of automorphisms,II

Let G be a compact abelian group, and τ an action of G on a C¹-algebra $\text{U}$, such that $\text{U}$^τ(γ)$\text{U}$^τ(γ)¹ = $\text{U}$^τ(0) $\text{U}$^τ for all $\text{γ ?}\text{G}\text{?}$, where $\text{U}$^τ(γ) is the spectral subspace of $\text{U}$ corresponding to the character γ on G. Derivations δ which are defined on the algebra $\text{U}$_F of G-finite elements are considered. In the special case δ¦_{$\text{U}$^τ} = 0 these derivations are characterized by a cocycle on $\text{G}\text{?}$ with values in the relative commutant of $\text{U}$^τ in the multiplier algebra of $\text{U}$, and these derivations are inner if and only if the cocycles are coboundaries and bounded if and only if the cocycles are bounded. Under various restrictions on G and τ properties of the cocycle are deduced which again give characterizations of δ in terms of decompositions into generators of one-parameter subgroups of τ(G) and approximately inner derivations. Finally, a perturbation technique is devised to reduce the case δ($\text{U}$_F) ? $\text{U}$_F to the case δ($\text{U}$_F) ? $\text{U}$_F and δ¦_{$\text{U}$^τ} = 0. This is used to show that any derivation δ with D(δ) = $\text{U}$_F is wellbehaved and, if furthermore G = T¹ and δ($\text{U}$_F) ? $\text{U}$_F the closure of δ generates a one-parameter group of ¹-automorphisms of $\text{U}$. In the case G = T^d, d = 2, 3,… (finite), and δ($\text{U}$_F) ? $\text{U}$_F it is shown that δ extends to a generator of a group of ¹-automorphisms of the σ-weak closure of $\text{U}$ in any G-covariant representation.     

Fourier transforms of smooth functions on certain nilpotent Lie groups

The authors consider irreducible representations $\text{π ?}\text{N}\text{?}$ of a nilpotent Lie group and define a Fourier transform for Schwartz class (and other) functions φ on N by forming the kernels K_φ(x, y) of the trace class operations π_φ = ∝_Nφ(n)π_ndn, regarding the π as modeled in L²(R^k) for all π in general position. For a special class of groups they show that the models, and parameters λ labeling the representations in general position, can be chosen so the joint behavior of the kernels K_φ(x, y, λ) can be interpreted in a useful way. The variables (x, y, λ) run through a Zariski open set in Rⁿ, n = dim N. The authors show there is a polynomial map u = A(x, y, λ) that is a birational isomorphism A: Rⁿ → Rⁿ with the following properties. The Fourier transforms F₁φ = K_φ(x, y, λ) all factor through A to give “rationalized” Fourier transforms Fφ(u) such that Fφ ° A = F₁φ. On the rationalized parameter space a function f(u) is of the form F_φ = f ? f is Schwartz class on Rⁿ. If polynomial operators T?P(N) are transferred to operators $\text{T}\text{?}$ on Rⁿ such that $\text{F(Tφ) =}\text{T}\text{?}\text{(Fφ), P(N)}$ is transformed isomorphically to P(Rⁿ).     

An application of L-functions of imaginary quadratic fields

Let F₁(x, y),…, F_2h+1(x, y) be the representatives of equivalent classes of positive definite binary quadratic forms of discriminant ?q (q is a prime such that q ≡ 3 mod 4) with integer coefficients, then the number of integer solutions of F_i(x, y) = n (i = 1,…, 2h + 1) can be calculated for each natural number n using L-functions of imaginary quadratic field $\text{Q}$((?q)^1/2).     

A note on polynomial matrix functions over a finite field

Let F_n denote the ring of n×n matrices over the finite field F=GF(q) and let A(x)=A_Nx^N+ ?+ A₁x+A₀?F_n[x]. A function $\text{?:F}{}_{\mathrm{n}}\text{→F}{}_{\mathrm{n}}$ is called a right polynomial function iff there exists an A(x)?F_n[x] such that $\text{?(B)=A}{}_{\mathrm{N}}\text{B}{}^{\mathrm{N}}\text{+?+A}{}_1\text{B+ A}{}_0$ for every B?F_n. This paper obtains unique representations for and determines the number of right polynomial functions.     

Corresponding residue systems in normal extensions

Let K and K′ be number fields with L = K · K′ and F = KφK′. Suppose that $\text{K}\text{F}$ and $\text{K′}\text{F}$ are normal extensions of degree n. Let $\text{B}$ be a prime ideal in L and suppose that $\text{B}$ is totally ramified in $\text{K}\text{F}$ and in $\text{K′}\text{F}$. Let π be a prime element for $\text{B}$_K = $\text{B}$ φ K, and let f(x) ∈ F[x] be the minimum polynomial for π over F. Suppose that $\text{B}$_K · $\text{D}$_L = ($\text{B}$^≠)^e. Then,

$\text{M(B\# : K, K′) =}\text{min}\text{{m, e(t + 1)}}$

, where $\text{t =}\text{min}\text{{t(}\text{K}\text{F}\text{), t(}\text{K′}\text{F}\text{)}}$ and m is the largest integer such that ($\text{B}$_K′)^nm/e φ f($\text{D}$_K′) ≠ {φ}.If we assume in addition to the above hypotheses that [K : F] = [K′: F] = pⁿ, a prime power, and that $\text{B}$ divides p and is totally ramified in $\text{L}\text{F}$, then

$\text{M(B\# : K, K′) ? p}{}^{\mathrm{n?1}}\text{[(p ? 1)(t + p]}$

, with t = t($\text{B}$ : L/F).     

Infinite-variate wide-sense Markov processes and functional analysis for bounded operator-forming vectors

Let p, q be arbitrary parameter sets, and let $\text{H}$ be a Hilbert space. We say that x = (xⁱ)_i?q, xⁱ ? $\text{H}$, is a bounded operator-forming vector (?$\text{H}$_F^q) if the Gram matrix 〈x, x〉 = [(xⁱ, x^j)]_i?q,j?q is the matrix of a bounded (necessarily ≥ 0) operator on $\text{l}{}_{\mathrm{q}}{}^2$, the Hilbert space of square-summable complex-valued functions on q. Let A be p × q, i.e., let A be a linear operator from $\text{l}{}_{\mathrm{q}}{}^2$ to $\text{l}{}_{\mathrm{p}}{}^2$. Then exists a linear operator ǎ from (the Banach space) $\text{H}$_F^q to $\text{H}$_F^p on $\text{D}$(A) = {x:x ? $\text{H}$_F^q, $\text{A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is p × q bounded on $\text{l}{}_{\mathrm{q}}{}^2$} such that y = ǎx satisfies y^j?σ(x) = {space spanned by the xⁱ}, 〈y, x〉 = A〈x, x〉 and $\text{〈y, y〉 = A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}{}^1$. This is a generalization of our earlier [J. Multivariate Anal.4 (1974), 166–209; 6 (1976), 538–571] results for the case of a spectral measure concentrated on one point. We apply these tools to investigate q-variate wide-sense Markov processes.     

On the rate for uniform strong consistency of empirical distributions of independent nonidentically distributed multivariate random variables

Let X_j = (X_1j ,…, X_pj), j = 1,…, n be n independent random vectors. For x = (x₁ ,…, x_p) in R^p and for α in [0, 1], let F_j${}^1$(x) = αI(X_1j < x₁ ,…, X_pj < x_p) + (1 ? α) I(X_1j ≤ x₁ ,…, X_pj ≤ x_p), where I(A) is the indicator random variable of the event A. Let F_j(x) = E(F_j${}^1$(x)) and D_n = sup_{x, α} max_{1 ≤ N ≤ n} |Σ₀ⁿ(F_j${}^1$(x) ? F_j(x))|. It is shown that P[D_n ≥ L] < 4pL exp{?2(L²n^?1 ? 1)} for each positive integer n and for all L² ≥ n; and, as n → ∞, $\text{D}{}_{\mathrm{n}}\text{= 0((n}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ with probability one.     

The lattice of subfields of a radical extension

Let x^m ? a be irreducible over F with char $\text{F?m}$ and let α be a root of x^m ? a. The purpose of this paper is to study the lattice of subfields of $\text{F(α)}\text{F}$ and to this end $\text{C(}\text{F(α)}\text{F}\text{, k)}$ is defined to be the number of subfields of F(α) of degree k over $\text{F. C(}\text{F(α)}\text{F}\text{, p}{}^{\mathrm{n}}\text{)}$ is explicitly determined for p a prime and the following structure theorem for the lattice of subfields is proved. Let N be the maximal normal subfield of F(α) over F and set n = |N : F|, then $\text{C(}\text{F(α)}\text{F}\text{, k) = C(}\text{F(α)}\text{F}\text{, (k, n)) = C(}\text{N}\text{F}\text{, (k, n))}$. The irreducible binomials x^s ? b, x^s ? c are said to be equivalent if there exist roots β^s = b, γ^s = a such that F(β) = F(γ). All the mutually inequivalent binomials which have roots in F(α) are determined. Finally these results are applied to the study of normal binomials and those irreducible binomials x^2e ? a which are normal over F (char F ≠ 2) together with their Galois groups are characterized.     

On Dynkin's Markov property of random fields associated with symmetric processes

Let p(t, x, y) be a symmetric transition density with respect to a σ-finite measure m on (E, $\text{E}$), g(x,y)=∫p(t,x,y)dt, and $\text{M}\text{={σ-finite measures μ?0:∫g(x,y)μ(}\text{d}\text{x)μ(}\text{d}\text{y)<∞}}$. There exists a Gaussian random field $\text{Φ={?}{}_{\mathrm{\mu }}\text{:μ?}\text{M}\text{}}$ with mean 0 and covariance $\text{E}\text{?}{}_{\mathrm{\mu }}\text{?}{}_{\mathrm{\nu }}\text{=∫g(x,y)μ(}\text{d}\text{x)ν(}\text{d}\text{y)}$. Letting $\text{F}\text{(B)=σ{?}{}_{\mathrm{\mu }}\text{:μ(B}{}^{\mathrm{c}}\text{)=0}}$ we consider necessary and sufficient conditions for the Markov property (MP) on sets B, C: $\text{F}$(B), $\text{F}$(C) c.i. given $\text{F}$(B ∩ C). Of crucial importance is the following, proved by Dynkin: $\text{E}\text{{?}{}_{\mathrm{\mu }}\text{∣}\text{F}\text{(B)}=?}{}_{\mathrm{\mu B}}$, where μ_B is the hitting distribution of the process corresponding to p, m with initial law μ. Another important fact is that ?_μ=?_ν iff μ, ν have the same potential. Putting these together with an additional transience assumption, we present a potential theoretic proof of the following necessary and sufficient condition for (MP) on sets B, C: For every x?E, T_B∩C=T_B+T_C∮ θ_TB=T_C+T_B∮θ_TC a.s. P^x where, for D ? $\text{E}$, T_D is the hitting time of D for the process associated with p, m. This implies a necessary condition proved by Dynkin in a recent preprint for the case where B∪C=E and B, C are finely closed.     

Characterization of similarities between two n-frames of projectors

An n-frame on a Banach space $\text{X}$ is E=(E₁,?, E_n) where the E_j's are bounded linear operators on $\text{X}$ such that E_j≠0,

$\text{∑}\text{j=1}\text{n}\text{E}{}_{\mathrm{j}}$

, and E_jE_k=δ_jkE_k (j, k=1,?, n). It is known that if two n-frames E and F are sufficiently close to each other, then they are similar, that is, F_j=TE_jT^-1 with T a bounded linear operator. Among the operators which realize the similarity of the two frames, there is the balanced transformation U(F, E)=(Σⁿ_j=1F_jE_j)(Σⁿ_j=1E_jF_jE_j)^{$\text{-1}\text{2}$}. One of our main results is a local characterization of the balanced transformation. Another operator which implements the similarity between E and F is the direct rotation R(F, E). It comes up in connection with the study of the set of all n-frames as a Banach manifold with an affine connection. Finally, it is shown that for quite a large set of pairs of 2-frames, the direct rotation has a global characterization.     

Finitely generated submodules of differentiable functions II

Let [$\text{E}$(Ω)]^p be the Cartesian product of the space of real-valued infinitely differentiable functions on a connected open set Ω in $\text{R}$ⁿ with itself p-times. The finitely generated submodules of [$\text{E}$(Ω)]^p are of the form im(F) where F: [$\text{E}$(Ω)]^q → [$\text{E}$(Ω)]^p is a p × q matrix of infinitely differentiable functions on Ω. Let $\text{r =}\text{max}\text{{}\text{rank}\text{(F(x)): x ? Ω}}$. The main results of the present paper are that for Ω ? $\text{R}$ⁿ, if the finitely generated submodule im(F) is closed in [$\text{E}$(Ω)]^p, then for every x?ω with rank(F(x)) < r there exists an r × r sub-matrix A of F such that x is a zero of finite order of det(A), and for Ω ? $\text{R}$¹ the converse also holds.     

Nonlinear equations involving m-accretive operators

Let X be a Banach space and T an m-accretive operator defined on a subset D(T) of X and taking values in 2^x. For the class of spaces whose bounded closed and convex subsets have the fixed point property for nonexpansive self-mappings, it is shown here that two boundary conditions which imply existence of zeroes for T, appear to be equivalent. This fact is then used to prove that if there exists x₀?D(T) and a bounded open neighborhood U of x₀, such that $\text{¦T(x}{}_0\text{)¦ < r ? ¦T(x)¦}$ for all x??U ∩ D(T), then the open ball B(0; r) is contained in the range of T.     

On the analytic continuation of a certain Dirichlet series

A Dirichlet series associated with a positive definite form of degree δ in n variables is defined by

$\text{D}{}_{\mathrm{F}}\text{(s,p,α)}\text{=}\text{∑}\text{α∈Z}{}^{\mathrm{n}}\text{?{0}}\text{F(α)}{}^{\mathrm{?s}}\text{e(ρF(α)+〈α, α〉)}$

where ? ∈ $\text{Q}$, α ∈ $\text{Q}$ⁿ, 〈x, y〉 = x₁y₁ + ? + x_ny_n, e(a) = exp (2πia) for a ∈ $\text{R}$, and s = σ + ti is a complex number. The author proves that: (1) D_F(s, ?, α) has analytic continuation into the whole s-plane, (2) D_F(s, ?, α), ? ≠ 0, is a meromorphic function with at most a simple pole at $\text{s =}\text{n}\text{δ}$. The residue at $\text{s =}\text{n}\text{δ}$ is given explicitly. (3) ? = 0, α ? $\text{Z}$ⁿ, D_F(s, 0, α) is analytic for $\text{α>,}\text{n}\text{(δ ? 1)}$.     

Arithmetic progressions that consist only of primes

Let N_m(x) be the number of arithmetic progressions that consist of m terms, all primes and not larger than x, and set $\text{F}{}_{\mathrm{m}}\text{(x) =}\text{C}{}_{\mathrm{m}}\text{x}{}^2\text{log}{}^{\mathrm{m}}\text{x}$ (C_m explicitly given). It is shown that Hardy and Littlewood's prime k-tuple conjecture implies that N_m(x) = F_m(x){1 + Σ_j=1^Na_jlog^?jx + O((log x)^?N?1)}, (here the bracket represents an asymptotic series with explicitly computable coefficients). This formula holds rather trivially for m = 1 and m = 2. It is proved here for m = 3, by the Vinogradov version of the Hardy-Ramanujan-Littlewood circle method.     

Hilbert space representations of general discrete time stochastic processes

We show that under mild conditions the joint densities Px₁,…,x_n) of the general discrete time stochastic process X_n on $\text{pH}$ can be computed via

$\text{Px}{}_1\text{,…,x}{}_{\mathrm{n}}\text{(x}{}_1\text{,…,x}{}_{\mathrm{n}}\text{) = 6?T(x}{}_1\text{)…T(x}{}_{\mathrm{n}}\text{)6}{}^2$

where ? is in a Hilbert space $\text{pH}$, and T (x), x ? $\text{pH}$ are linear operators on $\text{pH}$. We then show how the Central Limit Theorem can easily be derived from such representations.