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}$.     

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}$.     

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{)}$.     

Segmental solutions of Boolean equations

Davio and Deschamps have shown that the solution set, K, of a consistent Boolean equation $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{)=0}$ over a finite Boolean algebra B may be expressed as the union of a collection of subsets of Bⁿ, each of the form {(x₁, …, x_n) | a_i≤x_i≤b_i, a_i?B, b_i?B, i = 1, …, n}. We refer to such subsets of Bⁿ as segments and to the collection as a segmental cover of K. We show that $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{) = 1}$ is consistent if and only if ? can be expressed by one of a class of sum-of-products expressions which we call segmental formulas. The object of this paper is to relate segmental covers of K to segmental formulas for ?.     

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.     

Sur une loi de probabilite conditionelle de kleitman

Nous donnons une généralisation et une démonstration très courte d'un théorème de Kleitman qui dit: Pour toute paire d'idéaux $\text{F}$, (β) d'éléments dans le produit cartésien de k ensembles totalement ordonnés P = [1, 2, … n₁] ? … ? [1, 2, … n_k], nous avons ($\text{|}\text{F}\text{|}\text{|P|}$). ($\text{|(β)|}\text{|P|}\text{) ?}\text{|}\text{F}\text{∩ (β)|}\text{|P|}$ ou en langage probabiliste $\text{Pr(}\text{F}\text{? Pr (}\text{F}\text{|(β))}$.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

The minimal number of basic elements in a multiset antichain

Let M be a finite set consisting of k_i elements of type i, i = 1, 2,…, n and let S denote the set of subsets of M or, equivalently, the set of all vectors x = (x₁, x₂,…,x_n) with integral coefficients x_i satisfying 0 ? x_i ? k_i, i = 1, 2,…, n. An antichain

is a subset of S in which there is no pair of distinct vectors x and y such that x is contained in y (that is, there is no pair of distinct vectors x and y such that the inequalities x_i ? y_i, i = 1, 2,…, n all hold). Let $\text{∥Y}\textcolor{red}{}\text{∥}$ denote the number of vectors in S which are contained in at least one vector in

and let $\text{∥B}\textcolor{red}{}\text{∥=∑}{}_{\mathrm{x\in }}\text{(X}{}_1\text{+X}{}_2\text{+?+X}{}_{\mathrm{n}}\text{)}$, the number of basic elements in

. For given m we give procedures for calculating min $\text{∥Y}\textcolor{red}{}\text{∥}$ and min $\text{∥B}\textcolor{red}{}\text{∥}$, where the minima are taken over all m-element antichains

in S.     

Intersection theorems for group divisible difference sets

Let D be an (m,n;k;λ₁,λ₂)-group divisible difference set (GDDS) of a group G, written additively, relative to H, i.e. D is a k-element subset of G, H is a normal subgroup of G of index m and order n and for every nonzero element g of G,?{(d₁,d₂)?,d₁,d₂?D,d₁?d₂=g}? is equal to λ₁ if g is in H, and equal to λ₂ if g is not in H. Let H₁,H₂,…,H_m be distinct cosets of H in G and S_i=D∩H_i for all i=1,2,…,m. Some properties of S₁,S₂,…,S_m are studied here. Table 1 shows all possible cardinalities of S_i's when the order of G is not greater than 50 and not a prime. A matrix characterization of cyclic GDDS's with λ₁=0 implies that there exists a cyclic affine plane of even order, say n, only if n is divisible by 4 and there exists a cyclic (n?1,$\text{1}\text{2}$n?1,$\text{1}\text{4}$n?1)-difference set.     

Asymptotic independence of distributions of normalized order statistics of the underlying probability measure

