A note on bideterminants for Schur superalgebras

Let S(m|n,r)_Z be a Z-form of a Schur superalgebra S(m|n,r) generated by elements ξ_i,j. We solve a problem of Muir and describe a Z-form of a simple S(m|n,r)-module D_λ,Q over the field Q of rational numbers, under the action of S(m|n,r)_Z. This Z-form is the Z-span of modified bideterminants [T_?:T_i] defined in this work. We also prove that each [T_?:T_i] is a Z-linear combination of modified bideterminants corresponding to (m|n)-semistandard tableaux T_i.     

Representing abstract groups by powers of a graph

We deal with the problem of representing several abstract groups simultaneously by one graph as automorphism groups of its powers. We call subgroups Γ₁,…, Γ_n of a finite group Γ representable iff there is a graph G and an injective mapping φ from ∪_i=1ⁿΓ_i into the symmetric group on V(G) such that for i=1,…, n φ|_Γi is a monomorphism onto Aut Gⁱ. We give a necessary and a sufficient condition for groups being representable, the latter implying, e.g., that finite groups Γ₁≤…≤Γ_n are representable.     

Maximizing the probability of correctly ordering random variables using linear predictors

Let (T₁, x₁), (T₂, x₂), …, (T_n, x_n) be a sample from a multivariate normal distribution where T_i are (unobservable) random variables and x_i are random vectors in R^k. If the sample is either independent and identically distributed or satisfies a multivariate components of variance model, then the probability of correctly ordering {T_i} is maximized by ranking according to the order of the best linear predictors {E(T_i|x_i)}. Furthermore, it orderings are chosen according to linear functions {b′x_i} then the conditional probability of correct order given (T_i = t₁; i = 1, …, n) is maximized when b′x_i is the best linear predictor. Examples are given to show that linear predictors may not be optimal and that using a linear combination other that the best linear predictor may give a greater probability of correctly ordering {T_i} if {(T_i, x_i)} are independent but not identically distributed, or if the distributions are not normal.     

On a class of martingale inequalities

Let Z = {Z₀, Z₁, Z₂,…} be a martingale, with difference sequence X₀ = Z₀, X_i = Z_i ? Z_{i ? 1}, i ≥ 1. The principal purpose of this paper is to prove that the best constant in the inequality λP(sup_i |X_i| ≥ λ) ≤ C sup_iE |Z_i|, for λ > 0, is C = (log 2)^?1. If Z is finite of length n, it is proved that the best constant is $\text{C}{}_{\mathrm{n}}\text{= [n(2}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{? 1)]}{}^{\mathrm{?1}}$. The analogous best constant C_n(z) when Z₀ ≡ z is also determined. For these finite cases, examples of martingales attaining equality are constructed. The results follow from an explicit determination of the quantity G_n(z, E) = sup_zP(max_i=1,…,n |X_i| ≥ 1), the supremum being taken over all martingales Z with Z₀ ≡ z and E|Z_n| = E. The expression for G_n(z,E) is derived by induction, using methods from the theory of moments.     

Subsets of a finite set that intersect each other in at most one element

In this paper we study de Bruijn-Erdös type theorems that deal with the foundations of finite geometries. The following theorem is one of our main conclusions. Let S₁,…, S_n be n subsets of an n-set S. Suppose that |S_i| ? 3 (i = 1,…,n) and that |S_i ∩ S_j| ? 1 (i ≠ j;i,j = 1,…,n). Suppose further that each S_i has nonempty intersection with at least n ? 2 of the other subsets. Then the subsets S₁,…,S_n of S are one of the following configurations. (1) They are a finite projective plane. (2) They are a symmetric group divisible design and each subset has nonempty intersection with exactly n ? 2 of the other subsets. (3) We have n = 9 or n = 10 and in each case there exists a unique configuration that does not satisfy (1) or (2).     

Counting cycles and finite dimensional L norms

We obtain sharp bounds for the number of n-cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. We prove sharp estimates on both ∑_i=1ⁿx_i^k and ∑_i=1ⁿ|x_i|^k, subject to the constraints that ∑_i=1ⁿx_i²=C and ∑_i=1ⁿx_i=0.     

Finite factorizable groups with solvable ℙ2-subnormal subgroups

