Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

On the closability of some positive definite symmetric differential forms on c0∞(ω)

Let $\text{S}$ be a Dirichlet form in $\text{L}{}^2\text{(Ω; m)}$, where Ω is an open subset of $\text{R}$ⁿ, n ? 2, and m a Radon measure on Ω; for each integer k with 1 ? k < n, let $\text{S}$_k be a Dirichlet form on some k-dimensional submanifold $\text{Ω}{}_{\mathrm{k}}$ of Ω. The paper is devoted to the study of the closability of the forms E with domain $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ and defined by: $\text{(?,g)=}$$\text{E}$$\text{(?, g)+}\text{∑}\text{i}\text{p}\text{=1}$$\text{E}$k_i where 1 ? k_p < ? < n, and where , g^k_i denote restrictions of ?, g in $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ to . Conditions are given for E to be closable if, for each i = 1,…, p, one has k_i = n ? i. Other conditions are given for E to be nonclosable if, for some i, k_i < n ? i.     

An external theorem on divisors of a number

Main result: Let ? be a collection of divisors of N = pe11?penn (e1 = minei for all i? {1,…, n}) such that if any two numbers in ? are coprime then their common multiple is N and maximal with respect to this condition, i.e. there is no other collection satisfying this condition which properly contains ?. We prove that ? consists of at least $\text{e}{}_1\text{П}{}^{\mathrm{n}}{}_{\mathrm{i\; =\; 2}}\text{(e}{}_{\mathrm{i}}\text{+ 1)?(e}{}_1\text{? 2)}$ elements.     

On the probability that k positive integers are relatively prime II

Given a set S of positive integers let $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t)}$ denote the number of k-tuples 〈m₁, …, m_k〉 for which $\text{m}{}_{\mathrm{i}}\text{∈ S ? [1, t]}$ and (m₁, …, m_k) = 1. Also let $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n)}$ denote the probability that k integers, chosen at random from $\text{S ? [1, n]}$, are relatively prime. It is shown that if P = {p₁, …, p_r} is a finite set of primes and S = {m : (m, p₁ … p_r) = 1}, then $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t) = (td(S))}{}^{\mathrm{k}}\text{Π}{}_{\mathrm{\nu ?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) + O(t}{}^{\mathrm{k?1}}\text{)}$ if k ≥ 3 and $\text{Z}{}_2{}^{\mathrm{S}}\text{(t) = (td(S))}{}^2\text{Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^2\text{) + O(t}\text{log}\text{t)}$ where d(S) denotes the natural density of S. From this result it follows immediately that $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) = (ζ(k))}{}^{\mathrm{?1}}\text{Π}{}_{\mathrm{p\in P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{)}{}^{\mathrm{?1}}$ as n → ∞. This result generalizes an earlier result of the author's where $\text{P = ?}$ and S is then the whole set of positive integers. It is also shown that if S = {p₁^x₁ … p_r^x_r : x_i = 0, 1, 2,…}, then $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → 0}$ as n → ∞.     

An extremal problem for sets with applications to graph theory

Let X₁, …, X_n be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let A_ij and B_ij be subsets of X_i that satisfy |A_ij| ? r_i and |B_ij| ? s_i for 1 ? i ? n, 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{ij}}\text{) = ?}$ for 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{il}}\text{) ≠ ?}$ for 1 ? j < l ? h. We prove that $\text{h?}\text{Π}\text{i=1}\text{n}\text{r}{}_{\mathrm{i}}\text{+s}{}_{\mathrm{i}}\text{r}{}_{\mathrm{i}}$. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).     

Solution of a system of functional-differential equations arising from an optimization problem

In connection with an optimization problem, all functions ?: Iⁿ → $\text{R}$ with continuous nonzero partial derivatives and satisfying

$\text{??}\text{?x,}{}_{\mathrm{i}}\text{??}\text{?x}{}_{\mathrm{j}}$