Let n denote the sample size, and let r_i ∈ {1,…,n} fulfill the conditions r_i ? r_i?1 ≥ 5 for i = 1,…,k. It is proved that the joint normalized distribution of the order statistics Z_ri:n, i = 1,…,k, is independent of the underlying probability measure up to a remainder term of order $\text{O((}\text{k}\text{n}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$. A counterexample shows that, as far as central order statistics are concerned, this remainder term is not of the order $\text{O((}\text{k}\text{n}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ if r_i ? r_i?1 = 1 for i = 2,…,k.     

On maximal antichains consisting of sets and their complements

Let 1 ? k₁ ? k₂ ? … ? k_n be integers and let S denote the set of all vectors x = (x₁, x₂, …, x_n) with integral coordinates satisfying 0 ? x_i ? k_i, i = 1, 2, …, n. The complement of x is (k₁ ? x₁, k₂ ? x₂, …, k_n ? x_n) and a subset X of S is an antichain provided that for any two distinct elements x, y of X, the inequalities x_i ? y_i, i = 1, 2, …, n, do not all hold. We determine an LYM inequality and the maximal cardinality of an antichain consisting of vectors and its complements. Also a generalization of the Erdös-Ko-Rado theorem is given.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

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)}$

.     

Matrix extensions of Liouville-Dirichlet-type integrals

The Dirichlet integral provides a formula for the volume over the k-dimensional simplex ω={x₁,…,x_k: x_i?0, i=1,…,k, s?∑^k₁x_i?T}. This integral was extended by Liouville. The present paper provides a matrix analog where now the region becomes $\text{Ω={V}{}_1\text{,…,V}{}_{\mathrm{k}}\text{: V}{}_{\mathrm{i}}\text{>0, i=1,…,k, 0?∑V}{}_{\mathrm{i}}\text{?t}}$, where now each V_i is a p×p symmetric matrix and A?B means that A?B is positive semidefinite.     

A conjecture of recski in combinatorial set theory

A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ S_i = n and |S_i ∩ S_i| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(n^p+1logn).     

Decomposability of symmetric multilinear functions

Let V denote a finite dimensional vector space over a field K of characteristic 0, let T_n(V) denote the vector space whose elements are the K-valued n-linear functions on V, and let S_n(V) denote the subspace of T_n(V) whose members are the fully symmetric members of T_n(V). If $\text{L}$_n denotes the symmetric group on {1,2,…,n} then we define the projection $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{: T}{}_{\mathrm{n}}\text{(V) → S}{}_{\mathrm{n}}\text{(V)}$ by the formula , where P_σ : T_n(V) → T_n(V) is defined so that P_σ(A)(y₁,y₂,…,y_n = A(y_σ(1),y_σ(2),…,y_σ(n)) for each A?T_n(V) and y_i?V, 1 ? i ? n. If $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, then x₁?x₂? … ?x_n denotes the member of T_n(V) such that $\text{(x}{}_1\text{?x}{}_2\text{· ? ? ?x}{}_{\mathrm{n}}\text{)(y}{}_1\text{,y}{}_2\text{,…,y}{}_{\mathrm{n}}\text{) = П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{x}{}_{\mathrm{i}}\text{(y}{}_{\mathrm{i}}\text{)}$ for each y₁ ,₂,…,y_n in V, and x₁·x₂… x_n denotes $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{(x}{}_1\text{?x}{}_2\text{? … ?x}{}_{\mathrm{n}}\text{)}$. If B? S_n(V) and there exists $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, such that B = x₁·x₂…x_n, then B is said to be decomposable. We present two sets of necessary and sufficient conditions for a member B of S_n(V) to be decomposable. One of these sets is valid for an arbitrary field of characteristic zero, while the other requires that K = R or C.     

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)}$.     

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.     

Inverse Hölder inequalities in one and several dimensions

We study certain functionals and obtain an inverse Hölder inequality for n functions f₁^a1,…,f_n^an (f_k concave, 1 dimension).We also prove a multidimensional inverse Hölder inequality for n functions f₁,…,f_n, where $\text{?}{}^2\text{f}{}_{\mathrm{k}}\text{?x}{}_{\mathrm{i}}{}^2\text{? 0, i = 1,…, d, k = 1,…, n}$.Finally we give an inverse Minkowski inequality for concave functions.