A subgroup H of a finite group G is called ?²-subnormal whenever there exists a subgroup chain H = H ₀ ≤ H ₁ ≤ ... ≤ H _n = G such that |H _i+1: H _i | divides prime squares for all i. We study a finite group G = AB on assuming that A and B are solvable subgroups and the indices of subgroups in the chains joining A and B with the group divide prime squares. In particular, we prove that a group of this type is solvable without using the classification of finite simple groups.     

On marginal distributions and isomorphisms of stationary processes

LetT be an invertible ergodic aperiodic measure preserving transformation of a Lebesgue space, letA be a finite alphabet, and let π be a probability measure onA ⁿ which admits a mixing shift-invariant measureμ _π onΩ=A ^? such that the marginals of anyn successive coordinates are π and the entropyh(T) ofT is smaller than the entropy of the shift in (Ω,μ _π). Then there exists a shift invariant measure ν_π in Ω which also has marginals π and for whichT is isomorphic to the shift in (Ω, ν_π). This contains Krieger's finite generator theorem and strengthens the measure theoretic part of his approximation theorem for shift-invariant measures by showing that the preassigned marginal π can not only be achieved up to an ε>0 but exactly. Our result also contains an as yet unpublished theorem of Krieger, which says thatT can be embedded in an arbitrary mixing subshift of finite type, as long as the entropy of the subshift under the measure with maximal entropy exceeds that ofT. In the final section we show that the method can be extended to yield also exact marginals for the generator in the Jewett-Krieger theorem, i.e.T is shown to be isomorphic to a shift in (Ω, ν_π) where ν_π has exact marginals π and the shift is uniquely ergodic on the support of ν_π.     

Approximation of functions of finite variation by superpositions of a Sigmoidal function

The aim of this note is to generalize a result of Barron [1] concerning the approximation of functions, which can be expressed in terms of the Fourier transform, by superpositions of a fixed sigmoidal function. In particular, we consider functions of the type h(x) = ∫ℝ^d ƒ (〈t, x〉)dμ(t), where μ is a finite Radon measure on ℝ^d and ƒ : ℝ → ℂ is a continuous function with bounded variation in ℝ We show (Theorem 2.6) that these functions can be approximated in L₂-norm by elements of the set G_n = {Σ_i=0^staggeredn c_ig(〈a_i, x〉 + b_i) : a_iℝ^d, b_i, c_iℝ}, where g is a fixed sigmoidal function, with the error estimated by C/n^1/2, where C is a positive constant depending only on f. The same result holds true (Theorem 2.9) for f : ℝ → ℂ satisfying the Lipschitz condition under an additional assumption that ∫ℝ^d6t6e^d|u(t)| > ∞     

Effective Fast Algorithms for Polynomial Spectral Factorization

Let p(z) be a polynomial of degree n having zeros |ξ₁|≤???≤|ξ _m |<1<|ξ _m+1|≤???≤|ξ _n |. This paper is concerned with the problem of efficiently computing the coefficients of the factors u(z)=∏ _i=1 ^m (z?ξ _i ) and l(z)=∏ _i=m+1 ⁿ (z?ξ _i ) of p(z) such that a(z)=z ^?m p(z)=(z ^?m u(z))l(z) is the spectral factorization of a(z). To perform this task the following two-stage approach is considered: first we approximate the central coefficients x _?n+1,. . .x _n?1 of the Laurent series x(z)=∑ _i=?∞ ^+∞ x _i z ⁱ satisfying x(z)a(z)=1; then we determine the entries in the first column and in the first row of the inverse of the Toeplitz matrix T=(x _i?j ) _i,j=?n+1,n?1 which provide the sought coefficients of u(z) and l(z). Two different algorithms are analyzed for the reciprocation of Laurent polynomials. One algorithm makes use of Graeffe's iteration which is quadratically convergent. Differently, the second algorithm directly employs evaluation/interpolation techniques at the roots of 1 and it is linearly convergent only. Algorithmic issues and numerical experiments are discussed.     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.     

Uniform bound in the central limit theorem for Banach space valued dependent random variables

Let F be a Banach space with a sufficiently smooth norm. Let (X_i)_i≤n be a sequence in L_F², and T be a Gaussian random variable T which has the same covariance as X = Σ_i≤nX_i. Assume that there exists a constant G such that for s, δ≥0, we have P(sTs+δ)Gδ. (*) We then give explicit bounds of Δ(X) = sup_i|P(|X|≤t)−P(|T|≤t)| in terms of truncated moments of the variables X_i. These bounds hold under rather mild weak dependence conditions of the variables. We also construct a Gaussian random variable that violates (^*).     

