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.     

Decomposable bilinear numerical radii

Let A be an n-square normal matrix over $\text{C}$, and Q_{m, n} be the set of strictly increasing integer sequences of length m chosen from 1,…, n. For α,β∈Q_{m, n} denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k∈{0,1,…,m} write z.sfnc;α∩β|=k if there exists a rearrangement of 1,…,m, say i₁,…,i_k, i_k+1,…,i_m, such that α(i_j)=β(i_j), j=1,…,k, and {α(i_k+1),…,α(i_m)};∩{β(i_k+1),…,β(i_m)}=ø. Let

be the group of n-square unitary matrices. Define the nonnegative number

$\text{?}{}_{\mathrm{k}}\text{(A)=}\text{max}\text{U∈}\textcolor{red}{}\text{|}\text{det}\text{(U}{}^1\text{AU) [α|β]|}$

, where |α∩β|=k. Theorem 1 establishes a bound for ?_k(A), 0?k<m?1, in terms of a classical variational inequality due to Fermat. Let A be positive semidefinite Hermitian, n?2m. Theorem 2 leads to an interlacing inequality which, in the case n=4, m=2, resolves in the affirmative the conjecture that

$\text{?}{}_{\mathrm{m}}\text{(A)??}{}_{\mathrm{m?1}}\text{(A)????}{}_0\text{(A)}$

.     

Diophantine inequalities for forms of odd degree

If $\text{F}$ is a form of odd degree k with real coefficients in s variables where s ≥ c₁(k), then there are integers x₁,… x_s not all zero, with |$\text{F}$(x₁,… x_s)| < 1.     

Some limit results for longest common subsequences

The length l_n of a longest common subsequence before time n sequences (B₁₁, B₁₂, …) (B₂₁, B₂₂, …) is the cardinality of the largest increasing set of pairs of integers {(j_1α, j_2α)}

$\text{l?}\text{j}{}_{11}\text{<}\text{j}{}_{12}\text{<·<}\text{j}{}_{11}{}_{\mathrm{n}}\text{?}\text{n}\text{l?}\text{j}{}_{21}\text{<}\text{j}{}_{22}\text{<·<}\text{j}{}_{21}{}_{\mathrm{n}}\text{?}\text{n}$

such that ?1?α?l_n, (B_1j1α=B_2j2α). If B₁ and B₂ are independent random sequences with co-ordinates i.i.d. uniform on {1, 2, …, k}, it follows from Kingman's subadditive ergodic theorem that the ratio l_n/n converges to a constant c_k a.s. A method of deriving lower bounds for the constants c_k is given, the bounds obtained improving known lower bounds, for k>2. The rate of decrease of c_k with k is shown to be no faster than 1/√k, contrasting with P{B_1i?B_2i}=1/k. Finally, an alternative method of deriving lower bounds is given and used to improve the lower bound for c₂.     

Pairs of additive equations II. Large odd degree

Let k be an odd positive integer. Davenport and Lewis have shown that the equations

$\text{a}{}_1\text{x}{}_1{}^{\mathrm{k}}\text{+…+a}{}_{\mathrm{n}}\text{x}{}_{\mathrm{n}}{}^{\mathrm{k}}\text{=0}$

with integer coefficients, have a nontrivial solution in integers x₁,…, x_N provided that

$\text{N?[36klog6k]}$

Here it is shown that for any ? > 0 and k > k₀(?) the equations have a nontrivial solution provided that

$\text{N?}\text{8}\text{log 2}\text{+?}\text{k log k.}$

     

Resolvable perfect cyclic designs

Let k, λ, and υ be positive integers. A perfect cyclic design in the class PD(υ, k, λ) consists of a pair (Q, B) where Q is a set with |Q| = υ and B is a collection of cyclically ordered k-subsets of Q such that every ordered pair of elements of Q are t apart in exactly λ of the blocks for t = 1, 2, 3,…, k?1. To clarify matters the block [a₁, a₂, …, a_k] has cyclic order a₁ < a₂ < a₃ … < a_k < a₁ and a_i and a_i+1 are said to be t apart in the block where i + t is taken mod k. In this paper we are interested only in the cases where λ = 1 and υ ≡ 1 mod k. Such a design has $\text{υ(υ ? 1)}\text{k}$ blocks. If the blocks can be partitioned into υ sets containing $\text{(υ ? 1)}\text{k}$ pairwise disjoint blocks the design is said to be resolvable, and any such partitioning of the blocks is said to be a resolution. Any set of $\text{υ ? 1)}\text{k}$ pairwise disjoint blocks together with a singleton consisting of the only element not in one of the blocks is called a parallel class. Any resolution of a design yields υ parallel classes. We denote by RPD(υ, k, 1) the class of all resolvable perfect cyclic designs with parameters υ, k, and 1. Associated with any resolvable perfect cyclic design is an orthogonal array with k + 1 columns and υ rows with an interesting conjugacy property. Also a design in the class RPD(υ, k, 1) is constructed for all sufficiently large υ with υ ≡ 1 mod k.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