for all x_i, x_j ≠ I, i, j = 1,2,…, n (n > 2) are determined (I is an interval of positive real numbers).     

A fundamental theorem on lambda-matrices with applications —II. Difference equations with constant coefficients

The fundamental theorem of the title refers to a spectral resolution for the inverse of a lambda-matrix $\text{L(λ) =}\text{∑}\text{i=0}\text{l}\text{A}{}_{\mathrm{i}}\text{λ}{}^{\mathrm{i}}$ where the A_i are n×n complex matrices and detA_l ≠ 0. In this paper general solutions are formulated for difference equations of the form $\text{∑}\text{i=0}\text{l}\text{A}{}_{\mathrm{i}}\text{u}{}_{\mathrm{r\; +\; i}}\text{= ?}{}_{\mathrm{\gamma }}\text{, r = 1, 2,…}$. The use of these solutions is illustrated i new proof of Franklin's results describing the sums of powers of the eigenvalues of L(λ) (the generalized Newton identities), and in obtaining convergence proofs for the application of Bernoulli's method to the solution of $\text{∑}\text{i=0}\text{l}\text{A}{}_{\mathrm{i}}\text{S}{}^{\mathrm{i}}\text{= 0}$ for matrix S.     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

An optimum testing algorithm for some symmetric coherent systems

A symmetric coherent system (or k-out-of-n system) is a system composed of n components CO₁, CO₂ …, CO_n, each component existing in either a working or failing state. Such a system is in a working state if and only if k or more of its components are working, where 1 ? k ? n. It is assumed that the components can only be tested individually, and every test gives perfect information as to whether the tested component is working or failing. Let P_i, be the a priori probability that the component CO_i is working and C_i, be the cost of testing component CO_i. An optimal (minimum total expected cost) testing algorithm is an algorithm to determine the condition of a given symmetric coherent system by testing some of its components individually. In general, such an algorithm is a sequential process, that is, the next component to be tested is a function of the outcomes of the tests already applied. Every (optimal) testing algorithm corresponds to a (optimal) feasible testing policy which is basically a binary rooted tree with some component assigned to each node. In this paper an algorithm is presented for constructing an optimal feasible testing policy for symmetric coherent systems, where $\text{C}{}_{\mathrm{i}}\text{P}{}_{\mathrm{i}}\text{≠}\text{C}{}_{\mathrm{j}}\text{P}{}_{\mathrm{j}}$ and $\text{C}{}_{\mathrm{i}}\text{(1 ? P}{}_{\mathrm{i}}\text{)}\text{≠}\text{C}{}_{\mathrm{j}}\text{(1 ? P}{}_{\mathrm{j}}\text{)}$ whenever i ≠ j. This algorithm can be implemented as an optimal testing algorithm with polynomial complexity. Moreover, it is proven that any optimal testing algorithm corresponds to some feasible testing policy which can be generated by this algorithm.     

A characterization of planar cubic graphs

If S is a collection of circuits in a graph G, the circuits in S are said to be consistently orientable if G can be oriented so that they are all directed circuits. If S is a set of three or more consistently orientable circuits such that no edge of G belongs to more than two circuits of S, then S is called a ring if there exists a cyclic ordering C₀, C₁,…, C_{n ? 1}, C₀ of the n circuits in S such that $\text{EC}{}_{\mathrm{i}}\text{? EC}{}_{\mathrm{j}}\text{≠ ?}$ if and only if j = i or j ≡ i ? 1 (mod n) or j ≡ i + 1 (mod n). We characterise planar cubic graphs in terms of the non-existence of a ring with certain specified properties.     

Explicit expressions for Bezoutians

The following commutator identity is proved:

$\text{[u(S}{}^1\text{), v(S)] = [v}{}_1\text{(S}{}^1\text{), u}{}_1\text{(S)]}$