Extension of periodic Tchebycheff Systems

Given a periodic Tchebycheff System {y_i}_{i = 0}²ⁿ it is proved that there exist two functions y_{2n + 1}, y_{2n + 2}, such that also the system {y_i}_{i = 0}^{2n + 2} is a periodic T-System.     

Nonhomogeneous spectra of numbers

A simple characterization is given of those sequences of integersM_n={a_i}ⁿ_i=1for which there exist real numbers αandβ such thata_i=?iα+β?(1?i?n). In addition, for givenM_n, an open intervalI_nis computed such that α?I_nif and only ifa_i=?iα+β?(1?i?n)for suitableβ=β(α).     

Solution of systems with Toeplitz matrices generated by rational functions

We consider Toeplitz matrices T_n = (t_i−j)ⁿ_i,j=0, where Σ^∞_−∞t_jz^j is a formal Laurent series of a rational function R(z). A criterion is given for T_n to be invertible, in terms of the nonvanishing of a determinant D_n involving the zeros of R(z), and of order and form independent of n; i.e., n enters into D_n as a parameter, and not so as to complicate D_n as n increases. Explicit formulas involving similar determinants are given for the solution of the system T_nX = Y in the case where T_n is invertible. Formulas are also given for T⁻¹_n in the case where T_n−1 and T_n are both convertible Suggestions concerning possible computational procedures based on the results are included.     

Second-order linearity of the general signed-rank statistic

Let X₁,…, X_n be i.i.d. random variables symmetric about zero. Let R_i(t) be the rank of |X_i − tn^−1/2| among |X₁ − tn^−1/2|,…, |X_n − tn^−1/2| and T_n(t) = Σ_{i = 1}ⁿφ((n + 1)⁻¹R_i(t))sign(X_i − tn^−1/2). We show that there exists a sequence of random variables V_n such that sup_{0 ≤ t ≤ 1} |T_n(t) − T_n(0) − tV_n| → 0 in probability, as n → ∞. V_n is asymptotically normal.     

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.     

Minimal error difference formulas

The usual formula for the r^th difference of f(X), at intervals of h, may introduce an error of 2^rε, where ε is the |error| in f(X). When f(X) is either an exact polynomial of the n^th degree, or very closely approximated by one within a finite interval, say [?1, 1], the r^th difference, at X = X₀, is expressible as ∑ⁿ⁺¹_i=1 a_i f(X_i), where for certain points X_i within [?1, 1], depending upon (X₀, h), ∑ⁿ⁺¹_i=1 |a_i| may be very much less than 2^r. Nodes X_i that minimize ∑ⁿ⁺¹_i=1|a_i| are said to provide “minimal error difference formulas”. For very small h, close approximations to them are obtainable from similar derivative formulas. For other combinations (X₀, h), non-minimal formulas for equally spaced X_i's, with a_i's precomputed to higher accuracy than that in f(X), greatly reduce ∑ⁿ⁺¹_i=1|a_i| from 2^r, ensure its approach to zero with h, and in many cases also yield more decimals and significant figures than the direct differencing of f(X). For r = 1, simple conditions for the non-existence of any expression ∑ⁿ⁺¹_i=1 a_i f(X_i), which improves ∑ⁿ⁺¹_i=1|a_i| to be <2, are given for (X₀, h), expressed as h ≥ h₀ which depends upon X₀ and extrema of Chebyshev polynomials.     

An explicit expression for the cost of a class of Huffman trees

Let T_n denote a binary tree with n terminal nodes V={υ₁,…,υ_n} and let l_i denote the path length from the root to υ_i. Consider a set of nonnegative numbers W={w₁,…,w_n} and for a permutation π of {1,…,n} to {1,…,n}, associate the weight w_i to the node υ_π(i). The cost of T_n is defined as C(T_n∣W)=Min_π∑ⁿ_i=1w_il_π(i).A Huffman tree H_n is a binary tree which minimizes C(T_n∣W) over all possible T_n. In this note, we give an explicit expression for C(H_n∣W) when W assumes the form: w_i=k for i=1,…,n?m; w_i=x for i=n?m+1,…,n. This simplifies and generalizes earlier results in the literature.     

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.