An extremal result for sum-free sequences

Let a₁ < a₂ < … be a sequence of positive integers such that no a_k is a sum of distinct other terms. Erdös conjectured that if a₁ ≥ n, then $\text{Σ1}\text{a}{}_{\mathrm{k}}\text{<}\text{log}\text{2 + ?}{}_{\mathrm{n}}$, where, ?_n → 0 as n → ∞. This result, which is the best possible, is established in this paper.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

Recursive linear orders with recursive successivities

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities $\text{U}$ is recursively categorical if every recursive linear order with recursive successivities isomorphic to $\text{U}$ is in fact recursively isomorphic to $\text{U}$. We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k₁+g₁+k₂+g₂+…+g_n-1+k_n where each k_n is a finite order type, non-empty for i?{2,…,n-1} and each g_i is an order type from among {ω,ω^*,ω+ω^*}∪{k·η:k<ω}.     

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.     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

On monotone functions of tree structures

Let T be a rooted tree structure with n nodes a₁,…,a_n. A function f: {a₁,…,a_n} into {1 < ? < k} is called monotone if whenever a_i is a son of a_j, then f(a_i) ≥ f(a_j). The average number of monotone bijections is determined for several classes of tree structures. If k is fixed, for the average number of monotone functions asymptotic equivalents of the form c · ?^?nn^{?$\text{3}\text{2}$} (n → ∞) are obtained for several classes of tree structures.     

On intersecting families of finite sets

Let X = [1, n] be a finite set of cardinality n and let $\text{F}$ be a family of k-subsets of X. Suppose that any two members of $\text{F}$ intersect in at least t elements and for some given positive constant c, every element of X is contained in less than c |$\text{F}$| members of $\text{F}$. How large |$\text{F}$| can be and which are the extremal families were problems posed by Erdös, Rothschild, and Szemerédi. In this paper we answer some of these questions for n > n₀(k, c). One of the results is the following: let $\text{t = 1,}\text{3}\text{7}\text{< c <}\text{1}\text{2}$. Then whenever $\text{F}$ is an extremal family we can find a 7-3 Steiner system $\text{B}$ such that $\text{F}$ consists exactly of those k-subsets of X which contain some member of $\text{B}$.     

Extremal traces on some group-invariant C1-algebras

Let $\text{U}$ be a UHF-algebra of Glimm type n^∞, and {α_g: g?G} a strongly continuous group of ¹-automorphisms of product type on $\text{U}$, for G compact. Let $\text{U}$^α be the C¹-subalgebra of fixed elements of $\text{U}$. We show that any extremal normalized trace on $\text{U}$^α arises as the restriction of a symmetric product state ? on $\text{U}$ of the form ? = ?_k?1 ω. As an example we classify the extremal traces on $\text{U}$^α for the case G = SU(n), α_g = ?_{k ? 1} Ad(g).     

A determinant of symmetric forms

Let Δ(α + β) = |H_λ2?r+1| where H_r is the complete symmetric function in (α₁ + β₁), (α₂ + β₂), …, (α_n + β_n). It is proved that Δ(α + β) ? Δ(α) + Δ(β). This inequality is generalised for certain symmetric functions defined by Littlewood. Let . Then we prove that Ω(α + β) ? Ω(α) + Ω(β). Here λ₁, λ₂, λ₃, …, λ_n is a partition such that λ_n > λ_n?1 > ··· > λ₂ > λ₁.     

On a conjecture by D. Ž. D̄okovic

It is shown that if $\text{A?Ω}{}_{\mathrm{n}}\text{?{J}{}_{\mathrm{n}}\text{}}$ satisfies

$\text{nkσ}{}_{\mathrm{k}}\text{(A)?(n?k+1)}{}^2\text{σ}{}_{\mathrm{k?1}}\text{(A)}$

$\text{(k=1,2,…,n)}$

, where σ_k(A) denotes the sum of all kth order subpermanent of A, then Per[λJ_n+(1?λ)A] is strictly decreasing in the interval 0<λ<1.     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

A note on the least prime in an arithmetic progression

Let k, l denote positive integers with (k, l) = 1. Denote by p(k, l) the least prime p ≡ l(mod k). Let P(k) be the maximum value of p(k, l) for all l. We show $\text{lim inf}\text{P(k)}\text{(?(k)}\text{log}\text{k)}\text{≥ e}{}^{\mathrm{\gamma }}\text{= 1.78107…}$, where γ is Euler's constant and ? is Euler's function. We also show $\text{P(k)}\text{(?(k)}\text{log}\text{k)}\text{→ ∞}$ for almost all k.