. Here S is the n by n matrix of the truncated shift operator S = (Γ_i,i+1), i = 0, 1,…, n ? 1, and u, v are two polynomials of degree not exceeding n. The reciprocal polynomial f;₁ of a polynomial f; of degree ?n is defined by $\text{f}{}_1\text{(z) = z}{}^{\mathrm{n}}\text{f(}\text{1}\text{z}\text{)}$. The commutator identity is closely related to some properties of the Bezoutian matrix of a pair of polynomials; it is used to obtain the Bezoutian matrix in the form of a simple expression in terms of S and S¹. To demonstrate the advantage of this expression, we show how it can be used to obtain simple proofs of some interesting corollaries.     

On the law of large numbers for stationary sequences

We show that if X_i is a stationary sequence for which $\text{S}{}_{\mathrm{n}}\text{B}{}_{\mathrm{n}}$ converges to a finite non zero random variable of constant sign, where S_n=X₁+X₂+?+X_n and B_n is a sequence of constants, then B_n is regularly varying with index 1. If in addition $\text{Σ}\text{P}\text{(|X}{}_1\text{|>B}{}_{\mathrm{n}}$ is finite, then $\text{E}\text{|X}{}_1\text{|}$ is finite, and if in addition to this X_i satisfies an asymptotic independence condition, $\text{E}\text{X}{}_1\text{≠ 0}$.     

Phase reconstruction from magnitude of band-limited multidimensional signals

In this paper, the problem of phase reconstruction from magnitude of multidimensional band-limited functions is considered. It is shown that any irreducible band-limited function f(z₁…,z_n), z_i ? $\text{C}$, i=1, …, n, is uniquely determined from the magnitude of f(x₁…,x_n): | f(x₁…,x_n)|, x_i ? $\text{R}$, i=1,…, n, except for (1) linear shifts: ^{i(α1z1+…+α_n2n+β}), β, α_i?$\text{R}$, i=1,…, n; and (2) conjugation: $\text{f}{}^1\text{(z}{}_1{}^1\text{,…,z}{}_{\mathrm{n}}{}^1\text{)}$.     

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 divided difference inequality for n-convex functions

For a₍₁₎ ? a₍₂₎ ? ··· ? a_(n) ? 0, b₍₁₎ ? b₍₂₎ ? ··· ? b_(n) ? 0, the ordered values of a_i, b_i, i = 1, 2,…, n, m fixed, m ? n, and p ? 1 it is shown that

$\text{∑}\text{1}\text{n}\text{a}{}_{\mathrm{i}}\text{b}{}_{\mathrm{i}}\text{?}\text{∑}\text{1}\text{m}\text{a}{}^{\mathrm{p}}{}_{\mathrm{(i)}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}\text{∑}\text{1}\text{m?k?1}\text{b}{}^{\mathrm{q}}{}_{\mathrm{(i)}}\text{+}\text{b}{}^{\mathrm{q}}{}_{\mathrm{[m?k]}}\text{(k+1)}{}^{\mathrm{<mtext>q</mtext><mtext>p</mtext>}}{}^{\mathrm{<mtext>1</mtext><mtext>q</mtext>}}$

where $\text{1}\text{p}\text{+}\text{1}\text{q}\text{= 1, b}{}_{\mathrm{[j]}}\text{= b}{}_{\mathrm{(j)}}\text{+ b}{}_{\mathrm{(j\; +\; 1)}}\text{+ ··· + b}{}_{\mathrm{(n)}}\text{,}\text{and}\text{k}$ is the integer such that $\text{b}{}_{\mathrm{(m\; ?\; k\; ?\; 1)}}\text{?}\text{b[m ? k]}\text{(k + 1)}$ and $\text{b}{}_{\mathrm{(m\; ?\; k)}}\text{<}\text{b}{}_{\mathrm{[m\; ?\; k\; +\; 1]}}\text{k}$. The inequality is shown to be sharp. When p < 1 and a_(i)'s are in increasing order then the inequality is reversed.     

An Lp bound for the Riesz and Bessel potentials of orthonormal functions

Let ψ₁, …,ψ_N be orthonormal functions in $\text{R}$^d and let $\text{u}{}_{\mathrm{i}}\text{= (?Δ)}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}\text{ψ}{}_{\mathrm{i}}$, or $\text{u}{}_{\mathrm{i}}\text{= (?Δ + 1)}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}\text{ψ}{}_{\mathrm{i}}$, and let $\text{p(x) = ∑¦u}{}_{\mathrm{i}}\text{(x)¦}{}^2$. L^p bounds are proved for p, an example being $\text{∥p∥}{}_{\mathrm{p}}\text{? A}{}_{\mathrm{d}}\text{N}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}\text{for}\text{d ? 3}$, with p = d(d ? 2)^?1. The unusual feature of these bounds is that the orthogonality of the ψ_i, yields a factor $\text{N}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}$ instead of N, as would be the case without orthogonality. These bounds prove some conjectures of Battle and Federbush (a Phase Cell Cluster Expansion for Euclidean Field Theories, I, 1982, preprint) and of Conlon (Comm. Math. Phys., in press).     

Uniqueness of solutions of nonlinear Dirichlet problems

In this paper, we consider the uniqueness of radial solutions of the nonlinear Dirichlet problem $\text{Δu + ?(u) = 0}\text{in}\text{Ω}\text{with}\text{u = 0}\text{on}\text{?Ω,}\text{where}\text{Δ = ∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{?}{}^2\text{?x}{}_{\mathrm{i}}{}^2\text{,?}$ satisfies some appropriate conditions and Ω is a bounded smooth domain in $\text{R}$ⁿ which possesses radial symmetry. Our uniqueness results apply to, for instance, $\text{?(u) = u}{}^{\mathrm{p}}\text{, p > 1}$, or more generally λu + ∑_{i = 1}^ka_iu^pi, λ ? 0, a_i > 0 and p_i > 1 with appropriate upper bounds, and Ω a ball or an annulus.     

Enumeration of pairs of permutations

Let π = (a₁, a₂, …, a_n), ? = (b₁, b₂, …, b_n) be two permutations of $\text{Z}{}_{\mathrm{n}}\text{= {1, 2, …, n}}$. A rise of π is pair a_i, a_i+1 with a_i < a_i+1; a fall is a pair a_i, a_i+1 with a_i > a_i+1. Thus, for i = 1, 2, …, n ? 1, the two pairs a_i, a_i+1; b_i, b_i+1 are either both rises, both falls, the first a rise and the second a fall or the first a fall and the second a rise. These possibilities are denoted by RR, FF, RF, FR. The paper is concerned with the enumeration of pairs π, p with a given number of RR, FF, RF, FR. In particular if ω_n denotes the number of pairs with RR forbidden, it is proved that $\text{∑}{}^{\mathrm{\infty }}{}_0\text{ω}{}_{\mathrm{n}}\text{z}{}^{\mathrm{n}}\text{n!n!}\text{=}\text{1}\text{?(z)}$, $\text{?(z) = ∑}{}^{\mathrm{\infty }}{}_0\text{(-1)}{}^{\mathrm{n}}\text{z}{}^{\mathrm{n}}\text{n!n!}$. More precisely if ω(n, k) denotes the number of pairs π, p with exactly k occurences of RR(or FF, RF, FR) then $\text{1 + ∑}{}^{\mathrm{\infty }}{}_{\mathrm{n=1}}\text{z}{}^{\mathrm{n}}\text{n!n!}$$\text{∑}{}^{\mathrm{n?1}}{}_{\mathrm{k=0}}\text{ω(n, k)x}{}^{\mathrm{k}}\text{=}\text{(1 ? x)}\text{(?(z(1 ? x)) ? x)}$.